Algoritmos genéticos¶
La 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:
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).
Crear una clase que hereda de
Genetic.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¶
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
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.
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_
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$.
Image(filename="include/beale.png", width=500, height=300)
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.
beale_
{'function': CPUDispatcher(<function beale_function at 0x7f307a8eb1e0>),
'constraints': [CPUDispatcher(<function constraint1_beale at 0x7f307a8eb158>)],
'bounds': [-4.5, 4.5],
'decision_variables': 2}
Función de aptitud¶
Los 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}$
def aptitudeBeale(X: np.array) -> np.array:
return 1/ ( beale_['function'](X)+1)
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
GeneticConfigy posteriormente, se declara un objeto de la claseGenetic, donde, el constructor recibe la configuración en el parámetro con el nombreconfig. - Crear una clase que herede de la clase
Geneticy 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ística¶
Para 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.
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)
-------------------------------- 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 --------------------------------
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).
bealeGenetic = Genetic(
function= aptitudeBeale,\
decision_variables=beale_['decision_variables'],\
constraints= beale_['constraints'],\
bounds= beale_['bounds'],\
config=configuration_beale
)
Finalmente, ejecutamos el método optimize del objeto bealeGenetic usando:
- generations = 200.
- size_population = 100.
- verbose = True.
bealeGenetic.optimize(300,200)
100%|████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 300/300 [00:00<00:00, 329.52it/s]
print(bealeGenetic)
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
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.
args = (200, 100,False)
statistics = helpers.get_stats(bealeGenetic, 30, args,{},beale_['function'])
pprint(statistics)
{'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,
0.022163492244137047,
0.02255408268450889,
0.039706712808810773,
0.03622811676625766,
0.021853928620736675,
0.015490971844214548,
0.020685870817955646,
0.011089660382369462,
0.018464288396660596,
0.016807787308913708,
0.02866177257469625,
0.013523633161099165,
0.015768835994718483,
0.01217291075555824,
0.024291490425657425,
0.017134797339448306]}
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$.
Image(filename="include/ackley.jpg", width=500, height=300)
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.
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])
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 aptitud¶
Los 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})$
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)
100%|████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 200/200 [00:00<00:00, 357.09it/s]
print(AckleyGenetic)
Genetic search: F_a(X) = -4.440892098500626e-16 X = [ 1.01079412e-16 1.95011591e-16 -4.18121315e-17 1.22151952e-16 -2.09371212e-20 6.25142561e-17 -1.63548438e-19 1.06456001e-16 5.86767061e-18 -5.20341999e-17] Constraints: x1: -30 <= 0.00 <= 30 x2: -30 <= 0.00 <= 30 x3: -30 <= -0.00 <= 30 x4: -30 <= 0.00 <= 30 x5: -30 <= -0.00 <= 30 x6: -30 <= 0.00 <= 30 x7: -30 <= -0.00 <= 30 x8: -30 <= 0.00 <= 30 x9: -30 <= 0.00 <= 30 x10: -30 <= -0.00 <= 30
args = (200, 100,False)
statistics = helpers.get_stats(AckleyGenetic, 30, args, transformer=ackley_['function'])
pprint(statistics)
{'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,
4.440892098500626e-16,
4.440892098500626e-16,
4.440892098500626e-16,
4.440892098500626e-16,
4.440892098500626e-16,
4.440892098500626e-16,
4.440892098500626e-16,
4.440892098500626e-16,
4.440892098500626e-16,
4.440892098500626e-16,
4.440892098500626e-16,
4.440892098500626e-16,
4.440892098500626e-16,
4.440892098500626e-16,
4.440892098500626e-16,
4.440892098500626e-16,
4.440892098500626e-16,
4.440892098500626e-16,
4.440892098500626e-16,
4.440892098500626e-16,
4.440892098500626e-16,
4.440892098500626e-16,
4.440892098500626e-16]}
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.
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],\
]
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¶
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)
Función de aptitud¶
def aptitudeSalesman(x):
return -1 * f_salesman(x)
contraints_viajero = []
bounds_viajero = []
decision_variables_viajero = 10
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.
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)
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.
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()))
Finalmente, se hace una instancia de la clase TravellingSalesman_solver y se llama a su método optimize.
travellerGenetic = TravellingSalesman_solver(aptitudeSalesman,decision_variables_viajero,\
contraints_viajero,bounds_viajero,\
configuration_Travelling)
travellerGenetic.optimize(300,100)
100%|█████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 300/300 [00:07<00:00, 38.76it/s]
print(travellerGenetic)
Genetic search: F_a(X) = -195.0 X = [7. 2. 6. 9. 8. 4. 1. 3. 5. 0.]
Análisis estadístico¶
args = (200, 100,False)
statistics = helpers.get_stats(travellerGenetic, 30, args, transformer=f_salesman)
pprint(statistics)
{'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,
195.0,
195.0,
199.0,
195.0,
195.0,
227.0,
195.0,
199.0]}