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

1、西安科技大学毕业设计（论文）分类号 密级学校代码 学号 0608060124西安科技大学学 士 学 位 论 文 题目：非线性规划问题的粒子群算法作者：指导教师： 专业技术职称：学科专业： 申请学位日期：摘 要优化技术是一种以数学为基础，用于求解各种组合优化问题的应用技术。最优化问题是人们在工程技术、科学研究、和经济管理等诸多领域中经常碰到的问题，它是指在满足一定的约束条件下，寻找一组参数值，使目标函数达到最大或最小。最优化问题根据其目标函数、约束条件的性质以及优化变量的取值范围可以分为许多类型，例如：根据目标函数和约束条件是否均为线性表达式，把最优化问题划分为线性规划问题和非线性规划问题。针对

2、不同的最优化问题，提出了许多不同的优化方法，如牛顿法、共轭梯度法、polar-ribiere 法、拉格朗日乘子法等。这些优化算法能很好地找到问题的局部最优点，是成熟的局部优化算法。但是随着人类生存空间的扩大以及认识与改造世界范围的拓展，人们发现由于问题的复杂性、约束性、非线性、建模困难等特点，解析性优化算法已不能满足人们的要求，需要寻找一种适合于大规模并行且具有智能特征的优化算法。现代进化类方法如人工神经网络、遗传算法、禁忌搜索法、模拟退火法和蚁群算法等在解决大规模的问题时体现出强大的潜力，它们可以在合理的时间限制内逼近优化问题的较好可行解。其中，遗传算法和蚁群算法被称为智能优化算法，其基本思

3、想是通过模拟自然界生物的行为来构造随机优化算法。 近年来，另一种智能优化算法粒子群算法（particle swarm optimization，简称pso）越来越受到学者的关注。粒子群算法是美国社会心理学家jameskennedy 和电气工程师russell eberhart 在1995 年共同提出的，它是受到鸟群社会行为的启发并利用了生物学家frank heppner 的生物群体模型而提出的。它用无质量无体积的粒子作为个体，并为每个粒子规定简单的社会行为规则，通过种群间个体协作来实现对问题最优解的搜索。由于算法收敛速度快，设置参数少，容易实现，能有效地解决复杂优化问题，在函数优化、神经网络训

4、练、图解处理、模式识别以及一些工程领域都得到了广泛的应用。关键字：非线性规划；粒子群算法；智能算法abstractoptimization 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 e

5、conomic 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

6、. 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 newtons method, conjuga

7、te gradient method, polar-ribieres 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

8、, binding, nonlinear, modeling difficulties characteristic, it is not easy to find a satisfying analytic solutions. its necessary to find a optimization algorithm suiting for large-scale parallel operation with smart features. modern evolution methods such as artificial neural networks, genetic algo

9、rithms, 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 algorit

10、hm 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) increasi

11、ngly 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 particle

12、s 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 effecti

13、vely 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.key words:nonlinear programming; pso(particle swarm optimization);intelligent algorithm 目 录1概论11.1 背景介绍11.1.

14、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 基本

15、粒子群算法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 非

16、线性规划的粒子群算法程序设计215.2.1 算法过程描述215.2.2 粒子群算法程序流程图216 基于粒子群算法的非线性规划求解的性能分析306.1 概述306.2 粒子群算法参数设置效果比较306.3 时间复杂度336.3.1 理论时间复杂度336.3.2 样本数对算法运行时间的影响336.4 算法的发展与展望367 总结37致谢38参考文献39331概 论1.1 背景介绍1.1.1 非线性规划简介具有非线性约束条件或目标函数的数学规划，是运筹学的一个重要的分支，非线性规划研究一个n元实函数在一组等式或不等式的约束条件下的机制问题且目标函数和约束条件至少有一个是未知量的非线性函数，目标函数

17、和约束条件都是线性函数的情形则属于线性规划。非线性规划是20世纪50年代才开始形成的一门新兴学科。1951年h.w库恩和a.w塔克发表的关于最优性条件的论文是非线性规划正式诞生的一个重要标志。在50年代可得出了可分离规划和二次规划的n种解法，它们大都是以g.b.丹齐克提出的解线性规划的单纯形法为基础的。50年代末到60年代末出现了许多解非线性规划问题的有效的算法，70年代又得到进一步的发展。非线性规划在工程、管理、经济、科研、军事等方面都有广泛的应用，为最优设计提供了有力的工具。非线性规划问题广发存在于科学与工程领域，是一类比较难以解决的优化问题，没有普遍使用的解法。传统的求解该问题的方法（如

