DiscreteHillClimbing
v1.1.0
Dieses Paket (von DPEA) bietet die Implementierung des Hill Climbing Algorithmus für diskrete Aufgaben.
pip install DiscreteHillClimbing
Hill Climbing ( Koordinatenminimierung ) ist der einfachste Algorithmus für diskrete Aufgaben (einer einfacher wird das Beste von vollständig zufällig am besten). Bei diskreten Aufgaben kann jeder Prädiktor seinen Wert aus dem endlichen Satz haben. Daher können wir alle Werte des Prädiktors (variabel) oder einen nicht kleinen zufälligen Teil davon überprüfen und eine Optimierung durch einen Prädiktor durchführen. Danach können wir durch einen anderen Prädiktor optimieren und so weiter. Außerdem können wir versuchen, eine bessere Lösung mit 1, 2, 3, ... Prädiktoren zu finden und nur die beste Konfiguration zu wählen.
Es gibt eine Vielzahl von Möglichkeiten, um das Klettern des Hills zu verwirklichen. Deshalb habe ich versucht, einfach eine einfache und universelle Implementierung zu machen. Mit Sicherheit kann es besser sein, Ihre (schnellere) Implementierung zu erstellen, hängt von spezifisch für Ihre eigene Aufgabe ab, aber dieses Paket ist eine gute flexible Wahl für den Start.
Das Klettern des Hügels ist die perfekte Grundlage, wenn Sie anfangen, Lösung zu suchen. Es hilft wirklich und kann Sie wirklich ein sehr gutes Ergebnis mit nur 50 bis 200 Funktionsbewertungen erzielen.
Sehen Sie sich die Hauptidee meiner Implementierung in diesem Pseudocode an:
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 Pakete laden :
import numpy as np
from DiscreteHillClimbing import Hill_Climbing_descentBestimmen Sie optimierte Funktion :
def func ( array : np . ndarray ) -> float :
return ( np . sum ( array ) + np . sum ( array ** 2 )) / ( 1 + array [ 0 ] * array [ 1 ])Bestimmen Sie die verfügbaren Sets für jeden Prädiktor :
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 ])
]Lösung erstellen :
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; Callable Optimized Function verwendet Numpy 1D-Array als Argument.
available_predictors_values : Int -Sequenz Eine Liste der verfügbaren Werte für jeden Prädiktor (jede Dimension des Arguments).
random_counts_by_predictors : int oder int sequence, optional Wie viele zufällige Auswahl sollte es für jede Variable verwenden? Verwenden Sie die Liste/Numpy -Array für die Auswahloption für jeden Prädiktor (oder int - eine Nummer für jeden Prädiktor). Der Standard ist 3.
greedy_step : Int, optionale IT -Auswahl bessere Lösung nach dem Klettern durch Greedy_Step -Prädiktoren. Der Standard ist 1.
start_solution : Keine oder int -Sequenz, optionaler Punkt, wenn der Algorithmus startet. Die Standardeinstellung ist keine - zufällige Startlösung
max_function_evals : int, optionale maximale Anzahl von Funktionsbewertungen. Der Standard ist 1000.
maximize : bool, optional die Funktion maximieren? (standardmäßig minimieren). Der Standard ist falsch.
seed : int oder keine. Zufälliger Samen (keine, wenn keine Rolle spielt). Der Standard ist keine
Rückgaben : Tupel enthielt die beste Lösung und den besten Funktionswert.
Sie können Ihren unterschiedlichen Wert random_counts_by_predictors für jeden Prädiktor festlegen. Wenn beispielsweise der verfügbare Prädiktor-Satz nur 3-5 Werte enthält, ist es besser, alle zu überprüfen. Wenn es jedoch über 100 Werte gibt, ist es besser, 20-40 davon zu überprüfen, nicht 5. Siehe Beispiel:
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 Parameter greedy_step kann bei einigen Aufgaben wichtig sein. Es kann besser sein, greedy_step = 2 oder greedy_step = 3 anstelle von Standard greedy_step = 1 zu verwenden. Und es ist keine gute Wahl, Big greedy_step zu verwenden, wenn wir es uns nicht leisten können, optimierte Funktionen mehrmals zu bewerten.
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
