0 
 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 个工作有 140 个不同的选项，第 7 个工作在 possible_solution 矩阵中有 30 个不同的选项。

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

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

4

1 回答 1

0

对于 SA：

  • 可以从任何随机起始状态 ( S) 开始。它不应该对解决方案有很大的影响，因为在退火的初始阶段，大多数随机建议都被接受，因为我们从高温开始T。因此可以使用任何随机开始状态，也可以从解决方案矩阵中选择赎金。
  • 在退火期间，您稍微修改当前的 starte S。不要随意选择一个新的状态Q，而是稍微修改S一下，比如说S*。
  • 有条件的，检查S*是否在可行区域内执行。要么只修改使其可行，要么在之后修复任何违规行为。
  • *S尝试选择有意义的邻居州。模仿人类为改善当前状况所做的事情，例如；选择一个没有很好安排的随机作业并随机重新分配资源。随机选择一个资源也可能有效。
  • 应该开始T使得大多数提案（> 90％）被接受。在退火期间使用调试来获得一些比例接受状态的感觉。T_stop当几乎没有新状态被接受时，同样选择。
  • 在T_start并且T_stop可以接受之后，开始尝试不同的建议。它们对解决方案的质量有很大的影响。（冷却方案只是几何，即T = T * alpha.0 < alpha < 1
于 2020-06-10T07:00:02.593 回答