66777

АЛГОРИТМЫ И ПРОГРАММНЫЕ СРЕДСТВА ИДЕНТИФИКАЦИИ НЕЧЕТКИХ МОДЕЛЕЙ НА ОСНОВЕ ГИБРИДНЫХ МЕТОДОВ

Диссертация

Экономическая теория и математическое моделирование

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

Русский

2014-08-27

4.41 MB

32 чел.

PAGE  12

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

На правах рукописи

Лавыгина Анна Владимировна

АЛГОРИТМЫ И ПРОГРАММНЫЕ СРЕДСТВА ИДЕНТИФИКАЦИИ НЕЧЕТКИХ МОДЕЛЕЙ НА ОСНОВЕ ГИБРИДНЫХ МЕТОДОВ

05.13.18 Математическое моделирование,

 численные методы и комплексы программ

Диссертация на соискание ученой степени

кандидата технических наук

Томск – 2010


СОДЕРЖАНИЕ



ВВЕДЕНИЕ

Актуальность работы

При моделировании сложных систем исследователи сталкиваются с неточным или неполным описанием изучаемого объекта. Решением такой проблемы является нечеткое моделирование.

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

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

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

Основополагающие результаты в области идентификации нечетких моделей получили А.Н. Аверкин, И.З. Батыршин, Л.С. Берштейн,  С.М. Ковалев, Л.Г. Комарцова, Ю.И. Кудинов, А.О. Недосекин, Ф.Ф. Пащенко, В.Б.Тарасов, А.В. Язенин, Н.Г. Ярушкина, P. Angelov, R. Babuska, A. Bastian, J.C. Bezdek, J. Casillas, J.L. Castro, O. Cordon, D. Dubois, D. Filev, J. González, S. Guillaume, F. Herrera, H. Ishibuchi, U. Kaymak, B. Kosko, R. Krishnapuram, R. Kruse, E.H. Mamdani, J. M. Mendel, S. Oh, W. Pedrycz,  H. Prade, M. Sugeno, T. Takagi, H. Tanaka, I. B. Turksen, R.R. Yager, T.Yasukawa, L.-X.Wang, L.  Zadeh.

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

Цель работы

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

Для достижения поставленной цели необходимо решить следующие задачи:

1) исследование существующих методов идентификации нечетких моделей;

2) реализация гибридных алгоритмов идентификации нечетких моделей на базе метаэвристик и методов, основанных на производных;

3) проведение исследований разработанных алгоритмов на контрольных примерах;

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

Объект и предмет исследования

Объектом исследования является процесс идентификации нечетких моделей.

Предметом исследования является комплекс алгоритмов и программ идентификации параметров антецедентов и консеквентов правил.

Методы исследования

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

Достоверность результатов

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

Научная новизна

Научной новизной обладают следующие результаты диссертационной работы:

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

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

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

4. Алгоритм формирования базы нечетких правил на основе субъективного разделения данных и процедуры диффузии.

Теоретическая значимость

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

Практическая ценность

Обоснованность предложенных алгоритмов подтверждена использованием их для решения практических задач. Программная система нечеткой аппроксимации атмосферных температурных полей внедрена в Институте оптики атмосферы имени В.Е.Зуева СО РАН.

Результаты исследований использованы в следующих проектах:

  1.  при выполнении проекта РФФИ № 06-08-00248 «Основанное на данных нечеткое моделирование технических систем» (2006 2007 гг.)
  2.  при выполнении проекта РФФИ № 09-07-99008 «Исследование и разработка технологии идентификации нечетких моделей на базе метаэвристик и методов, основанных на производных» » (2009 2010 гг.);
  3.  при выполнении проекта-победителя «Основанные на метаэвристиках и производных гибридные алгоритмы идентификации нечетких систем и программно-инструментальный комплекс нечеткого моделирования» программы «Участник молодежного научно-инновационного конкурса» (У.М.Н.И.К.).

Разработанные алгоритмы построения нечетких моделей на основе таблиц наблюдений используются при проведении лабораторных работ по дисциплине «Базы знаний» на кафедре автоматизации обработки информации Томского государственного университета систем управления и радиоэлектроники.

Часть программно-инструментальных средств передана в отраслевой фонд алгоритмов и программ Министерства образования Российской федерации (номера государственной регистрации 50200602165, 50200800872).

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

Алгоритмы, разработанные в рамках программной системы нечеткой аппроксимации атмосферных температурных полей, универсальны и могут быть применены не только к базам атмосферных температурных полей, но и к другим данным формата netCDF.

Основные защищаемые положения

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

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

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

Апробация работы

Основные положения работы докладывались и обсуждались на Томском IEEE семинаре "Интеллектуальные системы моделирования, проектирования и управления", на семинарах кафедр АОИ и АСУ ТУСУР, на научных и научно-технических конференциях, в том числе на 3-й Всероссийской конференции молодых ученых, г. Томск, 2006 г., Международной конференции «Workshop on INTAS programmes supporting young scientists, their followup and European dimension of further prospective for young scientists», г. Томск, 2007 г., XLV и XLVI Международных научных конференциях «Студент и научно-технический прогресс», г. Новосибирск, (2007, 2008 гг.), Всероссийской научно-технической конференции «Научная сессия ТУСУР», г. Томск, 2007, 2008, 2009 гг., Всероссийской конференции по вычислительной математике КВМ2009, г. Новосибирск, 2009 г.

Доклады на конференциях Научная сессия ТУСУР в 2007 и 2008 гг. были награждены дипломами третьей и первой степени соответственно.

Публикации по теме работы

По теме диссертации опубликовано 19 печатных работ, из них две – в периодических изданиях, рекомендованных ВАК России для публикации научных работ, получено два свидетельства об официальной регистрации программной системы для ЭВМ в ОФАП, одно учебно-методическое пособие.

Личный вклад автора

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

Структура и объем работы

Диссертационная работа состоит из введения, пяти глав и заключения. Объем работы составляет 178 страниц. Список литературы содержит  108 наименований.

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

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

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

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

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

Диссертант выражает искреннюю благодарность за ценные указания и поддержку научному руководителю д.т.н. Ходашинскому И.А., профессору кафедры АСУ, д.т.н. Катаеву М.Ю., аспиранту каф. АОИ Дудину П.А., выпускнику каф. АОИ Эпштейну Д.В и студентке каф. АОИ Осадченко Д.А.


ГЛАВА 1. ИДЕНТИФИКАЦИЯ НЕЧЕТКИХ МОДЕЛЕЙ. ОБЗОР ЛИТЕРАТУРЫ

1.1 Нечеткие системы моделирования

Базовая концепция нечеткого моделирования заключается в использовании степени принадлежности, которая является эффективным средством описания поведения плохо формализованных объектов, систем и процессов. Построение нечетких моделей возможно на основе наблюдаемых данных, а также с использованием априорного знания и опыта, которые могут быть неточными и иметь неколичественный  характер. Нечеткие модели точны и легко поддаются интерпретации [36]. Основная задача нечеткого моделирования заключается в нахождении конечного множества локальных отношений вход-выход, которые описывают систему или процесс в виде нечетких «ЕСЛИ-ТО» правил.

Нечеткая система выполняет отображение из входного пространства  в выходное пространство . Такая система является системой типа «много входов – много выходов» (MIMO – «multiple in- multiple out») [20,23,31,65].

Структура нечеткой системы представлена на рисунке 1.1.

Рис. 1.1. Типовая структура системы нечеткого логического вывода


Нечеткая система содержит следующие блоки [31]:

  1.  фаззификатор, преобразующий вектор x значений входных переменных в вектор нечетких множеств , необходимых для выполнения нечеткого логического вывода;
  2.  нечеткая база знаний, содержащая информацию о зависимости между входными и выходными переменными в виде «ЕСЛИ-ТО» правил;
  3.  машина нечеткого вывода, которая на основе правил базы знаний определяет значение выходного вектора в виде вектора нечетких множеств , соответствующего нечетким значениям входных переменных ;
  4.  дефаззификатор, преобразующий  в вектор значений выходных переменных y.

Отображение вход/выход в нечеткой системе представлено как множество нечетких «ЕСЛИ-ТО» правил. Каждое правило состоит из двух частей: условной и заключительной. Антецедент или условная часть (ЕСЛИ-часть) содержит утверждение относительно значений входных переменных, в консеквенте или заключительной части (ТО-части) указывается значение, которое принимает выходная переменная. Таким образом, нечеткая система типа MIMO может быть задана нечеткими правилами следующего вида [20,23,31].:

правило 1: ЕСЛИ x1 = А11 И x2 = А21 И … И xm = Аm1  ТО  y1 = R11 И … И  yr = Rr1;

правило 2: ЕСЛИ x1 = А12 И x2 = А22 И … И xm = Аm2  ТО  y1 = R12 И … И  yr = Rr2;

………………………………………………………………………………..….….……

правило n: ЕСЛИ x1 = А1n И x2 = А2n И … И xm = Аmn  ТО  y1 = R1n И … И  yr = Rnr,

где x1,  x2, …, xm – входные переменные;

 y1,  y2, …, yr – выходные переменные;

 Аji – нечеткие области определения входных переменных, которые определены на универсальных множествах X1, X2, …, Xm;

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

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

Таким образом, нечеткая система осуществляет отображение . Важную роль в этом отображении играют функции принадлежности (xj), указывающие степень принадлежности четкой переменной xi нечеткому понятию Aji.

Существует большое разнообразие типов и форм функций принадлежности. Каждая тип функций принадлежности задается своим набором параметров [20,23].

Треугольная функция принадлежности (рис. 1.2) задается тремя параметрами (a, b, c) и аналитически описывается следующим образом:

    (1.1)

Рис. 1.2. Треугольная функция принадлежности

Трапециевидная функция принадлежности (рис. 1.3) определяется четверкой параметров и аналитически описывается следующим образом:

    (1.2)

Рис. 1.3. Трапециевидная функция принадлежности

Параболическая функция принадлежности (рис. 1.4): аналитически задается следующим образом:

 (1.3)

Рис. 1.4. Параболическая функция принадлежности

Гауссова функция принадлежности (рис. 1.5) определяется двумя параметрами  m0 и σ0 и описывается следующим образом

. (1.4)

Рис. 1.5. Гауссова функция принадлежности

Любая система типа MIMO может быть представлена  множеством систем типа «много входов – один выход» (MISO – «multiple in- single out») при помощи разбиения консеквентов правил. Это, несомненно, увеличивает количество баз правил, но вместе с тем моделирование и вывод становятся более прозрачными [48]. Поэтому системы типа MISO в настоящее время являются весьма популярными в практическом применении. Система такого типа выполняет отображение  из входного пространства  в выходное пространство .

Исследователи выделяют три основных типа нечетких моделей «много входов – один выход» [20,48,63,77,80,82,85,96,99]:

  1.  Нечеткая модель типа синглтон задается правилами следующего вида:

правило i: ЕСЛИ   x1 = А1i   И   x2 = А2i     И … И   xm = Аmi    ТО    y = ri ,

где Aji – лингвистический терм, которым оценивается переменная xj , а выход y оценивается действительным числом ri. 

Модель типа синглтон осуществляет отображение , заменяя оператор нечеткой конъюнкции произведением, а оператор агрегации нечетких правил – сложением. Отображение F определяется следующей формулой:

, (1.5)

где ,

n – количество правил нечеткой модели;

 m – количество входных переменных в модели;

– функция принадлежности нечеткой области.

  1.  Модель типа Такаги-Сугено. Консеквенты в базе правил задаются линейной функцией от входов:

правило i: ЕСЛИ   x1 = А1i   И   x2 = А2i     И … И   xm = Аmi    ТО    y = fi(x1,… xm) ,

где fi (x)=a0+a1x1+a2x2+…+anxn , ak , 0  k  n– действительные числа..

Отображение  F  для модели типа Такаги-Сугено определяется формулой:

 (1.6)

  1.  Модель типа Мамдани задается правилами следующего вида:

правило i:     ЕСЛИ   x1 = А1i   И   x2 = А2i     И … И   xm = Аmi    ТО    y = Bi ,

где Bi – терм лингвистической переменной.

Для описания отображения входного вектора x в выходное значение y в моделях типа Мамдани используются такие методы, как, например, аппроксимация Мамдани или метод, основанный на формальном логическое доказательстве [24].

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

При разработке нечеткой модели возникает вопрос обоснования выбора структуры и параметров модели. Указанные задачи должны быть решены на этапе идентификации модели. Известны два подхода к идентификации нечетких моделей: на основе знаний эксперта и на основе таблиц наблюдений [48].

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

1.2 Методы параметрической идентификации нечетких моделей

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

Для решения задачи параметрической идентификации используется множество методов: генетические алгоритмы [37,45,76,100,103], эволюционное программирование [56,79,82,97,107], алгоритм имитации отжига [42,51,59,98], метод градиентного спуска [39,52,53,66,101], фильтр Калмана [40,71,74,88,89]. Все множество методов можно разделить на две группы.

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

Трудности применения классических методов оптимизации, в частности проблема локального экстремума и «проклятие размерности», заставляют обратиться ко второй группе методов – метаэвристических, таких как алгоритмы муравьиной колонии, роящихся частиц, имитации отжига, генетические алгоритмы [45].

Метаэвристика – это метод оптимизации, многократно использующий простые правила или эвристики для достижения оптимального или субоптимального решения [45,105]. Эти методы имеют некоторые общие особенности: коллективное поведение и простое взаимодействие в группе, самоорганизация и децентрализация управления, эволюция и адаптация, миграция, параллельность и асинхронность. Достоинство метаэвристических методов заключается в большей устойчивости. Указанные свойства позволяют эффективно решать задачи поиска в многомерном пространстве. Но это методы грубой настройки, обладающие, как правило, более медленной сходимостью и, следовательно, требующие больших временных ресурсов. Кроме того, применение метаэвристик не гарантирует нахождения оптимального решения и, как правило, связано с эмпирической настройкой параметров используемых алгоритмов.

1.2.1 Методы, основанные на производных

Метод градиентного спуска

Градиентный метод в практике обучения нечетких правил используется давно [39,52,53,66,101]. Суть метода заключается в том, что последующее приближение функции получается из предыдущего движением в направлении, противоположном направлению градиента целевой функции. При оценивании параметров нечетких моделей целевой функцией является среднеквадратичная ошибка нечеткой модели , а вектор параметров определен на множестве параметров функций принадлежности и параметров консеквентов правил.

Фильтр Калмана

Фильтр Калмана в идентификации систем используется достаточно давно и успешно. Однако в идентификации нечетких моделей этот аппарат применяется крайне редко [40,71,74,88,89].

Общая схема алгоритма такова: сначала задаются значения вектора состояния и значения его матрицы ковариаций. Далее в заданные дискретные времена выполняются две операции прогноз и корректировка. Прогноз связан с определением ожидаемого значения вектора состояния и предварительной оценкой корреляционной матрицы. На этапе корректировки вычисляется матричный «коэффициент усиления Калмана», обновляется оценка вектора состояния, исходя из новых результатов измерения, и обновляется оценка корреляционной матрицы [1,72,73]. Сходимость алгоритма и точность определения параметров нечеткой модели зависят от выбора значений матриц ковариаций шума процесса и шума измерения.

Процесс фильтрации сводится к следующей рекурсии:

где  Kn — усиление фильтра Калмана,

Pn — ковариационная матрица погрешности оценивания состояния системы,

Rn — ковариационная матрица шума измерения,

Qn — ковариационная матрица шума процесса,

Матрица частных производных выходного вектора относительно параметров задачи:

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

Метод наименьших квадратов

В простейшем случае формулируется следующим образом [2].

Результат yi повторяющихся измерений можно рассматривать как сумму (неизвестной) величины x и ошибки измерений j:

yi= x + j.

Величина x должна быть определена таким образом, чтобы была минимальна сумма квадратов ошибок j:

 Эта функция является выпуклой и дифференцируемой. Необходимым и достаточным условием минимума функции является равенство нулю производной.

Метод наименьших квадратов широко используется в статистике. В задаче параметрической идентификации нечетких моделей этот метод используется для настройки параметров консеквентов [49,91,101].

1.2.2 Метаэвристические методы

Генетические алгоритмы

Генетические алгоритмы – поисковые алгоритмы, основанные на механизмах естественного отбора и наследования. Впервые генетический алгоритм предложен в 1975 году Д. Х. Холландом (John Holland) в Мичиганском университете [58]. В нем используется принцип выживания наиболее приспособленных особей. Преимущества алгоритма перед другими методами оптимизации заключаются в параллельной обработке множества альтернативных решений.

Работа генетического алгоритма (ГА) основана на принципах естественного отбора и наследования [10,11]. Преимущества ГА перед другими методами оптимизации заключаются в параллельной обработке множества альтернативных решений. Немаловажным достоинством ГА является  возможность задания начальных параметров задачи случайным образом. При работе алгоритма большее внимание уделяется наиболее перспективным решениям, однако и менее перспективные решения также участвуют в поиске.

Генетический алгоритм работает с популяцией особей (хромосом), каждая из которых представляет собой упорядоченный набор параметров задачи, подлежащих оптимизации [10,11,23]. Основной характеристикой каждой особи является ее мера приспособленности (функция приспособленности, функция пригодности). Более приспособленные особи участвуют в воспроизводстве потомства путем скрещивания с другими особями из популяции, при этом гены потомков получают свои значения путем обмена генов родителей. Наименее приспособленные особи постепенно исчезают из популяции в процессе эволюции. Таким образом, из поколения в поколение по всей популяции распространяются лучшие характеристики. Иногда в популяции происходят мутации – случайные изменения в генах некоторых хромосом, за счет чего происходит внесение некоторой случайности в процесс работы генетического алгоритма, что снижает вероятность застревания в локальных минимумах [7,10,11,23].

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

  •  выполнение заданного числа поколений;
  •  достижение заданной точности;
  •  прекращение улучшения популяции.

Общая схема генетического алгоритма представлена на рис. 1.6 [23].

Рис. 1.6. Блок-схема генетического алгоритма

Обобщенный генетический алгоритм приведен ниже.

Шаг 1. Выбор параметров генетического алгоритма: стратегии селекции, типы и вероятности операторов скрещивания и мутации.

Шаг 2. Генерация начальной популяции.

Шаг 3. Вычисление значений фитнес-функции. Если достигнуто условие останова, то переход на Шаг 6, иначе переход на Шаг 4.

Шаг 4. Отбор пар хромосом для скрещивания в соответствие с выбранной стратегией селекции.

Шаг 5. Применение операторов скрещивания и мутации с соответствующими вероятностями. Формирование новой популяции. Переход на шаг 3.

Шаг 6. Вывод решения – декодированной «наилучшей» хромосомы.

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

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

Достоинства:

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

Недостатки:

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

Алгоритм роящихся частиц

Алгоритм роящихся частиц — это алгоритм поиска глобального оптимума в пространстве непрерывно меняющихся переменных. Алгоритм предложили в 1995 году инженер-электрик Рассел Эбенхарт (Russel Ebenhart) и физиолог Джеймс Кеннеди (James Kennedy) [62], основываясь на работах биолога Крейга Рейнольдса (Craig Reynolds), который, изучая социальное поведение птиц, получил формулу поведения стаи птиц. Алгоритм роящихся частиц, как и генетический алгоритм, — это основанный на популяции метод поиска, в котором, вместо хромосомы — частица, вместо генов — координаты частицы в многомерном пространстве. Каждая частица представляет потенциальное решение. Частицы оценивают пространство поиска, перемещаясь в соответствии с заданной эвристикой. В алгоритме роящихся частиц каждая частица имеет память и хранит свою лучшую позицию в пространстве поиска. Известна частице и лучшая позиция роя. Зная эти две позиции, частица динамически изменяет скорость согласно ее собственному опыту и опыту полета других частиц. Таким образом, движение каждой частицы задается ее лучшей позицией и ее текущей скоростью, ускорением, заданным предыдущей позицией, и ускорением, заданным лучшей частицей в рое [62,69,70,78].

Пусть имеется n-мерное пространство поиска , рой состоит из N частиц. Позиция i-ой частицы определяется вектором

.

Лучшая позиция, которую занимала i-ая частица, определяется вектором

.

Скорость частицы определяется также n-местным вектором

.

Движение частиц  определяют простые математические уравнения:

,

,

где i = 1, 2, …, N;

vi(k) — вектор скорости частицы i на итерации k;

xi(k) — координаты частицы i на итерации k;

c1, c2 — эмпирические константы ускорения;

pi(k) — лучшая позиция частицы i на первых k итерациях;

pg(k) — лучшая позиция частицы в рое (задается индексом g) на первых k итерациях;

w —  эмпирический коэффициент инерции;

rand, Rand — случайное число из интервала [0, 1].

 


Обобщенный алгоритм метода приведен ниже.

Шаг 1: Случайным образом генерируется популяция.

Шаг 2: Оценка популяция. Если достигнуто условие окончания работы, то переход на шаг 4.

Шаг 3: Для каждой частицы определение ее новых координат и вектора скорости. Расчет новых лучших позиций каждой частицы. Определение частицы с лучшей позицией в рое. Переход к шагу 2.

Шаг 4: Окончание работы.

Алгоритм имитации отжига

Алгоритм имитации отжига использует упорядоченный случайный поиск, основываясь на аналогии с процессом, который происходит при кристаллизации вещества из жидкого состояния в твёрдое, в том числе при отжиге металлов [64]. Особенностью алгоритма является допустимость принятия решений, приводящих к увеличению ошибки.

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

Критерий допуска основывается на следующем уравнении:

  (1.7)

При высокой температуре плохие решения принимаются чаще, чем отбрасываются. При снижении температуры вероятность принятия худшего решения уменьшается. Таким образом, при высоких температурах алгоритм отжига выполняет поиск оптимального решения во всем диапазоне решений. При понижении температуры диапазон поиска уменьшается. Существует множество вариантов снижения температуры. Например, использование геометрической функция [5,64]

,

где – коэффициент снижения температуры, 0 < < 1.

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

1.2.3 Гибридные алгоритмы

Использование гибридных алгоритмов позволяет объединить преимущества метаэвристических методов с преимуществами классических методов, основанных на производных [37,41,44,87,100,102,108]. Такое объединение повысит качество решений при умеренном количестве ресурсов и за приемлемое время.

В работе [41] для идентификации нечетких моделей типа Такаги-Сугено используется гибридный алгоритм на основе метода Гусстафсона-Кесселя, алгоритма роящихся частиц и метода наименьших квадратов, которые запускаются последовательно до тех пор, пока не выполнится условие останова (рис. 1.7).

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

Рис. 1.7. Блок-схема гибридного алгоритма на основе алгоритма

Густаффсона-Кесселя, алгоритма роящихся частиц и метода наименьших квадратов, предложенного в работе [41]

В работе [102] применяется гибридный метод на основе генетического алгоритма и рекурсивного метода наименьших квадратов. В данном случае оба метода используются для настройки и антецедентов, и консеквентов правил. Суть гибридизации заключается в следующем. При помощи рекурсивного метода наименьших квадратов формируется начальное решение – набор параметров антецедентов и консеквентов. Затем формируется популяция генетического алгоритма на основе полученных решений метода наименьших квадратов и запускается процесс эволюции. На каждом шаге генетического алгоритма формируется решение методом наименьших квадратов, которое заменяет в популяции особь с наихудшим значением функции приспособленности.

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

1.3 Методы структурной идентификация нечетких моделей

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

Для решения выделенных задач структурной идентификации нечеткой модели применяют следующие методы: методы индуктивного обучения [38], генетический алгоритм, нечеткий кластерный анализ [36,48,55,86,87].

Нечеткий кластерный анализ

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

Термин кластерного анализа впервые ввел Р. Трионом (R.C. Tryon) в 1939 г в [95]. Кластерный анализ включает в себя набор различных методов классификации.

Кластеризация – это автоматическое разбиение  элементов некоторого множества на группы в зависимости от их схожести. Элементами множества может быть что угодно, например, данные или вектора характеристик. Сами группы принято называть кластерами [8,95].

Геометрически каждый кластер соответствует нечеткому правилу «ЕСЛИ-ТО». Лингвистические термы задаются проекцией данного кластера на соответствующие координатные оси переменных. Здесь центры кластеров определяют центральное значение функции принадлежности.

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

A=,

где   Kколичество объектов,  n – количество признаков.  

Задача кластеризации состоит в разбиении объектов из матрицы наблюдений на несколько подмножеств (кластеров), в которых объекты более схожи между собой, чем с объектами их других кластеров. В матричном виде обычно «схожесть» определяют через расстояния.

