# Búsqueda Tabú

La librería **Pyristic** incluye una clase llamada `TabuSearch` que facilita la implementación de una metaheurística basada en Búsqueda Tabú para resolver problemas de minimización. Para poder utilizar esta clase es necesario:

1. Definir:
    * La función objetivo $f$.
    * La lista de restricciones.
    * Estructura de datos (opcional).

2. Crear una clase que herede de `TabuSearch`.


3. Sobreescribir las siguientes funciones de la clase `TabuSearch`:
    * get_neighbors (requerido)
    * encode_change (requerido)

A continuación se muestran las librerías y elementos que se deben importar. Posteriormente, se resolverán dos problemas de optimización combinatoria usando la clase `TabuSearch`.


```python
import sys
import os

#library_path is the path where the Optimpy library is located.
library_path = "/home/dell/Documentos/Git_proejcts/pyristic/"
#library_path = "/Users/adrianamenchacamendez/Documentos/enes_morelia/papime/optimizacion-con-metaheuristicas/"
sys.path.append(os.path.abspath(library_path))
```


```python
from pyristic.heuristic.Tabu_search import TabuSearch
from pyristic.utils.helpers import *
from pprint import pprint
import numpy as np 
import copy 
```

## Problema de la mochila

\begin{equation}
  \label{eq:KP}
  \begin{array}{rll}
  \text{maximizar:} & f(\vec{x}) = \sum_{i=1}^{n} p_i \cdot x_{i} &  \\
  \text{donde: } & g_1(\vec{x}) = \sum_{i=1}^{n} w_i \cdot x_{i}  \leq c &  \\
          &  x_i \in \{0,1\} & i\in\{1,\ldots,n\}\\
  \end{array}
\end{equation}

Consideremos la siguiente entrada:
- $n = 5$
- $p = \{5, 14, 7, 2, 23\}$
- $w = \{2, 3, 7, 5, 10\}$
- $c = 15$

Donde la mejor solución es:
$x = [1, 1, 0, 0, 1]$ , $f(x) = 42$ y $g_{1}(x) = 15$


### Función objetivo

Dado que la clase `TabuSearch` considera problemas de minimización, es necesario convertir el problema de la mochila a un problema de minimización. Para esto se multiplica el valor de la función objetivo por -1.


```python
def f(x : np.ndarray) -> float:
    p = np.array([5,14,7,2,23])
    return -1*np.dot(x,p)
```

### Restricciones

Las restricciones se definen en funciones diferentes y se agregan a una lista. 


```python
def g1(x : np.ndarray) -> bool:
    w = [2,3,7,5,10]
    return np.dot(x,w) <= 15

constraints_list= [g1]
```

En el problema de la mochila unicamente queremos revisar que no se exceda el peso.

### Uso de `TabuSearch`

Para poder hacer uso de la metaheurística de búsqueda tabú implementada en la librería **Pyristic**, es necesario crear una clase que herede de la clase `TabuSearch`.



```python
class Knapsack_solver(TabuSearch):
    
    def __init__(self, f_ : function_type , constraints_: list):
        super().__init__(f_,constraints_)
        
        
    def get_neighbors(self, x : np.ndarray,**kwargs) -> list:   
        neighbors_list = []

        for i in range(len(x)):
            x[i] ^= 1 #1
            neighbors_list+=[copy.deepcopy(x)]
            x[i] ^= 1 
            
        return neighbors_list
        
    def encode_change(self, neighbor : (list,np.ndarray), x : (list,np.ndarray),**kwargs) -> list: #2
        
        x_ = [None,None]
        
        for i in range(len(x)):
            if x[i] != neighbor[i]:
                return [i,neighbor[i]]
            
        return x_
```

La nueva clase es llamada *Knapsack_solver*, donde, se han sobrescrito las funciones `get_neighbors` y `encode_change`. Si no implementamos las funciones mencionadas el algoritmo no va a funcionar.

### Ejecución de la metaheurística 

Una vez definida la clase *Knapsack_solver*, se crea un objeto de tipo *Knapsack_solver* indicando en los parámetros la función objetivo y las restricciones del problema. En este caso llamamos *Knapsack* al objeto creado.


```python
Knapsack = Knapsack_solver(f, [g1])
```

Finalmente, se llama a la función `optimize`. Esta función recibe tres parámetros:

* Solución inicial o función generadora de soluciones iniciales.
* El número de iteraciones.
* El tiempo donde evitaremos hacer un cambio en cierta posición (tiempo tabú).

