Решение магического квадрата с помощью генетических алгоритмов: численность населения быстро сходится, но никогда не достигает цели?

Question

Желание узнать больше о GA снова вспыхнуло, и вместо того, чтобы много читать и ничего не делать, я решил начать с другого пути: выбрать проблему и попытаться ее решить.

Я выбрал проблему Магический квадрат . Для кодирования хромосом я использую Кодировка перестановки и следующие методы для Мутация () и NewChild (parent1, parent2, pivot) .

Мой алгоритм выбора немного странный и адаптирован из примеров, найденных в Интернете.

Оценка рассчитывается на основе квадрата разности суммы строк / столбцов / диагоналей и магической константы, , как это .

Что я заметил, так это то, что он очень быстро сходится и перестает улучшаться, как только достигает значения 1,7 (меньше - лучше).

Я вижу это так: он достигает локального оптимума, потенциальная яма , если вы можете так назвать, и не будет перепрыгивать через соседний холм, потому что мутации не отличается достаточно?

Я пытался изменить частоту мутаций 5 - 80%, оставив элитную группу в 10-20% в популяции хромосом, изменив размер популяции с 16-32 хромосом, но не повезло.

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

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

Обновление: Вот как выглядит скорость сходимости для куба размером 5 с частотой кроссовера 60% и частотой мутаций 10%:

Answer 1

На этот вопрос нет точных и быстрых ответов, но я бы посоветовал снизить ваш элитарность не более чем на 5% и увеличить численность населения.Я не совсем понимаю, как работает ваш вызов getPermutation () для выбора потенциальных кандидатов, но я бы также увеличил размер вашего турнира (строки 8-16 в вашем алгоритме выбора) по мере увеличения численности населения.Если вы застряли в локальной оптиме, это означает, что либо ваша функция мутации не прыгает достаточно далеко, либо у вас недостаточно разнообразия в вашей популяции для начала.

Надеюсь, это поможет, удачи!

Answer 2

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