НАУКА и ОБРАЗОВАНИЕ

УДК 519.6

МГТУ им. Н.Э. Баумана, 105005, Москва, 2-я Бауманская ул., д.5.,
 тел.: (499)263-65-26,

E-mail: karpenko@nog.ru,
 dmitry_moor@mail.ru,
D.Mukhlisullina@mail.ru

Введение

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

         По характеру информации, получаемой МКО-системой от ЛПР на фазе анализа, выделяются несколько классов адаптивных методов. В работе рассматриваются прямые адаптивные методы [1], в основе которых лежит предположение, что ЛПР может непосредственно выполнять оценку (например, в терминах «лучше», «хуже», «одинаково») предлагаемых МКО-системой альтернатив.

         Прямой адаптивный метод решения МКО-задачи, который исследуется в данной работе, основан на предположении существования «функции предпочтений ЛПР» , которая определена на множестве  допустимых значений вектора варьируемых параметров  и выполняет отображение этого множества на множество действительных числе R. При этом задача многокритериальной оптимизации сводится к задаче выбора вектора  такого, что

, .

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

         В работе [2] предложен класс прямых адаптивных методов решения МКО-задачи, основанных на аппроксимации функции . Использование для аппроксимации функции  нейронных сетей рассмотрено в работах [3, 4]. В данной работе рассматривается использование для этой цели аппарата нечеткой логики [5].

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

1. Постановка МКО-задачи

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

 -

«технологический» параллелепипед допустимых значений вектора параметров; множество  формируют ограничивающие функции , так что

;

 - n-мерное арифметическое пространство.

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

, ,                                (1)

где  - искомое решение МКО-задачи. Частные критерии оптимальности полагаются нормализованными (тем или иным образом), так что , .

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

         При каждом фиксированном векторе  метод скалярной свертки сводит решение задачи (1) к решению однокритериальной задачи глобальной условной оптимизации (ОКО-задачи)

, .                          (2)

         Отметим, что в случае аддитивной свертки  вектор  принадлежит множеству эффективных по Парето векторов [1]. Для произвольной скалярной свертки вектор , полученный в результате решения задачи (2), вообще говоря, не принадлежит множеству Парето.

         Ограничимся случаем, когда множество достижимости  задачи (1) является выпуклым. В этом случае при каждом  решение задачи (2) единственно, и это решение ставит в соответствие каждому из допустимых векторов  единственный вектор , а также соответствующие значения частных критериев оптимальности  [1]. Данное обстоятельство позволяет полагать, что в этом случае функция предпочтений ЛПР определена не на множестве , а на множестве :

.

В результате МКО-задача сводится к задаче выбора вектора  такого, что

, .                                (3)

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

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

Отметим, что если вместо аддитивной свертки используется свертка Джоффриона, то взаимно однозначное отображение множества  на множество  имеет место и в случае, когда множество достижимости  не является выпуклым [6].

         Величину  будем считать лингвистической переменной со значениями от «Очень-очень плохо» до «Отлично». Ядро нечеткой переменной  обозначим [7], так что значению переменной  «Очень-очень плохо» соответствует , а значению «Отлично» - .

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

, .                                   (4)

2. Метод решения задачи

         Общая схема рассматриваемого метода является итерационной и состоит из перечисленных ниже следующих основных этапов [2].

         Этап «разгона» метода. МКО-система некоторым образом (например, случайно) последовательно генерирует  векторов  и для каждого из этих векторов выполняет следующие действия:

         1) решает ОКО-задачу

, , ;                         (5)

         2) предъявляет ЛПР найденное решение , а также соответствующие значение всех частных критериев оптимальности ;

         3) ЛПР оценивает эти данные и вводит в МКО-систему соответствующее значение своей функции предпочтений .

         Первый этап. На основе всех имеющихся в МКО-системе значений  вектора  и соответствующих оценок функции предпочтений  МКО-система выполняет следующие действия:

         1) строит функцию , аппроксимирующую функцию  в окрестности точек ;

         2) отыскивает максимум функции  – решает задачу

, ;

         3) с найденным вектором  решает ОКО-задачу вида (5) – находит вектор параметров и соответствующие значения частных критериев оптимальности, а затем предъявляет их ЛПР; ЛПР оценивает указанные данные и вводит в систему соответствующее значение своей функции предпочтений .

         Второй этап. На основе всех имеющихся в системе значений  вектора  и соответствующих оценок функции предпочтений  МКО-система выполняет аппроксимацию функции  в окрестности точек - строит функцию  и т.д. по схеме первого этапа до тех пор, пока ЛПР не примет решение о прекращении вычислений.

         На каждой итерации ЛПР может выполнить «откат» с целью изменения введенных ранее оценок своей функции предпочтений [3].

3. Алгоритм и программная реализация метода

         Входами системы нечеткого вывода являются значения весов частных критериев оптимальности – нечеткие термы , , . Выходной переменной системы нечеткого вывода является лингвистическая переменная , ядро которой  принимает значения 1, 2,…, 9.

         Взаимосвязь между входными и выходными переменными описывается нечеткими правилами вида

ЕСЛИ <значения входных переменных> ТО

<значение выходной переменной> .

Здесь  - коэффициенты определенности (веса нечетких правил), полагающиеся равными 1 в случае их неопределенности.

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

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

         3.1. Шаг 1. Положим, что выполнено  экспериментов по определению значений лингвистической переменной . Пусть в  этих экспериментов переменная  приняла значение , в  опытах - значение  и т.д. до  и . Соответствующие входные векторы  обозначим , где , .

         Матрицу знаний  можно представить в виде следующей системы логических высказываний

ЕСЛИ  и  и … и  или

 и  и … и  или

……….

 и и … и ,ТО .

         С использованием операций объединения и пересечения множеств эта система высказываний может быть переписана в более компактном виде

, .

Во введенных обозначениях нечеткий логический вывод включает в себя следующие операции [5].

         1). Фазификация. Для данного вектора  определяем значение многомерной функции принадлежности

где  - веса нечетких правил;  - символы логических операций ИЛИ, И;  - функция принадлежности весового множителя  терму . Веса  определяются с помощью модифицированного правила экспоненциального возрастания весов: . Здесь  - свободный параметр алгоритма, а величина  находится из условия .

         2). Агрегирование - определение степени истинности условий по каждому из правил системы нечеткого вывода. При вычислении значений функции принадлежности  в качестве операций “И”, “ИЛИ”, “импликация” используем операции min, max, prod соответсвенно.

         3). Активизация - нахождение степени истинности каждого из подзаключений правил нечетких продукций.

         4). Аккумуляция - нахождение функции принадлежности для каждой из выходных лингвистических переменных.

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

         3.2. Шаг 2. Тонкая настройка модели  (параметрическая идентификация модели) осуществляется путем подбора следующих параметров:

·              полуширина  функций принадлежности входных переменных ;

·              полуширина  функций принадлежности выходных переменных ;

·              величина , определяющая закон изменения весовых множителей .

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

, , .

         В качестве критерия оптимальности параметров  используется критерий

, ,

где  - экспериментальное выходное значение нечеткой модели в точке  (т.е. результат нечеткого логического вывода Мамдани в этой точке).

         Таким образом, формально задача параметрической идентификации формулируется в виде следующей задачи глобальной многомерной условной оптимизации [2]

, .                   (6)

         Вообще говоря, задача (6) должна решаться на каждой итерации рассматриваемого метода (п. 2).

         Замечание. Для параметрической идентификации модели  на этапе «разгона» метода может быть использована дополнительная тестовая выборка из некоторого количества допустимых векторов . Однако такой подход требует от ЛПР принятия значительного количества «лишних» решений и в данной работе не рассматривается.

         3.3. Программная реализация метода. Метод реализован в виде MatLab [7-9] программы PREP-FAZZY. Для решения задач (2), (3), (6) программа использует метод последовательного квадратичного программирования SQP, в котором градиенты целевой функции вычисляются численно с использованием конечных разностей этой функции. Поскольку, как отмечалось выше, все указанные задачи являются, вообще говоря, многоэкстремальными, используется комбинация SQP-метода с методом мультистарта: при решении задач (2), (3) используется 100 случайных начальных точек, равномерно распределенных в областях ,  соответственно; при решении задачи (6) – 30 аналогичных случайных точек, равномерно распределенных в области .

         В качестве критерия окончания поиска в SQP-методе используется относительный критерий вида

,

где  – конечное допустимое положительное отклонение по значению минимизируемой функции . 

4. Оценка эффективности метода

         Исследование выполнено для двух двумерных двухкритериальных задач и одной двумерной трехкритериальной тестовых МКО-задач:

         - двухкритериальная задача 1, имеющая выпуклый фронт Парето,

; ; ;

         - двухкритериальная задача 2 (невыпуклый фронт Парето) [10]

; ;

; ;

         - трехкритериальная задача 3 (выпуклый фронт Парето)

; ;

; .

         Использовались нормированные частные критерии оптимальности

,

