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

ign="justify">     Описание  глобальных констант, типов и переменных программы собраны в модуле UnitConstTyteData и описаны в Таблице 2.

     Таблица 2

     

 

     

6. Описание  функций программы

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

     Таблица 3

     

 

7. Результат работы программы

     Для работы программы были определены двенадцать дисциплин, представленные на рисунке 10.

       
 
 
 
 

     Рисунок 10 – Исходный файл с дисциплинами 

     На  базе каждой из двенадцати дисциплин  были сформированы вариативные наборы, содержащие от 120 до 240 экземпляров (Рисунок 11) . Пример файла вариативного набора дисциплин представлен в Приложении 2. 

     

     Рисунок 11 – Вариативные наборы дисциплин

     Затем из полученных вариативных наборов дисциплин были сгенерирована популяция из 200  «плохих» УП с fitness-функции не выше 20 баллов.

     После окончания работы ГА были получены восемь УП с максимальным значением fitness-функции (120 баллов) за 896 449 циклов. Было проведено десять экспериментов и из «УП-победителей» были выбраны наиболее “полезные” и был составлен учебный план занятий (рисунок 12).

       
 
 
 
 
 
 
 

     Рисунок 12 – Учебный план занятия 
 
 
 
 
 
 
 
 

ЗАКЛЮЧЕНИЕ

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

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

     Представленный  алгоритм использовался для формирования ряда магистерских учебных планов кафедры  «Электронных вычислительных машин»  Южно-Российского Государственного Технического Университета. 

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

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

Список  используемой литературы

1. Вентцель  Е.С. «Исследование операций», - М.: 1972 г.
2. Гальцына О.Л., Попов И.И.   «Основы алгоритмизации и

программирования».

3. Грешилов А.А.  «Как принять наилучшее решение в реальных

условиях», - М.: 1991 г., стр. 164-170

4. Корнеев В.В., Гареев А.Ф. «Базы данных. Интеллектуальная обработка

данных», М.: 2001г., стр. 220

5. Коршунов Ю.М. «Математические основы кибернетики. Для студентов

вузов», - М.: 1987 г., стр. 67-89

6. Леонов О.И.   «Теория графов».
7. Электронные источники:

«Генетические алгоритмы по-русски» http://www.chat.ru/~saisa

«Нейропроект. Аналитические технологии XXI века» http://www.neuroproject.ru

«Научное издательство ТВП» http://www.tvp.ru/mathem3.htm

«Факультет вычислительной математики и кибернетики МГУ (ВМиК)» http://cmc.cs.msu.su/labs/lvk/materials/tez_sapr99_1.html

«Neural Bench Development» http://www.neuralbench.ru/rus/theory/genetic.htm «Журнал "Автоматизация Проектирования"» http://www.opensystems.ru/ap/1999/01/08.htm 
 
 
 
 
 
 

Приложение 1

Листинг основной программы 

program GenAlg;

uses crt, UnitConstTyteData, UnitReadWriteCopy, UnitVariation; 

begin

     clrscr;

     randomize;

     filename:='discsau.txt';

     num_weeks:=NUM_WEEK; - способ отбора хромосом для скрещивания

cross_type:=1; - способ скрещивания: 1 - одноточечный

     mutation_probability:=5;   - вероятность мутации

     select2_type:=2; - способ выбора хромосом после скрещивания 

   GenerateGenotype;  - сгенерировать генотип - массив genotype

     GeneratePopulation; - создать популяцию - массив population

     count:=0;

     while (count<100) do

     begin

     inc(count);

        case select1_type of

1: IntermediatePopulationRnd; - отобрать из популяции особи для

скрещивания

2: IntermediatePopulationElit; - отобрать из популяции особи для скрещивания

3: IntermediatePopulationRoulete; - отобрать из популяции особи для скрещивания

     end;

     MakePairsToCross;  - составить всевозможные пары для скрещивания

     case cross_type of

     1:   Crossing1;   - одноточечное скрещивание хромосом

     2:   Crossing2;   - двухточечное скрещивание хромосом

     end;

     if (count mod mutation_probability) = 0 then    - если прошло 100 циклов

     begin

     Mutation1;

     end;

{отбор  особей после скрещивания  для записи в  популяцию в количестве NUM_CHROM_TO_CROSS}

     case select2_type of

     1:   ChildrenRnd;   - случайный выбор потомков

     2:   ChildrenElit;    - отбор элитных потомков

3: ChildrenParentElit;  - отбор элитных особей из множества родителей и детей

     end; 

     write('цикл ',count,': ');

     for i:=1 to NUM_CHROM_TO_CROSS do

     write(new_chrom[i].fitness:5:2,' ');

     {удалить  родителей и поместить  отобранные особи  в популяцию}

     ChangePopulation;

     FitnessPopulation;

      end;