Вектор оптимальный по парето

Общие сведения о генетических алгоритмах.

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

Простой ГА случайным образом генерирует начальную популяцию структур. Работа ГА представляет собой итерационный процесс, который продолжается до тех пор, пока не выполнятся заданное число поколений или какой-либо иной критерий остановки. На каждом поколении ГА реализуется отбор пропорционально приспособленности, одноточечный кроссовер и мутация. Сначала, пропорциональный отбор назначает каждой структуре вероятность Ps(i) равную отношению ее приспособленности к суммарной приспособленности популяции. Затем происходит отбор (с замещением) всех n особей для дальнейшей генетической обработки, согласно величине Ps(i). Простейший пропорциональный отбор – рулетка – отбирает особей с помощью n «запусков» рулетки. Колесо рулетки содержит по одному сектору для каждого члена популяции. Размер i-ого сектора пропорционален соответствующей величине Ps(i). При таком отборе члены популяции с более высокой приспособленностью с большей вероятность будут чаще выбираться, чем особи с низкой приспособленностью.

После отбора, n выбранных особей подвергаются кроссоверу (иногда называемому рекомбинацией) с заданной вероятностью Pc. – n строк случайным образом разбиваются на n/2 пары. Для каждой пары с вероятностью Pc может применяться кроссовер. Соответственно с вероятностью 1-Pc кроссовер не происходит и неизмененные особи переходят на стадию мутации. Если кроссовер происходит, полученные потомки заменяют собой родителей и переходят к мутации.

Одноточечный кроссовер работает следующим образом. Сначала, случайным образом выбирается одна из l-1 точек разрыва. (Точка разрыва – участок между соседними битами в строке.) Обе родительские структуры разрываются на два сегмента по этой точке. Затем, соответствующие сегменты различных родителей склеиваются и получаются два генотипа потомков.

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

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

Обобщенная блок-схема генетического алгоритма.

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

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

Первая проблема связана с выбором принципа оптимальности, который строго определяет свойства оптимального решения и отвечает на вопрос, в каком смысле оптимальное решение превосходит все остальные допустимые решения. В отличие от задач однокритериальной оптимизации, у которых только один принцип оптимальности f(xо)>=f(x), в данном случае имеется большое количество различных принципов, и каждый принцип может приводить к выбору различных оптимальных решений. Это объясняется тем, что приходится сравнивать векторы эффективности на основе некоторой схемы компромисса.

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

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

Третья проблема связана с учетом приоритета (или различной степени важности) локальных критериев. Хотя при выборе решения и следует добиваться наивысшего качества по всем критериям, однако степень совершенства по каждому из них, как правило, имеет различную значимость. Поэтому обычно для учета приоритета вводится вектор распределения важности критериев L=(l1, l2. ln), с помощью которого корректируется принцип оптимальности или проводится дифференциация масштабов измерения критериев.

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

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

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

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

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

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

Введение.
1. Анализ существующих методов и моделей многокритериальной оптимизации.
2. Разработка математической модели выбранного технологического объекта.
3. Разработка метода многокритериальной оптимизации для выбранного объекта.
4. Разработка программного обеспечения ля выбранного объекта.
5. Проведение экспериментов по многокритериальной оптимизации и анализ полученных результатов.
6. Обобщение результатов исследований и разработка рекомендаций по их использованию.
Заключение.

Видео:Выделение множества, оптимального по Парето. Графики (1)Скачать

Парето-оптимальные (эффективные) векторные оценки и варианты, их свойства

Отношение (9.1) остается и при т > 2 отношением строгого частичного порядка [1] , т.е. обладает свойствами антирефлексивности (у > у — не выполнено), антисимметричности ((у > у*) А (у* >у)=* (у = У*)) и транзитивности ((у > у*) А А (у* > у**) => (у > у**)).

В отличие от Л [1] , в пространстве Л»‘ существуют пары векторных критериев у, у*, как удовлетворяющие отношениям у > у* или у* > у, так и не удовлетворяющие ни одному из этих отношений. Таким образом, критериальное пространство Л™ — частично упорядоченная группа [3] .

Проиллюстрируем смысл критериального пространства как частично упорядоченной группы геометрически для случая т = 2, т.е. для двух критериев /,(х) и/₂(х). При т = 3, т.е. в критериальном пространстве Л [4] , геометрическая интерпретация становится менее наглядной. Приведем два примера, отвечающие двум часто встречающимся (и в теории, и на практике) вариантам множества альтернатив X: дискретному случаю и области возможных вариантов.

Пример: дискретное множество альтернатив. Если множество решений X с Л [3] дискретно [4] , т.е. все его точки изолированы [7] , то оно может быть либо конечным (X = <х_р х₂,х_п>), либо счетным множеством (X = <х,, х₂. х_п. >). На практике ситуация конечного множества может возникнуть, если имеется несколько (например, п = 10) вариантов приобретаемого товара, представленных проектов и т.н. Критериями г/, и у₀ в этом случае могут быть, в частности, цена и качество (товара, проекта).

Каждой альтернативе х_к с номером к сопоставим точку У_к плоскости 9? 2 с координатами г/, = /_<(х_к) и у₂ = /₂(х_к). Тогда графическое представление при п = 10 множества возможных оценок У = <у_х, у₂. г/₁₀> в критериальном пространстве 9? 2 представляет собой набор изолированных точек <У_р У₂. У₁₀> (рис. 9.1). Отметим, что согласно введенному вначале предположению критерий, отвечающий цене (скажем, у_х), подвергнут преобразованию М — /_<(х) так, что минимальной цене соответствует максимальное значение г/,. В данной ситуации отношение строгого порядка, введенное формулами (9.1), можно интерпретировать в терминах предпочтений ЛГ1Р следующим образом. Если две оценки у_х и у_к удовлетворяют отношению у. > у_к, то точка У- лежит правее и выше точки У_к, и тогда ЛПР может исключить вариант у_к как явно менее предпочтительный по сравнению с у..

Рис. 9.1. Дискретное множество возможных оценок У в двумерном критериальном пространстве 9? 2 и образ соответствующего множества Парето — Эджворта

Из рис. 9.1 очевидно, что, хотя множество возможных оценок У и не является линейно упорядоченным множеством, т.е. все 10 альтернатив нельзя выстроить в определенном порядке, но частичная упорядоченность группы позволяет выделить из множества Уточки У_1? У₂, У^ и У₈, расположенные на рис. 9.1 правее и выше всех остальных вариантов. Иными словами, при выборе наилучшего решения ЛПР может убрать из рассмотрения все остальные альтернативы и выбирать только из четырех: х,, х₂, х₄ и х₈. Между собой эти варианты несравнимы согласно формуле (9.1). Величины критериев у_] и у₂ достигают максимума в различных точках: критерий г/, достигает максимума в точке У₈, тогда как величинау₂ — в точке У_х, т.е. одновременный максимум на множестве X не реализуется. Промежуточные варианты У₂ и У₄ представляют собой компромиссные решения, которые вполне могут соответствовать предпочтениям ЛПР.

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

Следующий пример более сложного множества альтернатив X естественно было бы назвать непрерывным множеством (так как непрерывность — общепринятое противопоставление дискретности [8] ), но формально в математике непрерывными считают исключительно линейно упорядоченные множества [9] . Как мы убедились, линейная упорядоченность уже при т = 2 отсутствует. Поэтому назовем множество X областью, представляющей собой с точки зрения топологии связное подмножество топологического пространства. Нередко областью считают только открытое множество, но для теории принятия удобнее рассматривать замкнутую область, т.е. замыкание области, включающее также границу.

Пример: область как множество альтернатив. Если множество решений X связно, то между любыми «соседними» по величинам критериев альтернативами всегда могут быть промежуточные варианты. Тогда X обязано быть несчетным множеством. Подобная ситуация возникает, в частности, при выборе оптимальных значений двух управляющих параметров (финансовых регуляторов, технических показателей и т.п.) некоторой системы при условии, что регулировка этих параметров может осуществляться непрерывно в некоторых пределах. Графическое представление множества возможных оценок У в критериальном пространстве может иметь вид наподобие фигуры У, заштрихованной на рис. 9.2.

Рис. 9.2. Область возможных оценок У в двумерном критериальном

пространстве и образ соответствующего множества Парето — Эджворта

Как и на рис. 9.1, координаты каждой точки на рис. 9.2 (например, координаты точек А, В, С, I), Е, В, С, Я, М) представляют собой величины критериев у_х и у₂ для некоторой альтернативы из множества X. Но здесь, если ЛПР стремится достичь наибольшего значения обоих критериев у_< и у₂, т.е. требуется их максимизация, то частичная упорядоченность группы позволяет ЛПР выделить из множества X альтернативы с образами из отрезков ВС, ОЕ и ВС границы заштрихованной области У, расположенными, как и на рис. 9.1, правее и выше всех остальных вариантов. Иными словами, при выборе наилучшего решения ЛПР может убрать из рассмотрения все остальные альтернативы с векторными оценками из заштрихованной области У и выбирать только точки трех указанных отрезков.

