Analysis Determination of Genetic Algorithm Crossover Point Problem in Travelling Salesman Problem

  • Authors

    • Khairuddin Nasution
    • Tasliyah Haramaini
    • Oris Krianto Sulaiman
    • Mhd. Zulfansyuri Siambaton
    • Abdurrozzaq Hasibuan
    • Mhd. Asaad
    2018-04-15
    https://doi.org/10.14419/ijet.v7i2.13.16932
  • TSP, optimal service, PMX, selection, mutation, Roulette wheel, bays29.tsp

  • Abstract

    Travelling Salesman Problem (TSP) is an optimization problem that can be applied to a variety of activities. Highlights of theTSPproblem is how the salesman can manage the journey so that the distance by which this is the optimum route is the best minimum distance. This study was formulated with the effect of determining the crossover point, especially probabilities of crossover in the search for the optimal route to theTSP. One goal of this research is to find the value of a good crossover probability in achieving optimal route. Crossover method used in this study is a partially mapped crossover (PMX). Selection is used Roulette wheel selection. From the tests carried out by using 20%, 40%, 60%, 80% and 99% can be found that a good crossover probability is 99%, with the determination of mutations worth of 0.05%. The number of generation is the generation 10000. Optimal route obtained from the data bays29.tsp is 10463.

     

     

  • References

    1. [1] “Chapter 10 The Traveling Salesman Problem.â€

      [2] A. R. Amin, M. Ikhsan, and L. Wibisono, “Traveling Salesman Problem,†pp. 1–6, 1976.

      [3] A. Fitrah and A. Zaky, “Penerapan Algoritma Genetika Pada Persoalan Pedagang Keliling ( Tsp ),†pp. 3–7, 1997.

      [4] Anies Hannawati, Thiang, and Eleazar, “Pencarian Rute Optimum Menggunakan Algoritma Genetika,†J. Tek. Elektro, vol. 2, no. 2, pp. 78–83, 2002.

      [5] L. D. Davis and M. Mitchell, “Handbook of Genetic Algorithms,†VAN NOSTRAND REINHOLD, vol. 15, no. 1, pp. 4–6, 1991.

      [6] M. Gen and R. Cheng, Genetic Algoritms & Engineering Design. New York: Jhon Wiley and Sons Inc., 1997.

  • Downloads

  • How to Cite

    Nasution, K., Haramaini, T., Krianto Sulaiman, O., Zulfansyuri Siambaton, M., Hasibuan, A., & Asaad, M. (2018). Analysis Determination of Genetic Algorithm Crossover Point Problem in Travelling Salesman Problem. International Journal of Engineering & Technology, 7(2.13), 406-409. https://doi.org/10.14419/ijet.v7i2.13.16932

    Received date: 2018-08-06

    Accepted date: 2018-08-06

    Published date: 2018-04-15