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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


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

Информация:

Тип работы: дипломная работа. Добавлен: 20.08.2012. Сдан: 2011. Страниц: 36. Уникальность по antiplagiat.ru: < 30%

Описание (план):


Оглавление
 ВВЕДЕНИЕ 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]. 
 
 
 
 
 
 
 
 
 
 
 

    ГЕНЕТИЧЕСКИЕ  АЛГОРИТМЫ
      История появления эволюционных алгоритмов
     История эволюционных вычислений началась с  разработки ряда различных независимых  моделей. Основными из них были генетические алгоритмы и классификационные  системы Холланда (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) – другая методика поиска, которая основана скорее на физических, а не биологических процессах. 

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

     НАЧАЛО /* генетический алгоритм */
         Создать начальную популяцию
         Оценить приспособленность каждой особи
         останов := FALSE
         ПОКА  НЕ останов ВЫПОЛНЯТЬ
           НАЧАЛО /* создать популяцию нового поколения */
         ПОВТОРИТЬ (размер_популяции/2) РАЗ
           НАЧАЛО /* цикл воспроизводства */
          Выбрать две особи с высокой приспособленностью из предыдущего поколения для  скрещивания.
          Скрестить выбранные особи и получить двух потомков.
             Оценить приспособленности потомков
             Поместить потомков в новое поколение 
           КОНЕЦ
         ЕСЛИ  популяция сошлась ТО останов := TRUE
         КОНЕЦ
     КОНЕЦ 

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

      Модели  генетических алгоритмов
     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) – это разновидность однородного кроссовера, но в нем к каждому потомку попадает ровно половина битов хромосомы от каждого родителя. Таким образом, модель обладает следующими свойствами:
     - Фиксированный размер популяции.
     - Фиксированная разрядность генов.
     - Перезапуск алгоритма после нахождения решения.
     - Небольшая популяция.
     - Особи для скрещивания разбиваются на пары и скрещиваются при условии существенных отличий.
     Отбор в следующее поколение проводится между родительскими особями  и потомками.  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

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

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

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

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

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

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

     Рисунок 4 – Изменение целевой функции
     с ростом числа параметров задачи 

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

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

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

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

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

      Применение  генетических алгоритмов
     Генетические  алгоритмы в различных формах применились ко многим научным и  техническим проблемам. Они используются при создании других вычислительных структур, например, автоматов или сетей сортировки. В машинном обучении они использовались при проектировании нейронных сетей или управлении роботами. Они также применялись при моделировании развития в различных предметных областях, включая биологические (экология, иммунология и популяционная генетика), социальные (такие как экономика и политические системы) и когнитивные системы.
     Тем не менее, возможно наиболее популярное приложение генетических алгоритмов - оптимизация многопараметрических функций. Многие реальные задачи могут быть сформулированы как поиск оптимального значения, где значение - сложная функция, зависящая от некоторых входных параметров. В некоторых случаях, представляет интерес найти те значения параметров, при которых достигается наилучшее точное значение функции. В других случаях, точный оптимум не требуется - решением может считаться любое значение, которое лучше некоторой заданное величины. В этом случае, генетические алгоритмы - часто наиболее приемлемый метод для поиска "хороших" значений. Сила генетического алгоритма заключена в его способности манипулировать одновременно многими параметрами, эта особенность ГА использовалось в сотнях прикладных программ, включая проектирование самолетов, настройку параметров алгоритмов и поиску устойчивых состояний систем нелинейных дифференциальных уравнений.
     На  практике довольно часто приходится решать задачу размещения разногабаритных электрорадиоэлементов (ЭРЭ) на непрерывном монтажном пространстве. Структура задачи размещения разногабаритных элементов задается посредством ограничений пространства размещения (габариты конкретного корпуса или монтажной платы), элементы размещения, заданные своими габаритами. Принципиального отличия такого рода задачах между объемным и пространственным размещением не существует. Каждый элемент, предназначенный для размещения, представляется установочной площадью, которая задается двумя параметрами: длиной и шириной. Данная задача, относящаяся к классу оптимизационных задач, может быть решена с использованием генетических алгоритмов
     Генетические алгоритмы так же широко используются и в комбинаторных задачах, которые заключаются в переборе всех возможных вариантов решения данной задачи. К таким задачам относят и задачи составления расписания занятий. Для ее решения предложены специализированные ГА и соответствующее программное обеспечение. Особенностью метода решения является представление задачи составления расписания в форме модели задачи о назначении с дополнительными ограничениями. Здесь использование специализированных ГА позволяет автоматизировать процесс составления расписания занятий и добиться повышения его качества.
     Исходными данными для применения ГА являются: учебный план и учебная нагрузка преподавателей (дисциплина; вид занятий; количество часов в неделю; список групп; преподаватель). Каждая ячейка сетки  расписания рассматривается как  исполнитель работ и характеризуется  такими параметрами, как номер недели, день недели, номер ленты, номер аудитории.
     В терминах ГА, хромосома - вариант расписания занятий, а набор расписаний занятий  представляет собой популяцию. Кодировка  хромосомы выполнена одним из вариантов: для каждого преподавателя  отводится часть хромосомы - сетка  расписания, где значением «гена» будет код учебной нагрузки; для  каждого преподавателя отводится  часть хромосомы - вся его учебная  нагрузка, где значением «гена» будет  код ячейки в сетке расписания.
     Хромосомы могут содержать недопустимые значения «генов», при которых одновременно в одной и той же группе могут  проводить занятий разные преподаватели, т.е. популяция может содержать недопустимые решения. Во избежание недопустимых значений «генов» вводится оценка хромосомы fitness-функцией, которая задается суммой «штрафов», определяющихся при декодировании хромосомы. Целью генерации популяции является составление расписание занятий с минимальным значением функции приспособленности.
     Метод автоматизированного составления  расписаний занятий на основе модели задачи о назначении с ограничениями, применением ГА программно реализован и апробирован для отдельных  учебных подразделений ВУЗа. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

    ПРИМЕНЕНИЕ  ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ ДЛЯ ЗАДАЧ СОСТАВЛЕНИЯ  УЧЕБНЫХ ПЛАНОВ
        Учебные планы нового поколения. Общие сведения
     Учебный план по конкретной специальности или  направлению – основной документ, определяющий структуру учебного процесса на факультете, перечень и объемы учебных  дисциплин, последовательность их изучения, названия и продолжительность практик, используемые виды занятий (лекции, лабораторные и практические занятия, семинары и  др.), аттестации, формы контроля и  т.д. Он разрабатывается факультетом  на основе ГОС ВПО и примерного учебного плана по форме, определяемой университетом, и утверждается ректором.
     Учебный план предусматривает:
     -  последовательность изучения дисциплин,  основанную на их преемственности;
     -  рациональное распределение дисциплин  по семестрам с точки зрения  равномерной загруженности студента;
     -    эффективное использование кадрового  и материально-технического потенциала  университета.
     В 2011 году в соответствии с приказом Рособразования № 109 от 10.02.2010 «О задачах  высших учебных заведений по переходу на уровневую систему высшего  профессионального образования» вузы Российской Федерации переходят  на Федеральные государственные  образовательные стандарты третьего поколения (ФГОС-3).
     Принципиальное  отличие новой системы – большой  объем самостоятельной работы. Нынешнему  поколению постоянно приходится переучиваться, поэтому студентов  нужно заранее готовить к быстрому освоению новых программ. Отсюда вытекают и другие особенности двухуровневой системы по сравнению с привычной: более широкая свобода в выборе дисциплин и возможность изучать различные курсы в других вузах.
     Но  главное – это иные цели и результаты обучения. Если «специалитет» предполагал  получение студентом конкретной профессии, то бакалавра готовят  к деятельности в профессиональной сфере. К примеру, если раньше выпускник  педагогического вуза получал диплом по специальности «учитель», то теперь у него в «корочках» появится запись «бакалавр образования». В свою очередь  это даст более широкие возможности  для трудоустройства по окончании  вуза.
     Несмотря  на очевидные преимущества, изменения  влекут и ряд трудностей как для  студентов, так и для преподавателей. Главная проблема для первых –  неготовность учиться «по-новому». Студенты уже привыкли к тому, что  можно «долго раскачиваться», и серьезно берутся за учебу только дважды в  год – во время сессии. Для  будущих бакалавров эта схема  не сработает: набирать баллы здесь  нужно равномерно в течение всего  семестра. Кроме того, нынешним студентам  пока сложно самим делать выбор, им привычнее учиться по заданному  дисциплинарному плану.
     Те  студенты, которые сегодня уже  учатся в вузе, получат образование  по традиционной пятилетней программе  и выйдут из университета дипломированными специалистами. Кроме того, нововведения не коснутся военных, медицинских и  инженерных вузов. 
 
 
 
 
 
 
 

      Формирование  рабочих учебных  планов
     Рабочие учебные планы (РУП) являются основным документом для составления расписания занятий и экзаменационных сессий, организации учебного процесса, расчета  штатов ППС, планирования и выполнения учебной нагрузки преподавателям и  кафедрам, формирования индивидуальных учебных планов студентов по данной программе.
     1. Рабочие учебные планы разрабатываются на основе базовых учебных планов.
     2. Для формирования рабочего учебного плана в первую очередь составляется график учебного процесса.
           Количество недель теоретического обучения, желательно брать кратное 18 недель (т.к. ЗЕТ=36 часам). В разных ФГОСах третьего поколения  объем практик в ЗЕТах различен и колеблется от 9 до 18 ЗЕТ (от 6 до 12 недель) в связи с этим приходится корректировать теоретическое обучение на III и IV курсах, чтобы сохранить минимальное число недель отводимых на каникулы.
     3. Содержания рабочего плана формируется по блокам: общенаучному (М1), профессиональному (М2), практико и научно-исследовательскому (М3).
     4. В графе 1 рабочего учебного указывается номер дисциплины согласно базового учебного плана по блокам дисциплин.
     5. Во второй графе приводится название дисциплины, указывается полное название, сокращения не допускаются.
     6. Формы контроля по семестрам указываются в графе 3-6. В графе 3- экзамены, графа 4 –зачеты, графа 5 – курсовой проект, графа 6 курсовая работа.
     7. Графы 7 и 8 предусматривают сумму часов по дисциплине. Графа 7 – всего по учебному плану, а графа 8- всего по ФГОСу.
     8. В том числе предусматриваются аудиторные занятия – графа 9, контролируемая самостоятельная работа (КСР), графа 10 – это консультации по курсовым проектам и работам, групповые консультации для подготовки к текущему и промежуточному контролю и т.д., графа 11 предусматривает объем самостоятельной работы на каждого студента.
     В сумме гр.9+гр.10+гр.11=гр.7
     9. Распределение по курсам и семестрам формируется в графах с 12 по 43. По каждому курсу распределение идет по семестрам. В семестре предусмотрены следующие виды деятельности (аудиторные):
           - лекции;
           - лабораторные работы;
           - практические занятия;
           - КСР (контролируемая самостоятельная работа).
     Объем аудиторных занятий (лекций, лабораторных и практических работ) не должен превышать 14 часов в неделю и корректируется только, если ФГОС предусматривает  другое число аудиторных занятий.
     10. Особенности организации учебного процесса следующие:
           - каждый семестр должен иметь трудоемкость 20 ЗЕТ, то есть 20 учебных недель соответственно 720 часов;
           - длительность семестра включает в себя недели теоретического обучения, экзаменационные сессии, практики и итоговую аттестацию, сроки проведения практик;
           - на сдачу государственного экзамена отводится одна неделя (2 ЗЕТ);
           - на подготовку квалификационной работы магистра – 4-6 недель (6-9 ЗЕТ);
           - максимальная аудиторная нагрузка в семестре указана в ФГОСе и примерно составляет 14 часов в неделю;
           - максимальная трудоемкость студента в неделю составляет 54 часа (аудиторные + КСР + самостоятельная работа);
           - число экзаменов и зачетов не должно превышать 4. Наличие 2-х недель на экзамены определяет ограничения по числу экзаменов – 3-4 в семестр;
     В РУП предусмотрены три вида самостоятельной  работы  студента:
         -  выполнение курсовых проектов (работ), домашних заданий, рефератов и докладов (плановая самостоятельная работа);
         -  групповые консультации (самостоятельная  контролируемая работа);
         -  самоподготовка (самоконтроль, конспектирование учебных материалов, вынесенных на самостоятельное изучение,  самостоятельное изучение тем, домашняя самостоятельная работа (подготовка к лекциям лабораторным работам и практическим занятиям и т.д.)).
     11.  Количество курсовых проектов (работ) не должно быть более двух в одном семестре. Проведение аудиторных занятий по курсовому проектированию не предусмотрено.
     12.  Если дисциплина завершается выставлением оценки по результатам текущего контроля (дифференцированным зачетом), то назначение часов в неделю для проведения групповых консультаций обязательно. Часы на проведение групповых консультаций по дисциплинам с экзаменом назначаются по усмотрению преподавателя. Часы самоподготовки рассчитываются по остаточному принципу.
     13.  Если дисциплина заканчивается экзаменом, то на подготовку к экзамену, консультацию перед экзаменом  и сдачу экзамена отводится 1 ЗЕТ (36 академических часов в течение трех дней подготовки и одного дня сдачи экзамена). Эти часы вычитаются из общего количества часов самостоятельной работы по дисциплине и не учитываются при заполнении граф  «самостоятельная работа», так как для проведения экзаменов  учебным графиком предусмотрены две недели экзаменационных сессий, не входящие в период теоретического обучения в семестре. 
 

     Примеры расчета часов  в неделю:
     Дисциплина  без экзамена (4 ЗЕТ) в осеннем  семестре (18 учебных недель). 4 ЗЕТ  х 36 час. =144 час.
            144 час. =72 ауд.час. (4 час./нед.) + 72 сам.  часа (4 час./нед.).
     Дисциплина  с экзаменом (4 ЗЕТ) в осеннем семестре (18 учебных недель). 4 ЗЕТ х 36 час. = 144 час.
         144 час. =72 ауд.час. (4 час./нед.) + 36 сам.  часа (2 час./нед.) + 36 экз. часа.
     14.  Закрепленная за дисциплиной учебного плана кафедра указывается в виде кода в графе 44.
     15.  Графа 45 и 46 определяет количество зачетных единиц трудоемкости дисциплины фактически по плану (гр.45) и планируемая по ФГОСу (гр.46).
     16.  По каждому блоку дисциплины М1, М2, М3 подводится итог. Исходя из которого, определяется процент базовых дисциплин, вариативной части и дисциплины по выбору.
     17.  Рабочий учебный план  обсуждается на совете факультета, утверждается протоколом.  Предварительно он визируется ответственным за составление данного плана по кафедре, потенциальным работодателем, подтверждается его подписью и печатью, а также со стороны вуза  зав. кафедрой  ответственным за данное направление  подготовки специалиста и зав. кафедрами ответственными за профильную подготовку, если профиль один, то достаточно одной подписи зав. выпускающей кафедры.
     18.  Проверку рабочего учебного плана осуществляет учебно-методический отдел учебно-методического управления.
     19.  Утверждается рабочий учебный план  ректором университета, что свидетельствуется грифом утверждения на титульном листе с обязательным указанием даты утверждения и печатью.
      Формирование  учебных планов на основе генетических алгоритмов
     Генетические  алгоритмы – относительно новый  приём программирования, который  используется для решения задач, связанных с перебором множества  вариантов. Поскольку количество вариантов  выборки из n элементов равно n!, то задача построения оптимальной в  каком-либо смысле выборки с ростом числа структурных элементов  может оказаться неоправданно трудо- и ресурсоёмкой. Генетические алгоритмы  существенно облегчают такого рода задачу. Между тем эти алгоритмы  предоставляют  новый способ формирования учебных планов (УП) на основе как  количественных, так и качественных критериев дисциплин – актуальности, связности, инновационности и т.д. Особое значение приобретает учёт так  называемых компетенций, представляющих собой заданное социальное требование к образовательной подготовке специалиста, необходимое для его качественной продуктивной деятельности в соответствующей  сфере.
     В роли хромосом начальной и рабочей  популяций выступают хромосомы  – учебные планы, гены которых  представляют собой отдельные дисциплины. В состав генов включаются количественные и контрольные показатели дисциплины, междисциплинарные связи, качественные и компетнтностные характеристики, которые комплексно учитываются  оценочной (fitness) функцией.
     В базовый набор генов входят дисциплины государственного образовательного стандарта  и дисциплины специализации, предлагаемые экспертами – ведущими преподавателями, администраторами учебных подразделений, заказчиками специалистов-выпускников. Размер исходного набора дисциплин  для магистерских УП, как правило, невелик и содержит два-три десятка  экземпляров. Для расширения пространства поиска введен интеллектуальный этап формирования вариативных наборов  для каждой базовой дисциплины, который. из ограниченного базового набора позволит получить широкий спектр исходного материала для последующего отбора и селекции.
     На  этапе создания начальной популяции  из генного набора формируются хромосомы  разной длины, поскольку УП могут  содержать различное количество дисциплин, удовлетворяющих временным  ограничениям. Разная длинна хромосом накладывает специфический отпечаток  на последующие этапы селекции и  отбора элитных хромосом. В алгоритме  предусмотрено два способа мутации  хромосом. Один из них предусматривает  включение в хромосому произвольного  числа n1 новых генов и исключение из неё произвольного числа n2 генов существующих. Величины n1 и n2 случайные и принадлежат диапазону [0, lenchrom/10] , где lenchrom – длина хромосомы в генах. Второй способ мутации подобен процессу формирования вариативных наборов базовых дисциплин и предусматривает изменения количественных и контрольных характеристик произвольного числа генов. При мутации контрольных характеристик они меняют своё значение на противоположное (булевские величины), при мутации временных параметров происходит дискретное изменение количества часов/зетов на величину Nweek – количество недель в семестре учебного плана.
     При работе fitness-функции совокупность количественных и контрольных характеристик всех проверяется на соответствие набору заданных ограничений, таких как общее количество часов/зетов на теоретическое и самостоятельное обучение, минимальное количество часов/зетов для федерального блока дисциплин, соотношения между лекционными и практическими занятиями и т.д. Анализ междисциплинарных связей позволяет учесть ограничения на временные ограничения и число контрольных мероприятий в семестре. В случае если хотя бы одно из ограничений не удовлетворяется, фитнес функция возвращает отрицательное значение, что соответствует непригодности текущей хромосомы. Компетентностные и качественные показатели оказывают решающее воздействие на значение, возвращаемое fitness-функцией, и должны стремиться к максимально возможному значению:
      ;      ;      ,
     где {ki} – множество неповторяющихся компетенций;  Nk – количество компетенций в УП специальности; ND – число дисциплин в УП; Dkij  – доля  i-ой компетенции в j-ой дисциплине, %; Dqj  – доля l-го качественного показателя в j-ой дисциплине,  (%); Nq – количество качественных показателей в j-ой дисциплине. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

        Соответствие терминов биологии и предметной области
     Соответствие  биологических терминов – терминов предметной области  представлено в Таблице 1.
 

     
     Таблица 1.
     
