ANALISIS ELITISME PADA ALGORITMA GENETIKA MENGGUNAKAN PENGKODEAN ORDINAL REPRESENTATION DALAM TRAVELLING SALESMAN PROBLEM
-
Arfan Yehezkiel Mauko(1)
Program Studi Ilmu Komputer, Universitas Nusa Cendana, Indonesia
-
Adriana Fanggidae(2*)
Program Studi Ilmu Komputer, Universitas Nusa Cendana, Indonesia
-
Yulianto Triwahyuadi Polly(3)
Program Studi Ilmu Komputer, Universitas Nusa Cendana, Indonesia
(*) Corresponding Author
Abstrak
Traveling salesman problem (TSP) merupakan salah satu permasalahan optimasi untuk mencari rute terpendek, di mana setiap kota hanya diperbolehkan tepat satu kali untuk dikunjungi. Pencarian rute terpendek dapat diselesaikan oleh beberapa algoritma, salah satunya adalah algoritma genetika. Algoritma genetika adalah suatu algoritma optimasi yang bekerja dengan cara meniru proses evolusi di alam. Selama proses evolusi, individu dengan fitness terbaik dapat saja mengalami perubahan yang mengakibatkan penurunan fitness. Oleh karena itu, untuk menjaga individu dengan fitness terbaik tidak punah selama proses evolusi, maka perlu dibuat salinan individu tersebut yang disebut elitisme. Terdapat tiga model elitisme yaitu, Model 1: individu terbaik disalin sebanyak m menggantikan m individu terburuk, Model 2: m individu terbaik menggantikan m individu terburuk, dan Model 3: m individu terbaik menggantikan m individu terburuk yang dipilih secara acak dari 100%-m individu terburuk. Nilai dari parameter m yaitu 10%, 20%, 30%, dan 40%. Pengujian dilakukan dengan elitisme dan tanpa elitisme pada populasi dan jumlah kota yang berbeda. Hasil pengujian didapatkan bahwa Model 2 dengan m = 10% dan populasi = 20 merupakan parameter yang ideal dalam penyelesaian TSP.
##plugins.generic.usageStats.downloads##
Referensi
R. Kumar, “Effect of Polygamy with Selection in Genetic Algorithms,” vol. 2, no. 1, p. 6, 2012.
K. A. De Jong, “An Analysis of the behavior of a class of genetic adaptive systems.” 5140B University Microfilms No. 76/9381, 1975. [Online]. Available: https://deepblue.lib.umich.edu/handle/2027.42/4507
G. Roth and W. Crossley, “Investigation of number of children, number of parents, tournament size, and elitism in genetic algorithms,” in 8th Symposium on Multidisciplinary Analysis and Optimization, Long Beach,CA,U.S.A., Sep. 2000. doi: 10.2514/6.2000-4846.
W. Cheng, H. Shi, X. Yin, and D. Li, “An Elitism Strategy Based Genetic Algorithm for Streaming Pattern Discovery in Wireless Sensor Networks,” IEEE Commun. Lett., vol. 15, no. 4, pp. 419–421, Apr. 2011, doi: 10.1109/LCOMM.2011.022411.101804.
E. Zitzler, “An Analysis of the behavior of a class of genetic adaptive systems.” Doctoral thesis ETH NO. 13398, Zurich: Swiss Federal Institute of Technology (ETH), Aachen, Germany: Shaker Verlag. [Online]. Available: https://sop.tik.ee.ethz.ch/publicationListFiles/zitz1999a.pdf
E. Zitzler, K. Deb, and L. Thiele, “Comparison of Multiobjective Evolutionary Algorithms: Empirical Results,” Evolutionary Computation, vol. 8, no. 2, pp. 173–195, Jun. 2000, doi: 10.1162/106365600568202.
C. Grosan, M. Oltean, and M. Oltean, “The Role of Elitism in Multiobjective Optimization with Evolutionary Algorithms,” Acta Universitatis Apulensis, p. 9, Jan. 2003.
B. Chakraborty and P. Chaudhuri, “On The Use of Genetic Algorithm with Elitism in Robust and Nonparametric Multivariate Analysis,” Austrian Journal of Statistics, p. 16, Jan. 2003.
B. V. Natesha, “Adopting elitism-based Genetic Algorithm for minimizing multi-objective problems of IoT service placement in fog computing environment,” Journal of Network and Computer Applications, p. 10, 2021.
D. C. Lagos, R. A. Mancilla, P. E. Leal, and F. E. Fox, “Performance measurement of a solution for the travelling salesman problem for routing through the incorporation of service time variability,” Ing. Inv., vol. 39, no. 3, pp. 44–49, Sep. 2019, doi: 10.15446/ing.investig.v39n3.81161.
J. N. Macgregor and T. Ormerod, “Human performance on the traveling salesman problem,” Perception & Psychophysics, vol. 58, no. 4, pp. 527–539, Jun. 1996, doi: 10.3758/BF03213088.
A. Fanggidae and F. R. Lado, Algoritma Genetika dan Penerapannya. Yogyakarta: Teknosain, 2015.
B. Fernandez, A. Fanggidae, E. S. Y. Pandie, and A. Y. Mauko, “Travelling salesman problem: Greedy single point crossover in ordinal representation,” J. Phys.: Conf. Ser., vol. 2017, no. 1, p. 012012, Sep. 2021, doi: 10.1088/1742-6596/2017/1/012012.
##submission.copyrightStatement##
##submission.license.cc.by4.footer##Penulis yang mengirimkan naskah harus memahami dan menyetujui bahwa jika diterima untuk diterbitkan, penulis memiliki hak cipta dan memberikan jurnal hak publikasi pertama dengan karya yang dilisensikan secara bersamaan di bawah Creative Commons Attribution (CC-BY) 4.0 License yang memungkinkan orang lain untuk berbagi karya dengan pengakuan kepenulisan karya dan publikasi awal dalam jurnal ini.
