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

Оглавление

 ВВЕДЕНИЕ 3

 1. ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ 7

1.1. История появления эволюционных алгоритмов 7

1.2. Общие сведения о ГА 9

1.3. Модели генетических алгоритмов 13

1.4. Другие пути решения задач оптимизации 17

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

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

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

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

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

2.3. Формирование учебных планов на основе генетических алгоритмов 31

2.4. Соответствие терминов биологии и предметной области 34

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

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

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

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

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

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

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

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

 ЗАКЛЮЧЕНИЕ 51

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

 Приложение 1 53

 Приложение 2 63

ВВЕДЕНИЕ

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

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

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

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

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

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

     Генетические  алгоритмы являются достаточно мощным средством и могут с успехом  применяться для широкого класса прикладных задач, включая те, которые  трудно, а иногда и вовсе невозможно, решить другими методам. Однако, они, как и другие методы эволюционных вычислений, не гарантирует обнаружения  глобального решения за полиномиальное время. Генетические алгоритмы не гарантируют  и того, что глобальное решение  будет найдено, но они хороши для  поиска "достаточно хорошего" решения  задачи "достаточно быстро". Там, где задача может быть решена специальными методам, почти всегда такие методы будут эффективнее и в быстродействии и в точность найденных решений. Главным же преимуществом генетических алгоритмов является то, что они  могут применяться даже на сложных  задачах, там, где не существует никаких  специальных методов. Даже там, где  хорошо работаю существующие методики, можно достигнуть улучшения сочетанием их с генетическими алгоритмами [2]. 
 
 
 
 
 
 
 
 
 
 
 

1. ГЕНЕТИЧЕСКИЕ  АЛГОРИТМЫ

1. История появления эволюционных алгоритмов

     История эволюционных вычислений началась с  разработки ряда различных независимых  моделей. Основными из них были генетические алгоритмы и классификационные  системы Холланда (Holland), опубликованные в начале 60-х годов и получившие всеобщее признание после выхода в свет книги, ставшей классикой в этой области, - "Адаптация в естественных и искусственных системах" ("Adaptation in Natural and Artifical Systems", 1975). В 70-х годах в рамках теории случайного поиска Растригиным Л.А. был предложен ряд алгоритмов, использующих идей бионического поведения особей. Развитие этих идей нашло отражение в цикле работ Букатовой И.Л. по эволюционному моделированию. Развивая идеи Цетлина М.Л. о целесообразном и оптимальном поведении стохастических автоматов, Неймарк Ю.И. предложил осуществлять поиск глобального экстремума на основе коллектива независимых автоматов, моделирующих процессы развития и элиминации особей. Большой вклад в развитие эволюционного программирования внесли Фогел (Fogel) и Уолш (Walsh). Несмотря на разницу в подходах, каждая из этих "школ" взяла за основу ряд принципов, существующих в природе, и упростила их до такой степени, чтобы их можно было реализовать на компьютере.

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

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

     На практике нельзя разделить эти вещи так строго. Эти категории - составляют два полюса, между которыми лежат различные вычислительные системы. Ближе к первому полюсу – эволюционные алгоритмы, такие как Эволюционное Программирование (Evolutionary Programming), Генетические Алгоритмы (Genetic Algorithms) и Эволюционные Стратегии (Evolution Strategies). Ближе ко второму полюсу – системы, которые могут быть классифицированы как Искусственная Жизнь (Artificial Life).

     Эволюция биологических систем не единственный "источник вдохновения" создателей новых методов, моделирующих природные процессы. Нейронные сети (neural networks), например, основаны на моделировании поведения нейронов в мозге. Они могут использоваться для ряда задач классификации, например, задачи распознавания образов, машинного обучения, обработки изображений и др. Область их приложения частично перекрывается со сферой применения ГА. Моделируемый отжиг (simulated annealing) – другая методика поиска, которая основана скорее на физических, а не биологических процессах. 

2. Общие сведения о ГА

     Генетические  алгоритмы - адаптивные методы поиска, которые в последнее время часто используются для решения задач функциональной оптимизации. Они основаны на генетических процессах биологических организмов: биологические популяции развиваются в течении нескольких поколений, подчиняясь законам естественного отбора и по принципу "выживает наиболее приспособленный" (survival of the fittest), открытому Чарльзом Дарвином. Подражая этому процессу генетические алгоритмы способны "развивать" решения реальных задач, если те соответствующим образом закодированы. Например, ГА могут использоваться, чтобы проектировать структуры моста, для поиска максимального отношения прочности/веса, или определять наименее расточительное размещение для нарезки форм из ткани. Они могут также использоваться для интерактивного управления процессом, например на химическом заводе, или балансировании загрузки на многопроцессорном компьютере.