1

我有一个实现模拟退火的程序。我对接受概率有疑问，可能是因为我不明白为什么将欧拉数提高到（能量 - 能量）的幂是有用的。

即使温度非常低，概率也始终超过 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
4

1 回答 1

1

在您的示例输出中，如果新解决方案优于当前解决方案，概率将始终设置>= 1为1。

遵循@wiki（Kirkpatrick 等人）可用的经典原始公式（等同于您的；除了 if-else 行为）：

  • P(e, e', T) =
    • 1 if e' < e（如上所述）
    • exp(-(e' - e) / T否则
    • 在哪里：
      • e: 当前解决方案
      • e': 新的解决方案候选
      • T： 温度

一些例子：

  • T = 100000
    • 当前：0.666，新：0.555
      • 1作为e' < e
    • 当前：```0.555，新：0.666
      • ~0.99999889
  • T = 10
    • 当前：0.666，新：0.555
      • 1（T不会改变这个事实）
    • 当前：0.555，新：0.666
      • ~0.9889614

因此，只要每个新候选人更好，它仍然会进行完整的随机搜索以接受每个候选人。这是一个设计决定。但是当候选人比当前的解决方案更糟糕时，验收程序就很重要了。

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

于 2017-04-23T12:18:54.933 回答