Применение метода моделируемого отжига к задаче составления школьного расписания

Содержание

Введение…………………………………………………………………………………………………………….3

   Цель  курсовой работы………………………………………………………………………………………..4

   Постановка  задач курсовой работы…………………………………………………………………..5

   Реализация  задач курсовой работы

                        Задача 1)………………………………………………………………………………………….6

                        Задача 2)………………………………………………………………………………………….20

                        Задача 3)………………………………………………………………………………………….23

                        Задача 4)………………………………………………………………………………………….26

   Заключение……………………………………………………………………………………………………………29

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

    Приложения…………………………………………………………………………………………………………..31 
 
 
 
 
 
 
 
 
 
 

Введение

      Программа, выбранная мною для реализации в  качестве курсовой работы – программа, генерирующая расписание для школы. Подобных программ написано довольно много, но ни одна из них просто не может  удовлетворять всем параметрам и  нюансам, которые необходимо учесть при составлении расписания в  каждой конкретной школе. Ведь какой-то учитель любит приходить пораньше на работу, и уходить пораньше. Другой лучше придет попозже, третьему удобно работать с окнами, потому что в это время он проверяет тетради…. К тому же в каждой школе есть свои особенности: факультативы, коррекционные классы, своя нагрузка…. Все невозможно учесть. Моя мама работает учителем в средней школе, и не раз мне приходилось слышать от нее недовольства по поводу составленного расписания. Именно поэтому у меня возникла идея написать программу, генерирующую расписание для конкретной школы – школы №5, в которой я училась.  
 
 
 
 
 
 
 
 
 
 
 
 

Цель  курсовой работы

      Разработать программу, позволяющую максимально автоматизировать трудоемкий процесс составления школьного расписания, применяя метод моделируемого отжига.  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Постановка  задач курсовой работы

1. Сбор и анализ информации, которую необходимо учитывать при составлении расписания. Изучение необходимого для написания программы материала.
2. Составление реляционной схемы данных.
3. Разработка программы и удобного пользовательского интерфейса.
4. Обзор уже существующих программ, генерирующих школьное расписание.

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Реализация  задач курсовой работы

1. Первая задача на пути к реализации проекта – сбор всевозможной информации по теме курсовой работы. Так как программа составляется для конкретной школы, то и информацию я естественно искала в этой школе. Сначала я поговорила с мамой, потом с завучем, занимающимся составлением расписания в средней школе №5. Я изучила множество документов и материалов, прослушала полезную информацию и даже ряд пожеланий. Этих материалов оказалось достаточно для детального представления процесса составления расписания. Вот список материалов, собранных мною:

1. Образец расписания на 1 четверть 2008-2009 учебного года на понедельник (внешний облик), который висел в учительской. (Приложение 1)
2. Примерный учебный план для образовательных учреждений Российской Федерации на 1998 и 2004 года. (Приложение 2)
3. Учебный план средней общеобразовательной школы №5 на 2008-2009 учебный год. (Приложение 3)
4. Выдержки из «Охраны здоровья детей» по поводу балловой оценки предметов. (Приложение 4)
5. Требования к составлению расписания от Министерства Образования. (Приложение 5)
6. Таблица И.Г. Сивкова. Трудность каждого предмета здесь ранжируется в баллах:

Математика                                                   11 баллов

Иностранный язык                                       10 баллов

Физика, химия                                                9 баллов

История                                                            8 баллов

Русский язык, литература                            7 баллов

Естествознание, география                         6 баллов

Физкультура                                                    5 баллов

Труд                                                                   4 балла

Черчение                                                          3 балла

Рисование                                                         2 балла

Пение                                                                 1 балл

