智能优化算法应用:基于飞蛾扑火算法的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求解问题。如下图所示: