Java模拟退火接受概率

Question

我有一个程序实现模拟退火。我有一个接受概率的问题，可能是因为我不理解为什么把欧拉数提高到(能量-能量)的幂是有用的。

概率总是超过1.0 (100%)，即使温度很低，这实际上是一个随机搜索。如何将我的接受概率确定为sA的正常比率(在开始时接受一个更糟的解决方案的机会很高，在结束时接受一个更坏的解决方案的可能性很低)？

以下是方法代码：

if (mutatedSolutionFitness > originalSolutionFitness) {
        return 1.0;
    } else {
        System.out.println("Original solution fitness: "+originalSolutionFitness);
        System.out.println("Mutated solution fitness: "+mutatedSolutionFitness);
        System.out.println("Temperature: "+this.temperature);
        final double chance = Math.exp((originalSolutionFitness - mutatedSolutionFitness) / this.temperature);
        System.out.println("Math.exp((originalSolutionFitness - mutatedSolutionFitness) / this.temperature): "+chance);
        System.out.println();
        return chance;
    }

这是几次输出：

Original solution fitness: 0.6666666666666666
Mutated solution fitness: 0.5555555555555556
Temperature: 999998.000001
Math.exp((originalSolutionFitness - mutatedSolutionFitness) / this.temperature): 1.0000001111113395

Original solution fitness: 0.6666666666666666
Mutated solution fitness: 0.6666666666666666
Temperature: 999997.000003
Math.exp((originalSolutionFitness - mutatedSolutionFitness) / this.temperature): 1.0

Original solution fitness: 0.6666666666666666
Mutated solution fitness: 0.6666666666666666
Temperature: 999996.000006
Math.exp((originalSolutionFitness - mutatedSolutionFitness) / this.temperature): 1.0

Original solution fitness: 0.6666666666666666
Mutated solution fitness: 0.5555555555555556
Temperature: 999995.00001
Math.exp((originalSolutionFitness - mutatedSolutionFitness) / this.temperature): 1.0000001111116728

Original solution fitness: 0.6666666666666666
Mutated solution fitness: 0.4444444444444444
Temperature: 999994.0000149999
Math.exp((originalSolutionFitness - mutatedSolutionFitness) / this.temperature): 1.0000002222235802

Original solution fitness: 0.6666666666666666
Mutated solution fitness: 0.5555555555555556
Temperature: 999993.0000209998
Math.exp((originalSolutionFitness - mutatedSolutionFitness) / this.temperature): 1.000000111111895

Answer 1

在您的示例输出中，概率总是>= 1，因为如果新解决方案优于当前解决方案，则通常将设置为1。

遵循经典的原始公式(相当于您的公式；除了if-否则的行为)可用@维基 (Kirkpatrick等人)：

• P(e, e', T) =
  • 1 if e' < e (如上文所述)
  • 否则exp(-(e' - e) / T
  • 地点：
    • e：当前解决方案
    • e'：新的解决方案候选人
    • T：温度

​

​

下面是一些例子：

• T = 100000
  • 当前: 0.666，新: 0.555
    • 1 as e' < e

​

- current: ```0.555, new: 0.666  
    - `~0.99999889`

​

​

• T = 10
  • 当前: 0.666，新: 0.555
    • 1 (T不改变这一事实)

​

- current: 0.555, new: 0.666  
    - `~0.9889614`

​

​

因此，只要每个新的候选人都更好，它仍然会做一个完整的随机搜索--接受每一个候选人。这是一个精心设计的决定。但是，当候选人比目前的解决方案更糟糕时，接受程序很重要。

对于其他方法/设计，您应该能够找到大量的资源。Matlab似乎也总是接受更好的候选人，但在其他方面却使用了不同的公式。。