Разработка метода сведения общей задачи нелинейного программирования к задаче безусловной оптимизации и решение задачи оптимизации в нечетких условиях тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

ВВЕДЕНИЕ.4

ГЛАВА I МЕТОД М-2ЖЦШ

§1 Постановка задачи.15

§2 Вводимые ограничения.17

§3 Некоторые свойства М-функций.19

§4 Доказательство сходимости метода.

§5 Обсуждение результатов.33

ГЛАВА II

РЕШЕНИЕ ЗАДАЧИ ОПТИМИЗАЦИИ В НЕЧЕТКИХ УСЛОВИЯХ

§1 Вводные замечания.

§2 Решение задачи нелинейной оптимизации в нечетких условиях.38

Резюме.

ГЛАВА III

МЕТОДЫ 0ПР1ДМЕНШ ФУНКЦИЙ ПРИНАДИЕШОСТИ, СООТВЕТСТВУЮЩЕ НЕЧЕТКИМ УСЛОВИЯМ, НА ОСНОВЕ ЭКСПЕРТНЫХ ОЦЕНОК

§1 Постановка задачи. Нечеткие отношения как нечеткие гипотезы .47

§2 Меры нечеткости. Процедуры выбора нечеткой гипотезы в случае двух альтернатив и одного испытания.50

§3 Выбор нечеткой гипотезы в случае сходящейся выборочной последовательности.58

§4 Свойства меры нечеткости в случае произвольной последовательности испытаний.60

§5 Выбор нечеткой гипотезы в общем случае с нечетким взвешиванием.62

§6 Свойства меры нечеткости принятой гипотезы при операторе А .66

Р е з юм е.

ГЛАВА

ЧИСЛЕННОЕ ИССЛЕДОВАНИЕ МЕТОДА М-ФУНКЦИЙ.

ГЛАВА

РЕАЛИЗАЦИЯ МЕТОДА М-ФЛВДИЙ ПРИ РЕШЕНИИ

ЗАДАЧИ ЭКСПРЕСС-ДИАГНОСТИКИ

§1 Вводные замечания

§2 Некоторые математические и медико-технические аспекты диагностики по показаниям активных то чек коей

§3 Построение полиномов оптимальной степени от нескольких переменных, предсказывающих значения некоторых медицинских параметров .85

§4 Получение функций принадлежности психофизиологических состояний человека-оператора .96

§5 Алгоритм диагностики состояния человека-оператора по показаниям электрокожного потенциала активных точек коаи.104

Резюме.107

3 А К Л Ю Ч Е Н И Е.I09-III

Рассматриватся общая задача нелинейного математического программирования в известной постановке /43/: определить точку сс* во множестве

§(/г(х) = 0, хсА*} , да которой (Д) ffr*)zffcс) где /; ht/^^f^ ~ нелинейные функции; при этом Cj(ct) ж L (ос) - вектор-функции: i W > i (*)>., (х)} ■

Частные детализации формулировки (А) порождают различные варианты задачи поиска условного или безусловного экстрецутла. Исследовано, описано и используется немалое количество методов решения подобных задач: этому посвящены известные работы Д.Химмельблау, А.Фиакко и Г.Мак-Корми-ка, Б.Н.Пшеничного и Ю.М.Данилина, Н.Н.Моисеева, В.Ф.Фёдорова и др. В частности, оптимизация без ограничений чаще осуществляется с использованием методов спуска, например, градиентных методов / метод наискорейшего спуска /43/, градиентный метод с переменным шагом /35/ и др./, которые просты и эффективны для дифференцируемых функций, удовлетворяющих условию Липшица. Если функция f(x) дважды непрерывно дифференцируемая, то хорошие результаты дают модификации метода Ньютона: метод Ныотона-Рафсона /33/, обобщенный метод Ньютона /26/, метод двойственных направлений /19/; а также методы сопряженных направлений: метод Флет-чера-Ривса /20/, Давидона /24/, Пшеничного /34/, Пауэлла

47/. Если градиент функции f(^) разрывен, то полезны методы обобщенных градиентов /45/. Заслуживают внимания методы оврагов /23/, покоординатного и случайного поиска /48,49/.

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

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

