Metaheuristic Methods and Their Application Areas

Year 2013, Volume: 17 Issue: 2, 113 - 128, 01.12.2013

Aytuğ Onan

Abstract

Metaheuristic methods are approximate algorithms that produce efficient and appropriate solutions in an acceptable time for complex optimization problems to which conventional optimization algorithms are not able to provide an acceptable solution. Metaheuristic methods can provide efficient solutions to many different problems, such as scheduling, routing, timetabling, graph coloring owing to being easily adjustable to different problems. In this study, metaheuristic methods are classified as single solution based metaheuristic methods and population based metaheuristic methods based on solution number in search and the main algorithms of each class are introduced. In addition, primary application areas of metaheuristic methods are presented. 

Keywords

Metaheuristic Algorithms, Optimization, Application Areas

Metasezgisel Yöntemler ve Uygulama Alanları

Abstract

Metasezgisel yöntemler, geleneksel eniyileme yöntemlerinin kabul edilebilir bir çözüm üretemediği karmaşık eniyileme problemleri için kabul edilebilir bir zaman diliminde etkin ve uygun çözümler üretebilen yaklaşık algoritmalardır. Metasezgisel yöntemler, farklı problemlere kolayca uyarlanabilmeleri sayesinde çizelgeleme, rotalama, zaman planlama, çizge boyama gibi birçok farklı probleme etkin çözümler getirebilmektedir. Bu çalışma kapsamında, metasezgisel yöntemler, arama çözüm sayısına dayalı olarak, tek çözüme dayalı ve toplum tabanlı metasezgisel yöntemler olarak sınıflandırılmış ve bu sınıflar içerisinde incelenebilecek temel algoritmalar tanıtılmıştır. Ayrıca, metasezgisel yöntemlerin başlıca uygulama alanları sunulmuştur.

Keywords

Metasezgisel Yöntemler, Eniyileme, Uygulama Alanları

References

• Birattari, M., Paquette, L., Stützle, T. ve Varrentrapp, K. (2001) “Classification of Metaheuristics and Design of Experiments for the Analysis of Components” Teknik Rapor, AIDA-01-05.
• Blum, C. ve Roli, A. (2003) “Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison”, ACM Computing Surveys, 35(3):268-308.
• Brownlee, J. (2011) “Clever Algorithms: Nature-Inspired Programming Recipes”, 1st Edition, Lulu Enterprises.
• Busetti, F. (2013) “Simulated Annealing Overview”, http://163.18.62.64/wisdom/ Simulated% 20 annealing%20overview.pdf , (11.09.2013).
• Crainic, T.G. ve Toulouse, M. (2003) “Parallel Strategies for Meta-heuristics” Glover et al. (eds) Handbook of Metaheuristics, Kluwer Academic Publishers.
• Dorigo, M., DiCaro, G. ve Gambardella, L. (1999) “Ant Algorithms for Discrete Optimization”, Artificial Life, 5:137-172.
• Dorigo, M. ve Gambardella, L. (1997) “Ant Colonies for the Travelling Salesman Problem”, Biosystems, 43(2):73-81.
• Dorigo, M. ve Stützle, T. (2004) “Ant Colony Optimization”, Cambridge, MIT Press.
• Dumitrescu, I. ve Stützle, T. (2003) “Combinations of Local Search and Exact Algorithms”, Cagnoni et al. (eds) Applications of Evolutionary Computing, Springer.
• Eglese, R.W. (1990) “Simulated Anneling: A Tool for Operational Research”, European Journal of Operational Research, 46:271-281.
• Engelbrecht, A. (2007) “Computational Intelligence: An Introduction”, 2nd Edition, Wiley.
• Gendreau, M. (2003) “An Introduction to Tabu Search” Glover et al. (eds) Handbook of Metaheuristics, Kluwer Academic Publishers.
• Glover, F. (1990) “Tabu Search: A Tutorial”, Interfaces, 20:74-94.
• Goffe, W.L., Ferrier, G.D. ve Rogers, J. (1994) “Global Optimization of Statistical Functions with Simulated Annealing”, Journal of Econometrics, 60(1-2):65- 99.
• Grosan, C., Abraham, A. ve Chis, M. (2006) “Swarm Intelligence in Data Mining” Abraham et al. (eds) Swarm Intelligence in Data Mining, Springer.
• Henderson, D., Jacobson, S.H. ve Johson, A.W. (2003) “The Theory and Practice of Simulated Annealing” Glover et al. (eds) Handbook of Metaheuristics, Kluwer Academic Publishers.
• Kirkpatrick, S., Gelatt, C. ve Vecchi, M.P. (1983) “Optimization by Simulated Annealing”, Science, 220(4598):671-680.
• Larose, D.T. (2006) “Data Mining Methods and Models”, 1st Edition, Wiley.
• Lourenço, H.R., Martin, O.C. ve Stützle, T. (2003) “Iterated Local Search” Glover et al. (eds) Handbook of Metaheuristics, Kluwer Academic Publishers.
• Michiels, W., Aarts, E. ve Korst, J. (2007) “Theoretical Aspects of Local Search”, Springer.
• Mitchell, M. (1999) “An Introduction to Genetic Algorithms”, Fifth Edition, Cambridge, MIT Press.
• Obitko, M. (1998), “Introduction to Genetic Algorithms with Java Applets”, http://www.obitko.com/tutorials/genetic-algorithms/index.php, (11.09.2013).
• Onan, A. (2013) “Kümeleme Analizinde Melez Evrimsel Algoritmalar Üzerine Bir Çalışma”, Yüksek Lisans Tezi, Ege Üniversitesi, Fen Bilimleri Enstitüsü, İzmir.
• Reeves, C.R. ve Rowe, J.E. (2003) “Genetic Algorithms-Principles and Perspectives: A Guide to GA Theory”, Boston, Kluwer Academic Publishers.
• Russell, S.J. ve Norvig, P. (2010) “Artificial Intelligence: A Modern Approach”, Pearson Education.
• Schneider, J.J. ve Kirkpatrick, S. (2006) “Stochastic Optimization”, Springer.
• Shi, Y. ve Eberhart, R. (1998) “Parameter Selection in Particle Swarm Optimization” Evolutionary Programming VII.
• Sivanandam, S.N. ve Deepa, S.N. (2008) “Introduction to Genetic Algorithms”, Springer.
• Srinivas, M. Ve Patnaik, L.M. (1994) “Genetic Algorithms: A Survey”, Computer, 27(6): 17-26.
• Stützle, T.G. (1998) “Local Search Algorithms for Combinatorial Problems- Analysis, Improvements and New Applications”, Doktora Tezi, Darmstadt University of Technology, Darmstadt.
• Talbi, E.G. (2009) “Metaheuristic: from Design to Implementation”, 2nd Edition, Wiley.
• Voudouris, C. ve Tsang, E.P.K. (2003) “Guided Local Search” Glover et al. (eds) Handbook of Metaheuristics, Kluwer Academic Publishers.
• Yu, X. ve Gen, M. (2010) “Introduction to Evolutionary Algorithms”, Springer.
• Zäpfel, R.B.G. ve Bogl, M. (2010) “Metaheuristic Search Concepts: A Tutorial with Application to Production and Logistics”, Springer.