Генетический алгоритм судоку - оптимизирующая мутация

Question

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

Краткий обзор алгоритма

Фитнес-функция

Подсчитывает количество уникальных значений чисел от 1 до 9 в каждом столбце, строке и подполе 3 * 3. Каждое из этих уникальных значений в подмножествах суммируется и делится на 9, в результате чего получается плавающее значение между 0 и 1. Сумма этих значений делится на 27, обеспечивая общее значение пригодности в диапазоне от 0 до 1. 1 указывает на решенную задачу.

Численность населения: 100

Выбор:

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

Размножение: Две случайно выбранные хромосомы / доски обменивают случайно выбранный поднабор (строка, столбец или 3 * 3 подмножества). Выбор подмножества (какой ряд, столбец или поле) является случайным. Полученные доски вводятся в популяцию.

Коэффициент воспроизводства: 12% населения за цикл На одну итерацию приходится шесть репродукций, что приводит к 12 новым хромосомам за цикл алгоритма.

Мутация: мутация происходит с частотой 2% населения после 10 итераций без улучшения наивысшей приспособленности. Ниже перечислены три метода мутации, которые имеют различный вес вероятности отбора.

1: поменять местами случайно выбранные номера. Метод выбирает два случайных числа и обменивает их по всей доске. Этот метод, по-видимому, оказывает наибольшее влияние на рост на ранних стадиях алгоритма роста. 25% шанс выбора

2: ввести случайные изменения: случайным образом выбрать две ячейки и изменить их значения. Этот метод, кажется, помогает предотвратить схождение алгоритма. % 65 шанс выбора

3: подсчитать количество каждого значения на доске. Решенная доска содержит число 9 от каждого числа от 1 до 9. Этот метод берет любое число, встречающееся менее чем 9 раз, и случайным образом заменяет его числом, встречающимся более чем 9 раз. Это, кажется, положительно влияет на алгоритм, но используется только в редких случаях. % 10 шанс выбора

Мой главный вопрос: с какой скоростью мне применять метод мутации? Кажется, что по мере увеличения мутации у меня быстрее начальные результаты. Однако, как результат приближается к правильному результату, я думаю, что более высокая скорость изменений привносит в популяцию слишком много плохих хромосом и генов. Тем не менее, с более низкой скоростью изменения алгоритм, кажется, сходится слишком рано.

Последний вопрос: есть ли лучший подход к мутации?

Answer 1

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

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

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

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

С элитарностью вы можете использовать немного более высокую частоту мутаций. Все три ваших оператора кажутся полезными. (Обратите внимание, что # 3 на самом деле является формой локального поиска, встроенного в ваш генетический алгоритм. Это часто огромный выигрыш с точки зрения производительности. Вы могли бы фактически расширить # 3 в гораздо более сложный метод, который повторяется до он не мог понять, как сделать дальнейшие улучшения.)

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

Answer 2

Я однажды сделал довольно компетентный решатель судоку, используя GA.Блоги о деталях (включая различные представления и мутации) здесь: http://fakeguido.blogspot.com/2010/05/solving-sudoku-with-genetic-algorithms.html