Green-sell.info

Новые технологии
2 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Однокритериальная и многокритериальная оптимизация

Однокритериальная и многокритериальная

Оптимизация

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

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

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

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

Таким образом, задано m функций или функционалов fi, отображающих множество D – допустимых решений n-мерных векторов x =1, … , хn) во множество вещественных чисел R. Предполагается, что выбор оптимальных значений x производится не во всем n-мерном пространстве R n , а лишь в пределах некоторого его подмножества D. Например, можно интерпретировать задачу (6.1) как задачу оптимального выбора параметров х1, … , хn некоторой системы, качество функционирования которой оценивается показателями f1, … , fm. В этом случае ограничение x ÎD отражает технологические и иные возможности реализации тех или иных значений хi. Кроме того, часть ограничений может формироваться на основе имеющейся априорной информации, позволяющей исключить из рассмотрения заведомо неудачные варианты x.

Важнейшее значение при исследовании задач (6.1) имеет принцип Парето и связанные с ним понятия эффективного (Парето-оптимального) и слабо эффективного решения. Для сведения задачи многокритериальной оптимизации (6.1) к некоторой ее однокритериальной версии можно использовать следующие традиционные «инженерные» методы [13].

Метод главного критерия

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

Таким образом, вместо задачи (6.1) решается другая, уже однокритериальная задача следующего вида:

В результате получили более простую задачу поиска максимума функционала f1 на новом допустимом множестве D′ при ограничениях вида fi(x) ≥ ti, показывающих, что согласны не добиваться максимальных значений для функционалов f2, … , fm, сохраняя требование их ограниченности снизу на приемлемых уровнях. Однако, переход от задачи (6.1) к задаче (6.2) не есть переход от одной эквивалентной задачи к другой. Произошло существенное изменение исходной постановки задачи, которое в каждой конкретной ситуации требует отдельного обоснования. Применение этого метода на интуитивном уровне обычно наталкивается на трудности, связанные с возможным наличием нескольких «главных» критериев, находящихся в противоречии друг с другом. Кроме того, не всегда ясен алгоритм выбора нижних границ ti. Их необоснованное задание может привести, в частности, к пустому множеству D′.

Метод линейной свертки

Это наиболее часто применяемый метод «скаляризации» (свертки) задачи (6.1), позволяющий заменить векторный критерий оптимальности f = (f1, … , fm) на скалярный J׃ D → R. Он основан на линейном объединении всех частных целевых функционалов f1, … , fm в один:

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

Метод максиминной свертки

Этот метод обычно применяется в форме:

В отличие от метода линейной свертки на целевой функционал J(x)оказывает влияние только тот частный критерий оптимальности, которому в данной точке x соответствует наименьшее значение соответствующей функции fi(x). И если в случае (6.3) возможны «плохие» значения некоторых fi за счет достаточно «хороших» значений остальных целевых функционалов, то в случае максиминного критерия производится расчет «на наихудший случай» и по значению J(x)можно определить гарантированную нижнюю оценку для всех функционаловfi(x). Этот факт расценивается как преимущество максиминного критерия перед методом линейной свертки.

При необходимости нормировки отдельных частных целевых функционалов, т. е. приведения во взаимное соответствие масштабов измерения значений отдельных fi(x), используется «взвешенная» формула максиминного критерия:

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

Критерии оптимизации ТПШИ

Критериями оптимизации технологических процессов наиболее целесообразно выбирать такие характеристики ТП, как время изготовления изделия (Т),технологическую себестоимость (С) и капитальные затраты (К). С целью создания эффективного метода оптимизации технологических процессов было введено понятие упрощенных характеристик ТП. Упрощенные характеристики технологических процессов аналитически связаны с его внутренними характеристиками и линейно переходят с элементов низших уровней структуры ТП на элементы более высоких уровней. Элементами низшего уровня (базовыми элементами) ТПШИ являются технологические операции.

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

ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

Классификация методов оптимизации

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

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

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

Если необходимо установить экстремум целевой функции при некоторых условиях, которые накладываются на ряд других величин (например, определение максимальной производительности при заданной себестоимости, определение оптимальной температуры при ограничениях по термостойкости катализатора и др.), то такая оптимизация называется условной [2].

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

Ограничения могут накладываться как по технологическим, так и по экономическим соображениям.

