НАУКА и ОБРАЗОВАНИЕ

УДК 519.6

Россия, МГТУ им. Н.Э. Баумана

walentina.belous@gmail.com

aadobrjkov@mail.ru

apkarpenko@mail.ru

galiam@bmstu.ru

Введение

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

1) Оценка «мыслительной грамотности» учащегося требует оценки пяти следующих составляющих этой грамотности (ключевых компетенций):

-             знаниевая грамотность (способность воспринимать, понимать и самостоятельно приобретать знания),

-             функциональная грамотность (способность «грамотно» применять знания),

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

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

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

2) Качество изложения предмета изучения определяют следующие критерии:

-     антропоцентричность (опора на личностно ориентированный подход «от человека к изучаемой проблеме»),

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

-     визуализированность (оптимальное сочетание вербальной 75 % и визуальной 25 % информации),

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

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

В соответствии с терминологией, принятой в теории многокритериального принятия решений [2], называем рассмотренные и иные показатели качества частными критериями оптимальности, а их совокупность – векторным критерием оптимальности.

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

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

Оценку значений различных частных критериев оптимальности производят, вообще говоря, разные лица, принимающие решения (ЛПР). Полагаем, что интегральную оценку на основе этих значений формирует главное лицо, принимающее решения (ГЛПР). Если способ свертки частных критериев фиксирован, то задача формирования этой оценки сводится к определению весов частных критериев оптимальности. Можно сказать, что значения этих весов формализуют функцию предпочтений ГЛПР [3].

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

В конечном счете, апостериорный метод формирования значений весовых коэффициентов приводит к задаче глобальной условной многомерной оптимизации. Для решения этой задачи может быть использовано большое число детерминированных и стохастических алгоритмов [4]. Хорошо известно, что в случае отсутствия априорной информации о ландшафте целевой функции, наиболее эффективны стохастические алгоритмы глобальной оптимизации. Из числа этих алгоритмов наибольшую известность получили популяционные (метаэвристические) алгоритмы такие, как генетический алгоритм, алгоритм роя частиц, алгоритм колонии муравьев и т.д. [5]. Новизна данной работы заключается, в частности, в использовании для решения указанной задачи глобальной оптимизации перспективного алгоритма эволюции разума (Mind Evolutionary Computation, MEC) [6].

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

Известен, так называемый, простой алгоритм MEC и несколько его модификаций – расширенный MEC [7], улучшенный MEC [6] и хаотичный MEC [8]. Мы предполагаем широкое исследование всех указанных и иных модификаций алгоритма MEC. В данной работе используем первый из указанных алгоритмов ‑ простой алгоритм эволюции разума (Simple MEC, SMEC).

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

1. Постановка задачи.

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

Совокупность рассматриваемых субъектов или объектов обозначаем , а их число ‑ . Из множества  по некоторому правилу выделяем обучающую и тестовую выборки , числа элементов в которых равны  соответственно; .

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

Формальной оценкой элемента  называем величину , . Набор формальных оценок всех элементов множества  обозначаем .

Полагаем, что для каждого из элементов ,  известна также назначенная ГЛПР интегральная экспертная оценка , определенная на целочисленной шкале , где ,  ‑ нижняя и верхняя оценки соответственно. Оценки  считаем нечеткими, имеющими функции принадлежности , так что величины  представляют собой ядра нечеткой переменной  [9].

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

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

,  

приведенной экспертной оценкой элемента . Набор этих оценок для всех элементов множества  обозначаем .

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

.

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

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

,                                           (1)

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

.

Здесь , - заданные константы (не обязательно положительные).

2. Метод решения задачи

            Общая схема метода интегральной оценки многокритериальных альтернатив имеет следующий вид.

1) Случайным образом выделяем из множества  обучающую  и тестовую  выборки таким образом, что  и .

2) На обучающей выборке решаем задачу (1) – определяем компоненты вектора  и соответствующее значение меры .

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

4) Если условие завершения итераций

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

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

Мультипопуляция алгоритм MEC состоит из лидирующих групп (superior groups)  и отстающих групп (temporary groups)  числом  и  соответственно. В оригинальном алгоритме MEC числа индивидов в каждой из групп полагают одинаковыми и равными .

          Каждая из групп ,  имеет свою коммуникационную среду, которая названа авторами алгоритма локальной доской объявлений (localbillboard). Обозначим эти доски ,  соответственно. Кроме того, вся мультипопуляция  имеет общую, глобальную доску объявлений (globalbillboard) .

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

Алгоритм SMEC построен на основе операций инициализации групп, локальных состязаний (similar-taxis) и диссимиляции (dissimilation). Поочередно рассмотрим эти операции.

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

1) Генерируем случайный вектор , компоненты которого равномерно распределены в области поиска П. Отождествляем этот вектор с индивидом  группы .

2) Определяем начальные координаты остальных индивидов данной группы ,  по формуле

,                                         (2)

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

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

1) С доски объявлений  берем информацию о текущем индивиде-победителе группы . Пусть это будет индивид , .

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

          3) Вычисляем новые счета (scores)индивидов группы , , где  - значение функции  в точке с координатами .

          4) Определяем нового победителя группы , , т.е. индивида данной группы, который имеет максимальный текущий счет:

