Основы теории эволюционных вычислений

 
Министерство образования и науки 
РОССИЙСКОЙ ФЕДЕРАЦИИ 

 
Федеральное государственное автономное образовательное 
учреждение высшего профессионального образования 
«ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ» 
 
Технологический институт, г. Таганрог 
 
 
 
В. М. КУРЕЙЧИК 
В. В. КУРЕЙЧИК 
С. И. РОДЗИН 
Л.А. ГЛАДКОВ 
 
 
 
 
ОСНОВЫ  ТЕОРИИ 
ЭВОЛЮЦИОННЫХ ВЫЧИСЛЕНИЙ 
 

 
 
 
 
Ростов-на-Дону 
Издательство Южного федерального университета 
2010 
 

УДК 519.7:004.8 + 004.8.023; 004.81.85 
ББК  32.965 
          К 93 
 
Печатается по решению редакционно-издательского совета 
Южного федерального университета 
 
Рецензенты: 
первый проректор по учебной работе ТГПИ, доктор технических 
наук, профессор, Витиска Н.И., 
зав. кафедрой компьютерных образовательных технологий 
СПбГУИТМО, доктор технических наук, профессор, Лисицына Л.С. 
 
Монография подготовлена и издана в рамках национального проекта 
«Образование» по «Программе развития федерального государственного  
образовательного учреждения высшего профессионального образования  
«Южный федеральный университет» на 2007–2010 гг.» 

 
К 93     Основы теории эволюционных вычислений: научная 
монография /  В.М. Курейчик, В.В. Курейчик, С.И. Родзин – Ростов 
н/Д: Изд-во ЮФУ, 2010. − 222 с. 
Ил. 35. Библиогр.: 61 назв. 
ISBN 978-5-9275-0799-3 
Вычисления − это 
физический 
процесс. 
В 
природе 
действуют 
эволюционные процессы. Поэтому естественно говорить об эволюционных 
вычислениях, инспирированных природными системами. В книге делается 
попытка 
решения 
фундаментальной 
проблемы 
вычислительного 
интеллекта, связанной с разработкой общей теории эволюционных 
вычислений, инспирированных природными системами, математических 
моделей и эффективных форм распределенных алгоритмов эволюционных 
вычислений, а также изучаются когнитивные возможности композиции 
эволюционных операторов1. 
Монография адресована магистрам и аспирантам, изучающим теорию 
и практику создания интеллектуальных информационных систем и 
технологий. Книга может быть также полезна специалистам по системному 
анализу, теоретической информатике, автоматизации проектирования и 
управления, 
компьютерному 
моделированию 
и 
вычислительной 
математике. 
 
ISBN 978-5-9275-0799-3                          УДК 519.7:004.8 + 004.8.023; 004.81.85 
ББК  32.965 
 
 
© Курейчик В.М. , Курейчик В.В., Родзин С.И., 2010 
© Южный федеральный университет, 2010 
 
 
      1 Работа выполнена при поддержке грантов РФФИ 09-01-00492,  
         10-01-90017-Бел-а 

Содержание 
Введение............................................................................................. 5 

1. Анализ 
базовых 
моделей 
эволюционных 

вычислений, 
инспирированных 
природными 

системами .................................................................................... 9 

1.1. Таксономия эволюционных вычислений ............................. 9 

1.2. Модель генетических алгоритмов .................................... 14 

1.3. Модель генетического программирования ....................... 19 

1.4. Модель эволюционных стратегий ..................................... 24 

1.5. Модель эволюционного программирования ...................... 27 

1.6. Модель роевого интеллекта ............................................... 29 

1.7. Квантовая модель ................................................................. 33 

1.8. Другие эвристические модели, основанные на 

природных аналогиях ................................................................ 37 

2. Общая 
теория 
эволюционных 
вычислений, 

инспирированных природными системами ...................... 43 

2.1 Гипотезы и закономерности эволюционных 

вычислений .................................................................................. 43 

2.2. Основные положения теории эволюционных 

вычислений .................................................................................. 45 

2.3. Универсальная феноменологическая модель 

эволюционных вычислений ...................................................... 51 

2.4. Достоинства и отличительные особенности 

теории эволюционных вычислений ........................................ 54 

2.5. Общие правила представления решений в 

моделях эволюционных вычислений ...................................... 56 

2.6. Когнитивные возможности универсальной 

феноменологической модели эволюционных 

вычислений .................................................................................. 62 

2.7. Базовый цикл эволюционных вычислений ........................ 86 

