Книга 1 Киев „Корнійчук 2009 Кононюк Анатолий Ефимович



страница32/33
Дата18.05.2019
Размер5.66 Mb.
ТипКнига
1   ...   25   26   27   28   29   30   31   32   33

2.11.6. Случайный поиск

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

При случайном поиске можно использовать три критерия для останова программы, ведущей синтез:

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

2) сформирована рекомендация, качество которой превышает заданный уровень (например, уровень качества рекомендации, которая была сформирована ранее или в другой проблеме) ;

3) темп роста качества в получаемой последовательности рекомендаций, где каждая рекомендация является наилучшей из всех, сформированных до нее, упал ниже заданного предела.

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

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

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

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

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

1) выявление грамматики, а также в принятом здесь понима­нии и семантики, дающих принципиальную возможность формально и достаточно компактно описать любой вариант проблемы заданного класса, разумеется, в пределах принятых ограничений на детализацию и возможное разнообразие (другими словами — построе­ние морфологического ящика);

2) выбор правил, по которым из заданного грамматикой мно­жества будет выбираться и синтезироваться подмножество рекомендаций-гипотез, предназначенных для сравнения по их характеристи­кам. В частности при использовании полного перебора, указанное подмножество совпадает со всем множеством, но в общем случае это не обязательно.
2.11.7. Структурирование проблемы и рекомендации

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

Разделив проблему на несколько структурных единиц (допустим, на несколько узловых рекомендаций), на I этапе синтезируют все единичные рекомендации (узловые рекомендации) по отдельности независимо друг от друга. При этом получается какое-то количество вариантов узловых рекомендаций каждого типа. На II этапе комбинируют между собой полученные варианты этих узловых рекомендаций, синтезируя тем самым различные варианты уже всей рекомендации, при этом типы узловых рекомендаций играют роль параметров для всей рекомендации, а различные варианты узловой рекомендации каждого типа — роль значений этих параметров. Суть предлагаемого метода заключается в том, что на II этапе в процедуре комбинирования участвуют отнюдь не все синтезируемые узловые рекомендации, а лишь узловые рекомендацие, оптимальные по Парето в пространстве внешних характеристик. Заметим, что при ограничениях на возмож­ности стыковки узловых рекомендаций в процедуре комбинирования могут участвовать и некоторые близкие соседи группы Парето, но для упроще­нии изложения основного принципа эти детали рассматриваться не будут. Число перспективных узловых рекомендаций, т. е. узловых рекомендаций, оптимальных по Парето, обычно во много раз меньше полного множества синтезированных узловых рекомендаций.

В качестве иллюстрации предлагаемого принципа рассмотрим проблему, описываемою шестью параметрами, каждый из которых имеет 10 зничений. Тогда объем перебора при обычном, одноэтапном синтезе составит 106 вариантов. Рассмотрим двухэтапный процесс синтеза рекомендаций той же проблемы. Пусть нам удалось представить рекомендацию как структуру из двух узловых рекомендаций — узловая рекомендация типа 1 и узловая рекомендация типа 2, причем из шести имеющихся параметров три характеризуют узловую рекомендацию 1, а оставшиеся три —узловую рекомендацию 2. Тогда объем перебора, при синтезе каждой из двух узловых рекомендаций составит 103 вариантов, из которых около 30 будут оптимальны по Парето. Теперь оценим объем перебора на II этапе при синтезе всей рекомендации из «лучших представителей» узловых рекомендаций 1 и 2 типа: 302≈l03. Общий объем перебора при двухэтапном синтезе всей рекомендации составляет лишь около 3000 (2 раза по 103 на первом этапе и 103 — на втором). Если расчленить проблему на три узла по два параметра на узел, то суммарный объем перебора можно сделать еще меньше. Нетрудно заметить, что, действуя этим методом, можно к совершенно, казалось бы, безнадежным с точки зрения объема перебора рекомендаций применять метод вариантного синтеза и при этом на каждом этапе использовать полный перебор, реализуя все его положительные стороны и не выходя за разумные рамки расхода машинного времени.

