Синтез учебных пособий, адаптированных к индивидуальным особенностям обучаемых, из отдельных фрагментов учебных материалов, называемых модулями, выполняется на основе модели SCORM [SCORM, 2001] или технологии разделяемых единиц контента (ТРЕК), реализующей онтологический подход [Норенков, 2003].

В рамках ТРЕК задача СТОУП формулируется следующим образом. Имеются:

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

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

Требуется составить оптимальное по критерию Z (М) учебное пособие из модулей, соблюдая условие "входные концепты любого модуля должны либо относиться к T_исх, либо присутствовать среди выходных концептов предшествующих модулей". В качестве Z (М) могут использоваться число модулей или функции метаданных модулей, например, объем пособия, оценки сложности изложения материала и т.п.

Моделью задачи СТОУП является И/ИЛИ граф, в котором вершины ИЛИ соответствуют концептам онтологии, вершины И - модулям, дуги, направленные от И-вершин к ИЛИ-вершинам выражают отношения "определен в", дуги, идущие от ИЛИ-вершин к И-вершинам отношения "используется в". Каждому концепту K_p соответствуют переменная k_p и вершина типа ИЛИ в И/ИЛИ графе, а каждому модулю M_q - переменная m_q и вершина типа И, причем k_p=1 и m_q=1, если p-й концепт и q-й модуль, входят в рассматриваемый вариант решения, иначе k_p=0 и m_q=0. Другими словами, для каждого концепта в синтезируемом учебном пособии справедливо уравнение:

k_p = У m_pq & k_r = 1, (1.1)

q€Q_p r€ R_pq

где У и & - знаки логических сложения и умножения, Q_p множество номеров модулей, в которых определен концепт K_p, R_pq - множество номеров концептов, входных для модуля M_pq.

Решение задачи СТОУП начинается с записи модели в виде:

& k_r = 1, (1.2)

где k_r-переменные соответствуют концептам K_r€T_цел. Далее каждая переменная k_r в (1.2) заменяется на множество дизъюнктов по формуле (1.1). Рекурсивный процесс подстановки (1.1) в (1.2) продолжается до тех пор, пока в (1.1) не останется иных k_i, кроме соответствующих концептам множества T_исх. В получающейся после раскрытия скобок дизъюнктивной форме каждый дизъюнкт соответствует одному из возможных решений задачи СТОУП.

2. Пример модели СТОУП

На Рис.1 дан пример И/ИЛИ графа, где вершины концептов и модулей изображены овалами и прямоугольниками соответственно, вершины исходных концептов не показаны, Т_цел представлено вершинами K₁, K₂, K₃, изображающими одноименные концепты.

Описание структуры И/ИЛИ-графа удобно представить в форме таблиц 1 и 2, в которых зафиксированы отношения "род/вид" (в случае СТОУП это отношение "концепт определен в модулях") и "целое/часть" (в СТОУП это "в модуле используются концепты").

В соответствии с (1.2):

k₁&k₂&k₃=1.

Используя (1.1), имеем:

(m₁&k₄+m₂&k₅&k₆) & (m₃&k₈&k₁₁+m₇&k₁₀+m₉&k₁₂) & (m₄&k₇&k₁₃+m₇&k₁₀ + m₈&k₁₁&k₁₂) =1,

Рис.1. И/ИЛИ граф

где + знак логического сложения. Продолжая замены переменных k_r по формуле (1), приходим к итоговой записи модели в виде дизъюнктивной формы, в которой каждый дизъюнкт выражает одну из возможных альтернатив решения - подмножество переменных m_q, определяющих модульный состав синтезируемого учебного пособия.

Табл.1

Табл.2

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

3. Генетический поиск на И/ИЛИ графах

Для применения генетического алгоритма необходимо, прежде всего, определить способ кодирования искомых решений. Кодирование решений в задачах поиска на И/ИЛИ графах выполняется следующим образом. Каждому p-му концепту (вершине ИЛИ) в хромосоме отводится один ген. Гены подразделяются на активные и неактивные. Ген активен, если соответствующий ему концепт входит в проектное решение, представляемое данной хромосомой. Аллелем активного гена является имя одного из модулей, в которых определен p-й концепт.

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

Генерация начального поколения осуществляется по следующему алгоритму. Все гены, кроме генов целевого множества, первоначально объявляются неактивными. Для целевых генов случайным образом из таблицы 1 выбирается по одному из возможных значений. Выбор аллеля позволяет по таблице 2 или формуле (1.1) определить гены, входящие в решение, и, следовательно, преобразовать их в активные назначением их аллелей. Процесс выбора аллелей и определения активных генов назовем активизацией генов. Активизация завершается, когда все ветви активизации просмотрены и заканчиваются генами исходных концептов.

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

Для примера графа Рис.1 и двух хромосом-родителей А и В, представленных в таблице 3, применение этого алгоритма приводит к выделению в хромосоме А фрагментов

{ M ₁, M ₅, M ₁₀}; { M ₃, M ₁₀, M ₁₂}; { M ₇}; { M ₁₁}

и в хромосоме В соответствующих им фрагментов

{ M ₂, M ₁₀, M ₇}; { M ₇}; { M ₄, M ₉, M ₁₅}; { M ₁₂}.

Табл.3

Если рекомбинация фрагментов заключается в обмене четными фрагментами, то в примере будут получены хромосомы-потомки C и D, показанные в таблице 4.

Табл.4

Мутации должны относиться к активным генам, причем появление в некотором гене нового аллеля может сопровождаться изменением статуса активности у ряда других генов, т.е. может инициировать процессы активизации и дезактивизации. Гены в подключаемых ветвях активизируются, гены, не попавшие в рассмотрение при активизации, становятся неактивными. Так, в рассмотренном примере мутация гена k₂ с заменой аллеля m₃ на m₉ приводит к переходу гена k₁₂ с аллелем m₁₅ в число активных, а гена k_{11 -} в число неактивных.

Заключение