Краткое описание МГА и программа в среде Mathcad

Введение

 

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

Опыт исследования алгоритмов управления показал, что для простых одноконтурных систем автоматического регулиро­вания (АСР) с линейными регуляторами задачи оптимизации, как правило, являются одноэкстремальными. Однако для сложных многоконтурных систем управле­ния и систем управления с нейроконтроллерами характерно наряду с глобальным наличие большого числа локальных экстремумов. Кроме того, локальные экстремумы появляются и при введении ограничений на пространство поиска.

Для решения одноэкстремальных задач оптимизации существует достаточное число градиентных и численных алгоритмов. Одним из таких алгоритмов является метод деформируемого многогранника Нелдера-Мида [1]. При оптимизации одноконтурной АСР с ПИ-регулятором такой алгоритм устойчиво находит оптимальные значения настроечных параметров и для функции цели вида

(1.1)

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

Применение метода деформируемого многогранника для оптимизации двухконтурной АСР с дифференциатором и АСР с нейроконтроллерами различ­ной структуры приводит к неоднозначности решения. В каждом случае результаты зависят от выбранных на­чальных координат. Из этого следует вывод о многоэкстремальности подобных задач, и для их решения требу­ются методы глобальной оптимизации [2].

В настоящее время наиболее предпочтительными методами многоэкстремаль­ной оптимизации являются генетические алгоритмы (ГА), реализующие постулаты теории эволюции и опыта селекции растений и животных [3]. Стратегия поиска оптимального решения в генетических алгоритмах опирается на гипотезу селекции: чем выше приспособленность особи, тем выше вероятность того, что у потомков, полученных с её участием, признаки, определяющие приспособленность, будут выражены ещё сильнее [4].

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

Следует отметить, что класси­ческий генетический алгоритм находит глобальный экстремум в вероятностном смысле. И эта вероятность за­висит от числа особей в популяции. Как показали исследования, при оптимизации сложных многоконтурных и многосвязных систем регулирования и аналогичных систем с ней­роконтроллерами генетические алгоритмы (в частности диплоидная версия ГА) с доста­точно высокой вероят­ностью находят глобальный экстремум. Однако вычисление функции цели вида (1) на интервале времени пере­ходного процесса требует значительных вычислительных ресурсов, что существенно сказывается на общем времени работы ГА.

Особенностью ГА является то, что ни один из генетических операторов (кроссовер, му­тация, инверсия) в процессе генерирования потомков не опирается на знание локального рельефа поверхности отклика функции цели. Формирование потомков генетическими операторами происходит случайным образом и поэтому нет гарантии, что найденные реше­ния будут лучше родительских. Следовательно в процессе эволюции встречается доста­точно большое число “неудачных” потомков, которые увеличивают число обращений к функции цели и увели­чивают, тем самым, время поиска глобального экстремума.

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

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

В данной статье приводится пользовательская программа для Mathcad, а также результаты тестиро­вания и примеры использования в задачах управле­ния авторской версии модифицированного генетического алгоритма (МГА).

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

 

 

Краткое описание МГА и программа в среде Mathcad

Предлагаемый алгоритм содержит в себе гене­тиче­ские качества статистической селекции популя­ции поисковых точек. Для исключения “не­удачных” потомков в МГА реализована проце­дура регулярного поиска локальных экс­трему­мов с использованием операций дефор­мируе­мого многогранника. При смене поколе­ний в алгоритме заложена рекомендуемая во многих источниках 10-процентная замена неперспективных особей (элимини­рование).

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

 

 

3. Описание методики и результаты тестиро­вания МГА

 

Известной особенностью генетиче­ских алгоритмов является вероятностный ха­рактер определения глобального экстремума. Степень совершенства алгоритмов зависит как от запро­граммированного меха­низма гене­тической обработки информации (заложенные в программе генетические опе­рации и стратегия их работы, заданное число элиминированных особей), так и от пользовательских установок начальных усло­вий и объема используемой при поиске ин­формации (заданное число особей в популя­ции m и область поиска D).

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

