ГЛАВА 8. НЕЧЕТКИЕ АЛГОРИТМЫ

§ 8.1. Определение нечеткого алгоритма

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

Под алгоритмом понимается точно определенное правило действий (программа), для которого задано указание, как и в какой последовательности это правило необходимо применять к исходным данным задачи, чтобы получить ее решение [10]. Характеристиками алгоритма являются» а) детерминированность (определенность) — однозначность результата процесса при заданных исходных данных; б) дискретность определяемого алгоритмом процесса — расчлененность его на отдельные элементарные акты, возможность выполнения которых человеком или машиной не вызывает сомнения; в) массовость — исходные данные для алгоритма можно выбрать из некоторого множества данных (потенциально бесконечного), т. е. алгоритм должен обеспечивать решение любой задачи из класса однотипных задач.

Нечеткий же алгоритм, понятие которого впервые введено в работе [55], грубо говоря, определяется упорядоченным множеством нечетких инструкций (нечетких высказываний), содержащих понятия, формализуемые нечеткими множествами. Под нечеткой инструкцией понимается инструкция, содержащая нечеткие понятия [53], например, «пройти около 100 метров», а под машинными инетрукциями — инструкции, не содержащие никаких нечетких понятий, например, «пройти 100 метров». Здесь и далее четкие инструкции мы будем называть машинными инструкциями, чтобы подчеркнуть возможность моделирования нечетких алгоритмов на ЭВМ, воспринимающих только четкие инструкции.

Приведем точное определение нечеткого алгоритма из [42], обобщающее все известные в настоящее время определения [24, 48, 55]. Для формулировки определения первоначально вводится ряд определений и обозначений.

Во-первых, в [42] вместо интервала [0, 1], общепринятого множества значений функции принадлежности, рассматривается

непустое множество с отношением частичного порядка У и операциями удовлетворяющими свойствам коммутативности, ассоциативности и дистрибутивности, а также содержащее нулевой и единичный элементы: а а.

Во-вторых, рассматриваются инструкции следующего вида:

где (множество символов меток инструкций); (множество символов операторов или функций); (множество символов -значных предикатов или условий).

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

В-третьих, определяется понятие -машины. -машина есть функция определенная на множество символов для которых существуют множество входов X, множество состояний памяти и множество выходов а также выполнены условия:

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

В работах [24, 48, 41] формулируются различные определения нечетких алгоритмов, обобщаемые приведенным выше определениям: в [41] рассматриваются две эквивалентные формулировки нечетких алгоритмов, аналогичные определениям алгоритмов Тьюринга [52] и Маркова в [24, 48] рассматриваются нечеткие алгоритмы, которые описываются конечными нечеткими автоматами, т. е. такие алгоритмы, для которых у соответствующих -машин из приведенного определения множества являются конечными.

Пример 8.1. Конкретные типы алгоритмов могут быть получены посредством выбора множеств , функций (входов, действий, выходов, условий), операций

отношения X Рассмотрим некоторые случаи выбора множеств, функций, операций, отношений [42]. Пусть — непустые множества, тогда фупкцшо из в будем называть -функцией из в есть степень, с которой значение функции в точке и есть -функция является вероятностной, если для любого существует

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

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

Рассмотрим программу , которую допускает -машина Для каждой пары меток и пары состояний будем писать если в программе либо имеется инструкция вида где есть степень, с которой осуществляется переход из состояния в состояние либо имеется инструкция вида где — для некоторого к: есть степень, с которой осуществляется переход на метку

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

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

Приведем другую формулировку нечеткой программы, которая была введена в [24], а дальнейшее ее обобщепие и приложения были обсуждены в [48]. В [42] показано, что

рассматриваемая ниже формулировка является частным случаем выше приведенного определения нечеткой программы, так как в [24, 48] машины рассматриваются с конечным множеством состояний, которые моделируются конечными автоматами.

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

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

