Элементы теории эволюционных алгоритмов

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ
РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное автономное образовательное
учреждение высшего образования
ОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
им. Ф.М. ДОСТОЕВСКОГО
А. В. Еремеев
ЭЛЕМЕНТЫ ТЕОРИИ
ЭВОЛЮЦИОННЫХ АЛГОРИТМОВ
Учебное пособие
c
○Еремеев А. В., 2024
c
○ФГАОУ ВО «ОмГУ
им. Ф.М. Достоевского», 2024
ISBN 978-5-7779-2677-7
Омск
2024

УДК 510
ББК 22.12я73я05
Е700
Рецензенты:
канд. физ.-мат. наук П.А. Борисовский
(Институт математики им. С.Л. Соболева СО РАН),
канд. физ.-мат. наук, доцент Т.В. Леванова
(ОмГУ им. Ф.М. Достоевского)
Еремеев, А. В.
Е700
Элементы теории эволюционных алгоритмов : учебное пособие / А. В. Еремеев. – Омск : Издательство Омского государственного университета, 2024. – 1 CD-ROM. – Загл. с титул.
экрана.
ISBN 978-5-7779-2677-7
Учебное пособие содержит материал по дисциплине «Эволюционные алгоритмы», преподаваемой автором в течение ряда лет.
Рассматривается классический генетический алгоритм, различные
его модификации, а также эволюционные алгоритмы в целом. Основные теоремы приведены с полными доказательствами. Рассматриваются приложения эволюционных алгоритмов к задаче целочисленного линейного программирования, задачам о максимальном
разрезе, о наибольшем независимом множестве вершин и др.
Для студентов высших учебных заведений, обучающихся по направлению подготовки магистров 01.04.02 «Прикладная математика и информатика» и специализирующихся в области методов оптимизации, исследования операций и искусственного интеллекта.
УДК 510
ББК 22.12я73я05
Текстовое электронное издание
Самостоятельное электронное издание
Минимальные системные требования:
процессор с частотой 1,3 ГГц или выше; ОЗУ 512 Мб; Microsoft Windows XP/
Vista/7/8/10 и выше; Adobe Acrobat Reader 8.0 и выше; CD-ROM; мышь
c
○Еремеев А. В., 2024
c
○ФГАОУ ВО «ОмГУ
им. Ф.М. Достоевского», 2024

Оглавление
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
1. Классический генетический алгоритм . . . . . . . . . . . . . . . . .
9
1.1. Процедуры кроссинговера и мутации ....................... 12
1.2. Примеры использования классического генетического
алгоритма .................................................... 13
1.2.1. Максимизация функции 𝑓: {𝑎, . . . , 𝑏} →N .............. 13
1.2.2. Задача о разрезе максимального веса ................... 13
1.2.3. Задачи непрерывной оптимизации и геометрический
смысл кроссинговера .................................... 14
1.2.4. Учет ограничений задачи ................................ 17
1.2.5. Задача целочисленного линейного программирования . 18
1.2.6. Простейшая задача размещения производства.......... 20
1.3. Теорема о схемах............................................. 22
1.4. Анализ разнообразия популяции ............................ 26
1.5. Время первого достижения оптимума ...................... 28
1.6. Контрольные вопросы ....................................... 30
2. Модификации генетического алгоритма . . . . . . . . . . . . . . . 31
2.1. Операторы селекции ......................................... 31
2.1.1. Стохастическая универсальная селекция Бэкера ....... 31
2.1.2. Ранжирование особей в операторах селекции ........... 33
2.1.3. Ранговая селекция ....................................... 34
2.1.4. Турнирная селекция ..................................... 35
2.1.5. Оператор (𝜇, 𝜆)-селекции ................................ 36
2.2. Стратегии управления популяцией.......................... 36
2.3. Операторы скрещивания и мутации ........................ 38
3

2.3.1. Кроссинговер с частичным отображением для задач
на перестановках ......................................... 39
2.3.2. Порядковый кроссинговер для задач на перестановках 41
2.3.3. Мутация в задачах на перестановках.................... 41
2.4. Задача оптимальной рекомбинации ......................... 42
2.5. Генетический алгоритм как метод локального поиска ..... 44
2.5.1. Задачи комбинаторной оптимизации .................... 44
2.5.2. Задача поиска локального оптимума .................... 46
2.5.3. Достижение локальных оптимумов генетическим алгоритмом ................................................. 46
2.5.4. Задача OneMax ........................................... 52
2.5.5. Полиномиально ограниченные задачи ................... 53
2.6. Контрольные вопросы ....................................... 54
3. Эволюционные алгоритмы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.1. Общий вид операторов ...................................... 55
3.2. Эволюционные стратегии (𝜇, 𝜆)-ES и (𝜇+ 𝜆)-ES ........... 57
3.3. Сходимость эволюционных алгоритмов ..................... 59
3.4. Алгоритмы генетического программирования .............. 66
3.5. Алгоритм поиска с запретами ............................... 68
3.5.1. Общая схема поиска с запретами ........................ 68
3.5.2. Вероятностный поиск с запретами....................... 69
3.6. Сравнение (1+1) EA с другими эволюционными алгоритмами ...................................................... 70
3.6.1. Среднее время достижения оптимума и средняя приспособленность на заданной итерации................... 73
3.7. Контрольные вопросы ....................................... 74
Список использованной и рекомендуемой литературы . . . 75
4

