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

В недалеком 2002 году, заканчивая ВУЗ (Ярославский филиал МЭСИ), специальность «Прикладная информатика в экономике», стояла задача выбора дипломной работы. Предложенный список тем удручил, в основном скучные разработки БД. В принципе мог бы какой-нибудь из моих имеющихся наработок взять за основу, как предлагал зав. кафедры, но кровь бурлила, хотелось сделать что-нибудь интересное и новое для себя. Предложил руководителю тему составления расписания, тем более что работал в ИТ-службе ВУЗа, и в моем ведении была система КИС УЗ (Комплексная информационная система управления учебным заведением), продукт ярославской компании. КИС УЗ была хороша, но составлять расписание сама не могла. Также, этим я преследовал цель сделать что-то полезное, но вышло так, что не было попыток внедрения в жизнь, может хоть публикация на хабре даст кому-нибудь пользу.

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

• занятие
• преподаватель
• поток или группа
• тип аудитории
• количество занятий в данной группе занятий
• время, если постановщик желает «жестко» установить данное занятие в определенное время

Процесс должен расставить занятия на временной сетке – расписание. В оценке расписания участвуют 4 параметра - количество «окон» в расписании у группы и преподавателей, равномерное распределение занятий по дням у группы и преподавателей. Значимость этих параметров задает постановщик. Сначала хотел применить метод анализа иерархий в целевой функции, но пришлось бы ввести попарное сравнение этих параметров, поэтому обошелся линейной функцией.

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

PS. Позднее, когда услышал о PageRank, подумал, что есть в нем нечто схожее с этой эвристикой.

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

Приемлемость уроков и школьное расписание

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

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

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

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

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

Таблица 1

Примерная шкала приемлемости предметов

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

В средней общеобразовательной школе № 618 г. Санкт-Петербурга мы получили следующую шкалу приемлемости предметов (см. таблицу 2).

Таблица 2

Шкала приемлемости предметов

Алгоритм составления расписания

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

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

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

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

• первоначальной расстановки предметов с последующей ее ручной доводкой;
• сохранения информации и вывода ее на печать.

После автоматизированного распределения предметов (программа, как правило, расставляет от 40 до 70%) учитывать гигиенические требования к расписанию уроков практически невозможно, так как приходится не только доставлять оставшиеся нерасставленные предметы, но и существенно изменять (до 60%) автоматизированную расстановку предметов по принципу «лишь бы расставить».

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

Порядок изменения расписания

Алгоритм корректировки школьного расписания

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

Предложенный способ составления расписания занимает времени не более, чем обычно, но позволяет составить расписание грамотно, т.е.:

• сделать собственную шкалу приемлемости предметов (трудности и утомительности) для составления более рационального школьного расписания;
• держать в поле зрения заместителя директора школы достаточно большое количество необходимой информации;
• равномерно распределять уроки на каждый день (избегать излишнего количества седьмых уроков);
• ставить все классы с первого урока, что позволяет обеспечить обучение в одном ритме, поскольку каждый день учащиеся будут начинать учебный день в одно и то же время;
• регулировать степень сложности учебного дня в зависимости от динамики недельной работоспособности школьников;
• расставлять уроки практически без «окон» либо с минимальным их количеством, что позволяет сохранить ритм работы учителя и создать благоприятный рабочий режим;
• рационально чередовать предметы разной направленности;
• рационально расставить необходимые сдвоенные уроки;
• быстро изменять и корректировать расписание в силу производственной необходимости.

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

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

Критерии гигиенической оценки школьного расписания

1. Количество классов начальной школы – ______.

2. Количество классов основной и средней школы – ___________.

3. Всего учебных кабинетов, используемых для проведения уроков – ___________.

4. Наличие шкалы приемлемости для своего образовательного учреждения:

5. Учет шкалы приемлемости предметов в школьном расписании:

6. Распределение уроков на день для учащихся:

7. Все классы начинают учебу с первого урока:

8. Рациональное чередование предметов разной направленности и сложности:

9. Соблюдение в расписании учета работоспособности учащихся (в недельной динамике):

