论文部分内容阅读
粒子群优化算法(Particle Swarm Optimization,PSO)是由美国的Eberhart和Kennedy在1995年提出的一种高效的并行优化算法。由于该算法具有深刻的智能背景,且简单、易实现,因此,一经提出便引起了许多学者的广泛关注,并在短短的几年里出现了大量的研究成果,现已成为研究的热点。目前,已提出了多种PSO的改进算法,被广泛应用于函数优化、神经网络训练、模式分类、模糊系统控制等领域。但其应用大多是连续优化问题,很少被用来解决离散问题,而现实生活中的许多工程实例只能抽象出离散模型,如典型的旅行商问题(Traveling Salesman Problem,TSP)、加工调度(Job-shop)问题等。因此,把基本粒子群算法的优势加以扩展用来求解离散优化问题便成为本文的研究内容。本文在现有研究成果的基础上,主要做了四个方面的工作:(1)以TSP问题为例,重新定义了基本离散粒子群算法(Discrete Particle Swarm Optimization,DPSO)的位置、速度公式,使其适宜求解离散问题,并探讨了DPSO的搜索性能。(2)根据生物界中物种在生存密度过大时个体会自动分散迁徙的特性,提出了一种自逃逸思想,并将其引入到DPSO中,增强群体的多样性。(3)将求解TSP问题的局部搜索算法(Subpath Ejection Chain,SEC)融合到DPSO中,加快算法的搜索速度。(4)对候选边的产生方法进行改进,进一步提高算法的收敛速度。本文通过大量仿真实验证实了上述工作的正确性,取得了如下几方面的研究成果:(1)提出一种自逃逸混合离散粒子群算法(Self-escape Hybrid Discrete Particle Swarm Optimization,SEHDPSO),它融合了自逃逸思想和SEC的思想,很好的克服了DPSO容易陷入局部极小和收敛速度慢的缺陷。用算法SEHDPSO和混合蚁群算法(ACS+2-OPT)分别对TSP标准测试集中的26个典型实例进行仿真。结果显示,随着规模的增加,SEHDPSO具有明显的优势,尤其在实例U724上,SEHDPSO不仅搜索精度远高于ACS+2-OPT,而且收敛到当前最优解的时间不到ACS+2-OPT的十分之一。从26个实例的平均误差、最小误差和运行时间来看,SEHDPSO分别是ACS+2-OPT的35%、29%和26.6%。(2)对5-最邻近边法进行改进,提出的5-相对最邻近边法能生成一个更有效、规模更小的候选边集合。后者生成的候选边集合规模更小,只有前者的五分之四左右,(3)对自逃逸思想和生成候选边集合的方法进行了改进,提出了一种增强自逃逸离散粒子群算法(Reinforced Self-Escape Discrete Particle Swarm Optimization,RSEHDPSO)。用RSEDPSO算法对TSP实例的仿真结果表明,RSEDPSO具有更好的搜索速度和精度。从26个实例的平均误差、最小误差和运行时间来看,RSEDPSO分别是ACS+2-OPT的33.3%、25%和24.8%。最后,把RSEDPSO用于求解固定货架的拣选作业优化问题,并把仿真结果与混合遗传算法作了比较,结果表明RSEDPSO的各项指标均优于混合遗传算法。