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

Размещено на http://www.allbest.ru/

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

И.А. Ходашинский

П.А. Дудин

Томский государственный университет систем управления и радиоэлектроники, Томск

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

Широкое применение нечетких систем для решения проблем автоматического управления, прогнозирования, распознавания образов, принятия решений заставляет специалистов искать эффективные методы построения таких систем, для идентификации которых наряду с алгоритмами оптимизации, основанными на производных, применяются метаэвристики, чаще всего генетические алгоритмы и нейронные сети. В последнее время для этих целей стали применяться алгоритмы муравьиной колонии (АМК). В работах [Juang et al., 2009], [Tao et al., 2009], [Juang et al., 2007] АМК использован для настройки нечетких правил при решении задачи построения нечеткого регулятора. В работе [Casillas et al., 2007] задача обучения нечеткой системы моделирования сформулирована как комбинаторная проблема оптимизации и для ее решения применен модифицированный АМК. Совместное применение АМК и градиентного метода для идентификации нечетких систем представлена в работе [Ходашинский и др., 2008]. Все перечисленные приложения основаны на традиционном АМК, ориентированном на решение комбинаторных проблем, связанных с поиском оптимальных путей на графе [Dorigo et al., 1996]. Однако идентификация нечетких систем относится к задачам оптимизации с непрерывно меняющимися параметрами, и применение классического АМК в силу его изначальной дискретной природы не всегда позволяет достичь заданной точности решения. синглтон алгоритм идентификация

Было предложено несколько модификаций АМК для применения в непрерывной области: [Monmarche et al., 2000], [Tsutsui, 2000], [Tfaili et al., 2000]. Общий недостаток этих алгоритмов заключается в их неэффективной работе по сравнению с другими современными алгоритмами непрерывной оптимизации. Неэффективность эта во многом связанна со сложностью манипулирования феромоном. В нашей работе рассматривается прямой алгоритм муравьиной колонии, предложенный в работе [Kong et al., 2006]. В отличие от других непрерывных алгоритмов, в прямом АМК присутствует процедура непосредственного нанесения феромона, основанная на нормальном распределении.

Целью предлагаемой работы является описание применения прямого АМК для идентификации нечетких систем.

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

Рассматривается нечеткая система типа синглтон, i-ое правило в которой имеет следующий вид:

IF x₁=A_1i AND x₂=A_2i AND … AND x_n=A_ni THEN y = r_i,

где A_ij -- лингвистический терм, которым оценивается переменная x_i;

r_i -- действительное число, которым оценивается выход y.

Нечеткая система осуществляет отображение: :

где x - входной вектор, R - число правил; n - количество входных переменных; - функция принадлежности, определяемая набором своих параметров, например, треугольная - тремя параметрами, трапециевидная - четырьмя, гауссова и параболическая - двумя.

Нечеткая система может быть представлена как y = f(x, и), где и = ||и₁,…, и_N|| - вектор параметров, N = n · (число параметров, описывающих одну функцию принадлежности) (число термов, описывающих одну входную переменную), y - скалярный выход системы. Пусть дано множество обучающих данных (таблица наблюдений) {(x_p; t_p), p = 1 ,..., m}, тогда среднеквадратическая функция ошибки, являющаяся численным критерием адекватности модели, вычисляется по следующей формуле:

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

2. Прямой алгоритм муравьиной колонии

В прямом алгоритме муравей отвечает за вычисление значений закрепленного за ним параметра, поэтому муравьев в алгоритме столько, сколько параметров нечеткой модели. Каждый i-ый муравей создает свое решение, генерируя нормально распределенное действительное число N(м_i, у_i). В алгоритме используются два вида ферамонов: первый связан с центрами нормальных распределений м = ||м₁, …, м_N||. Количество ферамона определяет значения параметров м и у. Для каждого параметра и_j задан интервал изменения [a_j, b_j], где b_j и a_j - верхняя и нижняя граница параметра и_j. В качестве начальных значений для параметров м используются заданные случайным или иным способом значения параметров и. Начальные значения параметров у вычисляется по следующей формуле:

.

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

м(t) = (1- с) м(t-1), у(t) = (1- с) у(t-1),

где с -- эмпирический коэффициент испарения феромона, заданный на интервале [0, 1].

Далее происходит нанесение феромона:

м(t) = м(t) + си(t), у(t) = у(t) + с|и(t) - м(t)|,

где и(t) - решение найденное муравьиной колонией на текущей итерации, оно совпадает с глобальным лучшим решением.

Особенностью прямого АМК является включение в него простейшего локального поиска, состоящего из двух этапов: на первом значение параметра и_j увеличивается с определенным шагом до значения и_j + d_j, на втором этапе значение параметра уменьшается с определенным шагом до значения и_j - d_j. Значение d_j определяется по формуле:

d_j = у_j rand,

где rand - случайное равномерно распределенное число в интервале [0,1]. Шаг вычисляется по следующей формуле:

st_j = d_j / K,

где K - целое число, отвечающее за вычисление значения шага.

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

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

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

.

Когда алгоритм приближается к локальному минимуму, коэффициент конвергенции cf приближается к 0. Как только коэффициент конвергенции становится меньше критического значения cf_r , то вектор у возвращается в начальное состояние.

Ниже приведен собственно алгоритм для идентификации параметров нечеткой модели:

Шаг 1. Сгенерировать N муравьев, инициализировать для них начальные параметры. Сделать текущим первого муравья.

Шаг 2. Для текущего муравья вычислить значение параметра d_i. Вычислить шаг st_i.

Шаг 3. Для текущего i-го муравья, увеличивать значение параметра и_i на величину шага до и_i + d_i. Проверить полученное и будущее значения на ограничения, накладываемые нечеткой системой. Если проверки допускают данное изменение, то вычислить ошибку.

Шаг 4. Аналогично шагу 3, но уменьшать до значения и_i - d_i.

Шаг 5. В качестве нового значения параметра и_i выбирать значение, дающее наименьшую ошибку.

Шаг 6. Если есть следующий муравей, то сделать его текущим и перейти на шаг 2.

Шаг 7. Для всей колонии муравьев выполнить операции испарения и нанесения фермента.

Шаг 8. Если cf <cfr, то вернуть вектор у в начальное состояние.

Шаг 9. Если условие окончания работы алгоритма выполнено, то КОНЕЦ, иначе сделать текущим первого муравья и перейти на шаг 2.

Условием окончания работы алгоритма является выполнение определенного числа итераций или достижение ошибки меньше заданной.

3. Эксперимент

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

1) f(x₁, x₂) = x₁*sin(x₂), -р/2 < x₁, x₂ < р/2;

2) f(x₁, x₂) = sin(2x₁/р) * sin(2x₂/р), -5< x₁, x₂ <5;

;

;

На основе тестовой функции формировалась таблица наблюдений, по которой строилась нечеткая система, аппроксимирующая данную функцию. Критерием качества аппроксимации была среднеквадратическая ошибка вывода (RMSE).

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

Эксперимент показал, что точность решения не сильно зависит от числа итераций. Лучшие решения (малые ошибки) появляются при числе итераций 10…20.

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

При аппроксимации первой функции с увеличением константы с до значения 0,975 ошибка вывода уменьшается на четыре порядка, при дальнейшем увеличением константы до 1 ошибка возрастает на три порядка.

Эксперименты показали, что увеличение числа итераций и значения константы K не исключает попадание в локальный экстремум. Особенно ярко это проявляется при аппроксимации четвертой функции (Рис. 2), когда половина и больше испытаний при фиксированных параметрах алгоритма не привели к изменению ошибки.

4. Сравнение разработанного алгоритма с аналогами

Для сравнения разработанного алгоритма с существующими подходами построения нечетких моделей было проведено исследование результатов аппроксимации нескольких нелинейных функций. В силу того, что прямой АМК в представленной реализации оптимизирует только антецеденты правил, нами был включен в цикл идентификации метод наименьших квадратов (МНК) для настройки консеквентов правил [Ходашинский и др., 2009].

Аппроксимации третьей тестовой функции проводилась на 12 правилах, как в нашей работе, так и в аналогах. В работе [Lisin et al., 1999] для алгоритма Mitaim и Kosko ошибка аппроксимации составила 1.426, для алгоритма Lisin и Gennert 0.247, для прямого АМК+МНК ошибка равна 0,0206. На рисунке 4 представлены значения параметров шести первых термов функций принадлежности и их общий вид.

Настройка нечетких моделей разработанным алгоритмом и аналогами для аппроксимации четвертой тестовой функции производилась по таблице наблюдений, состоящей из 400 строк. В таблице 1 представлены результаты работы прямого АМК+МНК и алгоритмов, описанных в работе [Teng et al., 2004]. Как видно из таблицы, представленный в нашей работе алгоритм намного превосходит аналоги.

Табл. 1.

При аппроксимации пятой тестовой функции идентификация нечеткой системы разработанным алгоритмом и аналогом проводилась на таблице наблюдений, состоящей из 216 строк. В работе [Aliyari et al., 2007] эта работа выполнялась адаптивным алгоритмом роящихся частиц с 9 правилами, ошибка составила 0,00243. Прямой АМК + МНК на 27 правилах позволил уменьшить ошибку до 4,93E-06.

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

Список литературы

1. [Ходашинский и др., 2008] Ходашинский И.А., Дудин П.А. Параметрическая идентификация нечетких моделей на основе гибридного алгоритма муравьиной колонии // Автометрия. 2008. Том 44, № 5.

2. [Ходашинский и др., 2009] Ходашинский И.А., Гнездилова В.Ю., Дудин П.А., Лавыгина А.В. Основанные на производных и метаэвристические методы идентификации параметров нечетких моделей // Труды VIII международной конференции "Идентификация систем и задачи управления" SICPRO '08. Москва, 26-30 января 2009 г. Институт проблем управления им. В.А. Трапезникова РАН. - М: Институт проблем управления им. В.А. Трапезникова РАН, 2009.

3. [Aliyari et al., 2007] Aliyari M., Teshnehlab M. Sh., Sedigh A. K. Novel HybridLearning Algorithms for Tuning ANFIS Parameters Using Adaptive Weighted PSO // IEEE International Conference on Fuzzy Systems. 2007.

4. [Casillas et al., 2007] Casillas J., Cordon O., Fernandez de Viana I., Herrera F. Learning Cooperative Linguistic Fuzzy Rules Using the Best-Worst Ant System Algorithm // International Journal of Intelligent Systems. 2005. Vol. 20.

5. [Dorigo et al., 1996] Dorigo M., Maniezzo V., Colorni A. Ant System: Optimization by Colony of Cooperating Agents // IEEE Transaction Systems, Man and Cybernetics. Part B. 1996. Vol. 26.

6. [Juang et al., 2007] Juang C.-F., Lo C. Fuzzy systems design by clustering-aided ant colony optimization for plant control // International Journal of General Systems. 2007. Vol. 36, No. 6.

7. [Juang et al., 2009] Juang C.-F., Lu C.-M. Ant Colony Optimization Incorporated With Fuzzy Q-Learning for Reinforcement Fuzzy Control // IEEE Transactions Systems, Man, and Cybernetics. PART A. 2009. Vol. 39, No. 3.

8. [Kong et al., 2006] Kong M., Tian P. Application of ACO in Continuous Domain // Advances in Natural Computation, Second International Conference, ICNC 2006, Xian, China, September 24-28, 2006. Proceedings, Part II, LNCS 4222. Berlin, Springer-Verlag, 2006.

9. [Lisin et al., 1999] Lisin D., Gennert M. A. Optimal Function Approximation Using Fuzzy Rules // Proc. 18th Int. Conf. North American Fuzzy Information Processing Society. 1999.

10. [Monmarche et al., 2000] Monmarche N., Venturimi G., Slimane M. On how Pachycondla apicalis ants suggest a new search algorithm // Future Generation Computer System. 2000. Vol. 16.

11. [Tao et al., 2009] Tao C.-W., Taur J.-S., Jeng J.-T., Wang W.-Y. A Novel Fuzzy Ant Colony System for Parameter Determination of Fuzzy Controllers // International Journal of Fuzzy Systems. 2009. Vol. 11, No. 4.

12. [Teng et al., 2004] Teng Y.-W., Wang W.-J., Chiu C.-H. Function approximation via particular input space partition and region-based exponential membership functions // Fuzzy Sets and Systems. 2004. Vol. 142.

13. [Tfaili et al., 2000] Tfaili W., Dreo J., Siarry P. Fitting of an Ant Colony approach to Dynamic Optimization through a new set of test functions // International Journal of Computational Intelligence Research. 2007. Vol.3, No.3.

14. [Tsutsui, 2000] Tsutsui S. Ant Colony Optimization for Continuous Domain with Aggregation Pheromones Metaphor // Proc. 5th International Conference on Recent Advances in Soft Computing, 2004.

Размещено на Allbest.ru