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:

Definir:
- La función objetivo $f$.
- La lista de restricciones.
- Estructura de datos (opcional).
Crear una clase que herede de TabuSearch.

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.

In [1]:

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.

In [2]:

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.

In [3]:

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.

In [5]:

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.

In [6]:

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$.

In [7]:

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)

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.

In [8]:

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

In [9]:

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.

In [10]:

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 optimizecon los siguientes parámetros:

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

In [12]:

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

Tabu search: 
 f(X) = -2207 
 X = [0 0 1 0 0 1 0 0 0 1 0 1 1 0 0 0 1 1 1 0 1 1 0 1 1 1 1 1 1 1 1 0 1 0 1 1 1
 0 0 1 1 0 0 0 1 1 1 0 0 1] 
 Constraints: 
 856 <= 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.

In [13]:

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

In [14]:

pprint(statistics)

{'Best solution': {'f': -2310,
                   'x': array([0, 0, 1, 1, 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, 0, 0,
       0, 1, 1, 0, 0, 1])},
 'Mean': -2261.714285714286,
 'Median': -2270.0,
 'Standard deviation': 37.13186650579367,
 'Worst solution': {'f': -2193,
                    'x': array([0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1,
       1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0,
       0, 1, 1, 0, 0, 1])}}

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.

In [15]:

import random

In [16]:

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],\
]

In [17]:

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

In [18]:

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

In [19]:

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

In [20]:

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.

In [21]:

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

In [22]:

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

In [23]:

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}

In [24]:

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

In [25]:

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])}}

Búsqueda Tabú¶

Problema de la mochila¶

Función objetivo¶

Restricciones¶

Uso de TabuSearch¶

Ejecución de la metaheurística¶

Solución inicial¶

Problema del agente viajero¶

Solución inicial¶

Uso de `TabuSearch`¶