如何改进用于作业计划的 SA 算法?

Question

objective: max sum(solution(i,9))
---------------------------------------------
while T>Tmin
for iteration=100
for i=1:61
function(generate_possible_solutions)
random_value = generate random value
solution(i) = generate_possible_solution(random_value, :)
feasible = sum(solution(i, 9))
next
SA:
check feasible
if feasible > previous_feasible
update best
else 
check acceptance function
end
if iteration == limit
update (T)
end
end For
end While

代码在上面。

我在工作安排方面有问题。我的启发式算法使用矩阵possible_solution将每个作业分配给一行。例如，第 6 个作业在possible_solution矩阵中有 140 个不同的选项，第 7 个作业有 30 个不同的选项。

在模拟退火中，在每次迭代中，我随机使用其中一条解线进入possible_solution矩阵。但是，与 GAMS/Cplex 求解器相比，该解决方案最多达到 50%。

我可以使用溶液矩阵中的随机选择来使用模拟退火吗？ 我错过了什么？

Answer 1

对于 SA：

• 可以从任何随机启动状态(S(开始。它不应该对溶液产生很大的影响，因为在退火的初始阶段，大多数随机建议都被接受，因为我们从高温T开始。因此，可以使用任何随机启动状态，也可以从解决方案矩阵中选择赎金。
• 在退火过程中，您稍微修改当前起始S。不要随便Q选择一个新的状态，而是稍微修改一下S，比如S*。
• 有条件的情况下，检查强制S*在可行区域内。要么只修改使其可行，要么事后修复任何违规行为。
• 尝试选择有意义的邻居州*S。模仿人类会做些什么来改善当前的情况，例如;随机选择一个计划不好的作业，随机重新分配资源。随机选择资源也可能有效。
• 应该开始T以便大多数提案(>90%(被接受。在退火期间使用调试来获得一些比例接受状态的感觉。同样选择T_stop几乎没有接受新状态时。
• 在T_start和T_stop可以接受之后，开始尝试不同的建议。它们对溶液的质量有很大的影响。(冷却方案仅几何形状，即T = T * alpha与0 < alpha < 1.