【作者】 王雪飞；

【导师】 邱玉辉；

【作者基本信息】 西南大学 ， 基础心理学， 2008， 博士

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

【Abstract】 Optimization problems are of vital importance in fields of computer science, artificial intelligence, operational research and other relative fields. Many problems encountered in engineering technology, scientific research and economic management can be treated as variations of challengeable nonlinear optimization problem, such as: configuration designing need to minimize total weight of materials used while satisfying the intensity request; resource allotting need to maximize total benefit utilizing limited resources; transportation scheming need to minimize total expense on circumstance of appointed material and load capability; manufacture scheme arranging need to maximize total benefit by controlling the costs of manpower, devices, and raw and processed materials according to the flow of techniques and demand of client. Optimization theory and its techniques will surely take more and more important part in the information era of 21 century.Numerical optimization methods were proposed these years due to the universality of optimization problems. Many hard optimization problem emerged which cannot be solved in acceptable time, with the increasing complexity of real tasks in the field of industry and scientific research. More effective and practicable algorithms are needed for the traditional programming methods cannot meet complex problems nowadays.As a newly developed swarm intelligence paradigm, particle swarm algorithm is a very promising optimization tool, with many advantages in high-dimensional problems or tasks that lack prior knowledge. Its basic idea is originated from Social Psychology and Artificial Life as a simulation of socio-cognitive processes. Because of its high convergence rate and excellent generalization, particle swarm algorithm has attracted much attention since it was first proposed in 1995.In this literature, most researchers have focused their efforts on how to promote the convergence rate and avoid the premature convergence problem. Introducing new mechanisms to ensure the diversity of swarm population or escape from local minima may be useful on relieving premature convergence of the algorithm. As to improving convergence rate, much work focus on tuning strategy parameters, or modifying the original framework with ideas inspired from other meta-heuristics. As most researchers of this field are with pure scientific computing or engineering applications background, they care more about the results than probe into the real cause, not to mention consider social psychology origins of the algorithm.In our research, we attach importance to both theoretical analysis and experimental demonstration. From the aspect of information spread efficiency, a dynamic topology of particle swarm algorithm is thoroughly investigated and a novel particle swarm algorithm based on small world network model is proposed. The major contributions of the dissertation are:(1) We summarize the developing background of swarm intelligence, and introduce three methodologies of swarm intelligence: Ant Colony Optimization (ACO), Particle Swarm Optimization (PSO) and Artificial Fish-Swarm Algorithm (AFSA). The intrinsic and general character of swarm intelligence is analyzed through relevancy of reductionism, artificial life, self-organization system, and other topics.(2) We investigate the influence of parameters by large experiments and verify the parameter selecting of canonical PSO.(3) We analyze convergence of traditional PSO algorithm from the view of linear constant system, and elicit that the track of any particle will converge to the position held by the optimal particle. Then we theoretically analyze algorithm convergence from the view of random system, and present a sufficient condition for the system to be mean square stable. This enhances the effectiveness of conclusion under linear constant condition.(4) We propose two novel PSO algorithm based on edge-reassigning and edge-addition small-world network model, thus implement dynamic topology of PSO algorithm. New parameters introduced are thoroughly investigated by large amount of experiments on Benchmark problems.(5) The proposed algorithms are rigorously tested and compared on large amount of selected benchmark problems taken from the literature. These benchmark problems are designed to challenge optimization techniques with difficulty of high-dimensionality, multimodality, and deceptive gradient information. In this dissertation, we focus attention on comparing the performance of different algorithms on hard multimodal functions, and give the statistical results on measurements of convergence rate, success rate, function evaluations, and the quality of obtained solutions. The results of experiments demonstrate that the proposed small-world PSO algorithms with dynamic topology can improve performance of classical PSO algorithms apparently.更多还原