解全局优问题的粒子群算法.pdf

解全局优问题的粒子群算法

(理学院,数学系,数学与应用数学专业陈小红)
(学号:2000144023)

摘要:粒子群优化算法(PSO)是一类基于群体智能(Swarm Intelligence)的随机
全局优化算法。本文提出一类新颖的 PSO 算法,其目的在于克服传统的 PSO“易于局部收敛”
的缺陷。数值试验证实了所提出算法的有效性。
关键词:群体智能,粒子群算法,全局优化
教师点评:粒子群优化算法(PSO)是一类基于群体智能的优化算法。陈小红同学通过
对传统 PSO 的改进,提出一类新颖的 PSO 算法,该算法改进了传统 PSO 算法易于局部收敛
的缺陷,从而能够得到更好的结果。数值试验也验证了新提出算法的有效性。该论文工作放
映了陈小红同学具有较扎实的数学基础知识,以及较强的解决实际问题的能力。这是一篇优
秀的毕业论文。(指导教师:李国,副教授)

§1 引言
科学研究、工程实际和国民经济发展中许多问题可以归结为如下的数学模型:
max {F(x) | x ∈ D ⊆ Rn }
这类数学模型的目标在于寻求区域 D 内函数 F(x)的最大值(或等价的,最小值)——称之
为函数优化问题。函数优化问题求解算法的研究,已有很长的研究历史,简单地说,目前已
有的函数优化算法可分为确定性优化和随机性优化两大类。确定性优化算法以建立在梯度计
算基础上的非线性规划类方法为代表,例如牛顿法、最速下降法等[1],这类算法的特点是
求解速度快,并且具有很好的理论基础。但它们也具有一些本质的缺陷,这主要表现在:(1)
它们仅仅只能够求出函数在区域 D 内局部范围的极值(即,局部极值),而不是整个区域上
的全局最优值,(2)这类方法对待优化函数的光滑性一般要求较高(例如,二阶连续可导),
这当然极大地限制了其应用范围。随机性方法属于当前比较热门的研究范畴,这类算法的主
要特点是由于在计算中引入随机性因素,因此算法一般具有适用面广、全局优化性强、算法
简明易行、稳健等突出的优点。仿生类算法(例如遗传算法、进化程序、演化规划、模拟退
化方法等)是目前有代表性的随机性算法[2],它们虽然具有随机性算法的共同优点,但它
们的突出缺陷是,算法的计算速度比较慢,并且算法执行过程中涉及到许多参数,这些参数
的选取没有理论依据,往往依赖于使用者的经验和反复的计算实践,并且选取的参数没有可
1
推广性。本文目的在于讨论一种全新的解全局优化问题的算法——粒子群优化算法(Particle
swarm optimizer,简记为 PSO),虽然同样属于仿生类算法,但相对于其它仿生类算法,它
们往往具有较快的计算速度,并且执行过程中仅需要很少的参数选取。正是由于这些突出的
优点,PSO 算法已广泛应用到函数优化、模式分类、模糊系统的控制、以及神经网络的训
练等众多的学科领域。
PSO 算法最早于 1995 年由 Kennedy 和 Eberhart [3]提出,后又经过包括 Shi、Mendes 等
众多学者的不断努力而发展到今。PSO 是一类基于群体智能(Swarm Intelligence)的随机优
化算法,它起源于对简单社会行为(例如鸟群的飞行)的模仿,为了说明 PSO 算法的基本
思想,我们设想以下情景:一群鸟在设定的区域里随机地搜索食物。在这个区域里只有一块
食物,所有的鸟都不知道食物在哪里,可是鸟知道他们离食物有多远,因此,鸟群可以靠着
自己所搜索到的离食物最近的“记忆”(位置和方向),和周围邻居所传达的离食物最近的“记
忆”,进行搜索,直到找到食物。简单地说,PSO 基本思想是:设定优化问题的每个潜在解
为粒子,初始化阶段中随机选取一个粒子种群,每个粒子的性能(称之为适应性)由一个优
化函数来衡量,然后通过此适应值来调整粒子的速度与位置(粒子向个体最优位置和全局最
优位置趋近),从而得到新一代的粒子种群,这个过程一直循环往复,直到满足某种预设的
收敛条件。从上述我们看到,PSO 算法的主要特点为:(1)每一个体(粒子)都被赋予了一
个随机速度并在整个问题空间中流动;(2)个体具有记忆功能;(3)个体的进化主要是通过
个体之间的合作和竞争来实现[4]。
虽然 PSO 在众多领域取得较好的应用效果,但另一方面,应用实践却显示,PSO 算
法对解空间的搜索极易陷入局部极值,一旦粒子陷入它“认为”是全局最优值的范围,就容
易出现停滞现象,此时,即使算法继续执行,但粒子所搜索的空间并没有实质性的发展(大
部分的粒子仅在某一范围的位置内移动,适应值变化不太)([5])。本文的主要目的在于通
过对传统的 PSO 的改进,改善