Эволюционные алгоритмы моделирования и оптимизации сложных систем тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Сопов, Евгений Александрович

• Сопов, Евгений Александрович
• кандидат технических наук
• 2004

Оглавление диссертации кандидат технических наук Сопов, Евгений Александрович

Введение

Глава 1. Разработка и исследование вероятностного генетического 9 алгоритма для оптимизации сложных систем

§ 1.1 Основные свойства задач оптимизации сложных систем и возможные подходы к их решению

§ 1.2 Стандартный генетический алгоритм и исследование его работоспособности на тестовых задачах

§ 1.3 Метод изменяющихся вероятностей (МИВЕР) и исследование 27 его работоспособности на тестовых задачах

§ 1.4 Обоснование вероятностного генетического алгоритма и исследование его работоспособности на тестовых функциях

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

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

§ 2.1 Методы решения задач аппроксимации в моделировании сложных систем

§ 2.2 Обычный метод генетического программирования для решения 48 задачи символьной регрессии и его исследование

§ 2.3 Обоснование гибридного алгоритма генетического программирования и его исследование

§ 2.4 Комплексная процедура моделирования и оптимизации сложных систем

Выводы

Глава 3. Практическая реализация разработанных алгоритмов

§ 3.1 Программная реализация обыкновенного и вероятностного генетических алгоритмов

§ 3.2 Программная реализация обыкновенного и гибридного алгоритмов генетического программирования

§ 3.3 Программная реализация алгоритма прогноза сходимости генетических алгоритмов

§ 3.4 Постановка задачи оптимизации работы электростанции на 88 топливных элементах в стационарном режиме

§ 3.5 Решение задачи оптимизации работы электростанции на топливных элементах в стационарном режиме с помощью вероятностного генетического алгоритма

§ 3.6 Построение символьной модели вычисления эффективности 105 работы электростанции на топливных элементах в стационарном режиме с помощью гибридного алгоритма генетического программирования

Выводы

Введение диссертации (часть автореферата) на тему «Эволюционные алгоритмы моделирования и оптимизации сложных систем»

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Реализация результатов работы. Программные системы, реализующие гибридный метод генетического программирования и вероятностный генетический алгоритм прошли экспертизу и зарегистрированы в отраслевом фонде алгоритмов и программ (ОФАП) Государственного координационного центра информационных технологий Министерства образования и науки (коды программ по ЕСПД: .03524577.00637-01 и .03524577.00638-01, номера государственной регистрации 50200400500 и 50200400501, номера свидетельств об отраслевой регистрации разработок 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%.

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

Заключение

Список литературы диссертационного исследования кандидат технических наук Сопов, Евгений Александрович, 2004 год

1. Антамошкин А.Н. Оптимизация функционалов с булевыми переменными. Томск: Изд-во Том. ун-та, 1987, - 104 с.

2. Бабэ Б. Просто и ясно о Borland С++. М.: БИНОМ, 1994. - 400 с.

3. Вороновский Г.К., и др. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности. X.: ОСНОВА, 1997,

4. Гилл Ф., Мюррэй У. Численные методы условной оптимизации. М.: МИР. 1977.

5. Гмурман В.Е. Теория вероятностей и математическая статистика. Учеб. пособие. М.: Высш. шк., 2000, - 479 с.

6. Гринченко С.Н. Метод «проб и ошибок» и поисковая оптимизация: анализ, классификация, трактовка понятия «естественный отбор». Электронный журнал «Исследовано в России», 2003.

7. Ефимов С.H. О решении задач символьной регрессии методом генетического программирования / Ефимов С.Н., Сопов Е.А. // Вестник НИИ СУВПТ: Сб. научн. трудов. Красноярск: НИИ СУВПТ, 2003. - Вып.i: 13, 220-229 с.

8. Ефимов С.Н. Обработка результатов экспериментов с помощью метода генетического программирования / Ефимов С.Н., Сопов Е.А., Харин М.Г. // Вестник КГТУ. Машиностроение: Сб. научн. трудов. Красноярск: ИПЦ КГТУ, 2003. - Вып. 32, 404 е., 180-188 с.

9. Заенцев И.В. Нейронные сети: основные модели. Учеб. пособие к курсу «Нейронные сети», ВГУ, Воронеж, 1999.

10. Карманов В.Г. Математическое программирование // БСЭ, т. 15. М.: Советская энциклопедия, 1974.

11. Медведев A.B. Непараметрические системы адаптации. Новосибирск: Наука, 1983,- 174 с.

12. Оптимизация http://glossary.basegroup.rU/o/optimization.htm.

13. Перегудов Ф.И., Тарасенко Ф.П. Основы системного анализа: Учеб. 2-е изд., доп. Томск, 1997.

14. Растригин JI.A. Бинаризация задач оптимизации решений в САПР. В кн.: Моделирование и оптимизация решений в САПР. Таллин, 1983, ч.2.

15. Растригин JI.A. Случайный поиск. М.: Знание, 1979.

16. Растригин JI.A. Адаптация сложных систем. М.: Наука, 1981. 415 с.1. Красноярск, 1994, 220 с.

17. Рубан А.И. Методы оптимизации: Учебное пособие. Изд. 2-ое. Красноярск НИИ ИПУ, 2001. 528 с.

18. Семенкин Е.С., Семенкина О.Э., Коробейников С.П. Оптимизация технических систем. Учебное пособие. Красноярск: СИБУГ1, 1996.

19. Сопов Е.А. Вероятностный генетический алгоритм решения сложных -V) задач оптимизации и его исследование // Молодежь Сибири науке

