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

dmitry_moor@mail.ru
karpenko@nog.ru
D.Mukhlisullina@mail.ru

МГТУ им. Н.Э.Баумана

Введение

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

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

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

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

, .

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

            В работе [2] предложен класс прямых адаптивных методов решения МКО-задачи, основанных на аппроксимации функции предпочтений ЛПР . Использование нейронных сетей для аппроксимации функции  рассмотрено в работах [3, 4]. В данной работе аппроксимация функции предпочтений ЛПР  выполняется с помощью аппарата нейро-нечеткого вывода ANFIS (AdaptiveNeuro-FuzzyInferenceSystem) [5].

            Гибридные нейро-нечеткие системы находят существенно более широкую область применения, чем другие методы синтеза нечетких множеств и нейронных сетей [5]. Это связано с тем, что такие системы позволяют наиболее полно использовать «сильные» стороны нечетких систем (интерпретируемость накопленных знаний) и нейронных сетей (способность обучаться на данных). Характерной чертой гибридных систем является то, что они всегда могут быть рассмотрены как системы нечетких правил, при этом настройка функций принадлежности в предпосылках и заключениях правил на основе обучающего множества производится с использованием алгоритмов обучения нейронных сетей. Такие системы не только используют априорную информацию, но могут приобретать новые знания, являясь логически «прозрачными».

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

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

                Пусть X - вектор варьируемых параметров задачи. Множеством допустимых значений вектора Xявляется ограниченное и замкнутое множество , где  - «технологический» параллелепипед допустимых значений вектора параметров; множество  формируют ограничивающие функции , так что ;  - n-мерное арифметическое пространство.

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

, ,                                            (1)

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

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

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

,  .                                       (2)

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

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

.

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

, .                                             (3)

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

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

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

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

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

, .                                     (4)

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

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

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

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

, , ;                            (5)

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

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

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

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

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

, ;

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

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

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

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

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

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

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

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

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

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

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

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

ЕСЛИ  и  И … И  ИЛИ

 и  И … И  ИЛИ

……….

 И И … И , ТО .

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

, .

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

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

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

где  - веса нечетких правил;  - символы логических операций «ИЛИ», «И»;  - функция принадлежности весового множителя  терму .

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

            3) Активизация - нахождение степени истинности каждого из подзаключений правил нечетких продукций. Во-первых,  находятся значения степеней истинности  всех заключений правил нечетких продукций. Это выполняется с использованием метода  min-активизации. Во-вторых, осуществляется расчет обычных (не нечетких) значений выходных переменных каждого правила.

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

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

.

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

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

Система вывода ANFIS реализуется в виде нейроподобной структуры, состоящей из пяти слоев (рис. 1).

Рис. 1. Структура нейро-нечеткой сети ANFIS

Нейроны первого слоя служат для представления термов входных переменных. При конкретных (заданных) значениях входов на выходе слоя формируются значения функций принадлежности .

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

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

Четвертый слой предназначен для вычисления заключений правил. Здесь

,

где – набор параметров данного слоя (так называемые параметры вывода).

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

Для обучения сети ANFIS в работе используется гибридный градиентный метод_[5].

Для оценки погрешности нечеткой нейронной сети строится функция ошибки

, ,                 (6)

представляющая собой среднеквадратическое отклонение между фактическими значениями выходной переменной  и точечной оценкой , полученной на основе нечеткого вывода. Здесь a, b – параметры функций принадлежности первого слоя нечеткой нейронной сети; p, q, r– параметры четвертого слоя нечеткой нейронной сети.

3.3 Генерация нечетких правил. В процессе решения задачи система вывода ANFISимеет возможность приобретать новые знания, поэтому база знаний не остается фиксированной, а модернизируется по мере поступления экспериментальных данных. Поэтому топология нечеткой нейронной сети также меняется по мере приобретения новых знаний. Для модификации топологии нечеткой нейронной сети используется процедура, предложенная в работе [5].

Пусть исследуемый объект имеет на входе n-мерный вектор , на выходе - число y. Пусть кроме того «истинное» описание объекта имеет вид

,

где f(x) – неизвестная функция, e– случайная аддитивная помеха. Предположим, что может быть реализован эксперимент, заключающийся в регистрации Nнаборов значений , i=1,…,N. При этом компоненты вектора x, измеряются без ошибок, значение величины N при необходимости допускает модификацию.

Алгоритм построения системы вывода ANFISимеет следующий вид.

ШАГ 1. Из m, (m < N) произвольных наборов значений  составляется начальная база знаний модели.

ШАГ 2. Для каждого нового экспериментального набора  определяется прогнозируемое значение  величины y.

ШАГ 3. Проверяется неравенство

,

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

ШАГ 4. Проверяется выполнение правила останова. Если это правило выполнено, то алгоритм завершается; если правило не выполнено, алгоритм переходит к шагу 2.

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

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

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

;    ;

.

            Задача 2. Двухкритериальная задача 2 (невыпуклый фронт Парето) [8]:

; ;

;

.

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

;       ;

;  

.

Частные критерии оптимальности нормализованы следующим образом:

.

Здесь , ; , .

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

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

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

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

·          -ошибка аппроксимации, вычисляемая по формуле (6).

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

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

            Процесс решения задачи иллюстрирует таблица 1, где  - номер итерации, серым цветом выделены «разгонные» итерации; .

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

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

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

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

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

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

На рис. 4 представлена структура полученной нейро-нечеткой сети ANFIS. Здесь и далее для удобства слой 2 и слой 3 (см. рис. 1) объединены в один слой, узлы которого показаны синими кружками.

Рис. 4. Структура нейро-нечеткой сети ANFIS

            4.2 Задача 2 (МКО-задача 2). На рис. 5 представлено критериальное множество МКО-задачи 2. В процессе экспериментов ЛПР полагало, что «отличным» значениям его функции предпочтений соответствуют следующие значения критериев оптимальности: , .

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

Решение этой задачи потребовало семь итераций (для сравнения, в работе [7] для этого потребовалось 11 итераций). Процесс решения задачи иллюстрирует таблица 2, а результат решения – рис. 6. В данной задаче количество узлов первого слоя получилось равным семи (рис. 7).

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

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

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

            На рис.7 представлена структура полученной нейро-нечеткой сети ANFIS.

Рис.7. Структура нейро-нечеткой сети ANFIS

4.3 Задача 3 (МКО-задача 3). Критериальное множество МКО-задачи 3 представлено на рис. 8.

            При  «разгонных» точках решение задачи потребовало девять итераций (в исследовании [7] решение этой же задачи потребовало 14 итераций). Процесс решения задачи иллюстрирует таблица 3. Вид функции  после 13 итераций представляет рис. 9 (напомним, что ). На рис. 10 изображены линии уровня этой функции.

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

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

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

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

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

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

На рис. 11 изображена структура полученной нейро-нечеткой сети ANFIS.

Рис.11. Структура нейро-нечеткой сети ANFIS

На рис. 12 показана зависимость времени выполнения одной итерации алгоритма от номера итерации. Из рисунка видно, что время выполнения итерации слабо зависит от ее номера. Здесь левая шкала относится к МКО-задаче 3, правая шкала – к МКО-задаче 1 и МКО-задаче 2.

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

Заключение

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

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

Литература

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

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

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

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

5.      Круглов В.В. Искусственные нейронные сети. Теория и практика / В.В. Круглов, В.В. Борисов.- М.: Горячая линия – Телеком, 2002. – 382 с.

6.      Черноруцкий И.Г. Методы принятия решений / И.Г. Черноруцкий. – СПб.: БХВ-Петербург, 2005.-416 с.

7.      Карпенко А.П. Многокритериальная оптимизация на основе нечеткой аппроксимации функции предпочтений лица, принимающего решения / А.П. Карпенко, Д.А. Моор, Д.Т. Мухлисуллина // Электронное научно-техническое издание: наука и образование.-2010.- ╧1 (http://technomag.edu.ru/doc/135375.html).

8.      Лобарева И.Ф. Многоцелевая оптимизация формы лопасти гидротурбины / И.Ф. Лобарева, С.Г. Черный, Д.В. Чирков, В.А. Скороспелов, П.А. Турук // Вычислительные технологии, Том 11, ╧5, 2006. С.63 – 76.

9.      Леоненков А. Нечеткое моделирование в среде MATLAB и FuzzyTECH / А. Леоненков.- СПб.: БВХ-Петербург, 2005.- 736 с.

10.  Штовба С.Д. Введение в теорию нечетких множеств и нечеткую логику / С.Д. Штовба.- Режим доступа: http//www.matlab.exponenta.ru, свободный.

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