离散粒子群算法的改进研究及其在优化问题中的应用

摘要

粒子群优化算法(Particle Swarm Optimization，PSO)是由美国的Eberhart和Kennedy在1995年提出的一种高效的并行优化算法。由于该算法具有深刻的智能背景，且简单、易实现，因此，一经提出便引起了许多学者的广泛关注，并在短短的几年里出现了大量的研究成果，现已成为研究的热点。目前，已提出了多种PSO的改进算法，被广泛应用于函数优化、神经网络训练、模式分类、模糊系统控制等领域。但其应用大多是连续优化问题，很少被用来解决离散问题，而现实生活中的许多工程实例只能抽象出离散模型，如典型的旅行商问题(Traveling Salesman Problem，TSP)、加工调度(Job-slmp)问题等。因此，把基本粒子群算法的优势加以扩展用来求解离散优化问题便成为本文的研究内容。 本文在现有研究成果的基础上，主要做了四个方面的工作： (1) 以TSP问题为例，重新定义了基本离散粒子群算法(Discrete Particle SwarmOptimization，DPSO)的位置、速度公式，使其适宜求解离散问题，并探讨了DPSO的搜索性能。 (2) 根据生物界中物种在生存密度过大时个体会自动分散迁徙的特性，提出了一种自逃逸思想，并将其引入到DPSO中，增强群体的多样性。 (3) 将求解TSP问题的局部搜索算法(subpath Ejection Chain，SEC)融合到DPSO中，加快算法的搜索速度。 (4) 对候选边的产生方法进行改进，进一步提高算法的收敛速度。 本文通过大量仿真实验证实了上述工作的正确性，取得了如下几方面的研究成果： (1) 提出一种白逃逸混合离散粒子群算法(Self-escape Hybrid Discrete ParticleSwarm 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的各项指标均优丁混合遗传算法。

目录

文摘

英文文摘

独创性声明及学位论文版权使用授权书

第一章前言

§1.1研究背景

§1.1.1最优化问题

§1.1.2群智能算法

§1.2具体工作及内容安排

§1.2.1具体工作

§1.2.2内容安排

第二章粒子群优化算法的原理和收敛性分析

§2.1基本粒子群算法

§2.1.1算法原理

§2.1.2算法流程

§2.2粒子群算法收敛性分析

§2.2.1基本粒子群算法收敛性分析

§2.2.2约束系数粒子群算法收敛性分析

第三章离散粒子群优化算法法的改进及其在TSP中的应用

§3.1离散粒子群优化算法

§3.1.1算法定义

§3.1.2算法实现

§3.1.3仿真结果

§3.1.4性能及问题分析

§3.2具有自逃逸功能的混合离散粒子群算法

§3.2.1自逃逸的基本思想

§3.2.2算法实现

§3.2.3仿真结果及结论

§3.3具有增强自逃逸功能的离散粒子群算法

§3.3.1增强自逃逸的基本思想

§3.3.2算法实现

§3.3.3仿真结果及结论

第四章RSEDPSO算法在固定货架拣选作业问题中的应用

§4.1固定货架拣选作业问题描述

§4.2仿真结果及结论

第五章总结与展望

§5.1总结

§5.2展望

参考文献

附录

致谢

攻读硕士期间已发表或撰写的论文