Как найти оператор кроссовера для генетического алгоритма?

Раскрытие информации: Да, это моя домашняя работа.

У меня следующая проблема: у меня 50 мужчин, 50 женщин и 50 собак. Каждый из них имеет список своих фаворитов каждого из других. Например, у женщины номер 6 есть список из 50 ее любимых мужчин, отсортированный от наименее любимых до самых любимых, и список ее 50 любимых собак, отсортированный от наименее любимых до самых любимых. У мужчин есть списки для женщин и собак, а у собак есть списки для женщин и мужчин.

Мне нужно найти наилучшую пару, чтобы женщины, мужчины и собаки были максимально счастливы. Мне нужно сделать это с помощью генетических алгоритмов.

Допустим, у меня есть совпадения A и B (где я сопоставляю все 150 сущностей с 50 семьями, поэтому каждая женщина/мужчина/собака появляется только один раз).

Как совместить А и Б? Каждый кроссовер, о котором я мог подумать, приводит меня к следующей проблеме: кто-то появится дважды, а кто-то не появится вообще.

Например, если я случайным образом выберу X между 1 и 50 и возьму первые X семей из A и 50-x вторых семей из B, вероятность того, что новое совпадение является законным, и все появятся только один раз, равна примерно 0.

Как мне подойти к такой проблеме?

Любая подсказка будет полезна.


algorithm genetic-algorithm evolutionary-algorithm
person OopsUser    schedule 22.12.2013    source источник
comment
Что вы имеете в виду под генетическими алгоритмами?   -  person A. I. Breveleri    schedule 23.12.2013

Ответы (3)


arrow_upward
1
arrow_downward

Есть много способов сделать это, и ни один из них не идеален.

A и B могут по очереди предлагать семьям C. Поскольку C начинает с пула из 50 свободных мужчин, 50 свободных женщин и 50 свободных собак, он может сформировать первую предложенную семью. Если предложенной семье требуется член, скажем, собака, которая уже состоит в семье, новая семья может выбрать собаку случайным образом из пула свободных собак.

A может добавить набор из, скажем, 10 семейств в C, а затем B может внести свой вклад в любое из своих семейств, все еще жизнеспособное в C (то есть совместимые с 10 из A). Оставшиеся мужчины, женщины и собаки образовывали семьи случайным образом.

C может унаследовать пары мужчина-женщина A и пары женщина-собака B без каких-либо конфликтов.

person Beta    schedule 22.12.2013
comment
Спасибо за ответ, но я не уверен, что законно на этапе кроссовера случайным образом выбирать вещи, которые я не мог унаследовать от своих родителей. семья, например), но когда у меня нет подходящего гена для наследования, я не думаю, что можно просто случайным образом генерировать другие гены. Случайность возникает после кроссовера на стадии мутации. Я не говорю, что ваше предложение не сработает, скорее всего, сработает, но я не уверен, что это законный генетический алгоритм. - person OopsUser; 24.12.2013
comment
Что вы имеете в виду законно? И вы уверены, что хотите определить gene как семью? - person Beta; 25.12.2013

arrow_upward
0
arrow_downward

Нашел одно решение проблемы, может кому поможет в будущем. Я должен признать, что это немного похоже на «взлом», но это абсолютно законно.

У меня есть два совпадения A (содержит 50 семейств) и B (содержит 50 семейств), каждое семейство представлено кортежем размером 3 { WomanId,ManId,DogId }

Кроссовер выглядит так:

  • отсортируйте A и B по womanId, теперь в семействе номер i в A и в семействе номер i в B WomanId =i
  • Скопируйте A в дочерний вектор C
  • Замените собак в C собаками в B

Происходит следующее: C наследует пары «Женщина-Мужчина» от A, а пары «Женщина-Собака» от B.

Просто для полноты вы не всегда сортируете по WomanId, вы выбираете случайным образом женщину, мужчину, собаку, а затем случайным образом копируете остальные из A или B.

Это действительно работает (я также добавил мутации), я случайным образом сгенерировал 1000 совпадений и запустил алгоритм, число — это стоимость лучшего совпадения, которое я смог найти в текущем поколении.

введите здесь описание изображения

Стоимость - это просто сумма рангов каждой женщины/мужчины/собаки членов его семьи (чем ниже ранг, тем лучше)

person OopsUser    schedule 24.12.2013

arrow_upward
0
arrow_downward

Поскольку вы уже нашли решение, я хочу дать вам еще одну идею для исследования и сравнения, если вы хотите углубить свое понимание этого задания.

Вы можете представить его тремя перестановками размера 50, каждая из которых представляет принадлежность женщины, мужчины и собаки к определенному семейству. Это первая запись в каждой перестановке, представляющая, какие женщина, мужчина и собака образуют семью и так далее. В каждой перестановке каждое число встречается только один раз, и поэтому каждая женщина, мужчина или собака относятся только к одной семье. Затем вы можете использовать, например. частично согласованный кроссовер (PMX), который вы применяете ко всем перестановкам либо с одинаковыми контрольными точками, либо независимо друг от друга. В мутации вы можете поменять местами двух или более мужчин/женщин/собак и, таким образом, назначить их в разные семьи.

person Andreas    schedule 29.12.2013