В зависимости от управляющих параметров различают следующие задачи:

— оптимизация при одной управляющей переменной — одномерная оптимизация;

— оптимизация при нескольких управляющих переменных — многомерная оптимизация;

— оптимизация при неопределённости данных;

— оптимизация с непрерывными, дискретными и смешанным типом значений управляющих воздействий.

В зависимости от критерия оптимизации различают:

Читать еще:  Многокритериальная оптимизация примеры

— с одним критерием оптимизации — критерий оптимальности единственный;

— со многими критериями. Для решения задач со многими критериями используются специальные методы оптимизации [3].

Однокритериальная оптимизация

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

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

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

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

Для решения задачи минимизации функции f(x) на отрезке [a, b], в большинстве случаев, используют приближенные методы. С их помощь можно найти решения этой задачи с необходимой точностью в результате нахождения конечного числа значений функции f(x) и ее производных в некоторых точках отрезка [a, b]. Методы, использующие только значения функции и не требующие вычисления ее производных, называются прямыми методами минимизации. Достоинством прямых методов является то, что от целевой функции не требуется дифференцируемости и, более того, она может быть не задана в аналитическом виде. Единственное, на чем основаны алгоритмы прямых методов минимизации, это возможность определения значений f(x) в заданных точках [4]. Среди задач математического программирования самыми распространёнными и наиболее хорошо исследованными являются так называемые задачи линейного программирования (линейной оптимизации). Рассмотрим этот тип задач. Для них характерно то, что целевая функция линейно зависит от , а также, что ограничения, накладываемые на независимые переменные, имеют вид линейных равенств или неравенств относительно этих переменных.

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

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

где целевая функция, критерий оптимальности или линейная форма;

x вектор неизвестных;

коэффициенты целевой функции;

величины правых частей ограничений.

Вектор значений неизвестных x = (x1, x2, …, xn), удовлетворяющих условию задачи (1.1) — (1.4) , называется допустимым решением или допустимым планом задачи линейной оптимизации. Совокупность всех допустимых планов называется множеством допустимых планов. Допустимое решение x * = (x1 * , x2 * , …, xn * ) называется оптимальным, если оно обеспечивает максимальное (или, в зависимости от условий задачи, минимальное) значение целевой функции.

Решение задач линейной оптимизации может быть получено без особых затруднений (естественно, при корректной формулировке проблемы). Классическим методом решения задач данного типа является симплекс-метод. В случае лишь двух переменных успешно может использоваться также графический метод решения, обладающий преимуществом наглядности. Очевидно, в случае n > 2 применение графического метода невозможно.

При решении ряда оптимизационных задач требуется, чтобы значения неизвестных x = (x1, x2, …, xn) выражались в целых числах. К задачам подобного типа относятся те, в которых требуется определить необходимые для принятия решений значения физически цельных объектов (машин, агрегатов различного типа, людей, транспортных единиц и т.д. и т.п.).

Такие задачи относятся к задачам целочисленной оптимизации. Математическая модель задачи линейной целочисленной оптимизации также определяется формулами (1.1) — (1.4), но в данном случае налагается дополнительное требование целочисленности всех (или части) неизвестных. Если требование целочисленности распространяется лишь на часть неизвестных величин задачи, то такая задача называется частично целочисленной [5].

Тема 3.5. Многокритериальная оптимизация

Выбор критерия оптимизации. Система ограничений экономико-математической модели. Компромиссные методы векторной оптимизации. Парето – оптимальные решения.

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

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

Обозначим 1-й частный критерий через , где — допустимое решение, а область допустимых решений — через Q. Если учесть, что изменением знака функции всегда можно свести задачу минимизации к задаче максимизации, то кратко задачу многокритериальной оптимизации можно сформулировать следующим образом:

(3.28)

(3.29)

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

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

