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.


 

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

7682. Нормування праці 19.21 KB
  Нормування праці Нормування праці - це від діяльності з управління підприємством, пов’язаний з визначенням необхідних затрат праці та її результатів, контролем за мірою праці. Мета нормування праці в ринкових умовах полягає в тому, щоб на ...
7683. Призначення та класифікація нормативів праці 61.25 KB
  Призначення та класифікація нормативів праці. Під час нормування праці важливим завданням є забезпечення більш-менш рівної інтенсивності праці на різних за змістом та складністю роботах. Це досягається використанням єдиної методологічної (зага...
7684. Компенсаторно-приспособительные процессы 50 KB
  Компенсаторно-приспособительные процессы Определение. Приспособление (адаптация) - это процессы, с помощью которых организм реагирует на изменения условий жизни. Компенсация - это вид приспособления (адаптации) для восстановления нар...
7685. Опухоли системы крови (гемобластозы) 53.5 KB
  Опухоли системы крови (гемобластозы) Гемобластозы - опухолевые процессы кроветворной ткани. Разделяют две группы гемобластозов: лейкозы (лейкемия) - системные опухолевые заболевания кроветворной ткани. лимфомы - регионарны...
7686. Онкология. Теоретические особенности 49 KB
  Онкология Опухоль (tumor, neoplasma, blastoma) - патологический процесс, характеризующийся бесконтрольным размножением и ростом клеток, что связано с изменениями в генетическом аппарате клеток. Свойства опухоли: автономный рост опухоли...
7687. Эпителиальные органоспецифические опухоли 41 KB
  Эпителиальные органоспецифические опухоли Определение. Органоспецифические опухоли - это большая группа доброкачественных и злокачественных опухолей, которые развиваются только в определенном органе или происходят из клеток определенного органа...
7688. Мезенхимальные опухоли 49 KB
  Мезенхимальные опухоли Мезенхимальные опухоли происходят из тканей мезенхимального происхождения. Это группа включает опухоли из фиброзной, жировой, мышечной, синовиальной, мезотелиальной, костной, хрящевой тканей, а также опухоли сосудов (кро...
7689. Раки важнейших локализаций 91 KB
  Раки важнейших локализаций Актуальность темы Ежегодно число новых случаев выявления рака во всех странах мира составляет около 6 млн. человек. Уровни заболеваемости и смертности от злокачественных опухолей в разных странах и даже регионах этих стран...
7690. Акселерация и ретардация 35 KB
  Акселерация и ретардация. Акселерация (от лат. acceleration - ускорение) - это ускоренное физическое и отчасти психическое развитие в детском и подростковом возрасте...