Привет! Сегодня мы с вами обсудим один замечательный алгоритм и с его помощью спроектируем решение проблемы построения цепочки действий.

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

Генетический алгорим (далее ГА) — это метаэвристический (metaheuristic) универсальный (general-purpose) алгоритм.

Метаэвристические алгоритмы — это мощнейший, популярный класс оптимизационных методов, сила таких алгоритмов в способности решения сложных задач без знания пространства поиска. Фактически такие алгоритмы ищут случайным образом решение и останавливаются при достижении какого-либо условия или числа операций. Иногда можно доказать, что найденное решение близко к оптимальному, но на практике, оптимальное решение нужно далеко не всегда. Вот неполный перечень метаэвристических алгоритмов: алгоритм оптимизации муравьиной колонии, эволюционные вычисления, включая ГА, итеративный локальный поиск, метод имитации отжига, алгоритм поиска с запретами и другие.

Алгоритм считается универсальным (общего назначения), если вы можете взять различные задачи и реализовать с его помощью решение.

Генетический алгоритм основывается на процессе эволюции и трёх основных процессах: селекция (выбор лучших особей), скрещивание (выбор двух случайных особей и смешивание их) и мутации (случайные изменения особей).

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

 

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

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

Будьте готовы, что теория иногда разнится в терминах.

Проблема

Представим, что у нас есть проблема: мама отправляет за хлебом, нужно встретиться с друзьями, магазин закрывается рано, а еще нужно успеть погулять с девочкой. Вероятно, вы думаете, что такие проблемы никого не волнуют, но если вы вспомните каково это быть подростком, то думаю, что проблема вполне реальна. Также в качестве входных данных нам дается матрица весов. Если мы проиндексируем наши действия, как 0 (сходить за хлебом), 1 (встретиться с друзьями) и 2 (погулять с девочкой), то получится следующая матрица весов. Индекс строки будет означать, что действие выполнится первым, а индекс столбца — это действие которое будет выполнено следом.

Содержимое клеток означает следующее:

• позитивное значение — действие желательно пропорционально значению;
• негативное значение — действие нежелательно пропорционально значению;
• 0 — действие может быть выполнено без какого-либо оттенка;
• «-» — действие не допустимо.

    0     1     2
------------------
0|  -   -0,5   -1
1|  0     -    0.5
2|  0    0.5    -

Взглянем на матрицу. Выполнить тоже самое действие невозможно (см. на главную диагональ). Судя по первому столбцу, после любого действия допустимо пойти за хлебом (индекс 0), но мы знаем об ограничении, что магазин работает не долго и покупка хлеба не может быть концом цепочки действий. При этом, судя по первой строке, покупка хлеба первым действием всегда имеет оттенок нежелательности.

Решение

Спроектируем решение с помощью генетического алгоритма. Как вы уже знаете нам нужно создать случайную популяцию, но что будет считаться индивидом? Нам необходимо построить наилучшим образом цепочку действий, т.е. чтобы сумма коэффициентов из матрицы с весами была максимальна. Индивидом в нашем случае является последовательность действий, т.е. каждый генотип содержит одну хромосому, которая будет иметь 3 гена, которые и представляют из себя цепочку. Например, индивид с генотипом с одной хромосомой, который содержит последовательность генов «1, 2, 0» представляет из себя решение «встретиться с друзьями -> встретиться с девочкой -> сходить за хлебом».

Как оценить такое решение? Для этого нам нужно определить целевую функцию (в генетическом алгоритме она называется функцией приспособленности). Простым языком, это функция, результат которой дает нам представление о том на сколько хорош о наше решение (особь). В нашем случае, целевая функция это сумма весов переходов. Мы должны обойти последовательность и в результате переход 1->2 дает 0.5, а 2->0 дает 0, итого, в сумме целевая функция дает значение 0.5.

Селекция

Как вы понимаете, теперь мы умеем оценивать «лучших» особей, однако, подходов к селекции всё равно много. Простейший способ выбрать лучших — отсортировать особей по значениям целевой функции и выбрать N штук с наибольшим значением. Такой селектор называется Truncation Selector. Еще один интересный и популярный экземпляр это Tournament Selector. Всё зависит от решаемой задачи. Как вы понимаете, после селекции в популяции следующего поколения остается свободное место и, в зависимости от подхода, новое поколение может быть наполнено либо дубликатами лучших особей, либо случайными особями. Я нашел интересную статью в которой разбираются 6 популярных методов для селекции. Вы сможете скачать эту статью по ссылке.

Скрещивание

Для операции скрещивания также существует множество подходов. В англоязычной википедии есть не плохое описание некоторых из них (ссылка). Для рассматриваемого случая с цепочкой действий один из лучших подходов к скрещиванию называние Cycle Crossover. Как он работает? Когда мы скрещиваем две особи в их генотипах мы находим общий цикл и сохраняем его для потомков, а вот гены не задействованные в циклах меняются местами. Для цепочек из трёх генов такой подход, конечно бесполезен, как и не оправдано использование этого алгоритма, но всё же. В тот момент, когда я пытался осознать этот способ скрещивания лучше всего мне помогло вот это видео на YouTube:

Cycle Crossover

 

Мутация

В нашем случае мутация это случайный обмен случайных позиций для двух генов, т.е. это обычная смена последовательности. Здесь даже объяснения не нужны: была хромосома 1—2-0, мы сделали обмен для 0 и 1 позиции (ранее случайно определенных) и получили мутировавшую хромосому 2—1-0. Обычно, вероятность мутации сильно ниже вероятности скрещивания.

Реализация

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

Я подскажу вам одну отличную библиотеку для Java, которой сам пользовался: jenetics.

Примеры работы с такой библиотекой вы можете найти в документации к ней, либо вот здесь.

Реализовать решение задачи, которую мы рассматривали в ходе статьи довольно просто и если у вас действительно есть желание, то это будет исходной точкой для вас (домашним заданием). Все данные на руках, задача описана, вперед!

При подготовке к статье в качестве теоретических оснований я использовал: http://tvim.info/files/56_72_Shcherbina.pdf

Автор: Roman Brovko