量子粒子群算法的研究及应用

发布时间：2020-07-12 04:45

【摘要】：由于使用传统方法求解复杂度较高的问题时具有一定局限,通过模拟群居性生物表现出的宏观群体智能行为,学习自然界的特定现象或隐藏规律而产生的群体智能优化算法(Population-based Intelligent Optimization,PIO)应运而生。随着学科间交叉的不断深入,量子计算与传统群体智能优化算法的结合使得各类量子群体智能优化算法不断被提出,而量子粒子群算法(Quantum-behaved Particle Swarm Optimization,QPSO)作为其中较为经典的方法,虽然通过对粒子群算法的进化搜索策略进行改进,在一定程度上提升了算法性能,但依然存在单个粒子搜索能力弱,全局搜索性能一般,易出现早熟收敛等缺点。本文将集中于量子粒子群算法的研究及应用,针对算法的不足进行改进,提出一种混合量子粒子群算法,进而对新算法进行优化,并利用新算法对柔性车间调度问题(Flexible Job Shop Scheduling,FJSP)进行求解。具体研究工作如下:1.针对现有算法在解决高维度复杂问题时存在的收敛精度低,搜索效率慢的不足,提出一种混合量子粒子群算法。首先,使用概率幅编码方式将个体进行编码,扩展粒子群搜索范围;然后,将量子粒子群算法的更新公式融入量子旋转门的旋转角公式中进行粒子位置的更新迭代;最后,使用常见的量子非门对算法进行变异。仿真结果表明,该方法能有效优化算法求解问题的结果,提升算法搜索效率。2.针对量子非门在变异过程中变异幅度大易造成最优解丢失的问题,提出一种基于莱维飞行的混合量子粒子群算法。利用莱维飞行所表现出的反常运输和非标准统计行为,使用结合莱维飞行的旋转门替换原本的非门进行变异。实验结果表明,莱维飞行的加入能够提升算法搜索的随机性,改善算法的早熟收敛,并保留较优种群。3.为扩展算法应用范围,将所提新算法应用于柔性车间调度问题并做出相应调整。首先,将算法应用于柔性车间调度问题中的工序排序子问题;然后,在机器选择过程中加入基于概率的随机选择方式;最后,在迭代过程中加入基于邻域搜索的精英保留策略。实验表明,各项改进方式对于提升算法解决柔性作业车间调度问题都具有积极作用。
【学位授予单位】：兰州理工大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：TP18
【图文】：

原理图,粒子群算法,中粒,原理

+ += +使得粒子如图2.1，能够在全局最优tjgbest、个体历史最优tijpbest以及原速度tijv的共同作用下产生新的速度，但由于粒子的速度会在短时间内迅速增大，甚至导致粒子最终离开可行解空间。为控制粒子的全局探索行为，文献[61]中加入了粒子速度的钳制，使其只能在有界的局限范围内移动，当粒子超出范围时，会被强制指定为速度边界值。如图2.2所示，t1ijx+表示了没有速度钳制情况下的情况，而1( )'tijx+显示了在速度钳制下粒子位置的移动情况。与此同时可知，速度边界值较大时有利于全局搜索

粒子群算法,粒子,边界值,搜索空间

导致粒子最终离开可行解空间。为控制粒子的全局探索行为，文献[61]中加入了粒子速度的钳制，使其只能在有界的局限范围内移动，当粒子超出范围时，会被强制指定为速度边界值。如图2.2所示，t1ijx+表示了没有速度钳制情况下的情况，而1( )'tijx+显示了在速度钳制下粒子位置的移动情况。与此同时可知，速度边界值较大时有利于全局搜索，较小时利于局部开发，但过大或过小都会带来风险，过大会使算法可能错过最好区域，过小会使算法无法充分搜索空间。而速度钳制的存在仍无法保证粒子在搜索空间内，也无法限制粒子的步子大小以限制发散行为。

飞行轨迹,伽马分布,求积分,算法模拟

3/21( ) exp[ ] ,0, ) 2 2( ) ( )0 ,ss sotherwiseγ γμμ π μ μ < < < ∞= 小步长，γ 为比例系数。动轨迹如图 4.1 所示，莱维飞行具有长尾渐1/xμ +，0 2< μ< 为莱维指数。具体来说，莱维于难求积分的逆，所以除一些特殊情况并无算法模拟。在 Mantegna 算法的思想下，参考义，莱维飞行的步长 s 为:1/usvβ=布：2~ (0, )uu Nσ ，v ~ N (0,1)，其中，2(1 [(1 uσ Γ += Γ + 准伽马分布。

【相似文献】