Para este ejemplo usamos una mochila vacía ($x_0 = [0,0,0,0,0]$), $30$ iteraciones y un tiempo tabú igual a $3$.


```python
init_backpack_solution = np.zeros(5,dtype=int)
'''Parameters:
    Initial solution
    Number of iterations
    Tabu time
'''
Knapsack.optimize(init_backpack_solution,30,3)
print(Knapsack)
```

    100%|████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 30/30 [00:00<00:00, 1586.49it/s]

    Tabu search: 
     f(X) = -42 
     X = [1 1 0 0 1] 
     


    


A continuación resolveremos el mismo problema para una instancia más grande.

Tenemos que definir nuevamente la función objetivo y la restricción para emplearlo para cualquier instancia del problema.

Definiremos las siguientes variables como variables globales:
* n es un número que indicará el tamaño de nuestra instancia.
* p es un arreglo que se refiere al beneficio que proporciona cada uno de los objetos.
* w es un arreglo con el peso de cada uno de los objetos.
* c es el peso máximo que puede tener nuestra mochila.


```python
n = 50
p = [60, 52, 90, 57, 45, 64, 60, 45, 63, 94, 44, 90, 66, 64, 32, 39, 91, 40, 73, 61, 82, 94, 39, 68, 94, 98, 80, 79, 73, 99, 49, 56, 69, 49, 82, 99, 65, 34, 31, 85, 67, 62, 56, 38, 54, 81, 98, 63, 48, 83]
w = [38, 20, 21, 21, 37, 28, 32, 30, 33, 35, 29, 32, 35, 24, 28, 29, 22, 34, 31, 36, 36, 28, 38, 25, 38, 37, 20, 23, 39, 31, 27, 20, 38, 38, 36, 28, 39, 22, 23, 22, 21, 24, 23, 33, 31, 30, 32, 30, 22, 37]
c = 870
```


```python
def f(x : np.ndarray) -> float:
    global p
    return -1* np.dot(x,p)

def g1(x : np.ndarray) -> bool:
    global w,c
    result = np.dot(x,w)
    g1.__doc__="{} <= {}".format(result,c)
    return result <= c

constraints_list= [g1]
```

### Solución inicial

En el ejemplo anterior, la solución inicial fue una mochila vacía. Ahora crearemos una mochila que introduce objetos de manera aleatoria, mientras no se exceda el peso de la mochila.


```python
def getInitialSolution(NumObjects=5):
    global n,p,w,c
    #Empty backpack
    x = [0 for i in range(n)]
    weight_x = 0
    
    #Random order to insert objects.
    objects = list(range(n))
    np.random.shuffle(objects)
    
    for o in  objects[:NumObjects]:
        #Check the constraint about capacity.
        if weight_x + w[o] <= c:
            x[o] = 1
            weight_x += w[o]
            
    return np.array(x)
```

Definiremos nuestro objeto del tipo *Knapsack_solver* y llamaremos el método `optimize`con los siguientes parámetros:

* La función que crea la solución inicial.
* $100$ iteraciones.
* El tiempo tabú será $\frac{n}{2}$.


```python
Knapsack_2 = Knapsack_solver(f, [g1])
Knapsack_2.optimize(getInitialSolution,100,n//2)
print(Knapsack_2)
```

    100%|███████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 100/100 [00:00<00:00, 454.23it/s]

    Tabu search: 
     f(X) = -2309 
     X = [0 0 1 0 0 1 0 0 1 1 0 1 1 1 0 0 1 0 1 0 1 1 0 1 1 1 1 1 1 1 0 0 1 0 1 1 1
     0 0 1 1 1 1 0 0 1 1 0 0 1] 
     Constraints: 
     868 <= 870 
    


    


Para revisar el comportamiento de la metaheurística en determinado problema, la librería **Pyristic** cuenta con una función llamada `get_stats`. Esta función se encuentra en **utils.helpers** y recibe como parámetros:

* El objeto creado para ejecutar la metaheurística.
* El número de veces que se quiere ejecutar la metaheurística.
* Los argumentos que recibe la función `optimize` (debe ser una tupla).

La función `get_stats` retorna un diccionario con algunas estadísticas de las ejecuciones. 


