В этом пункте приведено описание некоторых модификаций генетического алгоритма.
1) Канонический генетический период [102]. Данная модель алгоритма является классической, и ее характеристики:
· Фиксированный размер популяции
· Фиксированная разрядность генов
· Пропорциональный отбор
· Особи для скрещивания выбираются случайным образом
· Одноточечный кроссовер и одноточечная мутация
· Следующее поколения формируется из потомков текущего поколения без «элитизма». Потомки занимают места своих родителей.
2) Алгоритм с замещением наименее приспособленной особи [104]. В данном алгоритме используется специфичная стратегия отбора. Вначале как я в классическом случае, популяция инициализируется, причем получается только один потомок, который оценивается и занимает место наименее приспособленной особи. После этого снова случайным образом выбираются 2 особи, и их потомок занимает место особи с самой низкой приспособленностью. Таким образом, на каждом шаге популяции обновляется только одна особь. Отсутствует выделенные эпохи формирования новых поколений. Подводя итоги, можно выделить следующие характерные особенности:
· Фиксированный размер популяции
· Особи для скрещивания выбираются случайным образом
· Ограничений на тип кроссовера и мутации нет
· В результате скрещивания особей получается один потомок, который занимает место наименее приспособленной особи.
3) Гибридный алгоритм [107,108]. Использованные гибридного алгоритма позволяет объединять преимущества генетического с преимуществами классических методов. Генетические алгоритмы позволяют находить решение, близкое к оптимальному но точнее определение максимума функции зачастую занимает очень много времени в силу стохатичности принципов работы алгоритма. Поэтому возникла идея использовать генетический алгоритм на начальном этапе для эффективного поиска окрестности глобального экстремума, а затем, взяв лучшую особь, применить один из «классических» методов оптимизации. Характеристики алгоритма:
· Фиксированный размер популяции
· Любые комбинации стратегии отбора и формирования следующего поколения
· Ограничений на тип кроссовера и мутации нет
· Генетический алгоритм применяется на начальном этапе, а затем после небольшого числа итераций в работу включается метод поиска локального экстремума.
4) Островная модель генетического алгоритма [104]. Эта модификация также заимствована из биологии с следующей ситуации: имеется группа близкорасположенных островов, на которых живут популяции особей одного вида. Эти популяции развиваются независимо, и только изредка происходит обмен представителями между популяциями. Основная модель генетического алгоритма использует описанный принцип для поиска решения. Данная модель генетического алгоритма обладает следующими свойствами:
· Наличие нескольких популяции, как правило, одинакового фиксированного размера.
· Любые комбинации стратегий отбора и формирования следующего поколения в каждой популяции. Можно сделать так, что в разных популяциях будут использоваться разные комбинации стратегий.
· Ограничений на тип кроссовера и тип мутаций нет.
· Случайный обмен особями между «островами» после определенного шага схемы генетического алгоритма.
5) Алгоритм с периодическим перезапуском [109]. Данный алгоритм довольно быстро сходится из-за того, что в нем нет мутаций, используются популяций небольшого размера, и отбор особей в следующее поколение ведется и между родительскими особями и между потомками. Из-за этого после некоторого количества эпох алгоритм может сойтись к локальному экстремуму. После этого алгоритм перезапускается, причем лучшая особь копируется в новую популяцию, а оставшиеся особи подвергаются сильной мутации (мутирует примерно треть генов хромосомы) и поиск повторяется. Ещё одной специфической чертой является стратегия скрещивания: все особи разбиваются на пары, причем скрещиваются только те пары, в которых хромосомы особей существенно различны. При скрещивании используется так называемый – половинный однородный кроссовер – это разновидность кроссовера, в котором каждому потомку попадает ровно половина генов хромосомы от каждого родителя. Таким образом, модель обладает следующими свойствами:
· Фиксированный размер популяции.
· Перезапуск алгоритма после нахождения решения после определенного шага.
· Небольшая популяция.
· Особи для скрещивания разбиваются на пары и скрещиваются при условии существенных отличий.
· Отбор в следующее поколение проводится между родительскими особями и потомками.
· Используется половинный однородный кроссовер.
· Макромутация при перезапуске.
Какой из перечисленных алгоритмов наиболее эффективен, зависит от решаемой задачи и вида оптимизируемой функции.
Таким образом, генетические алгоритмы представляют мощный аппарат для решения задач оптимизации. Разработано большое количество различных модификаций и усовершенствований генетического алгоритма, которые повышают его эффективность и позволяют с той или иной степенью точности предсказать требуемое вычислительное время [106,110]. В последнее время генетический алгоритм нашёл широкое применение для решения различных прикладных задач лазерной физики [107-108,111-112].
Выводы:
Таким образом, подводя сравнение различных итерационных алгоритмов можно сделать следующие выводы:
1) алгоритм последовательного градиентного спуска для случая восстановления фазы по одному распределению интенсивности эквивалентен алгоритму минимизации ошибки, а в случае двух известных распределений интенсивности имеет сходство с алгоритмом Гершберга- Сакстона;
2) важным критерием при выборе того или иного метода является скорость его сходимости. В ходе исследований было установлено, что наиболее быстрой сходимостью из предложенных методов обладает INPUT-OUTPUT алгоритм.
3) вопрос получения однозначного решения для задачи восстановления фазы из распределений интенсивности так же представляет большой интерес. При решении двумерных задач данные методы позволяют получить однозначное распределение фазы.
4) алгоритмы глобального поиска имитирующие процессы эволюции в природе способны отыскать глобальный экстремум многоэкстремальной функции.