ANALISIS MAPPING PADA PARTIALLY MAPPED CROSSOVER DALAM ALGORITMA GENETIKA PADA TRAVELLING SALESMAN PROBLEM

Sri Melvani Hardi, Muhammad Zarlis, Erna Budiarti

Abstract


Traveling salesman problem is the problem how salesman can set tour to visit a number of cities which known distance of the city with other cities so that the distance is the minimum distance where the salesman can only visit the city exactly once. To resolve TSP problem, there are many optimization methods that can be used one of them which is a genetic algorithm. Genetic algorithm is an algorithm which have same search method as a mechanism of biological evolution. Crossover is a genetic operator which the process of exchanging some genes on chromosome first parent with the majority of genes in the two parent chromosomes to form a new chromosome .One of the crossover method used in solving traveling salesman problem is partially mapped crossover ( PMX ),where the process mapping of PMX are determines the variation exchange of genes on chromosomes that affect the achievement of best fitness on 2 chromosome. In this study the first variation (PMX variation I) is designed using random point position while in the second variation (PMX variation II) is designed by using the change in the mapping area. Testing in this study using data from the Travelling Salesman Problem Library (TSPLIB). The result obtained that PMX which designed by using randomly cut position have best fittness better than PMX is designed by changing the position of the mapping area and if it compared with the general form of PMX with the same position cut point.

Full Text:

PDF

References


A. Tamilarasi and T. Anantha kumar. (2010). An enhanced genetic algorithm with simulated annealing for job-shop scheduling. International Journal of Engineering, Science and Technology Vol. 2, No. 1, 2010, pp. 144-151

Ahmed, Z., Younas, I.,& Zahoor, M (2010). A Novel Genetic Algorithm for GTSP. International Journal of Computer Theory and

Engineering, Vol.2, No.6, December, 2010 1793-8201

Al kasassbeh, M., Alabadleh, A., & Al-Ramadeen, T. (2012). Shared

Crossover Method for Solving Traveling Salesman Problem. IJICS

Volume 1, Issue 6, September 2012 PP. 153-158

Davis, L. (1991). Handbook of Genetic Algorithms. New York : Van Nostrand Reinhold.




DOI: https://doi.org/10.29103/techsi.v6i1.167

Article Metrics

 Abstract Views : 1229 times
 PDF Downloaded : 104 times

Refbacks

  • There are currently no refbacks.


Copyright (c) 2014 Sri Melvani Hardi, Muhammad Zarlis, Erna Budiarti

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

 


Indexed by:

          

Google Scholar
   
 

 


© Copyright of Journal TECHSI, (e-ISSN:2614-6029, p-ISSN:2302-4836).

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.