遗传TSP问题如何固定起点和终点？

[morestart]

现在输出是一个闭环，没有考虑起终点

[guofei9987]

改变目标函数就可以了，有一个更复杂的案例 #26

[guofei9987]

下面这个是起点终点不闭合，但是起点终点也由算法选取：

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
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], routine[i + 1]] for i in range(num_points-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_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 = 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()

[morestart]

感谢大佬，我研究学习一下

[00-z]

请问如果，中间点数量确定，位置不确定有办法解决么

[guofei9987]

请问如果，中间点数量确定，位置不确定有办法解决么

那最优就是个直线吧

如果每段带权重的话，可以把每个点的坐标也加入到变量中参与优化。

[anheraco]

How should I define the function to fix this variant of the problem with ACA_TSP? Thank you very much