Разработка инструментальных средств для исследования и конструирования генетических алгоритмов

• Автор: Минаков, Игорь Александрович
• Шифр специальности: 05.13.16
• Научная степень: Кандидатская
• Год защиты: 2000
• Место защиты: Самара
• Количество страниц: 181 с. : ил.

ВВЕДЕНИЕ

ГЛАВА 1 МЕТОДЫ 1ЮИСКА И ОПТИМИЗАЦИИ

1.1. Проблема поисковой оптимизации. Общая постановка задачи

1.2. Класс проблем, к которым неприменимы обычные детерминистические методы

1.3. Эвристические методы поиска и оптимизации

1.3.1. Методы случайного поиска

1.3.2. Моделируемый отжиг

1.3.3. Поиск с запретами

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

1.3.5. Подход с использованием нечеткой логики

1.3.6. Нейронные сети

1.3.7. Эволюционное программирование
1.3.8. Остальные эвристические методы поиска и оптимизации
1.4. Сопоставление эвристических методов поиска на примере некоторых задач.
роблсма оптимального подбора параметров
1.5 Особенности и отличия генетических алгоритмов
Основные выводы к главе 1
ГЛАВА 2 Г ЕНЕТИЧЕСКИЕ АЛГОРИТМЫ
2.1 Г енетические алгоритмы в задачах поиска и оптимизации
2.1.1. Общая структура
2.1.2 . Основные операторы. Схема представления. Функция пригодности. Механизмы воспроизведения
2.1.3. Гипотез 1 о целесообразности применения генетических алгоритмов. Теорема схем. Гипотеза строящихся блоков. Поиск и исследование
2.1.4 Области применения генетических алгоритмов
2.1.5 О выборе оптимального набора параметров для генетического алгоритма
2.2 Оператор выбора. Различные схемы выбора
2.2.1. Описание параметров, характеризующих схемы выбора
2.2.2. Селекция на основе турнира
2.2.3 Селекция с усечением
2.2.4 Селе кция с линейным ранжированием
2.2.5 Селекция с экспоненциальным ранжированием
2.2.6 Пропорциональная селекция
2.2.7 Сравнение различных методов селекции. Коэффициенты воспроизведения. Интенсивности селекции. Коэффициенты потери многообразия. Отклонения методов селекции
2.3. О связи генотипа с фенотипом
2.4. Возможности взаимодействия объектноориентированного моделирования
и подхода, основанного на использовании генетических алгоритмов.
2.5. Модификации генетических алгоритмов. Разделение. Уплотнение.
Элитизм. Генетические алгоритмы с устойчивым состоянием.
Параллельные ГА. Предварительные выводы о пользе и применимости различных вариаций ГА.
2.6. Классификация генетических алгоритмов по применимости к исследованию сложных систем
Основные выводы и результаты к главе 2
ГЛАВА 3. ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ ПО
ОПРЕДЕЛЕНИЮ ЭФФЕКТИВНОЙ РЕАЛИЗАЦИИ ГА.
3.1. Критерии для выбора тестовых функций
3.2. Набор тестовых функций для эмпирического исследования
3.3. Виды генетических алгоритмов, использующиеся при исследовании.
Общие параметры. Инициализация популяции. Нормирование функции пригодности. Методы селекции. Методы скрещивания.
Методы замещения. Мутация. Условия останова.
3.4. Результаты, полученные при исследовании и их сравнительный анализ
3.4.1. Критерии эффективности работы ГА
3.4.2. Общее предварительное исследование работы ГА на примере функции ОЫЕМАХ
3.4.3. Исследование работы ГА на тестовых функциях. Методы замещения. Методы нормирования функции пригодности. Методы селекции.
Операторы кроссирования. Операторы мутации.
3.5. Некоторые общие наблюдения и рекомендации но применению ГА
Основные выводы и результаты к главе 3
ГЛАВА 4. ПРИМЕРЫ ПРАКТИЧЕСКИХ ЗАДАЧ, РЕШЕННЫХ НА ОСНОВЕ ТЕХНОЛОГИИ ГА
4.1. Применение ГА к моделям класса продавецпокупатель. Игровая
постановка проблем дисбаланса
4.1.1.роблема установления динамического равновесия.
4.1.2. Идея применения популяционных игр в задачах класса продавецпокупатель
4.1.3. Изменчивость популяций
4.1.4. Сравнение игрового подхода с классическим
4.1.5. Имитационная модель
4.1.6. Обсуждение результатов и возможные улучшения.
4.2. Задача о путешествующем коммивояжере
4.2.1. Общая постановка задачи и используемые методы
4.2.2. Два основных представление генетического кодирования ЗК
4.2.3. Представление решения как списка вершин.
4.2.4. Представление решения как списка ребер, образующих Гамильтонов цикл.
4.2.5. Предлагаемый подход
4.2.6. Обсуждение результатов и возможные усовершенствования.
4.3. Задача о планировании и составлении расписаний
4.3.1. Задача о составлении расписания как проблема оптимизации со
множеством ограничений
4.3.2. Общая постановка задачи
4.3.3. Применение ГА к задачам составления расписания в учебных заведениях
4.3.4. Параллельные ГА как естественное средство улучшения производи
тельности для подобных задач
4.3.5. Обсуждение результатов и возможные улучшения
Основные выводы и результаты к главе 4
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ


Каждый из них имеет свои преимущества и недостатки, и применение конкретного метода зависит от особенностей задачи, но общей их характеристикой является то, что последовательность действий алгоритма строго предопределяется сложившейся ситуацией. Однако в последнее время все чаще встречаются задачи, в которых точные математические методы слабо применимы или неприменимы вовсе. Это связано с целым рядом проблем, основными из которых являются проблема размерности особенно ярко она проявляется в ИРсложных задачах, к которым относится и задача о коммивояжере и проблема априорной неопределенности, связанная с тем фактом, что в реальных задачах знания о проблеме могут быть трудноформализуемыми или неформализуемыми в принципе, иногда их трудно представить в числовом виде, а в некоторых случаях получение их представляется в принципе невозможным. Вес эти проблемы относятся в первую очередь к тем моделям, в которых частью является человек или общество, т. Итак, существует целый ряд задач например, задача рекламирования конкурирующих товаров , задачи экономического прогнозирования , задачи моделирования политической ситуации , задачи размещения и многие другие для которых детерминистические методы решения неприемлемы или нс обеспечивают необходимой степени точности. Поэтому необходим альтернативный подход использование эвристических методов и намеренное введение элемента случайности и вероятностного механизма в алгоритм поиска. В этом случае случайность будет служить целям сбора информации о поведении объекта исследования и целям управления. Необходимо сразу подчеркнуть, что областью применения таких методов служат многопараметричсскис задачи, задачи с большим уровнем помех и возможностью сбоя, неустойчивые, с большой размерностью, с множеством локальных экстремумов или негладкостью функции качества, с априорной неопределенностью или недооиределенностыо, т. Это связано в первую очередь с тем, что в более простых и формализуемых задачах аналитические методы намного превосходят эвристические методы поиска. Далее в главе будут рассмотрены известные эвристические алгоритмы поиска, а также новые, появившиеся в последнее время, но уже успевшие завоевать признание, и дан некоторый сравнительный анализ и рекомендации по применению этих методов. В недавно опубликованной теореме утверждается, что для всех алгоритмов, ищущих экстремум функции качества, производительность их одинакова, если усреднить результаты по всевозможным функциям качества. Практическое значение этой теоремы состоит в том, что не существует панацеи на все случаи жизни, несомненный успех какоголибо оптимизационного метода в определенной области знаний не гарантирует такого же успеха в другой области. Это означает, что для каждой специфической области необходимо проводить исследования и отыскивать тот оптимизационный метод, который подходит ей более всего. Далее рассмотрим различные эвристические методы поиска, наиболее используемые и популярные на сегодняшний день. Повидимому, впервые идея о пользе применения случайного поведения при поиске была сформулирована У. Р. Эшби в его книге Конструкция мозга, одним из первых в России этой проблемой занимался Л. А. Растригин и пр В последнее время, в связи с развитием новых технологий этой проблеме уделяется пристальное внимание, поэтому представляется целесообразным дать крагкое описание основных методов случайного поиска, применяемых в настоящее время. Для определенности будем полагать, что задачей алгоритма оптимизации является минимизация функции качества. Это самый простой и в то же время самый известный алгоритм случайного поиска, состоящий из равномерного случайного бросания точек в пространство поиска. Основное его достоинство простота, и в теории глобальной оптимизации этот алгоритм применяется в основном в качестве эталона при теоретическом или численном сравнении алгоритмов и в качестве составной части некоторых алгоритмов глобального случайного поиска. Алгоритм предполагает четкое разделение между поисковыми и рабочими шагами системы. В случайном направлении, определяемым случайным единичным вектором, по обе стороны от исходного состояния делаются пробы.