Нечеткие алгоритмы

Рассмотрим некоторые случаи выбора множеств, функций, операций, отношений. Пусть $$W, U,V$$ — непустые множества, тогда функцию $$f$$ из $$U\times V$$ в $$W$$ будем называть $$W$$ -функцией $$f$$ из $$U$$ в $$V$$ ; $$f(v|u)$$ есть степень, с которой значение функции в точке $$u$$ есть $$v$$.

$$W$$ -функция является вероятностной, если для любого $$u\in U$$ существует $$f(v|u)$$ и $$\(\sum\limits_{v \in V} {{{f(v|u) }} = {{1}}}\)$$.

$$W$$ -функция является детерминированной, если для любого $$u\in U$$ существует $$\(v_0 \in V\colon f(v_0 |u) = 1\)$$ и для любого $$\(v \ne v_0 \;F(v|u) = 0\)$$.

Если множество $$W$$ с определенными на нем операциями и отношениями записать в виде четверки $$\({{(W}}{{, }} \otimes {{, }} \oplus {{, }} \succ {{)}}\)$$, то:

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

Рассмотрим программу $$\pi$$, которую допускает $$W$$ -машина $$M$$. Для каждой пары меток $$L', L''\in L$$ и пары состояний $$m_{1},m_{2}\in M$$ будем писать $$\((L',m_1 )\xrightarrow{{{w}}}(L'',m_2 )\)$$, если в программе $$\pi$$ либо имеется инструкция вида $$\(L'\colon do F;\;go\;to\;L''\)$$, где $$w=M_{F}(m_{2}| m_{1})$$ есть степень, с которой осуществляется переход из состояния $$m_{1}$$ в состояние $$m_{2}$$, либо имеется инструкция вида $$\(L'\colon if\;P\;then\;go\;to\;(L_1 ,\ldots,L_n)\)$$, где $$\(m_1 = m_2 ,\;\;L'' = L_k\)$$ для некоторого $$k\colon 1\le k\le n$$ и $$w=M_{P}(k|m_{1})$$ есть степень, с которой осуществляется переход на метку $$L_{k}$$.

Выполнением программы $$\pi$$ на $$W$$ -машине $$M$$, допускающей $$\pi$$, называется конечная последовательность $$xL_{0}m_{0}\ldots L_{n}m_{n}y$$. Выполнение возможно тогда и только тогда, если $$\(w = w_0 \otimes w_1 \otimes .\ldots \otimes w_{n + 1} \ne 0\)$$, где $$w_{0}=M_{I}(m_{0}|x)$$, $$w_{n+1}=M_{O}(y|m_{n})$$, $$\(w_{i} \colon (L_{i - 1} ,m_{i - 1} )\xrightarrow{{w_i }}(L_i ,m_i )\)$$.

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

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

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

Обобщенная машина есть шестерка $$A=(K, S, \Psi, s_{0}, T,W)$$, где $$K$$ и $$S$$ — конечные непустые множества машинных инструкций и внутренних состояний соответственно, $$W$$ — непустое множество с отношением частичного порядка $$\( \succ\)$$ и операциями $$\( \otimes ,\;\; \oplus\)$$, удовлетворяющими свойствам коммутативности, ассоциативности и дистрибутивности, а также содержащие нулевой и единичный элементы; $$\Psi$$ — $$W$$ -функция переходов из состояния в состояние; $$\Psi\colon K\times S\to S$$ ; $$s_{0}$$ и $$T$$ — начальное состояние и множество финальных состояний.

Для цепочки инструкций $$k^{*}=k_{1} k_{2} \ldots k_{n}\in K^{*}$$ ( $$K^{*}$$ — множество всевозможных цепочек инструкций) переходов из состояния $$s_{0}$$ в $$s$$ определяется степенью $$\(\Psi (s_0 ,\,k_1 ,\,s_1 ) \otimes \Psi (s_1 ,\,k_2 ,\,s_2 ) \otimes \,\ldots\, \otimes \Psi (s_{n - 1} ,\,k_n ,\,s_n )\)$$.