— упорядочение заданного множества критериев и последовательная оптимизация по каждому из них (этот подход рассмотрен ниже на примере метода последовательных уступок;

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

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

Определение 3.1. Вектор называется эффективным (оптимальным по Парето) решением задачи (3.28), (3.29), если не существует такого вектора , что

Читать еще:  Оптимизатор игр на андроид

(3.30)

причем хотя бы для одного значения i имеет место строгое неравенство.

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

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

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

Рассмотрим один из таких методов решения многокритериальных задач — метод последовательных уступок.

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

Затем, исходя из практических соображений и принятой точности, назначается величина допустимого отклонения 8, > 0 (экономически оправданной уступки) критерия Z, и находится максимальное значение второго критерия Z’2 при условии, что значение первого критерия не должно отклоняться от своего максимального значения более чем на величину допустимой уступки, т.е. решается задача:

Снова назначается величина уступки δ2 > 0 по второму критерию, которая вместе с первой уступкой используется для нахождения условного максимума третьего частого критерия:

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

Пример 3.7. Решение задачи многокритериальной оптимизации методом последовательных уступок.

Решение. Пусть задача трехкритериальной оптимизации имеет вид

(3.31)

(3.32)

(3.33)

(3.34)

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

Для определенности будем считать, что допустимые уступки по первым двум критериям заданы: δ1 = 3; δ3 = 5/3.

Максимизируем функцию Z3 в области допустимых решений, т.е. решаем одну критериальную задачу (3.31), (3.34). Это несложно сделать рассмотренным в главе 2 графическим методом решения задач линейного программирования (рис. 3.3).

Максимум функции Z1 при условиях (3.34) достигается в точке А области Q с координатами (1; 4), так что в данном случае

Переходим к максимизации функции Z, при условиях (3.34) и дополнительном ограничении, позволяющем учесть, что по критерию Z, нельзя уступать более чем на δ1. Так как в нашем примере , то дополнительное ограничение будет иметь вид

(3.35)

Задачу (3.32), (3.34), (3.35) также решаем графически (рис. 3.4).

Получаем, что максимум функции Z2 при условиях (3.34), (3.35) достигается в точке В части Q, области Q, так что

Теперь уступаем по критерию Z2 на величину уступки 52= 5/3 и получаем второе дополнительное ограничение:

(3.36)

Максимизируем функцию Z3 при условиях (3.34), (3.35) и (3.36). Решение этой задачи представлено на рис 3.5.

Таким образом, получаем оптимальное решение рассматриваемой трехкритериальной задачи (точка С на рис. 3.5):

Соответствующие значения частных критериев при этом составляют:

Анализ методов однокритериальной и многокритериальной оптимизации

Понятие оптимизации

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

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

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

Рисунок 1.1 — Процесс оптимизации

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

Целевую функцию можно записать в следующем виде:

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

В случае одного проектного параметра целевая функция является функцией одной переменной и ее графики— некоторая кривая на плоскости.

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

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

Читать еще:  Параметрическая оптимизация это

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

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

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

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

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

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

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

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

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

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

Генетические алгоритмы многокритериальной оптимизации

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

Без потери общности задачу многокритериальной оптимизации можно сформулировать следующим образом:

Здесь пространство поиска решений определяется следующим образом

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

где — вектор значений целевых функций. Другими словами является множеством образов в .

5.1. Концепция доминирования Парето

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

Поэтому при многокритериальной оптимизации выполняется поиск не одной особи, а множество хромосом, оптимальных в смысле Парето [1,2,3]. Обычно пользователь имеет возможность выбирать оптимальное решение из этого множества .

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

для всех при максимизации функции и

для всех при минимизации функции .

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

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

Пусть и — родители и потомки текущей популяции . Тогда общая структура многокритериального ГА может быть представлена следующим образом:

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

Поскольку многокритериальная оптимизация является естественным развитием обычной численной или комбинаторной оптимизации, то многие разработанные методы были распространены на этот более общий случай. При использовании ГА для многокритериальной оптимизации центральным вопросом является построение фитнесс-функции. За последние десятилетия, следуя [2], разработано несколько подходов, которые можно разделить на представленные ниже три поколения:

  • Поколение 1. Векторная оценка (vector evaluated -veGA) [5].
  • Поколение 2. Ранжирование по Парето + Разнообразие:Многокритериальный ГА (multiobjective GA — moGA) [6].
  • Поколение 3. Взвешенная сумма + Элитизм:Случайный взвешенный ГА (rwGA) [7]; Адаптивный взвешенный ГА (awGA)[8]; Недоминируемый ГА на основе сортировки (nsGA) [9]; Интерактивный ГА с адаптивными весами (i-awGA) [10].

Далее мы рассмотрим эти методы более подробно.

Ссылка на основную публикацию
Adblock
detector