A ۲-Opt Genetic Algorithm for the Symmetric Traveling Salesman Problem

The genetic algorithm is a kind of evolutionary metaheuristicalgorithm, those find a good solution for some hard problemsin a reasonable time. Traveling salesman problem is an NPhardproblem, and its optimal solution is one of the mostchallenged discussions. So, researchers consider theproblem to find a nearby optimal solution instead of theoptimal solution. In the symmetric traveling salesmanproblem, the arc cost parameters satisfy the triangleinequality, in addition to the froward arc costs equal to thebackward arc costs in the network. The ۲-Opt heuristic couldimprove an obtained solution by transforming some crossarcs into the straight arcs. There is not any cross arc in theoptimal solution, then we apply the ۲-Opt algorithm on thegenerated population by the crossover operator in theproposed genetic algorithm. Therefore, the obtained solutionby the proposed ۲-Opt genetic algorithm performs a goodcomputation time as well as the optimality. The proposedalgorithm accelerates the improving trajectory in the geneticalgorithm by the features of the ۲-Opt heuristic.

کلیدواژه ها:

Traveling Salesman Problem ، Genetic Algorithm ، ۲-OptAlgorithm ، Metaheuristic Algorithm ، Network Optimization.