我正在使用模拟退火来解决 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）。但我还没有尝试过。