本文目录一览：
模拟退火求tsp问题可以用python编程吗
模拟退火求tsp问题可以用python编程
也许最初设计 Python 这种语言的人并没有想到今天Python 会在工业和科研上获得如此广泛的使用。著名的自由软件作者Eric Raymond 在他的文章《如何成为一名黑客》中，将Python 列为黑客应当学习的四种编程语言之一，并建议人们从Python 开始学习编程。这的确是一个中肯的建议，对于那些从来没有学习过编程或者并非计算机专业的编程学习者而言，Python 是最好的选择之一。Python 第一次学习Python，我只用了不到二十分钟的时间，站在书店里把一本教初学编程的人学习Python 的书翻了一遍。也是从那时起，我开始被这种神奇的语言吸引。 Python 可以用来开发symbian 上的东西。 易用与速度的完美结合Python 是一种用起来很方便的语言，很多初学Java 的人都会被 Java 的CLASSPATH 搞得晕头转向，花上半天的时间才搞明白原来是CLASSPATH 搞错了自己的 Hello World 才没法运行。
python实现TSP问题的案例
import math
from os import path
import numpy as np
import matplotlib.pyplot as plt
class TSPInstance:
'''
设计一个类，实现从文件读入一个旅行商问题的实例
文件格式为：
city number
best known tour length
list of city position (index x y)
best known tour (city index starts from 1)
以文件01eil51.txt为例：
第一行51为城市数
第二行426为最优解的路径长度
第三行开始的51行为各个城市的序号、x坐标和y坐标
最后是最优解的访问城市系列（注意里面城市序号从1开始，而python的sequence是从0开始）
Eil51Tour.png是最优解的城市访问顺序图
'''
def __init__(self, file_name):
'''
从文件file_name读入旅行商问题的数据
'''
self.file_name=file_name
a= open(file_name)
# 城市数量
self.city_num = a.readline()
# 返回坐标 51行，3列
self.city = np.zeros((int(self.city_num), 3))
# x坐标
self.x = np.zeros(int(self.city_num))
# y坐标
self.y = np.zeros(int(self.city_num))
# 城市ID
self.id = np.zeros(int(self.city_num))
b = a.readlines()
for i, content in enumerate(b):
if i in range(1, 52 ):
# 单行赋值
self.city[i-1] = content.strip('\n').split(' ')
self.x[i-1] = self.city[i-1][1]
self.y[i-1] = self.city[i-1][2]
for i, content in enumerate(b):
if i in range(53, 104):
self.id[i - 53] = content.strip('\n')
@property
def citynum(self):
'''
返回城市数
'''
return self.city_num
@property
def optimalval(self):
'''
返回最优路径长度
'''
c = 0
i = 1
s = open(self.file_name)
str = s.readlines()
for content in str:
if i == 2:
c = content
i = i + 1
return c
@property
def optimaltour(self):
'''
返回最优路径
'''
tour = np.array(self.id)
return tour
def __getitem__(self, n):
'''
返回城市n的坐标,由x和y构成的tuple:(x,y)
'''
(x, y) = (self.x[n-1], self.y[n-1])
return (x, y)
def get_distance(self, n, m):
'''
返回城市n、m间的整数距离（四舍五入）
'''
u=int(self.x[n-1] - self.x[m-1])
v=int(self.y[n-1] - self.y[m-1])
dis = math.sqrt(pow(u,2) + pow(v,2))
return int(dis+0.5)
def evaluate(self, tour):
'''
返回访问系列tour所对应的路径程度
'''
dis = 0
for i in range(50):
dis += self.get_distance(int(tour[i]), int(tour[i + 1]))
dis += self.get_distance(int(tour[50]), int(tour[0]))
return dis
def plot_tour(self, tour):
'''
画出访问系列tour所对应的路径路
'''
for i in range(51):
x0,y0 = self.__getitem__(i)
plt.scatter(int(x0),int(y0),s=10,c='c')
#记住坐标点的画法
for i in range(len(tour)-1):
x1,y1 = self.__getitem__(int(tour[i]))
x,y = self.__getitem__(int(tour[i+1]))
plt.plot([x1,x],[y1,y],c='b')
x2,y2 = self.__getitem__(int(tour[0]))
x3,y3 = self.__getitem__(int(tour[len(tour)-1]))
plt.plot([x2,x3],[y2,y3],c='b')
plt.xlabel('x label')
plt.ylabel('y label')
plt.title("City access sequence diagram")
plt.plot()
plt.show()
if __name__ == "__main__":
file_name = path.dirname(__file__) + "/1.txt"
instance = TSPInstance(file_name)
print(instance.citynum)
print(instance.evaluate(instance.optimaltour))
print(instance.optimaltour)
print(instance.__getitem__(2))
print(instance.get_distance(0, 1))
instance.plot_tour(instance.optimaltour)
'''
output:
51
426
[ 1. 22. 8. 26. 31. 28. 3. 36. 35. 20. 2. 29. 21. 16. 50.
34. 30. 9. 49. 10. 39. 33. 45. 15. 44. 42. 40. 19. 41. 13.
25. 14. 24. 43. 7. 23. 48. 6. 27. 51. 46. 12. 47. 18. 4.
17. 37. 5. 38. 11. 32.]
(49.0, 49.0)
14
'''
其实解决TSP问题有很多方法，比如模拟退火算法，贪心算法，回溯算法等等。希望各位博友可以把你们的解决方法出现在评论区。
Python怎么做最优化
一、概观scipy中的optimize子包中提供了常用的最优化算法函数实现。我们可以直接调用这些函数完成我们的优化问题。optimize中函数最典型的特点就是能够从函数名称上看出是使用了什么算法。下面optimize包中函数的概览：1.非线性最优化fmin -- 简单Nelder-Mead算法fmin_powell -- 改进型Powell法fmin_bfgs -- 拟Newton法fmin_cg -- 非线性共轭梯度法fmin_ncg -- 线性搜索Newton共轭梯度法leastsq -- 最小二乘2.有约束的多元函数问题fmin_l_bfgs_b ---使用L-BFGS-B算法fmin_tnc ---梯度信息fmin_cobyla ---线性逼近fmin_slsqp ---序列最小二乘法nnls ---解|| Ax - b ||_2 for x=03.全局优化anneal ---模拟退火算法brute --强力法4.标量函数fminboundbrentgoldenbracket5.拟合curve_fit-- 使用非线性最小二乘法拟合6.标量函数求根brentq ---classic Brent (1973)brenth ---A variation on the classic Brent（1980）ridder ---Ridder是提出这个算法的人名bisect ---二分法newton ---牛顿法fixed_point7.多维函数求根fsolve ---通用broyden1 ---Broyden’s first Jacobian approximation.broyden2 ---Broyden’s second Jacobian approximationnewton_krylov ---Krylov approximation for inverse Jacobiananderson ---extended Anderson mixingexcitingmixing ---tuned diagonal Jacobian approximationlinearmixing ---scalar Jacobian approximationdiagbroyden ---diagonal Broyden Jacobian approximation8.实用函数line_search ---找到满足强Wolfe的alpha值check_grad ---通过和前向有限差分逼近比较检查梯度函数的正确性二、实战非线性最优化fmin完整的调用形式是：fmin(func, x0, args=(), xtol=0.0001, ftol=0.0001, maxiter=None, maxfun=None, full_output=0, disp=1, retall=0, callback=None)不过我们最常使用的就是前两个参数。一个描述优化问题的函数以及初值。后面的那些参数我们也很容易理解。如果您能用到，请自己研究。下面研究一个最简单的问题，来感受这个函数的使用方法：f(x)=x**2-4*x+8，我们知道，这个函数的最小值是4，在x=2的时候取到。from scipy.optimize import fmin #引入优化包def myfunc(x):return x**2-4*x+8 #定义函数x0 = [1.3] #猜一个初值xopt = fmin(myfunc, x0) #求解print xopt #打印结果运行之后，给出的结果是：Optimization terminated successfully.Current function value: 4.000000Iterations: 16Function evaluations: 32[ 2.00001953]程序准确的计算得出了最小值，不过最小值点并不是严格的2，这应该是由二进制机器编码误差造成的。除了fmin_ncg必须提供梯度信息外，其他几个函数的调用大同小异，完全类似。我们不妨做一个对比：from scipy.optimize import fmin,fmin_powell,fmin_bfgs,fmin_cgdef myfunc(x):return x**2-4*x+8x0 = [1.3]xopt1 = fmin(myfunc, x0)print xopt1printxopt2 = fmin_powell(myfunc, x0)print xopt2printxopt3 = fmin_bfgs(myfunc, x0)print xopt3printxopt4 = fmin_cg(myfunc,x0)print xopt4给出的结果是：Optimization terminated successfully.Current function value: 4.000000Iterations: 16Function evaluations: 32[ 2.00001953]Optimization terminated successfully.Current function value: 4.000000Iterations: 2Function evaluations: 531.99999999997Optimization terminated successfully.Current function value: 4.000000Iterations: 2Function evaluations: 12Gradient evaluations: 4[ 2.00000001]Optimization terminated successfully.Current function value: 4.000000Iterations: 2Function evaluations: 15Gradient evaluations: 5[ 2.]我们可以根据给出的消息直观的判断算法的执行情况。每一种算法数学上的问题，请自己看书学习。个人感觉，如果不是纯研究数学的工作，没必要搞清楚那些推导以及定理云云。不过，必须了解每一种算法的优劣以及能力所及。在使用的时候，不妨多种算法都使用一下，看看效果分别如何，同时，还可以互相印证算法失效的问题。在from scipy.optimize import fmin之后，就可以使用help(fmin)来查看fmin的帮助信息了。帮助信息中没有例子，但是给出了每一个参数的含义说明，这是调用函数时候的最有价值参考。有源码研究癖好的，或者当你需要改进这些已经实现的算法的时候，可能需要查看optimize中的每种算法的源代码。在这里：https:/ / github. com/scipy/scipy/blob/master/scipy/optimize/optimize.py聪明的你肯定发现了，顺着这个链接往上一级、再往上一级，你会找到scipy的几乎所有源码！
模拟退火算法每次的解为什么不一样?
模拟退火每次的解不同是很正常的，因为模拟退火本身是一种随机算法，转移向更差的解不是必然而是概率性的，也就是说每次执行算法时，执行过程转移到的解可能都是完全不一样的。
至于TSP问题，本身属于NP-hard问题，找不到存在多项式时间复杂度的解。
如果要求精确的解，目前可行的方法有枚举、分支限界、动态规划等，但这些方法适用的数据范围都很小，一旦数据规模变大，它们都将无能为力。
所以目前广泛使用的大都是一些随机算法，比如蚁群、遗传等，模拟退火就是其中的一种，这些算法的一大特点就是通过随机去逼近最优解，但也有可能得到错解。
只有穷举法可以保证得到最优解，但是穷举法在数据量比较大的时候运行时间通常是不能接受的，所以用了各种近似方法。
模拟退火算法新解的产生和接受可分为如下四个步骤：
第一步是由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。
第二步是计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计算目标函数差的最快方法。
第三步是判断新解是否被接受,判断的依据是一个接受准则，最常用的接受准则是Metropolis准则: 若ΔT0则接受S′作为新的当前解S，否则以概率exp(-ΔT/T)接受S′作为新的当前解S。
第四步是当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时，则在原当前解的基础上继续下一轮试验。
