Эволюционное моделирование и его применение

В.И. Аверченков, П.В. Казаков

ЭВОЛЮЦИОННОЕ МОДЕЛИРОВАНИЕ 
И ЕГО ПРИМЕНЕНИЕ

Монография 

4-е издание, стереотипное

Москва 
Издательство «ФЛИНТА»  
2021 

УДК 004.89+004.021 
А19 

Аверченков В.И.  
А19   Эволюционное моделирование и его применение: монография / В.И. 
Аверченков, П.В. Казаков. — 4-е изд., стер. — Москва : ФЛИНТА, 
2021. — 200 с. — ISBN 978-5-9765-1264-1. — Текст : электронный.

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

УДК 004.89+004.021 

ISBN 978-5-9765-1264-1     
© Издательство «ФЛИНТА», 2016 
© Аверченков В.И., Казаков П.В., 2016 

ПРЕДИСЛОВИЕ

В настоящее время неотъемлемой составляющей переднего края 

исследований научного направления «Искусственный интеллект» являются так называемые «мягкие вычисления» (soft computing), объединяющие нечеткие системы, искусственные нейронные сети и эволюционные алгоритмы. Большое количество русскоязычных публикаций, посвященных первым двум разделам мягких вычислений, свидетельствует о неослабляющем интересе к ним, подтверждает большие перспективность их исследований и эффективность применения 
при решении соответствующего класса задач. Что касается эволюционных алгоритмов, то объем исследований, связанных с ними, выглядит в сравнении гораздо скромнее. В то же время эта неотъемлемая 
составляющая мягких вычислений образует целое фундаментальное 
научное направление, известное как эволюционное моделирование. 
Оно находит применение при решении различных классов задач, 
включающих оптимизацию, моделирование адаптивного поведения, 
моделирование эволюционных процессов в социальных, экономических и технических системах, которым наиболее свойственны основные принципы эволюции. Заимствование законов развития природы 
позволяет подойти к решению этих задач в более широком, универсальном смысле без ограничений ранее разработанных математических моделей их описания.

Зарубежные исследования в области эволюционного моделиро
вания объединены в направление, которое называется эволюционные 
вычисления (evolutionary computation). Научными и прикладными 
разработками в этой области занимаются во многих научных школах 
стран  Европы, Америки и Азии, а также научно-исследовательских 
центрах крупных компаний. Что отражает существенно большее, чем 
в Российской Федерации число публикаций и монографий по данной 
области искусственного интеллекта.

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

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

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

Вторая глава посвящена описанию эволюционных алгоритмов. 

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

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

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

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

