🗊Презентация Поиск решений и принципы оценки качества решения многокритериальных оптимизационных задач с помощью эталонов

Поиск решений и принципы оценки качества решения многокритериальных оптимизационных задач с помощью эталонов

Содержательная постановка задачи Заданы 1. Критерии, характеризующие некоторый объект; 2. Взаимосвязи между переменными, определяющими величины критериев; 3. Области определения переменных. Требуется Определить такое сочетание значений аргументов, которое бы было оптимальным.

Определения 1. Оптимальным по Парето является такое сочетание значений переменных, любое изменение которых, улучшающее значение одних критериев, приводит к ухудшению значений других критериев. 2. Идеальным называется такое сочетание значений критериев, которому отвечают их «наилучшие» величины. 3. Наихудшим называется такое сочетание значений критериев, которому отвечают их «наихудшие» величины.

Формальная постановка задачи многокритериальной оптимизации

Анализ существующих подходов Существующие подходы к решению задачи (1): Замена множества критериев их взвешенной суммой. Лексикографическое упорядочение критериев. Недостаток оптимума по Парето: низкая селективность: мощность множества оптимальных планов может оказаться соизмеримой с мощностью множества всех допустимых планов, что порождает проблему выбора. Недостатки существующих подходов: используется некая добавочная информация о важности либо весе критериев, отсутствующая в оригинальной постановке задачи; отсутствует гарантия того, что полученное решение будет Парето – оптимальным.

Формальная постановка задачи поиска идеального и наихудшего сочетания значений критериев

Новые определения оптимальности: Оптимальными считаются такие сочетания значений переменных, для которых: a) Вектор критериев определяет точку в пространстве критериев, которая находится на минимальном расстоянии от идеального сочетания значений критериев, ИЛИ b) Вектор критериев определяет точку в пространстве критериев, которая находится на максимальном расстоянии от наихудшего сочетания значений критериев, ИЛИ c) Вектор критериев определяет точку в пространстве критериев, для которой отношение расстояния до точки, отвечающей идеальному сочетанию значений критериев к расстоянию до точки, отвечающей наихудшему их сочетанию, минимально.

Формальная постановка задачи поиска решения, наименее удаленного от идеального сочетания значений критериев для случая, когда все критерии однородны

Использование эталона для выбора метода обучения

Графическая иллюстрация поиска оптимального сочетания значений критериев на основании определения b)

Использование эталона для выбора метода обучения

Графическая иллюстрация поиска оптимального сочетания значений критериев на основании определения c)

Использование эталонов для выбора метода обучения

Классификация задач ранжирования Классификация задач ранжирования

Содержательная постановка задачи Содержательная постановка задачи Пусть каждый эксперт или группа экспертов оценивают пару объектов «с», «d» пользуясь только бинарными отношениями: «объект “c” лучше объекта “d”», «объект “c” эквивалентен объекту “d”» и «объект “c” хуже объекта “d”». Целью является ранжирование объектов, т. е. определение такой перестановки n объектов , для которой справедливо: если k < j, то

Пример 2.1 (продолжение) Пример 2.1 (продолжение) Традиционный способ решения Одним из традиционных способов реализации ранжирования является использование языка и методов теории графов: строится взвешенный ориентированный граф G(X, U), вершины множества Х которого соответствуют объектам, и существует дуга (i, j) Є U, если справедливо: i  j, причем вес этой дуги r(i, j) может быть прямо пропорционален профессиональному рейтингу соответствующего эксперта или группы экспертов. Если граф G(X, U) содержит контуры, то это говорит о наличии противоречий в экспертных оценках. Наиболее простой способ избавиться от противоречий – отказаться от мнений некоторых экспертов, что сводится к задаче о разрыве контуров на графах. Таким образом, задача ранжирования объектов может быть, в конечном счете, сведена к поиску отношения доминирования вершин ориентированного графа без контуров, т.е. к определению некоторого упорядочения этих вершин. Одна из процедур ранжирования вершин на каждой i-й итерации (i=1, 2, . . .) сводится к выделению вершин-источников, объекты, соответствующие этим вершинам, ставятся на i-e место в перестановке , после чего выбранные вершины отбрасываются и, если граф не исчерпан, процедура повторяется на (i+1)-й итерации.

Пример 2.1 (продолжение) Решение с помощью эталонов Пример 2.1 (продолжение) Решение с помощью эталонов

Самостоятельно: 1) определить рейтинг пяти кафедр: