La formulación tradicional de un algoritmo genético fue presentada de excelente manera por el discípulo de Jhon Holland llamado David Goldberg, este último popularizó el uso de los algoritmos genéticos para una variada gama de problemas en las áreas de búsqueda, optimización y aprendizaje automático. En su formulación clásica, los algoritmos genéticos se basan en el esquema genérico de un algoritmo evolutivo. A partir de este esquema, el algoritmo genético define “operadores evolutivos” que implementan la recombinación de individuos, a través del operador de apareamiento, y la variación aleatoria para proporcionar diversidad, el operador de mutación. La característica distintiva de los algoritmos genéticos respecto a las otras técnicas evolutivas consiste en el uso fundamental del apareamiento como operador principal, mientras que la mutación se utiliza como operador secundario tan solo para agregar una nueva fuente de diversidad en el mecanismo de exploración del espacio de soluciones del problema. Inclusive la mutación puede llegar a ser un operador opcional o estar ausente en algunas variantes de algoritmos genéticos que utilizan otros operadores para introducir diversidad. En general, los algoritmos genéticos se han utilizado para trabajar con codificaciones binarias para problemas de búsqueda en espacios de cardinalidad numerable, aunque su alto nivel de aplicabilidad ha llevado a proponer su trabajo con codificaciones reales, e inclusive con codificaciones no tradicionales, dependientes de los problemas a resolver.
La gran mayoría de las variantes de algoritmos genéticos utiliza como principales operadores a la selección, el apareamiento o recombinación y la mutación. El mecanismo de selección determina el modo de perpetuar buenas características, que se asumen son aquellas presentes en los individuos más adaptados. El mecanismo de selección proporcional o selección por ruleta elige aleatoriamente individuos utilizando una ruleta sesgada, en la cual la probabilidad de ser seleccionado es proporcional a la adaptabilidad de cada individuo. Otros mecanismos de selección introducen diferentes grados de elitismo, conservando un cierto número prefijado de los mejores individuos a través de las generaciones. En el caso de la selección por torneo se escogen aleatoriamente un determinado número de individuos de la población, los cuales compiten entre ellos para determinar cuáles se seleccionarán para reproducirse, de acuerdo a sus valores de adaptación. El mecanismo de selección basado en el rango introduce el mayor grado de elitismo posible, al mantener entre generaciones un porcentaje generalmente elevado, de los mejores individuos de la población. Estas diferentes políticas de selección, conjuntamente con políticas similares utilizadas para determinar los individuos reemplazados por los descendientes generados posibilitan el diseño de diferentes modelos evolutivos para los algoritmos genéticos. Los esquemas de codificación binaria de tamaño fijo tienen como ventaja principal que resulta sencillo definir operadores evolutivos simples sobre ellos. En la formulación clásica de un algoritmo genético, denominada por Goldberg como algoritmo genético simple, se propone como operador de recombinación el apareamiento de un punto, que consiste en obtener dos descendientes a partir de dos individuos padres seleccionando un punto al azar, cortando los padres e intercambiando los trozos del cromosoma.
El operador tradicional de mutación introduce diversidad en el mecanismo evolutivo, simplemente modificando de manera aleatoria uno de los valores binarios del cromosoma. Sobre un esquema de codificación binaria la modificación consiste en invertir el valor binario de un alelo, y por ello recibe el nombre de mutación de inversión del valor de un bit. El operador tradicional de mutación introduce diversidad en el mecanismo evolutivo, simplemente modificando aleatoriamente uno de los valores binarios del cromosoma. Sobre un esquema de codificación binaria la modificación consiste en invertir el valor binario de un alelo, y por ello recibe el nombre de mutación de inversión del valor de un bit. Tanto el apareamiento como la mutación son operadores probabilísticos, en el sentido en que se aplican o no, teniendo en cuenta una tasa de aplicación del operador. Generalmente la tasa de aplicación del operador de apareamiento es elevada en un algoritmo genético simple, mientras que la tasa de aplicación del operador de mutación es muy baja, del orden de 0,001 para cada bit en la representación. Algunos operadores evolutivos más complejos han sido propuestos como alternativas para modificar el comportamiento del mecanismo de exploración del espacio de soluciones. Es habitual encontrar operadores de apareamiento multipunto en donde se utilizan dos o más puntos de corte o uniformes en donde para cada posición en el cromosoma se decide intercambiar material genético de acuerdo a una probabilidad prefijada.
El operador de selección juega un importante papel tanto en los algoritmos evolutivos secuenciales como en los paralelos, ya que guía la búsqueda y provoca la convergencia de la población de individuos. Por tanto, representa el tan importante compromiso entre exploración y explotación. De entre los operadores de selección proporcional a la adecuación, la implementación conocida como “ruleta” es la más popular. Sin embargo, también es de mayor complejidad algorítmica y con tendencia a cometer errores estocásticos respecto de la implementación conocida como “muestreo estocástico universal”. De hecho, la selección proporcional a la adecuación puede usarse para seleccionar un conjunto arbitrario de parejas y por tanto puede utilizarse en modelos secuenciales generacionales o de estado estacionario, así como en modelos paralelos distribuidos o celulares. La selección proporcional usa el valor de adecuación para seleccionar parejas o bien el individuo que se desea reemplazar. Algunos mecanismos utilizan una ordenación creciente atendiendo a la adecuación de los individuos para después seleccionar atendiendo a su posición en dicha ordenación. Esto reduce el error estocástico debido a valores de adecuación similares. Existen muchos otros mecanismos de selección interesantes como el torneo, y sobre todo variantes de estos modelos básicos que modifican de alguna forma la probabilidad de selección.
El operador de apareamiento es muy importante en el campo de los algoritmos genéticos. Existen numerosas variantes de él, todas ellas clasificables en tres categorías de alto nivel: (1) Operadores de apareamiento puros. Los cuales pueden ser aplicados en cualquier algoritmo genético. (2) Operadores de apareamiento híbridos: que mezclan un operador puro con una técnica no genética. (3) Operadores de apareamiento dependientes del problema: operadores que realizan operaciones basadas en el conocimiento del problema y por tanto son sólo aplicables a dicho problema. Existen numerosos tipos de apareamiento. El estándar es binario y genera dos hijos. Sin embargo no es raro encontrar aplicaciones que usan un apareamiento que genera un único hijo. También existen operadores de apareamiento típicos de problemas de reordenación y otros campos sobre todo de optimización combinatoria, en los que dicho operador transmite de padres a hijos la admisibilidad como solución al problema. El operador más tradicional genera aleatoriamente el mismo punto de apareamiento en ambos padres e intercambia los cuatro segmentos resultantes dando lugar a dos hijos nuevos. Existen numerosas extensiones a dos puntos y N puntos. Esta familia de operadores de apareamiento es eficiente y de aplicación bastante genérica. El apareamiento aritmético tradicional es un tipo especial de operador aritmético sesgado. El sesgo hacia el mejor padre de los dos últimos operadores permite introducir un componente de explotación en el comportamiento de exploración típico de cualquier apareamiento. Ambos operadores trabajan con independencia de la longitud de la cadena de parámetros, lo que supone una ventaja adicional en ciertos problemas.
El operador de mutación se describe por la instanciación a dos operadores concretos del operador genérico mencionado para un algoritmo genético. En el caso de genotipo binario se utiliza el tradicional operador de complemento de bits, mientras que en el caso de genotipo real se utiliza una definición propia que se encuentra implementada de forma parecida en la literatura asociada a este tipo de codificación. La mutación ha sido tradicionalmente entendida como un operador de segunda fila en los algoritmos genéticos. Sin embargo, numerosos estudios en este campo, así como en otros dominios donde la mutación es determinante, han puesto de manifiesto la gran importancia de este operador en problemas de complejidad real, ya que es el único que introduce nueva información en una población secuencial, permitiendo así escapar de óptimos locales y ampliando la exploración del algoritmo. Tanto el apareamiento como la mutación pueden sufrir un cambio dinámico durante la evolución en su conjunto de parámetros, típicamente en la probabilidad de aplicación. Esta característica ha proporcionado buenos resultados en algunos campos de aplicación aunque aún es un proceso relativamente caro debido a que dichos cambios surgen como consecuencia de una monitorización de la diversidad de la población, menor distancia de Hamming, mayor mutación o de la aportación que hacen a la adecuación de los descendientes generados.
No hay comentarios:
Publicar un comentario