1.2.Генетические алгоритмы
Генетический алгоритм (genetic algorithm) [4, 19, 34, 54] представляет собой стохастический метод оптимизации. Основная идея генетических алгоритмов состоит в использовании принципа естественного отбора, который составляет основы теории эволюции живых организмов, предложенной Чарльзом Дарвином.
Подобные идеи возникали у ряда исследователей. В 1962 г. Л. Фогель занялся изучением интеллектуального поведения индивида и его развития в процессе эволюции [37]. При этом поведение индивида задавалось конечным автоматом. Продолжая данные исследования, Л. Фогель, А. Оуэнс и М. Уолш предложили в 1966 г. схему эволюции конечных автоматов, решающих задачи предсказания [38]. Примерно в это же время (в середине 60-х годов) Дж. Холланд разработал новый метод поиска оптимальных решений – генетические алгоритмы. Результатом работы Дж. Холланда стала книга [44], вышедшая в 1975 г. Эти работы заложили основы эволюционных вычислений.
Кратко сформулировать принцип естественного отбора можно следующим образом: наименее приспособленные особи умирают раньше, а наиболее приспособленные выживают и дают потомство. Потомство выживших особей оказывается в среднем более приспособленным, но среди них опять выделяются более приспособленные особи, и так далее.
В генетических алгоритмах используются те же принципы. В качестве особей выступают элементы пространства возможных решений некоторой задачи (маршруты коммивояжера, диаграммы переходов автомата и т. п.). Задан набор генетических операций, с помощью которых из существующих особей формируются новые. Кроме этого определена так называемая функция приспособленности (fitness-function), которая показывает, насколько «хорошим» решением задачи является особь.
Процесс работы генетического алгоритма состоит в генерации поколений особей до тех пор, пока не будет выполнено некоторое условие останова (например, достигнуто целевое значение функции приспособленности или сгенерировано заданное число поколений). На Рис. 2. приведена общая схема работы генетического алгоритма.
|
Общая схема работы генетического алгоритма
|
По сравнению с традиционными методами оптимизации генетические алгоритмы имеют ряд преимуществ:
генетические алгоритмы легко модифицируются для параллельных вычислений;
они хорошо подходят для оптимизации недиффернцируемых функций.
Основными недостатками генетических алгоритмов являются:
высокая трудоемкость, ограничивающая их область применения;
сложность оценки степени пригодности конкретных генетических операций для конкретной задачи.
1.2.1.Основные определения
Приведем ряд определений, которые играют важную роль в теории эволюционных вычислений и необходимы для описания генетических алгоритмов.
Поколение (популяция) – это совокупность особей, способная к устойчивому самовоспроизводству, относительно обособленная от других групп, с представителями которых потенциально возможен генетический обмен.
Индивид (особь) – единичный представитель популяции.
Фенотип – совокупность характеристик, присущих индивиду на определённой стадии развития. Фенотип формируется на основе генотипа, опосредованного рядом внешнесредовых факторов.
Генотип – наследственная информация, закодированная в хромосомах, которая вместе с факторами внешней среды определяет фенотип организма. Генотип не всегда соответствует одному и тому же фенотипу. Некоторые гены проявляются в фенотипе только в определенных условиях.
Хромосома – структура, содержащая генетический код индивида.
Ген – определенная часть хромосомы, кодирующая врожденное качество индивида.
Генетические алгоритмы – это оптимизационный метод, базирующийся на принципах естественной эволюции популяции особей (индивидов). Каждая особь характеризуется приспособленностью – функцией ее генов. Задача оптимизации состоит в максимизации функции приспособленности. В процессе эволюции – в результате отбора, рекомбинаций, мутаций геномов особей, а также применения ряда других генетических операторов, происходит поиск особей с высокой приспособленностью. По сравнению с обычными оптимизационными методами генетические алгоритмы имеют особенности: параллельный поиск, случайные мутации и рекомбинации уже найденных хороших решений. Приведем описание генетических операторов.
Как известно в теории эволюции, важную роль играет то, каким образом признаки родителей передаются потомкам. В генетических алгоритмах за передачу признаков родителей потомкам отвечает оператор, который называется скрещивание. В литературе по генетическим алгоритмам этот оператор называют также кроссинговер, кроссовер, рекомбинация.
Мутация – случайное изменение одной или нескольких позиций в хромосоме. Мутации, которые проявляются на уровне фенотипа, могут иметь как отрицательные последствия, так и положительные – приводить к появлению у индивида новых полезных признаков. Таким образом, мутации являются двигателем естественного отбора, так как являются механизмом поддержания разнообразия особей в популяции.
Из-за избыточности и неоднозначности кодирования одному и тому же фенотипу может соответствовать множество генотипов. При этом часто порядок генов в хромосоме является критическим для строительных блоков, позволяющих осуществлять эффективную работу алгоритма. В ряде работ были предложены методы для переупорядочения позиций генов в хромосоме во время работы алгоритма. Одним из таких методов является инверсия, выполняющая реверсирование порядка генов между двумя случайно выбранными позициями в хромосоме. Когда используются методы переупорядочения, гены должны содержать некоторую «метку», такую, чтобы их можно было правильно идентифицировать независимо от их позиции в хромосоме. Цель переупорядочения состоит в том, чтобы попытаться найти порядок генов, который имеет лучший эволюционный потенциал. Многие исследователи использовали инверсию в своих работах, однако мало кто пытался ее обосновать или определить ее вклад. Переупорядочение также значительно расширяет область поиска. Мало того, что генетический алгоритм пытается находить «хорошие» множества генов, но он также одновременно пробует находить хорошее упорядочение генов. Это гораздо более трудная задача для решения. Еще раз отметим, что оператор переупорядочения не изменяет фенотипа индивидуума, а изменяет лишь структуру хромосомы.
Как правило, выделяют еще один оператор для генетических алгоритмов – оператор генерации случайной особи, который может быть использован при создании начальной популяции, при пополнении популяции случайными особями и при некоторых мутациях.
|
