Содержание к диссертации
Введение
1 Учебный план образовательной программы как объект исследования 14
1.1 Основные документы поддержки задач планирования учебного процесса 14
1.1.1 Назначение и общая характеристика учебного плана 14
1.1.2 Структура построения учебного плана 17
1.2 Процедура составления учебного плана образовательной программы .19
1.2.1 Обобщённая схема планирования учебного процесса 19
1.2.2 Ограничения на структуру и параметры учебного плана 21
1.3 Анализ существующих программных средств поддержки процесса составления учебных планов 24
1.4 Анализ возможностей формализации критериальной оценки эффективности учебных планов 27
1.4.1 Проблемы оценки эффективности учебного плана 27
1.4.2 Критериальная стратегия решения задачи оптимизации учебного плана 31
1.5 Анализ возможностей методов поисковой оптимизации как
инструментов построения учебных планов 34
1.5.1 Точные методы решения задачи оптимального расписания 34
1.5.2 Приближённые списочные алгоритмы составления оптимальных расписаний 37
1.5.3 Приближённые эвристические алгоритмы составления оптимальных расписаний 39
1.6 Эволюционно-генетический алгоритм как метод решения экстремальных задач 43
1.6.1 Общая характеристика эволюционно-генетических алгоритмов 43
1.6.2 Генетическая модель оптимизируемого объекта 44
1.6.3 Основные операции функционирования генетического алгоритма. Мутация 46
1.6.4 Основные операции функционирования генетического алгоритма. Кроссинговер 47
1.6.5 Основные операции функционирования генетического алгоритма. Отбор особей в новое поколение 49
1.6.6 Некоторые итоги по перспективам использования ЭГА 51
1.7 Выводы по первой главе 52
2 Эволюционно-генетическая модель учебного плана образовательной программы 54
2.1 Математическая модель учебного плана образовательной программы .54
2.1.1 Математическая формализация понятия учебного плана 54
2.1.2 Параметры и ограничения учебного плана 56
2.2 Критериальная стратегия оценки качества учебного плана 59
2.2.1 Общая характеристика подхода 59
2.2.2 Оценки равномерности освоения знаний 60
2.2.3 Оценка близости зависимых дисциплин 61
2.2.4 Оценка интенсивности изучения дисциплин 63
2.2.5 Нормализация частных оценок и построение обобщающего критерия 63
2.3 Генетическая модель учебного плана образовательной программы 65
2.3.1 Возможные концепции построения генетической модели УПОП...65
2.3.2 Почасовая генетическая модель 65
2.3.3 Поэлементная генетическая модель 66
2.3.4 Семестровая генетическая модель 67
2.3.5 Дисциплинарная генетическая модель 67
2.3.6 Структура особи на основе ДГМ 68
2.4 Эволюционно-генетическая модель популяций УПОП 69
2.4.1 Структура и свойства популяции особей на основе ДГМ 69
2.4.2 Принцип формирования особей первого поколения 70
2.4.3 Алгоритм формирования особей первого поколения 72
2.4.4 Отбор особей для скрещивания 75
2.4.5 Операция кроссинговера 78
2.5 Перспективы структурно-параметрической модификации ЭГА применительно к задачам субоптимального конструирования УПОП 85
2.6 Выводы по второй главе 90
3 Субоптимизация эволюционно-генетического алгоритма построения учебных планов 91
3.1 Эволюционно-генетический алгоритм составления УПОП как объект оптимизации 91
3.2 Выбор схемы эксперимента по оптимизации ЭГА применительно к задаче построения УПОП 93
3.3 Исследование и оптимизация механизма отбора родительских пар 96
3.3.1 Структура задачи и выбор схемы эксперимента 96
3.3.2 Проведение предварительного эксперимента 97
3.3.3. Обработка и анализ результатов предварительного эксперимента.98
3.3.4 Исследование эффективности отбора родительских пар в ЭГА на основе методов т2, т3, т4 и т5 102
3.3.5 Исследование эффективности отбора родительских пар в ЭГА на основе методов m,, т2, т3 108
3.3.6 Выводы по результатам исследования механизма формирования родительских пар 115
3.4 Исследование и оптимизация механизма мутации 116
3.4.1 Постановка задачи 116
3.4.2 Проведение исследований 116
3.4.4 Выводы по результатам исследования механизма мутации 126
3.5 Исследование и оптимизация механизма кроссинговера 127
3.5.1 Постановка задачи и выбор схемы исследования 127
3.5.2 Поиск оптимального значения поправочного коэффициента 128
3.6 Исследование и оптимизация механизма старения 131
3.6.1 Выбор структура эксперимента 131
3.6.2 Проведение исследований 132
3.7. Выводы по третьей главе 136
4. Программный комплекс построения субоптимальных учебных планов образовательных программ 139
4.1. Общая характеристика информационной системы 139
4.1.1 Общая характеристика комплекса 139
4.1.2 Информационно-функциональная структура комплекса 140
4.1.3 Интерфейс интерактивного взаимодействия с PC CAD 142
4.2 Структурно-топологическая схема УПОП 145
4.2.1 Общая характеристика структурно-топологической схемы 145
4.2.2 Функционально ориентированные области СТС 146
4.2.3 Сопряжение СТС с официальной формой учебного плана 148
4.3. Мастер формирования исходных данных для задачи составления УПОП 151
4.3.1 Объектная модель УПОП как основа для построения МФИД 151
4.3.2 Система наследования в четырехуровневой объектной модели УПОП 153
4.3.3 Расширение четырехуровневой объектной модели УПОП 159
4.4 Реализация эволюционно-генетического алгоритма 161
субоптимизации УПОП 161
4.4.1 Общая характеристика генетического алгоритма оптимизации учебного плана специальности 161
4.4.2 Объектная модель генетического алгоритма оптимизации учебного плана специальности 162
4.4.3 Применение эволюционно-генетического алгоритма для субоптимизации реальных учебных планов 166
4.5 Выводы по четвертой главе 171
Заключение
- Основные документы поддержки задач планирования учебного процесса
- Математическая модель учебного плана образовательной программы
- Эволюционно-генетический алгоритм составления УПОП как объект оптимизации
- Общая характеристика информационной системы
Введение к работе
Актуальность темы. Эффективное планирование учебного процесса является залог успешной подготовки высококвалифицированных кадров. В настоящее время происходит модернизация системы высшего образования в двухуровневую. Кроме того, наблюдается повышение спроса на качественное образование и появление новых специальностей, что особенно ярко выражено в стремительно развивающихся областях высоких технологий, менеджмента и экономики. В сложившихся условиях часто возникает необходимость в конструировании новых учебных планов, или же в преобразовании существующих. Процедура составления учебных планов достаточно длительна и трудоёмка, она требует высокой квалификации и внимания проектировщиков. Применение инструментов, позволяющих автоматизировано решать такую задачу, должно существенно повысить скорость и качество планирования учебного процесса.
Несмотря на интенсивное исследование данной проблемы практические успехи в этой области невелики. Хотя в данной области существуют отдельные программно-алгоритмические решения, однако они, по различным причинам, не предоставляют достаточных возможностей автоматизировано строить полноценные учебные планы в масштабах вузов. Их разработка затруднена рядом серьёзных проблем. В первую очередь, к ним следует отнести большую размерность задачи и её вычислительную сложность. Кроме того, для данной задачи характерна многокритериальность оценки качества решения, наличие ряда трудно формализуемых факторов и критериев эффективности, а также сильная неоднородность пространства поиска.
В связи со всеми указанными факторами проводимые в диссертационной работе исследования по разработке алгоритма и программного комплекса для построения учебных планов и их субоптимизации является весьма актуальными и по сути решаемых задач соответствуют заявленной научной специальности - 05.13.01.
Цели и задачи исследования. Основной целью работы является решение проблемы существенного повышения эффективности построения учебных планов образовательных программ. Для ее достижения необходимо решить следующие задачи:
изучить структуру и информационное наполнение учебных планов специальностей и направлений в высшей школе, рассмотреть критерии оценки их качества и требования ГОС ВПО;
построить концептуально-математическую модель учебного плана образовательной программы, а также формализовать систему ограничений и критериальную стратегию оценки его качества;
исследовать возможности применения существующих алгоритмов составления оптимального расписания для решения задачи оптимизации учебного плана;
разработать эволюционно-генетическую модель учебного плана;
адаптировать генетический алгоритм и его основные механизмы к решению задачи построения субоптимальных учебных планов;
исследовать разработанный эволюционно-генетическии алгоритм как объект описания и формирования свойств создаваемых планов и произвести структурно-параметрическую оптимизацию его механизмов применительно к задаче конструирования и субоптимизации учебных планов образовательных программ;
разработать информационную систему автоматизированного формирования и субоптимизации учебных планов на основе современных принципов построения пользовательских интерфейсов.
Существенные научные результаты, полученные в диссертации:
1) концептуально-математическая модель учебного плана образовательной программы в совокупности с системой структурно-параметрических ограничений и многокритериальной стратегией оценки его качества;
дисциплинарно-генетическая модель учебного плана, как основа для построения эффективного эволюционно-генетического алгоритма;
модифицированный эволюционно-генетический алгоритм, адаптированный к решению задачи субоптимизации учебных планов образовательных программ;
структура операторов эволюционно-генетического алгоритма и совокупность его параметров, полученные в работе для решения задачи конструирования учебных планов образовательных программ.
Научная новизна существенных результатов диссертации определяется следующими отличительными признаками:
разработанная концептуально-математическая модель учебного плана образовательной программы в совокупности с гибкой критериальной стратегией, в отличие от известных, ориентирована на построение его эффективной эволюционно-генетической модели;
сконструированная дисциплинарно-генетическая модель учебного плана уникальна, т.к. не применялась ранее для оптимизации подобных информационных объектов;
модификация традиционной схемы эволюционно-генетического алгоритма, заключающаяся в совокупном использовании в нем различных методов реализации его этапов, а также в применении парадигмы старения особей, позволяет рассматривать его как новую разновидность эволюционно-генетических алгоритмов;
структуры операторов, реализующих этапы эволюционно-генетического алгоритма, и совокупность характеризующих их параметров найдены из условий субоптимизации процесса построения учебного плана.
Методы исследования. В работе использованы математические методы исследования операций: оптимизации, теория генетических алгоритмов,
теория планирования эксперимента, теория множеств, теория графов, а также методология компьютерного имитационного моделирования.
Достоверность результатов исследования определяется корректностью приводимых выводов и доказательств, статистической представительностью обрабатываемых выборок, а также использованием апробированных пакетов программ. При этом разработанный в рамках данного диссертационного исследования программный комплекс и его основные компоненты, реализующие методики синтеза и имитационного моделирования, были зарегистрирован в Федеральной службе по интеллектуальной собственности, патентам и товарным знакам.
Практическая значимость. Разработанный на основе проведенных системных исследований проблемно-ориентированный 111111 позволяет существенно упростить процедуру составления учебных планов образовательных программ и устранить недостатки в их составлении, вызванные человеческим фактором, высокой размерностью и трудоемкостью задачи. Применение средств программной поддержки, реализующих полученные в диссертации решения, дает возможность повысить скорость и эффективность составления учебных планов за счет применения уникального эволюционно-генетического алгоритма их субоптимизации. Наличие в разработанном программном комплексе функции логического контроля УПОП позволяет на стадии конструирования избегать нарушений существующих образовательных стандартов и методических рекомендаций.
В условиях перехода на двухуровневую систему образования практическая значимость результатов проведенного диссертационного исследования повышается, так как они позволяют упростить, повысить качество и скорость разработки новых, и модификации существующих учебных планов.
Практическая значимость проведенных исследований и разработок подкрепляется актами об их внедрении на уровне управлений учебно-методическими процессами вузов региона, заключениями учебно-методических
органов ряда вузов РФ и свидетельствами Роспатента о регистрации авторского права на разработанный программный комплекс и его компоненты.
Соответствие диссертации научному плану работ и целевым комплексным программам. Тема диссертации утверждена приказом ректора РГАСХМ и выполняется в соответствии с тематическим планом госбюджетных работ академии. По содержанию диссертационные исследования соответствует задаче, направленной на обеспечение качества, доступности и эффективности образования, определенной в Концепции модернизации российского образования на период до 2010 года в Федеральной целевой программе развития образования на 2006-2010 годы, принятой постановлением правительства Российской Федерации № 803 от 23 декабря 2005 года [86].
Апробация диссертационной работы. Материалы диссертационной работы апробировались на следующих международных научных конференциях: XIX Международная научная конференция «Математические методы и технологиях 19» (ВГТА, Воронеж, 2006г.), Первый международный научно-методический симпозиум «Современные проблемы многоуровневого образования» (ДГТУ, 2006г.), XX Международная научная конференция «Математические методы и технологиях 20» (ЯГТА, Ярославль, 2007г.), Второй международный научно-методический симпозиум «Современные проблемы многоуровневого образования» (ДГТУ, 2007г.). Кроме того, промежуточные материалы исследований докладывались на ежегодных научно-технических конференциях ППС РГАСХМ и ДГТУ.
Публикации. Всего по теме диссертации опубликовано 12 работ, в которых освещены наиболее существенные её результаты. Большинство работ опубликовано в центральной печати: в журнале "Вестник ВГТУ", в сборниках научных трудов международных конференций ММТТ-19, ММТТ-20, сборниках первого и второго международного научно-методического симпозиума «Современные проблемы многоуровневого образования». Несколько
статей вышли в межвузовских сборниках "Научное знание: новые реалии" и "Системный анализ, обработка информации и управление".
Диссертационная работа состоит из введения, четырёх глав, заключения и приложений.
Во введении обоснована актуальность темы, определены цели и задачи исследования, сформулированы существенные научные результаты, научная новизна и практическая значимость результатов, полученных в диссертации, а также дана краткая характеристика содержания глав и полученных в них результатов.
В первой главе рассматриваются задачи и цели учебного плана образовательной программы (УПОП) в системе подготовки специалистов в высшей школе, исследуется его структура и информационное наполнение. На основе требований ГОС ВПО и опыта УМО вузов региона в общих чертах формулируются система ограничений, налагаемых на УПОП, а также определяются основные критерии качества, по которым его следует оценивать. На основе полученных сведений производится постановка задачи создания информационной технологии конструирования учебного плана и делается вывод об её актуальности и важности.
Произведён аналитический обзор существующих программных решений, применяемых для составления учебных планов, и методов составления оптимальных расписаний. На основании него делается вывод о необходимости синтеза на базе эволюционно-генетических методов оптимизации алгоритма построения субоптимальных учебных планов и разработки программного комплекса, реализующего функциональной по их конструированию.
Во второй главе формализуется понятие учебного плана, осуществляется построение его концептуально-математической и эволюционно-генетической моделей, а также синтез вероятностного алгоритма его автоматизированного построения и эволюционно-генетического алгоритма (ЭГА) субоптимизации.
Результатом исследований, проведённых во второй главе, стала дисциплинарно-генетическая модель учебного плана, эволюционно-генетический алгоритм (ЭГА) его совершенствования и постановка задачи для изучения системы УПОП-ЭГА как объекта информатизации и оптимизации.
Третья глава посвящена исследованиям по повышению эффективности основных генетических операторов ЭГА и всего алгоритма в целом. В связи с этим структура решаемой задачи рассматривается в совокупности с используемым методом. В качестве методологической основы для проведения оптимизации алгоритма используется аппарат теории планирования эксперимента, в совокупности с регрессионным анализом и градиентными методами поиска. В результате серии экспериментов определены эффективная структура операторов ЭГА и оптимальные значения его параметров.
В четвёртой главе описывается процесс разработки программного комплекса PC CAD (Program Complex for Curriculum Automated Designing), предназначенного для построения субоптимальных учебных планов, рассматривается его архитектура и технология построения его основных компонентов. Описывается структурно-топологическая схема, как инструмент для конструирования и редактирования учебного плана, мастер формирования исходных данных, в основе которого лежит объектно-ориентированная модель УПОП, и технология программной реализация эволюционно-генетического алгоритма. В заключительной части четвертой главы приводятся примеры синтеза субоптимальных структурно-топологических схем реальных учебных планов, построенных с использованием разработанного программного комплекса.
Основные документы поддержки задач планирования учебного процесса
В настоящее время в высших учебных заведениях применяется две системы образования: 1) Одноступенчатая - при которой ведётся подготовка специалистов доминирующего ранее инженерного уровня. 2) Двухступенчатая, состоящая из двух этапов: a) общеобразовательный - подготовка бакалавров; b) специализирующий - подготовка магистров.
Однако, независимо от используемой системы образования, организация образовательного процесса должна рассматриваться как комплексная целевая программа [19, 22], а не как совокупность независимых друг от друга дисциплин. Поэтому учебная процесс в вузе должен планироваться как последовательность изучения взаимосвязанных дисциплин.
Главными документами, на основании которых организуется учебный процесс в вузе, являются учебные планы образовательных программ (УПОП). Учебные планы составляются выпускающими кафедрами для каждого направления и каждой специальности, по которым ведётся подготовка студентов в вузе. Основной задачей УПОП является регламентирование графика всего цикла обучения и его эффективная организация. Этот результат достигается, как исключением неравномерности в учебной нагрузке, т.е. недогрузки в одних семестрах и перегрузки в других, так и обеспечением должной логической последовательности изучения дисциплин. Разрабатываемые УПОП являются основой для планирования посеместровых занятий кафедры, распределения рабочей нагрузки преподавателей и, в дальнейшем, составления расписания занятий.
Основным руководящим документом, на базе которого формируется УПОП является Государственный образовательный стандарт высшего профессионального образования (ГОС ВПО) [21,121]. В нем приведены требования к обязательному минимуму содержания основной образовательной программы по специальности, включающие перечень обязательных дисциплин, их основные дидактические единицы, группы дисциплин, назначаемых вузом, и часы, выделяемые на их освоение. Каждой дисциплине, включённой в стандарт, поставлены в соответствие идентификаторы, позволяющие разделить все дисциплины на группы, называемые учебными циклами и компонентами [84]. В результате, структуру ГОС ВПО в плане разделения дисциплин по циклам и компонентам можно представить табл.\Л.
Как видно из табл. 1.1, основное разбиение учебной программы производится по двум признакам: функциональному и уровневому.
По функциональному признаку содержания дисциплины в задаче подготовки специалиста данного профиля государством определены следующие циклы [121]: 1) цикл ГСЭ - общие гуманитарные и социально-экономические дис циплины, обеспечивающие адаптацию специальных знаний обучающегося и его самого к сфере их приложения; 2) цикл ЕН - общие математические и естественнонаучные дисциплины, образующие концептуально-методологический фундамент специальных знаний; 3) цикл ОПД - общепрофессиональные дисциплины, формирующие профессиональный базис обучаемого; 4) цикл СД - специальные дисциплины, используемые для направленной предметно-ориентированной подготовки специалиста; 5) цикл ДС - дисциплины специализации, дающие узко направленную подготовку обучаемого в соответствии с потребностями специальности, региона, возможностями кафедры и т.д.; 6) цикл ФТД - факультативные дисциплины, дающие возможность вузу и кафедре гибко реагировать на конъюнктуру рынка знаний.
По источнику включения дисциплины в учебную программу и, соответственно, её статусу в ГОС ВПО определены следующие компоненты [121]: 1) федеральный компонент; 2) региональный компонент; 3) выборочный компонент.
Принцип разделения дисциплин по смысловой нагрузке более или менее очевиден. Деление же по компонентам связано с решение задачи, суть которой состоит в совмещении государственного регулирования учебного процесса с региональными задачами и возможностями его реализации.
Федеральный компонент составляют дисциплины, перечень которых задаётся ГОС ВПО. Они задают определённый базис образовательной программы и обязательны для включения в учебную программу специальности. Для каждой дисциплины из этой группы определен объём учебной нагрузки, который необходимо распределить в учебном плане по семестрам.
Математическая модель учебного плана образовательной программы
Учебные планы образовательных программ (УПОП) формализуются как связное множество конкретных дисциплин D = {d1,d2»-.,cli,..,clm} где dr суть учебной дисциплины (УД), т- число дисциплин в образовательной программе [30, 39]. Структура и правила включения дисциплин в УПОП описаны в первой главе. На стадии построения плана необходимо, чтобы их выбор и параметры раскладки по видам занятий уже был осуществлён. Для каждой стандартом или разработчиком задаётся объём академических часов т?, отводимых на её изучение. Все дисциплины образовательной программы группируются по множествам образовательных циклов D= (JDC, где с - ин сеС деке, обозначающий принадлежность дисциплины к образовательному циклу, которые образуют множество C = {Cj :j = l,kc} , где kc- количество образовательных циклов. При этом Dc ={d J :j = l,kc} и выполняется условие VCj,ck eC- dqj,d :q r. Для каждого цикла стандартом задаётся объём академических часов тс = 2 Tf » которому соответствует суммарная учеб Vi- dj6Dc ная нагрузка по всем дисциплинам, составляющим этот цикл.
Как уже указывалось в первой главе, при реализации основной образовательной программы высшее учебное заведение имеет право изменить объем часов, отводимых на освоение учебного материала для циклов дисциплин - в пределах 5% и для дисциплины, входящей в цикл - в пределах 10%, при условии выполнения требований к содержанию, указанных в стандарте для специальности. Это означает, что значение if является формальным, а реальный объём учебной нагрузки т[ выбирается из интервала if ± if 0.1, при соблюдении условия
Учебная нагрузка делиться на аудиторную и самостоятельную. При планировании основной задачей является распределение именно аудиторных занятий, так как их количество оказывает непосредственное влияние на структуру кафедральной нагрузки и расписание занятий. В соответствии с требованиями ГОС ВПО, объём аудиторной нагрузки т?, для Vd; є D, ограничивается пятьюдесятью процентами от общей учебной нагрузки: VdieD- TJ x[ 0.5, (2.2) а объём часов, отводимых на самостоятельную подготовку х\, составляет оставшуюся часть от общего числа академических часов или х- = т[ - tf, VdjGD.
При конструировании учебного плана удобно оперировать не объёмами аудиторных занятий в семестрах, а часами, отведёнными на изучение дисциплины в неделю. Тогда, множеству дисциплин D можно сопоставить множество Tv = {Tf ,Т%,..,Т?,..,Тп), где Т? - столбец, содержащий по строкам значения объёма недельной аудиторной нагрузки дисциплины d; по всем семестрам, т.е. Tjd = ( ,,1 ,..,1 ]1, где t - число часов в неделю, отведённых на аудиторные занятия в s -ом семестре для і-ой дисциплины d;, Tj - вектор распределения недельной нагрузки по всем семестрам для дисциплины d; такое, что tjj = т?, m - число учебных дисциплин, п - число учебных семе s=l стров.
Тогда сам учебный план при описанном представлении удобно задавать п х m матрицей вида Ти = к - Td]= rtd td ... td п Ml l21 lml td td ... td 42 L22 lm2 (2.3) td td ... td In l2n lmn_
Таким образом, УПОП является довольно сложной структурой [30, 39], отражающей распределение академических часов по семестрам для каждой дисциплины образовательной программы. Эта структура характеризуется сравнительно небольшим числом фиксирующих ее констант - чаще всего, лишь двумя: 1) задаваемым ГОС ВПО количеством семестров обучения п; 2) планируемым учебно-методическими службами вуза числом недель в различных семестрах Ns.
Другие параметры УПОП - переменные величины, которые могут при его составлении варьироваться. Однако связаны они при этом довольно жесткими ограничениями, основные из которых следующие: 1) максимальная недельная нагрузка студента (аудиторная) в академических часах zamax 27; 2) ограниченное аттестационными возможностями сессии максимальное количество дисциплин, преподаваемых в семестре 1 ах; 3) минимальное 1 іп и максимальное 1 ах количество часов в неделю преподавания дисциплины dj; 4) требование неразрывности по семестрам фрагментарного планирования дисциплин с большим объемом часов; 5) требование соблюдения логической последовательности прохождения дисциплин в течение всего срока обучения; 6) отсутствие избыточных переносов изучения дисциплины через лет ниє каникулы.
Математическое задание описанных условий определяется конкретными формами представления УПОП в исследовательских и проектных задачах. Они могут быть разными. В данной работе математический формализм задачи выбран из условия удобства применения для проведения исследований используемых алгоритмов.
Эволюционно-генетический алгоритм составления УПОП как объект оптимизации
Данные литературного обзора, проведённого в первой главе, показывают, что результаты оптимизации УПОП с использованием генетического алгоритма сильно зависят от способов реализации всех его составляющих. Для построения эффективного алгоритма необходимо исследовать основные компоненты ЭГА, определить эффективную структуру его составляющих и эффективные количественные значения параметров. Это крайне необходимо в связи с высокой сложностью, нелинейностью, неоднородностью и высокой размерностью УПОП, как оптимизируемой системы. Кроме того, необходимо учитывать неординарность, и, даже, уникальность ЭГМ, разработанной во второй главе. Литературные данные по эффективности тех или иных методов скрещивания, мутации, отбора и т.д., а также данные по рекомендуемым значениям их параметров нельзя считать для этой модели однозначно достоверными.
В связи с этим необходимо рассмотреть структуру решаемой задачи в совокупности с используемым методом, т.е. систему «задача-метод». Такая постановка вопрос связана с тем, что ЭГА, как объект информатизации, представляет собой сложную многокомпонентную структуру со множеством параметров. Изменение способов реализации этапов ЭГА и значений параметров будет оказывать непосредственное влияние на результат оптимизации УПОП. Поэтому решаемую задачу следует рассматривать как совокупность двух взаимосвязанных объектов - «ЭГА-УПОП», и решить вопросы доступные для их исследования и оптимизации.
Во второй главе были рассмотрены основные этапы ЭГА и сформулированы идеи по их модификации. Кроме этого, предложена идея по расширению структуры алгоритма, путем его дополнения механизмом старения особей. Таким образом, для решения задачи построения эффективного алгоритма оптимизации УПОП необходимо выяснить следующие моменты: 1) стоит ли комбинировать стратегии отбора родительских пар, и если да, то в каком соотношении они будут наиболее эффективны, или же следует применять лишь какую-то одну их них; 2) при каких значениях вероятностей мутации особи и гена механизм мутации наиболее эффективен; 3) какое значение поправочного коэффициента следует использовать в операции кроссинговера при вычислении вероятности выбора родителя для наследования гена; 4) из какого диапазона выбирать средний срок жизни особей.
Как известно, решаемая задача имеет довольно большую размерность и решение всего комплекса поставленных вопросов за одно исследование более чем проблематично. Поэтому поставленные проблемы пришлось рассматривать последовательно.
При написании данной диссертационной работы автором не было обнаружено каких-либо сведений о степени важности того или иного этапа ЭГА. Поэтому при определении порядка исследования намеченных вопросов автор руководствовался соображениями трудоемкости проведения экспериментов и принял следующие решения:
Наиболее масштабными являются исследования стратегии отбора родительских пар. В первой главе рассмотрено 6 различных способов её реализации. Даже в том случаи, если исключить из рассмотрения способ случайного отбора, то предстоит исследовать 32 различных сочетания методов и далее решить вопрос об их соотношении. Ожидается, что число экспериментов будет довольно большим, поэтому исследование данного этапа ЭГА было решено проводить первым.
Объём необходимых экспериментов для исследования механизма мутации ожидается гораздо меньший, чем при рассмотрении стратегии отбора особей для скрещивания. В данном исследовании необходимо рассмотреть влияние на эффективность алгоритма только двух факторов - вероятности мутации особи и вероятности мутации гена. На основании этого этап мутации рассматривать вторым.
Наименьшее число экспериментов ожидается при исследовании крос-синговера. Предстоит определить значение лишь одного фактора, поэтому такое исследованию решено проводить вслед за рассмотрением механизма мутации.
Концепция старение особей является новой для теории генетических алгоритмов. Во всяком случаи, при обзоре по теме данной диссертационной работы автором не встречено ни одного упоминания об использовании такого механизма. При исследовании влияния этого этапа требуется выяснить, какое влияния на эффективность алгоритма оказывают значения двух факторов - минимального и максимального срока жизни особи. В виду небольшого ожидаемого объёма эксперимента и того, что данный этап является новым для ЭГА, его решено исследовать последним.
Общая характеристика информационной системы
Процедура формирования учебного плана является достаточно трудоёмкой. Она требует учёта множества параметров, ограничений и высокой концентрации проектировщика. Для упрощения и ускорения выпуска УПОП целесообразно применять специализированные программные средства, автоматизирующие этот процесс [29,36,38,40].
Как было продемонстрировано в обзоре существующих программных решений для планирования обучения в вузе, приведённом в первой главе, на сегодняшний день существует совсем незначительное число подобных программных продуктов. Среди них большинство ориентированы либо на решение только локальных задач планирования обучения [1,3,11,28,48] и не позволяют создавать полноценные учебные планы, либо автоматизация составления УПОП в них сводиться к его контролю на соответствие ограничениям ГОС ВПО и подсчёту итоговых показателей [92]. В условиях, когда появляется всё большее число специальностей и вводиться двухуровневая система образования, этого явно недостаточно. В настоящее время существует высокая потребность в программных средствах, позволяющих в автоматизированном режиме решать весь комплекс задач составления учебных планов, предоставляя при этом пользователю удобный дружественный интерфейс.
В рамках диссертационного исследования разработан программный комплекс автоматизированного проектирования учебных планов PC CAD (Program Complex for Curriculum Automated Designing), который выполняет функции поддержки принятия решения на всех этапах конструирования УПОП. Комплекс PC CAD охватывает весь цикл задач составления УПОП, начиная с опре деления параметров и составления списка дисциплин образовательной программы и заканчивая выпуском регламентируемой отчётности.
Данный программный продукт представляет собой приложение с графическим интерфейсом, работающее в среде Windows. Его архитектура имеет перечисленные ниже особенности.
1) Для хранения данных используется настольная СУБД MS Access. Работа с ней осуществляет посредством технологии доступа к данным ADO [41,47,62,68,77]. Благодаря этому, в случае нехватки ресурсов выбранной СУБД, существует возможность быстрого и «безболезненного» перехода на более мощные серверные СУБД.
2) Сформированные учебные планы сохраняются в файлы формата XML [2,14,43,98,119]. Применение этой технологии делает возможным и их импорт/экспорт, и интеграцию PC CAD с другими приложениями.
3) Разработанная информационная система позволяет передавать данные в Microsoft Excel. Такое взаимодействие осуществляется посредством технологии OLE [47,71,77], Благодаря этому существует возможность экспортировать и табличную форму УПОП, и его структурно-топологическую схемы в электронные книги Microsoft Excel. Это облегчает финальную коррекцию разработанных документов.
Информационно-функциональная структура комплекса Комплекс PC CAD объединяет в себе несколько подсистем, основные из которых следующие:
1) подсистема формирования и редактирования учебных планов специальностей (ПФР УПОП). Является центральным звеном всей информационной системы. Она выполняет множество функций, из которых можно выделить следующие: реализация всей функциональности пользовательского интерфейса для построения и редактирования структурно-топологической схемы УПОП (см. п. 4.2); предоставление интерфейса для наполнения УПОП списком дисциплин и задания необходимых реквизитов; контроль УПОП на его соответствие ограничениям и сигнализация пользователю об их нарушении; сохранение в файлы и загрузка из файлов промежуточных и конечных вариантов УПОП; обмен данными с MS Excel и выпуск печатной отчётности;
2) модуль с программной реализацией генетического алгоритма формирования и оптимизации УПОП (МГА).
3) мастер формирования исходных данных (МФИД) для построения учебного плана. С его помощью можно пошагово, путём последовательного заполнения диалоговых форм, определить все требуемые параметры для составления УПОП (см. п.4.3).
4) подсистема управления базой данной (ПУБД) образовательных стандартов, специальностей и дисциплин (БД СиУД).
Информационные потоки, протекающие между подсистемами PC CAD, продемонстрированы на Рис. 4.1.
Списки дисциплин, образовательные стандарты и другая необходимая информация, заносятся в систему и редактируются при помощи ПУБД, которая реализована в виде отдельного приложения. При составлении нового учебного плана ПФР УПОП запрашивает у мастера формирования исходных данных необходимую информацию. На основании запроса МФИД обращается к базе данных и выбирает из неё нужные сведения. После этого он преобразует их в требуемый формат и передаёт в ПФР УПОП. В ней пользователь либо своими силами, либо воспользовавшись разработанным эволюционно-генетическим алгоритмом, формирует структурно-топологическую схему учебного плана. По завершению процедуры построения УПОП осуществляется экспорт полученного результата в MS Excel, откуда и производиться распечатка всех необходимых форм отчётностей.