18、罚函数，可行方向法，以及变尺度法等）是基于梯度的方法所以目标函数与约束式必须是可微的，并且这些方法只能保证求的局部最优解。1.1.2 粒子群算法简介粒子群算法（particle swarm optimization，pso）的基本概念源于对于鸟群捕食行为的简化社会模型的模拟，1995年由kenndy和eberhart等人提出，它同遗传算法类似，通过个体间的协作和竞争实现全局搜索系统初始化为一组随机解，称之为粒子。通过粒子在搜索空间的飞行完成寻优，在数学公式中即为迭代，它没有遗传算法的交叉及变异算子，而是粒子在解空间追随最优的粒子进行搜索。pso算法的改进主要在参数选择、拓扑结构以及与其他优化算

19、法相融合方面。据此当前典型的改进算法有：自适应pso算法、模糊pso算法、杂交pso算法、混合粒子算法（hpso）和离散pso算法等等。其中自适应和模糊pso算法是eberhartshi研究了惯性因子对优化性能的影响，发现较大的值有利于跳出局部极小点，较小的值有利于算法的收敛。自适应pso算法通过线性地减少值动态的调整参数，而模糊pso算法则在此基础上利用模糊规则动态调整参数的值，即构造一个2输入、1输出的模糊推理机来动态地修改惯性因子。杂交和混合粒子群算法（hpso）是受遗传算法、自然选择机制的启示，将遗传算子与基本pso相结合而得。杂交pso在基本pso中引入了杂交算子，两者均取得了满意的

20、结果，改善了算法的性能。基本pso算法是求解连续函数优化的有力工具，但对离散问题却无能为力。因此kenndy和eberhart发展了离散pso算法，用于解决组合优化问题等。在一定程度上完善发展了基本pso算法，并将其应用于旅行商问题（tsp）的求解，取得了较好的结果。目前pso已经广泛应用于函数优化、神经网络训练、模糊系统控制以及其它遗传算法的应用领域。最初应用到神经网络训练上，在随后的应用中pso又可以用来确定神经网络的结构。一般说来，pso比较有潜在的应用包括系统设计、多目标优化、分类、模式识别、调度、信号处理、决策、机器人应用等。其中具体应用实例是非线性规划的粒子群算法。总之，pso算法

21、的应用十分广泛，它有着比较好的发展前景，值得做进一步的研究。1.2 研究内容本课题主要研究非线性规划的粒子群算法分析与实现。将非线性规划的问题使用粒子群最优算法求解其最优解，在一般求解非线性规划的问题时都与选择的算法有很大的关系，在选择变尺度法和梯度法时都必须考虑非线性规划函数的可微性，在初始值选择上也给函数的局部收敛带来局部的最优，不能达到全局最优解，这样就给一些其它非线性规划问题带来很大的困难。粒子群算法（pso）是一种新兴的优化技术，通过粒子追随自己找到最好解和整个群的最优解来完成优化。该算法简单易实现，可调参数少是解决非线性规划问题的比较理想的算法。题目以粒子群算法为工具，设计基于非线

22、性规划问题的应用，并对求解过程总结，比较其它算法的优越性和其存在的问题。2 非线性规划分析2.1 非线性规划的概念如果目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做非线性规划问题。其可分为两大类问题有约束问题与无约束问题，它们在处理方法上有明显的不同。实际问题中大多数都是有约束条件的问题。球接待有约束条件的问题比起无约束问题要困难得多，也复杂得多。在每次迭代时，不仅要使目标函数值有所下降，而且要使迭代点都落在可行域内。与线性规划一样，非线性规划也是运筹学的一个重要的分支，于20世纪50年代开始逐步形成，到20世纪70年代开始处于兴旺发展时期。随着计算机技术的日益发展，很多领域越

23、来越重视这门学科，应用非线性规划方法进行设计、管理等，非线性规划理论自身也得到了进一步的发展。关于求解非线性规划的迭代方法有二分法、简单迭代法、牛顿迭代法与拟牛顿迭代法、同论延拓法、单纯形法等。以上方法都有一定的局限性。2.2 非线性规划的应用非线性规划在军事、经济、管理、生产过程自动化、工程设计和产品优化设计等方面都有着重要的应用。但非线性规划的研究目前还不成熟，有许多问题需要进一步完善。非线性规划不像线性规划有统一的算法，对于不同的问题需要用不同的算法处理，现阶段各种算法都有一定的局限性，只有对各种算法加以改正，才能有效地解决人们在日常的生产、生活中遇到的优化问题，做出最优的决策。一般来说

