Tesis MaxMinMicrofluidos

Enrutamiento de microfluídos utilizando Max-Min Ant System
[Stützle 2000]
1. Objetivos
1. Minimizar el tamaño de la ruta de cada gota
2. Minimizar el número de adyacencias entre gotas
3. Minimizar eltiempo global de enrutamiento, o sea el tiempo de llegada de la última gota.
Vector de funciones objetivo:
⃗f (⃗x )=[f 1 (⃗x ), f 2 (⃗x ) , f 3 ( ⃗x )]
Funciones de evaluación según objetivos:
1.Tamaño de rutas:
n

⃗f (⃗x )=∑ c i

Si, ci ≠ ci-1

i=1

2. Número de Adyacencias entre gotas:
n−1

⃗f (⃗x )=

∑

a( x , y )ij

i=1, j=i+1

Si,

∣x ti−x tj> 1∣

o

∣ y ti − y tj >1∣

∣x ti +1−x tj >1∣

o∣x ti−x tj+1 >1∣

∣ y ti +1− y tj> 1∣

o

∣ y ti − y tj+1> 1∣

y,

3. Tiempo Global:
n

⃗f (⃗x )=∑ c i
i=1

2. Actualización de Feromonas:
Cada gota (subcolonia) posee una tabla de feromonas y unatabla de visibilidad por cada
gota/objetivo. La actualización y evaporación de feromonas se realiza según la siguiente fórmula:
k

k

best

τi , j=(1−ρ)τ i , j+ρ . Δ τ

Donde,
ρ=coeficiente deevaporación y,

(1)

1

Δ τ best =

b

considerando los b objetivos [Pinto 2005]

∑ f l (⃗x )

best

l=1

La actualización se realiza solo por la mejor hormiga donde f (⃗x )best denota el costo de la
solución,tanto de la mejor iteración (s ib ) o de la mejor iteración global (s gb ) . La mejor
estrategia parece ser el uso de una estrategia de mezcla dinámica la cual incrementa el uso de
(s gb ) para laactualización de feromonas durante la búsqueda. [Stützle 2000]
2.1. Limites de feromonas:
τ min⩽ τi , j (t)⩽ τmax
donde,
τ max (1)= Δ τ utilizando (s gb ) para la actualización de
1−ρ
con,

τ max (o) =un valor máximo arbitrario

τ min=

Δτ
con m = cantidad de hormigas
2.m.(1−ρ)

y,

2.1. Suavizamiento de feromonas:
τi , j= τi , j +fs (τmax −τ i , j)
con,

0⩽fs⩽1

3. Selección del siguiente estadoβ
[ τ ki , j]α .[η1,k
i, j ]
p =
∑ [ τ kx , j ]α .[ η1,x ,kj]β
k ,t
i, j

x∈ j

o,
2,k β
[ τ ki , j ] α .[η1,k
i , j . ηi , j ]
p =
∑ [ τ kx , j ]α .[η1,x ,kj . η2,i , kj ]β
k ,t
i, j

x∈ j

donde,...