Integrasi Kromosom Buatan Dinamis Untuk Memecahkan Masalah Konvergensi Prematur Pada Algoritma Genetika Untuk Traveling Salesman Problem
Abstract
Genetic Algorithm (GA) adalah metode adaptif yang digunakan untuk memecahkan masalah pencarian dan optimasi, diantaranya adalah Travelling Salesman Problem (TSP) yang merupakan persoalan optimasi, dimana rute terpendek merupakan solusi yang paling optimal. GA juga salah satu metode optimisasi global yang bekerja dengan baik dan efisien pada fungsi tujuan yang kompleks dalam hal nonlinear, tetapi GA mempunyai masalah yaitu konvergensi prematur. Untuk mengatasi masalah konvergensi prematur, maka pada penelitian ini diusulkan Dynamic Artificial Chromosomes (DAC) yang digunakan untuk mengkontrol keragaman populasi dan juga seleksi kromosom terbaik untuk memilih individu atau kromosom terbaik yang tujuannya untuk membuat keragaman pada populasi menjadi beragam dan keluar dari konvergensi prematur. Beberapa eksperimen dilakukan dengan menggunakan Genetic Algorithm Dynamic Artificial Chromosomes (GA-DAC), dimana threshold terbaik adalah 0.5, kemudian juga mendapatkan hasil perbaikan pada jarak terpendek yang dibandingkan dengan GA standar dengan dataset KroA100 sebesar 12.60%, KroA150 sebesar 13.92% dan KroA200 sebesar 12.92%. Untuk keragaman populasi mendapatkan hasil pada KroA100 sebesar 24.97%, KroA150 sebesar 50.84% dan KroA200 sebesar 49.08% dibandingkan dengan GA standar. Maka dapat disimpulkan bahwa GA-DAC bisa mendapatkan hasil lebih baik dibandingkan dengan GA standar, sehingga ini akan membuat GA bisa keluar dari konvergensi prematur.
Â
Keywords: algoritma genetika, konvergensi prematur, dynamic artificial chromosomes, seleksi kromosom terbaik, travelling salesman problem.Full Text:
PDFReferences
Çavdar, B., & Sokol, J. (2014). TSP Race: Minimizing completion time in time-sensitive applications. European Journal of Operational Research, 000, 1–8. doi:10.1016/j.ejor.2014.12.022
Chang, P.-C., Huang, W.-H., & Ting, C.-J. (2010). Dynamic diversity control in genetic algorithm for mining unsearched solution space in TSP problems. Expert Systems with Applications, 37(3), 1863–1878. doi:10.1016/j.eswa.2009.07.066
Chang, Y.-H. (2010). Adopting co-evolution and constraint-satisfaction concept on genetic algorithms to solve supply chain network design problems. Expert Systems with Applications, 37(10), 6919–6930. doi:10.1016/j.eswa.2010.03.030
Chen, S.-M., & Chien, C.-Y. (2011). Solving the traveling salesman problem based on the genetic simulated annealing ant colony system with particle swarm optimization techniques. Expert Systems with Applications, 38(12), 14439–14450. doi:10.1016/j.eswa.2011.04.163
De Giovanni, L., & Pezzella, F. (2010). An Improved Genetic Algorithm for the Distributed and Flexible Job-shop Scheduling problem. European Journal of Operational Research, 200(2), 395–408. doi:10.1016/j.ejor.2009.01.008
Elfeky, E., Sarker, R., & Essam, D. (2008). Analyzing the simple ranking and selection process for constrained evolutionary optimization. Journal of Computer Science and …, 23(1), 19–34. doi:10.1007/s11390-008-9109-z
Elsayed, S. M., Sarker, R. a., & Essam, D. L. (2014). A new genetic algorithm for solving optimization problems. Engineering Applications of Artificial Intelligence, 27, 57–69. doi:10.1016/j.engappai.2013.09.013
Liu, F., & Zeng, G. (2009). Study of genetic algorithm with reinforcement learning to solve the TSP. Expert Systems with Applications, 36(3), 6995–7001. doi:10.1016/j.eswa.2008.08.026
Ono, I., Kita, H., & Kobayashi, S. (2003). A real-coded genetic algorithm using the unimodal normal distribution crossover. Advances in Evolutionary Computing. Retrieved from http://link.springer.com/chapter/10.1007/978-3-642-18965-4_8
Pandey, H. M., Chaudhary, A., & Mehrotra, D. (2014). A comparative review of approaches to prevent premature convergence in GA. Applied Soft Computing, 24, 1047–1077. doi:10.1016/j.asoc.2014.08.025
Pavez-Lazo, B., & Soto-Cartes, J. (2011). A deterministic annular crossover genetic algorithm optimisation for the unit commitment problem. Expert Systems with Applications, 38(6), 6523–6529. doi:10.1016/j.eswa.2010.11.089
S.N Sivanandam, S. N. D. (2008). Introduction to Genetic Algorithms. (I. Integra Software Services Pvt. Ltd., Ed.)Vasa (p. 462). Berlin Heidelberg: Springer. doi:10.1007/978-3-540-73190-0_2
Siva Sathya, S., & Radhika, M. V. (2013). Convergence of nomadic genetic algorithm on benchmark mathematical functions. Applied Soft Computing, 13(5), 2759–2766. doi:10.1016/j.asoc.2012.11.011
Wang, Y. (2014). The hybrid genetic algorithm with two local optimization strategies for traveling salesman problem q. COMPUTERS & INDUSTRIAL ENGINEERING, 70, 124–133. doi:10.1016/j.cie.2014.01.015
Yang, S., & Jat, S. N. (2011). Genetic Algorithms With Guided and Local Search Strategies for University Course Timetabling. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 41(1), 93–106. doi:10.1109/TSMCC.2010.2049200
Zhang, H., Tong, W., Xu, Y., & Lin, G. (2015). The Steiner Traveling Salesman Problem with online edge blockages. European Journal of Operational Research, 243(1), 30–40. doi:10.1016/j.ejor.2014.11.013
Refbacks
- There are currently no refbacks.
Journal of Intelligent Systems(JIS, ISSN 2356-3982) Copyright © 2020IlmuKomputer.Com. All rights reserved. |