1 Introduccion
Los Algoritmos Geneticos (AGs) son metodos adaptivos que pueden usarse para resolver problemas de busqueda y optimizacion. Estan basados en el proceso genetico de los organismos vivos. A lo largo de las generaciones, las poblaciones evolucionan en la naturaleza acorde con los principios de la seleccion natural y la supervivencia de los mas fuertes, postulados por Darwin .
Por imitacion de este proceso, los Algoritmos Geneticos son capaces de ir creando soluciones para problemas del mundo real. La evolucion de dichas soluciones hacia valores optimos del problema depende en buena medida de una adecuada codificacion de las mismas.
Los principios basicos de los Algoritmos Geneticos fueron establecidos por Holland, y se encuentran bien descriptos en varios textos Goldberg, Davis, Michalewicz, Reeves .
En la naturaleza los individuos de una poblacion compiten entre si en la busqueda de recursos tales como comida, agua y refugio. Incluso los miembros de una misma especie compiten a menudo en la busqueda de una pareja. Aquellos individuos que tienen mas exito en sobrevivir y en atraer companeros tienen mayor probabilidad de generar un gran numero de descendientes. Por el contrario individuos poco dotados produciran un menor numero de descendientes. Esto significa que los genes de los individuos mejor adaptados se propagaran en sucesivas generaciones hacia un numero de individuos creciente. La combinacion de buenas caracteristicas provenientes de diferentes ancestros, puede a veces producir descendientes particularmente interesantes (superindividuos), ya que se encuentran muy bien dotados, con una gran adaptacion, tipicamente mucho mayor que la de cualquiera de sus ancestros. De esta manera, las especies evolucionan logrando caracteristicas cada vez mejor adaptadas al entorno en el que viven.
Los Algoritmos Geneticos usan una analogia directa con el comportamiento natural. Trabajan con una poblacion de individuos, cada uno de los cuales representa una solucion factible a un problema dado. A cada individuo se le asigna un valor o puntuacion, relacionado con la bondad de dicha solucion. En la naturaleza esto equivaldria al grado de efectividad de un organismo para competir por unos determinados recursos. Cuanto mayor sea la adaptacion de un individuo al problema, mayor sera la probabilidad de que el mismo sea seleccionado para reproducirse, cruzando su material genetico con otro individuo seleccionado de igual forma. Esta cruza producira nuevos individuos descendientes de los anteriores los cuales compartiran algunas de las caracteristicas de sus padres. Cuanto menor sea la adaptacion de un individuo, menor sera la probabilidad de que dicho individuo sea seleccionado para la reproduccion, y por tanto de que su material genetico se propague en sucesivas generaciones.
De esta manera se produce una nueva poblacion de posibles soluciones, la cual reemplaza a la anterior y verifica una interesante propiedad: contiene una mayor proporcion de buenas caracteristicas en comparacion con la poblacion anterior. Asi, a lo largo de las generaciones las buenas caracteristicas se propagan a traves de la poblacion, con lo que las areas mas prometedoras del espacio de busqueda van siendo exploradas al favorecer el cruce de los individuos mejor adaptados. Si el Algoritmo Genetico ha sido bien diseniado, la poblacion convergera hacia una generacion que contenga una solucion optima del problema.
El poder de los Algoritmos Geneticos proviene del hecho de que se trata de una tecnica robusta, y pueden tratar con exito una gran variedad de problemas provenientes de diferentes areas, incluyendo aquellos en los que otros metodos encuentran dificultades. Un Algoritmo Genetico encuentra la solucion optima a un problema, hecho demostrado por Holland, pero sin tener en cuenta el tiempo para encontrarla, de modo que muchas veces esta busqueda no resulta efectiva. Muchas veces existe evidencia empirica de que se encuentran soluciones de un nivel aceptable, en un tiempo competitivo con el resto de algoritmos de optimizacion combinatoria. En el caso de que existan tecnicas especializadas para resolver un determinado problema, lo mas probable es que superen a los Algoritmo Genetico, tanto en rapidez como en eficacia. El gran campo de aplicacion de los Algoritmos Geneticos se relaciona con aquellos problemas para los cuales no existen tecnicas especializadas. Incluso en el caso en que dichas tecnicas existan, y funcionen bien, pueden efectuarse mejoras de las mismas construyendo un hibrido tecnica especializada-Algoritmos Geneticos.
2 Algoritmo Genetico Simple (AGS)
Un Algoritmo Genetico Simple, tambien denominado canonico, se muestra en el siguiente codigo. Como se vera a continuacion, se necesita una codificacion o representacion del problema, que resulte adecuada al mismo. Ademas se requiere una funcion de ajuste (fitness) o adaptacion al problema, la cual asigna un numero real a cada posible solucion codificada. Durante la ejecucion del algoritmo, los padres se seleccionan para la reproduccion, a continuacion dichos padres seleccionados se cruzaran generando hijos (quizas dos), sobre cada uno de los cuales actuara un operador de mutacion. El resultado de la combinacion de las anteriores funciones sera un conjunto de individuos (posibles soluciones al problema), los cuales en la evolucion del Algoritmo Genetico formaran parte de la siguiente poblacion.
begin / Algoritmo Genetico Simple /
generar una poblacion inicial
computar la funcion de evaluacion de cada individuo
while not terminado do
begin / Producir una Nueva Generacion /
for tamanio de la poblacion/2 do
begin / Ciclo Reproductivo /
seleccionar dos individuos de la anterior
generacion para la cruza, con una probabilidad
de seleccion proporcional al valor de la funcion
de evaluacion de cada individuo.
cruzar con una probabilidad adecuada los dos
Individuos obteniendo dos descendientes
mutar los dos descendientes aleatoriamente,
con un valor de probabilidad asociada.
computar la funcion de evaluacion de los dos
descendientes mutados.
insertar los dos descendientes mutados en la
nueva generacion
end
if se encontro una solucion con un error aceptable then
terminado = TRUE
end
end
2.1 Codificacion
Se supone que los individuos (posibles soluciones del problema), pueden representarse como un conjunto de parametros, los cuales agrupados forman una cadena de valores (a menudo referida como cromosoma). Si bien el alfabeto utilizado para representar los individuos no debe necesariamente coincidir con el binario, buena parte de la teoria en la que se fundamentan los Algoritmos Geneticos utiliza dicho alfabeto.
En terminos biologicos, el conjunto de parametros que representan un cromosoma particular se denomina fenotipo. El fenotipo contiene la informacion requerida para construir un organismo, el cual se refiere como genotipo. Los mismos terminos se utilizan en el campo de los Algoritmos Geneticos. La adaptacion al problema de un individuo depende de la evaluacion del genotipo. Esta ultima puede inferirse a partir del fenotipo, es decir puede ser computada a partir del cromosoma, usando la funcion de evaluacion la que se disenia para cada problema de manera especifica. Dado un cromosoma particular, la funcion de adaptacion le asigna un numero real, que se supone refleja el nivel de adaptacion al problema del individuo representado por el cromosoma.
Durante la fase reproductiva se seleccionan los individuos de la poblacion para cruzarse y producir descendientes, los que constituiran, una vez mutados (si asi resulta de un valor de probabilidad asociado), la siguiente generacion de individuos. La seleccion de padres se efectua al azar usando un procedimiento que favorezca a los individuos mejor adaptados, ya que a cada individuo se le asigna una probabilidad de ser seleccionado, proporcional a su funcion de adaptacion. Este procedimiento se dice basado en el metodo de ruleta sesgada. Segun dicho esquema, los individuos bien adaptados se escogeran probablemente varias veces por generacion, mientras que, los pobremente adaptados al problema, no se escogeran mas que de vez en cuando o nunca.
Una vez seleccionados dos padres, sus cromosomas se combinan, utilizando habitualmente los operadores de cruce y mutacion. Las formas basicas de dichos operadores se describen a continuacion.
operador de cruza: toma dos padres seleccionados y corta sus cadenas de cromosomas en una posicion escogida al azar, para producir dos subcadenas iniciales y dos subcadenas finales. Despues se intercambian las subcadenas finales, produciendose dos nuevos cromosomas completos (vease la Figura 2). Ambos descendientes heredan genes de cada uno de los padres. Este operador se conoce como operador de cruza basado en un punto. Habitualmente el operador de cruce no se aplica a todos los pares de individuos que han sido seleccionados para emparejarse, sino que se aplica de manera aleatoria, normalmente con una probabilidad comprendida entre 0.5 y 1.0. En el caso en que el operador de cruza no se aplique, la descendencia se obtiene simplemente duplicando los padres.
operador de mutacion :se aplica a cada hijo de manera individual, y consiste en la alteracion aleatoria (normalmente con probabilidad pequenia) de cada gen componente del cromosoma. Si bien puede en principio pensarse que el operador de cruza es mas importante que el operador de mutacion, ya que proporciona una exploracion rapida del espacio de busqueda, este ultimo asegura que ningun punto deI espacio de busqueda tenga probabilidad cero de ser examinado, y es de capital importancia para asegurar la convergencia de los Algoritmos Geneticos.
Para criterios practicos, es muy util la definicion de convergencia introducida en este campo por De Jong en su tesis doctoral. Si el Algoritmo Genetico ha sido correctamente implementado, la poblacion evolucionara a lo largo de las generaciones sucesivas de tal manera que la adaptacion media extendida a todos los individuos de la poblacion, asi como la adaptacion del mejor individuo, se iran incrementando hacia el optimo global. El concepto de convergencia esta relacionado con la progresion hacia la uniformidad: un gen ha convergido cuando al menos el 95 % de los individuos de la poblacion comparten el mismo valor para dicho gen. Se dice que la poblacion converge cuando todos los genes han convergido. Se puede generalizar dicha definicion al caso en que al menos un poco de los individuos de la poblacion hayan convergido.
A medida que el numero de generaciones aumenta, es mas probable que la adaptacion media se aproxime a la del mejor individuo y por ende a la solucion del problema .
