Evolving Heuristics with Evolutionary Algorithm and Genetic Programming

The purpose is to obtain heuristics, for NP-complete problems, in an automated way.

Benefits and strengts:

Example 1: Travelling Salesman Problem

We want to evolve a heuristic better than Nearest Neighbour (NN).

The evolved heuristic constructs the path node by node, like NN, but chooses the next node based on an evolved function.

We cannot send, to the evolved function, the entire graph as a parameter so we extract only some summarized information from it (such as min, max and average distance in the graph, total length so far, number of nodes so far, distance to the nearest, farthest unvisited node, etc). We fill an array (vars_values in our source code) with this summarized information. A function having vars_values as a parameter will be evolved.

Download

Source code (C++) for evolving TSP heuristics

References:

  1. Oltean Mihai, Dumitrescu, D., Evolving TSP Heuristics using Multi Expression Programming, International Conference on Computational Sciences, ICCS'04, 6-9 June, Krakow, Poland, Edited by M. Bubak, G.van Albada, P. Sloot, and J. Dongarra, Vol II, pp. 670-673, Springer-Verlag, Berlin, 2004.

Back home