Markov

Algoritmos gen´ ticos paralelos
e
Antonio la Torre de la Fuente
16 de septiembre de 2005

Resumen
Este trabajo pretende presentar de una manera general el estado actual de los algoritmos gen´ ticos paralelos, su evoluci´ n a partir de los algoritmos gen´ ticos
e
o
e
tradicionales, establecer una clasificaci´ n no exhaustiva de los mismos, as´ como
o
ı
esbozar los principalesproblemas y retos que plantea el uso de estas t´ cnicas. A
e
lo largo del trabajo veremos que estos algoritmos son capaces de encontrar soluciones de una calidad similar a la obtenida por los algoritmos en su versi´ n
o
secuencial y, algo fundamental, en un tiempo considerablemente menor, llegando
en ocasiones a obtener un aumento de rendimiento superlineal.

´
Indice general
1. Introducci´ n
o1.1. Or´genes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ı
1.2. Fundamentos de los algoritmos gen´ ticos . . . . . . . . . . . . .
e
1.3. Algoritmos gen´ ticos paralelos . . . . . . . . . . . . . . . . . . .
e
2. Clasificaci´ n de los AGP
o
2.1. Algoritmos maestro-esclavo . . . . . . . . . . . .
2.2. Algoritmos de grano fino . . . . . . . . . . . . . .
2.3. Algoritmosde grano grueso . . . . . . . . . . . . .
2.3.1. Influencia de las migraciones . . . . . . . .
2.3.2. Influencia de la topolog´a de comunicaci´ n
ı
o
2.4. Algoritmos H´bridos . . . . . . . . . . . . . . . .
ı

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

2
2
3
4

5
.
6
.
7
.
8
.
9
.10
. 10

3. Sincronismo y asincronismo en los AGP

13

4. Superlinealidad en los AGP

15

5. Conclusiones

18

1

Cap´tulo 1
ı
Introducci´ n
o
Los algoritmos gen´ ticos son un subconjunto de unas t´ cnicas heur´sticas coe
e
ı
nocidas como t´ cnicas evolutivas. Estos algoritmos est´ n basados en la teor´a de
e
a
ı
la evoluci´ n de Darwin, imitando el comportamiento delos mecanismos de reo
producci´ n y selecci´ n dentro de una especie. Su gran versatilidad para resolver
o
o
problemas de muy diferentes campos han hecho que hayan adquirido una gran
´
popularidad en los ultimos a˜ os.
n

1.1. Or´genes
ı
Como ya se ha dicho, los algoritmos gen´ ticos se basan en los mecanismos de
e
selecci´ n que utiliza la naturaleza, seg´ n los cuales los individuosm´ s aptos de
o
u
a
una poblaci´ n son los que sobreviven y los que, por tanto, servir´ n de base para
o
a
generaciones posteriores.
Un investigador de la Universidad de Michigan, John Holland, se interes´ por
o
estos mecanismos, asombrado por la capacidad de la naturaleza de perfeccionar
a sus organismos. A principio de los a˜ os 60 comenz´ a desarrollar estas ideas
n
o
y a adaptarlaspara la resoluci´ n de problemas computacionales. Dos fueron los
o
objetivos sobre los que centr´ su investigaci´ n:
o
o
imitar los procesos adaptativos de los sistemas naturales
dise˜ ar sistemas inform´ ticos capaces de resolver problemas usando los men
a
canismos m´ s importantes presentes en la naturaleza
a
15 a˜ os m´ s tarde, un ingeniero industrial llamado David Golberg conoci´ an
a
o
´
John Holland y se convirti´ en alumno suyo. Este intent´ aplicar los algoritmos
o
o
gen´ ticos a problemas industriales, aunque Holland intent´ disuadirle por pensar
e
o
que eran demasiado complicados de resolver. Finalmente, consigui´ aplicarlos
o
2

de manera satisfactoria y esto, unido a las aplicaciones posteriores en diversos
campos que de ellos se hicieron, propici´que los algoritmos gen´ ticos adquirieran
o
e
la popularidad de la que a´ n hoy gozan.
u

1.2. Fundamentos de los algoritmos gen´ ticos
e
Los algoritmos gen´ ticos son m´ todos de resoluci´ n de problemas de b´ squee
e
o
u
da y optimizaci´ n que hacen uso de los mismos m´ todos de los que se sirve la
o
e
naturaleza, seg´ n la teor´a de Darwin, para la evoluci´ n biol´ gica: la...