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.


 

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

25987. Философия эллинизма 20.28 KB
  Жизнь и деятельность ВойноЯсенецкого. ВойноЯсенецкого Валентин Феликсович ВойноЯсенецкий родился в 1877 г. Его отец провизор Феликс Станиславович ВойноЯсенецкий происходил из известного с 16 века обедневшего дворянского рода. Отец ВойноЯсенецкого был католиком мать Мария Дмитриевна Кудрина православной.
25988. Основные принципы философии средневековья. Номинализм и реализм 16.6 KB
  Основные принципы философии средневековья. Возникновение средневековой философии очень частосвязывают с падением Западной Римской империи 476 год н. В средневековой философии напротив реальностью определяющей все сущщее есть Бог.э конкурируют между собой философские учения стоиков эпикурейцев неоплатоников и в это же время формируются очаги новой веры и мысли которые в последствии составят основу средневековой философии.
25989. Философия Фомы Аквинского, Наука в жизни общества 32.58 KB
  Платоническое представление Августина о человеческой душе как независимой от тела духовной субстанции обладающей способностью непосредственно усматривать вечные несотворенные истины Идеи в свете Божественного просвещения Фома заменяет восходящим к Аристотелю понятием души как формы тела. Воздействие объектов приводит к образованию в душе их чувственных образовподобий от которых интеллект абстрагирует умопостигаемые формы универсалии следы творения вещей с помощью Божественных Идей. разумная часть человеческой души являются...
25990. Возрождение Основные вопросы философии 24.92 KB
  Соловьёв Владимир Сергеевич [1628. Сын Соловьёв Владимир Сергеевич М. После речи против смертной казни в марте 1881 в связи с убийством Александра II народовольцами Соловьёв Владимир Сергеевич был вынужден оставить преподавательскую работу.Как мыслитель и утопист Соловьёв Владимир Сергеевич оказался на пересечении разных духовных течений.
25991. Основные принципы гуманизма. Э. Роттердамский и др 20.79 KB
  В данной работе мы не будем говорить ни о христианской догматике ни о христианской мистике. Мы будем говорить лишь о христианской морали то есть о том насколько христианство отвечает высоким моральным стремлениям человеческого духа здесь на земле. Уже одно то что из всех евангельских догматов самым главным является догмат о том что Бог именно изза любви к человеку Сам становится человеком терпит все человеческие невзгоды лишения и страдания вплоть до мучительной и позорной смерти и все это повторяем именно изза любви к...
25992. Научные открытия э похи Ренессанса Н. Коперник, Д. Бруно, Г. Галилей 20.66 KB
  Исходя из этого положения Коперник весьма просто объяснил всю кажущуюся запутанность движений планет но не зная ещё истинных путей планет и считая их окружностями он был ещё вынужден сохранить эпициклы и деференты древних для объяснения неравномерности движений. В первой части говорится о шарообразности мира и Земли а вместо положения о неподвижности Земли помещена иная аксиома Земля и другие планеты вращаются вокруг оси и обращаются вокруг Солнца. С гелиоцентрических позиций он без труда объясняет возвратное движение планет.Во второй...
25993. Социально-утопические учения Томаса Мора 22.4 KB
  Гуманистическое мировоззрение автора Утопии привело его к выводам большой социальной остроты и значимости особенно в первой части этого произведения. Уже эти глубокие констатации подсказали Мору основное направление проектов и мечтаний во второй части Утопии . Многие гуманисты начиная с Эразма видели в Утопии долгожданную соперницу этого величайшего творения политической мысли произведения существовавшего к тому времени почти два тысячелетия. Если ли не самую характерную определяющую черту социальнофилософской доктрины лежащую в...
25994. Социально - политические учения Никколо Макиавелли 16.88 KB
  Монтень Мишель Монтень является французским философом эпохи Возрождения. В историю Монтень вошел как основатель скептицизма как продолжатель античного скептицизма Пиррона.Отвергая религиозное учение о бессмертии души Монтень подходит к пониманию сознания как свойства материи.В отличие от агностиков Монтень не отрицает познаваемости мира.
25995. Философия, ее предмет и функции. Философия и естествознание 16.08 KB
  Философия ее предмет и функции. Философия и естествознание Философия с греч. Философия вырабатывает обобщенную систему взглядов на мир место человека в нем; она исследует познавательные ценности социальнополитическое нравственное и эстетическое отношение человека к миру. Философия всегда в той или иной степени выполняла по отношению к науке функции методологии познания и мировоззренческой интерпретации ее результатов.