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

КВАЛИФИКАЦИОННАЯ РАБОТА БАКАЛАВРА

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

Глава 1. Постановка задачи на разработку методов автоматического формирования нечетких систем управления

1.1 Тестовая задача

1.2 Функция пригодности

1.3 Формирование задачника

1.4 Общая постановка задачи

Глава 2. Сведения из теории интеллектуальных систем

2.1 Нечеткая логика

2.2 Искусственные нейронные сети

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

Глава 3 Методы и алгоритмы автоматического формирования нечетких систем управления

3.1 Генетический подход к формированию БП для нечеткой системы управления

3.2 Нейросетевой подход к формированию БП для нечеткой системы управления

3.3 Настройка семантики лингвистических переменных

3.4 Коэволюционный алгоритм для формирования НСУ в целом

Глава 4. Практическая реализация разработанных подходов и исследование эффективности их работы

4.1 Программная реализация

4.2 Подбор оптимальной структуры оптимизационного алгоритма

4.3 Сравнение эффективности подходов

Заключение

Актуальность

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

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

Цель работы

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

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

1. разработать методы автоматического формирования базы правил (БП) нечеткого контроллера

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

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

4. исследовать данные методы на тестовой задаче и сравнить результаты.

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

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

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

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

2. Разработан, реализован и исследован новый метод автоматической настройки семантики лингвистических переменных.

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

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

Алгоритмы автоматического формирования базы правил позволяют:

1. минимизировать роль человека при разработке НСУ,

2. ускорить процесс разработки НСУ,

3. уменьшить затраты на разработку НСУ,

4. решать более сложные задачи.

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

Защищаемые положения

1. Метод автоматического формирования БП, основанный на искусственной нейронной сети, превосходит по эффективности метод, основанный на генетических алгоритмах.

2. Метод автоматической настройки семантики лингвистических переменных позволяет улучшить работу НСУ для фиксированной базы правил;

3. Разработанный метод совместной настройки семантики лингвистических переменных и базы правил позволяет эффективно разрабатывать НСУ и превосходит по эффективности каждый из этих алгоритмов в отдельности;

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

Апробация

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

VII Всероссийская научная конференция «Решетневские чтения», Красноярск 2003.

Всероссийская научная конференция молодых ученых «НАУКА. ТЕХНОЛОГИИ. ИННОВАЦИИ», Новосибирск 2003.

37-ая Краевая научная студенческая конференция, Красноярск 2004.

42-ая научно-практическая конференция студентов, аспирантов и молодых ученых, посвященная Всемирному дню авиации и космонавтики, секция «Кибернетики», Красноярск 2004.

Всероссийская научная конференция студентов, аспирантов и молодых ученых, Кемерово 2004.

Межрегиональный научный фестиваль «Молодежь и наука — третье тысячелетие», Красноярск 2004.

Публикации

По материалам данной работы авторами опубликовано 8 печатных работ, из них: 3 — статьи в сборниках, 5 — работы, опубликованные в материалах конференций. Также на данный момент 2 статьи находятся в печати. Полный список публикаций представлен в конце работы.

Разработанные методы и алгоритмы

Методы и алгоритмы, разработанные Малько Владимиром.

1. Генетический подход для формирования базы правил НСУ.

2. Алгоритм настройки семантики лингвистических переменных.

3. Критерий оценивания эффективности работы НСУ.

Методы и алгоритмы, разработанные Липинским Леонидом.

1. Нейросетевой подход для формирования базы правил НСУ.

2. Коэволюционный алгоритм для настройки НСУ в целом.

3. Задачник для оценивания эффективности работы НСУ.

Методы, алгоритмы и модули программной системы, разработанные совместно Малько Владимиром и Липинским Леонидом.

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

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

3. Редактор базы правил нечеткой системы управления.

Структура работы

Квалификационная работа содержит основной текст на 45 с., 19 иллюстраций, приложение на 9 с., список использованной литературы из 5 наименований, список публикаций авторов, и имеет следующую структуру:

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

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

В главе 3 рассмотрены методы формирования БП и настройки семантики лингвистических переменных и описан алгоритм формирования НСУ в целом.

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

Глава 1. Постановка задачи на разработку методов автоматического формирования нечетких систем управления

1.1 Тестовая задача

Оценка качества рассматриваемых подходов производилась на следующей тестовой задаче: имеется система «Тележка — Перевернутый маятник», изображенная на рисунке 1.1.1.

Рис. 1.1.1 Система «Тележка — Перевернутый маятник»

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

(1.1.1)

(1.1.2)

где (t) — угол наклона маятника от вертикали в момент времени t,

'' (t) — угловая скорость,

''' (t) — угловое ускорение,

x (t) — позиция тележки в момент времени t,

x' (t) — скорость тележки,

x'' (t) — ускорение движения тележки,

l — длина маятника (от точки вращения до центра масс),

m_b — масса маятника,

m — суммарная масса тележки и маятника,

g — гравитационная постоянная,

F (t) — сила, прилагаемая к тележке в момент времени t.

Данные уравнения не учитывают силу трения при движении.

Состояние системы в каждый момент времени характеризуется значением 4-х ее параметров:

· положение системы — x (t);

· линейная скорость системы - x'(t);

· угол отклонения маятника - (t);

· угловая скорость маятника - '(t).

Управляющим воздействием является сила F (t), прикладываемая к системе «Тележка — Перевернутый маятник».

Система может перемещаться вдоль одной оси в интервале от минус 100 до 100 м. Маятник может совершать колебания в интервале от минус 12 до 12 градусов. Если значения положения системы или угла маятника превышают указанные интервалы, то считается, что система управления потерпела неудачу.

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

1.2 Функция пригодности

Оценка эффективности работы БП для задачи «Тележка — Перевернутый маятник» производилась по следующему критерию, который необходимо было минимизировать в процессе оптимизации:

(1.2.1)

(1.2.2)

(1.2.3)

(1.2.4)

(1.2.5)

где a — максимально допустимое число шагов (тактов) работы системы при тестировании,

S_q — число шагов, сделанных системой, до момента прекращения тестирования,

K_i — уровень значимости i-го параметра системы, i = 1, 2, 3, 4,

P_{i Cur} — текущие значение i-го параметра системы, i = 1, 2, 3, 4,

P_{i max} — максимальное реально достигаемое значение i-го параметра системы, i = 1, 2, 3, 4,

N — количество параметров системы (в нашем случае N = 4),

P_{1 j} — позиция тележки на j-м шаге,

P_{2 j} — линейная скорость тележки на j-м шаге,

P_{3 j} — угол отклонения маятника от вертикали на j-м шаге,

P_{4 j} — угловая скорость отклонения маятника на j-м шаге.

Значения 0.5 в формуле FitS, 200 в формуле B и 0.3 в формуле C были подобраны экспериментально.

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

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

[A] - когда почти все индивиды начнут более или менее хорошо «ловить» маятник, их пригодность будет уже определяться тем, насколько хорошо они «ловят» (FitS устремится к 0.5, а [A] начнет доминировать над FitS, определяя качество);

[B] - если индивид не смог продержаться заданное число тактов при тестировании, т. е. потерял управление над системой за число шагов, меньшее чем a, то он считается не способным решить данную тестовую задачу за что и получает «штрафные баллы»;

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

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

1.3 Формирование задачника

Для более объективной оценки качества управления, был введен тестовый задачник (ТЗ). ТЗ состоит из набора начальных параметров системы. Система ставится в условия каждой тестовой задачи, после чего запускается контроллер. Качество управления оценивается по критерию (1.2.1). Общая оценка находится как сумма оценок качества по каждой задаче.

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

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

1.4 Общая постановка задачи

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

(1.4.1)

где — значение критерия (1.2.1) на i-ой тестовой задачи из задачника, — значение соответствующего компонента критерия на i-ой тестовой задаче, M — количество задач в ТЗ.

Глава 2. Сведения из теории интеллектуальных систем

2.1 Нечеткая логика

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

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

Рассмотрим основные понятия определения из теории нечетких множеств.

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

Пусть S — множество с конечным числом элементов, S = {}, где n — число элементов (мощность) множества S, R — некоторое свойство. Тогда, нечеткое множество A, элементы которого удовлетворяют свойству R, определяется как множество пар {}, где — характеристическая функция принадлежности (или просто функция принадлежности), принимающая значения из упорядоченного множества M = [0,1]. Функция принадлежности указывает степень принадлежности элемента s нечеткому множеству A, причем, = 1, если элемент s полностью удовлетворят свойству R, и = 0 — в противном случае.

Введем еще несколько определений, которые понадобятся нам в дальнейшем.

Опорное множество A, обозначаемое как supp (A), есть четкое подмножество множества S, все элементы которого имеют не нулевую степень принадлежности в A, т. е. supp (A) = s S .

Нечеткое множество A называется нормальным, если существует элемент sS такой, что = 1. В противном случае A — субнормально.

Очень часто при описании какого-либо объекта возникают такие ситуации, когда мы не можем достаточно точно определить численные значения его параметров, а можем лишь задать их приблизительные значения. К примеру, глубина реки «больше 80» метров, Петрову «около 30» лет и т. д. Это все есть примеры так называемых нечетких чисел.

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

В зависимости от того, как мы определяем нечеткое число s S — «s приблизительно равен a» или «s приблизительно лежит в интервале [a;b]», — оно может быть представлено либо как триангулярное, либо как трапецеидальное.

Нечеткое множество A называется триангулярным нечетким числом с вершиной (или центром) a, шириной слева >0 и шириной справа >0, если его функция принадлежности имеет вид

(2.1.1)

и мы используем обозначение A = (a, ,). Опорным множеством множества A является (a —, a +). Данное нечеткое число с центром a можно понимать как нечеткую величину «s приблизительно равно a».

Нечеткое множество A называется трапецеидальным нечетким числом с интервалом допуска [a, b], шириной слева >0 и шириной справа >0, если его функция принадлежности имеет вид

(2.1.2)

и мы используем обозначение A = (a, b, ,). Опорным множеством множества A является (a —, b +). Данное нечеткое число можно понимать как нечеткую величину «s приблизительно находится в интервале [a, b]».

Нечеткие системы управления. Нечеткие системы управления (нечеткие контроллеры, НСУ) являются наиболее важным приложением теории нечетких множеств. Функционирование нечетких логических контроллеров отличается от работы обычных контроллеров. Это отличие состоит в том, что обычные контроллеры основаны на аналитическом выражении, описывающем объект управления, в то время как нечеткие контроллеры используют знания экспертов. Эти знания могут быть выражены естественным образом с помощью так называемых лингвистических переменных.

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

Лингвистические переменные характеризуются пятеркой (x, T (x), U, G, M), в которой x — имя переменной, T (x) — множество термов x, т. е. множество имен лингвистических величин x, каждое значение которой есть нечеткое число, определенное на U, G — синтаксические правила для выработки имен величин x, M — семантические правила для связывания каждой величины с ее смыслом.

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

Нечеткие логические системы управления обычно состоят из четырех основных частей: Интерфейс фаззификации (введение нечеткости на четких входных данных), База нечетких правил, Машина нечеткого вывода и Интерфейс дефаззификации (исключение нечеткости для обеспечения четкого выхода).

Интерфейс фаззификации — оператор фаззификации переводит четкие данные в нечеткие множества.

База нечетких правил — содержит информацию о связях нечетких входных и выходных значений.

Машина нечеткого вывода — механизм сопоставления по БП нечетких значений входных параметров нечетким значениям выходных.

Интерфейс дефаззификации — оператор дефаззификации переводит нечеткие множества в четкие значения.

В общем виде принцип работу НСУ представлен на рисунке 2.1.1.

Рис. 2.1.1 Структурная схема нечеткого логического контроллера

2.2 Искусственные нейронные сети

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

Рис. 2.2.1 Схема искусственного нейрона

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

S =, (2.2.1)

Y = f (S) = f (), (2.2.2)

где x ₁, x ₂, …, x _n — нормированные входные сигналы,

w ₁, w ₂, …, w _n — веса синаптических связей,

S — взвешенная сумма входных сигналов,

f (S) — функция активации.

Рис. 2.2.2 а) функция единичного скачка; б) линейный порог (гистерезис); в) сигмоид — гиперболический тангенс; г) сигмоид — формула (2.2.3)

Нелинейная функция f (s) — функция активации — может иметь различный вид (см. рисунок 2.2.2). Наиболее распространенной является нелинейная функция с насыщением — сигмоид (функция S-образного вида):

(2.2.3)

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

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

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

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

Рис. 2.2.3 Нейронная сеть с k скрытыми слоями

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

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

Обучение сети может производиться одним из двух способов: с учителем и без учителя. При обучении с учителем набирается некоторый объем наблюдений, либо с помощью экспертной оценки создается минимальный задачник (совокупность входных и выходных значений) и на их основе производится обучение нейронной сети по одному из известных алгоритмов обучения, например, Error Back Propagation — алгоритм обратного распространения ошибки. Если такой подход невозможен, то используется обучение без учителя. Настройка весом в этом случае производится либо на основе конкуренции нейронов между собой, либо с учетом корреляции обучающих и выходных сигналов. Примерами алгоритмов обучения без учителя могут служить алгоритм Winner Take All, генетические алгоритмы, обучение по Хеббу.

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

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

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

автоматический проектирование нейронный семантика

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

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

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

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

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

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

Преимуществами данного вида селекции является:

· нет преждевременной сходимости,

· нет стагнации,

· индивиды популяции охватывают большую площадь поискового пространства.

Недостаток: низкая эффективность поиска.

Пропорциональная селекция. Пропорциональная селекция является наиболее распространенной и используемой в ГА. Вероятность отбора индивида для скрещивания при данной селекции пропорциональна его пригодности и определяется следующим образом:

p_i = ,

где f_i — пригодность i — го индивида, — средняя пригодность популяции и N — объем популяции.

Однако данная модель селекции обладает двумя отрицательными чертами:

· преждевременная сходимость — если на ранних поколениях был получен индивид с f_i >>, но f_i << f_max, то гены такого индивида быстро распространятся на всю популяцию и рекомбинация не сможет более производить новых индивидов, т. е. f_i << f_max навсегда;

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

Ранговая (линейная) селекция. Первоначально происходит упорядочивание индивидов по их пригодности (по возрастанию), т. е. f_i f_j для i > j. Затем каждому индивиду, в зависимости от его места в упорядоченном ряду, назначается вероятность p_i быть отобранным. Для линейной ранговой селекции используется следующее распределение вероятностей: p_i = ai + b (a <0), причем _i p_i = 1. Здесь, i — номер индивида в ранжированном ряде, a и b — параметры линейной ранговой селекции.

Основные преимущества данной модели селекции:

· нет преждевременной сходимости,

· нет стагнации,

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

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

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

Преимущества турнирной селекции:

· нет преждевременной сходимости,

· нет стагнации,

· не требуется глобальное переупорядочивание,

· не требуется явное вычисление функции пригодности.

Элитарная селекция. Набирается группа из M наилучших индивидов из всей популяции (M — размер элиты и 2 M). Затем отобранная элита переносится в новую популяцию, а оставшиеся (N — M) индивидов новой популяции получаются при скрещивании индивидов элитарной группы между собой. Индивиды, не вошедшие в элиту, игнорируются и не участвуют ни в каких операциях.

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

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

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

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

Рис. 2.3.1 Пример одноточечной рекомбинации

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

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

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

Хорошим эмпирическим правилом считается выбор вероятности мутации из соотношения p_m =, где H — число бит в хромосоме. На основе этого правила можно произвести классификацию мутации по трем типам:

— слабая (p_m <),

— средняя (p_m =),

— сильная (p_m >).

Схема работы генетического алгоритма:

Инициализация популяции случайными значениями;

Оценивание популяции;

Повторять, пока не выполнится условие останова:

Селекция. Отбор по определенной методике части популяции для воспроизводства;

Рекомбинация. Формирование индивидов новой популяции путем обмена частей хромосом отобранных родителей;

Мутация. Изменение генов хромосом индивидов полученной популяции для восстановления потерянной информации;

Оценивание. Оценивание пригодности индивидов популяции.

Замещение. Отбор индивидов в следующее поколение из популяции родителей и потомков.

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

Глава 3 Методы и алгоритмы автоматического формирования нечетких систем управления

Для упрощения работы с БП при оптимизации нами был предложен следующий способ преобразования БП из вида if x = A then y = B к целочисленному виду. Каждому терму лингвистических переменных присваивался номер, соответствующий порядку его расположения на числовой оси. Например, в случае описания переменной 5-ю термами, им будут присвоены следующие номера — «Отрицательное большое» = 0, «Отрицательное малое» = 1, «Ноль» = 2, «Положительное малое» = 3 и «Положительное большое» = 4 (см. рис. 3.1).

Рис. 3.1 Порядок нумерации терм лингвистических переменных

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

3.1 Генетический подход к формированию БП для нечеткой системы управления

Каждый индивид в ГА представляет собой решение — БП, содержащую все правила, необходимые для управления системой, и принадлежащую множеству всех возможных БП.

В ГА БП кодируется бинарной строкой фиксированной длины. Поскольку БП представляет собой n-мерный целочисленный массив, то ее кодировка не составляет особой сложности (см. рис. 3.1.1). Если учесть тот факт, что БП симметрична относительно точки равновесия (точка в БП, где все входные параметры принимают нулевые значения), то длину хромосомы можно уменьшить в два раза. Тем самым мы уменьшаем время, затрачиваемое на поиск лучшего решения, и одновременно увеличиваем «качество» найденных решений.

Рис. 3.1.1 Кодирование решений в ГА После кодирования БП в хромосому запускается механизм обычного ГА, параметры которого были подобраны наиболее эффективным образом на основании проведенных нами исследований.

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

Полученная таким образом БП достаточно хорошо справляется с управлением системой, однако, поскольку поисковое пространство дискретно и содержит порядка 7⁸⁷⁵ точек, из которых надо выбрать наилучшую, то оптимизационному алгоритму сложно справиться с такой задачей. Вследствие чего, в сформированной БП существуют «пробелы», попадая в которые система теряет управляемость. Возникает необходимость более эффективного подхода к формированию базы правил.

3.2 Нейросетевой подход к формированию БП для нечеткой системы управления

Другим подходом к формированию БП является нейросетевой. Он заключается в интегрировании ИНС в НСУ с последующим ее обучением. Данное интегрирование осуществляется заменой базы нечетких правил в НСУ нейронной сетью. Таким образом, число входов нейронной сети равно числу входных лингвистических переменных, число выходов сети равно единице. Принцип работы такой системы изображен на рисунке 3.2.1.

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

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

По окончанию обучения ИНС происходит извлечение БП из «черного ящика» сети и представление ее (БП) в понятном пользователю формате. В дальнейшем, управление системой осуществляется по БП, извлеченной из обученной ИНС, без участия самой ИНС.

3.3 Настройка семантики лингвистических переменных

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

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

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

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

3. термы должны покрывать весь интервал изменения переменной, т. е. между термами не должно существовать разрывов.

Данные проблемы можно обойти, если наложить на решение множество ограничений, но тогда вместо задачи безусловной оптимизации пришлось бы решать задачу условной оптимизации, что гораздо сложнее. Следовательно, необходимо разработать такой способ кодирования и декодирования термов, который позволил бы решить обозначенные выше проблемы. Первая проблема решается достаточно просто — для каждой лингвистической переменной составляется своя масштабная функция вида, в результате применения которой диапазоны изменения переменных становятся одинаковыми. Здесь, x — исходная координата вершины терма по оси абсцисс, k = d/D — коэффициент масштаба, d = (l₂-l₁) — ширина интервала изменения переменной до масштабирования, D = (l_M2-l _M1) — ширина интервала изменения переменной после масштабирования, l₁ и l₂ — левая и правая границы изменения переменной до масштабирования, l_M1 и l_M2 — левая и правая границы изменения переменной после масштабирования, f_M(x) — промасштабированная абсцисса вершины. При декодировании полученного решения используется обратная к масштабной функция:

где k_M = 1/k = D/d — коэффициент обратного масштаба и x_M = f_M (x).

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

Однако сразу возникает вопрос, а какая из точек (1) и (2), (3) и (4) должна находиться левее, т. е. (1)>(2) или (2)>(1), (3)>(4) или (4)>(3)? Конечно, если предварительно определить очередность их расположения, например, (1)>(2), (3)>(4), то можно будет избежать данной проблемы. Однако, убрав из рассмотрения остальные варианты расположения точек, мы искусственно сократим поисковое пространство, что не допустимо при оптимизации.

Для решения данной проблемы авторами был разработан алгоритм перевода массива точек в вершины термов. Для каждой пары таких точек ((1) и (2), (3) и (4), …; рис. 3.3.1), назовем их спорными, определяется одна приоритетная точка, к примеру, первая точка пары. Затем найденный массив точек термов сортируется в порядке возрастания их значений. Каждой паре спорных точек в сортированном массиве соответствует своя двойка значений. Первой спорной паре первого терма соответствуют первый и второй элементы сортированного массива, второй паре второго терма — (3) и (4) элементы массива и т. д. Когда возникает вопрос о том, какая из точек будет лежать левее, из двух значений массива приоритетной точке приравнивается то число, которое в исходной строке (не сортированной) встречается раньше. Таким образом, отпадает какая-либо необходимость ввода ограничений на решение или искусственного сокращения пространство поиска.

Рассмотрим этот алгоритм на примере. Пусть некоторая лингвистическая переменная описывается тремя термами и пусть в ходе оптимизации было получено решение в виде массива {1,2,0,7,5,4,8,6}. Для каждой пары спорных точек (1 и 2, 3 и 4, 5 и 6, …; рис. 3.3.1) назначаем приоритетной первую точку, т. е. для 1 и 2 приоритетной является точка 1, для 3 и 4 — это 3 и т. д. После сортировки массив точек примет вид {0,1,2,4,5,6,7,8}. Далее, решается вопрос о расположении точек. Так, точка (2) терма будет лежать левее точки (1), поскольку элемент приоритетной точки {1} в исходном массиве находится левее точки {0}, т. е. точка (2) = {0} терма будет лежать левее точки (1) = {1}. Схематически данная процедура отображена на рисунке 3.3.2.

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

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

3.4 Коэволюционный алгоритм для формирования НСУ в целом

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

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

Алгоритм состоит из следующих шагов:

1. Инициализация БП и термов случайными значениями;

2. Фиксация значений термов лингвистических переменных, и оптимизация по БП;

3. Фиксация БП, найденной на предыдущем этапе, и оптимизация термов;

4. Если пройдено заданное число этапов, то завершение (найденные на последних этапах оптимизации БП и термы являются решением), иначе возвращаемся на п. 2.

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

Глава 4. Практическая реализация разработанных подходов и исследование эффективности их работы

4.1 Программная реализация

Приведенные выше алгоритмы были реализованы в виде программной системы (ПС). Стартовое окно данной системы отображено на рисунке 4.1.1.

Рис. 4.1.1 Стартовое окно программной системы Для упрощения работы с программой главная форма разбита на 4 основных блока: «Инициализация», «Текущее состояние», «Управление» (включая кнопки) и «Испытательный полигон». Рассмотрим каждый из этих элементов.

В блоке «Инициализация» задаются начальные параметры системы.

В блоке «Текущее состояние» отображаются текущие значения параметров системы и вектор силы, прикладываемый к тележке для управления системой.

Блок «Испытательный полигон» предназначен для визуального отображения работы системы.

Блок «Управление» состоит из 2-х частей: флага ручного либо автоматического управления и кнопок управления.

· Нажатие кнопки «Запуск» запускает механизм расчета физических параметров системы.

· Нажатие кнопки «Пауза/Продолжить» временно останавливает (замораживает) движение системы с сохранением всех параметров / запускает «физику» системы.

· При нажатии кнопки «Стоп» происходит остановка работы системы без запоминания последних параметров.

· Кнопка «Выход» — выход из программы, при необходимости выдается запрос о сохранении изменений БП и термов.

· Нажатие кнопки «Настройки» вызывает форму, на которой находятся редактор терм, редактор БП и панель работы с алгоритмами автоматического формирования БП (см. рис. 4.1.2, 4.1.3, 4.1.4).

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

После запуска оптимизационного алгоритма открывается окно Diagram, отображающее ход работы программы (см. рис. 4.1.5).

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

Рис. 4.1.2 Форма панели настроек Рис. 4.1.3 Форма панели редактора термов Рис. 4.1.4 Форма панели редактора БП

Рис. 4.1.5 График работы оптимизационного алгоритма

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

4.2 Подбор оптимальной структуры оптимизационного алгоритма

Генетический подход. Структура ГА состояла из параметров двух видов: фиксированных и переменных. Фиксированными параметрами являлись размер турнира и элиты (для турнирной и элитарной селекций соответственно), которые были равны 5 и 6 индивидам, вероятность мутации — средняя. Переменными параметрами были вид селекции, тип рекомбинации, объем популяции, число поколений. Число вычислений целевой функции было ограничено 2000. Для сравнения брались статистически усредненные значения за 50 прогонов. Сравнение алгоритмов осуществлялось по нескольким критериям, среди которых найденный минимум, скорость сходимости алгоритма к наилучшему решению, период активного спуска алгоритма (в процентах). Данные экспериментов приведены в таблице А.1 в приложении. Наиболее эффективной среди всех структур оказалась следующая: Элитарная + равновероятная селекция + Двухточечная рекомбинация + 20 индивидов х 100 поколений.

Нейросетевой подход. Фиксированными параметрами являлись размер турнира и элиты (для турнирной и элитарной селекций соответственно), которые были равны 2 и 3 индивидам, вероятность мутации — средняя. Также фиксированной была структура нейронной сети, которая имела следующие параметры: один скрытый слой, четыре нейрона на скрытом слое, параметр активационной функции был равен 0,5. Переменными параметрами были вид селекции, тип рекомбинации, объем популяции, число поколений. Число вычислений целевой функции было ограничено 2000. Для сравнения брались статистически усредненные значения за 50 прогонов. Сравнение алгоритмов осуществлялось также по нескольким критериям. Данные экспериментов приведены в таблице А.2 в приложении. Наиболее эффективной среди всех структур оказалась следующая: Элитарная + пропорциональная селекция + Одноточечная рекомбинация + 10 индивидов х 200 поколений.

4.3 Сравнение эффективности подходов

Перед алгоритмами ставилась задача поиска наилучшего решения за 2000 вычислений целевой функции. Для каждого алгоритма использовалась оптимальная структура ГА. Для сравнения брались статистически усредненные значения за 50 прогонов. Сравнение осуществлялось по скорости сходимости алгоритмов к наилучшему решению. Графики работы оптимизационных алгоритмов (статистически усредненные по 50 прогонам) приведены на рисунках 4.3.1 и 4.3.2, соответственно, для нейросетевого и генетического подходов формирования БП и график коэволюционного алгоритма — на рисунке 4.3.3. На графиках отображен разброс решений (ось ординат) за каждые 20 вычислений целевой функции (ось абсцисс).