1. Возможно, генетическому алгоритму оказывается гораздо проще найти точку оптимума функции, чем ждать пока настроится сеть на эту функцию с целью сокращения время оптимизации.

2. Возможно, генетический алгоритм при оптимизации использует те точки пространства, по которым настроить НС нельзя, то есть себя проявляет одна из проблем настройки сети - проблема генерации обучающей выборки или, по другому, проблема формирования точек обучения таким образом, чтобы они адекватно описывали функциональную зависимость (функцию на которую настраиваем НС).

3. Приведенные исследования показали, что при оптимальной структуре ГА требуется около 800 вычислений для нахождения точки оптимума, а НС была настроена при 1000 точек в обучающей выборке. Причем эти точки были случайно сгенерированы, а ГА, как известно, делает все-таки неравномерный разброс по поисковому пространству. То есть, возможно не хватило точек в обучающей выборке.

2.5 Проверка настройки НС во время оптимизации ГА одномерных функций

В предыдущем параграфе были высказаны сомнения по поводу целесообразности обучения НС в процессе оптимизации целевой функции генетическим алгоритмом, так как она должным образом не настраивается. Таким образом, было предложено проверить оправданность настройки нейронной сети на целевую функцию с целью применения ее при оптимизации генетическим алгоритмом в качестве вычисления целевой функции на «простых», одномерных функциях. Для этого вышеописанная программа подверглась некоторой модернизации - в качестве блока функций вычисления того или иного коэффициента готовности КА были «зашиты» простые для оптимизации функции: парабола, модуль корня от числа, комбинация косинуса в качестве многоэкстремальной функции. Начальное окно программы теперь выглядит так (см. рисунок 2.14).

Рис. 2.14 Начальное окно программы настройки сети

В ходе многократных запусков программы было замечено, что функция которую представляет собой НС, настроенная по точкам пройденным ГА, не отражает собой глобальный оптимум (то есть не применима в качестве замены для «настоящей» целевой функции) до тех пор, пока точки ГА не захватят реальный глобальный оптимум. Только тогда можно применять НС, когда она отражает реальный глобальный оптимум. Но остается вопрос: «Как определить что НС начала отражать глобальный оптимум или что ГА нащупал область глобального оптимума?». Ответ на этот вопрос на данный момент еще не найден. По величине ошибки обучения нейронной сети ответить на этот вопрос невозможно. Это доказано многократными запусками программы с одними и теми же настройками.

Приведем пример: на рисунке 2.15 изображено результирующее окно программы. Видно, что хоть НС и настроилась на глобальный оптимум многоэкстремальной функции, но это произошло во-первых после того как ГА нашел (вышел в область глобального оптимума) глобальный оптимум (см. лучшую точку найденную ГА) и во-вторых ошибка обучения достаточно велика.

Рис. 2.15 Результирующее окно программы настройки сети

Следовательно вопрос о целесообразности применения НС в качестве аппроксиматора целевой функции при оптимизации ГА остается открытым. Из проведенных исследований следует, что ответ на этот вопрос скорее «Нет», чем «Да». Во всяком случае, это можно, конечно не уверенно, но хоть как-то обосновать результатами тех исследований, которые были проведены на данный момент. Во всяком случае, попытка решить данный вопрос порождает серию не менее сложных и важных вопросов, чем исходный.

Выводы

Гипотеза о возможности применения нейронной сети в качестве аппроксиматора целевой функции во время оптимизации ее ГА не подтвердилась на практике. Основной причиной на взгляд автора является то, что пока генетический алгоритм не вышел в область глобального оптимума, нейронная сеть обучается на точках которые не имеют ни какого отношения к точке глобального оптимума и поэтому настраиваемая НС не может спрогнозировать точку глобального оптимума. То есть, обучающая выборка НС является не представительной - недостаточно точно отражает поверхность отклика настраиваемой функции. После того ГА вышел в область глобального оптимума нейронная сеть настраивается сравнительно долго и гибридному алгоритму проще сделать несколько шагов ГА и уточнить точку глобального оптимума, чем тратить время на подстройку сети под этот оптимум.

2.6 Гибридизация ГА с алгоритмами локального поиска

