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

Теория эволюции повлияла на изменение мировоззрения людей с самого своего появления. Теория, которую Чарльз Дарвин представил в работе, известной как "Происхождение Видов", в 1859 году, стала началом этого изменения. Многие области научного знания в настоящее время наслаждаются свободой мысли в атмосфере, которая многим обязана революции, вызванной теорией эволюции и развития. Но Дарвин, подобно многим своим современникам, кто предполагал, что в основе развития лежит естественный отбор, не мог не ошибаться. Например, он не смог показать механизм наследования, при котором поддерживается изменчивость. Это было на пятьдесят лет до того, как теория наследственности начала распространяться по миру, и за тридцать лет до того, как "эволюционный синтез" укрепил связь между теорией эволюции и относительно молодой наукой генетикой. Однако Дарвин выявил главный механизм развития: отбор в сочетании с изменчивостью или, как он его называл, "спуск с модификацией". Во многих случаях, специфические особенности развития через изменчивость и отбор все еще не бесспорны, однако, основные механизмы объясняют невероятно широкий спектр явлений, наблюдаемых в Природе.

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

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

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

История эволюционных вычислений началась с разработки ряда различных, независимых моделей. Основными из них были генетические алгоритмы и классификационные системы Голланда (Holland), опубликованные в начале 60-х годов и получившие всеобщее признание после выхода в свет книги, ставшей классикой в этой области, - "Адаптация в естественных и искусственных системах". В 70-х годах в рамках теории случайного поиска Растригиным Л.А. был предложен ряд алгоритмов, использующих идеи биологического поведения особей. Развитие этих идей нашло отражение в цикле работ Букатовой И.Л. по эволюционному моделированию. Развивая идеи о целесообразном и оптимальном поведении стохастических автоматов, Неймарк Ю.И. предложил осуществлять поиск глобального экстремума на основе коллектива независимых автоматов, моделирующих процессы развития и элиминации особей. Большой вклад в развитие эволюционного программирования внесли Фогел (Fogel) и Уолш (Walsh). Несмотря на разницу в подходах, каждая из этих "школ" взяла за основу ряд принципов, существующих в природе, и упростила их до такой степени, чтобы их можно было реализовать на компьютере.

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

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

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

2) системы, которые являются биологически более реалистичными, но которые не оказались особенно полезными в прикладном смысле. Они больше похожи на биологические системы и менее направлены (или не направлены вовсе). Они обладают сложным и интересным поведением, и, видимо, вскоре получат практическое применение.

Конечно, на практике мы не можем разделять эти вещи так строго. Эти категории - просто два полюса, между которыми лежат различные вычислительные системы. Ближе к первому полюсу - эволюционные алгоритмы, такие как Эволюционное Программирование (Evolutionary Programming), Генетические Алгоритмы (Genetic Algorithms) и Эволюционные Стратегии (Evolution Strategies). Ближе ко второму полюсу - системы, которые могут быть классифицированы как Искусственная Жизнь (Artificial Life).

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

2. Прикладное эволюционное моделирование

В эволюционном моделировании можно выделить:

1) модели возникновения молекулярно-генетических информационных систем,

2) моделирование общих закономерностей эволюции,

3) эволюционные модели искусственной жизни,

4) прикладное эволюционное моделирование.

В данном разделе я остановлюсь только на прикладном эволюционном моделировании.

Согласованность и эффективность работы элементов биологических организмов наводит на мысль – можно ли использовать принципы биологической эволюции для оптимизации практически важных для человека систем.

В нескольких модификациях подобные идеи возникали у ряда авторов. В 1966 году Л.Фогель, А.Оуенс, М.Уолш предложили схему эволюции логических автоматов, решающих задачи прогноза. Примерно в это же время группа немецких ученых (И.Рехенберг, Г.-П.Швефель и др.) начала разработку так называемой эволюционной стратегии. Эти работы заложили основы прикладного эволюционного моделирования или эволюционных алгоритмов.

В общем виде эволюционный алгоритм – это оптимизационный метод, базирующийся на эволюции популяции “особей”. Каждая особь характеризуется приспособленностью f(S) – многомерной функцией ее "генов" S = (S₁ , S₂ ,...,S_N). Задача оптимизации состоит в максимизации функции приспособленности f(S) . В процессе эволюции в результате отбора, рекомбинаций и мутаций геномов особей происходит поиск особей с высокими приспособленностями.

Основные эволюционные алгоритмы:

1) генетический алгоритм, предназначенный для оптимизации функций дискретных переменных и акцентирующий внимание на рекомбинациях геномов;