Нечеткие методы кластеризации, в отличие от четких, позволяют одному и тому же объекту принадлежать одновременно нескольким кластерам, но с различной степенью [35,43,44,55,86,87]. Наиболее распространенными являются алгоритм нечетких с–средних (c–means, FCM) [35] и его обобщение в виде алгоритма Густафсона-Кесселя [55,86,87].

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

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

Недостатки методов кластерного анализа:

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

Методы индуктивного обучения

Индукция – процесс, который позволяет делать предположение о законах или теориях развития при помощи наблюдений и анализа событий и фактов, при которых эти законы применяются. Благодаря процессу индукции происходит достижение общих выводов из отдельных примеров [38].

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

Можно выделить следующие способы формирования знаний на основе машинного обучения:

  •  извлечение множества правил из предъявляемых примеров;
  •  анализ важности отдельных правил;
  •  оптимизация производительности набора правил.

Идея индуктивных методов обучения сводится к извлечению набора нечетких правил из набора примеров, которые показывают особенности работы системы [38]. Для этого происходит разбиение пространства каждой входной переменной xi на нечеткие области (каждой области соответствует функция принадлежности μij) и кодирование выходной переменной. Затем происходит генерация начального набора нечетких правил по предложенным примерам. Для этого значения входных переменных каждого примера представляются значениями меток, которым соответствует максимальная функция принадлежности Lij =max jij (xi ) ). То же происходит и с выходом. Затем из полученного набора правил нужно сформировать эффективное множество правил. Зачастую для этой цели применяют генетические алгоритмы.

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

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

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

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

В 90-х годах появились пакеты программ, дающие возможность создавать и эксплуатировать нечеткие экспертные системы. Один из наиболее развитых подобных пакетов – система CubiCalc американской фирмы HyperLogic, первый профессиональный пакет, работающий на базе нечеткой логики. CubiCalc – многофункциональный пакет. Это не только оболочка создания законченных нечетких экспертных систем, но и средство разработки приложений, использующих нечеткую логику [9]. CubiCalc включает в себя следующие компоненты:

  •  пакет CubiCalc ver. 2.0;
  •  учебная версия пакета CubiQuick;
  •  вспомогательная утилита RuleMaker, обеспечивающей формирование правил на основе кластеризации;
  •  плата CubiCard, позволяющая создать «интеллектуальный анализатор» для обработки сигналов на базе ПК.

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

Система MATLAB – это интегрированная программная среда, предназначенная для выполнения расчетов и моделирования, в том числе и нечеткого с использованием пакета Fuzzy Logic Toolbox, включающего в себя следующие средства [20,32]:

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

Работа с пакетом ведется либо в интерактивном режиме, либо в режиме команд, используя входящие в состав пакета функции. Система MATLAB имеет собственный язык программирования. Программы хранятся в формате специальных m-файлов. Выполнение программы осуществляется в режиме интерпретации.

Для настройки нечетких систем в пакете Fuzzy Logic Toolbox используется адаптивная система нейро-нечеткого вывода ANFIS.

Система fuzzyTech (INFORM GmbH, Германия) является специализированным средством для разработки нечетких моделей, трансляции их в один из языков программирования (C, Java, MS Visual C++, COBOL, Assembler) для дальнейшего использования в программируемых микроконтроллерах. Разработка нечеткой модели в среде fuzzyTech ведется в интерактивном режиме с использованием следующих графических средств [20]:

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

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

Еще один пакет для создания нечетких экспертных систем – FIDE (Fuzzy Inference Development Environment – оболочка разработки систем нечеткого логического вывода) фирмы Aptronix (США). Его возможности схожи с возможностями CubiCalc. В основном пакет FIDE ориентирован на разработку контроллеров, использующих нечеткую логику [9].

Отмеченные программные продукты требуют настройки структуры и параметров создаваемой нечеткой модели на основе знаний эксперта и не содержат средств настройки модели на экспериментальные данные, за исключением Fuzzy Logic Toolbox, где настройка ведется с использованием технологии ANFIS для нечетких моделей типа Сугено (параметрическая идентификация) [20,32], и вспомогательной утилиты RuleMaker в составе CubiCalc, обеспечивающей формирование правил на основе кластеризации (структурная идентификация) [9].

В России одним из основных разработчиков программного обеспечения в области интеллектуального анализа данных является компания НейроПроект, поставляющая программы NeuroShell 2, GeneHunter, однако в них не представлены методы обработки данных на основе нечеткой логики.

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

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

Идентификация нечеткой модели ведется на основе таблицы наблюдений или тестовой функции  f(x). Необходимо так построить базу правил, чтобы ошибка вывода , определяемая разностью между значением выходной переменной из таблицы наблюдений f(x) и значением F(x), полученным при использовании нечеткой модели, была минимальной.

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

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

Выводы

  1.  Под идентификацией нечеткой модели подразумевается процесс определения структуры (лингвистических переменных и их термов, количества и структуры нечетких правил в базе) и параметров (параметров функций принадлежности, функции импликации и оператора агрегации) нечеткой модели. Задача идентификации заключается построении оптимальной модели по результатам наблюдений над входными и выходными переменными системы. Критерием оптимальности  служит наименьшая ошибка при обратных выводах.
    1.  Изучение рынка специализированного программного обеспечения показало отсутствие программных систем, позволяющих производить идентификацию нечетких моделей на основе данных. В существующих программных продуктах при разработке нечетких моделей выбор структуры, составляющих и параметров моделей основывается на знаниях и опыте экспертов, в качестве которых выступают пользователи.
    2.  Для параметрической идентификации нечетких моделей используются две группы методов: 1) основанные на производных (метод наименьших квадратов, градиентный метод, фильтр Калмана); 2) метаэвристические методы (генетический алгоритм, алгоритм муравьиной колонии, метод роящихся частиц, алгоритм имитации отжига и поиск с запретами). Методы, основанные на производных более точные, но  способны застревать в локальных минимумах. Метаэвристические методы более устойчивы, но это методы более грубой настройки и требуют больших временных ресурсов. Кроме того, применение метаэвристик не гарантирует нахождения оптимального решения и, как правило, связано с эмпирической настройкой параметров используемых алгоритмов.
    3.  Использование гибридных алгоритмов позволяет объединить преимущества метаэвристических методов с преимуществами классических методов, основанных на производных. Такое объединение повышает качество решений при умеренном количестве ресурсов и за приемлемое время.


ГЛАВА 2. АЛГОРИТМИЧЕСКОЕ ОБЕСПЕЧЕНИЕ СИСТЕМ ИДЕНТИФИКАЦИИ НЕЧЕТКИХ МОДЕЛЕЙ

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

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

Алгоритм идентификации нечетких моделей

Вход: таблица наблюдений.

Выход: нечеткая модель с оптимальными параметрами.

Шаг 1. Задание количества термов лингвистических переменных.

Шаг 2. Инициализация параметров нечеткой модели.

2.1 Задание параметров антецедентов правил с помощью субъективного разделения данных.

2.2 Инициализация консеквентов правил на основе модифицированной процедуры диффузии.

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

Шаг 4. Если среднеквадратичная ошибка нечеткой модели больше заданной, то увеличение количества термов, переход на шаг 2, иначе выход из алгоритма.

2.1 Инициализация параметров нечеткой модели

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

2.1.1 Субъективное разделение данных

Субъективное разделение данных основано на не оптимизирующих алгоритмах. Предполагается, что область изменения переменной может быть разбита на подобласти, каждая из которых описывается лингвистическим термом. База правил формируется перебором возможных сочетаний входных лингвистических термов. Наиболее часто применяемые способы разделения пространства данных – это случайное разделение, пример такого разделения дан на рис. 2.1, или равномерное, представленное на рис. 2.2 [21,25].

Рассмотрим случайное разделение данных. Если известны интервалы изменения входных и выходных переменных, то можно разделить каждый из этих интервалов на ti пересекающихся отрезков (ti – число лингвистических термов, на которое разбивается i-ая переменная). Параметры отрезка определяют параметры функции принадлежности лингвистического терма  Aji, заданного на данном отрезке.

Пусть i-ая переменная xi определена на интервале [0, 10], разделим указанный интервал на следующие пять (ti = 5) неравных отрезков: (0, 2), (1, 5), (2.5, 7), (4, 10), (9, 10).  Лингвистические термы, определенные на отрезках, обозначим следующим образом: л11, л12, л13, л14, л15. Допустим, выбран треугольный тип функции принадлежности. Тогда один из возможных способов описания i-ой переменной нечеткими значениями приведен на рис. 2.1. Здесь функция принадлежности терма л1 задана тройкой (0, 0, 2), л2 – (1, 3, 5) и т.д.

Функции принадлежности должны покрывать весь универсум, на котором они определены. Переход от одной функции принадлежности к другой не должен содержать разрывов, иначе поверхность вывода также будет содержать разрывы. При формировании лингвистических термов должны быть соблюдены следующие требования к значениям параметров функций принадлежности [25,27]:

a) для треугольной функции  принадлежности, определяемой по формуле 1.1

;

(2.1)

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

,

;

(2.2)

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

;

(2.3)

г) для гауссовой функций принадлежности (формула 1.4)

.

(2.4)

 

Равномерному разделению соответствуют такие функции принадлежности, для которых графики всех соседних функций принадлежности пересекаются на уровне 0,5 (рис. 2.2).

База правил формируется путем перебора всех сочетаний термов входных переменных. Фрагмент баз правил, сформированных на пяти входных лингвистических термах и пяти выходных термах, для нечеткой модели типа синглтон представлен в таблице 2.1.

Таблица 2.1

Пример базы правил для моделей типа синглтон

ЕСЛИ x1=л11 И x2=л21 , то y =r1

ЕСЛИ x1=л12 И x2=л21 , то r2

ЕСЛИ x1=л13 И x2=л21 , то r3

ЕСЛИ x1=л14 И x2=л21, то r4

ЕСЛИ x1=л15 И x2=л21, то r5

ЕСЛИ x1=л11 И x2=л22, то r6

ЕСЛИ x1=л12 И x2=л22, то r7

ЕСЛИ x1=л13 И x2=л22 , то r8

ЕСЛИ x1=л14 И x2=л22 , то r9

……………………

ЕСЛИ x1=л15 И x2=л25 , то r25

Алгоритм определения значений консеквентов для сформированной базы правил описан в параграфе 2.1.2 «Инициализация консеквентов правил».

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

Субъективное разделение данных имеет важное  достоинство: входное пространство охвачено все. Недостатком такой схемы является экспоненциальный рост числа правил с ростом числа входных переменных и лингвистических термов. Например, для решения проблемы средней сложности может потребоваться несколько сотен или даже тысяч правил. Это порождает две основные проблемы: во-первых, большое число правил затрудняет обработку этих правил, и, во-вторых, исчезает понятность и интерпретируемость нечеткой модели. Схема страдает от «проклятия размерности». Если каждая входная переменная представлена t лингвистическими термами, нечеткая модель имеет m входов и один выход, то система будет иметь  tm правил.

Нечеткие модели с большим числом правил имеют более высокую точность, но более слабую вычислительную эффективность и интерпретируемость.

2.1.2 Инициализация консеквентов правил

Ниже приведен алгоритм определения начальных значений консеквентов на основе процедуры диффузии [54].

Пусть дана таблица наблюдений (таблица 2.2):

Таблица 2.2

Пример таблицы наблюдений

Входные переменные

Выходная переменная

x1

x2

xm

y

x11

x21

xm1

y1

x1k

x2k

xmk

yk

x1K

x2K

xmK

yK

Здесь xk j – значение k-ой входной переменной j-го наблюдения;

 yj – значение выходной переменной j-го наблюдения;

 K – число наблюдений;

 m – количество входных переменных.

Сформирована база правил , состоящая из правил следующего вида:

Правило i: ЕСЛИ   x1 = А1i   И   x2 = А2i     И … И   xm = Аmi    ТО    y = ri ,

где Aki – лингвистический терм, которым оценивается k-ая входная переменная, а выход y оценивается действительным числом ri. Пусть определены параметры функций принадлежности термов, входящих в правило.

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

, (2.5)

где yj – значение выходной переменной в j-й строке таблицы наблюдений ij     – вес  i-го правила для пары входов в j-й строке наблюдений, который высчитывается по следующей формуле:

,

Выход нечеткой модели для j-й строки наблюдений определяется по формуле:

,

где n – количество правил нечеткой модели.

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

Пусть S – множество правил, для которых

Создадим для каждого правила множество :

,  (2.6)

где Ni – окрестность i- го правила – множество соседних правил. Под соседними правилами будем понимать такие, у которых индексы функций принадлежности по каждому входу отличаются на единицу от тех, которые входят в правило.  У каждого правила может быть не более двух соседей по каждому входу, т.е.  .

