Recocido Simulado¶

La librería Pyristic incluye una clase llamada SimulatedAnnealing que facilita la implementación de la metaheurística basada en Recocido Simulado. Para poder utilizar esta clase, se debe realizar lo siguiente:

1. Definir:
   • La función objetivo $f$.
   • La lista de restricciones.

1. Crear una clase que herede de SimulatedAnnealing.

1. Sobreescribir las siguientes funciones de la clase SimulatedAnnealing:
   • get_neighbor (requerido)
   • update_temperature (opcional)

A continuación se muestran los elementos que se deben importar. Posteriormente, se resolverán dos problemas de optimización combinatoria usando la clase SimulatedAnnealing.

In [1]:

from pyristic.heuristic.SimulatedAnnealing_search import SimulatedAnnealing
from pyristic.utils.helpers import *
from pprint import pprint
import numpy as np 
import copy

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

A continuación vamos a definir una instancia de este problema utilizando 10 ciudades.

In [2]:

import random 
import math

num_cities = 10
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],\
]

Función objetivo¶

In [3]:

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

    return float(total_dist)

Restricciones¶

Las restricciones se definen como una lista de funciones que retornan valores booleanos. Estos valores permitirán verificar si una solución es factible o no.

En el caso del problema del agente viajero queremos comprobar que estamos visitando todas las ciudades exactamente una vez.

In [4]:

def g_salesman(x : np.ndarray) -> bool:

    size = len(x)
    size_ = len(np.unique(x))
    return size == size_

constraints_list= [g_salesman]

Solución inicial¶

La estrategia utilizada para generar la solución inicial es la siguiente:

1. Introducir la ciudad $1$ en la primera posición de nuestra permutación y crear un arreglo con las ciudades restantes.

2. Seleccionar la ciudad más cercana desde nuestra ubicación actual.

3. Retirar del arreglo la ciudad seleccionada y asignar la como nuestra ubicación actual; Posterior, repetir el punto 2.

In [5]:

def getInitialSolutionTS(distance_matrix, total_cities) -> np.ndarray:
    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 np.array(Solution)

In [6]:

Path = getInitialSolutionTS(dist_matrix,num_cities)
print(Path)

[0 5 3 8 9 6 2 7 1 4]

Declaración de SimulatedAnnealing¶

Para implementar una metaheurística basada en recocido simulado, utilizando la librería Pyristic, es necesario crear una clase que herede de la clase SimulatedAnnealing. En este ejemplo, la nueva clase es llamada TravellingSalesman_solver.

La nueva clase debe sobreescribir la función get_neighbor, de lo contrario el algoritmo no va a funcionar.

In [8]:

class TravellingSalesman_solver(SimulatedAnnealing):

    def __init__(self, f_ : function_type , constraints_: list):
        super().__init__(f_,constraints_)

    def get_neighbor(self, x : np.ndarray) -> np.ndarray: 
        
        x_ = x.copy()
        N = len(x_)
        index1 = random.randint(1, N-1)
        index2 = random.randint(1, N-1)
    
        while index2 == index1:
            index2 = random.randint(1, N-1)
    
        v = x[index1]
        x_ = list(x_[v != x_])
        x_ = x_[:index2] + [v] + x_[index2:]
        return np.array(x_)

La función get_neigbor debe regresar una solución vecina de la solución actual, es decir, una variación de la solución actual. Para nuestro ejemplo, una solución vecina de la solución $x$, la vamos a definir como sigue:

Se seleccionan dos indices distintos de manera aleatoria llamados $i$ y $j$, donde, tomaremos el elemento $x_i$ y desplazaremos las otras posiciones de la solución $x$ de modo que $x_i$ se encuentre en la posición $j$ y esta nueva solución será retornada.

Ejecución de la metaheurística¶

Una vez definida la clase TravellingSalesman_solver, se crea una instancia indicando en los parámetros la función objetivo y las restricciones del problema. En este caso llamamos TravellingSalesman a la instancia creada.

In [9]:

TravellingSalesman =\
TravellingSalesman_solver( f_salesman, constraints_list)

