Генетические алгоритмы

Гладков Л.А.
Курейчик В.В.
Курейчик В.М.

Генетические

алгоритм ы

МОСКВА

ФИЗМАТЛИТ ®

УДК 621.3+681.3
ББК 74.263.2
Г 52

Гл а д к о в Л. А., Ку р е й ч и к В. В., Ку р е й ч и к В. М. Генетические
алгоритмы / Под ред. В. М. Курейчика. — 2-е изд., исправл. и доп. —
М.: ФИЗМАТЛИТ, 2010. — 368 с. — ISBN 978-5-9221-0510-1.

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

Допущено УМО вузов по университетскому политехническому образованию в качестве учебника для студентов вузов, обучающихся по направлению
210100 «Информатика и вычислительная техника», специальности 230104 «Системы автоматизированного проектирования».

ISBN 978-5-9221-0510-1

c⃝ ФИЗМАТЛИТ, 2006, 2010

c⃝ Л. А. Гладков, В. В. Курейчик,
В. М. Курейчик, 2006, 2010

СОДЕРЖАНИЕ

Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
5

1. Генетика и основы эволюции . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
9
1.1. Краткие исторические сведения . . . . . . . . . . .. . . . . . . . . . .. .. .. .
9
1.2. Кроссинговер . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
12
1.3. Мутация. . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . .. .. .. .
14
1.4. Селекция . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
18
1.5. Особенности механизма эволюционной адаптации. . . .. . . . . .. .. .. .
20
1.6. Выводы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
34
1.7. Контрольные вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
35
1.8. Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
37
Глоссарий к разделу 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
38
Список литературы к разделу 1 . . . . . . . . . . . . . .. . . . . . . . . .. .. .. .
40

2. Методы оптимизации . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
42
2.1. Постановка оптимизационных задач . . . . . . . . . . . . . . . . . .. .. .. .
42
2.2. Технологии локального поиска . . . . . . . . . . . . . . . . . . . . . .. .. .. .
49
2.3. Выводы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
64
2.4. Контрольные вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
65
2.5. Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
66
Глоссарий к разделу 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
70
Список литературы к разделу 2 . . . . . . . . . . . . . .. . . . . . . . . .. .. .. .
73

3. Основные понятия и структура генетических алгоритмов. . .. .. .. .
74
3.1. Определения и понятия генетических алгоритмов . . . .. . . . . .. .. .. .
74
3.2. Генетические операторы . . . . . . . . . . . . . .. . . . . . . . . . . . .. .. .. .
79
3.3. Теоретико-множественные операции над популяциями и хромосомами . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
95
3.4. Простой генетический алгоритм . . . . . . . . . . .. . . . . . . . . . .. .. .. .
104
3.5. Основные гипотезы генетических алгоритмов . . . . . . . . . . . .. .. .. .
111
3.6. Введение в аксиоматическую теорию генетических алгоритмов . .. .
120
3.7. Выводы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
126
3.8. Контрольные вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
126
3.9. Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
128

Содержание

Глоссарий к разделу 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
131
Список литературы к разделу 3 . . . . . . . . . . . . . .. . . . . . . . . .. .. .. .
135

4. Совместные схемы локального и генетического поиска . . . .. .. .. .
137
4.1. Модифицированные генетические операторы . . . . . .. . . . . . .. .. .. .
137
4.2. Архитектуры и стратегии генетического поиска . . . . . . . . . .. .. .. .
149
4.3. Генетическое программирование. . . . . . . . . . . . . . . . . . . . .. .. .. .
170
4.4. Новые структуры генетических операторов. . . . . . . . . . . . . .. .. .. .
175
4.5. Параллельные генетические алгоритмы . . . . . . . .. . . . . . . . .. .. .. .
188
4.6. Выводы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
192
4.7. Контрольные вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
193
4.8. Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
195
Глоссарий к разделу 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
197
Список литературы к разделу 4 . . . . . . . . . . . . . .. . . . . . . . . .. .. .. .
199

5. Оптимизационные задачи на графах. . . . . . . . . . . . . . . . . .. .. .. .
200
5.1. Генетические алгоритмы разбиения графов. . . . . . . . . . . . . .. .. .. .
200
5.2. Решения задачи о коммивояжере . . . . . . . . . . . . . . . . . . . .. .. .. .
221
5.3. Задачи раскраски, построения клик и независимых множеств графов . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . .. .. .. .
230
5.4. Определение планарности графов на основе генетического поиска
242
5.5. Определение изоморфизма графов. . . . . . . . . . . . . . . . . . . .. .. .. .
268
5.6. Генетический алгоритм определения паросочетаний графа . . .. .. .. .
276
5.7. Квантовый алгоритм построения Гамильтонова цикла . . . . . .. .. .. .
279
5.8. Нечеткие генетические алгоритмы решения задач оптимизации
и проектирования. . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . .. .. .. .
281
5.9. Выводы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
298
5.10. Контрольные вопросы . . . . . . . . . . . . . . .. . . . . . . . . . . . . .. .. .. .
298
5.11. Упражнения . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . .. .. .. .
299
Глоссарий к разделу 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
300
Список литературы к разделу 5 . . . . . . . . . . . . . .. . . . . . . . . .. .. .. .
301
Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
303

Приложения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
305
Приложение 1. Элементарные сведения из теории алгоритмов . . .. .. .. .
305
Приложение 2. Примеры реализации основных генетических операторов . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . .. .. .. .
319
Приложение 3. Задания к лабораторным работам . . . . . . .. . . . .. .. .. .
338
Приложение 4. Методические указания к выполнению курсовой работы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. .
351
Приложение 5. Примеры тестовых заданий по курсу . . . . . .. . . .. .. .. .
356

Введение

На базе фактов и законов (аксиом)
с помощью логического вывода создаются научные теории. Однако особую
роль играют аналогичные механизмы
научного поиска, объединенные термином «интуиция».
А. Сухотин

Большинство задач науки и техники относятся к обширному классу
проблем поиска оптимальных решений, т. е. к оптимизационным задачам.
Часть задач оптимизации относится к классу комбинаторных и
они, в большинстве случаев, имеют не одно, а множество решений
различного качества. Существует множество алгоритмов для решения
таких задач. Ядром всех комбинаторных алгоритмов являются операции полного или сокращенного перебора подмножеств решений. Стратегия комбинаторного перебора в различных алгоритмах реализуется
по-разному. Для поиска лучшего решения, как правило, осуществляются направленный, случайный и комбинированный переборы всевозможных значений параметров задачи. В этой связи разрабатывается
большое число точных, переборных и эвристических методов решения
этих задач. До последнего времени не существовало эффективного
механизма поиска решений на множестве альтернатив, что затрудняло
получение качественных результатов за приемлемое время.
В конце 1960-х годов американский исследователь Джон Холланд
в качестве принципов комбинаторного перебора вариантов решения
оптимизационных задач предложил использовать методы и модели
механизма развития органического мира на Земле. Поскольку основные
законы эволюции живых организмов были исследованы генетикой, то и
предложенный механизм получил название «генетические алгоритмы»
(ГА). Первый ввел в обиход термин «генетический алгоритм» Д. Багли
(США) в своей диссертации в 1967 г.
В мире сейчас успешно развиваются три основные научные школы
по генетическим алгоритмам. К ним относятся американская, европейская и российская школы. В американской школе отметим таких

Введение

