寻找n元组，使昂贵的成本函数最小化。
寻找n元组，使昂贵的成本函数最小化。
提问于 2021-02-18 23:27:58
假设有三个变量具有离散整数值，例如w1 ={1，2，3，4，5，6，7，8，10，11，12}，w2 ={1，2，3，4，5，6，8，10，11，12}，w3 ={1，2，3，4，5，6，7，8，8，9，10，11，12}。任务是从每个集合中选择一个值，这样生成的三重态集就可以最小化一些(黑匣子，计算费用昂贵)的成本函数。
我已经在Matlab中尝试过代理程序优化，但我不确定它是否合适。我也听说过模拟退火，但发现没有应用于这个实例的实现。
除了穷举搜索之外，哪种算法能解决这个组合优化问题？
任何帮助都将不胜感激。
回答 2
Stack Overflow用户
回答已采纳
发布于 2021-02-25 08:41:27
模拟退火(SA)的要求/优点是，目标表面是光滑的，即我们可以接近一个解。
- 对于一个完全随机的尖面-你也可以做一个随机搜索。
- 如果它是平滑的，甚至有时，它是有意义的尝试SA。
我们的想法是，(有时)只改变三个值中的一个，我们对输出黑盒函数的影响很小。
下面是一个使用模拟退火的基本示例，使用Python中的刚玉
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我使用拉斯特里金函数定义了一个黑匣子.
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模长度。
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计划
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和indicis np.array([9, 2, 2])
编辑：
- 若要更改冷却计划，请使用
alpha=.9。我的经验是，所有的实验工作，其中的冷却方案最有效的，不超过重量，只是让它运行一段时间。您提出的乘法(有时称为几何学)是标准乘法，也是用冰箱实现的。因此，要实现Tn+1 = 0.9*Tn，您需要一个alpha=.9。注意这个冷却步骤是在N个重复之后完成的，所以如果repeats=100，它将首先做100个建议，然后用因子alpha降低温度。 - 当前状态的简单变化通常效果最好。既然它的最佳做法是将初始温度设定到足以使大多数建议(>90%)被接受，那么这些步骤并不重要。但如果你害怕它的soo很小，试试2或3个变体。Frigidum接受一个提议函数列表，并且组合可以相互强制执行。
- 我对MINLP没有经验。但即便如此，这么多次实验也会让我们大吃一惊。因此，如果把另一个竞争者带到谈判桌上的时间/成本很小，是的！
Stack Overflow用户
发布于 2021-02-18 23:38:30
尝试这三个值的每一个可能的组合，看看哪一个有最低的成本。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/66269659
复制相关文章
相似问题
腾讯云开发者
