Авторы: P.J. Fleming, R.C. Purshouse
Название в оригинале: Genetic algorithms in control systems engineering
Перевод: В.А. Дрыкин
Источник(англ.): Department of Automatic Control and Systems Engineering, University of Sheffield, Mappin Street, Sheffield, S1 3JD, UK http://www.lania.mx/~ccoello/EMOO/fleming01.pdf.gz
Генетические алгоритмы (ГА) бывают глобальные, параллельные, и используются как методы поиска и оптимизации, они основаны на принципах теории Дарвина [Дарвин, 1859]. Они работают с популяцией возможных решений проблемы. Каждый индивидуум в популяции представляет собой конкретное решение этой проблемы, как правило, выражается в той или иной форме генетического кода. Популяция развивается, на протяжении многих поколений, чтобы произвести лучшее решение проблемы. Схема алгоритма показана на рисунке 1.
Рис. 1 – Схема стандартного генетического алгоритма
Каждой особи внутри популяции присваивается фитнесс–значение, которое показывает, насколько хорошо решение удовлетворяет проблему. Фитнесс–значение вероятностно определяет, насколько успешно особь будет распространять свои гены (код) для последующих поколений. Лучшим решениям назначаются лучшие фитнесс–значения, чем худшим решениям. Эволюция выполняется с использованием набора стохастических генетических операторов, которые манипулируют генетическим кодом. Большинство генетических алгоритмов включают операторы, которые выбирают особи для воспроизводства, производства новых лиц на основе выбраных, и определяют состав популяции в последующих поколениях. Кроссинговер (кроссовер) и оператор мутации это два хорошо известных оператора.
Рис. 2 – Одноточечный кроссинговер
Оператор кроссинговера включает в себя обмен генетическим материалом между хромосомами (родителями), для того, чтобы создать новые хромосомы (потомство). Были разработаны различные формы этого оператора. Самая простая форма, одноточечный кроссинговер, показан на рисунке 2. Этот оператор выбирает двух родителей, выбирает случайную позицию в генетическом коде, и меняет генетическую информацию справа от этой точки, тем самым создавая два новых потомка.
Рис. 3 – Двоичный оператор мутации
Оператор мутации, в своей простейшей форме, делает небольшие, случайные, изменения в хромосоме. Для двоичного (бинарного) кодирования, это предполагает замену гена 1 на ген 0 с малой вероятностью (обычно около одного процента) для каждого бита в хромосоме, как показано на рисунке 3.
Как только новое поколение построилось, процессы, которые приводят к появлению последующих поколений популяции повторяются.
Генетический алгоритм исследует и использует пространство поиска, для нахождения лучшего решения проблемы. Вполне возможно, для ГА поддерживать несколько разнородных, но одинаково хороших, решений проблемы, благодаря использованию популяции.
Несмотря на простую концепцию, генетические алгоритмы могут быть довольно сложными. С появлением первого ГА были предложены с появлением первого ГА различные вариации. Строгий математический анализ ГА сложен и еще не завершен.
Генетические алгоритмы – надежные инструменты, и в состоянии справиться с разрывами и шумами в задаче ландшафта. Включение предметно–ориентированных эвристик не является предварительным условием, хотя оно может улучшить производительность ГА. Они доказали свою полезность в решении проблем, которые не могут быть решены с помощью обычных средств.
Много вариаций на стандартный генетический алгоритм, представлено Goldberg [1989], можно найти в литературе. Изменения были вызваны желанием повысить производительность ГА, чтобы адаптировать его к конкретной области. Это может быть более полезным и целесообразно рассматривать эволюционные вычисления в качестве общего решения проблем методологии, а не конкретного инструмента.
Практически каждый аспект ГА подвергается проверкам на практике. Результаты такого изменения часто безрезультатны, а часто базируется на основе ограниченных эмпирических проверок. Краткое изложение ключевых понятий представлено ниже:
Популяция – численность популяции была стандартным вопросом и для теоретиков, и для исполнителей. Популяция от двадцати до ста хромосом, как правило, достаточна для большинства приложений. Кодирование потенциальных решений для формирования хромосом также было предметом интенсивных исследований. Двоичное кодирование или кодирование Грея, кодирование является традиционным подходом, но числа с плавающей точкой для представления проектных параметров становятся все более популярными [Michalewicz, 1996].
Фитнесс-распределение – техника для вычисления потенциального решения ГА, также получила большую долю внимания. Фитнесс-функция часто рассматривается как абсолют, перед нормализацией использования среднего популяции, но, в качестве альтернативы используются методы ранжирования. Важны задачи предотвращения преждевременной сходимости (в начале поиска), а также предотвращения бесцельного поиска в конце поиска. Ранжирование является, пожалуй, наиболее эффективным методом достижения этой цели.
Отбор - стандартное колесо рулетки, как известно, приводит к получению смещенных результатов, что приводит к явлению, известному как генетический дрейф. Две главных цели в разработке альтернатив: устранить статистические ошибки и достигнуть потенциального параллелизма. Были предложены и другие методы выбора, такие как турниры между парой особей (которые достигают хорошего параллелизма), и стохастические универсальные выборки (которые беспристрастны) [Baker, 1987].
Генетические манипуляции – генетические операторы были предметом интенсивного обсуждения, по поводу состава и назначения различных операторов. Некоторые исследователи отказались от рекомбинации, в то время как другие считают влияние мутации минимальной. По существу, рекомбинация имеет тенденцию направлять поиск в превосходной области пространства поиска, в то время как мутации направлена исследовать новые области пространства поиска и убедиться, что генетический материал не может быть безвозвратно потерян. Выбор генетических операторов должен быть сделан вместе с выбором представления.
Итерация – ГА развивают популяцию на протяжении ряда поколений. Точное число зависит от скорости, с которой сходимость может быть достигнута. Состав каждого нового поколения должен быть выбран. Обычно он будет включать потомства полученные в результате генетических операторов, действующих на старые особи, некоторые пережитки прошлой популяции, и, возможно, несколько случайно генерируемых особей (см. рисунок 5). Точная пропорции имеет тенденцию изменяться в зависимости от реализации, но потомство обычно доминирует в новом населении. Отношение потомства к численности популяции называют разрывом между поколениями. Это может быть статическое значение или может динамически изменяться в ходе выполнения. Элитарность описывает преднамеренное введение высоких достижений (по отношению к нынешней популяции) в новую популяцию.
Рис. 4 – Пропорции особей в новой генерации
Новые операторы – различные новые операторы, которые были введены для решения проблем. Например, фитнес-обмена можно использовать для поощрения поведения (субпопуляции формирования различны, сравнительно оптимальны). Ограничение на скрещивание может быть применено в случае, когда кроссовер между сильно отличающимися решениями вряд ли создаст хорошее потомство (плохое потомство обычно описывается как летальное).