3. Алгоритмы 
эволюционных 
вычислений, 

параллелизм .............................................................................. 91 

3.1. Алгоритмы эволюционных вычислений ........................... 91 

3.2. Организация параллельных эволюционных 

вычислений ................................................................................ 192 

3.3. Инструментальные средства для поддержки 

теории эволюционных вычислений ...................................... 203 

Заключение ................................................................................... 207 

Список использованных источников ...................................... 210 

Список используемых определений и сокращений ............. 216 

Персоналии ................................................................................... 220 

 
 
 
 
 
 
 
 
 
 

Природа  любит  скрываться 
Гераклит 
 
                                    Введение 

 
Интерес исследователей к решению математических 
проблем искусственного интеллекта возрастает, особенно в 
области разработки алгоритмов и компьютерных программ, 
использующих простые механизмы изменчивости и отбора 
по аналогии с эволюцией в природе. Идеи теории эволюции 
не бесспорны, однако они объясняют широкий спектр 
наблюдаемых явлений, а их потенциал не ограничивается 
только генетическими алгоритмами, эффективность которых 
известна давно. Необходима теория, обобщающая различные 
парадигмы эволюционных вычислений, инспирированных 
природными системами, опирающаяся на единую концепцию 
и 
когнитивные 
механизмы 
алгоритмов 
эволюционных 
вычислений, 
на 
возможности 
их 
распараллеливания. 
Обзорный 
анализ 
публикаций 
[Букатова, 1979; 
Емельянов, 2003; 
Курейчик, 2002; 
Поппер, 2000; 
Растригин, 1981; Редько, 2005; Родзин, 2005; Северцов, 2005; 
Abraham, 2006; Holland, 1975; Koza, 1992; Nissen, 1997], 
знакомство и сопоставление с разработками в данной 
области дают основание утверждать, что решение этой 
фундаментальной проблемы требует комплексного подхода и 
является актуальной научной задачей, имеющей широкое 
прикладное значение. 
Главная 
трудность 
при 
построении 
эволюционных 
вычислений, 
инспирированных 
природными 
системами, 
и 
применении этих вычислений в прикладных задачах, состоит в 
том, что природные системы довольно хаотичные, а все наши 

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

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

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

Математик строит модели, 
совершенные сами по себе (то 
есть совершенные по своей 
точности), но он не знает, модели 
чего он создает 
 
1. Анализ базовых моделей эволюционных 
вычислений, 
инспирированных 
природными 
системами 

1.1. Таксономия эволюционных вычислений 

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

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

сравниваются и обмениваются информацией друг с другом. 
Поэтому 
эволюционные 
вычисления 
способны 
выдать 
фантастический скачок производительности по сравнению со 
случайным поиском и «перемолоть» самые трудные задачи. 
Казалось бы, типичное случайное решение в среднем ничего 
интересного из себя не представляет, и эффективность его крайне 
низка. Но стоит только множеству решений в процессе 
эволюционных вычислений начать взаимодействовать между 
собой, как хорошее решение быстро появляется и прогрессирует. 
Конечно, ход естественной эволюции гораздо сложнее и 
эффективнее, нежели любой эволюционный алгоритм. Тем не 
менее, эволюционный алгоритм может находить эффективные 
решения в самых разных областях, когда даже неизвестно, как 
искать 
правильное 
решение. 
В 
пользу 
эволюционных 
вычислений говорит то обстоятельство, что жизнь на Земле (и 
разум), вероятно, появилась именно по таким принципам 
[Вернадский, 2006; Дарвин, 2003]. Эволюционные вычисления 
становятся ещё более эффективными, если популяция решений и 
операторы, их преобразующие, учитывают внешние данные и 
внутреннее состояние системы в текущий момент. Поскольку 
оценка и принятие решений при эволюционных вычислениях 
производятся на каждом шаге эволюции, то это выгодно 
отличает их от процедурных алгоритмов поиска оптимального 
решения. 
Несмотря 
на 
кажущуюся 
хаотичность, 
процедура 
эволюционного поиска является очень устойчивой. Главное, 
чтобы у нас был хоть какой-то критерий оценки качества 
получаемых решений, т.е. признак, на основании которого 
производится сравнительная оценка возможных решений и 
выбор наилучшего. Этого достаточно, чтобы эволюционный 
алгоритм заработал. Для реальных практических задач такой 
критерий обычно имеется. 
Оценка решений в процессе эволюционных вычислений 
должна быть кумулятивной, т.е. накапливаться, давая каждому 

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