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

Оглавление

 ВВЕДЕНИЕ 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), открытому Чарльзом Дарвином. Подражая этому процессу генетические алгоритмы способны "развивать" решения реальных задач, если те соответствующим образом закодированы. Например, ГА могут использоваться, чтобы проектировать структуры моста, для поиска максимального отношения прочности/веса, или определять наименее расточительное размещение для нарезки форм из ткани. Они могут также использоваться для интерактивного управления процессом, например на химическом заводе, или балансировании загрузки на многопроцессорном компьютере.

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

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

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

     Имеются много способов реализации идеи биологической  эволюции в рамках ГА. Традиционным считается ГА, представленный на схеме:  

     НАЧАЛО /* генетический алгоритм */

     Создать начальную популяцию

     Оценить приспособленность каждой особи

     останов := FALSE

     ПОКА  НЕ останов ВЫПОЛНЯТЬ

     НАЧАЛО /* создать популяцию нового поколения */

     ПОВТОРИТЬ (размер_популяции/2) РАЗ

     НАЧАЛО /* цикл воспроизводства */

Выбрать две особи с высокой приспособленностью из предыдущего поколения для  скрещивания.

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

     Оценить приспособленности потомков

     Поместить потомков в новое поколение 

     КОНЕЦ

     ЕСЛИ  популяция сошлась ТО останов := TRUE

     КОНЕЦ

     КОНЕЦ 

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

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

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

     1. Canonical GA (J. Holland)

     Данная  модель алгоритма является классической. Она была предложена Джоном Холландом  в его знаменитой работе "Адаптация  в природных и исусственных средах" (1975). Часто можно встретить описание простого ГА (Simple GA, D. Goldberg), он отличается от канонического тем, что использует либо рулеточный, либо турнирный отбор. Модель канонического ГА имеет следующие характеристики:

     - Фиксированный размер популяции.

     - Фиксированная разрядность генов.

     - Пропорциональный отбор.

     - Особи для скрещивания выбираются случайным образом.

     - Одноточечный кроссовер и одноточечная мутация.

     Следующее поколение формируется из потомков текущего поколения без "элитизма". Потомки занимают места своих  родителей.

     2. Genitor (D. Whitley)

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

     - Фиксированный размер популяции.

     - Фиксированная разрядность генов.

     - Особи для скрещивания выбираются случайным образом.

     - Ограничений на тип кроссовера и мутации нет.

     В результате скрещивания особей получается один потомок, который занимает место  наименее приспособленной особи.

     3. Hybrid algorithm (L. "Dave" Davis)

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

     - Фиксированный размер популяции.

     - Фиксированная разрядность генов.

     - Любые комбинации стратегий отбора и формирования следующего поколения

     - Ограничений на тип кроссовера и мутации нет.

     ГА  применяется на начальном этапе, а затем в работу включается классический метод оптимизации.

     4. Island Model GA

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

     - Наличие нескольких популяций, как правило, одинакового фиксированного размера.

     - Фиксированная разрядность генов.

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

     Случайный обмен особями между "островами". Если миграция будет слишком активной, то особенности островной модели будут сглажены, и она будет  не очень сильно отличаться от моделей  ГА без параллелизма.

     5. CHC (Eshelman)

     CHC расшифровывается как Cross-population selection, Heterogenous recombination and Cataclysmic mutation. Данный алгоритм довольно быстро сходится из-за того, что в нем нет мутаций, используются популяции небольшого размера, и отбор особей в следующее поколение ведется и между родительскими особями, и между их потомками. В силу этого после нахождения некоторого решения алгоритм перезапускается, причем лучшая особь копируется в новую популяцию, а оставшиеся особи подвергаются сильной мутации (мутирует примерно треть битов в хромосоме) существующих и поиск повторяется. Еще одной специфичной чертой является стратегия скрещивания: все особи разбиваются на пары, причем скрещиваются только те пары, в которых хромосомы особей существенно различны (хэммингово расстояние больше некоторого порогового плюс возможны ограничения на минимальное расстояние между крайними различающимися битами). При скрещивании используется так называемый HUX-оператор (Half Uniform Crossover) – это разновидность однородного кроссовера, но в нем к каждому потомку попадает ровно половина битов хромосомы от каждого родителя. Таким образом, модель обладает следующими свойствами:

     - Фиксированный размер популяции.

     - Фиксированная разрядность генов.

     - Перезапуск алгоритма после нахождения решения.

     - Небольшая популяция.

     - Особи для скрещивания разбиваются на пары и скрещиваются при условии существенных отличий.

     Отбор в следующее поколение проводится между родительскими особями  и потомками.  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

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

     Рассмотрим  достоинства и недостатки стандартных  и генетических методов на примере  классической задачи коммивояжера (TSP - travelling salesman problem). Суть задачи состоит  в том, чтобы найти кратчайший замкнутый путь обхода нескольких городов, заданных своими координатами (рисунок 1). Оказывается, что уже для 30 городов поиск оптимального пути представляет собой сложную задачу, побудившую развитие различных новых методов (в том числе нейросетей и генетических алгоритмов).

     Рисунок 1 – Кратчайший путь 

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

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

     Рисунок 2 – Переборный метод 

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