2017-04-22 125 views
0

我有一個程序實現模擬退火。我對接受概率存在問題,可能是由於我不瞭解爲什麼將歐拉數提高到(能量 - 能量)的能力是有用的。Java模擬退火驗收概率

即使溫度很低,概率總是超過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 

回答

0

在您的例子輸出的概率永遠>= 1,因爲它是通常設置爲1,如果新的解決方案比現在的更好。

繼經典原配方(等同於你;除了如果其他行爲)可用@wiki(Kirkpatrick等人):

  • P(e, e', T) =
    • 1 if e' < e(如上文所述)
    • exp(-(e' - e)/T否則
    • 其中:
      • e:當前溶液
      • e':新的解決方案候選
      • T:溫度

一些例子:

  • T = 100000
    • 電流:0.666,新:0.555
      • 1e' < e
    • 電流:```0.555,新:0.666
      • ~0.99999889
  • T = 10
    • 當前:0.666,新:0。555
      • 1(T不會改變這一事實)
    • 電流:0.555,新:0.666
      • ~0.9889614

所以它仍然會做一個完整的隨機搜索接受ev只要每個新的候選人都更好。這是一個設計決定。但是當候選人比目前的解決方案更糟時,接受程序很重要。

對於其他方法/設計,您應該能夠找到大量資源。 Matlab seems to always accept better candidates too, but uses a different formula elsewise