<jupyter_start><jupyter_text>Algoritmos genéticosLa librería **Pyristic** incluye una clase llamada `Genetic`  inspirada en la metaheurística de *Algoritmos genéticos* (AG) para resolver problemas de minimización. Para trabajar con esta clase se requiere hacer lo siguiente:1. Definir:    * La función objetivo $f$.    * La lista de restricciones.    * Lista de límites inferiores y límites superiores.     * Configuración de operadores de la metaheurística (opcional).    2. Crear una clase que hereda de `Genetic`.3. Sobreescritura de funciones auxiliares:        * initialize_population (opcional)    * fixer (opcional)    * mutation_operator (opcional)    * crossover_operator (opcional)    * survivor_selection (opcional)    * parent_selection  (opcional)    A continuación se mostrarán los elementos que se deben importar.   Librerías externas<jupyter_code>from pprint import pprint
import math
import random 
import numpy as np 
import copy
from IPython.display import Image
from IPython.core.display import HTML<jupyter_output><empty_output><jupyter_text>Componentes de `pyristic`La estructura que está organizada la librería es: * Las metaheurísticas están ubicadas en `heuristic`. * Las funciones de prueba están ubicadas en `utils.test_function`. * Las clases auxiliares para mantener la información de los operadores que serán empleados para alguna de las metaheurísticas basadas en los paradigmas del cómputo evolutivo están ubicadas en `utils.helpers`. * Las metaheurísticas basadas en los paradigmas del cómputo evolutivo dependen de un conjunto de operadores (selección, mutación y cruza). Estos operadores están ubicados en `utils.operators`. Para demostrar el uso de nuestra metaheurística basada en *algoritmos geneticos* tenemos que importar la clase llamada `Genetic` que se encuentra en `heuristic.GeneticAlgorithm_search`.<jupyter_code>from pyristic.heuristic.GeneticAlgorithm_search import Genetic
from pyristic.utils.operators import selection,mutation,crossover
import pyristic.utils.helpers as helpers
from pyristic.utils.test_function import ackley_, beale_<jupyter_output><empty_output><jupyter_text>Función de Beale\begin{equation}  \label{eq:BF}  \begin{array}{rll}  \text{minimizar:} & f(x_1, x_2) = (1.5 - x_1 + x_1x_2)^2 + (2.25 - x_1 + x_1x_2^2)^2 + (2.625 - x_1 + x_1x_2^3)^2  &  \\  \text{Tal que: } & -4.5 \leq x_1,x_2 \leq 4.5 &    \end{array}\end{equation}El mínimo global se encuentra en $x^* = (3, 0.5)$ y $f(x^*) = 0$.<jupyter_code>Image(filename="include/beale.png", width=500, height=300)<jupyter_output><empty_output><jupyter_text>La librería **Pyristic** tiene implementados algunos problemas de prueba en `utils.test_function`, entre ellos la función de Beale. Los problemas de prueba están definidos como diccionarios con las siguientes llaves:* `function.` Función objetivo.* `constraints.` Restricciones del problema.* `bounds.` Límites para cada una de las variables del problema. En el caso de que todas las variables del problema se encuentren en el mismo intervalo de búsqueda, se puede emplear una lista con dos valores numéricos.* `decision_variables.` Número de variables que tiene dicho problema.<jupyter_code>beale_<jupyter_output><empty_output><jupyter_text>Función de aptitudLos algoritmos evolutivos, se define una función llamada **aptitud** que describe a cada individuo que tan bueno es en el problema a resolver. Los valores más grandes de aptitud corresponden a las mejores soluciones. Para el problema de Beale, la función de aptitud es:$F_a(i) = \frac{1}{f(x^{(i)}_1, x^{(i)}_2) + 1}$<jupyter_code>def aptitudeBeale(X: np.array) -> np.array:
    return 1/ ( beale_['function'](X)+1)<jupyter_output><empty_output><jupyter_text>Declaración de `Genetic`La metaheurística AG implementada en la librería **Pyristic** se puede utilizar de las siguientes maneras:* Crear una configuración de los operadores que son almacenados en un objeto del tipo `GeneticConfig` y posteriormente, se declara un objeto de la clase `Genetic`, donde, el constructor recibe la configuración en el parámetro con el nombre `config`.* Crear una clase que herede de la clase `Genetic` y sobreescribir los métodos.* Realizar una combinación de las dos anteriores.La clase `Genetic` no tiene ningún operador definido por defecto, porque, no se tiene conocimiento si el problema a resolver es continuo o discreto.  Ejecución de la metaheurísticaPara crear una instancia de la clase `Genetic`, vamos a definir una configuración de los operadores que serán empleados. La configuración se hace a través de la clase `GeneticConfig`.<jupyter_code>configuration_beale = (helpers.GeneticConfig()
                 .cross(crossover.intermediate_crossover(0.5))
                 .mutate(mutation.uniform_mutator(beale_['bounds']))
                 .survivor_selection(selection.merge_selector())
                 .parent_selection(selection.tournament_sampler(3,0.5))
                 .fixer_invalide_solutions(helpers.ContinuosFixer(beale_['bounds'])))
print(configuration_beale)<jupyter_output>--------------------------------
	Configuration
--------------------------------
Crossover operator: Intermediate
	Arguments:
		-Alpha:0.5
Mutation operator: Uniform
	 Arguments:
		 -Lower bound: -4.5
		 -Upper bound: 4.5
Survivor selection: Merge population
Fixer: continuos
Parent selection: Tournament sampling
	 Arguments:
		-Chunks: 3
		-prob: 0.5

--------------------------------<jupyter_text>En este ejemplo se ha empleado la siguiente configuración:* `Crossover operator.` Cruza intermedia.* `Mutation operator.` Mutación uniforme.* `Survivor selection.` Esquema  $(\mu + \lambda)$.* `Parent selection.` Selección mediante torneos de tamaño 3, utilizando $p=0.5$.* `Fixer.` En caso de que haya soluciones infactibles, se utiliza una función auxiliar que actualiza cada variable de decisión que se encuentre fuera del espacio de búsqueda con el valor del límite que rebasó. A continuación, se inicializa un objeto del tipo `Genetic` con los siguientes parámetros:* `function`: Función para optimizar.* `decision_variables`: Número de variables que tiene el problema.* `constraints`: Restricciones del problema (por defecto, es una lista vacía).* `bounds`: Límites del problema (por defecto es una lista vacía).* `config`: Configuración de los operadores (por defecto es None).<jupyter_code>bealeGenetic  = Genetic(
                    function= aptitudeBeale,\
                    decision_variables=beale_['decision_variables'],\
                    constraints= beale_['constraints'],\
                    bounds= beale_['bounds'],\
                    config=configuration_beale
                )<jupyter_output><empty_output><jupyter_text>Finalmente, ejecutamos el método `optimize` del objeto `bealeGenetic` usando:* **generations** = 200.* **size_population** = 100.* **verbose** =  True.<jupyter_code>bealeGenetic.optimize(300,200)
print(bealeGenetic)<jupyter_output>Genetic search: 
 F_a(X) = 0.9905470686694063 
 X = [2.81121771 0.46109721] 
 Constraints: 
 x1: -4.5 <= 2.81 <= 4.5 
 x2: -4.5 <= 0.46 <= 4.5<jupyter_text>Análisis estadístico 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: * `optimizer. `Objeto que realiza la búsqueda de soluciones. * `Niter. `Número de veces que se quiere ejecutar la metaheurística. * `OptArgs. `Argumentos que recibe la función optimize (debe ser una tupla). * `ExternOptArgs. `Argumentos adicionales a la búsqueda (opcional). * `transformer. ` después de la ejecución de la metaheurística, se aplica la función y despliega las estadisticas bajo esta función. La función `get_stats` retorna un diccionario con algunas estadísticas de las ejecuciones.<jupyter_code>args = (200, 100,False)
