УДК 004.81

Способ структурно-параметрической настройки нечетких когнитивных карт на основе генетических алгоритмов

Орлов Артем Игоревич – магистрант филиала Национального исследовательского университета «МЭИ» в г. Смоленске.

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

Ключевые слова: нечеткие когнитивные карты, настройка когнитивных карт, обучение когнитивных карт, генетические алгоритмы.

Введение

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

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

В традиционных знаковых когнитивных картах дуги могут быть помечены знаками «+» (положительное влияние) и знаком «–» (отрицательное влияние). Такие карты впервые были предложены Р. Аксерольдом [1], Однако из-за бинарности отношений знаковые когнитивные карты позволяют исследовать характер протекающих процессов в системе лишь качественно и не дают точной количественной оценки силы влияния между концептами. Это ограничивает возможности анализа и моделирования систем, в которых присутствует неточность или неопределенность отношений. Для решения этой проблемы исследователями были предложены различные разновидности нечетких когнитивных карт.

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

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

Основные разновидности нечетких когнитивных карт и способы их настройки

В нечетких когнитивных картах Б. Коско [2] и В. Силова [3] состояния концептов могут изменяться в диапазоне от 0 до 1, а связи между концептами, показывающие степень влияния одного концепта на другой, принимают значения в диапазоне от –1 до 1. Основное различие этих разновидностей когнитивных карт заключаются в том, что в картах Коско используются динамические модели, основанные на сумме, а в картах Силова – на операциях T-нормы и S-нормы.

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

Перечисленные различия могут оказаться несущественными, если для когнитивной карты необходимо подобрать только значения весов связей. В таком случае когнитивную карту можно настроить, используя метод обучения с учителем. Такой подход представлен в работе [4]. В ней авторы обучают нечеткую когнитивную карту Коско, предназначенную для стратегического управления бизнесом. В качестве обучающей выборки используются значения концептов, полученные в результате наблюдения или эксперимента. Начальные веса задаются маленькими случайными значениями, а для изменения значений весов используется метод градиентного спуска.

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

Основная проблема при применении алгоритма Хэбба заключается в том, что при изменении веса связи между двумя концептами K_i и K_j учитываются только эти два концепта, а остальные игнорируются. Для аккумулирования влияния остальных концептов в работе [6] была предложена модификация этого алгоритма, получившая название балансового дифференциального алгоритма обучения Хэбба.

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

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

Параметрическая настройка начального состояния концептов в нечетких когнитивных картах Силова может быть решена с использованием теоретических методов решения нечетких уравнений и подробно описана в [3]. Для настройки матрицы весов связей могут также использоваться генетические алгоритмы. Такой подход исследовался в работе [10].

Еще одной разновидностью нечетких когнитивных карт являются «совместимые» нечеткие когнитивные карты [11], которые возникли из-за необходимости учитывать совместимость концептов при определении влияния между ними. Кроме концептов и связей в такой карте определена степень совместимости между парами концептов. Для получения динамической модели «совместимой» нечеткой когнитивной карты используется семейство параметризированных функций med, удовлетворяющих аксиомам нормировки, неубывания, непрерывности и бисимметричности [12].

Параметрическая настройка начального состояния концептов «совместимой» нечеткой когнитивной карты может выполняться с использованием разработанных в [12] правил определения значений аргументов p'_k и p'_l параметризированных операций типа p_об = med(p_k, p_l, c_ij) по значению p’_об.

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

Способ структурно-параметрическая настройка нечетких когнитивных карт на основе генетических алгоритмов

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

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

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

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

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

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

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

Таблица 1. Примеры ограничений концептов для различных типов нечетких когнитивных карт.

Среди связей нечеткой когнитивной карты также выделяют управляющие. Значение силы этих связей не известно исследователю заранее, а может изменяться в процессе настройки в рамках определенных ограничений. Изменение силы управляющей связи приводит к изменению конечного состояния целевых концептов в результате моделирования. Для нечетких когнитивных карт Коско и Силова ограничение связи задается в виде отрезка или интервала в области определения силы связей от –1 до 1. Ограничение для обобщенных нечетких продукционных карт может быть представлено в виде отрезка, интервала или множества значений из базового множества связи. Для нечетких реляционных когнитивных карт ограничение выражается в виде матрицы отрезков или интервалов, определяя тем самым границы, в рамках которых может изменяться нечеткое отношение. Для «совместимых» нечетких когнитивных карт ограничение описывается в виде двуместного кортежа отрезков или интервалов, в котором первый элемент определен в границах от –1 до 1 и выражает ограничение, накладываемое на силу связи, а второй – в границах от 0 до 1 и задает ограничение, накладываемое на степень совместимости концептов. Примеры ограничений связей для различных типов нечетких когнитивных карт представлены в таблице 2.

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

Если разновидность нечеткой когнитивной карты позволяет использовать несколько динамических моделей, то для любого концепта может быть выбрана любая из них. Так, например, для концепта нечеткой когнитивной карты Коско может быть выбраны любая из моделей: (1), (2), (3), (4). Установка динамической модели для отдельных концептов не является обязательной, поскольку ко всем концептам карты может применяться единая динамическая модель, устанавливаемая при запуске структурно-параметрической настройки.

