Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Evolutionary Intelligence
Published in: Evolutionary Intelligence 4/2021

13-08-2020 | Research Paper

Novel operators for quantum evolutionary algorithm in solving timetabling problem

Author: Mohammad-H. Tayarani-N.

Published in: Evolutionary Intelligence | Issue 4/2021

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Timetabling is a well-known combinatorial optimization problem which belongs to the class of NP hard problems. Quantum Evolutionary Algorithms (QEA) are highly suitable for the class of combinatorial optimization problems, but since proposed, they have not been used in solving this problem. In this paper we develop new operators for QEA to improve its performance in solving timetabling problem. The first operator we develop is a reinitialization operator which checks the population and when it is converged, reinitializes it to maintain the diversity. The other operator is called the Diversity Preserving operator which monitors the q-individuals, and if it finds more than one q-individuals searching around the same local optimum, reinitializes some of them to make sure different q-individuals are exploiting different regions in the search space. In this paper we also study the population size and the population structure of QEA in solving timetabling problem. In order to test the proposed algorithm, we perform experiments and compare the proposed algorithm to the existing algorithms on some well-known benchmark functions.
previous article Neighborhood centroid opposite-based learning Harris Hawks optimization for training neural networks
next article An extensive experimental evaluation of automated machine learning methods for recommending classification algorithms

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Literature
1.
2.
A lagrangian heuristic algorithm for a real-world train timetabling problem. Discrete Applied Mathematics 154(5):738–753 (2006). IV ALIO/EURO Workshop on Applied Combinatorial Optimization
3.
Abdullah S, Burke EK, McCollum B (2007) Using a randomised iterative improvement algorithm with composite neighbourhood structures for the university course timetabling problem. Springer, Boston, pp 153–169MATH
4.
Akkan C, Gülcü A (2018) A bi-criteria hybrid genetic algorithm with robustness objective for the course timetabling problem. Comput Oper Res 90:22–32MathSciNetMATHCrossRef
5.
Al-Yakoob SM, Sherali HD (2015) Mathematical models and algorithms for a high school timetabling problem. Comput Oper Res 61:56–68MathSciNetMATHCrossRef
6.
Alba E, Dorronsoro B (2005) The exploration/exploitation tradeoff in dynamic cellular genetic algorithms. IEEE Trans Evol Comput 9(2):126–142CrossRef
7.
Alba E, Tomassini M (2002) Parallelism and evolutionary algorithms. IEEE Trans Evol Comput 6(5):443–462CrossRef
8.
Arabas J, Michalewicz Z, Mulawka J (1994) Gavaps-a genetic algorithm with varying population size. In: Proceedings of the 1st IEEE conference on evolutionary computation, 1994. IEEE world congress on computational intelligence. vol 1, pp 73–78
9.
Azimi ZN (2005) Hybrid heuristics for examination timetabling problem. Appl Math Comput 163(2):705–733MathSciNetMATH
10.
Babaei H, Karimpour J, Hadidi A (2015) A survey of approaches for university course timetabling problem. Comput Ind Eng 86:43–59CrossRef
11.
Battistutta M, Ceschia S, Cesco FD, Gaspero LD, Schaerf A (2019) Modelling and solving the thesis defense timetabling problem. J Oper Res Soc 70(7):1039–1050CrossRef
12.
Beligiannis GN, Moschopoulos CN, Kaperonis GP, Likothanassis SD (2008) Applying evolutionary computation to the school timetabling problem: the greek case. Comput Oper Res 35(4):1265–1280MATHCrossRef
13.
Bryden KM, Ashlock DA, Corns S, Willson SJ (2006) Graph-based evolutionary algorithms. IEEE Trans Evol Comput 10(5):550–567CrossRef
14.
15.
Burke EK, Petrovic S (2002) Recent research directions in automated timetabling. Eur J Oper Res 140(2):266–280MATHCrossRef
16.
Cacchiani V, Furini F, Kidd MP (2016) Approaches to a real-world train timetabling problem in a railway node. Omega 58:97–110CrossRef
17.
Cantú-Paz E (2000) Efficient and accurate parallel genetic algorithms, 1st edn. Kluwer, DordrechtMATH
18.
Causmaecker PD, Demeester P, Berghe GV (2009) A decomposed metaheuristic approach for a real-world university timetabling problem. Eur J Oper Res 195(1):307–318MathSciNetMATHCrossRef
19.
Ceschia S, Schaerf A (2018) Solving the inrc-ii nurse rostering problem by simulated annealing based on large neighborhoods. PATAT
20.
Ceschia S, Thanh NDT, Causmaecker PD, Haspeslagh S, Schaerf A (2015) Second international nurse rostering competition (INRC-II) - problem description and rules-. CoRR arXiv:​1501.​04177
21.
Chang PC, Huang WH, Ting CJ (2010) Dynamic diversity control in genetic algorithm for mining unsearched solution space in tsp problems. Expert Syst Appl 37(3):1863–1878CrossRef
22.
23.
Dang NTT, Ceschia S, Schaerf A, De Causmaecker P, Haspeslagh S (2016) Solving the multi-stage nurse rostering problem. In: Proceedings of the 11th international conference of the practice and theory of automated timetabling, pp 473–475
24.
Detienne B, Péridy L, Pinson Éric, Rivreau D (2009) Cut generation for an employee timetabling problem. Eur J Oper Res 197(3):1178–1184MathSciNetMATHCrossRef
25.
Dick G (2003) The spatially-dispersed genetic algorithm: an explicit spatial population structure for gas. In: The 2003 congress on evolutionary computation, 2003, CEC ’03. vol 4, pp 2455–2461
26.
Duan HB (2010) A hybrid artificial bee colony optimization and quantum evolutionary algorithm for continuous optimization problems. Int J Neural Syst 20(1):39–50CrossRef
27.
Eley M (2007) Ant algorithms for the exam timetabling problem. In: Burke EK, Rudova H (eds) Practice and theory of automated timetabling VI. Springer, Berlin, pp 364–382CrossRef
28.
Fouilhoux P, Ibarra-Rojas O, Kedad-Sidhoum S, Rios-Solis Y (2016) Valid inequalities for the synchronization bus timetabling problem. Eur J Oper Res 251(2):442–450MathSciNetMATHCrossRef
29.
Goh SL, Kendall G, Sabar NR (2017) Improved local search approaches to solve the post enrolment course timetabling problem. Eur J Oper Res 261(1):17–29MathSciNetMATHCrossRef
30.
Gu J, Gu M, Cao C, Gu X (2010) A novel competitive co-evolutionary quantum genetic algorithm for stochastic job shop scheduling problem. Comput Oper Res 37(5):927–937MathSciNetMATHCrossRef
31.
Han CW, Park JI (2006) Population structure of heuristic search algorithm based on adaptive partitioning. In: Advances in applied artificial intelligence, vol 4031. Lecture notes in computer science. Springer, Berlin, pp 238–243
32.
Han H, Kim H (2004) Quantum-inspired evolutionary algorithms with a new termination criterion, \(\text{ h }_\epsilon \) gate, and two-phase scheme. IEEE Trans Evol Comput 8(2):156–169CrossRef
33.
Han KH, Kim JH (2002) Quantum-inspired evolutionary algorithm for a class of combinatorial optimization. IEEE Trans Evol Comput 6(6):580–593CrossRef
34.
Han KH, Kim JH (2003) On setting the parameters of quantum-inspired evolutionary algorithm for practical application. In: The 2003 congress on evolutionary computation, 2003, CEC ’03. vol 1, pp 178–194
35.
Han KH, Park KH, Lee CH, Kim JH (2001) Parallel quantum-inspired genetic algorithm for combinatorial optimization problem. In: Proceedings of the 2001 congress on evolutionary computation, vol 2, pp 1422–1429
36.
Haupt R (2000) Optimum population size and mutation rate for a simple real genetic algorithm that optimizes array factors. In: Antennas and propagation society international symposium, 2000, vol 2. IEEE, pp 1034–1037
37.
Hong Y, Ren Q, Zeng J (2005) Adaptive population size for univariate marginal distribution algorithm. In: The 2005 IEEE congress on evolutionary computation, 2005, vol 2, pp 1396–1402
38.
39.
Jang JS, Han KH, Kim JH (2003) Quantum-inspired evolutionary algorithm-based face verification. In: Genetic and evolutionary computation 2003, vol 2724. Lecture Notes in Computer Science. Springer, Berlin, pp 214–214
40.
Jang JS, Han KH, Kim JH (2004) Face detection using quantum-inspired evolutionary algorithm. In: Congress on evolutionary computation, 2004. CEC 2004. vol 2, pp 2100–2106
41.
Kaveh A, Shahrouzi M (2006) A hybrid ant strategy and genetic algorithm to tune the population size for efficient structural optimization. Emerald J Eng Comput 24:237–254MATHCrossRef
42.
Kennedy J, Mendes R (2002) Population structure and particle swarm performance. In: Proceedings of the 2002 congress on evolutionary computation, 2002. CEC ’02. vol 2, pp 1671–1676
43.
Khor E, Tan K, Wang M, Lee T (2000) Evolutionary algorithm with dynamic population size for multi-objective optimization. In: 26th Annual conference of the IEEE industrial electronics society, 2000. IECON 2000. vol 4, pp 2768–2773
44.
Koumousis V, Katsaras C (2006) A saw-tooth genetic algorithm combining the effects of variable population size and reinitialization to enhance performance. IEEE Trans Evol Comput 10(1):19–28CrossRef
45.
Koumousis VK, Katsaras CP (2002) The effect of oscillating population size and re-initialization on the performance of genetic algorithms. In: Proceedings of the third international conference on engineering computational technology, ICECT’03, Civil-Comp press, Edinburgh, UK, pp 185–186
46.
Legrain A, Omer J, Rosat S (2017) A rotation-based branch-and-price approach for the nurse scheduling problem. Math Program Comput 1:1–34MATH
47.
Leite N, Melício F, Rosa AC (2019) A fast simulated annealing algorithm for the examination timetabling problem. Expert Syst Appl 122:137–151CrossRef
48.
Leung JY (2004) Bus and train driver scheduling, handbook of scheduling: algorithms, models, and performance analysis, Chapter 51. CRC Press, Boca RatonCrossRef
49.
Leung JY (2004) Sports scheduling, handbook of scheduling: algorithms, models, and performance analysis, Chapter 52. CRC Press, Boca RatonCrossRef
50.
Leung JY (2004) University timetabling, handbook of scheduling: algorithms, models, and performance analysis, Chapter 45. CRC Press, Boca RatonCrossRef
51.
Lewis R, Thompson J (2015) Analysing the effects of solution space connectivity with an effective metaheuristic for the course timetabling problem. Eur J Oper Res 240(3):637–648MathSciNetMATHCrossRef
52.
Li D, Wang L (2002) A study on the optimal population size of genetic algorithm. In: Proceedings of the 4th World Congress on Intelligent Control and Automation 2002, vol 4, pp 3019–3021
53.
Li Y, Zhang Y, Zhao R, Jiao L (2004) The immune quantum-inspired evolutionary algorithm. IEEE Int Conf Syst Man Cybern 4:3301–3305
54.
Li Z, Xu B, Yang L, Chen J, Li K (2009) Quantum evolutionary algorithm for multi-robot coalition formation. In: Proceedings of the 1st ACM/SIGEVO summit on genetic and evolutionary computation. ACM, New York, pp 295–302
55.
Lu Q, Shen G, Yu R (2003) A chaotic approach to maintain the population diversity of genetic algorithm in network training. Comput Biol Chem 27(3):363–371CrossRef
56.
Mallipeddi R, Suganthan P (2008) Empirical study on the effect of population size on differential evolution algorithm. In: IEEE Congress on Evolutionary Computation, 2008, CEC 2008 (IEEE World Congress on Computational Intelligence), pp 3663 –3670
57.
Mischek F, Musliu N (2016) Integer programming and heuristic approaches for a multi-stage nurse rostering problem. In: PATAT 2016: Proceedings of the 11th international conference of the practice and theory of automated timetabling, PATAT
58.
Mohammad T, Reza ATM (2009) Improvement of quantum evolutionary algorithm with a functional sized population. In: Mehnen J, Koppen M, Saad A, Tiwari A (eds) Applications of soft computing. Springer, Berlin, Heidelberg, pp 389–398CrossRef
59.
60.
Árton PD, de Araújo OC, Buriol LS (2017) A column generation approach to high school timetabling modeled as a multicommodity flow problem. Eur J Oper Res 256(3):685–695MathSciNetMATHCrossRef
61.
Park S, Kim E, Cho BJ (2003) Genetic algorithm-based video segmentation with adaptive population size. In: Michaelis B, Krell G (eds) Pattern recognition. Lecture notes in computer science, vol 2781. Springer, Berlin, pp 426–433
62.
63.
Pillay N, Özcan E (2019) Automated generation of constructive ordering heuristics for educational timetabling. Ann Oper Res 275(1):181–208MathSciNetMATHCrossRef
64.
Post G, Kingston JH, Ahmadi S, Daskalaki S, Gogos C, Kyngas J, Nurmi C, Musliu N, Pillay N, Santos H, Schaerf A (2014) Xhstt: an xml archive for high school timetabling problems in different countries. Ann Oper Res 218(1):295–301MathSciNetMATHCrossRef
65.
Prügel-Bennett A, Tayarani-N MH (2011) Maximum satisfiability: anatomy of the fitness landscape for a hard combinatorial optimisation problem. IEEE Trans Evol Comput 16(3):319–338CrossRef
66.
Qin C, Zheng J, Lai J (2007) A multiagent quantum evolutionary algorithm for global numerical optimization. In: Life system modeling and simulation, vol 4689. Lecture notes in computer science. Springer, Berlin/Heidelberg, pp 380–389
67.
Raghavjee R, Pillay N (2015) A genetic algorithm selection perturbative hyper-heuristic for solving the school timetabling problem. ORiON 31(1):39–60CrossRef
68.
dos Santos Nicolau A, Schirru R, de Moura Meneses AA (2011) Quantum evolutionary algorithm applied to transient identification of a nuclear power plant. Prog Nucl Energy 53(1):86–91CrossRef
69.
Saviniec L, Constantino AA (2017) Effective local search algorithms for high school timetabling problems. Appl Soft Comput 60:363–373CrossRef
70.
Saviniec L, Santos MO, Costa AM (2018) Parallel local search algorithms for high school timetabling problems. Eur J Oper Res 265(1):81–98MathSciNetMATHCrossRef
71.
Schaerf A (1999) A survey of automated timetabling. Artif Intell Rev 13(2):87–127CrossRef
72.
Sekaj I, Oravec M (2009) Selected population characteristics of fine-grained parallel genetic algorithms with re-initialization. In: Proceedings of the 1st ACM/SIGEVO summit on genetic and evolutionary computation, GEC ’09. ACM, pp 945–948
73.
Sekaj I, Perkacz J (2007) Some aspects of parallel genetic algorithms with population re-initialization. In: IEEE Congress on evolutionary computation, 2007, CEC 2007. pp 1333–1338
74.
Sheskin DJ (2003) Handbook of parametric and nonparametric statistical procedures. CRC Press, Boca RatonMATHCrossRef
75.
Shi X, Wan L, Lee H, Yang X, Wang L, Liang Y (2003) An improved genetic algorithm with variable population-size and a pso-ga based hybrid evolutionary algorithm. In: International conference on machine learning and cybernetics, 2003, vol 3, pp 1735–1740
76.
Shimodaira H (1997) Dcga: a diversity control oriented genetic algorithm. In: Proceedings of the 9th IEEE international conference on tools with artificial intelligence, 1997, pp 367 –374
77.
Shimodaira H (2001) Methods for reinitializing the population to improve the performance of a diversity-control-oriented genetic algorithm. IEICE Trans Inf Syst E84–D(12):1745–1755
78.
Skoullis VI, Tassopoulos IX, Beligiannis GN (2017) Solving the high school timetabling problem using a hybrid cat swarm optimization based algorithm. Appl Soft Comput 52:277–289CrossRef
79.
Song T, Liu S, Tang X, Peng X, Chen M (2018) An iterated local search algorithm for the university course timetabling problem. Appl Soft Comput 68:597–608CrossRef
80.
Tayarani N MH, Akbarzadeh T MR (2008) A cellular structure and diversity preserving operator in quantum evolutionary algorithms. In: 2008 IEEE congress on evolutionary computation (IEEE world congress on computational intelligence), Hong Kong, China, 1–6 June 2008, pp 2665–2670
81.
Tayarani-N M, Akbarzadeh-T M (2008) A sinusoid size ring structure quantum evolutionary algorithm. In: 2008 IEEE conference on cybernetics and intelligent systems, Chengdu, China, 21–24 September 2008, pp 1165–1170
82.
Tayarani-N MH, Akbarzadeh-T MR (2014) Improvement of the performance of the quantum-inspired evolutionary algorithms: structures, population, operators. Evol Intel 7(4):219–239
83.
Tayarani-N M, Prügel-Bennett A (2014) On the landscape of combinatorial optimization problems. IEEE Trans Evol Comput 18(3):420–434CrossRef
84.
Tayarani-N M-H, Prügel-Bennett A (2015) Anatomy of the fitness landscape for dense graph-colouring problem. Swarm Evol 22:47–65CrossRef
85.
Tayarani-N M-H, Prügel-Bennett A (2015) Quadratic assignment problem: a landscape analysis. Evol Intel 8(4):165–184CrossRef
86.
Tayarani-N M-H, Prügel-Bennett A (2016) An analysis of the fitness landscape of travelling salesman problem. Evol Comput 24(2):347–384CrossRef
87.
Tsoy Y (2003) The influence of population size and search time limit on genetic algorithm. In: The 7th Korea-Russia international symposium on science and technology, 2003. Proceedings KORUS 2003. vol 3, pp 181–187
88.
Turabieh H, Abdullah S, McCollum B (2009) Electromagnetism-like mechanism with force decay rate great deluge for the course timetabling problem. In: Wen P, Li Y, Polkowski L, Yao Y, Tsumoto S, Wang G (eds) Rough sets and knowledge technology. Springer, Berlin, pp 497–504CrossRef
89.
Turabieh H, Abdullah S, McCollum B, McMullan P (2010) Fish swarm intelligent algorithm for the course timetabling problem. In: Yu J, Greco S, Lingras P, Wang G, Skowron A (eds) Rough set and knowledge technology. Springer, Berlin, pp 588–595CrossRef
90.
Valouxis C, Housos E (2003) Constraint programming approach for school timetabling. Comput Oper Res 30(10):1555–1572 Part Special Issue: Analytic Hierarchy ProcessMATHCrossRef
91.
Vlachogiannis J, Lee K (2008) Quantum-inspired evolutionary algorithm for real and reactive power dispatch. IEEE Trans Power Syst 23(4):1627–1636CrossRef
92.
Wang Y, Feng XY, Huang YX, Pu DB, Zhou WG, Liang YC, Zhou CG (2007) A novel quantum swarm evolutionary algorithm and its applications. Neurocomputing 70(4):633–640CrossRef
93.
Wilcoxon F (1945) Individual comparisons by ranking methods. Biomet Bull 1(6):80–83CrossRef
94.
Xiao J, Xu J, Chen Z, Zhang K, Pan L (2009) A hybrid quantum chaotic swarm evolutionary algorithm for dna encoding. Comput Math Appl 57(11):1949–1958CrossRef
95.
Yang S, Wang M, Jiao L (2004) A novel quantum evolutionary algorithm and its application. In: Congress on evolutionary computation, 2004, CEC2004. vol 1, pp 820–826
96.
Yong H (2007) Optimal population size for partheno-genetic algorithm. In: Chinese Control Conference, 2007. CCC 2007, pp 105–106
97.
You X, Liu S, Shuai D (2006) On parallel immune quantum evolutionary algorithm based on learning mechanism and its convergence. In: Advances in Natural Computation, vol 4221. Lecture Notes in Computer Science. Springer, Berlin, pp 903–912
98.
Yukiko Y, Nobue A (1994) A diploid genetic algorithm for preserving population diversity—pseudo-meiosis ga. In: Davidor Y, Schwefel HP, Männer R (eds) Parallel problem solving from nature—PPSN III, lecture notes in computer science, vol 866. Springer, Berlin, pp 36–45CrossRef
99.
Zhang D, Liu Y, M’Hallah R, Leung SC (2010) A simulated annealing with a new neighborhood structure based algorithm for high school timetabling problems. Eur J Oper Res 203(3):550–558MATHCrossRef
100.
Zhong W, Liu J, Xue M, Jiao L (2004) A multiagent genetic algorithm for global numerical optimization. IEEE Trans Syst Man Cybern Part B (Cybern) 34(2):1128–1141CrossRef
101.
Zhou A, Jin Y, Zhang Q, Sendhoff B, Tsang E (2007) Prediction-based population re-initialization for evolutionary dynamic multi-objective optimization. In: Proceedings of the 4th international conference on Evolutionary multi-criterion optimization, EMO’07. Springer, Berlin, pp 832–846
102.
Zhu K (2003) A diversity-controlling adaptive genetic algorithm for the vehicle routing problem with time windows. In: 15th IEEE International conference on proceedings tools with artificial intelligence, 2003. pp 176–183
Metadata
Title
Novel operators for quantum evolutionary algorithm in solving timetabling problem
Author
Mohammad-H. Tayarani-N.
Publication date
13-08-2020
Publisher
Springer Berlin Heidelberg
Published in
Evolutionary Intelligence / Issue 4/2021
Print ISSN: 1864-5909
Electronic ISSN: 1864-5917
DOI
https://doi.org/10.1007/s12065-020-00438-0

Other articles of this Issue 4/2021

Evolutionary Intelligence 4/2021 Go to the issue

Research Paper

Automated mammogram breast cancer detection using the optimized combination of convolutional and recurrent neural network

Research Paper

Distributed-elite local search based on a genetic algorithm for bi-objective job-shop scheduling under time-of-use tariffs

Research Paper

Intelligent environment for advanced brain imaging: multi-agent system for an automated Alzheimer diagnosis

Review Article

Just noticeable difference color space consistency spectral clustering based on firefly algorithm for image segmentation

Research Paper

The hub location’s method for solving optimal control problems

Research Paper

Artificial intelligence and game theory controlled autonomous UAV swarms

Premium Partner

    Image Credits