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

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

Содержание

Введение

1. Нечеткое моделирование: основные понятия и принципы

2. Задача нечеткой классификации

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

2.2 Алгоритм решения

3. Формирование базы правил для нечеткого классификатора

3.1 Классификация нечетких моделей

3.1.1 Структура модели

3.1.2 Управляемая данными инициализация

3.2 Сокращение модели

3.2.1 Отбор свойств, основанный на межклассовой отделимости

3.2.2 Упрощение базы правил

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

4.1 Основные понятия эволюционного программирования

4.1.1 Символьная модель

4.1.2 Канонический генетический алгоритм

4.1.3 Кроссовер

4.1.4 Мутация

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

4.2.1 Алгоритм генерации базы знаний

4.2.2 Получение "родительского элемента

4.2.3 Мутация

4.2.4 Нечеткие операторы

4.2.5 Условие останова

4.3 Описание генетического алгоритма

4.3.1 Нечеткое представление модели

4.3.2 Функция выбора

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

4.3.4 Ограничения

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

Заключение

Список используемой литературы



Введение

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

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

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

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

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

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



1. Нечеткое моделирование: основные понятия и принципы

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

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

– нечеткое (лингвистическое) описание входных и выходных переменных системы, которое обусловлено неточной информацией, получаемой от ненадежных датчиков, или качественной информацией, получаемой от эксперта;

– нечеткое описание системы в виде совокупности если-то - правил, отражающих особенности функционирования на качественном уровне.

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

Нечеткие правила - это нечеткие продукционные правила Под продукцией понимается кортеж следующего вида: <>, где i - имя продукции, Q характеризует сферу применения продукции, AB - ядро продукции (обычное прочтение ядра выглядит как: если A, то B), P - условие применимости ядра продукции или предусловие, N - постусловие продукции описывает действия и процедуры, которые необходимо выполнить после реализации B. Основной частью продукции является ядро, остальные элементы носят вспомогательный характер, поэтому в наиболее простом виде продукция может состоять лишь из имени и ядра., которые при фиксированной цели управления (например, сохранение значений управляемого параметра в некоторой области допустимых значений) описывают его стратегии на качественном уровне.

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

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

Лингвистическая переменная задается кортежем <, T, U, G, M>, где - название переменной; Т - базовое терм-множество или множество основных лингвистических значений (термов) переменной , причем каждому из них соответствует нечеткая переменная с функцией принадлежности, заданной на U; G - синтаксическое правило, описывающее процесс образования из множества Т новых значений лингвистической переменной

называется расширенным терм-множеством); М - семантическое правило, согласно которому новые значения лингвистической переменной , полученные с помощью G, отображаются в нечеткие переменные (это может быть процедура экспертного опроса, позволяющая приписать каждому новому значению, образованному процедурой G, некоторую семантику путем формирования соответствующего нечеткого множества). Шкала U, на которой определена лингвистическая переменная, может быть числовой или нечисловой.

Нечеткое число - это нечеткая переменная, определенная на числовой оси функцией принадлежности . Самые простые нечеткие числа - треугольные и трапециевидные.

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

Трапециевидное нечеткое число А с отрезком толерантности [a,b], левой шириной и правой шириной задается функцией

Треугольное нечеткое число с центром в точке а можно рассматривать как нечеткое значение высказывания х приблизительно равен а, в то время как трапециевидное число обозначает нечеткое значение высказывания х находится приблизительно в интервале [a,b]. Величины l и r также называются соответственно левым и правым коэффициентами нечеткости и показывают насколько неточно (нечетко) определены границы числа. Трапециевидное нечеткое число обозначается кортежем ; при получим треугольное нечеткое числа .

Нечеткое моделирование - это методология, согласно которой правило вида R_i: если x есть A_i, то y есть B_i ,

