Лекции по дисциплине Оптимальное управление многоуровневыми ММС. Глава 3 (2016) (Лекции по дисциплине "Оптимальное управление многоуровневыми ММС". Главы 1-3 (2016)), страница 2

Их можноклассифицировать следующим образом:1) метод получения эволюционных стратегий — метод параметрического поискаквазиоптимального решения в действительном пространстве исходных параметров;2) генетический алгоритм — это эволюционный метод параметрического поискаквазиоптимального решения в кодовом пространстве искомых параметров;3) генетическое программирование — эволюционный метод структурного поискаквазиоптимального решения в пространстве символьных компьютерных программ.Генетические алгоритмы отличаются от других оптимизационных и поисковых процедурследующими свойствами:работают не с параметрами задачи, а с закодированным множеством параметров;осуществляют поиск не путем улучшения одного решения, а путем использования сразунескольких альтернатив на заданном множестве решений;используют целевую функцию-показатель или множество целевых функций-показателей, а неразличные приращения показателей для оценки качества решений;применяют не детерминированные, а вероятностные правила анализа оптимизационных задач.Механизмы селекции и генетики в ГА формируются на основе эволюционных операторов наисходном пространстве параметров [13]:селекция (пропорциональная, турнирная, элитная, вытеснением);выбор родительской пары: панмиксия (родительская пара образуется случайно);5 селективный; инбридинг (родительская пара, состоящая в родстве); аутбридинг (родительская пара из лучших особей).кроссинговер (скрещивание) (одно/двухточечный, равномерный);мутация (точечная, абсолютная).Типичный вариант ГА МКО состоит из следующих этапов:Этап 1.

Формирование первого ( j  1 ) поколения ( 1  j  N ) популяции альтернативныхрешенийQ j  q1j ,, qij ,, qmj ,(3.17)где m — размерность популяции из хромосом-особейqij  q1ji , q2ji ,, q pij ,(3.18)которая, в свою очередь, состоит из вектора генов размерностью p.Этап 2. Выбор n родительских пар из хромосом в соответствии с вероятностьюP qij  . Ô q Ô qijm(3.19)jii 1Замечание 3.2. Показатель Ô представляет собой свертку нормированного векторапоказателей задачи МКО вектором скаляризующих коэффициентов α   1 , ,  k , , l lÔ    k J kí , 0   k  1,k 1l  k  1,k 10  J kí  1,(3.20)см. ниже метод скаляризации задачи МКО (2.1).

Без ограничения общности результатовпредполагается, что имеют место критерии эффективности:J kí  max; Ô  max, k  1, l.q(3.21)qПри фиксированных значениях вектора а получаем решение на области Парето. При изменениивеличин  k в соответствии с (3.20) получаем область Парето-оптимальных решений.Критерий (3.19) в ГА носит название функции полезности, приспособленности илипригодности (fitness). Функция пригодности используется в ГА для сравнения альтернативныхрешений (хромосом) между собой и выбора лучших из них.Очевидно, что отбор n родительских пар из nmax производится по наибольшим величинамвероятностей (3.20).Замечание 3.3.

Максимальное число родительских пар nmax из числа m альтернативныхрешений вычисляется как сочетание по два из mC  ,2mнапример, при m  3 (4) соответственноnmax  3 (6).Этап 3. Кроссинговер (скрещивание) на основе отобранных пар qikj , qikj , где k1 , k2 — пара12решений (хромосом).j 1qciaqikj a , åñëè maska  0;ci  ik1  ik2  1, n, 1qikj a , åñëè maska  1; 2(3.22)где a  1, p — номер параметра (гена) варианта решения (скрещенной хромосомы q cij 1 нового (j  1 )-го поколения популяции Q j1 ), maska — случайная величина (0 или 1).Этап 4.

Мутацияj 1qmiaqckj 1a , åñëè maska  0; 1mi  ci  1, n,j 1 w, åñëè maska  1;qcia(3.23)6где w — случайная величина, распределенная по нормальному закону (математическое ожиданиеравно нулю, среднеквадратическое отклонение равно  ).Этап 5. Селекция5.1. Формирование репродукционного множестваj 1qrj 1  qmi, q sj , r  1, n  1.(3.24)В (3.24) применена элитная селекция: потомок дополнен одним лучшим предком.5.2. Отбор с заданным уровнем функции пригодности m хромосом-особейqij 1  q rj 1 , r  i  1, m.(3.25)Этап 6.

Адаптация. Каждые g поколений изменяется  в зависимости от частоты fулучшения критерия качества Ô sj варианта решения q sj  , åñëè f  f p ;(3.26)  1.  , åñëè f  f p ;Этап 7. Окончание ГА в соответствии с одним из условий:7.1. Достижение заданного числа поколений N : j  N .7.2.