Finalmente, se llama la función optimize (esta función es la misma para todas las clases en la librería). La función optimize recibe tres parámetros:

• Solución inicial o función generadora de soluciones iniciales.
• La temperatura inicial.
• La temperatura final.

Vamos a utilizar los siguientes parámetros:

• Emplearemos la solución obtenida por la función getInitialSolutionTS.
• $1000$ de temperatura inicial.
• $0.1$ de temperatura final.

In [10]:

TravellingSalesman.optimize(Path, 1000.0 , 0.1)
print(TravellingSalesman)

Simulated Annealing: 
 f(X) = 271.0 
 X = [0 5 3 8 9 6 2 7 1 4] 
 

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 deben estar contenidos en una tupla.

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

In [11]:

#Ejecutamos get_stats 30 veces.
args = (Path, 1000.0, 0.01)
statistics = get_stats(TravellingSalesman, 30, args)

In [12]:

pprint(statistics)

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

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}

Para este problema vamos a crear una instancia de $1000$ objetos, donde, cada objeto estará definido:

• $p_{i} \in [50,100]$
• $w_{i} \in [5,100]$
• $C = 9786$

In [13]:

n = 1000
p = np.random.randint(50,101,n)
w = np.random.randint(5,101,n)
c = 9786

A continuación mostraremos dos algorimos basados en recocido simulado. El primero de ellos es un diseño sencillo y el segundo es un diseño más elaborado que obtiene mejores resultados.

Función objetivo¶

Dado que la clase SimulatedAnnealing 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 [14]:

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

Restricciones¶

La restricción del problema de la mochila es seleccionar un número de objetos sin exceder la capacidad de la mochila.

In [15]:

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¶

Nuestra solución inicial es creada introduciendo objetos de manera aleatoria, mientras no se exceda el peso de la mochila.

In [16]:

def getInitialSolution(NumObjects=15):
    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)

Ejecución de la metaheurística¶

In [17]:

class Knapsack_solver(SimulatedAnnealing):

    def __init__(self, f_ : function_type , constraints_: list):
        super().__init__(f_,constraints_)
        
    def get_neighbor(self, x : np.ndarray, **kwargs) -> np.ndarray: 
        
        x_ = x.copy()
        N = len(x_)
        while(True):
            ind = random.randint(0, N-1)
            x_[ind] ^= 1
            
            if(self.is_valid(x_)):
                break
            
            x_[ind] ^= 1
        
        return np.array(x_)

    def update_temperature(self, **kwargs) -> float:
        return self.logger['temperature'] * 0.99

Parte clave de este algoritmo es la temperatura. La temperatura es una función que varía de acuerdo al tiempo $t$, donde, al inicio de la búsqueda permite aceptar con mayor probabilidad soluciones peores.

La clase SimulatedAnnealing define esta función como update_temperature que está implementada por defecto. En este ejemplo vamos a definir nuestra función de cambio lineal $T(t + 1) = \sigma T(t)$

La función get_neighbor tomará la solución $x$ (arreglo de 0's y 1's), donde, el valor de retorno será la solución $x$ con una posición aleatoria $i$ que será reemplazada por el valor 0 si la posición $x_i$ es 1, sino, será 1.

In [18]:

Knapsack_ = Knapsack_solver(f, [g1])
Knapsack_.optimize(getInitialSolution,1000.0,0.1)

In [19]:

print(Knapsack_)

Simulated Annealing: 
 f(X) = -15986.0 
 X = [1 0 0 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0
 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0
 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0
 0 1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0
 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0
 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0
 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 1 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0
 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0
 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 1 0 0 0 0
 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 1 1 1 0
 0 1 0 0 0 0 0 1 0 0 1 0 0 1 1 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 1
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 1
 0 0 0 0 0 0 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 1 0 1 1 0 1 1 0 1 0 0 0 0 0 0 0
 0 0 0 0 1 0 0 0 1 0 1 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0
 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0
 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1
 0 0 0 1 0 0 0 1 1 1 1 0 0 1 0 1 0 0 0 1 1 0 1 0 0 0 0 0 1 0 1 0 0 1 0 0 0
 0 0 0 0 1 1 0 1 0 0 0 1 0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1
 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 1 0 1 0 0 1 0 0
 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 0
 0 0 1 0 0 0 1 1 1 0 1 0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 1 0 0 0 1 0 0 0 0 0 0
 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0
 1] 
 Constraints: 
 9784 <= 9786 

