Материал: 2488

3.1.1. Определения

Общая многокритериальная задача оптимизации может быть представлена в виде min x 1 x ... k x Τ ; gj x 0 j 1... m; hi x 0 i 1... , где k – номер целевой функции; m – номер ограни-

x | x X .

Многокритериальная оптимизация возникла из трех областей знаний: теории экономического равновесия и благосостояния, теорий игр и математики.

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

Функция полезности. Функция полезности представляет степень человека или группы удовлетворенности человека (ЛПР). При многокритериальной оптимизации индивидуальная функция полезности определена для каждой цели. Функция полезности U – математическое выражение, которое является обобщением индивидуальных функций полезности с учетом предпочтений ЛПР.

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

Методы скаляризации и векторные методы оптимизации.

Для заданного вектора целевых функций наиболее просто объединить

136

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

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

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

Если два решения x1, x2 полностью сравнимы, то:

– доминирование: x1 x2 , если и только если f x1 f x2 ;

– индифферентность:или x1 x2 , если и только если f x1 f x2 .

В случае MOOP не все решения полностью сравнимы:

доминирование: x1 x2 , если и только если F x1 F x2 и по крайней мере для одной цели F x1 F x2 ;

доминирование: x1 x2 , если и только если F x1 F x2 и по крайней мере для одной цели F x1 F x2 ;

слабое доминирование: x1 x2 ,еслиитолько если F x1 F x2 ;

слабое доминирование: x1 x2 ,еслиитолько если F x1 F x2 ;

индифферентность: x1 x2 , если и только если F x1 F x2 ;

недоминирование: x1 x2 , если и только если F x1 F x2 .

xt называют эффективным (недоминирующим, Парето-опти-

мальным) решением MOOP, если не существует x (x xt ):

137

F x F xt ;F x F xt . xt называют слабо эффективным решением

MOOP, если не существует x (x xt ): F x F xt .

Гольдберг предложил метод ранжирования популяции, использующий доминирование Парето. Если подпопуляция недоминирующее множество, то подпопуляции задается ранг 1 и подпопуляция временно удаляется из популяции; далее находится подпопуляция недоминирующее множество оставшейся популяции, которой дается ранг 2, и временно удаляется. Процесс продолжается, пока вся популяция не будет ранжирована. Таким образом, популяция сортируется в «частичный порядок» групп подмножеств, которые взаимно неразличимы по Парето.

Фонцеза и Флеминг предложили метод MOGA, в котором каждой точке назначается ранг – количество точек, над которыми она доминирует, плюс один. Недоминирующим точкам назначается ранг 1.

Зицлер, Тиле предложили схему ранжирования, в которой опре-

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

ляции; SPEA (Strength Pareto Evolutionary Algorithm) использует уста-

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

Для поддержания размера популяции применяется кластерный метод. Алгоритм кластерного метода следующий: 1) помещают каждый элемент элитной популяции в его собственный кластер; 2) если

138

количество кластеров меньше чем или равно максимальному размеру элитного популяции, то переход в 5); 3) вычисляют дистанции между каждой парой кластеров; дистанция между кластерами c1,c2:

дуумами i, j в пространстве целей; 4) два кластера с минимальной дистанцией между ними объединяются и переход в 2); 5) для каждого кластера определяются индивидуумы, ближайшие к центру кластера, и другие индивидуумы этого кластера удаляются из популяции.

Классификация методов. Лучшее компромиссное решение должно быть решением, которое может лучше всего удовлетворить требованиям ЛПР. Если требования ЛПР могут моделироваться функцией полезности, агрегирующей все целевые функции в один критерий u F x u f1 x ...fk x , то лучшее компромиссное решение может быть определено как решение, максимизирующее функцию полезности u F x ; x . Если функция полезности может быть создана, то MOOP редуцируется до одноцелевой задачи. Однако во многих ситуациях затруднительно создать такую функцию полезности; при этом должны использоваться другие методы, которые используют локальную информацию предпочтения.

Методы, основанные на способах извлечения информации предпочтения ЛПР, могут быть разделены на три класса: 1) эффективные методы формирования решений с предпочтениями, обеспеченными после оптимизации (a posteriori method); при этом формируется множество желаемых эффективных решений; значения этих решений и целевых функций представляются ЛПР, который выберет лучшие компромиссные решения на основе его предпочтений; 2) методы формирования лучших компромиссных решений, основанные на априорных предпочтениях; ЛПР должен предоставить глобальную привилегированную информацию a priori; 3) интерактивные методы с предпочтениями, извлеченными последовательно в процессе анализа решения.

Метод взвешенной суммы. Если функциональное пространство f задачи MOOP – выпуклое, то в методе взвешенной суммы зада-

k

ча переформулируется в форме min F x l fl x ; x . Если про-

l 1

странство целей первоначальной задачи невыпукло, то метод взве-

139

шенной суммы, возможно, не способен к формированию эффективных решений.

Методы p-нормы. В этой секции рассматривается семейство многообъектных методов оптимизации, которые основаны на p-норме для нахождения лучших компромиссных решений. Большинство этих методов требует глобальную привилегированную информацию. Некоторые из них могут использовать интерактивно. Рассмотрено четыре метода: метод минимакса, метод целевого достижения, метод целевого программирования, метод точки предпочтения.

Метод минимакса (идеальной точки). В MOOP можно оптими-

зировать каждую из целей: min fl(x), l 1, ...,k ;x .

Предположим, что оптимальное решение вышеупомянутой задачи xl . Тогда, оптимальное значение целевой функции fl* fl xl . Определите идеальную точку в пространстве целевых функций как F* [ f1*...fk*]. В общем случае идеальная точка не достижима, иначе цели не были бы в конфликте друг с другом.

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

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

d dp d1,1 p .

Для p 1 задача становится негладкой задачей оптимизации:

k

min dp j fj x fj* ; x .

j 1

140