Proceedings of the 2nd International Conference of Science and Technology for the Internet of Things, ICSTI 2019, September 3rd 2019, Yogyakarta, Indonesia

Research Article

The Comparison of Genetic Algorithm and Ant Colony Optimization in Completing Travelling Salesman Problem

Download3287 downloads
  • @INPROCEEDINGS{10.4108/eai.20-9-2019.2292121,
        author={Alexander  Alexander and Haris  Sriwindono},
        title={The Comparison of Genetic Algorithm and Ant Colony Optimization in Completing Travelling Salesman Problem},
        proceedings={Proceedings of the 2nd International Conference of Science and Technology for the Internet of Things, ICSTI 2019, September 3rd 2019, Yogyakarta, Indonesia},
        publisher={EAI},
        proceedings_a={ICSTI},
        year={2020},
        month={3},
        keywords={: travelling salesman problem genetic algorithm ant colonies optimization},
        doi={10.4108/eai.20-9-2019.2292121}
    }
    
  • Alexander Alexander
    Haris Sriwindono
    Year: 2020
    The Comparison of Genetic Algorithm and Ant Colony Optimization in Completing Travelling Salesman Problem
    ICSTI
    EAI
    DOI: 10.4108/eai.20-9-2019.2292121
Alexander Alexander1,*, Haris Sriwindono1
  • 1: Department of Informatics, Faculty of Science and Technology, Universitas Sanata Dharma, Yogyakarta, Indonesia
*Contact email: alexanderujang96@gmail.com

Abstract

Traveling Salesman Problem abbreviated as TSP, is a NP-hard problem that is often applied in various applications. TSP is a polynomial problem, so the solution is exponential. One way to improve the resolution of NP-hard problems is to use probabilistic algorithms such as genetic algorithms, ant colony optimization algorithms, and others. In this study genetic algorithm (GA) was applied with ordered crossover method and reciprocal mutation method. And also use the ant colony algorithm (ACO). This research will compare the performance of the two algorithms. The data used are 10, 20, ..., 100 cities, so the result shows that the ant colony algorithm is able to find a shorter distance than the genetic algorithm, but the genetic algorithm shows a better speed of completion than the ant colony algorithm.