智能优化算法应用：基于树种算法的TSP问题求解 - 附代码
文章目录
摘要：TSP是数学领域内一道著名的难题之一，如何求解一直是学术界研究的热点问题。本文利用树种算法对TSP进行求解。
1.TSP问题
现有对TSP问题的标准描述为：已知有城市数量为，一位旅行商人从其中的某一个城市出发，途中需要经过所有的城市，但经过的次数有且仅有一次，最后再回到出发的城市，怎样规划路线才能使旅行商所走的路线最短。
设城市集合为
V
=
v
1
,
v
2
,
.
.
.
,
v
A
V = {v_1,v_2,...,v_A}
V=v1,v2,...,vA，对城市的访问顺序为
T
=
t
1
,
t
2
,
.
.
.
,
t
A
T={t_1,t_2,...,t_A}
T=t1,t2,...,tA,其中
t
i
=
V
(
i
=
1
,
.
.
.
,
A
)
t_i = V(i = 1,...,A)
ti=V(i=1,...,A)而且
t
i
+
1
=
t
1
t_{i+1} = t_1
ti+1=t1,则问题的目标函数如下：
f
=
m
i
n
∑
i
=
1
A
d
t
i
t
i
+
1
(1)
f = min\sum_{i=1}^{A}d_{t_it_{i+1}} \tag{1}
f=mini=1∑Adtiti+1(1)
意为目标函数的最优值为所有途径城市之间的路径和最短。
3.树种算法
树种算法的具体原理参考博客：https://blog.csdn.net/u011835903/article/details/108830958。
适应度函数采用rankedorder value(ROV)规则的编码方式，即根据对数据按照升序规则进行排序，得到排序索引，然后根据索引作为路径计算路径长度，即为TSP的目标函数。
4.实验参数设定
树种算法参数如下：
%% 树种参数设定
pop=50; % 种群数量
Max_iteration=2000; %设定最大迭代次数
lb = 0; %上边界
ub = N*10;%下边界
dim = N; %维度
fobj = @(X) fun(X,PathCost);%适应度函数
5.算法结果
随机设定10个城市，作为TSP求解问题。如下图所示：
