Адаптивные эволюционные алгоритмы решения сложных задач оптимизации

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

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

ГЛАВА 1. Разработка и исследование вероятностного генетического

алгоритма для решения задач однокритериальной оптимизации

1.1 Стандартный генетический алгоритм

1.2 Вероятностный генетический алгоритм

1.3 Условная оптимизация эволюционными алгоритмами

1.4 Экспериментальное исследование эффективности алгоритмов

1.5 Выводы

ГЛАВА 2. Разработка и исследование вероятностного генетического

алгоритма для решения задач многокритериальной оптимизации

2.1 Многокритериальная оптимизация генетическими алгоритмами
2.2 Экспериментальное исследование
2.3 Результаты исследований эффективности алгоритмов
2.4 Выводы
ГЛАВА 3. Практическая реализация разработанных алгоритмов
3.1 Программная система для решения однокритериальных задач
3.2 Программная система для решения многокритериальных задач
3.3 Реальные практические задачи
3.4 Система поддержки принятия решения для инвестиционного аналитика
3.5 Результаты решения практических задач
ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ


В ГА существует строгое различие между фенотипом (решением, выраженным в терминах поставленной задачи) и генотипом (хромосомой, представлением решения). ГА работает с генотипом, фенотип служит для определения пригодности индивида (оценки качества решения поставленной задачи) []. Поэтому для работы алгоритма необходимо определить некоторую функцию кодирования (е : D -» 5, где D - пространство поиска, S-пространство представлений решений) и функцию декодирования (е"‘ :S~> D). СО = /Ог’(*)) = Ж>. На практике наибольшее распространение получили ГА с бинарным представлением решений [,]. В -> R'. Инициализировать случайным образом популяцию решений. С помощью оператора селекции выбрать наиболее пригодную часть популяции (родителей) для порождения новых решений (потомков). Применить оператор скрещивания. Сформировать новую рабочую популяцию из родителей и потомков. Новую популяцию подвергнуть мутации. Повторять шаги 2-5 пока не выполнится условие остановки. На шаге инициализации задаются параметры алгоритма: длина хромосомы, размер популяции и др. Если априорные сведения о пространстве поиска отсутствуют, то начальная популяция генерируется случайным образом с помощью датчика псевдослучайных чисел. Пользователем задается размерность турнира Ntur. Случайным образом из популяции индивидов выбираются Nlur индивидов. Из выбранных N(ur индивидов для дальнейшей обработки отбирается индивид с наилучшей функцией пригодности []. Вероятность индивида быть отобранным в популяцию родителей пропорциональна его пригодности. При применении ранговой селекции индивиды популяции ранжируются в соответствии с их пригодностью: К, <Л7 если /(Х')<Т{Х]). Р(Х‘) = ^ = 4- = -? Р(Х')=. Одноточечное скрещивание. Два индивида, отобранные операцией селекции, подвергаются операции скрещивания. Оба индивида представлены бинарной строкой. Одноточечное скрещивание позволяет получить два новых индивида, как показано на рисунке ниже. Точка разрыва выбирается случайно []. Потомок 1 lj. Потомок 2 0 0 ! Двухточечное скрещивание. При двухточечном скрещивании случайным образом выбираются две точки разрыва. Хромосомы обмениваются сегментами, которые лежат между точками разрыва. Схематично двухточечное скрещивание изображено на рисунке ниже []. Родитель 1 ! Потомок 1 г. I . При равномерном скрещивании двух (и более) отобранных селекцией родителей, каждый бит потомка получается путем равновероятного выбора из соответствующих битов родителей []. Схематично равномерное скрещивание изображено на следующем рисунке. Родитель 1 I 1 I 1 I I I ! I I 1 ! Родитель 2 О О О 0. ГсПоГоЩ Л. С выбранной вероятностью Рт1е каждый бит индивида, полученного при скрещивании, изменяется на противоположный. N - количество бит в индивиде (хромосоме); ? Лф. В зависимости от параметра 5 различают следующие типы мутаций: слабая (5=1/3), средняя (5=1) и сильная (5=3) []. Формируется промежуточная популяция путем объединения популяции родителей и популяции потомков. В новое поколение переходят N лучших индивидов (в смысле функции пригодности) промежуточной популяции. Где N - размер популяции. В новое поколение переходит заданный процент лучших индивидов из популяции родителей. Для того чтобы размер популяции оставался равен заданному ранее числу, недостающее количество индивидов берется из лучших индивидов популяции потомков. Алгоритм заканчивает работу, когда выполнено ^,хЛГ2 вычислений целевой функции, где N1 И N2 - число поколений и размер популяции, соответственно. Нетрудно понять, что ГА накапливают и обрабатывают некоторую статистическую информацию о пространстве поиска, однако эта статистика в явном виде отсутствует. Инициализировать случайным образом популяцию решений с помощью датчика псевдослучайных чисел. С помощью оператора селекции выбрать г наиболее пригодных индивидов текущей популяции (родителей). В соответствии с распределением Р сформировать популяцию потомков с помощью датчика псевдослучайных чисел. Из популяции родителей и потомков сформировать новую рабочую популяцию. Новую популяцию подвергнуть мутации. Повторять шаги 2-5 пока не выполнится условие остановки.