Несколько повторений выбора турнира в генетическом алгоритме

Question

Эй, ребята, я немного смущен тем, как работает несколько итераций выбора турнира.

Я знаю, что вы начинаете выбирать случайные пары (или k членов) и помещать победителя в спаривающийся пул. Вы продолжаете делать это до заполнения пула спаривания.

Однако я не уверен, что произойдет потом.

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

Спасибо.

Answer 1

Традиционно после победы победителей турнира они образуют следующее поколение. Все процессы мутации, отбора и т. Д. Продолжаются после этого в циклах.

Answer 2

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

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

Вы можете использовать случайное спаривание, но это даст вам «худшие» решения - хуже, потому что вы понятия не имеете, производят ли они лучшего человека или нет. Это все равно будет хорошим решением, и когда я начал писать эти алгоритмы, я всегда использовал случайное спаривание, но сразу после получения нового человека из двух старых я сравнивал производительность 3 и отбрасывал худшее, заканчивая 2 родителя иногда (и отбрасывание 1-го-старого ребенка), или в конечном итоге с 1 родителем и 1 ребенком.

Но если вы знаете, как объединить людей так, чтобы они дали лучшее решение (и это может быть очень сложно), вы можете использовать функцию сродства, которая принимает двух человек и возвращает сродство между ними. Трудная часть заключается в определении близости. В зависимости от проблемы, это может быть совсем иначе. Например, если я беру проблему коммивояжера, у меня есть лучшие решения, когда вы спариваете человека с меньшим сходством. Таким образом, моя функция близости возвращает 1 - сходство.

Таким образом, я мог бы уменьшить количество итераций на 80% и получить очень хорошие решения.

Но имейте в виду, что чем больше ваш пул, тем дольше будет выполняться функция близости, функции близости могут быть O (n²) или даже O (n³), в каких случаях это может быть узким местом вашего алгоритма. В этом случае лучше использовать случайное спаривание.

В заключение, случайное спаривание хорошее - в конце концов, мы можем сказать, что это работает в реальной жизни, но если вы знаете, как вычислить близость между двумя людьми, вы можете использовать его для уменьшения числа итераций вам нужно будет получить хорошее решение. Имейте в виду, что сродство к вычислению может быть очень сложным (и я даже предполагаю, что вычисление наилучших аффинностей для данного пула NP-Complete).

Answer 3

Это не хороший совет, но ...

Однако, я не уверен, что произойдет после этого.

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

Как кто-то еще на этом форуме указал: грязный маленький секрет об GA - то, что это больше искусства, чем науки.

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