Алгоритм Мамдани в системах нечеткого вывода

Введение

Так уж повелось, что любую статью о нечеткой логике принято начинать с упоминания имени Лотфи Заде. И я не стану исключением. Дело в том, что этот человек стал не только отцом-основателем целой научной теории, написав в 1965 году фундаментальный труд "Fuzzy Sets", но и проработал различные возможности ее практического применения. Он описал свой подход в 1973 году в тексте "Outline of a New Approach to the Analysis of Complex Systems and Decision Processes" (опубликованном в журнале IEEE Transactions on Systems). Примечательно, что сразу после его выхода одна предприимчивая датская фирма весьма успешно применила изложенные в нем принципы для усовершенствования своей системы управления сложным производственным процессом.

Но при всех заслугах Л. Заде, не менее важный вклад внесли последователи этой теории. Например, английский математик Э. Мамдани (Ebrahim Mamdani). В 1975 году он разработал алгоритм, который был предложен в качестве метода для управления паровым двигателем. Предложенный им алгоритм, основанный на нечетком логическом выводе, позволил избежать чрезмерно большого объема вычислений и был по достоинству оценен специалистами. Этот алгоритм в настоящее время получил наибольшее практическое применение в задачах нечеткого моделирования.

Основные определения

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

Нечеткая переменная - это кортеж вида <α, X, Α>, где:

α - имя нечеткой переменной;

X - её область определения;

A - нечеткое множество на универсуме X.

Пример: Нечеткая переменная <"Тяжелый бронежилет", {x| 0 кг < x < 35 кг}, B={x, μ(x)}> характеризует массу военного бронежилета. Будем считать его тяжелым, если его масса > 16 кг (рис. 1).

Рис. 1. График функции принадлежности μ(x) для нечеткого множества B

Лингвистическая переменная есть кортеж <β, T, X, G, M>, где:

β - имя лингвистической переменной;

T - множество её значений (термов);

X - универсум нечетких переменных;

G - синтаксическая процедура образования новых термов;

M - семантическая процедура, формирующая нечеткие множества для каждого терма данной лингвистической переменной.

Пример: Допустим, мы имеем субъективную оценку массы бронежилета. Она, например, может быть получена от военнослужащих (выступающих в роли экспертов), которые непосредственно имеют дело с подобной амуницией. Формализовать эту оценку можно с помощью следующей лингвистической переменной <β, T, X, G, M> (рис. 2), где:

β - Бронежилет;

T - {"Легкий бронежилет (Light)", "Бронежилет средней массы (Medium)", "Тяжелый бронежилет (Heavy)"};

X = [0; 35];

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

M - процедура задания на универсуме X=[0; 35] значений лингвистической переменной, т.е. термов из множества T.

Рис. 2. Графики функций принадлежности значений лингвистической переменной "Бронежилет"

Нечетким высказыванием будем называть высказывание вида "β IS α", где:

β - лингвистическая переменная;

α - один из термов этой переменной.

Пример: "Бронежилет IS легкий". Здесь "Бронежилет" - это лингвистическая переменная, а "легкий" её значение.

Упрощенно говоря, правилом нечетких продукций (далее просто правилом) будем называть классическое правило вида "ЕСЛИ ... ТО ...", где в качестве условий и заключений будут использоваться нечеткие высказывания. Записываются такие правила в следующем виде:

IF (β₁ IS α₁) AND (β₂ IS α₂) THEN (β₃ IS α₃).

Кроме "AND" также используются логическая связка "OR". Но такой записи обычно стараются избежать, разделяя такие правила на несколько более простых (без "OR"). Также каждое из нечетких высказываний в условии любого правила будем называть подусловием. Аналогично, каждое из высказываний в заключении называется подзаключением.

Пример: Следующие примеры помогут зафиксировать определение:

1) IF (Бронежилет тяжелый) THEN (Солдат уставший);
2) IF (Муж трезвый) AND (Зарплата высокая) THEN (Жена довольная).

Все. Этого минимума достаточно для понимая принципов работы алгоритма.

Алгоритм Мамдани

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

Рис. 3. Диаграмма деятельности процесса нечеткого вывода

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

Для реализации алгоритма использовался объектно-ориентированный подход. Исходный код написан на языке программирования Java. Диаграмма (рис. 4) показывает наиболее существенные связи и отношения между классами, задействованными в алгоритме.

Рис. 4. Диаграмма классов реализации алгоритма Мамдани

Правила (Rule) состоят из условий (Condition) и заключений (Conclusion), которые в свою очередь являются нечеткими высказываниями (Statement). Нечеткое высказывание включает в себя лингвистическую переменную (Variable) и терм, который представлен нечетким множеством (FuzzySet). На нечетком множестве определена функция принадлежности, значение которой можно получить с помощью метода getValue(). Это метод определенный в интерфейсе FuzzySetIface. При выполнении алгоритма необходимо будет воспользоваться "активизированным" нечетким множеством (ActivatedFuzzySet), которое некоторым образом переопределяет функцию принадлежности нечеткого множества (FuzzySet). Также в алгоритме используется объединение нечетких множеств (UnionOfFuzzySets). Объединение также является нечетким множеством, и поэтому имеет функцию принадлежности (определенную в FuzzySetIface).

