Составление учебных планов на основе генетических алгоритмов

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

     Рисунок 3 – Метод градиентного спуска 

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

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

     Рисунок 4 – Изменение целевой функции

     с ростом числа параметров задачи 

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

     Рисунок 5 – Зависимость точности

     расчетов  от времени 

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

     Рисунок 6 – Эффективность алгоритмов 

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

5. Применение  генетических алгоритмов

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

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

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

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

     Исходными данными для применения ГА являются: учебный план и учебная нагрузка преподавателей (дисциплина; вид занятий; количество часов в неделю; список групп; преподаватель). Каждая ячейка сетки  расписания рассматривается как  исполнитель работ и характеризуется  такими параметрами, как номер недели, день недели, номер ленты, номер аудитории.

     В терминах ГА, хромосома - вариант расписания занятий, а набор расписаний занятий  представляет собой популяцию. Кодировка  хромосомы выполнена одним из вариантов: для каждого преподавателя  отводится часть хромосомы - сетка  расписания, где значением «гена» будет код учебной нагрузки; для  каждого преподавателя отводится  часть хромосомы - вся его учебная  нагрузка, где значением «гена» будет  код ячейки в сетке расписания.

     Хромосомы могут содержать недопустимые значения «генов», при которых одновременно в одной и той же группе могут  проводить занятий разные преподаватели, т.е. популяция может содержать недопустимые решения. Во избежание недопустимых значений «генов» вводится оценка хромосомы fitness-функцией, которая задается суммой «штрафов», определяющихся при декодировании хромосомы. Целью генерации популяции является составление расписание занятий с минимальным значением функции приспособленности.

     Метод автоматизированного составления  расписаний занятий на основе модели задачи о назначении с ограничениями, применением ГА программно реализован и апробирован для отдельных  учебных подразделений ВУЗа. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

     Целью предлагаемой работы была разработка реально действующих компьютерных программ, базирующихся на генетических алгоритмах. Таковой задачей стала  разработка формирования учебных планов (УП). Проблема формирования УП является крайне важной, поскольку при составлении расписания занятий приходится постоянно подстраиваться под преподавателей различных факультетов ЮРГТУ, что приводит к необходимости частой смены расписания и делает невозможным использование «хорошего» расписания. При этом задача перебора возможных вариантов должна быть оптимизирована по многим параметрам: непересечению пар одного преподавателя в разных классах, нежелательность включения подряд однородных предметов, ограниченные возможности аудиторного фонда также накладывают свои ограничения и т.д. Решение такой задачи традиционным способом весьма трудоёмко.

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

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

2. ПРИМЕНЕНИЕ  ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ ДЛЯ ЗАДАЧ СОСТАВЛЕНИЯ  УЧЕБНЫХ ПЛАНОВ

1.   Учебные планы нового поколения. Общие сведения

     Учебный план по конкретной специальности или  направлению – основной документ, определяющий структуру учебного процесса на факультете, перечень и объемы учебных  дисциплин, последовательность их изучения, названия и продолжительность практик, используемые виды занятий (лекции, лабораторные и практические занятия, семинары и  др.), аттестации, формы контроля и  т.д. Он разрабатывается факультетом  на основе ГОС ВПО и примерного учебного плана по форме, определяемой университетом, и утверждается ректором.

     Учебный план предусматривает:

     -  последовательность изучения дисциплин,  основанную на их преемственности;

     -  рациональное распределение дисциплин  по семестрам с точки зрения  равномерной загруженности студента;

     -    эффективное использование кадрового  и материально-технического потенциала  университета.

     В 2011 году в соответствии с приказом Рособразования № 109 от 10.02.2010 «О задачах  высших учебных заведений по переходу на уровневую систему высшего  профессионального образования» вузы Российской Федерации переходят  на Федеральные государственные  образовательные стандарты третьего поколения (ФГОС-3).

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

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

     Несмотря  на очевидные преимущества, изменения  влекут и ряд трудностей как для  студентов, так и для преподавателей. Главная проблема для первых –  неготовность учиться «по-новому». Студенты уже привыкли к тому, что  можно «долго раскачиваться», и серьезно берутся за учебу только дважды в  год – во время сессии. Для  будущих бакалавров эта схема  не сработает: набирать баллы здесь  нужно равномерно в течение всего  семестра. Кроме того, нынешним студентам  пока сложно самим делать выбор, им привычнее учиться по заданному  дисциплинарному плану.

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

2. Формирование  рабочих учебных  планов

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

     1. Рабочие учебные планы разрабатываются на основе базовых учебных планов.

     2. Для формирования рабочего учебного плана в первую очередь составляется график учебного процесса.

           Количество недель теоретического обучения, желательно брать кратное 18 недель (т.к. ЗЕТ=36 часам). В разных ФГОСах третьего поколения  объем практик в ЗЕТах различен и колеблется от 9 до 18 ЗЕТ (от 6 до 12 недель) в связи с этим приходится корректировать теоретическое обучение на III и IV курсах, чтобы сохранить минимальное число недель отводимых на каникулы.

     3. Содержания рабочего плана формируется по блокам: общенаучному (М1), профессиональному (М2), практико и научно-исследовательскому (М3).