假设有三个取离散整数值的变量，如w1 = {1,2,3,4,5,6,7,8,9,10,11,12}， w2 = {1,2,3,4,5,6,7,8,9,10,11,12}， w3 ={1,2,3,4,5,6,7,8,9,10,11,12}。任务是从每个集合中选择一个值，使结果三元组最小化某个(黑盒，计算代价昂贵)代价函数。
我在Matlab中尝试了代理优化，但我不确定它是否合适。我也听说过模拟退火，但没有发现适用于这个实例的实现。
除了穷举搜索之外，哪个算法可以解决这个组合优化问题?
任何帮助都将非常感激。
模拟退火(SA)的要求/好处是，目标表面有些光滑，也就是说，我们可以接近解。
- 对于一个完全随机的尖刺表面-你不妨做一个随机搜索
- 如果是平滑的，甚至有时，尝试SA是有意义的。
这个想法是(有时)只改变3个值中的1个，我们对我们的黑盒函数几乎没有影响。
下面是一个模拟退火的基本示例，使用Python中的frigum
import numpy as np
w1 = np.array( [1,2,3,4,5,6,7,8,9,10,11,12] )
w2 = np.array( [1,2,3,4,5,6,7,8,9,10,11,12] )
w3 = np.array( [1,2,3,4,5,6,7,8,9,10,11,12] )
W = np.array([w1,w2,w3])
LENGTH = 12
我使用Rastrigin函数定义了一个黑盒。
def rastrigin_function_n( x ):
"""
N-dimensional Rastrigin
https://en.wikipedia.org/wiki/Rastrigin_function
x_i is in [-5.12, 5.12]
"""
A = 10
n = x.shape[0]
return A*n + np.sum( x**2- A*np.cos(2*np.pi * x) )
def black_box( x ):
"""
Transform from domain [1,12] to [-5,5]
to be able to push to rastrigin
"""
x = (x - 6.5) * (5/5.5)
return rastrigin_function_n(x)
模拟退火需要修改状态x，而不是直接获取/修改值，我们跟踪指标。这简化了创建新提案，因为索引总是一个整数，我们可以简单地加/减1模LENGTH。
def random_start():
"""
returns 3 random indices
"""
return np.random.randint(0, LENGTH, size=3)
def random_small_step(x):
"""
change only 1 index
"""
d = np.array( [1,0,0] )
if np.random.random() < .5:
d = np.array( [-1,0,0] )
np.random.shuffle(d)
return (x+d) % LENGTH
def random_big_step(x):
"""
change 2 indici
"""
d = np.array( [1,-1,0] )
np.random.shuffle(d)
return (x+d) % LENGTH
def obj(x):
"""
We have a triplet of indici,
1. Calculate corresponding values in W = [w1,w2,w3]
2. Push the values in out black-box function
"""
indices = x
values = W[np.array([0,1,2]), indices]
return black_box(values)
给它一个SA Scheme
import frigidum
local_opt = frigidum.sa(random_start=random_start,
neighbours=[random_small_step, random_big_step],
objective_function=obj,
T_start=10**4,
T_stop=0.000001,
repeats=10**3,
copy_state=frigidum.annealing.naked)
我不确定这个函数的最小值应该是什么，但它找到了一个目标，47.9095与指标np.array([9, 2, 2])
对于制冷机改变制冷计划，使用
alpha=.9。我的经验是，所有的实验工作哪种冷却方案效果最好并不会让它运行得更久一点。你提出的乘法(有时称为几何乘法)是标准的，也在冰箱中实现。所以要实现Tn+1 = 0.9*Tn，你需要一个alpha=.9。注意，这个冷却步骤是在N次重复之后完成的，所以如果repeats=100，它将首先做100个提案，然后再降低因子alpha当前状态的简单变化通常效果最好。由于最佳实践是将初始温度设置得足够高，以使大多数建议(>90%)被接受，因此步骤小并不重要。但如果你担心它太小了，那就尝试2到3个不同的版本。Frigidum接受一个建议函数列表，并且组合可以相互强制。
我没有MINLP的经验。但即便如此，很多时候实验也能让我们大吃一惊。所以，如果把另一个竞争对手带到谈判桌上的时间/成本很小，那就去吧!
尝试这三个值的每种可能组合，看看哪种组合的成本最低。