Другие журналы
|
научное издание МГТУ им. Н.Э. БауманаНАУКА и ОБРАЗОВАНИЕИздатель ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". Эл № ФС 77 - 48211. ISSN 1994-0408![]()
Аппроксимация функции предпочтений лица, принимающего решения, в задаче многокритериальной оптимизации. 3. Методы на основе нейронных сетей и нечеткой логики
#4 2008 DOI: 10.7463/0408.0086335
УДК 519.6
Карпенко А.П. (д.ф.-м.наук, профессор МГТУ им.Н.Э.Баумана, E-mail: karpenko@nog.ru) Федорук В.Г. (к.т.н., доцент МГТУ им.Н.Э.Баумана, E-mail: fedoruk@comcor.ru)
Работа является третьей работой в серии, посвященной адаптивным методам решения непрерывной конечномерной задачи многомерной многокритериальной оптимизации [1, 2]. Рассматривается три метода аппроксимации функции предпочтений лица, принимающего решения (ЛПР) - метод на основе персептронных нейронных сетей, метод на основе нейронных сетей с радиальными базисными функциями и метод на основе нечеткой логики.
1. Основные обозначения Постановка задачи многокритериальной оптимизации приведена в первой работе рассматриваемой серии [1]. Повторим основные обозначения, введенные там. Вектор
замкнутое множество допустимых значений вектора параметров; Полагается, что все частные критерии тем или иным способом нормализованы и за нормализованными частными критериями оптимальности сохранены обозначения Решение задачи многокритериальной оптимизации отыскивается с помощью метода скалярной сверки, который при каждом фиксированном векторе
где Если при каждом
В результате задача многокритериальной оптимизации сводится к задаче выбора вектора
Величина При аппроксимации функции предпочтений ЛПР с помощью нейронных сетей вместо задачи (2) рассматривается задача отыскания вектора
2. Нейронные сети и их аппроксимационные свойства Искусственный нейрон (далее - нейрон) обычно определяется как элемент, имеющий некоторое количество входов (синапсов), на которые поступают входные сигналы
Рис. 1. К определению искусственного нейрона.
Функция состояния нейрона 1. Скалярное произведение векторов
2. Расстояние между векторами
где Искусственный нейрон с функцией состояния (4) называется персептроном, с функцией состояния (2) – нейроном с радиальной базисной функцией. На функцию активации (передаточную функцию)
где a - параметр, определяющий фронт этой функции. Отметим, что в данном случае ее производная имеет вид Часто функция состояния и функция активации объединяются в одну (передаточную) функцию. Далее мы будем следовать этому соглашению. Нейронные сети образуются путем соединения входов одних нейронов с выходами других. Как правило, вид передаточных функций всех нейронов в сети фиксирован (используются однородные сети), а веса и, возможно, параметры передаточных функций могут изменяться. Существует нейронные сети с множеством различных топологий. Основными являются многослойные сети, которые классифицируются следующим образом: · сети без обратных связей (сети прямого распространения) - многослойные персептроны и многослойные сети с радиальными базисными функциями; · сети с обратными связями (рекуррентные сети) - соревновательные сети, сети Кохонена, сети Хопфилда, сети Элмана, сети Жордана и пр. Для решения задач аппроксимации наиболее адекватными являются многослойные сети прямого распространения - двухмерные многослойные персептроны (MultiLayer Perceptron, MLP-сети) и двухмерные нейронные сети, использующие радиальные базисные функции (RadialBasisFunctionNetwork, RBF-сети). Если, как в нашем случае, аппроксимируемая функция является скалярной, то минимальной реализацией таких сетей является двухслойная нейронная сеть, состоящая из входного (распределительного), промежуточного (скрытого) и выходного слоя из одного нейрона (при подсчете числа слоев входной слой обычно не учитывается) - см. Рис. 2. Задачу аппроксимации скалярной функции можно интерпретировать как задачу реализации отображения Теорема 1 (теорема о полноте). Если множество
Рис. 2. Двухслойная сеть без обратных связей:
3. Аппроксимация функции предпочтений на основе персептронной нейронной сети Обозначим выходы нейронов скрытого слоя
Здесь Точным решением рассматриваемой задачи аппроксимации является функция В качестве оценки ошибки В качестве множителей Заметим, что другой класс критериев качества обучения для задач аппроксимации образуют робастные целевые функции и функции с возможностью задания допуска на точность решения задачи [5]. Для первоначальной оценки числа нейронов Hв скрытом слое MLP-сети можно использовать эвристическую рекомендацию [6]:
В нашем случае величина
Отметим, что оценка (6), (7) исходит из предположения об использовании в MLP-сети сигмоидальных передаточных функций. Для определения числа нейронов в скрытом слое MLP-сети чаще всего используют метод динамического наращивания узлов, суть которого состоит в следующем. Если средняя скорость уменьшения ошибки
r– номер обучающей итерации, на которой производится оценка скорости обучения, q– количество итераций. Известно значительное количество различных модификаций метода динамического наращивания узлов. Например, качество обучения можно повысить за счет использования нескольких нейронов-кандидатов, претендующих на включение в сеть. Эффективность включения в сеть каждого из этих нейронов проверяется по отдельности (путем обучения сети с каждым из них и сравнения достигнутой точности аппроксимации). При фиксированном количестве нейронов в скрытом слое задача обучения MLP-сети состоит в определении весов Легко видеть, что
где Имея указанные производные, легко найти градиент величины
Таким образом, для каждого
На обратном ходе вычисляются величины
Наконец, градиентный шаг метода обратного распространения имеет вид:
Здесь Хорошо известно, что метод обратного распространения не свободен от существенных недостатков: · метод не всегда сходится; · процесс градиентного спуска может завершиться в одном из локальных минимумов критерия качества обучения; · при увеличении количества нейронов в скрытом слое MLP-сеть склонна к переобучению; · в MLP-сети с функциями активации, имеющими горизонтальные асимптоты (например, с сигмоидальными функциями), в процессе обучения может иметь место «паралич» сети. Для улучшения сходимости алгоритма обратного распространения могут быть предприняты следующие меры [7 - 10]. 1). Выбор начального приближения для весов таким образом, чтобы гарантированно обеспечить попадание значений скалярных произведений в «рабочую зону» передаточных функций. Можно, например, использовать в качестве начальных значений весов значения
где 2). Добавление в формулу для приращения веса некоторой инерционности. Например, можно принять 3). Ограничение возможного роста абсолютных значений весов путем добавления к функционалу
Отметим, что такое «сокращение весов» представляет собой частный случай регуляризации некорректно поставленных задач по А. Н. Тихонову. Важно, что данный прием повышает устойчивость весов в случае мультиколлинеарности - когда в обучающей выборке имеются линейно зависимые или сильно коррелированные векторы 4). Усреднение градиента по всем или некоторой части примеров обучающей выборки – использование «пакетной коррекции». 5). Применение более сложных алгоритмов выбора величины шага, например, градиентного алгоритма с дроблением шага, алгоритма наискорейшего спуска, алгоритма на основе квадратичной аппроксимации функции 6). Использование комбинации градиентного метода с методом случайного локального поиска с целью обеспечения поиска глобального минимума функционала 7). Использование методов и алгоритмов оптимизации, обеспечивающих более высокую скорость сходимости - метод сопряженных градиентов, квази-ньютоновский метод, алгоритмы QuickProp, RProp. Эффективность обучения можно повысить также за счет выбора критерия останова, изменения порядка предъявления объектов обучающей выборки, использования «раннего останова», обучения с использованием генетических и «отжиговых» алгоритмов обучения и пр. [7].
4. Аппроксимация функции предпочтений на основе нейронной сети с радиальными базисными функциями Отметим прежде следующее обстоятельство. Из теоремы 1 следует, что MLP-сети и RBF-сети являются универсальными аппроксиматорами. Поэтому всегда существует RBF-сеть, имитирующая любую MLP-сеть, и наоборот. RBF-сеть аппроксимирует произвольную нелинейную функцию с помощью всего одного промежуточного слоя (см. Рис. 2). Таким образом, в отличие от MLP-сети в данном случае отсутствует проблема определения количества слоев в сети. Выходной слой RBF-сети строится на основе нейрона с линейной передаточной функцией, что позволяет не обучать этот нейрон. Известным недостатком RBF-сетей являются их плохие экстраполяционные свойства [11]. Рассмотрим типичную для наших приложений ситуацию, когда число элементов в обучающей выборке относительно невелико (не превышает нескольких сотен). При этом каждому вектору
Здесь Если предположить, что величины
Здесь, как и ранее, Решение указанной СЛАУ сводится к обращению
Теорема 2 (теорема Митчела). Если в обучающей выборке
В случае Как и в MLP-сети, в качестве оценки ошибки используем взвешенное среднеквадратичное отклонение Очевидно, что если веса
Задача (10) представляет собой многомерную задачу условной оптимизации и решать ее приходится с использованием итеративных численных методов оптимизации. Найдем частные производные критерия
Таким образом,
Заметим, что поскольку Таким образом, при фиксированных весах При использовании градиентного метода с дроблением шага итерационная формула имеет вид
где Поскольку критерий Отметим, что при высокой размерности обучающей выборки целесообразно использовать не градиентные методы, а методы на основе генетических алгоритмов оптимизации. Замечание. Рассмотренная схема обучения (когда количество нейронов в скрытом слое равно количеству примеров в первой обучающей выборке) не применима в случае, когда эта выборка содержит слишком большое количество элементов (тысячи или десятки тысяч). В таком случае приходится группировать элементы обучающего множества по степени их близости в пространстве входных значений в некоторое число кластеров. Количество таких кластеров задает количество нейронов в скрытом слое сети, а их средние характеристики используют для начальной инициализации параметров передаточных функций. Для такого рода группировки можно использовать метод k-средних, самоорганизующиеся карты Кохонена или деревья решений.
5. Основные понятия нечеткой логики Теоретической основой аппроксимации функций с помощью аппарата нечетких множеств является следующая теорема. Теорема 3 (теорема Ванга). Для любой вещественной непрерывной функции
где
Если
Этап построения нечеткой модели, на котором определяются терм-множества переменных и необходимые для их формализации функции принадлежности, называется фаззификации переменных (fuzzification). При выполнении логической операции «И» над нечеткими множествами используется T-норма, а при выполнении логической операции «ИЛИ» - S-норма [13]. Чаще всего используют следующие T-нормы: пересечение по Л.Заде - В качестве S-норм обычно используют объединение по Л. Заде - Дефаззификацией (defuzzification) называется процедура преобразования нечеткого множества в четкое число. Простейшим способом выполнения процедуры дефаззификации является выбор четкого числа, соответствующего максимуму функции принадлежности. Для многоэкстремальных функций принадлежности используются следующие методы дефаззификации: · метод центра тяжести (centroid), при котором искомое четкое число a находится из равенства
· метод медианы (bisector), при котором число aпредставляет собой точку на оси абсцисс, перпендикуляр в которой к этой оси делит площадь под кривой функции принадлежности на две равные части
· метод максимума (MeanOfMaximumsMOM), в котором четкое число a находится из равенства
где G - множество всех элементов из U, имеющих максимальную степень принадлежности нечеткому множеству A. Нечетким логическим выводом (fuzzylogicinference) называется аппроксимация зависимости Композиционное правило Заде. Если Различают нечеткий логический вывод [13] · на основе синглтонной модели нечеткого вывода, · по алгоритму Сугено (нечеткий логический вывод Сугено), · по алгоритму Мамдани (нечеткий логический вывод Мамдани). Синглтонная модель нечеткого вывода предполагает, что входы объекта Нечеткий логический вывод Сугено исходит из того, что задано некоторое количество линейных функций Одним из центральных вопросов теории нечетких множеств является вопрос о построении функций принадлежности. В практических приложениях применяются методы определения функций принадлежности по выборкам и на основании априорной информации, в которую входят ограничения на эти функции [14]. Мы будем рассматривать в качестве функции принадлежности следующие двухпараметрические функции 1). Треугольная функция принадлежности 2). Трапецеидальная функция принадлежности
3). Гауссова функция принадлежности 4). Колоколообразная функция принадлежности Для любой указанных функций принадлежности
6. Аппроксимация функции предпочтений на основе нечеткой логики Задачу аппроксимации функции предпочтений ЛПР можно рассматривать как задачу идентификации объекта, в котором входными переменными являются значения весов частных критериев оптимальности – нечеткие термы Взаимосвязь между входными и выходной переменной описывается нечеткими правилами вида ЕСЛИ <значения входных переменных>, ТО <значение выходной переменной>. Совокупность таких правил представляет собой нечеткую базу знаний. Построение модели На первом этапе (этапе структурной идентификации) осуществляется формирование базы знаний и грубая настройка модели Суть второго этапа (этапа параметрической идентификации) состоит в тонкой настройке модели Термы
Здесь Аналогично, термы
Здесь Положим, что выполнено N опытов по определению значений лингвистической переменной
Таблица 1. Матрица знаний.
Указанную матрицу знаний можно представить в виде системы логических высказываний ЕСЛИ
……….
ТО С использованием операций объединения и пересечения множеств эта система может быть переписана в более компактном виде:
Во введенных обозначениях схема нечеткого логического вывода Мамдани имеет следующий вид. 1). Для данного вектора где 2). "Срезаем" функции принадлежности 3). Объединяем (агрегируем) полученные нечеткие множества – получаем нечеткое множество с функцией принадлежности 4). Определяем четкое значение выхода Этап параметрической идентификации состоит в подборе таких параметров функций принадлежности В нашем случае имеется всего три варьируемых параметра: · Полуширина · полуширина · величина Область допустимых значений варьируемых параметров Для параметрической идентификации построенной нечеткой модели необходима еще одна обучающая выборка
где Таким образом, формально задача параметрической идентификации формулируется следующим образом:
Задача (11) является многомерной задачей условной оптимизации. Нет никаких оснований полагать, что эта задача является одноэкстремальной. Поэтому, вообще говоря, следует классифицировать ее как задачу глобальной оптимизации. Обычно для решения задачи (11) используется метод наискорейшего спуска (с приближенным вычислением направления градиента с помощью конечных разностей). Для отыскания глобального экстремума приходится использовать поиск из разных начальных точек. При высокой размерности вектора
7. Заключение В работе рассмотрено использование персептронной нейронной сети, нейронной сети с радиальными базисными функциями, а также нечеткой логики для аппроксимации функции предпочтений ЛПР. На основе данных методов в последующих публикациях данной серии работ будут предложены адаптивные методы многокритериальной оптимизации.
Литература 1. Карпенко А.П., Федорук В.Г. Адаптивные методы решения задачи многокритериальной оптимизации. 1. Методы на основе планов первого порядка. //"Наука и образование: электронное научное издание. Инженерное образование", www.technomag.edu.ru, (╧ Гос. регистрации 0420700025, ЭЛ ╧ ФС 77-305 69), март, 2008, ╧0420800025/0007. 2. Карпенко А.П., Федорук В.Г. Адаптивные методы решения задачи многокритериальной оптимизации. 2. Методы на основе планов второго порядка. //"Наука и образование: электронное научное издание. Инженерное образование", www.technomag.edu.ru, (╧ Гос. регистрации 0420700025, ЭЛ ╧ ФС 77-305 69), март, 2008, ╧0420800025/0008. 3. Хайкин С. Нейронные сети. Полный курс. –М.: ООО «И.Д.Вильямс», 2008. -1104 с. 4. Загоруйко Н.Г. Прикладные методы анализа данных и знаний, Новосибирск, Изд-во Ин-та математики, 1999 г.-270 с. 5. Горбань А.Н., Россиев Д.А. Нейронные сети на персональном компьютере. -Новосибирск, Наука, 1996. -276 с. 6. Галушкин А. И. О методике решения задач в нейросетевом логическом базисе. - М.: Новые технологии, 2006. - 24 с. - (Приложение к журналу "Информационные технологии"; ╧ 9/2006). 7. Головко В. А. Нейронные сети: обучение, организация и применение. -М.: Радиотехника, 2001. -256 с. 8. Аттетков А.В., Галкин С.В., Зарубин В.С. Методы оптимизации. –М.: Изд-во МГТУ им. Н.Э. Баумана, 2003. -440 с. 9. LeCun Y., Bottou L., Orr G.B., Muller K.-R. Efficient BackProp //Neural Networks: Tricks of the Trade. Lecture Notes in Computer Science, Vol. 1524 - Springer, 1998, 432 p. 10. Poggio Т., Girosi F. Networks for approximation and learning //Proceedings of the IEEE, 1990, ╧ 9. – pp. 1481—1497. 11. Воронцов К.В. Лекции по искусственным нейронным сетям, www.ccas.ru/voron/download/NeuralNets.pdf 12. Круглов В. В., Борисов В.В. Искусственные нейронные сети. Теория и практика. - М.: Радио и связь, 2000. -382 с. 13. Ротштейн А.П. Интеллектуальные технологии идентификации //http://matlab.exponenta.ru/fuzzylogic/book5/references.php 14. Норвич А.М., Турксен И.Б. Фундаментальное измерение нечеткости. В сб.: Нечеткие множества и теория возможностей. - М: Радио и связь, 1986, с.54-64. Публикации с ключевыми словами: нейронные сети Публикации со словами: нейронные сети Смотри также:
Тематические рубрики: Поделиться:
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|