Open AccessTaxonomy Genetic Algorithm For Implementation Partially Mapped Crossover In Travelling Salesman Problem
Author(s) -
Surya Hardi,
Muhammad Zarlis,
Syahril Effendi,
Maya Silvi Lydia
Publication year - 2020
Publication title -
journal of physics. conference series
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.21
H-Index - 85
eISSN - 1742-6596
pISSN - 1742-6588
DOI - 10.1088/1742-6596/1641/1/012104
Subject(s) - crossover , travelling salesman problem , lin–kernighan heuristic , genetic algorithm , mathematical optimization , algorithm , mathematics , computer science , 2 opt , artificial intelligence
Genetic algorithmhasvarious process are carried out to get optimal results in solving the problem of traveling salesman problemTravelling salesman problem (TSP) as known as combinatorial NP problem. Salesman given a map that he has accomplished all cities only once by minimized the total of distance and he has to return to the first city. By describing the taxonomy in genetic algorithm, it can avoid confusion in understanding the various classifications that exist in the genetic algorithm operator. This paper explains one of the parts from genetic algorithm is crossover. Crossover being important step in genetic algorithm. Commonly mechanism crossover replaces two selected chromosome which part from two parent’s individual randomly position, generate random number interval 0-1. Crossover occur for each individual by determining the probability of the crossover. If the probability crossover is smaller than random number, there is no crossover process. Partially mapped crossover is part of the taxonomy of genetic algorithms whose implementations can be applied in a variety of problem solving including in the travelling salesman problem. The test results of this researchusing pc 0.25 and pm 0,1 with tsp eil51 data, it was found that the optimal route average value was 4069.34 and the best fitness average was 2.46E-04, while for the eil76 test data the optimal route average value was 6844.4. and the average best fitness value of 1.46E-04.