Para realizar un estudio estadístico del comportamiento de la metaheurística, 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:

Objeto que realiza la ejecución de la metaheurística.
El número de veces que se quiere ejecutar la metaheurística.
Tupla con los argumentos que recibe la función optimize.
Argumentos adicionales a la búsqueda (opcional).

La función get_stats considera las solución regresada por la metaheurística en cada ejecución y retorna un diccionario con la mejor y peor solución encontrada, la media y desviación estándar del valor de la función objetivo.

In [20]:

args = (getInitialSolution,1000.0,0.01)
statistics = get_stats(Knapsack_, 30, args)

In [21]:

pprint(statistics)

{'Best solution': {'f': -16731.0,
                   'x': array([1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0,
       0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0,
       1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0,
       0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0,
       0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0,
       1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1,
       1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1,
       0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0,
       0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
       0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1,
       0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
       1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0,
       0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0,
       0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0,
       0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0,
       0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0,
       1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0,
       1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0,
       0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0,
       0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0,
       0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
       0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0,
       0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1,
       0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1,
       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1,
       0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0,
       0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1,
       0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0,
       0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0,
       0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0,
       1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0,
       0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0,
       0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0,
       1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0,
       1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0,
       0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0,
       0, 0, 0, 1, 0, 0, 1, 0, 0, 0])},
 'Mean': -15826.4,
 'Median': -15822.5,
 'Standard deviation': 478.939912723924,
 'Worst solution': {'f': -14882.0,
                    'x': array([0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0,
       0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
       1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1,
       0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0,
       0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1,
       0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
       1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0,
       0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0,
       0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1,
       0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0,
       1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0,
       0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0,
       0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0,
       1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0,
       1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0,
       0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1,
       0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0,
       0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0,
       1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0,
       1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0,
       0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
       1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0,
       0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1,
       0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0,
       1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0,
       0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0,
       1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
       1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0,
       0, 1, 0, 0, 0, 0, 1, 0, 0, 1])}}

Se puede observar que los resultados obtenidos no son tan buenos como los obtenidos con la metaheurística basada en Búsqueda Tabú. A continuación se harán algunas modificaciones en el diseño, con el objetivo de mejorar los resultados.

Solución inicial¶

En el diseño anterior, no se consideró el beneficio de introducir un objeto determinado a la mochila según su valor y peso. Una forma de hacerlo es la siguiente:

1. Asignar a cada objeto su valor por unidad de peso: $\frac{p_{i}}{w_{i}}$.

2. Ordenar todos los objetos con respecto a este indicador.

3. Seleccionar los objetos que tenga mayor valor en este indicador sin exceder la capacidad.

In [22]:

def Init_GISP():
    global n,p,w,c
    Arr_=[]
    for i in range(n):
        Arr_.append((p[i]/w[i],i))
    
    Arr_.sort(reverse=True)
    return Arr_
GISP_Arr = Init_GISP()

def getInitialSolution2():
    global n,p,w,c, GISP_Arr
    X = [0 for i in range(n)]
    current_weight = 0
    for i in range(n):
        ind = GISP_Arr[i][1]
        if current_weight+ w[ind] <= c:
            current_weight+=w[ind]
            X[ind] = 1
    return np.array(X)

Para crear un nuevo vecino, seguiremos la misma estrategia que en el diseño anterior. Sin embargo, si la nueva solución no es válida vamos a realizar lo siguiente:

1. Fase de reparación.
2. Fase de mejoramiento.

Fase de reparación: En esta fase retiramos objetos que se encuentran en la mochila mientras la capacidad actual exceda el límite definido $c$. Los objetos son retirados de acuerdo a los valores más pequeños en el indicador definido ($\frac{p_{i}}{w_{i}}$).

