Бураков М.В

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

Государственное образовательное учреждение

Высшего профессионального образования

«Санкт-Петербургский государственный университет
аэрокосмического приборостроения»

________________________________________________________________

М. В. Бураков

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

теория и практика

Учебное пособие

Санкт-Петербург

УДК 681.3

ББК

Д79

Рецензенты:

Кафедра автоматики и процессов управления Санкт-Петербургского государственного электротехнического университета «ЛЭТИ»,

д-р техн. наук профессор Душин С.Е.

Кафедра «Интегрированные системы управления» Санкт-Петербургского государственного Политехнического университета,

канд. ф.-м. наук, с.н.с. Курбанов В.Г.

Бураков М.В.

Д79 Генетический алгоритм: теория и практика. Учеб. пособие / М.В. Бураков; ГУАП. – СПб., 2007.

ISBN

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

Приводится описание генетического алгоритма и его основных модификаций, рассмотрены принципы использования генетического алгоритма для решения конкретных задач. Описываются возможности пакета математического моделирования MatLab для организации генетических вычислений.

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

УДК 681.3

ББК

ISBN © ГУАП, 2008

© М.В. Бураков, 2008

СОДЕРЖАНИЕ

Введение
ГЛАВА 1. Основы генетического алгоритма
§ 1.1. Глобальная оптимизация
1.1.1. Задачи локальной и глобальной оптимизации
1.1.2. Классификация методов глобальной оптимизации
1.1.3. Алгоритм имитации отжига
1.1.4. Генетический алгоритм и другие методы оптимизации
§ 1.2. Общие сведения о генетическом алгоритме
1.2.1. Основные представления об эволюции
1.2.3. Классический генетический алгоритм
1.2.4. Пример работы классического генетического алгоритма
Вопросы для самопроверки к главе 1
ГЛАВА 2. Механизмы работы генетического алгоритма
§ 2.1. Строительные блоки в генетическом алгоритме
§ 2.2. Кодирование параметров в ГА
§ 2.3. Варианты оценки пригодности хромосом
§ 2.4 Операция селекции
2.4.1. Варианты стохастического отбора
2.4.2 Турнирная селекция
2.4.3 Селекция отсечением
2.4.4 Селекция генов
§ 2.5. Варианты операции скрещивания
2.5.1. Бинарный кроссовер
2.5.2. Всеобщий кроссовер (uniform crossover)
§ 2.6. Операция мутации
§ 2.7. Миграционная модель генетического алгоритма
Вопросы для самопроверки к главе 2
ГЛАВА 3. приложения генетического алгоритма
§ 3.1. Генетический синтез регуляторов
3.1.1. Общие принципы синтеза регуляторов
3.1.2. Синтез ПИД-регуляторов
3.1.3. Синтез нечетких регуляторов
3.1.4. Нейроконтроллеры
§ 3.2. Мультиагентные системы
3.2.1. Понятие интеллектуального агента
3.2.2. Обучение интеллектуального агента
§ 3.3. Генетическое программирование
3.3.1 Автоматическое составление программ
3.3.2. Механизмы языка ЛИСП
3.3.3. ЛИСП и генетическое программирование
§ 3.4. Генетическое тестирование программного обеспечения
3.4.1. Проблемы тестирования программ
3.4.2. Принципы тестирования программ
3.4.3. Количественная оценка надежности программы
3.4.4. Генетическое тестирование программ
Вопросы для самопроверки к главе 3
ГЛАВА 4. Генетический алгоритм в MatLab
§4.1. Общие сведения
§4.2. Использование графического окна GATOOL
4.2.1. Общий вид графического окна
4.2.2. Описание задачи и ограничений
4.2.3. Визуализация результатов работы алгоритма
4.2.4. Параметры запуска генетического алгоритма
4.2.5. Панель Options
§4.3. Запуск из командной строки и M-файлов
Вопросы для самопроверки к главе 4
ГЛАВА 5. Примеры решения задач
§5.1. Минимизация функций
§5.2. Решение диофантова уравнения
§5.3. Настройка ПИД-регулятора
§5.4. Настройка нечеткого регулятора
5.4.1. Настройка масштабирующих коэффициентов
5.4.2. Настройка регулятора Сугэно
§ 5.5. Настройка нейронной сети
§5.6. Задачи для самостоятельной работы
5.6.1. Поиск экстремума функции одной переменной
5.6.2. Поиск экстремума функции двух переменных
5.6.3. Решение задачи линейного программирования
5.6.4. Решение задачи нелинейного программирования
5.6.5. Генетический синтез параметров регулятора
Заключение
Библиографический список

Введение

Генетический алгоритм (ГА) является мощным инструментом для эволюционного решения сложных задач.

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

Считается, что стандартный ГА впервые описан в работе [1]. Всеобщий интерес к ГА вызвала работа [2], в которой была сделана попытка его математического обоснования.

В последующие годы развитию ГА было посвящено множество зарубежных публикаций, в том числе – ряд обобщающих работ [3 - 6].

В Советском Союзе также происходило развитие идей эволюционного поиска решений сложных задач. Так в 70-х годах в рамках теории случайного поиска Л.А. Растригиным был предложен ряд алгоритмов, использующих идей бионического поведения особей [7]. Развитие этих идей нашло отражение в ряде работ И.Л. Букатовой по эволюционному моделированию [8, 9]. Ю.И. Неймарк предложил осуществлять поиск глобального экстремума на основе коллектива независимых автоматов [10].

