毕业论文-非线性规划问题的粒子群算法（定稿）

西安科技大学毕业设计（论文）PAGEPAGEI西安科技大学学士学位论文题目：非线性规划问题的粒子群算法作者：摘要优化技术是一种以数学为基础，用于求解各种组合优化问题的应用技术。最优化问题是人们在工程技术、科学研究、和经济管理等诸多领域中经常碰到的问题，它是指在满足一定的约束条件下，寻找一组参数值，使目标函数达到最大或最小。最优化问题根据其目标函数、约束条件的性质以及优化变量的取值范围可以分为许多类型，例如：根据目标函数和约束条件是否均为线性表达式，把最优化问题划分为线性规划问题和非线性规划问题。针对不同的最优化问题，提出了许多不同的优化方法，如牛顿法、共轭梯度法、Polar-Ribiere法、拉格朗日乘子法等。这些优化算法能很好地找到问题的局部最优点，是成熟的局部优化算法。但是随着人类生存空间的扩大以及认识与改造世界范围的拓展，人们发现由于问题的复杂性、约束性、非线性、建模困难等特点，解析性优化算法已不能满足人们的要求，需要寻找一种适合于大规模并行且具有智能特征的优化算法。现代进化类方法如人工神经网络、遗传算法、禁忌搜索法、模拟退火法和蚁群算法等在解决大规模的问题时体现出强大的潜力，它们可以在合理的时间限制内逼近优化问题的较好可行解。其中，遗传算法和蚁群算法被称为智能优化算法，其基本思想是通过模拟自然界生物的行为来构造随机优化算法。近年来，另一种智能优化算法—粒子群算法（particleswarmoptimization，简称PSO）越来越受到学者的关注。粒子群算法是美国社会心理学家JamesKennedy和电气工程师RussellEberhart在1995年共同提出的，它是受到鸟群社会行为的启发并利用了生物学家FrankHeppner的生物群体模型而提出的。它用无质量无体积的粒子作为个体，并为每个粒子规定简单的社会行为规则，通过种群间个体协作来实现对问题最优解的搜索。由于算法收敛速度快，设置参数少，容易实现，能有效地解决复杂优化问题，在函数优化、神经网络训练、图解处理、模式识别以及一些工程领域都得到了广泛的应用。关键字：非线性规划；粒子群算法；智能算法ABSTRACTOptimizationtechnologyisbasedonmathematicsandcansolvevariouscombinatorialoptimizationproblems.Manyproblemspossessasetofparameterstobeoptimized,especiallyinthefieldsofengineeringtechnology,scientificresearchandeconomicmanagement.Optimizationistolookforasetofparametersindefiniterestrictionwiththeaimofminimizingormaximizingtheobjectivefunction.Accordingtoqualityofobjectivefunctionandrestrictconditionandscopeofvariable,optimizationproblemcanbedividedintolotsoftypes.Forexample,ifobjectivefunctionandrestrictconditionarebothlinealexpression,thisproblembelongstolinearprogrammingproblem,ifnot,itbelongstononlinearprogrammingproblem.Differentmethodshavebeenpresentedtosovledifferentkindsofproblems,suchasNewton'smethod,conjugategradientmethod,Polar-Ribiere'smethod,LagrangeMultiplierMethodetc.Thesemethodscannicelyfindlocalextremeindifferentproblems.However,withthedevelopmentofhumanlivingspaceandthescopeofunderstandingandtransformingtheworld,peoplehavefoundthatbecauseofthecomplexity,binding,nonlinear,modelingdifficultiescharacteristic,itisnoteasytofindasatisfyinganalyticsolutions.It’snecessarytofindaoptimizationalgorithmsuitingforlarge-scaleparallelOperationwithsmartfeatures.Modernevolutionmethodssuchasartificialneuralnetworks,geneticalgorithms,Taboosearchmethod,simulatedannealing,andantcolonyalgorithmetc.,reflectastrongpotentialinsolvinglarge-scaleproblems.Theycanapproximatethebetterfeasiblesolutionfortheoptimizationproblemwithinareasonableperiodoftime.TheGeneticAlgorithmandantcolonyalgorithmareknownasintelligentoptimizationalgorithm,andtheirbasicideaistoconstructstochasticoptimizationalgorithmsbysimulatingthebehaviorofthenaturalworld.Inrecentyears,anotherkindofintelligentoptimizationalgorithm–PSOalgorithm(particleswarmoptimization,orPSO)increasinglyaccessestotheconcernsofscholars.PSOalgorithmisproposedbyAmericansocialpsychologistJamesKennedyandelectricalengineerRussellEberhartin1995,anditisinspiredbybirdpopulations'socialbehaviorandusesthebiologicalgroupmodelofbiologistFrankHeppner.Itusesparticleswithoutqualityandvolumesindividuals,providessimplesocialrulesofconductforeachparticle,andsearchestheoptimalsolutiontotheproblemthroughindividualcollaborationamongpopulations.Thealgorithmconvergesfast,needinglessparameters.Alsoitiseasilyachieved,andcaneffectivelysolvecomplexoptimizationproblems.Ithasbeenwidelyusedinfunctionoptimization,neuralnetworktraining,graphicprocessing,patternrecognitionaswellassomeengineeringfields.KeyWords:NonlinearProgramming;PSO(ParticleSwarmoptimization);Intelligentalgorithm目录1概论 11.1背景介绍 11.1.1非线性规划简介 11.1.2粒子群算法简介 11.2研究内容 22非线性规划的分析 32.1非线性规划的概念 32.2非线性规划的应用 32.3非线性规划相关的概念 42.4凸函数与凸规划 42.4.1凸函数定义 42.4.2凸规划 53基本的非线性规划算法 53.1罚函数概述 53.2无约束非线性规划求解算法描述 73.2.1最优速下降法 73.2.2共轭梯度法 83.2.3牛顿法 93.3算法优缺点性能分析 104基本粒子群算法 114.1粒子群算法概述 114.1.1粒子群算法发展 114.1.2粒子群算法简介 124.1.3粒子群算法的特点 124.1.4粒子群算法的应用 134.2基本粒子群算法 144.2.1基本遗传算法的构成要素 144.2.2基本遗传算法的形式化定义 154.2.3基本遗传算法描述 154.3粒子群算法的关键 164.3.1粒子状态向量形式的确定 164.3.2适应度函数的建立 164.3.3粒子多样性的保证 174.3.4粒子群算法的运行参数设置 175基于粒子群算法的非线性规划问题的求解设计 185.1实用粒子群算法设计 185.1.1编码方法设计 185.1.2适应度函数设计 185.1.3基于约束适应度优先排序的约束条件处理方法 195.1.4动态邻域算子 195.1.5可变惯性权重和最大速度 205.1.6粒子群算法运行参数设计 205.2非线性规划的粒子群算法程序设计 215.2.1算法过程描述 215.2.2粒子群算法程序流程图 216基于粒子群算法的非线性规划求解的性能分析 306.1概述 306.2粒子群算法参数设置效果比较 306.3时间复杂度 336.3.1理论时间复杂度 336.3.2样本数对算法运行时间的影响 336.4算法的发展与展望 367总结 37致谢 38参考文献 391概论1.1背景介绍1.1.1非线性规划简介具有非线性约束条件或目标函数的数学规划，是运筹学的一个重要的分支，非线性规划研究一个n元实函数在一组等式或不等式的约束条件下的机制问题且目标函数和约束条件至少有一个是未知量的非线性函数，目标函数和约束条件都是线性函数的情形则属于线性规划。非线性规划是20世纪50年代才开始形成的一门新兴学科。1951年H.W库恩和A.W塔克发表的关于最优性条件的论文是非线性规划正式诞生的一个重要标志。在50年代可得出了可分离规划和二次规划的n种解法，它们大都是以G.B.丹齐克提出的解线性规划的单纯形法为基础的。50年代末到60年代末出现了许多解非线性规划问题的有效的算法，70年代又得到进一步的发展。非线性规划在工程、管理、经济、科研、军事等方面都有广泛的应用，为最优设计提供了有力的工具。非线性规划问题广发存在于科学与工程领域，是一类比较难以解决的优化问题，没有普遍使用的解法。传统的求解该问题的方法（如罚函数，可行方向法，以及变尺度法等）是基于梯度的方法所以目标函数与约束式必须是可微的，并且这些方法只能保证求的局部最优解。1.1.2粒子群算法简介粒子群算法（ParticleSwarmoptimization，PSO）的基本概念源于对于鸟群捕食行为的简化社会模型的模拟，1995年由Kenndy和Eberhart等人提出，它同遗传算法类似，通过个体间的协作和竞争实现全局搜索系统初始化为一组随机解，称之为粒子。通过粒子在搜索空间的飞行完成寻优，在数学公式中即为迭代，它没有遗传算法的交叉及变异算子，而是粒子在解空间追随最优的粒子进行搜索。PSO算法的改进主要在参数选择、拓扑结构以及与其他优化算法相融合方面。据此当前典型的改进算法有：自适应PSO算法、模糊PSO算法、杂交PSO算法、混合粒子算法（HPSO）和离散PSO算法等等。其中自适应和模糊PSO算法是EberhartShi研究了惯性因子ω对优化性能的影响，发现较大的ω值有利于跳出局部极小点，较小的ω值有利于算法的收敛。自适应PSO算法通过线性地减少ω值动态的调整参数ω，而模糊PSO算法则在此基础上利用模糊规则动态调整参数ω的值，即构造一个2输入、1输出的模糊推理机来动态地修改惯性因子ω。杂交和混合粒子群算法（HPSO）是受遗传算法、自然选择机制的启示，将遗传算子与基本PSO相结合而得。杂交PSO在基本PSO中引入了杂交算子，两者均取得了满意的结果，改善了算法的性能。基本PSO算法是求解连续函数优化的有力工具，但对离散问题却无能为力。因此Kenndy和Eberhart发展了离散PSO算法，用于解决组合优化问题等。在一定程度上完善发展了基本PSO算法，并将其应用于旅行商问题（TSP）的求解，取得了较好的结果。目前PSO已经广泛应用于函数优化、神经网络训练、模糊系统控制以及其它遗传算法的应用领域。最初应用到神经网络训练上，在随后的应用中PSO又可以用来确定神经网络的结构。一般说来，PSO比较有潜在的应用包括系统设计、多目标优化、分类、模式识别、调度、信号处理、决策、机器人应用等。其中具体应用实例是非线性规划的粒子群算法。总之，PSO算法的应用十分广泛，它有着比较好的发展前景，值得做进一步的研究。1.2研究内容本课题主要研究非线性规划的粒子群算法分析与实现。将非线性规划的问题使用粒子群最优算法求解其最优解，在一般求解非线性规划的问题时都与选择的算法有很大的关系，在选择变尺度法和梯度法时都必须考虑非线性规划函数的可微性，在初始值选择上也给函数的局部收敛带来局部的最优，不能达到全局最优解，这样就给一些其它非线性规划问题带来很大的困难。粒子群算法（PSO）是一种新兴的优化技术，通过粒子追随自己找到最好解和整个群的最优解来完成优化。该算法简单易实现，可调参数少是解决非线性规划问题的比较理想的算法。题目以粒子群算法为工具，设计基于非线性规划问题的应用，并对求解过程总结，比较其它算法的优越性和其存在的问题。2非线性规划分析2.1非线性规划的概念如果目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做非线性规划问题。其可分为两大类问题有约束问题与无约束问题，它们在处理方法上有明显的不同。实际问题中大多数都是有约束条件的问题。球接待有约束条件的问题比起无约束问题要困难得多，也复杂得多。在每次迭代时，不仅要使目标函数值有所下降，而且要使迭代点都落在可行域内。与线性规划一样，非线性规划也是运筹学的一个重要的分支，于20世纪50年代开始逐步形成，到20世纪70年代开始处于兴旺发展时期。随着计算机技术的日益发展，很多领域越来越重视这门学科，应用非线性规划方法进行设计、管理等，非线性规划理论自身也得到了进一步的发展。关于求解非线性规划的迭代方法有二分法、简单迭代法、牛顿迭代法与拟牛顿迭代法、同论延拓法、单纯形法等。以上方法都有一定的局限性。2.2非线性规划的应用非线性规划在军事、经济、管理、生产过程自动化、工程设计和产品优化设计等方面都有着重要的应用。但非线性规划的研究目前还不成熟，有许多问题需要进一步完善。非线性规划不像线性规划有统一的算法，对于不同的问题需要用不同的算法处理，现阶段各种算法都有一定的局限性，只有对各种算法加以改正，才能有效地解决人们在日常的生产、生活中遇到的优化问题，做出最优的决策。一般来说，解非线性规划问题要比求解线性规划的问题困难得多，而且也不想线性规划那样有统一的数学模型及如单纯形法这一通用的解法，非线性规划的各种算法大都有自己特定的适应范围。都有一定的局限性，到目前为止还没有适合于各种非线性规划问题的一般算法。这正是需要人么进一步研究的课题。非线性规划在工程、管理、经济、科研、军事等方面都有广泛的应用，为最优设计提供了有力的工具。例如：如何在有人力、物力、财力要求的前提下合理安排产品生产，以取得最高的利润；如何设计某种产品，在满足规格、性能要求的前提下，达到最低的成本；如何确定一个自动控制系统的某些参数，使系统的工作状态最佳；如何安排库存储量，既能保证供应，又使储存费用最低；如何分配一个动力系统中各电站的负荷，在保证一定指标要求的前提下，使总耗费量最小；如何组织货源，既能满足顾客需要，又使资金周转最快等对于静态的最优化问题，当目标函数或约束条件出现未知量的非线性函数，且不便于线性化，或勉强线性化后会招致较大误差时，就可以应用非线性规划的方法去处理。2.3非线性规划相关的概念定义：如果目标函数或约束条件中至少有一个是非线性规划函数时的最优化问题就叫做非线性规划问题。一般形式：minSKIPIF1<0SKIPIF1<0SKIPIF1<0（2-1）其中SKIPIF1<0是定义在SKIPIF1<0上的实值函数，简记：SKIPIF1<0其它情况：求目标函数的最大值或约束条件为小于等于零的情况，都可通过取其相反数化为上述一般形式。定义1把满足问题(2-1)中条件的解SKIPIF1<0称为可行解（或可行点），所有可行点的集合称为可行集（或可行域）．记为D．即SKIPIF1<0问题(2-1)可简记为SKIPIF1<0定义2对于问题(2-1)，设SKIPIF1<0，若存在SKIPIF1<0，使得对于一切SKIPIF1<0且‖SKIPIF1<0‖<SKIPIF1<0，都有SKIPIF1<0则称SKIPIF1<0是SKIPIF1<0在D上的局部极小值点（局部最优解）。特别地当SKIPIF1<0时，若SKIPIF1<0，则称SKIPIF1<0在D上的严格局部极小值点（严格局部最优解）。定义3对于问题(2-1),设SKIPIF1<0，对于任意的SKIPIF1<0，都有SKIPIF1<0则称SKIPIF1<0是SKIPIF1<0在D上的全局极小值点（全局最优解）。特别地当SKIPIF1<0时，若SKIPIF1<0，则称SKIPIF1<0是SKIPIF1<0上的严格全局极小值点（严格全局最优解）。2.4凸函数与凸规划在最优化理论中，凸集与凸函数占有非常重要的地位。通过对凸函数的学习了解求解非线性规划的基础知识。2.4.1凸函数定义设SKIPIF1<0为凸集，SKIPIF1<0是定义在凸集S上的函数，如果SKIPIF1<0恒有SKIPIF1<0，则称SKIPIF1<0是凸集S上的凸函数，如果上式取严格不等式，则称SKIPIF1<0是凸集S上的严格凸函数，将上式的不等号反向，即可得到凹函数和严格凹函数的定义。凸函数的性质如下：设SKIPIF1<0是定义在凸集S上的凸函数，则SKIPIF1<0，以及SKIPIF1<0，恒有SKIPIF1<0。设SKIPIF1<0是定义在凸集S上的凸函数，如果SKIPIF1<0，那么SKIPIF1<0仍是凸集S上的凸函数。设SKIPIF1<0是定义在凸集S上的凸函数，那么对任意实数SKIPIF1<0，集合SKIPIF1<0是S的凸子集，称为水平集。凸函数的判定：设n元函数SKIPIF1<0可微，称列向量SKIPIF1<0为f在X处的梯度，记作SKIPIF1<0。若SKIPIF1<0二阶连续可微，则称f的所有二阶偏导数构成的n阶方阵SKIPIF1<0为f在X处的二阶导数矩阵或称海赛（Hessian）矩阵，记作SKIPIF1<0或SKIPIF1<0。f在X处沿梯度方向有最快的上升趋势。一阶可微的函数SKIPIF1<0是凸集S上的凸函数的充分必要条件是：SKIPIF1<0，恒有SKIPIF1<0类似地，SKIPIF1<0是在凸集S上的严格凸函数的充分必要条件是上式不等号严格成立。二阶连续可微的函数SKIPIF1<0是凸集S上的凸函数的充分必要条件是：SKIPIF1<0为半正定矩阵。类似地，SKIPIF1<0是凸集S上的严格凸函数的充分必要条件是SKIPIF1<0为正定矩阵。2.4.2凸规划若SKIPIF1<0是凸函数，SKIPIF1<0是凹函数（即所有SKIPIF1<0全为凸函数），则称这种规划问题为凸规划。显然，线性规划是一种凸规划，其性质有如以下：（1）可行解集为凸集。（2）最优解集为凸集（假定最优解存在）。（3）中心任何局部最优解也是其全局最优解。（4）若目标函数为严格凸函数，且最优解存在，则其最优解必唯一。3基本非线性规划算法3.1罚函数法概述罚函数法基本思想是通过构造罚函数把约束问题转化为一系列无约束最优化问题，进而用无约束最优化方法去求解。这类方法称为序列无约束最小化方法，简称为SUMT法。其一为SUMT外点法，其二为SUMT内点法。SUMT外点法其基本思想是：利用目标函数和约束条件组成辅助函数对一般的非线性规划：minSKIPIF1<0SKIPIF1<0(3.1)可设：SKIPIF1<0(3.2)将问题(3.1)转化为无约束问题：SKIPIF1<0(3.3)其中T(X,M)称为罚函数，M称为罚因子，带M的项称为罚项，这里的罚函数只对不满足约束条件的点实行惩罚：当SKIPIF1<0时，满足各SKIPIF1<0故罚项=0，不受惩罚，当SKIPIF1<0时，必SKIPIF1<0或SKIPIF1<0约束条件，故罚项>0，要受惩罚。SUMT外点法（罚函数法）的迭代步骤：1、任意给定初始点SKIPIF1<0，取SKIPIF1<0，给定允许误差SKIPIF1<0，令k=1；2、求无约束极值问题SKIPIF1<0的最优解，设为SKIPIF1<0，即SKIPIF1<0；3、若存在SKIPIF1<0，使SKIPIF1<0，则取SKIPIF1<0令k=k+1返回(3.2)，否则，停止迭代。取得最优解SKIPIF1<0。计算时也可将收敛性判别准则SKIPIF1<0改为SKIPIF1<0。罚函数法的缺点是：每个近似最优解SKIPIF1<0往往不是容许解，而只能近似满足约束，在实际问题中这种结果可能不能使用；在解一系列无约束问题中，计算量太大，特别是随着SKIPIF1<0的增大，可能导致错误。SUMT内点法（障碍函数法）其基本思想是：迭代过程中总是从可行域内的出发，并保持在可行域内进行搜索。该方法适用于只有不等式约束的问题。考虑问题：SKIPIF1<0(3.4)设集合SKIPIF1<0，SKIPIF1<0是可行域中所有严格内点的集合。构造障碍函数SKIPIF1<0或SKIPIF1<0其中称SKIPIF1<0或SKIPIF1<0为障碍项，r为障碍因子。这样问题(3.4)就转化为求一系列极值问题：SKIPIF1<0得SKIPIF1<0。内点法的迭代步骤：1、给定允许误差SKIPIF1<0，取SKIPIF1<0；2、求出约束集合D的一个内点SKIPIF1<0，令k=1；3、以SKIPIF1<0为初始点，求解SKIPIF1<0，其中SKIPIF1<0的最优解，设为SKIPIF1<0；4、检验是否满足SKIPIF1<0或SKIPIF1<0，满足，停止迭代，SKIPIF1<0；否则取SKIPIF1<0，令k=k+1，返回3。3.2无约束非线性规划求解方法无约束非线性规划问题的求解方法分为解析法和直接法两类。解析法需要计算函数的梯度，直接法仅通过比较目标函数值的大小来移动迭代点。其中最速下降法、共轭梯度法、牛顿法、变尺度法等解析方法和步长加速法、旋转方法、方向加速法等直接方法。一般来说，无约束非线性规划问题的求解是通过一系列一维搜索来实现。因此，如何选择搜索方向是求解无约束非线性规划问题的核心问题，搜索方向的不同选择，形成不同的求解方法。3.2.1最优速下降法最速下降法是由法国著名数学家Cauchy于1847年首次提出。该方法将目标函数SKIPIF1<0在SKIPIF1<0的负梯度方向SKIPIF1<0作为下降迭代法的迭代公式SKIPIF1<0中的SKIPIF1<0，并通过求解SKIPIF1<0，确定最佳步长SKIPIF1<0。若SKIPIF1<0具有二阶连续偏导，在SKIPIF1<0处作SKIPIF1<0的二阶泰勒展开式SKIPIF1<0对SKIPIF1<0求导令其等于零，得最佳步长SKIPIF1<0。最速下降法的计算步骤如下：（1）给定初始点SKIPIF1<0，允许误差SKIPIF1<0，置k=0（2）计算搜索方向SKIPIF1<0。（3）若SKIPIF1<0，则停止计算，得近似极小点SKIPIF1<0；否则，确定最佳步长SKIPIF1<0，转第（4）步（4）令SKIPIF1<0，置k=k+1，转第（2）步。3.2.2共轭梯度法共轭梯度法最初由Hesteness和Stiefel于1952年为求解非线性方程组而提出，后来成为求解无约束非线性规划问题的一种重要的方法。其基本思想是：把共轭性与最速下降方法相结合，利用已知点处的梯度构造一组共轭方向，并沿这组方向进行搜索，求出目标函数的极小点。该方法对于正定二次函数能在有限步内达到极小点，即该算法具有二次终结性。对于问题SKIPIF1<0，由于SKIPIF1<0，可推出其唯一极小点SKIPIF1<0。如果已知某共轭向量组SKIPIF1<0，由SKIPIF1<0（3.1）可知，问题SKIPIF1<0的极小点SKIPIF1<0可通过下列算法得到SKIPIF1<0（3.2）该算法称为共轭方向法。它要求搜索方向SKIPIF1<0必须共轭，确定各近似极小点时必须按最佳一维搜索进行。共轭梯度法是共轭方向的一种，它的方向是利用一维搜索所得极小点处的梯度生成的。由于SKIPIF1<0，故SKIPIF1<0，又因为SKIPIF1<0故SKIPIF1<0。任取初始近似点SKIPIF1<0，并取初始搜索方向的负梯度方向，即SKIPIF1<0，沿射线SKIPIF1<0进行一维搜索，得到SKIPIF1<0，其中SKIPIF1<0满足SKIPIF1<0，计算SKIPIF1<0，由SKIPIF1<0，从而SKIPIF1<0和SKIPIF1<0正交，构成正交系，在由它构成的子空间中搜寻SKIPIF1<0，令SKIPIF1<0，SKIPIF1<0为待定系数，欲使SKIPIF1<0和SKIPIF1<0为A共轭，从而可求的SKIPIF1<0。令SKIPIF1<0由此可得SKIPIF1<0。综合以上步骤可以得到共轭梯度法德一般计算公式如下：SKIPIF1<0(3.3)其中SKIPIF1<0为初始近似，SKIPIF1<0。对于正定二次函数，从理论上说，进行n次迭代即可达到极小点。但是，在实际计算中，由于数据的输入以及计算误差的积累，往往做不到这一点。此外，由于n维问题的共轭方向最多只有n个，在n步以后继续加上进行是没有意义的。因此，在实际应用时，如迭代到n步还不收敛，就将SKIPIF1<0作为新的初始近似，重新开始迭代。共轭梯度法的计算步骤如下：（1）选择初始近似SKIPIF1<0，给出允许误差SKIPIF1<0。（2）计算SKIPIF1<0，置k=0。（3）用式(3.3)计算SKIPIF1<0。（4）若k<n-1，则置k=k+1，并转向第（3）步，否则，转向第（5）步。（5）若SKIPIF1<0，停止计算，SKIPIF1<0即为近似极小点；否则，令SKIPIF1<0，并转向第（2）步。3.2.3牛顿法牛顿法在搜索方向上比梯度法有所改进，它不但利用了目标函数的搜索点的梯度，而且还利用了目标函数的二阶偏导数。也就是说，它不但考虑了函数的梯度，还考虑了梯度的变化趋势，所以在更大范围内考虑了函数的性质。与梯度法一样，牛顿法也有其缺陷。例如对一般多变量非线性函数的极小化问题，它可能收敛不到所寻找的极小值点。因而，有些在实践中被认为非常成功的方法，是由牛顿法经过修改后得到的。假定SKIPIF1<0是二阶连续可微函数，在给定点SKIPIF1<0附近取SKIPIF1<0的二阶泰勒多项式作逼近SKIPIF1<0(3.4)式中，SKIPIF1<0，SKIPIF1<0为函数在点SKIPIF1<0的n阶海赛矩阵，设为非奇异阵。SKIPIF1<0的极小点处，必然满足SKIPIF1<0，将SKIPIF1<0代入式(3.4)，然后求一阶微分得：SKIPIF1<0(3.5)可解得点SKIPIF1<0(3.6)式中，SKIPIF1<0为函数SKIPIF1<0在点SKIPIF1<0的搜索方向，称为牛顿方向，即SKIPIF1<0。若令SKIPIF1<0为二次函数，有SKIPIF1<0（Q为对称非奇阵）则SKIPIF1<0，即为海赛矩阵，它是一个常数矩阵。用SKIPIF1<0代入(3.4)右边，可知该式是一个等式而不是近似式。若再设Q为正定矩阵，则SKIPIF1<0有一极小值点SKIPIF1<0，并且SKIPIF1<0，因此有SKIPIF1<0。令SKIPIF1<0综合这两个方程得SKIPIF1<0将此式与(3.6)式比较可知，从任意点SKIPIF1<0出发，用牛顿法只要一步就达到一个二次函数的极小值点，如果这个二次函数存在极小值的话。但对一般的非线性函数，一步是达不到SKIPIF1<0的极小点的。迭代中往往也会有一些问题。例如SKIPIF1<0在SKIPIF1<0点非正定，或者由式(3.6)得到的点SKIPIF1<0不靠近SKIPIF1<0，以致SKIPIF1<0在SKIPIF1<0附近的二阶近似在SKIPIF1<0处无效，还可能出现SKIPIF1<0的情况等等。为了补救这些问题，人们往往用一个限步牛顿公式：SKIPIF1<0来代替式(3.6)，其中SKIPIF1<0的选择有各种方法，总是使SKIPIF1<0。一般也多用使SKIPIF1<0沿牛顿方向取极小的一维搜索法。牛顿法迭代步骤如下：（1）取初始点SKIPIF1<0，允许误差SKIPIF1<0，令k：=0。（2）检验是否满足收敛性判别准则SKIPIF1<0，若满足判别准则，迭代停止，得到SKIPIF1<0。否则进行（3）。（3）令SKIPIF1<0。（4）求单变量极值问题的最优解SKIPIF1<0，SKIPIF1<0。（5）令SKIPIF1<0，k：=k+1。转到（2）。3.3算法性能优缺点分析（1）梯度法优点：计算量少，存储变量较少，初始点要求不高。梯度法缺点：初值依赖，收敛慢，最速下降法适用于寻优过程的前期迭代或作为间插步骤，越接近极值点时，收敛熟读越慢，后期宜选用收敛快的算法。（2）牛顿迭代法优点：收敛速度很快。牛顿迭代法缺点：当维数较高时，计算SKIPIF1<0的工作量很大，初值依赖，当初值选择不好时，有可能计算出现异常，导致迭代无法进行，该法需要修正。所以此算法在计算复杂，要计算二次偏导数，又要计算逆矩阵。尤其在变量较多时，计算量就更大了。（3）罚函数法在实际应用中，由于外点法的初始点可任意选择，不必保证在可行域内，迭代过程中也不要求在可行域内，而是逐步向可行域靠近，因此它比内点法优越。内点法要求初始点在可行域内，在搜索过程中要控制中要控制每次的搜索步长，以保持迭代点的可行性，因此，在实现上要比外点法困难，但它的最终收敛点总在可行域内，即使最后只得到一个粗略的近似最优点，这个点也必是可行的。4基本粒子群算法4.1粒子群算法概述4.1.1粒子群算法发展1995年美国电气工程师Eberhart和社会心理学家Kenndy基于鸟群觅食行为提出了粒子群优化算法（particleswarmoptimization，PSO），简称粒子群算法。由于该算法概念简明、实现方便、收敛速度快、参数设置少，是一种高效的搜索算法。PSO是模拟鸟群随机搜寻食物的捕食行为。假设在搜索食物区域里只有一块食物，所有的小鸟都不知道食物在什么地方，所以Kenndy等认为鸟之间存在着互相交换信息，通过估计自身的适应度值，它们知道当前的位置离食物还有多远，所以搜索目前离食物最近的鸟的周围区域是找到食物的最简单有效的办法，通过鸟之间的集体协作使群体达到最优。PSO就是从这种模型中得到启示并用于解决优化问题。在PSO中每个优化问题的潜在解都可以想象成搜索空间中的一只鸟，我们称之为“粒子”。粒子主要追随当前的最优粒子在解空间中搜索，PSO初始化为一群随机粒子（随机解），然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个“极值”来更新自己，第一个就是粒子本身所找到的最优解，这个解叫做个体极值pbest，另一个极值是整个种群目前找到的最优解，这个极值是全局极值gbest。这两个最优变量使得鸟在某种程度上朝着这些方向靠近，此外也可以不用整个种群而只用其中一部分作为粒子的邻居，那么所有邻居的极值就是局部极值，粒子始终跟随这两个极值变更自己的位置和速度直到找到最优解。到目前为止粒子群算法的发展得到越来越多的众多领域学者的关注和研究，称为解决许多问题的热点算法的研究重点。其中对PSO算法的改进也非常多，有增强算法自适应性的改进、增强收敛性的改进、增加多种群多样性的改进、增强局部搜索的改进、与全局优化算法相结合、与确定性的局部优化算法相融合等。以上所述的是对于算法改进的目的的讨论的，实际改进中应用的方法有基于参数的改进，即对PSO算法的迭代公式的形式上做改进；还有从粒子的行为模式进行改进，即粒子之间的信息交流方式，如拓扑结构的改进、全局模式与局部模式相结合的改进等；还有基于算法融合的粒子群算法的改进，算法融合可以引入其他算法的优点来弥补PSO算法的缺点，设计出更适合问题求解的优化算法。4.1.2粒子群算法简介粒子群算法是一个非常简单的算法，且能够有效的优化各种函数。从某种程度上说，此算法介于遗传算法和进化规划之间。此算法非常依赖于随机的过程，这也是和进化规划的相识之处，此算法中朝全局最优和局部最优靠近的调整非常的类似于遗传算法中的交叉算子。此算法还是用了适应值的概念，这是所有进化计算方法所共有的特征。在粒子群算法中，每个个体称为一个“粒子”，其实每个粒子代表着一个潜在的解。例如，在一个D维的目标搜索空间中，每个粒子看成是空间内的一个点。设群体由m个粒子构成。m也被称为群体规模，过大的m会影响算法的运算速度和收敛性。PSO算法通常的数学描述为：设在一个D维空间中，由m个粒子组成的种群SKIPIF1<0，其中第i个粒子位置为SKIPIF1<0，其速度为SKIPIF1<0。它的个体极值为SKIPIF1<0，种群的全局极值为SKIPIF1<0，按照追随当前最优例子的原理，粒子SKIPIF1<0将按(4.1)、(4.2)式改变自己的速度和位置。SKIPIF1<0(4.1)SKIPIF1<0(4.2)式中j=1,2,…,D，i=1,2,…m，m为种群规模，t为当前进化代数，SKIPIF1<0为分布于[0,1]之间的随机数；SKIPIF1<0为加速常数。从式(4.1)中可知，每个粒子的速度由三部分组成：第一部分为粒子先前的速度；第二部分为“认知”部分，表示粒子自身的思考；第三部分为“社会”部分，表示粒子间的信息共享与相互合作。4.1.3粒子群算法的特点粒子群算法是一种新兴的智能优化技术，是群体智能中一个新的分支，它也是对简单社会系统的模拟。该算法本质上是一种随机搜索算法，并能以较大的概率收敛于全局最优解。实践证明，它适合在动态、多目标优化环境中寻优，与传统的优化算法相比较具有更快的计算速度和更好的全局搜索能力。具体特点如下：（1）粒子群优化算法是基于群体智能理论的优化算法，通过群体中粒子间的合作与竞争产生的群体智能指导优化搜索。与进化算法比较，PSO是一种更为高效的并行搜索算法。（2）PSO与GA有很多共同之处，两者都是随机初始化种群，使用适应值来评价个体的优劣程度和进行一定的随机搜索。但PSO是根据自己的速度来决定搜索，没有GA的明显的交叉和变异。与进化算法比较，PSO保留了基于种群的全局搜索策略，但是其采用的速度-位移模型操作简单，避免了复杂的遗传操作。（3）PSO有良好的机制来有效地平衡搜索过程的多样性和方向性。（4）GA中由于染色体共享信息，故整个种群较均匀地向最优区域移动。在PSO中gbest将信息传递给其他粒子，是单向的信息流动。多数情况下，所有的粒子可能更快地收敛于最优解。（5）PSO特有的记忆使其可以动态地跟踪当前的搜索情况并调整其搜索策略。（6）由于每个粒子在算法结束时仍然保持着其个体极值。因此，若将PSO用于调度和决策问题时可以给出多种有意义的选择方案。而基本遗传算法在结束时，只能得到最后一代个体的信息，前面迭代的信息没有保留。（7）即使同时使用连续变量和离散变量，对位移和速度同时采用和离散的坐标轴，在搜索过程中也并不冲突。所以PSO可以很自然、很容易地处理混合整数非线性规划问题。（8）PSO算法对种群大小不十分敏感，即种群数目下降时性能下降不是很大。（9）在收敛的情况下，由于所有的粒子都向最优解的方向飞去，所以粒子趋向同一化（失去了多样性）使得后期收敛速度明显变慢，以致算法收敛到一定精度时无法继续优化。因此很多学者都致力于提高PSO算法的性能。4.1.4粒子群算法的应用粒子群算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的适应性，所以广泛应用于很多学科。下面是粒子群算法的一些主要应用领域：（1）函数优化。函数优化是粒子群算法的经典应用领域，也是对粒子群算法进行性能评价的常用算例。（2）约束优化。随着问题的增多，约束优化问题的搜索空间也急剧变换，有时在目前的计算机上用枚举法很难或甚至不可能求出其精确最优解。粒子群算法是解决这类问题的最佳工具之一。实践证明，粒子群算法对于约束优化中的规划，离散空间组合问题的求解非常有效。（3）工程设计问题。工程设计问题在许多情况下所建立起来的数学模型难以精确求解，即使经过一些简化之后可以进行求解，也会因简化得太多而使得求解结果与实际相差甚远。现在粒子群算法已成为解决复杂调度问题的有效工具，在电路及滤波器设计、神经网络训练、控制器设计与优化、任务分配等方面粒子群算法都得到了有效的应用。（4）电力系统领域。在其领域中有种类多样的问题，根据目标函数特性和约束类型许多与优化相关的问题需要求解。PSO在电力系统方面的应用主要如下：配电网扩展规划、检修计划、机组组合、负荷经济分配、最优潮流计算与无功优化控制、谐波分析与电容配置、配电网状态估计、参数辨识、优化设计。随着粒子群优化理论研究的深入，它还将在电力市场竞价交易、投标策略以及电力市场仿真等领域发挥巨大的应用潜在力。（5）机器人智能控制。机器人是一类复杂的难以精确建模的人工系统，而粒子群算法可用于此类机器人群搜索，如机器人的控制与协调，移动机器人路径规划。所以机器人智能控制理所当然地成为粒子群算法的一个重要应用领域。（6）交通运输领域。交通方面有车辆路径问题，在物流配送供应领域中要求以最少的车辆数、最小的车辆总行程来完成货物的派送任务；交通控制，城市交通问题是困扰城市发展、制约城市经济建设的重要因素。城市交通运输系统的管理和控制技术进行研究，来为缓解交通拥挤发挥巨大作用。其中在其解决方法中应用粒子群算法给解决问题提供了新的，有效的计算方式。（7）通信领域。其中包括路由选择及移动通信基站布置优化，在顺序码分多址连接方式（DS-CDMA）通讯系统中使用粒子群算法，可获得可移植的有力算法并提供并行处理能力。比传统的先前的算法有了显著的优越性。还应用到天线阵列控制和偏振模色散补偿等方面。（8）计算机领域。在计算机中处理各种问题都涉及到大量的信息计算的方法选择以减少程序运行的时间，增加系统解决问题的能力，其中包括任务分配问题、数据分类、图像处理等，都得到了粒子群算法的实际问题解决效率的提高。（9）生物医学领域。许多菌体的生长模型即为非线性模型提出了用粒子群算法解决非线性模型的参数估计问题。还在分子力场的参数设定和蛋白质图形的发现。根据粒子群算法提出的自适应多峰生物测定融合算法，提高了解决问题的准确性。在医学方面，如医学成像上得到的推广应用等。4.2基本粒子群算法4.2.1基本粒子群算法的构成要素（1）粒子群编码方法。基本粒子群算法使用固定长度的二进制符号串来表示群体中的个体，其等位基因是由二值符号集{0，1}所组成的。初始群体中各个个体的基因值可用均匀分布的随机数来生成。（2）个体适应度评价。通过确定局部最优迭代达到全局最优收敛，得出结果。（3）基本粒子群算法的运行参数。基本粒子群算法有下述7个运行参数需要提前设定：●r为粒子群算法的种子数，对粒子群算法其中种子数值可以随机生成也可以固定为一个初始的数值，要求能涵盖目标函数的范围内。●M：粒子群群体大小，即群体中所含个体的数量，一般取为20～100。在变量比较多的时候可以取100以上较大的数。●max_d：一般为最大迭代次数以最小误差的要求满足的。粒子群算法的最大迭代次数，也是终止条件数。●r1,r2：两个在[0,1]之间变化的加速度权重系数随机产生。●c1,c2：加速度数，取随机2左右的值。●ww：为惯性权重产生的。●vk，xk：为一个粒子的速度和位移数值，用粒子群算法迭代出每一组数值。4.2.2基本粒子群算法的形式化定义基本粒子群算法可定义为的元素：max_d——粒子群算法的最大迭代次数；r——给定个体的种子数值；fmax——为最大的惯性权值；fmin——为最小的惯性权值；pg——初始群体值；M——粒子群的群体大小；vk——粒子移动的速度；xk——粒子移动的方向；c1,c2；r1,r1——随机参数变量；[x,dd]=judge(x,M)——算法调用的求解函数。4.2.3基本粒子群算法描述beginInitalize;%包括初始化粒子群数，粒子初始速度和位置[x,xd]=judge(x,pop_size);%调用judge函数，初始化第一次值fornum=2:最大迭代次数wk=wmax-num*(wmax-wmin)/max_gen;%计算惯性权重r1=;r2=%随机产生加速权重PSO算法迭代求vk,xk；While判断vk是否满足条件再次重新生成加速权重系数r1;r2PSO算法再次迭代求vk;xk数值end调用[x,xd]=judge(x,pop_size);重新计算出目标函数值判断并重新生成pj数值；判断并重新生成pjd数值；if迭代前数值>迭代后的数值累加迭代次数值end输出随机数种子、进度、最优迭代次数、每个函数的数值和目标函数的数值用ASCII保存粒子位移的数值用ASCII保存粒子速度的数值end4.3粒子群算法的关键4.3.1粒子状态向量形式的确定类似于遗传算法中染色体串的形式，粒状态向量的构造形式也属于一种编码，但不同的是，由于PSO算法中粒子状态的更新方式的简捷，因此其编码形式相比遗传算法更简单，向量维数更小。可以根据优化系统的规模与控制变量的性质和特点来确定粒子状态的维数n和编码的排列顺序以及不同维的含义。对于同一问题，即使采用同一种优化算法，也可以有不同的编码方式。4.3.2适应度函数的建立适应度函数用于评价各粒子的性能优劣，根据适应值的大小来寻找粒子的状态极值，从而更新群中其它粒子的状态。粒子的适应度函数值越大，表示该个体粒子的适应度越高，也即该粒子个体的质量越好，更适应目标函数所定义的生存环境。全局极值就是粒子群中适应值最高的粒子状态，个体极值也是如此。适应度函数为群体极值的选择和更新提供了依据。对于一般函数优化问题可以直接将函数本身作为适应度函数，但是对于复杂的多目标函数适应度函数一般不那么直观，往往需要研究者自己根据具体情况和预定的优化效果来自行构造。特别地，对于多变量、多约束的复杂系统，变量的不等式约束通常采用罚函数形式来处理，通过这个广义目标函数，使得算法在惩罚项的作用下找到原问题的最优解。4.3.3粒子多样性的保证在基本PSO算法搜索后期，粒子群容易向局部极小或全局极小收敛，此时群中粒子也在急剧地聚集，粒子状态的更新速度越来越慢，群体粒子出现趋同性，粒子的多样性越来越差，甚至陷入局部最优值。如何采取一定的措施增加粒子的多样性，以避免陷入局部最优也是基本PSO算法的一个关键问题。4.3.4粒子群算法的参数设置PSO算法一个最大的优点是不需要调节太多的参数，但是算法中少数几个参数却直接影响着算法的性能以及收敛性。目前，PSO算法的理论研究尚处于初始阶段，所以算法的参数设置在很大程度上还依赖于经验。PSO参数包括：群体规模m，微粒子长度l，微粒范围SKIPIF1<0，微粒最大速度SKIPIF1<0，惯性权重SKIPIF1<0，加速常数SKIPIF1<0。下面是这些参数的作用及其设置经验。群体规模m：即微粒数目，一般取20～40。试验表明，对于大多数问题来说，30个微粒就可以取得很好的结果，不过对于比较难的问题或者特殊类别的问题，微粒数目可以取到100或200。微粒数目越多，算法搜索的空间范围就越大，也就更容易发现全局最优解。当然，算法运行的时间也越长。微粒长度l：即每个微粒的维数，由具体优化问题而定。微粒范围SKIPIF1<0：微粒范围由具体优化问题决定，通常将问题的参数取值范围设置为微粒的范围。同时，微粒每一维也可以设置不同的范围。微粒最大速度SKIPIF1<0：微粒最大速度决定了微粒在一次飞行中可以移动的最大距离。如果SKIPIF1<0太大，微粒可能会飞过好解；如果SKIPIF1<0太小，微粒不能在局部好区间之外进行足够的搜索，导致陷入局部最优值。通常设定SKIPIF1<0，SKIPIF1<0，每一维都采用相同的设置方法。惯性权重fw：fw使微粒保持运动惯性，使其有扩展搜索空间的趋势，有能力探索新的区域。取值范围通常为SKIPIF1<0。早期的实验将fw固定为1.0发现，动态惯性权重因子能够获得比固定值更为优越的寻优结果，使算法在全局搜索前期有较高的探索能力以得到合适的种子。动态惯性权重因子可以在PSO搜索过程中线性变化，亦可根据PSO性能的某个测度函数而动态改变，比如模糊规则系统。目前采用较多的动态惯性权重因子是Shi建议的线性递减权值策略，如式(4.3)。它能使fw由0.8随迭代次数递减到0.2。SKIPIF1<0(4.3)式中，max_d为最大进化代数，fmax为初始惯性值，fmin为迭代至最大代数时的惯性权值。经典取值fmax=0.8，fmin=0.2。加速常数SKIPIF1<0和SKIPIF1<0：SKIPIF1<0和SKIPIF1<0代表将每个微粒推向pBest和gBest位置的统计加速项的权重。低的值允许微粒在被拉回之前可以在目标区域外徘徊，而高的值则导致微粒突然的冲向或越过目标区域。SKIPIF1<0和SKIPIF1<0是固定常数，早期实验中一般取2。有些文献也采取了其它取值，但一般都限定SKIPIF1<0和SKIPIF1<0相等并且取值范围为SKIPIF1<0。5基于粒子群算法求解非线性规划问题的设计作为运筹学的一个重要的分支，非线性规划问题求解方法一直式人们研究的重点。随着优化对象复杂性的增加，优化问题的规模也越来越大，传统的优化方法难以适应，因此人们在寻求严格最优化理论化方法和智能优化方法如遗传算法，蚁群算法等，但各种方法都有其相应的适用范围和局限性。粒子群优化算法是由Kennedy和Eberhart开发的一种演化计算技术。由于PSO概念简单、容易实现并且没有许多参数需要调整，同时又有深刻的智能背景，即适合科学计算，又特别适合工程应用。因此，将粒子群算法应用于非线性规划，是改善求解非线性规划的效果，提高非线性规划质量的有效途径。本章就是介绍粒子群算法在非线性规划中的具体应用，设计并实现基于粒子群算法的非线性规划问题的求解。5.1实用粒子群算法设计5.1.1编码方法设计在MATLAB中编写非线性规划问题的粒子群算法编码的过程中，首先在函数中把非线性规划函数转化为一种MATLAB可以阅读的矩阵型的函数值，在其中添加约束条件，并作超出约束的变换的方法。在运行函数中设置各种参数数值，编写粒子群方法的实现方法，并迭代求解各个过程中目标函数的数值解，输出结果值。在所有局部解中搜索最优解，作为最终的目标函数数值。计算结束。5.1.2适应度函数设计适应度表示个体x对环境的适应程度。分为两类，一类为针对被优化的目标函数的优化型适应度，另一类为针对约束函数的约束性适应度。其中优化型适应度和约束型适应度分别表示为SKIPIF1<0（5-1）SKIPIF1<0（