Fase de mejoramiento: En esta fase se introducen objetos a la mochila siempre y cuando no excedan la capacidad. Estos objetos son introducidos priorizando aquellos con los valores más grandes en el indicador definido ($\frac{p_{i}}{w_{i}}$).

In [23]:

class Knapsack_solver2(SimulatedAnnealing):

    def __init__(self, f_ : function_type , constraints_: list):
        super().__init__(f_,constraints_)
        
        
    def generate_neighbor(self, x: np.ndarray) -> np.ndarray:
        x_ = x.copy()
        N = len(x_)
        ind = random.randint(0, N-1)
        x_[ind] ^= 1
        
        return x_
    
    def repair_neighbor(self, x: np.ndarray) -> np.ndarray:
        global GISP_Arr,w,c,n
        
        #Get the total weight
        total_weight=0
        for i in range(n):
            if x[i]:
                total_weight += w[i]
        
        for i in range(n):
            ind = GISP_Arr[n - (1+i)][1] #Lowest
            
            if x[ind]:
                total_weight -= w[ind]
                x[ind] = 0
            
            if total_weight <= c:
                break
                
    def improve_neighbor(self, x: np.ndarray) -> np.ndarray:
        global GISP_Arr,w,c,n
        
        #Get the total weight
        total_weight=0
        for i in range(n):
            if x[i]:
                total_weight += w[i]
                
        for i in range(n):
            ind = GISP_Arr[i][1]
            if total_weight + w[ind] > c:
                continue
                
            if x[ind] == 0 :
                total_weight += w[ind]
                x[ind] = 1
                
    def get_neighbor(self, x : np.ndarray) -> np.ndarray: 
        
        neighbor_ = self.generate_neighbor(x)
            
        if(self.is_valid(neighbor_)):
            return neighbor_
        
        #RI strategy
        self.repair_neighbor(neighbor_)
        self.improve_neighbor(neighbor_)
        
        return neighbor_

Ejecutamos nuestra metaheurística:

In [24]:

f(getInitialSolution2())

Out[24]:

-30214.0

In [25]:

Knapsack_2 = Knapsack_solver2(f, [g1])

In [26]:

Knapsack_2.optimize(getInitialSolution2,1000.0,0.1)
print(Knapsack_2)

Simulated Annealing: 
 f(X) = -30214.0 
 X = [1 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 1 1 1 1 0 1 0 0 1 0 1 0 1 0 0 0 0 0 0
 1 1 0 0 0 1 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 0 0 0 1
 0 0 1 1 0 1 1 0 0 1 0 1 0 0 1 0 0 0 0 0 0 1 1 0 0 1 1 0 1 0 1 0 0 1 1 0 0
 0 0 1 0 1 0 0 0 1 0 0 0 0 1 0 1 0 1 0 1 0 1 0 0 1 1 1 0 0 1 1 1 1 1 0 0 1
 0 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 0 1 1 1 0 0 0 1 0 0 0 0 0
 1 0 1 0 0 0 0 0 1 1 1 0 0 0 0 1 0 1 0 1 1 0 0 0 0 1 0 1 0 0 0 0 1 1 0 1 0
 1 0 1 0 1 0 0 0 1 0 0 1 0 0 0 0 0 1 1 1 0 1 0 0 1 1 1 1 0 0 1 1 1 1 1 0 1
 0 0 1 1 0 1 0 0 1 0 0 1 1 0 1 1 0 0 0 1 0 1 0 0 1 0 0 1 0 0 1 0 0 0 0 1 1
 0 1 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0
 0 0 1 0 0 0 0 1 1 0 1 0 0 1 1 1 0 0 0 1 1 0 0 0 1 0 0 1 0 1 0 1 1 1 0 0 0
 0 1 0 1 1 0 0 0 0 1 0 1 1 0 1 0 1 1 1 1 1 0 0 0 1 0 1 0 1 0 1 0 0 1 0 0 0
 0 0 1 1 0 0 1 1 0 0 0 1 0 0 1 1 1 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1 0 1 1 0 1
 0 1 0 0 0 0 1 1 0 0 1 1 0 0 1 0 1 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0
 0 0 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 0 1 1 0 0 1 0 1 1 1 1 1 1 1 1
 0 0 0 1 1 1 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 1 1 0 0 0 0 0 1 1 0 1 1 0
 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 0 0 1 0 0 1 0 1 0 1 1 0 1 0 0 0 1 0 0 0
 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 1 1 0 1
 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0
 1 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 1 0 1 0 0 0 0 0
 0 1 0 1 0 0 1 0 0 1 0 1 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0
 1 0 0 0 0 1 1 1 0 0 0 0 0 1 1 1 0 0 0 1 0 0 1 1 0 0 0 0 1 1 0 0 0 1 0 1 0
 1 0 1 1 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 0 1 1 0 1 1
 0 0 0 0 0 0 1 0 1 0 1 0 0 0 1 0 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1 0 1 1 0
 1 0 0 1 1 0 0 0 1 1 0 0 1 1 1 0 1 0 1 1 1 0 0 1 1 0 0 0 0 0 1 0 0 1 0 1 1
 1 0 1 0 1 0 0 0 1 0 1 1 1 1 1 0 0 1 1 0 0 1 0 0 1 1 1 0 0 0 0 1 1 0 1 0 0
 1 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 0 1 0 0 0 0 0
 0 1 0 1 1 1 1 0 0 1 0 0 1 0 0 1 1 1 0 0 0 0 0 1 1 0 1 0 0 0 0 1 0 0 0 0 0
 0] 
 Constraints: 
 9786 <= 9786 

