DiscreteHillClimbing
v1.1.0
Ce paquet (de DPEA) fournit la mise en œuvre de l'algorithme d'escalade en colline pour les tâches discrètes.
pip install DiscreteHillClimbing
L'escalade de colline ( minimisation des coordonnées ) est l'algorithme le plus simple pour les tâches discrètes (une plus simple ne fait que devenir le meilleur aléatoire). Dans les tâches discrètes, chaque prédicteur peut avoir sa valeur à partir de l'ensemble fini, nous pouvons donc vérifier toutes les valeurs de prédicteur (variable) ou une partie aléatoire non petite et faire l'optimisation par un prédicteur. Après cela, nous pouvons optimiser par un autre prédicteur et ainsi de suite. Nous pouvons également essayer de trouver une meilleure solution en utilisant 1, 2, 3, ... des prédicteurs et choisir uniquement la meilleure configuration.
Il existe une très variété de façons de réaliser l'escalade en colline , j'ai donc essayé de faire une implémentation simple et universelle. Assurément, il peut être préférable de créer votre implémentation (plus rapide) dépend de spécifique de votre propre tâche, mais ce package est un bon choix flexible pour commencer.
L'escalade est la base parfaite lorsque vous commencez à rechercher une solution. Cela aide vraiment et cela peut vraiment vous obtenir un très bon résultat en utilisant seulement 50-200 évaluations de fonctions.
Voir l'idée principale de mon implémentation dans ce pseudocode:
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 Packages de chargement :
import numpy as np
from DiscreteHillClimbing import Hill_Climbing_descentDéterminer la fonction optimisée :
def func ( array : np . ndarray ) -> float :
return ( np . sum ( array ) + np . sum ( array ** 2 )) / ( 1 + array [ 0 ] * array [ 1 ])Déterminez les ensembles disponibles pour chaque prédicteur :
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 ])
]Créer une solution :
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 fonction optimisée callable utilise un argument Numpy 1D comme argument.
available_predictors_values : séquence Int Une liste des valeurs disponibles pour chaque prédicteur (chaque dimension de l'argument).
random_counts_by_predictors : séquence int ou int, facultatif combien de choix aléatoires doivent-ils utiliser pour chaque variable? Utilisez le tableau List / Numpy pour l'option Sélectionner pour chaque prédicteur (ou int - un numéro pour chaque prédicteur). La valeur par défaut est 3.
greedy_step : int, IT facultatif Choices Une meilleure solution après l'escalade par les prédicteurs Greedy_step. La valeur par défaut est 1.
start_solution : Aucun ou séquence int, point facultatif lorsque l'algorithme démarre. La valeur par défaut n'est pas - Solution de démarrage aléatoire
max_function_evals : int, comptage maximal facultatif des évaluations de fonctions. La valeur par défaut est 1000.
maximize : bool, facultatif maximiser la fonction? (minimiser par défaut). La valeur par défaut est fausse.
seed : int ou aucun. Graines aléatoires (aucune si elle n'a pas d'importance). La valeur par défaut n'est pas
Renvoie : Tuple contenait la meilleure solution et la meilleure valeur de fonction.
Vous pouvez définir votre valeur random_counts_by_predictors pour chaque prédicteur. Par exemple, si l'ensemble du prédicteur disponible ne contient que 3 à 5 valeurs, il est préférable de les vérifier tous; Mais s'il y a plus de 100 valeurs, il sera préférable d'en vérifier 20 à 40, pas 5. Voir l'exemple:
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 Paramètre greedy_step peut être important dans certaines tâches. Il peut être préférable d'utiliser greedy_step = 2 ou greedy_step = 3 au lieu de par défaut greedy_step = 1 . Et ce n'est pas un bon choix d'utiliser Big greedy_step si nous ne pouvons pas nous permettre d'évaluer plusieurs fois la fonction optimisée.
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