Для предлагаемого алгоритма выполнено тестирование влияния заданных значений m и D на вероятность определения глобального экстремума r и числа обращений к функции цели S. Для сравнения параллельно с МГА проведено тестирование диплоидной версии ГА [5].

Тестирование проведено для трех двухмерных функций цели. На рис. 2а, б, в для этих функций показаны изометрические изображения и сечения по опти­мальной координате x₂. Первая функция предложена авторами статьи, вторая и третья взяты из ис­точника [6]. Аналитические выражения функций имеют вид

; (3.1)

; (3.2)

. (3.3)

Для определения оценки r для заданных значений D и m было выполнено по 10000 решений МГА и ГА. Затем из каждых 10000 результатов отбирались правильные решения и вычислялся процент их появления. Найденная таким образом величина принималась за оценку вероятности появления пра­вильного решения r.

Такая процедура проделывалась для трех диапазонов поиска. Диапазоны поиска выбирались индивиду­ально для каждой функции цели. Полученные данные обрабатывались с помощью встроенных функций Mathcad interp и regress.

На рис. 3 показаны графики зависимостей вероятности определения глобального экстремума от числа особей в популяции для функции (3.1).

Критерием правильности решения задачи принята 97-процентная вероятность появления правильных решений. Из графиков (рис. 3) выбраны числа особей в популяциях m₉₇, которые гарантируют такую вероят­ность. Затем для всех шести значений m₉₇ выполнено по 10000 решений задачи оптимизации. В процессе решений подсчитывались числа обращений к функции цели S. Значения S являются дискретными слу­чайными числами. Для шести ансамблей из 10000 значений S рассчитаны функции плотности распределения. Расчеты выполнялись с помощью встроенной функции Mathcad hist.

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

На рис. 4 показаны шесть графиков функций распределения вероятности дискретной случайной вели­чины S (число обращений к функции цели) для протестированной функции (3.1).

В табл. 1 сведены результаты тестирования трех функций цели (3.1), (3.2) и (3.3) двумя анализируемыми алгоритмами. Из табл. 1 видно, что МГА почти в два раза меньше обращается к функции цели по сравнению с диплоидной версией ГА. Кроме того, в процессе регулярного поиска МГА способен найти глобальный экстремум за пределами заданного диапазона.

Для иллюстрации работы МГА на рис. 5 показаны четыре поверхности отклика функции (3.1), на которых показано множество особей (координатных точек) в процессе эволюции поколений. Звездочкой отмечена точка глобального экстремума. На рис. 5 а показан начальный разброс точек в первом поколении. В популяции тридцать особей. В каждом поколении удалялись по три наихудших особи. На замену им находились точки в локальных экстремумах. Расположение точек популяции в десятом и в пятнадцатом поколении представлены соответственно на рис. 5 б и 5 в. Состояние решенной задачи, когда все точки стянулись в одну точку глобального экстремума, представлено на рис 5 г. Для получения окончательного решения потребовалось семнадцать поколений.

Таблица 1

Функция	Диапазон поиска	Число особей в популяции, гарантирующее определе­ние глобального экстре­мума с вероятностью 97%	Ордината пика кривой распределения вероятности числа обращений к функции цели, %	Абсцисса пика кривой распределения вероятности числа обращений к функции цели (мода случайной величины S)
МГА	ГА	МГА	ГА	МГА	ГА
	0 ¸ +10			29,89	13,5
+3 ¸ +7			28,07	8,89
+15 ¸ +25			24,54	6,11
	-10 ¸ +10			24,95	11,68
-20 ¸ +20			13,56	7,93
-40 ¸ +40			12,55	5,34
	-3 ¸ +3			23,25	7,59
-6 ¸ +6			14,63	3,00
-12 ¸ +12			11,25	3,09
Суммарное для девяти тестов число обращений к функции цели

 

Рис. 3. Зависимость вероятности определения глобального экстремума от числа особей в популяции

для функ­ции цели (3.1)

 

---

Дата добавления: 2016-01-05; просмотров: 21; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!