```python
args = (getInitialSolution,500,n//2)
statistics = get_stats(Knapsack_2, 21, args)
```

    100%|███████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 500/500 [00:00<00:00, 913.61it/s]
    100%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 500/500 [00:00<00:00, 1378.92it/s]
    100%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 500/500 [00:00<00:00, 1339.77it/s]
    100%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 500/500 [00:00<00:00, 1345.36it/s]
    100%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 500/500 [00:00<00:00, 1261.83it/s]
    100%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 500/500 [00:00<00:00, 1315.93it/s]
    100%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 500/500 [00:00<00:00, 1378.99it/s]
    100%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 500/500 [00:00<00:00, 1356.77it/s]
    100%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 500/500 [00:00<00:00, 1348.58it/s]
    100%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 500/500 [00:00<00:00, 1255.58it/s]
    100%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 500/500 [00:00<00:00, 1341.23it/s]
    100%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 500/500 [00:00<00:00, 1379.97it/s]
    100%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 500/500 [00:00<00:00, 1380.98it/s]
    100%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 500/500 [00:00<00:00, 1358.95it/s]
    100%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 500/500 [00:00<00:00, 1250.25it/s]
    100%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 500/500 [00:00<00:00, 1340.90it/s]
    100%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 500/500 [00:00<00:00, 1377.66it/s]
    100%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 500/500 [00:00<00:00, 1376.81it/s]
    100%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 500/500 [00:00<00:00, 1363.01it/s]
    100%|███████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 500/500 [00:00<00:00, 910.14it/s]
    100%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 500/500 [00:00<00:00, 1082.86it/s]



```python
pprint(statistics)
```

    {'Best solution': {'f': -2309,
                       'x': array([0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1,
           0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0,
           0, 1, 1, 1, 0, 1])},
     'Mean': -2252.7619047619046,
     'Median': -2254.0,
     'Standard deviation': 38.34418657359848,
     'Worst solution': {'f': -2187,
                        'x': array([0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1,
           0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1,
           0, 1, 1, 0, 0, 1])},
     'averageTime': 0.39534649394807364,
     'objectiveFunction': [-2214,
                           -2279,
                           -2284,
                           -2263,
                           -2305,
                           -2281,
                           -2309,
                           -2187,
                           -2273,
                           -2215,
                           -2222,
                           -2225,
                           -2254,
                           -2302,
                           -2230,
                           -2195,
                           -2307,
                           -2220,
                           -2248,
                           -2211,
                           -2284]}


## Problema del agente viajero


\begin{equation}
    \label{eq:TSP}
    \begin{array}{rll}
    \text{minimizar:} & f(x) = d(x_n, x_1) + \sum_{i=1}^{n-1} d(x_i, x_{i+1}) &  \\
    \text{tal que: } & x_i \in \{1,2,\cdots,n\} & \\
    \end{array}
\end{equation}

Donde:
* $d(x_i,x_j)$ es la distancia desde la ciudad $x_i$ a la ciudad $x_j$.
* $n$ es el número de ciudades.
* $x$ es una permutación de las $n$ ciudades.


```python
import random 
```


```python
num_cities = 10
iterations = 100
dist_matrix = \
[\
[0,49,30,53,72,19,76,87,45,48],\
[49,0,19,38,32,31,75,69,61,25],\
[30,19,0,41,98,56,6,6,45,53],\
[53,38,41,0,52,29,46,90,23,98],\
[72,32,98,52,0,63,90,69,50,82],\
[19,31,56,29,63,0,60,88,41,95],\
[76,75,6,46,90,60,0,61,92,10],\
[87,69,6,90,69,88,61,0,82,73],\
[45,61,45,23,50,41,92,82,0,5],\
[48,25,53,98,82,95,10,73,5,0],\
]

```


```python
def f_salesman(x : np.ndarray) -> float:
    global dist_matrix
    total_dist = 0
    for i in range(1,len(x)):
        u,v = x[i], x[i-1]
        total_dist+= dist_matrix[u][v]
    total_dist += dist_matrix[x[-1]][0]
    return total_dist
```


```python
def g_salesman(x : np.ndarray) -> bool:
    """
    Xi in {1,2, ... , N}
    """
    size = len(x)
    size_ = len(np.unique(x))
    return size == size_
```

En este ejemplo mostraremos la forma de definir nuestra lista tabú para el problema del agente viajero para emplearla en nuestra búsqueda `TabuSearch`. Es necesario que nuestra lista tabú contenga los siguientes métodos:
- `reset`
- `update`
- `push`
- `find` 



