Методы решения задач возможностной оптимизации с взаимодействующими параметрами тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Солдатенко, Илья Сергеевич

• Солдатенко, Илья Сергеевич
• кандидат физико-математических наук
• 2008

Оглавление диссертации кандидат физико-математических наук Солдатенко, Илья Сергеевич

Введение.

1 Исчисление возможностей при агрегировании нечеткой информации на основе 1;-норм.

1.1 Основные понятия теории возможностей.

1.2 Агрегирование нечеткой информации на основе ^норм.

1.3 Способы моделирования взаимодействия возможностных переменных.

1.4 Взвешенная Тм--сумма нечетких величин.

1.5 Примеры идентификации функции распределения Т^-суммы и расчета границ ее ск-уровневых множеств.

1.6 Выводы по первой главе.

2 Методы решения задач возможностного программирования с взаимодействующими нечеткими параметрами.

2.1 Базовые модели возможностной оптимизации.

2.2 Непрямые методы решения в случае меры возможности

2.3 Непрямые методы решения в случае меры необходимости

2.4 Спецификация генетического алгоритма решения эквивалентных детерминированных аналогов.

2.5 Выводы по второй главе.

3 Сравнительное изучение эквивалентных детерминированных аналогов задач возможностного программирования при различных t-нормах.

3.1 Сравнительный анализ.

3.2 Теорема вложенности множеств допустимых решений.

3.3 Исследование задач возможностной оптимизации в контексте возможность/необходимость.

3.4 Выводы по третьей главе.

4 Программный комплекс и модельные расчеты.

4.1 Программный комплекс FIESTA.

4.2 Архитектура системы.

4.3 Модельные расчеты в системе FIESTA.

4.4 Выводы по четвертой главе.

Введение диссертации (часть автореферата) на тему «Методы решения задач возможностной оптимизации с взаимодействующими параметрами»

Актуальность

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

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

В настоящее время интенсивно разрабатываются многочисленные математические формализмы для описания и моделирования неопределенности. Одним из таковых является подход, предложенный в середине 60-х годов американским ученым Лотфи Заде. Он предложил способ моделирования неопределенности как нечеткости, основанный на идее расширения понятия характеристической функции множества до функции принадлежности, принимающей значения на отрезке [0,1]: л(-) : >4 [0,1].

Значения функции /¿л(-) характеризуют степень проявления отдельных свойств объектом А.

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

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

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

В диссертационной работе показано, что минисвязанность это лишь одна из возможных реализаций ¿-нормы. В ней проводится сравнительное изучение других ¿-норм — в частности исследуется взаимозависимость параметров по другой экстремальной ¿-норме — слабой треугольной норме Тцг. При использовании различных ¿-норм можно добиться управления «нечеткостью» при решении задач оптимизации, что, в свою очередь, дает большую гибкость при принятии решений.

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

Обзор литературы

Основоположником теории нечетких множеств и связанной с ней теории возможностей является профессор Калифорнийского университета Беркли Лотфи Заде, который в своей знаменитой работе «Fuzzy Sets» [115] обобщил понятие характеристической функции множества предположив, что она может принимать значения не только из множества {0,1}, но и из всего отрезка [0,1], характеризуя таким образом «степень принадлежности» элемента нечеткому множеству.

В 1978 году Стефан Намиас в своей работе «Fuzzy Variables» [97] предложил «аксиоматическую базу, являющуюся основой для построения строгой теории возможностей» («theoretical framework from which a rigorous theory may ultimately be constructed»). В этой статье было введено понятие нечеткой переменной, которое в дальнейшем трансформировалось в такое важное понятие, как возможностная (нечеткая) величина. В этой основополагающей статье Намиас также ввел понятие несвязанности (unrelatedness) нечетких величин и аксиоматически определил бинарные операции над несвязанными нечеткими величинами, тем самым заложив теоретические основы современного исчисления возможностей. Позже в работе Pao и Рашеда [105] было замечено, что несвязанность, определенную Намиасом, было бы логичней называть минисвязанностыо (min-relatedness), так как получалось, в частности, что по Намиасу нечеткая величина А несвязанна сама с собой. Эти работы можно считать одними из основополагающих в теории возможностей.

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

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

Одной из первых работ в области возможностной оптимизации можно назвать работу Беллмана и Заде «Decision making in a fuzzy environment» [68]. Значительную роль в развитии данного научного направления также сыграли работы Циммермана [118], Луханджулы [89-91], Дюбуа и Прада [14], К.Негойце [33], Бакли [69,70], Орловского С.А. [26], Р.Фуллера [53], Рамика [104], А.В.Язенина [58-65,113] и М. Вагенкнех-та [114] и многие др.

К настоящему моменту хорошо изученными являются модели возможностной (нечеткой) оптимизации в случае независимых (минисвязан-ных) нечетких параметров. Получены методы решения соответствующих задач как в классах параметризованных возможностных распределений, так и в общем случае — квазивогнутых полунепрерывных сверху распределений. Следует отметить, что взаимодействие нечетких параметров в них основано на использовании жесткой конъюнкции, принятой в нечеткой логике. Помимо разработки непрямых методов решения, проведены также исследования вопросов устойчивости данных задач [11,12,37-42], изучены модели возможностной оптимизации, в которых не только параметры, но и отношения, связывающие операнды моделей критерия и моделей ограничения, являются нечеткими [8-10,13]. Однако в том случае, когда параметры оптимизационных моделей являются взаимодействующими, исследования в этом научном направлении находятся на начальном этапе развития.

Стоит отметить, что учет зависимости нечетких параметров может быть осуществлен различными способами, а не только на основе ¿-норм.

В работе Танака и Ишибучи [108] зависимость параметров «отражается» через совместную функцию распределения нечетких параметров. В том случае, когда это распределение является эллипсоидальным, в [114] рассматривается одна из возможных постановок задачи идентификации функции распределения взвешенной суммы возможностных величин и предлагается метод ее решения, основанный на методе множителей Лагранжа. В работах Фуллера, Мажлендера и Карлссона [71,77,78] вводятся понятия вариации, ковариации и корреляции возможностных переменных и предлагаются методы их расчета в ряде случаев. Интерпретация данных характеристик тесно связана с теорией вероятностей. Как видно из работ авторов, возможностная ковариация между нечеткими числами А и В есть ни что иное, как взвешенное среднее вероятностных ковариаций между случайными величинами, имеющими равномерное совместное распределение на уровневых множествах совместного распределения возможностей А и В:

Соу/(А, В) = Г соу(Х7, У7)/(7) ¿7 J о о где и У7 - это случайные величины, имеющие равномерное совместное распределение вероятностей на С7 для всех 7 е [0,1], С7 — 7-уровневое множество совместного распределения нечетких величин А и В, /(7) : [0,1] —> М — неотрицательная, монотонно возрастающая весовая функция, удовлетворяющая следующему условию нормировки:

Использование весовой функции мотивировано, в частности, желанием дать меньшую степень важности нижним уровням нечетких множеств (именно поэтому / является монотонно возрастающей).

Точно так же возможностная вариация нечеткого числа есть взвешенное среднее вероятностных вариаций случайных величин, равномерно распределенных на его уровневых множествах: где Щ — это случайная величина, равномерно распределенная на А1 для всех 7 6 [0,1].

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