Концы отрезков ВС и ГС остаются в числе представляющих интерес для ЛПР, а концы отрезка ОЕ — нет, так как они доминируемы точками С и Л соответственно.

В данном случае сужение множества альтернатив, само собой разумеющееся при взгляде на рис. 9.2, тем более (по сравнению с рис. 9.1) перестает быть очевидным в случае критериальных пространств более высоких размерностей п или же для более сложных множеств альтернатив X.

Приведенные два примера показывают важность сужения множества возможных оценок У. Если в нервом примере выбор из 4 альтернатив становится значительно проще, чем первоначальный выбор из 10 вариантов, то во втором — не просто уменьшается число альтернатив, но происходит качественное преобразование первоначальной области У с конечной площадью в объединение отрезков кривой линии, имеющих нулевую площадь.

Получаемое в результате сужение множества альтернатив X называется множеством Парето — Эджворта (Френсис Эджворт 1 (Francis Edgeworth, (1845—1926) — английский экономист, родившийся в Ирландии, который впервые, раньше В. Парето, ввел понятие Парето-оптимального решения для двух критериев). Именно с построения этого множества начинается анализ любой задачи теории принятия решений. Практическое применение указанного алгоритма показывает, что нередко, как и в двух приведенных примерах, сужение X и построение множества Парето — Эджворта настолько ограничивает множество оставшихся вариантов, что дальнейший выбор достаточно несложен и не составляет труда для ЛПР.

Множеством Парето — Эджворта, или множеством Парето-оптималъных решений, называется множество Р/(Х) входящих в X альтернатив х*, которые не являются доминируемыми, т.е. для которых не существует доминирующих альтернатив х, удовлетворяющих отношению строгого предпочтения: х > х*.

Из определения вытекает, что для построения множества Парето — Эджворта необходимо исключить из множества решений X все доминируемые альтернативы. Иными словами, надо отбросить все такие альтернативы х*, для которых найдется хотя бы одна доминирующая альтернатива х > х*.

Практическая значимость множества Парето — Эджворта обусловлена тем, что любое решение х из множества альтернатив X, не входящее в РДХ), заведомо не может быть оптимальным.

Действительно, по определению решение х будет доминируемым по отношению к некоторому элементу х* множества Парето — Эджворта, т.е. ЛПР предпочтет х* вместо х.

Парето-оптимальным решениям в критериальном пространстве отвечают Парето-оптимальные векторы (оценки).

Парето-оптимальным вектором (или Парешо-оптималъной векторной оценкой) называется вектор /₂(.г*), /_т(х*)), соответствующий Парсто-опти-

мальному решению х*.

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

Парето-оптимальные варианты благодаря свойствам своих векторных оценок образуют существенно более узкое по сравнению с первоначальным множеством X множество Парето — Эджворта Р^Х). Тем самым окончательный выбор ЛПР наилучшего эффективного решения становится намного легче и проще.

Наряду с множеством недоминируемых альтернатив рассматривается и множество недоминируемых векторных оценок.

Множество Парето-оптимальных векторных оценок, т.е. образ множества Парето — Эджворта РХХ) в критериальном пространстве называют фронтом Парето [10] (иногда Парето-фронтом — от англ. Pareto-frontier) или множеством Парето — Эджворта в критериальном пространстве.

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

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

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

Видео:Граница производственных возможностей. Оптимум по ПаретоСкачать

Критерий оптимальности принятия решений

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

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

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

Видео:Построение множества, оптимального по Парето. ТаблицыСкачать

Парето-оптимальное состояние (оптимум Парето)

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

На рис. 4.2 показано, что в точке А все ресурсы отданы участнику игры X и его полезность максимальна. В точке В максимальная полезность у игрока Y.

Рис. 4.2. Ресурсы (полезность игроков Хи У)

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

Точка С не является оптимальной по Парето. Двигаясь в направлении вправо вверх, можно улучшать полезность и игрока X и игрока Y. При этом с точки зрения игроков точки D и Е не равноценны по полезности (для X предпочтительна точка D; для Y — точка Е).

Видео:Лекция 9. Многокритериальная оптимизация. Парето. Линейная свертка и др.Скачать

Нахождение Парето-оптимальных решений для многокритериальной задачи

