Задача многокритериальной оптимизации. Multiobjectivization
Введение
В данной статье рассматривается многокритериальная оптимизация, её задача. Рассматривается понятие Парето-фронт - множество Парето оптимальных значений. Также рассматривается задача коммивояжера и предлагается алгоритм её мультиобъективизации
Задача многокритериальной оптимизации
Постановка задачи
| Определение: |
| Задача многокритериальной оптимизации:
|
Так как не существует единого решение, которое было бы максимальным для всех целевых функций, вместо него можно искать множество множество Парето оптимальных значений.
Множество Парето оптимальных значений
| Определение: |
Множество Парето оптимальных значений:
|
Выражение означает, что доминирует над .
Говорят, что доминирует над . по Парето, если не хуже по всем критериям и хотя бы по одному критерию превосходит . В таком случае в выборе нет смысла, т.к. по всем параметрам не уступает, а по каким-то и превосхожит . Если рассматривать всего два критерия то на рис. 1 показана область пространства, доминируемая данным решением А. Эта область «замкнута»: элементы на ее границе также доминируемы А
| Определение: |
| Для двух решений и говорят тогда и только тогда, когда – такую пару решений называют недоминируемой |
На рис. 2 показана граница Парето для возможных решений в двухкритериальном пространстве
Множество Парето оптимальных недоминируемых решений называется Парето фронтом.
Multi-objectivization
Суть метода мульти-объективизации заключается в разбитии сложной задачи с одной целевой функцией на несколько подзадач, найти для каждой подзадачи решение и выбрать оптимальное решение.
Для выполнения оптимизации многокритериальной задачи мы должны добавить в целевую функцию новые параметры, либо должны добавить новые целевые функции.
Сложность этой процедуры заключается в разложении проблемы на ряд мелких независимых между собой подпроблем.
Алгоритмы
Hill-Climbers
| Определение: |
| Hill-Climbers – Итеративный алгоритм, который начинается с произвольного решения проблемы, а затем пытается найти лучшее решение, постепенно изменяя его. Если изменения позволяют найти лучшее решение, алгоритм сохраняет его и повторяет и повторяет своё выполнение до тех пор, пока лучшие решения не могут быть найдены |
| Initialization: | Init_pop |
| Main Loop: | Rand_mem,Rand_mem Mutate,Mutate
if if |
| Termination: | return Best |
Задачи
Hierarchical-if-and-only-if function
H-IIF – предназначена для моделирования проблемы с блочной структурой, каждый блок которой строго связан с остальными блоками.
- ,
где – блок бит – размер блока, а – левая и правая часть блока соответственно.
Применяя к этой задаче мультиобъективизацию, разобьём задачу на -задач.
Представим, как будет выглядеть :
где – первая цель; – вторая цель.
Данный подход помогает избежать проблему локальных максимумов (минимумов).
Задача коммивояжера
Задача коммивояжера (TSP)является наиболее известно из всего класса -сложных задач. Формулируется задача следующим образом:
Задано – множество городов и для каждой пары задано расстояние. Наша цель – найти цепь из городов, минимизирующую величину:
Применяя к этой задаче мультиобъктивизацию, нужно разбить её на подзадачи. TSP – является -сложной именно потому, что нет хорошего разложения этой задачи. Тем не менее задачу можно разбить на две или больше подтуров, каждый из которых мы можем минимизировать.
Представим подтуры в виде двух городов. Тогда наша задача примет вид:
-
- where
- and ,
где и – два города, указанных априори. Если , меняем их местами.
Предполагается, что и выбраны произвольно.
