【作者】 秦全德；

【导师】 李荣钧；

【作者基本信息】 华南理工大学 ， 管理决策与系统理论， 2011， 博士

【摘要】 群体智能是指众多行为简单的个体在相互作用过程中涌现产生的整体智能行为。群体智能由于原理简单、容易实现、全局搜索能力强的特点,目前已经成为计算机、工程、管理、经济、生物等学科的研究热点和前沿领域。粒子群算法(Particle Swarm Optimization, PSO)是群体智能中较新的一种优化方法,其搜索过程基本不利用外部信息,仅仅以适应度函数作为进化的依据,从而形成一种“生成+检验”为特征的智能计算方法。然而,同与所有随机搜索算法一样,PSO在求解较复杂的问题时容易陷入局部最优。本文在分析PSO目前研究现状的基础上,从不同的角度提出了几种改进算法,使之更加有效可靠;并将提出的改进算法应用于经济管理中的实际问题,拓展粒子群算法的应用领域。本文主要的内容概括如下:(1)介绍了传统优化方法和进化计算,重点探讨了群体智能的发展、特点和几种典型的群体智能方法。在阅读大量文献的基础上,按照作者的理解对PSO的研究现状与应用进行了归纳和总结,较为深入地分析了PSO中3个重要要素:邻域结构、边界约束处理和速度限制。(2)PSO是源于对社会型群居动物的行为模拟,因此将自然界的一些生物行为融入PSO中是一条潜在可行的改进途径。本文第三章提出了3种基于生物行为的PSO改进方法:基于生物寄生的双种群PSO(PSOPB)、模拟生物理想自由分布模型的PSO(IFDPSO)以及基于predator-prey行为的改进PSO(PPPSO)。PSOPB由宿主群和寄生群两个种群组成,两个种群之间模拟自然界中生物的兼性寄生行为,并考虑了“优胜劣汰”的进化法则。在分析生物觅食行为中资源斑块选择理想自由分布模型的基础上,提出了一种新型的粒子群算法—IFDPSO。IFDPSO将所有粒子中3个不重叠的个体最优位置的适应度视为资源斑块的食物质量,并根据理想自由分布模型随机分配相应数量的粒子到各个资源斑块中,从而保证了群体的多样性和算法的全局搜索能力。在分析生物的捕食—被捕食(predator-prey)行为规律的基础上,提出了一种由predator和prey两个种群构成的PSO(PPPSO)。predator种群间隔一定的迭代次数排斥prey种群,逐步向prey种群的群体最优位置靠近,同时每个prey粒子尽量逃离距离最近的predator粒子。采用这样的机制,提高了摆脱局部最优的能力。多个测试函数的仿真实验证明了3种算法的有效性。(3)鉴于单一智能算法在实际应用中面临各自的问题,相互之间的促进与补充便成为自然的选择。在分析PSO与人工蜂群算法(Artificial Bee Colony, ABC)的各自优势和缺陷的基础上,提出了一种以PSO为主,在适当的时候嵌入ABC邻域算子的混合算法(PSOABC)。在对PSO搜索原理简要分析的基础上,提出了PSOABC中2种ABC邻域算子方法:O邻域算子和R邻域算子。综合考虑PSO的邻域结构和2种ABC邻域算子,构建了4种不同类型的PSOABC。对4种不同类型的PSOABC仿真实验结果表明R邻域算子性能优于O邻域算子。将R邻域算子的PSOABC与其他几种PSO的实验结果进行比较表明带R邻域算子的PSOABC具有快速的收敛速度和搜索精度,是一种可靠的全局优化方法。(4)在分析基本PSO学习策略缺陷的基础上,本文第五章提出了2种新的学习策略的改进PSO:交互学习的双种群粒子群算法(ILPSO)和自适应的正交学习粒子群算法(SOLPSO)。ILPSO是启发于人类社会行为的特征,不同群体之间可以交互学习。由于交互学习的机制,群体的多样性可以得到维护,从而不容易陷入局部最优,测试函数的实验结果证明其有效性。针对PSO中的“两进一退”的现象,将PSO的每一维看成是影响试验结果(函数适应度值)的一个因素,利用种群中其他个体的信息,通过正交试验组合可以产生更优的个体最优位置,从而有利于加快收敛速度和提高搜索的精度。SOLPSO中提出了4种正交组合方法,并分析它们各自优势和缺陷,设计了一种根据算法的进程自适应调整正交组合方法的策略。多个测试函数的仿真实验表明了提出的两种算法的有效性。(5)建立了连续型物流配送中心选址的数学模型,并根据问题的特点,设计了合适的粒子编码方案。在考虑现实情况下,构建了一类离散Mean-CVaR投资组合模型,通过增加一个特定的惩罚项,将离散问题转化为连续问题的求解。提出的PSOPB和SOLPSO分别用于两类模型的求解,结果表明了它们的有效性。最后,总结了本文的研究成果,并对未来的研究方向提出了进一步的展望。更多还原

【Abstract】 Swarm intelligence refers to the emergence of the overall intelligent behavior through the interactions of many individuals with simple intelligence. Swarm Intelligence has become the research focus and frontier of computer science, management, economics, biology and other disciplines as it is simple, easy to implementation and has good global search abilities. Particle swarm optimization (PSO) is a relatively new branch optimization method of swarm intelligence. The search process of PSO usually does not use external information, solely on the objective function. As a result, PSO is an adaptive artificial intelligence technique characterized by "generate-and-test". However, just like any other stochastic algorithm, PSO is prone to get trapped in the local optima when complex multimodal problems are being optimized. This article proposed some new some new improved PSOs from different perspective in order to enhance the reliability and effectiveness of PSO. Moreover, the proposed methods are used to solve the practical problem in management and economy areas to extend the application scope.In this article, the main contents summarized as follows(1) This paper introduced traditional optimization methods, evolutionary computation and swarm intelligence, especially focusing on the development, characteristics and several typical swarm intelligence methods. Current research situation on PSO improvements and applications are summarized according the author’s understanding. Three key elements in PSO, that is neighborhood structure, boundary constraint handling and velocity-constrained, are analyzed in-depth.(2) As PSO algorithm is derived from mimicking sociological behaviors of animals, it is natural to incorporate other biological mechanisms into basic PSO, which may be a viable way to improve the algorithm’s performance. The third chapter proposed three kinds of improvements based on biological behavior, to be specific, a two-population PSO mimicking bio-parasitic behavior named PSOPB, a PSO variant based on simulation of biological ideal free distribution model (IFDPSO) and a two-population PSO based on predator-prey behavior (PPPSO). PSOPB is composed of the host and the parasite population. In the proposed algorithm, two populations mimic facultative bio-parasitic behavior and exchange particles according to particles’fitness values sorted of each population in a certain number of iterations. In order to embody the law of“survival of the fittest”in biological evolution, the particles with poor fitness in the host population are removed and replaced by the same numbers of the re-initialization particles in order to maintain a constant population size. In IFDPSO, three non-overlapping personal best positions of the particles are selected, and their fitness values are regarded as food quality of resource patch. The number of particles is randomly assigned to each resource patch according to ideal free distribution model. In order to guarantee the diversity of the whole population, thus improving the global search capabilities, the best position of each sub-population keep a distance, which linearly decreases with the increase of iterations. According to biological rules of predator-prey behavior, a two-population particle swarm optimization (PPPSO) was proposed. In the presented algorithm, the particles are divided into two populations, the predator and prey population. Particles in predator population exclude the particles in prey population in a certain interval of iterations. In order to enhance the capacities to escape from local optimum of the particles with stagnation state in prey population, a method with speed mutation is used. The experimental results of some benchmark functions demonstrate three proposed algorithm’s efficacy.(3) In view of the limitations of each single algorithms used to solve practical problems, it is natural to hybrid different algorithm. After analyzing the strength and drawbacks of PSO and artificial bee colony (ABC), this article designed a new hybrid algorithm called PSOABC, in which PSO is the main part and ABC is incorporated into PSO at the proper time. According to the principle of PSO, two types ABC neighbor search operators, that is origin neighbor search (ONS) and random neighbor search (RNS), are proposed in PSOABC. Considering PSO neighbor structure and ABC neighbor search operators, four types of PSOABC are presented. Some experimental results show that the performance of RNS is better than ONS. Comparing PSOABC with RNS with other PSO variants, experiments show that the proposed algorithm has faster convergence speed and search accuracy. Thus it is a reliable global optimization method.(4) As the learning mechanism of basic PSO results in premature easily, this article developed two new improved PSOs, interactive learning PSO (ILPSO) and self-adaptive orthogonal learning PSO (SOLPSO). ILPSO is inspired by the phenomenon of human social behavior that individuals in different groups can learn each other. In ILPSO, leaning population and learned population are determined according their best particle’s fitness. Each particle in learning population has different learning probability according its fitness. As the mechanism of interactive learning, diversity of the two populations can be maintained. Therefore, ILPSO is not to easily fall into local optimum. Experimental results on some test function demonstrate its effectiveness. For“two step forward, one step back”phenomenon in basic PSO, a self-adaptive orthogonal learning PSO(SOLPSO)was proposed. In SOLPSO, each dimension of a particle is regarded as a factor in orthogonal experimental design. The orthogonal learning mechanism guide the particle, which did not improve its personal best position in a certain iterations, to fly in better direction by utilizing the information of other individuals, and formed a better personal best position. The article develop four methods that to utilize other individual information, and analyze the strength and drawbacks of each method. A self-adaptive strategy is proposed that probability of each method selected is adjusted in terms of search process. The comparisons show that SOLPSO significantly improved the performance of PSO.(5) This article builds a continuous logistics distribution center location model, and designs a suitable encoding scheme of particles in accordance with the characteristics of the problem. Considering the reality, a class of discrete Mean-CVaR portfolio selection model is created. The discrete problem solved turns into the continuous one by added a particular punishment item. The proposed PSOPB and SOLPSO are used to solve two models, respectively. Results show the effectiveness of the two algorithms.Finally, achievements in this paper are summarized, and the prospects of the future research are discussed.更多还原