Anzeige
Erschienen in:
2008 | OriginalPaper | Buchkapitel
A Hybrid Genetic Algorithm for the Travelling Salesman Problem
verfasst von : Xiao-Bing Hu, Ezequiel Di Paolo
Erschienen in: Nature Inspired Cooperative Strategies for Optimization (NICSO 2007)
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Genetic Algorithms (GAs) for the Travelling Salesman Problem (TSP) are often based on permutation representations, which makes it difficult to design effective evolutionary operators without causing feasibility problems to chromosomes. This paper attempts to develop a binary representation based hybrid GA to solve the TSP. The basic idea is to design a pre-TSP problem (PTSPP), where the input is the coordinates of a point in the map of cities, and the output is a feasible route connecting all cities. An effective deterministic algorithm is developed for this PTSPP to search the local optimum starting from the coordinates of a given point. The new GA is then designed to randomly choose and evolve the coordinates of generations of points for the PTSPP, and also to find out the global optimum or suboptima for the TSP. The preliminary experiments show the potential of the proposed hybrid GA to solve the TSP.