Для запуска процедуры рекурсии вводится вектор g размера n для хранения промежуточных значений консеквентов.

Процедура диффузии сводится к следующей рекурсии:

;  (2.7)

.  (2.8)

Процесс диффузии продолжается до тех пор, пока для каждого правила не выполнится равенство . Результатом алгоритма являются значения консеквентов ri=g(i).

Алгоритм, основанный на процедуре диффузии, приведен ниже.

Алгоритм инициализации консеквентов правил

Вход: Таблица наблюдений, антецеденты правил.

Выход: Консеквенты правил.

Шаг 1. Сформировать множество Sмножество правил, для которых знаменатель формулы 2.5 не равен нулю.

Шаг 2. Для каждого правила создать окрестность по формуле (2.6).

Шаг 3. Вычислить  по формуле (2.7).

Шаг 4. Вычислить  по формуле (2.8).

Шаг 5. Если  то перейти на шаг 4, иначе для каждого i: , выход из алгоритма.

2.2 Параметрическая идентификация нечетких моделей

2.2.1 Модифицированный генетический алгоритм для задачи идентификации нечетких моделей

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

Начинает работу генетический алгоритм с некоторого набора исходных решений, называемых популяцией. Каждое решение (элемент популяции) представляет собой строку символов, которая называется особью или хромосомой. Хромосома состоит из множества генов. В нашем случае каждый ген кодирует один параметр нечеткой модели. Поэтому для решения задачи параметрической идентификации воспользуемся разновидностью генетического алгоритма, в котором хромосомы представлены в виде вектора действительных чисел. Размер хромосомы при разбиении входных переменных на одинаковое количество термов вычисляется следующим образом: <количество термов> * <количество параметров функций принадлежности> * <количество входных переменных> + 1.

В нулевой ген помещается значение степени приспособленности, которое определяется ошибкой системы [4,13,18,19].

Значения ненулевых генов – числа из интервала [0, 1], декодируемые в область значений входных переменных.

На рис. 2.3 представлена структура хромосомы для задачи настройки треугольных функций принадлежности, где – нормированные значения параметров i-го терма j-й переменной, t – количество термов переменной.

Ошибка

Рис. 2.3. Схема строения хромосомы

С учетом требований (2.1)-(2.4) к значениям параметров функций принадлежности должны соблюдаться специфические условия включения хромосомы в популяцию в зависимости от типа функций принадлежности.

Предлагается три способа формирования начальной популяции:

  1.  гены всех хромосом в популяции задаются случайным образом; при создании каждой особи учитываются условия включения в популяцию;
  2.  одна хромосома в популяции соответствует параметрам таких функций принадлежности, графики которых для соседних термов пересекаются на уровне 0,5 (равномерное распределение параметров по области определения входных переменных);
  3.  одна или несколько хромосом в популяции задаются исследователем.

Генетические операторы

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

В работе исследованы следующие типы оператора селекции: «случайный отбор», «турнирный отбор», «рулеточный отбор», «стратегия элитаризма» [9,10,23].

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

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

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

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

  •  для треугольной функции принадлежности

0 ≤ p(i,j,k) ≤ p(i,j,k+1) , если p(i,j,k) соответствует параметру a функции принадлежности j-го терма i-й входной переменной

p (i,j,k-1) ≤ p (i,j,k) ≤ p (i,j,k+1), если p (i,j,k)  соответствует параметру b

p (i,j,k-1) ≤ p (i,j,k) ≤ 1 если p (i,j,k) соответствует параметру c

  •  для трапециевидной функции принадлежности  

0 ≤ p (I,j,k) ≤ p (i,j,k+1), если p (i,j,k) соответствует параметру u1

p(i,j,k-1)≤ p (i,j,k) ≤ p(i,j,k+1) , если p (i,j,k) соответствует параметру u01 или u02

p (i,j,k-1) ≤ p (i,j,k) ≤ 1, если p (i,j,k) соответствует параметру u2

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

p (i,j,k) > 0, если k – четное

p (i,j-1,k) ≤ p (i,j,k) ≤ p (i,j+1,k), если kнечетное

Эта мера позволяет сократить время вычислений по сравнению с использованием классической случайной мутации, при которой значение мутирующего гена выбирается из интервала [0, 1], и дальнейшей проверкой особи на условия включения в популяцию.

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

Формирование промежуточной популяции

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

Для формирования промежуточной популяции в работе используются следующие методы [25]:

  1.  полная замена старой популяции новой, полученной в результате применения операторов скрещивания и мутации;
  2.  полная замена с добавлением в новую популяцию лучшей особи из старой популяции;
  3.  помещение в новую популяцию лучших хромосом из старого поколения и лучших хромосом из нового поколения в отношении 3:7;
  4.  помещение в новую популяцию лучших хромосом из старого поколения и худших хромосом из нового поколения в отношении 3:7;
  5.  частичная замена; в этом случае в новую популяцию попадают «лучшие» особи, как из новой популяции, так и из старой; размер популяции после скрещивания будет равен 2N–2 (N — размер исходной популяции).

Алгоритм параметрической идентификации с использованием генетического алгоритма

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

Алгоритм параметрической идентификации на основе генетического алгоритма

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

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

Шаг 1. Генерация начальной популяции.

Шаг 2. Вычисление значений ошибки с помощью нечеткой модели. Сортировка хромосом по значению ошибки.

Шаг 3. Если достигнуто условие останова, то переход на Шаг 6, иначе переход на Шаг 5.

Шаг 4. Отбор пар хромосом для скрещивания в соответствие с выбранной стратегией селекции.

Шаг 5. Применение операторов скрещивания и мутации с соответствующими вероятностями. Формирование новой популяции. Переход на шаг 2.

Шаг 6. Вывод решения – декодированной «наилучшей» хромосомы.

В качестве условия останова алгоритма выбраны следующие:

  •  выполнение заданного числа поколений;
  •  достижение заданной точности;
  •  прекращение улучшения популяции.


2.2.2 Особенности применения алгоритма имитации отжига в задаче идентификации нечетких моделей

Алгоритм имитации отжига для параметрической идентификации нечетких моделей приведен ниже.

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

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

Выход: параметры функций принадлежности.

Шаг 1. Значения параметров функций принадлежности записываются в текущее решение и в лучшее решение.

Шаг 2. Алгоритм имитации отжига копирует текущее решение в рабочее и изменяет рабочее решение случайным образом.

Шаг 3. Из рабочего решения значения параметров передаются нечеткой модели. Нечеткая модель вычисляет значение среднеквадратичной ошибки вывода для параметров, соответствующих рабочему решению (ошибка рабочего решения).

Шаг 4. Алгоритм имитации отжига сравнивает ошибку текущего и рабочего решения. Если ошибка рабочего решения меньше, чем ошибка текущего решения, то переход к шагу 5. В противном случае, определяется критерий допуска  (формула 1.7). Если критерий допуска выполняется, то выполняется переход к шагу 5. В противном случае, текущее решение копируется в рабочее, и осуществляется переход к шагу 6.

Шаг 5. Алгоритм имитации отжига копирует рабочее решение в текущее и сравнивает ошибку текущего решения с ошибкой лучшего решения. Если ошибка текущего решения меньше, то текущее решение копируется в лучшее решение.

Шаг 6. Алгоритм имитации отжига уменьшает температуру. Если температура становится равной заранее заданной конечной температуре, т.е. выполняется условие окончания, то вывод лучшего решения, выход из алгоритма. В противном случае, осуществляется переход к шагу 2.[25].

Для снижения температуры предлагается использовать простую геометрическую функцию: , где  константа, меньшая единицы, и функцию Больцмана : , где T – начальная температура.

Обобщенная процедура применения алгоритма имитации отжига для идентификации нечетких моделей приведена на рис. 2.4.

Рис. 2.4. Обобщенная процедура идентификации нечетких систем алгоритмом имитации отжига

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

Подробно применение алгоритма имитации отжига для идентификации нечетких моделей представлено в блок-схеме, изображенной на рис. 2.5.

Рис. 2.5. Блок-схема алгоритма идентификации нечетких моделей на основе алгоритма имитации отжига


2.2.3 Особенности применения метода наименьших квадратов в задаче идентификации нечетких моделей 

Метод наименьших квадратов используется в работе для настройки параметров консеквентов [25]. Здесь минимизируется сумма квадратов отклонений значений, полученных в результате нечеткого вывода, от наблюдаемых данных (таблица 2.2).

Нечеткая модель типа синглтон задается правилами вида

Правило i: ЕСЛИ   x1 = А1i   И   x2 = А2i     И … И   xm = Аmi    ТО    y = bi ,

где Aji – лингвистический терм, которым оценивается j-ая входная переменная, а выход y оценивается действительным числом bi. 

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

,

где yk*— выходное значение, полученное в результате нечеткого вывода для входных значений k-го наблюдения.

Пусть

где w,i=1..R . Тогда. Если Aне вырожденная матрица (det(A) ≠ 0), то .

2.2.4 Особенности применения метода градиентного спуска в задаче идентификации нечетких моделей 

Для нечетких моделей типа синглтон с двумя входными переменными, разделенными на пять лингвистических термов, базы правил, состоящей из двадцати пяти правил (таблица 2.1. на стр. 39), рассмотрим градиентный алгоритм обучения.  Для обучающих примеров, заданных в виде троек (x1*, x2*,y*), предложена целевая функция для минимизации погрешности решений:

,

где y* – желательное выходное значение, y – выходное значение, полученное в результате нечеткого вывода [14,25,26].

Для треугольных функций принадлежности частные производные равны:

для i = 1..5;  l = (j mod 5) + 1; m = (j div 5) + 1; L = (s mod 5) + 1;  M = (s div 5) + 1; k = 5(g -1) + i.

Производная функции ошибки по параметрам b и c вычисляется аналогичным образом.

Значения параметров на t+1 итерации вычисляются по следующим формулам:


Частные производные вычисляются по следующим формулам:

 

Значения параметров на t+1 с учетом полученных значений производных определяются следующим образом:

,   (2.9)

,   (2.10)

  (2.11)

,   (2.12)

,   (2.13)

 (2.14)

для i = 1..5;  l = (j mod 5) + 1;  m = (j div 5) + 1;  k = 5(j-1) + i;  n = 5(i -1) + j;    — константы обучения, t — итерация обучения.

Значение консеквента правила yj на t+1-ом шаге определяются следующим образом:

  (2.15)

где g  - константы обучения, t – итерация обучения, i = 0..24; l = (j mod 5) + 1;

m = (j div 5) + 1;  k = (i mod 5) + 1;  n = (i div 5) + 1.

 Алгоритм параметрической идентификации на основе градиентного метода приведен ниже [25].

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

Вход: исходные параметры функций принадлежности и консеквентов правил.

Выход: функций принадлежности и консеквентов правил.

 Шаг 1. Задать начальные параметры: константы обучения , количество итераций и шаг дискретизации входных переменных Delta.

Шаг 2. Для всех значений входных переменных (x1*, x2*) из таблицы наблюдений выполнять Шаг 3.

Шаг 3. Для тройки параметров (a,b,c) первой лингвистической переменной первой функции принадлежности изменить значения параметров по формулам (2.9), (2.10) или (2.11) соответственно. Затем изменить значения тройки параметров для второй, третьей функции принадлежности и т.д. После аналогичная процедура для параметров функции принадлежности второй лингвистической переменной по формулам (2.12), (2.13) или (2.14).

Шаг 4. Для всех значений входных переменных (x1*, x2*) из таблицы наблюдений выполнять шаг 5.

Шаг 5. Для всех консеквентов в базе правил изменить значения, используя формулу (2.15).

Шаг 6. Если условия останова алгоритма выполнено, то закончить вычисления. Иначе перейти к шагу 2.

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

2.2.5 Особенности применения фильтра Калмана в задаче идентификации нечетких моделей 

Фильтр Калмана можно представить в виде линейной системы, дискретной во времени. Такая система характеризуется своим входом, состоянием и выходом. Здесь проблема идентификации решается как задача минимизации методом взвешенных наименьших квадратов, где вектор ошибки — разность между выходом нечеткой модели и тестовым значением из таблицы наблюдений [15,16,18]

Система задана следующими уравнениями:

;

;

где xn — вектор состояния системы в момент времени n,

— шум процесса,

— шум измерения,

f(·) и h(·) — нелинейные функции состояния системы

где M(·) - математическое ожидание,  — дельта Кронекера.

Процесс фильтрации сводится к следующей рекурсии:

 (2.16)

 (2.17)

 (2.18)

где Kn – усиление фильтра Калмана,

Pn – ковариационная матрица погрешности оценивания состояния системы,

Rn – ковариационная матрица шума измерения,

Qn – ковариационная матрица шума процесса,

– матрица частных производных функции h(·) относительно вектора x.

– матрица частных производных функции f(·) относительно вектора x.

Рассмотрим специфику применения алгоритма фильтрации Калмана в задаче настройки параметров функций принадлежности.

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

Вектор состояния для системы с двумя входными переменными, разделенными на t термов, определенных треугольными функциями принадлежности, характеризуемыми параметрами (a,b,c),  имеет следующий вид:

.

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

Система будет описана следующими уравнениями:

f(·) в этом случае – тождественное отображение и, следовательно, матрица будет единичной. Шумы при решении задачи идентификации вводятся искусственно для устойчивой работы алгоритма.

Матрица  – матрица частных производных нечёткого выхода относительно параметров функций принадлежности:

 (2.19)

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

для  i = 1..t;  l = (j mod t) + 1;  m = (j div t) + 1;  L = (s mod t) + 1;  M = (s div t) + 1;  k = t(g -1) + i.

 Производная нечеткого выхода по параметрам b и c вычисляется аналогичным образом.

Частные производные равны:

  

 

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

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

Матрицы шумов R и Q задаются в виде диагональных матриц: R=rI, Q=qI, где I — единичная матрица, r,q – эмпирические коэффициенты.

В работе исследовано два способа формирования значения матрицы P0:

  1.  с использованием формул:

 

 

  1.  P0 — диагональная матрица: P0=pI, где p – эмпирический коэффициент.

Ниже приведена общая схема алгоритма фильтрации Калмана для настройки параметров функций принадлежности [15,16].

Алгоритм параметрической идентификации на основе фильтра Калмана

Вход: исходные параметры функций принадлежности.

Выход: параметры функций принадлежности.

Шаг 1. Задать начальный вектор параметров x, матрицы ковариации измерений R и ковариации Q. Рассчитать начальное значение матрицы P0. Скопировать начальный вектор параметров в лучшее решение.

Шаг 2. Если достигнуто условие останова, то вывести лучшее решение и выйти из алгоритма, иначе вычислить матрицу частных производных выхода от параметров нечеткой модели по формуле (2.19).

Шаг 3. Вычислить матрицу усиления K по формуле (2.17).

Шаг 4. Вычислить вектор параметров нечеткой модели по формуле (2.16). Если ошибка нечеткой модели с текущим вектором параметров меньше, чем при лучшем решении, то скопировать текущий вектор параметров в лучшее решение.

Шаг 5. Если матрицасингулярна, то вывести сообщение о сингулярности матрицы, иначе вычислить значение ковариационной матрицы ошибок параметров P по формуле 2.18. Перейти на шаг 2.

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

2.2.6 Гибридные алгоритмы идентификации нечеткой модели на основе метаэвристических методов и методов, основанных на производных

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

В работе для параметрической идентификации нечетких моделей предлагается три способа гибридизации.

Первый способ - двухэтапная идентификация (рис. 2.6). На первом этапе параметры функций принадлежности настраиваются генетическим алгоритмом, а консеквенты – методом наименьших квадратов. На втором этапе параметры функций принадлежности и консеквенты настраиваются градиентным методом или алгоритмом фильтрации Калмана [14,26]. Такой подход исключает недостаток основанных на производных методов – неспособность проходить локальные минимумы, и недостаток генетического алгоритма – не всегда точное попадание в глобальный оптимум. Таким образом, используя на начальных этапах генетический алгоритм, вычисляется начальное приближение, локализованное в области экстремума, на заключительном этапе уточняется положение экстремума градиентным методом или алгоритмом фильтрации Калмана.

Ниже приведен алгоритм параметрической идентификации с помощью гибридного алгоритма (первый способ гибридизации).

Алгоритм параметрической идентификации на основе гибридного алгоритма (первый способ гибридизации)

Шаг 1. Задание начальных параметров нечеткой модели и алгоритмов (генетического алгоритма, градиентного метода/фильтра Калмана и метода наименьших квадратов).

Шаг 2. Задание количество итераций первого этапа гибридного алгоритма.

Шаг 3. Настройка параметров функций принадлежности с помощью генетического алгоритма.

Шаг 4. Настройка консеквентов с помощью метода наименьших квадратов.

Шаг 5. Если текущее количество итераций меньше чем количество итераций первого этапа, то переход на Шаг 3.

Шаг 6. Настройка параметров нечеткой модели с помощью градиентного метода (фильтра Калмана).

Рис. 2.6. Схема первого способа гибридизации (ГА – генетический алгоритм, МНК – метод наименьших квадратов, ГМ – градиентный метод, ФК – фильтр Калмана,ФП – функция принадлежности)

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

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

Рис. 2.7. Схема третьего способа гибридизации (АИО – алгоритм имитации отжига, ГА – генетический алгоритм, МНК – метод наименьших квадратов, ГМ – градиентный метод, ФК – фильтр Калмана)

Ниже приведен алгоритм параметрической идентификации с помощью гибридного алгоритма (третий способ гибридизации).

Алгоритм параметрической идентификации на основе гибридного алгоритма (третий способ гибридизации)

Шаг 1. Задание начальные параметры нечеткой модели и алгоритмов (генетического алгоритма, алгоритм имитации отжига, градиентного метода (фильтра Калмана) и метода наименьших квадратов), размера популяции генетического алгоритма popul_size.

Шаг 2. Генерация popul_size решений задачи алгоритмом имитации отжига.

Шаг 3. Создание начальной популяции генетического алгоритма из полученных popul_size решений.

Шаг 4. Запуск генетического алгоритма с полученной начальной популяцией. Передача «наилучшей» особи на вход градиентного метода (фильтра Калмана).

Шаг 5. Настройка параметров модели с помощью градиентного метода (фильтра Калмана).

Выводы

  1.  Разработаны алгоритмы формирования базы нечетких правил на основе субъективного разделения данных и процедуры диффузии. Нечеткие правила и функции принадлежности должны покрывать весь универсум, на котором они определены. Переход от одной функции принадлежности к другой не должен содержать разрывов, иначе поверхность вывода также будет содержать разрывы.
  2.  Разработаны алгоритмы идентификации на основе градиентного метода, фильтра Калмана, генетического алгоритма, метода наименьших квадратов и алгоритма имитации отжига. Сходимость алгоритма идентификации зависит от правильности выбора параметров метода, которым осуществляется идентификация. Результаты исследований влияния тех или иных параметров будут приведены на этапе эксперимента.  
  3.  Разработаны гибридные алгоритмы на основе классических (градиентный метод, фильтр Калмана, метод наименьших квадратов) и метаэвристических (генетический алгоритм и алгоритм имитации отжига) методов оптимизации, направленные на объединение преимуществ метаэвристических методов с преимуществами  методов, основанных на производных. Такое объединение повысит качество решений при умеренном количестве ресурсов и за приемлемое время.


ГЛАВА 3. ПРОГРАММНО-ИНСТРУМЕНТАЛЬНОЕ ОБЕСПЕЧЕНИЕ СИСТЕМ ИДЕНТИФИКАЦИИ НЕЧЕТКИХ МОДЕЛЕЙ

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

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

  1.  формирование базы нечетких правил,
  2.  настройка параметров антецедентов и консеквентов правил на основе наблюдаемых данных и на основе знаний эксперта,
  3.  реализация нечеткого вывода,
  4.  представления результатов вывода.

Основное требование – наличие описания изучаемого объекта или явления, заданное в виде таблицы наблюдений.

Программная система включает в себя следующие классы и модули:

  •  класс TFuzzySystem (хранение и  изменение структуры и параметров нечетких моделей, а так же методы для осуществления нечеткого вывода и оценки оптимальности модели);
  •  класс TGeneticAlgorithm (объекты и методы, необходимые для выполнения операторов генетического алгоритма);
  •  класс TAnnealingAlgorithm (алгоритм имитации отжига);
  •  класс TKalmanFilter (фильтр Калмана);
  •  класс TGradient (метод градиентного спуска);
  •  модуль Matrices (модуль для выполнения операций над матрицами);
  •  класс TIdentification (интерфейс между классом TFuzzySystem и классами, соответствующими методам идентификации).

3.1 Взаимодействие нечеткой модели и метода идентификации

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

  1.   Метод идентификации инициирует запрос к нечеткой модели на выдачу значения ошибки (в этом случае внутри класса «метод идентификации» создается экземпляр класса «нечеткая модели»);
  2.  Нечеткая модель посылает запрос методу идентификации на выдачу решения и выдает обратно значение ошибки (в этом случае внутри класса «нечеткая модель» создается экземпляр класса «метод идентификации»);
  3.  Организация модуля, осуществляющего интерфейс между классами «нечеткая модель» и «метод идентификации»

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

В общем виде схема взаимодействия будет иметь следующий вид (рис. 3.1):

Рис. 3.1. Схема взаимодействия нечеткой модели и метода идентификации

Для осуществления данной схемы взаимодействия требуется создание следующих внешних (интерфейсных) методов:

класс «нечеткая модель»

  •  set_parameters — метод установки параметров нечеткой модели;
  •  estimation — метод получения ошибки модели с текущими параметрами;

класс «метод идентификации»:

  •  init — метод инициализации полей класса;
  •  dat_ get— вывод текущего решения;
  •  data_set— получение оценки;
  •  is_continue — продолжение идентификации;
  •  final_data_ get — вывод конечного решения.

3.2 Функциональная структура программной системы

Функциональную структуру программной системы идентификации нечетких моделей можно представить в виде следующей схемы (рис. 3.2):

Рис. 3.2. Функциональная структура программной системы идентификации нечетких моделей

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

Блок моделирования и расчетов оформлен в виде dll-библиотеки и может быть интегрирован в любую программную систему для построения нечеткой модели изучаемого объекта.

3.3 Описание типов данных, классов и модулей программной системы

3.3.1 Типы данных

vector = array of double — динамический одномерный массивы для хранения векторов вещественных чисел

matrix = array of vector — динамический двумерный массив для хранения матриц вещественных чисел

3.3.2 Класс TFuzzySystem

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

Входные данные класса TFuzzySystem

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

Выходные данные класса TFuzzySystem

  •  параметры нечеткой модели;
  •  ошибка нечеткой модели для текущих параметров;
  •  значение выходной переменной для заданного вектора входных переменных.

3.3.3 Класс TGeneticAlgorithm

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

Входные данные класса TGeneticAlgorithm

  •  количество входов нечеткой модели;
  •  количество термов лингвистических переменных;
  •  тип функции принадлежности (1 – ‘треугольная’, 2 –  ‘трапециевидная’, 3 – ‘двухпараметрическая’);
  •  размер начальной популяции;
  •  стратегия выбора хромосом для выполнения оператора скрещивания (значение из списка:  ‘элитаризм’ ‘случайный отбор’, ‘рулеточный отбор’, ‘турнирный отбор’);
  •  вероятность скрещивания хромосом;
  •  тип оператора скрещивания (‘одноточечный’, ‘двухточечный’, ‘унифицированный’, ‘многоточечный’, ‘арифметический’);
  •  вид мутации (‘одноточечная’, ‘ многоточечная’);
  •  вероятность мутации;
  •  способ формирования текущей популяции;
  •  число шагов генетического алгоритма.

Выходные данные класса TGeneticAlgorithm

Одномерный массив со следующими данными:

  •  при работе алгоритма – гены особи, которую нужно оценить на данном этапе;
  •  в случае завершения работы алгоритма – гены особи с нулевым номером.

3.3.4 Класс TAnnealingAlgorithm

Класс предназначен для идентификации нечетких моделей алгоритм имитации отжига. Описание полей и методов класса приведено в приложении А.

Входные данные класса TAnnealingAlgorithm

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

Выходные данные класса TAnnealingAlgorithm

Одномерный массив со следующими данными:

  •  при работе алгоритма – текущее решение.
  •  в случае завершения работы алгоритма – лучшее решение.

3.3.5 Класс  TKalmanFilter 

Класс TKalmanFilter содержит поля для хранения матриц, необходимых для выполнения алгоритма фильтрации Калмана, а также методы, необходимые для организации процесса фильтрации. Описание полей и методов класса приведено в приложении А.