Resultados¶

Vamos a comparar las distintas combinaciones entre la forma de generar la solución inicial y la estrategia de generar un nuevo vecino.

1. Solución por Indicador y RI estrategia.
2. Solución por Indicador y estrategia ingenua.
3. Solución ingenua y RI estrategia.
4. Solución ingenua y estrategia ingenua.

Solución por Indicador y RI estrategia.¶

In [27]:

args = (getInitialSolution2,1000.0,0.01)
statistics = get_stats(Knapsack_2, 30, args)

In [28]:

print("f(x*) = {} \nfunción objetivo promedio: {} \nfunción objetivo de la peor solución: {}".format(statistics['Best solution']['f'],statistics['Mean'],statistics['Worst solution']['f']))

f(x*) = -30214.0 
función objetivo promedio: -30214.0 
función objetivo de la peor solución: -30214.0

Solución por Indicador y estrategia ingenua.¶

In [29]:

args = (getInitialSolution2,1000.0,0.01)
statistics = get_stats(Knapsack_, 30, args)

In [30]:

print("f(x*) = {} \nfunción objetivo promedio: {} \nfunción objetivo de la peor solución: {}".format(statistics['Best solution']['f'],statistics['Mean'],statistics['Worst solution']['f']))

f(x*) = -30214.0 
función objetivo promedio: -30214.0 
función objetivo de la peor solución: -30214.0

Solución ingenua y RI estrategia.¶

In [31]:

args = (getInitialSolution,1000.0,0.01)
statistics = get_stats(Knapsack_2, 30, args)

In [32]:

print("f(x*) = {} \nfunción objetivo promedio: {} \nfunción objetivo de la peor solución: {}".format(statistics['Best solution']['f'],statistics['Mean'],statistics['Worst solution']['f']))

f(x*) = -30004.0 
función objetivo promedio: -29836.833333333332 
función objetivo de la peor solución: -29702.0

Solución ingenua y estrategia ingenua.¶

In [33]:

args = (getInitialSolution,1000.0,0.01)
statistics = get_stats(Knapsack_, 30, args)

In [34]:

print("f(x*) = {} \nfunción objetivo promedio: {} \nfunción objetivo de la peor solución: {}".format(statistics['Best solution']['f'],statistics['Mean'],statistics['Worst solution']['f']))

f(x*) = -16366.0 
función objetivo promedio: -15746.633333333333 
función objetivo de la peor solución: -14781.0

In [ ]: