DiscreteHillClimbing
v1.1.0
Paket ini (dari DPEA) memberikan implementasi algoritma pendakian bukit untuk tugas -tugas diskrit.
pip install DiscreteHillClimbing
Panjat bukit ( minimalisasi koordinat ) adalah algoritma paling sederhana untuk tugas -tugas diskrit (yang lebih sederhana hanya mendapatkan yang terbaik dari sepenuhnya acak). Dalam tugas -tugas diskrit, setiap prediktor dapat memiliki nilai dari set terbatas, oleh karena itu kita dapat memeriksa semua nilai prediktor (variabel) atau beberapa bagian acak yang tidak kecil dan melakukan optimasi oleh satu prediktor. Setelah itu kita dapat mengoptimalkan dengan prediktor lain dan sebagainya. Kami juga dapat mencoba menemukan solusi yang lebih baik menggunakan 1, 2, 3, ... prediktor dan hanya memilih konfigurasi terbaik.
Ada berbagai cara untuk mewujudkan pendakian bukit , jadi saya mencoba membuat implementasi sederhana dan universal. Tentu saja, mungkin lebih baik untuk membuat implementasi (lebih cepat) Anda tergantung pada spesifik tugas Anda sendiri, tetapi paket ini adalah pilihan fleksibel yang baik untuk memulai.
Panjat bukit adalah garis dasar yang sempurna ketika Anda mulai mencari solusi. Ini sangat membantu dan benar-benar bisa mendapatkan hasil yang sangat baik dengan hanya menggunakan evaluasi fungsi 50-200.
Lihat ide utama implementasi saya di pseudocode ini:
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 Paket Muat :
import numpy as np
from DiscreteHillClimbing import Hill_Climbing_descentTentukan fungsi yang dioptimalkan :
def func ( array : np . ndarray ) -> float :
return ( np . sum ( array ) + np . sum ( array ** 2 )) / ( 1 + array [ 0 ] * array [ 1 ])Tentukan set yang tersedia untuk setiap prediktor :
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 ])
]Buat Solusi :
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; Fungsi yang dioptimalkan dapat dipanggil menggunakan array 1D numpy sebagai argumen.
available_predictors_values : Int Urutan Daftar nilai yang tersedia untuk setiap prediktor (setiap dimensi argumen).
random_counts_by_predictors : Int atau int urutan, opsional berapa banyak pilihan acak yang harus digunakan untuk setiap variabel? Gunakan Daftar/Numpy Array untuk opsi pilih untuk setiap prediktor (atau int - satu nomor untuk setiap prediktor). Standarnya adalah 3.
greedy_step : int, opsionalnya pilihan solusi yang lebih baik setelah mendaki oleh prediktor Greedy_step. Standarnya adalah 1.
start_solution : tidak ada atau urutan int, titik opsional saat algoritma dimulai. Standarnya tidak ada - solusi start acak
max_function_evals : int, jumlah maks opsional dari evaluasi fungsi. Standarnya adalah 1000.
maximize : bool, opsional memaksimalkan fungsi? (Minimalkan secara default). Standarnya false.
seed : int atau tidak sama sekali. Benih acak (tidak ada jika tidak masalah). Defaultnya tidak ada
Pengembalian : Tuple berisi solusi terbaik dan nilai fungsi terbaik.
Anda dapat mengatur nilai random_counts_by_predictors Anda yang berbeda untuk setiap prediktor. Misalnya, jika set prediktor yang tersedia hanya berisi 3-5 nilai, lebih baik memeriksa semuanya; Tetapi jika ada 100+ nilai, akan lebih baik untuk memeriksa 20-40 dari mereka, bukan 5. Lihat contoh:
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 bisa menjadi penting dalam beberapa tugas. Lebih baik menggunakan greedy_step = 2 atau greedy_step = 3 daripada default greedy_step = 1 . Dan itu bukan pilihan yang baik untuk menggunakan Big greedy_step jika kita tidak mampu mengevaluasi fungsi yang dioptimalkan berkali -kali.
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
