36211

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

Доклад

Математика и математический анализ

Процедуры первой группы осуществляют поочередный поиск отдельных неулучшаемых точек как решений вспомогательных скалярных задач. В них на каждой итерации получается целое множество “неплохих†точек которое на последующих шагах постепенно улучшается. Генератор на каждой итерации порождает набор точек zk а ФВ осуществляет отбор в некотором смысле лучших из них: Генератор множеств точек zk Функция выбора С Для организации выбора необходимо произвести парные сравнения исходных вариантов и отбросить те из...

Русский

2013-09-21

31.5 KB

2 чел.

9  Вопрос

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

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

Определение 2.1. Будем говорить, что некоторая функция (у), у Q, убывает (не возрастает) по бинарному отношению R, определенному на элементах множества Q, если для любых у, z  Q из отношения (у, z)  R следует          (у) < (z)  ( (у)  (z) ).

Теорема 2.1. (основная для поточечных методов). Если в точке у*  Q достигается минимум некоторой функции (у), убывающей по бинарному отношению R, то  у* СR (Q).

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

Будем рассматривать методы, представляющие собой суперпозицию двух процедур, работающих поочередно: генератора и функции выбора (ФВ). Генератор на каждой итерации порождает набор точек zk, а ФВ осуществляет отбор в некотором смысле лучших из них:

Генератор множеств точек zk                 Функция выбора С()

Для организации выбора необходимо произвести парные сравнения исходных вариантов и отбросить те из них, для которых найдется доминирующий элемент. Если исходное множество велико, то метод попарного сравнения трудоемок, т.к. в общем случае необходимо произвести N(N – 1) / 2 сравнений, где N – число сравниваемых вариантов. Более эффективен следующий алгоритм последовательного выбора, который производит постепенное накопление элементов искомого множества.

Обозначим X = {xi} – исходное множество сравниваемых вариантов.  Для него будем производить отсев плохих точек и получение множества R(Х), содержащее альтернативы, неулучшаемые по заданному бинарному отношению R.

     begin   R(Х) := {х1};

                 for   j := 2   to   N   do

                      R(Х) := CR ({ xj } R(Х) ) ;

     end.

Обычно множество недоминируемых точек содержит значительно меньше элементов, чем исходное, т.е. n = | R(Х) | << |Х| = N. В этом случае нужно провести O(Nn) сравнений, т.е. намного меньше, чем при всевозможных парных сравнениях.

Данный алгоритм корректен, т.е. дает верное решение, если для любых множеств Z, Y X выполняется соотношение:

            CR ( Z Y) = CR ( Z CR(Y) ),                              (2.1)

т.е. выбор можно производить как последовательно – сначала на Y, получив CR(Y), потом на Z  CR(Y), так и сразу на объединении Z  Y.

Теорема 2.2. (основная для алгоритмов последовательного выбора). Соотношение  (2.1)  выполняется, если отношение R является качественным порядком (асимметричным и транзитивным).

Для справок: Отношение R асимметрично, если R R–1= , т.е. пересечение отношения R с обратным отношением пусто.

Эквивалентное определение асимметричности: из двух отношений (x, y) R и (y, x)R одно не выполняется.

Примеры асимметричных отношений:  ">",  "<", "быть начальником".                                                                                           

Отношение R транзитивно, если для любых x, y, zA из того, что (x, y)R и (y, z)R следует (x, z)R.

Примеры транзитивных отношений:  ">",  "<", "=".

Не транзитивным является отношение "". Действительно, пусть x = 2,      y = 3,  z = 2, тогда справедливо x y и y z, но x = z, т.е. (x, z)R.