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

Актуальность темы

При решении задач оптимизации сложных систем у. часто встречаются ситуации, которые затрудняют или делают невозможным применение классических методов, такие как неопределенность, разношкаль-ность, вычислительная сложность, высокая размерность, существенная нелинейность и многоэкстремальность. Эволюционные алгоритмы способны преодолевать многие из возникающих трудностей [42, 43, 46, 78, 81, 83]. В частности, генетические алгоритмы реализуют прямой поиск, тем самым исключают проблему неопределенности, переменные решаемой задачи в генетических алгоритмах кодируются бинарными строками — решается проблема разношкаль-ности. Как показывает практика применения эволюционных алгоритмов, высокая размерность задач, нелинейность и многоэкстремальность не создают для них дополнительных проблем. В том числе, эволюционные алгоритмы способны преодолеть проблему вычислительной сложности, путем решения задачи символьной регрессии с помощью метода генетического программирования. Символьная регрессия дает не только вычислительную процедуру, но и символьное математическое выражение, которое можно было бы подвергнуть содержательному анализу, упростить, уточнить, и далее использовать для оптимизации.

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

Целью работы является совершенствование процедур моделирования и оптимизации сложных систем с помощью эволюционных алгоритмов.

Поставленная цель определила следующие основные задачи исследоваг ния:

1. Провести анализ основных свойств задач оптимизации сложных систем и возможных подходов к их решению.

2. Программно реализовать и провести сравнительный анализ эффективности стохастических поисковых методов с бинарным представлением решений и генетического алгоритма.

3. Разработать, программно реализовать и оценить эффективность генетического алгоритма, более полно использующего накапливаемую статистическую информацию.

4. Провести анализ методов решения задачи символьной регрессии.

5. Разработать и программно реализовать алгоритм решения задачи символьной регрессии с помощью метода генетического программирования. Показать его работоспособность на тестовых задачах.

6. Разработать процедуру совместного использования предложенных алгоритмов для автоматического генерирования и оптимизации моделей сложных систем.

Методы исследования. Для решения поставленных задач использовались методы системного анализа, исследования операций, теории вероятности, математической статистики, дискретной оптимизации и эволюционных алгоритмов.

Научная новизна диссертационной работы состоит в следующем:

1. Разработан новый генетический алгоритм, отличающийся от известных способом генерирования перспективных решений и превосходящий их по быстродействию и надежности.

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

3. Впервые предложен метод прогноза сходимости стохастических г поисковых алгоритмов решения задач оптимизации с булевыми переменными.

4. Впервые предложена интегрированная процедура для автоматизированного генерирования и оптимизации моделей сложных систем эволюционными алгоритмами.

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

Реализация результатов работы. Программные системы, реализующие гибридный метод генетического программирования и вероятностный генетический алгоритм прошли экспертизу и зарегистрированы в отраслевом фонде алгоритмов и программ (ОФАП) Государственного координационного центра информационных технологий Министерства образования и науки (коды программ по ЕСПД: .3 524 577.00637−01 и .3 524 577.00638−01, номера государственной регистрации 50 200 400 500 и 50 200 400 501, номера свидетельств об отраслевой регистрации разработок 3507 и 3508).

Предложенная система моделирования и оптимизации сложных систем на основе гибридного алгоритма генетического программирования и вероятностного генетического алгоритма использована при решении актуальной практической задачи — оптимизации работы электростанции на топливных элементах в установившемся режиме. Полученные с помощью вероятностного генетического алгоритма параметры позволяют повысить эффективность работы станции на 6.4%. Результаты решения переданы Институту автоматизации управления при Высшей технической школе г. Ульм (ФРГ).

Предложенные в диссертации алгоритмы и программные системы используются в учебном процессе при проведении занятий по специальным курсам «Системы искусственного интеллекта» и «Адаптивные и эволюционные методы принятия решений» в Сибирском государственном аэрокосмическом университете, а также по общему курсу «Методы оптимизации» и специальным курсам «Системный анализ и управление» и «Эволюционные алгоритмы оптимизации» в Красноярском государственном университете.

Основные защищаемые положения:

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

2. Гибридный алгоритм генетического программирования позволяет строить адекватные аналитические модели сложных систем по результатам наблюдений и превосходит стандартный алгоритм генетического программирования по быстродействию.

3. Метод прогноза сходимости алгоритмов позволяет повысить их надежность и снизить трудоемкость.

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

Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на следующих научно-практических конференциях: Межвузовская научно-практическая конференция «Молодежь Сибири — науке России», СИБУП, Красноярск, 2002; Межвузовская научная конференция «Информатика и информационные технологии», КГТУ, Красноярск, 2003; XXVI Научная студенческая конференция по математике, КГУ, 2003; Краевая выставка технических идей и разработок «Первый сибирский техносалон», Красноярск, 2003; Всероссийская научно-техническая конференция с молодых ученых «Совершенствование методов поиска и разведки, технологий добычи и переработки полезных ископаемых», КрасГАЦиЗ, Красноярск, 2003; Всероссийская молодежная научная конференция «VII Королевские чтения», Самара, 2003; Всероссийская научная конференция «Решетневские чтения», Красноярск, 2003; X Юбилейная Международная научно-практическая конференция молодых ученых «Современные техника и технологии», Томск, 2004; Международная научно-практическая конференция «Актуальные проблемы информатики и информационных технологий», Тамбов, 2004.

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

Публикации. По результатам диссертационной работы опубликовано пятнадцать печатных научных работ, среди которых 7 статей в сборниках трудов. Список публикаций приведен в конце диссертации.

Структура и объем работы. Диссертация содержит 118 страниц основного текста и состоит из введения, трех глав, заключения, списка литературы из 84 наименований и двух приложений.

Основные результаты работы:

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

2. Обоснован и разработан вероятностный генетический алгоритм, отличающийся от стандартного генетического алгоритма способом генерирования перспективных решений и превосходящий его как по надежности, так и по быстродействию.

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

4. Обоснован и разработан гибридный алгоритм символьной регрессии, сочетающий стандартную процедуру генетического программирования для выбора структуры модели и вероятностный генетический алгоритм для настройки ее параметров.

5. Обоснована и реализована интегральная процедура автоматизированного моделирования и оптимизации сложных систем эволюционными алгоритмами.

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

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

Заключение

.