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

Что это такое

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

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

Программирование на компьютере

Псевдокод выглядит следующим образом:

1. Инициализация: Создаются некоторые возможные решения; очень часто они имеют случайные значения
2. Оценка: Функция пригодности оценивает каждое решение; оценка представляет собой число, которое говорит о том, насколько хорошо это решение решает проблему.
3. Следующие шаги выполняются до тех пор, пока не будет выполнено требование об остановке:
1. Выбор: Выбор решений/индивидуумов для следующей итерации
2. Рекомбинация: Объедините выбранные решения
3. Мутация: Случайное изменение вновь созданных решений
4. Оценка: Примените фитнес-функцию, см. шаг 2.
5. Если требование об остановке не выполнено, начните заново с шага выбора.

Пример

Приведенное выше описание является абстрактным. Поможет конкретный пример.

Приложения

В целом

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

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

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

В своем руководстве по проектированию алгоритмов Скиена не советует использовать генетические алгоритмы для решения любых задач: "Довольно неестественно моделировать приложения в терминах генетических операторов, таких как мутация и кроссинговер на битовых строках. Псевдобиология добавляет еще один уровень сложности между вами и вашей проблемой". Во-вторых, генетические алгоритмы занимают очень много времени при решении нетривиальных задач. [...] Аналогия с эволюцией, где значительный прогресс требует [sic] миллионов лет, может быть вполне уместной. [...] Я никогда не сталкивался с проблемой, для решения которой генетические алгоритмы казались бы мне подходящим способом. Более того, я никогда не видел результатов вычислений с использованием генетических алгоритмов, которые произвели бы на меня благоприятное впечатление. Придерживайтесь моделированного отжига для эвристического поиска".

Настольные игры

Настольные игры являются очень актуальной частью области генетических алгоритмов в применении к проблемам теории игр. Большая часть ранних работ по вычислительному интеллекту и играм была направлена на классические настольные игры, такие как крестики-нолики,^[3] шахматы и шашки.^[4] В настоящее время в большинстве случаев настольные игры могут быть сыграны компьютером на более высоком уровне, чем лучшие люди, даже при использовании методов слепого исчерпывающего поиска. Го - заметное исключение из этой тенденции, и до сих пор она не поддавалась машинным атакам. Лучшие компьютерные игроки в го сейчас играют на уровне хорошего новичка.^[5][6] Считается, что стратегия го в значительной степени опирается на распознавание образов, а не только на логический анализ, как в шахматах и других более независимых от фигур играх. Огромный эффективный коэффициент разветвления, необходимый для поиска качественных решений, сильно ограничивает возможности поиска последовательности ходов с опережением.

Компьютерные игры

Генетический алгоритм может быть использован в компьютерных играх для создания искусственного интеллекта (компьютер играет против вас). Это позволяет получить более реалистичный игровой опыт; если человек-игрок может найти последовательность шагов, которая всегда приводит к успеху, даже при повторении в разных играх, в игре не может остаться никаких сложностей. И наоборот, если техника обучения, например, генетический алгоритм для стратега, может избежать повторения прошлых ошибок, игра будет более играбельной.

Генетические алгоритмы состоят из следующих частей:

• Метод представления задачи в терминах решения (например, маршрутизация солдат в атаке в стратегической игре)
• Подходящая или оценочная функция для определения качества экземпляра (например, измерение ущерба, нанесенного противнику при такой атаке).

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

Ограничения

Существуют ограничения использования генетического алгоритма по сравнению с альтернативными алгоритмами оптимизации:

• Повторная оценка фитнес-функции для сложных задач часто является наиболее ограничивающим сегментом искусственных эволюционных алгоритмов. Поиск оптимального решения сложных проблем часто требует очень дорогих оценок фитнес-функций. В реальных задачах, таких как задачи структурной оптимизации, оценка одной функции может потребовать от нескольких часов до нескольких дней полного моделирования. Типичные методы оптимизации не могут справиться с такими типами задач. Часто приходится использовать аппроксимацию, поскольку вычисление точного решения занимает слишком много времени. Генетические алгоритмы иногда комбинируют различные модели аппроксимации для решения сложных реальных задач.
• Генетические алгоритмы плохо масштабируются. То есть, при большом количестве элементов, подверженных мутации, часто происходит экспоненциальное увеличение размера пространства поиска. Это делает чрезвычайно сложным использование метода для решения таких задач, как проектирование двигателя, дома или самолета. Чтобы использовать генетические алгоритмы для решения таких задач, их необходимо разбить на максимально простые представления. По этой причине мы видим, что эволюционные алгоритмы кодируют проекты лопастей вентиляторов вместо двигателей, формы зданий вместо детальных планов строительства, а также аэродинамические обводы вместо целых конструкций самолетов. Вторая проблема сложности - это вопрос о том, как защитить части, которые эволюционировали и представляют хорошие решения, от дальнейших разрушительных мутаций, особенно когда оценка их пригодности требует, чтобы они хорошо сочетались с другими частями.
• "Лучшее" решение находится только в сравнении с другими решениями. В результате критерий остановки не является однозначным в каждой задаче.
• Во многих задачах генетические алгоритмы имеют тенденцию сходиться к локальным оптимумам или даже произвольным точкам, а не к глобальному оптимуму задачи. Это означает, что алгоритм не "умеет" жертвовать краткосрочной пригодностью для получения долгосрочной пригодности. Вероятность этого зависит от формы фитнес-функции: в некоторых задачах легко найти глобальный оптимум, в других - легче найти локальные оптимумы. Эту проблему можно уменьшить, используя другую функцию пригодности, увеличивая скорость мутации или используя методы отбора, которые поддерживают разнообразие популяции решений. Распространенной техникой поддержания разнообразия является использование "штрафа за нишу": к любой группе особей с достаточным сходством (радиус ниши) добавляется штраф, который уменьшает представительство этой группы в следующих поколениях, позволяя сохранить в популяции другие (менее похожие) особи. Этот прием, однако, может оказаться неэффективным, в зависимости от ландшафта проблемы. Другой возможной техникой может быть простая замена части популяции случайно сгенерированными особями, когда большая часть популяции слишком похожа друг на друга. Разнообразие важно в генетических алгоритмах (и генетическом программировании), потому что скрещивание однородной популяции не дает новых решений. В эволюционных стратегиях и эволюционном программировании разнообразие не так важно, поскольку в большей степени полагается на мутацию.
• Работа с динамическими наборами данных затруднена, поскольку геномы начинают рано сходиться к решениям, которые могут быть уже недействительными для более поздних данных. Было предложено несколько методов, чтобы исправить это, каким-то образом увеличивая генетическое разнообразие и предотвращая раннюю конвергенцию, либо путем увеличения вероятности мутации при снижении качества решения (так называемая запущенная гипермутация), либо путем периодического введения совершенно новых, случайно сгенерированных элементов в генофонд (так называемые случайные иммигранты). Опять же, стратегии эволюции и эволюционное программирование могут быть реализованы с помощью так называемой "стратегии запятой", при которой родители не сохраняются, а новые родители выбираются только из потомства. Это может быть более эффективным при решении динамических задач.
• Генетические алгоритмы не могут эффективно решать задачи, в которых единственной мерой пригодности является единственная мера "правильно/неправильно" (например, задачи принятия решений), поскольку нет способа сходимости к решению (нет холма, на который можно подняться). В этих случаях случайный поиск может найти решение так же быстро, как и ГА. Однако если ситуация позволяет повторять испытания на успех/неуспех, получая (возможно) разные результаты, то отношение успехов к неудачам является подходящей мерой пригодности.
• Для конкретных задач оптимизации и экземпляров задач другие алгоритмы оптимизации могут быть более эффективными, чем генетические алгоритмы, с точки зрения скорости сходимости. К альтернативным и дополнительным алгоритмам относятся стратегии эволюции, эволюционное программирование, имитационный отжиг, гауссова адаптация, подъем на холм, роевой интеллект (например: оптимизация муравьиной колонии, оптимизация роя частиц) и методы, основанные на целочисленном линейном программировании. Пригодность генетических алгоритмов зависит от объема знаний о проблеме; хорошо известные проблемы часто имеют лучшие, более специализированные подходы.

История

В 1950 году Алан Тьюринг предложил "обучающуюся машину", которая параллельно использовала бы принципы эволюции. Компьютерное моделирование эволюции началось уже в 1954 году с работы Нильса Аалла Барричелли, который использовал компьютер в Институте перспективных исследований в Принстоне, штат Нью-Джерси. Его публикация 1954 года не была широко замечена. Начиная с 1957 года, австралийский генетик Алекс Фрейзер опубликовал серию работ по моделированию искусственного отбора организмов с несколькими локусами, контролирующими измеряемый признак. С этих работ началось компьютерное моделирование эволюции биологами, которое стало более распространенным в начале 1960-х годов, а методы были описаны в книгах Фрейзера и Бернелла (1970) и Кросби (1973). Моделирование Фрейзера включало все основные элементы современных генетических алгоритмов. Кроме того, Ханс-Иоахим Бремерманн в 1960-х годах опубликовал серию работ, в которых также рассматривалась популяция решений задач оптимизации, подвергающаяся рекомбинации, мутации и отбору. Исследования Бремерманна также включали элементы современных генетических алгоритмов. Среди других заслуживающих внимания первопроходцев - Ричард Фридберг, Джордж Фридман и Майкл Конрад. Многие ранние работы перепечатаны в Fogel (1998).

Хотя Барричелли в работе, о которой он сообщил в 1963 году, смоделировал эволюцию способности играть в простую игру, искусственная эволюция стала широко признанным методом оптимизации в результате работы Инго Рехенберга и Ханса-Поля Швефеля в 1960-х и начале 1970-х годов - группа Рехенберга смогла решить сложные инженерные проблемы с помощью эволюционных стратегий. Другим подходом была техника эволюционного программирования Лоуренса Дж. Фогеля, которая была предложена для создания искусственного интеллекта. Эволюционное программирование первоначально использовало конечные автоматы состояний для прогнозирования среды и применяло вариации и отбор для оптимизации логики прогнозирования. Генетические алгоритмы, в частности, стали популярны благодаря работе Джона Холланда в начале 1970-х годов, и особенно его книге "Адаптация в естественных и искусственных системах" (1975). Его работа началась с изучения клеточных автоматов, проведенного Холландом и его студентами в Мичиганском университете. Холланд представил формализованную основу для прогнозирования качества следующего поколения, известную как теорема Холланда о схемах. Исследования в области ГА оставались в основном теоретическими до середины 1980-х годов, когда в Питтсбурге, штат Пенсильвания, состоялась Первая международная конференция по генетическим алгоритмам.