Ген   
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Хромосома 
 
 
 
 

Популяции
Дисциплина 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Учебный план, состоящий  из набора переменных дисциплин 
 
 
 

Набор учебных  планов
     
Тип: TDisc = record Переменные:
key: integer - уникальный номер
number: integer - номер в вариативном наборе
name : string[60] - наименование дисциплины
code : string[7] - шифр
kind1: string[6] – общенаучная/ профессиональная
kind2: string[8] – базовая/ вариативная
kind3: string[7] – вариативная-обязательная/вариативная по выбору            
h_lection :integer – часов лекций
h_laborat : integer – часов лабораторных работ
h_practical : integer – часов практических работ
h_all: integer – всего часов
h_auditorium: integer – часов аудиторных работ                 
examination: Boolean – наличие экзамена
final_test: boolean– наличие зачета
yearly_project : boolean– наличие курсового проекта
yearly_work : boolean– наличие курсовой работы
homework : boolean–наличие домашнего задания
referat :boolean– наличие выполнение реферата
Тип: TChrom =  record 

Переменные:
length:integer – длинна дисциплины
disc: array [1..MAX_NUM_DISC_IN_CHROM] of TDisc
fitness: real
Тип: TChrom 

Переменные:
TPopulation=array [1..NUM_CHROM_IN_POPUL] of TChrom
 
 

     
    ПРОГРАММНАЯ РЕАЛИЗАЦИЯ ГЕНЕТИЧЕСКОГО  АЛГОРИТМА ДЛЯ  ГЕНЕРАЦИИ УЧЕБНЫХ ПЛАНОВ
        Выбор языка программирования. 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 
 
 
 

 


      Функциональная схема работы программы
     Общая схема работы ГА представлена на рисунке 7. Случайным образом создаётся множество генотипов начальной популяции. Они оцениваются с использованием «функции приспособленности», в результате чего с каждым генотипом ассоциируется определённое значение («приспособленность»), которое определяет насколько хорошо фенотип, им описываемый, решает поставленную задачу.
     Из  полученного множества решений («поколения») с учётом значения «приспособленности»  выбираются решения (обычно лучшие особи  имеют большую вероятность быть выбранными), к которым применяются  «генетические операторы» (в большинстве  случаев «скрещивание» — crossover и «мутация» — mutation), результатом чего является получение новых решений. Для них также вычисляется значение приспособленности, и затем производится отбор («селекция») лучших решений в следующее поколение.
     Этот  набор действий повторяется итеративно, так моделируется «эволюционный  процесс», продолжающийся несколько  жизненных циклов (поколений), пока не будет выполнен критерий остановки алгоритма. Таким критерием может быть:
     - нахождение глобального, либо оптимального решения;
     - исчерпание числа поколений, отпущенных на эволюцию;
     - исчерпание времени, отпущенного на эволюцию.
     Генетические  алгоритмы служат, главным образом, для поиска решений в многомерных  пространствах поиска.
     Таким образом, можно выделить следующие  этапы генетического алгоритма:
    Задать целевую функцию (приспособленности) для особей популяции
    Создать начальную популяцию (Начало цикла)
    Размножение (скрещивание)
    Мутирование
    Вычислить значение целевой функции для всех особей
    Формирование нового поколения (селекция)
    Если выполняются условия останова, то (конец цикла), иначе (начало цикла).

 
     Рисунок 7 – Общая схема работы ГА
      Создание начальной популяции
     Перед первым шагом нужно случайным  образом создать начальную популяцию; даже если она окажется совершенно неконкурентоспособной, генетический алгоритм все равно достаточно быстро переведет ее в жизнеспособную популяцию. Таким образом, на первом шаге можно  особенно не стараться сделать слишком  уж приспособленных особей, достаточно, чтобы они соответствовали формату  особей популяции, и на них можно  было подсчитать функцию приспособленности (Fitness). Итогом первого шага является популяция H, состоящая из N особей.
      Размножение (Скрещивание)
     Размножение в генетических алгоритмах обычно половое – чтобы произвести потомка, нужны несколько родителей, обычно два.
     Размножение в разных алгоритмах определяется по-разному – оно, конечно, зависит от представления данных. Главное требование к размножению – чтобы потомок или потомки имели возможность унаследовать черты обоих родителей, «смешав» их каким-либо способом.
     Главной проблемой многих генетических алгоритмов – недостаток разнообразия (diversity) в особях. Достаточно быстро выделяется один-единственный генотип, который представляет собой локальный максимум, а затем все элементы популяции проигрывают ему отбор, и вся популяция «забивается» копиями этой особи. Есть разные способы борьбы с таким нежелательным эффектом; один из них – выбор для размножения не самых приспособленных, но вообще всех особей. 

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

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

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

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

 

     
       
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     Рисунок 8 – Сема формирования вариативного набора одной дисциплины
      Описание  констант и переменных программы
     Описание  глобальных констант, типов и переменных программы собраны в модуле UnitConstTyteData и описаны в Таблице 2.
     Таблица 2
     
