梯度粒子群算法及应用（完整版）

1 绪论

最优化问题是在满足一定约束条件下，寻找一组参数值，以使某些最优性度量得到满足，即使系统的某些性能指标达到最大或者最小。它广泛存在于农业、国防、工程、交通、金融、化工、能源、通信、材料等许多领域。最优化技术在上述领域的应用已经产生了巨大的经济效益和社会效益。国内外的实践表明，在同样条件下，经过优化技术的处理，对系统效率的提高、能耗的降低、资源的合理利用及经济效益提高均有显著的效果，而且随着处理对象规模的增大，这种效果也更加显著。传统的优化方法根据问题的性质不同，通常将问题划分为线性规划问题、非线性规划问题、整数规划问题和多目标规划问题。相应的有一些成熟的常规算法，如应用于线性规划问题的单纯形法，应用于非线性规划的牛顿法、共轭梯度法等，应用于整数规划的分枝定界法、动态规划法等。

目前，基于严格机理模型的开放式方程建模与优化已成为国际上公认的主流技术方向。许多工程公司和各大科研机构纷纷投入大量的人力物力对系统的建模与优化进行深入细致的研究，希望取得突破性的进展。然而，基于严格机理模型所得到的优化命题往往具有方程数多、变量维数高、非线性强等特点，这使得相关变量的存储、计算及求解都相当困难。在国民经济的各个领域中都存在着相当多的涉及因素多、规模大、难度高和影响广的优化命题，如流程工业系统优化、运输中的最优调度、生产流程的最优排产、资源的最优分配、农作物的合理布局、工程的最优设计以及国土的最优开发等等，所有这些问题的解决也必须有一个强有力的优化工具来进行求解。而前述传统的优化算法面对这样的大型问题已无能为力，无论是在计算速度、收敛性、初值敏感性等方面都远不能满足要求。

人们从生命现象中得到启示，发明了许多智能的优化方法来解决上述复杂优化问题。例如遗传算法(Genetic Algorithm)参考了生物种群通过遗传和自然选择不断进化的功能、人工免疫系统(Artificail Immune Systems)模拟了生物免疫系统的学习和认知功能、蚁群优化(Ant colony Optimization)算法模仿了蚂蚁群体在路径选择和信息传递方面的行为，粒子群优化（Particle swarm optimization)算法模拟了鸟群和鱼群觅食迁徙中个体与群体协调一致的机理，群落选址算法(colony Location Algorithm)模拟了植物群落的形成机制等，这类借鉴模拟了生命系统的行为、功能和特性的科学计算

1

方法称之为人工生命计算(Artifieial Life Computation)。人工生命计算是生命科学、信息科学和运筹学的交叉研究学科，是进化计算的一个新的分支，是由具有生命特性的多智能体以特定计算目标为依据，有序组合起来所形成的计算方法。按照此定义，人工神经网络(Artificial Neural Network)，文化算法(Cultural Algorithm)、人工生命算法(Artifieial Life Algorithm)、捕食搜索策略(Predatory Search Strategy)等都可以被归纳为人工生命计算。

粒子群优化(PSO)算法是其中较新的一种人工生命计算方法。它同遗传算法类似，是一种基于迭代的优化工具。系统初始化为一组随机解，通过迭代搜索最优值。同遗传算法等其他人工生命计算方法相比，粒子群优化算法概念简单、容易实现，没有很多参数需要调节。目前粒子群算法越来越引起人们的关注，已成为国际上一个新的研究热点。粒子群优化算法的研究还处于初级阶段，还有很多领域需要研究。

在这篇文章中，首先提出了标准的粒子群算法， 标准的粒子群算法由于其简单和解决问题的有效能力而被应用到很多的领域。但在实际应用当中，也表现出了一些不尽人意的问题。这些问题中最主要的是它容易产生早熟收敛、局部寻优能力较差等。实际上这些缺点也是几乎所有随机算法的弊病。本文将梯度信息引入标准PSO算法，并在群体最优信息陷入停滞时将群体进行部分初始化来保持群体的活性，防止群体陷入局优，构造出带有梯度加速的PSO算法。带有梯度加速优化算法却具有很强的局部搜索能力，一种带有梯度加速的PSO算法是对标准PSO算法进行改进。并通过实验讨论了改进算法的适用范围。实验表明，对于单峰函数和多峰函数，带有梯度加速的PSO都能够取得更好的优化效果。

2

2 粒子群优化算法及其理论基础

2.1概述

长久以来 ，人们向往着设计的人工系统像自然系统那样健壮，高效灵活，具有 适应性、自组织和再生能力。近几十年来，一些新颖的优化算法，如人工神经网络、遗传算法及蚁群算法、粒子群算法等通过模拟或揭示某些自然现象或过程而得到发展，其思想和内容涉及数学、生物进化、人工智能、神经科学和量子统计学等方面，为解决复杂工程问题提供了新的思路和手段.这些算法独特的优点和机制，引起了国内外学者的广泛重视并掀起了该领域的研究热潮，且在许多领域得到了成功应用。在优化领域，由于这些算法构造的直观性与自然机理，被称作为智能优化算法。

