Algunas notas sobre “Genetic Algorithms: Concepts and Applications”

En este artículo publicado en 1996 en una publicación de la IEEE, los autores, K.F. Man, K.S. Tang y S.Kwong se propusieron dar una base conceptual de algoritmos genéticos para presentárselo a ingenieros. El enfoque ingenieril sobre los GA no sólo se basa en las aplicaciones industriales posibles, sino que también, en su fundamento, intenta conformar un cuerpo de conocimiento técnico que sirva como marco de trabajo para herramientas de diseño en la ingeniería industrial.

Se hace hincapié en el trabajo fundacional de J.H.Holland de la década de 1970, enfocándose en los problemas intratables bajo otros mecanismos.

Para dar un breve pantallazo sobre los conceptos básicos, se toma el algoritmo genético clásico, en el que los cromosomas están formados por arreglos de bits, divididos en genes que expresan las características de la solución que está siendo codificada por el individuo/cromosoma.

Un valor de fitness es calculado para cada individuo utilizando la función de fitness asignada al problema, que indica cuán buena es la solución evaluada para resolver el problema en cuestión. El modelo que utiliza para representar la selección es el de la ruleta de probabilidades.

A través de la evolución genética, los individuos tienen la tendencia a mejorar su desempeño a lo largo de las generaciones.

El ciclo básico del algoritmo genético se expresa en el siguiente pseudocódigo:

Standard Genetic Algorithm ()
{
  // start with an initial time
  t := 0;
  // initialize a usually random population of individuals
  initpopulation P (t);
  //evaluate fitness of all initial individuals of population
  evaluate P (t);
  // test for termination criterion (time, fitness, etc.)
  while not done do
    // increase the time counter
    t := t + 1;
    // select a sub-population for offspring production
    P' := selectparents P (t);
    //recombine the ”genes”of selected parents
    recombine P (t);
    // perturb the mated population stochastically
    mutate P (t);
    //evaluate it’s new fitness
    evaluate P (t);
    // select the survivors from actual fitness
    P := survive P,P‘ (t);
  od
}

La selección de los parámetros de probabilidad de mutación y crossover es en si un problema complejo, un problema de optimización no lineal. De hecho, su configuración es dependiente de la función objetivo. En este punto se cita a K.A. DeJong y W.M. Spears, en “An analysis of the interacting roles of population size and crossover in genetic algorithms” y a J.J. Grefenstette en “Optimization of control parameters for genetic algo-
rithms”, donde se sugiere que para una población grande, la probabilidad de cruza debiera ser del orden de 0,6 y la de mutación, de 0,001; siendo, para una población más pequeña, la probabilidad de cruza, de 0,9 y la de mutación, 0,01.

En el ámbito teórico, los autores citan al gran trabajo de Michalewicz (“Genetic Algorithms + Data Structures = Evolution Programs”), de allí toman la teoría de los esquemas. Se llama esquema a una estructura de máscara sobre el arreglo de bits del que están formados los cromosomas. Estas máscaras funcionan como los comodines de las expresiones regulares, o de los comandos para explorar los sistemas de archivos de los sistemas operativos.

El orden de estos esquemas va a estar dado por la cantidad de posiciones fijas (con 0 o 1) en el cromosoma (las que no tienen asterisco). Es decir, que el orden del esquema determina el grado de especificidad del mismo.

Se define la longitud del esquema como la diferencia entre la posición fija más alejada del mismo y la posición fija más cercana a la primer posición (es como restar el índice de un array).

Se denota como \zeta(S,t) a la cantidad de cromosomas matcheados por el esquema S en la generación t de la corrida del algoritmo genético en cuestión. Como f(S,t) se va a denotar al fitness promedio de los individuos que matchean con el esquema S en la generación t. Se llama L a la longitud de un cromosoma.

Finalmente, se va a denotar F(t) a la sumatoria de los fitness de todos los individuos de la generación t. Y es aquí donde creemos que el artículo incluye un pequeño error, dado que dice que F(t) denota el número promedio de ocurrencias de S, lo que no tendría mucho sentido, dado que ya fue estudiado.

Siguiendo adelante en el razonamiento, y tomando las operaciones de crossover en un punto y mutación, se puede obtener una ecuación de crecimiento de un esquema de la siguiente manera:

\zeta(S,t+1) >= \zeta(S,t) \dfrac {f(S,t)}{F(t)} . [1-p_{c} \dfrac{\delta (S)}{L-1} - o(S) p_{m}]

Y es aquí donde encontramos otra diferencia con el trabajo de Michalewicz, ya que en el mismo se utiliza la notación de valor medio o promedio para F(t), es decir la sumatoria de todos los fitness de los individuos de la generación t dividido su cantidad, llamémosla N (tamaño de la población). Por tanto la ecuación de crecimiento, debiera ser escrita como:

\zeta(S,t+1) >= \zeta(S,t) \dfrac {f(S,t).N}{F(t)} . [1-p_{c} \dfrac{\delta (S)}{L-1} - o(S) p_{m}]

Cabe aclarar que F(t)>0 y que L>1

Allí se cita el teorema de los esquemas que dice que los esquemas cortos, de bajo orden, que están por encima del promedio, reciben un crecimiento exponencial en la cantidad de matcheos en las subsiguientes generaciones de un algoritmo genético.

Luego se plantea la hipótesis de los bloques de construcción, en donde se afirma que un algoritmo genético busca rendimientos cercanos al óptimo de un problema a través de la yuxtaposición de esquemas cortos, de bajo orden y alto rendimiento, llamados bloques de construcción (building blocks).

