Basic Evolutionary Approach to the Traveling Salesman Problem

Main Article Content

Débora Regina de São José
Mauricio Garcia Hernandez

Abstract

Evolutionary programming (EP) is a metaheuristic method developed as an alternative approach to artificial intelligence. The aim of this paper is to bring an introduction to EP algorithms through the implementation of the basic D. B. Fogel’s Evolutionary Programing approach of 1988 and the emulation of his results in order to analyze the performance of the evolutionary programming method on solving a benchmark test case. The EP approach is implemented thru a simple simulation of natural evolution and the allowance of probabilistic survival of individuals. The novelty of this paper relies on testing the algorithm performance in some problems of well-known benchmark instances of the Traveling Salesman Problem, where that 1988 evolutionary approach was not tested. The reproduction of 1988 D. B. Fogel’s approach was possible, the found average error of this method for 200000 offspring applied to the benchmark instances was found to be in the order of the 10%.

Downloads

Download data is not yet available.

Article Details

Author Biographies

Débora Regina de São José, Universidade do Porto

Programa Doutoral em Engenharia e Gestão Industrial

Faculdade de Engenharia

Universidade do Porto

Rua Dr. Roberto Frias

4200-465 PORTO

Portugal

Mauricio Garcia Hernandez, Universidade do Porto

Programa Doutoral em Engenharia Electrotécnica e de Computadores

Faculdade de Engenharia

Universidade do Porto

Rua Dr. Roberto Frias

4200-465 PORTO

Portugal