Дальнейшим направлением модификации ГА стало его соединение с методами локального поиска (ЛП). Речь идет не об очевидном использовании ЛП после остановки ГА для уточнения положения экстремума, т.к., как отмечалось выше, ГА работал абсолютно надежно, а об использовании ЛП в качестве еще одного "генетического" оператора.

Один из видов гибридизации ГА заключается в следующем. На каждом поколении ГА отбираются несколько (перспективных) индивидов для того, чтобы из них были выполнены несколько шагов ЛП (моделирование прижизненной адаптации индивидов). В зависимости от типа моделируемой эволюции, индивид после локального спуска в следующую популяцию переходит: либо таким же, каким он был перед ЛП, но с «новой» пригодностью (прижизненная адаптация делает индивида более пригодным, но по наследству не передается - эволюция по Дарвину), или таким, каким он стал после ЛП (прижизненная адаптация делает индивида более пригодным и передается по наследству - эволюция по Ламарку). Обе концепции гибридного алгоритма были реализованы совместно с обыкновенным ГА. Для этого была разработана соответствующая программная система, начальное и финальное окна которой представлены на рисунках 2.16 и 2.17.

Рис. 2.16 Начальное окно программы ГА + локальный поиск

Рис. 2.17 Финальное окно программы ГА + локальный поиск

Необходимо обратить внимание на различие в поведении графиков пригодности на рис. 2.7 и 2.17. Очевидно, что гибридный алгоритм намного быстрее выходит на экстремум, чем обычный ГА. Кроме того, он сглаживает осцилляции целевой функции.

Как и в исследованиях с обыкновенным ГА, постоянными параметрами гибридного алгоритма были: численность популяции - 25, число поколений - 35.

В приложениях Б и В приведены таблицы, в которых изображены результаты оптимизации коэффициентов готовности технологического контура КА с помощью гибридного ГА для каждой концепции локального поиска. Также, как и для простого ГА, полужирным шрифтом выделена оптимальная структура алгоритма.

Результаты проведенных экспериментов по сравнению эффективности алгоритмов по тем же показателям, что и раньше: надежность, скорость, разброс:

1. Оптимальной структурой гибридного ГА при использовании концепции ЛП по Дарвину является: турнирная селекция, слабая или сильная мутация, двухточечная рекомбинация.

2. Оптимальной структурой гибридного ГА при использовании концепции ЛП по Ламарку является: турнирная селекция, слабая или средняя мутация, скрещивание может быть различным.

3. При решении данной задачи использование концепции по Ламарку оказалась значительно эффективней, чем по Дарвину.

4. Гибридный алгоритм успешно справился с задачей оптимизации (т.к. показатели надежности равны 1 при использовании концепции по Ламарку)

5. Скорость гибридного алгоритма по сравнению с обыкновенным ГА в два раза выше при оптимальных структурах (см. таблицы 2.1, 2.2 и 2.3).

6. Использование заранее настроенной нейросети для аппроксимации целевых функций в ходе оптимизации не снижает показателей эффективности гибридных алгоритмов, но ускоряет оптимизацию.

Таблица 2.1. Сравнение показателей эффективности ГА и гибридного алгоритма при оптимизации коэффициента готовности КА

Таблица 2.2. Сравнение показателей эффективности ГА и гибридного алгоритма при оптимизации коэффициента готовности ЦА

Таблица 2.3. Сравнение показателей эффективности ГА и гибридного алгоритма при оптимизации коэффициента готовности БКУ

Вывод: использование генетического алгоритма, моделирующего эволюцию по Ламарку, предпочтительнее в силу его большей надежности и скорости сходимости (в 2 раз выше по сравнению с эволюцией по Дарвину) в точку глобального оптимума.

Заключение

При решении сложных задач оптимизации следует сначала исследовать целевые функции на наличие удобных для оптимизации свойств этих функций. Для этого предлагается использовать алгоритмы целочисленной оптимизации: обобщенные и неулучшаемые. После того как свойства изучены, следует применять для оптимизации определенный алгоритм, ориентированный на эффективную оптимизацию функции с данными свойствами.