Предположим, что требуется выбрать одно оптимальное решение из множества допустимых решений, каждое из которых определяется парой показателей (М^_г о,). Изобразим на координатной плоскости пространство оценок (рис. 4.3) с точками (М^,, о,).

Рис. 4.3. Пространство оценок Ми а: точки 1. 7— соответствуют решениям Х_<. Х₇; крупные точки — Парето-оптимальные решения;

Д — уступка по критерию М

Левая часть рисунка (круглые точки) значения математического ожидания положительно, а о отрицательно, так как этот критерий (а) мы должны минимизировать. Парето-оптимальными оценками является правая верхняя граница и соответственно Парето-оптимальными решениями X_v Х₂, Х₉ и Х₇. Этих решений множество, и окончательный выбор оптимального решения проводится из этого множества. Возможны два подхода: первый подход заключается в том, что строится множество Парето-оптимальных решений и из этого множества ЛПР выбирает единственное решение на основе неформальных дополнительных соображений.

Рассмотрим второй подход на основе сужения множества Парето-оптимальных альтернатив.

• 1. Выбор главного критерия и назначение нижних границ по остальным критериям. Назначим нижнюю границу по критерию М и будем минимизировать критерий а. Если в качестве нижней границы критерия М взять значение М₄ ,то оптимальным будет решение Х₂, так как среди решений удовлетворяющих условию А/. >М₄, она наименее рискованна.
• 2. Лексикографическая оптимизация предполагает упорядочение критериев по важности. Допустим, например, что М — важнейший критерий. Так как максимальное значение по критерию М имеет единственное решение Х₇, то оно и является оптимальным. Здесь наглядно проявляется недостаток метода лексикографической оптимизации: учет одного (важнейшего) критерия. Этот недостаток связан с необходимостью введения жесткого приоритета критериев и может быть снят за счет изменения приоритетов. В этом случае используют метод последовательных уступок, который был рассмотрен выше.

Допустим, что по критерию М возможна уступка А. Тогда результатом выбора на первом шаге будут альтернативы Х₇, Х%, Х₉. Среди них наилучшей по второму критерию будет Х₉. Таким образом, несколько снизив требования по критерию М, мы значительно улучшили оценку по критерию а (т.е. некоторое уменьшение ожидаемого выигрыша привело к существенному снижению риска).

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

где X — некоторая постоянная величина.

Фактически критерий (4.33) представляет аддитивный критерий оптимальности частных критериев (А/, а) с весовыми коэффициентами (1 и -X). При Х>0 оценка случайной величины с помощью аддитивного критерия (4.33) меньше, чем ее среднее значение, что характерно для осторожного человека. Напротив, при X О состоит в том, что увеличение критерия f[M, а) может происходить как за счет увеличения М, так и за счет уменьшения о. Таким образом, для человека, не склонного к риску, критерий (4.33) отражает стремление к увеличению ожидаемого выигрыша и уменьшению риска отклонения от него. При этом показатель X характеризует субъективное отношение принимающего решение к риску. Следовательно, X можно рассматривать как субъективный показатель меры несклонности к риску (показатель осторожности).

В качестве примера разберем случай выбора варианта производимого товара.

Фирма может выпускать продукцию из следующих шести видов: зонтики (3), куртки (К), плащи (П), сумки (С), туфли (Т) и шляпы (Ш). Глава фирмы должен принять решение, какой из этих видов продукции выпускать в течение предстоящего летнего сезона. Прибыль фирмы зависит оттого, каким будет лето — дождливым (Д), жарким (Ж) или умеренным (У), и определяется в табл. 4.23.

🔍 Видео

Закон Парето. Правило Парето. Принцип 80/20Скачать

32 Парето оптимальные распределения определение и пример поискаСкачать

Метод множества ПаретоСкачать

5.1.3. Парето-эффективностьСкачать

33 Дифференциальная характеристика внутреннего Парето оптимумаСкачать

35 Пример поиска Парето оптимальных распределений Кобб ДугласСкачать

Урок 1.Поиск решения, оптимизация, оптимальный план производстваСкачать

Лекция 1. Формирование равновесной цены. Общее равновесие. Эффективность по ПаретоСкачать

Морозов — 14: Метод сужения множества стратегий, оптимальных по ПаретоСкачать

Теория Игр. Вектор Шепли 74Скачать

Диаграмма Парето в Excel 2016Скачать

#3: Генераторы инсайтов - Закон ПаретоСкачать

Множество и принцип Парето 2022 #13Скачать

Excel. Диаграмма Парето.Скачать