Нечеткие алгоритмы обучения

Моделируется поиск глобального экстремума функции следующим образом:

область определения целевой функции делится на некоторое число подобластей (форма подобластей постоянно меняется) и описывается некоторым множеством точек;

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

выбирается состояние с максимальным значением функции принадлежности (эта точка называется кандидатом);

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

когда подобласть пересекается с некоторой другой, или две точки-кандидаты находятся в одной подобласти, то подобласти разделяются, если степень разделения большая, или объединяются, если степень разделения малая;

точки-кандидаты выбираются на этапе локального поиска в подобласти, затем во всей области среди точек-кандидатов ищется глобальная оптимальная точка;

глобальный и локальный поиск осуществляется поочередно.

Алгоритм поиска глобального экстремума приведен на рис.12.2.

(рис 12.2)

Пусть $$S$$ — множество состояний, $$V$$ — выходной универсум, $$\sigma$$ — функция выхода (функция принадлежности, указывающая степень оптимума в состоянии $$s$$ ), $$I(t)$$ — текущее значение целевой функции, $$I_{0}$$ — среднее значение $$I(t)$$.

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

если $$I(t)>I_{0}$$, то попытка успешна и$$\mu _{\delta (t)} (s_k ,s_j ) = \alpha _k \mu _{\delta (t)} (s_k ,s_j ) + (1 - \alpha ),$$

если $$I(t)\le I_{0}$$, то попытка неудачна и$$\mu _{\delta (t + 1)} (u_i ,s_j ) = \alpha \mu _{\delta (t)} (u_i ,s_j ),$$ где $$\alpha = 1-|(I(t)-I_{0})/I_{0}|$$ ; $$\alpha<1$$ — гарантируемая сходимость.

В случае локального поиска:

если $$I(t)>I_{0}$$, то$$\mu _{\delta (t + 1)} (u_i ,s_j ) = \alpha \mu _{\delta (t)} (u_i ,s_j ) + (1 - \alpha ),$$

если $$I(t)\le I_{0}$$, то$$\mu _{\delta (t + 1)} (u_i ,s_j ) = \alpha \mu _{\delta (t)} (u_i ,s_j ).$$

Обучение на основе условной нечеткой меры

Пусть $$X=\{x_{1}, \ldots ,x_{n}\}$$ — множество причин (входов) и $$Y=\{y_{1}, \ldots ,y_{m}\}$$ — множество результатов. Если $$h$$ — функция из $$X$$ в интервал $$[0,1]$$, $$\(h(x_1 ) \leqslant \;\ldots\; \leqslant h(x_n )\)$$ и $$g_{x}$$ — нечеткая мера на $$X$$, то$$\int\limits_X {h(x)g_x ( \cdot )} = \mathop {\max }\limits_{i = 1,...,n} \;\min (h(x_i ),g_X (H_i )),$$ где $$H_{i}=\{x_{i}, \ldots ,x_{n}\}$$.

Задача состоит в оценке (уточнении) причин по нечеткой информации.

Пусть $$g_{Y}$$ — нечеткая мера на $$Y$$, $$g_{Y}$$ связана с $$g_{X}$$ условной нечеткой мерой $$\sigma_{Y}(\cdot | x)$$:$$g_Y = \int\limits_X {\sigma _Y ( \cdot |x)g_X } .$$

Предполагается следующая интерпретация вводимых мер: $$g_{X}$$ оценивает степень нечеткости утверждения "один из элементов $$X$$ был причиной", $$\sigma_{Y}(A| x)$$, $$A\subset Y$$ оценивает степень нечеткости утверждения "один из элементов $$A$$ является результатом благодаря причине $$x$$ "; $$g_{Y}(\{y\})$$ характеризует степень нечеткости утверждения: " $$y$$ — действительный результат".

Пусть $$\mu_{A}(y)$$ описывает точность информации $$A$$, тогда по определению $$\(g_Y (A) = \int\limits_X {\mu _A (y)g_X }\)$$.