24、，解非线性规划问题要比求解线性规划的问题困难得多，而且也不想线性规划那样有统一的数学模型及如单纯形法这一通用的解法，非线性规划的各种算法大都有自己特定的适应范围。都有一定的局限性，到目前为止还没有适合于各种非线性规划问题的一般算法。这正是需要人么进一步研究的课题。非线性规划在工程、管理、经济、科研、军事等方面都有广泛的应用，为最优设计提供了有力的工具。例如：如何在有人力、物力、财力要求的前提下合理安排产品生产，以取得最高的利润；如何设计某种产品，在满足规格、性能要求的前提下，达到最低的成本；如何确定一个自动控制系统的某些参数，使系统的工作状态最佳；如何安排库存储量，既能保证供应，又使储存费用最

25、低；如何分配一个动力系统中各电站的负荷，在保证一定指标要求的前提下，使总耗费量最小；如何组织货源，既能满足顾客需要，又使资金周转最快等对于静态的最优化问题，当目标函数或约束条件出现未知量的非线性函数，且不便于线性化，或勉强线性化后会招致较大误差时，就可以应用非线性规划的方法去处理。2.3 非线性规划相关的概念定义：如果目标函数或约束条件中至少有一个是非线性规划函数时的最优化问题就叫做非线性规划问题。一般形式：min （2-1）其中是定义在上的实值函数，简记：其它情况：求目标函数的最大值或约束条件为小于等于零的情况，都可通过取其相反数化为上述一般形式。 定义1 把满足问题(2-1)中条件的解称为

26、可行解（或可行点），所有可行点的集合称为可行集（或可行域）记为d即问题(2-1)可简记为定义2 对于问题(2-1)，设，若存在，使得对于一切且0，要受惩罚。sumt外点法（罚函数法）的迭代步骤：1、任意给定初始点，取，给定允许误差，令k=1；2、求无约束极值问题的最优解，设为，即；3、若存在，使，则取令k=k+1返回(3.2)，否则，停止迭代。取得最优解。计算时也可将收敛性判别准则改为。罚函数法的缺点是：每个近似最优解往往不是容许解，而只能近似满足约束，在实际问题中这种结果可能不能使用；在解一系列无约束问题中，计算量太大，特别是随着的增大，可能导致错误。sumt内点法（障碍函数法）其基本思想是

27、：迭代过程中总是从可行域内的 出发，并保持在可行域内进行搜索。该方法适用于只有不等式约束的问题。考虑问题： (3.4)设集合，是可行域中所有严格内点的集合。构造障碍函数或其中称或为障碍项，r为障碍因子。这样问题(3.4)就转化为求一系列极值问题：得。内点法的迭代步骤：1、给定允许误差，取；2、求出约束集合d的一个内点，令k=1；3、以为初始点，求解，其中的最优解，设为；4、检验是否满足或，满足，停止迭代，；否则取，令k=k+1，返回3。3.2 无约束非线性规划求解方法无约束非线性规划问题的求解方法分为解析法和直接法两类。解析法需要计算函数的梯度，直接法仅通过比较目标函数值的大小来移动迭代点。其

28、中最速下降法、共轭梯度法、牛顿法、变尺度法等解析方法和步长加速法、旋转方法、方向加速法等直接方法。一般来说，无约束非线性规划问题的求解是通过一系列一维搜索来实现。因此，如何选择搜索方向是求解无约束非线性规划问题的核心问题，搜索方向的不同选择，形成不同的求解方法。3.2.1最优速下降法最速下降法是由法国著名数学家cauchy于1847年首次提出。该方法将目标函数在的负梯度方向作为下降迭代法的迭代公式中的，并通过求解，确定最佳步长。若具有二阶连续偏导，在处作的二阶泰勒展开式对求导令其等于零，得最佳步长。最速下降法的计算步骤如下：（1）给定初始点，允许误差，置k=0（2）计算搜索方向。（3）若，则停

29、止计算，得近似极小点；否则，确定最佳步长，转第（4）步（4）令，置k=k+1，转第（2）步。3.2.2 共轭梯度法共轭梯度法最初由hesteness和stiefel于1952年为求解非线性方程组而提出，后来成为求解无约束非线性规划问题的一种重要的方法。其基本思想是：把共轭性与最速下降方法相结合，利用已知点处的梯度构造一组共轭方向，并沿这组方向进行搜索，求出目标函数的极小点。该方法对于正定二次函数能在有限步内达到极小点，即该算法具有二次终结性。对于问题，由于，可推出其唯一极小点。如果已知某共轭向量组， 由 （3.1） 可知，问题的极小点可通过下列算法得到 （3.2）该算法称为共轭方向法。它要求搜

