# 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.
    
    
2. Crear una clase que herede de *SimulatedAnnealing*.


3. 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*.


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


```python
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


```python
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.


```python
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.


```python
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)
```


```python
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.


```python
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.


```python
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.


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

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


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. 


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


```python
pprint(statistics)
```

    {'Best solution': {'f': 248.0, 'x': array([0, 5, 3, 8, 9, 6, 2, 7, 4, 1])},
     'Mean': 263.9,
     'Median': 271.0,
     'Standard deviation': 10.425449630591478,
     'Worst solution': {'f': 271.0, 'x': array([0, 5, 3, 8, 9, 6, 2, 7, 1, 4])},
     'averageTime': 0.02728691101074219,
     'objectiveFunction': [271.0,
                           271.0,
                           248.0,
                           271.0,
                           271.0,
                           248.0,
                           271.0,
                           269.0,
                           271.0,
                           271.0,
                           271.0,
                           248.0,
                           248.0,
                           271.0,
                           271.0,
                           271.0,
                           269.0,
                           271.0,
                           271.0,
                           248.0,
                           271.0,
                           248.0,
                           271.0,
                           248.0,
                           271.0,
                           269.0,
                           248.0,
                           271.0,
                           271.0,
                           248.0]}


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


```python
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.


```python
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.


```python
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.


```python
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



```python
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.



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


```python
print(Knapsack_)
```

    Simulated Annealing: 
     f(X) = -16579.0 
     X = [0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0
     0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 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 1 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0
     0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0
     0 0 0 1 0 1 0 0 0 0 1 0 0 0 1 1 0 1 1 0 0 0 1 0 1 0 1 0 0 0 0 0 0 1 1 0 0
     0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0
     1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 1 1 0 0 1 0
     0 0 0 0 1 0 0 0 0 1 0 1 0 1 0 1 0 0 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 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 1 0 0 1 0 0 0 0 0 1
     0 1 0 1 0 1 0 1 0 0 0 0 0 1 0 0 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 1 0 0 1 1 1 0 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0
     0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 1 0 0 0 0 0
     0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 1
     0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 1 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 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0
     0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 1 1 0 1 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0
     0 0 0 0 1 1 1 1 0 1 0 0 0 1 1 0 0 0 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 0 0 0 0 0 1 0 1 1 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0
     0 1 0 0 1 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 0 0 1 0 0 1
     1 1 0 1 1 1 0 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 1 1 0 1 0
     0 0 1 0 0 0 1 0 0 1 0 0 0 1 1 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 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 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0
     0 0 0 0 0 1 1 0 0 0 1 0 1 0 1 0 1 1 1 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0
     1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 1
     1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 1 1 0 0 0 1 0 0 1 0 0 1
     0 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 1 0 0 0 0 1 0
     0 0 0 0 1 0 0 0 0 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 1 0
     0] 
     Constraints: 
     9785 <= 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. 


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


```python
pprint(statistics)
```

    {'Best solution': {'f': -17760.0,
                       'x': array([0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0,
           0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0,
           1, 0, 1, 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, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0,
           0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
           1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0,
           0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0,
           0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0,
           0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0,
           0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0,
           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, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0,
           0, 0, 0, 0, 0, 1, 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, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0,
           0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0,
           1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0,
           0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1,
           1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0,
           0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1,
           0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0,
           0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0,
           0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
           1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0,
           0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0,
           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, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0,
           1, 0, 0, 0, 1, 0, 1, 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, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0,
           0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
           0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0,
           0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 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, 0, 1,
           0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1,
           0, 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, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
           0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0,
           0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1,
           0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 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, 1, 0, 0,
           0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0,
           1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0,
           0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0,
           1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1,
           0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0,
           0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0,
           0, 0, 0, 0, 0, 0, 0, 1, 0, 0])},
     'Mean': -16051.933333333332,
     'Median': -16045.0,
     'Standard deviation': 632.8604866442173,
     'Worst solution': {'f': -15000.0,
                        'x': array([0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
           0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1,
           1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
           0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0,
           0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0,
           1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1,
           0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1,
           0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1,
           0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0,
           1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 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, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0,
           0, 0, 0, 0, 0, 0, 0, 1, 1, 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, 0, 0, 0, 0, 1, 0,
           0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0,
           0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0,
           0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0,
           0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0,
           1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0,
           0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0,
           0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0,
           1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0,
           1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
           0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0,
           0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0,
           0, 0, 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, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1,
           0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0,
           0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0,
           0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 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, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 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, 1, 0,
           0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0,
           0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0,
           0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0,
           0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1,
           0, 0, 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, 1, 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, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0,
           0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0,
           1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 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, 1,
           0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1,
           0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0,
           1, 0, 1, 0, 0, 0, 0, 0, 0, 1])},
     'averageTime': 0.038174986839294434,
     'objectiveFunction': [-15538.0,
                           -15342.0,
                           -15438.0,
                           -16765.0,
                           -16003.0,
                           -16903.0,
                           -15939.0,
                           -16588.0,
                           -15772.0,
                           -15795.0,
                           -16196.0,
                           -15438.0,
                           -17760.0,
                           -16736.0,
                           -15766.0,
                           -16294.0,
                           -16892.0,
                           -16508.0,
                           -15000.0,
                           -16388.0,
                           -15179.0,
                           -15987.0,
                           -16529.0,
                           -15322.0,
                           -15515.0,
                           -16163.0,
                           -16087.0,
                           -15020.0,
                           -16529.0,
                           -16166.0]}


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.


```python

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


