русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Многокритериальная оптимизация. Задачи и методы

Многокритериальная оптимизация или программирование ( англ. Multi-objective optimization ), - это процесс одновременной оптимизации двух или более конфликтующих целевых функций в заданной области определения.

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







Содержание

Определение

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

\ Min_ \ vec {x} \ {f_1 (\ vec {x}), f_2 (\ vec x), \ dots, f_k (\ vec x) \},
\ Vec x \ in S

где f_i: R ^ n \ to Rэто k ( k \ ge 2) целевых функций. Векторы решений \ Vec x = (x_1, x_2, \ dots, x_n) ^ Tотносятся к не пустой области определения S.

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

 

Эталонные точки

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

  • идеальная точка, Y I,
  • утопическая точка, Y U,
  • надир ( надир ), Y N.

В некоторых случаях эти точки могут быть решениями.

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

y_k ^ I = \ min_ {x \ in X} f_k (x) = \ min_ {y \ in Y} y_k.

Точка надир y ^ N = (y_1 ^ N, \ dots, y_p ^ N) определяется как вектор:

y ^ N_k = \ max_ {x \ in X_E} y_k (x) = \ max_ {y \ in Y_N} y_k, \ qquad k = 1, \ dots, p.

Утопическую точку Y U вычисляют на основе идеальной:

y ^ U = y ^ I - \ epsilon U,

где ?> 0, U - единичный вектор.

 

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

Критерий Парето

Вектор решения \ Vec x \ in S называется оптимальным по Парето если не существует \ Vec x '\ in S такого, что f_i (\ vec x) \ le f_i (\ vec x ') для всех i = 1, \ dots, k и f_i (\ vec x) <f_i (\ vec x ') для хотя бы одного i. Множество оптимальных по Парето решений можно обозначить как P ( S ). Целевой вектор является оптимальным по Парето, если соответствующий ему вектор из области определения также оптимальный по Парето. Множество оптимальных по Парето целевых векторов можно обозначить как P ( Z ).

Множество оптимальных по Парето векторов является подмножеством оптимальных по Парето в слабом смысле векторов. Вектор \ Vec x '\ in Sявляется слабым оптимумом по Парето тогда, когда не существует вектора \ Vec x \ in Sтакого, что f_i (\ vec x) <f_i (\ vec x ') для всех.

Диапазон значений оптимальных по Парето решений в области допустимых значений дает полезную информацию об исследуемой задачу если целевые функции ограничены областью определения. Нижние границы оптимальной по Парето множества представлено в «идеальном целевом векторе». Его компоненты Z и полученные путем минимазации каждой целевой функции в пределах области определения.

Множество оптимальных по Парето решений также называют Парето-фронтом ( англ. Pareto-frontier ).

Лексикографический порядок

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

Отношение лексикографического порядка < lex между векторами \ Vec aи \ Vec b выполняется, если A Q < B Q, где. То есть, первые q компонент вектора \ Vec a меньше компоненты вектора, а компоненты q + 1 - уровни (если есть). Лексикографический порядок для случая действительных чисел является линейным.

Вектор \ Vec x \ in Xявляется лексикографическим решением, если не существует вектора \ Vec x '\ in X такого, что f(\vec x') <_{\mathrm{lex}} f(\vec x).

Поскольку отношение лексикографического порядка является линейным, можно доказать, что вектор \ Vec x является лексикографическим решением, если для всех \ Vec x '\ in X выполняется:

\ Vec f (\ vec x) <_ {\ mathrm {lex}} \ vec f (\ vec x ').

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

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

 

Скаляризация

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

Пусть F - функция скаляризации, что превращает векторную функцию \ Vec y = \ vec f (\ vec x) на скалярную. Если F сохраняет упорядоченность по Парето, то есть, если для произвольных \ Vec y ^ 1, \ vec y ^ 2 \ in \ vec f (X) выполняется:

\ Vec y ^ 1 \ le \ vec y ^ 2 \ implies F (\ vec y ^ 1) <F (\ vec y ^ 2),

тогда решение, что минимизирует F на X является решением по Парето.

Если F сохраняет отношение порядка < в, то есть, если для произвольных \ Vec y ^ 1, \ vec y ^ 2 \ in \ vec f (X) выполняется:

\ Vec y ^ 1 <\ vec y ^ 2 \ implies F (\ vec y ^ 1) <F (\ vec y ^ 2),

тогда решение, что минимизирует F на X является слабым по Парето. Если F непрерывна на, и \ Vec x ^ 0единственная точка минимума F на X, тогда \ Vec x ^ 0является решением по Парето.

Взвешенная сумма

F_1 (\ vec f (\ vec x)) = w_1 f_1 (\ vec x) + \ dots + w_r f_r (\ vec x).

Приведенная функция F 1 сохраняет упорядоченность по Парето для w > 0. Поэтому решения, минимизирующие F 1 на X для произвольных w > 0 являются оптимальными по Парето. Однако F 1 не сохраняет упорядоченность по Парето для w \ geq 0а сохраняет лишь отношение < и поэтому решения, минимизирующие F 1 на X для w \ geq 0 являются слабыми по Парето.

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

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

 

Функция скаляризации Чебышева

F_ \ infty (\ vec f (\ vec x)) = \ max_ {1 \ leq i \ leq r} w_i f_i (\ vec x).

Взвешенная функция скаляризации Чебышева сохраняет отношения < и поэтому минимум F_ \ infty является слабым по Парето.


Метод изменения ограничений (?-ограничения)

По методу изменения ограничений одну из целевых функций оставляют в качестве целевой, а остальные превращают в ограничения. То есть, пусть F R будет целевой, а остальные f_1, \ dots, f_ {r-1} как ограничение неравенства:

\ Min_x f_r (\ vec x),
при условиях: f_i (\ vec x) \ leq \ varepsilon_i, i = 1, \ dots, r - 1,
\ Vec x \ in X.

Значение \ Varepsilon_1, \ dots, \ varepsilon_ {r-1} могут рассматриваться как допустимые уровни для f_1, \ dots, f_ {r-1}.

 

Методы решения

Интерактивность

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

Эволюционные методы

Упоминания о применении генетических алгоритмов для решения задачи многокритериальной оптимизации относятся к концу 1960-х.

Просмотров: 15209

Вернуться в оглавление:Теория оптимизации




Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Полезен материал? Поделись:

Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.