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

                                   14
но, интересный и является одной из разновидностей параллельных ГА. Дан-
ная модель генетического алгоритма обладает следующими свойствами.
   • Наличие нескольких популяций, как правило, одинакового фиксиро-
      ванного размера.
   • Фиксированная разрядность генов.
   • Любые комбинации стратегий отбора и формирования следующего
      поколения в каждой популяции. Можно сделать так, что в разных по-
      пуляциях будут использоваться разные комбинации стратегий, хотя
      даже один вариант дает разнообразные решения на различных "остро-
      вах".
   • Ограничений на тип кроссовера и мутации нет.
   • Случайный обмен особями между "островами". Если миграция будет
      слишком активной, то особенности островной модели будут сглажены
      и она будет не очень сильно отличаться от моделей ГА без паралле-
      лизма.
5. CHC (Eshelman)
      CHC расшифровывается как Cross-population selection, Heterogenous
recombination and Cataclysmic mutation. Данный алгоритм довольно быстро
сходится из-за того, что в нем нет мутаций, используются популяции не-
большого размера и отбор особей в следующее поколение ведется и между
родительскими особями, и между их потомками. После нахождения некото-
рого решения алгоритм перезапускается, причем лучшая особь копируется в
новую популяцию, а оставшиеся особи подвергаются сильной мутации (му-
тирует примерно треть битов в хромосоме) и поиск повторяется. Еще одной
специфичной чертой является стратегия скрещивания: все особи разбивают-
ся на пары, причем скрещиваются только те пары, в которых хромосомы
особей существенно различны (хэммингово расстояние больше некоторого
порога, плюс возможны ограничения на максимальную длину цепочки оди-
наковых бит). При скрещивании используется так называемый HUX-
оператор (Half Uniform Crossover) - это разновидность однородного кроссо-
вера, но в нем к каждому потомку попадает ровно половина битов хромосо-
мы от каждого родителя. Таким образом, модель обладает следующими
свойствами.
   • Фиксированный размер популяции.
   • Фиксированная разрядность генов.
   • Перезапуск алгоритма после нахождения решения.
   • Небольшая популяция.
   • Особи для скрещивания разбиваются на пары и скрещиваются при ус-
      ловии существенных отличий.
   • Отбор в следующее поколение проводится между родительскими осо-