Colonia De Hormigas
Páginas: 2 (404 palabras)
Publicado: 27 de mayo de 2012
N = Número de ciudades
Q = Constante de feromona
m = Número de hormigas
di,j = Distancia de la ciudad i a la ciudad j
α= Constante de ponderación
ρ= Constante de evaporación de laferomona
τi,j=
0 para i=j
Q para 1≠j
ηi,j=
0 para i=j
1/di,j para 1≠j
J=1,2,3,4
Q=400; m=12;α=0.09 y ρ=0.13
i=1,2,3,4
ρi,j=
ατi,j+(1-α) ηi,j
∑ ατi,j+(1-α) ηi,jfact
Ck= r *N
i
donde
ri~ u(0,1)
5.1 Considerar la i-ésima hormiga ubicada en la j-ésima ciudad.
5.2 Marcar la j-ésima ciudad como ya visitada.
5.3 Seleccionar laciudad k con la máxima probabilidad (de todos los tramos posibles desde la j-ésima ciudad a otra ciudad). En
caso de no existir ningún arco posible se reubica la i-ésima hormiga al azar y secontinúa en el paso 5.1.1
5.4 Acumular la distancia recorrida por la i-ésima hormiga de la ciudad j a la k (dj,k).
5.5 Marcar la ciudad k como ya visitada.
5.6 Actualizar la posición de lai-ésima hormiga (ahora está en la ciudad k).
5.7 Si la i-ésima hormiga ya visitó las N ciudades, ir al paso 5.8. Si no, hacer j = k e ir al paso 5.1.
5.8 Si ya se consideraron las mhormigas, continuar en el paso 6. Si no, ir al paso 5.1.
0.083
0.083
0.083
0.083
0.083
0.083
0.083
0.083
0.083
1, 2, 3, 4
1, 2 , 3, 4
1, 2, 3, 4
Una vezcalculados los tours de las m hormigas tenemos
una tabla de viajes entre ciudades así:
Ruta
Viajes
Q´
1-2
1
400
1-3
7
2800
1-4
4
1600
2-1
0
0
2-34
1600
2-4
8
3200
3-1
3
1200
Donde: r= al número de hormigas que
recorrieron ese tramo.
Ruta
Viajes
Q´
3-2
7
2800
3-4
0
0
4-1
72800
4-2
4
1600
4-3
1
400
fact
Ir al paso 4 si no ha terminado el algoritmo de acuerdo a la regla de detención.
En caso contrario, se
detiene el algoritmo.
Q = Constante de feromona
m = Número de hormigas
di,j = Distancia de la ciudad i a la ciudad j
α= Constante de ponderación
ρ= Constante de evaporación de laferomona
τi,j=
0 para i=j
Q para 1≠j
ηi,j=
0 para i=j
1/di,j para 1≠j
J=1,2,3,4
Q=400; m=12;α=0.09 y ρ=0.13
i=1,2,3,4
ρi,j=
ατi,j+(1-α) ηi,j
∑ ατi,j+(1-α) ηi,jfact
Ck= r *N
i
donde
ri~ u(0,1)
5.1 Considerar la i-ésima hormiga ubicada en la j-ésima ciudad.
5.2 Marcar la j-ésima ciudad como ya visitada.
5.3 Seleccionar laciudad k con la máxima probabilidad (de todos los tramos posibles desde la j-ésima ciudad a otra ciudad). En
caso de no existir ningún arco posible se reubica la i-ésima hormiga al azar y secontinúa en el paso 5.1.1
5.4 Acumular la distancia recorrida por la i-ésima hormiga de la ciudad j a la k (dj,k).
5.5 Marcar la ciudad k como ya visitada.
5.6 Actualizar la posición de lai-ésima hormiga (ahora está en la ciudad k).
5.7 Si la i-ésima hormiga ya visitó las N ciudades, ir al paso 5.8. Si no, hacer j = k e ir al paso 5.1.
5.8 Si ya se consideraron las mhormigas, continuar en el paso 6. Si no, ir al paso 5.1.
0.083
0.083
0.083
0.083
0.083
0.083
0.083
0.083
0.083
1, 2, 3, 4
1, 2 , 3, 4
1, 2, 3, 4
Una vezcalculados los tours de las m hormigas tenemos
una tabla de viajes entre ciudades así:
Ruta
Viajes
Q´
1-2
1
400
1-3
7
2800
1-4
4
1600
2-1
0
0
2-34
1600
2-4
8
3200
3-1
3
1200
Donde: r= al número de hormigas que
recorrieron ese tramo.
Ruta
Viajes
Q´
3-2
7
2800
3-4
0
0
4-1
72800
4-2
4
1600
4-3
1
400
fact
Ir al paso 4 si no ha terminado el algoritmo de acuerdo a la regla de detención.
En caso contrario, se
detiene el algoritmo.
Leer documento completo
Regístrate para leer el documento completo.