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-else 行为）可用 @wiki（Kirkpatrick 等人）：

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 seems to always accept better candidates too, but uses a different formula elsewise.

Java 模拟退火验收概率

Java Simulated Annealing Acceptance Probability

java

search

heuristics

simulated-annealing

fitness