Если $$l$$ — пустая цепочка инструкций, то задается расширенная $$W$$ -функция $$\Psi$$ следующим образом:$$\Psi (s,l,s') = \left\{ {\begin{array}{*{20}c} {0,} {\t{\char229}\t{\char241}\t{\char235}\t{\char232}\;s \ne s',} \\ {1,} {\t{\char229}\t{\char241}\t{\char235}\t{\char232}\;s = s'.} \\ \end{array} } \right.$$

Обобщенная нечеткая машина определяется парой $$(A,\Sigma)$$ , где $$A$$ — обобщенная машина, $$\Sigma$$ — конечное множество нечетких инструкций и каждая нечеткая инструкция $$\sigma$$ из $$\Sigma$$ есть $$W$$ -функция из $$S$$ в $$K$$.

Пусть задана некоторая обобщенная нечеткая машина $$(A,\sigma)$$. Выполнение последовательности $$\sigma= \sigma_{1}\sigma_{2} \ldots\sigma_{n}$$ на обобщенной машине $$A$$ есть последовательность$$s_{0} k_{1} s_{1} k_{2} \ldots k_{n}s_{n},\ \t{где}\ s_{i}\in S,\ k_{i}\in K,\ s_{n}\in T.$$ Весом, соответствующим выполнению, является элемент$$w \in W:\quad w = w_1 \otimes w'_1 \otimes w_2 \otimes w'_2 \,\ldots\,w_n \otimes w'_n ,$$ где$$w_i = \sigma _i (k_i |s_{i - 1} ),\quad w'_i = \psi (s_i |k_i ,s_{i - 1} ).$$

Выполнение возможно тогда и только тогда, если $$\(w \ne 0\)$$. Если $$\sigma_{i}$$ и $$W$$ принимают значения из различных множеств $$W$$ и $$V$$, то вес, соответствующий выполнению, будет определяться парой $$\( (w,v) = (w_1 \otimes \;\ldots\; \otimes w_n \,,\,v_1 \otimes \,\ldots \otimes v_n )\)$$. В этом случае говорят, что программа $$\sigma$$ выполнима с весом $$(w,v)$$, если $$(w,v)>(0,0)$$.

Пример. Пусть имеется последовательность инструкций для водителя автомобиля и карта местности. Водителю предлагается найти место назначения, используя карту и последовательность нечетких инструкций, описывающих маршрут. Для простоты изложения предположим, что все точки на плоскости имеют только целочисленные координаты. Типичные инструкции для водителя: "двигаться прямо около $$L$$ метров", "повернуть налево", "повернуть направо", "двигаться прямо до тех пор, пока не увидишь ...".

Сконструируем соответствующую $$W$$ -машину $$M$$. $$W$$ -машина имеет множество состояний памяти $$M$$ в виде упорядоченных троек $$\((a,b,\bar v)\)$$, где $$(a,b)$$ — точка на плоскости, соответствующая местонахождению автомобиля, $$\(\bar v\)$$ — единичный вектор направления движения автомобиля. Множество входов $$X=M$$ и множество выходов $$Y$$ состоят из упорядоченных пар $$(a,b)$$ ; $$M_{I}$$ — функция входов, соответствует тождественной функции; $$M_{O}$$ — функция выходов, соответствует функции, отображающей каждую тройку $$\((a,b,\bar v)\)$$ в $$(a,b)$$.

Машина $$M$$ не имеет ни одной функции условия. Каждой инструкции, приведенной выше, соответствует функция операции. При этом $$i$$ -я инструкция в последовательности инструкций может быть преобразована в инструкцию операции вида do $$F_{i}$$ ; go to $$L_{i}$$. Совокупность таких инструкций и инструкций start: go to $$L_{0}$$ и $$L_{n}$$: halt, где $$n$$ — длина последовательности, составляет программу $$\pi$$. Процесс выполнения программы $$\pi$$ на машине $$M$$ определяется последовательностью инструкций и картой местности. Краткости ради приведем только функцию операции для инструкции типа "двигаться прямо около $$L$$ метров":$$\begin{gathered} M_{F_L } = \left( {(a_2 ,b_2 ,\bar v_2 )|(a_1 ,b_1 ,\bar v_1 )} \right) = \\ =f_L \left( {\sqrt {(a_2 - a_1 )^2 + (b_2 - b_1 )^2 } } \right) \times G\left( {(a_2 ,b_2 ,\bar v_2 )|(a_1 ,b_1 ,\bar v_1 )} \right), \\ \end{gathered}$$ где $$f_{L}(d)$$ — степень (вес), соответствующая расстоянию $$d$$, $$\(G( (a_2 ,b_2 , \bar v_2 )$$ | $$(a_1 ,b_1 ,\bar v_1 ))\)$$ — вес, соответствующий утверждению: "точка $$(a_{2},b_{2})$$ и направление $$v_{2}$$ достижимы при движении прямо из точки $$(a_{1},b_{1})$$ по направлению $$v_{1}|$$ ".

Примеры функций $$f_{L}$$ и $$G:\colon f_{L}(d)=[1+((L-d)/c)^{2}]^{-1}$$, где $$c$$ — параметр: $$\( G\left( {(a_2 ,b_2 ,\bar v_2 )|(a_1 ,b_1 ,\bar v_1 )} \right) = 1 \)$$ тогда и только тогда, если $$\(\bar v_1 = \bar v_2\)$$ вектор из $$(a_{1},b_{1})$$ в $$(a_{2},b_{2})$$ параллелен $$\(\bar v_1\)$$ и каждая точка на отрезке линии, проходящей через $$(a_{1},b_{1})$$ и $$(a_{2},b_{2})$$, имеющая целые координаты, есть точка на карте. Очевидно, что $$f_{L}$$ зависит только от $$L$$, а $$G$$ зависит только от карты. Другие функции операций могут быть построены аналогично. Нечеткий алгоритм, описывающий движение автомобиля к месту назначения, определяется конкретной последовательностью инструкций приведенного вида, которая реализуется на рассмотренной $$W$$ -машине.

Приведем другие примеры применения нечетких алгоритмов.

Способы выполнения нечетких алгоритмов

Для реализации поиска какого-либо выполнения нечеткого алгоритма $$\sigma = \sigma_{1}\sigma_{2} \ldots \sigma_{n}$$ необходимо определить правила выбора машинной инструкции на каждом шаге. Правила выбора машинной инструкции и переходов из состояния в состояние зависят от типа нечеткой машины.

Выбор машинной инструкции:

a. Нечеткий выбор. Машина выбирает машинную инструкцию $$k_{i}\in K(i,s_{i-1})$$ с наивысшей степенью на каждом шаге $$\sigma_{i}\colon \sigma_{i}(s_{i-1},k)\ge \sigma_{i}(s_{i-1},k')$$ для любой инструкции $$k'\in K$$.

b. Вероятностный выбор. Машина на каждом шаге нечеткой инструкции $$\sigma_{i}$$ выбирает инструкцию $$k\in K(i,s_{i-1})$$ с вероятностью $$p$$, пропорциональной нечеткой степени $$\sigma_{i}(s_{i-1},k)$$$$p = \sigma _i (s_{i - 1} ,k)/\sum\limits_{k'} {\sigma _i (s_{i - 1} ,k')} ,\quad \quad k' \in K(i,s_{i - 1} ).$$

c. Недетерминированный выбор. Машинная инструкция $$k\in K(i,s_{i-1})$$ выбирается недетерминированным образом.

Определение перехода из состояния в состояние:

a. Нечеткий переход. Машина переходит из состояния $$s_{i}$$ в состояние $$\(s\colon \Psi (s_i ,k_i ,s) \geqslant \Psi (s_i ,k_i ,s')\)$$ для любого состояния $$\(s' \in K(i,s_{i - 1} ,k_i )\)$$.

b. Вероятностный переход. Машина переходит из состояния $$s_{i}$$ в состояние $$s$$ с вероятностью$$p = \frac{\Psi (s_{i - 1} ,k_i ,s)}{\displaystyle \sum\limits_{s' \in K(i,s_{i - 1} ,k_i )}\Psi (s_{i - 1} ,k_i ,s')}.$$

c. В случае детерминированного перехода состояние, пригодное для машины, единственным образом определяется функцией переходов $$\Psi$$.

Процедура возврата:

a. Вернуться на предыдущую нечеткую инструкцию.

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

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

Представление нечеткого алгоритма в виде графа

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

Определение. Графом $$G$$ называется тройка $$(V,U, \varphi)$$, где $$V=\{v\}$$ — множество элементов, называемых вершинами графа; $$U=\{u\}$$ множество элементов, называемых ребрами графа, причем $$V\cap U=\varnothing$$ ; $$\varphi$$ — функция, ставящая в соответствие каждому ребру $$u\in U$$ упорядоченную или неупорядоченную пару вершин $$(v_{1},v_{2})$$, $$v_{1}$$ и $$v_{2}$$ называются концами ребра $$u$$. Если множество $$U\cup V$$ конечно, то граф называется конечным. Если $$\varphi(u)=(v_{1},v_{2})$$ — упорядоченная пара (т.е. $$(v_{1},v_{2})\ne (v_{2},v_{1})$$ ), то ребро $$u$$ называется ориентированным ребром или дугой, исходящей из вершины $$v_{1}$$ и входящей в вершину $$v_{2}$$ ; $$v_{1}$$ называется началом, $$v_{2}$$ — концом дуги $$u$$. Граф, все ребра которого ориентированные, называется ориентированным графом.

Определение. Последовательность вершин и ребер графа $$G\(v_{i_0 } u_1 v_{i_2 } u_2 \ldots v_{i_{n - 1} } u_n v_{i_n }\)$$ называется путем $$\([v_{i{}_0} ,v_{i_n } ]\)$$ из вершины $$\(v_{i{}_0}\)$$ в вершину $$\(v_{i{}_n}\)$$, если $$\(\varphi (u_k ) = (v_{i_{k - 1} } ,v_{i_k } )\)$$ для $$k=1,2,\ldots,n$$. Вершина $$\(v_{i{}_0}\)$$ называется началом, а $$\(v_{i{}_n}\)$$ — концом пути; число $$n$$ называется длиной пути.

Определение. Нечеткая программа есть четверка $$(X,Y,Z,G)$$, где $$X=(x_{1},\ldots,x_{l})$$ — вектор входа, $$Y=(y_{1},\ldots,y_{n})$$ — вектор программы (внутренние переменные), $$Z=(z_{1},\ldots,z_{m})$$ — вектор выхода, $$G$$ — ориентированный граф: