Алгоритм 8 ферзей скачать

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

Генетический алгоритм. Целевая функция и выбраковка плохих решений. Решения задачи представим в виде кортежа размерности 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 конфликтов. Если бы нам заранее не было известно условие останова, то было бы затруднительно достичь точного решения. Часто бывает, что для сложной задачи непросто составить адекватную функцию ранжирования, поэтому отличить локальный минимум от истинного решения также становится тяжело. Заключение. Алгоритм критичен к быстродействию функции скрещивания, к ее выбору нужно подходить тщательно.

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