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:

could obtain better heuristics (better approximation, faster etc.) than the existing ones.

newly obtain heuristics could lead to new strategies for solving problems.

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.

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.