Отметим, что введение структурного деления, о котором здесь говорится, не тождественно повторению традиционного деления любого сложного объекта на более мелкие функциональные элементы. Мы ратуем за осознанное разделение проблемы на части с достаточно малым числом параметров, целью которого является удерживать объем перебора в разумных с точки зрения затрат машин­ного времени пределах. Иными словами, предлагается сознательно управлять объемом перебора при вариантном синтезе рекомендаций. Части, на которые при этом делится рекомендация, — это фактически лишь небольшие группы параметров, обладающие тем свойством, что для этих групп внешние характеристики аддитивны. Это деление в принципе может не совпадать с традиционным функциональным делением проблемы, хотя чем ближе проходят эти линии раздела, тем удобнее работать. Программы синтеза I и II этапов (этапов может быть и больше двух) поочередно вводятся в действие программой-диспетчером.

Сознательно управлять объемом перебора в некоторых преде­лах можно и при одноэтапном синтезе за счет выбора уровня сложности фрагментов. Деление на фрагменты, блоки и т. п. в боль­шой мере условно. Очевидно, чем больший уровень сложности фраг­ментов выбрал разработчик системы консультирования, тем меньше будет число типов этих фрагментов, т. е. тем меньше объем пере­бора. Однако повышение уровня сложности фрагментов требует большей квалификации составителя программы и большего объема работы по анализу возможных видов фрагментов и выделению из них оптимальных по Парето для занесения в гнезда морфологиче­ского ящика. В этом случае составитель берет на себя часть ра­боты, которую могла бы выполнять программа синтеза, использую­щая простые фрагменты. Подготовку консультантом сложных фрагмен­тов можно рассматривать как первый этап двухэтапного синтеза, выполняемый вручную. Вопрос о сложности фрагментов сводится, таким образом, к вопросу о рациональном разделении труда между человеком — составителем программы и ЭВМ. При этом надо учитывать существующее соотношение между уровнем знаний о консультируемой проблеме, стоимостью машинного времени и ожидаемой интенсивностью использования программы автоматического.



2.12. Выбор рациональных вариантов формируемых рекомендаций

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

Для поиска рекомендаций с помощью эвристических приемов распространены комбинаторные алгоритмы, основанные на организации множества генерируемых вариантов рекомендаций в виде древовидных (ярус­ных) графов. Если, например, общее количество ярусов (парамет­ров) равно 15—20, а число значений параметров на каждом ярусе 3—5, то общее число вариантов рекомендаций, которое необходимо про­смотреть в процессе машинного консультирования по одному консультационному заданию, может составить 108—1012. Это означает, что даже при применении компьютерова нахождение и оценка всех вариантов могут потребовать огромных затрат машинного времени.

Для сокращения перебора (количества вариантов формируемых рекомендаций) мож­но применять методы отсечения и метод ветвей и границ.

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

Рассмотрим наиболее эффективные методы выбора рациональ­ных вариантов формируемых рекомендаций.



Последовательный анализ. Отсечение бесперспективных вариантов рекомендаций в процессе их последовательной генерации может осуществ­ляться методом последовательного анализа, основанным на пра­виле доминирования. При этом i-й вариант рекомендации домини­рует над j-м, если взвешенная сумма показателей i-гo варианта больше соответствующей суммы показателей j-го варианта. В ре­зультате признается бесперспективным построение новых вариан­тов рекомендаций на основе показателей j-го варианта.

Общая схема формирования рекомендаций такова. Пусть на



(k — 1)-м шаге формирования рекомендаций определено множество перспективных вариантов={x1(k-1), x2(k-1),..... xl(k-1),}, каждый из которых характеризуется k параметрами. На очередном k-м шаге поиска каждый из полу­ченных ранее перспективных вариантов xl(k-1), используется для формирования новых вариантов рекомендации, число которых будет п k (где п — число вершин древовидного графа). Построение выпол­няется простым добавлением к xl(k-1) одного из еще не вошедших в этот вариант номеров вершин, при этом новые варианты харак­теризуются (k + 1)-ми параметрами. В результате получим рас­ширенное множество вариантов