,   .

          5) Заносим информацию о новом победителе группы  на доски объявлений , .

Операция диссимиляции управляет глобальным поиском. Схема операции имеет следующий вид.

          1) С глобальной доски объявлений  считываем счета , , , всех групп (т.е. текущие счета победителей этих групп).

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

          3) С помощью операции инициализации взамен каждой из удаленных групп инициализируем новую группу.

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

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

3. Программная реализация метода

_{Реализация метода выполнена на языке программирования Pythonс использованием библиотек matplotlob, numpy, scipy, os.Соответствующая программа получила наименование MEC-Python. Язык программирования Pythonявляется высокоуровневым интерпретируемым языком программирования, включающим, широкий спектр функций, интегрированную среду разработки и объектно-ориентированные возможности.}

          Основные входными данные программы MEC-Pythonразбиты на три группы, условно названные данные задачи, данные метода, данные алгоритма.

          К входным данным задачи отнесены

          ‑ число частных критериев оптимальности ,

          ‑ тип используемой скалярной свертки (выбирается пользователем из библиотеки сверток),

          ‑ число элементов  во множестве , а также числа элементов  в обучающей и тестовой выборках,

          ‑ шкалы  (используются только с целью проверки корректности исходных данных программы),

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

‑ функции принадлежности  (выбирается пользователем из библиотеки этих функций),

‑ мера близости  формальной и приведенной экспертной оценок (выбирается пользователем из соответствующей библиотеки),

‑ мера близости  наборов формальных и экспертных оценок (выбирается пользователем из библиотеки этих мер),

‑ константы , , , определяющие параллелепипед П допустимых значений компонентов вектора .

          В библиотеке скалярных сверток содержится аддитивная свертка

,                                      (3)

мультипликативная свертка

и свертка Гермейера

.

          Библиотека функций принадлежности включает в себя функции классов  [10].

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

.                                                   (4)

Библиотека мер близости наборов формальных и экспертных оценок содержит гарантирующую меру

,                                                (5)

срединную меру

и евклидову меру

.

          Входные данные метода включают в себя

‑ меру  (выбирается пользователем из библиотеки этих мер),

‑  константу ,

‑ максимально допустимое число итераций .

Библиотека мер включает в себя меру

.                                             (6)

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

          Входные данные алгоритма представляют собой свободные параметры алгоритма SMEC:

          ‑ число групп ;

‑ число индивидов в группе ;

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

          ‑ максимально допустимое число итераций алгоритма ;

          ‑ критерий стагнации алгоритма ;

          ‑ константа стагнации ;

          ‑ число мультистартов .

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

4. Исследование эффективности алгоритма MEC

Исследование выполнено для одноэкстремальной, но овражной функции Розенброка (Rozenbrock)

,

минимальное значение  которой достигается в точке с координатами  и равно нулю, а также для многоэкстремальной функции функция Растригина (Rastrigin)

,

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

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

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

          ‑ размерность задачи  (варианты ),

          ‑ число групп =10; 20; 30.

          ‑ число индивидов в группе =10; 20; 30,

          ‑ когнитивный параметр =0,7; 0,8; 0,9.

Во всех случаях использовано значение константы стагнации .

Сводные результаты исследования для функции Розенброка представлены в таблице 1.

Таблица 1 – Результаты исследования эффективности алгоритма MEC: функция Розенброка

Характер сходимости итераций при поиске минимума функции Розенброка иллюстрируют рисунки 1 ‑ 3. Здесь и далее нижняя кривая соответствует , следующая кривая ‑ , третья снизу кривая ‑ , последняя кривая ‑ . Величина  представляет собой номер итерации.

Рисунок 1 – Сходимость алгоритма: функция Розенброка; =;

Рисунок 2 – Сходимость алгоритма: функция Розенброка; =;

Рисунок 3 – Сходимость алгоритма: функция Розенброка; =;

Сводные результаты для функции Растригина представлены в таблице 2, которую иллюстрируют рисунки 4 – 6. Здесь  - номер итерации.

Таблица 1 – Результаты исследования эффективности алгоритма MEC: функция Растригина

Рисунок 4 – Сходимость алгоритма: функция Растригина; =;

Рисунок 5 – Сходимость алгоритма: функция Растригина; =;

Рисунок 6 – Сходимость алгоритма: функция Растригина; =;

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

5. Вычислительный эксперимент

С использованием программы MEC-Pythonвыполнено два вычислительных эксперимента. Во всех случаях использованы следующие значения основных входных данных.

Входные данные задачи:

          ‑ скалярная аддитивная свертка (3);

          ‑ пятибалльные шкалы ;

‑ гауссовы функции принадлежности с ядрами  и средним квадратичным отклонением 0,2821;

‑ мера близости  формальной и приведенной экспертной оценок (4);

‑ мера близости  наборов формальных и экспертных оценок (5),

‑ константы , ; .

Входные данные метода:

‑ мера (6);

