Генетические алгоритмы (ГА) пытаются подойти к решению проблем так, как это делают природа и эволюция. Наиболее приспособленные особи отбираются для размножения, чтобы произвести потомство следующего поколения. В этой статье мы попытаемся решить головоломку с 8 ферзями, используя одну из них в образовательных целях. 8 ферзей — это классическая задача-головоломка о размещении восьми шахматных ферзей на шахматной доске 8x8 так, чтобы никакие два ферзя не угрожали друг другу. Таким образом, никакие два ферзя не должны находиться в одном ряду, столбце или диагонали.

Подход, который мы будем использовать при решении проблемы 8 ферзей. Во-первых, мы будем искать комбинацию списка, которая дает нулевую стоимость функции стоимости, что означает, что ни один ферзь не атакует другого ферзя.

Мы предполагаем, что каждый ферзь принадлежит отдельному ряду, иначе они бы уже атаковали друг друга. Например, шахматная доска справа будет расшифрована как [3,1,6,2,5,7,4,0] . Наша цель — найти одну такую ​​перестановку.

Аналитически процесс включает в себя следующие этапы:

  • Инициализация: создается популяция подходящего размера подходящей длины. Размер популяции не должен быть слишком большим, так как это может привести к замедлению GA, а меньшей популяции может быть недостаточно для хорошего брачный пул. Поэтому оптимальный размер популяции необходимо определять методом проб и ошибок.
  • Выбор: он включает в себя выбор подмножества лучших результатов из текущей совокупности, то есть исходов с 8 ферзями, которые имеют функцию минимальной стоимости. В нашем случае мы сохраним 20% населения.
  • Кроссовер: выбирая это подмножество, мы каждый раз случайным образом выбираем 2 из этих слов и пересекаем их. Выбрав случайную длину из 0,8, которая является длиной состояний королевы, мы возьмем первый бит первого слова и соединим его со вторым словом второго бита.

На изображении ниже показано, что происходит:

  • Мутация: Мутация проявляется небольшим случайным изменением в сочетании особей. Эта мутация происходит один раз с небольшой вероятностью. В нашем случае это 30% времени.

Нижеприведенное не делает ничего, кроме описанного выше в одной процедуре:

Наконец, для того, чтобы все работало, необходимо представление класса EightQueensState:

Двойной цикл for для каждой шахматной позиции, как показано ниже, визуализирует наше решение:

Итак, теперь наш алгоритм работает. Но давайте улучшим его, сделав несколько дополнительных шагов и расширив наше приложение:

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

Мы попытались использовать OX1 для получения более быстрых результатов. То, что мы сделали в нашей новой кроссоверной функции, включает в себя следующие шаги.

  1. Создайте две случайные точки пересечения в первом родителе, скопируйте отрезок между ними от первого родителя к потомку.
  2. Начиная со второй точки пересечения во втором родителе, скопируйте оставшиеся неиспользуемые числа из второго родителя в первый дочерний элемент, обернув список.
  3. Сделайте то же самое для второго ребенка, при этом первый родитель теперь будет вторым, и наоборот.
  4. Поскольку сохранение одной и той же функции мутации или ее стирание либо нарушает работу приложения, потому что у нас будет более одного вхождения одного и того же числа, и это нарушит реализацию OX1, либо очень быстро сойдется при получении стека при попытке найти комбинацию, где она не существует. Мы реализовали функцию мутации, которая каждые 30% времени просто вводит случайную перестановку нового человека.

Пример кроссовера Дэвида [2]

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

Добавление графика и статистики для среднего, среднего, дисперсии, максимума и минимума даст нам представление о том, насколько хорошо мы справились.

На этом графике показаны наши начальные времена:

Расширенная версия наглядно показывает значительное увеличение эффективности алгоритма.

Полный проект находится на GitHub https://github.com/nikkaramessinis/Genetic-Algorithm.

Если вам понравился контент, рассмотрите подписку на Ника Карамессиниса или https://www.buymeacoffee.com/nikaramesinis. Для любых исправлений или дополнений вы более чем можете оставить комментарий для дальнейшего обсуждения.

Рекомендации

[1] Искусственный интеллект: современный подход, третье издание. (н.д.).

[2]Генетический алгоритм: задача 8 ферзей | Ченг Си Цзоу | ботаник для техники | Средний. (н.д.). Получено 18 января 2022 г. с сайта

https://medium.com/nerd-for-tech/genetic-algorithm-8-queens-problem-b01730e673fd

[3] Генетические алгоритмы — Краткое руководство. (н.д.). Получено 18 января 2022 г. с https://www.tutorialspoint.com/genetic_algorithms/genetic_algorithms_quick_guide.htm.