ANALYSIS OF ELITISM IN GENETIC ALGORITHM USING ORDINAL REPRESENTATION CODING ON TRAVELING SALESMAN PROBLEMS
-
Arfan Yehezkiel Mauko(1)
Department of Computer sciences, Universitas Nusa Cendana, Indonesia
-
Adriana Fanggidae(2*)
Department of Computer sciences, Universitas Nusa Cendana, Indonesia
-
Yulianto Triwahyuadi Polly(3)
Department of Computer sciences, Universitas Nusa Cendana, Indonesia
(*) Corresponding Author
Abstract
Traveling salesman problem (TSP) is one of the optimization problems to find the shortest route, where each city is only allowed to visit exactly once. The search for the shortest route can be completed by several algorithms, one of which is the genetic algorithm. Genetic algorithm is an optimization algorithm that works by imitating the evolutionary process in nature. During the evolution process, individuals with the best fitness may undergo changes that result in a decrease in fitness. Therefore, in order to keep individuals with the best fitness from becoming extinct during the evolutionary process, it is necessary to make copies of these individuals which is called elitism. There are three models of elitism, namely, Model 1: the best individuals are copied as many as m replacing the worst m individuals, Model 2: the best m individuals replace the worst m individuals, and Model 3: the best m individuals replace the worst m individuals selected randomly from 100%-m worst individual. The values of the m parameters are 10%, 20%, 30%, and 40%. The tests were carried out with elitism and without elitism on different populations and cities. The test results show that Model 2 with m = 10% and population = 20 is the ideal parameter in solving TSP.
Downloads
References
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.
Copyright (c) 2022 Arfan Yehezkiel Mauko, Adriana Fanggidae, Yulianto Triwahyuadi Polly
This work is licensed under a Creative Commons Attribution 4.0 International License.
The author submitting the manuscript must understand and agree that if accepted for publication, authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution (CC-BY) 4.0 License that allows others to share the work with an acknowledgment of the work’s authorship and initial publication in this journal.
