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

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

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

Две королевы в позициях (x1, y1) и (x2, y2) угрожают друг другу по диагонали, если x2 — x1 = |y2 — y1|.

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

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

  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 потоках приведены в таблице (медиана в пяти испытаниях).

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 конфликтов. Если бы нам заранее не было известно условие останова, то было бы затруднительно достичь точного решения. 

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

Заключение

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

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

 

 
 


генетические алгоритмы методы искусственного интеллекта
Если у вас есть статья, заметка или обзор, которыми вы хотите поделиться с аудиторией нашего сайта, присылайте информацию на: neuronus.com@yandex.ru.
Гость, оставишь комментарий?
Имя:*
E-Mail:


Свежее новое
  • Раскрыли новые детали «межзвездной» миссии NASA
  • Американский проект Interstellar Probe можно будет начать осуществлять на практике уже в 2030 году, заявляют ученые. Это межзвездная миссия NASA,
  • Ученые выяснили, что древняя мумия кошки оказалась «с секретом»
  • Французские эксперты исследовали мумию древнеегипетской кошки с помощью современных методик, не повредив ее. Сканирование показало, что внутри
  • Ученые нашли самый простой способ борьбы с глобальным потеплением: убрать мясо и есть овощи
  • Проблема глобального потепления остается главной климатической угрозой последних лет. Эксперты, в том числе и ученые, сотрудничающие с ООН,
  • Очередной дефект на космодроме «Восточный» признали критическим
  • На сайте госзакупок появилась информация об очередных недочетах в строительстве новых объектов космодрома «Восточный». На этот раз, говорят
  • Российский солнечный парусник станет самым быстрым космическим кораблем в мире
  • В Самарском университете приступили к разработке солнечного парусника. Аппарат станет самым скоростным космическим кораблем в мире.
Последние комментарии
Почему специалисты считают, что Ту-334 «тупиковый» и не сравнится с SSJ-100
Основная претензия с SSJ в интернете - это что там нет украинских комплектующих. В результате авиационная промышленность Украины оказывается в одном
Эксперты считают, что «золотой» астероид серьезно навредит мировой экономике
Бесплатного - нет. А дешевого - вполне. Это поднять с поверхности Земли 1кг дорого. А транспортировать его с орбиты Сатурна до орбиты Земли не так уж
Эксперты считают, что «золотой» астероид серьезно навредит мировой экономике
Разве что если отбуксировать метеорит на Землю.. вроде имело бы смысл
Откуда взялась нефть на Земле
Ещё в прошлом веке доказали, что нефть имеет минеральное происхождение! Так как её слишком много на Земле. И чем глубже, тем её больше. Никакой
Эксперты считают, что «золотой» астероид серьезно навредит мировой экономике
Допустим, найдете планету из чистого золота, в поясе Койпера. Подсчитайте транспортные расходы по доставке 1 кг груза, ракета летит туда- обратно.
Мы в социальных сетях
Статистика
1  
Всего статей 2212
0  
Всего комментариев 532
0  
Пользователей 149