ученых, как Д. Холланд, Д. Гольдберг, Д. Коза, Л. Чамберс и др. В европейскую школу входят такие ученые, как Р. Клинг, П. Банерджи,
Э. Фалькенауер и др. В российской отметим И. Букатову, Д. Батищева,
И. Норенкова, авторов книги и многих др. Интерес к этой области
исследований в мире с каждым годом возрастает. Для дальнейшего
успешного развития этого направления в России необходимы учебники
и монографии различных школ. Хочется надеяться, что этот пробел
в ближайшее время будет восполнен.
Предлагаемое учебное пособие частично восполняет этот пробел.
Учебное пособие предназначено для студентов, обучающихся по всем
специальностям направлений «Информатика и вычислительная техника» и «Информационные системы», а также может быть полезно
студентам других специальностей, желающим углубить свои знания
в области методов оптимизации. Кроме того, пособие может быть
полезно специалистам и инженерам соответствующих специальностей,
оно может быть использовано при повышении квалификации и переподготовке специалистов по информационным технологиям.
Учебное пособие помимо оригинальных научных исследований авторов включает хорошо методически проработанные исследования
Д. Холланда, Д. Голдберга, Дэвиса, Л. Чамберса (США), а также других российских и зарубежных ученых. Материалы каждого раздела
пособия подготовлены на основе анализа существуюшей литературы,
список которой приведен в конце каждого раздела. В учебном пособии
содержатся материалы курсов лекций «Методы генетического поиска»,
«Эволюционное моделирование» и «Генетические алгоритмы», которые
авторы читают в Таганрогском государственном радиотехническом университете. Частично материалы учебного пособия были апробированы
при чтении лекций профессором В. М. Курейчиком в Мичиганском
государственном университете (США) в 1992, 1993, 1994 годах.
Учебное пособие включает материал, который, в отличие от документаций на программные системы, содержит концепции, принципы,
стратегии и методы генетического поиска, а также процедуры использования средств программных систем для решения конкретных задач
проектирования на основе генетических алгоритмов.
Учебное пособие состоит из одной книги. Центральной частью
пособия являются разделы 2–5, где приведены фундаментальные математические основы генетических алгоритмов, описаны процедуры генетического поиска, в которых шаг за шагом комментируется решение
практических задач проектирования с момента постановки задачи до
описания алгоритма и выполнения процедур работы.
Учебное пособие включает следующие разделы:
— генетика и основы эволюции (раздел 1);
— методы оптимизации (раздел 2);
— основные понятия и структура генетических алгоритмов (раздел 3);
— совместные схемы локального и генетического поиска (раздел 4);
— оптимизационные задачи на графах (раздел 5).

Введение
7

Комплексная цель и задачи изучения учебника

Цель учебника:

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

В результате освоения учебника студент должен быть готов продемонстрировать следующие компетенции и уровень подготовки:

1) знание основных естественнонаучных понятий, определений и терминов, заимствованных из биологии, генетики, теории эволюции
и используемых в теории эволюционного моделирования, а также
в процессе создания и практического использования генетических
алгоритмов;
2) умение идентифицировать основные формы и механизмы генетической изменчивости, действующие в естественных организмах
и системах;
3) навыки по составлению и модификации математических моделей,
позволяющих симулировать эволюционные процессы, протекающие в естественных популяциях и биологических системах;
4) возможности использования методов формализации параметров
и построения математической модели решаемой задачи;
5) знание основных определений и понятий теории генетических алгоритмов, базовой структуры генетических алгоритмов;

Введение