10. Рациональная расстановка уроков для учителей:

11. Максимальное количество уроков у учителей в день:

а) до 4 уроков – у____ учителей – ______ (%);

б) 5 и 6 уроков – у____ учителей – _____ (%);

в) 7 уроков и более – у____ учителей – ___ (%).

12. Методический день имеется (указать количество учителей):

а) с нагрузкой до 24 часов в неделю – у____ учителей;

б) с нагрузкой от 25 до 30 часов в неделю – у___ учителей;

в) с нагрузкой более 30 часов в неделю – у___ учителей.

1. Подготовить наборы с названиями предметов с 5-го по 11-й класс.
2. Учащимся раздать наборы карточек с названиями предметов и листки для ответов.
3. Предложить выбрать карточки с названиями тех предметов, которые изучаются в данном классе (по дневнику).
4. Уточнить понятие «трудность» предметов.
5. Предложить самостоятельно определить трудность каждого предмета путем ранжирования, т.е. раскладывания карточек в порядке убывания трудности предмета (карточки укладывать сверху вниз, т.е. на первом месте сверху – карточка с самым трудным предметом, ниже – менее трудным и т.д.).
6. Полученный расклад предметов записать на листе ответов.
7. После этого разобрать и уточнить понятие «утомительность» предметов.
8. Выполнить аналогичную процедуру ранжирования и записать полученный расклад на листе ответов.
9. Листы с ответами собрать и обработать (см. форму сводной таблицы ниже).

– где: mk – средний балл по предмету одного класса;

n – количество классов в исследуемой параллели;

или по формуле:

– где: Mk – сумма баллов по предмету одного класса;

n – количество учащихся одной параллели, участвующих в исследовании.

Например, в параллели 7-х классов имеется пять классов, приняли участие в диагностике 130 человек. Сумма баллов по русскому языку в параллели составила 469. Подставляем в формулу числа:

Ср. б. пр. = (469/130) = 3,61 – средний балл по русскому языку в параллели 7-х классов составил 3,61, дети воспринимают этот предмет как достаточно трудный.

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

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

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

Форма сводной таблицы для обработки ответов

Приложение 2

Ранжирование учебных часов в течение недели
в зависимости от уровня работоспособности учащихся разных классов

1 – наиболее благоприятные часы; 10 – наиболее неблагоприятные.

6–7 – пониженный уровень работоспособности (малоблагоприятные часы для проведения уроков).

8–10 – низкий уровень работоспособности (неблагоприятные часы для проведения уроков).

Таблица распределения недельной нагрузки учителя

Приложение 3

Технология выполнения макета таблицы расписания уроков

Для выполнения макета необходимо приготовить:

• 4 листа картона (толщина 1–2 мм, высота – 42 см, ширина – 22 см; высота строк – 0,8 см, ширина столбца – 1 см)*;
• 4 листа цветной бумаги (лучше светлых тонов) плотностью 200 г/см и размерами, аналогичными размерам листов картона;
• широкий прозрачный скотч;
• ледерин (бумвинил) для склеивания картона в папку (ленты шириной 4–5 см; длиной 49–50 см);
• клей ПВА (достаточно сильный, типа «силакра»).

Алгоритм выполнения макета

1. Склеить листы картона в «раскладушку»:

2. На одном листе цветной бумаги поместить всю необходимую информацию для составления расписания (поместить на лист картона № 1); пример: таблица на с. 27.

3. На двух следующих листах цветной бумаги начертить сетку, по три дня на каждом листе, по 7 ячеек на каждый день (поместить на 2-й и 3-й лист картона).

4. На 4-м листе расчертить сплошную сетку без деления на дни (ячейки – аналогичных размеров).

5. Готовые расчерченные листы покрыть скотчем, чтобы при разрезах ячеек не было разрывов.

6. Сделать прорези в ячейках размером от 0,5–0,6 см.

7. Приклеить бумажные листы по боковым частям листов картона на готовую «раскладушку». Макет готов.

