Эвристический алгоритм оптимизации на основе генетического поиска

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

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

Основные отличия ГА от стандартных локальных (например, градиентных) и глобальных (например, случайных) алгоритмов оптимизации:

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

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

• для оценки «пригодности» решения и последующего эволюционного развития наряду с использованием целевой функции дополнительно моделируются «правила выживания», которые расширяют разнообразие множества реше­ний и определяют эволюционное развитие;

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

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

Схема простого генетического алгоритма представлена на рис. 2.

Рис. 2 Схема простого генетического алгоритма

Генетическим алгоритмом называется следующий объект:

ГА(Р°, r, l, sl, Fit, cr, m, ot),

где ГА - генетический алгоритм; Р° - исходная популяция; r - ко­личество элементов популяции; l - длина битовой строки, коди­рующей решение: sl – оператор селекции; Fit - функция фитнесса (функция полезности), определяющая «пригодность» решения; сr - оператор кроссинговера, определяющий возможность получения нового решения; т - оператор мутации; ot - оператор отбора.

Наименьшей неделимой единицей биологического вида, подверженной действию факторов эволюции, является особь Н^t_к (к - номер особи, t — момент времени эволюционного процесса). В качестве аналога особи в задаче опти­мизации принимается произвольное допустимое решение X Є D, которому присвоено имя Н^t_к. Действительно, вектор X - это наименьшая неделимая единица, характеризующая в экстремальной задаче внутренние параметры объекта оптимизации на каждом t- мшаге поиска оптимального решения, которые изменяют свои значения в процессе минимизации некоторого крите­рия оптимальности J (X).

Формирование популяции. Совокупность особей (Н^t ₁,..., Н^t_r)образуют популяцию Р^t (численностью r). Эволюция популяции Р^t рассматривается как чередование поколений (рис. 3). Номер поколения отождествляется с момен­том времени t = 0,1,.., Т,где T - жизненный цикл популяции, определяющий период ее эволюции. Совокупность генотипов всех особей Н^t_к образует хромо­сомный набор, который полностью содержит в себе генетическую информацию.

Рис. 3 Формирование популяции

Способы создания начальной популяции Р°. В настоящее время наиболее известными являются три стратегии создания начального мно­жества решений:

1) формирование полной популяции;

2) генерация случайного множества решений, достаточно большого, но не исчерпывающего все возможные вари­анты;

3) генерация множества решений, включающего разновидности одного решения.

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

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

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

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