УДК ББК 74.580 | , (РГУПС) |
ПРИМЕНЕНИЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА В ОПТИМИЗАЦИИ УЧЕБНОГО РАСПИСАНИЯ ВУЗА
В наиболее общей формулировке задача составления расписаний состоит в следующем. С помощью некоторого множества ресурсов или обслуживающих устройств должна быть выполнена некоторая фиксированная система заданий. Цель заключается в том, чтобы при заданных свойствах заданий и ресурсов и наложенных на них ограничениях найти эффективный алгоритм упорядочивания заданий, оптимизирующий или стремящийся оптимизировать требуемую меру эффективности. В качестве основных мер эффективности изучаются длина расписания и среднее время пребывания заданий в системе. Модели этих задач являются детерминированными в том плане, что вся информация, на основе которой принимаются решения об упорядочивании, известна заранее.
Задача планирования расписания учебных занятий ¾ это задача на составление расписания комбинаторного типа, характерной особенностью которой является огромная размерность и наличие большого числа ограничений сложной формы. Фактически, в настоящее время, не существует универсальных методов решения таких задач. Математическая теория расписаний охватывает лишь узкий круг хорошо формализуемых проблем, которые обычно сводятся к задачам коммивояжера, транспортной и т. д.
Следует отметить, что построение допустимого расписания или даже выяснение того факта, существует ли оно вообще, является зачастую далеко не тривиальной задачей. Вместе с тем во многих ситуациях построение допустимых расписаний не вызывает сколько-нибудь серьезных затруднений, и речь идет о выборе среди них наилучшего в том или ином смысле расписания.
Наиболее распространенный способ оценки качества расписаний для детерминированных систем обслуживания состоит в следующем. Каждому расписанию s соответствует вектор t(s)=(t1(s), t2(s), ..., tn(s)) моментов завершения обслуживания требований при этом расписании. Задается действительная неубывающая функция n переменных F(x)=F(x1 x2, ..., хn). Качество расписания s характеризуется значением этой функции при x=t(s). Из двух расписаний лучшим считается то, которому соответствует меньшее значение F(x).
Расписание, которому соответствует наименьшее значение F(x) (среди всех допустимых расписаний), называется оптимальным.
При задании функции F(x) каждому требованию i обычно сопоставляют некоторую неубывающую функцию ji(t), выражающуюся в количественном отношении «штраф», который необходимо «заплатить», если обслуживание этого требования завершится в момент времени t. Качество расписания s характеризуется суммарным или максимальным штрафом, который необходимо заплатить при обслуживании требований по этому расписанию, т. е.
Få(s) = åji (ti (s)) или Fmax (s) = max{(ji (ti(s))}, i = 1, ..., n.
В частности, если ji (t)=t, i = 1, … ,n, то Fmax(s) = max{ti(s)} ¾ момент завершения обслуживания всех требований (общее время обслуживания). В этом случае Fmax(s) обозначают через tmax(s), и расписание s*, доставляющее наименьшее значение tmax(s), называют оптимальным по быстродействию расписанием.
Если ji (t) = t –Di то Fmax (s) обозначают через Lmax (s). Имеем Lmax (s) = max{Li(s)}, где Li (s) = ti(s)-Di— временное смещение момента завершения обслуживания требования I относительно директивного срока Di.
Если ji(t) = max{0, t-Di }, то Fmax (s) обозначают через zmax(s). Имеем zmax(s) = max{Zi(s)}, где Zi(s) = max{0, Li(s)} — запаздывание в обслуживании требования i относительно директивного срока D. В этом случае Få(s) = åzi(s),
i = 1,…,n — суммарное запаздывание.
Если ji(t) = sign (max {0, t-Di}, то Få = ui(s), i = l,...,n,
где ui (s) = sign(zi(s)) представляет собой число запаздывающих (относительно директивных сроков) требований.
Наряду с перечисленными используются и другие критерии оптимальности расписаний.
В большинстве ситуаций оптимальное расписание может быть найдено в результате перебора конечного множества возможных вариантов. Основное затруднение состоит в том, что число таких вариантов обычно оказывается исключительно большим и растет по меньшей мере экспоненциально с ростом размерности задачи.
Генетические алгоритмы ¾ адаптивные методы поиска, которые в последнее время часто используются для решения задач функциональной оптимизации. Они основаны на генетических процессах биологических организмов: биологические популяции развиваются в течение нескольких поколений, подчиняясь законам естественного отбора и по принципу «выживает наиболее приспособленный» открытому Чарльзом Дарвином. Подражая этому процессу, генетические алгоритмы способны «развивать» решения реальных задач, если те соответствующим образом закодированы.
Основные принципы генетического алгоритма были сформулированы Голландом (Holland, 1975) и хорошо описаны во многих работах. В отличие от эволюции, происходящей в природе, генетические алгоритмы только моделируют те процессы в популяциях, которые являются существенными для развития. Генетические алгоритмы работают с совокупностью «особей» ¾ популяцией, каждая из которых представляет возможное решение данной проблемы. Каждая особь оценивается мерой ее «приспособленности» согласно тому, насколько «хорошо» соответствующее ей решение задачи. Наиболее приспособленные особи получают возможность «воспроизводить» потомство с помощью «перекрестного скрещивания» с другими особями популяции. Это приводит к появлению новых особей, которые сочетают в себе некоторые характеристики, наследуемые ими от родителей. Наименее приспособленные особи с меньшей вероятностью смогут воспроизвести потомков, так что те свойства, которыми они обладали, будут постепенно исчезать из популяции в процессе эволюции. Так и воспроизводится вся новая популяция допустимых решений, методом выбора представителей предыдущего поколения, скрещивания их и получения множества новых особей. Это новое поколение содержит более высокое соотношение характеристик, которыми обладают хорошие члены предыдущего поколения. Таким образом, из поколения в поколение лучшие характеристики распространяются по всей популяции. Скрещивание наиболее приспособленных особей приводит к тому, что исследуются наиболее перспективные участки пространства поиска. В конечном итоге популяция будет сходиться к оптимальному решению задачи.
Простой генетический алгоритм случайным образом генерирует начальную популяцию структур. Работа генетического алгоритма представляет собой итерационный процесс, который продолжается до тех пор, пока не выполнятся заданное число поколений или какой-либо иной критерий остановки. На каждом реализуется отбор пропорциональной приспособленности, одноточечный кроссовер и мутация.
Сначала пропорциональный отбор назначает каждой структуре вероятность Ps(i), равную отношению ее приспособленности к суммарной приспособленности популяции:
Затем происходит отбор (с замещением) всех п особей для дальнейшей генетической обработки, согласно величине Ps(i). Простейший пропорциональный отбор ¾ рулетка ¾ отбирает особей с помощью п «запусков» рулетки. Колесо рулетки содержит по одному сектору для каждого члена популяции. Размер i-го сектора пропорционален соответствующей величине Ps(i). При таком отборе члены популяции с более высокой приспособленностью с большей вероятностью будут чаще выбираться, чем особи с низкой приспособленностью.
После отбора, п выбранных особей подвергаются кроссоверу (иногда называемому рекомбинацией) с заданной вероятностью Pc; n строк случайным образом разбиваются на n/2 пары. Для каждой пары с вероятностью Рс может применяться кроссовер. Соответственно, с вероятностью 1-Рс кроссовер не происходит и неизмененные особи переходят на стадию мутации. Если кроссовер происходит, полученные потомки заменяют собой родителей и переходят к мутации.
После того как закончится стадия кроссовера, выполняются операторы мутации. В каждой строке, которая подвергается мутации, каждый бит с вероятностью Рm изменяется на противоположный. Популяция, полученная после мутации, записывается поверх старой и этим цикл одного поколения завершается. Последующие поколения обрабатываются таким же образом: отбор, кроссовер и мутация.
В конце концов должен получиться вариант расписания, полностью удовлетворяющий всем правилам. Представляется целесообразным применять генетический алгоритм для составления не сразу всего расписания, а более мелких структур, например, расписания одной учебной группы, а потом уже из них собирать полное расписание.
