E3S Web Conf.
Volume 31, 2018The 2nd International Conference on Energy, Environmental and Information System (ICENIS 2017)
|Number of page(s)||5|
|Section||11. Smart Information Systems|
|Published online||21 February 2018|
Comparison of Genetic Algorithm and Hill Climbing for Shortest Path Optimization Mapping
Master of Information System, School of Postgraduate Studies, Diponegoro University, Semarang – Indonesia 50242
2 Department of Physics, Faculty of Science and Mathematics, Diponegoro University, Semarang – Indonesia 50275
* Corresponding author: firstname.lastname@example.org
Traveling Salesman Problem (TSP) is an optimization to find the shortest path to reach several destinations in one trip without passing through the same city and back again to the early departure city, the process is applied to the delivery systems. This comparison is done using two methods, namely optimization genetic algorithm and hill climbing. Hill Climbing works by directly selecting a new path that is exchanged with the neighbour’s to get the track distance smaller than the previous track, without testing. Genetic algorithms depend on the input parameters, they are the number of population, the probability of crossover, mutation probability and the number of generations. To simplify the process of determining the shortest path supported by the development of software that uses the google map API. Tests carried out as much as 20 times with the number of city 8, 16, 24 and 32 to see which method is optimal in terms of distance and time computation. Based on experiments conducted with a number of cities 3, 4, 5 and 6 producing the same value and optimal distance for the genetic algorithm and hill climbing, the value of this distance begins to differ with the number of city 7. The overall results shows that these tests, hill climbing are more optimal to number of small cities and the number of cities over 30 optimized using genetic algorithms.
© The Authors, published by EDP Sciences, 2018
This is an Open Access article distributed under the terms of the Creative Commons Attribution License 4.0, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. (http://creativecommons.org/licenses/by/4.0/).
Initial download of the metrics may take a while.