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.


 

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

84185. ОПУХОЛИ МЫШЕЧНОЙ ТКАНИ 24.53 KB
  Макроскопически опухоль представляет собой четко отграниченный узел плотной консистенции волокнистый на разрезе. При обилии сосудов опухоль называют ангиолейомиома. Лейомиосаркома злокачественная лейомиома незрелая злокачественная опухоль из гладкой мускулатуры.
84186. ОПУХОЛИ КРОВЕНОСНЫХ И ЛИМФАТИЧЕСКИХ СОСУДОВ 24.01 KB
  Микроскопически опухоль состоит из ветвящихся сосудов капиллярного типа с узким просветом который не всегда заполнен кровью. 1ломусангиома опухоль Барре Массона зрелая доброкачественная опухоль сосудистого происхождения миоартериального гломуса. Гемангиоперицитома опухоль сосудистого происхождения в которой наряду с формированием сосудов происходит пролиферация периваскулярных клеток.
84187. Опухоли синовиальной ткани. Опухоли мезотелиальной ткани. Опухоли периферических нервов 24.61 KB
  Опухоли мезотелиальной ткани. Опухоли периферических нервов. Опухоли симпатических ганглиев.
84188. ОПУХОЛИ (ОБЩЕЕ УЧЕНИЕ) 24.92 KB
  Хондрома зрелая доброкачественная опухоль. Микроскопически опухоль имеет строение зрелого гиалинового хряща. Остеома зрелая доброкачественная костная опухоль. Макроскопически опухоль пестрого вида от белосерой до коричневокрасной окраски рыхлой консистенции несмотря на наличие очагового обызвествления.
84189. РАК ВАЖНЕЙШИХ ЛОКАЛИЗАЦИЙ 28.8 KB
  Высокая заболеваемость раком желудка по мнению многих авторов обусловлена употреблением в пишу продуктов содержащих нитраты. Чаще всего рак в желудке возникает в пилорическом отделе затем на малой кривизне в кардиалъном отделе на большой кривизне реже на передней и задней стенке очень редко в области дна. Чаще всего рак желудка имеет язвенную форму с бугристыми приподнятыми или плоскими краями иногда в сочетании с инфильтрирующим ростом язвенноинфильтративный рак на втором месте стоит диффузный рак форма инфильтрата с...
84190. ОПУХОЛИ КРОВЕТВОРНОЙ СИСТЕМЫ, ИЛИ ГЕМОБЛАСТОЗЫ 26.56 KB
  Лимфомы. Принципы классификации лимфом: неходжкинские лимфомы; лимфомы Ходжкина. Лимфомы и лейкемии относят к полиэтиологическим заболеваниям.
84191. РЕВМАТИЧЕСКИЕ БОЛЕЗНИ. РЕВМАТИЗМ. ПОРОКИ СЕРДЦА 28.8 KB
  ПОРОКИ СЕРДЦА Определение Этиология и патогенез Морфогенез Эндокардит Миокардит Перикардит Патаритрит Пороки сердца Системные заболевания соединительной ткани принято называть в настоящее время ревматическими болезнями. Ревматизм болезнь Сокольского Вуйо инфекционноаллергическое заболевание с преимущественным поражением сердца и сосудов волнообразным течением периодами обострения атаки и ремиссии. Важное значение придается антителам перекрестно реагирующим с антигенами стрептококка и антигенами тканей сердца а также клеточным...
84192. ПАТОЛОГИЯ КЛЕТОК КРОВИ И КОСТНОГО МОЗГА. АНЕМИИ 23.96 KB
  АНЕМИИ Анемии Паталогическая анатомия Гемолитические анемии Болезни системы крови разнообразны. Наибольшее развитие имеют анемии гемобластозы тромбоцитопении и тромбоцитопатии. Анемии или малокровие группа заболеваний и состояний характеризующихся уменьшением общего количества гемоглобина. В зависимости от этиологии и патогенеза различают анемии: постгеморрагические; вследствие нарушения кровообразования; вследствие повышенного кроворазрушения гемолитические.
84193. ПАТОЛОГИЯ КЛЕТОК КРОВИ И КОСТНОГО МОЗГА. ЛЕЙКОЗЫ. ЛИМФОГРАНУЛЕМАТОЗ 24.71 KB
  костном мозге бластных клеток. Острый плазмобластный лейкоз возникает из клетокпредшественников Влимфоцитов способных к продукции иммуноглобулинов. При остром эритромиелозе ди Гульелымо в костном мозге происходит разрастание эритробластов и других ядросодержащих клеток эритропоэза миелобластов монобластов и недифференцированных бластов.