Simplifica tu vida con sistemas complejos y algoritmos genéticos

Parte 2 - Sistemas Complejos

¿Qué es un sistema complejo?

Por el momento, no existe una definición formal exacta de qué es un sistema complejo. Sin embargo, de forma general, se puede aceptar que los sitemas complejos tienen una serie de propiedades que los identifican. De manera resumida, podemos decir que los más característicos son:

Están compuestos por múltiples unidades simples
Estas unidades se relacionan entre sí
Estas relaciones producen comportamientos emergentes que no se deducen fácilmente del análisis de los agentes sencillos por separado.

Ejemplo: una colonia de hormigas, el cerebro, un animal, la biosfera, una célula... También es ralativamente común que las unidades simples de un sistema complejo sean sistemas complejos a su vez.

Una de los aspectos más interesantes de estos sistemas son las citadas propiedades emergentes: Son características, patrones, variables o comportamientos del sistema que no se deducen de manera fácil a partir del estudio de cada agente del sistema. Por ejemplo, la inteligencia no se deduce fácilmente del estudio independiente de cada neurona. La estructura compleja y eficiente de un termitero no se puede calcular sólo analizando qué hace una termita aislada.

¿Por qué son interesantes en ingeniería los sistemas complejos?

Los sistemas complejos pueden ser realmente interesantes en muchos campos de la ingeniería:

Pueden llegar a ser muy robustos: un hormiguero que pierda a 2/3 de sus miembros puede sobrevivir, pero imagina intentar usar un ordenador o un vehículo con 2/3 de sus piezas rotas...
A veces pueden autoregularse a partir de reglas simples.
Algunos son fácilmente escalables: un enjambre de robots colaborando en una tarea, si han sido diseñados con este enfoque en mente, pueden mejorar su rendimiento añadiendo más robots iguales sin necesidad de más cambios.
Pueden usarse para resolver problemas complicados: Problema del viajante, distribución de paquetes en telecomunicaciones, líneas de transporte que se adaptan al tráfico en tiempo real...

Ejemplo : Algoritmo de Colonia de Hormigas (ACO) para el problema del viajante

Imaginemos una distribución de ciudades en un mapa. Somos un vendedor que quiere visitarlas todas, sólo una vez cada una, gastando el menor combustible posible. Este es el conocido Problema del Viajante, que se puede resolver fácilmente con un sistema complejo. Es importante tener en cuenta que aunque este método obtiene resultados muy buenos rápidamente, no necesariamente encontrará siempre la solución óptima.

Este problema clásico es muy conocido, porque bajo su enunciado simple se esconde una enorme complejidad:

Para 10 ciudades hay 181.440 rutas diferentes, pero para 30 ciudades hay más de 4·10^31 rutas posibles. Un ordenador que calcule un millón de rutas por segundo necesitaría 10^18 años para resolverlo. Dicho de otra forma, si se hubiera comenzado a calcular al comienzo de la creación del universo (hace unos 13.400 millones de años) sólo habría calculado el 0,0000001% a día de hoy.

Suena interesante, ¿verdad? ¡Veamos cómo modelarlo y resolverlo con Hormigas!

El algoritmo se basa en varias generaciones sucesivas de hormigas que recorren el mapa viajando de ciudad en ciudad, eligiendo su siguiente ciudad de manera aletoria hasta que las han recorrido todas. En cada etapa del viaje, las hormigas eligen moverse de una ciudad a otra teniendo en cuenta las siguientes reglas:

Debe visitar cada ciudad exactamente una vez, excepto la inicial en la que estará dos veces (salida y llegada final);
Una ciudad distante tiene menor posibilidad de ser elegida (Visibilidad);
Cuanto más intenso es el rastro de feromonas de una arista entre dos ciudades, mayor es la probabilidad de que esa arista sea elegida;
Después de haber completado su recorrido, la hormiga deposita feromonas en todas las aristas visitadas, mayor cantidad cuanto más pequeña es la distancia total recorrida;
Después de cada generación, algunas feromonas son evaporadas.



In [ ]:

    
%matplotlib inline
from Ejercicios.Hormiguero import ants



In [ ]:

    
mapa1 = ants.Mapa()
mapa1.draw_distances()



In [ ]:

    
mapa1.swarm_create(100)
print('generación:', end=' ')
for i in range(100):
    print(i, end='·')
    mapa1.swarm_generation()
mapa1.draw_best_path()

Después, durante la explicación de los ejercicios propuestos, veremos este caso con más detalle.



In [ ]:



In [ ]:

Siro Moreno, Aeropython, 19 de Noviembre de 2015



In [ ]: