Universidad Aútonoma De
Nuevo León
Facultad de Ingeniería Mecánica y
Eléctrica
Laboratorio
de Programación de Sistemas Adaptativos
Dra. Sara Elena Garza
Practica
#3
Jorge Alberto Sanchez Villanueva 1607211
Carlos Orlando Ramírez Rodriguéz 1460809
Daniel Alejandro Reyna Barrón 1414127
Oscar Daniel Arreguín Puente 1019950
Alfredo Yovany Ángeles Dominguez 1612260
Salón: 4-200
Hora: M5-M6
Introducción:
El problema de viajero consiste en hacer un recorrido a
traves de distintas ciudades, pasando por cada una de ellas una sola ves y terminar
en el lugar de la que se comenzó, por lo cual se debe de escoger la ruta más
corta, el problema del viajero lo podemos encontrar en los mapas digitales
cuando deseamos saber cual es la ruta mas cercana para llegar a un punto, he
aquí que se presentan distintas formas de resolver este problema, una sería por
fuerza bruta la cual sería hacer cada una de las combinaciones posibles que se
nos puedan ocurrir, y la otra sería programar un agente que determine cual
sería el camino más corto.
El problema del viajero es dificil cuando aumenta el numero
de ciudades ya que sería un mayor número de cálculos que se tienen que hacer.
ACO es un algoritmo de colonias de hormigas (Ant Colony
Optimization) y es una técnica que se utiliza para solucionar problemas computacionales
de probalistica que se reduce a determinar los mejores caminos o mejor conocido
como rutas en grafos.
El problema del viajero se puede resolver por el algoritmo de
colonia de hormigas (Ant System) en este algoritmo las hormigas visitan cada
uno de los lugares solo una vez, una ciudad tiene menor posibilidad de ser
elejida si ésta es muy distante(Visibilidad), cuanto mas fuerte es el rastro de
las feromonas de uno de los aristas mayor sera la posibilidad de ser elejido.
Marco Teórico:
El problema del viajero es considerado un problema de
NP-Completo debido a su nivel de complejidad.
EL problema del viajero es recorrer la ruta más cercana de un
número de ciudades pasando por cada una de ella solo una vez.
El mapa del viajero se representa como una estructura de
datos de manera de un grafo que nos permite representar diferentes tipos de
relaciones entre objetos
Se puede decir que para este problema la instancia sería un
grafo donde las ciudades tomarían el lugar de los vertices al igual que
determinarán el tamaño de la matriz y los caminos serían las aristas las cuales
tienen cierto coste.
A continuación se presenta el problema del viajero:
Este es un ejemplo mostrado en clase
Esta tabla de
excel seria un ejemplo de lo que sería resolver el problema del
viajero por
fuerza bruta
Y esta lista está un poco corta no se alcanza apreciar toda,
y para que no hubiera repeticiones se incluyó un poco de programación solo para
confirmar las distintas posibilidades.
String[] elementos =
texto.split(",");
int n =
6; //Tipos
para escoger
int r =
elementos.length; //Elementos elegidos
Perm2(elementos,
"", n, r);
}
private static void Perm2(String[] elem, String act, int n, int r) {
if (n == 0) {
System.out.println(act);
} else {
for (int i = 0; i < r; i++) {
if
(!act.contains(elem[i])) { // Controla que no haya
repeticiones
Perm2(elem,
act + elem[i] + ",
", n - 1, r);
}
}
}
}
Por lo que se
alcanza a ver en la imagen es demasiada larga la lista de datos y sería demasiado
tardado hacer un ejemplo de fuerza bruta para 6 ciudades, ahora imaginate para
20, 30 o hasta 100…
ACO (Ant Colony Optimization)es un algoritmo
de la colonia de las hormigas, es una técnica de probabilidad donde una hormiga
vaga aleatoriamente en busca de comida, pero cuando la encuentra deja un rasto
de feromona y si otras hormigas encuentran dicho rastro es probable que ya no
anden por ahí vagando y puede que éstas sigan el rastro de feromonas.
Este algoritmo
fue inicialmente propuesto por Marco Dorigo en 1992 en su tesis de doctorado.
Desarrollo:
La manera en como se resuelve el Problema del Viajero
utilizando ACO es en el cual las hormigas encuentran el camino mas corto entre
dos puntos, en este caso serían dos ciudades, tambien hay que considerar que el
punto inicial es tambien el punto final del recorrido, de esta manera las
hormigas deben recorrer todas las ciudades seleccionadas sin pasar dos veces
por un mismo punto.
A continuación se muestra fragmentos de código del ACO:
·
Inicialización del Algoritmo
Console.WriteLine("\n¡¡Bienvenido al Simulador ACO!!\n");
int numCds = 10;
int numHorm = 5;
int maxTime = 1000;
Console.WriteLine("Numero de Ciudades en el Emulador = " +
numCds);
Console.WriteLine("\nNumero de Hormigas = " + numHorm);
Console.WriteLine("Tiempo máximo = " + maxTime);
Console.WriteLine("\nAlpha (feromona) = " + alpha);
Console.WriteLine("Beta (la influencia del nodo) = " +
beta);
Console.WriteLine("Rho (coeficiente de evaporacion de la feromona) =
" + rho.ToString("F2"));
Console.WriteLine("Q (feromona depositada) = " +
Q.ToString("F2"));
Console.WriteLine("\nSe inicia el calculo de la distancia entre
ciudades");
int[][] dists =
Calc_Dista(numCds);
Console.WriteLine("\nIniciando el camino aleatorio a tomar por las
hormigas\n");
int[][] horm =
Alea_Horm(numHorm, numCds);
Selección de probabilidades por una
arista
·
static int[][] Alea_Horm(int
numHorm, int numCds)
{
int[][] horm = new int[numHorm][];
for (int k = 0; k
< numHorm; ++k)
{
int start = random.Next(0, numCds);
horm[k] =
Camin_Aleat(start, numCds);
}
return horm;
}
static
int[] Camin_Aleat(int
inicio, int numCds)
{
int[] trail = new int[numCds];
for (int i = 0; i
< numCds; ++i) { trail[i] = i; }
for (int i = 0; i
< numCds; ++i)
{
int r = random.Next(i, numCds);
int tmp =
trail[r]; trail[r] = trail[i]; trail[i] = tmp;
}
int idx = IndexOfTarget(trail, inicio);
int temp = trail[0];
trail[0] = trail[idx];
trail[idx] = temp;
return trail;
·
La actualización de las feromonas
static double[][] InicFeromonas(int
numCds)
{
double[][] ferom = new
double[numCds][];
for (int i = 0; i
< numCds; ++i)
ferom[i] = new double[numCds];
for (int i = 0; i
< ferom.Length; ++i)
for (int j = 0; j
< ferom[i].Length; ++j)
ferom[i][j] =
0.01;
return ferom;
}
INSTANCIAS
Con 10
ciudades la distancia más corta fue 30
PARAMETROS
Parámetros
ACO
|
||||
Hormigas
|
Coeficiente
|
Feromona
|
Feromona
|
Nodo
|
de
evaporación
|
depositada
|
α
|
ß
|
|
4
|
0.01
|
2
|
3
|
2
|
10
|
0.01
|
3
|
6
|
4
|
Resultados
Basandonos
en toda la teoría expuesta y en los experimentos realizados mediante el código,
concluimos que la calidad de la solución depende en gran manera del número de
hormigas que participan.
Una
gran ventaja de ACO sobre otros métodos es que se puede llegar a un resultado
relativamente aceptable realizando pocas iteraciones, por lo tanto encuentra
resultados más rapido.
Es un
método que se puede utilizar en problemas que requieren soluciones prácticas y
rápidas
Bibliografia
Fuentes-Penna
Alejandro and González-Ramírez Marcos S. (2013). Meta-Heuristic
Algorithm based on Ant Colony Optimization Algorithm and Project Scheduling
Problem (PSP) for the Traveling Salesman Problem. Journal of Network and
Innovative Computing ISSN 2160-2174 Volume 1 (2013) pp. XXX-XXX © MIR Labs, www.mirlabs.net/jnic/index.html.
MATLAB. (2007, May 21). Solving tsp
with ant colony system. Retrieved
October 12, 2009, from The MathWorks:
http://www.mathworks.com/matlabcentral/fileexchange/15049
No hay comentarios:
Publicar un comentario