python寻找波峰波谷算法（利用爬山法和迪杰斯特拉算法求解TSP最短路径）

爬山法和模拟退火算法通常用来求解TSP的最短路径问题。爬山法的一个最大的缺点就是，它只能获取一个局部最优的解，但是无法获取一个全局最优的解。而模拟退火算法，它以一定的概率接受较差的解，因此，可以在一定程度上避免局部最优的问题。而迪杰斯特拉算法虽然能够得到最短路径，但是由于需要大量的计算，比较消耗性能，因此，实际应用中并不多。关于爬山法和模拟退火算法的介绍，百度上不是很清楚，其他的一些资料上也介绍的不是很详细。找了一篇比较靠谱的解释和介绍，参见 http://www.cnblogs.com/JiePro/p/Metaheuristics_0.html 和 维基百科 https://zh.wikipedia.org/wiki/模拟退火）：

局部搜索是解决最优化问题的一种启发式算法。对于某些计算起来非常复杂的最优化问题，比如各种NP完全问题，要找到最优解需要的时间随问题规模呈指数增长，因此诞生了各种启发式算法来退而求其次寻找次优解，是一种近似算法（Approximate algorithms），以时间换精度的思想。局部搜索就是其中的一种方法。

对于组合问题，给出如下定义：

邻域动作是一个函数，通过这个函数，对当前解s，产生其相应的邻居解集合。例如：对于一个bool型问题，其当前解为：s = 1001，当将邻域动作定义为翻转其中一个bit时，得到的邻居解的集合N(s)={0001,1101,1011,1000}，其中N(s) ∈ S。同理，当将邻域动作定义为互换相邻bit时，得到的邻居解的集合N(s)={0101,1001,1010}.

2、过程描述

局部搜索算法从一个初始解开始，通过邻域动作，产生其邻居解，判断邻居解的质量，根据某种策略，来选择邻居解，重复上述过程，至到达终止条件。不同局部搜索算法的区别就在于：邻域动作的定义和选择邻居解的策略，也是决定算法好坏的关键（集中性和发散性，Intensification and Diversification）。

3、算法简介

对于优化问题相关算法有如下分类：

下文分别简单介绍几个局部搜索相关算法，也是基于个体的启发式算法（Single solution）。

3.1 爬山法（HILL-CLIMBING）

爬山法与Iterative Improvement的思想是一样的，区别在于前者寻找最大值，后者寻找最小值。一种完全的贪心的思想，有更好的，则选择更好的，没有更好的，则终止。

流程如上图所示，判断当前解s的邻居解质量，若其中有比当前解更好的解，则s = Improve(N(S))，令当前解等于邻居解中质量最好的解，重复上述过程，直至邻居解中没有更好的解为止。

缺点：很容易陷入局部极值，最终解的好坏与初始解的选择有很大关系。

我们今天要解决的一个场景就是有280个城市，已知他们的二维坐标。求从某个城市出发，遍历整个城市，并回到出发点的最短路径。测试数据从http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp/a280.tsp.gz 网上下载，格式如下：

算法的思路是：

1、计算所有节点两两之间的欧式距离，存放在二维数组中。

2、构建一个空的集合，作为最短路径的集合。一个值为0 的变量，作为最初始的最短路径值。

while 最短路径集合中的元素个数 <= 所有的节点数

do :

3、构建邻域。每次从所有节点中，如果原始的节点集合大于或等于10，则从原始节点集合中随机选择所有节点的十分之一个节点作为邻域。如果小于10，则用原始节点集合的个数对10取模的结果，作为邻域的节点个数。

4、如果最短路径的集合为空，则从邻域中随机选择一个。如果不为空，则选取最短路径集合中的最后一个元素，与邻域中的元素，依次计算其欧氏距离，选择距离最小的节点，添加到最短路径集合中，作为最短路径集合中的最后一个元素的下一个节点。同时，在原来的最短路径值的基础上，加上当前的最短路径。从原始的节点集合中，则删除当前选择的节点。

输出最短路径的节点序列及相应的最短路径值，并在坐标系中画出该最短路径

下面，我们开始采用python编程实现。关键代码如下：

## 计算任意两点间的距离

num = len(list)

arr = [[ col for col in range(num)] for row in range(num)]

valstr = ""

for row in range(num):

for col in range(num):

if col == row:

arr[row][col] = 0

else:

p1 = list[row]

p2 = list[col]

arr[row][col] = round(math.sqrt(math.pow((p1.x - p2.x),2) math.pow((p1.y - p2.y),2)),2) ### 求欧式距离，保留2位小数

## print the matrix for check

"""

for row in range(num):

for col in range(num):

if (col 1) == 0 :

print valstr "\n"

valstr = ""

valstr = str(arr[row][col]) ","

"""

print "爬山法查找最短路径："

### 参数：最小路径的最后一个节点和邻域

def valHillClimbSum(curnode,nextnodeList):

if nextnodeList == None or len(nextnodeList) < 1 :

print "empty"

return 0

maxcost = sys.maxint

retnode = 0

for node in nextnodeList:

# print "curnode : ",curnode ," node: " ,node ," mincost : ",mincost

if arr[curnode][node] < maxcost :

maxcost = arr[curnode][node]

retnode = node

else:

return (retnode,maxcost)

return (retnode,maxcost)

indexList = [ i for i in range(num)] ### 原始的节点序列

selectedList = [] ## 选择好的元素

### 具体思想是： 从剩余的元素中随机选择十分之一的元素，作为邻域。然后从邻域中选择一个元素作为已经构建好的最小路径的下一个节点，使得该路径

mincost = sys.maxint ###最小的花费

count = 0 ### 计数器

while count < num:

count = 1

### 构建一个邻域: 如果indexList中元素个数大于10个，则取样的个数为剩余元素个数的十分之一。否则为剩余元素个数对10的取余数

leftItemNum = len(indexList)

# print "leftItemNum:" ,leftItemNum

nextnum = leftItemNum//10 if leftItemNum >= 10 else leftItemNum

nextnodeList = sample(indexList,nextnum) ### 从剩余的节点中选出nextnum个节点

if len(selectedList) == 0 :

item = choice(nextnodeList)

selectedList.append(item)

indexList.remove(item)

mincost = 0

continue

curnode = selectedList[len(selectedList) - 1]

# print "nextnodeList:" ,nextnodeList

nextnode, cost = valSum(curnode,nextnodeList) ### 对待选的序列路径求和

### 将返回的路径值添加到原来的路径值上，同时，在剩余的节点序列中，删除nextnode节点

mincost = cost

indexList.remove(nextnode)

selectedList.append(nextnode)

print "最合适的路径为：" ,selectedList

print "路径节点个数：" ,len(selectedList)

print "最小花费为：" , mincost

print "尝试次数:", count

得到的计算结果为：

爬山法：

路径节点个数： 280

最小花费为： 23442.51

迪杰斯特拉算法：

路径节点个数： 280

最小花费为： 3222.45

将得到的结果序列在坐标系中画出来的效果分别如下：

爬山法得到的最短路径示意图

迪杰斯特拉算法得到的最短路径示意图

从上可以看出，采用爬山法得到的只是一个局部最优解，与采用迪杰斯特拉算法求得的全局最优解还是有相当的一段距离，但胜在效率高，计算复杂度低，因此，在实际应用中也较多。下一节我们将介绍用python实现模拟退火算法的问题。

,