Site hosted by Angelfire.com: Build your free website today!

ALGORITMOS GENÉTICOS.

3. ¿QUÉ ES UN ALGORITMO GENÉTICO?

Analicemos el modelo biológico desde el punto de vista informático. ¿Podemos crear un algoritmo con la misma filosofía que emplea la naturaleza? Parece que a la naturaleza le va bien el método y con este planteamiento nacieron los algoritmos genéticos.

La idea básica es la siguiente: generemos un conjunto con algunas de las posibles soluciones. Cada una va a ser llamada individuo, y a dicho conjunto se le denominará población.

Cada individuo tiene una información asociada a él. En un problema de optimización corresponde a las variables libres, es decir, aquellas a las que el algoritmo tiene que asignar un valor para que una función sea mínima o máxima para esos valores. Esa función es la denominada en el tema anterior función de costo. Esta función en nuestro modelo biológico, sin embargo, se denominará función de adaptación en nuestro modelo; y determina el grado de adaptación de un individuo. A dicha información se la va a denominar código genético.

Las características de los individuos, sean beneficiosas o no, se van a denominar fenotipos. La información asociada a un individuo se compone de partes indivisibles denominados cromosomas.

Un fenotipo puede estar en más de un cromosoma, en cuyo caso puede ser que el hijo herede un fenotipo que no tenía ni el padre ni la madre, sino una combinación de ambos. Un ejemplo en el humano es el color de la piel o la estructura del cráneo. En caso de que el hijo tenga parte de los genes del padre y parte de los genes de la madre que intervienen en un fenotipo, se va a crear una característica nueva asociada a ese fenotipo. De todas formas, no es un enfoque muy frecuente, ya que debemos asegurar que el conjunto de los fenomas tendrá ley de composición interna respecto al operador de cruce definido sobre el alfabeto cromosómico. Por otro lado, que un cromosoma codifique más de un fenotipo es más raro todavía. El cromosoma debe tener en dicho caso tantos valores como el producto del número de valores posibles que tenga cada fenotipo del cromosoma. Esto es un inconveniente para los problemas de naturaleza discreta y de conjunto de soluciones acotado, ya que puede ocurrir que no podamos dar nunca soluciones que pertenezcan a alguna parte del espacio de estados -ley de composición interna-. En el caso de los problemas continuos o de alfabeto no acotado es peor, ya que en muy contadas ocasiones podemos asegurar la ley de composición interna del operador de cruce. Obsérvese que, tanto la forma de codificar los fenotipos en los cromosomas, como la determinación de qué es fenotipo -o dicho de otra forma, como la información va a ser almacenada en el código genético- son de vital importancia en los algoritmos genéticos. Escoger equivocadamente la forma de almacenar la información puede ralentizar la convergencia -es decir, que tardemos más en encontrar la solución-, o que no converja de ninguna forma -es decir, que la población esté errando aleatoriamente por efecto de las mutaciones y de los cruzamientos, sin llegar nunca a un punto estable, en un fenómeno que se denomina deriva genética-. Puede ser peor, ya que, si existen variables libres en la función de coste no controladas dentro del genoma, podemos llegar a una solución estable que no es el mínimo de la función de coste, y que puede que ni siquiera sea el mínimo local. Es interesante que parte de la información heurística de la que disponemos ha de ser suficiente como para permitirnos una codificación razonablemente buena; si no, la implementación de este algoritmo y su convergencia no será satisfactoria.

Los algoritmos genéticos son métodos sistemáticos para la resolución de problemas de búsqueda y optimización que aplican a estos los mismos métodos de la evolución biológica: selección basada en la población, reproducción sexual y mutación; es decir, consiste en una función matemática o una rutina de software que toma como entradas a los ejemplares y retorna como salidas cuales de ellos deben generar descendencia para la nueva generación.

Los algoritmos genéticos son métodos de optimización, que tratan de resolver el mismo conjunto de problemas que se ha contemplado anteriormente, es decir, hallar (xi,...,xn) tales que F(xi,...,xn) sea máximo. En un algoritmo genético, tras parametrizar el problema en una serie de variables, (xi,...,xn) se codifican en un cromosoma. Todas los operadores utilizados por un algoritmo genético se aplicarán sobre estos cromosomas, o sobre poblaciones de ellos. En el algoritmo genético va implícito el método para resolver el problema; son solo parámetros de tal método los que están codificados, a diferencia de otros algoritmos evolutivos como la programación genética. Hay que tener en cuenta que un algoritmo genético es independiente del problema, lo cual lo hace un algoritmo robusto, por ser útil para cualquier problema, pero a la vez débil, pues no está especializado en ninguno.

Las soluciones codificadas en un cromosoma compiten para ver cuál constituye la mejor solución (aunque no necesariamente la mejor de todas las soluciones posibles). El ambiente, constituido por las otras camaradas soluciones, ejercerá una presión selectiva sobre la población, de forma que sólo los mejor adaptados (aquellos que resuelvan mejor el problema) sobrevivan o leguen su material genético a las siguientes generaciones, igual que en la evolución de las especies. La diversidad genética se introduce mediante mutaciones y reproducción sexual.

En la Naturaleza lo único que hay que optimizar es la supervivencia, y eso significa a su vez maximizar diversos factores y minimizar otros. Un algoritmo genético, sin embargo, se usará para optimizar habitualmente para optimizar sólo una función, no diversas funciones relacionadas entre sí simultáneamente. Este tipo de optimización, denominada optimización multimodal, también se suele abordar con un algoritmo genético especializado.

Por lo tanto, un algoritmo genético consiste en lo siguiente: hallar de qué parámetros depende el problema, codificarlos en un cromosoma, y se aplican los métodos de la evolución: selección y reproducción sexual con intercambio de información y alteraciones que generan diversidad.

Los algoritmos genéticos establecen una analogía entre el conjunto de soluciones de un problema y el conjunto de individuos de una población natural, codificando la información de cada solución en un string (vector binario) a modo de cromosoma. En palabras del propio Holland:

"Se pueden encontrar soluciones aproximadas a problemas de gran complejidad computacional mediante un proceso de "evolución simulada",

A tal efecto se introduce una función de evaluación de los cromosomas, que llamaremos calidad ("fitness") y que está basada en la función objetivo del problema. Igualmente se introduce un mecanismo de selección de manera que los cromosomas con mejor evaluación sean escogidos para "reproducirse" mas a menudo que los que la tienen peor.

Los algoritmos desarrollados por Holland inicialmente eran sencillos pero dieron buenos resultados en problemas considerados difíciles. Los algoritmos Genéticos están basados en integrar e implementar eficientemente dos ideas fundamentales: Las representaciones simples como strings binarios de las soluciones del problema y la realización de transformaciones simples para modificar y mejorar estas representaciones.

Para llevar a la práctica el esquema anterior y concretarlo en un algoritmo, hay que especificar los siguientes elementos:

Representación cromosómica

En los trabajos originales las soluciones se representaban por strings binarios, es decir, listas de 1s y 0s. Este tipo de representaciones ha sido ampliamente utilizada incluso en problemas en donde no es muy natural. En 1985, De Jong introduce la siguiente cuestión: ¿Qué se debe hacer cuando los elementos del espacio de búsqueda se representan de modo natural por estructuras complejas como vectores, árboles o grafos?, ¿Se debe intentar linealizar en un string o trabajar directamente con estas estructuras?

En la actualidad podemos distinguir dos escuelas:

Hemos de notar que las operaciones genéticas dependen del tipo de representación, por lo que la elección de una condiciona a la otra.

La ventaja de las primeras es que permite definir fácilmente operaciones de recombinación, además los resultados sobre convergencia están probados para el caso de strings binarios. Sin embargo en algunos problemas puede ser poco natural y eficiente el utilizarlas. Por ejemplo en el problema del agente viajero sobre 5 ciudades y 20 aristas, el string 01000100001000100010 representa una solución sobre las aristas ordenadas. Sin embargo dicha representación no es muy natural y además, no todos los strings con cinco 1s representan soluciones lo cual complica substancialmente la definición de una operación de sobrecruzamiento. Es mas natural la ruta de ciudades: (2,3,1,5,4), lo cual permite definir naturalmente diferentes operaciones estables.

Población inicial

La población inicial suele ser generada aleatoriamente. Sin embargo, últimamente se están utilizando métodos heurísticos para generar soluciones iniciales de buena calidad. En este caso, es importante garantizar la diversidad estructural de estas soluciones para tener una "representación" de la mayor parte de población posible o al menos evitar la convergencia prematura.

Medida de evaluación

Respecto a la evaluación de los cromosomas, se suele utilizar la calidad como medida de la bondad según el valor de la función objetivo en el que se puede añadir un factor de penalización para controlar la infactibilidad. Este factor puede ser estático o ajustarse dinámicamente, lo cual produciría un efecto similar al de la Oscilación Estratégica en Tabu Search:

 

calidad = ValorObjetivoNormalizado - Penalización * MedidaInfactibilidad

 
Selección
La selección de los padres viene dada habitualmente mediante probabilidades según su fitness. Uno de los procedimientos más utilizado es el denominado de la ruleta en donde cada individuo tiene una sección circular de una ruleta que es directamente proporcional a su calidad. Para realizar una selección se realizaría un tirada de bola en la ruleta, tomando el individuo asociado a la casilla donde cayo la bola.

 

Operadores de recombinación
Los Operadores de Cruzamiento más utilizados son:
Mutación

La operación de Mutación más sencilla, y una de la más utilizadas consiste en reemplazar con cierta probabilidad el valor de un bit. Notar que el papel que juega la mutación es el de introducir un factor de diversificación ya que, en ocasiones, la convergencia del procedimiento a buenas soluciones puede ser prematura y quedarse atrapado en óptimos locales. Otra forma obvia de introducir nuevos elementos en una población es recombinar elementos tomados al azar sin considerar su fitness.

 

 

 

                                                                                                                    

ANTERIOR       SIGUIENTE

 

ÍNDICE