30、索方向必须共轭，确定各近似极小点时必须按最佳一维搜索进行。共轭梯度法是共轭方向的一种，它的 方向是利用一维搜索所得极小点处的梯度生成的。由于，故，又因为故。任取初始近似点，并取初始搜索方向的负梯度方向，即，沿射线进行一维搜索，得到，其中满足，计算，由，从而和正交，构成正交系，在由它构成的子空间中搜寻，令，为待定系数，欲使和为a共轭，从而可求的。令由此可得。综合以上步骤可以得到共轭梯度法德一般计算公式如下： (3.3)其中为初始近似，。对于正定二次函数，从理论上说，进行n次迭代即可达到极小点。但是，在实际计算中，由于数据的输入以及计算误差的积累，往往做不到这一点。此外，由于n维问题的共轭方向最多

31、只有n个，在n步以后继续加上进行是没有意义的。因此，在实际应用时，如迭代到n步还不收敛，就将作为新的初始近似，重新开始迭代。共轭梯度法的计算步骤如下：（1）选择初始近似，给出允许误差。（2）计算，置k=0。（3）用式(3.3)计算。（4）若k迭代后的数值 累加迭代次数值 end 输出随机数种子、进度、最优迭代次数、每个函数的数值和目标函数的数值 用ascii保存粒子位移的数值 用ascii保存粒子速度的数值 end4.3 粒子群算法的关键4.3.1 粒子状态向量形式的确定类似于遗传算法中染色体串的形式，粒状态向量的构造形式也属于一种编码，但不同的是，由于pso算法中粒子状态的更新方式的简捷，因

32、此其编码形式相比遗传算法更简单，向量维数更小。可以根据优化系统的规模与控制变量的性质和特点来确定粒子状态的维数n和编码的排列顺序以及不同维的含义。对于同一问题，即使采用同一种优化算法，也可以有不同的编码方式。4.3.2 适应度函数的建立适应度函数用于评价各粒子的性能优劣，根据适应值的大小来寻找粒子的状态极值，从而更新群中其它粒子的状态。粒子的适应度函数值越大，表示该个体粒子的适应度越高，也即该粒子个体的质量越好，更适应目标函数所定义的生存环境。全局极值就是粒子群中适应值最高的粒子状态，个体极值也是如此。适应度函数为群体极值的选择和更新提供了依据。对于一般函数优化问题可以直接将函数本身作为适应度

33、函数，但是对于复杂的多目标函数适应度函数一般不那么直观，往往需要研究者自己根据具体情况和预定的优化效果来自行构造。特别地，对于多变量、多约束的复杂系统，变量的不等式约束通常采用罚函数形式来处理，通过这个广义目标函数，使得算法在惩罚项的作用下找到原问题的最优解。4.3.3 粒子多样性的保证在基本pso算法搜索后期，粒子群容易向局部极小或全局极小收敛，此时群中粒子也在急剧地聚集，粒子状态的更新速度越来越慢，群体粒子出现趋同性，粒子的多样性越来越差，甚至陷入局部最优值。如何采取一定的措施增加粒子的多样性，以避免陷入局部最优也是基本pso算法的一个关键问题。4.3.4 粒子群算法的参数设置pso算法一

34、个最大的优点是不需要调节太多的参数，但是算法中少数几个参数却直接影响着算法的性能以及收敛性。目前，pso算法的理论研究尚处于初始阶段，所以算法的参数设置在很大程度上还依赖于经验。pso参数包括：群体规模m，微粒子长度l，微粒范围，微粒最大速度，惯性权重，加速常数。下面是这些参数的作用及其设置经验。群体规模m：即微粒数目，一般取2040。试验表明，对于大多数问题来说，30个微粒就可以取得很好的结果，不过对于比较难的问题或者特殊类别的问题，微粒数目可以取到100或200。微粒数目越多，算法搜索的空间范围就越大，也就更容易发现全局最优解。当然，算法运行的时间也越长。微粒长度l：即每个微粒的维数，由具体优化问题而定。微粒范围：微粒范围由具体优化问题决定，通常将问题的参数取值范围设置为微粒的范围。同时，微粒每一维也可以设置不同的范围。微粒最大速度：微粒最大速度决定了微粒在一次飞行中可以移动的最大距离。如果太大，微粒可能会飞过好解；如果太小，微粒不能在局部好区间之外进行足够的搜索，导致陷入局部最优值。通常设定，每一维都采用相同的设置方法。惯性权重fw：fw使微粒保持运动惯性，使其有扩展搜索空间的趋势，有能力探索新的区域。取值范围通常为。早期的实验将fw固定为1.0发现，动态惯性权重因子能够获得比固定值更为优越的寻优结果，使算法在全局搜索前期有较高的探索能力以得到