粒子群算法的动态拓朴结构研究

论文摘要

最优化问题在计算机科学、人工智能、运筹学和其它相关领域中有着重要的地位,是人们在工程技术、科学研究和经济管理等诸多领域中经常遇到的问题,很多应用领域中都面临困难的非线性优化问题,如:结构设计要在满足强度要求等条件下使所用材料的总重量最轻;资源分配要使各用户利用有限资源产生的总效益最大;安排运输方案要在满足物质需求和装载条件下使运输总费用最低;编制生产计划要按照产品工艺流程和顾客需求,尽量降低人力、设备、原材料的成本使总利润达到最大等等。在21世纪的信息时代,其理论和技术必将在社会的各个方面起着越来越大的作用。由于优化问题存在的普遍性,多年以来有数不清的优化技术被提出和研究。但工业和科学领域的大多数实际问题的复杂程度也正日益增加,出现了大量根本无法在可接受的时间内找到解的问题。传统的规划技术已经无法满足求解复杂问题的需求,因此更高效更实用的优化算法总是需要的。作为一种新的群体智能方法,粒子群算法PSO是一个非常有前景的工具,在处理高维的以及缺乏领域知识的问题时尤其有用。该算法的灵感来源于社会心理学和人工生命,致力于模拟个体间的社会交互,具有收敛速度快、通用性强等优势,自1995年被提出之后得到了数值优化领域的广泛关注。如何加快粒子群算法的收敛速度和避免出现早熟收敛,一直是大多数研究者关注的重点。克服早熟收敛的措施主要是设法保持种群的多样性,或引入跳出局部最优点的机制。在加快收敛速度方面,主要的工作集中在如何选择最优的算法参数,以及从其他智能优化算法中借鉴一些思想对PSO算法的主要框架加以修正。但这些研究者多数属于纯科学计算或工程应用领域,他们只专注于结果而不探究原因,更少有人深入考虑粒子群算法的社会心理学渊源。本文在研究过程中,注重算法的理论分析和实验验证相结合。从信息传播效率入手,详细研究了粒子群算法种群的一种动态拓扑结构,实现了基于小世界网络模型的新颖粒子群算法。论文的主要工作和创新点包括:(1)总结了目前群体智能的发展背景,介绍了群体智能的三种主要方法论:蚁群算法、粒子群优化算法和人工鱼群算法,通过与还原论、人工生命、自组织系统等相关论题的关系,分析了群体智能技术的内在特征和共性。(2)通过大量实验,研究了PSO中关键参数对算法性能的影响,并由此得出规范PSO的参数设置。(3)从线性定常系统的角度对PSO的收敛性加以分析,得出粒子轨迹最终收敛到全局最优粒子所在的位置。从随机系统的角度对算法的收敛性进行了理论分析,增强了线性定常条件下结论的有效性,给出了系统均方稳定的一个充分条件。(4)提出了基于边重构和边增加小世界网络模型的两种改进PSO算法,实现了PSO算法的动态邻域结构,并对改进算法引入的新参数做了详尽的实验研究。(5)在选定的Benchmark问题和性能衡量标准上,对比研究了提出的小世界PSO算法与其他经典PSO算法。这些benchmark问题具有挑战优化算法的困难性:高维、多峰、具有欺骗性的梯度信息等。本研究尤其重视比较算法在困难多峰函数上的表现,以多次试验的统计结果给出算法在收敛速度、收敛成功率、目标函数计算次数以及获得解的质量等几个衡量指标上的表现。仿真实验的结果显示,本论文提出的具有动态拓扑机构的小世界PSO算法能明显改善经典PSO的性能。

论文目录

• 摘要
• Abstract
• 目录
• 第一章 前言
• 1.1 研究背景
• 1.2 研究动机
• 1.3 本文的创新性工作
• 1.4 论文内容介绍
• 第二章 群体智能
• 2.1 群体智能方法
• 2.1.1 蚁群算法ACO
• 2.1.2 粒子群算法PSO
• 2.1.3 人工鱼群算法AFSA
• 2.2 与群体智能相关的几个论题
• 2.2.1 还原论的局限
• 2.2.2 自组织现象、涌现与复杂系统
• 2.2.3 人工生命
• 第三章 粒子群优化算法
• 3.1 PSO算法的发展
• 3.1.1 原始的PSO
• 3.1.2 标准的PSO
• 3.1.3 带收缩因子的PSO
• 3.1.4 规范的PSO
• 3.1.5 其他的变形PSO算法
• 3.2 规范PSO的参数设置
• 3.2.1 实验设计
• 3.2.2 实验实现
• 3.2.3 结果
• 3.2.4 结论
• 3.3 研究与应用现状
• 第四章 PSO系统收敛性分析
• 4.1 粒子轨迹与收敛行为分析
• 4.1.1 收敛行为
• 4.1.2 原始PSO的收敛性
• 4.1.3 收敛的PSO参数
• 4.2 基于随机过程的PSO收敛性分析
• 第五章 基于小世界网络的动态邻域PSO算法
• 5.1 复杂网络
• 5.1.1 概念
• 5.1.2 特征
• 5.1.3 小世界效应与无标度性
• 5.1.4 小世界网络的生成方法
• 5.1.5 小世界网络的统计特性
• 5.2 基于小世界网络的动态邻域PSO算法
• 第六章 实验设计及结果
• 6.0.1 实验一:更新邻域的间隔迭代次数m
• 6.0.2 实验二:重连/边增加概率p
• 6.0.3 实验三:初始规则网络的阶次K
• 6.0.4 实验四:在benchmark函数上与其他PSO算法的性能比较
• 第七章 总结
• 7.1 研究工作总结
• 7.2 未来工作计划与研究方向
• 参考文献
• 攻博期间发表的论文
• 致谢