Содержание к диссертации
Введение
ГЛАВА 1. Задачи отсева нехудших решений на итерациях поиска в численной оптимизации по совокупности критериев 10
1.1 Специфические особенности выбора решений в моделях оптимизации 10
1.2 Возможности применения аппарата теории выбора для отсева решений на итерациях поиска 16
1.3 Модели отсева решений на итерациях поиска, основанные на существующих механизмах выбора 20
1.4 Моделей экспертных оценок и возможности их использования для отсева на итерациях поиска 27
1.5 Общие требования к архитектуре автоматизированной системы поддержки принятия решения 30
1.6 Выводы и задачи исследования 33
ГЛАВА 2. Параметрический синтез функций выбора на итерациях поиска 36
2.1 Построение оптимального набора функций и механизмов выбора 36
2.2 Разработка моделей и алгоритмов выбора на итерациях поиска . 49
2.2.1 Алгоритм "Парето-спуск" 49
2.2.2 Модель многокритериальной оптимизации путем перераспределения плотности вероятности 55
2.2.3 Алгоритм экспертного выбора на базе экстраполяции экспертных оценок по функции максимального правдоподобия 63
ГЛАВА 3. Структурный синтез функций выбора на итерациях поиска 67
3.1. Ситуации выбора для многокритериальных численных схем... 67
3.2 Обобщение типовых схем выбора 78
3.3 Построение адаптивных процедур выбора на итерациях поиска 84
ГЛАВА 4. Программный эксперимент и моделирование процесса выбора решений на итерациях поиска 91
4.1 Системная модель выбора решений для класса задач многокритериальной оптимизации. ПМК "Vector ХР" 91
4.2 Программный эксперимент и исследование построенных моделей, алгоритмов и ситуаций выбора 108
4.2.1 Анализ предложенных функций выбора 108
4.2.2 Анализ предложенных ситуаций выбора 119
4.2.3 Анализ условий существования построенных механизмов и ситуаций выбора 125
4.3 Апробация и результаты внедрения в сфере социального управления 132
Заключение 138
Список использованных источников
- Модели отсева решений на итерациях поиска, основанные на существующих механизмах выбора
- Разработка моделей и алгоритмов выбора на итерациях поиска
- Обобщение типовых схем выбора
- Анализ предложенных функций выбора
Модели отсева решений на итерациях поиска, основанные на существующих механизмах выбора
Современные системы предметного назначения как правило описываются достаточно большим количеством качественных и количественных признаков, наличием сложных зависимостей между ними. Моделирование и оптимизация параметров и режимов на всех этапах жизненного цикла и на всех уровнях организации, функционирования и управления таких систем представляет собой трудоемкую задачу большой размерности. Одним из путей решения таких задач является привлечение эффективного аппарата многокритериальной оптимизации (МКО).
Использование процедур МКО накладывает ряд организационных и вычислительных ограничений. Так, например перебор большого количества вариантов недоминируемых решений от итерации к итерации ведет к переполнению памяти вычислительной среды, при этом увеличивается время поиска, уменьшается точность полученных решений.
Сведение же исходной векторной формы представление критериев на скалярное, требует теоретического обоснования причин выбора того или иного "главного" критерия или способа построения критериальной свертки, что в свою очередь снижает эффективность получаемого решения и требует подтверждения адекватности полученной скалярной модели [10, 11].
Эффективным способом решения задачи является прямое обобщение известных схем скалярной оптимизации на векторный случай, но здесь возникает проблема неуправляемого роста мощности недоминируемых решений на итерациях поиска, что приводит к необходимости разработки обоснованных процедур отсева [9, 55, 77-82].
Основным недостатком существующих методов отсева решений является то, что отбор части "хороших", с точки зрения поставленной задачи вариантов, как правило основывается на случайном выборе. При этом нет объективных обоснований - почему был сделан выбор той или иной части множества недоминируемых решений. Поэтапный поиск решений и проводимый на нем выбор описывается разнородными способами формализации, привязанными к конкретному используемому методу. Принятие окончательного решения на сформированном множестве недоминируемых альтернатив также затруднено [17, 21, 43-45].
Эти особенности численных схем МКО в свою очередь предъявляют повышенные требования к математическому и программному обеспечению. Очевидно, что наиболее приемлемый путь решения задачи - это использование эффективных процедур, ведущих к повышению качества полученного решения. При этом необходимо проводить обоснованный выбор решений как на итерациях поиска, так и при принятии окончательного решения.
Формализуем математическую модель задачи многокритериального выбора [96]. Пусть есть m исходных вариантов решения, каждый из которых имеет некоторое множество X; eD(i = l,m,D = D, xD2x...xDm) их реализации (х - символ декартового произведения). Каждая реализация варианта X определяется некоторым множеством X - количественных показателей параметров задачи. Выбор конкретного варианта решения связан с определенным значением вектора критериев оптимизации Q = (Q!(X),...,Qn(X)). Например, при описании технологических систем, такими критериями могут быть удельные приведенные затраты, себестоимость единицы выпускаемой продукции, коэффициент готовности линии, коэффициент выхода годных изделий с линии, надежность технологиче ского процесса, уровень механизации и автоматизации, удельный уровень межоперационных заделов, показатели эргономики и эстетики и др. Тогда задача МКО, в общем случае, сводится к модели [96]: Q = (QI(X),Q2(X),...,Qn(X))-3 - Opt, (1.1) D: D,xD2x...xDn, Х = {АІ ХІ ВІ, і = їдп}, г;=(Х;) 0, i = Ui, i = 1,2,3,..., где: Opt - оператор, реализующий некоторый принцип оптимизации; X -вариант решения, определяемый множеством X = (Х„...,ХШ) - технико-экономических, или количественных параметров и задающий параметрические ограничения на область поиска; Q - вектор критериев оптимизации; А, В - параметрические ограничения на область поиска D, представляющую собой множество возможных вариантов решения; f - функциональные ограничения на область D.
При оптимизации по модели (1.1), в условиях реализации ее на ЭВМ, возникает ряд проблемных вопросов, таких как: 1. Гибкая настройка на предметную область, задание в аналитической форме, параметрических и функциональных ограничений в D. 2. Выбор численной схемы оптимизации. Возможное использование произвольных комбинаций схем, для достижения наилучших результатов. 3. Эффективное ограничение роста мощности множества недоминируемых решений на итерациях поиска с минимальной потерей значимых вариантов. 4. Привлечение эффективных методов экстраполяции экспертных оценок не только при принятии окончательного решения, но и непосредственно на итерациях поиска. 5. Выбор направления поиска, с помощью подсистемы управления ходом поиска. Возможное изменение на любой итерации параметров и режимов поиска. 6. Выбор объективного условия окончание поиска. 7. Выделение и ранжирование недоминируемых решений по степени полезности, с использованием экспертных процедур. Разрешение поставленных вопросов связанно с изучением существующих моделей МКО, построением инвариантных с точки зрения поставленной задачи моделей и алгоритмов поиска. С позиций системного подхода [11, 42, 43, 57], можно выделить три основных этапа реализации модели (1.1): 1. Выделение допустимого множества решений, удовлетворяющих ограничениям области D. 2. Выделение из допустимого множества решений подмножества недоминируемых альтернатив. 3. Получение оптимального в некотором смысле решения на недоминируемом множестве альтернатив. Поскольку количество возможных альтернатив очень велико, а между критериями оптимизации возможен конфликт, то на втором этапе приходится решать задачу МКО, с последующим определением окончательного решения на полученном множестве [63].
Разработка моделей и алгоритмов выбора на итерациях поиска
Рассмотрим типовые критерии выбора, наиболее часто встречающиеся при отборе решений на итерациях поиска в моделях МКО, проведем их сравнительный анализ и выделим из них наиболее предпочтительные.
Любое бинарное отношение предпочтения, применяемое для выбора эффективных решений на итерациях поиска, должно базироваться на некотором критерии предпочтения [1-7].
В условиях оптимизации по совокупности критериев наиболее известными в этом смысле являются критерии, построенные на отношении по Парето, по Слейтеру, по Джоффриону и по Борвейну [13-15, 102, 106].
В связи с этим большой интерес представляет вопрос о том, при каких условиях (в каких случаях) понятия эффективности различного типа оказываются эквивалентными, а множества соответствующих оценок и решений - равными. Это объясняется тем, что анализ условий совпадения решений, эффективных в различных смыслах, позволяет оценить степень взаимной близости понятий эффективности разных типов, а также дает возможность прямого переноса того или иного результата, полученного для эффективных решений одного типа на другой.
Известно что для задач с конечным множеством допустимых решений (дискретных задач) понятия оптимальности по Парето, Джоффриону и Борвейну совпадают и являются частным случаем оптимальности по Слей-теру, являются асимметричными и транзитивными, то есть качественным порядком [13-15, 102, 106].
Основываясь на вышесказанном, за основу возьмем наиболее распространенное и изученное отношение предпочтения по Парето. В данном случае для получения искомого оптимального решения поставленной задачи может применяться известная двухэтапная процедура [87-96]: на первом этапе осуществляется численная оптимизация и построение множества эффективных, в смысле некоторого бинарного отношения решений; на втором - выбор из них окончательного результата.
Решение задачи второго этапа связано с проблемами отсева на итерациях поиска неэффективных решений, построением для этих целей функции выбора и функции полезности.
Принципиальным отличием предлагаемой модели от традиционных подходов в разработке процедур принятия компромиссных решений является отказ от принятия аксиоматических установок о возможной значимости частных критериев эффективности.
Это обусловлено тем, что, во-первых, априорное принятие аксиом предполагает затруднения у эксперта мысленно охватить все анализируемое множество альтернатив и кроме того, сделать это до того, как начинается собственно экспертиза. Во-вторых, даже при наличии абсолютно объективных, неискаженных и верно проинтерпретированных аксиоматических установок, они имеют достаточно узкую область адекватности и не могут охватить все возможные варианты сравнения.
Исходя из этого, можно, например, использовать адаптивные модели выбора и принятия решений на конечном множестве Парето - оптимальных альтернатив с использованием экстраполяции экспертных оценок [23, 26, 39, 52-54, 84].
Сущность методов экстраполяции экспертных оценок состоит в том, что по ограниченной выборке альтернативных вариантов, несравнимых по безусловному критерию предпочтений, идентифицируется система экспертных предпочтений с ее последующей экстраполяцией на всю исходную совокупность. Идентификация состоит в определении неизвестных коэффициентов функции полезности, при которых структура экспертных предпочтений или полностью сохраняется, или претерпевает минимальные изменения.
Распространен также подход , состоящий в задании скалярного критерия оптимальности (оценочной функции полезности) [28]. Метод экстраполяции экспертных оценок позволяет построить оценку вектора коэффициентов функции полезности. Эта оценка обладает некоторой погрешностью и в общем случае решение, оптимальное по оценочной функции полезности, не совпадает с истинным оптимальным решением. Поэтому, чтобы максимально увеличить вероятность получения истинного решения, можно отобрать определенное количество лучших вариантов в соответствии с оценочной функцией полезности. Геометрически это означает отсечение некоторого подмножества решений с помощью отсекающей гиперплоскости.
Для сужения множества эффективных решений можно использовать отношение, основанное на функции максимального правдоподобия [52], как наиболее эффективное и в наименьшей степени зависящее от разногласий экспертов.
Рассмотрим теперь, какими свойствами должно обладать бинарное отношение, чтобы его можно было использовать в процессе принятия решений в ситуациях выбора.
Чтобы использовать бинарные отношения для сравнения вариантов из некоторого множества, целесообразно ввести понятия строгого упорядочения и безразличия [39, 48, 56]. Минимальное требование к строгому упорядочению - это асимметричность соответствующего отношения. Из асимметричности бинарного отношения следует его антирефлексивность. Под отношением безразличия будем понимать отношение, исключающее строгое превосходство одного элемента над другим. Отношение безразличия между вариантами может возникнуть в одном из трех случаев: 1. Лицо, принимающее решение (ЛПР), считает, что нет различия (в смысле бинарного отношения) между вариантами х и у. 2. ЛПР не уверен в строгом превосходстве одного из вариантов над другим, в строгом упорядочении вариантов между собой. 3. ЛПР считает варианты х и у несравнимыми между собой.
Отношение безразличия симметрично и рефлексивно. Отношения безразличия и строгого упорядочения определяют весьма грубые подходы к сравнению вариантов и не обладают достаточной определенностью и избирательностью. Для того, чтобы использовать бинарные отношения как инструмент рационального выбора из множества объектов произвольной природы, необходимо наделить отношения дополнительными более жесткими свойствами.
Сузим класс строгих упорядочений, добавляя к свойству асимметричности соответствующего бинарного отношения свойство негатранзи-тивности. Полученное отношение называется слабым порядком [102, 106]. Примером слабого порядка является отношение "больше" на любом подмножестве вещественной прямой. Отношение слабого порядка индуцирует отношение эквивалентности - рефлексивное, симметричное и транзитивное, то есть транзитивное отношение безразличия.
Обобщение типовых схем выбора
Предлагаются более эффективные способы выбора: 1. Выбор точек из внешнего программного модуля, с помощью разрабо танной технологии "FastLink"; 2. Выбор точек с участием ЛПР, для чего специально разработана подсистема контроля ЛПР за процессом поиска и предложен новый механизм выбора по экстраполяции, основанный на принципе экстраполяции экспертных оценок. 3. Выбор контрастных точек. Предлагается новый механизм выбора, основанный на формуле Штойера [103], для расчета координат наиболее "контрастных" точек, которая не использовалась ранее для решения данной задачи. Сам алгоритм выбора контрастных точек можно формализовать в виде: 1. Выбор начальной точки Xj и количества решений, которые необходимо оставить. 2. Перебор всех остальных точек Хь Х2, ... , Х;_ь Xj+i, ... , Xm и вычисления расстояний до X;, которые обозначим вектором R, т.е. Ri, К2, ..., Rra-l 3. Нахождение максимального расстояния R1 = max {Rk} и k=l,..,,m-l запоминание соответствующей точки Xj. 4. Выбор очередной j - й точки, кроме отобранных, перебор остальных точек Хь Х2, ..., Xm_j и вычисления расстояний до каждой из отобранных на предыдущем шаге Rb R2, ... , Rm-j 5. Нахождение максимального расстояния до всех выбранных точек RJ = max {Rk} и запоминание соответствующей точки х;. 1 k=l..m-j 6. Повторение шагов 4 и 5 ведется до тех пор, пока не будет выбрано заранее заданное количество решений, заданное на шаге 1. На четвертом шаге (рис. 2.2) строятся последовательности точек, группирующихся вокруг полученных на первом шаге решений.
Строятся последовательности точек, распределенных по нормальному закону. Их координаты, согласно методу перераспределения плотности вероятности, рассчитываются по формуле [94]: где SR(I) - среднеквадратическое отклонение для і - й переменной; АМ(1) - математическое ожидание для 1-й переменной; Rj - последовательность случайных чисел, равномерно распределенных в интервале от 0 до 1.
За математические ожидания принимают значение элементов из множества Парето, полученного на предыдущем этапе. Для этой цели можно использовать процедуры выбора из 3-го шага.
Среднеквадратическое отклонение на первом шаге полагается равным: SR(I) = (Xmax- Xmin)/3.
Это позволяет с равной вероятностью попасть в любую точку области поиска. На каждом последующем шаге итерации среднеквадратическое отклонение уменьшается по линейному закону: SR(i)k+1 = 0.8 SR(i)k.
Условием пока окончания уменьшения значения считается пороговая величина 0.06 (Xmax-Xmil)).
На этом этапе возникает проблема роста мощности множества недоминируемых решений, т.к. размерность Парето растет с каждой итерацией.
Стандартный вариант метода предлагает случайный отсев. Достоинства и недостатки такого подхода, представленного в виде механизма случайного отсева были рассмотрены ранее. Для улучшения качества получаемого решения и уменьшения времени поиска, предлагаются другие варианты: 1. Выбор точек из внешнего программного модуля, с помощью предложенной в 4 главе технологии "FastLink". 2. Отсев на базе механизма выбора контрастных точек. 3. Отсев с помощью ЛПР, на базе механизма экспертного выбора. 4. Отсев на базе скалярного оптимизационного механизма выбора. На пятом шаге (рис. 2.2) проверяется условие окончания поиска.
Поиск считается завершенным, если множества Парето не улучшилось с точки зрения поставленной задачи за заданное количество раз.
В противном случае идет переход на второй шаг и следующая итерация метода. Предлагается также подключение других критериев остановки процесса: 1. Внешний критерий, подключаемый к программному комплексу с помощью предложенной в 4 главе технологии "FastLink". 2. Человеко-машинные методы экспертных оценок. Как уже ранее отмечалось, рассматриваемое недоминируемое множество решений является необозримым для ЛПР.
Для дальнейшего его сужения рассмотрим принципиальную схему решения, в которой на каждой итерации предусматривается последовательное выполнение следующих процедур, соответствующих модели экстраполяции на базе функции максимального правдоподобия (рис.2.3).
Учитывая результаты работы на подмножестве YM механизма выбора MQ , экспертом принимается решение либо об остановке итерационного процесса решения задачи и окончательном выборе HaYM, либо о продолжении итерационного процесса.
Для проведения экспертного опроса на і-й итерации генерируется новая ограниченная выборка (обозначим Xі), Xі cYM" , где Y "1 - результат работы многоэкстремально- экстремизационного механизма М на (i-l) - ой итерации поиска оптимального решения. Причем, имея результат ра боты однокритериально - экстремизационного механизма М30 на множе стве Y , рекомендуется, чтобы выборка Xі содержала альтернативы, ко торые не являются эквивалентными с точки зрения эксперта. На вновь сформированной ограниченной выборке Xі проводится экспертный опрос и далее весь описанный процесс повторяется. Заметим, что на каждой итерации возможно ранжирование (упорядочивание) альтернатив на множестве YM, используя при этом структуру а однокритериально - экстремизационного механизма М : и0 = о х, где а0 - точечная оценка коэффициентов функции полезности. Тогда результат полученного ранжирования на Хпар используется при принятии решения об остановке данного итерационного процесса. Проведенные сравнения [88, 92, 93] метода экстраполяции с использованием построения функции максимального правдоподобия показали, что при отсутствии разногласий в мнениях экспертов, либо когда ранжирование проводится одним экспертом (ЛПР), он вырождается в метод экстраполяции по вектору. В этом случае он дает более точные оценки при построении направляющего конуса, а именно A(XJ+1-XJ) Зет, вместо A(Xj+,-Xj) 0.
С другой стороны он основан на вероятностных расчетах (построение функции L(A)), а значит его использование возможно при условии, когда в работе участвует достаточная по количеству экспертная группа. Однако метод устойчиво работает при имеющихся существенных разногласиях экспертов, даже в случае несовместных систем неравенств A(Xj+1-Xj) О, что проблематично выполнить другими методами.
Таким образом идеальными условиями применимости метода экстраполяции на основе построения функции максимального правдоподобия -это выбор ограниченной совокупности экспертной группой, имеющей 3-7 человек. Привлечение этого метода на итерация поиска в виде механизма экспертного выбора, предложено впервые и позволило существенно улучшить качество получаемых проектных решений, более объективно произвести коррекцию поиска и выбор окончательного решения, что подтверждено практическими экспериментами.
Анализ предложенных функций выбора
В качестве условий применимости обязательным условием является наличие информации о критериях оптимизации, которой должно быть достаточно для того, чтобы можно было выделить "главный" критерий, а на остальные назначить критериальные ограничения.
Анализ механизма выбора по экстраполяции. Этот механизм выбора предполагает наличие вектора относительной важности критериев, который формируется при участии ЛПР.
После проведения к - итераций, с последовательным отсевом на каждой из них получаем искомое множество вариантов решения: X с MExtra(Xk) с МЕ СХ 1) С MExtra(Xk-2) с ... с ME.UX1) с X. Искомая область поиска X достигалась в среднем через к = 46 итераций. Графическая интерпретация эксперимента приведена на (рис. 4.17). Здесь график [2] - результат работы механизма выбора по экстрапо 114 ляции. Как видно из графика полученные результаты применения механизма выбора по экстраполяции [2] обеспечивают сходимость численной схемы перераспределения плотности вероятности, так как попадают в исходную область поиска [3], давая приемлемую точность сравнения с тестовым графиком решения [1].
Таким образом предложенный механизм выбора по экстраполяции MExtra, порождающий функцию выбора по экстраполяции, для отсева решений на итерация поиска экспериментально подтвердил адекватность модели (4.1). В качестве условий применимости можно выделить наличие опытного ЛПР или экспертной группы, а также разработанных человеко-машинные процедур.
Анализ механизма выбора контрастных точек. Следует отметить, что предлагаемый подход является одним их наиболее объективных, "машинных" способов отсева, так как охватывает всю область поиска и позволяет анализировать даже удаленные от основного скопления точки. Это позволяет свести к минимуму потери "значимых" точек. В тоже время, реализация алгоритма громоздка и существенно снижает скорость поиска, накладывая ограничения на мощность вычислительной среды.
Здесь график [2] - результат работы механизма выбора контрастных точек. Как видно из графика полученные результаты применения механизма выбора контрастных точек [2] обеспечивают сходимость численной схемы перераспределения плотности вероятности, так как попадают в исходную область поиска [3], давая приемлемую точность сравнения с тестовым графиком решения [1].
Таким образом предложенный механизм выбора контрастных точек Mcontrs порождающий функцию выбора контрастных точек, для отсева решений на итерация поиска экспериментально подтвердил адекватность модели (4.1). Данный механизм выбора можно предложить, если вычислительные возможности позволяют проводить детальный анализ области решения D, а временной фактор несущественен. Анализ случайного механизма выбора. После проведения к - итераций, с Искомая область поиска X достигалась в среднем через к = 65 итераций. Графическая интерпретация эксперимента приведена на рисунке (рис. 4.19). Здесь график [2] -результат
Как видно из графика полученные результаты применения случайного механизма выбора [2] обеспечивают сходимость численной схемы перераспределения плотности вероятности, так как попадают в исходную область поиска [3], давая приемлемую точность сравнения с тестовым графиком решения [1].
Таким образом предложенный механизм случайного выбора MRand, порождающий случайную функцию выбора, для отсева решений на итерация поиска экспериментально подтвердил адекватность модели (4.1). Данный механизм выбора, основанный на случайном отсеве, можно рекомен 117 довать в ситуациях, когда требуется принять решение в кратчайшие сроки и с минимальными затратами вычислительной среды, причем качество полученного решения не играет существенной роли.
Обобщим проведенные исследования и исследуем - в каких ситуациях выбора можно предложить тот или иной механизм отсева на итерациях поиска.
Приведем результаты машинного эксперимента, с отображением исходной области поиска и начальным построением множества вариантов для выбора (рис. 4.20-4.22).
Здесь график [1] - результат оптимизации на тестовом примере; график [2] - скалярный оптимизационный механизм выбора; график [3] - Па-ретовский механизм выбора; график [4] -механизм выбора контрастных точек; график [5] - случайный механизм выбора; график [6] - область поиска D, масштабированная на графике в области полученных решений.
Наложение полученных графиков также позволяет уверенно говорить, что все рассмотренные механизмы, при решении задачи на минимум, обеспечивают сходимость (попадают в нижнюю границу исходной области поиска D), подтверждают адекватность модели (4.1) и могут быть использовании для отсева решений на итерациях поиска в моделях МКО, а нижняя граница построенных графиков отображает оптимальную последовательность используемых механизмов выбора, для получения наилучшего решения модели (4.1).
Эксперимент будем проводить при тех же начальных условиях, что и разделе 4.2.1, но теперь будем проводить анализ сходимости предложенных во второй главе функций выбора, в зависимости от построенных в третьей главе ситуаций выбора. В главе 3 было предложено 5 ситуаций выбора, используемых на итерациях поиска в моделях МКО:
На (рис 4.23, 4.24) приведены зависимости сходимости модифицированного алгоритма перераспределения плотности вероятности, с использованием на итерациях поиска различных СВ, от времени решения задачи и точности полученных результатов.
Здесь и в дальнейшем: график [1] - последовательная ситуация выбора; график [2] - параллельная ситуация выбора; график [3] - ситуация выбора для расходящихся процессов; график [4] - ситуация выбора для сход, процессов; график [5] - ситуация выбора с уточнением;
