Искусственный интеллект. Генетический алгоритм и его применения / Offсянка

„Выживает не самый сильный и не самый умный, а тот, кто лучше всех приспосабливается к изменениям.“
Чарльз Дарвин

“Даже если у одного прочитавшего из тысячи появится интерес к этим алгоритмам, и он решит углубиться — это уже отлично.”

Внимание, вопрос: помните ли вы движущие силы эволюции по Дарвину? Эти знания нужны для понимания работы генетического алгоритма, так как он пытается имитировать процессы, действительно происходящие в природе. Итак, основной предпосылкой эволюции является наследственная изменчивость, а её движущими силами — борьба за существование и естественный отбор. Используя генетический алгоритм, вы действуете по сути как творец и сами устанавливаете законы эволюции, позволяющие достичь оптимальности в популяции. В идеале должны выработаться необходимые для выживания и адаптации качества, которые и будут искомым решением. Посмотрим, как реализуются эти принципы в генетическом алгоритме.

⇡#Что это?

Генетический алгоритм (ГА) — это алгоритм поиска и оптимизации, прообразом которого стал биологический принцип естественного отбора.

⇡#Как он работает?

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

Второй этап — подсчёт функции пригодности (приспособленности, fitness function). Данная функция принимает на вводе потенциальное решение проблемы (candidate solution), а выдаёт значение, оценивающее его пригодность. В случае с классическим генетическим алгоритмом целевая функция и функция пригодности — это одно и то же. Далее проверим, выполнено ли условие остановки алгоритма. Алгоритм прекратит исполняться, если достигнуто ожидаемое оптимальное значение, если полученное значение больше не улучшается или по истечении заданного времени/количества итераций. После остановки происходит выбор самой приспособленной хромосомы (по наибольшему значению функции). Если же условие остановки не выполнено, то по результатам естественного отбора будет производиться селекция хромосом для производства потомков.

Третий этап – скрещивание ( в русских источниках — «кроссинговер», реже «кроссовер») и мутация.

Блок-схема генетического алгоритма

Скрещивание, мутация и селекция – это генетические операторы. Как и в природе, вероятность скрещивания на несколько порядков выше вероятности мутации. Скрещивание поддерживает бесконечное разнообразие в популяции, это перераспределение генетического материала родителей, благодаря которому у потомков появляются новые сочетания генов. Но о каких «генах» и «хромосомах» может идти речь вне контекста живой природы? В генетическом алгоритме «хромосома» — набор параметров, определяющих предлагаемое возможное решение, а «ген» — это одна из «букв» строки «хромосомы», как правило, имеющая двоичное значение. Как мы помним, в результате селекции отбираются самые приспособленные хромосомы — к ним и применяются эти генетические операторы. Наверное, вы сейчас думаете, каким же образом может происходить скрещивание у таких «хромосом». Возможно несколько сценариев, упомянем лишь некоторые из них.

Одноточечный кроссинговер (single-point crossover): есть пара родительских хромосом с набором генов L, для них случайным образом выбирается так называемая точка скрещивания P_x– это некая позиция гена в хромосоме. К [1; P_x] одной родительской хромосомы присоединяется [P_x+1; L] другой, и получается первый потомок. Второй потомок получается также скрещиванием, но «в обратную сторону».

Одноточечный кроссинговер

Двухточечный кроссинговер (two-point crossover): обмен генетическим материалом, (то есть, битами) происходит в двух точках скрещивания.

Двухточечный кргоссинговер

Однородный кроссинговер (uniform crossover): значение каждого бита в хромосоме потомка определяется согласно случайно сгенерированной маске кроссинговера. Если в маске стоит 0 – берется ген от первого родителя, если 1 – от второго.

Однородный кроссинговер

Для более глубокого погружения в тему эволюционных алгоритмов реокмендуем изучить статью F.Herrera, M.Losano, A.M.Sanches Hybrid Crossover Operators for Real-Coded Genetic Algorithms: An Experimental Study.

Мутация — генетический оператор, который с некой вероятностью меняет один или несколько «генов» в случайных позициях «хромосомы». Для чего он нужен? Зачем мутации (изменения в генетическом коде) существуют в природе, могут ли они способствовать лучшей выживаемости вида? Эта статья не о генетике, но не будем забывать, что именно она послужила источником вдохновения для Холланда, создателя генетического алгоритма (1975). Потомки, которые подверглись воздействию генетических операторов, образуют новую популяцию – и в ней начинается очередная итерация ГА. Снова идет подсчет функции пригодности, происходит естественный отбор, а дальше алгоритм либо остановится, если заданное условие выполнено, либо вновь перейдет к селекции. Если хочется посмотреть интересное применение, можно почитать разбор задачи коммивояжера (travelling salesman problem) и задачи об укладке рюкзака (knapsack problem) с применением ГА. Обе эти задачи являются задачами комбинаторной оптимизации, то есть в конечном множестве объектов мы ищем оптимальный. Сами того не подозревая, мы решаем подобные задачи каждый день. Теперь посмотрим на преимущества и недостатки этого метода.

Плюсы ГА

Этот алгоритм имеет уникальные сильные стороны:

предлагает на выборнесколько решений, а не одно;
исследует сразу несколько точек, а не одну за другой, благодаря чему целевая функция не упрётся в локальный экстремум;
оптимизация происходит непрерывнопри меняющихся условиях среды, а популяции приходится приспосабливаться;
может предложить удовлетворительное решение для NP-hard проблемы;
допускает параллельные вычисления;
подходит для решения задач с самыми разными параметрами (главное — задать подходящую функцию пригодности).

Минусы ГА

«просто хорошее решение» — это тоже иногда недостаток;
много точек в пространстве поиска – это тоже иногда недостаток;
не всегда удобно представить задачу в терминах генов и хромосом.

⇡#Для каких задач используется ГА?

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

В финансах ГА успешно используется для моделирования экономических агентов с ограниченно рациональным поведением: финансового прогнозирования, инвестирования, и т. д. Одна из интересных задач — оптимизация финансового портфеля (portfolio optimization). В теории игр ГА применяется, например, для разрешения дилеммы узника. Его можно применять в играх с двумя участниками для оптимизации стратегий.

В робототехнике ГА прекрасно применяется для управления человекоподобным роботом, оптимизации планирования маршрута (routing). В авиации — для системы контроля полетов. Кстати об авиации: ученые General Electric и Ренсселеровского политехнического института применили ГА для конструирования турбины реактивного двигателя, который применяется в современных авиалайнерах.

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

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

https://loginom.ru/blog/ga-math

Ещё по применениям ГА на английском языке:

https://www.brainz.org/15-real-world-applications-genetic-algorithms/

Недавно вышла привлекающая внимание книга: Buontempo, Frances. Genetic algorithms and machine learning for programmers: create AI models and evolve solutions. Pragmatic Bookshelf, 2019.

Материалы, которые использовались для написания этой статьи:

Джон Х. Холланд. Генетические алгоритмы. "В мире науки", 1992
Hornby, Gregory, et al. "Automated antenna design with evolutionary algorithms." Space 2006. 2006. 7242.
Darrel Whitley "A Genetic Algorithm Tutorial", 1993.
F.Herrera, M.Losano, A.M.Sanches. "Hybrid Crossover Operators for Real-Coded Genetic Algorithms: An Experimental Study".
Guennoun, Z., and F. Hamza. "Stocks portfolio optimization using classification and genetic algorithms." Applied Mathematical Sciences 6.94 (2012): 4673-4684.
Блок-схема: intuit.ru
Диаграммы кроссовера: geeksforgeeks.org