Дифференцированный генетический алгоритм решения сложных задач оптимизации

• Автор: Паротькин, Николай Юрьевич
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Красноярск
• Количество страниц: 135 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ

1 ЭВОЛЮЦИОННЫЕ МОДЕЛИ И АЛГОРИТМЫ ОПТИМИЗАЦИИ

1.1 Классические модели эволюции

1.2 Модель синтетической эволюции

1.3 Модели эволюции, построенные на полиморфизме

1.4 Выводы

2 РАЗРАБОТКА И ИССЛЕДОВАНИЕ ДИФФЕРЕНЦИРОВАННОГО ГЕНЕТИЧЕСКОГО АЛГОРИТМА

2.1 Модель дифференцированного генетического алгоритма

2.2 Дифференцированный генетический алгоритм решения задачи безусловной оптимизации
2.3 Исследование эффективности дифференцированного ГА решения задачи безусловной оптимизации
2.4 Дифференцированный генетический алгоритм решения задачи условной оптимизации
2.5 Исследование эффективности дифференцированного
генетического алгоритма решения задачи условной оптимизации .
2.6 Выводы
3 ПРИМЕНЕНИЕ ДИФФЕРЕНЦИРОВАННОГО ГЕНЕТИЧЕСКОГО АЛГОРИТМА ПРИ РЕШЕНИИ СЛОЖНЫХ ЗАДАЧ ОПТИМИЗАЦИИ
3.1 Программная система исследования эффективности ГА
3.2 Задача структурно-параметрического синтеза сети Wi-Fi..
3.2.1 Постановка задачи
3.2.2 Алгоритм расчет зоны действия сигнала

3.2.3 Программная реализация метода расчёта параметров сети Wi-Fi
3.2.4 Проверка корректности модели беспроводной сети.
3.3 Применение ГА при прогнозировании временных рядов
3.3.1 Постановка задачи
3.3.2 Описание алгоритма построения нечеткого временного ряда
3.3.3 Программная реализация метода прогноза на основе нечеткого временного ряда
3.3.4 Проверка эффективности алгоритма на тестовых данных
3.4 Выводы
ЗАКЛЮЧЕНИЕ
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
ПРИЛОЖЕНИЕ А
ПРИЛОЖЕНИЕ Б
ПРИЛОЖЕНИЕ В
ПРИЛОЖЕНИЕ Г

ВВЕДЕНИЕ
Актуальность. Для решения сложных задач оптимизации на практике часто применяют эволюционные алгоритмы. Однако, в отличие от эволюции, происходящей в природе, эволюционный алгоритм, в процессе решения задачи оптимизации, только моделирует те процессы в популяции, которые являются существенными для развития. Существует большое количество моделей эволюции, которые могут применяться в качестве базиса для проектирования эволюционных алгоритмов оптимизации, например, модели Ч. Дарвина, Ж. Ламарка, Г. де Фриза, Гулда-Элдриджа и другие. В любом случае эволюционный алгоритм работает с совокупностью индивидов - популяцией, каждый из которых представляет возможное решение проблемы. В процессе работы алгоритм, в рамках выделенного ресурса, исследует пространство поиска путем информационного обмена с внешней средой, то есть популяция всегда эволюционирует в соответствующей среде. В целом, эволюция подразумевает наличие двух главных аспектов: сохранение и изменение. Для эффективной реализации первого аспекта популяция должна быть устойчивой, стабильной, неизменяемой, то есть информационно дистанцироваться от среды. С другой стороны (второй аспект), без тесного информационного контакта со средой невозможен поиск решения - популяция должна постоянно эволюционировать. Таким образом, требования эволюции с точки зрения информационного обмена популяции со средой являются противоречивыми.
В качестве решения данной проблемы алгоритм, вне зависимости от применяемой модели, как эволюционирующая система, удерживает популяцию на некотором оптимальном информационном расстоянии от среды. Например, для реализации первого аспекта используется селективное давление совместно с принципом элитизма, а для второго аспекта применяются операторы

2 РАЗРАБОТКА И ИССЛЕДОВАНИЕ ДИФФЕРЕНЦИРОВАННОГО ГЕНЕТИЧЕСКОГО АЛГОРИТМА 2Л Модифицированная синтетическая модель эволюции для генетического алгоритма
На основе рассмотренных моделей эволюций, работ Ю.П. Алтухова и
В.А. Геодакяна была разработана модифицированная синтетическая модель эволюции для генетического алгоритма. Она обладает следующими особенностями.
- Наличие двух подсистем, обладающих различными механизмами взаимодействия с внешней средой и выполняющих различные функции по адаптации к ней.
- Подсистема, функционально активно взаимодействующая со средой, должна проводить апробацию новых найденных решений, получаемых на основе уже найденных решений и их случайных изменений.
- Закрытая от внешней среды подсистема (ядро решений)
функционально предназначена для длительного хранения информации об удачных решениях и взаимодействует с внешней средой только через другую подсистему.
- Переход решений между подсистемами возможен только при достаточном времени нахождении их в одной из подсистем в неизменном
состоянии, что обуславливается высоким рангом решения,
соответствующему удовлетворению всем предъявляемым критериям к нему.
Условная упрощенная схема предлагаемой модели эволюции
представлена на рисунке 10. Данная схема на этапе отбора решений позволяет