DiscreteHillClimbing download DiscreteHillClimbing源代码下载

离散的山坡

该软件包（来自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;可呼叫优化的功能使用numpy 1D阵列作为参数。
available_predictors_values ：INT序列每个预测指标的可用值列表（参数的每个尺寸）。
random_counts_by_predictors ：int或int序列，可选的每个变量应该使用多少随机选择？为每个预测变量使用list/numpy阵列（或选择每个预测指标的一个数字）。默认值为3。
greedy_step ：INT，可选的IT选择更好的解决方案在通过Greedy_Step预测器攀爬后。默认值为1。
start_solution ：无或int序列，算法启动时可选点。默认值无 - 随机启动解决方案
max_function_evals ：INT，功能评估的可选最大计数。默认值为1000。
maximize ：bool，可选的功能最大化？（默认情况下最小化）。默认值为false。
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