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 回答