梯度粒子群算法及应用.doc

1 绪论最优化问题是在满足一定约束条件下，寻找一组参数值，以使某些最优性度量得到满足，即使系统的某些性能指标达到最大或者最小。它广泛存在于农业、国防、工程、交通、金融、化工、能源、通信、材料等许多领域。最优化技术在上述领域的应用已经产生了巨大的经济效益和社会效益。国内外的实践表明，在同样条件下，经过优化技术的处理，对系统效率的提高、能耗的降低、资源的合理利用及经济效益提高均有显著的效果，而且随着处理对象规模的增大，这种效果也更加显著。传统的优化方法根据问题的性质不同，通常将问题划分为线性规划问题、非线性规划问题、整数规划问题和多目标规划问题。相应的有一些成熟的常规算法，如应用于线性规划问题的单纯形法，应用于非线性规划的牛顿法、共轭梯度法等，应用于整数规划的分枝定界法、动态规划法等。目前，基于严格机理模型的开放式方程建模与优化已成为国际上公认的主流技术方向。许多工程公司和各大科研机构纷纷投入大量的人力物力对系统的建模与优化进行深入细致的研究，希望取得突破性的进展。然而，基于严格机理模型所得到的优化命题往往具有方程数多、变量维数高、非线性强等特点，这使得相关变量的存储、计算及求解都相当困难。在国民经济的各个领域中都存在着相当多的涉及因素多、规模大、难度高和影响广的优化命题，如流程工业系统优化、运输中的最优调度、生产流程的最优排产、资源的最优分配、农作物的合理布局、工程的最优设计以及国土的最优开发等等，所有这些问题的解决也必须有一个强有力的优化工具来进行求解。而前述传统的优化算法面对这样的大型问题已无能为力，无论是在计算速度、收敛性、初值敏感性等方面都远不能满足要求。人们从生命现象中得到启示，发明了许多智能的优化方法来解决上述复杂优化问题。例如遗传算法(Genetic Algorithm)参考了生物种群通过遗传和自然选择不断进化的功能、人工免疫系统(Artificail Immune Systems)模拟了生物免疫系统的学习和认知功能、蚁群优化(Ant colony Optimization)算法模仿了蚂蚁群体在路径选择和信息传递方面的行为，粒子群优化（Particle swarm optimization)算法模拟了鸟群和鱼群觅食迁徙中个体与群体协调一致的机理，群落选址算法(colony Location Algorithm)模拟了植物群落的形成机制等，这类借鉴模拟了生命系统的行为、功能和特性的科学计算方法称之为人工生命计算(Artifieial Life Computation)。人工生命计算是生命科学、信息科学和运筹学的交叉研究学科，是进化计算的一个新的分支，是由具有生命特性的多智能体以特定计算目标为依据，有序组合起来所形成的计算方法。按照此定义，人工神经网络(Artificial Neural Network)，文化算法(Cultural Algorithm)、人工生命算法(Artifieial Life Algorithm)、捕食搜索策略(Predatory Search Strategy)等都可以被归纳为人工生命计算。粒子群优化(PSO)算法是其中较新的一种人工生命计算方法。它同遗传算法类似，是一种基于迭代的优化工具。系统初始化为一组随机解，通过迭代搜索最优值。同遗传算法等其他人工生命计算方法相比，粒子群优化算法概念简单、容易实现，没有很多参数需要调节。目前粒子群算法越来越引起人们的关注，已成为国际上一个新的研究热点。粒子群优化算法的研究还处于初级阶段，还有很多领域需要研究。在这篇文章中，首先提出了标准的粒子群算法， 标准的粒子群算法由于其简单和解决问题的有效能力而被应用到很多的领域。但在实际应用当中，也表现出了一些不尽人意的问题。这些问题中最主要的是它容易产生早熟收敛、局部寻优能力较差等。实际上这些缺点也是几乎所有随机算法的弊病。本文将梯度信息引入标准PSO算法，并在群体最优信息陷入停滞时将群体进行部分初始化来保持群体的活性，防止群体陷入局优，构造出带有梯度加速的PSO算法。带有梯度加速优化算法却具有很强的局部搜索能力，一种带有梯度加速的PSO算法是对标准PSO算法进行改进。并通过实验讨论了改进算法的适用范围。实验表明，对于单峰函数和多峰函数，带有梯度加速的PSO都能够取得更好的优化效果。2 粒子群优化算法及其理论基础2.1概述长久以来 ，人们向往着设计的人工系统像自然系统那样健壮，高效灵活，具有适应性、自组织和再生能力。近几十年来，一些新颖的优化算法，如人工神经网络、遗传算法及蚁群算法、粒子群算法等通过模拟或揭示某些自然现象或过程而得到发展，其思想和内容涉及数学、生物进化、人工智能、神经科学和量子统计学等方面，为解决复杂工程问题提供了新的思路和手段.这些算法独特的优点和机制，引起了国内外学者的广泛重视并掀起了该领域的研究热潮，且在许多领域得到了成功应用。在优化领域，由于这些算法构造的直观性与自然机理，被称作为智能优化算法。在这些智能优化方法中，有一类是模拟某些群体的智能行为，虽然群体中的个体仅具有简单的智能，但通过个体与个体和个体与环境的信息交流以及个体的简单行为，从而使群体表现出复杂的自组织、分布式控制、可扩展、健壮的智能体，实现对空间的高效搜索。也就是说，群体智能可以在适当的进化机制引导下通过个体交互以某种突现形式发挥作用，这是个体的智能难以做到的。在群体智能优化算法的框架下，大量基于不同物理背景的算法纷纷被提出，如，遗传算法，粒子群算法等，并进行了广泛的应用尝试。粒子群算法(Particle Swarm Optimization.简称PSO)，是一种基于群体智能的进化计算方法.是由PSO由Kennedy和Eberhart博士于1995年提出。PSO的基本概念源于对鸟群捕食行为的研究:一群鸟在随机搜寻食物，在这个区域里只有一块食物，所有鸟都不知道食物在哪里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢?最简单有效的就是搜寻目前离食物最近的鸟的周围区域.PSO从这种模型中得到启示并用于解决优化问题.在PSO中，每个优化问题的潜在解都是搜索空间中的一只鸟，称之为“粒子”，即问题的解空间对应于搜索空间粒子群。所有的粒子都有一个由被优化的问题(如，函数)决定的适应值，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子群们就追随当前的最优粒子在解空间中搜索.PSO初始化为一群随机粒子也就是随机解，然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪“两个极值”来更新自己。第一个就粒子本身所找到的最优解，这个解称为个体极值，另一个极值是整个种群目前找到的最优解，这个极值是全局极值。另外也可以不用整个种群而是用其中一部分作为粒子的邻居，那么在所有邻居中的极值就是局部极值。PSO一经提出，立刻引起了进化计算领域学者们的广泛关注，形成一个研究热点，目前己广泛应用于函数优化、神经网络训练、模式分类、模糊控制等领域，取得了较好的效果。2.2原始粒子群优化算法的基本概念为了更好地描述粒子群优化算法，在此作如下定义定义1 粒子类似于遗传算法中的染色体，PSO中粒子为基本的组成单位，代表解空间的一个候选解。定义2 种群粒子种群由n个粒子组成，代表n个候选解。定义3 粒子速度粒子速度表示粒子在单位迭代次数位置的变化即为代表解变量的粒子在d维空间的位移。定义4 适应度函数一般由适应度函数由优化目标决定，用于评价粒子的搜索性能，指导粒子种群的搜索过程。算法迭代停止时适应度函数最优的解变量即为优化搜索的最优解。定义5 个体极值个体极值是单个粒子从搜索初始到当前迭代对应的适应度最优的解。定义6 全局极值全局极值是整个粒子种群从搜索开始到当前迭代对应的适应度最优的解。2.3粒子群优化算法的一般数学模型粒子群算法的基本思想是:用随机解初始化一群随机粒子，然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个“极值”来更新自己:第一个就是粒子本身所找到的最好解，即个体极值(Pbest)，另一个极值是整个粒子群中所有粒子在历代搜索过程中所达到的最优解(Gbest)，即全局极值，在找到这两个最好解后，接下来是PSO中最重要的“加速”过程，每个粒子不断地改变其在解空间中的速度，以尽可能地朝Pbest和Gbest所指向的区域“飞”去。基本的粒子群模型由一个m维变量空间内n个粒子(位置，速度)=（,)组成的群体构成，表示为: (2.1) (2.2)式中 ， i=1,2,n，n为粒子群中粒子的个数:j=1,2,m，m 为解向量的维数;k是进化代数.粒子根据如下的式(2.3)和式(2.4)来更新自己的速度和位置. (2.3) (2.4)、分别表示第i个粒子在j维方向上的当前速度和修正后的速度;、分别为第i个粒子在j维方向上的当前坐标和修正后的坐标;c1, c2是加速系数，分别调节向全局最好粒子和个体最好粒子方向飞行的最大步长;是第i个粒子在第j维的个体极值点的位置，是到第k代为止，所有粒子在第j维的全局极值点的位置:rand1,和rand2为两个在0, 1范围内变化的随机函数。2.4粒子群优化算法的设计步骤和算法流程设计步骤:(1) 确定问题的表示方案粒子群算法在求解问题时，其首要步骤是将问题的解从解空间映射到具有某种结构的表示空间，即用特定的编码表示问题的解，这和遗传算法是类似的。粒子群算法的大部分研究均集中在数值优化领域中，其位置一速度计算模型使用于具有连续特征的问题函数，因此，目前算法大多采用实数向量的编码方式，以粒子的位置向量来表示问题的解。(2) 确定优化问题的评价函数在求解问题时，必须根据问题的具体特征，选取适当的目标函数来计算适应值，适应值是唯一能够反映并引导优化过程不断进行的参量。(3) 选择控制参数粒子群算法的控制参数通常包括粒子种群数量、算法执行的最大代数、惯性权重系数其他一些辅助控制参数，如粒子位置和速度的控制范围等。(4) 选择粒子群模型目前 ， 粒子群算法己经发展了多种位置一速度计算模型，如惯性权重PSO模型、二进制PSO模型等等，在求解不同类型优化问题时，不同PSO模型的优化性能也有差异。（5）确定算法的终止准则与其他进化算法一样，PSO算法中最常用的终止准则时预先设定一个最大的迭代次数，或者当搜索过程中解的适应值在连续多少代后不再发生明显改变时，终止算法。PSO 的算法流程如下:Step 1 :设定加速常数C1和C2，最大进化代数等参数，将当前进化代数置为t=1,初始化一群微粒(群体规模为N)，包括随机位置和速度;Step 2 :评价每个微粒的适应度;Step 3 :对每个微粒，将其适应值与其经历过的最好位置pbest作比较，如果较好，则将其作为当前的最好位置pbest;Step 4 :对每个微粒，将其适应值与全局所经历的最好位置gbest作比较，如果较好，则重新设置gbest;Step5 : 根据方程(2.3)和(2.4)变化微粒的速度和位置;Step6 :检查结束条件，若满足，则结束寻优，如未达到结束条件(通常为足够好的适应值或达到一个预设最大代数T)，则返回Step 2.从上述粒子群优化算法寻优过程可以看出其有如下特性:粒子群中的群体随着时间的变化而进行空间位置的计算;粒子群中的群体对环境中的品质因素做出响应，这种品质因素是通过PSO中每个粒子的最好位置和种群中的最优粒子来反映的;粒子群通过一定方式(即通过对个体最优粒子的记忆和对全局最优粒子的学习的方式)分配这种响应而体现出种群的多样性，仅仅当粒子群中的最优粒子发生改变时，粒子群中粒子的行为才发生改变，这正体现出了粒子群的稳定性和适应性。 初始化粒子群计算每个粒子的适应度值根据粒子的适应度值更新个体极值与全局极值根据公式（2.3）(2.4)更新粒子群的速度和位置满足算法结束条件？输出优化结果，全局极值？YN2.5 标准的粒子群算法为了改善算法收敛性能，Shi和Eberhart在1998年的论文中引入了惯性权重的概念，引入惯性权重因子w后，公式(2.3).(2 .4)就变为 (2.5) (2.6)显见 ， 惯性权重W描述了粒子上一代速度对当前代速度的影响，控制其取值大小可调节PSO算法的全局与局部寻优能力。w值较大，全局寻优能力强，局部寻优能力弱，反之，则局部寻优能力增强，而全局寻优能力减弱。刚开始惯性权重为常数，但后来的试验发现，动态惯性权值能够获得比固定值更为好的寻优结果。动态惯性权值可以在PSO搜索过程中线性变化，亦可根据PSO性能的某个测度而动态改变。惯性权重的引入，可从不同的角度调整算法全局和局部搜索能力，使PSO算法的性能得到了很大提高，也使PSO算法得以比较成功地应用于很多实际问题。2.6粒子群优化的研究现状（1）理论研究现状在算法的理论研究方面，有部分研究者对算法的收敛性进行了分析，更多的研究者致力于研究算法的结构和性能改善，包括参数分析，拓扑结构，粒子多样性保持，算法融合和性能比较等。在收敛性研究方面，Clerc和Knenedy将PSO基本公式简化为一维空间中的单个粒子，分析了其在离散时间和连续时间的移动情况，并提出了完全描述系统的五维模型，里面包含的参数能够控制系统收敛的趋势。Ozcan和Mohan在假设w=1,C1和C2为常数，和为固定点情况下，通过理论分析将一个微粒随时间变化描述为波的运行，并对不同区域进行了轨迹分析。Trealea应用离散动态系统理论对简化PSO模型的动态行为和收敛性进行了分析，推导出对参数选择的参考准则。PSO的早期版本没有惯性权重，Shi和Ebehart首次提出了惯性权重的概念，来对基本算法中的速度更新公式进行修正。修正后的公式已成为PSO的标准版本，为大多数研究者所使用。惯性权重常被设置为随时间递减的时变权重来提高算法性能，如将权重设为1.4到0，0.9到0.4，0.95到0.2等。shi和Eberhart还提出一个模糊系统来一调节惯性权重，取得较好效果。Kennedy把Cl和C2分别设置为0，得到了PSO的“只有社会(social only)的模型”(Cl=0)，“只有认知(cognition only)的模型”(C2=0)和“无私(selfless)的模型”(C2=0，且自己的最好解不包含在邻域内)，并分析了几种模型的表现。Suganthan的研究表明C1和C2为常数时可以取得较好的解，但不一定为2。有研究者在实验中将C1和C2取为1.494，1.7等。EI一Gallad等对种群规模，迭代次数和粒子速度的选择进行了分析并给出选择的基本原则，并通过对约束问题的求解来验证这些参数的基本影响。在算法的拓扑结构研究方面，Angeline发现PSO可以比其他演化算法更快找到较好解，但后期精确搜索性能不好，为此suganthan引入一个变化的邻域算子(neighborhood operator)来改善解的质量，在优化初始阶段，粒子邻域就是其本身，随着迭代次数增加，邻域逐渐增大，直至包括所有粒子。基本PSO算法中邻域是基于索引号划分的，Suganthan使用了基于空间位置划分的方案，称为空间邻域(space neighborhoods)法。Kennedy对几种拓扑结构的实验表明拓扑非常影响算法性能，且最佳拓扑结构因问题而定。Knenedy还提出了混合空间邻域和环形拓扑方法的局部PSO版本，称为社会趋同(social stereotyping)法。Kennedy和Mendes系统分析了不同的拓扑结构对算法性能的影响，说明了构造种群结构的基本原则。为克服早熟现象，保持粒子群体的多样性是提高算法性能的重要途径，很多学者对此进行了研究。Riget和Vestersrtom将排斥过程引入标准PSO，通过多样性度量控制种群特征，从而实现粒子间吸引和排斥平衡以避免早熟现象。Lovbjerg和Krink将自组织临界控制引入PSO来增加种群的多样性，实验结果表明可以使算法有更快收敛速度和找到更好的解。Krink等还提出一种粒子空间扩展的方法来解决粒子间的冲突和聚集问题，并增强了粒子逃脱局优的能力。Al一kazemi和Mohan通过在求解离散和连续问题的不同阶段设置不同的阶段性目标建立了多阶段(multi一phase)PSO，这种算法在实验中表现出比标准PSO，GA和进化规划更好的性能。Xie等将负嫡(negative entropy)概念引入标准PSO，通过将混沌因素加入到粒子更新过程建立了开放消耗系统，两个多峰函数的优化实验结果表明了其有效性。在PSO和其他算法的融合以及性能的比较方面，也有很多研究成果出现。Angeline提出了采用进化计算中的选择操作的混合PSO(HPSO)模型。Lovbjerg等将PSO与进化算法的思想融合，通过将繁殖和子种群的概念引入PSO，建立了两种混合型粒子群优化器，获得了更快的收敛速度和发现更好解的潜力。Natasuki等提出了带有高斯变异的PSO算法。Eberhart和shi将PSO与标准GA进行了分析和性能比较。国内也有很多学者进行了这方面的研究，提出了基于模拟退火的PSO算法，免疫粒子群算法，基于群体适应度方差自适应变异的PSO算法，将PSO与差别进化算法结合等。PSO最初多用于解决连续优化问题，Eberhart和Kennedy又提出了PSO的离散二进制版本，用于解决组合优化问题。Knenedy和spears还利用多峰问题产生器把PSO的二进制版本和三种版本的GA进行了比较。Mohan等提出了几种二进制方法，但是实验有限，没有得到确定性的结论。Hu等介绍了解决数列问题的改进PSO。目前关于PSO的离散版本的研究还很有限，并没有一个较好的解决方案，离散变量如何进行加法和乘法处理是个严重的问题，并且离散型PSO非常容易陷入局优。（2）应用研究现状PSO最早应用于非线性连续函数的优化和神经元网络的训练，后来也被用于解决约束优化问题。Eberhart用PSO来分析人类的帕金森综合怔等颤抖类疾病。Yoshida等通过PSO对各种离散个连续变量的优化，达到控制核电机组输出稳定电压的目的。Robinson等将PSO用于剖面波状喇叭天线的优化，并与GA的优化效果进行了比较，研究了二者混合应用的可行性。Ciuprina提出一种智能PSO(Intelligent PSO)用于电磁线圈尺寸的优化。Abido将 PS0用于解决最优功率通量(OPF)问题。国内也有越来越多的学者关注PSO的应用，将其应用于非线性规划，同步发电机辩识，车辆路径，约束布局优化，新产品组合投入，广告优化，多目标优化等问题。还有一些学者尝试将PSO算法应用于解决动态优化问题，也取得了较好效果。PSO由于其算法的简单，易于实现，无需梯度信息，参数少等特点在连续非线性优化问题和组合优化问题中都表现出良好的效果。在多目标优化、数据分类、数据聚类、模式识别、电信QOS管理、生物系统建模、流程规划、信号处理、机器人控制、决策支持以及仿真和系统辩识等方面，都表现出良好的应用前景。2.7 标准粒子群优化算法存在的问题根据文献和我们进行实验得到的结果，将标准PSO算法在优化过程中表现出来的问题总结如下:(l)参数控制：对不同的问题，如何选择合适的参数来达到最优效果。(2)缺乏速度的动态调节：爬山能力不强，有时在达到一定的精度后，很难再找到更好的解。(3)早熟:粒子群过早收敛，使寻优停滞。3 带有梯度加速的粒子群算法3.1引言标准PSO算法具有很强的通用性，适用于各种优化问题，特别是实优化问题。但是这种广泛的适应性也导致对具体问题的特性考虑不够，比如没有考虑很多问题中有效的梯度信息。也有研究表明标准PSO算法与遗传算法相比，早期的迭代表现较好，能够更快的发现质量好的解存在的区域。但是后期迭代搜索效率不高。这是因为标准粒子群优化缺乏速度的动态调节，爬山能力不强。针对如上问题，本文提出一种带有梯度加速的PSO算法，对标准PSO算法进行了改进。在粒子的速度更新中以一定概率加入梯度信息，使粒子的移动更有针对性，移动更有效率。同时为了减小粒子陷入局优的可能性，对群体最优值进行观察。在寻优过程中，当最优信息出现停滞时，对部分粒子进行重新初始化，从而保持群体的活性。通过实验对带有梯度加速的PSO算法的适用范围进行了讨论。3.2带有梯度加速的粒子群算法3.2.1原理与步骤与其他进化算法一样，标准PSO算法利用种群进行随机搜索，没有考虑具体问题的特性，不使用梯度信息，而梯度信息往往包含目标函数的一些重要信息对于函数,其梯度可表示为函数值的最速下降方向是负梯度方向。带有梯度加速的粒子群算法的思想：通过引入梯度信息来影响粒子速度的更新，构造出一种带有梯度加速的PSO算法每次粒子进行速度和位置更新时，每个粒子以概率P按式(2.5)和式(2.6)更新，并以概率(1一P)按梯度信息更新，在负梯度方向进行一次直线搜索来确定移动步长。直线搜索采用黄金分割法，这一步骤可以详述如下： 产生一伪随机数，若大于P，则按照公式（2.5）和（2.6）更新粒子速度和位置； 否则，试探方式确定一单谷搜索区间， 计算， 计算， 若，（为终止限），则即为粒子的下一位置；否则转 判别是否满足，若满足，则置，然后转；否则若，则置，然后转。同时，为防止陷入局优，在群体最优信息陷入停滞时，对群体进行部分重新初始化，以保持群体的活性，减小群体陷入局优的可能性。梯度信息的加入使粒子的移动更具针对性和效率，进一步提高了PS0算法的收敛速度，但也会增加算法对问题的依赖性，特别是有些梯度信息极易将粒子引入局优。所以带有梯度加速的PSO算法需要根据问题的性质来调整梯度信息对于粒子移动的影响程度。综上，带有梯度加速的PSO算法主要步骤如下：1)在初值范围内随机初始化粒子种群，包括随机位置和速度2)评价每个粒子的适应值3)将每个粒子的适应值与其经历过的最好值进行比较，如果更好，则将其作为当前粒子的个体最优值4)将每个粒子的个体最优值与群体最优值进行比较，如果更好，则将其作为群体最优值；若规定迭代次数内群体最优值未得到更新，则按一定概率将部分粒子重新初始化5)对于每个粒子的速度和位置，以概率P按（2.5）和（2.6）更新，并以概率(1一p)按梯度信息更新，在负梯度方向进行一次直线搜索来确定移动步长6)若未达到终止条件，则转步骤2)3.2.2梯度加速的流程图改进PSO算法的梯度加速过程体现在上面的第5步，为直观说明，这里将其详细表示为图3.1：产生一伪随机数, apN将方向设为负梯度方向沿方向进行直线搜索，得到 按公式（2.5）更新速度按公式（2.6）更新位置Y 图3.1梯度加速的流程图3.3实验与结果分析3.3.1实验设置为了对标准PSO算法和带有梯度加速的PSO算法进行比较，并对改进后算法的问题依赖性进行研究，这里采用2个测试函数Schaffers f6函数和Sphere函数。 函数名 表达式 维数 初值范围 目标值Schaffers f62 Sphere30 0.01标准PSO算法及带有梯度加速的PSO算法分别选取种群30和种群10并选取不同的惯性权重(这里均采用时变权重)，为了全面比较优化效果，采用两种停止准则: 用两种停止准则:(1)是否达到规定的达优值(观察其达优率、平均迭代次数及平均计算时间);(2)迭代4000次(观察其取得的最优值)。改进PSO算法中，当20次迭代未取得更好的群体最优值时，认为群体最优信息陷入停滞，在粒子群体中随机选取30%进行重新初始化，重新初始化的方式为在初值范围内随机产生一个新的粒子代替原粒子