Незначительное улучшение критерия Ô sj1  Ô sj  .Этап 8. Получение оптимального решения q  q sj1.Замечание 3.4. Замена скаляризации (3.20), (3.21) на процедуры методов конусовдоминирования дает версию ГА МКО, которая была разработана В.А. Серовым [2].Далее в подразделе 3.2.5 приводится краткий справочный комментарий методов МКО наоснове скаляризации (2.1), (2.2), (2.3) и компромиссов (3.1), (3.2), (3.3).3.2.3. Метод многокритериальной оптимизациина основе скаляризации в форме линейнойсвертки показателей (2.1)Линейные свертки показателей задач управления (регулирования) и принятия решений имеютвидlli 11Ô   i J ií ; P    Eí ,(3.27)где  i ,   — весовые коэффициенты, имеющие смысл важности показателей, удовлетворяютограничениямll 1  i  1     1 ,0  i  1 0    1 ;i 1(3.28)а J ií , Eí — нормированные показатели:J ií E  E minJ i  J i min.; Eí E max  E minJ i max  J i min(3.29)Величины J i min ( E min ), J i max ( E max ) — наименьшие и наибольшие значения показателей,могут быть в приближенном варианте получены на основе глобального (сетевого) анализа припараметризации управлений (решений).Очевидно, что значения нормированных величин показателей удовлетворяют неравенствам0  J ií  1 0  Eí  1 , i  1, l   1, l .(3.30)Нормирование показателей необходимо выполнять, чтобы обеспечить в показателях свертки(13.27) одинаковый диапазон (3.30) их изменения, иначе исходные ненормированные показатели сразными физическими диапазонами приведут к деформации процесса оптимизации в пользу тех, укоторых диапазон изменений больше.7Ограничивая, без изменения общности анализа, показатели J i критериями Ji  opt одногосмысла (например, J i  max, i  1, l , l  2 ), нетрудно сделать вывод, что свертка (3.27) есть не чтоиное, как развернутый конус доминирования с одинаковыми строками матрицы B (рис.

3.6)12   2   J1   1 J1   2 J 2 B   11; B 1     0. 21  22 1  2   J 2   1 J1   2 J 2 (3.31)Рис. 3.16. Точка максимума показателя Ô на фронте Паретопри заданных 1 и  2Из рис. 3.6 следует, что, перебирая величины i , i  1, 2 из диапазонов (3.28), можно получитьвсю область значений J Ï  U  , так как развернутый конус доминирования пройдет все угловыезначения от горизонтального положения до вертикального.Положительным свойством данного метода является переход к скалярной оптимизации наоснове вариационного подхода, принципа максимума, динамического программирования ичисленных методов.Недостатками данного метода являютсямногократное решение задачи скаляризованной оптимизации для получения области Паретоисходной задачи МКО;неопределенность выбора весовых коэффициентов для получения желаемых свойствпоказателей;уход от интерактивного анализа значений вектора показателей в процессе итераций.3.2.4.

Метод лексикографической оптимизации(метод последовательных уступок) (2.2)В данном методе заложен последовательный процесс оптимизации, например, вектора наоснове ранжирования показателей по важности (значимости). Процедура экспертногоранжирования показателей по значимости рассмотрена ниже в методе сравнения альтернатив наоснове анализа иерархий (4.2).В результате ранжирования имеет место соотношениеJ1 J 2Jl ,(3.32)где знак « » означает, что показатель слева важнее (предпочтительнее) показателя справа.

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

Решение скалярной задачи с наиболее значимым показателемmax J1  J1max ;(3.33)x  f  x, u  , u  U, x  X, x  t0   x 0 , x  tk   x k .(3.34)uДалее формируется уступка J1max  J1 ,J1max  J1  J1max  J1.(3.35)Шаг 2. Решение задачи по второму по значимости показателю8max J 2  J 2*uпри условии (3.35) и всех условиях (3.34).Далее формируется уступка J 2*  J 2 ,J 2*  J 2  J 2*  J 2 .(3.36)Шаг 3. Решение задачи по третьему по значимости критериюmax J 3  J 3*uпри выполнении уступок (3.35), (3.36) и условий (3.34) и т.

д.Данный алгоритм иллюстрируется на рис. 3.7 при l  2.Рис. 3.7. Получение подфронта Парето J ÌÓUметодом уступокИз рис. 3.7 следует, что при решении задачи на шаге 1 получено значение J1max исформирована уступка. Далее задача на шаге 2 с учетом равенства J1  J1max  J1 дает значениеJ 2*  max J 2 . Очевидно, что при условии неравенства (3.35) будут получены все точки подобластиuJÌ Ó U   J Ï  U   J  Un  .Положительным свойством данного метода является получение подобласти Парето вокрестности наиболее значительного показателя.Недостатком данного метода является решение с шага 2 скалярных задач с дополнительнымиограничениями в форме неравенств, что, как известно, вызывает сложности при оптимизации, азамена ограничений в форме неравенств приводит к необходимости многократного решениязадачи с необходимостью интерполяции сетевой оценки подобласти J Ì Ó  U  .3.2.5.

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