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.


 

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

43833. Повышение эффективности процесса управления физической культурой и спортом на муниципальном уровне 320 KB
  Практика применения Федерального закона «О физической культуре и спорте в Российской Федерации» выявила его излишнюю декларативность, существенные недостатки и пробелы в числе норм регулирующих правоотношения в сфере физической культуры и спорта, противоречия с иными актами высшей юридической силы.
43834. Разработка рекомендаций и мероприятия по управлению конфликтными ситуаций в ООО «ВАЛ-РЕЙСИНГ63» г.о.Тольятти 711.32 KB
  Особенности управления конфликтом в производственной организации . Конфликт в организации принимает самые различные формы. Большинство конфликтов оказывают негативное влияние на деятельность организации.
43835. Получение биологически активного hrNGF человека путём бактериального синтеза в клетках Escherichia coli 2.32 MB
  Объект исследования рекомбинантный человеческий фактор роста нервов hrNGF Цель дипломной работы получение биологически активного hrNGF человека путём бактериального синтеза в клетках Escherichi coli. Сконструированы гибридная система экспрессии hrNGF в которой в качестве белка партнёра выступал белок SUMO.
43836. Проект станции технического обслуживания с разработкой участка по ремонту и окраске кузовов легковых автомобилей 2.82 MB
  Эксплуатационные повреждения кузова Аварийные повреждения кузова Нарушение геометрии кузова.Общие требования при устранении перекосов кузова Планировочное решение зон ТО и ТР и производственных участков
43837. Расчет водоснабжения спортивно-оздоровительной базы «Бережок» 1.54 MB
  Таким образом целью дипломного проекта является создание системы водоснабжения базы отдыха Бережок включая проектирование водозаборных сооружений нужной производительности и степени надежности сооружений очистки воды до питьевых нормативов внутренних и наружных водопроводных сетей и сооружений а также мероприятий по пожаротушению. Грунтовые воды Высота стояния грунтовых вод низкая. Воды не напорные не агрессивны по отношению к бетону. Показатели качества воды в озере представлены санитарноэпидемиологической службой Вологодской...
43838. Разработка стандарта организации «Управление несоответствующей продукцией» системы менеджмента качества (СМК) «Орловский завод» ОАО «Северсталь-метиз» 2.26 MB
  Аудит процесса Управление несоответствующей продукцией Описание исходного состояния процесса на предприятии Разработка модели процесса Результаты аудита процесса
43839. Программный комплекс классифицирования выпускников вуза (учебный аспект) 3.2 MB
  Разработка структуры данных Разработка инфологической модели данных Разработка даталогической модели данных Проектирование схемы базы данных
43840. Гражданско-правовое положение акционерного общества 649 KB
  Российское законодательство со всей очевидностью отдает предпочтение форме акционерного общества предоставляя ему право осуществлять практически любые виды предпринимательской деятельности. Одновременно существует убеждение что коммерческая организация в процессе своего функционирования не только вправе осуществлять любые виды деятельности и совершать любые сделки но и что это допустимо независимо от ее финансового состояния. ГК РФ устанавливает что...
43841. Сущность права на иск в гражданском и арбитражном процессе 384.5 KB
  Понятие иска. Элементы иска. Предпосылки права на предъявление иска. Порядок предъявления иска и последствия его не соблюдения в гражданском процессе.