На шахматной доске размера N x N нужно расставить N ферзей так, чтобы они не угрожали друг другу. Поиск с возвратом — стандартный метод решения для небольших N. Ниже рассмотрен генетический алгоритм позволяющий находить решение для N порядка нескольких тысяч.
Сложность задачи зависит от способа начальной расстановки ферзей и составляет O(NN) в случае, когда на каждой строке может стоять только одна фигура, и O(N!), если в каждой строке и столбце находится только один ферзь. Количество вариантов можно сократить еще сильнее, анализируя положения фигур по диагоналям.
Две королевы в позициях (x1, y1) и (x2, y2) угрожают друг другу по диагонали, если x2 — x1 = |y2 — y1|.
Методы такого рода основаны на трех биологических принципах: отбор, скрещивание и мутация. Потенциальные решения представляют собой отдельные 'особи', которые ранжируются целевой функцией для селекции наиболее приспособленных (близких к требуемому решению).
Общая схема генетического алгоритма:
Решения задачи представим в виде кортежа размерности 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 потоках приведены в таблице (медиана в пяти испытаниях).
N |
Функция crossover |
Функция gemmation |
||
Время работы, с. |
Поколений, тыс. шт. |
Время работы, с. |
Поколений, тыс. шт. |
|
500 | 663 | 43,6 | 69 | 10,3 |
1000 | 4269 | 94,7 | 233 | 24,8 |
2500 | 67180 | 297,3 | 1780 | 53,5 |
5000 | Не тестировалось | 87569 | 227,6 |
Функция gemmation
потребляет меньше ресурсов и обеспечивает более быструю сходимость к решению. Использование генератора Мерсенна в crossover
все равно не позволило приблизиться к быстродействию функции размножения gemmation
как по времени, так и по количеству поколений. Их число растет экспоненциально с увеличением N.
Скорость работы отличается более, чем в два раза с учетом количества итераций, а в абсолютном исчислении почти в десять раз даже для N=500. Предположу, что чтение из /dev/random
позволит улучшить быстродействие. Что интересно, более сложная функция размножения находит решение за большее число итераций.
Алгоритм хорошо параллелится, что подтверждает рисунок рядом (синий — crossover
; зеленый — gemmation
). Но на ускорение оказывает большое влияние функция размножения: для gemmation
наблюдается почти линейный рост ускорения. А crossover
этого не показывает, т.к. постоянная генерация новых положений и проверка подходит ли оно для данной 'особи' занимает значительное время. От решения к решению время на эту операцию различно, поэтому логично предположить, что некоторые потоки быстрее обрабатывают свою часть популяции. Если же для цикла с функцией crossover
изменить порядок получения потоками итераций на исполнение (клауза schedule(dynamic)
, голубым цветом на графике), то ускорение увеличится и почти достигнет уровня функции gemmation
.
На примере N=2500 рассмотрим проблему сходимости (рисунок справа). Почти половина всех итераций тратится на то, чтобы убрать последние 30 конфликтов. Если бы нам заранее не было известно условие останова, то было бы затруднительно достичь точного решения.
Часто бывает, что для сложной задачи непросто составить адекватную функцию ранжирования, поэтому отличить локальный минимум от истинного решения также становится тяжело.
Буду рад замечаниям и дополнениям.