Материал: 2488

3. МНОГОКРИТЕРИАЛЬНАЯ ОПТИМИЗАЦИЯ

3.1. Краткий обзор методов многокритериальной оптимизации

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

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

Задача оптимизации с ограничениями есть задача уменьшения скалярной функции 0 p некоторого p вектора в области U, подчиненного n условиям. Тогда задача оптимизации с ограничениями мо-

жет быть выражена как min 0 p при i p i;i 1,...,n.

p U

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

Условная многокритериальная оптимизация. Многие задачи характеризуются несколькими несоизмеримыми и часто конкурирующими критериями рабочих характеристик или целей. Задача многокритериальной оптимизации является задачей одновременного уменьшения n целей k p ,k 1,...,n переменного вектора p в области

U, то есть min 1 p ,..., n p . Задача не имеет оптимального реше-

p U

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

132

многокритериальной оптимизации: априорная артикуляция предпочтений; апостериорная артикуляция предпочтений; последовательная артикуляция предпочтений.

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

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

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

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

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

ограничений неравенств min i p : k p k ;k 1,...,n; k i. Пробле-

p U

133

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

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

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

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

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

MOGA. Генетические алгоритмы (GAs) являются процедурами поиска, основанными на эволюционных процессах. Идея в том, что GAs оперирует с множеством индивидуумов, представляющих потенциальное решение задачи, и применяет правило выживания пригодных индивидуумов так, чтобы индивидуумы развились к лучшему решению задачи. Индивидуумам дают представление в форме хромосом, которое соответствует генотипу индивидуума в природе. Могут быть выполнены три операции: selection, crossover and mutation. По-

134

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

венств. Индивидуум j с множеством целевых функций j 1j,..., nj не доминирует, если для множества индивидуумов N нет никаких других индивидуумов k 1,...,N, k j, таких, что a) i: ik ij;

б) ik ij; i 1,...,n. Индивидуумы ранжированы на основе количества других индивидуумов, над которыми они доминируют. Каждый индивидуум тогда назначается согласно его рангу. Задачи, которые решаются MOGA, могут быть сформулированы так: найти множество

objective optimization problem) может быть представлена как програм-

ма векторной математической оптимизации

x 1 x ,..., k x ; x ;

x gi x 0, i 1, ...,m1; hj x 0, j 1, ...,m2; x x1...xn T ,

где x – вектор решений; fl x – нелинейные целевые функции; gi x ,hj x – нелинейные функции ограничения неравенства и равенства соответственно.

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

135