【作者】 梁军；

【导师】 王强；

【作者基本信息】 广西师范大学 ， 计算机软件与理论， 2008， 硕士

【摘要】 优化技术是一种以数学为基础,用于求解各种组合优化问题的应用技术。最优化问题是人们在工程技术、科学研究、和经济管理等诸多领域中经常碰到的问题,它是指在满足一定的约束条件下,寻找一组参数值,使目标函数达到最大或最小。最优化问题根据其目标函数、约束条件的性质以及优化变量的取值范围可以分为许多类型,例如:根据目标函数和约束条件是否均为线性表达式,把最优化问题划分为线性规划问题和非线性规划问题。针对不同的最优化问题,提出了许多不同的优化方法,如牛顿法、共轭梯度法、Polar-Ribiere法、拉格朗日乘子法等。这些优化算法能很好地找到问题的局部最优点,是成熟的局部优化算法。但是随着人类生存空间的扩大以及认识与改造世界范围的拓展,人们发现由于问题的复杂性、约束性、非线性、建模困难等特点,解析性优化算法已不能满足人们的要求,需要寻找一种适合于大规模并行且具有智能特征的优化算法。现代进化类方法如人工神经网络、遗传算法、禁忌搜索法、模拟退火法和蚁群算法等在解决大规模的问题时体现出强大的潜力,它们可以在合理的时间限制内逼近优化问题的较好可行解。其中,遗传算法和蚁群算法被称为智能优化算法,其基本思想是通过模拟自然界生物的行为来构造随机优化算法。近年来,另一种智能优化算法—粒子群算法(particle swarm optimization,简称PSO)越来越受到学者的关注。粒子群算法是美国社会心理学家James Kennedy和电气工程师Russell Eberhart在1995年共同提出的,它是受到鸟群社会行为的启发并利用了生物学家Frank Heppner的生物群体模型而提出的。它用无质量无体积的粒子作为个体,并为每个粒子规定简单的社会行为规则,通过种群间个体协作来实现对问题最优解的搜索。由于算法收敛速度快,设置参数少,容易实现,能有效地解决复杂优化问题,在函数优化、神经网络训练、图解处理、模式识别以及一些工程领域都得到了广泛的应用。不过,尽管粒子群算法发展有十几年了,但是无论在理论上还是在实践上都尚未成熟。粒子群算法也和其它全局优化算法一样,有易陷入局部极值点,进化后期收敛慢,精度较差等缺点。如何加快粒子群算法的收敛速度和提高算法的收敛精度,一直是大多数研究者关注的重点。加快收敛速度的措施主要有如何选择最优的算法参数,以及与其它优化算法结合来对粒子群算法的主要框架加以修正。在提高收敛精度,防止粒子早熟方面,主要有设法保持种群的多样性,或引入跳出局部最优点的机制等措施。现已有的改进粒子群算法有模糊自适应PSO算法(FAPSO),杂交PSO算法(HPSO),离散二进制PSO算法,协同PSO算法,免疫粒子群优化算法等。本文在综述了粒子群算法及其发展过程的基础上,对现有文献进行了研究和分析,针对连续问题和离散问题分别提出了两种改进算法。在对连续问题的改进算法中,用一种无约束条件的随机变异操作代替速度公式中的惯性部分,并且使邻居最优粒子有条件地对粒子行为产生影响,提高了粒子间的多样性差异,从而改善了算法能力。本文主要以函数优化为例,通过对Sphere、Rosenbrock、Girewank等几类经典测试函数进行测试,来说明算法的有效性。PSO算法虽然被广泛应用于连续问题的优化,但在求解离散优化问题方面还是一种全新的尝试。本文在对离散问题的分析中,以矩形件优化排样具体问题为例,提出了针对离散问题的改进算法,该算法对解码方式进行了改进,并且融合了遗传算法中的交叉和变异思想,使其能快速地达到优化目的。最后,通过对这两种改进算法的分析研究,发现了几种针对粒子群算法的改进策略。无论是连续问题还是离散问题运用这几种改进策略都可以得到较好的优化。改进策略如下:对粒子行为有条件地增加邻居最优粒子的影响,可以提高粒子间的多样性差异。增加变异操作。对每个新生成的粒子增加变异操作,使用不同的变异策略对粒子进行变异。定义一个阀值,对粒子使用不同的更新策略进行更新。总之,论文对粒子群算法做了较为全面深入的分析和讨论,采用了几种改进策略,使其能有效地应用在连续问题和离散问题中。最后,论文进行了总结,并提出了进一步的研究方向。更多还原

【Abstract】 Optimization technology is based on mathematics and can solve various combinatorial optimization problems. Many problems possess a set of parameters to be optimized, especially in the fields of engineering technology, scientific research and economic management. Optimization is to look for a set of parameters in definite restriction with the aim of minimizing or maximizing the objective function. According to quality of objective function and restrict condition and scope of variable, optimization problem can be divided into lots of types. For example, if objective function and restrict condition are both lineal expression, this problem belongs to linear programming problem, if not, it belongs to nonlinear programming problem. Different methods have been presented to sovle different kinds of problems, such as Newton’s method, conjugate gradient method, Polar-Ribiere’s method, Lagrange Multiplier Method etc. These methods can nicely find local extreme in different problems.However, with the development of human living space and the scope of understanding and transforming the world, people have found that because of the complexity, binding, nonlinear, modeling difficulties characteristic, it is not easy to find a satisfying analytic solutions. It’s necessary to find a optimization algorithm suiting for large-scale parallel Operation with smart features.Modern evolution methods such as artificial neural networks, genetic algorithms, Taboo search method, simulated annealing, and ant colony algorithm etc., reflect a strong potential in solving large-scale problems. They can approximate the better feasible solution for the optimization problem within a reasonable period of time. The Genetic Algorithm and ant colony algorithm are known as intelligent optimization algorithm, and their basic idea is to construct stochastic optimization algorithms by simulating the behavior of the natural world.In recent years, another kind of intelligent optimization algorithm - PSO algorithm (particle swarm optimization, or PSO) increasingly accesses to the concerns of scholars. PSO algorithm is proposed by American social psychologist James Kennedy and electrical engineer Russell Eberhart in 1995, and it is inspired by bird populations’ social behavior and uses the biological group model of biologist Frank Heppner. It uses particles without quality and volumes individuals, provides simple social rules of conduct for each particle, and searches the optimal solution to the problem through individual collaboration among populations. The algorithm converges fast, needing less parameters.Also it is easily achieved, and can effectively solve complex optimization problems. It has been widely used in function optimization, neural network training, graphic processing, pattern recognition as well as some engineering fields.Although the PSO algorithm has developed for more than 10 years, it has not been widely used in theory or practice. PSO algorithm, like other global optimization algorithm, has many shortcomings, such as easily falling into the local maximum, having slow convergence speed in the late evolutionary, having poor accuracy. How to accelerate the particle swarm algorithm for the convergence rate and improve its convergence accuracy are topics that most of the researchers have focused on. There are mainly two measures in accelerating the convergence speed. One is how to choose the best parameters, and the other is to combine with other optimization algorithm to amend the main framework. For improving accuracy and avoiding the common defect of premature convergence, some measures need to be taken that the diversity of the population should be maintained and the mechanism of jumping out of the local maximum should be introduced. There have been some methods for improving PSO algorithms, such as fuzzy adaptive PSO algorithm (FAPSO), the hybrid PSO algorithm (HPSO), discrete binary PSO algorithm, coordination PSO algorithm and immune PSO algorithm etc.In this paper, the PSO algorithm is summarized, the existing literatures are analysised, then, two improved algorithm are separately presented for continuous and discrete problems.In the continuous problems, the improved algorithm uses a random and unconditional mutation strategy which substitutes for previous velocity, and considers the effect which the best position of neighbor particle has conditionally on the particle behavior. It efficiently increases diversity of particles and improves the performance of algorithm. In this paper, as an example to function optimization, it is tested to illustrate the effectiveness of the algorithm through several classic functions, such as the Sphere, Rosenbrock and Girewank.At present, particle swarm optimization algorithm (PSO) has been applied to continuous problems for several years, but it is still an attempt to use the algorithm in discrete problems. An improved particle swarm optimization algorithm is proposed to solve the packing problem of rectangles, which belongs to discrete problems. This algorithm modifies the mode of decoding and combines the crossover and mutation in genetic algorithm in order to speed the optimization process.Finally, several improvement strategies have been found in this paper by adopting two improved PSO algorithm .Whether the issue is continuous or discrete problem using these strategies can be better optimized. The improved strategies are as follows:To consider the effect which the best position of neighbor particle has conditionally on the particle behavior can improve the diversity of particles.To increase mutation. To increase mutation for each new generation of particles and different mutation strategies can be used.To use different updated strategy updates the particle through defining a threshold in the different generation.In short, in this paper, a more comprehensive and in-depth analysis is discussed on particle swarm algorithm, and several improvements strategies are made for discre- te and continuous problems. Finally, the whole research contents are summarized, and further research directions are indicated.更多还原