автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Эволюционные алгоритмы моделирования и оптимизации сложных систем

На правах рукописи

СОПОВ ЕВГЕНИЙ АЛЕКСАНДРОВИЧ

ЭВОЛЮЦИОННЫЕ АЛГОРИТМЫ МОДЕЛИРОВАНИЯ И ОПТИМИЗАЦИИ СЛОЖНЫХ СИСТЕМ

05.13.01 - Системный анализ, управление и обработка информации

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Красноярск - 2004

Работа выполнена в Государственном образовательном учреждении высшего профессионального образования «Сибирский государственный аэрокосмический университет имени академика М.Ф. Решетнёва», г. Красноярск

Научный руководитель: доктор технических наук, профессор

Семенкин Евгений Станиславович

Официальные оппоненты: доктор технических наук, профессор

Терсков Виталий Анатольевич

доктор технических наук, профессор Слюсарчук Валентин Федорович

Ведущая организация: Томский государственный университет

Защита состоится 16 декабря 2004 года в 14 часов на заседании диссертационного совета Д 212.249.02 при Государственном образовательном учреждении высшего профессионального образования «Сибирский государственный аэрокосмический университет имени академика М.Ф. Решетнёва» по адресу: 660014, г. Красноярск, просп. им. газ. Красноярский рабочий, 31.

С диссертацией можно ознакомиться в библиотеке Сибирского государственного аэрокосмического университета

Автореферат разослан 15 ноября 2004 г.

Ученый секретарь диссертационного совета

И.В. Ковалев

Общая характеристика работы

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

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

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

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

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

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

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

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

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

1ХрОС. НАЦИОНАЛЬНА* БИБЛИОТЕКА С.П«тер«у»г ЛЛ Л ОЭ ^/««с/Л/

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 статей в сборниках трудов. Список публикаций приведен в конце автореферата.

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

Содержание работы

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

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

Х(Х)-> opt, где % - Br -* R\

численные исследования эффективности ГА проводились в сравнении с известным стохастическим методом псевдобулевой оптимизации - методом изменяющихся вероятностей (МИВЕР).

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

N i

н ___

