DiscreteHillClimbing
v1.1.0
このパッケージ（DPEAから）は、離散タスク用のヒルクライミングアルゴリズムの実装を提供します。
pip install DiscreteHillClimbing
ヒルクライミング（座標の最小化）は、離散タスクの最も簡単なアルゴリズムです（1つのシンプルは、完全にランダムからのみ最適になります）。離散タスクでは、各予測子は有限セットから値を持つことができます。したがって、予測子のすべての値（変数）またはその小さなランダムな部分ではない部分を確認し、1つの予測子による最適化を行うことができます。その後、別の予測因子などによって最適化できます。また、1、2、3、...予測子を使用してより良いソリューションを見つけて、最適な構成のみを選択することもできます。
ヒルクライミングを実現するには非常に多様な方法があるので、シンプルで普遍的な実装を作ろうとしました。確かに、（より高速な）実装を作成する方が自分のタスクの特定に依存する方が良い場合がありますが、このパッケージはSTARTに適した柔軟な選択肢です。
ヒルクライミングは、解決策を探し始めるときの完璧なベースラインです。それは本当に役立ち、50〜200の機能評価を使用して非常に良い結果を得ることができます。
この擬似コードでの私の実装の主なアイデアを参照してください。
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 ロードパッケージ：
import numpy as np
from DiscreteHillClimbing import Hill_Climbing_descent最適化された関数を決定します：
def func ( array : np . ndarray ) -> float :
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 ,
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;呼び出し可能な最適化関数は、引数としてnumpy 1D-Arrayを使用します。
available_predictors_values ：int sequence各予測子の使用可能な値のリスト（各引数の二量体）。
random_counts_by_predictors ：intまたはint sequence、オプションは、各変数に使用するランダム選択の数がいくつありますか？各予測子の選択オプションにリスト/numpy配列を使用します（または各予測子の1つの数値）。デフォルトは3です。
greedy_step ：int、optional it greedy_step予測子に登った後、より良いソリューションを選択します。デフォルトは1です。
start_solution ：noneまたはint sequence、オプションのポイントアルゴリズムが起動するとき。デフォルトはなしです - ランダム開始ソリューション
max_function_evals ：int、オプションの機能評価の最大カウント。デフォルトは1000です。
maximize ：ブール、オプションの機能を最大化しますか？ （デフォルトで最小化）。デフォルトはfalseです。
seed ：intまたはnone。ランダムシード（問題ではない場合）。デフォルトはなしです
返品：タプルには、最良のソリューションと最良の機能値が含まれていました。
uは、各予測子の異なるrandom_counts_by_predictors値を設定できます。たとえば、Predictor利用可能なセットに3〜5の値のみが含まれている場合、それらすべてを確認することをお勧めします。しかし、100以上の値がある場合は、5ではなく20-40を確認する方が良いでしょう。例を参照してください。
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パラメーターgreedy_step 、一部のタスクで重要です。デフォルトのgreedy_step greedy_step = 1の代わりに、greedy_step greedy_step = 2またはgreedy_step = 3使用する方が良い場合があります。そして、最適化された機能を何度も評価する余裕がない場合、Big greedy_stepを使用することは良い選択ではありません。
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