‑  константа ;

‑ максимально допустимое число итераций .

Входные данные алгоритма:

          ‑ число групп ;

‑ число индивидов в группе ;

          ‑ среднее квадратичное отклонение ;

          ‑ максимально допустимое число итераций алгоритма ;

          ‑ критерий стагнации алгоритма ;

          ‑ константа стагнации ;

          ‑ число мультистартов ;

          ‑ когнитивный параметр .

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

‑ генерируем для данного элемента ,  случайную экспертную оценку , равномерно распределенную на дискретном множестве ;

‑ генерируем случайные величины ,распределенные по нормальному закону с математическим ожиданием, равным , и средним квадратичным отклонением, равным 1,22;

‑ величины  получаем путем округления по математическим правилам величин .

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

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

Таблица 3 – Исходные и результирующие оценки: эксперимент 1

Таблица 4 – Оптимальные значения весовых множителей: эксперимент 1

Рисунок 7 – Гистограмма невязок : эксперимент 1

Эксперимент 2 выполнен в рамках апробации ментально-структурированной образовательной технологии [1, 11]. В эксперименте использованы количественные показатели качества образовательного процесса в ВУЗе, полученные, в частности, с помощью системы автоматизированного анализа структурированных электронных документов [12]. Точнее говоря, использованы следующие показатели качества расчетно-пояснительной записки (РПЗ) к курсовой работе по дисциплине «Технология программирования» тринадцати студентов одной из учебных групп второго курса МГТУ им. Н.Э. Баумана:  ‑ новизна,  ‑ трудоемкость,  ‑ сложность,  ‑ системность,  ‑ структурированность.

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

Итого, в эксперименте 2 мощности множеств  приняты равными  соответственно, число частных критериев оптимальности . Наборы исходных формальных и соответствующих интегральных экспертных оценок представлены в таблице 5. Те же нормализованные данные приведены в таблице 6.

Таблица 5 ‑ Исходные оценки: эксперимент 2

Таблица 6 – Нормализованные входные данные: эксперимент 2

          Результаты работы программы представлены в таблицах 7, 8. Таблицу 7 иллюстрирует рисунок 8, аналогичный рисунку 7.

Таблица 7– Исходные и результирующие оценки: эксперимент 2

Таблица 8 – Оптимальные значения весовых множителей: эксперимент 2

Рисунок 8 – Гистограмма невязок : эксперимент 2

Заключение

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

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

Работа выполнена в рамках Государственного контракта № 16.740.11.0407 от 26 ноября 2010 г.

Литература

1.              Добряков А.А., Карпенко А.М., Смирнова Е.В. Основные принципы ментально-структурированной образовательной технологии, ориентированные на формирование компетентности специалиста технического профиля // Наука и образование: электронное научно- техническое издание, 2011, № 10 (http://technomag.edu.ru/doc/237464.html).

2.              Черноруцкий И.Г. Методы принятия решений. – СПб.: БХВ-Петербург, 2005.- 416 с.

3.              Карпенко А.П., Федорук В.Г. Один класс прямых адаптивных методов многокритериальной оптимизации // Информационные технологии.- 2009.- №5.- С. 24-30.

4.              Орлянская И.В.  Современные подходы к построению методов глобальной оптимизации // Электронный журнал «Исследовано в России» (http://zhurnal.ape.relarn.ru/articles/2002/189.pdf).

5.              Engelbrecht A. P. Computational Intelligence. An Introduction (second edition).- John Wiley & Sons, 2007. - 597 p.

6.              Jie J., Han Ch., Zeng J. An Extended Mind Evolutionary Computation Model for Optimizations // Applied Mathematics and Computation, 2007, No. 185(2), pp. 1038 – 1049.

7.              Jie J., Zeng J. Improved mind evolutionary computation for optimizations / Proceedings of the 5th World Congress on Intelligent Control and Automation, WCICA 2004, Hangzhou, China 3, Vol. 3, pp. 2200-2204.

8.              Lui J., Li N., Xie K. Application of Chaos Mind Evolutionary Algorithm in Antenna Arrays Synthesis // Journal of computers, 2010, Vol. 5, No. 5, pp. 717-724.

9.              Штовба С.Д. Введение в теорию нечетких множеств и нечеткую логику / С.Д. Штовба.- Режим доступа: http//www.matlab.exponenta.ru, свободный.

10.          Д. Рутковская, М. Пилиньский, Л. Рутковский. Нейронные сети, генетические алгоритмы и нечеткие системы: Пер. с польского И. Д. Рудинского. — М.:Горячая линия — Телеком, 2004. — 452 с.

11.          Галямова Е.В., Карпенко А.П., Соколов Н.К. Методика контроля понятийных знаний субъекта обучения в обучающей системе /Наука и образование: электронное научно-техническое издание, 2009, 2, 042090025\0007 (http://technomag.edu.ru/doc/115086.html )

12.          Смирнова Е.В., Панов А.С. Система автоматического анализа структурированного электронного документа / Свидетельство о государственной регистрации Программы для ЭВМ № 2011615171  от 01 июля 2011 г.