Суть работы
Широкое применение нечетких систем для решения проблем автоматического управления, прогнозирования, принятия решений заставляет специалистов искать эффективные методы построения систем, для идентификации которых наряду с алгоритмами оптимизации, основанными на производных, применяются генетические алгоритмы, эволюционные стратегии и нейронные сети. Эволюционные стратегии совместно с эволюционным программированием и генетическим алгоритмом представляют три главных направления развития эволюционного моделирования. Несмотря на то, что каждый из методов возник независимо от других, они характеризуются рядом общих свойств. Для любого из них формируется исходная популяция, которая подвергается селекции и воздействию различных генетических операторов, что позволяет находить более хорошие решения. Эволюционная стратегия – это алгоритмы, созданные в качестве методов решения оптимизации задач и основанные на принципах природной эволюции. Целью работы является описание классического алгоритма эволюционно стратегии для идентификации нечеткой системы.
Основные понятия
Популяция – конечное множество особей.
Особи – хромосомы с закодированным в них множеством параметров.
Ген – атомарный элемент генотипа(свойство хромосомы).
Генотип (структура) – набор хромосом данной особи
Фенотип – набор значений, соответствующий данному генотипу (декодированная структура или множество параметров задачи) – решение, точка пространства поиска.
Аллель – значение конкретного гена, свойства или вариант свойства.
Локус (позиция) – указывает место размещения данного гена в хромосоме. А локи – это множество позиций генов.
Функция приспособленности – мера приспособленности данной особи в популяции.
Идентификация параметров – это определение неизвестных параметров антецедентов и консеквентов нечетких правил путем оптимизации работы нечеткой системы по заданному критерию.
База правил – структура описывающая логику работы апроксиматора /классификатора и состоит из правил.
Правила – Элемент базы правил следующего вида.
Для задачи аппроксимации:
Ri: If x1=A1i and x2=A2i and x3=A3i and…and…xn=Ani then y=Ψ
где x=(x1, x2, x3, …, xn) вектор параметров аппроксимируемой модели;
Aki – нечеткий терм, характеризующий k-ый параметр в i-том правиле;
Ψ – числовое значение выхода аппроксиматора.
Аппроксиматор — вычислительный блок, на вход которому приходит значения параметров модели и требуется получить число, которое будет близко в модели.
Антецедент – часть правила для задачи аппроксимации, соответствующая части правила до ключевого слова then…
Консиквент – часть правила для задачи аппроксимации, соответствующая части правила после ключевого слова then. [1]
Нечеткая система
Нечеткое моделирование осуществляется посредством системы нечеткого вывода, которая выполняет следующие действия [2, 3]:
1. Преобразует числовую информацию в лингвистические переменные (процесс фаззификации);
2. Обрабатывает лингвистическую информацию, выполняя логические операции нечеткой конъюнкции, импликации и агрегации правил;
3. Формирует численные результаты (процесс дефаззификации).
Процесс фаззификации описывает предметную область посредством лингвистических переменных и правил естественного языка, содержащих качественную оценку ситуации. Основой для описания ситуации является нечеткое высказывание следующего вида:
xi есть Ai или xi = Ai,
где xi – некоторая величина; Ai – элемент терм-множества лингвистической переменной из исследуемой предметной области.
Обработка лингвистической информации происходит при помощи базы правил. Каждое правило состоит из двух частей: условной и заключительной. Антецедент или условная часть (ЕСЛИ–часть) содержит утверждение относительно значений входных переменных, в консеквенте или заключительной части (ТО–части) указывается значение, которое принимает выходная переменная. Таким образом, нечеткая система типа «много входов – один выход» может быть задана нечеткими правилами следующего вида:
правило 1: ЕСЛИ x1 = А11 И x2 = А21 И … И xm = Аm1 ТО r = R1;
правило 2: ЕСЛИ x1 = А12 И x2 = А22 И … И xm = Аm2 ТО r = R2;
………………………………………………………………………………..….….……
правило n: ЕСЛИ x1 = А1n И x2 = А2n И … И xm = Аmn ТО r = Rn,
где x1, x2, …, xm – входные переменные;
r – выходная переменная;
Аij – нечеткие области определения входных переменных, которые определены на универсальных множествах X1, X2, …, Xm;
Rs – значение выходной переменной, которое может быть представлено как действительное число, либо как функция, определенная на входных переменных, либо как нечеткая область определения выходной переменной. Каждая нечеткая область Аij связана с функцией принадлежности
[4].Процесс дефаззификации зависит от типа нечеткой системы.
Рассмотрим нечеткая модель типа синглтон. Она задается правилами вида:
правило i:
ЕСЛИ x1 = А1i И x2 = А2i И … И xm = Аmi ТО r = ai,
где ai – действительное число.
Модель типа синглтон осуществляет отображение
, заменяя оператор нечеткой конъюнкции произведением, а оператор агрегации нечетких правил — сложением. Отображение F определяется следующей формулой:
, (1.1)где
, n — количество правил нечеткой модели;
m — количество входных переменных в модели;
— функция принадлежности нечеткой области.Функции принадлежности
Функции принадлежности для нечетких систем представляют собой субъективное представление эксперта о предметной области. Часто такая субъективность помогает снизить степень неопределенности при решении слабо формализованных задач. Как правило, для задания функций принадлежности используются типовые зависимости, параметры которых определяются путем обработки мнений экспертов. Представление произвольных функций при реализации автоматизированных систем часто затруднено, поэтому в реальных разработках такие зависимости аппроксимируются кусочно-линейными функциями [5].
Выход нечёткой модели напрямую зависит от вида функции принадлежности, например, при использовании треугольных функций, получаем:
(1.2)Параметрическая идентификация
Параметры функции принадлежности входных переменных нечеткой системы можно представить в следующем виде:
Xromosoma=[N_xromosomi, N_ruls, N_peremennoi, [an,bn,cn] ] (1.3)
где N_xromosomi – номер генерируемой хромосомы;
N_ruls – номер правила;
N_peremennoi – номер переменной;
[an,bn,cn] – тройка параметров в модели типа синглтон с треугольными функциями принадлежности.
Параметры, входящие в данный вектор влияют на адекватность модели. Задача параметрической идентификации – определить неизвестные параметры консеквентов нечетких правил путем оптимизации работы нечеткой системы по заданному критерию.
Параметрическая идентификация рассматривается как процесс оптимизации нечеткой модели, который сводится к нахождению таких параметров нечеткой системы, чтобы ошибка вывода была минимальной.
При этом оценивается качество нечеткого вывода по значениям ошибки вывода (– разницы между значениями выходной переменной из таблицы наблюдений f(x) и значениями F(x), полученными нечеткой системой. Исследуются три типа ошибки вывода:
Среднеквадратичная ошибка:
(1.4)Среднеабсолютная ошибка:
(1.5)Максимальная ошибка:
(1.6)Ошибки вывода представляются в следующем виде:
Error_for_xromosoma=[N_xromosomi, N_type_error] (1.7)
где N_xromosomi – номер хромосомы,
N_type_error-тип ошибки.
Для задач параметрической идентификации нечеткой системы адаптируется алгоритм эволюционной стратегии [1].
Эволюционная стратегия
Эволюционная стратегия — эвристический метод оптимизации в разделе эволюционных алгоритмов, основанный на адаптации и эволюции. Стратегия основана на механизмах естественного отбора и наследования. В ней используется принцип выживания наиболее приспособленных особей. Преимущества алгоритма перед другими методами оптимизации заключаются в параллельной обработке множества альтернативных решений. [3]
Алгоритм работает с популяцией особей (хромосом), каждая из которых представляет собой упорядоченный набор параметров задачи, подлежащих оптимизации. Основной характеристикой каждой особи является ее мера приспособленности.
При поиске решения в эволюционной стратегии вначале происходит мутация и скрещивание особей для получения потомков, затем происходит детерминированный отбор без повторений лучших особей из общего поколения родителей и потомков. В качестве мутации часто используется добавление нормально распределенной случайной величины к каждой компоненте хромосомы. При этом параметры нормального распределения самоадаптируются в процессе выполнения алгоритма.
Работа алгоритма представляет собой итерационный процесс, который продолжается до выполнения одного из условий останова:
• выполнение заданного числа поколений;
• прекращение улучшения популяции.
Алгоритм эволюционной стратегии для настройки нечеткой системы
Классический алгоритм эволюционной стратегии для настройки нечеткой системы приведен ниже:
Вход:
Таблица наблюдений;
Выход:
Оптимизированная база правил. Значение ошибки нечеткого вывода.
Алгоритм:
Шаг 1. Задание количества термов
Шаг 2. Построение базы правил для каждой хромосомы:
• Построение нечетких термов, равномерно распределенных по каждой переменной
• Задание консеквентов для каждого правила методом ближайшего из таблицы наблюдение
Шаг 3. Генерация хромосом
Шаг 4. Подсчет ошибок
Шаг 5. Выбор параметров алгоритма эволюционной стратегии:
• задание количества итераций
• количество точек скрещивание и алгоритм скрещивание
• вероятность мутации
• тип алгоритма селекции
Шаг 6. Генерация начальной популяции
Шаг 7. Вычисление меры приспособленности.
Если достигнуто условие выхода Шаг 11, иначе Шаг 8
Шаг 8. Применение алгоритма скрещивания
Шаг 9. Применение алгоритма мутации
Шаг 10. Селекция и отбор хромосом для новой популяции. Переход на Шаг 7
Шаг 11. Вывод решения – «наилучшей» хромосомы
Алгоритмическая часть программы
В среде визуального программирования Microsoft Visual Studio 2010 была написана программа, предназначенная для параметрической идентификации нечетких систем, в основе которой лежат алгоритм эволюционной стратегии.
Входными данными является таблица наблюдений, выходными – набор параметров нечеткой системы, обеспечивающий наиболее адекватное построение модели, и значения основных ошибок, по которым оценивается адекватность.
Реализованы несколько типов оператора скрещивания: многоточечный и унифицированный тип. Селекция – случайный отбор, турнирный отбор, рулеточный отбор и стратегия элитаризма. В результате применения оператора мутации случайным образом вносятся изменения в гены некоторых особей. Исследована многоточечная случайная мутации.
Заключение
В ходе разработки и исследования системы параметрической идентификации нечетких моделей были получены тестовые результаты на тестовых функциях, которые показали необходимость в доработке и возможной модернизации.
В дальнейшем планируется тестирование системы на реальных данных, сравнение результатов с методами генетического алгоритма. Модернизация эволюционной стратегии засчет применения матриц ковариации. Также возможно применение других функций принадлежности. Но об этом в следующий раз.
Литература
1. S. Hoche, and S. Wrobel. A Comparative Evaluation of Feature Set Evolution Strategies for Multirelational Boosting. Proc. 13th Int. Conf. on ILP 2003.
2. Espinosa J., Vandewalle J., Wertz V. Fuzzy logic, identification and predictive control. — London: Springer-Verlag, 2005. — 263 p.
3. Рутковская Д., Пилиньский М., Рутковский Л.: Нейронные сети, генетические алгоритмы и нечеткие системы. — М.: Горячая линия-телеком, 2006. — 452 с.
4. Ходашинский И.А. Технология идентификации нечетких моделей типа синглтон и Мамдани. / Труды VII международной конференции «Идентификация систем и задачи управления» SICPRO '08. Москва, 28-31 января 2008 г. Институт проблем управления им. В.А. Трапезникова РАН. — М: Институт проблем управления им. В.А. Трапезникова РАН, 2008. — С. 137-163.
5. Корнеев В.В., Гареев А.Ф., Васютин С.В., Райх В.В. Базы данных. Интеллектуальная обработка информации. — М.: «Нолидж», 2000. 352 c.
6. Пантелеев А.В., Летова Т.А. Методы оптимизации в примерах и задачах. — М.: Высш. шк., 2005. — 544 c
Спасибо за внимание!