Метод обучения должен соответствовать обязательному условию: при получении информации $$A$$ нечеткая мера $$g_{X}$$ меняется таким образом, чтобы $$g_{Y}(A)$$ возрастала. Предположим, что $$g_{X}(\cdot)$$ и $$\sigma_{Y}( \cdot|x)$$ удовлетворяют $$\lambda$$ -правилу. Пусть $$\sigma_{Y}(A|x_{i})$$ является убывающей, тогда$$g_Y (A) = \mathop \vee \limits_{i = 1}^n \left[ {\sigma _Y (A|x_i ) \wedge g_X (F_i )} \right],$$ где $$F_{i}=\{x_{1}, \ldots, x_{i}\}$$. При этих условиях существует $$l$$:$$\begin{gathered} g_Y (A) = \sigma _Y (A|x_l ) \wedge g_X (F_l ), \\ \sigma _Y (A|x_l ) \wedge g_X (F_l ) \geqslant \sigma _Y (A|x_{l - 1} ) \wedge g_X (F_{l - 1} ), \\ \sigma _Y (A|x_l ) \wedge g_X (F_l ) > \sigma _Y (A|x_{l + 1} ) \wedge g_X (F_{l + 1} ). \\ \end{gathered}$$

Обучение может быть осуществлено увеличением тех значений $$g_{i}$$ ( $$i=1, \ldots ,n$$ ) нечеткой меры $$g_{X}$$, которые увеличивают $$g_{Y}(A)$$, и уменьшением тех значений $$g_{i}$$ ( $$i=1, \ldots ,n$$ ) меры $$g_{X}$$, которые не увеличивают $$g_{Y}(A)$$. Можно показать, что на величину $$g_{Y}(A)$$ влияют только такие $$g_{i}$$, что $$1\le i\le l$$. Следовательно, нечеткий алгоритм обучения следующий:$$\begin{gathered} g^i = \alpha g^i + (1 - \alpha )\sigma _Y (A|x_i );\quad \quad i = 1,\ldots,l; \\ g^i = \alpha g^i ;\quad \quad i = l + 1,\ldots,n. \\ \end{gathered}$$

Параметр $$\alpha\in[0,1]$$ регулирует скорость обучения, т.е. скорость сходимости $$g^{i}$$. Чем меньше $$\alpha$$, тем сильнее изменяется $$g^{i}$$. В приведенном алгоритме нет необходимости увеличивать $$g^{i}$$ больше, чем на $$\sigma_{Y}(A|x_{i})$$, так как большое увеличение $$g^{i}$$ не влияет на $$g_{Y}(A)$$. Приведем некоторые свойства модели обучения.

Свойство 1. Если повторно поступает одна и та же информация, то происходит следующее:

a. новое $$g^{i}$$ больше старого $$g^{i}$$ ( $$i=1, \ldots ,l$$ ) и новое $$g^{i}$$ меньше старого $$g^{i}$$ ( $$i=l+1, \ldots ,n$$ ), следовательно, новая мера $$g_{Y}(A)$$ не меньше старой меры $$g_{Y}(A)$$, и новая мера$$g_Y (A) = \sigma _Y (A|x_k ) \wedge g_X (F_k ),\quad \quad k \leqslant l;$$

b. при предположении $$\sigma_{Y}(A|x_{1}) > \sigma_{Y}(A|x_{2})$$, $$k<l$$, $$g^{1}$$ сходится к $$\sigma_{Y}(A|x_{1})$$ и $$g^{i}$$ сходится к 0 для $$i=2, \ldots ,n$$.

Свойство 2. Если поступает одна и та же информация повторно: $$\(h_A (y) = c\)$$ для всех $$y$$, то $$\(\sigma _Y (A|x) = \int\limits_X {c\sigma _Y ( \cdot |x)} = c,\quad \sigma _Y (A) = c \wedge g_X(X)\)$$.

Следовательно, $$l=n$$ и $$g^{i}$$ сходится к $$c$$ для всех $$i$$.

Свойство 3. Предельное значение $$g^{i}$$ не зависит от начального значения тогда, когда на вход повторно поступает одна и та же информация.

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

$$x_{1}$$ — оценивает число точек, проанализированных на предыдущих шагах;

$$x_{2}$$ — оценивает среднее значение функции по результатам предыдущих шагов;

$$x_{3}$$ — оценивает число точек, значение функции в которых принадлежит десятке лучших в своей области;

$$x_{4}$$ — оценивает максимум по прошлым попыткам;

$$x_{5}$$ — оценивает градиент функции.