Рк ={р\,.,ркл /=i,«>

где - вероятность присвоения компоненте вектора решения значения \,к- номер итерации, j - номер решения в популяции, N— размер популяции.

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

1. Случайным образом формируются г векторов i^eD, i = \,r (D - допустимая область решений). Вычисляется распределение Р° ={р° ,...,р'},

Вычисляются соответствующие значения оптимизируемого функционала =l,r {х-В2, ->£')■

2. На к-М шаге в соответствии с распределением рк = jp*,..,,^* j формируются векторов

3. Случайным образом формируются новые решения: с вероятностью р" компоненты векторов Х[ е D меняются на противоположные.

4. Вычисляются соответствующие значения функционала ;jf(Jfj[),i = l,r.

5. Выбираются г векторов Хк из Xt_,uXk в соответствии с конкретным правилом отбора.

6. Пересчитывается распределение единичных компонент Хк.

7. Если не выполняется условие остановки, то Хк=Хк, к = к+1, повторить шаги 2 - 6.

В результате численных исследований на представительном множестве тестовых задач было показано, что ВГА превосходит обычный ГА и МИВЕР, как по надежности, так и по быстродействию.

При анализе графиков изменения компонент вектора вероятностей для ВГА, ГА и МИВЕР было отмечено следующее свойство: изменения компонент вектора вероятностей в алгоритмах происходят целенаправленно, в среднем компоненты вектора вероятностей сходятся к истинным значениям, т.е.

р, ->1, еслих] =1 р1 0, еслих' = о'

где р, - г'-я компонента вектора вероятностей,-значение г-й компоненты бу-левого вектора решения задачи.

На основе данного свойства был построен следующий алгоритм прогноза сходимости:

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

2. Набрать статистику =1,...,п. Усреднить по к. Выявить тенденцию изменения компонент р].

3. Положить хТЛисмр>-*1' (1)

1 [0, если -» О

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

„ Г1, есни±(р,- 0,5)>0,. (2)

[О, шаче

Пример усреднения компонент вектора вероятностей в алгоритме прогноза показан на рисунке 1. Сплошная линия - с использованием простого усреднения и критерия (1) и пунктирная - взвешенное усреднение с интегральным критерием (2). Из графиков видно, что взвешенное усреднение с интегральным критерием позволяет выявить тенденцию изменения компонент вектора вероятностей за меньшее число итераций, т.к. уменьшает вклад «неудачных» прогонов.

Предложенный алгоритм прогноза сходимости был программно реализован для ГА, ВГА, МИВЕР и апробирован на том же наборе тестовых задач. Наилучшие результаты получены при использовании прогноза для ВГА, который превосходит исследуемые алгоритмы по быстродействию и активнее использует получаемую статистическую информацию.

Рис. 1. Пример усреднения компонент вектора вероятностей в алгоритме прогноза

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

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

При оптимизации сложных систем часто возникают ситуации, когда с объектом нельзя активно экспериментировать, или вычисление целевого функционала стоит дорого (в смысле времени, стоимости проведения эксперимента и т.д.), тогда оптимизация проводится по модели объекта. Если экспертные знания об объекте в явном виде отсутствуют, то обычно модель строится по имеющимся статистическим данным. В большинстве численных методов идентификации для аппроксимации экспериментальных (статистических) данных используются регрессионные модели. Наибольшее распространение получили нейронные сети, непараметрические методы. Однако недостаток вычислительной модели заключается в том, что она, по сути, является «черным ящиком». Решение задачи символьной регрессии могло бы значительно продвинуть ситуацию.

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

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

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

где fitness(Aj) - пригодность р е ш еАр, ия - обучающая выборка объема S, Error (Aj) - квадратичная ошибка аппроксимации, вычисляемая по всем точкам обучающей выборки, - значение полученного выражения в

точке - некоторый штраф на сложность дерева, выраженный в

суммарном количестве вершин.

Предложена следующая схема алгоритма решения задачи символьной регрессии с помощью метода ГП:

1. Инициализировать популяцию А0 случайным образом одним из методов роста.

2. Оценить популяцию, использую критерий (3).

3. Если выполняется критерий остановки, то закончить работу.

4. На итерации g для поколения Аг произвести селекцию одним из предложенных методов отбора.

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

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

7. Переход к шагу 2.

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

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

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

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

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

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

1. Определить функциональное множество и множество термов (переменные и априори известные константы). Задать параметры алгоритмов ГП и ВГА.

2. Инициализировать популяцию с помощью выбранного способа выращивания деревьев.

3. С помощью ВГА «грубо» настроить численные коэффициенты полученных структур. Оценить популяцию.

4. Применить операторы селекции, скрещивания и мутации. Сформировать новую популяцию.

5. Если заданная точность аппроксимации достигнута, то перейти к шагу 6. Иначе повторить шаги 3-5.

6. Произвести «точную» настройку численных коэффициентов лучшего найденного решения с помощью ВГА.

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

= ----сотр1ех1!у(А))

\ + Error{Aj)

s _

Error(Aj) = - evaIuate(Aj, хк ))г

1

п

N'

(4)

fitness(Aj) =

complexity(A,)

■кп-\к>1

(5)

\ + Епог(А;) у _

Еггог(А= -еуа!иШе{А1, хк))2,

4.1

где - пригодность решения - обучающая выборка объема

- квадратичная ошибка аппроксимации, вычисляемая по всем точкам

в

обучающей выборки, evaluate{Aj,xk) - значение полученного выражения ^ точке хк, complexity {Aj) - некоторый штраф на сложность дерева, выраженный в суммарном количестве вершин, N - число переменных задачи, п - число различных переменных, представленных в решении

В критерии (4) штраф за отсутствие в решении переменных пропорционален количеству отсутствующих переменных, в критерии (5) штраф гораздо жестче - имеет экспоненциальную зависимость.

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

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

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

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

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

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

В ходе решения практической задачи объектом исследования являлась малогабаритная ТЭС на водородных топливных элементах, исследуемая в институте автоматизации управления при Высшей технической школе Ульм (ФРГ). Инженерами института автоматизации управления была разработана имитационная модель, выделены 12 параметров, которые устанавливаются перед запуском электростанции и которые должны оказывать существенное влияние на эффективность работы ТЭС: расход воздуха в топливном элементе, расход воды на реформере газа, температура в реформере, расход природного газа, давление в топливном элементе, температура воды в топливном элементе, температура высокотемпературного реактора, температура низкотемпературного реактора, давление газа в реформере, отношение количества воздуха подводимого до/после блока реактора-окислителя, расход воды в увлажнителе, расход воды в увлажнителе.

В качестве критерия оптимизации была предложена электрическая производительность (выход тепла в рассмотрение не берется) для установившегося режима работы ТЭС. Математически критерий выглядит следующим образом:

где Ег - вырабатываемая электроэнергия, - суммарное потребление энергии для обеспечения нормального функционирования - интенсив-

ность расхода природного газа.

Сложность задачи оптимизации состоит в том, что априорная информация о свойствах целевой функции отсутствует, т.к. функция задана алгоритмически (имитационной моделью). Однократное вычисление производительности по результатам имитации работы ТЭС требует до 20 минут реального времени.

Рис. 3. Блок-схема совместной процедуры моделирования и оптимизации сложных систем эволюционными алгоритмами

В качестве алгоритма оптимизации использовался вероятностный генетический алгоритм. В результате применения ВГА после 575 вычислений целевой функции было найдено решение, позволяющее получить производительность равную 11.5%. Лучшее значение производительности, полученное ранее по модели исследуемой ТЭС, было равно 5.5%.

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

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

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

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

Основные результаты и выводы

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

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

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

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

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

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

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

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

Публикации по теме диссертации

1. Гуменникова А.В. Об эволюционных алгоритмах решения сложных задач оптимизации / Гуменникова А.В., Емельянова М.Н., Семенкин Е.С., Со-пов Е.А. // Вестник Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнева. - Вып. 4. - Красноярск: СибГАУ, 2003. С.14-23.

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

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

4. Ефимов С.Н. Применение метода генетического программирования при обработке статистических данных / Ефимов С.Н., Сопов ЕА. // Компьютерное моделирование - 2004. - СПб : Изд-во "Нестор", 2004.- С. 31-34.

5. Ефимов С.Н. Применение метода генетического программирования для задач символьной регрессии при обработке результатов экспериментов / Ефимов С.Н., Сопов Е.А. // Информационные технологии в проектировании и производстве, №2, 2004. - 42-46 с.

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

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

»23 20 1

8. Сопов Е.А. Вероятностный генетический алгоритм и его исследование // VII Королевские чтения. Том 5. - Самара: Изд-во Самарского научного центра РАН, 2003. - С. 38-39.

9. Сопов Е.А. Исследование алгоритмов прогноза сходимости генетического алгоритма с бинарным представлением решений // Решетневские чтения. -Красноярск: СибГАУ, 2003. С. 243-244.

10. Сопов Е.А. О вероятностном генетическом алгоритме // Современные техника и технологии. В 2-х т. - Томск: Изд-во Томского политехи. ун-та,-2004. -Т.2.-С. 197-199.

11. Сопов Е.А. Вероятностный генетический алгоритм решения сложных задач оптимизации и его исследование // Молодежь Сибири - науке России. -Красноярск: СИБУП, 2004. - С. 26-29.

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

13.Sopov Е.А. Probabilistic genetic programming design // Actual problems of informatics and intelligent techniques. - Tambov, 2004. - P. 98 - 99.

Сопов Евгений Александрович

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

Автореферат

Подписано к печати ff_.Jjl.2004 Формат 60x84/16. Бумага писчая. Печ. л. 1.0 Тираж 100 экз. Заказ № Отпечатано в отделе копировальной и множительной техники СибГАУ 660014 г. Красноярск, просп. им. газеты "Красноярский рабочий", 31

26

Введение

Глава 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%.

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

Заключение

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.