Algoritmos Genéticos: parte 1
No es un tema desconocido que a la humanidad, desde sus inicios, le ha fascinado el tema del origen, nuestro origen. Desde modelos teocentristas hasta elucubradas teorías sobre alienígenas y virus espaciales. Lo cierto es que estamos vivos y seguiremos cambiando, afectados por nuestro entorno, nuestro mundo y nuestras experiencias.
Esto es lo que conocemos como evolución y es un tema realmente apasionante desde el punto de la vista de la Biología y la teoría de la vida en sí misma, tan apasionante es, que desde mediados de los 70 su campo ha traspasado la barrera de lo natural y ha llegado al mundo de los complejos algoritmos y sistemas informáticos, donde ha crecido, madurado y, por sobre todo, ha desvelado misterios incluso para el hombre.
En este artículo quiero hablarles del apasionante mundo de los Algoritmos Genéticos y su aplicación práctica en varios problemas, relacionados mayoritariamente con optimización.
Cómo la naturaleza está en todo (bueno en casi todo)
Como explicaba en la introducción, la evolución y la teoría evolutiva es un campo que puede unir o dividir a la humanidad, pero si algo ha demostrado ser cierto, es que todos los miembros del ecosistema, para bien o para mal, nos encontramos en un continuo cambio, una continua “mejora”, que se le atribuye primordialmente a la evolución y a la denominada selección natural.
Son ambos conceptos que han logrado traspasar la barrera del mundo natural al mundo tecnológico, en especial con problemas de optimización. Los problemas de optimización son una serie de problemas matemáticos o lógicos, que tienen más de una solución posible y el problema radica en encontrar la mejor solución, o la respuesta mas optima, lo que entrega un nivel de complejidad al problema.
Tomemos como ejemplo el archi famoso problema del TSP, (Travel Salesman Problem), o problema del vendedor viajero:
El problema consiste en que un vendedor va a visitar muchas ciudades para ofrecer sus productos y debe encontrar el mejor circuito para llevar a cabo dicha tarea, la principal restricción es que la ciudad debe ser visitada una sola vez.
Si se analiza la premisa, el problema en realidad es encontrar la ruta más óptima para visitar todas las ciudades una sola vez recorriendo la menor cantidad de Kms. Entre ciudades, en resumen, hay que optimizar el tiempo y los recursos.
Si consideramos que muchas ciudades se puede generalizar con n
Sea dͥij la distancia de la ciudad i a la ciudad j, donde dij= ∞ el modelo del agente o vendedor viajero corresponde a:
El conjunto de restricciones (1) y (2) definen un modelo de asignación tradicional. Lamentablemente en general, el problema de asignación producirá soluciones de subcircuito más que circuitos completos que abarque las n ciudades.
Entendiendo esto ya comprendemos que la solución es bastante compleja y requiere revisar muchas casos y no todos los casos nos permitirán llegar a resultados óptimos. También es correcto decir que este problema ya tiene algoritmos que implementan cadenas de decisión como el Diskjtra que es un algoritmo altamente aceptado para resolver este problema.
Algoritmos Genéticos
Un algoritmo genético, como bien dice, toma los conceptos de la genética y la evolución natural para fundamentarse.
Para entenderlo rápidamente hagamos un pequeño juego:
Estoy pensando en una palabra de 3 letras, por cada palabra que me digas que tenga una letra de mi palabra te diré que es correcto al menos en una letra.
Palabra secreta: Dia
- Tia
- Dar
- Tia = 2
- Dar = 2
Para la tercera generación
Tir + Daa = Tia
Daa + Tir = Dar
Y para la cuarta generación:
Dar + Tía = Dia
Para explicar brevemente lo que ocurre es básicamente una mutación, una evolución en el tiempo.
¿Interesante, no? Los Algoritmos Genéticos son algo que no se aprende en un día, por lo que en el siguiente post utilizaremos un algoritmo regular para resolver el problema del viajero y un algoritmo genético.
Además analizaremos y compararemos sus resultados y ahondaremos más en este fascinante mundo.