```python
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:


```python
f(getInitialSolution2())
```




    -31626.0




```python
Knapsack_2 = Knapsack_solver2(f, [g1])
```


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

    Simulated Annealing: 
     f(X) = -31626.0 
     X = [1 0 1 0 0 1 0 0 1 1 1 1 0 0 0 1 0 1 1 0 0 0 1 1 0 0 1 0 0 0 0 0 0 1 0 0 0
     1 0 0 0 1 0 1 0 0 0 1 1 0 0 1 1 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1
     0 0 1 1 0 1 1 0 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 0 1 0 0 1 0 1 1 1 0 0 0 0 1
     0 1 0 1 1 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 1 1 0 1 1 0 1 1 0 1 0 1 0
     1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 1 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1
     1 1 0 1 0 0 0 1 1 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0
     0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 1 0 1 1 0 0 1 0 0
     0 1 0 0 1 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 0 1 1
     1 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 1 1 0 1 0 1 1 1 0 1 1 1 0 0 1 0 0 1 1 0 0
     0 0 1 1 0 1 0 0 0 1 1 0 0 1 0 1 0 0 1 0 0 0 0 1 0 0 0 1 1 1 0 0 1 0 0 0 1
     0 0 1 1 0 1 1 1 1 1 0 1 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 1 1 1 0 1 1
     0 0 1 1 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 1 1 0 0 0 1 1 0 0 1 0 0 1 0 1 1 1 0
     0 0 1 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 0 0
     1 0 1 1 0 0 0 1 1 1 0 0 1 0 1 0 1 1 0 1 1 0 1 1 0 1 1 0 0 1 1 0 0 1 0 1 0
     0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 1 1 0 0 0 0 1 0 1 1 0 0 0 1 1 1 0 0 0 1 0
     0 0 1 0 0 0 1 1 0 0 1 0 0 1 0 0 0 1 0 0 0 1 1 1 1 0 0 0 0 1 1 0 0 1 0 0 0
     1 0 1 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 1
     0 0 0 0 0 0 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 0 1 0
     1 1 0 0 0 0 1 0 0 0 1 1 1 0 0 1 0 1 0 0 0 1 1 1 0 0 1 1 0 0 1 1 1 0 0 1 0
     1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 1 0 1 0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0
     1 1 1 1 1 0 1 0 1 0 1 0 1 1 1 1 1 0 0 1 0 1 0 0 1 0 0 1 1 0 0 1 0 0 0 0 1
     1 0 1 1 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 1 0 1 0
     0 1 1 0 1 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 0 0 0 0 1 0 0 1 0 1 1 0 0 0 0 0 0
     1 1 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0 1 1 0 1 0 1
     1 0 0 1 0 1 0 1 0 1 0 0 1 1 0 0 1 1 1 1 1 0 1 0 0 1 1 0 0 1 1 0 0 1 0 1 0
     1 0 1 0 0 1 1 0 0 0 0 1 0 1 0 1 0 0 1 1 0 0 1 0 0 0 1 0 1 0 1 0 0 0 0 1 0
     1 1 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 1 0 0 0 0 0 0 1 1 0 0 1 0 0 1 0 1 0 1 0
     1] 
     Constraints: 
     9774 <= 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.


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


```python
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*) = -31644.0 
    función objetivo promedio: -31630.5 
    función objetivo de la peor solución: -31626.0


### Solución por Indicador y estrategia ingenua.


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


```python
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*) = -31626.0 
    función objetivo promedio: -31626.0 
    función objetivo de la peor solución: -31626.0


### Solución ingenua y RI estrategia.


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


```python
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*) = -31401.0 
    función objetivo promedio: -31269.3 
    función objetivo de la peor solución: -31143.0


### Solución ingenua y estrategia ingenua.


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


```python
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*) = -17258.0 
    función objetivo promedio: -16229.833333333334 
    función objetivo de la peor solución: -15228.0


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