Busqueda Tabu

APÉNDICE A

EJEMPLO DE BÚSQUEDA TABÚ

A.1 Introducción
En este apéndice se presenta un ejemplo de búsqueda tabú tomado de la siguiente
referencia electrónicahttp://www.udlap.mx/~leolopez/TabuSearch.htm desarrollado por
Leovigildo López García.

A.2 Ejemplo
Minimizar C(x)=20 x1 + 25 x2 - 30 x3 - 45 x4 + 40 x5
s.a.

x1 + x2 - x3 + x4 + x5 >= 1
x1 + x2
- x4 +2x5 >= 2
- x2
+ x4 +x5

C(x)= 85

m3(x0) : x3 = 1

x = (1,0,1,0,1)

=>

C(x)= 30 *

m4(x0) : x4 = 1

x = (1,0,0,1,1)

=>

C(x)= 15 +100=115

m5(x0) : x5 = 0

x = (1,0,0,0,0)

=>

C(x)= 20 + 70=90

Paso 3: Mejor vecino x´

(1, 0, 1, 0, 1), C(x´) = 30

Paso 4: x´ no es tabú
Paso 5: Solución actual: x1= (1, 0, 1, 0, 1), C(x1) = 30
Lista tabú = (1, 0, 0, 0, 1), C=60
Movimientos tabú:x3 = 0, C=60
Mejor solución: x' = (1,0,1,0,1), C(x') = 30
Paso 6: Aún no se cumple el criterio de paro.
Iteración 2:
Paso 2: Vecindario
Movimientos

Vecindad

m1(x1) : x1 = 0

x =(0,0,1,0,1)

=>

C(x)= 10 + 70 = 80 *

m2(x1) : x2 = 1

x = (1,1,1,0,1)

=>

C(x)= 35 + 100=135

m3(x1) : x3 = 0 T

x = (1,0,0,0,1)

=>

C(x)= 60

m4(x1) : x4 = 1

x = (1,0,1,1,1)

=>C(x)= -15 +100= 85

m5(x1) : x5 = 0

x = (1,0,1,0,0)

=>

C(x)= -30 +140 =110

Paso 3: Mejor Vecino

x´ = (1, 0, 0, 0, 1), C(x´) = 60

Paso 4: Es tabú y no cumple el criterio deaspiración
Siguiente mejor vecino

x´ = (0, 0, 1, 0, 1), C(x´) = 80

T

No es tabú
Paso 5: Solución actual

x´ = (0, 0, 1, 0, 1)

Solución actual: x2= (0,0,1,0,1), C(x2) = 80
Lista tabú =(1,0,0,0,1), C=60
(1,0,1,0,1), C=30
Movimientos Tabú: x3= 0, C=60
x1= 1, C=30
Mejor solución: x' = (1,0,1,0,1), C(x')=30
Paso 6: No se cumple el criterio de paro.
Iteración 3:
Paso 2:
MovimientosVecindad

m1(x2) : x1 = 0 T

x = (1,0,1,0,1)

=>

C(x)= 30

m2(x2) : x2 = 1

x = (0,1,1,0,1)

=>

C(x)= 35 + 100=135

m3(x2) : x3 = 0 T

x = (0,0,0,0,1)

=>

C(x)= 40...