={x1(k), x2(k),..... xl(п k)(k),}.

Сгруппируем варианты из , заканчивающиеся одним и тем же номером вершины древовидного графа, и с одинаковым множе­ством входящих в последовательность номеров. Использовав пра­вило доминирования, выделим в каждой такой группе по одному доминирующему варианту. Выделенные варианты образуют множество перспективных вариантов после k -го шага поиска. В дальнейшем процедура повторяется до тех пор, пока на п-м шаге из множества вариантов не будет выделен единственный оптимальный вариант.

Метод последовательного анализа используется для построе­ния кратчайшего замкнутого маршрута от вершины 1 к вершине 1 древовидного графа (рис. 2.16).

Рис. 2.16. Древовидный граф формирования рекомендаций для задачи о кратчайшем замкнутом маршруте


При этом для параметров ветвей перехода выбираем следующие значения: с12 = с21= 9; c12 = с31 = 10; с14 = с41 = 4; с23 = с32 = 6; с24 =с42= 8; c34 = c43 = 7.

Применяя метод последовательного анализа после 2-го шага

поиска, когда все три начальных варианта рекомендации принимаются

перспективными, находим решение задачи, сведенное в табл. 2.13.

Таблица 2.13

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

Нетрудно видеть, что вариант {1, 4, 3, 2, 1} является оптимальным.



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

Проиллюстрируем сказанное на графе рекомендаций (рис. 2.16), выбрав начальный базовый вариант, соответствующий маршруту {1, 3, 2, 4, 1} с «весом» с13 + с32 + с24 + с41 = 28 единиц. Начальный участок маршрута, соответствующего выбранному базовому ва­рианту рекомендации, содержит вершины 1, 3.

Далее рассмотрим возможность использования других началь­ных участков маршрута, содержащих две вершины (в нашем при­мере это участки графа (1, 2) и (1, 4) соответственно). Для каж­дого из этих участков последовательно вычисляется оптимистиче­ская оценка нижней границы длины маршрута, или «веса» соот­ветствующего варианта. Если значение получаемой оценки для очередного участка больше длины маршрута базового варианта, рассматриваемый участок считается бесперспективным и все про­должающие его ветви графа рекомендаций могут быть отсечены. В этом случае переходят к рассмотрению очередного участка. Если же значение получаемой оценки длины маршрута для очередного уча­стка меньше длины базового маршрута, то из конечной вершины этого участка осуществляется ветвление с последующим перебором участков, содержащих теперь уже три вершины графа. Процесс продолжается до получения полного маршрута с полной последо­вательностью вершин.

Если длина полученного маршрута (варианта рекомендации) меньше, чем для выбранного вначале, то новый вариант следует принять в качестве базового. Последний полученный итеративно базовый вариант будет оптимальным.

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

Х1 = {х1(1), х1(1),....., хk(1)} сводится к следующему. Из матрицы отношений

характеризующей граф рекомендаций, вычеркиваются строки с номерами {1, 2, ..., k — 1} и столбцы с номерами {2, 3.....k}, определяемыми номерами ветвей, образующих рассматриваемый участок нового маршрута. В оставшейся части матрицы С'ij на первом этапе оценки в каждой строке матрицы С'ij отыскивается мини­мальный элемент , который запоминается. Затем, вычитая минимальные элементы из всех остальных ненулевых элементов соответствующих строк, получаем новую матрицу С′'ij. На втором этапе оценки в каждом столбце матрицы С′'ij отыскивается минималь­ный элемент , который также запоминается и затем вычитается из всех ненулевых элементов соответствующих столбцов.

При этом оптимистическая оценка длины маршрута опреде­ляется суммой

(2.28)

Для графа рекомендаций, изображенного на рис. 2.16, матрица отношений имеет вид



Если в качестве начального участка маршрута выбран участок (1, 2), то в соответствии с процедурой оптимистической оценки маршрута получаем



в результате чего



По аналогии можно показать, что при выборе в качестве началь­ного участка маршрута нового варианта рекомендации участка (1, 4), получаем



