CFP last date
22 April 2024
Reseach Article

Article:Optimization: A Comparative Study of Genetic and Tabu Search Algorithms

by Bajeh, A. O, Abolarinwa, K. O
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 31 - Number 5
Year of Publication: 2011
Authors: Bajeh, A. O, Abolarinwa, K. O
10.5120/3823-5302

Bajeh, A. O, Abolarinwa, K. O . Article:Optimization: A Comparative Study of Genetic and Tabu Search Algorithms. International Journal of Computer Applications. 31, 5 ( October 2011), 43-48. DOI=10.5120/3823-5302

@article{ 10.5120/3823-5302,
author = { Bajeh, A. O, Abolarinwa, K. O },
title = { Article:Optimization: A Comparative Study of Genetic and Tabu Search Algorithms },
journal = { International Journal of Computer Applications },
issue_date = { October 2011 },
volume = { 31 },
number = { 5 },
month = { October },
year = { 2011 },
issn = { 0975-8887 },
pages = { 43-48 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume31/number5/3823-5302/ },
doi = { 10.5120/3823-5302 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:17:22.984350+05:30
%A Bajeh
%A A. O
%A Abolarinwa
%A K. O
%T Article:Optimization: A Comparative Study of Genetic and Tabu Search Algorithms
%J International Journal of Computer Applications
%@ 0975-8887
%V 31
%N 5
%P 43-48
%D 2011
%I Foundation of Computer Science (FCS), NY, USA
Abstract

Examination timetabling problem like all scheduling problems are NP-hard problems in which the complexity and time needed to solve the problem increase with the problem size. This paper aims to compare Genetic Algorithm and Tabu Search approaches to solve this kind of problem. Both algorithms were tested with regard to the quality of generated timetables and the speed with which the timetables are generated using collected test data. The test shows that though both algorithms are capable of handling the examination timetabling problem, the Tabu Search approach can produce better timetables than Genetic Algorithm, even at a greater speed.

References
  1. Wren, A. (1996): Scheduling, Timetabling and Rostering – a special relationship? In Lecture Notes in Computer Science: Practice and Theory of Automated Timetabling, E. Burke and P. Ross, editors. Springer Berlin, Germany, Vol 1153 pp. 46-75.
  2. Garg, P. (2005): A Comparison of Memetic & Tabu Search for the Cryptanalysis of Simplified Data Encryption Standard Algorithm, Journal of Theoretical and Applied Information Technology, Vol IV No. 4, 2005-2008 pp. 360-366.
  3. Verma, A. K., Dave, M. and Joshi, R. C. (2007): Genetic Algorithm and Tabu Search attack on the Mono-Alphabetic Substitution Cipher in Adhoc Networks, Journal of Computer Science(3): pp. 134-137, 2007.
  4. Hou, J. H., Wang, J. M. and Xu, X. J. (1999): A Comparison of Three Heuristic Algorithms for Molecular Docking, Chinese Chemical Letters Vol. 10, No. 7, pp. 615-618, 1999.
  5. Merz, P. and Freisleben, B. (1999): A Comparison of Memetic Algorithms, Tabu Search and Ant Colonies for the Quadratic Assignment Problem, In 1999 Congress on Evolutionary Computation (CEC'99) IEEE Press, Piscataway, NJ, pp. 2063–2070.
  6. Wilke, P. and Ostler, J. (2008): Solving the School Time Tabling Problem using Tabu Search, Simulated Annealing, Genetic and Branch & bound Algorithms. In the proceedings of the 7th International Conference on the Practice and Theory of Automated Timetabling (PATAT 2008), Montreal, http://w1.cirrelt.ca/~patat2008/PATAT_7_PROCEEDINGS/ Papers/Wilke-WD2c.pdf, last accessed 19 April, 2011.
  7. Davis, L. (1991): Handbook of Genetic Algorithms. New York: Van Nostrand Reinhold
  8. Gen, M., Cheng, R. and Lin, L. (2008): Network Models and Optimization; Multiobjective Genetic Algorithm Approach. Springer-Verlag London.
  9. Glover, F. (1990): Tabu search, A tutorial Interfaces, 20(4): pp. 74-94, July 1990
  10. Al-Milli N.R (2010): Hybrid Genetic Algorithms with Great Deluge for Course Timetabling. International Journal of Computer Science and Network Security, Vol.10 No.4. Page 283-288.
  11. Gendreau M, (2002): An Introduction to Tabu Search. http://home.ifi.uio.no/infheur/Bakgrunn/Intro_to_TS_Gendreau.htm (Last visited on 18th October, 2011.)
  12. Stutzle T., grun A., Linke S., Ruttger M.(2000): A Comparison of Nature Inspired Heuristics on the Travelling Salesman Problem, Proceedings of PPSN-VI, Sixth International Conference on Parallel Problem Solving from Nature, volume 1917 of LNCS. http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.791 (Last visited 19th of October, 2011).
  13. Arostegui Jr. M.A, Kadipasaoglu S.N, Khumawala B.M (2006): An empirical comparison of Tabu Search, Simulated Annealing, and Genetic Algorithms for facilities location problems. International Journal of Production Economics (2006) Volume: 103, Issue: 2, Pages: 742-754.
  14. Houck C.R, Joines J.A, Kay M.G (2011): Characterizing Search Spaces For Tabu Search. Currently under second review in European Journal of Operational Research.
Index Terms

Computer Science
Information Sciences

Keywords

Chromosome Examination timetabling Genetic Algorithm Tabu Search Generation