В описанном случае $$g_{X}$$ показывает степень важности подмножеств критериев и $$\sigma_{Y}(\{y_{j}\}|x_{i})$$ оценивает предположение о нахождении экстремума в блоке $$y_{j}$$ в соответствии с критерием $$x_{i}$$. Например, $$\sigma_{Y}(\{y_{j}\}|x_{i})$$ может зависеть от числа ранее проанализированных точек в блоке $$y_{j}$$. Пусть входная информация $$A$$ определяется формулой$$\mu _A (y_j ) = \frac{{p_j - \mathop {\min }\limits_k \;p_k }} {{\mathop {\max }\limits_k \;p_k - \mathop {\min }\limits_k \;p_k }},$$ где $$p_{k}$$ — максимум анализируемой функции, найденный к рассматриваемому моменту в блоке $$y_{j}$$. Очевидно, что $$A$$ сходится к максимизирующему множеству функции. На каждой итерации осуществляется следующее: проверяется заданное число новых точек; число этих точек выбирается пропорционально $$g_{Y}(\{y_{j}\})$$ ; в~каждой точке $$y_{j}$$ вычисляется и нормализуется мера $$\sigma_{Y}(\cdot |x_{i}$$ ); нормализуется $$g_{X}$$ ; по $$\sigma_{Y}$$ и $$\sigma_{X}$$ вычисляется $$g_{Y}(\{y_{j}\})$$, а затем $$g_{Y}(A)$$ ; посредством правил подкрепления корректируется $$g_{Y}(\{x_{i}\})$$. Затем выполняется новая итерация, и так до тех пор, пока не сойдется $$g_{Y}$$.

Адаптивный нечеткий логический регулятор

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

(рис 12.3)

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

Получение отклика;

Преобразование значения отклонения к нечеткому виду, такому, как "большой", "средний";

Оценка входного значения по заранее сформулированным правилам принятия решения с помощью композиционного правила вывода;

Вычисление детерминированного выхода, необходимого для регулирования процесса.

(рис 12.4)

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

$$U(t)$$ — управление, генерируемое НЛРУП;

$$E(t)$$ — ошибка (отклонение от устанавливаемого выходного значения процесса $$s$$ );

$$S$$ — желаемое значение выхода управляемого процесса, $$C(t)= E(t) - E(t - 1)$$ ;

$$P(t)$$ — модификация управления.

Правила НЛРУП имеют форму: if $$E=E_{i}$$ then if $$C=C_{i}$$ then $$U=U_{i}$$.

Правила НЛРУ имеют форму: if $$E=E_{j}$$ then if $$C=C_{j}$$ then $$P=P_{j}$$.

Здесь $$E_{i}$$, $$E_{j}$$, $$C_{i}$$, $$C_{j}$$, $$U_{i}$$, $$P_{j}$$ — предварительно описанные нечеткие множества. Символ $$P(t)$$ используется для модификации стратегии управления следующим образом: в нечетком правиле $$i$$, которое ухудшает течение процесса, заменяется значение управления $$U$$ на $$U_{i}'=U_{i}\otimes p_{i}(t)$$. Правило $$i$$ в НЛРУП заменяется на правило if $$E=E_{i}$$ then if $$C=C_{i}$$ then $$U=U_{i}'$$.

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

Алгоритм формирования нечеткого отношения предпочтения

Пусть $$R$$ — множество таких альтернатив, что каждое $$S\in R$$ характеризуется набором оценок по $$n$$ признакам: $$S=\{t_{1}, \ldots ,t_{n}\}$$, и пусть $$B$$ — семейство всех непустых конечных подмножеств множества $$R$$. Для некоторого $$\(R' \in B\)$$ известно подмножество выбранных альтернатив $$\(R'' \subset R'\)$$, т.е. для любых $$S''\in R''$$ и $$\(S' \in R'\backslash R''\)$$ имеет место доминирование $$\(S'' \succ S'\)$$. Предварительно, при анализе исходного множества альтернатив, сформирован эталонный набор нечетких оценок $$\(A^0 = (t_1^0 ,\ldots,t_n^0 )\)$$. Значения функции принадлежности нечеткой оценки $$\(t_i^0\)$$ указывают на степень близости значений $$i$$ -го признака к значениям, определяющим идеальную альтернативу. Используя множество предпочтений$$E = \left\{ {(S'',S'):\quad S'' \in R'',\quad S' \in R'\backslash R''} \right\},$$ требуется найти обобщенные правила предпочтения на множестве $$R$$.

Пример. Рассмотрим задачу выбора для рыболовецкого судна рационального района промысла с учетом следующих показателей: $$u_{1}$$ — время перехода в район лова, $$u_{2}$$ — прогноз вылова, $$u_{3}$$ — стоимостная характеристика прогнозируемого объекта лова, $$u_{4}$$ — гидрометеоусловия. Показатели, в сущности, играют роль лингвистических переменных.

Лицу, принимающему решение, предложены альтернативы $$S_{1}$$ — $$S_{6}$$ (см.табл.12.1). Пусть выбрана альтернатива $$S_{1}$$. Для обучения формируются две таблицы:

