Algoritmos genéticos

Introducci´n a los Algoritmos Gen´ticos
o
e
Marcos Gestal Pose
Depto. Tecnolog´ de la Informaci´n y las Comunicaciones
ıas
o
Universidade da Coru˜a
n
http://sabia.tic.udc.es/˜mgestal
mgestal@udc.es

´
Indice
1. Introducci´n
o

2

2. Or´
ıgenes

2

3. Bases Biol´gicas
o

4

4. Codificaci´n de Problemas
o

4

5. Algoritmo Principal

5

6. Operadores Gen´ticos
e6.1. Selecci´n . . . . . . . . . . .
o
6.1.1. Selecci´n por ruleta
o
6.1.2. Selecci´n por torneo
o
6.2. Cruce . . . . . . . . . . . .
6.2.1. Cruce de 1 punto . .
6.2.2. Cruce de 2 puntos .
6.2.3. Cruce Uniforme . . .
6.2.4. Cruces espec´
ıficos de
6.3. Algoritmos de Reemplazo .
6.4. Copia . . . . . . . . . . . .
6.5. Mutaci´n . . . . . . . . . .
o

. . . . . . . .
. . . . . . ..
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
codificaciones
. . . . . . . .
. . . . . . . .
. . . . . . . .

. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
no binarias
. . . . . . .
. . . . . . .
. . . . . . .

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
..
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

7. Evaluaci´n
o

8
8
8
9
9
10
10
11
11
12
13
13
14

´
Indice de figuras
1.
2.
3.
4.
5.
6.
7.

Ecuaci´n Evolutiva . . . . . . . . . . . . . . . . . .
o
Soft Computing . . . . . . . . . . . . . . . . . . . .
Individuo Gen´tico Binario . . . .. . . . . . . . .
e
Ejemplo Codificaci´n: Red de Neuronas Artificiales
o
Cruce de 1 Punto . . . . . . . . . . . . . . . . . . .
Cruce de 2 Puntos . . . . . . . . . . . . . . . . . .
Cruce Uniforme . . . . . . . . . . . . . . . . . . . .
1

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
..
.

.
.
.
.
.
.
.

2
3
5
6
10
11
12

Introducci´n a los Algoritmos Gen´ticos
o
e

El siguiente tutorial no pretende ser un documento exhaustivo acerca de los Algoritmos Gen´ticos. M´s bien una referencia que sirva para
e
a
introducir la terminolog´ los conceptos claves y una bibliograf´ de baıa,
ıa
se, quedando en manos del lector profundizar en aquellos aspectos queconsidere de mayor inter´s.
e

1.

Introducci´n
o

Los Algoritmos Gen´ticos son m´todos adaptativos, generalmente usados en
e
e
problemas de b´squeda y optimizaci´n de par´metros, basados en la reproducu
o
a
ci´n sexual y en el principio supervivencia del m´s apto.
o
a
M´s formalmente, y siguiendo la definici´n dada por Goldberg, “los Algorita
o
mos Gen´ticos son algoritmos deb´squeda basados en la mec´nica de selecci´n
e
u
a
o
natural y de la gen´tica natural. Combinan la supervivencia del m´s apto entre
e
a
estructuras de secuencias con un intercambio de informaci´n estructurado, auno
que aleatorizado, para constituir as´ un algoritmo de b´squeda que tenga algo de
ı
u
las genialidades de las b´squedas humanas” [Goldberg, 1989].
u
Para alcanzar lasoluci´n a un problema se parte de un conjunto inicial
o
de individuos, llamado poblaci´n, generado de manera aleatoria. Cada uno
o
de estos individuos representa una posible soluci´n al problema. Estos indio
viduos evolucionar´n tomando como base los esquemas propuestos por Dara
win [Darwin, 1859] sobre la selecci´n natural, y se adaptar´n en mayor medida
o
a
tras el paso de cada generaci´n ala soluci´n requerida.
o
o

2.

Or´
ıgenes

Si algo funciona bien, ¿por qu´ no imitarlo?. La respuesta a esta pregune
ta nos lleva directamente a los or´
ıgenes de la computaci´n evolutiva. Durante
o
millones de a˜os las diferentes especies se han adaptado para poder sobrevivir
n
en un medio cambiante. De la misma manera se podr´ tener una poblaci´n de
ıa
o
potenciales...