| 主权项 |
一种基于改进粒子群算法的多路径规划方法，其特征在于，包括如下步骤：（1）利用贪心算法初始化粒子群，利用贪心算法，从每一个城市出发，选择与当前城市距离最近的城市作为下一个城市，遍历所有城市，得到N个初始的城市序列；（2）如果达到最大迭代次数转到步骤（5），如不满足则对种群进行更新，找到个体最好位置Pi<sub>best</sub>，以及全局最好位置G<sub>best</sub>；（3）更新所有粒子的位置；X<sub>temp</sub>=X<sub>i</sub>(k)+ωV<sub>i</sub>(k) 惯性分量V<sub>temp</sub>=c<sub>1</sub>(Pi<sub>best</sub>‑X<sub>temp</sub>) 个体极值X<sub>temp</sub>=X<sub>temp</sub>+V<sub>temp</sub> 更新粒子位置V<sub>temp</sub>=c<sub>2</sub>(G<sub>best</sub>‑X<sub>temp</sub>) 全局极值X<sub>temp</sub>=X<sub>temp</sub>+V<sub>temp</sub> 更新粒子位置X<sub>i</sub>(K+1)=c<sub>3</sub>variation(X<sub>temp</sub>) 位置变异，解开路径中有交叉部分V<sub>i</sub>(K+1)=X<sub>i</sub>(K+1)‑X<sub>i</sub>(k)； 计算粒子速度（4）采用模拟退火降温方法选择接受的粒子位置，以避免陷入局部最优解；初始温度设为最大迭代次数的三分之一，退火接受变坏解的概率设为温度与最大迭代次数的比值，退火系数取0.99；迭代次数加一，转到步骤（2）；（5）输出最优城市序列，并输出最短距离；（6）根据实际需求，对城市数据进行预处理；分如下两种情况：a对于只有一个出发城市的多路径问题，如果要计算出首发相连的N条路径，这N条路径除了出发城市相同外其余经过的城市各不相同，但覆盖所有城市，则需增加N个与出发城市位置相同的虚拟城市；b对于出发城市互不相同的多路径问题，则不需要进行预处理；（7）使用上述求解旅行商问题的算法计算出一条城市序列X=(x<sub>1</sub>,x<sub>2</sub>,…,x<sub>i</sub>,x<sub>v1</sub>,x<sub>j</sub>,…,x<sub>k</sub>,x<sub>v2</sub>,x<sub>l</sub>,…,x<sub>n</sub>)；假设需要计算两条路径，其中x<sub>v1</sub>和x<sub>v2</sub>代表两个虚拟城市或者出发城市；（8）将算出来的城市序列看成首尾相连的环状；城市序列中只要遇到虚拟城市或者出发城市就代表回到上一个出发城市，这样将环分割成多条路径，X<sub>1</sub>=(x<sub>v1</sub>,x<sub>j</sub>,…,x<sub>k</sub>,x<sub>v1</sub>)，X<sub>1</sub>=(x<sub>v2</sub>,x<sub>l</sub>,…,x<sub>n</sub>,x<sub>1</sub>,x<sub>2</sub>,…,x<sub>i</sub>,x<sub>v2</sub>)，得到最终需要的多条路径。 |
