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

Антенна космического корабля НАСА ST5 2006 года . Эта сложная форма была найдена программой эволюционного компьютерного проектирования для создания наилучшей диаграммы направленности. Она известна как развитая антенна .

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

Методология

Проблемы оптимизации

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

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

Типичный генетический алгоритм требует:

1. генетическое представление области решения,
2. функция приспособленности для оценки области решения.

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

После того, как генетическое представление и функция приспособленности определены, ГА приступает к инициализации совокупности решений, а затем улучшает ее посредством многократного применения операторов мутации, кроссовера, инверсии и выбора.

Инициализация

Размер популяции зависит от характера проблемы, но обычно содержит сотни или тысячи возможных решений. Часто начальная популяция генерируется случайным образом, позволяя использовать весь диапазон возможных решений ( пространство поиска ). Иногда решения могут быть «засеяны» в областях, где оптимальные решения могут быть найдены, или распределение вероятности выборки может быть настроено так, чтобы сосредоточиться на тех областях, которые представляют больший интерес.

Выбор

Основная статья: Отбор (генетический алгоритм)

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

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

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

Генетические операторы

Основные статьи: Кроссовер (генетический алгоритм) и Мутация (генетический алгоритм)

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

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

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

Мнения относительно важности скрещивания и мутации разделились. (2006) есть много ссылок В Fogel , подтверждающих важность поиска на основе мутаций.

Хотя скрещивание и мутация известны как основные генетические операторы, в генетических алгоритмах можно использовать и другие операторы, такие как перегруппировка, колонизация-вымирание или миграция.

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

Эвристика

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

Прекращение действия

Этот процесс генерации повторяется до тех пор, пока не будет достигнуто условие завершения. Общие условия завершения:

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

Гипотеза строительных блоков

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

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

Гольдберг описывает эвристику следующим образом:

«Короткие схемы низкого порядка и схемы с высокой степенью соответствия отбираются, рекомбинируются [пересекаются] и повторно выбираются для формирования строк потенциально более высокой пригодности. В некотором смысле, работая с этими конкретными схемами [строительными блоками], мы уменьшили сложность нашей проблемы; вместо того, чтобы строить высокопроизводительные струны, пробуя все мыслимые комбинации, мы конструируем все лучшие и лучшие струны из лучших частичных решений прошлых выборок.

«Поскольку очень подходящие схемы малой определяющей длины и низкого порядка играют такую ​​важную роль в работе генетических алгоритмов, мы уже дали им специальное название: строительные блоки. Точно так же, как ребенок создает великолепные крепости, располагая простые блоки Так и генетический алгоритм стремится к почти оптимальной производительности за счет сопоставления коротких, высокопроизводительных схем низкого порядка или строительных блоков».

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

Ограничения

Практическое использование генетического алгоритма имеет ограничения, особенно по сравнению с альтернативными алгоритмами оптимизации:

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

Варианты

Представление хромосомы

Основная статья: генетическое представление

Самый простой алгоритм представляет каждую хромосому как битовую строку . Обычно числовые параметры могут быть представлены целыми числами , хотя можно использовать представления с плавающей запятой . Представление с плавающей запятой естественно для стратегий эволюции и эволюционного программирования . Было предложено понятие реальных генетических алгоритмов, но оно на самом деле является неправильным, поскольку на самом деле оно не отражает теорию строительных блоков, предложенную Джоном Генри Холландом в 1970-х годах. Однако эта теория не лишена поддержки, основанной на теоретических и экспериментальных результатах (см. ниже). Базовый алгоритм выполняет кроссовер и мутацию на битовом уровне. Другие варианты рассматривают хромосому как список чисел, которые являются индексами в таблице инструкций, узлами в связанном списке , хэшами , объектами или любой другой мыслимой структурой данных . Кроссовер и мутация выполняются с учетом границ элементов данных. Для большинства типов данных можно разработать специальные операторы вариаций. Различные типы хромосомных данных, похоже, работают лучше или хуже для разных конкретных проблемных областей.

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

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

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

Элитизм

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

Параллельные реализации

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

Адаптивные ГА

Генетические алгоритмы с адаптивными параметрами (адаптивные генетические алгоритмы, AGA) — еще один важный и перспективный вариант генетических алгоритмов. Вероятности скрещивания (pc) и мутации (pm) во многом определяют степень точности решения и скорость сходимости, которую могут получить генетические алгоритмы. Исследователи проанализировали конвергенцию GA аналитически.

