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

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

Введение 3
1.Постановка задачи многокритериальной оптимизации 4
2.Метод решения задачи 6
3.Особенности нейросетевой аппроксимации ФП ЛПР 7
3.1.Особенности аппроксимации ФП ЛПР с помощью аппарата нечеткой логики ………… 7
3.2.Особенности аппроксимации ФП ЛПР с помощью аппарата нейро-нечеткого вывода 8
4.Исследование эффективности методов 9
5. Задачи многокритериальной оптимизации
5.1. Задачи о производстве клея с двумя целевыми функциями……..………12
5.2. Задача о рюкзаке с двумя целевыми функциями…………………………15
Выводы 19
Список литературы 220

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

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

Поскольку на компоненты вектора весовых множителей наложено ограничение один из весовых множителей (пусть это будет множитель можно выразить через остальные множители: . Вследствие этого, в качестве входов нейронных сетей рассматриваются только компоненты , вектора .ЛПР в процессе решения МКО–задачи может переоценивать результаты предыдущих итераций, указанные им оценки могут быть противоречивы. Особенности аппроксимации ФП ЛПР с помощью аппарата нечеткой логикиВходами системы нечеткого вывода в данном случае являются значения весов частных критериев оптимальности – нечеткие термы , . Выходной переменной системы нечеткого вывода является лингвистическая переменная , ядро которой принимает значения 1, 2,…, 9.Взаимосвязь между входными и выходными переменными описывается нечеткими правилами видаЕСЛИ <значения входных переменных>, ТО <значение выходной переменной> Здесь QUOTE Fi – коэффициенты определенности (веса нечетких правил).Совокупность значений указанных нечетких входных переменных, выходных лингвистических переменных, а также правил нечетких продукций образуют нечеткую базу знаний.Используется схема нечеткого вывода Мамдани, которая выполняется за два шага [6]. Шаг 1. Положим, что выполнено N экспериментов по определению значений лингвистической переменной . Пусть в этих экспериментов переменная приняла значение QUOTE ψ1 , в экспериментах – значение и т.д. до и . Соответствующие входные векторы обозначим , , .Матрицу знаний представим в виде , .Шаг 2. Тонкая настройка модели (параметрическая идентификация модели) осуществляется путем подбора следующих параметров: полуширина a функций принадлежности входных переменных QUOTE μi,j,kλ ; полуширина функций принадлежности выходных переменных QUOTE μijkψ ; величина δ, определяющая закон изменения весовых множителей правил. Область допустимых значений указанных параметров представляет собой параллелепипед QUOTE DP , а критерий оптимальности имеет вид QUOTE Ea,b,δ=(ψΛi-ψ(Λi))2 ,где – результат нечеткого логического вывода Мамдани в точке .Таким образом, формально задача параметрической идентификации формулируется в виде следующей задачи глобальной многомерной условной оптимизации , .(7)Особенности аппроксимации ФП ЛПР с помощью аппарата нейро-нечеткого выводаИспользуется адаптивная нейро-нечеткая система вывода ANFIS, функционально эквивалентная системе нечеткого вывода Сугено. Вывод осуществляется за два шага, которые по сути своей аналогичны шагам, рассмотренным в предыдущем разделе. Особенностью метода является наличие этапа тонкой настройки ФП в предпосылках и заключениях правил, этот этап проводится с использованием алгоритмов обучения нейронных сетей.Система ANFIS реализуется в виде нейроподобной структуры, состоящей из пяти слоев (рис. 1). Для обучения сети был применен гибридный градиентный метод.Рис. 1. Структура нейро-нечеткой сети ANFISПо мере приобретения новых знаний меняется топология нечеткой нейронной сети, для чего используется процедура, предложенная в работе [3]. Исследование эффективности методовИсследование эффективности выполнено для следующих тестовых задач. Двухкритериальная задача 1, имеющая выпуклый фронт Парето:; ; .Двухкритериальная задача 2 (невыпуклый многосвязный фронт Парето): ;; .Трехкритериальная задача 3 (выпуклый фронт Парето):; ;; .Для всех трех задач полагалось, что число k «разгонных» значений вектора равно трем (k=3).Исследование вышеперечисленных МКО-задач проводилось на MLP-сетях с тремя (MLP3), пятью (MLP5), семью (MLP7) и девятью (MLP9) нейронами в скрытом слое и на RBF-сети (RBF), а также с использованием системы нечеткого вывода Мамдани (Fuzzy) и с использованием нейро-нечеткого логического вывода ANFIS (ANFIS).Результаты исследования сведены в таблицу 1. Результаты более широкого исследования приведены в работах [4], [5], [6]. Таблица 1Результаты исследования эффективности методаМКО-задача 1МКО-задача 2МКО-задача 3MLP3967MLP55513MLP710713MLP9958RBF565Fuzzy81114ANFIS579Исследование показало, что, хотя использование всех рассматриваемых технологий аппроксимации ФП ЛПР обеспечивает получение оптимального решения, методы, основанные на MLP сетях с пятью и девятью нейронами в скрытом слое, а также RBF-сети и системе ANFIS позволяют находить лучшее решение за наименьшее количество итераций.Вид функции после 7 итераций решения МКО-задачи 2 с использованием аппарата нейро-нечеткого вывода показан на рис. 2. Рис. 2. Аппроксимация ФП ЛПР для МКО-задачи 2: ANFIS; 7-я итерация 5. Задачи многокритериальной оптимизации 5.1. Задача о производстве клея с двумя целевыми функциями.Некоторое производственное предприятие выпускает три вида клея. Для производства клея используются 4 типа химических веществ: (крахмал, желатин, квасцы и мел). Расход этих веществ в кг для получения 1 кг каждого вида клея и их запас на складе предприятия представлены в таблице.Вид клея/ Химические веществаклей№1клей№2клей№3Запас на складеКрахмал0,40,30,220Желатин0,20,30,435Квасцы0,050,070,17Мел0,010,050,1510Стоимость каждого вида клея на внутреннем рынке составляет: с1=380руб/кг, с2=430руб./кг, с3=460руб/кг, стоимость каждого вида клея на внешнем рынке составляет: d1=12$/кг, d2=10$/кг, d3=8$/кг.Требуется определить оптимальный объем выпуска клея каждого вида, обеспечивающего максимум общей стоимости всей партии клея, как на внутреннем, так и на внешнем рынке.Математическая постановка рассматриваемой двухкритериальной задачи о клеи может быть записана в следующем виде:Где множество допустимых альтернатив формируется следующей системой ограничений типа неравенства:Решение:1. Решение многокритериальной задачи об оптимальном клеи.С помощью программы MS Excel, через поиск решения рассмотрим метод уступка.Переменныех1х2х3Значение ЦФ1Значение ЦФ2Значения037,543,7536250725,00на внутреннем рынке380430460  на внешнем рынке12108   коэффициенты ограничений:Значения ог-нийЗапас на складеКрахмал0,40,30,22020Желатин0,20,30,428,7535Квасцы0,050,070,177Мел0,010,050,158,4410Результатом решения двухкритериальной задачи об оптимальном клеи найденное значение первой функции f1=36250. Анализ найденного решения показывает, что общая стоимость на внутреннем рынке будет приближенно равна 36250 руб, причем стоимость на внешнем рынке будет составлять приблизительно 725 $. Предположим, что допустима уступка, общей стоимости на внутреннем рынке равная 20руб. На следующем этапе найдем максимум общей стоимости всей партии клея на внешнем рынке с учетом уступки.Переменныех1х2х3Значение ЦФ1Значение ЦФ2Значения0,0037,5043,7536250725,00на внутреннем рынке380430460  на внешнем рынке12108   коэффициенты ограничений:Значения ог-нийЗапас на складеКрахмал0,40,30,22020Желатин0,20,30,428,7535Квасцы0,050,070,17,007Мел0,010,050,158,4410дополнительное ограничение   3625036270Результатом решения задачи об оптимальном клеи являются найденные оптимальные значения переменных: х1=0, х2=37,5, х3=43,75, которым соответствуют значения целевой функции: f1=36250 и f1=725То есть следует произвести 37,5кг клея второго вида и 43,75кг третьего вида, а от производства клея первого вида следует отказаться.Решение двухкритериальной задачи о клеи, методом минимального отклонения.С помощью поиска решения.Переменныех1х2х3Значение ЦФ1Значение ЦФ2Значения0,0037,5043,7536250,00725,00на внутреннем рынке38043046036250725на внешнем рынке12108   коэффициенты ограничений:Значения ог-нийЗапас на складеКрахмал0,40,30,220,0020Желатин0,20,30,428,7535Квасцы0,050,070,17,007Мел0,010,050,158,4410итоговая целевая функция;   0,00 Результатом решения задачи методом минимального отклонения от идеальной точки является принятие решения о производстве 37,5кг клея второго вида и 43,75кг третьего вида, а от производства клея первого вида следует отказаться, при этом следует отметить, что такое производство позволит достигнуть максимальной стоимости как на внутреннем рынке 36250 руб так и на внешнем 725$ о чем свидетельствует отклонение от идеальной точки равное нулю.Решение двухкритериальной задачи о клее, методом аддитивной сверки.С помощью поиска решения.Переменныех1х2х3Значение ЦФ1Значение ЦФ2Значения0,0037,5043,7536250,00725,00на внутреннем рынке380430460на внешнем рынке12108коэффициенты ограничений:Значения ог-нийЗапас на складеКрахмал0,40,30,220,0020Желатин0,20,30,428,7535Квасцы0,050,070,17,007Мел0,010,050,158,4410итоговая целевая функция;7830,00Результатом решения задачи об оптимальном клеи методом аддитивной сверки на основе задания весов отдельных целевых функций являются найденные оптимальной значения переменных: х1=0, х2=37,5, х3=43,75, которым соответствуют значения целевых функций: f1=36250 и f1=725Таким образом решение двухкритериальной задачи о клее, методом аддитивной сверки оказалось аналогичным двум предыдущим методам.