$$\[ \begin{gathered} K_1 = \left\{ {(S_1 ,S_2 ),(S_1 ,S_3 ),(S_1 ,S_4 ),(S_1 ,S_5 ),(S_1 ,S_6 )} \right\}, \\ K_2 = \left\{ {(S_2 ,S_1 ),(S_3 ,S_1 ),(S_4 ,S_1 ),(S_5 ,S_1 ),(S_6 ,S_1 )} \right\}, \\ \end{gathered}$$

	U1	U2	U3	U4		U1	U2	U3	U4
S1	хор.	хор.	хор.	уд.	S1	плох.	хор.	плох.	уд.
S2	оч. хор.	плох.	хор.	уд.	S2	уд.	хор.	хор.	неуд.
S3	оч. хор.	хор.	хор.	неуд.	S3	плох.	хор.	хор.	уд.
S4	уд.	хор.	хор.	уд.	S4	уд.	хор.	норм.	уд.
S5	оч. плох.	хор.	хор.	уд.	S5	уд.	норм.	норм.	уд.
S6	хор.	норм.	плох.	уд.	S6

Для каждой пары наборов $$(S_{i},S_{j})$$ вычисляются оценки сравнения $$i$$ -го элемента первого набора с $$i$$ -м элементом второго набора:$$\left. {\begin{array}{*{20}c} {(t'_1 ,...,t'_n )} \\ {(t''_1 ,...,t''_n )} \\ \end{array} } \right\} \to (L^\alpha (t'_1 ,t''_1 ),...,L^\alpha (t'_n ,t''_n )),$$ где $$\alpha$$ определяет конкретный оператор, например, нечеткую меру сходства.

В результате получаются две таблицы наборов нечетких оценок поэлементного сравнения. На основе полученных таблиц, используя логические операторы и логические функции двух переменных, выделяются полезные признаки и минимальный базис. Содержательное значение утверждения, соответствующего минимальному базису, следующее:$$\begin{gathered} \quad \quad \quad \quad \Phi (S_i ,S_j ) \succ \Phi (S_j ,S_i ) = \hfill \\ = (x_1^i \succ x_1^j ) \ (x_2^i \succ x_2^j ) \ (x_4^i \succ x_4^j ) \succ (x_1^i \prec x_1^j ) \ (x_2^i \prec x_2^j ) \ (x_4^i \prec x_4^j ), \hfill \\ \end{gathered}$$ где $$\(x_k^m\)$$ — лингвистическое значение $$k$$ -го показателя, $$\Phi$$ — логический признак. Физический смысл приведенного утверждения: район $$S_{i}$$ предпочтительнее района $$S_{j}$$, если утверждение [(время перехода до $$S_{i}$$ "меньше", чем до $$S_{j}$$ ), и (прогноз вылова в $$S_{i}$$ "больше", чем в $$S_{j}$$ ), и (погодные условия в $$S_{i}$$ "лучше", чем в $$S_{j}$$ )] более истинно, чем обратное утверждение [(время перехода до $$S_{i}$$ "больше", чем до $$S_{j}$$ ), и (прогноз вылова в $$S_{i}$$ "меньше", чем в $$S_{j}$$ ), и (погодные условия в $$S_{i}$$ "хуже", чем в $$S_{j}$$ )].

