Actividad 2 - Equipo 1 - Biokterii

Biokterii

Inteligencia Computacional
Grupo 1
Alejandro Morales A01161376
Jonathan Valle A01161110
Rafael Santos A01161734
18 de febrero de 2010
Equipo 1 : ./42
Actividad 1

Descripción del medio ambiente

El medio ambiente dentro del que se desarrolla Biokterii es el interior de un ser vivo, donde el virus maligno debe infectar la mayoría de células posibles antes de morir, para lo cual debe optimizar su recorrido, sin embargo el virus no se encuentra solo, pues en su recorrido encontrará lugares donde puede recuperar su energía.

Descripción breve del problema de optimización

Este problema es muy similar al problema del viajero, pues se debe cubrir una ruta recorriendo la menor cantidad posible de distancia. Pero a diferencia del problema del viajero tradicional, nuestro virus cuenta con una vida limitada y cuenta con "estaciones de recarga" que le permiten completar su recorrido a través del ser vivo.


Solución con recocido simulado

Configuración

El primer ejemplo de configuración es el siguiente:

Como podemos observar en la ilustracion anterior la ruta se encuentra completamente al azar y es muy poco óptima, existen crueces y las estación de recarga se encuentra en el final.

En la imagen anterior podemos observar la ruta que encontró el algoritmo, al poner las células en esta disposición es fácil de observar como es que el algoritmo funciona y como en este caso arrojó una solución, que al menos a simple vista, es bastante óptima y mucho mejor que la configuración que se tenía anteriormente.

El segundo ejemplo de configuración es un poco más interesante:

Como podemos observar, la ruta que ha construido para esta configuración es bastante óptima, pues incluso considera el utilizar la estación de recarga a medio recodido, en vez de desperdiciarlo utilizandolo al principio, es importante mencionar que el virus tiene una salud máxima, por lo que utilizar la estación al principio del recorrido no es una decisión muy inteligente u óptima.

Por último tenemos este tercer ejemplo:

Aquí podemos observar una vez más una configuración y un camino óptimos.

Reordenamientos
En cada reordenamiento se intercambia aleatoriamente una célula o estación de recarga con otra elegida también aleatoriamente.


Función objetivo
EL objetivo es minimizar el daño que recibe el virus al pasar por las diferentes células y estaciones de recarga. Además se ponderan algunos casos especiales para alterar un poco la forma en la que toma en cuenta cada estación de recarga.

Si la configuración tiene una estación de recarga al inicio, se penaliza con 1000 puntos (pues estaría desperdiciando dicha estación). Si no, entonces se acumulan las distancias entre cada célula de la lista en una variable.

Si el siguiente elemento a analizar de la lista es una estación de recarga, entonces se resta el daño que recuperaría de dicha estación de la variable donde se están acumulando las distancias y se penaliza ligeramente si no aprovecha en su totalidad la estación (si la utiliza con la vida llena).

Finalmente, se revisa si el virus moriría en algún punto del recorrido al restarle a su vida las distancias recorridas. Si el virus muere, se penaliza con 10,000 puntos.

Calendario de recocido
La temperatura inicial es de 1000.

El control de la temperatura se divide uniformemente entre la temperatura inicial y la cantidad de iteraciones que se generan. Por lo anterior, la temperatura se reduce en cada iteración una pequeña cantidad.

El recocido se detiene cuando la temperatura llega a 0.001.

Conclusiones
En nuestra simulación es posible observar como funciona el algoritmo de recocido simulado, pues las lineas o rutas se van pintando conforme va aceptando configuraciones para poder apreciar las primeras soluciones y como ésta va evolucionando hasta llegar a una solución óptima.

El algoritmo de recocido simulado sí funciona para nuestro proyecto porque lo que se intenta hacer es optimizar el recorrido del virus minimizando el daño que recibe. Como el algoritmo minimiza la función objetivo, se puede llegar a una solución óptima o que se acerca mucho a la óptima.

Video: