牛刀小试系列-案例1：利用“智能优化算法炼丹炉” 设计改进算法，并应用于TSP问题求解

牛刀小试系列-案例1：利用“智能优化算法炼丹炉” 设计改进算法，并应用于TSP问题求解

摘要：利用“ 智能优化算法炼丹炉.exe” 设计一种改进算法，要求多次TSP问题求解的路径长度，均小于海鸥算法TSP求解。

1.TSP问题数据

TSP坐标数据点如下：

x = np.array([5,43,46,94,62,45,82,31,20,91]) # x坐标 y = np.array([18,51,40,31,34,19,22,8,99,57]) # y坐标

2.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_1ti+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∑A​dti​ti+1​​(1)
意为目标函数的最优值为所有途径城市之间的路径和最短。

3.算法设计

根据个人经验，改进算法：以粒子群算法打底，引入种群变异（Iterative混沌映射），简单改进应该就可以取得不错的结果。
打开“智能优化算法炼丹炉v1.1”,选择策略，生成改进算法MyOptAlgFunc.py

4.实验对比

本文将改进的优化算法与海鸥算法TSP进行对比
实验参数设置如下：

# 优化算法参数设置 pop = 30 # 种群数量 MaxIter = 100 # 最大迭代次数 dim = N # 维度 lb = 0*np.ones(dim) # 下边界 ub = N*np.ones(dim) # 上边界 fobj = fun

种群数量30，最大迭代次数100.

4.1 实验1

实验采用多次实验（本文设置20次），统计算法结果，主要指标包括：算法平均路径长度，路径标准差（衡量多次实验，各结果的离散程度，标准差越小，算法越稳定），多次实验最优路径长度，多次实验最差路径长度

从结果来看，改进算法明显优于海鸥算法结果

4.2 涨点实验

虽然PSO+Iterative已经取得了不错的结果，还有改进的空间，简单再增加一个只对最优位置的Levy改进，相信可以得到更好的结果。
还是打开“智能优化算法炼丹v1.1.exe” 阶段6选择Lvey飞行策略

将生成的代码与海鸥算法求解TSP问题进行求解

实验结果如下：

从结果来看改进策略是有效的。

5.结语

上述案例只是一个简单的改进，相信还有更好的融合改进策略，大家可以通过“智能优化算法炼丹炉v1.1” ，针对自己的应用发现更多的改进方法。希望该工具能帮助大家快速实现自己的实验！