МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ
БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ»
И.Л. Каширина
ЭВОЛЮЦИОННОЕ МОДЕЛИРОВАНИЕ
Учебное пособие для вузов
Издательско-полиграфический центр
Воронежского государственного университета
2011
1
Стр.1
Содержание
1. Основные идеи и механизмы эволюционного моделирования ....................................... 4
1.1. Эволюционные методы ........................................................................................... 5
1.2. Достоинства и недостатки эволюционных вычислений.................................... 6
1.3. Парадигмы эволюционного моделирования ........................................................ 6
2. Основные понятия и базовая схема генетического алгоритма ........................................ 7
2.1. Кодирование решений ............................................................................................... 8
2.2. Общая схема генетического алгоритма ................................................................... 9
2.2.1. Формирование начальной популяции ......................................................... 9
2.2.2. Оценка особей популяции ............................................................................ 9
2.2.3. Отбор (селекция) ......................................................................................... 10
2.2.4. Скрещивание ................................................................................................ 11
2.2.5. Мутация ........................................................................................................ 11
2.2.6. Формирование новой популяции ............................................................... 13
2.2.7. Останов алгоритма ...................................................................................... 13
3. Модели ГА ............................................................................................................................ 14
3.1. Canonical GA (J.Holland) ....................................................................................... 14
3.2. Genitor (D. Whitley) ............................................................................................... 15
3.3. Hybrid algorithm (L. «Dave» Davis) ...................................................................... 15
3.4. Island Model GA ..................................................................................................... 16
3.5. CHC (Eshelman) ..................................................................................................... 16
4. Теорема схем (шим, шаблонов) .......................................................................................... 17
5. Решение задачи коммивояжера с помощью генетических алгоритмов ......................... 19
5.1. Соседское представление ..................................................................................... 20
5.2. Порядковое представление ................................................................................... 22
5.3. Путевое представление ......................................................................................... 23
5.4. Матричное представление .................................................................................... 29
6. Непрерывные генетические алгоритмы ............................................................................. 31
7. Генетические алгоритмы решения многокритериальных задач ...................................... 35
7.1. Методы решения задач многокритериальной оптимизации ............................. 36
7.2. Преимущества и недостатки представленных методов ..................................... 37
7.3. Гибридный алгоритм ............................................................................................. 38
8. Генетическое программирование ....................................................................................... 38
8.1. Особенности операторов ГП ................................................................................ 40
8.2. Пример синтеза программы ................................................................................. 42
8.3. Применение ГП ..................................................................................................... 43
9. Эволюционные стратегии и эволюционное программирование ..................................... 43
9.1. Эволюционные стратегии .................................................................................... 43
9.2. Эволюционное программирование ..................................................................... 45
Приложения .............................................................................................................................. 46
1. Математическая модель и генетический алгоритм для решения задачи
составления школьного расписания ........................................................................... 46
2. Генетический алгоритм решения многокритериальной задачи
о назначениях ................................................................................................................ 49
Литература ................................................................................................................................ 58
3
Стр.3
стики того или иного решения могут быть случайно изменены, что приведет
к новому направлению в процессе эволюции решений и может ускорить
процесс выработки лучшего решения.
1.2. Достоинства и недостатки эволюционных вычислений
Преимущества и недостатки эволюционных вычислений можно
вкратце сформулировать следующим образом.
Достоинства эволюционных вычислений:
• широкая область применения;
• возможность проблемно-ориентированного кодирования решений,
подбора начальной популяции, комбинирования эволюционных вычислений
с неэволюционными алгоритмами, продолжения процесса эволюции до
тех пор, пока имеются необходимые ресурсы;
• пригодность для поиска решений в сложном пространстве большой
размерности;
• отсутствие ограничений на вид целевой функции;
• ясность схемы и базовых принципов эволюционных вычислений;
• интегрируемость эволюционных вычислений с другими неклассическими
парадигмами искусственного интеллекта, такими как искусственные
нейросети и нечеткая логика.
Недостатки эволюционных вычислений:
• эвристический характер эволюционных вычислений не гарантирует
оптимальности полученного решения (правда, на практике зачастую важно
в течение заданного времени получить одно или несколько субоптимальных
альтернативных решений, тем более что исходные данные в задаче могут
динамически меняться, быть неточными или неполными);
• относительно высокая вычислительная трудоемкость, которая, однако,
преодолевается за счет распараллеливания на уровне организации эволюционных
вычислений и на уровне их непосредственной реализации в вычислительной
системе;
• относительно невысокая эффективность на заключительных фазах
моделирования эволюции (операторы поиска в эволюционных алгоритмах
не ориентированы на быстрое попадание в локальный оптимум);
• нерешенность вопросов самоадаптации.
1.3. Парадигмы эволюционного моделирования
История эволюционных вычислений началась с разработки ряда различных
независимых моделей эволюционного процесса. Среди этих моделей
можно выделить несколько основных парадигм:
• генетические алгоритмы;
6
Стр.6
• генетическое программирование;
• эволюционные стратегии;
• эволюционное программирование.
2. ОСНОВНЫЕ ПОНЯТИЯ И БАЗОВАЯ СХЕМА
ГЕНЕТИЧЕСКОГО АЛГОРИТМА
Важнейшим частным случаем эволюционных методов являются генетические
методы, основанные на поиске лучших решений с помощью наследования
и усиления полезных свойств множества объектов определенного
приложения в процессе имитации их эволюции.
Генетические алгоритмы (ГА) – это стохастические, эвристические
оптимизационные методы, впервые предложенные Холландом (1975). Идея
генетических алгоритмов заимствована у живой природы и состоит в организации
эволюционного процесса, конечной целью которого является получение
решения в сложной задаче оптимизации. Разработчик генетических
алгоритмов выступает в данном случае как «создатель», который должен
правильно установить законы эволюции, чтобы достичь желаемой цели как
можно быстрее. Впервые эти нестандартные идеи были применены к решению
оптимизационных задач в середине 70-х гг. Примерно через десять лет
появились первые теоретические обоснования этого подхода. В настоящее
время генетические алгоритмы доказали свою конкурентоспособность при
решении многих трудных задач, и особенно в практических приложениях,
где математические модели имеют сложную структуру и применение стандартных
методов (типа ветвей и границ) динамического или линейного программирования
крайне затруднено.
Цель в оптимизации с помощью ГА состоит в том, чтобы найти лучшее
возможное решение или решения задачи по одному или нескольким
критериям. Чтобы реализовать генетический алгоритм, нужно сначала выбрать
подходящую структуру для представления этих решений. В постановке
задачи поиска объект этой структуры данных представляет точку в
пространстве поиска всех возможных решений. Свойства объектов представлены
значениями параметров, объединяемыми в запись, называемую в
эволюционных методах хромосомой. В генетических методах оперируют
хромосомами, относящимися к множеству объектов – популяции. Имитация
генетических принципов: вероятностный выбор родителей среди членов
популяции, скрещивание их хромосом, отбор потомков для включения
в новые поколения объектов на основе оценки целевой функции – все это
ведет к эволюционному улучшению значений целевой функции (функции
приспособленности) от поколения к поколению.
7
Стр.7
Чаще всего хромосома – это битовая строка. Однако ГА не ограничены
бинарным представлением данных. Некоторые реализации используют
целочисленное или вещественное кодирование. Несмотря на то, что для
многих реальных задач, видимо, больше подходят строки переменной длины,
в настоящее время структуры фиксированной длины наиболее распространены
и изучены. Вначале и мы ограничимся только структурами, которые
являются одиночными строками по n бит.
Каждая хромосома (строка) представляет собой конкатенацию ряда
подкомпонентов, называемых генами. Гены располагаются в различных позициях,
или локусах, хромосомы и принимают значения, называемые аллелями.
В представлениях с бинарными строками ген – бит, локус – его позиция
в строке и аллель – его значение (0 или 1). Биологический термин
«генотип» относится к полной генетической модели особи и соответствует
структуре в ГА. Термин «фенотип» относится к внешним наблюдаемым
признакам и соответствует вектору в пространстве параметров. Чрезвычайно
простой, но иллюстративный пример – задача максимизации следующей
функции двух переменных:
f (x1, x2) = x1x2, где 0 ≤ x1 ≤ 1 и 0 ≤ x2 ≤ 1.
Обычно методика кодирования реальных переменных x1 и x2 состоит в
их преобразовании в двоичные целочисленные строки достаточной длины –
достаточной для того, чтобы обеспечить желаемую точность. Предположим,
что 10-разрядное кодирование достаточно и для x1, и для x2. Установить соответствие
между генотипом и фенотипом закодированных особей можно,
разделив соответствующее двоичному представлению целое число на значение
210 – 1. Например, код [0000000000] соответствует вещественному значению
0/1023 или 0, тогда как код [1111111111] соответствует 1023/1023 или 1.
Оптимизируемая структура данных – 20-битная строка, представляющая
конкатенацию кодировок x1 и x2. Переменная x1 размещается в крайних левых
10-разрядах, тогда как x2 размещается в правой части генотипа особи
(20-битовой строке). Генотип – точка в 20-мерном бинарном пространстве,
исследуемом ГА. Фенотип – точка в двумерном пространстве параметров.
2.1. Кодирование решений
После того как выбраны параметры, их число и разрядность, необходимо
решить, как непосредственно записывать данные. Можно использовать
обычное кодирование, когда, например, 10112 = 1110, либо коды Грея,
когда 1011G = 11102 = 1410. Несмотря на то, что коды Грея влекут неизбежное
кодирование/декодирование данных, они позволяют избежать некоторых
проблем, которые появляются в результате обычного кодирования.
Можно лишь сказать, что преимущество кодов Грея в том, что если два
числа являются последовательными при кодировании, то и их двоичные ко8
Стр.8