где , ; , .

         Приняты следующие обозначения:

         , ,  - времена решения задач (2), (3), (6) соответственно;

          - прочее время;

          - время выполнения одной итерации метода; =+++.

         Эксперименты выполнены на персональном компьютере, имеющем следующие значения основных параметров: процессор - IntelCore2 DuoE8400, 3.00 Ггерц, оперативная память - 2.00 Гбайт.

         4.1. МКО-задача 1. Критериальное множество МКО-задачи 1 представлено на рис. 1. Исследование выполнено для  «разгонных» значений  вектора . В процессе экспериментов ЛПР полагало, что «отличным» значениям его функции предпочтений соответствуют следующие значения критериев оптимальности: , .

Рис. 1. Множество достижимости  МКО-задачи 1

         При  «разгонных» точках решение задачи потребовало 12 итераций (здесь и далее в число итераций включаются и «разгонные» итерации). Процесс решения задачи иллюстрирует таблица 1, где  - номер итерации, серым цветом выделены «разгонные» итерации; .

         Вид функции  после 12 итераций представляет рис. 2. Здесь и далее светлые кружки соответствуют значениям функции предпочтений ЛПР на промежуточных итерациях метода, а темный кружок – на последней итерации.

Таблица 1. Результаты решения МКО-задачи 1 ()

Рис. 2. Функция предпочтений ЛПР :

МКО-задача 1; число «разгонных » точек ; 12-я итерация

         При  «разгонных» точках решение задачи потребовало 16 итераций. Процесс решения задачи иллюстрирует таблица 2, а результаты - рис. 3.

Таблица 2. Результаты решения МКО-задачи 1 ()

Рис. 3. Функция предпочтений ЛПР :

МКО-задача 1; число «разгонных » точек ; 16-я итерация

         Аналогичные результаты для  «разгонных» точек представлены в таблице 3 и на рис. 4.

Таблица 3. Результаты решения МКО-задачи 1 ()

Рис. 4. Функция предпочтений ЛПР :

МКО-задача 1; число «разгонных » точек ; 11-я итерация

         Представляет интерес также характер зависимости времени выполнения одной итерации  от номера итерации (рис. 13).

         Приведенные результаты исследования показывают, что для первой МКО-задачи аппроксимация функции предпочтений ЛПР с помощью нечеткой логики позволяет быстро найти решение задачи с приемлемой точностью. Так при  «разгонных» точках решение задачи потребовало всего 12 итераций. Увеличение количества «разгонных» точек практически не увеличивает точность решения задачи, а также требуемое количество итераций. Заметим, что решение той же задачи с помощью нейросетевой аппроксимации функции предпочтений ЛПР позволяет найти решение всего за 5 итераций [3].

         4.2. МКО-задача 2. Критериальное множество МКО-задачи 2 представлено на рис. 5.

Рис. 5. Множество достижимости  МКО-задачи 2

         Исследование также выполнено для  «разгонных» значений вектора . В процессе экспериментов ЛПР полагало, что «отличным» значениям его функции предпочтений соответствуют следующие значения критериев оптимальности: , .

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

         Аналогичные результаты для  и  «разгонных» точек приведены в таблицах 5, 6 и на рисунках 7, 8.

Таблица 4. Результаты решения МКО-задачи 2 ()

Рис. 6. Функция предпочтений ЛПР :

МКО-задача 2; число «разгонных » точек ; 14-я итерация

Таблица 5. Результаты решения МКО-задачи 2 ()

Рис. 7. Функция предпочтений ЛПР :

МКО-задача 2; число «разгонных » точек ; 12-я итерация

Таблица 6. Результаты решения МКО-задачи 2 ()

Рис. 8 Функция предпочтений ЛПР :

МКО-задача 2; число «разгонных » точек ; 14-я итерация

         Характер зависимости времени выполнения одной итерации  от номера итерации иллюстрирует рис. 13.

         Результаты исследования показывают, что для второй МКО-задачи аппроксимация функции предпочтений ЛПР с помощью нечеткой логики позволяет найти решение задачи с приемлемой точностью за 12 – 14 итераций. Так же, как для МКО-задачи 1, увеличение количества «разгонных» точек практически не увеличивает точность решения задачи и требуемое количество итераций.

         4.3. МКО-задача 3. Критериальное множество МКО-задачи 3 представлено на рис. 9. Исследование, как и в предыдущих пунктах, выполнено для  «разгонных» значений вектора .

         При  «разгонных» точках решение задачи потребовало 17 итераций. Процесс решения задачи иллюстрирует таблица 7. Вид функции  после 17 итераций представляет рис. 10 (напомним, что ).

         Аналогично, для  «разгонных» точек потребовалось 11 итераций, а для  - 16 итераций. Соответствующие результаты представлены в таблицах 8, 9, а также на рис. 11, 12.

