Введение в эволюционное моделирование. Каширина И.Л. - 11 стр.

                                   11
сто становится стахостическим, что увеличивает вероятность выхода попу-
ляции из локального оптимума.
      Иногда (с целью повышения средней приспособленности популяции)
допустимо осуществлять направленные мутации, т. е. после каждого изме-
нения хромосомы проверять, повысилась ли в результате этой мутации ее
приспособленность и, если нет, возвращать хромосому к исходному состоя-
нию.
                    Формирование нового поколения
       После скрещивания и мутации особей необходимо решить проблему о
том, какие из новых особей войдут в следующее поколение, а какие � �
нет, и что делать с их предками. Есть два наиболее распространенных спосо-
ба.
    1. Новые особи (потомки) занимают места своих родителей. После чего
       наступает следующий этап, в котором потомки оцениваются, отбира-
       ются, дают потомство и уступают место своим "детям".
    2. Следующая популяция включает в себя как родителей, так и их потом-
       ков.
       Во втором случае необходимо дополнительно определить, какие из
особей родителей и потомков попадут в новое поколение. В простейшем
случае, в него после каждого скрещивания включаются две лучших особи из
четверки родителей и их потомков. Более эффективным является механизм
вытеснения, который реализуется таким образом, что стремится удалять
«похожие» хромосомы из популяции и оставлять отличающиеся.
Принцип "элитизма"
Суть этого принципа заключается в том, что в новое поколение всегда вклю-
чаются лучшие родительские особи. Их число может быть от 1 и больше.
Использование "элитизма" позволяет не потерять хорошее промежуточное
решение, но в то же время из-за этого алгоритм может "застрять" в локаль-
ном экстремуме. В большинстве случаев "элитизм" не вредит поиску реше-
ния, и главное � � это предоставить алгоритму возможность анализировать
разные хромосомы из пространства поиска.
                           Останов алгоритма
     Работа ГА представляет собой итерационный процесс, который про-
должается до тех пор, пока не пройдет заданное число поколений или не вы-
полнится какой-либо иной критерий останова. В оптимизационных задачах
традиционными критериями останова алгоритма являются, например, дли-
тельное отсутствие прогресса в смысле улучшения значения средней (или
лучшей) приспособленности популяции, малая разница между лучшим и
худшим значением приспособленности для текущей популяции и т.п.