2) эволюционное программирование, ориентированное на оптимизацию непрерывных функций без использования рекомбинаций;

3) эволюционная стратегия, ориентированная на оптимизацию непрерывных функций с использованием рекомбинаций;

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

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

Часть 2. Генетические алгоритмы

1. Введение в генетические алгоритмы (ГА)

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

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

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

ГА состоит из следующих компонент:

Хромосома. Решение рассматриваемой проблемы. Состоит из генов.

Начальная популяция хромосом.

Набор операторов для генерации новых решений из предыдущей популяции.

Целевая функция для оценки приспособленности решений.

Чтобы применять ГА к задаче, сначала выбирается метод кодирование решений в виде строки. Фиксированная длина (l-бит) двоичной кодировки означает, что любая из 2^l возможных бинарных строк представляет возможное решение задачи.

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

2. Операторы ГА

Стандартные операторы для всех типов генетических алгоритмов это: селекция, скрещивание и мутация.

Селекция

Оператор селекции (reproduction, selection) осуществляет отбор хромосом в соответствии со значениями их функции приспособленности. Существуют как минимум два популярных типа оператора селекции: рулетка и турнир.

Метод рулетки (roulette-wheel selection) - отбирает особей с помощью n "запусков" рулетки. Колесо рулетки содержит по одному сектору для каждого члена популяции. Размер i-ого сектора пропорционален соответствующей величине P_sel(i) вычисляемой по формуле:

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

Selection
Рис. 1. Оператор селекции типа колеса рулетки с пропорциональными функции приспособленности секторами

Турнирный отбор (tournament selection) реализует n турниров, чтобы выбрать n особей. Каждый турнир построен на выборке k элементов из популяции, и выбора лучшей особи среди них. Наиболее распространен турнирный отбор с k=2.

Скрещивание

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

Crossover
Рис. 2. Одноточечный оператор скрещивания (точка разрыва равна трем)

Мутация

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

Mutation
Рис. 3. Оператор мутации (четвертый ген мутировал)

3. Алгоритм работы ГА

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

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

GA structure
Рис. 4. Алгоритм работы классического ГА

НАЧАЛО /* генетический алгоритм */

Создать начальную популяцию

Оценить приспособленность каждой особи

останов = FALSE

ПОКА НЕ останов ВЫПОЛНЯТЬ

НАЧАЛО /* создать популяцию нового поколения */

ПОВТОРИТЬ (размер_популяции/2) РАЗ

НАЧАЛО /* цикл воспроизводства */

Выбрать две особи с высокой приспособленностью из предыдущего поколения

Скрестить выбранные особи и получить двух потомков

Оценить приспособленности потомков

Поместить потомков в новое поколение

КОНЕЦ

ЕСЛИ популяция сошлась, ТО останов = TRUE

КОНЕЦ

4. Особенности генетических алгоритмов

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

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

Каждый вариант решения (для 30 городов) - это числовая строка, где на j-ом месте стоит номер j-ого по порядку обхода города. Таким образом, в этой задаче 30 параметров, причем не все комбинации значений допустимы. Естественно, первой идеей является полный перебор всех вариантов обхода.

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

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

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

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

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

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

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

Часть 3. Генетический алгоритм для решения многопараметрической непрерывной задачи оптимизации

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

1. Постановка задачи

Рассматривается непрерывная многопараметрическая задача оптимизации,

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

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

2. Эволюционный поиск

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

Реализацию базового генетического алгоритма можно представить как итерационный процесс, включающий несколько этапов:

1. генерация начальной популяции,

2. воспроизводство "потомков":

- выбор родительской пары,

- выбор и реализация одного из операторов кроссовера,

- выбор и реализация одного из операторов мутации,

3. создание репродукционной группы,

4. процедура отбора и формирование на его основе нового поколения,

5. если не выполнено условие останова, то перейти к п.2.

3. Тестовые задачи

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

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

Тестовая задача	Размерность	Свойства
De Jong 2	2	Овражная функция, один глобальный экстремум
De Jong 3	5	Разрывы типа "скачек", максимум достигается на гиперкубе
De Jong 5	2	Один глобальный на гиперкубе, 24 локальных максимума.
Griewank	2	Один глобальный и множество локальных максимумов.

De Jong 2

De Jong 3

De Jong 5

Griewank

4. Символьная модель

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

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

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

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