statistics = helpers.get_stats(bealeGenetic, 30, args,{},beale_['function'])
pprint(statistics)<jupyter_output>{'Best solution': {'f': 0.011089660382369462,
                   'x': array([2.92871608, 0.45929644])},
 'Mean': 0.021504580265503944,
 'Median': 0.01992776683804405,
 'Standard deviation': 0.008124017147345685,
 'Worst solution': {'f': 0.03997790448285727,
                    'x': array([2.97884391, 0.45097737])},
 'averageTime': 0.32114324569702146,
 'objectiveFunction': [0.025822560118872368,
                       0.016050104329712274,
                       0.02417822129033239,
                       0.012048467992121056,
                       0.014648483275912321,
                       0.014974706586485916,
                       0.027812363582186164,
                       0.02637874043433408,
                       0.021131853822972196,
                       0.014483266896073321,
                       0.014565555808386357,
                       0.03997790448285727,
                       0.019169662858132458,
                       0.037297164360997205,
                   [...]<jupyter_text>Función de Ackley\begin{equation}  \min f(\vec{x}) = -20\exp \left( -0.2 \sqrt{\frac{1}{n} \sum_{i=1}^n x_i^2} \right)   - exp \left( \frac{1}{n} \sum_{i=1}^n \cos (2\pi x_i) \right)  + 20 + e  \end{equation}El mínimo global está en $x_i^* = 0 $, $f(\vec{x}) = 0$ y su dominio es $|x_{i}| < 30$.<jupyter_code>Image(filename="include/ackley.jpg", width=500, height=300)<jupyter_output><empty_output><jupyter_text>Para este problema se va a crear una clase llamada *custom_AG* que herede de la clase `Genetic`. Posteriormente, se van a sobreescribir los métodos para que utilicen los siguientes operadores:* *__parent_selection:__* `tournament_sampler`* *__survivor_selection:__* `merge_selector`* *__crossover_operator:__* `intermediate`* *__mutation_operator:__* `non_uniform_mutator`* *__fixer:__* `ContinuosFixer`La siguiente tabla muestra la forma en que se encuentran definidos los operadores en la librería. |    Operador               |  Función           |  Clase          ||---------------------------|:------------------:|:------------ --:||  Mutación                 | *_mutation*        |    *_mutator*   ||  Cruza                    | *_cross*           |    *_crossover* ||  Selección padres         | *_sampling*        |    *_sampler*   ||  Selección sobrevivientes | No existe          |    *_selector*  ||           |    | |Cuando los operadores no requieren de parámetros adicionales o actualizar sus parámetros de los operadores cada que se llama el método `optimize`, se recomienda utilizar los operadores definidos como clases e inicializar la clase `Genetic` con la configuración, como en el ejemplo de la función de Beale. Cuando los operadores requieren de parámetros adicionales, se recomienda usar los operadores definidos como funciones, crear una clase que herede de `Genetic` y sobreescribir los operadores como se muestra a continuación.<jupyter_code>class custom_AG(Genetic):
    
    def __init__(self, function: helpers.function_type,\
                        decision_variables:int,\
                        constraints:list=[],\
                        bounds: list=[],\
                        config = None):
        super().__init__(function, decision_variables, constraints, bounds, config)
        self._survivor_selection = selection.merge_selector()
        
    def crossover_operator(self, parent_ind1: np.ndarray,\
                                 parent_ind2: np.ndarray) -> np.ndarray:
        return crossover.intermediate_cross(self.logger['parent_population_x'], parent_ind1,parent_ind2)
    
    def mutation_operator(self, **kwargs):
        return mutation.non_uniform_mutation(self.logger['offspring_population_x'])
    
    def survivor_selection(self,**kwargs) -> np.ndarray:
        individuals = {}
        individuals['population'] = [self.logger['parent_population_x'], self.logger['offspring_population_x']]
        return self._survivor_selection(   self.logger['parent_population_f'],\
                                            self.logger['offspring_population_f'],\
                                            individuals) 
        
    def parent_selection(self, **kwargs) -> np.ndarray:
        return selection.tournament_sampling(self.logger['parent_population_f'],3,0.5)
    
    def fixer(self, ind: int)-> np.ndarray:
        return np.clip(self.logger['offspring_population_x'][ind], self.Bounds[0], self.Bounds[1])<jupyter_output><empty_output><jupyter_text>Es importante tener en cuenta que se debe incluir `super().__init__()` para llamar al constructor de `Genetic` con los argumentos antes mencionados.  Función de aptitudLos algoritmos evolutivos, se define una función llamada **aptitud** que describe a cada individuo que tan bueno es en el problema a resolver. Los valores más grandes de aptitud corresponden a las mejores soluciones. Para el problema de Ackley, la función de aptitud es:$F_a(\vec{X}) = -f(\vec{X})$<jupyter_code>def aptitudeAckley(X: np.array) -> np.array:
    return -1*ackley_['function'](X)
AckleyGenetic = custom_AG(
                    function= aptitudeAckley,\
                    decision_variables=ackley_['decision_variables'],\
                    constraints= ackley_['constraints'],\
                    bounds= ackley_['bounds'])
                
AckleyGenetic.optimize(200,100)
print(AckleyGenetic)
args = (200, 100,False)
statistics = helpers.get_stats(AckleyGenetic, 30, args, transformer=ackley_['function'])
pprint(statistics)<jupyter_output>{'Best solution': {'f': 4.440892098500626e-16,
                   'x': array([ 3.21306544e-16,  6.07489340e-18, -1.35252761e-17, -2.79718736e-17,
        3.28516540e-16,  2.56920003e-16, -4.06023420e-17, -1.71812717e-16,
       -6.27616537e-17, -3.48603208e-17])},
 'Mean': 4.440892098500626e-16,
 'Median': 4.440892098500626e-16,
 'Standard deviation': 0.0,
 'Worst solution': {'f': 4.440892098500626e-16,
                    'x': array([ 3.21306544e-16,  6.07489340e-18, -1.35252761e-17, -2.79718736e-17,
        3.28516540e-16,  2.56920003e-16, -4.06023420e-17, -1.71812717e-16,
       -6.27616537e-17, -3.48603208e-17])},
 'averageTime': 0.36108405590057374,
 'objectiveFunction': [4.440892098500626e-16,
                       4.440892098500626e-16,
                       4.440892098500626e-16,
                       4.440892098500626e-16,
                       4.440892098500626e-16,
                       4.440892098500626e-16,
                       4.440892098500626e-16,
               [...]<jupyter_text>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 y $x$ es una permutación de las $n$ ciudades. A continuación se define una instancia de este problema utilizando 10 ciudades.<jupyter_code>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],\
]<jupyter_output><empty_output><jupyter_text>`dist_matrix` es una matriz de adyacencia. Cada componente $x_{i,j}$ es la distancia de la ciudad $x_{i}$ a la ciudad $x_{j}$.  Función objetivo<jupyter_code>def f_salesman(x : (list,np.ndarray)) -> float:
    global dist_matrix
    total_dist = dist_matrix[int(x[-1])][0]
    for i in range(1,len(x)):
        u,v = int(x[i]), int(x[i-1])
        total_dist+= dist_matrix[u][v]

    return float(total_dist)<jupyter_output><empty_output><jupyter_text>Función de aptitud<jupyter_code>def aptitudeSalesman(x):
    return -1 * f_salesman(x) 
contraints_viajero = []
bounds_viajero = []
decision_variables_viajero = 10<jupyter_output><empty_output><jupyter_text>Dado que para este problema vamos a usar una representación de permutaciones, no es necesario definir los límites de las variables de decisión.  Definición de la configuración Para este problema se va a utilizar una combinación de las dos formas empleadas anteriormente para hacer uso de la metaheurística de AG. A continuación, definimos la clase `TravellingSalesman_solver` que hereda de `Genetic` y sobreescribimos el método `initialize_population` de tal forma que cada individuo de la población sea una permutación de las ciudades.<jupyter_code>class TravellingSalesman_solver(Genetic):
    def __init__(self,  function: helpers.function_type,\
                        decision_variables:int,\
                        constraints:list=[],\
                        bounds: list=[],\
                        config = None):
        super().__init__(function, decision_variables, constraints, bounds, config)
    
    def initialize_population(self, **kwargs) -> np.ndarray:
        individuals = []
        
        for i in range(self.logger['population_size']):
            individuals += [np.random.permutation(self.Decision_variables)]
            
        return np.array(individuals)<jupyter_output><empty_output><jupyter_text>En este ejemplo se ha empleado la siguiente configuración:* `Crossover operator.` Permutaciones - Order Crossover (`permutation_order`).* `Mutation operator.` Mutación para permutaciones: por intercambio recíproco (`exchange_mutator`). * `Survivor selection.` Esquema  $(\mu + \lambda)$.* `Parent selection.` Selección mediante torneos de tamaño 3, utilizando $p=0.5$.* `Fixer.` No se emplea ninguna función auxiliar para corregir las soluciones.<jupyter_code>configuration_Travelling = (helpers.GeneticConfig()
                         .cross(crossover.permutation_order_crossover())
                         .mutate(mutation.exchange_mutator())
                         .survivor_selection(selection.merge_selector())
                         .parent_selection(selection.tournament_sampler(chunks_=3,prob_=0.8))
                         .fixer_invalide_solutions(helpers.NoneFixer()))<jupyter_output><empty_output><jupyter_text>Finalmente, se hace una instancia de la clase `TravellingSalesman_solver` y se llama a su método `optimize`.<jupyter_code>travellerGenetic = TravellingSalesman_solver(aptitudeSalesman,decision_variables_viajero,\
                                                 contraints_viajero,bounds_viajero,\
                                                 configuration_Travelling)
travellerGenetic.optimize(300,100)
print(travellerGenetic)<jupyter_output>Genetic search: 
 F_a(X) = -195.0 
 X = [7. 2. 6. 9. 8. 4. 1. 3. 5. 0.]<jupyter_text>Análisis estadístico<jupyter_code>args = (200, 100,False)
statistics = helpers.get_stats(travellerGenetic, 30, args, transformer=f_salesman)
pprint(statistics)<jupyter_output>{'Best solution': {'f': 195.0,
                   'x': array([7., 2., 6., 9., 8., 4., 1., 3., 5., 0.])},
 'Mean': 197.53333333333333,
 'Median': 195.0,
 'Standard deviation': 5.7950170165601955,
 'Worst solution': {'f': 227.0,
                    'x': array([4., 1., 5., 3., 8., 9., 6., 7., 2., 0.])},
 'averageTime': 5.144353644053141,
 'objectiveFunction': [195.0,
                       195.0,
                       199.0,
                       199.0,
                       195.0,
                       195.0,
                       199.0,
                       199.0,
                       195.0,
                       199.0,
                       195.0,
                       195.0,
                       195.0,
                       195.0,
                       195.0,
                       195.0,
                       199.0,
                       199.0,
                       195.0,
                       199.0,
                       195.0,
                       199.0,
   [...]
{'fraction_non_alphanumeric': 0.11508076284405978, 'fraction_numerical': 0.07230916318623258, 'mean_word_length': 3.0484823793033202, 'pattern_counts': {'":': 0, '<': 76, '<?xml version=': 0, '>': 79, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 1, 'word_list_counts': {'cursed_substrings.json': 13, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '19', 'dir': 'jupyter-structured-clean-dedup', 'id': '356872', 'license': 'MIT', 'n_tokens_mistral': 7438, 'n_tokens_neox': 6498, 'n_words': 1643, 'path': 'docs/docs/AGEjemplo.ipynb', 'repo_name': 'JAOP1/pyristic', 'size': '19873'}