Statistical Analysis of the Performance of Modified Genetic Algorithms for Automated Compilation of a Multilevel University Scheduling

Full Text

Введение Построение расписания занятий учебного заведения, в том числе вуза, является трудоемкой задачей, относящейся к классу NP-сложных [1]. Громоздкость решения таких задач характерна для многоуровневых вузов, сочетающих в своих организационно-педагогических структурах несколько уровней обучения, включая профессионалитет, среднее профессиональное и высшее образование, а также подготовку научно-педагогических кадров высшей квалификации. При этом необходимо учитывать многочисленные и отчасти противоречивые требования ограниченности наличных ресурсов и нечеткость интегрального многокомпонентного критериев оценки качества полученного расписания учебных занятий для вуза в целом и отдельных участников образовательного процесса. Проблема увязки предъявляемых требований в формируемом учебном расписании дополнительно усугубляется необходимостью учета нелинейности образовательного процесса, для которой характерна «возрастающая открытость и взаимопересечение образовательных и культурных сред[15]. Как школы, так и высшие учебные заведения перестают быть „вещью в себе“, оказываются поставленными в обстоятельства, когда одновременно должны предоставлять субъектам возможности для обучения в интеграции разнообразных сред и поддерживать собственную образовательную специфику», отмечаемая в работе [2]. Как отмечают С.В. Аранова, Л.К. Боровик, Н.В. Примчук, упомянутая нелинейность определяет такие характеристики, как: «динамичный характер в открытом взаимодействии с внешней средой; возможность внесения изменений на уровне целей, содержания и результатов образования с учетом социальных и культурных вызовов; самореализация обучающихся за счет выстраивания индивидуальных образовательных маршрутов» [2]. Цитируемые авторы отмечают ряд ключевых моментов, необходимых при составлении расписания «Математическое моделирование и автоматизация процесса реализации учебного расписания; Типологизация и формирование требований к учебному расписанию с учетом стандартов и регламентов; методы и алгоритмы построения расписания» [3]. Известны различные математико-алгоритмические подходы к решению задачи оптимизации учебного расписания, исследованные в работах А.С. Хасухаджиева, М.Э. Нагорных, И.И. Холода, В.С. Иванова, В.А. Бабкина, И.С. Григорьева и других исследователей, включая математическое моделирование и специализированные фреймворки [4; 5], мультиагентные системы [3; 6; 7] и другие методы. В качестве эффективного подхода при составлении расписания вуза, как большой многокомпонентной системы, ряд авторов рекомендует метод компьютерного решения задачи оптимизации при составлении расписаний многоуровневого вуза на основе генетического алгоритма (ГА), являющегося эвристическим подвидом искусственного интелекта (ИИ) [8]. С целью системного семантического описания предметной области задачи составления учебных расписаний обоснован онтологический подход к формированию структуры ее данных[16] [1]. Разработанные компьютерные программы обеспечивают построение расписания учебных занятий многоуровневого вуза. Известны различные методы оценки и реализации эффективного интегрального критерия качества, в том числе на основе комбинированных штрафных функций для учета ограничений математической модели оптимального расписания. С учетом NP-сложности рассматриваемой задачи, существенного времени счета даже на современных быстродействующих ЭВМ, дости-гающих десятков минут, и необходимости опе-ративных корректировок расписания, вопросы оптимизации машинного времени являются весьма актуальными, что невозможно без соответствующих статистических методов учета при модификации генетических алгоритмов и структуры входных и расчетных данных. 1. Методы База данных (БД) решаемой задачи была сформирована на основе семантического описания предметной области проектирования расписания с учетом особенностей многоуровневого вуза, включающего частично пересекающиеся подмножества ресурсных ограничений для реализуемых уровней образования [9]. Для компьютерной поддержки решения оптимизационной задачи использованы методы онтологического инжиниринга, эволюционно-генетического и математического моделирования, статистического анализа, построения, а также нормализации и структурной оптимизации базы данных. Эволюционная оптимизация учебного расписания была реализована посредством модифицируемого ГА, обобщенная схема которого представлена на рис. 1. Исходный вариант расписания, представляющий собой начальную популяцию ГА, формировался рандомно с использованием случайных значений хромосом. Основные генетические операторы селекции, скрещивания и мутации [10-12] реализованы с возможностью модификации, в том числе в процессе реализации бесконечного цикла «while true» с предварительной проверкой условия останова. Расчеты выполнялись на ПК со следующими характеристиками: CPU: 11th Gen Intel® Core™ i5-11400 2.60Ghz (12 CPUs); RAM: 32Gb; SSD: M.2 NVME 1Tb. 2. Результаты и обсуждение Программа для формирования оптимизированного расписания включает специализированную базу данных и оптимизатор, реализованный на основе генетического алгоритма. Рис. 1. Обобщенная блок-схема ГА c модифицируемыми генетическими операторами: 1 - останова, обозначены блоки генерации поколения; 2 - вычисление функции пригодности; 3 - проверка условия останова; 4 - задание основного цикла; 5 - блок реализации генетических операторов, 6 - блок модификации; 7 - обновление популяции; 8 - завершение ГА И с т о ч н и к: выполнено Д.С. Захаровым, А.Ф. Рогачевым Figure 1. Generalized flowchart of GA with modifiable genetic operators: 1 - breakpoint, the generation blocks are designated; 2 - calculation of the fitting function; 3 - checking of the breakpoint condition; 4 - definition of the main cycle; 5 - block for implementing genetic operators; 6 - modification block; 7 - population update; 8 - completion of genetic algorithms S o u r c e: by D.S. Zakharov, A.F. Rogachev 2.1. Особенности разработанного программного средства для оптимизации расписания Основные элементы БД, используемой для оптимизации расписания многоуровневого вуза и разработанной на основе онтологической модели, представлены в табл. 1. Перед началом работы методист учебного отдела загружает файл учебной нагрузки и преподавателей [13]. В этом файле содержатся: a. название дисциплины; b. часы на дисциплину с разбивкой лекции/практики/лабы/СРС; c. прикрепленный преподаватель; d. кафедра, за которой закреплена дисциплина; e. прочие данные (коды дисциплин, кол-во групп бюджет/внебюджет, кол-во человек в группе, формы контроля и прочее). После этого программа запускается на выполнение оптимизации расписания до момента останова по заданному критерию. Разработанная авторами зависимость, описывающая значение безразмерной функции пригодности единичного индивида в популяции и учитывающая окна в сетке расписания, равномерность загрузки, типы кабинетов, ограничения, а также предпочтения преподавателей, имеет вид (1) где K1…i - весовые (уравнивающие) коэффициенты показателей; N1…j - количество окон различных типов; X - штраф за окна в сетке расписаний студентов; Y - штраф за окна в сетке расписаний преподавателей; GD - показатель отклонения от среднего показателя занятий в день (для расчета равномерности нагрузки); D - день недели (1…6); Zс - показатель штрафа за несоблюдение типа занятия и кабинета; C - ячейка расписания; R - штраф за несоблюдение ограничения; W - штраф за несоблюдение предпочтения; t - преподаватель/время/иной объект предпочтения или ограничения. Таблица 1 / Table 1 Фрагмент БД с основными расчетными параметрами / Snapshot of the database with the main calculated parameters И с т о ч н и к: выполнено Д.С. Захаровым, А.Ф. Рогачевым / S o u r c e: by D.S. Zakharov, A.F. Rogachev Таблица 2 Варианты модификации генетических операторов Этапы реализации ГА Варианты модификации Результаты модификации 1. Построение начальной популяции Построение начальной популяции по строгому алгоритму, с соблюдением жестких (обязательных) ограничений Невозможность нарушения жестких ограничений в ходе работы алгоритма, отсутствие пересечений 2. Селекция Механизм «встряски» при стагнации популяции, добавление новых неоптимизированных индивидов, сокращение популяции по принципу «катаклизма» Сокращение вероятности ухода алгоритма в локальные минимумы и периоды однообразия популяций 3. Скрещивание Групповое скрещивание особей популяции с возможностью скрещиваться более двух особей Увеличение разнообразия индивидов 4. Мутация Двухэтапная мутация: вынужденная, в случае нахождения пересечений отдельных генов, и случайная мутация Уменьшение вероятности появления нежестких ограничений, разнообразие индивидов 5. Гиперпараметры ГА Гибкая подстройка и адаптация параметров ГА (размер популяции, количество скрещиваемых индивидов, вероятность мутации и т.д.) Ускорение работы алгоритма и более эффективное использование ресурсов ЭВМ И с т о ч н и к: выполнено Д.С. Захаровым, А.Ф. Рогачевым Table 2 Modification options for genetic operators Stages of GA implementation Modification options Modification results 1. Building the initial population Building an initial population according to a strict algorithm, subject to strict (mandatory) restrictions The impossibility of violating strict restrictions during the operation of the algorithm, the absence of intersections 2. Breeding The mechanism of “shaking up” during population stagnation, the addition of new unoptimized individuals, the reduction of the population according to the principle of “cataclysm” Reducing the probability of the algorithm going into local minima and periods of population uniformity 3. Crossbreeding Group interbreeding of individuals of the population with the possibility of interbreeding more than two individuals Increasing the diversity of individuals 4. Mutation Two-stage mutation: forced, in case of intersections of individual genes, and accidental mutation Increasing the diversity of individuals. Reducing the likelihood of non-rigid restrictions, diversity of individuals 5. Hyperparameters of GA Flexible adjustment and adaptation of GA parameters (population size, number of individuals crossed, probability of mutation, etc.) Acceleration of the algorithm and more efficient use of computer resources S o u r c e: by D.S. Zakharov, A.F. Rogachev Представленные в табл. 2 возможные варианты модификации генетических операторов и элементов ГА способствуют уменьшению ресурсоемкости проводимых операций, позволяют строго соблюдать жесткие ограничения при составлении расписаний, а также снижают влияние системных недостатков ГА на конечный результат. 2.2. Результаты численных экспериментов Результаты численных экспериментов расчета оптимального расписания с использованием разработанной программы методом ГА, использующей модуль «Статистика» [14], представлены на рис. 2. Упомянутый модуль статистического анализа обеспечивает сбор, анализ и отображения статистики работы ГА, позволяет в автоматизированном режиме корректировать гиперпараметры ГА, его характеристики, а также параметры ограничений при оптимизации расписаний. Проведенные расчеты на ПК показали, что отбор индивидов популяции в количестве 50 %, после подсчета функции приспособленности показала лучшую эффективность по времени и конфигурации нисходящего характера графиков, при чем 80 %. Потомство дают 50 % лучших особей (из 1000 особей), при этом время расчета составило 8 минут и останов происходил в районе 90 поколений (эпох). На рис. 3 представлены результаты численного эксперимента, предусматривающего применение более широкого разнообразия особей для дальнейшего скрещивания. Отметим, что 80 % лучших особей дают потомство (1000 особей), при этом останов происходил ориентировочно на 280-м поколении, а время расчета составляло порядка 30 минут. Анализ графика на рис. 3 показывает, что увеличение количества особей, участвующих в турнирном отборе дальнейших популяций, дает отрицательную динамику поиска оптимального результата. Анализ конфигурации диаграммы на рис. 3 показывает, что высокий показатель доли скрещиваемых в поколении особей дает негативный эффект кратковременного ухудшения показателя пригодности популяции (синие пики на графике), а также способствует увеличению времени работы алгоритма и конкретной ресурсозатратности. Более низкое значение показателя (30-40 %) дает эффект недостаточности генного разнообразия индивидов и приводит процесс расчета оптимального решения к стагнации популяции и невозможности применения останова по достижении оптимального результата функции приспособленности (рис. 4). - лучший результат функции приспособленности индивида в популяции / The best outcome of an individual’s fitness function in a population - средний результат функции приспособленности популяции / Average result of the population adaptation function Рис. 2. Результаты численных экспериментов с использованием модуля «Статистика» разработанной программы И с т о ч н и к: выполнено Д.С. Захаровым, А.Ф. Рогачевым Figure 2. Results of numerical experiments using the developed program module "Statistics" S o u r c e: by D.S. Zakharov, A.F. Rogachev - лучший результат функции приспособленности индивида в популяции / The best outcome of an individual's fitness function in a population - средний результат функции приспособленности популяции / Average result of the population adaptation function Рис. 3. Результаты численного эксперимента при увеличенной доле скрещиваемых хромосом особей И с т о ч н и к: выполнено Д.С. Захаровым, А.Ф. Рогачевым Figure 3. Results of numerical experiment at increased proportion of crossed chromosome individuals S o u r c e: by D.S. Zakharov, A.F. Rogachev - лучший результат функции приспособленности индивида в популяции / The best outcome of an individual’s fitness function in a population - средний результат функции приспособленности популяции / Average result of the population adaptation function Рис. 4. Результаты численного эксперимента при уменьшенной доле скрещиваемых особей до 30 % И с т о ч н и к: выполнено Д.С. Захаровым, А.Ф. Рогачевым Figure 4. Results of numerical experiment at reduced proportion of crossbred individuals up to 30% S o u r c e: by D.S. Zakharov, A.F. Rogachev Анализ диаграммы на рис. 4 показывает, что низкий уровень доли скрещиваемых особей приводит к зацикливанию алгоритма, чего необходимо избегать. Диаграмма показывает, что на определенном этапе большая часть особей пришла к единому неоптимальному решению и не может из него выбраться. Случайная мутация способствует выходу на оптимальное решение, но зачастую не позволяет этого добиться из-за ухудшения показателя целевой функции пригодности, и, соответственно, непрохождения в следующую популяцию. Совершенствование функционирования эволюционных вычислений при решении задачи оптиизации расписания многоуровневого вуза можно совмещать с различными модификациями реализациями непосредственно ГА. Обеспечиваемый при этом синергетический эффект также может способствовать повышению эффективности оптимизации и, прежде всего, сокращению времени достижения при-емлемого времени счета по задаваемому критерию его качества. Для этого можно использовать отдельную программу grid-оптимизации, которую удобно разработать на языке Python. Заключение Проведенные теоретические и численные исследования создания компьютерной программы для оптимизации составления расписания многоуровневого вуза позволили сформулировать следующие выводы. 1. Разработанный программный комплекс, включающий блоки ввода исходных данных (учебных планов дисциплин, аудиторного фонда, учебных групп, преподавателей дисциплин п др.), формирования начального варианта расписания методом случайного выбора, оптимизации расписания методом ГА, модуля статистики, а также вывода результатов оптимизации обеспечивает автоматизированное построение оптимального расписания по заданному критерию, при этом время счета для заданного многоуровневого филиала ВолгГТУ составляло порядка 6…30 минут. 2. Разработанный модуль статистики обеспечивает возможность проведения автоматизированного тестирования различных параметров с проведением анализа и вывода на экран статистических данных о процессе тестирования. Также данный модуль на основе проведенных тестов способен выдавать оптимальный набор параметров на основе конкретных данных, что можно использовать для оценки эффективности функционирования текущей конфигурации ГА, сравнения вариантов его модификации и совершенствования гиперпараметров, что следует выполнять для каждого набора параметров оптимизируемого расписания, а также при их существенном изменении. 3. Совершенствование функционирования эволюционно-генетического алгоритма при решении задачи оптимизации расписания многоуровневого вуза возможно совмещать с различными модификациями реализации непосредственно ГА. Достигаемый при этом синергетический эффект может способствовать повышению эффективности оптимизации и сокращению времени ее достижения по задаваемому критерию его качества.

About the authors

Dmitry S. Zakharov

Volgograd State Technical University

Email: zakator@bk.ru
ORCID iD: 0009-0009-6665-510X
SPIN-code: 8794-7672

Applicant, Senior Lecturer of the Department of Mathematical and Natural Sciences, Sebryakovsky branch

28 Lenina ave., Volgograd, 400005, Russian Federation

Aleksey F. Rogachev

Volgograd State Technical University

Author for correspondence.
Email: rafr@mail.ru
ORCID iD: 0000-0002-3077-6622
SPIN-code: 8413-5020

Doctor of Technical Sciences, Professor of the Department of Information Systems in Economics

28 Lenina ave., Volgograd, 400005, Russian Federation

References

Supplementary files