В России в последние годы были изданы несколько учебников и монографий, посвященных ГА [11 - 14]. Продолжает расти поток научных публикаций, посвященных теоретическим и прикладным аспектам использования ГА ([15 - 18] и другие).

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

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

- аппроксимация функций и регрессионный анализ;

- поиск кратчайших путей (задачи коммивояжера);

- комбинаторная оптимизация;

- параметрический дизайн;

- задачи размещения и составления расписаний;

- задачи автоматического программирования и тестирования программ;

- техническое проектирование.

В системах управления ГА используется для следующих задач:

- выбор структуры и параметров искусственных нейронных сетей;

- оптимизация параметров регуляторов (в том числе – нейронных и нечетких);

- проектирование мультиагентных систем и клеточных автоматов;

- оптимизация траекторий робота, обучение робота ходьбе.

Последняя задача является одним из наиболее наглядных приложений ГА. В Японии был разработан робот Pino (сокращение от Pinokkio), отличающийся относительно невысокой стоимостью при простоте конструкции (рис.1.1). Pino уже поступил в массовую продажу (в том числе – в России), он может «разговаривать», «петь», двигать руками и ногами, ходить, танцевать, выражать свое настроение.

До появления Pino на рынке были сложные и дорогие высокотехнологичные роботы. Эти роботы использовали мощные моторы для управления «ходьбой». Алгоритм управления строился на основании анализа походки человека и движения его суставов.

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

Рис. 1.1. Шагающий робот Pino

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

Учёным из Технического университета в Гётеборге (Швеция), удалось построить робота, который самостоятельно, методом проб и ошибок, научился летать.

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

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

Расчет орбит спутников для эффективной связи также оказался приложением, в котором ГА показал хорошие результаты. Эта проблема заключается в том, что летающие на самой большой (более 35 тыс. км) высоте спутники способны "видеть" половину земного шара, однако, стоимость их вывода на такие орбиты очень высока. Более дешевые орбиты от 130 до 480 км неудобны для спутников вследствие кривизны земной поверхности, которая препятствует связи со станциями в ходе большей части 90-минутного витка вокруг планеты. ГА выбрал наиболее производительные группировки спутников путем изменения таких параметров, как удаление одного аппарата от другого и высота полета над поверхностью планеты. Низкоорбитальные спутники незаменимы для пользователей мобильных компьютеров, поскольку дают возможность использовать устройства беспроводной связи.

Генетическое программирование, т. е. автоматическое составление программ с помощью ГА становится все более реальным по мере увеличения мощности компьютеров.

В Стэнфордском университете генетическое программирование (одно из направлений ГА) нашло применение для оценки дублирования и заимствований на существующем множестве патентов США. Эта система работает на базе сети из 1000 компьютеров. Разработчики системы надеются, что на ее базе можно будет создать «машину изобретений», способную к самостоятельному творчеству.

Деятельность инженера-проектировщика часто связана с проблемой выбора нужного технического решения в условиях огромного количества альтернатив.

Например, при разработке новых реактивных двигателей возникает задача конструирование газовой турбины. Турбина имеет более 100 параметров, на которые наложены несколько десятков условий, так что существует около 10 в 380-й степени различных вариантов решения. По сообщениям прессы, в одном довольно типичном случае инженеру понадобилось 8 недель вычислений на рабочей станции, чтобы достичь удовлетворительного варианта конструкции. Дальнейшее применение традиционного метода оптимизации позволило за сутки повысить эффективность конструкции турбины в 2 раза. Однако это оказался локальный максимум оценочной функции, из которого не удавалось выйти. Использование ГА позволило за двое суток обнаружить другой максимум, на 50% выше найденного традиционными средствами оптимизации.

Можно сказать, что уже ГА прочно вошел в арсенал методов решения сложных задач. Об этом свидетельствует появление библиотек ГА (Genetic Algorithm and Direct Search Toolbox) в последних версиях популярного математического пакета MatLab [19]. В сочетании с уже имевшимися в MatLab пакетами Fuzzy Logic Toolbox и Neural Network Toolbox, это дает инструменты для решения многих «интеллектуальных» задач.

Таким образом, изучение ГА является необходимым компонентом в подготовке инженеров-разработчиков систем управления.

Настоящее учебное пособие состоит из четырех разделов:

- Первая глава посвящена описанию основ ГА, его места в арсенале методов оптимизации и связи ГА с представлениями о биологической эволюции.

- Во второй главе рассмотрены механизмы работы ГА, особенности и варианты описания генетических операций.

- В третьей главе рассматриваются принципы использования ГА для решения ряда прикладных задач, в том числе – настройки регуляторов, обучения интеллектуальных агентов, генетического программирования и тестирования программ;

- Четвертая глава содержит описание возможностей пакета расширения Genetic Algorithm and Direct Search Toolbox (GADS), приводится описание графического интерфейса GAtool, а также примеров запуска ГА из командной строки и из М-файлов MatLab.

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

ГЛАВА 1

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

§1.1. Глобальная оптимизация