в котором посылка (условие) x есть A_i и заключение y есть B_i представляют собой нечеткие высказывания, переводится в четкую модель, т.е. функцию , которая описывает связь между множествами X и Y. Совокупность нечетких правил , предназначенных для формального представления эмпирических знаний или знаний экспертов в некоторой проблемной области, образует базу правил. Лингвистические переменные, которые используются в условиях нечетких правил, называются входными переменными, а в заключениях - выходными. При формировании базы правил необходимо определить множество входных лингвистических переменных, множество выходных лингвистических переменных и множество нечетких правил, связывающих входные переменные с выходными. Заметим, что нечеткие правила должны быть согласованы относительно используемых в них переменных. Согласованность правил означает, что в качестве условий и заключений правил могут использоваться только нечеткие лингвистические высказывания рассмотренных выше типов, и в каждом из нечетких высказываний должны быть определены функции принадлежности значений терм-множеств для каждой из лингвистических переменных.



2. Задача нечеткой классификации

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

Пусть имеется N объектов, каждый из которых характеризуется n свойствами, так что объекту соответствует векторная оценка . - множество векторных оценок. Требуется определить разбиение множества на подмножества , такие что и для (, для . Подмножества будем называть классами (или кластерами). Если разбиение определено, то для любого нового объекта определить, к какому классу он принадлежит.

2.2 Алгоритм решения

Замечание: Данная задача связана с поиском на множестве векторных оценок А отношения эквивалентности Е, которое однозначно определяет искомое разбиение. Оно представляет собой фактор-множество отношения А по отношению эквивалентности Е.

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

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

Блок задание векторной оценки нового объекта представляет объект классификации как вектор, состоящий из n компонент (характеристик).

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

Рис. 1. Модель нечеткого классификатора

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

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

В блоке вывод о принадлежности к классу определяется наиболее вероятная принадлежность объекта к одному из заданных классов.



3. Формирование базы правил для нечеткого классификатора

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

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

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

Рис. 2. Процесс проектирования нечеткого классификатора

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

3.1 Классификация нечетких моделей

Нечеткие модели в зависимости от типа входных и выходных параметров можно разделить следующим образом (Рис. 3).

Рис. 3

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

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

,

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

.

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

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

Модель Takagi - Sugeno (TS-модель) можно рассматривать как комбинацию лингвистической и регрессионной модели. Она задается в следующем виде:

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

3.1.1 Структура модели

Мы применяем нечеткие правила классификации, каждое из которых описывает один из классов в наборе данных. Априорное правило является нечетким описанием в n-мерном пространстве свойств и последовательность правил является свежей (ненечеткой) меткой класса из множества :

.

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

.

Выход классификатора затем определяется правилом, которое имеет наивысшую степень активации:

.

В дальнейшем мы предполагаем, что число классов соответствует числу правил, т.е. M=. Степень уверенности в решении дана нормализованной степенью запуска правила:

.

3.1.2 Управляемая данными инициализация

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

Шаг 1: М функций принадлежности многих переменных определяются в пространстве функций продукта. Каждая описывает область, где система может быть приближена единственным нечетким правилом. Это разбиение может быть реализовано итерационными методами, такими как кластеризация. Здесь предложен одношаговый подход. Это предполагает, что каждый класс описывается единственной компактной конструкцией в пространстве функций. Если дело обстоит не так, могут быть применены другие методы, такие как, например, реляционные классификации. Подобный нечеткому алгоритму объединения в кластеры, подход, предложенный здесь, также предполагает, что форма нечетких множеств может быть приближена эллипсоидами. Таким образом, каждый прототип класса представляет собой центр его ковариационной матрицы :

.

.

Здесь i обозначает индекс классов, , и обозначает число образцов, принадлежащих i-му классу.

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

.

Используя расстояние, принадлежность становится:

.

где m - весовой показатель, определяющий размытость полученных разделений (m = 1,8 применяется в примере).

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

Шаг 3: Одномерные нечеткие множества в классификации правил (1) получаются путем проектирования рядов U на входные переменные , а затем приближением проекций параметрическими функциями. Для простоты мы применяем треугольные нечеткие числа:

.

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

3.2 Сокращение модели

3.2.1 Отбор свойств, основанный на межклассовой отделимости

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

Шаг 1: Строится матрица .

.

.

- число случаев в каждом классе. Общая матрица разброса может быть представлена как:

.

.

.

Критерий выбора отделимости межклассовой особенности является обменом между и .

Шаг 2: Ранжирование особенности делается многократно, не учитывая худшую особенность в каждом шаге, и применяется в открытом цикле выбора особенности:

,

где det - определитель и - значение критерия, включая j особенностей.

3.2.2 Упрощение базы правил

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

.

где обозначает мощность множества, а и операторы представляют собой объединение и пересечение соответственно. Если , то две функции принадлежности эквивалентны. S (A,B) становится 0, когда функции принадлежности не накладываются.

Нечетких множества объединяются, когда их сходства превышают определяемый пользователем порог (применяется = 0,5). Слияние уменьшает количество различных нечетких множеств (лингвистических терминов), используемых в модели, и тем самым увеличивает прозрачность. Если все нечеткие множества для высказывания сходны с универсальным набором или если слияние привело только к одной функции принадлежности для высказывания, то это высказывание исключается из модели. Метод иллюстрируется на Рис. 4.

Рис. 4

Здесь нечеткие множества A₁₁, A₂₁ и A₃₁ подобны, следовательно, они объединяются в одно нечеткое множество, которое исключаются из модели. Нечеткое множество A₃₂ является объединением множеств A₁₂ и A₂₂, поэтому его исключают из модели. Множества A₁₃ и A₂₃ сходны, поэтому они тоже объединяются.



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

4.1 Основные понятия эволюционного программирования

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

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

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

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

Цель генетических алгоритмов в том, чтобы:

- Абстрактно и формально объяснять адаптацию процессов в естественной системе и интеллектуальной исследовательской системе.

- Моделировать естественные эволюционные процессы для эффективного решения задач науки и техники.

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

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

- Работают в основном не с параметрами задачи, а с закодированным множеством параметров.

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

- Используют целевую функцию, а не ее различные приращения для оценки качества принятия решений.

- Применяют не детерминированные, а вероятностные правила анализа оптимизационных задач.

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

4.1.1 Символьная модель

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

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

Каждая хромосома (строка) представляет собой объединение ряда подкомпонентов, называемых генами. Гены располагаются в различных позициях или локусах хромосомы, и принимают значения, называемые аллелями. В представлениях с бинарными строками, ген-бит, локус - его позиция в строке, и аллель - его значение (0 или 1). Биологический термин "генотип" относится к полной генетической модели особи и соответствует структуре в ГА. Термин "фенотип" относится к внешним наблюдаемым признакам и соответствует вектору в пространстве параметров. Чрезвычайно простой, но иллюстративный пример - задача максимизации слудующей функции двух переменных:

.

Обычно, методика кодирования реальных переменных и состоит в их преобразовании в двоичные целочисленные строки достаточной длины - достаточной для того, чтобы обеспечить желаемую точность. Предположим, что 10-ти разрядное кодирование достаточно для и . Установить соответствие между генотипом и фенотипом закодированных особей можно, разделив соответствующее двоичное число на . Например, 0000000000 соответствует 0/1023 или 0, тогда как 1111111111 соответствует 1023/1023 или 1. Оптимизированная структура данных - 20-ти битная строка, представляющая конкатенацию кодировок и . Переменная размещается в крайних левых 10-ти разрядах, тогда как размещается в правой части генотипа особи (20-ти битной строке). Генотип - точка в 20-мерном хемминговом пространстве, исследуемом ГА. Фенотип - точка в двумерном пространстве параметров.

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

4.1.2 Канонический генетический алгоритм (Canonical GA)

Данная модель алгоритма является классической. Она была предложена Джоном Холландом в его знаменитой работе "Адаптация в природных и искусственных средах" (1975). Часто можно встретить описание простого ГА (Simple GA, D. Goldberg), он отличается от канонического тем, что использует либо рулеточный, либо турнирный отбор. Модель канонического ГА имеет следующие характеристики:

· Фиксированный размер популяции.

· Фиксированная разрядность генов.

· Пропорциональный отбор.

· Особи для скрещивания выбираются случайным образом.

· Одноклеточный кроссовер и одноклеточные мутации.

4.1.3 Кроссовер

Оператор кроссовера (crossover operator) является основным генетическим оператором, за счет которого производится обмен генетическим материалом между особями. Кроссовер моделирует процесс скрещивания особей.

Пусть имеются две родительские особи с хромосомами и . Случайным образом определяется точка внутри хромосомы, в которой обе хромосомы делятся на две части и обмениваются ими. Назовем эту точку точкой разрыва. Вообще говоря, в англоязычной литературе она называется точкой кроссовера (crossover point). Описанный процесс изображен на рисунке 5.

Родительские особи Потомки

.

Рис. 5. Кроссовер

Данный тип кроссовера называется одноточечным, так как при нем родительские хромосомы разрезаются только в одной случайной точке. Также существует 2-х и n-точечный операторы кроссовера. В 2-х точечном кроссовере точек разрыва 2, а n-точечный кроссовер является своеобразным обобщением 1- и 2-точечного кросоеверов для n>2.

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

4.1.4 Мутация

Оператор мутации (mutation operator) необходим для вывода популяции из локального экстремума и способствует защите от преждевременной сходимости. Это достигается за счет того, что инвертируется случайно выбранный бит в хромосоме, что показано на рисунке 6.

До мутации После мутации

.

Рис. 6. Мутация

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

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



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

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

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

4.2.1 Алгоритм генерации базы знаний

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

Идея эволюционных стратегий была предложена Инго Рехенбергом (Ingo Rechenberg) в 1960-70 годах. Так же, как и генетические алгоритмы, они работают с популяцией решений и основываются только на целевой функции и ограничениях. Основные отличия от классического генетического алгоритма заключаются в том, что эволюционная стратегия работает с векторами действительных чисел и использует только оператор мутации. При мутации каждому элементу вектора добавляется случайная нормально распределенная величина.

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

.

Метод кодирования нечеткой системы с двумя входами и одним выходом показан на рисунке 6.

Рисунок 6. Нечеткие правила, закодированные в хромосому

Правило 3 на рисунке 7 означает следующее:

Если есть и есть , то y есть .

Здесь и - трапециевидные функции принадлежности с четырьмя параметрами.

В нашей задаче один вход и один выход, поэтому правила представлены в следующем виде: Если x есть , то y есть , где i - номер правила.

4.2.2 Получение "родительского элемента

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

4.2.3 Мутация

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

4.2.4 Нечеткие операторы

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

Отмена. Если функция принадлежности становится слишком "узкой", она не должна больше использоваться. Данный критерий записывается следующим образом:

,

где и - длины медиан функций принадлежности заданных входных и выходных переменных в i-м и j-м правилах;

- параметр отмены. Чем он больше, тем критерий более строгий.

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

Для слияния существует два критерия:

,

,где и - длины медиан функций принадлежности заданных входных и выходных переменных в i-м и j-м правилах;

f - расстояние между центром и .

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

,

где

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

,

,

,

,

где - исходные параметры трапециевидной функции принадлежности;

- новые значения и ; параметры не меняются.

4.2.5 Условие останова

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

* выполнение заданного числа поколений;

* прекращение улучшения популяции.

Когда была получена начальная нечеткая модель, она была упрощена и оптимизирована итерационным методом. Комбинации GA с инструментами сокращения модели, описанными выше, могут привести к различным схемам моделирования. Три разных подхода показаны на Рис. 7.

Рис. 7. Моделирование схемы в результате сочетания инструментов

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

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

.

где MCE является средней ошибкой классификации:

.

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

.

где n - число входов и - количество наборов для каждого входной переменной. Функция надбавки определяет, поощрено ли подобие () или наказано (). В примере для двух случаев применено неподвижное -0.2 и 0.2.

4.3 Описание генетического алгоритма

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

4.3.1 Нечеткое представление модели

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

,

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

4.3.2 Функция выбора

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

,

.

и является представлением модели, закодированном в хромосоме . Обратная к функции выбора используется, чтобы выбрать хромосомы для удаления. Лучшая хромосома всегда сохраняется в популяции (элитарный выбор). Шанс, что отобранная хромосома используется в переходной операции, составляет 90 % и шанс мутации составляет 10 % (в данной работе). Когда хромосома отобрана для перехода (или мутации), с равной вероятностью применяется один из трех переходных (или мутационных) операторов.

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

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

(1) Однородная мутация; случайный отобранный элемент заменяется , являющимся случайным числом из диапазона []. Результирующие хромосомы

,

(2) Множественная единая мутация; единая мутация n случайно

(3) выбранных элементов, где n также выбрано случайно из {1,…,N}.

(4) Мутация Гаусса; все элементы хромосомы видоизменены таким образом что

,

, k =1,2,…,N.

Здесь - случайное число из распределения Гаусса с нулевым средним и адаптивной дисперсией:

.

Настройка параметра, выполненная этим оператором, становится все лучше и лучше с увеличением счетчика поколения.

(5) Простой арифметический переход; и пересечены в k-й позиции. Получающееся потомство:

,

где k выбрано случайно из {2,…,N-1}.

(6) Полный арифметический переход; линейная комбинация и превращается в

, .

Эвристический переход; и объединяются так, что

и .

4.3.4 Ограничения

Оптимизация, представленная GA, подвергнута двум типам ограничений: разделение и область поиска. Ограничение разделения запрещает пробелы в частях входных данных (антецедентов) переменных. Кодирование нечеткого множества должно соответствовать (9), т.е. . Для того чтобы избежать пробелов в частях, пары соседних нечетких множеств ограничены: , где L и R обозначают левый и правый набор, соответственно. Область поиска GA ограничена определенным пользователем связанным параметром, который относится к предыдущему правилу. Оценка предназначена, чтобы поддержать различимость набора терминов моделей (нечетких множеств), позволяя параметрам, описывающим нечеткие множества, изменяться только в пределах границы , вокруг их начальных значений, где - длина (диапазон) области, на которой определены нечеткие множества . Ограничения области поиска закодированы двумя векторами, и , являющимися верхней и нижней границей на каждом из элементов N в хромосоме. В пределах поколения начального разделения, и в случае однородной мутации, элементы сгенерированы наугад в пределах этих границ.

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

(1) Учитывая модель матрицы Z и базу нечетких правил, выберите число поколений Т, численность населения L, число операций и ограничения и - нынешнее число решений , и пусть - вектор соответствующих значений функции оценки:

(2) Создайте начальную хромосому из начальной базы нечетких правил.

(3) Вычислите векторы ограничений и , используя .

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

(5) Повторите генетическую оптимизацию для t = 0,1,2,…,T-1:

(a) Оцените и получите

(b) Выберите хромосом для операции.

(c) Выберите хромосом для удаления.

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

(e) Осуществите раздел ограничений.

(f) Создайте новую популяцию , заменяя хромосомы, выбранные для удаления управляемыми хромосомами.

(6) Выберите лучшее решение из , оценивая .



Заключение

В ходе выполнения курсовой работы были изучены:

– основы нечеткого моделирования;

– модель и принцип работы нечеткого классификатора;

– процесс проектирования нечеткого классификатора и формирования базы правил.

Была разработана программа, выполняющая построение нечеткого классификатора на основе наблюдаемых данных.

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



Список используемой литературы

1. Леденева Т.М. Основы нечеткого моделирования в среде MatLab: учебное пособие / Т.М. Леденева, Д.С. Татаркин, А.С. Тарасова. - Воронеж: ЛОП ВГУ, 2006. - 51 с.

2. Леденева Т.М. Обработка нечеткой информации / Т.М. Леденева. - Воронеж: ВГУ, 2006. - 232 с.

3. Roubos J.A. Learning Fuzzy Classification Rules from Labeled Data. / J.A. Roubos, M. Setnes, J. Abonyi. // Elsevier Preprint, 2001.

4. Рутковская Д. Нейронные сети, генетические алгоритмы и нечеткие системы. / Рутковская Д., Пилинский М., Рутковский Л. - Москва: Горячая линия - Телеком, 2004. - 315 с.

5. Тэрано Т. Прикладные нечеткие системы. / Тэрано Т., Асаи К., Сугено М. - Москва: Мир, 1993. - 386 с.

6. Гладков Л.А. Генетические алгоритмы: Учебное пособие. - 2-е изд. / Л.А. Гладков, В.В. Курейчик, В.М. Курейчик. - М.: Физматлит, 2006. - 320 с.

7. Рыжков А.П. Элементы Теории нечетких множеств и измерения нечеткости. / А.П. Рыжков - М.: Диалог-МГУ, 1998.

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

...