8. Отдельно сделать разноцветные бирки с литерой класса (5-й «А», 7-й «Г» и т.д.), количество – из расчета нагрузки 5- или 6-дневной недели + дополнительно на уроки, где классы делятся на подгруппы. Размер бирки: ширина – 8 мм; высота – 15 мм.

9. Подготовить бирки любого цвета без надписей литер класса для расчета недельной нагрузки на каждого учителя. Размеры: ширина 5 мм; высота 12–14 мм.

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

Информация, необходимая для составления расписания

___________ * Размеры листа картона индивидуальны, т.к. в каждой школе различное количество учителей, разный режим работы (5- и 6-дневная учебная неделя). Мы предлагаем размеры для расписания из расчета 6-дневной учебной недели и школы, в которой работают 50–55 учителей.

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

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

Пример . Пусть имеется три процессора и шесть заданий, время выполнения каждого из которых равно:

Рассмотрим расписание В начальный момент времениT=0 , процессорначинает обработку задания, процессор- задания, а процессор- задания. Процессорзаканчивает выполнение заданияв момент времени
, пока процессорыивсе еще работают над своими первоначальными заданиями. ПриT=3 процессоропять заканчивает заданиеи начинает обрабатывать задание, которое завершается в моментT=4 . Тогда он начинает выполнять последнее задание. Процессорыизаканчивают задания приT=5 , но, так как списокL пуст, они останавливаются. Процессорзавершает выполнение заданияприT=12 . Рассмотренное расписание проиллюстрировано на рис.1. временной диаграммой, известной каксхема Ганта . Очевидно, что расписание не оптимально. Можно «подобрать», например, расписание, которое позволяет завершить все задания заT* = 8 единиц времени (рис.2.).

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

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

Литература

1. Т. Кормен, Ч. Лейзерсон, Р. Ривест

Алгоритмы: построение и анализ. М.: МЦНМО, 2000.

2. Д.Кнут Искусство программирования, том 1. Основные алгоритмы. Уч. пос. М.:Изд. Дом " Вильямс ", 2000.

3. Вирт Н. Алгоритмы и структуры данных.: Пер. С англ. - М.: Мир, 2001.

4. Хусаинов Б.С. Структуры и алгоритмы обработки данных. Примеры на

языке Си. Учеб. пособие. М: Финансы и статистика, 2004.

5. А. Ахо, Дж.Хопкрофт, Дж.Ульман, Структуры данных и алгоритмы М: СПб: Киев: Вильямс, 2001г.

Воцарилась тишина, которую нарушил сам Швейк, вздохнув:
- … На военной службе должна быть дисциплина - без неё никто бы и пальцем для дела не пошевельнул. Наш обер-лейтенант Маковец всегда говорил: «Дисциплина, болваны, необходима. Не будь дисциплины, вы бы, как обезьяны, по деревьям лазили. Военная служба из вас, дураки безмозглые, людей сделает!» Ну, разве это не так? Вообразите себе сквер, скажем, на Карловой площади, и на каждом дереве сидит по одному солдату без всякой дисциплины. Это меня ужасно пугает.
Ярослав ГАШЕК ПОХОЖДЕНИЯ БРАВОГО СОЛДАТА ШВЕЙКА

Расписание занятий, это совмещение в пространстве и времени дисциплины (предмета), преподавателя (преподавателей), аудитории и группы (подгруппы, потока) студентов.

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

Буду краток.

• При проведении занятия могут отсутствовать его любые участники, например, на заседании кафедры студенты, как правило не приходят или студенты ушли на военную кафедру (у них свое расписание), а для того рода занятий нет дисциплины, преподавателя и аудитории.
• Как правило, необходимым требованием ставится непрерывность (отсутствие окон) у студентов и желательно у преподавателей.
• Расписание может составлятся на семестр/полсеместра по неделям, по двум неделям и числитель/знаменатель (нечетная неделя/четная неделя). Также бывает расписание на месяц.
• Занятия должна иметь возможность постановки в ручном режиме (другими словами в редакторе). Например учёный совет или пара большого начальника и даже занятие просто хорошего человека.
• Должна быть система запретов для всех участников занятия. Например, сейчас практически все преподаватели подрабатывают на стороне (иначе не проживешь) или аудиторный фонд разделен между факультетами и после обеда в часть аудиторий занятия ставить нельзя.
• Наличие изощренных пожеланий преподавателей, одному ставь 5 пар в день, чтобы освободить другие дни, а другому больше двух пар в день не ставить, он переутомляется, а если лекцию, то одну пару и обязательно 2 или 3-ю пару.
• Занятия в разных корпусах, требующих для перехода время большее, чем время перерыва между занятиями. Естественно и условие минимизации перемещений.

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

