Научный журнал
Современные наукоемкие технологии
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 0,899

ОРИГИНАЛЬНАЯ СВЕРТКА ДВУХ КРИТЕРИЕВ ДЛЯ ЗАДАЧИ ВЫБОРА ЛУЧШЕГО ВАРИАНТА

Белов В.В. 1 Лопатин А.К. 2
1 ФГБОУ ВО «Рязанский государственный радиотехнический университет им. В.Ф. Уткина»
2 ГОУ ВО МО «Государственный социально-гуманитарный университет»
В рамках конкретной проблемной задачи синтеза алгоритма обработки изображений изделий, оптимального по двум критериям – точности обработки и быстродействию, – рассматриваются вопросы, связанные с формированием адекватного условиям задачи интегрального критерия, включая проблемы разных диапазонов значений частных критериев, их качественной разнонаправленности и рациональности структуры формулы свёртки критериев. Показана целесообразность нормализации частных критериев их максимальными значениями для установления отношения эквивалентности между нормализованными значениями. Указаны недостатки широко применяемой в настоящее время на практике нормализации критериев отрезками значений. Предложена семантически оригинальная структура мультипликативной свертки, отличающаяся от аналогов тем, что в ней в качестве выигрыша используется преимущество, получаемое от уменьшения качественно отрицательного критерия, а в качестве проигрыша – ущерб от уменьшения качественно положительного критерия. Приводится иллюстративный пример, демонстрирующий практическое применение и геометрический смысл предлагаемого критерия. Сопоставляются результаты практического применения мультипликативных сверток с традиционной и предлагаемой семантикой выигрыша и проигрыша в задаче синтеза оптимальной по двум критериям цепочки операторов обработки изображений. Показано, что первая «тяготеет» к минимальным значениям качественно отрицательного критерия, а вторая – к максимальным значениям качественно положительного критерия.
многокритериальный выбор
интегральный критерий
свертка
множество Парето
качественное направление критерия
нормализация
диапазоны значений
1. Грошев С.В., Карпенко А.П. Метаоптимизация популяционных алгоритмов многоцелевой оптимизации // Интернет-журнал «НАУКОВЕДЕНИЕ». 2016. Т. 8. № 6. [Электронный ресурс]. URL: http://naukovedenie.ru/PDF/52TVN616.pdf (дата обращения: 27.06.2019).
2. Забелин С.Л., Фроловский В.Д., Жеголко К.В. Разработка и исследование генетического алгоритма для автоматизации проектных процедур оптимизации геометрического покрытия // Вестник тамбовского государственного технического университета. 2015. Т. 21. № 2. С. 257–265. DOI: 10.17277/vestnik.2015.02.pp.257-265.
3. Белов В.В., Лопатин А.К. Применение механизмов эвристического поиска для формирования цепочек алгоритмов, улучшающих градиентные изображения // Вестник РГРТУ. 2018. № 66–1. С. 78–89. DOI: 10.21667/1995-4565-2018-66-4-1-78-89.
4. Айзерман М.А., Алескеров Ф.Т. Выбор вариантов. Основы теории. М.: Наука, 1990. 240 с.
5. Ногин В.Д. Принятие решений в многокритериальной среде: количественный подход. М.: ФИЗМАТЛИТ, 2002. 176 с.
6. Орлов А.И. Теория принятия решений. М.: Экзамен, 2010. 574 с.
7. Кини Р.Л., Райфа Х. Принятие решений при многих критериях: предпочтения и замещения. М: Радио и связь, 1981. 560 с.
8. Халафян А.А., Кошкаров А.А., Пелипенко Е.Ю. Cравнительная оценка эффективности вузов методами классификационного анализа // Фундаментальные исследования. 2016. № 5–1. С. 58–64.
9. Бражников М.А. Теория менеджмента: лабораторный практикум. Самара: Самар. гос. техн. ун-т, 2016. 76 с.

В настоящей статье рассматриваются некоторые аспекты задачи выбора лучшего варианта, актуальность которых возникла в процессе решения задачи синтеза оптимальной цепочки операторов, образующих алгоритм обработки изображений изделий, находящихся на конвейерной ленте, с целью квалификации их качества [1–3]. Синтез цепочек осуществлялся с помощью модифицированного генетического алгоритма [1, 3], осуществляющего одновременно и структурную, и параметрическую идентификацию формируемого алгоритма. При этом требовалось обеспечить оптимальность алгоритма по двум критериям – быстродействию и точности вычислений. Это требование обусловило необходимость выбора и конкретизации метода оптимизации.

Задача выбора лучшего варианта предполагает наличие некоторого количества конкурирующих вариантов, каждый из которых характеризуется одним или несколькими показателями качества, которые могут называться частными критериями. При этом критерии характеризуются качественным направлением:

– критерий качественно положителен (имеет положительное качественное направление), если качество варианта тем больше, чем больше значение этого критерия;

– критерий качественно отрицателен (имеет отрицательное качественное направление), если качество варианта тем больше, чем меньше значение этого критерия.

Формирование множества конкурирующих вариантов и оценка их показателей качества является самостоятельной задачей, предшествующей задаче выбора варианта. Выбор лучшего варианта [3] заключается в определении варианта, который в некотором смысле лучше других вариантов.

Неопределенный термин «в некотором смысле» становится вполне определенным, если количество частных критериев равно одному: лучшим считается вариант с лучшим (наибольшим или наименьшим) значением критерия. В этом случае задача выбора варианта тривиальна и проблемы выбора не существует.

Проблема выбора имеет место, когда количество критериев не меньше двух, и именно при двух критериях эта проблема возникает. Суть проблемы такова: варианты, лучшие по частным критериям, – это в общем случае разные варианты. Преодоление этой проблемы невозможно без вовлечения экзогенной информации, безусловно связанной с субъективным взглядом на предметную область, в рамках которой решается задача выбора [4].

Рассмотрим задачу выбора лучшего (оптимального) варианта в условиях использования двух частных критериев для оценки качества конкурирующих вариантов [4, 5]:

Искомая величина:

k – ? bel01.wmf,

Цель оптимизации выбора:

bel02.wmf

Ограничения:

bel03.wmf

где k – номер искомого лучшего варианта; n – натуральное число, выражающее количество конкурирующих вариантов; m+, m– – натуральные числа, выражающие соответственно количество качественно положительных и качественно отрицательных критериев; bel04.wmf – качественно противонаправленные частные критерии; bel05.wmf – значения j-х частных критериев, соответствующих i-му варианту; bel06.wmf – соответственно минимальное и максимальное значения j-х частных критериев.

В общем случае рассматриваемая задача не имеет точного решения, поскольку максимумы и минимумы разных частных критериев в общем случае соответствуют разным вариантам.

Цель исследования возникла в процессе решения задачи синтеза оптимальной цепочки операторов, образующих алгоритм обработки изображений изделий, находящихся на конвейерной ленте, и заключается в поиске наиболее рациональных способов решения следующих «классических» проблем, связанных с применением интегрального критерия в процедурах выбора «лучшего» варианта:

1) проблема разных диапазонов значений частных критериев качества сопоставляемых вариантов;

2) проблема качественной разнонаправленности частных критериев;

3) проблема синтеза рациональной структуры интегрального критерия.

Проблемы вербальности и разной значимости частных критериев не рассматриваются, поскольку они не имели места в контексте проблемной задачи.

Материалы и методы исследования

Все возможные решения рассматриваемой задачи являются приблизительными и, соответственно, необъективными. Каждый из методов решения этой задачи основан на формализации субъективных представлений о целесообразном и рациональном (разумном). Субъект или коллектив, представления которого формализуются, называется лицом, принимающим решение (ЛПР). Поскольку формализация субъективного представления о целесообразном и рациональном, как правило, является составной процедурой метода решения задачи, то, естественно, многократные решения задачи в одних и тех же условиях, определяющих количество вариантов и конкретику значений частных критериев, но разными ЛПР (а иногда и с одним и тем же ЛПР) могут приводить к получению разных результатов.

При любой формализации субъективных представлений предполагается, что выполнены два предварительных этапа:

1) формирование множества исходных вариантов;

2) оценивание значений частных критериев исходных вариантов.

Далее целесообразно осуществить сокращение информационного пространства рассматриваемой задачи путем выполнения следующих этапов:

3) формирование множества допустимых вариантов;

4) формирование множества Парето.

Множество допустимых вариантов формируется путем удаления из множества исходных вариантов тех из них, которые не удовлетворяют ограничениям на значения частных критериев [5, 6]. Обратим внимание на срабатывание механизма многокритериальности при выполнении указанной тривиальной процедуры: даже если некоторый вариант является наилучшим по какому-либо критерию, он все равно исключается из рассмотрения, если хотя бы один из других критериев не удовлетворяет установленному ограничению.

Множество Парето формируется путём удаления из множества допустимых вариантов качественно эквивалентных (дублирующих) и доминируемых вариантов.

Два варианта качественно эквивалентны, если имеют равные значения соответствующих показателей качества (частных критериев).

Отношение доминирования обозначается так: bel07.wmf. Говорят, что вариант Vi доминирует вариант Vj, и, соответственно, вариант Vj доминируется вариантом Vi, если одновременно справедливы следующие два условия:

1) среди показателей качества варианта Vi нет ни одного показателя, который был бы хуже соответствующего показателя варианта Vj;

2) хотя бы один из показателей качества варианта Vi лучше соответствующего показателя варианта Vj.

Таким образом, доминирующий и доминируемый варианты могут иметь равные показатели качества, но хотя бы по одному показателю первый лучше второго.

Множество Парето, состоящее из допустимых вариантов, само по себе представляет собой решение задачи выбора лучшего варианта. Причем это решение является точным, если множество Парето оказывается одноэлементным. Если же множество Парето состоит из нескольких элементов, то оно является решением «в первом приложении» и возможен поиск некоторого компромисса между значениями частных критериев, реализуемый на основе субъективных представлений о рациональном и целесообразном.

Результаты исследования и их обсуждение

Наиболее часто используемыми разновидностями формами интегрального критерия являются линейная и мультипликативная свертки [7, 8]. При использовании этих сверток приходится решать следующие проблемы:

1) разные диапазоны изменения разных критериев;

2) разное качественное направление критериев;

3) разные уровни значимости (важности) для ЛПР разных критериев;

4) лингвистические (словесные) значения некоторых частных критериев.

Первую проблему принято решать нормализацией – переходом от абсолютных значений критериев к относительным значениям, получаемым посредством операции деления.

Малорациональной представляется наиболее часто предлагаемая для практического использования в учебно-методической литературе [9] нормализация, совмещающая решение первой и второй проблем одновременно:

bel08.wmf (1)

Эта нормализация внешне эффектная: 1) она отображает значения всех частных критериев в один и тот же отрезок от нуля до единицы; 2) автоматически решает проблему разной качественной направленности критериев (все нормализованные критерии можно суммировать со знаком плюс). Однако такая нормализация по принципу «два в одном» имеет крайне существенный недостаток – она устанавливает эквивалентность диапазонов изменения частных критериев. В то же время очевидно, что незначительные (пренебрежимо малые) изменения одного критерия (например, точности решения задачи) никак не могут быть эквивалентны существенным изменениям другого критерия (например, длительности решения этой задачи). Таким образом, указанная нормализация (1) порождает новую проблему, которую приходится решать с помощью дополнительных весовых коэффициентов:

bel09.wmf, (2)

где wj – весовой коэффициент j-го частного критерия. Семантика указанных весовых коэффициентов такова: чем больше диапазон изменения частного критерия, тем выше его значимость. Таким образом, фактически нормализация (2) полностью решает только одну проблему – разной качественной направленности и только частично – проблему разных диапазонов изменения частных критериев. «Дорешивать» эту проблему приходится с помощью весовых коэффициентов (2).

Более рациональной представляется нормализация критериев их максимальными значениями:

bel10.wmf (3)

где bel11.wmf, bel12.wmf – нормализованное значение j-го критерия i-го варианта; bel13.wmf – максимальное значение j-го критерия среди всех вариантов; n – количество частных критериев; * – символ качественного направления частного критерия:

bel14.wmf

Нормализацию (3) можно рассматривать как установление эквивалентности максимальных значений критериев: максимальные значения всех нормализованных критериев оказываются одинаковыми – равными единице.

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

Аддитивная свертка равнозначных критериев, нормализованных максимальными значениями (1), имеет вид

bel15.wmf, (4)

где m+, m– – соответственно количество повышающих и понижающих критериев.

Аналогичная мультипликативная свертка имеет вид

bel16.wmf. (5)