PCX, А А) = fa - Sk I f?Kc (0 -1, JL tfQ lc C§J) J где J0!"',^' - весовые коэффициенты, - параметры,

GX(§) - операторы, удовлетворяющие требованиям: Q.j'g^oo при fcc) —■> + О , что необходимо для того, чтобы точка о: всегда была внутренней /методы "внутренней точки"/, Н< Ui)>0 при Ь('эс) 9.

HJU О при K ~*OQ и /-/к- (/и)-О при Lc (oc)-О. ' Рть

Кроме того, lluib ^p<K>QK(Cj.) .-=0 йт ( РСзСкЛЛ) - f С( =0 к-^оо то есть влияние функций-ограничений cji „ h-j на значение штрафной функции постепенно ослабевает и в пределе полностью исчезает, а экстремум Функции P(x/i,s) совпадает с экстремумом функции J (ос) .

Примерами штрафных функций с параметрами могут служить функции: fO^'^f- фф.) ~ мет°Д "барьерных поверхностей" р(хд)= Jcc)- г llpi^o^^iC^ - мет°д "логарифмического потенциала" /116/,

О Г Л О ПРИ n*>Sгде $«*)*{ 4 при метод Вейсмана /41/ /, т

Р(х,г,с) = /(*) - г £I - cj* q >л

- метод "компенсирующей константы" /115/, t г

Р(х> t,s) = ffc)- it hjfrj-S^fyfrf*) - комбинированный метод штрафных функций /41/.

В непараметрических методах, таких как "метод центров" /116/ или метод Фиакко и Мак-Кормика /114/ целевая функция рассматривается как функция, задающая дополнительное искусственное ограничение, постепенно "уплотняемое" по мере получения информации в ходе решения задачи.

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

Прежде всего мы хотим сформулировать некоторую задачу аналогичную (А) . , учитывающую элементы неопределенности, свойственные реальной ситуации. Речь идет о той неопределенности в наших знаниях и суждениях, которая исключает возможность строгого логического описания условий задачи. В результате этого такие, например, предложения как h(jc)-Q или трансформируются в "нечеткие" высказывания: "значение (\.(х) ориентировочно равно нулю;' "значение Cj(cc) примерно /или "существенно","несколько", много" и так далее/ больше нуля и др. Подобная ситуация уже достаточно широко обсуждается в литературе, её формализованное изучение связано с именем Лотфи Заде, предложившего ввести понятие нечеткого /расплывчатого, размытого/ множества, лингвистической переменной, нечеткого бинарного отношения /3,4,16 - 18,106-113 /.

Итак,-первое,что мы привлечем для формулирования: нашей задачи (В>) , есть аппарат нечетких множеств. Нечетким множеством А на множестве X называется отображение f^te) /именуемое функцией принадлежности или функцией назначения/ :

Носителем нечеткого множества А называется подмножество точек множества X , для которых •

Понятие нечеткого множества и служит для описания отношений, содержащих элемент некоторой неопределенности /по

Л. Заде/.

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

Первая публикация по теории нечетких множеств появилась в 1965году /106/. jd ней Л.Заде изложил в постановочном плане концепцию нечетких множеств. С тех пор было опубликовано большое количество работ по теории и приложениям нечетких множеств.

Ряд работ /89,94,95,97', 103-105,110/ посвящен вопросам, связанным с нечеткими отношениями и их приложениями. Особо следует отметить работы /94,95,97/, где рассматривается подход к проблеме распознавания образов и принятия решения на основе нетранзитивных отношений предпочтения. В работе

С.А.Орловского /94/ сформулирован подход к проблеме принятия решения на основе множества недоминирующих альтернатив, а в его работе /95/ этот подход получает дальнейшее развитие и формулируется общая задача нечеткого математического программирования. Ряд исследований /4,22,51-58, 60,62,64,68,77,81,84/ посвящен проблеме принятия решения в нечетких условиях /с нечеткими целями и ограничениями/.

