如何设计具有多个不同成本的模拟退火的接受概率函数？

Question

我正在使用模拟退火来解决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.

所以我对Stack Overflow的问题是:我如何设计一个考虑多个能量的接受概率函数,但总是认为第一个能量比第二个能量更重要,依此类推？换句话说,我想通过old_cost和new_cost为一些费用元组和返回一个合理的值.

编辑:经过几天试验提出的解决方案后,我得出的结论是,对我来说唯一合适的方法是Mike Dunlavey的建议,尽管这会给成本组件带来许多其他困难.我实际上被迫将苹果与橙子进行比较.

所以,我付出了一些努力来"规范化"价值观.首先,deadline_cost是一个平方和,因此它呈指数增长,而其他组件线性增长.为了解决这个问题,我使用平方根来获得类似的增长率.其次,我开发了一个函数来计算成本的线性组合,但是根据到目前为止看到的最高成本组件自动调整系数.

例如,如果最高成本的元组是(A,B,C)并且输入成本向量是(x,y,z),则线性组合是BCx + Cy + z.这样,无论z有多高,它都不会比x值为1更重要.

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

让我感到有些困惑的一件事是,当最高成本为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。在这种情况下，我定义了特定状态的（非标准化）对数似然（给定其先验），并且我找到了一种方法来澄清我对我想要的想法。