ПРО РОЗВ'ЯЗУВАННЯ ЗАДАЧI СКЛАДАННЯ РОЗКЛАДУ ЗАНЯТЬ, ВИКОРИСТОВУЮЧИ ГЕНЕТИЧНИЙ АЛГОРИТМ

O. Zanevych, V. Kukharskyy

Анотація


Задача складання розкладу занять — актуальна проблема у закладах вищої освіти. Для її розв'язування існує низка класичних методів: методи динамічного програмування, цілочисельного програмування, нелінійного програмування, метод гілок і меж, методи імітаційного моделювання, метод розмальовки графа, задача про призначення та інші. Особливістю цих методів є математична строгість формулювання задачі складання розкладу занять та алгоритмів її розв'язання. Вони мають зазделегіть визначені час збіжності і точність розв'язку, дають змогу проводити оцінки вливу різних чинників на час знаходження розв'язку. Недоліком усіх класичних методів є те, що вони використовують ітераційну процедуру пошуку або поліпшення деякого початкового наближення, де пошук результату відбувається в околі цього наближення. Це означає, що отриманий результат безпосередньо залежить від деякого початкового наближення і природно виникає проблема його вибору, яка призводить до необхідності множинного експерименту з різними значеннями початкового наближення, що суттєво збільшує час пошуку остаточного розв'язку. Також для класичних методів характерна складність одержуваної математичної моделі та різке (експоненціальне) зростання витрат часу на пошук прийнятного розв'язку з ростом обсягів вихідної інформації. Для уникнення вищенаведених недоліків класичних методів задачу складання розкладу занять можна розв'язати, застосувуючи генетичний алгоритм. Запропоновано один варіант заданння цільової функції для оптимізації розкладу та визначено на її підставі функцію придатності. Описано реалізацію класичних генетичних операторів: кросинговера, мутації та вибірки для популяції розкладів, а також запропоновано оператор поправки, який допомагає поліпшити варіанти розкладу, отримані внаслідок викликів класичних генетичних операторів. Для реалізації операторів кросинговеру та поправки введено поняття локальної цільової функції. Наведено загальну схему генетичного алгоритму для розв'язування задачі складання розкладу та результати числового експеременту.

Повний текст:

PDF

Посилання


Бабкин Э.А., Ретинский И.М. Проектирование и реализация алгоритмов составления учебного расписания на основе многоагентных технологий // Материалы научно-технической конференции. Технические, программные и математические аспекты управления сложными распределенными системами – Нижний Новгород, 2003 – C. 10–12.

Безгинов А.Н., Трегубов С.Ю. Обзор существующих методов составления расписания // Информационные технологии и программирование: межвузовский сборник статей. Выпуск 2 (14) – Москва: МГИУ, 2005.

Вагнер Г. Основы исследования операций: в 3 т. Т. 2 / пер. с англ. Алтаева В.Я. – Москва:Мир, 1973 – 488 с.

Вагнер Г. Основы исследования операций: в 3 т. Т. 3 / пер. с англ. Вавилова Б.Т. – Москва: Мир, 1972 – 501 с.

Каширина И.Л. Генетический алгоритм решения квадратичной задачи о назначениях специального вида // Вестник ВГУ, № 1 – 2003.

Клеванский Н.Н., Макарцова Е.А., Костин С.А. Моделирование стратегии формирования расписания занятий ВУЗа средствами реляционной алгебры // Прикладные проблемы образовательной деятельности: Межвуз. сб. научн. тр. Воронеж – ВГПУ, 2003 – С. 71–74.

Клеванский Н.Н. Макарцова Е.А. Формирование расписания с использованием динамических критериев загруженности // XI Международная конференция-выставка ``Информационные технологии в образовании''. Часть IV – Москва: МИФИ, 2001 – С. 139–140.

Конвей Р.В. Теория расписаний. – Москва: Наука, 1975 – 395 с.

Маслов М.Г. Эвристический алгоритм решения задачи составления расписания учебных занятий в вузе // Математические методы в технике и технологиях: Сб. трудов XV Международной научной конференции. В 10–и т. 2–4 июня 2002 г. – Тамбов, 2002 – Т. 9, С. 86–88.

Строкина Ю.Г. Алгоритмические процедуры формирования гетерогенных расписаний для производственных систем: дис. на соискание ученой степени канд. техн. наук. – Уфа: УГАТУ, 1997 – 150 с.

Танаев В.С. Теория расписаний – Москва: Наука, 1989 – 256 с.

Танаев В.С., Шкуба В.В. Введение в теорию расписаний – Москва: Наука, 1975 – 256 с.

Coello C.A., Van Veldhuizen D.A., Lamont G B. Evolutionary Algorithms for Solving Multi-Objective Problems. Second Edition – Springer, 2007.

Colorni A., Dorigo M., Maniezzo V. Genetic Algorithm To Solve The Timetable Problem // Research Gate – 1994.