Входные данные класса TKalmanFilter

  •  количество входов нечеткой модели;
  •  количество термов лингвистических переменных;
  •  тип функции принадлежности (1 – ‘треугольная’, 2 –  ‘трапециевидная’, 3 – ‘двухпараметрическая’);
  •  начальный вектор параметров функций принадлежности;
  •  целевой вектор значений выходной переменной;
  •  число итераций алгоритма;
  •  способ задания ковариационной матрицы погрешности оценивания состояния системы;
  •  вектор параметров фильтра Калмана.

Выходные данные класса TKalmanFilter

Одномерный массив со следующими данными:

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

3.3.6 Класс TGradient

Класс TGradient содержит поля и методы, необходимые для организации работы метода градиентного спуска. Описание полей и методов класса приведено в приложении А.

Входные данные класса TGradient

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

Выходные данные

Одномерный массив со следующими данными:

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

 

3.3.7 Модуль Matrices

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

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

Описание функций модуля приведено в приложении А.

3.3.8 Класс TIdentification

Класс предназначен для выполнения процесса идентификации нечетких моделей. Осуществляет интерфейс между классом TFuzzySystem и классами TGeneticAlgorithm, TAnnealingAlgorithm TKalmanFilter и TGradient по выбранной схеме взаимодействия нечеткой модели и метода идентификации. Описание полей и методов класса приведено в приложении А.

Входные данные класса TIdentification

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

Выходные данные класса TIdentification

  •  параметры нечеткой модели;
  •  значение выходной переменной для заданного вектора входных переменных.

3.4 Описание пользовательского интерфейса

Взаимодествие с пользователем осуществляется при помощи одного окна, разделенного на пять следующих вкладок:

  •  «Исходные данные»;
  •  «Функции принадлежности»;
  •  «Метод идентификации»;
  •  «База правил»;
  •  «Результаты».

Закладка «Исходные данные»

В этой вкладке пользователь определяет исходные данные для построения модели  (рис. 3.3).

Рис. 3.3. Закладка «Исходные данные»

Пользователь имеет возможность работать с ранее определенной таблицей наблюдений или создать новую.

В первом случае он должен в пункте главного меню «Таблица наблюдений» (рис. 3.4) выбрать подпункт «Загрузить таблицу наблюдений». Далее выполняются стандартные действия.

Рис. 3.4. Пункт меню «Таблица наблюдений»

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

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

Также пользователю необходимо определить количество термов, на которые будут разбиты входные переменные.

При нажатии кнопки «Сформировать нечеткую систему по умолчанию» будет создана нечеткая модель с параметрами по умолчанию.

Для сохранения созданной таблицы наблюдений необходимо в пункте главного меню «Таблица наблюдений» (рис. 3.4) выбрать подпункт «Сохранить таблицу наблюдений».

Закладка «Функция принадлежности»

Закладка предназначена для задания типа и параметров функций принадлежности, а также отображения графиков функций принадлежности для каждой из входных переменных (рис. 3.5). По умолчанию задано равномерное распределение параметров по областям определения входных переменных.

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

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

Рис. 3.5. Закладка «Функции принадлежности»

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

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

При изменении функций принадлежности происходит автоматическое изменение базы правил. Просмотреть ее можно в закладке «База правил»

Закладка «Метод идентификации»

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

Рис. 3.6. Закладка «Метод идентификации»

При выборе того или иного метода (нажатии на соответсвующем компоненте radio button), в левой части закладки появляется панель выбора параметров метода идентификации. Первоначально соответствующие компоненты заполнены значениями по умолчанию. Для запуска процесса идентификации выбранным методом необходимо нажать кнопку «Оптимизировать», которая находится внизу формы.

Закладка «База правил»

Закладка для отображения базы правил, соответствующей текущим параметрам и структуре системы (рис. 3.7).

Рис. 3.7. Закладка «База правил»

Количество правил в базе определяется количеством входных переменных и количеством термов, на которые они разбиты. Обновление базы правил происходит при любом  изменении структуры и параметров нечеткой модели.


Закладка «Результаты»

 Закладка для отображения результатов нечеткого моделирования (рис. 3.8).

Рис. 3.8. Закладка «Результаты»

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

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

Выводы

  1.  Разработан программный комплекс, который, в отличие от известных систем нечеткого моделирования Fuzzy Logic Toolbox, CubiCalc, fuzzyTech, ориентированных на знания эксперта, позволяет формировать нечеткие модели, как на основе знаний эксперта, так и на основе наблюдаемых данных. Разработанная система классов может быть встроена в конкретную программную систему для построения нечеткой модели изучаемого объекта.
  2.   Анализ трех способов организации взаимодействия класса «нечеткая модель» и классов, соответствующих методам идентификации позволил выбрать третий способ (организация дополнительного класса, осуществляющего интерфейс между классами «нечеткая модель» и «метод идентификации»), позволяющий получить универсальные классы для нечеткой модели и методов идентификации и упрощающий процесс добавления нового метода идентификации в программную систему по сравнению с двумя другими способами организации взаимодействия.
  3.  Оформление блока моделирования и расчетов программной системы в виде dll-библиотеки позволяет включить разработанную систему классов в конкретную программную систему для построения нечеткой модели изучаемого объекта.


ГЛАВА 4. ИМИТАЦИОННОЕ ИССЛЕДОВАНИЕ РАЗРАБОТАННЫХ АЛГОРИТМОВ ИДЕНТИФИКАЦИИ НЕЧЕТКИХ МОДЕЛЕЙ

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

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

1) Функция с несколькими экстремумами  (рис.4.1)

Рис.4.1. График функции

2) Гладкая нелинейная функция

(рис. 4.2)

Рис.4.2. График функции

3) кусочно-линейная функция

(рис. 4.3)

Рис.4.3. График функции

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

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

Ошибки аппроксимации для треугольных функций принадлежности до настройки системы методами идентификации приведены в таблице 4.1.

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


Таблица 4.1

Ошибки аппроксимации до настройки системы

тестовая

функция

количество

термов

значения ошибки

среднеквадратичная

средняя абсолютная

максимальная

1

5

0,02189213

0,19862888

0,47785643

7

0,01207435

0,10891042

0,24285214

9

0,07571604

0,06227339

0,18175317

2

5

0,01064780

0,08202846

0,31026966

7

0,00525326

0,03603180

0,16811704

9

0,00318839

0,02307181

0,09492507

3

5

0,01669029

0,12933876

0,55555556

7

0,00939927

0,06731215

0,29952932

9

0,00622097

0,04196511

0,20277778

4.1 Исследование работы генетического алгоритма для настройки параметров нечетких моделей

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

Таблица 4.2

Значения параметров нечеткой модели и генетического алгоритма по умолчанию

Параметр

Значение

тип функций принадлежности

треугольные

количество термов

5

размер популяции

20

стратегия отбора

турнирный отбор

тип скрещивания

арифметическое

тип мутации

одноточечная

вероятность мутации

0,6

количество итераций

300

Влияние количества итераций на работу аппроксиматора

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

Для выявления оптимального числа итераций была исследована работа алгоритма на 50, 100, 300, 500  и 1000 шагах. Результат исследования представлен в таблице 4.3.

Таблица 4.3

Влияние количества итераций алгоритма на ошибку вывода нечеткой модели

тестовая

функция

Количество итераций

усредненная ошибка

относительное время

средне-

квадратичная

средняя абсолютная

максимальная

1

50

0,010148

0,068182

0,362235

3,25

100

0,003513

0,023654

0,111391

6,48

300

0,002615

0,015629

0,10407

19,31

500

0,002555

0,01573

0,102845

32,12

1000

0,002414

0,014155

0,102845

64

2

50

0,007145

0,056968

0,208581

3,25

100

0,001751

0,014341

0,056485

6,48

300

0,000856

0,006673

0,02954

19,31

500

0,000766

0,005859

0,027959

32,12

1000

0,000527

0,00407

0,019073

64

3

50

0,011448

0,068056

0,500801

3,25

100

0,006093

0,03521

0,268825

6,48

300

0,00577

0,031278

0,271009

19,31

500

0,005760

0,031193

0,268823

32,12

1000

0,005752

0,03081

0,268049

64

На рисунках 4.4-4.6 представлена динамика поиска решений генетическим алгоритмом.

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

Рис. 4.4. Динамика поиска решений генетическим алгоритмом для функции  

Рис. 4.5. Динамика поиска решений генетическим алгоритмом для функции

Рис. 4.6. Динамика поиска решений генетическим алгоритмом для функции

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

Влияние размера популяции на работу аппроксиматора

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

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

Таблица 4.4

Влияние размера популяции на ошибку вывода нечеткой модели

тестовая

Функция

размер популяции

усредненная ошибка

относительное время

средне-

квадратичная

средняя абсолютная

максимальная

1

10

0,003040

0,020574

0,101941

9,66

20

0,002615

0,015629

0,10407

19,31

30

0,002302

0,013637

0,099153

29,08

40

0,002451

0,013887

0,10475

37,24

2

10

0,001397

0,011091

0,046595

9,66

20

0,000856

0,006673

0,02954

19,31

30

0,000734

0,005332

0,02197

29,08

40

0,000452

0,003537

0,015461

37,24

3

10

0,005961

0,033770

0,270699

9,66

20

0,005770

0,031278

0,271009

19,31

30

0,005788

0,031737

0,270407

29,08

40

0,005732

0,029965

0,271082

37,24

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

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

Рис. 4.7. График зависимости усредненной среднеквадратичной ошибки от времени работы генетического алгоритма для различных значений размера популяции  для тестовой функции

 

Рисунок 4.8. График зависимости усредненной среднеквадратичной ошибки от времени работы генетического алгоритма для различных значений размера популяции  для тестовой функции

Рис. 4.9. График зависимости усредненной среднеквадратичной ошибки от времени работы генетического алгоритма для различных значений размера популяции  для тестовой функции

Влияние стратегии отбора

По полученным данным установлено, что тип отбора существенно влияет на качество работы генетического алгоритма (таблица 4.5). Наихудший результат обеспечивает случайный отбор. Это объясняется тем, что все особи в популяции выбираются для скрещивания с одинаковой вероятностью независимо от значения меры приспособленности.

Таблица 4.5

Влияние типа селекции на ошибку вывода нечеткой модели

тестовая

функция

тип отбора

усредненная ошибка

относительное

время

средне-

квадратичная

средняя абсолютная

максимальная

1

случайный

0,014180

0,103292

0,422336

20,40

рулеточный

0,003375

0,022154

0,110195

20,20

турнирный

0,002615

0,015629

0,10407

19,31

элитаризм

0,002459

0,014783

0,102361

20,03

Продолжение таблицы 4.5

2

случайный

0,005119

0,041155

0,178827

20,40

рулеточный

0,000397

0,003276

0,013045

20,20

турнирный

0,000856

0,006673

0,02954

19,31

элитаризм

0,000641

0,00481

0,022884

20,03

3

случайный

0,009321

0,061599

0,385025

20,40

рулеточный

0,005959

0,033348

0,273639

20,20

турнирный

0,00577

0,031278

0,271009

19,31

элитаризм

0,00586

0,031796

0,269406

20,03

Влияние типа оператора скрещивания

В работе исследовано 6 типов скрещивания: арифметическое, одноточечное, двухточечное, многоточечное, унифицированное и однородное.

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

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


Таблица 4.6

Влияние метода скрещивания на ошибку вывода нечеткой модели

тестовая

функция

метод скрещивания

усредненная ошибка

относительное

время

средне-

квадратичная

средняя абсолютная

максимальная

1

арифметическое

0,003513

0,023654

0,111391

6,48

одноточечное

0,003720

0,024958

0,120094

6,77

двухточечное

0,003893

0,025967

0,127672

6,68

многоточечное

0,003971

0,026288

0,127872

6,88

унифицированное

0,003810

0,025272

0,118797

6,78

однородное

0,004054

0,027457

0,139568

6,78

2

арифметическое

0,001751

0,014341

0,056485

6,48

одноточечное

0,002143

0,016517

0,07458

6,77

двухточечное

0,002044

0,015477

0,069259

6,68

многоточечное

0,001996

0,015582

0,066443

6,88

унифицированное

0,001835

0,013752

0,065437

6,78

однородное

0,002120

0,015847

0,075018

6,78

3

арифметическое

0,006093

0,03521

0,268825

6,48

одноточечное

0,006289

0,036442

0,272963

6,77

двухточечное

0,006288

0,035998

0,278844

6,68

многоточечное

0,006238

0,036402

0,275089

6,88

унифицированное

0,006166

0,035638

0,270856

6,78

однородное

0,006183

0,035741

0,277404

6,78

Влияние типа оператора мутации

 В таблице 4.7 приведены результаты исследования влияния типа мутации на время и точность аппроксимации.

Таблица 4.7

Влияние типа мутации на ошибку вывода нечеткой модели

тестовая

функция

тип мутации

усредненная ошибка

относительное

время

средне-

квадратичная

средняя абсолютная

максимальная

1

одноточечная

0,002615

0,015629

0,10407

19,31

многоточечная

0,004445

0,03259

0,140176

20,02

2

одноточечная

0,000856

0,006673

0,02954

19,31

многоточечная

0,002300

0,017776

0,083359

20,02

3

одноточечная

0,005770

0,031278

0,271009

26,44

многоточечная

0,006596

0,040354

0,27448

27,66

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

Влияние вероятности мутации

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

Таблица 4.8

Влияние вероятности мутации на ошибку вывода нечеткой модели

Тестовая

функция

вероятность мутации

усредненная ошибка

относительное

время

средне-

квадратичная

средняя абсолютная

максимальная

1

0,1

0,004479

0,0314

0,153608

19,23

0,3

0,002756

0,017074

0,105623

19,24

0,6

0,002615

0,015629

0,10407

19,31

0,9

0,002541

0,015342

0,10517

19,35

2

0,1

0,002117

0,017057

0,068226

19,23

0,3

0,001092

0,00858

0,037411

19,24

0,6

0,000856

0,006673

0,02954

19,31

0,9

0,000829

0,006262

0,030175

19,35

3

0,1

0,006116

0,035024

0,274045

19,23

0,3

0,00602

0,034168

0,273564

19,24

0,6

0,00577

0,031278

0,271009

19,31

0,9

0,005795

0,031546

0,267774

19,35

 

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


Влияние способа формирования текущей популяции

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

  1.  полная замена старой популяции новой, полученной в результате применения операторов скрещивания и мутации;
  2.  полная замена с добавлением в новую популяцию лучшей особи из старой популяции;
  3.  частичная замена; в этом случае в новую популяцию попадают «лучшие» особи, как из новой популяции, так и из старой
  4.  помещение в новую популяцию лучших хромосом из старого поколения и лучших хромосом из нового поколения в отношении 3:7;
  5.  помещение в новую популяцию лучших хромосом из старого поколения и худших хромосом из нового поколения в отношении 3:7;

Таблица 4.9

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

тестовая

функция

способ

усредненная ошибка

относительное

время

средне-

квадратичная

средняя абсолютная

максимальная

1

1

0,002771

0,016667

0,108970

19,34

2

0,002615

0,015629

0,104070

19,31

3

0,002657

0,015988

0,104072

19,59

4

0,002736

0,016483

0,108970

19,41

5

0,100638

0,014022

0,454905

19,41

2

1

0,00074

0,005835

0,026689

19,34

2

0,000856

0,006673

0,029540

19,31

3

0,00484

0,039303

0,134230

19,59

4

0,004328

0,034112

0,132989

19,41

5

0,00304437

0,02221100

0,3126038

19,41

3

1

0,005796

0,030605

0,270397

19,34

2

0,005770

0,031278

0,271009

19,31

3

0,005806

0,031269

0,280870

19,59

4

0,005779

0,031673

0,261631

19,41

5

0,0064016

0,0431405

0,316569

19,41

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

На рис. 4.10–4.12 представлены графики зависимости усредненной среднеквадратичной ошибки от времени работы генетического алгоритма для четырех первых способов формирования промежуточной популяции.  

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

Рис. 4.10. График зависимости усредненной среднеквадратичной ошибки от количества итераций генетического алгоритма для различных способов формирования текущей популяции  для  функции

Рис. 4.11. График зависимости усредненной среднеквадратичной ошибки от количества итераций генетического алгоритма для различных способов формирования текущей популяции  для  функции

Рис. 4.12. График зависимости усредненной среднеквадратичной ошибки от количества итераций генетического алгоритма для различных способов формирования текущей популяции  для  функции

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

  •  размер популяции – 20;
  •  стратегия отбора особей для скрещивания – турнирный отбор, элитаризм;
  •  тип оператора скрещивания – арифметический;
  •  тип оператора мутации – одноточечная;
  •  вероятность мутации – 0,6;
  •  способ формирования текущей популяции – полная замена, добавление «лучшей» особи из предыдущей популяции или помещение в новую популяцию лучших хромосом из старого поколения и лучших хромосом из нового поколения в отношении 3:7.

Влияние количества термов

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

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

Рис. 4.13. График зависимости усредненной среднеквадратичной ошибки от количества итераций  генетического алгоритма для изменяющегося числа термов для тестовой функции

Рис. 4.14. График зависимости усредненной среднеквадратичной ошибки от количества генетического алгоритма для изменяющегося числа термов для тестовой функции

Рис. 4.15. График зависимости усредненной среднеквадратичной ошибки от количества итераций генетического алгоритма для изменяющегося числа термов для тестовой функции

Таблица 4.10

Результаты эксперимента для изменяющегося числа термов

тестовая функция

количество термов

усредненная ошибка

относительное время

средне-

квадратичная

средняя абсолютная

максимальная

1

5

0,002615

0,015629

0,10407

19,31

7

0,004901

0,029251

0,153221

28,5

9

0,000247

0,001911

0,008363

38,41

2

5

0,000856

0,006673

0,029540

19,31

7

0,000424

0,003357

0,014055

28,5

9

0,000226

0,001785

0,007410

38,41

3

5

0,005770

0,031278

0,271009

19,31

7

0,00378

0,017496

0,186673

28,5

9

0,00291

0,013580

0,136628

38,41

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

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

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

4.2 Исследование работы алгоритма имитации отжига при настройке параметров нечеткой модели

Цель экспериментов – исследование и анализ работы алгоритма имитации отжига и нечеткой модели при изменении их параметров.

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

Таблица 4.11

Параметры алгоритма имитации отжига и нечеткой модели по умолчанию

алгоритм имитации отжига

начальная температура

0.01

конечная температура

0.0001

количество итераций

10

функция снижения температуры

коэффициент понижения температуры

0.8

нечеткая модель

количество термов

5

параметры функций принадлежности

равномерные

Влияние числа итераций

В таблице 4.12 приведены результаты экспериментов для различного количества итераций.

На рисунках 4.16 и 4.17 представлены графики зависимости среднеквадратичной ошибки от количества итераций при одном значении температуры для первой и второй тестовой функции соответственно.

Таблица 4.12

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

тестовая

функция

количество итераций

усредненная ошибка

относительно время

средне-

квадратичная

средняя абсолютная

максимальная

1

1

0,005361

0,033924

0,20807

1

10

0,003295

0,019557

0,10897

8

20

0,003265

0,019111

0,110195

16

50

0,003265

0,018794

0,110195

41

100

0,003215

0,018193

0,110195

86

2

1

0,002022

0,013885

0,078784

1

10

0,001419

0,009878

0,054679

8

20

0,00134

0,009498

0,050627

16

50

0,001312

0,009176

0,050041

40

100

0,001409

0,009551

0,0514

80

Рис. 4.16. Зависимость среднеквадратичной ошибки от количества итераций для функции

Рис. 4.17. Зависимость среднеквадратичной ошибки от количества итераций для функции

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

Влияние коэффициента понижения температуры

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

На рисунках 4.18 и 4.19 представлены графики зависимости среднеквадратичной ошибки от коэффициента понижения температуры для первой и второй тестовой функции соответственно.


Таблица 4.13

Влияние коэффициента понижения температуры на ошибку вывода нечеткой модели

Тестовая

Функция

коэффициент понижения температуры

усредненная ошибка

относительное

время

средне-

квадратичная

средняя абсолютная

максимальная

1

0,2

0,007978

0,046206

0,333474

1

0,4

0,004514

0,028262

0,149814

2

0,6

0,003843

0,023689

0,115608

4

0,8

0,003379

0,019616

0,108970

8

0,9

0,003266

0,018476

0,110195

17

2

0,2

0,002535

0,017801

0,097567

1

0,4

0,002379

0,02626

0,087022

2

0,6

0,00201

0,013771

0,075693

4

0,8

0,001419

0,009878

0,054679

8

0,9

0,001189

0,008139

0,045038

17

Рисунок 4.18. Зависимость ошибки от значения коэффициента понижения температуры для функции

Рис. 4.19. Зависимость ошибки от значения коэффициента понижения температуры для функции

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

Влияние температуры

В таблице 4.14 приведены результаты экспериментов для различных значений начальной и конечной температуры. Конечная температура меньше начальной в 100 раз для всех значений.

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

Таблица 4.14

Влияние значения начальной температуры на ошибку вывода нечеткой модели

Тестовая

функция

значение начальной температуры

усредненная ошибка

относительное время

средне-

квадратичная

средняя абсолютная

максимальная

1

0,000001

0,003738

0,021589

0,127145

8

0,00001

0,003638

0,020712

0,129729

8

0,0001

0,0037

0,021253

0,119091

8

0,001

0,003648

0,020628

0,132032

8

0,01

0,003379

0,019616

0,108970

8

0,1

0,00412

0,026657

0,131807

8

1

0,00714

0,046156

0,280374

8

2

0,000001

0,001002

0,006372

0,042794

8

0,00001

0,001016

0,006542

0,043969

8

0,0001

0,001163

0,007684

0,045598

8

0,001

0,001393

0,009577

0,054895

8

0,01

0,001419

0,009878

0,054679

8

0,1

0,001796

0,013025

0,066461

8

1

0,002775

0,019724

0,100303

8

 

На основе проведенных экспериментов были получены следующие параметры алгоритма имитации отжига:

  •  начальная температура – 0,00001;
  •  конечная температура – 0,0000001;
  •  коэффициент понижения температуры – 0.9;
  •  количество итераций при одном значении температуры – 10.

В таблице 4.15 приведены результаты экспериментов для различного количества термов. Эти эксперименты проводились для рекомендуемых параметров алгоритма имитации отжига.

Таблица 4.15

Результаты эксперимента для изменяющегося числа термов.

Тестовая функция

количество термов

усредненная ошибка

относительное время

средне-

квадратичная

средняя абсолютная

максимальная

1

5

0,003379

0,019616

0,108970

8

7

0,005053

0,029356

0,155318

12

9

0,001797

0,009691

0,082858

19

2

5

0,001419

0,009878

0,054679

8

7

0,000661

0,004671

0,023386

12

9

0,000504

0,00349

0,019483

19

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

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

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

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

4.3 Исследование фильтра Калмана

Цель этой части эксперимента — исследование и анализ работы фильтра Калмана и нечеткой модели при изменении их параметров.

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

  •  количество термов лингвистических переменных,
  •  способ задания начального значения матрицы P;
  •  для второго способа задания матрицы  P— параметр p;
  •  параметры r и q  — значения диагональных элементов матриц R и Q, соответственно.

Значения параметров фильтра Калмана и нечеткой модели  по умолчанию приведены в таблице 4.16.

Таблица 4.16

Параметры фильтра Калмана и нечеткой модели по умолчанию

фильтр Калмана

количество итераций

100

R

1

Q

0,01

нечеткая модель

количество термов

5

равномерное распределение параметров

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

Влияние числа итераций алгоритма фильтрации Калмана

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

Таблица 4.17

Результаты эксперимента для изменяющегося числа итераций алгоритма фильтрации

тестовая функция

число итераций

ошибка

относительное время

средне-

квадратичная

средняя абсолютная

максимальная

1

10

0,002672

0,016784

0,110195

2,1

50

0,00208

0,012442

0,110195

11

100

0,002077

0,01232

0,110195

22

200

0,002077

0,012307

0,110195

40

500

0,002077

0,012307

0,110195

110

2

10

0,001879

0,0123

0,081462

2,1

50

0,00057

0,00309

0,033288

10

100

6,13E-05

0,000302

0,00304

20

200

2,23E-07

1,08E-06

1,04E-05

40

500

1,22E-14

8,21E-14

5,90E-13

100

3

10

0,005771

0,029432

0,268436

1,6

50

0,005718

0,029632

0,267689

8,1

100

0,005713

0,029722

0,267657

16

200

0,005713

0,029745

0,267622

32

500

0,005713

0,029746

0,267621

85

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

В таблице 4.18 представлены результаты экспериментов для различного количества термов.

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

Таблица 4.18

