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

Question

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

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

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

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

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

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

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

Любой подсказку было бы полезно.

Answer 1

Существует много способов сделать это, но не идеальны.

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

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

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

Answer 2

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

У меня есть два матча А (содержит 50 семей) и В (содержат 50 семей), каждую семью, представленного размером кортежа 3 { WomanId,ManId,DogId }

кроссовера выглядят следующим образом:

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

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

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

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

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

Answer 3

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

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