Далее предположим, что среди неизвестных ситуаций $$S_{7}$$ - $$S_{11}$$ (табл. 12.1) необходимо выбрать лучшую альтернативу, используя минимальный базис. В табл. 12.2 изображена матрица предпочтений $$M=(\mu^{ij}(K_{1}) | \mu^{ij}(K_{2}))$$, элементы которой вычислялись посредством гарантированной оценки$$\[ \mu ^{ij} (K_1 ) = \mathop {\max }\limits_{v \in [0,1]} \;\mu _{H_1 (S_i ,S_j )} (v),$$

	S7	S8	S9	S10	S11
S7		0,88 0,38	1 0,38	0,88 0,38	0,88 0,38
S8	0,75 1		0,75 1	0,75 1	0,75 1
S9	1 0,38	0,88 0,38		0,88 0,38	0,88 0,38
S10	1 0,38	1 0,38	1 0,38		1 0,38
S11	0,88 0,38	0,88 0,38	0,88 0,38	0,88 0,38

где $$\( H_i (S_1 ,S_2 ) = \mathop \cap \limits_j \left( {C_j^i \cap C_j (S_1 ,S_2 )} \right),\) \(C_j (S_1 ,S_2 )\)$$ — значение $$j$$ -го признака на паре альтернатив $$\((S_1 ,S_2 )\), \(C_j^i\)$$ — значение $$j$$ -го признака на парах альтернатив $$i$$ -го класса ( $$i=1,2$$ ). Каждый элемент матрицы содержит два значения. Левое значение указывает степень, с которой $$S_{i}$$ доминирует над $$S_{j}$$. Правое значение указывает степень, с которой $$S_{j}$$ доминирует над $$S_{i}$$. Для построения нечеткого графа предпочтений альтернатив (рис.12.5) используется следующее правило определения отношения доминирования $$D$$:$$D(S_i ,S_j ) = \left\{ {\begin{array}{*{20}c} {S_i \succ S_j ,} {\t{\char229}\t{\char241}\t{\char235}\t{\char232}\;\mu _1 \geqslant \mu _2 ;} \\ {S_j \succ S_i } {\t{\char229}\t{\char241}\t{\char235}\t{\char232}\;\mu _1 \leqslant \mu _2 ;} \\ \end{array} } \right.$$ где$$\mu _1 = \mu ^{ij} (k_1 ) \vee \mu ^{ji} (k_2 ),\quad \mu _2 = \mu ^{ij} (k_2 ) \vee \mu ^{ji} (k_1 ).$$

(рис 12.5)

Согласно рис. 12.5, $$S_{10}$$ является недоминируемой альтернативой, т.е. не существует альтернативы, которая с ненулевой степенью доминирует над $$S_{10}$$.

Алгоритм уточнения лингвистических критериев

Глобальные представления ЛПР о выборе альтернатив формулируются в виде глобального критерия, и решение многокритериальной задачи сводится к построению композиции $$\(M_1 \circ M_2 = M\)$$, где$$\begin{gathered} M_1 \colon\Im (U^n ) \to \Im (Q^m ),\quad U^n = U_1 \times \ldots \times U_n ,\quad Q^m = Q_1 \times \ldots \times Q_m , \\ M_2 \colon\Im (Q^m ) \to \Im (Q), \\ \end{gathered}$$ $$Q_{i}$$, $$Q$$ — множества значений признаков, локальных и глобального критериев, соответственно. $$M_{1}$$ и $$M_{2}$$ формируются на основе высказываний типа: "если значения признаков $$u_{1}, \ldots ,u_{n}$$, характеризующие альтернативу $$u_{i}$$, оцениваются термами $$t_{1i}, \ldots ,t_{ni}$$, то альтернатива удовлетворяет $$j$$ -му критерию с оценкой $$t_{n+j,i}$$ ".

$$M_{1}$$ и $$M_{2}$$ описываются наборами$$\begin{gathered} M_1 = \left\{ {(t_{1i} ,\ldots,t_{ni} ,t_{n + j,i} )|n + 1 \leqslant j \leqslant n + k,\;i = 1,m_1 } \right\}, \\ M_1 = \left\{ {(t_{n + 1i} ,\ldots,t_{n + k\,i} ,t_{n + k + 1,i} )|\;i = 1,\ldots,m_2 } \right\}. \\ \end{gathered}$$

Степень удовлетворения глобальному критерию для альтернативы $$u^{i}\in U^{n}$$ вычисляется следующим образом:$$w(u^i ) = \bigcup\limits_{t^p \in M_2 } {\left( {\bigcup\limits_{t^e \in M_1 } {u^i \circ t^e } } \right)} \circ t^p .$$

В процессе обучения уточняются оценки глобального и локальных критериев на основе сравнения выбранных ЛПР альтернатив $$\(R''\)$$ из множества предъявленных $$\(R' \supset R''\)$$. $$M$$ заменяется некоторым $$\(\tilde M\)$$, подтверждающим соответствующий выбор:$$\tilde w(u^i ) \prec \tilde w(u^j )\quad \t{\char228}\t{\char235}\t{\char255}\quad u^i \in R',\;\;u^j \in R'\backslash R''.$$

Обучение осуществляется в два этапа: формирование обобщенных описаний предпочтения ЛПР; модификация M при несовпадении предпочтений ЛПР с порядком оценок $$w(u)$$. На втором этапе выполняется следующее: генерация допустимых наборов оценок показателей; определение отношения предпочтения на парах сгенерированных альтернатив; выделение из $$M=M_{1}\cup M_{2}$$ наборов, не подлежащих корректировке; корректировка оценок по критериям.