Content area
Full text
Abstract
In this paper, we present a new mutation operator, Hybrid Mutation (HPRM), for a genetic algorithm that generates high quality solutions to the Traveling Salesman Problem (TSP). The Hybrid Mutation operator constructs an offspring from a pair of parents by hybridizing two mutation operators, PSM and RSM. The efficiency of the HPRM is compared as against some existing mutation operators; namely, Reverse Sequence Mutation (RSM) and Partial Shuffle Mutation (PSM) for BERLIN52 as instance of TSPLIB. Experimental results show that the new mutation operator is better than the RSM and PSM.
Keywords: NP-complete problem, Traveling Salesman Problem, Mutation operator.
(ProQuest: ... denotes formula omitted.)
1. Introduction
NP-Complete is a class of problems that are so difficult that even the best solutions cannot consistently determine their solutions in an efficient way. Specifically, NP Complete problems can only possibly be solved in polynomial time using a nondeterministic Turing machine. Problems such as the Traveling Salesman problem fall into the realm of NP Complete problems. Because of the problem with finding the "best" solution, programs are often developed to find a usually reasonable solution.
The traveling salesman problem (TSP) is a well known and important combinatorial optimization problem. In the traveling salesman problem (TSP) we are given n vertices 1, .., n and all n(n-1)/2 distances between them, as well as a budget b. We are asked to find a tour, a cycle that passes through every vertex exactly once, of total cost b or less or to report that no such tour exists. The number of solutions becomes extremely large for even moderately large n so that an exhaustive search is impracticable.
The methods that provide the exact optimal solution to the problem are called exact methods. An implicit way of solving the TSP is simply to list all the feasible solutions, evaluate their objective function values and pick out the best. However it is obvious that this "exhaustive search" is grossly inefficient and impracticable because of vast number of possible solutions to the TSP even for problem of moderate size.
Since practical applications require solving larger problems, hence emphasis has shifted from the aim of finding exactly optimal solutions to TSP, to the aim of getting, heuristically, 'good solutions' in reasonable time and 'establishing...