Для поиска оптимального разбиения пространства параметров на гиперкубы, кодируемые хромосомными наборами соответствующей длины NL (N - размерность задачи, L - длина кодировки одного гена), проводились испытания на четырех тестовых функция: De Jong 2, De Jong 3, De Jong 5 и функция Griewank'а. В качестве рассматриваемых вариантов были выбраны L₁=4, L₂=6, L₃=8, L₄=16. Эффективность поиска определялась по отношению среднему (усредненному по 50 запускам) значению приспособленности популяции к максимальному значению после 1000 вычислений функции, что соответствует порядка 23-25 поколениям, при численности популяции 50 и формировании 20 брачных пар на каждом поколении, вероятность мутации была около 0.001. Результаты эксперимента приведены на рисунке.

Как видно из представленной диаграммы уже после L=6 для представленных функций не происходит значительно улучшения эффективности поиска. Вообще, длина кодировки в значительной мере сказывается на функциях, ландшафту которых присущи скачкообразные изменения, как например у De Jong 3 или 5, и наоборот непрерывная функция De Jong 2, а тем более функция Griewank'а слабо чувствительны к длине кодировки. Очевидно, такая особенность объясняется разбросом значений приспособленностей особей, имеющих одинаковые генотипы, этот разброс тем больше, чем крупнее гиперкубы разбиения пространства. Поэтому в процессе поиска для таких функций сложнее определить хромосомные наборы, которые бы соответствовали оптимальному решению.

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

De Jong 2 (L=4)
De Jong 2 (L=10)
De Jong 5 (L=4)
De Jong 5 (L=10)

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

Формирование генотипов особей начальной популяции желательно проводить по принципу максимального побитого разнообразия. Максимальное побитовое разнообразие призвано обеспечить максимальное богатство генетического материала в начальной популяции.

5. Влияние параметров генетического алгоритма на эффективность поиска

Операторы кроссовера и мутации

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

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

De Jong 2	De Jong 3	Griewank (n=10)

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

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

Выбор родительской пары

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

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

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

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

Механизм отбора

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

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

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

- во-первых, не теряются лучшие найденные решения, обладающие различными хромосомными наборами,

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

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

6. Три задачи генетического алгоритма

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

- задача быстрой локализации одного оптимального значения,

- задача определения нескольких (или всех) глобальных экстремумов,

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

Основное различие в методах решения этих трех задач лежит в реализации различных уровней соотношения, которое в теории генетических алгоритмов называется как соотношение "исследование – использование".

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

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

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

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

Таблица

Выбор род	панмиксия		селективный		инбридинг		аутбридинг
Отбор	элитный	вытесн.	элитный	вытесн.	элитный	вытесн.	элитный	вытесн.
De Jong 2
Макс	99,999	99,964	99,998	99,982	99,999	99,983	99,986	99,98
Мин	92,254	90,735	83,529	80,211	83,725	88,445	91,754	94,843
ср.знач	98,038	98,666	96,595	96,903	98,464	98,833	98,811	98,639
De Jong 3
Макс	29	29	30	30	28	29	30	30
Мин	27	27	27	29	24	25	28	28
ср.знач	28,32	28,16	29,28	29,18	26,88	27,18	28,78	28,62
De Jong 5
макс	1,002	1,002	1,002	1,002	1,002	1,002	1,002	1,002
мин	0,502	0,55	0,202	0,966	0,202	0,715	0,988	0,91
ср.знач	0,982	0,981	0,985	1	0,962	0,978	1,001	0,991
Griewank n=2
макс	1	1	1	1	1	1	1	1
мин	0,836	0,871	0,871	0,871	0,871	0,869	0,872	0,906
ср.знач	0,963	0,977	0,953	0,96	0,946	0,97	0,993	0,988

В таблице приведены результаты поиска по 50 запускам при различных параметрах генетического алгоритма. Для всех примеров: L=6, численность популяции 50, число брачных пар 20, вероятность мутации 0.01.

Литература

1. Введение в ГА и Генетическое Программирование (http://algolist.manual.ru/ai/ga/intro.php)

2. Генетические алгоритмы - эволюционные методы поиска (http://algolist.manual.ru/ai/ga/ga3.php)

3. Генетические алгоритмы (http://www.ai.tsi.lv/ru/ga/ga_intro.html)

4. Машинная эволюция (http://re-tech.narod.ru/inf/ai/gl6.htm)

5. Курс лекций по предмету "Основы проектирования систем с искусственным интеллектом" (http://re-tech.narod.ru/inf/ai/lectures.htm)

6. Прикладное эволюционное моделирование. Генетический алгоритм. Оценка эффективности генетического алгоритма (http://www.keldysh.ru/pages/BioCyber/Lectures/Lecture10/Lecture10.html)

7. Оптимизация многоэкстремальных функций с помощью генетических алгоритмов (http://www.chat.ru/~saisa/index.html)