Особого внимания заслуживает работа /53/. Авторы Л.Заде и Р. Беллман рассматривают нечеткие цели и ограничения как эквивалентные понятия, а решение задачи математического программирования - как пересечение соответствующих нечетких множеств целей и ограничений, что приводит к естественному понятию оптимального решения многоцелевой задачи математического программирования, как множеству элементов "в наибольшей степени соответствующих" всем целям и ограничениям. Дальнейшая конкретизация данного подхода рассмотрена К.Танакой,Т.0кудой,К. Асаи /104,105/, предложившими многошаговую процедуру оптимизации, Язениным А. В. и ^кантом Г. П. /50/ для задачи линейного программирования с нечеткими целями и ограничениями, Курдшовым И.В., Мосоловым М.В., Назайкиным В.Е. /22/, использовавшими многошаговую человеко-машинную процедуру оптимизации многокритериальной задачи.

В данной работе рассматривается нелинейная задача математического программирования с нечеткими целями и ограничениями - вспомогательная задача для решения исходной задачи (А) . Мы заимствуем у Р.Беллмана и Л.Заде /4/ такие понятия как нечеткое решение и оптимальное нечеткое решение. Нам удалось сформулировать и решить задачу (В) благодаря найденному здесь способу задания функций принадлежности нечетких условий. Замечательно, что решение задачи (Е>) существенно проще решения задачи (А) .

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

Внешне метод М-функций напоминает известные методы штрафных функций, однако ему свойственны и определенные отличия /глава I, §5/. Наконец, существенно то, что общее доказательсво сходимости данного метода здесь приведено при меньших ограничениях по отношению к известным результатам, полученным для методов штрафных функций /19,33,41/. Этим вопросам посвящена первая глава работы.

Во второй главе рассмотрены некоторые алгоритмические . аспекты решения задачи математического программирования в нечетких условиях/задачи (S)/.

Получение исходной информации для формулирования задачи (в) может основываться на результатах экспертных оценок. Методам обработки экспертных оценок среди последних публикаций посвящены сборники работ /13,38/. Методика экспериментальной оценки функций принадлежности рассмотрена в статье А. Н. Борисова и И.Н.Осиса /II/.

Представляет определенный интерес проблема получения функций принадлежности некоторых нечетких множеств на основе экспертных оценок, данных в виде высказываний, которым поставлены в соответствие нечеткие множества. Этому посвящена третья глава диссертационной работы. Вводимые в этой главе процедуры основываются существенным образом на понятие меры нечеткости. Вопросу оценки меры нечеткости нечеткого множества посвящены работы /70,89,90/. В этих работах рассматривается ряд различных подходов к построению меры нечеткости: вероятностные подходы /89/ проводят некоторую аналогию меры нечеткости с энтропией и негэнтро-пией - мерой информации по Шеннону; А.Де Люка и С.Термини /70/ рассматривают построения меры нечеткости, не связанные с вероятностными аналогами. Наиболее общий подход предложен в работе /90/.

Проблема задания функций принадлежности, соответствующих нечетким целям и ограничениям, приводит нас к задаче выбора нечетких гипотез. Причем, гипотезы являются нечеткими множествами. Под решением понимаем нечеткое множество, удовлетворяющее некоторому критерию. Критерий строится на основе введения: понятий "нечеткости гипотезы","уклонения множеств" и "нечеткости ситуации". Кроме того, нечеткие множества трактуются как значения некоторой лингвистической переменной. Неформально под лингвистическойпеременной понимается переменная, значениями которой служат слова определенного языка. Более строго: лингвистической переменной называется пятерка: ( Х,Т(Х) , 7, Г, М^ , где X - название лингвистической переменной, Т(х) - терм-множество /множество значений переменной X/, У - универсальное множество, Г - порождащая грамматика терм-множества, М - семантика - совокупность правил, ставящих в соответствие каждому элементу из т(х) его "смысл" - нечеткое подмножество из У.

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

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

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

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

Итак, в качестве основных результатов в данной работе предлагается:

I/ метод М-фушщий - метод решения общей задачи математического программирования и доказательство его сходимости; 2/ математическое форэдулированиеи и решение задачи нелинейной оптимизации в нечетких условиях; 3/ алгоритм построения функций принадлежности, соответствующих нечетким условиям, на основе экспертных оценок; 4/ алгоритм и пакет программ решения задачи распознавания психо-физиологического состояния человека-оператора по показаниям вольт-амперных характеристик активных точек кожи.

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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