ОСНОВНЫЕ  УПОТРЕБЛЯЕМЫЕ  ОБОЗНАЧЕНИЯ

}
,...,
,
{
2
1
nx
x
x
x 
- переменные оптимизации математической модели;

f(x) – целевая функция;

)
,...,
( 1
n
i
x
x

- ограничения на параметры математической модели;




j
j x
x ,
- нижняя и верхняя границы области определения переменной;

f(x*), f* – значение целевой функции в точке экстремума;
R(x) – функция штрафа;

}
,...,
,
{
2
1
n
i
g
g
g
С 
- хромосома с номером i, описывающая одно 

решение   и состоящая из n числа генов;

)
(i
j
g
- ген номер j хромосомы 
i
C ;

f(
i
С ) – fitness-функция;

i
С (t) – хромосома 
i
C  поколения t;

)
(
i
C
L
– число бит в хромосоме 
i
C ;

)
(
j
g
L
- разрядность гена с номером j;

Np – размер популяции;
Ng –число поколений;
Nf – число вычислений функции;
Np(t) – размер популяции в поколении t;
Nt – число элементов в группе для турнирной схемы отбора;
Pm – вероятность применения оператора мутации;
Pc – вероятность применения оператора кроссинговера;
Pinv – вероятность применения оператора инверсии;
k – сайт кроссинговера;
K – фрагмент длины K хромосомы;
G(t) – поколение номер t;
С* - хромосома, соответствующая оптимальному решению;
(С*,
t)
– хромосома, соответствующая лучшему решению в 

поколении  t;

)
(
~

i
C
f
- нормированное значение fitness-функции;

)
(
i
C
f
- относительная оптимальность хромосомы 
i
C ;

)
(t
f
- средняя оптимальность поколения G(t);

))
(
(
t
H
f
- 
средняя 
оптимальность 
хромосом, 
содержащих 

шаблон H(t);

H – шаблон хромосомы;
(H) – порядок шаблона;
L(H) – длина шаблона;
P(H,d) – вероятность уничтожения шаблона;
P(H,s) – вероятность сохранения шаблона;
Pm(H,s) – вероятность сохранения шаблона после оператора мутации;
N(H(t)) 
–
число 
хромосом 
популяции 
G(t), 
содержащих 

шаблон H;

Nq – число запусков генетического алгоритма, когда  он 

 нашел оптимальное решение;

V – скорость сходимости генетического алгоритма;
 - эффективность генетического алгоритма.

ВВЕДЕНИЕ

В природе не происходит ничего, 
в чем не был бы виден смысл какого–
нибудь  максимума или  минимума.

Леонард  Эйлер

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

Эволюционное моделирование можно определить как направле
ние в искусственном интеллекте, в основе которого лежат принципы 
и понятийный аппарат, заимствованные из популяционной генетики и 
объединяющее компьютерные методы (генетические алгоритмы, генетическое программирование, эволюционное программирование и 
эволюционные стратегии) моделирования естественных эволюционных процессов. Происходящие в естественных системах эволюционные преобразования направлены на достижение аналогичной цели, 
что и в искусственных системах при решении оптимизационных задач. Только в последнем случае критерием «приспособленности» решения является его качество, оптимальность относительно других исследованных точек поискового пространства. Заимствование остальных ключевых свойств эволюции – наследственности, изменчивости 
и естественного отбора - выделило ЭМ в отдельную методологию 
решения оптимизационных задач. В том числе и таких, которые невозможно решить точными математическими методами из-за 

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

Основоположниками развития эволюционного моделирования 

как самостоятельного направления в области искусственного интеллекта принято считать Дж. Холланда, Л. Фогеля, А. Овена, М. Уолша, 
И. Букатову, Л. Расстригина и других исследователей. Их работы связаны с попытками воспроизвести с помощью математических моделей и алгоритмов основные механизмы эволюционных преобразований в естественных системах, характеризующихся постоянным 
стремлением достижения оптимальных форм существования в сочетании с минимальными затратами ресурсов. Созданная в итоге теория 
эволюционного моделирования (эволюционных вычислений) стала 
фундаментом для разработки принципиально новых компьютерных 
методов оптимизации в том числе задач, которые до этого считались 
неразрешимыми.

Трудно назвать естественную или искусственную систему, ко
торой бы не были свойственны эволюционные процессы развития. 
Главным из них является стратегия «выживает сильнейший». Применение методов ЭМ для исследования таких систем позволяет наиболее точно, не прибегая к модификации их математических моделей, 
определить оптимальные характеристики функционирования этих 
систем, новые структуры и формы их развития (эволюции). При этом 
используется главная концепция ЭМ искусственных систем: вместо 
моделирования системы в уже готовом виде следует заниматься исследованием эволюции образующих ее простых объектов. В итоге 
наблюдается их самоорганизация в направлении повышения качества 
свойств системы в целом.

Практические возможности эволюционного моделирования 

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

Отличительной чертой эволюционных алгоритмов от других 

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

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

- применение эволюционных алгоритмов для изучения и моде
лирования отдельных процессов естественной эволюции;

- совершенствование существующих искусственных систем 

путем наделения их свойствами адаптивного поведения и самоорганизации на основе методов эволюционного моделирования;

- автоматизация решения различных оптимизационных задач 

науки и техники.

Методы эволюционного моделирования можно рассматривать 

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