基于改进粒子群算法的多路径规划方法

摘要

本发明公开一种基于改进粒子群算法的多路径规划方法，在解决单路径规划中对粒子群算法做的改进的基础上，融合贪心算法、遗传算法和模拟退火算法的思想，使用贪心算法初始化粒子群算法，并且加入一种良好的变异算子与模拟退火思想。将算出来的路径看成首尾相连的环状，对于出发城市相同的多路径问题，要计算N条路径，就增加N个与出发城市位置相同的虚拟城市，路径中只要遇到虚拟城市就代表回到出发城市，这样将环分割成N条路径；对于出发城市不相同的多路径问题，则不用增加虚拟城市，所有的出发城市就起到了虚拟城市的作用。此多路径计算方法比原来的更简单且更具有通用性。

主权项

一种基于改进粒子群算法的多路径规划方法，其特征在于，包括如下步骤：(1)利用贪心算法初始化粒子群，利用贪心算法，从每一个城市出发，选择与当前城市距离最近的城市作为下一个城市，遍历所有城市，得到N个初始的城市序列；(2)如果达到最大迭代次数转到步骤(5)，如不满足则对种群进行更新，找到个体最好位置Pi_best，以及全局最好位置G_best；(3)更新所有粒子的位置；其中，X_i(k)为第i个粒子的当前位置，即第i个当前城市序列，ω,c₁,c₂,c₃为(0,1)之间的数，c₃variation(X)表示以概率c₃对X进行变异操作，X_i(K+1)为第i个粒子新的位置，即新生成的第i个城市序列；(4)采用模拟退火降温方法选择接受的粒子位置，以避免陷入局部最优解；初始温度设为最大迭代次数的三分之一，退火接受变坏解的概率设为温度与最大迭代次数的比值，退火系数取0.99；迭代次数加一，转到步骤(2)；(5)输出最优城市序列，并输出最短距离；(6)根据实际需求，对城市数据进行预处理；分如下两种情况：a对于只有一个出发城市的多路径问题，如果要计算出首发相连的N条路径，这N条路径除了出发城市相同外其余经过的城市各不相同，但覆盖所有城市，则需增加N个与出发城市位置相同的虚拟城市；b对于出发城市互不相同的多路径问题，则不需要进行预处理；(7)使用上述算法计算出一条城市序列X＝(x₁,x₂,…,x_i,x_v1,x_j,…,x_k,x_v2,x_l,…,x_n)；假设需要计算两条路径，其中x_v1和x_v2代表两个虚拟城市或者出发城市；(8)将算出来的城市序列看成首尾相连的环状；城市序列中只要遇到虚拟城市或者出发城市就代表回到上一个出发城市，这样将环分割成多条路径，X₁＝(x_v1,x_j,…,x_k,x_v1)，X₁^*＝(x_v2,x_l,…,x_n,x₁,x₂,…,x_i,x_v2)，得到最终需要的多条路径。