| Artículos | 01 JUL 1997

Un algoritmo genético simple

Tags: Histórico
Eloy Anguiano.

Imaginemos un mundo abstracto lleno de unos seres vivos dotados de sistemas de decisión siendo éste el más sencillo posible. Los ingenieros informáticos los denominan autómatas finitos. En este mundo cada individuo está controlado por un cromosoma único.

Estos individuos se van a ver sometidos a una serie de situaciones ambientales a las que el individuo deberá adaptarse por predicción. Es decir, todos los individuos de este mundo imaginario sobrevivirán más fácilmente cuanto más sean capaces de predecir los cambios que sufrirá el ambiente a corto plazo. En cada generación los más adaptados se reproducirán y los menos adaptados morirán. Al cabo de unas cuantas generaciones obtendremos casi con seguridad una serie de individuos de capacidad de predicción próxima a la perfección.

Este sistema es lo que los informáticos han dado en denominar algoritmos genéticos por su similitud con los procesos de selección natural. Si conseguimos codificar adecuadamente un problema de tal forma que la codificación sea el problema y el cromosoma la solución seremos capaces de resolver problemas aplicando esta técnica. Es más, se ha utilizado en sistemas clasificadores, funcionamiento de oleoductos, desarrollo de sistemas robóticos para tareas específicas y en muchos otros problemas difíciles de enumerar de forma sistemática.

Hace ya más de treinta años que el pionero de estos algoritmos, John H. Holland de la universidad de Míchigan, los propuso y utilizó para resolver problemas de difícil solución. En este artículo vamos a ver cómo funcionan estos algoritmos genéticos a través de un ejemplo sencillo que cualquiera con un mínimo de conocimientos de programación puede realizar en su ordenador.

Lo primero y más importante es determinar qué es un autómata finito puesto que cada uno de los individuos que van a sucederse generación tras generación lo van a ser. Un autómata finito es un elemento que se puede encontrar en un estado determinado elegido entre un conjunto finito de estados. Tras la recepción de una señal de entrada el estado del autómata cambia a otro de los estados (o incluso al mismo estado) y genera una señal de salida. En la figura adjunta se representa la tabla de transformación del autómata. Los posibles estados del autómata son el ROJO, el AZUL y el VERDE. Las señales pueden ser BLANCAS o NEGRAS. Para saber que sucede en una situación determinada se escoje la señal de entrada entre las dos de arriba y el estado entre los tres de la izquierda. En la intersección se encuentran el nuevo estado y la salida.

Supongamos que el autómata está en el estado ROJO (izquierda) y que llega una señal NEGRA, entonces, el autómata se pondrá en el estado AZUL y generará una señal de salida BLANCA. Supongamos que, en cualquier otro momento el autómata está en AZUL y que recibe una señal NEGRA. En esta situación el autómata se pondrá VERDE y generará una señal de salida NEGRA. Inicialmente, todos los autómatas toman un estado inicial específico que puede ser cualquiera de los estados accesibles.

Las señales, al ser biestables en este caso pueden ser generadas con solo dos números, el 1 y el 0 y los estados necesitan de tres valores, por ejemplo el 0, el 1 y el 2. Una vez que hemos definido lo que es un autómata finito vamos a ver cómo aplicar sobre un conjunto de ellos un algoritmo que se pueda calificar de genético.

El primer paso es redistribuir la matriz anterior uniendo las distintas filas hasta realizar una ristra para después cerrarla sobre sí misma para crear un cromosoma circular. El siguiente paso es crear un conjunto discreto de individuos (cromosomas) de forma aleatoria. El número de estos individuos debe ser lo suficientemente grande como para que la evolución sea posible y lo suficientemente pequeño como para que el problema sea tratable en un tiempo razonable. Evidentemente será uno de los parámetros de nuestro programa. Otros dos parámetros de nuestro programa serán el número de estados en los que puede estar el autómata y el número de señales que puede recibir y generar.

Una vez creados los individuos es necesario crear un ambiente al que tienen que adaptarse. Este ambiente puede ser una sucesión aleatoria de señales o una predeterminada por el programador.

El número de señales que determinan el ambiente puede ser cualquiera pero la predicción perfecta de un ambiente muy variable (con un patrón de ambiente muy largo) exige cromosomas con un número de estados más grande, de otra forma, ningún individuo podrá adaptarse perfectamente a la situación ambiental. Una situación ambiental válida y para la que se puede encontrar para un autómata con tres estados y dos señales que se adapte perfectamente es por ejemplo:

011010011010011010011010

donde la parte en negrita es el patrón ambiental básico. La salida que genera cada individuo deberá ser comparada con el ambiente de tal forma que el individuo está más adaptado al ambiente cuanta mayor es su capacidad de predicción del siguiente estado ambiental. Es decir, el patrón de salida de un individuo perfectamente adaptado al caso anterior es:

110100110100110100110100

en el que se repite el mismo patrón pero desplazado un lugar a la izquierda.

Pero, ¿cuál es el sistema por el cual se adaptan los cromosomas al ambiente?. Es muy sencillo. Podemos idear un sistema de clasificación de individuos en función de su capacidad de predicción, es decir simplemente utilizando el numero de aciertos totales. Una vez clasificados, unos cuantos de los de máxima puntuación, pongamos el 10%, se van a reproducir con otros tantos de los restantes elegidos al azar. El obtenido por el método de reproducción que describiré a continuación substituirá al elegido al azar.

La reproducción es muy sencilla basta con elegir dos posiciones del cromosoma al azar. La porción de cromosoma entre estas dos posiciones del primero de los individuos se inserta en el mismo lugar del cromosoma del segundo individuo formando un tercero que le substituye. Otro método de variación del que no hay que abusar es la alteración genética individual. Consiste en elegir un individuo al azar y de ese individuo un elemento de su cromosoma (aleatoriamente) y cambiarlo (también aleatoriamente) a uno de sus posibles valores. Este proceso se repite generación tras generación y veremos que los individuos estarán cada vez mejor adaptados hasta llegar al perfectamente adaptado si esto es posible.

Una vez programado este algoritmo es fácil ver variante aplicables de forma sencilla y otras mas complejas. Si alguno de los lectores consigue una variante que le parezca interesante puede comentármelo y consideraré su publicación en este reducido espacio.

Contenidos recomendados...

Comentar
Para comentar, es necesario iniciar sesión
Se muestran 0 comentarios
X

Uso de cookies

Esta web utiliza cookies técnicas, de personalización y análisis, propias y de terceros, para facilitarle la navegación de forma anónima y analizar estadísticas del uso de la web. Consideramos que si continúa navegando, acepta su uso. Obtener más información