Результаты эксперимента для изменяющегося числа термов

тестовая функция

количество термов

ошибка

относительное время

средне-

квадратичная

средняя абсолютная

максимальная

1

5

0,002077

0,012322

0,110195

22

7

0,005318

0,031819

0,155717

27

9

0,00072

0,003861

0,048354

33

2

5

6,13E-05

0,000302

0,00304

22

7

0,000679

0,004221

0,030203

27

9

0,000239

0,000239

0,010774

31

3

5

0,005713

0,029722

0,267657

18

7

0,003734

0,016727

0,183353

21

9

0,002872

0,012476

0,141164

27

Влияние матриц шумов

 Особое внимание нужно уделить экспериментам со значениями матриц R и Q. Как следует из таблиц 4.19 и 4.20, уменьшение параметра r и увеличение параметра q ведет к большей скорости сходимости фильтра к оптимуму. Но в случае настройки параметров функций принадлежности при использовании фильтра Калмана, так же как и других методов на основе производных, возможен «разрыв» функций принадлежности – состояние, когда функции принадлежности не будут покрывать всю область изменения переменной. Поэтому для большей устойчивости фильтра лучше использовать большие значения параметра r и небольшие значения q. Но при очень больших r  и очень малых q скорость сходимости фильтра будет очень низкой.

Таблица 4.19

Результаты эксперимента для изменяющегося параметра q

Тестовая функция

q

ошибка

относительное время

средне-

квадратичная

средняя абсолютная

максимальная

1

0,00001

0,002079

0,012366

0,110195

22

0,0001

0,002079

0,012384

0,110195

22

0,01

0,002077

0,012322

0,110195

22

0,1

0,002077

0,012308

0,110195

22

2

0,00001

0,001155

0,007492

0,056545

22

0,0001

0,001067

0,006997

0,053807

22

0,01

6,13E-05

0,000302

0,00304

22

0,1

7,02E-09

3,51E-08

3,76E-07

22

3

0,00001

0,005743

0,029559

0,265128

18

0,0001

0,005739

0,029585

0,265581

18

0,01

0,005713

0,029722

0,267657

18

0,1

0,005713

0,029745

0,267621

18

Таблица 4.20

Результаты эксперимента для изменяющегося параметра r

тестовая функция

r

ошибка

относительно время

средне-

квадратичная

средняя абсолютная

максимальная

1

0,1

0,002077

0,012307

0,110195

22

1

0,002077

0,012322

0,110195

22

10

0,006878

0,05485

0,133976

22

100

0,008020

0,064603

0,159257

22

2

0,1

1,85E-09

1,23E-08

7,70E-08

22

1

6,13E-05

0,000302

0,00304

22

10

0,000983

0,005602

0,055045

22

100

0,001894

0,012097

0,090209

22

3

0,1

0,005713

0,029748

0,26762

18

1

0,005713

0,029722

0,267657

18

10

0,006203

0,035422

0,270837

18

100

0,005818

0,029276

0,277685

18

В результате экспериментов получено, что важно также и соотношение значений параметров: необходимо, чтобы значение параметра p как минимум в 10 раз должно превосходить значение параметра q.

Выводы по использованию фильтра Калмана для настройки нечетких моделей, предназначенных для решения задачи аппроксимации

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

  •  увеличение количества итераций работы алгоритма в большинстве случаев существенно уменьшает ошибку до определенного момента, дальнейшее увеличение количества итераций не дает значительного уменьшения ошибки, при этом время идентификации растет линейно, поэтому необходимо прерывать работу алгоритма при прекращении улучшения решения;
  •  уменьшение параметра r и увеличение параметра q ведет к большей скорости сходимости фильтра к оптимуму, но может нарушить устойчивость фильтра. При этом при очень больших r  и очень малых q скорость сходимости фильтра низка. По результатам исследований получено, что влияние на устойчивость алгоритма оказывает и соотношение этих параметров и значение параметра p как минимум в 10 раз должно превосходить значение параметра q, значение q должно быть меньше единицы. Значения параметров r и q не оказывают влияние на время работы алгоритма.

4.4 Исследование метода градиентного спуска

На данном этапе проводилось исследование работы метода градиентного спуска и влияния параметров метода на сходимость алгоритма.

Изменялись следующие параметры:

  •  количество термов лингвистических переменных,
  •  число итераций метода градиентного спуска;
  •  значение коэффициентов метода градиентного спуска.

Значения параметров метода градиентного спуска и нечеткой модели по умолчанию приведены в таблице 4.21.

Таблица 4.21

Параметры метода градиентного спуска и нечеткой модели по умолчанию

метод градиентного спуска

количество итераций

100

коэффициент

0,05

нечеткая модель

количество термов

5

равномерное распределение параметров

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

В таблицах 4.22-4.24 представлены результаты экспериментов для различного числа итераций метода градиентного спуска для пяти, семи и девяти термов соответственно.

Таблица 4.22

Результаты эксперимента для изменяющегося числа итераций метода градиентного спуска (5 термов)

тестовая функция

число итераций

ошибка

относительное

время

средне-

квадратичная

средняя

абсолютная

максимальная

1

10

0,005988

0,053082

0,130353

1

50

0,005749

0,051248

0,121708

5

100

0,005593

0,050573

0,114311

13

500

0,005271

0,050368

0,090622

58

1000

0,00538

0,051247

0,091374

121

2

10

0,001835

0,013409

0,066839

1

50

0,00164

0,01205

0,054398

5

100

0,001556

0,011464

0,052262

10

500

0,001245

0,008587

0,042478

51

1000

0,000965

0,006451

0,032577

103

3

10

0,005246

0,030385

0,25627

1

50

0,0051

0,02964

0,247195

5

100

0,0051

0,029474

0,245362

10

500

0,00497

0,029775

0,238136

51

1000

0,004882

0,029704

0,232552

103

Таблица 4.23

Результаты эксперимента для изменяющегося числа итераций метода градиентного спуска (7 термов)

Тестовая

функция

количество итераций

ошибка

относительное

время

средне-

квадратичная

средняя абсолютная

максимальная

1

10

0,003085

0,027206

0,057221

2

50

0,00066

0,006045

0,014312

9

100

0,00063

0,005429

0,014603

18

500

0,00049

0,004236

0,011494

92

1000

0,000363

0,00311

0,008454

180

2

10

0,00081

0,00511

0,032123

2

50

0,000601

0,004276

0,019791

8

100

0,000544

0,003936

0,017413

15

500

0,00027

0,001988

0,008601

78

1000

0,003983

0,000923

0,000923

150

3

10

0,0033

0,01429

0,169824

2

50

0,002975

0,014756

0,142926

8

100

0,002928

0,013954

0,136378

15

500

0,002857

0,014226

0,127112

80

1000

0,002825

0,01448

0,122757

150

Таблица 4.24

Результаты эксперимента для изменяющегося числа итераций метода градиентного спуска (9 термов)

тестовая

функция

количество итераций

ошибка

относительное время

средне-

квадратичная

средняя абсолютная

максимальная

1

10

0,002868

0,019526

0,077498

2

50

0,00047

0,00276

0,013886

12

100

0,00012

0,00101

0,003331

24

500

6,42E-06

3,91E-05

0,000235

120

1000

4,73E-06

2,81E-05

0,000168

238

2

10

0,000435

0,003181

0,012957

2

50

4,23E-05

0,000307

0,001539

12

100

1,01E-05

7,22E-05

0,000352

23

500

2,86E-06

2,28E-05

7,89E-05

121

1000

6,44E-07

5,13E-06

1,82E-05

238

3

10

0,002439

0,009404

0,122293

2

50

0,001904

0,008977

0,084036

9

100

0,001764

0,008867

0,073504

18

500

0,001668

0,007772

0,064176

96

1000

0,001665

0,007832

0,063436

210

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

Влияние значений коэффициентов метода градиентного спуска

В таблице 4.25 представлены результаты исследований для различных значений параметров метода градиентного спуска.

Таблица 4.25

Влияние значений коэффициентов метода градиентного спуска на ошибку вывода нечеткой модели

тестовая

функция

коэффициенты обучения

ошибка

относительное время

средне-

квадратичная

средняя абсолютная

максимальная

1

0,005

0,006062

0,052606

0,128615

13

0,01

0,005985

0,052114

0,127705

13

0,05

0,005593

0,050573

0,114311

13

0,1

0,005263

0,049862

0,096999

13

0,5

0,005282

0,03544

0,221327

13

1

0,035549

0,268537

0,839359

13

2

0,005

0,001846

0,013485

0,066495

10

0,01

0,001753

0,012784

0,012784

10

0,05

0,001556

0,011464

0,052262

10

0,1

0,001299

0,009081

0,04502

10

0,5

6,15E-08

4,69E-07

2,37E-06

10

1

7,52E-14

5,94E-13

2,40E-12

10

3

0,005

0,00525

0,030402

0,256205

10

0,01

0,005177

0,030297

0,249771

10

0,05

0,0051

0,029474

0,245362

10

0,1

0,004992

0,029853

0,239835

10

0,5

0,004782

0,03054

0,222084

10

1

0,006096

0,04456

0,220039

10

 

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

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

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

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


4.5 Исследование метода наименьших квадратов

В таблице 4.26 представлены результаты настройки параметров консеквентов методом наименьших квадратов.

Таблица 4.26

Ошибки нечеткой модели после метода наименьших квадратов

тестовая

функция

количество

термов

значения ошибки

средне-

квадратичная

средняя абсолютная

максимальная

1

5

0,001751

0,012826

0,055414

7

0,001514

0,011097

0,049388

9

5,15E-05

4,08E-04

0,000133

2

5

0,005079

0,044947

0,107149

7

0,000706

0,006048

0,015792

9

4,63E-05

2,69E-04

0,000152

3

5

0,00516

0,029449

0,248294

7

0,002943

0,013279

0,135719

9

0,001669

0,007749

0,063932

4.6 Исследование гибридных алгоритмов

На данном этапе исследовалась работа гибридных алгоритмов, построенных на основе предложенных метаэвристик и методов, основанных на производных.

Первый способ гибридизации

В таблицах 4.27 и 4.28 представлены результаты работы гибридного алгоритма (первый способ гибридизации) на основе генетического алгоритма и градиентного метода (таблица 4.27) и генетического алгоритма и фильтра Калмана (таблица 4.28) для различного количества термов для трех тестовых функций.

На первом этапе запускался генетический алгоритм для сужения пространства поиска, затем запускались методы, основанные на производных (эксперименты проводились при рекомендуемых значениях параметров алгоритмов).

Таблица 4.27

Результаты эксперимента с гибридным алгоритмом на основе метода наименьших квадратов, генетического алгоритма и фильтра Калмана (первый способ гибридизации)

тестовая функция

количество термов

усредненная ошибка

относительное время

средне-

квадратичная

средняя абсолютная

максимальная

1

5

0,000557

0,004479

0,020706

48

7

0,000350

0,002437

0,017275

62

9

0,000199

0,002127

0,011101

85

2

5

0,0004326

0,003063

0,016578

48

7

5,7E-5

0,000321

0,001526

62

9

1,17 E-06

9,00E-06

4,83E-05

85

3

5

0,004913

0,030322

0,227657

48

7

0,002643

0,010569

0,135719

62

9

0,001459

0,006332

0,051164

85

Таблица 4.28

Результаты эксперимента с гибридным алгоритмом на основе метода наименьших квадратов, генетического алгоритма и градиентного метода (первый способ гибридизации)

тестовая функция

количество термов

усредненная ошибка

относительное время

средне-

квадратичная

средняя абсолютная

максимальная

1

5

0,000585

0,003692

0,025790

42

7

0,000350

0,002437

0,017275

58

9

0,000104

0,000524

0,004338

81

2

5

5,94E-06

2,92E-05

0,000358

42

7

0,000093

0,000621

0,003526

58

9

2,32E-07

2,39 E-06

1,07 E-05

81

3

5

0,004962

0,030322

0,227657

42

7

0,002643

0,010569

0,135719

58

9

0,001459

0,006565

0,053932

81

 

Использование гибридного алгоритма на основе генетического алгоритма и методах, основанных на производных, позволяет существенно уменьшить значения ошибки вывода по сравнению с использованием методов идентификации по отдельности (данные сравнивались на уровне значимости 0,05).


Второй способ гибридизации

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

Таблица 4.29

Результаты эксперимента с гибридным алгоритмом на основе метода наименьших квадратов, генетического алгоритма и фильтра Калмана (второй способ гибридизации)