Алгоритм Мамдани (MamdaniAlgorithm), включает в себя все этапы (рис. 3) и использует базу правил (List<Rule>) в качестве входных данных. Также алгоритм предполагает использование "активизированных" нечетких множеств (ActivatedFuzzySet) и их объединений (UnionOfFuzzySets).

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

1. Формирование базы правил

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

База правил может иметь следующий вид (для примера используются правила различных конструкций):

RULE_1 : IF "Condition_1" THEN "Conclusion_1" (F₁) AND "Conclusion_2" (F₂);

RULE_2 : IF "Condition_2" AND "Condition_3" THEN "Conclusion_3" (F₃);

...

RULE_n : IF "Condition_k" THEN "Conclusion_(q-1)" (F_q-1) AND "Conclusion_q" (F_q);

Где F_i - весовые коэффициенты, означающие степень уверенности в истинности получаемого подзаключения (i = 1..q). По умолчанию весовой коэффициент принимается равным 1. Лингвистические переменные, присутствующие в условиях называются входными, а в заключениях выходными.

Обозначения:

n - число правил нечетких продукций (numberOfRules).

m - кол-во входных переменных (numberOfInputVariables).

s - кол-во выходных переменных (numberOfOutputVariables).

k - общее число подусловий в базе правил (numberOfConditions).

q - общее число подзаключений в базе правил (numberOfConclusions).

Примечание: Данные обозначения будут использоваться в последующих этапах. В скобках указаны имена соответствующих переменных в исходном коде.

2. Фаззификация входных переменных

Этот этап часто называют приведением к нечеткости. На вход поступают сформированная база правил и массив входных данных А = {a₁, ..., a_m}. В этом массиве содержатся значения всех входных переменных. Целью этого этапа является получение значений истинности для всех подусловий из базы правил. Это происходит так: для каждого из подусловий находится значение b_i = μ(a_i). Таким образом получается множество значений b_i (i = 1..k).

Реализация:

                    private double[]
                    fuzzification(double[] inputData) {
                    
                        int i = 0;
                    
                        double[]
                    b = new double[numberOfConditions];
                    
                        for (Rule rule : rules) {
                    
                            for
                    (Condition condition : rule.getConditions()) {
                    
                                int
                    j = condition.getVariable().getId();
                    
                                FuzzySet
                    term = condition.getTerm();
                    
                                b[i] =
                    term.getValue(inputData[j]);
                    
                                i++;
                    
                            }
                    
                        }
                    
                        return b;
                    
                    }

Примечание: Массив входных данных сформирован таким образом, что i-ый элемент массива соответствует i-ой входной переменной (номер переменной храниться в целочисленном поле "id").

3. Агрегирование подусловий

Как уже упоминалось выше, условие правила может быть составным, т.е. включать подусловия, связанные между собой при помощи логической операции "AND". Целью этого этапа является определение степени истинности условий для каждого правила системы нечеткого вывода. Упрощенно говоря, для каждого условия находим минимальное значение истинности всех его подусловий. Формально это выглядит так:

c_j = min{b_i}.

Где:

j = 1..n;

i - число из множества номеров подусловий в которых участвует j-ая входная переменная.

Реализация:

                    private double[] aggregation(double[] b) {
                    
                        int i = 0;
                    
                        int j = 0;
                    
                        double[] c =
                    new double[numberOfInputVariables];
                    
                        for (Rule rule : rules) {
                    
                            double
                    truthOfConditions = 1.0;
                    
                            for
                    (Condition condition : rule.getConditions()) {
                    
                                truthOfConditions =
                        Math.min(truthOfConditions, b[i]);
                    
                                i++;
                    
                            }
                    
                            c[j] = truthOfConditions;
                    
                            j++;
                    
                        }
                    
                        return c;
                    
                    }

4. Активизация подзаключений

На этом этапе происходит переход от условий к подзаключениям. Для каждого подзаключения находится степень истинности d_i = c_i*F_i, где i = 1..q. Затем, опять же каждому i-му подзаключению, сопоставляется множество D_i с новой функцией принадлежности. Её значение определяется как минимум из d_i и значения функции принадлежности терма из подзаключения. Этот метод называется min-активизацией, который формально записывается следующим образом:

μ^'_i(x) = min {d_i, μ_i(x)}.

Где:

μ^'_i(x) - "активизированная" функция принадлежности;

μ_i(x) - функция принадлежности терма;

d_i - степень истинности i-го подзаключения.

