Генетический алгоритм для задачи о N ферзях

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

Сложность задачи зависит от способа начальной расстановки ферзей и составляет O(N^N) в случае, когда на каждой строке может стоять только одна фигура, и O(N!), если в каждой строке и столбце находится только один ферзь. Количество вариантов можно сократить еще сильнее, анализируя положения фигур по диагоналям.

Две королевы в позициях (x₁, y₁) и (x₂, y₂) угрожают друг другу по диагонали, если x₂ — x₁ = |y₂ — y₁|.

Генетический алгоритм

Методы такого рода основаны на трех биологических принципах: отбор, скрещивание и мутация. Потенциальные решения представляют собой отдельные 'особи', которые ранжируются целевой функцией для селекции наиболее приспособленных (близких к требуемому решению).
Общая схема генетического алгоритма:

1. Генерируется случайная популяция 'особей'-решений задачи. Все решения ранжируются целевой функцией.
2. Худшие решения заменяются решениями-потомками, которые появляются в результате скрещивания лучших 'особей'. К потомкам применяется функция мутации.
3. Новая популяция вновь оценивается и процесс повторяется.

Целевая функция и выбраковка плохих решений

Решения задачи представим в виде кортежа размерности N: индекс — это строка, в которой стоит фигура, а значение — это номер столбца.
Например, для N=8 решение (4, 0, 3, 5, 7, 1, 6, 2) показано рядом на рисунке.
В качестве 'особей' исходной популяции будем генерировать только такие решения, у которых нет конфликтов по горизонталям и вертикалям. Функция ранжирования hits будет подсчитывать количество конфликтов по диагоналям для каждого решения. Чем выше ее значение, тем хуже 'особь'. Заменим решения, для которых значение целевой функции больше медианы всего поколения. Т.е. на каждой итерации популяция будет обновляться примерно на половину.

Функции скрещивания

Можно придумать разные способы производства потомков. Рассмотрим две функции:
crossover(скрещивание) на основе двух родителей генерирует потомка, который будет содержать только повторяющиеся у родителей значения, остальные позиции заполняются случайно, но без конфликта по столбцам. Например,
родитель I:  (3, 0, 5, 7, 6, 2, 1, 4);
родитель II: (3, 0, 4, 6, 5, 2, 1, 7);
потомок:     (3, 0, 7, 6, 4, 2, 1, 5).
Преимущество этой функции заключено в обмене 'генетическим' материалом, но, из-за постоянной генерации новых значений в потомке, работать она будет не сильно быстро.
gemmation (почкование) на основе одного родителя генерируется потомок, в котором случайным образом два элемента поменяны местами. Например,
родитель: (3, 0, 5, 7, 6, 2, 1, 4);
потомок:  (1, 0, 5, 7, 6, 2, 3, 4).
Такая функция будет работать быстрее crossover, но она практически реализует клонирование ('генетический' материал меняется мало).

Функция мутации

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

Тестирование

Популяция состоит из 75 особей, вероятность мутации 3%. В качестве генератора псевдослучайных чисел использован Mersenne twister (mt19937). Программа распараллелена с помощью OpenMP (этапы генерации первого поколения, ранжирования и скрещивания). Результаты тестов на 8 потоках приведены в таблице (медиана в пяти испытаниях).

Функция gemmation потребляет меньше ресурсов и обеспечивает более быструю сходимость к решению. Использование генератора Мерсенна в crossover все равно не позволило приблизиться к быстродействию функции размножения gemmation как по времени, так и по количеству поколений. Их число растет экспоненциально с увеличением N. 

Скорость работы отличается более, чем в два раза с учетом количества итераций, а в абсолютном исчислении почти в десять раз даже для N=500. Предположу, что чтение из /dev/random позволит улучшить быстродействие. Что интересно, более сложная функция размножения находит решение за большее число итераций.

Алгоритм хорошо параллелится, что подтверждает рисунок рядом (синий — crossover; зеленый — gemmation). Но на ускорение оказывает большое влияние функция размножения: для gemmation наблюдается почти линейный рост ускорения. А crossover этого не показывает, т.к. постоянная генерация новых положений и проверка подходит ли оно для данной 'особи' занимает значительное время. От решения к решению время на эту операцию различно, поэтому логично предположить, что некоторые потоки быстрее обрабатывают свою часть популяции. Если же для цикла с функцией crossover изменить порядок получения потоками итераций на исполнение (клауза schedule(dynamic), голубым цветом на графике), то ускорение увеличится и почти достигнет уровня функции gemmation.

На примере N=2500 рассмотрим проблему сходимости (рисунок справа). Почти половина всех итераций тратится на то, чтобы убрать последние 30 конфликтов. Если бы нам заранее не было известно условие останова, то было бы затруднительно достичь точного решения. 

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

Заключение

1. Алгоритм критичен к быстродействию функции скрещивания, к ее выбору нужно подходить тщательно.
2. Мутация важна не так сильно, т. к. конструктивно почти невозможно попасть в локальный минимум.
3. Использование генетического алгоритма не гарантирует нахождение решения, даже, если доказано его существование (но здесь удалось расставить фигуры во всех случаях). Когда требуется найти все возможные решения этой задачи, то генетический алгоритм становится практически бесполезным.

Буду рад замечаниям и дополнениям.