Структурная схема последовательности работы алгоритма ме­тода ветвей и границ для частного случая графа рис. 2.16 показана на рис. 2.17. Из рис. 2.17 ясно, как происходит процесс отсечения бесперспективных ветвей исходного графа рекомендаций.

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

Для сокращения переборов вариантов решения применяют также различный приближенные формально-эвристические методы или идут по пути принудительного сокращения области по­иска, когда консультант на основании личного опыта задает значения параметров объекта на некоторых ярусах графа рекомендаций. Очевидно, что чем больше опыт консультанта и чем выше его квалификация, тем большее значение па­раметров он может выбрать и тем меньше времени потребуется для просмотра воз­можных вариантов рекомендации. В предель­ном случае, когда заданы все парамет­ры, задача сводится к оценке выбранного варианта по совокуп­ности частных кри­териев качества.



Рис. 2.17. Структурная схема последовательности

работы алгоритма ветвей и границ для частотного

случая графа рис. 2.16


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

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

Целесообразно применение в САК иных методов агрегации оценок (свертывания частных критериев в обобщенный) для полу­чения оптимальных рекомендаций. Этому способствуют те обстоя­тельства, что частные критерии φi, образующие векторный крите­рий качества

Ф = (φ1,..., φk, ..., φm), являются, как правило, ко­личественными; задачи формирования рекомендаций возникают в условиях определенности; структура предпочтений чаще всего допускает представление обобщенного критерия Ф в виде некоторого функ­ционала



W (Ф) = W((φ1,..., φm) в формах:

аддитивной



(2.29)

и мультиплексной



(2.30)

где wiA и wiМ — функционалы, определенные на множестве допустимых вариантов рекомендации X = {x1, ... , xN}.

В процессе выбора рациональной рекомендации очень важно учитывать неравноценность частных критериев φk. Как пра­вило, величина φk упорядочена по важности, при этом для пары φk и φs критерий φk важнее φs в строго определенное число раз wks = wk/ws, где wk, wsкоэффициенты относительной важности критериев φk и φs соответственно.

Таким образом, для формирования рекомендаций в САК необходимо иметь решающее правило, основанное на обобщенном (интеграль­ном) критерии W(φ1,..., φm), представленном в виде свертки ча­стных критериев [например, в виде выражений (2.29) и (2.30)].

При этом важно обеспечить (на экспериментальном уровне) адекватность принятой математической абстракции W(Ф) отображенным свойством реальности, в первую очередь, путем учета не­равномерности частных критериев φk,

Распространено также мнение, что нет принципиальной раз­ницы в том, какую из форм [выражение (2.29) или выражение (2.30)] обобщенного критерия применять на практике. Однако сравнитель­ный анализ этих выражений показывает, что мультипликативная форма (2.30) обладает рядом принципиальных недостатков. В со­ответствии с полученными экспертными оценками коэффициент важности wk воспринимается в консультационной практике именно как коэффициент для величины φk, при этом функционал



wkk)= wk φ′k, (2.31)

где φ′k — некоторый нормирующий функционал, обеспечивающий соизмеримость вклада критерия φk с вкладами других частных критериев в обобщенный показатель.

Нетрудно видеть, что в мультипликативной форме (2.30) при представлении частного критерия в виде выражения (2.31) не учитывается изменение коэффициентов важности wk. Кроме того, для любой пары сравниваемых вариантов рекомендации отношение обобщенных показателей остается неизменным при разном наборе коэф­фициентов w1, ..., wm. В то же время аддитивная форма

(2.32)
хорошо согласуется с теорией полезности и сущностью многокритериальных постановок задач для САК.

В выражение (2.32) входит нормированный показатель



(2.33)

или


(2.34)

При этом подразумевается такое определение частных крите­риев φk, что либо все они в процессе выбора рационального ва­рианта минимизируются (φk→min) или, наоборот, максимизи­руются (φk→max).

Для устранения возможности компенсации уменьшения ка­чества по одному частному критерию увеличением качества по другому предложено следующее решающее правило, в котором

(2.35)