Название Тип Назначение
 
MAX_NUM_DISC_IN_CHROM MIN_NUM_DISC_IN_CHROM
MAX_NUM_DISC
MAX_NUM_COMPETENCE
NUM_CHROM_IN_POPUL 
NUM_CHROM_TO_CROSS
NUM_PAIRS
NUM_SEMESTR
NUM_YEAR
HOURS_ALL
HOURS_PRAC
HOURS_WORC
HOURS_EXAM  

disc
variation
real_size_genotype
population
new_chrom
new_chrom_numbers
children
select1_type
select2_type
cross_type
Константы integer
integer
integer
integer
integer
integer
integer
integer
integer
integer
integer
integer
integer
Переменные
TDisc
Tvariation
Integer
TIntermediate
TIntermediateNumbers
TPair
TChildren
integer
integer
integer
 
Максимальное число дисциплин в хромосоме; Минимальное число дисциплин в хромосоме;
Число генов; 
Уровень компетенции;
Число хромосом в популяции;
Число особей для скрещивания;
Число пар для скрещивания;
Количество семестров;
Количество лет обучения;
Всего часов учебного плана;
Часов учебного плана на все практики;
Часы на выпускную работу;
и т.д.................


Перейти к полному тексту работы


Скачать работу с онлайн повышением уникальности до 90% по antiplagiat.ru, etxt.ru или advego.ru


Смотреть полный текст работы бесплатно


Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.