DiscreteHillClimbing
v1.1.0
Этот пакет (от DPEA) обеспечивает реализацию алгоритма восхождения на холм для дискретных задач.
pip install DiscreteHillClimbing
Подъем на холме ( минимизация координат ) является наиболее простым алгоритмом для дискретных задач (одно проще становится лучше всего от совершенно случайного). В дискретных задачах каждый предиктор может иметь свое значение из конечного набора, поэтому мы можем проверить все значения предиктора (переменная) или некоторую не небольшую случайную его часть и выполнять оптимизацию одним предиктором. После этого мы можем оптимизировать другим предиктором и так далее. Также мы можем попытаться найти лучшее решение, используя 1, 2, 3, ... предикторы и выбрать только лучшую конфигурацию.
Существует очень разнообразные способы реализации лазания на холме , поэтому я старался сделать простой и универсальную реализацию. Конечно, может быть лучше создать вашу (более быструю) реализацию, зависит от конкретной задачи, но этот пакет является хорошим гибким выбором для начала.
Подъем на холме - идеальная базовая линия, когда вы начинаете искать решение. Это действительно помогает, и это действительно может получить вам очень хороший результат, используя только 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; Оптимизированная функция Callible использует Numpy 1D-Array в качестве аргумента.
available_predictors_values : int Последовательность Список доступных значений для каждого предиктора (каждый размер аргумента).
random_counts_by_predictors : int или int -последовательность, необязательно, сколько случайных вариантов следует использовать для каждой переменной? Используйте список/Numpy Array для опции SELECT для каждого предиктора (или int - по одному номеру для каждого предиктора). По умолчанию 3.
greedy_step : int, необязательное выбор решения лучшего решения после восхождения по предикторам greedy_step. По умолчанию 1.
start_solution : none или int -последовательность, необязательная точка, когда начинается алгоритм. По умолчанию нет - Random Start Solution
max_function_evals : int, необязательный максимальный счет оценки функций. По умолчанию 1000.
maximize : Bool, необязательный максимизируйте функцию? (минимизировать по умолчанию). По умолчанию ложь.
seed : int или нет. Случайное семя (нет, если не имеет значения). По умолчанию нет
Возврат : кортеж содержал лучшее решение и лучшее значение функции.
Вы можете установить свое различное значение random_counts_by_predictors для каждого предиктора. Например, если доступный набор предиктора содержит только 3-5 значений, лучше проверить их все; Но если есть 100+ значений, будет лучше проверить 20-40 из них, а не 5. См. Пример:
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 = 2 или greedy_step = 3 вместо по умолчанию greedy_step = 1 . И это не хороший выбор использовать 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