Применение выражения (2.35) обеспечивает предпочтительный выбор таких вариантов рекомендации консультационной задачи, при которых значения частных критериев располагаются ближе всего к некото­рому идеальному вектору (φ1 min, …, φk min) при φk → min или век­тору

1mах..... φk mах) при φk→max. При этом отклонение от идеальной рекомендации определяется как относительное и взвешенное. Таким образом, всякий консультационный процесс, с точки зрения формирования рекомендаций, можно в принципе описать достаточно адекватно набором некоторых величин φk, сово­купность Ф={φk} которых образует векторный критерий эффек­тивности. Однако задача формирования множества Ф остается не­решенной, так как отсутствует методически обоснованное и про­веренное на практике руководство или методика получения Ф, ранжирования элементов φkФ по важности, вычисления значе­ний коэффициентов wk. Применительно к САК в указанной мето­дике отправным пунктом должно служить использование коллек­тивного опыта путем организации экспертиз (метод экспертных оценок).

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

Одним из вопросов, возникающих в начальной стадии, является выбор конкретного метода отбора рабочей экспертной группы (ЭГ). Наименее трудоемкий и действенный подход к формирова­нию ЭГ основан на известном принципе «снежного кома». Здесь в самом начале (нулевой тур) формируется очень узкий спи­сок специалистов, каждый из которых является бесспорным кан­дидатом в ЭГ. Далее (первый тур) каждый из них выдвигает по свое­му усмотрению кандидатов в эксперты. Из числа последних отби­раются специалисты, которым, в свою очередь, в следующем туре предлагается назвать своих кандидатов. Количество туров не бо­лее 3—4.

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

В качестве отправного рекомендован метод Дельфи, предложенный О. Халмер и Т. Гордон. Основной принцип этого метода заключается в том, что эксперты заполняют анонимные анкеты, а организаторы экспертизы стремятся получить общее мнение экспертов с минимальным разбросом их оценок, т. е. полностью согласованное мнение. Последнее достигается благодаря осуществлению ряда итераций (туров), в процесссе которых позиции экспертов, как правило, сближаются. В каждом последующем туре ими принимается к све­дению интегральная информация предыдущего тура и вносятся коррективы в свои оценки. Отметим два существенных недостатка этой процедуры согласования:

1) многократные итерации требуют значительных затрат времени;

2) метод исключает непосредственные контакты между экспер­тами, а они нередко бывают продуктивными.

Ни один из известных методов не снимает серьезных организационных и методологических труд­ностей, с которыми сопряжено получение согласованных эксперт­ных оценок. Именно эти трудности не дают возможности в усло­виях, близких к консультативным, рекомендовать целиком ка­кой-либо известный метод в качестве рабочего.

Для решения консультационных задач можно использовать методику, при которой первые два тура проводятся в полном соответствии с методом Дельфи. Третий и все последующие туры заменяются обычной дискуссией, которую метод Дельфи совершенно исклю­чает. Применение этого «запрещенного приема» в итоге приводит к тому, что сохраняется принцип анонимности на начальной ста­дии (первый и второй туры) и в то же время на заключительной стадии реализуются существенные преимущества, присущие дискуссиям — немедленная обратная связь, быстрое достижение экспертами взаимопонимания, возможность выступать большое число раз и уточнять или изменять свою точку зрения с учетом инфор­мации, полученной от коллег.

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

Возможен также формализованный подход к выбору весов wk. Первый шаг при этом состоит в минимизации каждой из функ­ций φk в отдельности. Эта процедура дает консультанту информа­цию об области возможных значений целевых функций. Следую­щий шаг предполагает определение весов wk, которые в соответ­ствии с принципом Парето обеспечат компромисс между этими частными экстремумами.

Напомним, что точками Парето являются точки пространства рекомендаций хп X, что для любого другого ва­рианта рекомендации

φi(x)≤ φi(xn) i= 1, ... , т.

Таким образом, точки (об­ласти) Парето представляют собой перспективные варианты рекомендаций. Для существования области

Парето, т. е. для хп X, необходимо, чтобы существовало множе­ство весов W = (w 1, ..., wm), wi > 0 такое, что

(2.36)

т. е.