20. России: Сб. материалов Межрегиональной научно-техничесчкои конференции / Сост.: Сувейзда В.В.; ГУЦМиЗ, КРО НС «Интеграция». СИБУП. Красноярск, 2004. - 208 с. 26-29 с.

21. Сопов Е.А. Вероятностный генетический алгоритм с прогнозированием сходимости // Вестник университетского комплекса: Сб. научн. Трудов Под общей ред. Профессора Н.В. Василенко; Красноярск: ВСФ РГУИТП, НИИ СУВПТ. 2004. - Вып 1(15).- 292 е., 219-227 с.

22. Сопов Е.А. О вероятностном генетическом алгоритме // X Юбилейная Международная научно-практическая конференция студентов, аспирантов и молодых ученых «Современные техника и технологии», посвященная

23. Y' 400-летию г. Томска, 29 марта 2 апреля 2004г. Труды. В 2-х т. - Томск:

24. Изд-во Томского политехи, ун-та, 2004. Т.2. - 378 е., 197-199 с.

25. Сопов Е.А. Прогнозирование временных рядов с помощью генетического программирования // Материалы региональной межвузовской научно-практической конференции «Молодежь Сибири науке России» /Сост. Д.О. Иванова; СИБУП, Красноярск, 2002. - 432 е., 178-180 с.

26. Сопов Е.А. Разработка и исследование вероятностного генетического алгоритма // Информатика и информационные технологии. Межвуз. Сб. научн. Тр. / Под ред. В.А. Вейсова, Ю.А. Шитова. Красноярск: ИПЦ КГТУ, 2003. 306с., 225-227 с.

27. Сопов Е.А. Программная реализация вероятностного генетического алгоритма решения сложных задач оптимизации // М. ВНТИЦ, 2004. .М4. гос. рег. 50200400501. 3 с.

28. Сопов Е.А. Приложение для решения задачи символьной регрессии с помощью метода генетического программирования // М. ВНТИЦ, 2004. -№ гос. рег. 50200400500. 4 с.

29. Уоссермен Ф. Нейрокомпьютерная техника: теория и практика. — М.: Мир, 1992.

30. Хаймен M. Borland С++ для «чайников». К.: «Диалектика», 1995. -416с .

31. Харт-Дэвис Г. Microsoft Windows ХР Professional. Полное руководство. -СП ЭКОМ, 2003.-816 с.

32. Черноруцкий, И.Г. Методы оптимизации и принятия решений: Учебное пособие / И.Г. Черноруцкий СПб: Лань, 2001 - 384 с.7 ' 39. Шамис В.А. С++ Builder 3. Техника визуального программирования. М.: «Нолидж», 1998.-512 с.1.l

33. Antamoshkin A., Schwefel H.-P., Torn A., Yin G., Zilinskas A. System Analysis, Design and Optimization. An Introduction. Krasnoyarsk, 1993. -203 p.

34. Back, Hoffmeister, Schwefel. A Survey of Evolution Strategies. / Proc. 4 International Conf. on Genetic Algorithms, 1991.

35. Baluja S. The Equilibrium Genetic Algorithm and the Role of Crossover. 1993.

36. Baluja S., Caruana R. Removing the Genetic from the Standard Genetic Algorithm. In Proc. Of the Twelfth International Conference on Machine Learning, 1995.

37. Banzhaf W., Francone F. D., Nordin P. Explicitly Defined Introns and Destructive Crossover in Genetic Programming. Sys. report. Department Of Computer Science, University of Dortmund, Germany, 1995.

38. Caruana R., Schaffer J., Representation and Hidden Bias: Gray vs. Binary Coding for Genetic Algorithms. Proc. 5lh International Conference of Machine Learning, 1988.

39. Cramer N. L. A representation for the adaptive generation of simple sequential programs. Proceedings of an International Conference on Genetic Algorithms and Their Applications. Hillsdale, NJ: Lawrence Erlbaum Associates, 1985.

40. De Jong K.A., Spears W.M. An Analysis of the Interacting Role of Population Size and Crossover in Genetic Algorithms.

41. Ferguson A., Ugursal I. A Fuel Cell Model for Building Cogeneration Applications.- Tech. Report, Canadian Resedential Energy End-use Data and Analysis Center.