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

• Автор: Неймарк, Елена Александровна
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Нижний Новгород
• Количество страниц: 144 с. : ил.

1 ПОСТАНОВКА ЗАДАЧИ НЕСТАЦИОНАРНОЙ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ

1.1 Нестационарные задачи комбинаторного типа

1.2 Трудности решения задач комбшьаторного типа

1.3 Обзор методов оптимизации I шстационарных задач

1.4 Критерии оценки эффективгюсти алгоритмов для решения задач в динамических средах

2 ГАПЛОИДНЫЙ ГЕНЕТИЧЕСКИЙ АЛГОРИТМ ДЛЯ РЕШЕНИЯ НЕСТАЦИОНАРНЫХ ЗАДАЧ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ

2.1 Переход от задачи дискретной оптимизации к задаче поиска, генетический поиск.

2.2 Основные определения и структура генетического алгоритма

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

2.4 Применение популяционногенетического алгоритма к решению нестационарных задач дискретной оптимизации
2.5 Применение генетического алгоритма к решению задачи коммивояжера большой размерности.
2.6 Гаплоидный генетический алгори тм с гипермутацией
2.7 Генетический алгоритм с использованием базы опыта для формирования начальной популяции.
3 ТЕОРЕТИЧЕСКОЕ ИССЛЕДОВАНИЕ ПОВЕДЕНИЯ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ
3.1 Шаблоны сходства генотипов.
3.2 Основные теоретические результаты
3.3 Время сходимости и время захвата.
3.4 Применение цепей Маркова для исследования генетического
ДРЕЙФА В ГЕНЕТИЧЕСКИХ АЛГОРИТМАХ.
4 ГЕНЕТИЧЕСКИЙ АЛГОРИТМ С ДИПЛОИДНЫМ ПРЕДСТАВЛЕНИЕМ ГЕНОТИПА ДЛЯ РЕШЕНИЯ НЕСТАЦИОНАРНЫХ ЗАДАЧ.
4.1 Диплоидная хромосома. Понятие доминировавия.
4.2 Операторы кроссовера и мутации для диплоидного
представления.
4.3 Диплоидные алгоритмы с доминированием и без
4.4 Диплоидный алгоритм для задач на перестановках.
4.5 Ме тод, основанный на структурном представлении генотипа
5 ВЫЧИСЛИТЕЛЬНЫЙ ЭКСПЕРИМЕНТ.
5.1 Ме тоды адан ации нестационарных функций
5.2 Описание программного комплекса
5.3 Сравнение различных подходов к адаптации решений на основе
ПОПУЛЯЦИОП ЮГЕНЕШЧЕСКИХ МЕТОДОВ.
5.4 Сравнение популяционногенетического алгоритма с
классическими алгоритмами на задаче о ранце1
5.5 Использование популяционногенетического алгоритма в
ЗАДАЧЕ ОПРЕДЕЛЕНИЯ ОПТИМАЛЬНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ ВЫПОЛНЕНИЯ ОПЕРАЦИЙ ТЕХНОЛОГИЧЕСКОГО КОНТРОЛЯ ПРИ ПРОИЗВОДСТВЕ ИЗДЕЛИЙ МИКРОЭЛЕКТРОНИКИ С МИКРОННЫМИ ТОПОЛОГИЧЕСКИМИ НОРМАМИ
5.6 Использование популяционногенетического алгоритма в
задаче загрузки уникального оборудования.1
6 ЗАКЛЮЧЕНИЕ
7 СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ
8 ПРИЛОЖЕНИЯ
Приложение А
Приложение Б
Введение


Исследования по теме диссертационной работе проводились в рамках бюджетной темы Математическое моделирование и создание новых методов анализа динамических систем и систем оптимизации. Работа состоит из пяти глав, введения, заключения, списка литературы и приложений. Общий объем работы составляет 6 страниц. Список литературы составляет 0 наименований. По теме диссертации опубликовано работ в том числе 7 статей, 3 из которых опубликованы в сборниках, рекомендованных ВАК, и одно учебное пособие. Основные результаты диссертации опубликованы в следующих работах 6,7,9,,,,. В главе 1 приводится постановка задачи оптимизации нестационарной функции как декомпозиция конечного числа стационарных задач оптимизации. Приводятся постановки нестационарных задач комбинаторного типа на примере задачи о ранце и задачи коммивояжера. Ставится задача адаптации оптимальных решений нестационарной функции при помощи популяционногенетических алгоритмов. В 1. В частности проблема нерегулярности, трудности при определении окрестности решения, и вычислительная сложность. Вводится понятие окрестности для бинарных кодировок и кодировок в виде перестановок. В 1. Поскольку методы сравнения эффективности алгоритмов оптимизации стационарных функций не подходят для сравнения эффективности алгоритмов оптимизации нестационарных функций, то в 1. В главе 2 даются основные понятия генетического алгоритма на примере генетического алгоритма с гаплоидным представлением генотипа. В 2. В 2. В 2. В 2. Также приводятся эвристические алгоритмы получения приближенного решения для стационарной задачи, которые используются для улучшения качества получаемого решения в генетическом алгоритме. Для нестационарной задачи о ранце и нестационарной задачи коммивояжера в 2. Показаны используемые при решении задач методы кодирования и предложены модификации основных операторов генетического алгоритма. В 2. Для реализации этого подхода предложено использование ярусного генотипа, для которого разработаны специальные операторы, гарантирующие допустимое разбиение на регионы и построение гамильтонова цикла. В 2. В 2. В основе этого метода лежит использование внешней памяти для запоминания и дальнейшего использования решений, найденных при определенных состояниях среды. В главе 3 приводятся основные результаты теоретического исследования поведения генетических алгоритмов на примере генетического алгоритма с бинарным кодированием генотипа. В 3. Схема это шаблон, представленный строкой длины состоящей из символов 0,1,, который описывает сходство генотипов в определенных позициях. Понятие шаблона является основным в теоретическом исследовании поведения генетических алгоритмов. Вводится понятия средней приспособленности шаблона и средней наблюдаемой приспособленности. В 3. В частности, фундаментальная теорема генетических алгоритмов, теорема о неявном параллелизме и исследование сходимости генетического алгоритма на базе цепей Маркова. В следующих параграфах 3. Рассматривается процесс изменения пропорции аллелей в одном локусе популяции при переходе в следующее поколение. Выводятся рекуррентные соотношения для изменения пропорции аллелей формулы, отражающие время сходимости и захвата признаком популяции. В главе 4 приводятся основные понятия, операторы и алгоритмы для диплоидного представления генотипа. В 4. Поскольку диплоидный генотип имеет две гомологичные хромосомы, то генетические операторы для него будут отличаться от классических операторов. В 4. Существует несколько алгоритмов, основанных на диплоидном представлении генотипа. Эти генетические алгоритмы приведены в 4. Общей чертой этих алгоритмов является использование принципа доминирования. Для триаллельного и четырехаллельиого алгоритма формулируются и доказываются утверждения об изменении пропорции аллелей в популяции при переходе в следующее поколение. В 4. Для него описаны варианты операторов кроссовера и мутации. Этот подход специально разработан для нестационарной задачи коммивояжера. В главе 5 приводятся результаты вычислительного эксперимента. В 5. В 5. В 5. В 5. В 5.