[人工智能]利用scikit-opt库中的GA遗传优化算法解决旅行商问题TSP（含自定义起终点）

scikit-opt库简介

官网
是一个封装了7种启发式算法的 Python 代码库，包含差分进化算法、遗传算法、粒子群算法、模拟退火算法、蚁群算法、鱼群算法、免疫优化算法。

一：编写自定义问题

主要是将自己问题的数据输入到封装的代码中，操作简单，修改码量很少
其中只有两行代码需要修改

num_points = 30###num_points指需要遍历的节点个数
points_coordinate = np.random.rand(num_points, 2)points_coordinate是自定义问题中的节点坐标信息 

完整代码

import numpy as np
from scipy import spatial
import matplotlib.pyplot as plt
####需要修改部分###########################################################################
###num_points指需要遍历的节点个数
num_points = 30
###points_coordinate是自定义问题中的节点坐标信息，为矩阵结构。这里只是利用random模块生成随机数据
points_coordinate = np.random.rand(num_points, 2) 
#################################################################################################################
###distance_matrix是自定义节点中任意两点间的距离
###其中的metric参数是可选择的距离度量方式
distance_matrix = spatial.distance.cdist(points_coordinate, points_coordinate, metric='euclidean')
###官方参数说明
'''
metric : str or callable, optional
        The distance metric to use. If a string, the distance function can be
        'braycurtis', 'canberra', 'chebyshev', 'cityblock', 'correlation',
        'cosine', 'dice', 'euclidean', 'hamming', 'jaccard', 'jensenshannon',
        'kulsinski', 'mahalanobis', 'matching', 'minkowski', 'rogerstanimoto',
        'russellrao', 'seuclidean', 'sokalmichener', 'sokalsneath',
        'sqeuclidean', 'wminkowski', 'yule'.
'''
###这个函数是计算一条路径的总距离
def cal_total_distance(routine):
    '''The objective function. input routine, return total distance.
    cal_total_distance(np.arange(num_points))
    '''
    num_points, = routine.shape
    return sum([distance_matrix[routine[i % num_points], routine[(i + 1) % num_points]] for i in range(num_points)])

二：调用遗传算法进行求解

其中的best_points表示最短距离的num_points点的序列（即points_coordinate矩阵中第几个点，但没有回到起点）

from sko.GA import GA_TSP

ga_tsp = GA_TSP(func=cal_total_distance, n_dim=num_points, size_pop=50, max_iter=500, prob_mut=1)
best_points, best_distance = ga_tsp.run()

三：绘制近似最优路径图像

其中的best_points_ 表示从起点出发并回到起点的路径。
（其实与best_points差别就是在best_points后加入起点（best_points的第一个点））

fig, ax = plt.subplots(1, 2)
best_points_ = np.concatenate([best_points, [best_points[0]]])
best_points_coordinate = points_coordinate[best_points_, :]
ax[0].plot(best_points_coordinate[:, 0], best_points_coordinate[:, 1], 'o-r')
ax[1].plot(ga_tsp.generation_best_Y)
plt.show()

整体代码

import numpy as np
from scipy import spatial
import matplotlib.pyplot as plt

num_points = 50

points_coordinate = np.random.rand(num_points, 2)  # generate coordinate of points
distance_matrix = spatial.distance.cdist(points_coordinate, points_coordinate, metric='euclidean')


def cal_total_distance(routine):
    '''The objective function. input routine, return total distance.
    cal_total_distance(np.arange(num_points))
    '''
    num_points, = routine.shape
    return sum([distance_matrix[routine[i % num_points], routine[(i + 1) % num_points]] for i in range(num_points)])


# %% do GA

from sko.GA import GA_TSP

ga_tsp = GA_TSP(func=cal_total_distance, n_dim=num_points, size_pop=50, max_iter=500, prob_mut=1)
best_points, best_distance = ga_tsp.run()

# %% plot
fig, ax = plt.subplots(1, 2)
best_points_ = np.concatenate([best_points, [best_points[0]]])
best_points_coordinate = points_coordinate[best_points_, :]
ax[0].plot(best_points_coordinate[:, 0], best_points_coordinate[:, 1], 'o-r')
ax[1].plot(ga_tsp.generation_best_Y)
plt.show()

四：如何自定义起点或终点

其实上面的代码已经求出了一条回到起点的路径，用best_points_变量表示。
那么只需正常运行前述代码，然后观察best_points_结果，找到起点，起点与两个点相连，只需切断较长的那一条即可。（未必最优）

五：如何自定义起点和终点

这里的代码和前面的代码基本一致，主要是在自定义问题有部分修改

start_point=[[0,0]]###定义起点
end_point=[[1,1]]###定义终点
num_points = 20###除去起终点外的点数
points_coordinate=np.concatenate([points_coordinate,start_point,end_point])

整体代码

import numpy as np
from scipy import spatial
import matplotlib.pyplot as plt

num_points = 20
####需要修改代码##################################################################################
points_coordinate = np.random.rand(num_points, 2)  # generate coordinate of points
start_point=[[0,0]]###定义起点
end_point=[[1,1]]###定义终点
##################################################################################
points_coordinate=np.concatenate([points_coordinate,start_point,end_point])
distance_matrix = spatial.distance.cdist(points_coordinate, points_coordinate, metric='euclidean')


def cal_total_distance(routine):
    '''The objective function. input routine, return total distance.
    cal_total_distance(np.arange(num_points))
    '''
    num_points, = routine.shape
    # start_point,end_point 本身不参与优化。给一个固定的值，参与计算总路径
    routine = np.concatenate([[num_points], routine, [num_points+1]])
    return sum([distance_matrix[routine[i], routine[i + 1]] for i in range(num_points+2-1)])
    from sko.GA import GA_TSP

ga_tsp = GA_TSP(func=cal_total_distance, n_dim=num_points, size_pop=50, max_iter=500, prob_mut=1)
best_points, best_distance = ga_tsp.run()


fig, ax = plt.subplots(1, 2)
best_points_ = np.concatenate([[num_points],best_points, [num_points+1]])
best_points_coordinate = points_coordinate[best_points_, :]
ax[0].plot(best_points_coordinate[:, 0], best_points_coordinate[:, 1], 'o-r')
ax[1].plot(ga_tsp.generation_best_Y)
plt.show()