2-opt其实是2-optimization的缩写，简言之就是两元素优化。也可以称作2-exchange 。（摘自百度百科）
这个一种随机性算法，基本思想就是随机取两个元素进行优化，一直到无法优化为止。在小规模TSP问题上，2-opt无论从效率还是效果上都优于蚁群算法。
最初这个算法就是在解决TSP问题上取得了比较好的成效，这里也以TSP问题为例。
TSP（旅行商）问题：假设有十一座城市，一位旅行商要经过这十一座城市并且最终返回出发的城市，求解最短的路线。
使用2-opt思想解决该问题的算法如下（首先设置参数最大迭代次数maxCount，初始化计数器count为0）：
- 随机选择一条路线（比方说是A->B->C->D->E->F->G），假设是最短路线min；
- 随机选择在路线s中不相连两个节点，将两个节点之间的路径翻转过来获得新路径，比方我们随机选中了B节点和E节点，则新路径为A->(E->D->C->B)->F->G，()部分为被翻转的路径;
- 如果新路径比min路径短，则设新路径为最短路径min，将计数器count置为0，返回步骤2，否则将计数器count加1，当count大于等于maxCount时，算法结束，此时min即为最短路径，否则返回步骤2;
在网上没能找到相关的python代码实现，于是我就自己粗糙地实现了一个（数据来源于某次华为杯数学建模竞赛）:
# -*- coding: utf-8 -*-
"""
Created on Fri Jul 21 13:47:57 2017
@author: 燃烧杯
"""
import numpy as np
import matplotlib.pyplot as plt
#在这里设置迭代停止条件，要多尝试一些不同数值，最好设置大一点
MAXCOUNT = 100
#数据在这里输入，依次键入每个城市的坐标
cities = np.array([
[256, 121],
[264, 715],
[225, 605],
[168, 538],
[210, 455],
[120, 400],
[96, 304],
[10,451],
[162, 660],
[110, 561],
[105, 473]
])
def calDist(xindex, yindex):
return (np.sum(np.power(cities[xindex] - cities[yindex], 2))) ** 0.5
def calPathDist(indexList):
sum = 0.0
for i in range(1, len(indexList)):
sum += calDist(indexList[i], indexList[i - 1])
return sum
#path1长度比path2短则返回true
def pathCompare(path1, path2):
if calPathDist(path1) <= calPathDist(path2):
return True
return False
def generateRandomPath(bestPath):
a = np.random.randint(len(bestPath))
while True:
b = np.random.randint(len(bestPath))
if np.abs(a - b) > 1:
break
if a > b:
return b, a, bestPath[b:a+1]
else:
return a, b, bestPath[a:b+1]
def reversePath(path):
rePath = path.copy()
rePath[1:-1] = rePath[-2:0:-1]
return rePath
def updateBestPath(bestPath):
count = 0
while count < MAXCOUNT:
print(calPathDist(bestPath))
print(bestPath.tolist())
start, end, path = generateRandomPath(bestPath)
rePath = reversePath(path)
if pathCompare(path, rePath):
count += 1
continue
else:
count = 0
bestPath[start:end+1] = rePath
return bestPath
def draw(bestPath):
ax = plt.subplot(111, aspect='equal')
ax.plot(cities[:, 0], cities[:, 1], 'x', color='blue')
for i,city in enumerate(cities):
ax.text(city[0], city[1], str(i))
ax.plot(cities[bestPath, 0], cities[bestPath, 1], color='red')
plt.show()
def opt2():
#随便选择一条可行路径
bestPath = np.arange(0, len(cities))
bestPath = np.append(bestPath, 0)
bestPath = updateBestPath(bestPath)
draw(bestPath)
opt2()
运行结果（只取了最后两行输出）：
1511.49908777
[0, 4, 3, 2, 1, 8, 9, 10, 7, 5, 6, 0]
运行结果
注：因为该算法具有随机性，所以每次运行的结果可能都有所不同，但是大多都是在1500~1600之内，要多运行几次比较一下取较好的结果，我上面给的运行结果就是我在几次运行中挑选得比较好的一次
关于调参：
本算法只有COUNTMAX一个参数，用于设置算法的停止条件，当算法已经连续COUNTMAX次没能得到更好的路径时便会停止，经过试验，一般设置大一些效果会比较好，但是大到一定程度的情况下再增大数值算法的效果也不会变得更好。
