牛刀小试系列-案例1：利用“智能优化算法炼丹炉” 设计改进算法，并应用于TSP问题求解
文章目录
- 牛刀小试系列-案例1：利用“智能优化算法炼丹炉” 设计改进算法，并应用于TSP问题求解
- 1.TSP问题数据
- 2.TSP问题
- 3.算法设计
- 4.实验对比
- 4.1 实验1
- 4.2 涨点实验
- 5.结语
摘要：利用“ 智能优化算法炼丹炉.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∑Adtiti+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” ，针对自己的应用发现更多的改进方法。希望该工具能帮助大家快速实现自己的实验！
