optimization - 如何设计具有多个不同成本的模拟退火的验收概率函数？

Question

我正在使用simulated annealing解决NP完全资源调度问题。对于任务的每个候选排序，我计算了几种不同的成本(或能量值)。一些例子是(尽管具体细节可能与问题无关):

global_finish_time:计划跨越的总天数。

split_cost:每个任务由于其他任务的中断而延迟的天数(这是为了防止任务一旦开始就被中断)。

deadline_cost:每个错过的截止日期都过期的天数的平方和。

传统的接受概率函数如下所示(在Python中):

def acceptance_probability(old_cost, new_cost, temperature):
    if new_cost < old_cost:
        return 1.0
    else:
        return math.exp((old_cost - new_cost) / temperature)

到目前为止，我仅通过将它们的前两个成本加起来就将其合并为一个，以便可以将结果输入 acceptance_probability。但是我真正想要的是 deadline_cost始终优先于 global_finish_time，并且 global_finish_time优先于 split_cost。

因此，我对堆栈溢出的问题是:如何设计一个接受概率函数，该函数考虑多个能量，但始终认为第一个能量比第二个能量更重要，依此类推？换句话说，我想将 old_cost和 new_cost作为具有多个成本的元组传递，并返回一个有意义的值。

编辑:在对提议的解决方案进行了几天的试验之后，我得出结论，对我而言，唯一有效的唯一方法是Mike Dunlavey的建议，即使这会给具有不同单位的成本要素带来许多其他困难。我几乎被迫将苹果与橙子进行比较。

因此，我付出了一些努力来“标准化”值。首先， deadline_cost是平方和，因此它呈指数增长，而其他分量呈线性增长。为了解决这个问题，我使用平方根来获得相似的增长率。其次，我开发了一个函数，该函数可以计算成本的线性组合，但会根据迄今为止看到的最高成本构成自动调整系数。

例如，如果成本最高的元组为(A，B，C)，而输入成本向量为(x，y，z)，则线性组合为BCx + Cy + z。这样，无论z得到多高，x都不会比x值更重要。

当发现新的最大成本时，这会在成本函数中产生“锯齿”。例如，如果C上升，那么对于给定的(x，y，z)输入，BCx和Cy都将更高，因此成本之间的差异也将更高。更高的成本差异意味着验收几率会下降，就好像温度突然降低了一个额外的步骤。实际上，这不是问题，因为最大成本在开始时仅更新了几次，以后不再更改。我相信从理论上讲，这甚至可以证明收敛到正确的结果，因为我们知道成本将朝着更低的值(value)收敛。

让我有些困惑的是，当最大成本为1.0或更低(例如0.5)时会发生什么。对于最大向量(0.5，0.5，0.5)，这将给出线性组合0.5 * 0.5 * x + 0.5 * y + z，即优先顺序突然颠倒了。我认为最好的处理方法是使用最大向量将所有值缩放到给定范围，以便系数始终可以相同(例如100x + 10y + z)。但是我还没有尝试过。

Answer 1

乏味的是正确的。

您可以对不同能量进行线性组合并调整系数吗？

可能对它们进行日志转换，以进行输入和输出？

我已经使用Metropolis-Hastings完成了一些MCMC。在那种情况下，我要定义特定状态(鉴于其先验)的(非标准化)对数似然率，然后我找到了一种方法来阐明我对自己想要的东西的想法。