После выбора управляющих концептов и их ограничений, целевых концептов и их значений, динамических моделей для каждого концепта, а также управляющих связей и их ограничений запускается генетический алгоритм структурно-параметрической настройки, в котором особь выражается в виде состояния управляющих концептов и весов управляющих связей. Вид такой особи представлен на рисунке 1, где K = K₁, K₂,…, K_n – хромосома состояний управляющих концептов; n – число управляющих концептов; C = C₁, C₂,…, C_m – хромосома весов управляющих связей; m – число управляющих связей.

Рисунок 1. Вид особи.

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

В качестве метода скрещивания используется скрещивание смешением, в котором каждый потомок случайным образом выбирается из следующего отрезка, созданного родителями p₁ и p₂:

[p₁– α(p₂– p₁); p₂+ α(p₂– p₁)],           (1)

где α – константа от 0 до 1.

Значение родителя p₂ должно быть больше значения родителя p₁. Если это не так, то родители меняются местами. Константа α определяет ширину отрезка. При значении α =0,5 отрезок получается в два раза шире, чем между родителями, поэтому такое значение является наиболее целесообразным. Однако полученный таким методом отрезок может выходить за пределы диапазона, установленного ограничением или областью определения значений концепта или силы связи, поэтому его необходимо соответствующим образом скорректировать.

Мутация хромосомы осуществляется с помощью замены одного из ее генов на новый. Получение нового случайного значения гена осуществляется аналогично получению отдельного значения при генерации хромосомы. Выполнять мутацию необходимо с некоторой вероятностью. Пусть вероятность одновременной мутации обеих хромосом K и C особи равняется 0,45, а вероятность мутации только одной из хромосом равняется 0,5, тогда в одной половине случаев вероятности мутаций хромосом K и C равны 0,9 и 0,5 соответственно, а в другой половине случаев эти вероятности равны 0,5 и 0,9.

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

В результате моделирования ошибка особи вычисляется по следующей формуле:

,           (2)

где y_i(t) – значение целевого концепта i в момент времени t; y_i – искомое целевое значение концепта i; t_l – минимальное время, в котором осуществляется поиск решения; t_r – максимальное время, в котором осуществляется поиск решения; a – число целевых концептов.

Целевое значение концепта задается в виде диапазона, поэтому значение y_i может быть получено по следующей формуле, если диапазон является отрезком:

,           (3)

где y_i^d – целевой отрезок.

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

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

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

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

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

Заключение

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

Список литературы

1. Аксельрод Р. Структура решения: когнитивные карты политических элит. Принстонский университет, пресса, Нью-Йорк: 1976.
2. Коско Б. Нечеткие когнитивные карты // Межд. Журнал человеко-машинных исследований. 1986. Т. 24. С. 65–75.
3. Силов В. Б. Принятие стратегических решений в нечеткой обстановке. М.: ИНПРО–РЕС, 1995.
4. Карлссон К., Фуллер Р. Адаптивные нечеткие когнитивные карты для представления гиперзнаний в процессе формирования стратегии // В кн. Международной панельной конференции по мягким и интеллектуальным вычислениям, Будапештский технический университет, 1996. С. 43–50.
5. Коско Б. Дифференциальное обучение Хэбба // Материалы конференции AIP. Т. 151. 1986. С. 265–270.
6. Хуэрга А. Сбалансированный дифференциальный алгоритм обучения в нечетких когнитивных картах // В сборнике тезисов Шестнадцатой Международной конференции по качественному рассуждению, QR’2002, Испания, 2002. С. 210–214.
7. Кулуриотис Д.Е., Диакулакис И.Е., Эмирис Д.М., Антонидакис Е.Н., Калиакатсос И.А. Эффективное моделирование и управление сложными динамическими системами с использованием эволюционных нечетких когнитивных карт (Приглашенная статья) // Междунар. журн. вычисл. когнитивики 1 (2) (2003) 41–65
8. Стач В., Курган Л., Педрич В., Реформат М. Генетическое обучение нечетких когнитивных карт // Нечеткие множества и системы 153 (2005) С. 371–401.
9. М.С. Хан, А. Чонг, Анализ нечетких когнитивных карт с использованием генетического алгоритма // Труды 1-ой Индийской международной конф. по искусственному интеллекту (IICAI-03), 2003
10. Аверкин А. Н., Паринов А. А. Генетический алгоритм обучения нечетких когнитивных карт // Научные труды Вольного экономического общества России. 2010. №.
11. Борисов В. В., Федулов А. С. «Совместимые» нечеткие когнитивные модели // Сборник трудов Пятнадцатой национальной конференции по искусственному интеллекту с международным участием КИИ-2016. Смоленск, 3–7 октября 2016 г. В 3-х томах. Т.2. С. 244–249.
12. Борисов В. В., Федулов Я. А. Нечеткая модель оценки сложных организационно-технических систем // Естественные и технические науки. 2014. №5. С. 134–145.
13. Борисов В. В., Федулов А. С., Мнев В. И. Моделирование сложных нечетко-целевых систем на основе обобщенных нечетких когнитивных карт // Информ. бюл. Акад. воен. наук. Смоленск: Изд-во ВУ ВПВО ВС РФ, 2001. С. 22–25.
14. Федулов А. С. Нечеткие реляционные когнитивные карты // Изв. РАН. Теория и системы управления. 2005. № 1. С. 120–133.