Prey-predator algorithm for discrete problems: a case for examination timetabling problem

The prey-predator algorithm is a metaheuristic algorithm inspired by the interaction between a predatorand its prey. Initial solutions are put into three categories: the better performing solution as the best prey, theworst performing solution as a predator, and the rest as ordinary prey. The best prey totally focuses on exploitingits neighborhood while the predator explores the search space searching for a promising region in the search space. Theordinary prey will be affected by these two extreme search behaviors of exploration and exploitation. The algorithm hasbeen tested and found to be effective in solving different problems arising from different disciplines including engineering,tourism, and management. Originally, the algorithm was designed to deal with continuous problems. However, manyproblems arising from real aspects are not continuous. Hence, in this paper the prey-predator algorithm will be extendedto suit discrete problems. Examination timetabling is used to test the approach. The simulation results with appropriatestatistical analysis show that the approach is as good as the cumulative best performance of results recorded in theliterature for the selected benchmark problems.

PDF

___

[1] Little DL, Murty GK, Sweeney WD, Karel C. An algorithm for the traveling salesman problem. Oper Res 1963; 11: 972-989.
[2] Schrijver A. On the history of combinatorial optimization (till 1960). In: Aardal K, Nemhauser GL, Weismantel R, editors. Discrete Optimization, Volume 12 of Handbooks in Operations Research and Management Science. Amsterdam, the Netherland, Science Direct, 2005, pp. 1-68.
[3] Ayob M, Malik A, Abdullah S, Hamdan AR, Kendall G, Qu R. Solving a practical examination timetabling problem: a case study. In: Gervasi O, Gavrilova M, editors. ICCSA-2007, Part III LNCS, Vol. 4707. Heidelberg, Germany: Springer, 2007, pp. 611-624.
[4] Korf RE. A new algorithm for optimal bin packing. In: Proceedings of the Eighteenth National Conference on Artificial Intelligence; 28 July–1 August 2002; Edmonton, Canada. pp. 731-736.
[5] Yang XS. Nature-Inspired Metaheuristic Algorithms. 2nd ed. London, UK: Luniver Press, 2010.
[6] Bahmani-Firouzi B, Sharifinia S, Azizipanah-Abarghooee R, Niknam T. Scenario-based optimal bidding strategies of GENCOs in the incomplete information electricity market using a new improved prey-predator optimization algorithm. IEEE Syst J 2015; 99: 1-11.
[7] Dai W, Liu Q, Chai T. Particle size estimate of grinding processes using random vector functional link networks with improved robustness. Neurocomputing 2015; 169: 361-372.
[8] Tilahun SL, Goshu NN, Ngnotchouye JMT. Prey predator algorithm for travelling salesman problem: application on the Ethiopian tourism sites. In: Vasant P, Kalaivanthan M. editors. Handbook of Research on Holistic Optimization Techniques in the Hospitality, Tourism, and Travel Industry. Hershey, PA, USA: IGI Global, 2017, pp. 400-422.
[9] Hamadneh N, Tilahun SL, Sathasivam S, Ong HC. Prey-predator algorithm as a new optimization technique using in radial basis function neural networks. Research Journal of Applied Sciences 2013; 8: 383-387.
[10] Tilahun SL, Ong HC. Comparison between genetic algorithm and prey-predator algorithm. Malay J Fund App Sc 2013; 9: 167-170.
[11] Tilahun SL. Prey predator algorithm: a new metaheuristic optimization approach. PhD, Universiti Sains Malaysia, Penang, Malaysia, 2013.
[12] Korte B, Vigen J. Combinatorial Optimization: Theory and algorithm. 2nd ed. Heidelberg, Germany: SpringerVerlag, 2002.
[13] Ross P, Hart E, Corne D. Some observations about GA-based exam timetabling. In: Burke EK, Carter M. editors, LNCS - 1408, Practice and Theory of Automated Timetabling II. Toronto, Canada: Springer-Verlag, 1997, pp. 115–129.
[14] Tilahun SL, Ngnotchouye JMT. Prey predator algorithm with adaptive step length. Int J Bio-Ins Comp 2016; 8: 195-204.
[15] Tilahun SL, Ong HC, Ngnotchouye JMT. Extended prey-predator algorithm with a group hunting scenario. Adv Oper Res 2016; 2016: 1-14.
[16] Tilahun SL, Ong HC. Prey predator algorithm: a new metaheuristic optimization algorithm. Int J Info Tech Dec Mak 2015; 14: 1331-1352.
[17] Tilahun SL. Prey predator hyperheuristic. App Soft Comp 2018; 59: 104-114.
[18] Hamadneh N, Khan W, Tilahun S. Optimization of microchannel heat sinks using prey-predator algorithm and artificial neural networks. Machines 2018; 6: 1-18.
[19] Tilahun SL, Tawhid MA. Swarm hyperheuristic framework. J Heur (in press).
[20] Ong HC, Tilahun SL, Lee WS, Ngnotchouye JMT. Comparative study of prey predator algorithm and firefly algorithm. Intell Aut Soft Comp 2017; 2017: 1-8.
[21] Tilahun SL, Matadi MB. Weight minimization of a speed reducer using prey predator algorithm. Int J Man Mat Mech Eng 2018; 8: 19-32.
[22] Carter MW, Laporte G, Lee SY. Examination timetabling algorithmic strategies and applications. J Oper Res Soci 1996; 47: 373-383.
[23] Qu R, Burke EK, McCollum B, Merlot LTG, Lee SY. A survey of search methodologies and automated system development for examination timetabling. J Sched 2009; 12: 55-89.
[24] Merlot LG, Boland N, Hughes B, Stuckey P. A hybrid algorithm for the examination timetabling problem. In: Burke E, Causmaecker P. editors. Practice and Theory of Automated Timetabling IV. Heidelberg, Germany: Springer, 2003, pp. 207-31.
[25] Burke EK, Newall JP. Enhancing timetable solutions with local search methods, In: Burke EK, Causmaecker P. editors. Practice and Theory of Automated Timetabling. Heidelberg, Germany: Springer, 2003. pp. 195-206.
[26] Caramia M, Dell’Olmo P, Italiano GF. New algorithms for examination timetabling. In: Naher S, Wagner D. editors. 4th International Workshop on Algorithm Engineering (WAE 2000); 5–8 September 2000; Saarbrücken, Germany. Berlin, Germany: Springer. pp. 230-242.
[27] White GM, Xie BS. Examination timetables and tabu search with longer-term memory. In: Burke EK, Erben W. editors. PATAT - 2000: LNCS Vol. 2079; 16–18 August 2000; Konstanz, Germany. Berlin, Germany: Springer. pp. 85-103.
[28] Weng FC, Asmuni HB. An automated approach based On bee swarm in tackling university examination timetabling problem. Int J Eng Comp Sci 2013; 13: 8-23.
[29] Gaspero LD, Schaerf A. Tabu search techniques for examination timetabling. In: Burke EK, Erben W, editors. Practice and Theory of Automated Timetabling III, Third International Conference - PATAT 2000, LNCS 2079; 16–18 August 2000; Konstanz, Germany. Berlin, Germany: Springer. pp. 104-117.
[30] Sabar NR, Ayob M, Kendall G. Solving examination timetabling problems using honeybee mating optimization (ETP-HBMO). In: Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA 2009); 10–12 August 2009; Dublin, Ireland. pp. 115-129.
[31] Snedecor WG, Cochran WG. Statistical Methods. 8th ed. Ames, IA, USA: Iowa State University Press, 1989.