Введение в эволюционное моделирование. Каширина И.Л. - 38 стр.

                                                        38

                                     ∑            z k i = 1 , i = 1, p , j = 1, q
                                   k ∈K
                                          j
                                            (i)
       Здесь z k i = ⎧1, к − й предмет преподается на i − м уроке .
                       ⎪
                       ⎨
                       ⎪⎩0, иначе; k = 1, n i = 1, p .

      Целевая функция минимизирует количество несовместимых предметов
преподающихся на каждом уроке. Первая группа ограничений отвечает за
то, что каждый предмет k проводится только один раз, причем на допусти-
мом уроке. Вторая группа ограничений следит за тем, чтобы в каждой груп-
пе j на каждом уроке i проводится только один предмет. Заметим, что в ре-
зультате получилась модель, похожая на постановку квадратичной задачи о
назначениях [1], причем оптимальное значение целевой функции известно
заранее и равно 0. Все дополнительные требования к расписанию, не учтен-
ные в модели, выполняются алгоритмически.
                            Генетический алгоритм
     Для построения генетического алгоритма необходимо выбрать способ
представления данных в виде хромосом. В данном случае хромосома будет
матрицей. Ее элемент y i j = k , если у j-й группы на i-м уроке проводится
предмет k ( yi j = 0 , если у j-й группы нет i-го урока). Связь с переменными
zk i в модели: y i j = k , если z k i = 1 , g j −1 < k ≤ g j , i ∈1, p , j ∈1, q , k ∈ K j (i) . В ка-
честве стратегии отбора в данной задаче используется турнирный отбор (он
оказался для нее более эффективным, чем пропорциональный). Поэтому
функцию приспособленности можно не максимизировать, а уменьшать от
популяции к популяции. В ее роли выступает целевая функция задачи с до-
бавками в виде штрафов за нарушение дополнительных ограничений. (На-
пример, водится матрица : lij =1, если по нормам СанПин предметы i,j не мо-
гут преподаваться в один день; lij =0, если могут, и рассчитывается количе-
ство нежелательных ситуаций в оцениваемом расписании. И т.п.) Получен-
ные значения добавляется в функцию приспособленности (возможно, с ко-
эффициентами, характеризующими их значимость). При скрещивании про-
исходит обмен фрагментами внутри одного выбранного столбца матрицы Y.
В качестве оператора скрещивания используется циклический кроссовер. Он
гарантирует допустимость получаемых после скрещивания хромосом, т. к.
каждый ген потомка будет находиться на том месте, на котором он находил-
ся в одном из родителей. Для мутации внутри одного столбца выбирается
любая пара генов таких, что их обмен не нарушит допустимости хромосо-
мы, затем эти гены меняются местами. Проведенные эксперименты показы-
вают эффективность генетического алгоритма построения расписания.