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

Размещено на http: //www. allbest. ru/

МГТУ им. Н.Э. Баумана, Москва

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

А.П. Карпенко (karpenko@nog.ru)

Д.А. Моор (dmitry_moor@mail.ru)

Д.Т. Мухлисуллина (d.mukhlisullina@mail.ru)

Аннотация

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

Введение

Современные инженерные задачи оптимизации многокритериальные. Выделяют класс задач многоцелевой или многокритериальной оптимизации (класс МКО-задач).

В МКО-задаче предполагается, что задана вектор-функция

,

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

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

.

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

, .

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

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

· Метод, основанный на аппроксимации функции предпочтения ЛПР с помощью многослойных персептронных сетей (MLP-сети), а также с помощью нейронных сетей с радиально-базисными функциями (RBF-сети).

· Метод, в основе которого лежит аппроксимация функции предпочтений ЛПР посредством аппарата нечеткой логики.

· Метод, основанный на аппроксимации функции предпочтений ЛПР с помощью аппарата нейро-нечеткого вывода.

1. Постановка задачи многокритериальной оптимизации

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

,

множество формируют ограничивающие функции , :

.

Векторный критерий оптимальности

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

, , (1.1)

где - искомое решение МКО-задачи.

Введем следующие обозначения: - критериальное множество (множество достижимости) задачи, т.е. множество, в которое векторный критерий оптимальности отображает множество ; - фронт Парето задачи, ; - множество Парето. Если , то будем говорить, что вектор X - эффективный по Парето вектор [Лотов, 1984]. Положим, что частные критерии оптимальности тем или иным образом нормализованы [Карпенко и др., 2008a].

Рассмотрим решение задачи (1.1) методом скалярной свертки. Способ свертки не фиксируется. Обозначим операцию свертки , где - вектор весовых множителей,

-

множество допустимых значений этого вектора.

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

, . (1.2)

В силу ограниченности и замкнутости множества решение этой задачи существует.

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

.

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

, . (1.3)

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

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

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

, .

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

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

многокритериальный оптимизация нейронный аппроксимация

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

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

1) решает однокритериальную задачу (ОКО-задачу)

, , ; (1.4)

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

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

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

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

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

, ;

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

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

3. Особенности нейросетевой аппроксимации функции предпочтения ЛПР

Аппроксимация функции предпочтения ЛПР нейронными сетями имеет в работе ту особенность, что процесс обучения нейронных сетей происходит в условиях малой обучающей выборки. Это обстоятельство обусловлено тем, что количество «разгонных» итераций не должно быть слишком большим, иначе ЛПР может прекратить процесс вычислений, не получив окончательного решения. Как следствие, для аппроксимации функции предпочтения ЛПР в работе используются только двухслойные MLP и RBF нейронные сети.

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

.

Вследствие этого, в качестве входов нейронных сетей рассматриваются только компоненты ₁, ₂, …, _m-1 вектора .

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

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

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

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

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

Здесь - коэффициенты определенности (веса нечетких правил).

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

Используется схема нечеткого вывода Мамдани, который выполняется за два шага [Карпенко и др., 2008d].

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

, где .

Матрицу знаний представим в виде

Шаг 2. Тонкая настройка модели (параметрическая идентификация модели) осуществляется путем подбора следующих параметров: полуширина a функций принадлежности входных переменных ; полуширина b функций принадлежности выходных переменных ; величина д, определяющая закон изменения весовых множителей правил. Область допустимых значений указанных параметров представляет собой параллелепипед , а критерий оптимальности имеет вид:

, ,

где - результат нечеткого логического вывода Мамдани в точке

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

.

5. Особенности аппроксимации функции предпочтений ЛПР с помощью аппарата нейро-нечеткого вывода

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

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

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

По мере приобретения новых знаний меняется топология нечеткой нейронной сети, для чего используется процедура, предложенная в работе [Круглов и др., 2002].

6. Исследование эффективности методов

Исследование выполнено для следующих тестовых задач.

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

; ; .

Двухкритериальная задача 2 (невыпуклый многосвязный фронт Парето):

; ;

; .

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

; ;

; .

Для всех трех задач полагалось, что число k «разгонных» значений вектора равно трем (k=3).

Исследование вышеперечисленных МКО-задач проводилось на MLP-сетях с тремя (MLP3), пятью (MLP5), семью (MLP7) и девятью (MLP9) нейронами в скрытом слое и на RBF-сети (RBF), а также с использованием системы нечеткого вывода Мамдани (Fuzzy) и с использованием нейро-нечеткого логического вывода ANFIS (ANFIS).

Результаты исследования сведены в таблицу 1. Результаты более широкого исследования приведены в работах [Карпенко и др., 2010b], [Карпенко и др., 2010c], [Карпенко и др., 2010d].

Табл. 1 Результаты исследования эффективности метода

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

Вид функции после 7 итераций решения МКО-задачи 2 с использованием аппарата нейро-нечеткого вывода показан рисунке 2.

Рис. 2 Аппроксимация функции предпочтений ЛПР для МКО-задачи 2: ANFIS; 7-я итерация

Выводы

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

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

Список литературы

1. [Карпенко и др., 2008a] Карпенко А.П., Федорук В.Г. Адаптивные методы решения задачи многокритериальной оптимизации, использующие аппроксимацию функции предпочтений лица, принимающего решения. [Электронный ресурс] // Электронное научно-техническое издание: наука и образование. - 2008. - №8. (http://technomag.edu.ru/doc/101804.html).

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

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

4. [Карпенко и др., 2010d] Карпенко А.П., Моор Д.А., Мухлисуллина Д.Т. Многокритериальная оптимизация но основе нечеткой аппроксимации функции предпочтений лица, принимающего решения // Наука и образование: электронное научно-техническое издание, 2010, 6, (http://technomag.edu.ru/doc/149317.html).

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

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

Размещено на Allbest.ru