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

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

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

1) разработка новых методов тестирования генетических алгоритмов;
разработка адаптивных генетических алгоритмов;

2) расширение круга решаемых с использованием генетических алго­ритмов задач;

3) максимальное приближение генетических алгоритмов к естествен­ному эволюционному процессу.

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

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

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

В первом же случае применяется структурирование популяции реше­ний на основе одного из двух подходов:

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

2)Для каждой особи устанавливается ее пространственное положе­ние в популяции. Скрещивание в процессе работы происходит между ближайшими особями. Такой подход получил название концепции скрещивания в локальной области.


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

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

Устойчивость работы генетических алгоритмов

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

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

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

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

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

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

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

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

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

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

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

- случайный равновероятный отбор;

- рангово-пропорциональный отбор;

- отбор пропорционально значению целевой функции.

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

- случайное равновероятное удаление;

- удаление К наихудших;

- удаление, обратно пропорциональное значению целевой функции.

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

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

Однако практика показала, что иногда бывает полезно варьировать размер популяции в определенных пределах. Подобные алгоритмы полу­чили название поколенческих [82]. В данном случае после очередного по­рождения потомков усечения популяции не происходит. Таким образом, на протяжении нескольких итераций размер популяции может расти, пока не достигнет определенного порога, После чего популяция усекается до своего исходного размера. Такой подход способствует расширению обла­сти поиска, но вместе с тем не ведет к значительному снижению скорости, поскольку усечение популяции, хотя и реже, но все же происходит.

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

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

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

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

Друзья! Приглашаем вас к обсуждению. Если у вас есть своё мнение, напишите нам в комментарии.