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

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