В настоящей работе взаимодействие возможностных переменных моделируется, как нам представляется, более естественным образом — при помощи аппарата ¿-норм. Это есть более естественный механизм моделирования процесса агрегирования нечеткой информации, к тому же позволяющий контролировать рост нечеткости результатов, неизбежно возникающий при выполнении операций над нечеткими величинами. С этой 1 целью в работе используется понятие взаимной Т-связанности, которое было введено в работе Хонга «Parameter estimations of mutually T-related fuzzy variables» [79]. Такой способ моделирования взаимодействия (зависимости) параметров позволяет более гибко управлять нечеткостью при решении задач возможностной оптимизации и является в данный момент наиболее общим. В частности, операция конъюнкции (минимума) выступает одним из видов ¿-норм. Подробную информацию о ¿-нормах можно найти, например, в [83-85]. Вопросам построения исчислений, основанных на различных ¿-нормах, посвящены работы Месьяра [93-96], Дюбуа и Прада [72,74] и многих других.

Цель работы

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

Основные задачи

Для достижения поставленной цели в диссертации решены следующие задачи:

• разработано исчисление возможностей для взаимно Т^-связанных нечетких величин, предполагающее решение задач идентификации функций распределения взвешенных TV-сумм нечетких величин с одинаковыми и различными функциями представления формы;

• получены формулы для вычисления границ а-уровневых множеств взвешенной TV-суммы возможностных величин;

• разработаны непрямые методы решения задач возможностной оптимизации при взаимно Тр^-евязанных параметрах в возможностно-необходимостном контексте;

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

• проведено сравнительное изучение моделей и методов возможностной оптимизации при агрегировании нечеткой информации на основе Ту/- и Тм-норм;

• реализован программный комплекс поддержки соответствующих методов возможностной оптимизации при моделировании взаимодействия нечетких параметров на основе ¿-норм.

Методика исследования

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

Практическая значимость работы

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

Внедрение результатов работы

Результаты диссертационной работы внедрены в учебный процесс на факультете прикладной математики и кибернетики Тверского госуниверситета. Непрямые методы решения задач, полученные в диссертации, представлены в дисциплине «Теория неопределенностей», методы агрегирования возможностной информации — в программе курса «Современные проблемы прикладной математики и информатики». Соответствующее программное обеспечение, разработанное в диссертации, используется в качестве программной составляющей учебно-методического комплекса по дисциплинам «Теория неопределенностей» и «Нечеткое математическое программирование». Часть исследований, проводимых в работе, была поддержана грантом РФФИ, проект номер 08-01-08076.

Апробация

Основные результаты работы докладывались автором на IV Международной научно-практической конференции «Интегрированные модели и мягкие вычисления в искусственном интеллекте» (Коломна, 2007 год), на 27-м ежегодном съезде Северо-Американского общества обработки нечеткой информации КАК1Р8-2008 (Нью-Йорк, 2008 год), на семинарах в Тверском госуниверситете и ВЦ РАН.

Достоверность и обоснованность

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

Структура работы и ее содержание

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

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Солдатенко, Илья Сергеевич

4.4 Выводы по четвертой главе

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

Система FIESTA реализована на основе библиотеки MFC в виде объектно-ориентированного приложения, в результате чего есть возможность для расширения функциональности системы. Система может быть применена как для практического решения задач финансового, экономического, производственного планирования, так и для проведения лабораторных работ по изучению и применению непрямых методов решения оптимизационных задач и исследования поведения задач при использовании различных агрегирующих í-норм на занятиях по дисциплинам «Теория неопределенностей» и «Современные проблемы прикладной математики и информатики», упомянутым выше.

Заключение

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

Среди результатов можно выделить следующие основные:

1. Получены элементы исчисления возможностей для взаимно Ту/связанных нечетких величин, в частности получены методы идентификации функции распределения взвешенной Тцг-суммы нечетких величин с одинаковыми и различными левыми и правыми формами.

2. Получены формулы для рассчета границ а-уровневых множеств взвешенной Т\у-суммы нечетких величин.

3. Разработаны непрямые методы решения задач возможностной' оптимизации (максимизации уровня достижения нечеткой цели и максимизации возможности достижения нечеткой цели при построчных ограничениях по возможности), позволяющие строить эквивалентные детерминированные аналоги задач.

4. Разработаны непрямые методы решения задач возможностной оптимизации в необходимостном контексте, то есть когда в качестве меры нечеткости выступает мера необходимости.

