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

Рис. 1. Когнитивная карта

Нечеткие когнитивные карты (Fuzzy cognitive maps, FCM), предложенные Кошко, являются обобщением когнитивных карт. В нечетких когнитивных картах каждой вершине, обозначающей фактор, присваивается нечеткая переменная с_i [0,1], характеризующая активность данного фактора. Связи между i-м фактором-причиной и j-м фактором-следствием, присваивается нечеткое значение w_ij [-1,1] [Kosko, 1993]. Нечеткую когнитивную карту можно представить в виде матрицы смежности W={w_ij}. Нечеткие когнитивные карты используются для получения прогноза развития системы и для получения стратегии, которую необходимо использовать для того, чтобы достичь желаемый результат. Задача поиска прогноза состоит в определении вектора состояний С_i (t) при t=1…n.

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

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

1. Нейронный

2. Подход на основе нечетких реляционных уравнений

Нейронный подход к моделированию когнитивной карты позволяет использовать нейронный [Carlsson et al., 1996] и генетический алгоритм обучений [Stach et al., 2005]. Российскими учеными развивается направление моделирования когнитивных карт на основе нечетких реляционных уравнений [Силов, 1995]. Для обучения моделей когнитивных карт на основе нечетких реляционных уравнений можно использовать генетический алгоритм [Аверкин и др., 2010].

Важную роль играет возможность ускорения работы генетического алгоритма с использованием компьютеров с многоядерными процессорами. Для сетей на основе нейронной модели (модели Кошко) был разработан параллельный алгоритм обучения [Stach et al., 2010]. Для модели когнитивной карты на основе нечетких реляционных уравнений нами разработан оригинальный параллельный алгоритм обучения. Рассмотрим подробнее последовательную и параллельную реализацию генетического алгоритма.

При реализации подхода основанного на нечетких уравнениях логический вывод обобщается с использованием t-норм и s-норм [Кулинич, 2003]. Используя t-нормы и s-нормы формула определения значения активности нейронов записывается в виде:

С_i (t+1) =S [T (С_j (t), w_ji)], (1)

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

, (2)

где - макстриангулярная композиция, которая в частном случае представляется в виде:

. (3)

Для реализации алгоритма обучения когнитивной карты на основе нечетких уравнений необходимо наличие набора из 3-х строк, характеризующих значения величин активности факторов в t, t+1, t+2 моменты времени соответственно.

Приращение значений факторов от i-й итерации к (i+1) итерации составляет исходный вектор приращений X. В этом случае значения, рассчитанные по формуле (2) должны совпадать с историческими значениями приращений на (i + 2) итерации. Пусть A_i (t) - значение активности i-го фактора в момент времени t. Тогда A (t), A_i (t+1), A_i (t+2) - значение активности i-го фактора в t, t+1, t+2 моменты времени соответственно.

Исходный вектор приращений задается формулой:

,

результирующий вектор приращений:

.

Пусть o_i (t) - приращение i-го фактора, полученное в результате прогноза на исходном векторе x (t). Тогда задача обучения состоит в минимизации ошибки, определяемой по формуле

, (4)

с учетом введенных значений x, y, o.

2. Параллельная реализация генетического алгоритма

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

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

2. Определяется функция приспособленности (fitness function) для каждой хромосомы. Функция приспособленности является обратной к функции характеризующей ошибку сети, определяемой по формуле (4)

3. Определяется пул родителей по методу "рулетки".

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

5. Происходит скрещивание хромосом, попавших в пул родителей. Скрещивание хромосом A и B происходит следующим образом. Случайным образом определяется граница скрещивания l. Обозначим A_l+ часть хромосомы A, состоящую из генов, расположенных начиная с l, и A_{l -} часть хромосомы, расположенную до l. Тогда результатом скрещивания будут две хромосомы A_l-B_l+ и B_l-A_l+. Вероятность скрещивания определена заранее. Если скрещивания не происходит, обе родительские хромосомы без изменений переходят в популяцию потомков.

6. Из потомков, полученных на шаге 6, формируется новая популяция (размер ее в точности совпадает с размером популяции на предыдущем шаге алгоритма).

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

8. Определяются следующие параметры поколения: элитная особь; значение приспособленности элитной особи; среднее значение приспособленности популяции.

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

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

Параллельный алгоритм реализован на языке Microsoft C#.net 4.0. Были проведены вычислительные эксперименты на компьютере с установленным многоядерным процессором.

3. Результаты эксперимента

В качестве исходных данных для проведения экспериментов использовались параметры модели прогнозирования макроэкономических показателей экономики РФ [Аверкин и др., 2010]. Результаты проведения экспериментов на компьютере с установленным процессором Core i7 (8 ядер) приведены в Таблице 1.:

Таблица 1

когнитивная карта нечеткая эксперт

Рис.2. График ускорения для карт с различным количеством вершин

Из данных таблицы 1 видно, что ускорение, достигаемое при запуске алгоритма на восьми ядерном процессоре, в 7 раз больше при вычислениях модели с 500-ми вершинами и в 5 раз больше при вычислениях, производимых на модели с 3000-ми вершинами. Снижение ускорения при росте количества вершин объясняется увеличением затрат ресурсов компьютера на организацию нитей в многопоточной программе при увеличении количества вершин.

Заключение