Рис. 9. Множество достижимости  МКО-задачи 3

Таблица 7. Результаты решения МКО-задачи 3 ()

Рис. 10. Линии уровня функции предпочтений ЛПР :

МКО-задача 3; число «разгонных » точек ; 17-я итерация

Таблица 8. Результаты решения МКО-задачи 3 ()

Рис. 11. Линии уровня функции предпочтений ЛПР :

МКО-задача 3; число «разгонных » точек ; 11-я итерация

Таблица 9. Результаты решения МКО-задачи 3 ()

Рис. 12. Линии уровня функции предпочтений ЛПР :

МКО-задача 3; число «разгонных » точек ; 16-я итерация

         Зависимость времени выполнения одной итерации  от номера итерации представлена на рис. 13.

         Результаты исследования показывают, что для третьей МКО-задачи аппроксимация функции предпочтений ЛПР с помощью нечеткой логики позволяет найти решение задачи за 11 – 17 итераций. Увеличение количества «разгонных» точек мало влияет на точность решения задачи и требуемое количество итераций. Нейросетевая аппроксимация функции предпочтений ЛПР в МКО-задаче 3 позволяет, в лучшем случае, найти решение задачи за 8 итераций (включая 7 «разгонных» итераций).

Рис. 13. Время выполнения одной итерации  как функция номера итерации

Заключение

         Разработан прямой адаптивный метод решения МКО – задачи, основанный на нечеткой аппроксимации функции предпочтений ЛПР. Выполнено исследование эффективности метода, показавшее перспективность его развития. Метод реализован в виде MatLabпрограммы PREF-FUZZY.

         Результаты исследования показывают, что для всех трех рассмотренных МКО-задач аппроксимация функции предпочтений ЛПР с помощью нечеткой логики позволяет найти решение задачи не более чем за 17 итераций. При этом увеличение количества «разгонных» точек мало влияет на точность решения задачи и требуемое количество итераций. На каждой итерации большая часть времени уходит на решение задач (4), (6) - на поиск максимума функции предпочтений ЛПР и поиск минимума функции ошибки аппроксимации соответственно. Этот факт объясняется тем, что вычисление значений двух последних функций требует большего количества вычислений на пути

фазификацияàагрегированиеàактивизацияàаккумуляцияàдефаззификация.

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

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

         В развитии работы предполагается исследовать эффективность использования сверток , отличных от рассмотренной в работе аддитивной свертки.

         Авторы благодарят Федорука В.Г. за плодотворное обсуждение работы, а также ценные советы по ее совершенствованию.

Литература

1.           Лотов, А.В. Введение в экономико-математическое моделирование / А.В.Лотов.– М.: Наука, 1984.- 392 с.

2.           Карпенко, А.П. Один класс прямых адаптивных методов многокритериальной оптимизации / А.П.Карпенко, В.Г.Федорук // Информационные технологии.- 2009.- ╧5.- С.24-30.

3.           Карпенко, А.П. Нейросетевая аппроксимация функции предпочтений лица, принимающего решения, в задаче многокритериальной оптимизации / А.П.Карпенко, Д.Т.Мухлисуллина, В.А.Овчинниокв // Информационные технологии.- 2010.- (в печати).

4.           Мухлисуллина, Д.Т. Исследование погрешности нейросетевой аппроксимации функции предпочтений лица, принимающего решения. [Электронный ресурс] / Д.Т.Мухлисуллина // Электронное научно-техническое издание: наука и образование. - 2009.- ╧12. (http://technomag.edu.ru/).

5.           Ротштейн, А.П. Интеллектуальные технологии идентификации: нечеткая логика, генетические алгоритмы, нейронные сети / А.П. Ротштейн.- Винница: УНИВЕРСУМ-Винница, 1999.- 320 с.

6.           Штойер, Р. Многокритериальная оптимизация. Теория, вычисления и приложения / Р.Штойер.– М.: Радио и связь, 1992.- 504 с.

7.           Леоненков, А. Нечеткое моделирование в среде Matlab и fuzzyTECH / А.Леоненков.- СПб: БХВ-Петербург, 2005.- 719 с.

8.           Дьяконов, В.П. MATLAB 7.*/R2006/2007. Самоучитель / В.П.Дьяконов.- М.: ДМК-Пресс, 2008.- 768 с.

9.           Трифонов, А.Г. Optimization Toolbox 2.2 Руководство пользователя / А.Г.Трифонов [Электронный ресурс]. (http://matlab.exponenta.ru/optimiz/book_1/index.php).