5. Проведена спецификация генетических алгоритмов, ориентированная на решение полученных детерминированных эквивалентов.

6. Исследованы свойства эквивалентных детерминированных аналогов в зависимости от вида ¿-нормы, описывающей взаимодействие нечетких параметров.

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Солдатенко, Илья Сергеевич, 2008 год

1. Ашманов С.А. Линейное программирование. — М.: Наука, 1981.

2. Ашманов С.А. Условие устойчивости задач линейного программирования // ЖВМиМФ, том 21, № 6, 1981. Стр. 1402 1410.

3. Васильев Ф.П. Численные методы решения экстремальных задач / 2-е, перераб. и доп. изд. — М.: Наука, 1988.

4. Васильев Ф.П. Критерии устойчивости общей задачи линейного программирования // Вест. Моск. ун-та, Сер. 15. Вычислительная математика и кибернетика, №2, 1998. Стр. 17 20.

5. Васильев Ф.П. К вопросу устойчивости методов регуляризации в линейном программировании // Вест. Моск. ун-та, Сер. 15. Вычислительная математика и кибернетика, №3, 1998. Стр. 19 23.

6. Васильев Ф.П., Иваницкий А.Ю. Линейное программирование / 2-е, доп. изд. — М.: Изд-во «Факториал Пресс», 2003.

7. Гамма Э., Хелм Р., Джонсон Р., Влисидес Д. Приемы объектно-ориентированного проектирования. Паттерны проектирования. — СПб.: Питер, 2004.

8. Гордеев Р.Н. К задаче максимизации необходимости нечеткой цели // Вестник ТвГУ. Сер. Прикладная математика, 2005. Стр. 100 -107.

9. Гордеев Р.Н., Язенин A.B. Метод решения одной задачи возмож-ностного программирования // Известия РАН. Теория и системы управления, №3, 2006. Стр. 121 128.

10. Гордеев Р.Н. Исследование устойчивости одного класса задач воз-можностного программирования // Всероссийская научная конференция по нечетким системам и мягким вычислениям НСМВ-2006. М.: Физматлит, 2006. Стр. 121 132.

11. Дюбуа Д., Прад А. Теория возможностей / Пер. с франц. — М.: Радио и связь, 1990.

12. Ермольев Ю.М. Методы стохастического программирования. — М.: Наука, 1976.

13. Заде JI. Понятие лингвистической переменной и его применение к принятию приближенных решений / Под. ред. H.H. Моисеева, С.А. Орловского. — М.: Мир, 1976.

14. Зангвилл У.И. Нелинейное программирование. Единый подход / Под. ред. Е.Г. Голыптейна — М.: Советское радио, 1973.

15. Измаилов А.Ф., Солодов М.В. Численные методы оптимизации. — М.: Физматлит, 2005.

16. Измаилов А.Ф. Чувствительность в оптимизации. — М.: Физматлит, 2006.

17. Канторович JI.B., Акилов Г.П. Функциональный анализ / Под ред. Бухвалова A.B. — 4-е, испр. изд. — СПб.: Невский диалект; БХВ-Петербург, 2004.

18. Карманов В.Г. Математическое программирование. — М.: Наука, 1980.

19. Ковач М, Васильев Ф.П., Фуллер Р. Об устойчивости нечеткого решения систем линейных алгебраических уравнений с нечеткими коэффициентами // Вест. Моск. ун-та, Сер. 15. Вычислительная математика и кибернетика, №1, 1989. Стр. 5-9.

20. Колмогоров А.Н. Основные понятия теории вероятностей. — М.: Наука, 1974.

21. Кофман А. Введение в теорию нечетких множеств. — М.: Радио и связь, 1982.

22. Мину М. Математическое программирование. — М.: Наука, 1990.

23. Орловский С.А. Проблемы принятия решений при нечеткой исходной информации. — М.: Наука, 1981.28