Статистически оптимальный генератор псевдослучайных последовательностей
1.4 Задачи многокритериальной оптимизации
Многие практические задачи приводят к необходимости решения так называемых задач многокритериальной оптимизации. Эти задачи возникают в тех случаях, когда необходимо с помощью одного акта принятия решений добиться наилучшего выполнения нескольких возможно противоречивых целей. С математической точки зрения задачи многокритериальной оптимизации являются естественным обобщением обычных задач оптимизации.
Пусть есть n-мерный вектор конструктивных параметров создаваемого изделия и задано допустимое множество X, которому должны принадлежать вектора x. Качество изделия оценивается набором критериев . Этот набор объединим единым символом , называемым векторным критерием.
Наша задача подобрать такую допустимую точку , чтобы все компоненты вектора принимали возможно меньшие значения. Это условие обычно бывает невыполнимо: минимизация какой-нибудь одной компоненты F приводит к увеличению других компонент.
Задачу многокритериальной минимизации на множестве X будем обозначать
(22)
Определим множество
(Векторное неравенство , где означает, что выполнены покомпонентные неравенства , или, что то же самое, выполнено любое из неравенств:
)
Введем образы множеств X и при отображении , . Задачу (22) перепишем в виде
.(23)
Множество можно определить условием
Пространство n-мерных векторов будем называть пространством параметров. Пространство m-мерных векторов назовем пространством критериев. Множество называется множеством Парето в пространстве критериев, множество - множеством Парето в пространстве параметров.
Рисунок 2. Множество Парето.
На рисунке 2 для двухкритериальной задачи (m=2) показаны множества Парето в пространстве критериев (жирная линия), множество достижимых критериев Y (лежит внутри и на границе области, ограниченной сплошной линией). С каждой точкой можно связать отрицательный и положительный ортанты: Можно сказать, что - совокупность точек, лучших, чем , а - худших, чем . Точки, принадлежащие множеству Парето в пространстве критериев, таковы, что для каждой точки множество лучших точек не содержит ни одной точки из множества Y. Можно множество назвать юго-западом точки , а множество - северо-востоком. Тогда для каждой точки из множества Парето в пространстве критериев пересечение ее юго-запада с множеством допустимых критериев Y пусто.
Понятия "лучший", "худший" можно перенести из пространства критериев в пространство параметров. Будем говорить, что точка лучше точки (или z хуже, чем x), если , . Множество , таким образом, представляет собой объединение таких точек, что для каждой из них нет ни одной точки из X, лучшей, чем . Эта идея отражена в определении множества . Под точным решением задачи многокритериальной оптимизации (22) или эквивалентной ей задачи (23) мы понимаем нахождение множества Парето в пространстве параметров , которое в дальнейшем будем называть множеством оптимальных решений задачи (22). Структура множества даже для простейших задач оказывается сложной. Ее описание с помощью аппроксимационных формул трудно реализуемо, поэтому введем понятие е - оптимального решения. Далее считаем, что множество X не пусто, каждая компонента вектор-функции F(x) удовлетворяет на X условию Липшица с одной и той же константой Липшица L, т.е. для любых x и z из X выполнены условия Отсюда следует векторной условие
(24)
(e - единичный m-мерный вектор). Определение: Множество называется е-оптимальным решением задачи (22), если:
1) Для каждой точки найдется такая точка , что
(25)
2) В множестве A нет таких двух различных точек x и z, что . Векторное неравенство (25) эквивалентно выполнению любого из следующих двух скалярных неравенств:
.(26)
Второе условие е-оптимальности можно переформулировать так: для любых разных точек x и z из A выполнены эквивалентные между собой неравенства:
Другими словами, у вектора наименьшая компонента строго отрицательная, наибольшая - строго положительная. Тем самым ни об одной точке из A нельзя сказать, что она лучше или хуже любой другой точки из A. Нет среди них точек, имеющих один и тот же образ, т.е. для всех точек z и x из A.
Зададим набор точек из допустимого множества X и обозначим эту совокупность В каждой точке вычислим векторный критерий. Количество точек в наборе будем увеличивать специальным образом, определяя при этом последовательность множества таким образом, чтобы в конце расчетов множество оказалось е-оптимальным решением задачи (22).
Правило построения множества .
Множество состоит из одной точки . Пусть известны В допустимой точке вычислим вектор .
Возможны 3 случая:
1) Если оказалось, что среди элементов есть такие, что , , то все они удаляются из ; точка включается в множество . Полученное множество обозначается через .
2) Если оказалось, что существует хотя бы один такой элемент , что , то не включается в . Множество обозначается через .
3) Если не выполнены условия предыдущих двух случаев, то точка включается в множество , которое обозначается далее .