Введение
Эволюционные алгоритмы (ЭА), к котоpым можно отнести эволюционные стратегии, генетические алгоpитмы, эволюционное программирование, беpут свое начало в pаботах А.Г. Ивахненко [13],
Л.А. Растригина [20], Дж. Холланда [49], И. Реченбеpга [61], Л. Фогеля, А. Оуэнса, М. Уолша [24] и дp., вышедших в 60–70-х годах
XX века. Основная идея ЭА состоит в компьютеpном моделиpовании
пpоцесса эволюции. Пpи этом моделиpование пpедназначено не для
исследования биологических популяций, а для pешения пpактических задач пpикладной математики, в частности задач оптимизации.
Области применения ЭА: экономика, управление, инженерные
задачи, переработка информации, космос, медицина и т. д. Область
эволюционных вычислений возникла на стыке биологии и прикладной математики (искусственный интеллект, методы оптимизации,
теория вероятностей). В настоящее время ЭА зачастую относятся
к методам искусственного интеллекта. С одной стороны, эти алгоритмы позволяют решать задачи машинного обучения, такие как
задачи символьной регрессии, оптимизация структуры нейронной
сети, выбор модели машинного обучения и др. С другой стороны,
в процессе работы этих алгоритмов используются эвристики, традиционно применяемые человеком для принятия решений, такие как
метод проб и ошибок (эволюционная стратегия (1+1) ES), жадная
эвристика (декодирование решений), комбинация нескольких известных идей в одном изобретении (оператор рекомбинации), адаптация к среде (локальная оптимизация). Наконец, во многих системах
искусственного интеллекта требуется решать задачи оптимизации
большой размерности, которые не удается решить классическими методами математического программирования, однако ЭА позволяют
находить для них приемлемые решения.
Один из типичных представителей эволюционных алгоритмов
в оптимизации – генетический алгоритм (ГА). При запуске ГА со5

здается «виpтуальная» популяция особей (как пpавило, достаточно
хpанить только их генотипы), каждая из которых пpедставляет элемент пpостpанства pешений оптимизационной задачи. Здесь и далее
используются некоторые термины, заимствованные из биологии [21].
Пpиспособленность особей к условиям окpужающей сpеды выpажается некотоpой монотонной функцией от значения целевой функции задачи. Чем лучше pешение – тем выше приспособленность особей с соответствующим генотипом. Популяция pазвивается за счет
отбоpа более пpигодных особей и пpименения к ним случайных опеpатоpов, имитиpующих мутацию генов и рекомбинацию pодительских генотипов (кроссинговер).
Отбоp может осуществляться по-pазному. Особенно распpостpаненными являются опеpатоpы пpопоpциональной селекции (веpоятность выбоpа пpопоpциональна пpигодности), сpезающей селекции
(задается pавномеpным pаспpеделением на множестве из 𝑇% лучших генотипов популяции) и туpниpной селекции (𝑠особей извлекаются с помощью pавномеpного pаспpеделения, затем беpется лучшая
из них).
Генетический алгоритм представляет собой универсальную схему
решения широкого круга задач. Достаточно определить представление решений в виде генотипа, выбрать операторы селекции и кроссинговера, и алгоритм можно применять. Более того, при достаточно
общих предположениях можно доказать, что с вероятностью единица алгоритм находит оптимальное решение, если время его работы
не ограничено.
В области эволюционных алгоритмов находит себе пpименение
бионический подход, состоящий в заимствовании пpинципов организации систем из живой пpиpоды. В данном случае имеет место
использование принципа постепенных адаптивных преобразований
в пределах популяции или вида в ходе так называемой микpоэволюции. Как показывают исследования академика Ю.П. Алтухова
и других авторов (см.: [1, § 6.4]), более «масштабная» межвидовая
изменчивость (макроэволюция) требует скачкообразных перестроек генотипа и не может быть выведена непосредственно из постепенной внутривидовой изменчивости. Среди специалистов по мето6

