DiscreteHillClimbing
v1.1.0
Este pacote (da DPEA) fornece a implementação do algoritmo de escalada de montanhas para tarefas discretas.
pip install DiscreteHillClimbing
A escalada nas montanhas ( minimização de coordenadas ) é o algoritmo mais simples para tarefas discretas (um mais simples está ficando melhor com o melhor de totalmente aleatório). Em tarefas discretas, cada preditor pode ter seu valor do conjunto finito; portanto, podemos verificar todos os valores do preditor (variável) ou alguma parte aleatória não pequena e fazer otimização por um preditor. Depois disso, podemos otimizar por outro preditor e assim por diante. Também podemos tentar encontrar uma solução melhor usando 1, 2, 3, ... preditores e escolher apenas a melhor configuração.
Existe uma variedade de maneiras de realizar escalada nas montanhas , então tentei fazer apenas uma implementação simples e universal. Certamente, pode ser melhor criar sua implementação (mais rápida) depende de sua própria tarefa, mas este pacote é uma boa opção flexível para o início.
A escalada nas montanhas é a linha de base perfeita quando você começa a buscar solução. Realmente ajuda e realmente pode obter um resultado muito bom usando apenas 50-200 avaliações de funções.
Veja a idéia principal da minha implementação neste pseudocódigo:
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 Carregar pacotes :
import numpy as np
from DiscreteHillClimbing import Hill_Climbing_descentDetermine a função otimizada :
def func ( array : np . ndarray ) -> float :
return ( np . sum ( array ) + np . sum ( array ** 2 )) / ( 1 + array [ 0 ] * array [ 1 ])Determine conjuntos disponíveis para cada preditor :
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 ])
]Criar solução :
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; A função otimizada chamável usa o Numpy 1D-Array como argumento.
available_predictors_values : Int Sequence Uma lista de valores disponíveis para cada preditor (cada dimensão do argumento).
random_counts_by_predictors : int ou int sequência, opcional quantas opções aleatórias devem usar para cada variável? Use List/Numpy Array para selecionar opção para cada preditor (ou int - um número para cada preditor). O padrão é 3.
greedy_step : int, opcional, ele escolhe melhor solução depois de subir por preditores gananciosos. O padrão é 1.
start_solution : nenhuma ou sequência int, ponto opcional quando o algoritmo inicia. O padrão é nenhum - solução de início aleatório
max_function_evals : int, contagem máxima opcional de avaliações de funções. O padrão é 1000.
maximize : bool, opcional maximize a função? (minimizar por padrão). O padrão é falso.
seed : int ou nenhum. Semente aleatória (nenhuma se não importa). O padrão é nenhum
Retornos : a Tupla continha a melhor solução e o melhor valor da função.
Você pode definir seu valor diferente random_counts_by_predictors para cada preditor. Por exemplo, se o conjunto de pretitores disponível contiver apenas 3-5 valores, é melhor verificar todos eles; Mas se houver mais de 100 valores, será melhor verificar 20-40 deles, não 5. Veja o exemplo:
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 Parâmetro greedy_step pode ser importante em algumas tarefas. Pode ser melhor usar greedy_step = 2 ou greedy_step = 3 em vez de greedy_step = 1 . E não é uma boa opção usar o Big greedy_step se não podemos se dar ao luxo de avaliar a função otimizada várias vezes.
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
