Algorit Gen

´
ALGORITMOS GENETICOS
1

Introducci´n
o

Los Algoritmos Gen´ticos (AGs) son m´todos adaptativos que pueden usarse para resolver problee
e
mas de b´squeda y optimizaci´n. Est´n basados en el proceso gen´tico de los organismos vivos. A
u
o
a
e
lo largo de las generaciones, las poblaciones evolucionan en la naturaleza de acorde con los principios de la selecci´n natural y lasupervivencia de los m´s fuertes, postulados por Darwin (1859).
o
a
Por imitaci´n de este proceso, los Algoritmos Gen´ticos son capaces de ir creando soluciones para
o
e
problemas del mundo real. La evoluci´n de dichas soluciones hacia valores optimos del problema
o
´
depende en buena medida de una adecuada codificaci´n de las mismas.
o
Los principios b´sicos de los Algoritmos Gen´ticos fueronestablecidos por Holland (1975), y se
a
e
encuentran bien descritos en varios textos – Goldberg (1989), Davis (1991), Michalewicz (1992),
Reeves (1993) – .
En la naturaleza los individuos de una poblaci´n compiten entre s´ en la b´squeda de recursos tales
o
ı
u
como comida, agua y refugio. Incluso los miembros de una misma especie compiten a menudo en
la b´squeda de un compa˜ero. Aquellosindividuos que tienen m´s ´xito en sobrevivir y en atraer
u
n
a e
compa˜eros tienen mayor probabilidad de generar un gran n´mero de descendientes. Por el conn
u
trario individuos poco dotados producir´n un menor n´mero de descendientes. Esto significa que los
a
u
genes de los individuos mejor adaptados se propagar´n en sucesivas generaciones hacia un n´mero de
a
u
individuos creciente.La combinaci´n de buenas caracter´
o
ısticas provenientes de diferentes ancestros,
puede a veces producir descendientes “superindividuos”, cuya adaptaci´n es mucho mayor que la de
o
cualquiera de sus ancestros. De esta manera, las especies evolucionan logrando unas caracter´
ısticas
cada vez mejor adaptadas al entorno en el que viven.
Los Algoritmos Gen´ticos usan una analog´ directa conel comportamiento natural. Trabajan con
e
ıa
una poblaci´n de individuos, cada uno de los cuales representa una soluci´n factible a un problema
o
o
dado. A cada individuo se le asigna un valor o puntuaci´n, relacionado con la bondad de dicha
´
o
soluci´n. En la naturaleza esto equivaldr´ al grado de efectividad de un organismo para compeo
ıa
tir por unos determinados recursos. Cuantomayor sea la adaptaci´n de un individuo al problema,
o
mayor ser´ la probabilidad de que el mismo sea seleccionado para reproducirse, cruzando su material
a
gen´tico con otro individuo seleccionado de igual forma. Este cruce producir´ nuevos individuos –
e
a
descendientes de los anteriores – los cuales comparten algunas de las caracter´
ısticas de sus padres.
Cuanto menor sea la adaptaci´nde un individuo, menor ser´ la probabilidad de que dicho individuo
o
a
sea seleccionado para la reproducci´n, y por tanto de que su material gen´tico se propague en suceo
e
sivas generaciones.
De esta manera se produce una nueva poblaci´n de posibles soluciones, la cual reemplaza a la anterior
o
y verifica la interesante propiedad de que contiene una mayor proporci´n de buenas caracter´
oısticas en
comparaci´n con la poblaci´n anterior. As´ a lo largo de las generaciones las buenas caracter´
o
o
ı
ısticas
se propagan a trav´s de la poblaci´n. Favoreciendo el cruce de los individuos mejor adaptados, van
e
o
siendo exploradas las areas m´s prometedoras del espacio de b´squeda. Si el Algoritmo Gen´tico
´
a
u
e
ha sido bien dise˜ado, la poblaci´n converger´ hacia unasoluci´n optima del problema.
n
o
a
o ´
El poder de los Algoritmos Gen´ticos proviene del hecho de que se trata de una t´cnica robusta,
e
e
y pueden tratar con ´xito una gran variedad de problemas provenientes de diferentes areas, ine
´
cluyendo aquellos en los que otros m´todos encuentran dificultades. Si bien no se garantiza que el
e
Algoritmo Gen´tico encuentre la soluci´n optima del...