Вместо использования фиксированных значений pc и pm AGA используют информацию о популяции в каждом поколении и адаптивно корректируют pc и pm , чтобы поддерживать разнообразие популяции, а также поддерживать способность конвергенции. В AGA (адаптивный генетический алгоритм) регулировка pc и pm зависит от значений приспособленности растворов. Есть и другие примеры вариантов AGA: метод последовательного масштабирования — ранний пример улучшения сходимости. В CAGA (адаптивный генетический алгоритм на основе кластеризации) Благодаря использованию кластерного анализа для оценки состояний оптимизации совокупности корректировка pc и pm зависит от этих состояний оптимизации. Последние подходы используют более абстрактные переменные для определения pc и pm . Примерами являются принципы доминирования и кодоминирования. и LIGA (уровневый интерполяционный генетический алгоритм), который сочетает в себе гибкий ГА с модифицированным поиском A * для решения проблемы анизотропности пространства поиска.

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

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

Вариант, при котором развивается популяция в целом, а не ее отдельные члены, известен как рекомбинация генофонда.

Ряд вариантов был разработан, чтобы попытаться улучшить производительность ГА при решении задач с высокой степенью эпистаза пригодности, т.е. когда пригодность решения состоит из взаимодействующих подмножеств его переменных. Цель таких алгоритмов — изучить (прежде чем использовать) эти полезные фенотипические взаимодействия. По сути, они соответствуют гипотезе строительных блоков в адаптивном уменьшении разрушительной рекомбинации. Яркими примерами этого подхода являются mGA, СОХРАНЯТЬ и ЛЛГА.

Проблемные области

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

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

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

В своем «Руководстве по разработке алгоритмов» Скиена советует не использовать генетические алгоритмы для любых задач:

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

[...]

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

— Стивен Скиена

История

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

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

Коммерческие продукты

В конце 1980-х годов General Electric начала продавать первый в мире продукт для генетических алгоритмов — набор инструментов на базе мэйнфреймов, предназначенный для промышленных процессов. В 1989 году компания Axcelis, Inc. выпустила Evolver , первый в мире коммерческий продукт GA для настольных компьютеров. Обозреватель New York Times, пишущий о технологиях Джон Маркофф, написал: об Evolver в 1990 году, и до 1995 года он оставался единственным интерактивным коммерческим генетическим алгоритмом. Evolver был продан Palisade в 1997 году, переведен на несколько языков и в настоящее время находится в шестой версии. С 1990-х годов MATLAB построил три эвристических алгоритма оптимизации без производных (имитация отжига, оптимизация роя частиц, генетический алгоритм) и два алгоритма прямого поиска (симплексный поиск, поиск по шаблону).

Связанные методы

См. Также: Список приложений генетических алгоритмов.

Родительские поля

Генетические алгоритмы - это подполе:

• Эволюционные алгоритмы
• Эволюционные вычисления
• Метаэвристика
• Стохастическая оптимизация
• Оптимизация

Связанные поля

Эволюционные алгоритмы

Основная статья: Эволюционный алгоритм

Эволюционные алгоритмы — это подобласть эволюционных вычислений .

• Стратегии эволюции (ЭС, см. Рехенберг, 1994) развивают особей посредством мутаций и промежуточной или дискретной рекомбинации. Алгоритмы ES разработаны специально для решения задач в области реальных значений. Они используют самоадаптацию для настройки параметров управления поиском. Дерандомизация самоадаптации привела к созданию современной Стратегии эволюции адаптации на основе ковариационной матрицы ( CMA-ES ).
• Эволюционное программирование (ЭП) включает в себя совокупность решений, в основном с мутацией, отбором и произвольными представлениями. Они используют самоадаптацию для настройки параметров и могут включать в себя другие операции изменения, такие как объединение информации от нескольких родителей.
• Алгоритм оценки распределения (EDA) заменяет традиционные операторы воспроизводства операторами, управляемыми моделями. Такие модели изучаются на основе совокупности с использованием методов машинного обучения и представляются как вероятностные графические модели, из которых можно выбирать новые решения. или сгенерирован из управляемого кроссовера.
• Генетическое программирование (GP) — это родственный метод, популяризированный Джоном Коза , при котором оптимизируются компьютерные программы, а не параметры функций. Генетическое программирование часто использует древовидные внутренние структуры данных для представления компьютерных программ для адаптации вместо списковых структур, типичных для генетических алгоритмов. Существует множество вариантов генетического программирования, включая декартово генетическое программирование , программирование экспрессии генов , грамматическая эволюция , линейное генетическое программирование , программирование с несколькими выражениями и т. д.
• Генетический алгоритм группировки (GGA) — это эволюция ГА, в которой фокус смещается с отдельных элементов, как в классических ГА, на группы или подмножества элементов. Идея этой эволюции ГА, предложенная Эмануэлем Фалькенауэром, заключается в том, что решение некоторых сложных проблем, таких как проблемы кластеризации или разделения , когда набор элементов должен быть оптимальным образом разделен на непересекающиеся группы элементов, лучше достигать путем создания характеристик групп. предметов, эквивалентных генам. К такого рода проблемам относятся упаковка контейнеров , балансировка строк, кластеризация по мере расстояния, равные стопки и т. д., на которых классические ГА показали себя плохо. Чтобы сделать гены эквивалентными группам, необходимо использовать хромосомы, которые, как правило, имеют переменную длину, а также специальные генетические операторы, которые манипулируют целыми группами элементов. В частности, для упаковки контейнеров лучшим методом на сегодняшний день является GGA, гибридизированный с критерием доминирования Мартелло и Тота.
• Интерактивные эволюционные алгоритмы — это эволюционные алгоритмы, использующие человеческую оценку. Они обычно применяются в областях, где сложно разработать функцию вычислительной пригодности, например, при разработке изображений, музыки, художественных проектов и форм в соответствии с эстетическими предпочтениями пользователей.

Роевой интеллект

Основная статья: Роевой интеллект

Роевой интеллект — это подобласть эволюционных вычислений .

• Оптимизация колонии муравьев ( ACO ) использует множество муравьев (или агентов), оснащенных моделью феромонов, для перемещения по пространству решений и поиска локально продуктивных областей.
• Хотя это и считается алгоритмом оценки распределения , Оптимизация роя частиц (PSO) — это вычислительный метод многопараметрической оптимизации, который также использует популяционный подход. Популяция (рой) решений-кандидатов (частиц) перемещается в пространстве поиска, и на движение частиц влияет как их собственное наиболее известное положение, так и глобальное наиболее известное положение роя. Как и генетические алгоритмы, метод PSO зависит от обмена информацией между членами популяции. В некоторых задачах PSO часто более эффективен в вычислительном отношении, чем GA, особенно в задачах без ограничений с непрерывными переменными.

Другие эволюционные вычислительные алгоритмы

Эволюционные вычисления - это подобласть метаэвристических методов.

• Меметический алгоритм (МА), часто называемый, среди прочего, гибридным генетическим алгоритмом , представляет собой популяционный метод, в котором решения также подлежат локальным этапам улучшения. Идея меметических алгоритмов исходит от мемов , которые, в отличие от генов, могут адаптироваться. Показано, что в некоторых проблемных областях они более эффективны, чем традиционные эволюционные алгоритмы.
• Бактериологические алгоритмы (БА), вдохновленные эволюционной экологией и, в частности, бактериологической адаптацией. Эволюционная экология — это изучение живых организмов в контексте их окружающей среды с целью выяснить, как они адаптируются. Его основная концепция заключается в том, что в гетерогенной среде не существует ни одного человека, подходящего для всей среды. Значит, нужно рассуждать на уровне населения. Также считается, что БА можно успешно применять для решения сложных задач позиционирования (антенны для сотовых телефонов, городское планирование и т. д.) или интеллектуального анализа данных.
• Культурный алгоритм (КА) состоит из популяционного компонента, почти идентичного компоненту генетического алгоритма, и, кроме того, компонента знаний, называемого пространством убеждений.
• Дифференциальная эволюция (ДЭ), вдохновленная миграцией суперорганизмов.
• Гауссова адаптация (нормальная или естественная адаптация, сокращенно NA, чтобы избежать путаницы с GA) предназначена для максимизации производительности производства систем обработки сигналов. Его также можно использовать для обычной параметрической оптимизации. Он опирается на определенную теорему, справедливую для всех областей приемлемости и всех гауссовских распределений. Эффективность NA опирается на теорию информации и определенную теорему эффективности. Его эффективность определяется как количество информации, разделенное на работу, необходимую для ее получения. Поскольку NA максимизирует среднюю приспособленность, а не приспособленность индивидуума, ландшафт сглаживается так, что провалы между пиками могут исчезнуть. Поэтому у него есть определенное «амбиция» избегать локальных пиков фитнес-ландшафта. NA также хорошо справляется с преодолением острых гребней за счет адаптации матрицы моментов, поскольку NA может максимизировать беспорядок ( среднюю информацию ) гауссианы, одновременно сохраняя постоянную среднюю приспособленность .

Другие метаэвристические методы

Метаэвристические методы в целом относятся к методам стохастической оптимизации.

• Имитированный отжиг (SA) — это родственный метод глобальной оптимизации, который пересекает пространство поиска путем проверки случайных мутаций на отдельном решении. Мутация, повышающая приспособленность, всегда допускается. Мутация, снижающая приспособленность, принимается вероятностно на основе разницы в приспособленности и уменьшения температурного параметра. На языке ЮАР говорят о поиске наименьшей энергии вместо максимальной физической формы. SA также можно использовать в стандартном алгоритме GA, начиная с относительно высокой скорости мутаций и уменьшая ее с течением времени по заданному графику.
• Поиск с табу (TS) аналогичен моделируемому отжигу в том, что оба метода пересекают пространство решений, проверяя мутации отдельного решения. В то время как имитация отжига генерирует только одно мутированное решение, поиск с табу генерирует множество мутировавших решений и переходит к решению с наименьшей энергией из сгенерированных. Чтобы предотвратить циклическое движение и стимулировать более активное движение по пространству решений, поддерживается запретный список частичных или полных решений. Запрещен переход к решению, содержащему элементы списка табу, который обновляется по мере прохождения решения по пространству решений.
• Экстремальная оптимизация (EO). В отличие от ГА, которые работают с совокупностью возможных решений, EO разрабатывает одно решение и вносит локальные изменения в худшие компоненты. Для этого необходимо выбрать подходящее представление, позволяющее присвоить отдельным компонентам решения меру качества («пригодность»). Руководящим принципом этого алгоритма является принцип внезапного улучшения путем выборочного удаления некачественных компонентов и замены их случайно выбранным компонентом. Это явно противоречит ГА, который выбирает хорошие решения в попытке найти лучшие решения.

Другие методы стохастической оптимизации

• Метод перекрестной энтропии (CE) генерирует возможные решения с помощью параметризованного распределения вероятностей. Параметры обновляются посредством минимизации перекрестной энтропии, чтобы на следующей итерации генерировать более качественные выборки.
• Реактивная поисковая оптимизация (RSO) выступает за интеграцию субсимвольных методов машинного обучения в эвристику поиска для решения сложных задач оптимизации. Слово «реактивный» намекает на готовую реакцию на события во время поиска через внутреннюю онлайн-петлю обратной связи для самонастройки критически важных параметров. Методологии, представляющие интерес для Реактивного поиска, включают машинное обучение и статистику, в частности обучение с подкреплением , активное обучение или обучение по запросам , нейронные сети и метаэвристику .

См. также

• Генетическое программирование
• Список приложений генетических алгоритмов
• Генетические алгоритмы обработки сигналов (также известные как фильтры частиц)
• Распространение схемы
• Универсальный дарвинизм
• Метаэвристика
• Система классификаторов обучения
• Машинное обучение на основе правил

Библиография

