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

 

 

     

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

1.   Выбор языка программирования. Pascal ABC

     Система Pascal ABC  предназначена для обучения программированию на языке Паскаль  и ориентирована на школьников и  студентов.

     Эта система призвана осуществить плавный  переход от простейших программ к  модульному, объектно-ориентированному, событийному и компонентному  программированию. Многие концепции  в Pascal ABC сознательно упрощены, что  позволяет использовать их на более  ранних этапах обучения. Модуль графики  обходится без объектов, хотя его  возможности практически совпадают  с графическими возможностями Borland Delphi.

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

       Компилятор Pascal ABC не генерирует  исполняемый код в виде .exe-файла,  а создает в результате компиляции  дерево программы в памяти, которое  затем выполняется с помощью  встроенного интерпретатора.

       В систему Pascal ABC интегрирован  электронный задачник Programming Taskbook (автор  М.Э.Абрамян), содержащий 1000 задач разного  уровня сложности и охватывающий  все основные разделы базового  курса программирования: от скалярных  типов и управляющих операторов  до составных структур данных, рекурсивных алгоритмов и указателей. Электронный задачник обеспечивает генерацию исходных данных для каждого задания, проверку правильности решения, а также ведение протокола выполнения заданий. Использование электронного задачника существенно ускоряет процесс выполнения заданий, так как избавляет учащегося от дополнительных усилий по организации ввода-вывода [4].

     Язык  программирования Pascal ABC был выбран в качестве инструментального средства, так как он позволяет снять ограничение на размер сегмента данных объёмом 64 кБ, как это имеет место в системах программирования под MS DOS.

     По  предварительным оценкам объём  данных ГА будет значительно превышать указанные 64кБ, поскольку один УП (хромосома) будет представлять собой совокупность примерно 15 дисциплин (генов), где каждая дисциплина занимает порядка 120 байт.

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

     Схема генерации дисциплины представлена в п. 3.4 
 
 
 

 

2. Функциональная схема работы программы

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

     Из  полученного множества решений («поколения») с учётом значения «приспособленности»  выбираются решения (обычно лучшие особи  имеют большую вероятность быть выбранными), к которым применяются  «генетические операторы» (в большинстве  случаев «скрещивание» — crossover и «мутация» — mutation), результатом чего является получение новых решений. Для них также вычисляется значение приспособленности, и затем производится отбор («селекция») лучших решений в следующее поколение.

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

     - нахождение глобального, либо оптимального решения;

     - исчерпание числа поколений, отпущенных на эволюцию;

     - исчерпание времени, отпущенного на эволюцию.

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

     Таким образом, можно выделить следующие  этапы генетического алгоритма:

1. Задать целевую функцию (приспособленности) для особей популяции
2. Создать начальную популяцию (Начало цикла)
3. Размножение (скрещивание)
4. Мутирование
5. Вычислить значение целевой функции для всех особей
6. Формирование нового поколения (селекция)
7. Если выполняются условия останова, то (конец цикла), иначе (начало цикла).

 

     Рисунок 7 – Общая схема работы ГА

1. Создание начальной популяции

     Перед первым шагом нужно случайным  образом создать начальную популяцию; даже если она окажется совершенно неконкурентоспособной, генетический алгоритм все равно достаточно быстро переведет ее в жизнеспособную популяцию. Таким образом, на первом шаге можно  особенно не стараться сделать слишком  уж приспособленных особей, достаточно, чтобы они соответствовали формату  особей популяции, и на них можно  было подсчитать функцию приспособленности (Fitness). Итогом первого шага является популяция H, состоящая из N особей.

2. Размножение (Скрещивание)

     Размножение в генетических алгоритмах обычно половое – чтобы произвести потомка, нужны несколько родителей, обычно два.

     Размножение в разных алгоритмах определяется по-разному – оно, конечно, зависит от представления данных. Главное требование к размножению – чтобы потомок или потомки имели возможность унаследовать черты обоих родителей, «смешав» их каким-либо способом.

     Главной проблемой многих генетических алгоритмов – недостаток разнообразия (diversity) в особях. Достаточно быстро выделяется один-единственный генотип, который представляет собой локальный максимум, а затем все элементы популяции проигрывают ему отбор, и вся популяция «забивается» копиями этой особи. Есть разные способы борьбы с таким нежелательным эффектом; один из них – выбор для размножения не самых приспособленных, но вообще всех особей. 

3. Мутации

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

4. Отбор

     На  этапе отбора нужно из всей популяции  выбрать определенную ее долю, которая  останется «в живых» на этом этапе  эволюции. Есть разные способы проводить  отбор. Вероятность выживания особи h должна зависеть от значения функции  приспособленности Fitness(h). Сама доля выживших s обычно является параметром генетического  алгоритма, и ее просто задают заранее. По итогам отбора из N особей популяции H должны остаться sN особей, которые  войдут в итоговую популяцию H'. Остальные  особи погибают. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

3. Описание fitness-функции

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

      - общее количество часов учебного плана;

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

      - число  экзаменов в семестре и в целом за период обучения;

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

      - число курсовых проектов в семестре и в целом за период обучения;

      - соотношение аудиторной и самостоятельной  работы;

      - число аудиторных часов в  неделю

      - и т.д.

     Эти показатели определены в Федеральном  государственный образовательном  стандарте для каждого направления  магистратуры.

      Кроме того, в fitness-функции осуществляется проверка на наличие повторяющихся дисциплин.

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

 

     Рисунок 9 – Схема алгоритма fitness-функции 

4. Генерация вариативных наборов

     Успешность  работы ГА определяется большим разнообразием «генетического материала».  Под генетическим материалом в нашем случае будем понимать наличие различных вариантов представления одной и той же дисциплины (гена).

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

     Процедура генерации вариантов базовой  дисциплины предполагает дискретное изменение  количественных и контрольных характеристик  дисциплины. К количественным характеристикам относятся число часов лекций, практических и лабораторных работ, самостоятельная работа студентов, контрольные характеристики подразумевают  наличие или отсутствие экзаменов, зачетов, рефератов, курсовых и т. п. Так, в данном варианте формирования генотипа дисциплины,  генерирование вначале ведется по зачету, экзамену, либо наличию их обоих. Далее каждая из полученных дисциплин генерируется по количеству часов 18, 36 или 54. Причем в программе допускается варьирование: 18 либо 36 часов, затем 36, 18 или 54 часа и 54 либо 36 часов. Затем получившиеся новые дисциплины делятся по наличию лекций, лабораторных и практических занятий, а каждая из них уже по реферату, домашнему заданию, курсовой работе или курсовому проекту. Таким образом, из ограниченного базового набора можно получить широкий спектр исходного материала для работы генетического алгоритма.

       Вид формирования одной дисциплины представлен на рисунке 8.  

 

     

       
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     Рисунок 8 – Сема формирования вариативного набора одной дисциплины

5. Описание  констант и переменных программы