Algoritmos Bioinspirados

En nuestro entorno se dan una serie de acontencimientos que han inspirado algunos algoritmos de búsqueda de soluciones. Algoritmos genéticos y colonia de hormigas son algunos de ellos.
Estos algoritmos ofrecen soluciones óptimas y pseudoóptimas, y su estudio ha demostrado que se pueden obtener muy buenos resultados en un tiempo en el que otros algoritmos de búsqueda en profundidad no se acercaría ni por asomo a una solución semejante.

Genético:

El funcionamiento del genético se basa en la generación de estados mediante un conjunto de individuos, que forman una población.
Cada individuo se compone de un conjunto de genes, que suelen ser 0 y 1s, aunque pueden ser enteros, caracteres... todo es cuestión de saber interpretar el estado y la solución obtenida según la representación del individuo escogida.
Esta población se va modificando mediante la reproducción de unos individuos que han pasado un proceso de selección, mezclando sus genes. La probabilidad de que un individuo sea escogido para la reproducción es proporcional a lo bueno que sea ese individuo, para lo que deberemos implementar una función, denominada fitness, que nos da dicho valor.
Una vez pasada la etapa de selección, se inicia la etapa de reproducción. Podemos elegir que los individuos se procreen 2 a 2 por la mitad, o con un random... escogiendo los genes que conservará el hijo de cada individuo padre y formando la siguiente generación.
Ahora solo nos queda la etapa de mutación. En esta etapa se procede a mutar los genes, según cierta probabilidad, que suele ser muy baja. Una probabilidad alta nos da una convergencia lenta, pero una alta amplia el espacio de búsqueda cuando el algoritmo se ha estancado en una solución debido a que hemos alcanzado un máximo local.
Este proceso se repite durante un número de iteraciones definido por el usuario.
Una vez implementado el algoritmo, se trata de jugar con los parámetros probabilidad de selección, probabilidad de mutación, numero de individuos y número de iteraciones.

Colonia de hormigas:

En la naturaleza, las hormigas encuentran el camino óptimo desde el alimento hasta el hormiguero ayudandose de una sustancia denominada feromona que es depositada por las hormigas y se evapora con el tiempo. A mayor cantidad de feromona mejor es el camino. Cada hormiga escogerá los caminos de mejor feromona. Así, inicialmente se mueven de forma aleatoria hasta encontrar el alimento. Es en la vuelta al hormiguero cuando depositan el rastro de feromona para que otras hormigas lo sigan.
En esto es básicamente en lo que se basa este algoritmo.
Las hormigas son agentes computacionales, que colaboran entre sí para encontrar la solución óptima, almacenando en cada paso cómo de bueno es el camino escogido.
Existen varios tipos de algoritmos que implementan este comportamiento, pero solo me voy a centrar en explicar a nivel general en qué consiste la idea.
Cada agente puede explorar el espacio de estados o explotar la feromona, según un valor probabilístico.
Explorar el espacio de estados significará que avanzará al siguiente estado vecino, sin importarle la distancia ni la feromona.
Al explotar la feromona el agente eligirá el siguiente estado en función de una probabilidad dada por la distancia al siguiente estado y por la feromona que hay en ese camino. Esta feromona como ya he comentado se decrementa con el tiempo.
A la vuelta del recorrido el agente actualiza los niveles de feromona, indicando como de bueno ha sido el recorrido.

Lo curioso de estos algoritmos es lo bien que funcionan basándose simplemente en parámetros de probabilidad, en el que escoger el siguiente estado es "pseudoaleatorio" en cierto modo.