Задача многокритериальной оптимизации. Multiobjectivization

Введение

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

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

Постановка задачи

Определение:

Задача многокритериальной оптимизации:

где – целевая вектор-функция, где

Так как не существует единого решение, которое было бы максимальным для всех целевых функций, вместо него можно искать множество [math]X^* \subseteq X [/math] множество Парето оптимальных значений.

Множество Парето оптимальных значений

Определение:

Множество Парето оптимальных значений:

:, где

Выражение [math]x \succ x^*[/math] означает, что [math]x[/math] доминирует над [math]x^*[/math].

Говорят, что [math]x[/math] доминирует над [math]x^*[/math]. по Парето, если [math]x[/math] не хуже [math]x^*[/math] по всем критериям и хотя бы по одному критерию превосходит [math]x^*[/math]. В таком случае в выборе [math]x^*[/math] нет смысла, т.к. [math]x[/math] по всем параметрам не уступает, а по каким-то и превосхожит [math]x^*[/math]. Если рассматривать всего два критерия то на рис. 1 показана область пространства, доминируемая данным решением А. Эта область «замкнута»: элементы на ее границе также доминируемы А

Рис.1 – Доминируемые решения

Определение:

Для двух решений и говорят тогда и только тогда, когда – такую пару решений называют недоминируемой

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

Рис.2 – Парето фронт

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

Multi-objectivization

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

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

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

Алгоритмы

Hill-Climbers

Определение:

Hill-Climbers – Итеративный алгоритм, который начинается с произвольного решения проблемы, а затем пытается найти лучшее решение, постепенно изменяя его. Если изменения позволяют найти лучшее решение, алгоритм сохраняет его и повторяет и повторяет своё выполнение до тех пор, пока лучшие решения не могут быть найдены

Initialization:

Init_pop

Main Loop:

Rand_mem,Rand_mem

[math]x'_1 \leftarrow [/math]Mutate[math](P)[/math],[math]x_2 \leftarrow [/math]Mutate[math](P)[/math]
if

Swap

if [math]f(x'_1) \gt f(x_1)[/math]

if [math]f(x'_2) \gt f(x_2)[/math]

Termination:

return Best

Задачи

Задача коммивояжера (TSP)является наиболее известно из всего класса [math]NP[/math]-сложных задач. Формулируется задача следующим образом:

Задано [math]C=\{c_1,c_2,\dots,c_N\} [/math] – множество городов и для каждой пары [math]\{c_i,c_j\}[/math] задано расстояние. Наша цель – найти цепь из городов, минимизирующую величину:

Для того, чтобы объектизировать эту задачу, нам необходимо определить подзадачи. TSP – является [math]NP[/math]-сложной именно потому, что нет хорошего разложения этой задачи.

Разобьём задачу таким образом:

where

and ,

где [math]a[/math] и [math]b[/math] – два города, указанных априори.

Предполагается, что [math]a[/math] и [math]b[/math] выбраны произвольно.

Источники

Википедия: Многокритериальная оптимизация
Knowles J., Watson R., Corne D. Reducing Local Optima in Single-Objective Problems by Multi-objectivization
Wikipedia: Multiobjective optimization
Wikipedia: Hill climbing
Гладков Л.А., Курейчик В.В., Курейчик В.М. "Генетические алгоритмы. Учебное пособие"

Задача многокритериальной оптимизации. Multiobjectivization

Введение