Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

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

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

Трудность задачи зависит от метода исходной расстановки ферзей и составляет O(NN) в случае, когда на всякой строке может стоять только одна фигура, и O(N!), если в всякой строке и столбце находится только один ферзь. число вариантов дозволено сократить еще мощнее, анализируя расположения фигур по диагоналям.
Две королевы в позициях (x1, y1) и (x2, y2) угрожают друг другу по диагонали, если x2 — x1 = |y2 — y1|.

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

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

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

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


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

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

Дозволено придумать различные методы производства потомков. Разглядим две функции:
crossover (скрещивание) на основе 2-х родителей генерирует потомка, тот, что будет содержать только повторяющиеся у родителей значения, остальные позиции заполняются нечаянно, но без раздора по столбцам. Скажем,
родитель I:  (30, 5, 7, 6, 21, 4);
родитель II: (30, 4, 6, 5, 21, 7);
потомок:     (30, 7, 6, 4, 21, 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 раздоров. Если бы нам предварительно не было вестимо условие останова, то было бы затруднительно достичь точного решения. Зачастую бывает, что для трудной задачи сложно составить адекватную функцию ранжирования, следственно отличить локальный минимум от правдивого решения также становится т

Источник: programmingmaster.ru

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB