Разработка и исследование гибридного алгоритма решения сложных задач оптимизации
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
?ом в качестве вычисления целевой функции на простых, одномерных функциях. Для этого вышеописанная программа подверглась некоторой модернизации - в качестве блока функций вычисления того или иного коэффициента готовности КА были зашиты простые для оптимизации функции: парабола, модуль корня от числа, комбинация косинуса в качестве многоэкстремальной функции. Начальное окно программы теперь выглядит так (см. рисунок 2.14).
Рис. 2.14 Начальное окно программы настройки сети
В ходе многократных запусков программы было замечено, что функция которую представляет собой НС, настроенная по точкам пройденным ГА, не отражает собой глобальный оптимум (то есть не применима в качестве замены для настоящей целевой функции) до тех пор, пока точки ГА не захватят реальный глобальный оптимум. Только тогда можно применять НС, когда она отражает реальный глобальный оптимум. Но остается вопрос: Как определить что НС начала отражать глобальный оптимум или что ГА нащупал область глобального оптимума?. Ответ на этот вопрос на данный момент еще не найден. По величине ошибки обучения нейронной сети ответить на этот вопрос невозможно. Это доказано многократными запусками программы с одними и теми же настройками.
Приведем пример: на рисунке 2.15 изображено результирующее окно программы. Видно, что хоть НС и настроилась на глобальный оптимум многоэкстремальной функции, но это произошло во-первых после того как ГА нашел (вышел в область глобального оптимума) глобальный оптимум (см. лучшую точку найденную ГА) и во-вторых ошибка обучения достаточно велика.
Рис. 2.15 Результирующее окно программы настройки сети
Следовательно вопрос о целесообразности применения НС в качестве аппроксиматора целевой функции при оптимизации ГА остается открытым. Из проведенных исследований следует, что ответ на этот вопрос скорее Нет, чем Да. Во всяком случае, это можно, конечно не уверенно, но хоть как-то обосновать результатами тех исследований, которые были проведены на данный момент. Во всяком случае, попытка решить данный вопрос порождает серию не менее сложных и важных вопросов, чем исходный.
Выводы
Гипотеза о возможности применения нейронной сети в качестве аппроксиматора целевой функции во время оптимизации ее ГА не подтвердилась на практике. Основной причиной на взгляд автора является то, что пока генетический алгоритм не вышел в область глобального оптимума, нейронная сеть обучается на точках которые не имеют ни какого отношения к точке глобального оптимума и поэтому настраиваемая НС не может спрогнозировать точку глобального оптимума. То есть, обучающая выборка НС является не представительной - недостаточно точно отражает поверхность отклика настраиваемой функции. После того ГА вышел в область глобального оптимума нейронная сеть настраивается сравнительно долго и гибридному алгоритму проще сделать несколько шагов ГА и уточнить точку глобального оптимума, чем тратить время на подстройку сети под этот оптимум.
.6 Гибридизация ГА с алгоритмами локального поиска
Дальнейшим направлением модификации ГА стало его соединение с методами локального поиска (ЛП). Речь идет не об очевидном использовании ЛП после остановки ГА для уточнения положения экстремума, т.к., как отмечалось выше, ГА работал абсолютно надежно, а об использовании ЛП в качестве еще одного "генетического" оператора.
Один из видов гибридизации ГА заключается в следующем. На каждом поколении ГА отбираются несколько (перспективных) индивидов для того, чтобы из них были выполнены несколько шагов ЛП (моделирование прижизненной адаптации индивидов). В зависимости от типа моделируемой эволюции, индивид после локального спуска в следующую популяцию переходит: либо таким же, каким он был перед ЛП, но с новой пригодностью (прижизненная адаптация делает индивида более пригодным, но по наследству не передается - эволюция по Дарвину), или таким, каким он стал после ЛП (прижизненная адаптация делает индивида более пригодным и передается по наследству - эволюция по Ламарку). Обе концепции гибридного алгоритма были реализованы совместно с обыкновенным ГА. Для этого была разработана соответствующая программная система, начальное и финальное окна которой представлены на рисунках 2.16 и 2.17.
Рис. 2.16 Начальное окно программы ГА + локальный поиск
Рис. 2.17 Финальное окно программы ГА + локальный поиск
Необходимо обратить внимание на различие в поведении графиков пригодности на рис. 2.7 и 2.17. Очевидно, что гибридный алгоритм намного быстрее выходит на экстремум, чем обычный ГА. Кроме того, он сглаживает оiилляции целевой функции.
Как и в исследованиях с обыкновенным ГА, постоянными параметрами гибридного алгоритма были: численность популяции - 25, число поколений - 35.
В приложениях Б и В приведены таблицы, в которых изображены результаты оптимизации коэффициентов готовности технологического контура КА с помощью гибридного ГА для каждой концепции локального поиска. Также, как и для простого ГА, полужирным шрифтом выделена оптимальная структура алгоритма.
Результаты проведенных экспериментов по сравнению эффективности алгоритмов по тем же показателям, что и раньше: надежность, скорость, разброс:
1.Оптимальной структурой гибридного ГА при использовании концепции ЛП по Дарвину является: турнирная селекция, слабая или сильная мутация, двухточечная рекомб