Картинка взята отсюда.

Генетический алгоритм

Чисто риторически, повторю основные этапы генетического алгоритма :

1. Задать целевую функцию (приспособленности) для особей популяции
2. Создать начальную популяцию
3. (Начало цикла)
   1. Размножение (скрещивание)
   2. Мутирование
   3. Вычислить значение целевой функции для всех особей
   4. Формирование нового поколения (селекция)
   5. Если выполняются условия остановки, то конец цикла, иначе (начало цикла).

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

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

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

Алгоритм составления расписаний

Я только опишу сами гены, алгоритм построения по ним решения, скрещивание и мутацию.

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

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

Скрещивание можно организовать несколькими способами. Например один из них. Пусть имеем следующие гены

3 1 2 5 6 4 7
2 3 5 7 1 4 6

Здесь видно, что занятие 3 встречается в обоих генах до позиции 2 включительно, а, например, с позиции 2 до позиции 5 интервал для 1 занятия. Сделаем следующую табличку

_ * * * * _ _ для 1 занятия
* * * _ _ _ _ для 2 занятия
* * _ _ _ _ _ для 3 занятия
_ _ _ _ _ * _ для 4 занятия
_ _ * * _ _ _ для 5 занятия
_ _ _ _ * * * для 6 занятия
_ _ _ * * * * для 7 занятия

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

1 позиция {2, 3}
2 позиция {1, 2, 3}
3 позиция {1, 2, 5}
4 позиция {1, 5, 7}
5 позиция {1, 6, 7}
6 позиция {4, 6, 7}
7 позиция {6, 7}

Для построения решений можно использовать следующий алгоритм. Сначала будем ставить те номера занятий, которые реже встречаются. Если их отсортировать по возрастанию, то будем иметь
1 раз 4
2 раза 3, 5
3 раза 2, 6
4 раза 1, 7
Следовательно сначала ставим 4 занятие на 6 позицию, затем 3 или 5 на позиции {1, 2} или {3, 4} соответственно. На каждом шаге можно кидать коробок спичек. В результате можно получить например следующие шаги для алгоритма скрещивания

* * * * * 4 *
3 * * * * 4 *
3 * * 5 * 4 *
3 * * 5 * 4 6
3 * 2 5 * 4 6
3 * 2 5 7 4 6
3 1 2 5 7 4 6

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

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

Заключение

Это продолжение, в некотором смысле, моих постов Программа по составлению расписания занятий в ВУЗе и Расчет нагрузки по кафедре .

Повторно предлагаю следующие решение (набросок).

• GUI на PyQt или PySide
• СУБД PosgreSQL (у меня здесь готово примерно на 80%), в ней кроме самого расписания еще заявки и нагрузка преподавателей, учебные планы и еще много чего (с этой целью опубликую один или несколько топиков)
• web интерфейс на CherryPy+Cheetah (но это может обсуждаться)
• экспорт всяких отчетов (расписаний, карточек учебных поручений и т.д.) в формате OpenDocument (ГОСТ Р ИСО/МЭК 26300-2010. Госстандарт России (01.06.2011)) посредством ODFPY
• алгоритмы составления расписания от меня (об этом этот топик)
• постановка от меня
• для заинтересованных работа над общим ядром
• для заинтересованных адаптация под собственный ВУЗ и возможность гибко все менять, жизнь идет, а чиновники не дремлют

Спасибо Всем кто откликнулся, после обсуждения этого топика можно будет со организоваться.