An Improved Hybrid Genetic Algorithm for Traveling Salesman Problem
Citations Over Time
Abstract
Traveling salesman problem (TSP) is a typical NP-complete problem which lacks polynomial time algorithm. In this paper, an improved ¿-hybrid genetic algorithm framework is presented, the application of which in solving the TSP is also introduced. It applies both global search strategy and local search strategy to ensure the searching breadth as well as the solution precision. It adds a local search process in the standard genetic algorithm. When the best individual of every generation is found, the algorithm performs local search in the neighborhood of the best individual to find local optimum. The Elite retention strategy is also used to have the searched results and the best individual substitute the worst or other individuals and directly enter into the operation of next generation. Experiments show that this algorithm greatly enhances the performance of the standard genetic algorithm, not only improves the precision of the algorithm, but also increases the stability of the algorithm.
Related Papers
- → Simulated Evolutionary Optimization and Local Search: Introduction and Application to Tree Search(2001)17 cited
- → Improving Search-based Test Case Generation with Local Search using Adaptive Simulated Annealing and Dynamic Symbolic Execution(2022)3 cited
- → The Probabilistic Heuristic In Local (PHIL) Search Meta-strategy(2005)
- Improving Local Optima of Local Search with Adjustable Multipliers(2005)
- → Evolving search trajectories(2020)