Существенным семантическим недостатком сверток (4) и (5) является их абсолютное базирование нулем – отсчет значений критериев начинается с нуля. В то же время очень часто ноль является либо физически, либо логически (согласно ограничениям) недостижимым значением. В таких случаях базирование значений нулем приводит к снижению их сопоставимости, – например, некорректно сравнивать фактические массы продуктов по их массе с упаковкой (брутто). Поэтому более целесообразным является базирование критериев их минимальными значениями во множестве Парето. При этом аддитивная и мультипликативная свертки приобретают вид

bel17.wmf, (6)

bel18.wmf. (7)

Теоретически, а иногда и практически интересным является частный случай – двух качественно противонаправленных критериев, т.е. когда m+ = 1, m– = 1. В теоретическом плане случай с двумя частными критериями показывает проблему формальной неразрешимости задачи выбора наилучшего варианта в рафинированном виде, подобно тому, как испытания Бернулли с двумя исходами иллюстрируют семантику принципа стохастичности наиболее четко и наглядно. Противонаправленность двух частных критериев позволяет рассматривать и сравнивать в «чистом» виде различные подходы к преодолению проблемы качественной противонаправленности применяемых показателей качества вариантов.

В практическом плане проблема выбора варианта с двумя частными критериями качества наиболее актуальна в задачах сопоставления различных алгоритмов решения задач: очень часто алгоритмы сравниваются по двум качественно противонаправленным критериям: точности и оперативности решения некоторой задачи. При этом качественно положительный критерий bel19.wmf имеет семантику точности вычислений, а качественно отрицательный критерий bel20.wmf имеет семантику времени вычислений. Мультипликативная свертка двух частных критериев вида (7) имеет вид

bel21.wmf, bel22.wmf. (8)

Семантически интегральный критерий (8) представляет собой прирост «производительности»: он показывает, насколько увеличивается (по отношению к минимальному значению) точность вычислений при увеличении на единицу времени вычислений. Верхний индекс [M2+] символизирует мультипликативность, двухкритериальность и тот факт, что свертка создана для поиска максимума прироста «производительности» (в числителе формулы размещено приращение качественно положительного частного критерия).

Применение свертки (8) при решении практической задачи синтеза оптимальной цепочки алгоритмов для вычисления градиентных изображений изделий по их фотографиям [3] привело к получению следующего наблюдения: максимум bel23.wmf «тяготеет» к начальной части упорядоченного множества допустимых вариантов, образующих множество Парето. Предпочтительными оказываются алгоритмы со значениями частных критериев, близкими к минимальным значениям (естественно, допустимым).

По этой причине был предложен и использован альтернативный интегральный критерий:

bel24.wmf, bel25.wmf. (9)

Заметим, что единицы в числителе и знаменателе (9) – это максимальные значения нормализованных значений частных критериев: bel26.wmf, т.е. (9) можно записать и так:

bel27.wmf, bel28.wmf.

Семантически интегральный критерий (9) отражает уменьшение затратности: он показывает, насколько сокращается (по отношению к максимальному значению) время вычислений при уменьшении на единицу точности вычислений. Минус в индексе [M2–] символизирует тот факт, что в числителе формулы размещено уменьшение качественно отрицательного частного критерия. Эта свертка создана для поиска максимума сокращения временных затрат за счет точностных потерь.

Применение свертки (9) при решении задачи синтеза оптимальной цепочки алгоритмов для вычисления градиентных изображений привело к получению следующего наблюдения: максимум bel29.wmf «тяготеет» к конечной части упорядоченного множества Парето. Предпочтительными оказываются алгоритмы со значениями частных критериев, близкими к максимальным значениям. В упоминаемой задаче синтеза цепочки алгоритмов свертка (9) представляется более целесообразной по сравнению (8), поскольку она позволяет выбрать наиболее производительный алгоритм при незначительных потерях точности вычислений. В то же время свертка (8) может оказаться более предпочтительной при существенной абсолютной трудоемкости исследуемых алгоритмов.

Заметим, что обе свертки, и (8), и (9), представляют собой отношение некоторого выигрыша к ассоциированному проигрышу, т.е. конструкцию типа win / loss, которую можно назвать относительным преимуществом. В (8) числитель bel30.wmfпредставляет собой выигрыш по точности вычислений, а знаменатель bel31.wmf – проигрыш по времени счета. В (9) числитель bel32.wmf представляет собой выигрыш по времени счета, а знаменатель bel33.wmf – проигрыш по точности вычислений. При этом обе свертки выражают некоторый рациональный компромисс между двумя критериями, используемыми для выбора лучшего варианта.

На основе указанных сверток можно предложить следующее правило выбора лучшего варианта, которое имеет вид: в качестве лучшего варианта по двум качественно противонаправленным критериям следует принять вариант, входящий во множество Парето и имеющий максимум относительного преимущества в этом множестве. Значение качественно положительного критерия, соответствующее максимуму относительного преимущества, назовем рациональным максимумом, соответствующее значение качественно отрицательного критерия назовем рациональным минимумом.

Иллюстративный пример. На рисунке приведен график зависимости точности вычислений от времени счета пятнадцати алгоритмов, синтезированных с помощью генетического алгоритма [3], вошедших в динамическое множество Парето.

belov1.tif

Зависимость точности вычислений от временных затрат

Кружочки на графике соответствуют алгоритмам, вошедшим во множество Парето. По оси абсцисс отложено нормализованное время работы алгоритма – реальное время, поделенное на максимальное значение времени счета среди алгоритмов, вошедших во множество Парето. По оси ординат отложена нормализованная точность алгоритма (коэффициент корреляции) – реальный коэффициент, поделенный на максимальное значение коэффициента среди алгоритмов, вошедших во множество Парето.

Вектор значений интегрального критерия (8):

bel34.wmf = [1; 0.1387; 0.8608; 0.7931; 1.053; 1.45; 1.355; 1.164; 1.141; 1.114; 1.059; 0.9733; 0.9319; 1.164; 0.9947]

Графически каждое значение вектора bel35.wmf – это тангенс угла наклона к оси абсцисс прямой, соединяющей начальную и текущую точку графика.

Вектор значений интегрального критерия (9):

bel36.wmf = [1.005; 0.8815; 0.9604; 0.9265; 1.044; 1.46; 1.471; 1.324; 1.306; 1.257; 1.159; 0.9488 0.8161; 3.281; 1]

Графически каждое значение вектора bel37.wmf – это тангенс угла наклона к оси ординат прямой, соединяющей текущую и конечную точку графика.

Рассматривая значения векторов bel38.wmf и bel39.wmf, можно установить, что согласно критерию (8) лучшим является шестой алгоритм, а по критерию (9) – четырнадцатый.

Заключение

1. При решении проблемы разных диапазонов значений частных критериев процедура нормализации рассмотрена как процесс установления эквивалентности между нормализованными значениями. Показана целесообразность нормализации частных критериев их максимальными значениями (3). Указаны недостатки широко применяемой нормализации отрезками значений (2).

2. Проблема качественной разнонаправленности частных критериев решена использованием мультипликативной формы свертки этих критериев со следующей семантикой – в числителе размещается выигрыш, а в знаменателе проигрыш от отклонений критериев от их максимальных значений (единицами в нормализованном представлении).

3. При решении проблемы выбора структуры свертки частных критериев предпочтение отдано мультипликативной форме, но этот факт не является принципиальным, – все последующие предложения могли бы быть представлены и в аддитивной форме.

4. Предложена семантически оригинальная структура мультипликативной свертки (9), отличающаяся тем, что в ней в качестве выигрыша используется преимущество, получаемое от уменьшения качественно отрицательного критерия, а в качестве проигрыша – ущерб от уменьшения качественно положительного критерия. Назовем эту структуру структурой B. Структуры с традиционной семантикой (8), в качестве выигрыша используют увеличение положительно направленного критерия, а в качестве проигрыша – увеличение критерия с отрицательным качественным направлением. Назовем структуру с классической семантикой структурой A.

5. Показано отличие сверток критериев со структурами А и B – первая «тяготеет» к минимальным значениям качественно отрицательного критерия, а вторая – к максимальным значениям качественно положительного критерия.

6. В рамках решения задачи автоматического синтеза алгоритма по двум качественно разнонаправленным критериям могут использоваться как предложенная структура B, так и классическая структура A в зависимости от абсолютных значений того или иного критерия.


Библиографическая ссылка

Белов В.В., Лопатин А.К. ОРИГИНАЛЬНАЯ СВЕРТКА ДВУХ КРИТЕРИЕВ ДЛЯ ЗАДАЧИ ВЫБОРА ЛУЧШЕГО ВАРИАНТА // Современные наукоемкие технологии. – 2019. – № 8. – С. 14-19;
URL: https://top-technologies.ru/ru/article/view?id=37623 (дата обращения: 23.10.2021).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074