Memetic Algorithms

Memetic Algorithms for those, Who don’t know these kind of algorithms they are genetic or evolutionary algorithms more local search. First of all I think I need to explain the genetic algorithms.

The genetic algorithms are a heuristic, “a method to help solve a problem, commonly an informal method” [1]. The genetic algorithms were developed by John Holland on the sixties. He was studying how the evolution theory works and trying to apply this to computers. He’s technique is fairly simple, let’s say that a solution is an individual, it could be bad or a good solution. So if we have more than one possible solution we have a population. So we need that our individuals evolutes and become better individuals.

Each individual is compound of genes, for example in a clustering problem each point would be a gene and its group would be the gene value. The mechanisms used to evolution are mutation and crossover. The first one mutate a specific gene of an individual, in the other side the crossover uses other components of the population to create a new individual.

Figura 1 – Clustering Problem

For example if we want to look for the better way to separate the points above the representation would be:

1

2

3

3

4

1

2

3

…

So we could mutate the value of a gene to any other group, what would be equal to change randomly the group of a point, and the other thing that we could do would be to try to recombinate two individuals from the population for instance:

Crossing the two individuals:

1

2

3

3

4

1

2

3

…

3

2

1

2

3

4

4

2

…

We would have:

3

2

1

3

4

1

4

3

…

There is needed also a way to compare the solutions, in the clustering problem we could compare the total SSE of the individual, SSE is the Euclidian distance from the point to the centroid of the group its belongs.

Maybe you doubt that this kind of way of resolve a problem can works, but believes me it really works, this kind of algorithms aren’t trying to find the perfect solution they are trying to find one good solution in a reasonable time. There are a lot of serious research already done in this kind of algorithms and a lot of real projects already using it.

The algorithm above is a memetic algorithm because as you can see it works localSearch to improve the solution. In the clustering problem the localSearch chose to a point the group that has his centroid more near of the point.

1 – http://en.wikipedia.org/wiki/Heuristic

2 – Matteucci, M. (17 de setembro de 2003). A Tutorial on Clustering Algorithms. Acesso em 20 de novembro de 2008, disponível em Matteo Matteucci: http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/

3 – Mendes, A. d. (1999). ALGORITMOS MEMÉTICOS APLICADOS AOS PROBLEMAS DE SEQUENCIAMENTO EM MÁQUINAS. Campinas.

4 – Mez., P. (2000). Memetic Algorithm for Combinatorial Optimization Problems: Fitness Landscapes and Effective Search Strategies.

5 – Mitchell, M. (1998). An Introduction to Genetic Algorithms. MIT Press.