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

Введение


Так уж повелось, что любую статью о нечеткой логике принято начинать с упоминания имени Лотфи Заде. И я не стану исключением. Дело в том, что этот человек стал не только отцом-основателем целой научной теории, написав в 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 (β1 IS α1) AND (β2 IS α2) THEN (β3 IS α3).

Кроме «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» (F1) AND «Conclusion_2» (F2);
RULE_2: IF «Condition_2» AND «Condition_3» THEN «Conclusion_3» (F3);

RULE_n: IF «Condition_k» THEN «Conclusion_(q-1)» (Fq-1) AND «Conclusion_q» (Fq);

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

Обозначения:
n — число правил нечетких продукций (numberOfRules).
m — кол-во входных переменных (numberOfInputVariables).
s — кол-во выходных переменных (numberOfOutputVariables).
k — общее число подусловий в базе правил (numberOfConditions).
q — общее число подзаключений в базе правил (numberOfConclusions).

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

2. Фаззификация входных переменных
Этот этап часто называют приведением к нечеткости. На вход поступают сформированная база правил и массив входных данных А = {a1, ..., am}. В этом массиве содержатся значения всех входных переменных. Целью этого этапа является получение значений истинности для всех подусловий из базы правил. Это происходит так: для каждого из подусловий находится значение bi = μ(ai). Таким образом получается множество значений bi (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». Целью этого этапа является определение степени истинности условий для каждого правила системы нечеткого вывода. Упрощенно говоря, для каждого условия находим минимальное значение истинности всех его подусловий. Формально это выглядит так:

cj = min{bi}.

Где:
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. Активизация подзаключений
На этом этапе происходит переход от условий к подзаключениям. Для каждого подзаключения находится степень истинности di = ci*Fi, где i = 1..q. Затем, опять же каждому i-му подзаключению, сопоставляется множество Di с новой функцией принадлежности. Её значение определяется как минимум из di и значения функции принадлежности терма из подзаключения. Этот метод называется min-активизацией, который формально записывается следующим образом:

μ'i(x) = min {di, μi(x)}.

Где:
μ'i(x) — «активизированная» функция принадлежности;
μi(x) — функция принадлежности терма;
di — степень истинности i-го подзаключения.

Итак, цель этого этапа — это получение совокупности «активизированных» нечетких множеств Di для каждого из подзаключений в базе правил (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-ой выходной переменной сопоставляется объединение множеств Ei = ∪ Dj. Где j — номера подзаключений в которых участвует i-aя выходная переменная (i = 1..s). Объединением двух нечетких множеств является третье нечеткое множество со следующей функцией принадлежности:

μ'i(x) = max {μ1(x), μ2(x)}, где μ1(x), μ2(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-ая выходная переменная и относящееся к ней множество Ei (i = 1..s). Затем при помощи метода дефаззификации находится итоговое количественное значение выходной переменной. В данной реализации алгоритма используется метод центра тяжести, в котором значение i-ой выходной переменной рассчитывается по формуле:


Где:
μi(x) — функция принадлежности соответствующего нечеткого множества Ei;
Min и Max — границы универсума нечетких переменных;
yi — результат дефаззификации.

Реализация:
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 с.
Поделиться публикацией

Комментарии 15

    +1
    Неплохо, но я думаю можно проще всё объяснить. У многих людей, когда видят дифуры в тексте, резко уменьшается тяга читать. И когда еще делаешь саму простую програмульку — всё так красиво выходит…
      +4
      А вот я против «простых» объяснений, потому как они «на пальцах», а когда объяснение «на пальцах» пытаешься применять, вылазит очень много подводных камней.

      И да, в тексте нету ни одного дифура.
        +3
        Иногда для дальнейшего углубления в тему требуются простые аналогии из смежной или житейской области.

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

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

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

        Угадайте, чей материал был усвоен лучше.
          0
          Видимо, все зависит от цели, которой руководствуешься при написании текста. Обычно, статьи бывают двух видов: учебник или справочник. По одной лучше учиться, а в другую полезно заглядывать.
            0
            Я бы уточнил есть советского типа учебники где в большинстве пресекалась всякая «ересь» и есть учебники хороших авторов в основном западных где автор пытается написать понятно и легко ввести в курс ориентируясь на неподготовленую аудиторию. Я обработку сигналов выучил уже после ВУЗа по видео лекциям MIT OpenCourse Ware и там примеров с реальными применениями очень много и значительно понятнее чем та лабуда которую оторвано от жизни пытались втиснуть в ВУЗе.
            Конечно есть по некоторым дисцыплинам и хорошие учебники наших авторов, но к сожалению их слишком мало.
        +2
        Какие еще дифуры? :) Два интеграла, вычисляемые на раз-два, любой студент, нюхнувший лабу-другую по численным и пару лекций по теории множеств, разберется при желании :)
          0
          Студент определенно, а когда лет 10 с подобным не сталкивался, уже если честно и не помнишь что это такое вообще.
        0
        Давно работаю с нечёткой логикой, а не знал, что этот алгоритм — Мамдани =) Вот надо же. Спасибо.
          +2
          А где применяете? Было бы интересно услышать свой пример «из народа» :)
            0
            Все просто. Процесс нечеткого вывода (рис. 3) описывается очень расплывчато. А алгоритмы уже формально описывают этот процесс и специфицируют его. Поэтому они так друг на друга похожи.
            0
            Спасибо, очень интересная статья! Навело на мысль, где этот алгоритм использовать в игровой логике.

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

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

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

                Самое читаемое