Содержание к диссертации
Введение
1. Обзор и анализ моделей, методов и программных комплексов, используемых в корпоративных системах обучения персонала 15
1.1 Роль персонала в работе современного предприятия 15
1.2 Обзор корпоративных систем обучения персонала 20
1.3 Математические модели, используемые при построении корпоративных систем обучения персонала 29
Выводы по главе 1 35
2. Методы и алгоритмы организации и управления деятельностью обучаемого с учебным материалом 38
2.1 Базовая графовая модель процесса освоения учебного материала 38
2.2. Оценка времени освоения программы обучения с помощью имитационного моделировани 42
2.3 Темпоральная графовая модель, учитывающая эффект «забывания» изученного учебного материала 46
2.4 Алгоритмы имитационного моделирования процесса обучения с учетом нестационарности графа программы обучения
2.4.1 Равновероятный случайный выбор доступного учебного объекта 48
2.4.2 Равновероятный случайный выбор доступного учебного объекта с учетом приоритетов 51
2.4.3 Построение рациональных стратегий выбора учебных объектов при освоении учебного материала
2.5 Генерация случайных графов 55
2.6 Численные эксперименты с имитационными моделями
2.6.1 Численный эксперимент «20/31» 59
2.6.2 Численный эксперимент «20/48» з
2.6.3 Численный эксперимент «25/33» 61
2.6.4 Численный эксперимент «25/53» 62
2.6.5 Численный эксперимент «30/42» 63
2.6.6 Численный эксперимент «30/61» 64
2.6.7 Численный эксперимент «35/43» 65
2.6.8 Численный эксперимент «35/58» 66
2.6.9 Численный эксперимент «40/59»
2.6.10 Численный эксперимент «40/89» 68
2.6.11 Анализ результатов численных экспериментов 69
Выводы по главе 2 70
3. Методы и алгоритмы структуризации образовательного контента систем электронного обучения 74
3.1 Задача формирования оптимального состава учебных модулей 74
3.2 Обзор известных постановок задачи о разбиения ориентированного ациклического графа 77
3.3 Комбинаторные соотношения, необходимые для оценки мощности множества решений и его декомпозиции 79
3.4 Решение задачи прямым перебором 83
3.5 Решение задачи методом ненаправленного случайного поиска 85
3.6 Решение задачи методом локального поиска 86
3.7 Популяционные методы
3.7.1 Эволюционные стратегии 89
3.7.2 Модифицированный алгоритм искусственной иммунной системы с клональной селекцией 91
3.7.3 Генетический алгоритм 93
3.7.4 Островная модель параллелизма и критерий останова вычислительного процесса 99
3.8 Численные эксперименты 102
3.8.1 Численный эксперимент «20/31/[7,7,6]» 102
3.8.2 Численный эксперимент «20/48/[7,7,6] 104 3.8.3 Численный эксперимент «25/33/[8,8,9] 106
3.8.4 Численный эксперимент «25/53/[8,8,9] 108
3.8.5 Численный эксперимент «30/42/[8,8,7,7] 109
3.8.6 Численный эксперимент «30/61/[8,8,7,7] 111
3.8.7 Численный эксперимент «35/43/[9,9,9,8] 113
3.8.8 Численный эксперимент «35/58/[9,9,9,8] 115
3.8.9 Численный эксперимент «40/59/[10,10,10,10]» 117
3.8.10 Численный эксперимент «40/89/[ 10,10,10,10]» 119
Выводы по главе 3 121
4. Программная реализация методов и алгоритмов структуризации образовательного контента и управления процессом электронного обучения 124
4.1 Разработка классов для работы с графовыми моделями 124
4.1.1 Шаблонный класс Graph 124
4.1.2 Классы меток вершин и дуг 129
4.2 Генерация случайных графов 130
4.2.1 Классы для работы с псевдослучайными числами 130
4.2.2 Программный модуль генерации случайных графов
4.3 Программный модуль имитационного моделирования 136
4.4 Класс Partition для работы с разбиениями 138
4.5 Класс Population для работы с множествами разбиений и поддержки функциональности иммунного алгоритма 148
4.6 Классы для поддержки островной схемы организации вычислений 156
4.7 Программный модуль поиска наилучшего разбиения 159
4.8 Реализация системы электронного обучения 160
Выводы по главе 4 160
Заключение 162
Список использованной литературы
- Обзор корпоративных систем обучения персонала
- Оценка времени освоения программы обучения с помощью имитационного моделировани
- Обзор известных постановок задачи о разбиения ориентированного ациклического графа
- Программный модуль имитационного моделирования
Введение к работе
Актуальность темы. Современные промышленные предприятия
являются сложными человекомашинными системами, в которых работники
предприятия (персонал), являются непосредственными участниками
производственного процесса и в значительной степени влияют на
эффективность, надежность и безопасность производства, даже при высоком
уровне автоматизации. Профессиональные знания персонала являются
важнейшим стратегическим ресурсом промышленного производства. Поэтому
подготовка квалифицированных кадров совершенствование х знаний
отнесены к числу высших приоритетов государства.
Сегодня многие российские корпорации разработали основополагающие нормативные документы (стратегии, концепции, стандарты и пр.) в сфере непрерывного развития персонала, создали внутрикорпоративные образовательные структуры (корпоративные университеты, академии, институты, учебно-тренировочные центры, технические школы и пр.), системы электронного обучения и системы управления знаниями. Провозглашается трансформация корпораций в самообучающиеся организации.
Примеры системного подхода к созданию корпоративных систем обучения персонала, встроенных в структуру корпорации, демонстрируют: АО «СО ЕЭС», ОАО «РЖД», Госкорпорация «Росатом», АО «Концерн Росэнергоатом», ПАО «РусГидро», ПАО «Газпром» и другие. Такие системы охватывают десятки тысяч обучаемых, подготовка которых ведется о индивидуализированным программам обучения. Происходит лавинообразный рост образовательного контента (программ обучения, обучающих куров, тестовых заданий, электронных учебников, компьютерных тренажеров и пр.), требующий его систематизации и структуризации, построения и исследования соответствующих моделей, методов и алгоритмов, что позволит не только повысить эффективность хранения больших объемов данных и доступа к ним, но и оказать помощь в работе методистов и обучающихся. Затраты времени на обучение персонала непосредственно влияют на эффективность производства и должны по возможности минимизироваться.
Теоретические вопросы структуризации образовательного контента,
построения и моделирования индивидуальных образовательных траекторий
рассматривались диссертационных исследованиях Курганской Г.С,
Строганова Д.В., Асадуллаева Р.Г., Карташева М.И., Соколова Н.К., Ягудаева Г.Г., Лифанова А.Е. Была предложена формальная теория компьютерного обучения, включающая структурную модель знаний и модель оценки знаний. Использовались графовые модели для представления графа знаний и обучающих кластеров (модулей). Граф знаний был представлен размеченным ориентированным ациклическим графом и с его помощью предлагалось решать задачу выбора наилучшей последовательности среди всех допустимых последовательностей изложения учебного материала. Предлагалось
использовать ярусно-параллельную (уровневую) форму представления графа знаний, а также такие понятия, как логический уровень и фронт обучения, непосредственные связи, отложенные связи, коэффициент забывания и др.
Рассматривались различные подходы к моделированию процесса
обучения предлагалось для формирования качественных учебно-
методических материалов использовать формальные методы структуризации
учебных планов и рабочих программ подготовки, переподготовки и аттестации
специалистов промышленных предприятий, которые основаны на терм-анализе
связности учебных материалов и моделях научения-забывания. Увязку
междисциплинарных связей предлагалось делать путем введения модулей
(однородных, функционально законченных разделов дисциплины) и термов
(понятий предметной области, имеющих собственную синтаксическую
конструкцию). Рассматривалась возможность использования имитационных
моделей. Значительное место в исследованиях рассматриваемой предметной
области уделяется вопросам реализации систем электронного обучения с
использованием возможностей современных информационно-
коммуникационных технологий.
Вместе с тем, научные исследования и разработки в области системного
анализа и моделирования образовательного контента корпоративных
образовательных структур проводятся настоящее время недостаточно
интенсивно, а по вопросам структуризации контента и имитационного
моделирования процессов его изучения отсутствуют общепризнанные
неоспоримые модели, методы алгоритмы, что делает актуальным
продолжение исследований в этих направлениях.
Диссертационная работа выполнена в рамках научного направления ЮРГПУ (НПИ) «Теория, принципы и технологии построения информационно-вычислительных и измерительных систем» (утверждено решением ученого совета университета от 20.09.2011 г.)
Целью диссертационной работы является разработка и исследование
моделей, методов, алгоритмов, программных модулей и комплексов для
решения задачи планирования управления процессами электронного
обучения с учетом вероятностной природы получения оценок и эффекта «забывания», а также оптимальной структуризации образовательного контента.
Для достижения поставленной цели были решены следующие задачи:
-
Выполнен аналитический обзор публикаций и других источников по теме исследования.
-
На основе системного анализа выполнена формализация и построение модели процесса изучения учебного материала в условиях электронного обучения и тестирования с учетом логической взаимозависимости учебных объектов. Для этого использована не только общепринятая теоретико-множественная нотация с использованием положений теории графов, но и
формально-языковая нотация с использованием объектно-ориентированного подхода, принятая в компьютерных науках.
-
Выполнено построение и компьютерная реализация имитационных моделей процесса освоения учебного материала, позволяющих получить статистические оценки общего времени освоения программы обучения, необходимые при планировании процессов обучения. Имитационные модели учитывают вероятностную природу оценок, получаемых при промежуточной аттестации (тестировании), вероятностный характер выбора очередного учебного объекта, а также эффект «забывания» изученного учебного материала. Для этого усовершенствована базовая модель процесса изучения учебного материала с использованием формализмов размеченных темпоральных графов.
-
Разработаны эвристические алгоритмы «советчиков», позволяющие обучаемому рационально управлять процессом обучения посредством такого выбора очередного учебного объекта, который позволяет в среднем сократить общее время по сравнению со случайным выбором.
5) Выполнена ормализация задачи оптимальной структуризации
образовательного контента и ее сведение к задаче о разрезании взвешенного
направленного ациклического графа. Проведен анализ известных методов и
алгоритмов оптимального разрезания графов и сделана комбинаторная оценка
мощности множества допустимых решений.
-
Выполнена разработка и компьютерная реализация алгоритма решения задачи о разрезании взвешенного направленного ациклического графа на базе современных эволюционных методов поисковой оптимизации.
-
Разработано и реализовано объектно-ориентированное вычислительное ядро программного комплекса системы электронного обучения персонала предприятий, содержащее иерархию классов, модули имитационного моделирования и программу поиска квазиоптимального разбиения графов, а также разработана общая структура системы электронного обучения персонала предприятий с использованием концепции многозвенной архитектуры и реализована ее серверная часть на базе современных программных платформ.
Методы исследования. Для решения задач диссертационной работы использованы: методы системного анализа, математическое моделирование, теория графов, структуры и базы данных, методы поисковой оптимизации, эволюционные и иммунные алгоритмы, объектно-ориентированное программирование, методы построения многозвенных программных приложений с веб-интерфейсом. Для практической реализации результатов исследований использованы продукты мировых лидеров - компаний Microsoft и Apple: сервер баз данных Microsoft SQL Server, веб-сервер IIS, технологии и , среды разработки Visual Studio и Xcode, а также языки программирования С++ и C#.
Достоверность обоснованность результатов обеспечивается
корректностью поставленных задач, обоснованностью принятых допущений,
устойчивой работой разработанного программного обеспечения и результатами численных экспериментов на модельных примерах.
Объектом исследования являются процессы обработки информации и принятия решений при организации и проведении электронного обучения персонала промышленных предприятий.
Предметом исследования являются математические модели, методы, алгоритмы и программные комплексы, ориентированные на обработку информации в процессе планирования и реализации электронного обучения персонала предприятий.
Тематика работы соответствует технической отрасли науки паспорта
научной специальности 05.13.01 – «Системный анализ, управление и обработка
информации»: формуле паспорта специальности, так как в диссертации
рассматриваются вопросы «анализа, моделирования, оптимизации,
совершенствования управления и принятия решений, с целью повышения
эффективности функционирования объектов исследования»; а также областям
исследования по п. 3 «Разработка критериев и моделей описания и оценки
эффективности решения задач системного анализа, оптимизации, управления,
принятия решений и обработки информации», п. 4 «Разработка методов и
алгоритмов решения задач системного анализа, оптимизации, управления,
принятия решений и обработки информации» и п. 5. «Разработка специального
математического и алгоритмического обеспечения систем анализа,
оптимизации, управления, принятия решений и обработки информации».
Научная новизна. В диссертации получены следующие новые научные и практические результаты:
1. Предложена расширенная графовая модель процесса освоения
учебного материала в условиях электронного обучения и тестирования,
отличающаяся использованием формализмов размеченных те мпоральных
графов, позволяющая построить алгоритмы имитационного моделирования и
оптимальной структуризации образовательного контента, учитывающие
случайный характер результатов тестирования и эффект «забывания»
изученного материала (соответствует области исследования п. 3 паспорта
специальности).
2. На основе предложенной модели разработаны методы и алгоритмы
имитационного моделирования процесса обучения и оптимальной
структуризации образовательного контента, отличающиеся применением
островной схемы организации вычислений и модифицированных
популяционных алгоритмов для построения квазиоптимального разбиения
направленного ациклического графа, что позволяет уменьшить сложность
графовой модели, получить достоверные оценки общего времени обучения и
оказать помощь обучаемому в навигации по учебным объектам программы
обучения (соответствует области исследования п. 4 паспорта специальности).
3. Создано вычислительное ядро системы электронного обучения
персонала предприятий, содержащее программную реализацию имитационных
моделей, шаблонных классов и модифицированных популяционных
алгоритмов, отличающееся возможностями расширения и повторного использования кода за счет применения парадигмы объектно-ориентированного программирования, что позволяет сократить затраты времени на его адаптацию к решению других задач с использованием графовых моделей (соответствует области исследования п. 5 паспорта специальности).
Основные положения, выносимые на защиту:
1. Расширенная графовая модель процесса освоения учебного материала в
условиях электронного обучения и тестирования.
-
Методы и алгоритмы имитационного моделирования процесса обучения и оптимальной структуризации образовательного контента.
-
Набор программных модулей, образующих вычислительное ядро системы электронного обучения персонала предприятий.
Ценность работы состоит в том, что создано специальное математическое и алгоритмическое обеспечение для корпоративных систем обучения персонала. Предложен и программно реализован набор алгоритмов обработки информации для решения задачи разбиения взвешенных направленных ациклических графов с использованием модифицированных популяционных алгоритмов.
Практическая значимость работы.
Результаты работы могут быть использованы при разработке веб-ориентированных систем электронного обучения персонала промышленных предприятий. Разработанные программные модули рекомендуются к применению при создании имитационных моделей и решении различных прикладных задач с использованием графовых моделей. Разработанные модифицированные популяционные алгоритмы, островная схема организации вычислений и их программные р еализации после незначительной доработки могут применяться к решению широкого круга задач поисковой оптимизации.
Реализация и внедрение работы. Результаты диссертационной работы нашли практическое применение в Центре тренажерной подготовки персонала АО «Системный оператор Единой энергетической системы» (г. Москва) при формировании образовательного контента, планировании и управлении процессами обучения персонала.
Отдельные материалы диссертационной работы используются в учебном процессе ФГБОУ ВО «Южно-Российский государственный политехнический университет (НПИ) имени М.И. Платова» в магистерских программах кафедры «Программное обеспечение вычислительной техники» при изучении тем «Темпоральные графы», «Алгоритмы разрезания графов» и «Применение эволюционных алгоритмов к решению задач на графах».
Апробация результатов работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на следующих конференциях: Региональная научно-техническая к онференция студентов, аспирантов и молодых ученых вузов Ростовской области «Студенческая научная весна». (г. Новочеркасск, ЮРГПУ(НПИ), 5 апреля - 15 июня 2015 г., 6 апреля - 15 июня 2016 г .); VII Международная научно-практическая конференция «Новые задачи технических наук и пути их решения» (г.Челябинск, 10 декабря 2015 г .); 4th International Conference on Applied Innovations in IT - ICAIIT 2016 (Koethen, Germany, 10 March 2016).
Публикации. Основное содержание диссертационной работы отражено в 12 печатных работах, в том числе 3 работы представлены в научных изданиях, рекомендуемых ВАК Министерства образования и науки РФ; 5 работ в сборниках трудов различных конференций (из них одна работа в сборнике, индексируемом в международной базе SCOPUS), 4 свидетельства о регистрации программ для ЭВМ.
Структура и объем работы. Диссертация изложена на 185 страницах машинописного текста (257 страниц с приложениями), иллюстрирована 56 рисунками (105 с приложениями), 28 таблицами (48 с приложениями), содержит 6 приложений. Библиография включает 88 отечественных, 49 иностранных источников, 6 нормативных и иных документов.
Обзор корпоративных систем обучения персонала
Хороший пример применения системного подхода к вопросам анализа и учета роли персонала в работе одной из наиболее сложных социотехнических систем – Единой энергетической системы (ЕЭС) страны демонстрирует одна из крупнейших российских корпораций, непосредственно влияющая на энергетическую безопасность – Акционерное общество «Системный оператор Единой энергетической системы» (АО «СО ЕЭС», или Системный оператор) [16].
Надежная работа ЕЭС в значительной степени зависит от профессиональных знаний и навыков технологического персонала всех уровней иерархии диспетчерского управления Системного оператора (Центральное диспетчерское управление – ЦДУ, Объединенные диспетчерские управления – ОДУ и региональные диспетчерские управления – РДУ). Деятельность персонала Системного оператора направлена на управление ЕЭС в нормальных эксплуатационных, аварийных и послеаварийных режимах, в которых решаются особые задачи по предотвращению развития аварий, восстановлению и ликвидации последствий аварийных отключений оборудования. Высокие темпы технического прогресса, быстрое обновление аппаратуры и программных средств поддержки деятельности технологического персонала Системного оператора приводят к необходимости постоянного обновления знаний и умений специалистов. Требования к процедурам контроля знаний, программам и процедурам обучения закреплены в ряде нормативных документов. Так, в соответствии с «Правилами работы с персоналом в организациях электроэнергетики
Российской Федерации» [17] технологический персонал Системного оператора проходит предэкзаменационную подготовку и проверку знаний: - диспетчерский персонал, а также оперативно-ремонтный персонал, эксплуатирующий технологические и инженерные системы диспетчерских центров – не реже одного раза в год, остальной технологический персонал – не реже одного раза в 3 года; - не технологический персонал проходит предэкзаменационную подготовку и сдачу экзамена по охране труда, а руководители подразделений, дополнительно, экзамен по противопожарному минимуму – один раз в три года. Законом «Об электроэнергетике» [18] на Правительство РФ или уполномоченные им федеральные органы исполнительной власти возложена обязанность по утверждению единых аттестационных требований к лицам, осуществляющим профессиональную деятельность, связанную с оперативно диспетчерским управлением в электроэнергетике, и проведение их аттестации. Приказом Минпромэнерго России от 20.07.2006г. №164 [19] определены «Единые аттестационные требования к лицам, осуществляющим профессиональную деятельность, связанную с оперативно-диспетчерским управлением в электроэнергетике», а также «Порядок аттестации лиц, осуществляющих профессиональную деятельность, связанную с оперативно диспетчерским управлением в электроэнергетике». Поэтому кроме указанной выше регулярной проверки знаний в комиссиях ОАО «СО ЕЭС», диспетчерский персонал проходит государственную аттестацию в комиссиях Ростехнадзора каждые пять лет. Дополнительно, для обеспечения требуемого уровня квалификации технологический персонал проходит регулярное обучение (каждые три года) на курсах подготовки персонала в Центрах тренажерной подготовки персонала. Таким образом ежегодно в АО «СО ЕЭС» проходят различные формы обучения, предэкзаменационной подготовки и проверки знаний несколько тысяч работников. Другие примеры системного подхода к развитию персонала демонстрируют такие корпорации, как Открытое акционерное общество «Российские железные дороги» (ОАО «РЖД») [20], Государственная корпорация по атомной энергии «Росатом» (Госкорпорация «Росатом») [21] и ее энергетический дивизион Акционерное общество «Российский концерн по производству электрической и тепловой энергии на атомных станциях» (АО «Концерн Росэнергоатом») [22], Публичное акционерное общество «Федеральная гидрогенерирующая компания - РусГидро» (ПАО «РусГидро») [23], Публичное акционерное общество «Газпром» (ПАО «Газпром») [24] и другие.
Так, например, в ОАО «РЖД» разработана стратегия развития кадрового потенциала [25], одна из функциональных задач которой – «Непрерывное развитие персонала на основе компетентностного подхода и переход к самообучающейся организации» нацелена на превращение холдинга «РЖД» в самообучающуюся организацию, имеющую эффективную по результатам и используемым ресурсам систему непрерывного индивидуализированного обучения и профессионального развития персонала, собственную базу интеллектуальной собственности и знаний, способствующую стремлению персонала к самостоятельному профессиональному развитию. В рамках Стратегии разработан также стандарт по качеству «Обучение и повышение квалификации персонала» [26], который устанавливает общие требования к обучению и повышению квалификации персонала в ОАО «РЖД» и предназначен для применения департаментами и другими подразделениями аппарата управления, филиалами, дирекциями и структурными подразделениями ОАО «РЖД». Стандарт соответствует требованиям ГОСТ Р ИСО 9001-2015 «Системы менеджмента качества. Требования» [27], а именно п. 7.1.6 «Знания организации».
Оценка времени освоения программы обучения с помощью имитационного моделировани
Практический интерес представляет задача оценки общего времени Т0 освоения обучаемым ОП. Величина нижней границы для Г0 очевидна - это сумма продолжительностей изучения и тестирования для всех УО. Однако фактическое значение Г0 всегда будет больше этой величины, так как количество бллов, получаемых при оценке знаний по модулю может оказаться меньше порогового значения, разрешающего допуск к изучению следующего модуля и потребуется проводить повторное тестирование, что приведет к увеличению общего времени Т0.
Поэтому оценку величины То целесообразно выполнять путем имитационного моделирования [72, 73, 74, 75, 76] процесса освоения ОП и рассматривать некоторые (или все) исходные числовые параметры модели как случайные величины, меющие некоторый известный закон распределения вероятностей. Будем рассматривать в качестве случайной величины оценку ги которую получает обучаемый при тестировании по УО, который соответствует вершине Vj. При этом общее время То освоения образовательной программы также будет случайной величиной. Заметим, что величины tt и тг правильнее считать также случайными, однако это принципиально ничего не меняет плане разработки процедуры имитационного моделирования. Будем использовать случайный выбор на каждом шаге моделирования в вух направлениях: ри выборе очередного модуля из множества допустимых ля изучения модулей и при имитации езультатов тестирования. В первом случае можно применить равновероятный выбор (хотя, как будет показано далее, можно разработать определенные правила предпочтения при выборе для изучения одного из доступных модулей), а во втором - использовать псевдослучайные числа с заданным дискретным распределением (например, сформированным на основе экспериментально полученной таблицы частот). Вопросы выбора и программной реализации подходящих генераторов псевдослучайных чисел (ГПСЧ) отражены в приложении
Построим имитационную модель процесса изучения МОП в виде цикла, на каждой итерации которого моделируется изучение /или тестирование по одному УО, а условием выхода является достижение финальной вершины/ Событием в этой модели будем считать завершение обучения/тестирования по модулю и готовность к выбору следующего доступного модуля. При этом модельное время То будет дискретной величиной, изменяющейся «скачками» по-событийно на tt + тг (если по УО проводится обучение тестирование) ли тг (в случае овторного тестирования по УО с целью получения более высокой оценки).
Для удобства компьютерной реализации модели расширим состав характеристик вершин и дуг графа, содержащихся в их метках. Примем, что метка вершины имеет вид кортежа: lv,—(ti, тг-, id(v,), od(Vi), rt, Pi, presence(v,)), в который добавлены новые характеристики вершины: - id(v,), od(Vi) - полустепени захода и исхода, - г І - текущая оценка, полученная при тестировании, - Pi - булев признак необходимости изучения содержащегося УО материала (false - материал УО еще не изучался; true - материал УО уже изучался и, возможно, требуется повторное тестирование), - presence(Vi) - текущее состояние вершины (0 - вершина «выключена», так как od(v,)=0; 1 - вершина недоступна для обучения, так как id(v,)0; 2 -вершина доступна для обучения, так как id(v,)=0). В свою очередь, метка дуги имеет вид кортежа: lek=(wk, presence(ek)\ в который добавлена новая характеристика дуги: - presence(ek) - текущее состояние дуги (0 - дуга «выключена»; 1 - дуга «включена» и соответствующая ей связь является удерживающей). Алгоритм 1. Имитационная модель процесса освоения ОП. Вход. В качестве исходных данных для моделирования используются параметры, характеризующие граф образовательной программы G=(V, Е), а также вариационный ряд распределения (таблица частот), характеризующий вероятности получения конкретных оценок обучаемым (по 100-балльной шкале) в виде массива пар (гк, рк), где гк - оценка, рк - частота ее получения. Выход. То - общее время освоения ОП. Метод. Задается начальное значение модельного времени Т0 = 0. Пока финальная вершина f находится в состоянии 1, следующие действия циклически повторяются. Из числа вершин, находящихся остоянии 2, равновероятным случайным образом выбирается вершина vt и имитируется процесс изучения/тестирования соответствующего УО с получением случайной оценки rt (для имитации случайного выбора модуля и случайной оценки используется соответствующие ГПСЧ). Модельное время То увеличивается на продолжительность изучения/тестирования.
В завершение очередной итерации цикла производится модификация меток вершин и дуг. Все исходящие из Vj дуги ек, для которых выполняются условия ггм?к, переводятся в состояние 0. Одновременно с этим декрементируются полустепень исхода для вершины Vj и полустепени захода вершин Vj, в которые входят эти дуги. Если оказывается od(Vi)=0, то вершина vt переводится в состояние 0. Если при корректировке полу степени захода вершины Vj оказывается id(Vj)=0, то вершина v,- переводится в состояние 2. [Конец алгоритма] Этот алгоритм можно записать на языке С++ следующим образом: void algorithml(GraphKLabel V, Label E & Gr, roulettes rul) { double TO = 0.0; while (Gr[(int)Gr.vertex size()].presence == 1) int idl = choice vertexl(Gr); learn test(Gr, rul, idl, TO); postprocessingl(Gr, idl); } } Здесь: Gr - граф ОП, гаї - ГПСЧ для получения случайной оценки по заданной таблице частот, choicevertexl - функция, реализующая равновероятный случайный выбор вершины (УО) из числа доступных, learntest - функция, моделирующая изучение/тестирование выбранного УО, postprocessingl - функция, выполняющая модификацию меток вершин и дуг. Полное описание функций choicevertexl, learntest и postprocessingl, а также пример использования алгоритма algorithm 1 основной программе приведены в Приложении 3.
Обзор известных постановок задачи о разбиения ориентированного ациклического графа
Оценку работоспособности и качества разработанных имитационных моделей целесообразно проводить на множестве графов ОП, имеющих различную конфигурацию и это множество должно быть достаточно большим. В связи этим актуальной вляется адача автоматизации формирования (генерации) подобных графов, не привязанных к какой-либо конкретной ОП, используемых исключительно целях отладки и тестирования имитационных моделей.
Предлагается рассматривать графы ОП как случайные графы (random graphs) [86, 87, 88], причем, в отличие от классического подхода, случайными будем считать не только дуги графа, но и параметры меток вершин и дуг. В дальнейшем будем использовать ярусно-параллельную (уровневую) форму [89] для представления графа ОП, что оказывается удобным и применяется многими исследователями для анализа структур представления знаний [55]. Будем считать граф G=(V,E) представленным в уровневой форме, если его множество вершин V разбито на непустые непересекающиеся подмножества (ярусы, уровни): V = V0UV1\J...Vt_1, VinVj = 0, i,je[0,t-l], i j и при этом все дуги, входящие в любую вершину vx Є Vt, исходят из вершин подмножеств V0,V1,…Vi-1, причем имеется хотя бы одна дуга, исходящая из вершины vy Є Уі_г . Очевидно, что все вершины из подмножества V0 являются входными вершинами графа G (имеют нулевую полустепень захода).
В общем случае граф G может иметь несколько выходных вершин (вершин с нулевой полустепенью исхода), расположенных на разных уровнях, однако для целей моделирования образовательной программы удобнее считать, то граф имеет единственную выходную вершину (фиктивную, так как ей не соответствует никакой УО), обозначающую завершение обучения. Расположим эту вершину на уровне Vt и соединим ее дугами со всеми выходными вершинами графа ОП. Разработаем алгоритм генерации случайного графа.
Алгоритм 5. Генерация графа со случайной топологией связей вершин и случайными параметрами меток вершин и дуг. Вход. Количество вершин графа nv, количество уровней t, примерное количество дуг пе. Статистические характеристики параметров меток вершин и дуг: - dt0 - среднее значение времени изучения материала УО; - sdt0 - стандартное отклонение времени изучения материала У О; - dtau0 - среднее значение времени тестирования по УО; - sdtau0 - стандартное отклонение времени тестирования по УО; - w0 - среднее значение веса дуги (пороговой величины оценки при тестировании); - dw0 - стандартное отклонение веса дуги. Выход. Сформированный случайный граф. Метод. Генерируются случайным образом мощности подмножеств І оИ іІ l t-il так, чтобы выполнялось условие: І=ОІ ІІ — nv — 1 . Подмножества V0,V1,…Vt-1 в соответствии с их мощностями заполняются вершинами по порядку их перечисления от 1 до nv-1. Для каждой вершины vx из подмножеств V1,…Vt-1 случайным образом генерируется ее полустепень захода id(vx)1 так, чтобы выполнялось условие: I l(l\yx) Tic \ t— ll \ " J vxevjje[i,t-i] В правой части равенства отражен факт, что полустепень захода финальной вершины будет, как минимум, равна Vt-il. В цикле по подмножествам V1,…Vt-1 для каждого элемента vx Є Vj выполняется следующее (здесь Vj - текущее подмножество): - в граф включается дуга (у,х), где vy Є Vj_1- случайно выбранная вершина; - если id(vx) 2, то в граф включаются id(vx) — 1 дуг (z,x), где vz Є VQ U Vt U ...Vj_1 - случайно выбранная вершина (при выборе обеспечивается неповторяемость дуг). Для каждой вершины графа vt, і Є [1, п — 1] вычисляется ее полустепень исхода od(y ) и, если оказывается od(Vi)=0, в граф включается дуга (/,и v) (т.е. вершина с нулевой полу степенью исхода соединяется дугой с финальной вершиной vnv).
Для всех вершин и всех дуг графа с помощью соответствующих ГПСЧ (с нормальным законом распределения) генерируются случайные параметры меток вершин и дуг. [Конец алгоритма]
Полное описание алгоритма генерации случайного графа в форме программного кода на языке С++ приведено в приложении 3. С помощью данного программного модуля была составлена «библиотека графов» из 10 случайно сгенерированных графов с различным количеством вершин и ребер, приведенная в приложении 2. Представленные в библиотеке графы использованы в качестве исходных данных при выполнении различных численных экспериментов.
Программный модуль имитационного моделирования
Можно предложить различные способы реализации функции Tweak, которая должна выполнять небольшие случайные вариации своего аргумента (англ. tweak переводится как «ущипнуть, дернуть»). По причинам, которые будут объяснены ниже, будем считать, что случайные вариации выполняет операция мутации (функция Mutate), которая широко используется в эволюционных алгоритмах [118, 119, 120, 121]. Мутацию предлагается реализовать следующим образом: в двух случайно выбранных элементах (подмножествах) заданного разбиения случайным образом выбирается по одной вершине, которые затем меняются местами. После этого полученное новое разбиение проверяется на допустимость (все разрезы должны быть ориентированными, а компонентный граф - ацикличен) и, случае допустимости разбиения мутация считается успешной. Если же разбиение недопустимо, о восстанавливается состояние разбиения о обмена вершинами делается повторная попытка мутации. Для исключения зацикливания количество попыток мутации ограничивается некоторой достаточно большой величиной Мтах (например, 500). Функция Mutate может иметь числовой параметр т, по умолчанию равный 1, который определяет, сколько нужно сделать удачных попыток мутации за один вызов этой функции.
Функция Mutate реализует следующий алгоритм: Шаг 1. Начало цикла по попыткам получения допустимого разбиения путем мутации: счетчик количества попыток і = 0; счетчик количества удачных попыток mi = 0. Шаг 2. Случайный выбор пары различных подмножеств, случайный выбор по одной вершине в каждом из выбранных подмножеств и обмен этими вершинами (получение нового разбиения). Шаг 3. Проверка полученного разбиения на допустимость: сли допустимо - переход к шагу 4, иначе - к шагу 5. Шаг 4. Инкремент счетчика удачных попыток мутации: ++mi. Если mi==m (сделано заданное количество удачных попыток), то функция Mutate завершает работу, иначе - переход к шагу 6. Шаг 5. «Откат»: происходит обратный обмен вершинами (восстанавливается разбиение до мутации). Шаг 6. Инкремент счетчика цикла: ++І. Если i==M_max, функция Mutate завершает работу, иначе - возврат к шагу 2.
Таким образом, после вызова функции Mutate гарантированно получим допустимое разбиение, которое будет отличаться от исходного, если была хотя бы одна удачная попытка мутации (но не более т), либо останется прежним, если был исчерпан лимит числа попыток Мтах и среди них не было ни одной удачной.
Заметим, что для получения начального решения, которое должно быть допустимым разбиением, целесообразно также использовать функцию Mutate, которая будет «стартовать» с произвольно задаваемого разбиения (которое может и не быть допустимым). Конечно, в этом случае нужно проверять на допустимость получаемое после вызова Mutate решение. Экспериментально было показано, что допустимое разбиение быстрее отыскивается, если использовать уровневое представление рафа [94] (представление в ярусно-параллельной форме [55]) и последовательность номеров вершин графа сформировать в порядке их размещения по уровням: сначала идут все вершины нулевого уровня, затем первого и т.д. Полное описание функции Mutate и алгоритма локального поиска приведены в Приложении 3.
Методы, основанные на использовании популяции, отличаются от методов с «одним состоянием», тем, что работают с множеством допустимых решений, а не с единственным решением [139]. Каждое решение («особь») постепенно улучшается и оценивается, и основным отличием от простого метода локального поиска заключается в том, что одно решение может повлиять на то, как будут улучшены другие решения: «хорошие» решения влияют на то, какие «плохие» решения будут отброшены, либо «помогают» улучшить плохие решения.
Обычно под популяционными понимают набор методов, известных как эволюционные вычисления (Evolutionary Computation), а реализующие их алгоритмы называют эволюционными алгоритмами (Evolutionary Algorithm). Эти алгоритмы заимствуют подходы популяционной биологии, генетики и эволюции. Традиционно к эволюционным алгоритмам относят эволюционные стратегии (Evolution strategy) и генетический алгоритм (Genetic algorithm). Эволюционные стратегии (ЭС) были разработаны I.Rechenberg и Н.-Р. Schwefel в Берлинском техническом университете в середине 1960-х гг. [140]. ЭС используют простую процедуру селекции (отбора особей из популяции), называемую селекцией усечением (Truncation Selection), а в качестве оператора для улучшения особей применяется только мутация. В [139] описаны несколько алгоритмов эволюционных стратегий; остановимся на одном из них - “алгоритме (ц.+)”, в котором новая популяция (популяция следующего поколения) составляется как из родительских особей текущей популяции (берется fi лучших особей), так и из потомков (их количество равно ). Запись алгоритма (х+) на псевдокоде имеет вид: 1: (х = количество отбираемых из текущей популяции лучших родительских особей 2: = количество генерируемых потомков (предполагается, что =k fi, где к 1 - целое число, показывающее, сколько потомков получается от каждой родительской особи в результате ее мутации) 3: S = {} // пустая популяция (начальное поколение)