小蛇学python（2）两百行代码实现旅游中国34座大城市最短路
直接说基础语法，也许大家不会感兴趣。前言之后的这一章，给大家介绍一下我最近写出来的一个小功能。用python语言实现GA算法来解决TSP问题，希望以此来激发大家学习python的兴趣。
何为GA，何为TSP问题，我将会在以后准备写的算法专题里详细解释，这里不再赘述，文章将主要讲述算法思路，以及实现效果，并内附重要代码。
程序思路
python3.6+pycharm+Anaconda3.6外加了一个basemap包是我的编程环境。
遗传算法流程图.jpg
首先我创建了一个GA.py,用来实现解决TSP问题的GA算法。算法流程如上图大致所述。有关TSP问题的解决算法有很多，近似算法，模拟退火，遗传算法等等，已经是造好了的轮子，可以拿来就用，也可以自己实现一边，还是蛮有意思的。最重要的是要领会算法思想，体会它解决问题的思路。
实现算法核心后，再来实现程序主体TSP.py，即用算法将读取的城市信息进行处理计算，并最后可视化呈现出来。
程序整体架构.jpg
如图所示，先从txt文件中读取34个城市的经纬度，然后根据地球弧度以及角度计算出34个城市两两之间距离。将这个数据传递给GA算法类，类内部有一个适配函数计算，通过距离数据，进行交叉，变异，产生下一代等一系列操作。最终产生一个最优秀的个体，也就是遍历了34个城市后使路程距离最短的那个序列。
其实所谓交叉，变异等等就是说，在这个算法中，我们把一个数组当作个体，这个数组代表什么含义呢？就是城市先后顺序。交叉就是让两个数组交换一部分序列产生新数组，变异就是一个数组部分序列改变，自己变成新数组。注意的是，第一代个体中，要特意保留下来本来路径就是最短的数组，直接放到下一代中，如此循环往复，以求寻找到最佳数组序列。
在这里我设置了一个全局数组，即迭代足够多的次数后，将最后得到的个体，或者说数组储存在里面，再在画图函数中使用它，以求将最优数组展现在由basemap勾勒出的地图上。
最短路径实现图.jpeg
代码实现
def __init__(self, aLifeCount=100, ):
self.initCitys()
self.lifeCount = aLifeCount
self.ga = GA(aCrossRate=0.7,
aMutationRage=0.02,
aLifeCount=self.lifeCount,
aGeneLenght=len(self.citys),
aMatchFun=self.matchFun())
self.bestcityorder = []
这是初始化函数，其中self.bestcityorder即是我所说的全局数组，它起到一个在各个函数中间传递数据的中枢作用。此外，该初始化函数还初始化了GA算法的交叉概率，变异概率，以及适配函数等等。
这里面的self要特别提一下，它是一个关键字，它的意思是该类的一个实例化对象。相当于一个指针，才让全局数组起到畅通无阻的中枢作用。
def distance(self, order):
distance = 0.0
for i in range(-1, len(self.citys) - 1):
index1, index2 = order[i], order[i + 1]
city1, city2 = self.citys[index1], self.citys[index2]
distance += math.sqrt((city1[0] - city2[0]) ** 2 + (city1[1] - city2[1]) ** 2)
return distance
这个是距离计算函数，没什么好说的。
def run(self, n=0):
while n > 0:
self.ga.next()
distance = self.distance(self.ga.best.gene)
print(self.ga.best.gene)
print(("%d : %f") % (self.ga.generation-1, distance))
n -= 1
这是整个代码的核心关键，self.ga.next()即实现通过遗传变异以及接受上一代最优秀的个体组合形成下一代。n是迭代次数，我取的是100，即循环迭代一百次以寻求最优个体。最后将最有个体输出，并将该个体存储在全局数组中。
def mappath(self):
citylon1 = []
citylat1 = []
citylon2 = []
citylat2 = []
for i in self.bestcityorder:
temp = i[0]
i[0] = i[1]
i[1] = temp
# create new figure, axes instances.
fig = plt.figure()
ax = fig.add_axes([0, 0, 1, 1])
# setup mercator map projection.
m = Basemap(llcrnrlon=73.33, llcrnrlat=14.01, urcrnrlon=138.16, urcrnrlat=54.123, resolution='i',
projection='merc', lat_0=42.5, lon_0=120)
# nylat, nylon are lat/lon of New York
for i in self.bestcityorder:
citylon1.append(i[0])
citylat1.append(i[1])
for i in range(len(self.bestcityorder)):
if i == len(self.bestcityorder)-1:
citylon2.append(self.bestcityorder[0][0])
citylat2.append(self.bestcityorder[0][1])
else:
citylon2.append(self.bestcityorder[i + 1][0])
citylat2.append(self.bestcityorder[i + 1][1])
x, y = m(citylon1, citylat1)
m.scatter(x, y, marker='D', color='m')
# draw great circle route between NY and London
for i in range(len(self.bestcityorder)):
lon1 = citylon1[i]
lat1 = citylat1[i]
lon2 = citylon2[i]
lat2 = citylat2[i]
m.drawgreatcircle(lon1, lat1, lon2, lat2, linewidth=2, color='r')
m.drawcoastlines()
m.readshapefile('CHN_adm_shp/CHN_adm1', 'comarques', drawbounds=True)
#m.fillcontinents()
m.drawcountries()
# draw parallels
m.drawparallels(np.arange(10, 90, 20), labels=[1, 1, 0, 1])
# draw meridians
m.drawmeridians(np.arange(-180, 180, 30), labels=[1, 1, 0, 1])
ax.set_title('Great Circle the shortest path')
plt.show()
这个可以说是最长的一个函数了，其实它很简单，因为basemap画地图比较繁杂，所以代码也显得比较冗余。它实现了先在中国地图上用散点图函数标出34个城市，在利用传递过来的全局数组将里面的城市一个一个连起来。
大功告成，python是不是很简单？
可改进的地方
这个程序肯定不够实用，毕竟它计算的是直线距离。所以下一步我打算调用百度地图API爬取铁路数据，这个工程比较浩大，敬请期待哦～
大家也可以尝试一下，体验一把将代码融入生活的乐趣。
需要源码可以私信我，不要做伸手党，点个赞再来哦～