Итак, цель этого этапа - это получение совокупности "активизированных" нечетких множеств D_i для каждого из подзаключений в базе правил (i = 1..q).

Реализация:

                    private List<ActivatedFuzzySet>
                    activation(double[] c) {
                    
                        int i = 0;
                    
                        List<ActivatedFuzzySet>
                    activatedFuzzySets =
                    
                             new
                    ArrayList<ActivatedFuzzySet>();
                    
                        double[] d =
                    new double[numberOfConclusions];
                    
                        for (Rule rule : rules) {
                    
                            for
                    (Conclusion conclusion : rule.getConclusions()) {
                    
                              d[i] = c[i]*conclusion.getWeight();
                    
                              ActivatedFuzzySet
                    activatedFuzzySet =
                    
                                  (ActivatedFuzzySet) conclusion.getTerm();
                    
                              activatedFuzzySet.setTruthDegree(d[i]);
                    
                              activatedFuzzySets.add(activatedFuzzySet);
                    
                              i++;
                    
                            }
                    
                        }
                    
                        return activatedFuzzySets;
                    }

                    
                    private double
                        getActivatedValue(double x) {
                    
                        return
                    Math.min(super.getValue(x), truthDegree);
                    
                    }

5. Акумуляция заключений

Целью этого этапа является получение нечеткого множества (или их объединения) для каждой из выходных переменных. Выполняется он следующим образом: i-ой выходной переменной сопоставляется объединение множеств E_i = ∪ D_j. Где j - номера подзаключений в которых участвует i-aя выходная переменная (i = 1..s). Объединением двух нечетких множеств является третье нечеткое множество со следующей функцией принадлежности:

μ^'_i(x) = max {μ₁(x), μ₂(x)},

где μ₁(x), μ₂(x) - функции принадлежности объединяемых множеств.

Реализация:

                    private List <UnionOfFuzzySets>
                    accumulation(List<ActivatedFuzzySet> activatedFuzzySets) {
                    
                        List<UnionOfFuzzySets>
                    unionsOfFuzzySets =
                    
                            new
                    ArrayList<UnionOfFuzzySets>(numberOfOutputVariables);
                    
                        for (Rule rule : rules) {
                    
                            for
                    (Conclusion conclusion : rule.getConclusions()) {
                    
                                int
                    id = conclusion.getVariable().getId();
                    
                    unionsOfFuzzySets.get(id).addFuzzySet(activatedFuzzySets.get(id));
                    
                            }
                    
                        }
                    
                        return unionsOfFuzzySets;
                    
                    }

                    
                    private double
                    getMaxValue(double x) {
                    
                        double result = 0.0;
                    
                        for (FuzzySet fuzzySet : fuzzySets) {
                    
                            result =
                        Math.max(result, fuzzySet.getValue(x));
                    
                        }
                    
                        return result;
                    
                    }

6. Дефаззификация выходных переменных

Цель дефаззификациии получить количественное значение (crisp value) для каждой из выходных лингвистических переменных. Формально, это происходит следующим образом. Рассматривается i-ая выходная переменная и относящееся к ней множество E_i (i = 1..s). Затем при помощи метода дефаззификации находится итоговое количественное значение выходной переменной. В данной реализации алгоритма используется метод центра тяжести, в котором значение i-ой выходной переменной рассчитывается по формуле:

Где:

μ_i(x) - функция принадлежности соответствующего нечеткого множества E_i;

Min и Max - границы универсума нечетких переменных;

y_i - результат дефаззификации.

Реализация:

                    private double[]
                    defuzzification(List<UnionOfFuzzySets> unionsOfFuzzySets) {
                    
                        double[] y =
                    new double[numberOfOutputVariables];
                    
                        for(int
                    i = 0; i < numberOfOutputVariables; i++) {
                    
                            double
                        i1 = integral(unionsOfFuzzySets.get(i),
                        true);
                    
                            double
                        i2 = integral(unionsOfFuzzySets.get(i),
                        false);
                    
                            y[i] = i1 / i2;
                    
                        }
                    
                        return y;
                    
}

Заключение

Алгоритм Мамдани и многие другие алгоритмы нечеткого вывода уже реализованы в таких замечательных продуктах как Fuzzy Logic Toolbox (расширение для MatLab), fuzzyTECH и многих других. Поэтому столь детальное рассмотрение алгоритма, как в данной статье, носит больше теоретическую ценность, чем практическую. Однако замечу, что только имея под собой прочный фундамент из знаний и понимания основ работы алгоритма появляется возможность применять его с максимальным эффектом.

Литература

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

1. Леоненков А.В. Нечеткое моделирование в среде MATLAB и fuzzyTECH / А. Леоненков. – СПб: БХВ-Петербург, 2003. – 736 с.

2. Штовба С.Д. Проектирование нечетких систем средствами MATLAB / С. Штовба. – М: Горячая линия–Телеком, 2007. – 288 с.