Evolving TSP heuristics using multi expression programming

DOI10.1007/978-3-540-24687-9_99MaRDI QIDQ5712699zbMATH OpenOpenAlexFDO

Authors Mihai Oltean, Dumitru D. Dumitrescu

Publication date 23 December 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1509.02459

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Abstract: Multi Expression Programming (MEP) is an evolutionary technique that may be used for solving computationally difficult problems. MEP uses a linear solution representation. Each MEP individual is a string encoding complex expressions (computer programs). A MEP individual may encode multiple solutions of the current problem. In this paper MEP is used for evolving a Traveling Salesman Problem (TSP) heuristic for graphs satisfying triangle inequality. Evolved MEP heuristic is compared with Nearest Neighbor Heuristic (NN) and Minimum Spanning Tree Heuristic (MST) on some difficult problems in TSPLIB. For most of the considered problems the evolved MEP heuristic outperforms NN and MST. The obtained algorithm was tested against some problems in TSPLIB. The results emphasizes that evolved MEP heuristic is a powerful tool for solving difficult TSP instances.

Recommendations

• Paralell evolution heuristic approach for the traveling salesman problem
• Evolution algorithms in combinatorial optimization
• scientific article; zbMATH DE number 5300053
• Evolutionary computational approaches to solving the multiple traveling salesman problem using a neighborhood attractor schema
• scientific article; zbMATH DE number 1852707

Cited in

(5)

• The algorithm for algorithms: an evolutionary algorithm based on automatic designing of genetic operators
• Mining classification rules with Reduced MEPAR-miner Algorithm
• An algorithm of multivariant evolutionary synthesis of nonlinear models with real-valued chromosomes
• Development of a metaheuristic programming method for the nonlinear models synthesis
• Evolving diverse TSP instances by means of novel and creative mutation operators

Describes a project that uses

Uses Software

• TSPLIB

This page was built for publication: Evolving TSP heuristics using multi expression programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5712699)