Algoritmos Genéticos

´
ALGORITMOS GENETICOS
1

Introducci´
on

Los Algoritmos Gen´eticos (AGs) son m´etodos adaptativos que pueden usarse para resolver problemas de b´
usqueda y optimizaci´on. Est´an basados en el proceso gen´etico de los organismos vivos. A
lo largo de las generaciones, las poblaciones evolucionan en la naturaleza de acorde con los principios de la selecci´on natural y la supervivencia delos m´as fuertes, postulados por Darwin (1859).
Por imitaci´on de este proceso, los Algoritmos Gen´eticos son capaces de ir creando soluciones para
problemas del mundo real. La evoluci´on de dichas soluciones hacia valores o´ptimos del problema
depende en buena medida de una adecuada codificaci´on de las mismas.
Los principios b´asicos de los Algoritmos Gen´eticos fueron establecidos porHolland (1975), y se
encuentran bien descritos en varios textos – Goldberg (1989), Davis (1991), Michalewicz (1992),
Reeves (1993) – .
En la naturaleza los individuos de una poblaci´on compiten entre s´ı en la b´
usqueda de recursos tales
como comida, agua y refugio. Incluso los miembros de una misma especie compiten a menudo en
la b´
usqueda de un compa˜
nero. Aquellos individuos que tienenm´as ´exito en sobrevivir y en atraer
compa˜
neros tienen mayor probabilidad de generar un gran n´
umero de descendientes. Por el contrario individuos poco dotados producir´an un menor n´
umero de descendientes. Esto significa que los
genes de los individuos mejor adaptados se propagar´an en sucesivas generaciones hacia un n´
umero de
individuos creciente. La combinaci´on de buenascaracter´ısticas provenientes de diferentes ancestros,
puede a veces producir descendientes “superindividuos”, cuya adaptaci´on es mucho mayor que la de
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´eticos usan una analog´ıa directa con el comportamiento natural. Trabajancon
una poblaci´on de individuos, cada uno de los cuales representa una soluci´on factible a un problema
dado. A cada individuo se le asigna un valor o´ puntuaci´on, relacionado con la bondad de dicha
soluci´on. En la naturaleza esto equivaldr´ıa al grado de efectividad de un organismo para competir por unos determinados recursos. Cuanto mayor sea la adaptaci´on de un individuo al problema,mayor ser´a la probabilidad de que el mismo sea seleccionado para reproducirse, cruzando su material
gen´etico con otro individuo seleccionado de igual forma. Este cruce producir´a nuevos individuos –
descendientes de los anteriores – los cuales comparten algunas de las caracter´ısticas de sus padres.
Cuanto menor sea la adaptaci´on de un individuo, menor ser´a la probabilidad de que dichoindividuo
sea seleccionado para la reproducci´on, y por tanto de que su material gen´etico se propague en sucesivas generaciones.
De esta manera se produce una nueva poblaci´on de posibles soluciones, la cual reemplaza a la anterior
y verifica la interesante propiedad de que contiene una mayor proporci´on de buenas caracter´ısticas en
comparaci´on con la poblaci´on anterior. As´ı a lo largo de lasgeneraciones las buenas caracter´ısticas
se propagan a trav´es de la poblaci´on. Favoreciendo el cruce de los individuos mejor adaptados, van
siendo exploradas las a´reas m´as prometedoras del espacio de b´
usqueda. Si el Algoritmo Gen´etico
ha sido bien dise˜
nado, la poblaci´on converger´a hacia una soluci´on o´ptima del problema.
El poder de los Algoritmos Gen´eticos proviene del hechode que se trata de una t´ecnica robusta,
y pueden tratar con ´exito una gran variedad de problemas provenientes de diferentes a´reas, incluyendo aquellos en los que otros m´etodos encuentran dificultades. Si bien no se garantiza que el
Algoritmo Gen´etico encuentre la soluci´on o´ptima del problema, existe evidencia emp´ırica de que se
encuentran soluciones de un nivel aceptable, en un tiempo...