Tema elegido: Optimización mediante Ant Colony
Optimization (ACO)
¿Qué es?
Es una meta heurística que se basa en aplicar la metáfora
del comportamiento en las colonias de hormigas reales para encontrar los
caminos más cortos entre las fuentes de comida y el hormiguero.
Mientras las hormigas se mueven entre el hormiguero y la
fuente de comida, las hormigas van depositando feromonas (sustancia que puede
“olerse”). Entre más restos de feromona se encuentren en el camino, las
hormigas tienden a seguir ese camino más seguido. Las feromonas se van
evaporando al pasar el tiempo, si una hormiga deja de pasar por determinado
camino, el olor a feromona desaparecerá y si no encuentran algún rastro de
feromonas, las hormigas ya no seguirán pasando por el mismo lugar. Cabe aclarar
que las hormigas se mueven de forma aleatoria.
Esta técnica es usada para la resolución de problemas
complejosde optimización
combinatoriay búsqueda.
Objetivo
Desarrollar un algoritmo basado en ACO para la resolución
del problema del viajero.
Justificación
Elegimos este método por que nos pareció una manera muy interesante
para optimizar un resultado (en este caso, el del problema del viajero).
Desarrollo
Tenemos 8 ciudades a las que queremos visitar, las
ciudades con sus costos y distancias son:
Ciudad
Costo
Distancia
1
40
60
2
15
25
3
30
50
4
10
20
5
90
110
6
140
170
7
110
95
8
75
130
Para
determinar cual será la probabilidad de que las hormigas pasen mas por cierto
camino según la cantidad de feromona es, es:
Donde:
Pkij (t) es la probabilidad con la
que, en una iteración t del algoritmo, la hormiga k, situada actualmente en la
ciudad i, elige a la ciudad j como próxima parada. Nki es el
conjunto de ciudades no visitadas todavía por la hormiga k. tij (t) es la cantidad de
feromona acumulada sobre el arco (i, j) de la red en la iteración tij
es la información heurística para la que, en el caso del TSP, se utiliza la
inversa de la distancia existente entre las ciudadesi y j alfa y beta son dos parámetros del
algoritmo, los cuales hay que ajustar.
También
necesitamos una formula que nos diga el tiempo de actualización de la feromona,
la cual es:
tij = (1- P) tij
Donde P es la constante de evaporación. Para
este problema usamos una constante de evaporación de 0.1.
Código
Realizamos el programa en
lenguaje JAVA usando el compilador ECLIPSE, para este problema usamos 3 clases:
*ACO.java: Clase principal del programa, es
donde se desarrolla el mismo:
*Datos.java: Donde tenemos las constantes a
utilizar en el problema
Dentro
de la clase ACO tenemos la función calcularprob() donde aplicamos la formula de
probabilidad donde las hormigas eligen el camino según el rastro de feromona.
También
tenemos la función actualizarferomona(), la cual como su nombre lo dice,
actualiza las feromonas, usando la formula mencionada anteriormente.
Realizamos con éxito la practica, vemos como funciona
correctamente la implementación de las formulas en el programa, solo tenemos
que arreglar la manera en que se muestran los resultados (los enumera del 0 al
7).
Conclusiones
Es
obvio que podemos mejorar el programa, por ejemplo, dar una opción para que el
usuario pueda ingresar los valores de los costos, distancia entre las ciudades
o cantidad de ciudades a recorrer
Aprendimos
mucho en esta práctica sobre ACO y vimos esta manera de optimizar de forma más
entendible.
En esta práctica programaremos un sistema adaptativo, el programa consiste en un cruce de calles y tenemos que controlar el tráfico de cada calle con su respectivo semáforo, brindándole prioridad a las calles más congestionadas. No solo se tiene que tomar en cuenta el tráfico de la calle, si no también tenemos que prevenir que los semáforos de calles contrarias se enciendan al mismo tiempo para evitar un choque. Como sabemos, el trafico en las calles pueden variar dependiendo de la hora del dia, por lo que tambien consideramos la hora del dia como otro factor para la afluencia de trafico.
Entonces, el objetivo de esta practica es implementar un sistema que se adapte a la necesidad de ese cruce de calles, que se minimicen las congestiones y sea un sistema funcional, adaptable y con el menor número de fallos, adaptandose tambien a la hora del dia en que se encuentre.
Para esto usaremos el lenguaje de programación Java con el compilador Eclipse.
Desarrollo
Se decidió trabajar con las
calles en pares. Solo un par de calles podrá estar en verde al mismo tiempo
mientras que el otro par estará en luz roja evitando así cualquier colisión.
Estos pares son las calles:
•A y B
•C y D
Los tiempos de los intervalos de
los semáforos se modificarán cada vez que un, comprobando también
cuantos autos se encuentran ahora en los pares de calles. Esto para saber si se
modificará de nuevo los tiempos o seguirán igual.
La clasificación que se le da a
una calle está en función del número de autos que tenga detrás de su semáforo
correspondiente.
Con la utilización de hilos de
tiempo controlamos los cambios de luces de los semáforos y la entrada de nuevos
autos a cada calle.
Usando una matriz de conflictos y un grafo de conflictos podemos ver el total de
combinaciones que es posible hacer, para que no existan problemas a la hora de
encender los semáforos.
Matriz de conflictos
Grafo de conflictos
Diseño de la solucion
Empezamos generando de forma aleatoria el trafico inicial de cada calle. Usaremos dos variables booleanas, para determinar que semaforos encender (los de las calles A y B o los de las calles C y D). Pasamos a obtener la hora del dia con la funcion Calendar.HOUR_OF_DAY (ubicada en la clase java.util.Calendar).
Con una estructura de decision if, el programa decidira que cantidad de trafico habrá para cada calle dependiendo de la hora del dia.
Cabe mencionar que por ahora, el programa solo funciona de 3 a 9 de la noche, pero lo podemos modificar para que funcione las 24 horas del dia.
Usando un hilo de tiempo, haremos transcurrir el tiempo de encendido del semáforo en cada par de calles.
Los tiempos de encendido de los semáforos dependen del trafico y de la hora del dia:
-De 3 a 5 de la tarde, se dan 5 segundos a las calles con poca afluencia y 8 segundos a las calles con mucha afluencia.
-De 6 a 9 de la noche, se dan 8 segundos a las calles con poca afluencia y 14 segundos a las calles con mucha afluencia.
El trafico se va reduciendo o aumentando segun la hora del dia:
-De 3 a 5 de la tarde, se aumenta/reduce 1 vehiculo cada segundo para las calles A y B cuando los semaforos de estas calles se encuentran encendidas/apagadas, se aumenta/reduce 1 vehiculo para las calles C y D cuando su respectivo semaforo se encuentra encendido.
-De 6 a 9 de la noche, se reducen 2 vehiculos cada segundo para
las calles A y B (tenian prisa los automovilistas :P) y se aumenta 1 vehiculo para las calles C y D cuando el semaforo AB se encuentra encendido, se reducen 2 vehiculos en las calles C y D y se aumenta 1 vehiculo para las calles A y B cuando el semaforo CD se encuentra encendidos.
Si el trafico de una calle llega a 0 se volvera a generar un trafico de 1 a 4 o 7 vehiculos, dependiendo de las horas del dia.
Podemos ver una cómo funciona una parte del código aqui:
if(hora == 15 || hora == 16 || hora == 17) { //Dependiendo del valor de la variable hora, habra mucho o poco trafico en las calles
//Semaforos A y B
if(AB == true){
System.out.print("\n== Se encienden los semaforos A y B == \n");
System.out.print("== Se apagan los semaforos C y D == \n");
trAB = A+B; //Suma los traficos de las calles A y B
trCD = C+D; //Suma los traficos de las calles C y D
Random tr2 = new Random(); //Nuevo random
if(trAB > trCD){ //Si el trafico de las calles A y B mayores que C y D, se da un tiempo de 8 segundos para que pasen los autos
try{
for(n=1;n<9;n++){
A= A-1; //Se elimina un auto cada segundo
B= B-1;
if (A <= 0){ //Si el numero de autos en la calle A es menor o igual a 0, se genera un nuevo numero de trafico de manera aleatoria
A = 1 + (tr2.nextInt(3));
}
if(B <= 0){
B = 1 + (tr2.nextInt(3));
}
C= C+1;//Se suma un nuevo carro a la calle C
D= D+1;
Thread.sleep(1000);
System.out.print(", "+n); //Imprime los segundos
}
}//Fin del try
catch (InterruptedException e) {
System.out.println(e.getMessage());
}
System.out.print("\nTrafico en la calle A = "+A+"\n");
System.out.print("Trafico en la calle B = "+B+"\n");
System.out.print("Trafico en la calle C = "+C+"\n");
System.out.print("Trafico en la calle D = "+D+"\n");
}
if(trAB < trCD){//Si el trafico de las calles A y B menores que C y D, se da un tiempo de 5 segundos para que pasen los autos
try{
for(n=1;n<6;n++){
A= A-1;
B= B-1;
if (A <= 0){
A = 1 + (tr2.nextInt(3));
}//Fin del if
if(B <= 0){
B = 1 + (tr2.nextInt(3));
}//Fin del if
C= C+1;
D= D+1;
Thread.sleep(1000);
System.out.print(", "+n);
}//Fin del for
}//Fin del try
catch (InterruptedException e) {
System.out.println(e.getMessage());
}//Fin del catch
System.out.print("\nTrafico en la calle A = "+A+"\n");
System.out.print("Trafico en la calle B = "+B+"\n");
System.out.print("Trafico en la calle C = "+C+"\n");
System.out.print("Trafico en la calle D = "+D+"\n");
}//Fin del if
AB=false; //Se apagan los semaforos A y B
CD=true;//Se encienden los semaforos C y D
hora = cal.get(Calendar.HOUR_OF_DAY); //Se obtiene de nuevo la hora, para asegurar si hay una transicion de horas, por ejemplo de 5 p.m. a 6 p.m.
}//fin del super If
//Semaforos C y D
if(CD == true){
System.out.print("\n== Se encienden los semaforos C y D ==\n");
System.out.print("== Se apagan los semaforos A y B == \n");
trAB = A+B;
trCD = C+D;
Random tr2 = new Random();
if(trCD > trAB){ //Si el trafico de las calles C y D mayores que A y B, se da un tiempo de 8 segundos para que pasen los autos
try{
for(n=1;n<9;n++){
A= A+1;
B= B+1;
C= C-1;
D= D-1;
if (C <= 0){
C = 1 + (tr2.nextInt(3));
}
if(D <= 0){
D = 1 + (tr2.nextInt(3));
}
Thread.sleep(1000);
System.out.print(", "+n);
}
}//Fin del try
catch (InterruptedException e) {
System.out.println(e.getMessage());
}
System.out.print("\nTrafico en la calle A = "+A+"\n");
System.out.print("Trafico en la calle B = "+B+"\n");
System.out.print("Trafico en la calle C = "+C+"\n");
System.out.print("Trafico en la calle D = "+D+"\n");
}
if(trCD < trAB){//Si el trafico de las calles C y D menores que A y B, se da un tiempo de 5 segundos para que pasen los autos
try{
for(n=1;n<6;n++){
A= A+1;
B= B+1;
C= C-1;
D= D-1;
if (C <= 0){
C = 1 + (tr2.nextInt(3));
}//Fin del if
if(D <= 0){
D = 1 + (tr2.nextInt(3));
}//Fin del if
Thread.sleep(1000);
System.out.print(", "+n);
}//Fin del for
}//Fin del try
catch (InterruptedException e) {
System.out.println(e.getMessage());
}//Fin del catch
System.out.print("\nTrafico en la calle A = "+A+"\n");
System.out.print("Trafico en la calle B = "+B+"\n");
System.out.print("Trafico en la calle C = "+C+"\n");
System.out.print("Trafico en la calle D = "+D+"\n");
}//Fin del if
AB=true; //Se encienden los semaforos A y B
CD=false;//Se apagan los semaforos C y D
hora = cal.get(Calendar.HOUR_OF_DAY);
}//fin del super If
}// Fin del if de horas
A continuación un video con la demostración del programa en ejecución:
Conclusiones
Sabemos que podemos mejorar el codigo y la logica, además de agregarle la interfaz grafica para dar una mejor impresión al programa, pero con esta practica hemos comprendido como pueden funcionar el uso de hilos y el autoajuste de parametros.
Referencias
Deitel M., Harvey (2008). Java, Como programar. México: Editorial Prentice Hall.
Sin autor, "http://lineadecodigo.com/java/obtener-la-hora-en-java/" (2007)
Sin autor, "http://equis.umh.es/alex-bia/teaching/PC/material/hilos_tutorial-java/cap10-2.htm" (2006)
