Статистически оптимальный генератор псевдослучайных последовательностей

дипломная работа

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) Если не выполнены условия предыдущих двух случаев, то точка включается в множество , которое обозначается далее .

Делись добром ;)