如何设计具有多个不同成本的模拟退火的接受概率函数？
我正在使用模拟退火来解决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）。 但我还没有尝试过。
I am using simulated annealing to solve an NP-complete resource scheduling problem. For each candidate ordering of the tasks I compute several different costs (or energy values). Some examples are (though the specifics are probably irrelevant to the question):
global_finish_time: The total number of days that the schedule spans.split_cost: The number of days by which each task is delayed due to interruptions by other tasks (this is meant to discourage interruption of a task once it has started).deadline_cost: The sum of the squared number of days by which each missed deadline is overdue.
The traditional acceptance probability function looks like this (in 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)
So far I have combined my first two costs into one by simply adding them, so that I can feed the result into acceptance_probability. But what I would really want is for deadline_cost to always take precedence over global_finish_time, and for global_finish_time to take precedence over split_cost.
So my question to Stack Overflow is: how can I design an acceptance probability function that takes multiple energies into account but always considers the first energy to be more important than the second energy, and so on? In other words, I would like to pass in old_cost and new_cost as tuples of several costs and return a sensible value .
Edit: After a few days of experimenting with the proposed solutions I have concluded that the only way that works well enough for me is Mike Dunlavey's suggestion, even though this creates many other difficulties with cost components that have different units. I am practically forced to compare apples with oranges.
So, I put some effort into "normalizing" the values. First, deadline_cost is a sum of squares, so it grows exponentially while the other components grow linearly. To address this I use the square root to get a similar growth rate. Second, I developed a function that computes a linear combination of the costs, but auto-adjusts the coefficients according to the highest cost component seen so far.
For example, if the tuple of highest costs is (A, B, C) and the input cost vector is (x, y, z), the linear combination is BCx + Cy + z. That way, no matter how high z gets it will never be more important than an x value of 1.
This creates "jaggies" in the cost function as new maximum costs are discovered. For example, if C goes up then BCx and Cy will both be higher for a given (x, y, z) input and so will differences between costs. A higher cost difference means that the acceptance probability will drop, as if the temperature was suddenly lowered an extra step. In practice though this is not a problem because the maximum costs are updated only a few times in the beginning and do not change later. I believe this could even be theoretically proven to converge to a correct result since we know that the cost will converge toward a lower value.
One thing that still has me somewhat confused is what happens when the maximum costs are 1.0 and lower, say 0.5. With a maximum vector of (0.5, 0.5, 0.5) this would give the linear combination 0.5*0.5*x + 0.5*y + z, i.e. the order of precedence is suddenly reversed. I suppose the best way to deal with it is to use the maximum vector to scale all values to given ranges, so that the coefficients can always be the same (say, 100x + 10y + z). But I haven't tried that yet.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
姆贝克什是对的。
你能将不同能量进行线性组合并调整系数吗？
可能对它们进行日志转换？
我已经使用 Metropolis-Hastings 完成了一些 MCMC。 在这种情况下，我定义了特定状态的（非标准化）对数似然（给定其先验），并且我找到了一种方法来澄清我对我想要的想法。
mbeckish is right.
Could you make a linear combination of the different energies, and adjust the coefficients?
Possibly log-transforming them in and out?
I've done some MCMC using Metropolis-Hastings. In that case I'm defining the (non-normalized) log-likelihood of a particular state (given its priors), and I find that a way to clarify my thinking about what I want.
我会从多目标进化算法 (MOEA) 中获取提示，如果所有目标同时通过您提供的
acceptance_probability函数，我会进行转换。 这将具有探索帕累托前沿的效果，就像标准模拟退火探索相同能量解决方案的平台一样。然而，这确实放弃了让第一个优先的想法。
您可能需要调整参数，例如给予其更高的初始温度。
I would take a hint from multi-objective evolutionary algorithm (MOEA) and have it transition if all of the objectives simultaneously pass with the
acceptance_probabilityfunction you gave. This will have the effect of exploring the Pareto front much like the standard simulated annealing explores plateaus of same-energy solutions.However, this does give up on the idea of having the first one take priority.
You will probably have to tweak your parameters, such as giving it a higher initial temperature.
我会考虑以下内容：
当然，计算概率的三个地方中的每一个都可以使用不同的函数。
I would consider something along the lines of:
Of course each of the three places you calculate the probability could use a different function.
这取决于您所说的“优先”是什么意思。
例如，如果
deadline_cost下降 0.001，但global_finish_time成本上升 10000，该怎么办？ 您是否返回 1.0，因为deadline_cost减少了，并且这优先于其他任何内容？这似乎是只有您才能做出的判断，除非您可以提供足够的项目背景信息，以便其他人可以提出自己的明智判断。
It depends on what you mean by "takes precedence".
For example, what if the
deadline_costgoes down by 0.001, but theglobal_finish_timecost goes up by 10000? Do you return 1.0, because thedeadline_costdecreased, and that takes precedence over anything else?This seems like it is a judgment call that only you can make, unless you can provide enough background information on the project so that others can suggest their own informed judgment call.