6) навыки по составлению математических моделей решаемых задач
и подбору необходимых генетических операторов, выбору необходимой архитектуры и структуры генетического поиска;
7) возможности использования основных гипотез генетических алгоритмов для оценки вероятности «выживания» лучших решений
в процессе генетического поиска;
8) знание основных методов и схем локального поиска;
9) умение в зависимости от специфики решаемой задачи строить
новые или использовать существующие модификации основных
генетических операторов;
10) навыки по модификации и составлению новых архитектур, стратегий и схем совместных локального и генетического поисков для
решения практических задач оптимизации;
11) возможности использования различных моделей эволюции и уровней иерархии для повышения эффективности генетического поиска.
Самостоятельная работа с учебником предусматривает проработку
лекций, подготовку к выполнению и сдаче лабораторных работ, тестирование, а также изучение литературы, формулировку цели работы,
объекта и задач исследования, методов, источников и средств библиографического поиска, использованных для достижения поставленной
цели.
Авторы благодарны членам научно-педагогической школы «Интеллектуальные САПР» Таганрогского государственного радиотехнического университета за обсуждение результатов работы. Выражаем искреннюю благодарность сотрудникам, аспирантам и студентам кафедры
САПР за помощь в апробации алгоритмов и программ, ректору Таганрогского государственного радиотехнического университета Захаревичу В. Г. за поддержку исследований. Особо отметим работу рецензентов — профессоров Попова Э. В., Емельянова В. В., Еремеева А. П., чьи
пожелания и замечания способствовали улучшению качества пособия.
Мы понимаем, что пособие не свободно от недостатков. Все замечания и предложения будут с благодарностью приняты.

Авторы

1. ГЕНЕТИКА И ОСНОВЫ ЭВОЛЮЦИИ

Все в биологии имеет смысл лишь
в свете эволюционного учения.
Ф. Добжанский

Я понимаю под эволюцией все изменения (большие и малые), видимые
и невидимые, адаптивные и неадаптивные.
М. Кимура

1.1. Краткие исторические сведения

1. Основоположником генетики является Иоганн Грегор Мендель,
который в середине XIX в. открыл общий закон природы и вывел
формулы расщепления признаков в гибридном потомстве. Известны три
знаменитых закона И. Менделя:
1) закон однородности и реципрокности (взаимность, эквивалентность). Первое гибридное поколение оказывается полностью однородным;
2) закон расщепления. При скрещивании гибридов первого поколения в потомстве происходит расщепление признаков по фенотипу 3:1,
а по генотипу в отношении 1:2:1 1);
3) закон независимой комбинации. Закон справедлив для потомков родителей, отличающихся более чем одной парой признаков, и говорит о том, что признаки наследуются независимо друг от друга.
И. Мендель пришел к выводу, что наследственность прерывиста
(дискретна), что наследуется не большая совокупность свойств, а отдельные признаки. Он предположил, что в половых клетках есть
какие-то материальные структуры (позже их назвали генами), ответственные за формирование признаков. Одна из основных заслуг
И. Менделя — его гипотеза о материальных задатках, которые в двойном комплекте находятся в клетках и которые зародыш получает от
обоих родителей. Такие задатки (хромосомы) играют важную роль
в явлениях наследственности. Они представляют собой нитевидные

1) Фенотип и генотип — см. глоссарий.

1. Генетика и основы эволюции

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

2. В клетках существует сложный и важный механизм перераспределения хромосом. Каждая клетка организма имеет одинаковое число
хромосом. У потомков содержится то же самое число хромосом, причем
ровно половина от отца, а половина — от матери. Хромосомы передают наследственные признаки. Ч. Вильсон в 1900 г. определил, что
хромосомы состоят из генов. Модель хромосомы в настоящее время —
это нить, на которую, словно бусины, нанизаны гены. Определяют
гомологичные и негомологичные хромосомы.
Гомологичными хромосомами называются пары одинаковых хромосом, несущие гены одинаковых признаков. Две гомологичные хромосомы (одна от отца, а другая от матери) сближаются при созревании половых клеток и обмениваются частями. Это явление назвали crossover
(кроссинговер). Он происходит случайным образом между разными
генами с разной частотой.

3. В 1809 г. Ж. Б. Ламарк определил эволюцию как возникновение новых форм путем постепенного изменения старых. При этом
происходит усложнение форм. Он считал, что организмы изменяются
под прямым воздействием окружающей среды, что причиной эволюции
являются «упражнения» органов и внутреннее стремление к прогрессу.

4. Ч. Дарвин определил в живой природе существование общего
принципа — естественного отбора. Он различал две стороны эволюционного учения: учение о материале для эволюции и факторах.
Движущая сила эволюции — естественный отбор.

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