Cowling P., Kendall G., Han L. An Investigation of a Hyperheuristic Genetic Algorithm Applied to a Trainer Scheduling Problem // Proceedings of the 2002 Congress on Evolutionary Computation (CEC 2002) – 2002 – pp. 1185–1190.

Cowling P., Kendall G., Soubeiga E. Hyperheuristics: A Robust Optimisation Method Applied to Nurse Scheduling // Proceedings of the VII Parallel Problem Solving From Nature (PPSN VlI), Lecture Notes in Computer Science – 2002 – Vol. 2439, Springer, pp. 7–11.

De Jong K.A., Spears W.M. Using genetic algorithms to solve NP-complete problems // Proceedings of the Third International Conference on Genetic Algorithms – Morgan Kaufmann, 1989.

Deb K., Manikanth M., Mishra S. Towards a Quick Computation of Well-Spread Pareto Optimal Solutions // Proceedings of the 2nd International Conference on Evolutionary Multi-Criterion Optimization (EMO 2003), Faro Portugal, Lecture Notes in Computer Science – 2003 – Vol. 2632, Springer, pp. 222–236.

Farina M., Amato P. Fuzzy Optimality and Evolutionary Multi-Objective Optimization // Proceedings of the 2nd International Conference on Evolutionary Multi-Criterion Optimization (EMO 2003), Faro Portugal, Lecture Notes in Computer Science – 2003 – Vol. 2632, Springer, pp. 58–72.

Garey M.R., Johnson D.S. Computers and intractability, W.H. Freeman & Company, 1979.

Gaw A., Rattadilok P., Kwan R.S. Distributed Choice Function Hyper-Heuristics for Timetabling and Scheduling // Proceedings of the 2004 International Conference on the Practice and Theory of Automated Timetabling (PATAT 2004) – Pittsburgh, 2004 – pp. 495–497.

Gunawan S., Farhang A., Azarm S. Multilevel Multiobjective Genetic Algorithm Using Entropy to Preserve Diversity // Proceedings of the 2nd International Conference on Evolutionary Multi-Criterion Optimization (EMO 2003), Faro Portugal, Lecture Notes in Computer Science – 2003 – Vol. 2632, Springer, pp. 148–161.

Han L., Kendall G. Investigation of a Tabu Assisted Hyper-Heuristic Genetic Algorithm //Proceedings of the 2003 Congress on Evolutionary Computation (CEC2003) – Canberra, 2003 – pp. 2230–2237.

Jain T., Jamil N. Genetic Algorithm as a General Approach to Time Tabling Problem // Eur. J. Bus .Manag. – 2015 – Vol. 7, no. 4, pp. 7–11.

Horn J. Niche Distributions on the Pareto Optimal Front // Proceedings of the 2nd International Conference on Evolutionary Multi-Criterion Optimization (EMO 2003), Faro Portugal, Lecture Notes in Computer Science – 2003 – Vol. 2632, Springer, pp. 365–375.

Jin H., Wong M.L. Adaptive Diversity Maintenance and Convergence Guarantee in Multiobjective Evolutionary Algorithms // Proceedings of the 2003 Congress on Evolutionary Computation (CEC 2003) – Camberra, 2003 – pp. 2498–2505.

Kumar R., Rockett P. Improved Sampling of the Pareto-front in Multiobjective Genetic Optimization by Steady-state Evolution: A Pareto Converging Genetic Algorithm // Evolutionary Computation – 2002 – Vol. 10, No. 3, pp. 283–314.

Laumams M., Thiele L., Deb K., Zitzler E. Combining Convergence and Diversity in Evolutionary Multiobjective Optimization // Evolutionary Computation – 2002 – Vol. 10, No. 3, pp. 263–282.

Mostaghim S., Teich J. The Role of e-dominance in Multi-objective Particle Swarm Optimization Methods // Proceedings of the 2003 Congress on Evolutionary Computation (CEC 2003) – Camberra, 2003 – pp. 1764–1771.

Muehlenbein H. Parallel genetic algorithms, population genetics and combinatorial optimization, Proceedings of the Third International Conference on Genetic Algorithms – Morgan Kaufmann, 1989.

Peng Y., Qu X., Sh J. A hybrid simulation and genetic algorithm approach to determine the optimal scheduling templates for open access clinics admitting walk-in patients // Computers & Industrial Engineering, 72 – 2014 – pp. 282–296.

Premasiril D.M. University Timetable Scheduling Using Genetic Algorithm Approach Case Study: Rajarata University of Sri Lanka // Journal of Engineering Research and Application ISSN: 2248-9622 – 2018 – Vol. 8, Issue 12 (Part -II), pp. 30-35.

Premlata L.R., Sonawane A. Solving the class timetable problem by using genetic algorithm and tabu search algorithm // IRD India – 2014 – Vol. 3, no. 5, pp. 45–50.




DOI: http://dx.doi.org/10.30970/vam.2019.27.10725

Посилання

  • Поки немає зовнішніх посилань.