在这些智能优化方法中，有一类是模拟某些群体的智能行为，虽然群体中的个体仅具有简单的智能，但通过个体与个体和个体与环境的信息交流以及个体的简单行为，从而使群体表现出复杂的自组织、分布式控制、可扩展、健壮的智能体，实现对空间的高效搜索。也就是说，群体智能可以在适当的进化机制引导下通过个体交互以某种突现形式发挥作用，这是个体的智能难以做到的。

在群体智能优化算法的框架下，大量基于不同物理背景的算法纷纷被提出，如，遗传算法，粒子群算法等，并进行了广泛的应用尝试。

粒子群算法(Particle Swarm Optimization.简称PSO)，是一种基于群体智能的进化计算方法.是由PSO由Kennedy和Eberhart博士于1995年提出。

3

PSO的基本概念源于对鸟群捕食行为的研究:一群鸟在随机搜寻食物，在这个区域里只有一块食物，所有鸟都不知道食物在哪里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢?最简单有效的就是搜寻目前离食物最近的鸟的周围区域.PSO从这种模型中得到启示并用于解决优化问题.在PSO中，每个优化问题的潜在解都是搜索空间中的一只鸟，称之为“粒子”，即问题的解空间对应于搜索空间粒子群。所有的粒子都有一个由被优化的问题(如，函数)决定的适应值，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子群们就追随当前的最优粒子在解空间中搜索.PSO初始化为一群随机粒子也就是随机解，然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪“两个极值”来更新自己。第一个就粒子本身所找到的最优解，这个解称为个体极值，另一个极值是整个种群目前找到的最优解，这个极值是全局极值。另外也可以不用整个种群而是用其中一部分作为粒子的邻居，那么在所有邻居中的极值就是局部极值。

PSO一经提出，立刻引起了进化计算领域学者们的广泛关注，形成一个研究热点，目前己广泛应用于函数优化、神经网络训练、模式分类、模糊控制等领域，取得了较好的效果。

2.2原始粒子群优化算法的基本概念 为了更好地描述粒子群优化算法，在此作如下定义 定义1 粒子

类似于遗传算法中的染色体，PSO中粒子为基本的组成单位，代表解空间的一个候选解。 定义2 种群

粒子种群由n个粒子组成，代表n个候选解。 定义3 粒子速度

粒子速度表示粒子在单位迭代次数位置的变化即为代表解变量的粒子在d维空间的位移。

定义4 适应度函数

一般由适应度函数由优化目标决定，用于评价粒子的搜索性能，指导粒子种群的搜索过程。算法迭代停止时适应度函数最优的解变量即为优化搜索的最优解。 定义5 个体极值

4

个体极值是单个粒子从搜索初始到当前迭代对应的适应度最优的解。 定义6 全局极值

全局极值是整个粒子种群从搜索开始到当前迭代对应的适应度最优的解。 2.3粒子群优化算法的一般数学模型

粒子群算法的基本思想是:用随机解初始化一群随机粒子，然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个“极值”来更新自己:第一个就是粒子本身所找到的最好解，即个体极值(Pbest)，另一个极值是整个粒子群中所有粒子在历代搜索过程中所达到的最优解(Gbest)，即全局极值，在找到这两个最好解后，接下来是PSO中最重要的“加速”过程，每个粒子不断地改变其在解空间中的速度，以尽可能地朝Pbest和Gbest所指向的区域“飞”去。基本的粒子群模型由一个m维变量空间内n个粒子(位置，速度)=（Xik,Vik)组成的群体构成，表示为:

kkkXik??Xik,X,...,X,...,X1i2ijim? (2.1)

Tkkk,Vi2,...,Vijk,...,Vim Vik??Vi1? (2.2)

T式中 ， i=1,2,…,n，n为粒子群中粒子的个数:j=1,2,…,m，m 为解向量的维 数;k是进化代数.粒子根据如下的式(2.3)和式(2.4)来更新自己的速度和位置.

kkkkVijk?1?Vijk?c1rand1(pbestij?Xij)?c2rand2(gbestij?Xij) (2.3) k?1kXij?Xij?Vijk?1 (2.4)

Vijk、Vijk?1分别表示第i个粒子在j维方向上的当前速度和修正后的速度;

kk?1、Xij分别为第i个粒子在j维方向上的当前坐标和修正后的坐标;c1, c2是加速系Xij数，分别调节向全局最好粒子和个体最好粒子方向飞行的最大步长;

k?1k?1是第i个粒子在第j维的个体极值点的位置，gbestij是到第k代为止，所有粒pbestij子在第j维的全局极值点的位置:rand1,和rand2为两个在[0, 1]范围内变化的随机函数。

2.4粒子群优化算法的设计步骤和算法流程 设计步骤:

(1) 确定问题的表示方案

粒子群算法在求解问题时，其首要步骤是将问题的解从解空间映射到具有某种

5

本文来源：https://www.bwwdw.com/article/649x.html