7. Расписание уроков на 1 полугодие 2008-2009 года в баллах и соответствующие схемы распределения нагрузки в течение недели. (Приложение 6 и приложение 7)

     Изучая  найденный материал, я почерпнула для себя много интересной и полезной информации. Оказалось, что составление  расписания – это целая наука! Ведь необходимо руководствоваться  учебным планом, балловой оценкой  предметов, дневной нагрузкой…. Учебный  план необходимо составлять, отталкиваясь от примерного учебного плана, составленного  Министерством Образования. Учебный  план – это нагрузка для класса, количество часов каждого предмета в неделю. А ведь есть коррекционные  классы, есть классы, которым необходима дополнительная нагрузка. Поэтому здесь  необходим индивидуальный подход, несмотря на то, что есть примерный учебный  план. Моя программа будет включать в себя процедуру создания учебного плана. Учебный план меняется ежегодно, расписание же может меняться 4 раза в год. Существует и учебный план для начальной школы, но расписание составляет сам учитель, поэтому  мой проект составляет расписание только для 5-11 классов. Но и здесь есть свои исключения: физкультуру, музыку и иностранный язык в начальных классах ведут другие учителя, поэтому всё же при составлении общего расписания нужно будет учесть и некоторые уроки 1-4 классов. Я думаю, что для учителей (не классных руководителей), преподающих в начальной школе, нужно составить график работы обычным образом (естественно отталкиваясь от правил составления расписания для начальной школы), после чего классные руководители начальных классов досоставляют расписание сами.

     Очень заинтересовала меня балловая оценка предметов. О существовании этой системы я слышала, но никогда  раньше ей не интересовалась. Каждый предмет имеет свой уровень сложности восприятия, и это необходимо учитывать при составлении расписания, ведь, при правильно составленном расписании занятий, наибольшая интенсивность нагрузки (количество баллов за день по сумме всех предметов) для учащихся старших классов должна приходиться на вторник и (или) среду; для школьников младшего и среднего звена – на вторник и четверг при несколько облегченной среде. При этом следует помнить, что в течение дня оптимальные значения показателя работоспособности приходятся на интервал 10-12 часов, то есть основная учебная нагрузка должна приходиться на 2,3,4 уроки. Также есть замечание по поводу сдвоенных уроков: в начальных классах их проведение недопустимо, так как степень утомления детей возрастает в таком случае в 7 раз! Допускаются сдвоенные уроки лишь в старших классах! Этот факт необходимо учесть при составлении программы, так же как и максимальное количество занятий для каждого класса. Балловая система неоднозначна, но изменения её незначительны. В программе будет предусмотрено изменение таблицы с баллами, зарисовка схем нагрузки учебной недели для каждого класса, начиная с 5. Естественно, проект предполагает подбор нескольких вариантов расписания, подходящих всем требованиям. Ведь есть ещё такие требования как: максимально допустимая недельная нагрузка в часах, чередование в течение дня и недели основные предметы с уроками музыки, изо, труда, физкультуры (для начальных классов), с предметами естественно-математического и гуманитарного циклов (для среднего и старшего звена), максимальное количество баллов по каждому дню.

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

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

     Алгоритм  имитации отжига

     Алгоритм  имитации отжига (англ. Simulated annealing) — общий алгоритмический метод решения задачи глобальной оптимизации, особенно дискретной и комбинаторной оптимизации. Один из примеров методов Монте-Карло. Экзотическое название данного алгоритма связано с методами имитационного моделирования в статистической физике, основанными на технике Монте-Карло. Исследование кристаллической решетки и поведения атомов при медленном остывании тела привело к появлению на свет вероятностных алгоритмов, которые оказались чрезвычайно эффективными в комбинаторной оптимизации. Впервые это было замечено в 1983 году. Сегодня этот алгоритм является популярным как среди практиков благодаря своей простоте, гибкости и эффективности, так и среди теоретиков, поскольку для данного алгоритма удается аналитически исследовать его свойства и доказать асимптотическую сходимость. Алгоритм основывается на имитации физического процесса, который происходит при кристаллизации вещества из жидкого состояния в твёрдое, в том числе при отжиге металлов. Предполагается, что атомы уже выстроились в кристаллическую решётку, но ещё допустимы переходы отдельных атомов из одной ячейки в другую. Предполагается, что процесс протекает при постепенно понижающейся температуре. Переход атома из одной ячейки в другую происходит с некоторой вероятностью, причём вероятность уменьшается с понижением температуры. Устойчивая кристаллическая решётка соответствует минимуму энергии атомов, поэтому атом либо переходит в состояние с меньшим уровнем энергии, либо остаётся на месте. (Этот алгоритм также называется алгоритмом Н. Метрополиса, по имени его автора).

     Алгоритм  имитации отжига - алгоритм решения различных оптимизационных задач. Он основан на моделировании реального физического процесса, который происходит при кристаллизации вещества из жидкого состояния в твёрдое, в том числе при отжиге металлов.

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

Основные  шаги алгоритма:

1. Выбор начального решения и начальной температуры
2. Оценка начального решения
3. Основной шаг алгоритма
1. Случайное изменение текущего решения
2. Оценка измененного решения
3. Критерий допуска
4. Уменьшение температуры и, если температура больше некоторого порога, то переход к основному шагу

Выбор начального решения

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

Оценка  решения

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

Основной  шаг алгоритма

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

Случайное изменение решения

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

Критерий  допуска