• Банцхаф, Вольфганг; Нордин, Питер; Келлер, Роберт; Франконе, Франк (1998). Генетическое программирование – Введение . Сан-Франциско, Калифорния: Морган Кауфманн. ISBN  978-1558605107 .
• Бис, Роберт Р.; Малдун, Мэтью Ф.; Поллок, Брюс Г.; Манук, Стивен; Смит, Гвенн; Сейл, Марк Э. (2006). «Гибридный подход машинного обучения на основе генетических алгоритмов к выбору модели». Журнал фармакокинетики и фармакодинамики . 33 (2): 196–221. дои : 10.1007/s10928-006-9004-6 . ПМИД   16565924 . S2CID   39571129 .
• Ча, Сон Хёк; Тапперт, Чарльз К. (2009). «Генетический алгоритм построения компактных двоичных деревьев решений». Журнал исследований в области распознавания образов . 4 (1): 1–13. CiteSeerX   10.1.1.154.8314 . дои : 10.13176/11.44 .
• Эйбен, Агостон; Смит, Джеймс (2003). Введение в эволюционные вычисления . Спрингер. ISBN  978-3540401841 .
• Фрейзер, Алекс С. (1957). «Моделирование генетических систем с помощью автоматических цифровых компьютеров. I. Введение» . Австралийский журнал биологических наук . 10 (4): 484–491. дои : 10.1071/BI9570484 .
• Гольдберг, Дэвид (1989). Генетические алгоритмы в поиске, оптимизации и машинном обучении . Ридинг, Массачусетс: Addison-Wesley Professional. ISBN  978-0201157673 .
• Гольдберг, Дэвид (2002). Дизайн инноваций: уроки компетентных генетических алгоритмов и для них . Норвелл, Массачусетс: Kluwer Academic Publishers. ISBN  978-1402070983 .
• Фогель, Дэвид (2006). Эволюционные вычисления: к новой философии машинного интеллекта (3-е изд.). Пискатауэй, Нью-Джерси: IEEE Press. ISBN  978-0471669517 .
• Хингстон, Филип; Бароне, Луиджи; Михалевич, Збигнев (2008). Дизайн от эволюции: достижения в области эволюционного дизайна . Спрингер. ISBN  978-3540741091 .
• Холланд, Джон (1992). Адаптация в природных и искусственных системах . Кембридж, Массачусетс: MIT Press. ISBN  978-0262581110 .
• Коза, Джон (1992). Генетическое программирование: о программировании компьютеров посредством естественного отбора . Кембридж, Массачусетс: MIT Press. ISBN  978-0262111706 .
• Михалевич, Збигнев (1996). Генетические алгоритмы + Структуры данных = Программы эволюции . Спрингер-Верлаг. ISBN  978-3540606765 .
• Митчелл, Мелани (1996). Введение в генетические алгоритмы . Кембридж, Массачусетс: MIT Press. ISBN  9780585030944 .
• Поли, Р.; Лэнгдон, ВБ; Макфи, Северная Каролина (2008). Полевое руководство по генетическому программированию . Lulu.com, бесплатно доступный в Интернете. ISBN  978-1-4092-0073-4 .
• Речехберг, Инго (1994): Эволюционная стратегия '94, Штутгарт: Фромман-Хольцбуг.
• Шмитт, Лотар М.; Неханив, Кристофер Л.; Фуджи, Роберт Х. (1998). «Линейный анализ генетических алгоритмов» . Теоретическая информатика . 208 : 111–148.
• Шмитт, Лотар М. (2001). «Теория генетических алгоритмов» . Теоретическая информатика . 259 (1–2): 1–61. дои : 10.1016/S0304-3975(00)00406-0 .
• Шмитт, Лотар М. (2004). «Теория генетических алгоритмов II: модели генетических операторов над струнно-тензорным представлением популяций и сходимость к глобальному оптимуму для произвольной функции приспособленности при масштабировании» . Теоретическая информатика . 310 (1–3): 181–231. дои : 10.1016/S0304-3975(03)00393-1 .
• Сульфур, Ханс-Пол (1974): Численная оптимизация компьютерных моделей (докторская диссертация). Перепечатано Биркхойзером (1977).
• Восе, Майкл (1999). Простой генетический алгоритм: основы и теория . Кембридж, Массачусетс: MIT Press. ISBN  978-0262220583 .
• Уитли, Даррелл (1994). «Учебное пособие по генетическому алгоритму» (PDF) . Статистика и вычисления . 4 (2): 65–85. CiteSeerX   10.1.1.184.3999 . дои : 10.1007/BF00175354 . S2CID   3447126 . Архивировано (PDF) из оригинала 9 октября 2022 года.

Внешние ссылки

Ресурсы

• [1] Предоставляет список ресурсов в области генетических алгоритмов.
• Обзор истории и особенностей эволюционных алгоритмов

Учебники

• Генетические алгоритмы. Компьютерные программы, которые «эволюционируют» способами, напоминающими естественный отбор, могут решать сложные проблемы, которые даже их создатели не до конца понимают. Отличное введение в ГА Джона Холланда и приложение к дилемме узника.
• Интерактивное онлайн-руководство по генетическому алгоритму, позволяющее читателю попрактиковаться или узнать, как работает ГА : изучайте шаг за шагом или наблюдайте за глобальной конвергенцией в пакетном режиме, изменяйте размер популяции, скорости/границы скрещивания, скорости/границы мутаций и механизмы отбора, а также добавляйте ограничения. .
• Учебное пособие по генетическому алгоритму от Даррелла Уитли, факультет компьютерных наук, Университет штата Колорадо. Превосходное учебное пособие с большим количеством теории.
• «Основы метаэвристики» , 2009 (225 с). Свободный открытый текст Шона Люка.
• Алгоритмы глобальной оптимизации - теория и применение. Архивировано 11 сентября 2008 г. в Wayback Machine.
• Учебное пособие по генетическим алгоритмам в Python с интуицией, лежащей в основе GA и реализации Python.
• Генетические алгоритмы развиваются, чтобы решить дилемму заключенного. Автор Роберт Аксельрод.