Los building blocks me remiten mentalmente al concepto de meme, acuñado por Dawkins en “The Selfish gene”, a pesar de que no creo que la naturaleza sea egoísta, siguiendo a Chaitin, en mi humilde opinión la naturaleza es más indiferente que egoísta.

Una conclusión interesante es la siguiente: dado que el mecanismo de los GA no es gobernado ni por ecuaciones diferenciales, así como tampoco se comporta como una función continua, puede concebirse que esta estructura sencilla pueda ser utilizada como un optimizador en muchas aplicaciones prácticas. Tampoco cabe ninguna duda acerca de que los GA puedan ser utilizados en problemas en los que las técnicas de hill-climbing o basadas en gradientes presentan inconvenientes.

Aunque también se hace énfasis en las limitaciones de los GA y se sugieren varias líneas de investigación, como otras estructuras de representación de cromosomas por fuera de los arreglos de bits.

Se aclara que las predicciones de los GA pueden carecer de sentido o llevar a resultados erróneos en determinados problemas, refiriéndose al problema que se da cuando se abordan temáticas con funciones deceptivas.

Como modificaciones estructurales a los algoritmos genéticos se proponen diversidad de cambio en la representación de los cromosomas. También se proponen cambios sobre la escala de valores de la función de fitness (y función objetivo), nombrando como alternativas:

  • Escala lineal
  • Escala de potencia
  • Sigma Truncation

Respecto a los mecanismos de selección, además de la ruleta se porpone Stochastic Universal Sampling (SUS) donde la complejidad algorítmica es similar, esquemas de rankings y otros.

Para la operación de crossover se propone la cruza multipunto, la cruza uniforme (por máscara) y la PMX (Partially matched crossover).

Una forma diferente de incrementar el rendimiento del algoritmo genético es intentar reordenar los genes dentro del cromosoma para encontrar patrones que tengan un mejor potencial evolutivo.

Las estrategias de reinserción en la población también son tema de discusión, generalmente se utiliza el reemplazo generacional en donde las descendencias reemplazan totalmente a los individuos que los generaron. Existe una manera elitista de reemplazar individuos, en donde permanecen los dos mejores entre “padres” e “hijos”.

Otro punto calificado de controversial es el ajuste de las probabilidades de mutación y cruza.

En ciertos procesos dinámicos es difícil mantener estático el “entorno”. En el enfoque tradicional de algoritmos genéticos existen complicaciones para variar el entorno, es por eso que se han desarrollado extensiones como la posibilidad de mantener individuos diploides con una representación tri-alélica para decidir dominancia de genes, de modo de poder ser más flexible a la hora de cambiar el enterno en el que son evaluados los individuos. Otras técnicas para el cambio de entorno incluyen la migración de individuos para generar mayor diversidad, o la introducción en determinado momento de un mecanismo de hipermutación (un cambio radical en la tasa de mutación).

Respecto de la paralelización, se dice que la performance serial de los GA no es buena respecto de otros mecanismos de optimización o búsqueda, dado que no se basa en heurística alguna. Para eso se han desarrollado modelos de procesamiento en paralelo, siendo los principales:

  • Global: Hay una sola población y se procesa en paralelo, siendo más apto para los enfoques de paralelismo en memoria compartida.
  • Migración de individuos en donde hay islas de evolución que corren en paralelo y cada tanto migran individuos.
  • Difusión en donde cada individuo se le asigna una ubicación en una plantilla de 2 dimensiones y sólo puede cruzarse con individuos “cercanos”, este enfoque de difusión ha evolucionado al enfoque celular.

Uno de los nichos de utilización de GA es el de optimización multiobjetivo, dado que matemáticamente es muy complejo resolver este tipo de problemas. Se ha demostrado que los GA son particularmente aptos para encontrar conjuntos de soluciones Pareto-óptimas.

Los problemas más evidentes que se detectan en los GA son:

  • Deception: Existen funciones que son GA-deceptivas, en donde la combinación de building blocks positivos evolutivamente hablando no generan una descendencia mejor que sus antecesores.
  • Estancamiento en subóptimos: Dado que los GA no buscan óptimos globales, existe la posibilidad de que la evolución se estanque en un óptimo local y no pueda salir de allí. Existen diversas técnicas para evitar este tipo de comportamientos.
  • Tiempo real: Los GA no son una técnica aplicable fácilmente a problemas de tiempo real.

Finalmente se describen situaciones prácticas en las que los GA han sido exitosamente implementados, describiendo particularidades de cada implementación:

  • Parámetros e Identificación de Sistema (IIR)
  • Procesos de Control (por ejemplo proceso de neutralización de pH)
  • Robótica (navegación, cálculo de trayectorias)
  • Reconocimiento de patrones (imágenes, tanto en el proceso de extracción, como en el de reconocimiento en si)
  • Reconocimiento del habla
  • Diseño e ingeniería (VLSI)
  • Planificación y Scheduling (travelling salesman, pump scheduling, job-shop scheduling, etc)
  • Sistemas de clasificación (detección de pérdidas de gas y control de cañerías).

Tecnología emergente a partir de los algoritmos genéticos:

  • Integración con las redes neuronales: en donde los GA pueden ser buenos seleccionando las reglas de aprendizaje o los parámetros de las redes neuronales, pudiendo funcionar como buenos supervisores de aprendizaje.
  • Integración con lógica difusa: este punto es más complejo porque no hay una relación de feedback tan evidente como con las reglas neuronales.
Anuncios

Deje un comentario

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s