1.2.Генетические алгоритмы
Генетический алгоритм (genetic algorithm) [4, 20, 35, 55] представляет собой стохастический метод оптимизации. Основная идея генетических алгоритмов состоит в использовании принципа естественного отбора, который составляет основы теории эволюции живых организмов, предложенной Чарльзом Дарвином.
Подобные идеи возникали у ряда исследователей. В 1962 г. Л. Фогель занялся изучением интеллектуального поведения индивида и его развития в процессе эволюции [38]. При этом поведение индивида задавалось конечным автоматом. Продолжая данные исследования, Л. Фогель, А. Оуэнс и М. Уолш предложили в 1966 г. схему эволюции конечных автоматов, решающих задачи предсказания [39]. Примерно в это же время (в середине 60-х годов) Дж. Холланд разработал новый метод поиска оптимальных решений – генетические алгоритмы. Результатом работы Дж. Холланда стала книга [45], вышедшая в 1975 г. Эти работы заложили основы эволюционных вычислений.
Кратко сформулировать принцип естественного отбора можно следующим образом: наименее приспособленные особи умирают раньше, а наиболее приспособленные выживают и дают потомство. Потомство выживших особей оказывается в среднем более приспособленным, но среди них опять выделяются более приспособленные особи, и так далее.
В генетических алгоритмах используются те же принципы. В качестве особей выступают элементы пространства возможных решений некоторой задачи (маршруты коммивояжера, диаграммы переходов автомата и т. п.). Задан набор генетических операций, с помощью которых из существующих особей формируются новые. Кроме этого определена так называемая функция приспособленности (fitness-function), которая показывает, насколько «хорошим» решением задачи является особь.
Процесс работы генетического алгоритма состоит в генерации поколений особей до тех пор, пока не будет выполнено некоторое условие останова (например, достигнуто целевое значение функции приспособленности или сгенерировано заданное число поколений). На Рис. 2. приведена общая схема работы генетического алгоритма.
|
Общая схема работы генетического алгоритма
|
По сравнению с традиционными методами оптимизации генетические алгоритмы имеют ряд преимуществ:
генетические алгоритмы легко модифицируются для параллельных вычислений;
они хорошо подходят для оптимизации недиффернцируемых функций.
Основными недостатками генетических алгоритмов являются:
высокая трудоемкость, ограничивающая их область применения;
сложность оценки степени пригодности конкретных генетических операций для конкретной задачи.
1.2.1.Основные определения
Приведем ряд определений, которые играют важную роль в теории эволюционных вычислений и необходимы для описания генетических алгоритмов.
Поколение (популяция) – это совокупность особей, способная к устойчивому самовоспроизводству, относительно обособленная от других групп, с представителями которых потенциально возможен генетический обмен.
Индивид (особь) – единичный представитель популяции.
Фенотип – совокупность характеристик, присущих индивиду на определённой стадии развития. Фенотип формируется на основе генотипа, опосредованного рядом факторов внешней среды.
Генотип – наследственная информация, закодированная в хромосомах, которая вместе с факторами внешней среды определяет фенотип организма. Генотип не всегда соответствует одному и тому же фенотипу. Некоторые гены проявляются в фенотипе только в определенных условиях.
Хромосома – структура, содержащая генетический код индивида.
Ген – определенная часть хромосомы, кодирующая врожденное качество индивида.
Генетические алгоритмы – это оптимизационный метод, базирующийся на принципах естественной эволюции популяции особей (индивидов). Каждая особь характеризуется приспособленностью – функцией ее генов. Задача оптимизации состоит в максимизации функции приспособленности. В процессе эволюции – в результате отбора, рекомбинаций, мутаций геномов особей, а также применения ряда других генетических операторов, происходит поиск особей с высокой приспособленностью. По сравнению с обычными оптимизационными методами генетические алгоритмы имеют особенности: параллельный поиск, случайные мутации и рекомбинации уже найденных хороших решений. Приведем описание генетических операторов.
Как известно в теории эволюции, важную роль играет то, каким образом признаки родителей передаются потомкам. В генетических алгоритмах за передачу признаков родителей потомкам отвечает оператор, который называется скрещивание. В литературе по генетическим алгоритмам этот оператор называют также кроссинговер, кроссовер, рекомбинация.
Мутация – случайное изменение одной или нескольких позиций в хромосоме. Мутации, которые проявляются на уровне фенотипа, могут иметь как отрицательные последствия, так и положительные – приводить к появлению у индивида новых полезных признаков. Таким образом, мутации являются двигателем естественного отбора, так как являются механизмом поддержания разнообразия особей в популяции.
Из-за избыточности и неоднозначности кодирования одному и тому же фенотипу может соответствовать множество генотипов. При этом часто порядок генов в хромосоме является критическим для строительных блоков, позволяющих осуществлять эффективную работу алгоритма. В ряде работ были предложены методы для переупорядочения позиций генов в хромосоме во время работы алгоритма. Одним из таких методов является инверсия, выполняющая реверсирование порядка генов между двумя случайно выбранными позициями в хромосоме. Когда используются методы переупорядочения, гены должны содержать некоторую «метку», такую, чтобы их можно было правильно идентифицировать независимо от их позиции в хромосоме. Цель переупорядочения состоит в том, чтобы попытаться найти порядок генов, который имеет лучший эволюционный потенциал. Многие исследователи использовали инверсию в своих работах, однако мало кто пытался ее обосновать или определить ее вклад. Переупорядочение также значительно расширяет область поиска. Мало того, что генетический алгоритм пытается находить «хорошие» множества генов, но он также одновременно пробует находить хорошее упорядочение генов. Это гораздо более трудная задача для решения. Еще раз отметим, что оператор переупорядочения не изменяет фенотипа индивидуума, а изменяет лишь структуру хромосомы.
Как правило, выделяют еще один оператор для генетических алгоритмов – оператор генерации случайной особи, который может быть использован при создании начальной популяции, при пополнении популяции случайными особями и при некоторых мутациях.
1.2.2.Традиционный генетический алгоритм
В этом разделе приведено краткое описание традиционного генетического алгоритма (conventional genetic algorithm) [55] с одноточечной рекомбинацией и мутацией. В этом алгоритме каждая особь представляет собой битовую строку длины L, а размер популяции равен n.
Шаг 1. Генерации начальной популяции  . Для этого, например, можно сгенерировать n битовых строк, в которых каждый из L битов равен 0 или 1 с одинаковой вероятностью.
Шаг 2. Вычислить функцию приспособленности f(x) для каждой особи из текущей популяции. Этот шаг обычно является наиболее трудоемким по времени во всем алгоритме. Отметим, что при вычислении функции приспособленности, как правило, необходимо осуществить декодирование некоторого объекта из двоичной строки.
Шаг 3. Переход к следующему поколению популяции. При создании нового поколения могут использоваться различные стратегии. В качестве примера приведем так называемый метод рулетки (roulette wheel selector) [4].
Создание нового поколения в этом случае разбивается на n итераций, на каждой из которых в популяцию добавляется одна особь. Для этого случайно с вероятностями, пропорциональными их функция приспособленности, из текущего поколения популяции выбираются две родительские особи x и y.
После этого с некоторой наперед заданной вероятностью происходит скрещивание (рекомбинация, кроссовер, кроссинговер) родительских особей. В результате образуются их «потомки» – z1 и z2. Происходит это следующим образом: случайно (с равномерным распределением на множестве {1, 2, …, L}) выбирается число k. Хромосомы «потомков» z1 и z2 теперь строятся следующим образом: для z1 – первые k символов совпадают с первыми k символами x, последние (L-k) – с последними (L-k) символами y, для z2 – наоборот. Например, если L=7, x=1001010, y=0001001, k=3, то z1=1001001, z2=0001010. После этого равновероятно выбирается одна из особей z1 либо z2 – выбранную особь обозначим как z.
С некоторой (как правило, порядка 0.01) вероятностью производится мутация особи z – в ней случайно выбирается один бит и изменяется.
Получившаяся в результате особь z добавляется в следующее поколение.
Шаг 4. Повторять шаги 2 и 3 до тех пор, пока не будет выполнено условие останова (максимальная приспособленность в популяции достигла целевого значения, прекратился рост максимальной приспособленности, число поколений достигло некоторого предела и т.д.).
Отметим, что кроме описанных выше методов одноточечного кроссовера, алгоритма рулетки и мутации изменением случайного бита, существуют и другие – обзор приведен в работе [15].
1.2.3.Генетическое программирование
Генетическое программирование (genetic programming), предложенное J.R. Koza в 1992 году [49], предполагает применение генетических алгоритмов для автоматизированного построения программ.
Основным отличием генетического программирования от традиционных генетических алгоритмов является способ кодирования особей. Если в генетическом алгоритме особи кодируются с помощью битовых строк, то в генетическом программировании используется более высокоуровневое представление: деревья разбора, тексты программ на языках программирования с несложной структурой, диаграммы переходов конечных автоматов и т. д.
Такой подход позволяет определить генетические операции скрещивания и мутации, которые лучше подходят для решаемой задачи. Например, если каждая особь представляет собой программу, то возможны так называемые операции, изменяющие архитектуру, (architecture-altering operations) – например, добавление подпрограммы [21].
|
