DiscreteHillClimbing
v1.1.0
Este paquete (de DPEA) proporciona la implementación del algoritmo de escalada para tareas discretas.
pip install DiscreteHillClimbing
Hill Climbing ( Minimización de coordenadas ) es el algoritmo más simple para tareas discretas (una más simple solo es ser mejor que sea completamente aleatorio). En tareas discretas, cada predictor puede tener su valor del conjunto finito, por lo tanto, podemos verificar todos los valores del predictor (variable) o alguna parte no pequeña y aleatoria y hacer optimización por un predictor. Después de eso podemos optimizar por otro predictor, etc. También podemos intentar encontrar una mejor solución utilizando 1, 2, 3, ... predictores y elegir solo la mejor configuración.
Hay una gran variedad de formas de realizar la escalada , por lo que traté de hacer una implementación simple y universal. Seguramente, puede ser mejor crear su implementación (más rápida) depende de su propia tarea, pero este paquete es una buena opción flexible para el inicio.
La escalada es la línea de base perfecta cuando comienzas a buscar una solución. Realmente ayuda y realmente puede obtener un muy buen resultado utilizando solo evaluaciones de funciones de 50-200.
Vea la idea principal de mi implementación en este pseudocódigo:
best solution < - start_solution
best value < - func ( start_solution )
while functions evaluates_count < max_function_evals :
predictors < - get greedy_step random predictors ( variables )
for each predictor from predictors :
choose random_counts_by_predictors values from available values of this predictor
for each chosen value :
replace predictor value with chosen
evaluate function
remember best result as result of this predictor
select best predictor with its best configuration
replace values in solution
it is new best solution Paquetes de carga :
import numpy as np
from DiscreteHillClimbing import Hill_Climbing_descentDeterminar la función optimizada :
def func ( array : np . ndarray ) -> float :
return ( np . sum ( array ) + np . sum ( array ** 2 )) / ( 1 + array [ 0 ] * array [ 1 ])Determinar conjuntos disponibles para cada predictor :
available_predictors_values = [
np . array ([ 10 , 20 , 35 , 50 ]),
np . array ([ - 5 , 3 , - 43 , 0 , 80 ]),
np . arange ( 40 , 500 ),
np . linspace ( 1 , 100 , num = 70 ),
np . array ([ 65 , 32 , 112 ]),
np . array ([ 1 , 2 , 3 , 0 , 9 , 8 ]),
np . array ([ 1 , 11 , 111 , 123 , 43 ]),
np . array ([ 8 , 9 , 0 , 5 , 4 , 3 ]),
np . array ([ - 1000 , - 500 , 500 , 1000 ])
]Crear solución :
solution , value = Hill_Climbing_descent ( function = func ,
available_predictors_values = available_predictors_values ,
random_counts_by_predictors = 4 ,
greedy_step = 1 ,
start_solution = None ,
max_function_evals = 1000 ,
maximize = False ,
seed = 1 )
print ( solution )
print ( value )
# [ 10. -5. 493. 98.56521739 112. 9. 123. 9. 1000. ]
# -26174.972801975237 function : func np.array-> float/int; La función optimizada llamable utiliza la matriz Numpy 1D como argumento.
available_predictors_values : int Sequence Una lista de valores disponibles para cada predictor (cada dimensión del argumento).
random_counts_by_predictors : int o int secuencia, opcional ¿cuántas opciones aleatorias debe usar para cada variable? Use la lista de lista/numpy para la opción Seleccionar para cada predictor (o int - un número para cada predictor). El valor predeterminado es 3.
greedy_step : int, opcional TI opta mejor solución después de escalar por los predictores greedy_step. El valor predeterminado es 1.
start_solution : ninguna o secuencia int, punto opcional cuando se inicia el algoritmo. El valor predeterminado es ninguno: solución de inicio aleatorio
max_function_evals : int, conteo máximo opcional de evaluaciones de funciones. El valor predeterminado es 1000.
maximize : bool, opcional maximizar la función? (Minimizar por defecto). El valor predeterminado es falso.
seed : int o ninguno. Semilla aleatoria (ninguna si no importa). El valor predeterminado es ninguno
Devuelve : Tuple contenía la mejor solución y el mejor valor de función.
Puede establecer su valor diferente random_counts_by_predictors para cada predictor. Por ejemplo, si el conjunto de predictor disponible contiene solo 3-5 valores, es mejor verificarlos a todos; Pero si hay más de 100 valores, será mejor verificar 20-40 de ellos, no 5. Ver ejemplo:
import numpy as np
from DiscreteHillClimbing import Hill_Climbing_descent
def func ( array ):
return ( np . sum ( array ) + np . sum ( array ** 2 )) / ( 1 + array [ 0 ] * array [ 1 ])
available_predictors_values = [
np . array ([ 10 , 20 , 35 , 50 ]),
np . array ([ - 5 , 3 , - 43 , 0 , 80 ]),
np . arange ( 40 , 500 ),
np . linspace ( 1 , 100 , num = 70 ),
np . array ([ 65 , 32 , 112 ]),
np . array ([ 1 , 2 , 3 , 0 , 9 , 8 ]),
np . array ([ 1 , 11 , 111 , 123 , 43 ]),
np . array ([ 8 , 9 , 0 , 5 , 4 , 3 ]),
np . array ([ - 1000 , - 500 , 500 , 1000 ])
]
solution , value = Hill_Climbing_descent ( function = func ,
available_predictors_values = available_predictors_values ,
random_counts_by_predictors = [ 4 , 5 , 2 , 20 , 20 , 3 , 6 , 6 , 4 ],
greedy_step = 1 ,
start_solution = None ,
max_function_evals = 1000 ,
maximize = False ,
seed = 1 )
print ( solution )
print ( value )
# [ 10. -5. 494. 100. 112. 9. 123. 9. 1000.]
# -26200.979591836734 Parámetro greedy_step puede ser importante en algunas tareas. Puede ser mejor usar greedy_step = 2 o greedy_step = 3 en lugar de predeterminado greedy_step = 1 . Y no es una buena opción usar Big greedy_step si no podemos permitirnos evaluar la función optimizada muchas veces.
import numpy as np
from DiscreteHillClimbing import Hill_Climbing_descent
def func ( array ):
return ( np . sum ( array ) + np . sum ( np . abs ( array ))) / ( 1 + array [ 0 ] * array [ 1 ]) - array [ 3 ] * array [ 4 ] * ( 25 - array [ 5 ])
available_predictors_values = [
np . array ([ 10 , 20 , 35 , 50 ]),
np . array ([ - 5 , 3 , - 43 , 0 , 80 ]),
np . arange ( 40 , 500 ),
np . linspace ( 1 , 100 , num = 70 ),
np . array ([ 65 , 32 , 112 ]),
np . array ([ 1 , 2 , 3 , 0 , 9 , 8 ]),
np . array ([ 1 , 11 , 111 , 123 , 43 ]),
np . array ([ 8 , 9 , 0 , 5 , 4 , 3 ]),
np . array ([ - 1000 , - 500 , 500 , 1000 ])
]
seeds = np . arange ( 100 )
greedys = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 ]
results = np . empty ( len ( greedys ))
for i , g in enumerate ( greedys ):
vals = []
for s in seeds :
_ , value = Hill_Climbing_descent ( function = func ,
available_predictors_values = available_predictors_values ,
random_counts_by_predictors = [ 4 , 5 , 2 , 20 , 20 , 3 , 6 , 6 , 4 ],
greedy_step = g ,
start_solution = [ v [ 0 ] for v in available_predictors_values ],
max_function_evals = 100 ,
maximize = True ,
seed = s )
vals . append ( value )
results [ i ] = np . mean ( vals )
import pandas as pd
print ( pd . DataFrame ({ 'greedy_step' : greedys , 'result' : results }). sort_values ([ 'result' ], ascending = False ))
# greedy_step result
# 1 2 1634.172483
# 0 1 1571.038514
# 2 3 1424.222610
# 3 4 1320.051325
# 4 5 1073.783527
# 5 6 847.873058
# 6 7 362.113555
# 7 8 24.729801
# 8 9 -114.200000