Это позволяет сформировать комплексную целевую функцию



(2.37)

и минимизировать ее в программе рекомендаций для получения точек множества Парето хп X.

В свою очередь, задача минимизации (2.37) може быть сформулирована как задача минимизации функционала

π=W t Ф, (2.38)

в пространстве частных критериев ФQ, где Q — область допу­стимых или реализуемых рекомендаций. При этом ищется точка ФQ такая, что ее проекция на W является наименьшей среди всех ФQ. Можно показать, что в этом случае Ф(хп) лежит на гра­нице Q и функционал π определяет плоскость, касательную в точ­ке Парето хп и поддерживающую область Q (рис. 2.18).

Рис. 2.18 пояснению выбора точки множества Паето (а) и построения нижней (б) и верхней (в) аппроксимирующих областей


Предположим, что путем минимизации функционала π при использовании различных векторов весов W1, ..., Wm получены т точек множества Парето хi хп, i =1, ..., т.

Тогда это множество весов и точек образует нижнюю кусочно-линейную аппроксимацию Фн(хп) для области Фп). Если поло­жить



то пересечение πi определяет аппроксимацию Фн(хп) (рис. 2.18, б). Верхняя аппроксимация Фв(хп) может быть получена формирова­нием выпуклой оболочки точек Ф1п), ..., Фп т), внутренней по отношению к Q. Эта выпуклая оболочка может быть представлена ограничивающими ее гиперплоскостями, заданными своими внеш­ними нормалями (рис. 2.18, в).

В случае, когда компромиссная область Парето Фп) является выпуклой, ее ограничивают верхняя и нижняя аппроксимации. Эти аппроксимации могут быть улучшены путем добавления новых

точек Парето xпт+1, xпт+2, .... Например, консультанту требуется детализирующая информация о некотором участке компромиссной поверхности. Предположим, что интересующий его участок огра­ничен точками



хni1,…, хniт

которые образуют лицевую сторону верхней аппроксимации F. Нормаль W* к этой поверхности получают при помощи формиро­вания матрицы

Ф = {(Фi1п), ..., Фп iт)}

и решения уравнения

Ф tW* = е, (2.39)

где еt = (1,1.....1).

Таким образом, лицевая сторона F задается такими точками

Фijп)), j = 1, ... , т, что Ф tW* = 1.

Затем находится точка Ф*Фпп), которая минимизирует (W*)t Ф путем формирования матрицы

Wt= (Wi1.....Wim)

и решения уравнения



Wt Ф * = qj, (2.40)

где qj = (Wij)t Ф (xijn), j = 1,…,т.

Затем Ф* проектируется на поверхность F вдоль направления W* для получения на верхней аппроксимирующей области точки

ФF = Ф* +αW*, (2.41)

где α = (1 — W*tФ*) / W*tW*. Следовательно, W*t ФF =1, при этом подразумевается, ФF Ф в.

Компромиссная поверхность Парето про­ходит через т экстремальных точек, соответствующих φk min и об­разующих лицевую сторону верхней аппроксимации F, поэтому в соответствии с выражением (2.39) запишем

Найденный вектор весов W, представляющий собой нормаль к поверхности Парето, используется при последующей минимиза­ции всего аддитивного критерия (2.32) для получения дополни­тельной



+ 1)-й точки Парето φ(т+1). Если эта рекомендация неудов­летворяет (например, из-за большого j-го слагаемого), то про­изводится замена φjmin на φ(т+1), и процедура нахождения нормали W по уравнению (2.39) повторяется. Минимизация аддитивного кри­терия (2.32) с новым вектором весов обеспечивает уменьшение компоненты реализуемой аддитивной целевой функции, соответ­ствующей новой точке Парето φ(т+2). По усмотрению консультанта процедура уточнения вектора W может итеративно повто­ряться путем использования вновь получаемых точек Парето φ (т+k) вместо исходных φkmin .



Поделитесь с Вашими друзьями:
1   ...   25   26   27   28   29   30   31   32   33


База данных защищена авторским правом ©vossta.ru 2019
обратиться к администрации

    Главная страница