дам случайного поиска распространено мнение, что, хотя эволюционные алгоритмы и подобны природным генетическим «механизмам»,
биологические принципы не следует рассматривать как ограничения при построении оптимизационных алгоритмов. Л.А. Растригин:
«...стремление к моделям механизмов биологической эволюции не
должно быть чрезмерным, т. к. они созданы природой (и/или Творцом) для развития биологических существ. Переносить их без поправок на развитие технических объектов было бы серьезной методологической ошибкой»1 [60, p. 141]. Чрезвычайно малые вероятности реализации элементарных сценариев эволюционного развития2
не позволяют использовать аналогии с макроэволюцией и процессами видообразования для обоснования работоспособности эволюционных алгоритмов. Вместо этого в теории эволюционных алгоритмов проводятся непосредственные исследования ЭА с использованием теории сложности и теории вероятностей (см.: [65, § 1.3]). В частности, такие результаты рассматриваются далее, в разделах 2.5 и 3.
Генетические алгоритмы, наряду с алгоритмами имитации отжига, поиска с запретами и муравьиной колонии и др., относятся к классу метаэвристик. Вообще, эвристикой (от греч. heurisko – обнару1 Перевод автора.
2 Для примера оценим вероятность возникновения нового белка из 150 аминокислот в результате случайных мутаций. Одна аминокислота кодируется триплетом нуклеотидов, т. е. для кодировки белка необходимо 450 нуклеотидных
позиций в молекуле ДНК. Было бы серьезным упрощением считать, что заданным требованиям удовлетворяет только одна последовательность аминокислот.
Однако можно считать, что примерно половина из нуклеотидных позиций имеют не более двух «подходящих» нуклеотидов (ср., например: [32]) и вероятность
случайного получения требуемого нуклеотида в такой позиции не больше 0,5.
Тогда вероятность получения подходящего белка при однократном испытании
(случайном выстраивании 450 нуклеотидов) не превышает 2−225 ≈10−67. Оценим число таких испытаний за историю Земли. Число бактерий на Земле оценивается как 2 · 1030 (см.: [44]). Число нуклеотидов в геноме одной бактерии – до
12,2 млн [58]. За год наиболее быстро размножающиеся бактерии e.coli проходят
около 2 000 поколений. Возраст Земли оценивается как 4 · 109 лет. Тогда общее
число испытаний не превышает величины порядка 2 · 1030 · 12,2·106
450
· 8 · 1012 ≈1047
и вероятность хотя бы однократного получения подходящего белка за историю
Земли не превышает 10−20.
7

живаю) называют метод решения, основанный на неформальных,
интуитивных соображениях, не гарантирующий получения наилучшего решения. Метаэвристика является эвристикой с универсальной
схемой, применимой для поиска приближенных решений различных
оптимизационных задач и представляющей собой итерационный процесс, в котором многократно используются подчиненные эвристики,
учитывающие особенности задачи. В метаэвристике могут использоваться различные принципы исследования пространства решений
и стратегии адаптации для учета полученной информации. На каждой итерации метаэвристики могут выполняться операции с единственным текущим решением (или частичным решением) либо с набором (популяцией) решений. Подчиненные эвристики могут быть
процедурами высокого или низкого уровня, простым локальным поиском, градиентным методом построения решения или классическими оптимизационными процедурами.
Ограниченный объем настоящего пособия не позволяет дать подробного изложения различных подходов к применению ГА в практических приложениях (см., например: [11; 22]) и описать весь класс
эволюционных алгоритмов, включающий в себя также алгоритмы
дифференциальной эволюции [67], имитации отжига [17] и др. Интересующийся читатель может найти информацию по этим темам
в указанных источниках.
8

1. Классический генетический
алгоритм
Рассмотрим задачу безусловной оптимизации в общем виде:
max{𝑓(𝑥) : 𝑥∈𝑋},
(1.1)
где 𝑋– пространство решений (мощности континуума, счетное или
конечное).
Генетический алгоритм представляет собой эвристический алгоритм оптимизации, в основу которого положены биологические
принципы естественного отбора и изменчивости. Процесс работы алгоритма представляет собой последовательную смену поколений, состоящих из фиксированного числа особей-точек пространства решений, причем особи с б´
ольшим значением целевой функции (более
приспособленные) получают больше потомков в каждом следующем
поколении. Кроме того, при формировании следующего поколения
часть потомков полностью идентична родителям, а часть изменяется некоторым случайным образом в результате мутации и кроссинговера (скрещивания).
При использовании ГА для поиска в дискретном пространстве 𝑋
каждой строке из 𝑙символов некоторого алфавита 𝐴должен быть
сопоставлен элемент пространства 𝑋, т. е. определена функция
𝑥: 𝐵→𝑋(называемая также схемой представления), где 𝐵= 𝐴𝑙.
Строку 𝜉= (𝜉1, . . . , 𝜉𝑙) ∈𝐵принято называть генотипом, а ее образ
𝑥(𝜉) ∈𝑋– фенотипом.
В классическом генетическом алгоритме (КГА) используется двоичный алфавит 𝐴= {0, 1}. Вообще, по умолчанию будем предполагать, что алфавит 𝐴конечный.
9