Performance Evaluation of Genetic Algorithm and Simulated Annealing in Solving Kirkman Schoolgirl Problem.

Christopher A Oyeleye, Victoria O Dayo-Ajayi, Emmanuel Abiodun, Alabi O Bello

Abstract


This paper provides performance evaluation of Genetic Algorithm and Simulated Annealing in view of their software complexity and Simulation runtime. Kirkman Schoolgirl is about arranging fifteen schoolgirls into five triplets in a week with a distinct constraint of no two schoolgirl must walk together in a week. The developed model was simulated using Matlab version R2015a. The performance evaluation of both Genetic algorithm and Simulated Annealing was carried out in terms of program size, program volume, program effort and the intelligent content of the program. The results obtained show that the runtime for GA and SA are 11.23sec and 6.20sec respectively. The program size for GA and SA are 2.01kb and 2.21kb, respectively. The lines of code for GA and SA are 324 and 404, respectively. The program volume for GA and SA are 1121.58 and 3127.92, respectively. The program effort for GA and SA are 135021.70 and 30633.26 respectively, while the intelligent content of the program for GA and SA are 72.461 and 41.06, respectively. Both Algorithms are good solvers, however it can be concluded that Genetic Algorithm outperformed simulated Annealing in most of the evaluated parameters.

Keywords:   Genetic Algorithm, Simulated Annealing, Kirkman Schoolgirl, software complexity and simulation runtime


Full Text:

PDF

References


Abed, M. H., and Alicia, Y. (2013). Hybridizing Genetic Algorithm and Record-to-Record Travel Algorithm for Solving Uncapacitated Examination Timetabling Problem. Electronic Journal of Computer Science and Information Technology: eJCIST, 4(1).

Adewole, A.P., Otubamowo, K., Egunjobi, T. O., and Ng, K. M. (2012). A comparative study of simulated annealing and genetic algorithm for solving the travelling salesman problem. International Journal of Applied Information Systems (IJAIS), 4(4), 6-12.

Akinwale, O.C., Olatunde, O.S., Olusayo, O. E., and Temitayo, F. (2014). Hybrid Metaheuristic Simulated Annealing and Genetic Algorithm for Solving Examination Timetabling Problem. International Journal of Computer Science and Engineering (IJCSE), India, 3(5), 7-22.

Bhatia, A., Singh, A., and Goyal, R. (2015). A Hybrid Autonomic Computing-Based Approach to Distributed Constraint Satisfaction Problems. Computers, 4(1), 2-23.

Blum, C., Puchinger, J., Raidl, G. R., and Roli, A. (2011). Hybrid metaheuristics in combinatorial optimization: A survey. Applied Soft Computing, 11(6), 4135-4151.

Cao, P., Fan, Z., Gao, R. X., and Tang, J. (2017). Solving Configuration Optimization Problem with Multiple Hard Constraints: An Enhanced Multi-Objective Simulated Annealing Approach. arXiv preprint arXiv:1706.03141.

Froncek, D., and Kubesa, M. (2011). Rectangular table negotiation problem revisited. Open Mathematics, 9(5), 1114-1120.

Hanafy, T. O., Zaini, H., Shoush, K. A., and Aly, A. A. (2014). Recent trends in soft computing techniques for solving real time engineering problems. International Journal of Control, Automation and Systems, 3(1), 27-33.

Nopiah, Z. M., Khairir, M. I., Abdullah, S., Baharin, M. N., and Arifin, A. (2010, February). Time complexity analysis of the genetic algorithm clustering method. In Proceedings of the 9th WSEAS International Conference on Signal Processing, Robotics and Automation, ISPRA (pp. 171-176).

Rere, L. R., Fanany, M. I., & Arymurthy, A. M. (2015). Simulated annealing algorithm for deep learning. Procedia Computer Science, 72, 137-144.

Yazdani, M., Khalili, S. M., and Jolai, F. (2016). A parallel machine scheduling problem with two-agent and tool change activities: an efficient hybrid metaheuristic algorithm. International Journal of Computer Integrated Manufacturing, 29(10), 1075-1088.




DOI: http://dx.doi.org/10.46792/fuoyejet.v5i2.477

Refbacks

  • There are currently no refbacks.


Copyright (c) 2020 The Author(s)

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

Powered by ICT and Faculty of Engineering, FUOYE

Copyright © 2020 The Author(s). Published by Faculty of Engineering, FUOYE

image The FUOYEJET website and her metadata are licensed under CC BY-NC