36211

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

Доклад

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

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

Русский

2013-09-21

31.5 KB

1 чел.

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.


 

А также другие работы, которые могут Вас заинтересовать

35649. Вязаная сумочка под различные мелочи 800.13 KB
  Затраты на изделие=стоимость ниток стоимость Крючка Стоимость всей пряжи:60 рублей. Стоимость крючка:10 рублей.
35650. Краснодара Творческий проект Би. 22.55 KB
  170 руб. 2 200 руб. 3 220 руб. 4 250 руб.
35652. Творческий проект «Фартук» 441.77 KB
  Прежде всего я села за стол взяла карандаш тетрадь нарисовала и описала несколько моделей фартука. Из нарисованных мною вариантов фартука я выбрала модель 5 . В качестве материала для изготовления этой модели фартука подойдет хлопчатобумажная ткань ситец: для основных деталей с печатным рисунком для отделки гладкокрашеная....
35653. Кулинария. Творческий проект 1.21 MB
  Цели и задачи проекта: – расширение кругозора в области кулинарии; – развитие понятия о здоровом и рациональном питании характеристика пищевой ценности отдельных продуктов рекомендации по организации рационального питания; – восприятие различных национальных блюд освоение приготовления; – формирование умения сервировки стола правильно вести себя за столом. Искусство приготовления пищи. Правильно смешать все ингредиенты подобрать правильное количество того или иного продукта красиво подать блюдо Так почему бы не устроить из приготовления...
35654. Вязание крючком 134.39 KB
  Х б нитки коричневого цвета м 16 руб. Х б нитки жёлтого цвет м 16 руб. Самоотценка Экологическая оценка Мои нитки сделаны из натурального материала с добавлением искусственных материалов.
35655. Группа киноведов. Сравнение фильмов Сергея Бондарчука с работой Французского режиссера Дорнхельмом 57.5 KB
  Фахрутдинов Владислав В своей творческой работе я хочу сравнить два фильма снятых по роману Война и Мир с оригиналом произведения. За то время пока я собирал материал для этой работы я прочитал множество рецензий на оба фильма и сделал для себя вывод. Перейду сразу к самому интересному за что ругают оба фильма – это кино ошибки. Или в начале фильма обозначена сюжетная линия Николая Ростова и после 1807 года она почти полностью опущена.
35656. Лавочка. Творческий проект 40.1 KB
  Лавочки стол шкаф вот весь интерьер комнаты.ЦельПроявить свои способности в проектной деятельностиИзучить конструирования и технологию изготовления лавочки Научиться правильно пользоваться инструментами Изготовить Лавочку 4. Выбор изделияЛавочки весной и летом весьма востребованные изделия на даче когда люди много трудятся сажают растения и...
35657. Летняя сумочка. Вязание крючком 8.05 MB
  Связать изделие 4. Булавки вкалывают в изделие в три прокола таким образом чтобы острие осталось по возможности между слоев ткани. Незавершенное изделие лучше хранить завернув в ткань или положив в пакет. работа оформлена в законченное изделие в целом изделие производит благоприятное впечатление.