-функция переходов из состояния в состояние; — начальное состояние и множество финальных состояний.

Для цепочки инструкций (К — множество всевозможных цепочек инструкций) переход из состояния в определяется степенью

Если I — пустая цепочка инструкций, то задается расширенная -функция для любой цепочки к следующим образом:

Рис. 8.1. Выполнение нечеткой инструкция а

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

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

Рассмотрим различные типы нечетких машин, полученные при различных

Пример 8.2. Если в определении обобщенной машины конкретизировать различным образом то получим различные типы обобщенных машин. Если шах, то это нечеткая машина. Если то это недетерминированная машина. Если и существует единственное для любых , то это детерминирванная машина. Если то это вероятностная машина.

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

Таблица 8.1

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

Выполнение последовательности на обобщенной машине А есть последовательность

Весом, соответствующим выполнению, является элемент

где

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

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

Пример 8.4. Пусть [24, 42, 48] имеется последовательность инструкций для водителя автомобиля и карта местности (города). Водителю предлагается найти место назначения, используя карту и последовательность нечетких инструкций, описывающих маршрут. Для простоты изложения предложим, что все точки на плоскости имеют только целочисленные координаты. Типичные инструкции для водителя: «двигаться прямо около метров», «повернуть налево», «повернуть направо», «двигаться прямо до тех пор, пока не встретишь...» (станцию, светофор).

Сконструируем соответствующую И-машину -машнна имеет множество состояний памяти М в виде триад где — точка на плоскости, соответствующая местонахождению автомобиля, — единичный вектор направления движения автомобиля. Множество входов множество выходов состоит из упорядоченных пар — функция входов, соответствует тождественной функции; — функция выходов, соответствует функции, отображающей каждую тройку

Машина не имеет ни одной функции условия. Каждой инструкции, приведенной выше, соответствует функция операции. При этом инструкция в последовательности инструкций может быть преобразована в инструкцию операции вида Совокупность таких инструкций и инструкций где — длина последовательности, составляет программу . Процесс выполнения программы на машине определяется последовательностью инструкций и картой местности. Для краткости приведем только функцию операций для инструкций типа «двигаться прямо около метров»:

где — степень (вес), соответствующая расстоянию — вес, соответствующий утверждению:

«точка и направление достижимы при движении прямо из точки по направлению

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

Пример 8.5. В [24] рассматривается нечетко-детерминированная машина (в табл. 8.1 тип 2). Функция переходов из состояния в состояние считается детерминированной, а степень выбора машинной инструкции когда машина находится в состоянии и получает нечеткую ипструкцию определяется функцией , где — функция осуществимости, а k — функция выполнимости. Функция дает объективные ограничения на выполнение определенных машинных инструкций. Например, если когда машина в состоянии получает нечеткую инструкцию о, то машинная инструкция к может быть выполнена. Аналогично, если то инструкция к не может быть выполнена. С другой стороны, функция к дает субъективную оценку выполнимости машинной инструкции в рассматриваемой ситуации. Например, если то, когда машина находится в состоянии и получена нечеткая инструкция о, субъективно машинная инструкция дает лучшее выполнение, чем Функции рассматриваются для независимого анализа субъективных и объективных ограничений.

В [6] рассматриваются области применения нечетких алгоритмов. Приводятся следующие примеры:

— алгоритмы определения сложного нечеткого понятия А через более простые понятия, которые легко описать нечеткими множествами; результатом применения таких алгоритмов к некоторому элементу и области рассуждений будет степень принадлежности и понятию А (степень, с которой элемент и может характеризоваться понятием

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

— алгоритмы описания отношений между нечеткими переменными, например, в виде последовательности нечетких

инструкций типа: «если х мало и х увеличить слегка, то у увеличится слабо»; такие алгоритмы позволяют приближенно описывать поведение систем, входные и выходные сигналы которых являются нечеткими подмножествами;

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