详解Python使用模拟退火算法求解列表“最大值”

之前发过一个使用爬山算法的文章，请参考：Python使用爬山算法寻找序列“最大值”

模拟退火算法可以看作是爬山算法的一种改进，如果前方有更优解就前进，如果没有更优解就以一定概率前进。与简单的爬山算法相比，模拟退火算法有可能跳出局部而得到全局最优解，但也有可能得到更差的解，算法参数的设置非常重要。

def simAnnealingMax(lst, howFar):

'''

lst:待确定最大值的列表

howFar:爬山时能看到的“最远方”，越大越准确

'''

#由于切片是左闭右开区间，所以howFat必须大于1

assert howFar>1, 'parameter "howFar" must >1'

#从列表第一个元素开始爬

#如果已经到达最后一个元素，或者已找到局部最大值，结束

start = 0

ll = len(lst)

#随机走动的次数

times = 1

while start <= ll:

#当前局部最优解

m = lst[start]

#下一个邻域内的数字

loc = lst[start+1:start+howFar]

#如果已处理完所有数据，结束

if not loc:

return m

#下一个邻域的局部最优解及其位置

mm = max(loc)

mmPos = loc.index(mm)

#如果下一个邻域内有更优解，走过去

if m <= mm:

start += mmPos+1

else:

#如果下一个邻域内没有更优解，以一定的概率前进或结束

delta = (m-mm)/(m+mm)

#随机走动次数越多，对概率要求越低

if delta <= random()/times:

start += mmPos+1

times += 1

else:

return m

函数用法为：

from random import randint

lst = [randint(1, 100) for i in range(200)]

print(simAnnealingMax(lst, k))