Критерием останова работы генетического алгоритма  может быть одно из трех событий:

     1) Сформировано заданное пользователем число поколений.

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

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

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

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

     Рассмотрим  теперь непосредственно работу генетического  алгоритма. Общая схема его работы представлена на рисунке 7. 
 
 
 
 

       

     

     

     

     

     

     

     

     

     Рисунок 7 – Схема работы генетического  алгоритма 

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

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

     Рассмотрим  простейший оператор скрещивания. Он выполняется  в два этапа. Пусть особь представляет собой строку из т элементов. На первом этапе равновероятно выбирается натуральное число k от 1 до т-1. Это число называется точкой разбиения. В соответствии с ним обе исходные строки разбиваются на две подстроки. На втором этапе строки обмениваются своими подстроками, лежащими после точки разбиения, то есть элементами с k+1-го по m-й. Так получаются две новые строки, которые наследовали частично свойства обоих родителей. Этот процесс проиллюстрирован ниже.

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

     К =   (1   -   Р)   *  N, (7.2)

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

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

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

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

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

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

 

       

     4 ЭФФЕКТИВНОСТЬ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ И СРЕДСТВА ЕЕ ПОВЫШЕНИЯ

     4.1 Показатели эффективности  генетических алгоритмов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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