Если функции оказываются немонотонными и многоэкстремальными, как в нашем случае, то следует использовать генетический алгоритм, моделирующий эволюцию по Ламарку, который имеет хорошую глобальную сходимость. В некоторых случаях, если известно что это оправдано с точки зрения временных затрат, удобно использовать нейронную сеть, заранее настроенную на вычисление значений целевой функции.

Список литературы

1. Воловик М.А. Коэффициент готовности прибора со встроенной системой контроля // Системный анализ и исследование операций. - Новосибирск: ВЦ АН СССР, 1977.

2. Семенкина О.Э. Оптимизация управления сложными системами методом обобщенного локального поиска. - М.: МАКС Пресс, 2002. - 215 с.

3. Semenkin E., Volovik M. Modelling and Optimization of Spacecrafts' Systems Design // Operations research'95. - Berlin: Springer, 1995. - Pp. 353-358.

4. Semenkina O. Adaptive Search Algorithms for Solving Mixed Optimization Problems in CAD of Spacecraft Control Systems // Operations Research'97. - Jena: TU-Jena, 1997.

5. Goldberg D.E. Genetic algorithms in search, optimization and machine learning. Reading, MA: Addison-Wesley, 1989.

6. Семенкин Е.С., Семенкина О.Э., Терсков В.А. Методы оптимизации в управлении сложными системами // Учебное пособие. - Красноярск: СибЮИ МВД РФ, 2000. - 254 с.

7. Уоссермен Ф. Нейрокомпьютерная техника. Теория и практика. - М.: Мир, 1984.

Список публикаций автора

1. Бежитский С.С. О трудоемкости алгоритмов локального поиска для задачи выбора структуры технологического контура космического аппарата //Информатика и информационные технологии: Межвуз. сб. научн. тр./Красноярск: ИПЦ КГТУ, 2003. с.17-19.

2. Бежитский С.С. О свойствах целевой функции в задаче выбора структуры технологического контура космического аппарата // Тезисы докладов 7-й Всероссийской научной конференции «Решетневские чтения». Красноярск: СибГАУ, 2003. - С. 266.

3. Бежитский С.С., Семенкин Е.С., Семенкина О.Э. Разработка и исследование эволюционного алгоритма для оптимизации управления сложными системами // Вестник Кемеровского государственного университета. Журнал теоретических и прикладных исследований. Выпуск 1(17) - Кемерово: КемГУ, 2004. - с.26-33.

4. Бежитский С.С. Гибридный эволюционный алгоритм для решения сложных задач оптимизации // Вестник университетского комплекса. Сборник научных трудов. Выпуск 1(15). - Красноярск: ВСФ РГУИТП, НИИ СУВПТ, 2004. - с.166- 173.

5. Бежитский С.С. Разработка и исследование гибридного эволюционного алгоритма для решения сложных задач оптимизации // Сборник научных трудов. Красноярск: СИБУП, 2004.

6. Бежитский С.С. О монотонности показателей эффективности технологического контура системы управления космическим аппаратом / C.С. Бежитский //Вестник Сибирского государственного аэрокосмического университета. - Выпуск 5. - Красноярск: СибГАУ, 2004. - с. 19-26.

7. Бежитский С.С. Модификация генетического алгоритма для решения задачи оптимизации показателей эффективности технологического контура системы управления космическим аппаратом / С.С. Бежитский // Труды пятой международной конференции молодых ученых и студентов «Актуальные проблемы современной науки». - Самара. 2004. - с.20-23.

8. Бежитский С.С. Сравнение эффективности работы генетического алгоритма и алгоритма эволюционных стратегий на задачах оптимизации многоэкстремальных функций /С.С. Бежитский // Материалы международной «8-ой тамбовской межвузовской» научно-практической конференции.- Тамбов: ТГУ, 2004. - с. 81-82.

Приложение А

Результаты выполнения оптимизации с помощью ГА для каждой из целевых функций

Таблица А.1. Усредненные результаты работы ГА для коэффициента готовности КА

Таблица А.2. Усредненные результаты работы ГА для коэффициента готовности ЦА

Таблица А.3. Усредненные результаты работы ГА для коэффициента готовности БКУ