Получение конвергенции слишком рано в GA

Question

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

Я использовал выбор 2-турмената и заказал кроссовер. Я попытался установить разный размер населения, размер турнира и скорость мутации, но это не помогло! Где проблема? Прошла неделя, и я застрял в том же прогрессе.

Любое предложение?

Answer 1

Возможно, вы быстро сходитесь на локальных максимумах; это неотъемлемая проблема генетических алгоритмов. Обычно вы можете обнаружить такое состояние по длительным периодам поколений без какого-либо прогресса.

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

Answer 2

В общем, если ваш GA сходится слишком быстро Есть несколько вещей, которые нужно посмотреть на:

• Устанавливается ваша мутация/частота кроссовера надлежащим образом? Если это слишком мало, ваше население застаивается довольно быстро.
• Является ли ваш показатель производительности чувствительным? Если метрика плохо откалибрована, вы получаете слишком высокое преимущество для одной группы, которая быстро будет доминировать в генофонде.
• Вы используете достаточно случайных данных? Если вы имеете дело с очень маленьким пространством для решения проблемы, вероятно, нет смысла использовать GA, и если вы это сделаете, вы в конечном итоге сходитесь очень быстро.
• Действительно ли ваша реализация правильна? Очень легко ввести некоторые тонкие логические ошибки, которые очень трудно найти. Я бы предложил пройти через поколение с отладчиком и убедиться, что ключевые моменты действуют так, как вы предполагаете.

При этом десять поколений не являются абсолютно необоснованными. Я бы посоветовал убедиться, что что-то действительно не так с вашей работой, прежде чем утверждать, что что-то не так с вашей ГА.