字符串匹配的模拟退火 Python

Question

我在使用 SA 实现字符串匹配算法时遇到了问题。完成所有迭代后，我并没有更接近我想要的字符串！我试图降低温度变化，但没有任何变化。

对我来说，我认为问题是因为 p 没有稳定下降。我认为的原因是 de 正在“随机”变化。我对吗？如果是，如何解决？

目标是最后得分达到0。该分数总结了随机字母与实际字母之间的所有距离。 change_cur_solution每次只改变一个随机字母。

def eval_current_sol(target,cur_sol): 
  dist = 0
  for i in range(len(target)): 
    c = cur_sol[i] 
    t = target[i] 
    dist += abs(ord(c) - ord(t)) 
  return dist 


t = 10000
# loop until match the target
it = 0
while True: 
    if t == 0:
       break
    print('Current best score ', bestScore, 'Solution', "".join(bestSol)) 
     
    if bestScore == 0: 
      break
     
    newSol = list(bestSol) 

    change_cur_solution(newSol)
    score = eval_current_sol(newSol,targetSol) 
    de =  score - bestScore

    if de < 0:                  ## score < bestScore i.e. (score of new solution < score of previous solution) ===> #better
        bestSol = newSol 
        bestScore = score
    else:
        r = random.random()
        try:
            p = math.exp(-(de / t))
        except:
            p = 0
        print("p is %f de is %d t is %d" %(p, de,t))
        if p > r:
            bestSol = newSol
            bestScore = score
    it += 1
    t -= 0.5
    
print('Found after, ',it, 'Iterations' )

这里是代码示例运行ning 当 t 约为 700

这是另一个示例运行最后：

注意：爬山时使用了类似的代码并且运行良好。

Answer 1

t -= 0.5

是线性散热。这通常不是最好的。 (?)你试过几何吗？

t = t * 0.95

当然，0.95 是一个猜测，您想探索差异 start/stop 温度组合和冷却系数。

字符串匹配的模拟退火 Python

Simulated Annealing for string matching with Python

python

artificial-intelligence

simulated-annealing