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.
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
This work is licensed under a
Creative Commons Attribution-ShareAlike 4.0 International License.
Indexed by:
© Copyright of Journal TECHSI, (e-ISSN:2614-6029, p-ISSN:2302-4836).
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.