```python
class Tabu_Salesman_list:
    def __init__(self,timer):
        self.__TB = {}
        self.timer = timer
    
    def reset(self,timer) -> None:
        self.__TB = {}
        self.timer = timer
        
    def update(self) -> None:
        to_pop = []
        for key in self.__TB:
            if self.__TB[key]-1 == 0:
                to_pop.append(key)
            else:
                self.__TB[key]-=1
        for key in to_pop:
            self.__TB.pop(key)
        
    @checkargs
    #x has [p,v,step], we are only interested in v (value)
    def push(self, x : list ) -> None:
        self.__TB[x[1]] = self.timer
        
    @checkargs
    def find(self, x : list) -> bool:
        return x[1] in self.__TB
        
```


```python
class TravellingSalesman_solver(TabuSearch):

    def __init__(self, f_ : function_type , constraints_: list, TabuStorage):
        super().__init__(f_,constraints_,TabuStorage)
        
    @checkargs
    def get_neighbors(self, x : np.ndarray,**kwargs) -> list: 
        
        neighbors_list = []
        
        ind = random.randint(1,len(x)-1)
        while  self.TL.find([-1,x[ind]]):
            ind = random.randint(1,len(x)-1)
        v = x[ind]
        x_tmp = list(x[v != x])
        for i in range(1, len(x)):
            if ind == i:
                continue
            neighbors_list += [ x_tmp[:i] + [v] + x_tmp[i:]]
            
        return neighbors_list

        
    @checkargs
    def encode_change(self, neighbor : (list,np.ndarray), x : (list,np.ndarray),**kwargs) -> list: #2
        
        x_p ={x[i] : i for i in range(len(x))}
        n_p = {neighbor[i]: i for i in range(len(x))}
        ind = -1
        max_dist = -1
        value = -1
        for i in range(1, len(x)):
            v = x[i]
            dist = abs(x_p[v] - n_p[v])
            if dist > max_dist:
                ind = i
                max_dist = dist
                value = v
       
        return [ind , value]
```

### Solución inicial
En este caso, creamos la solución inicial utilizando una estrategia voraz.


```python
def getInitialSolutionTS(distance_matrix, total_cities):
    Solution = [0]
    remaining_cities  = list(range(1,total_cities))
    
    while len(remaining_cities) != 0:
        from_ =Solution[-1] 
        to_ = remaining_cities[0]
        dist = distance_matrix[from_][to_]
        
        for i in range(1, len(remaining_cities)):
            distance = distance_matrix[from_][remaining_cities[i]]
            if distance < dist:
                to_ = remaining_cities[i]
                dist = distance
        Solution.append(to_)
        ind = remaining_cities.index(to_)
        remaining_cities.pop(ind)
    return Solution
```


```python
TravellingSalesman = TravellingSalesman_solver(f_salesman,[g_salesman],Tabu_Salesman_list(num_cities//2))
init_path = np.array(getInitialSolutionTS(dist_matrix,num_cities))
print("Initialize search with this initial point {} \n f(x) = {}".format(init_path, f_salesman(init_path)))
```

    Initialize search with this initial point [0 5 3 8 9 6 2 7 1 4] 
     f(x) = 271



```python
TravellingSalesman.optimize(init_path, iterations, num_cities//2)
print(TravellingSalesman)
```

    Tabu search: 
     f(X) = 248 
     X = [0 5 3 8 9 6 2 7 4 1] 
     Constraints: 
     
        Xi in {1,2, ... , N}
         
    



```python
args = (init_path, iterations, num_cities//2)
statistics = get_stats(TravellingSalesman, 30, args)

```


```python
pprint(statistics)
```

    {'Best solution': {'f': 248, 'x': array([0, 5, 3, 8, 9, 6, 2, 7, 4, 1])},
     'Mean': 248.0,
     'Median': 248.0,
     'Standard deviation': 0.0,
     'Worst solution': {'f': 248, 'x': array([0, 5, 3, 8, 9, 6, 2, 7, 4, 1])}}


23ef0afde786a2d5ed8d2aa88543c09e0127ae11
ipynb
Jupyter Notebook
examples/SpanishExamples/TabuEjemplo.ipynb
JAOP1/pyristic
ae3c1151640d05e144535c6c95c286c5c6a9a817
MIT
2021-09-20T15:13:07.000Z
2021-09-20T15:13:07.000Z
examples/SpanishExamples/TabuEjemplo.ipynb
JAOP1/pyristic
ae3c1151640d05e144535c6c95c286c5c6a9a817
MIT
examples/SpanishExamples/TabuEjemplo.ipynb
JAOP1/pyristic
ae3c1151640d05e144535c6c95c286c5c6a9a817
MIT
2021-07-13T00:39:17.000Z
2021-07-13T00:39:17.000Z
Qwen/Qwen-72B
1. YES
2. YES