分类号密级
学校代码学号 0608060124
西安科技大学
学士学位论文
题目：非线性规划问题的粒子群算法
作者：
指导教师：专业技术职称：
学科专业：申请学位日期：
摘要
优化技术是一种以数学为基础，用于求解各种组合优化问题的应用技术。最优化问题是人们在工程技术、科学研究、和经济管理等诸多领域中经常碰到的问题，它是指在满足一定的约束条件下，寻找一组参数值，使目标函数达到最大或最小。最优化问题根据其目标函数、约束条件的性质以及优化变量的取值范围可以分为许多类型，例如：根据目标函数和约束条件是否均为线性表达式，把最优化问题划分为线性规划问题和非线性规划问题。针对不同的最优化问题，提出了许多不同的优化方法，如牛顿法、共轭梯度法、Polar-Ribiere 法、拉格朗日乘子法等。这些优化算法能很好地找到问题的局部最优点，是成熟的局部优化算法。
但是随着人类生存空间的扩大以及认识与改造世界范围的拓展，人们发现由于问题的复杂性、约束性、非线性、建模困难等特点，解析性优化算法已不能满足人们的要求，需要寻找一种适合于大规模并行且具有智能特征的优化算法。现代进化类方法如人工神经网络、遗传算法、禁忌搜索法、模拟退火法和蚁群算法等在解决大规模的问题时体现出强大的潜力，它们可以在合理的时间限制内逼近优化问题的较好可行解。其中，遗传算法和蚁群算法被称为智能优化算法，其基本思想是通过模拟自然界生物的行为来构造随机优化算法。
近年来，另一种智能优化算法—粒子群算法（particle swarm optimization，简称PSO）越来越受到学者的关注。粒子群算法是美国社会心理学家JamesKennedy 和电气工程师Russell Eberhart 在1995 年共同提出的，它是受到鸟群社会行为的启发并利用了生物学家Frank Heppner 的生物群体模型而提出的。它用无质量无体积的粒子作为个体，并为每个粒子规定简单的社会行为规则，通过种群间个体协作来实现对问题最优解的搜索。由于算法收敛速度快，设置参数少，容易实现，能有效地解决复杂优化问题，在函数优化、神经网络训练、图解处理、模式识别以及一些工程领域都得到了广泛的应用。
关键字：非线性规划；粒子群算法；智能算法
ABSTRACT
Optimization 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 economic 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. 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 Newton's method, conjugate gradient method, Polar-Ribiere's 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, binding, nonlinear, modeling difficulties characteristic, it is not easy to find a satisfying analytic solutions. It’s necessary to find a optimization algorithm suiting for large-scale parallel Operation with smart features. Modern evolution methods such as artificial neural networks, genetic algorithms, 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 algorithm 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) increasingly 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 particles 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 effectively 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概论 (2)
1.1 背景介绍 (2)
1.1.1 非线性规划简介 (2)
1.1.2 粒子群算法简介 (2)
1.2 研究内容 (3)
2 非线性规划的分析 (3)
2.1 非线性规划的概念 (3)
2.2 非线性规划的应用 (4)
2.3 非线性规划相关的概念 (4)
2.4 凸函数与凸规划 (5)
2.4.1 凸函数定义 (5)
2.4.2 凸规划 (6)
3 基本的非线性规划算法 (5)
3.1罚函数概述 (5)
3.2无约束非线性规划求解算法描述 (7)
3.2.1 最优速下降法 (7)
3.2.2 共轭梯度法 (8)
3.2.3 牛顿法 (9)
3.3算法优缺点性能分析 (10)
4 基本粒子群算法 (12)
4.1 粒子群算法概述 (11)
4.1.1 粒子群算法发展 (11)
4.1.2 粒子群算法简介 (12)
4.1.3 粒子群算法的特点 (12)
4.1.4 粒子群算法的应用 (13)
4.2 基本粒子群算法 (14)
4.2.1 基本遗传算法的构成要素 (14)
4.2.2 基本遗传算法的形式化定义 (15)
4.2.3 基本遗传算法描述 (15)
4.3 粒子群算法的关键 (17)
4.3.1 粒子状态向量形式的确定 (17)
4.3.2 适应度函数的建立 (17)
4.3.3 粒子多样性的保证 (17)
4.3.4 粒子群算法的运行参数设置 (17)
5 基于粒子群算法的非线性规划问题的求解设计 (18)
5.1 实用粒子群算法设计 (18)
5.1.1 编码方法设计 (18)
5.1.2 适应度函数设计 (18)
5.1.3 基于约束适应度优先排序的约束条件处理方法 (19)
5.1.4 动态邻域算子 (19)
5.1.5 可变惯性权重和最大速度 (20)
5.1.6 粒子群算法运行参数设计 (21)
5.2 非线性规划的粒子群算法程序设计 (22)
5.2.1 算法过程描述 (22)
5.2.2 粒子群算法程序流程图 (22)
6 基于粒子群算法的非线性规划求解的性能分析 (24)
6.1 概述 (24)
6.2 粒子群算法参数设置效果比较 (24)
6.3 时间复杂度 (26)
6.3.1 理论时间复杂度 (26)
6.3.2 样本数对算法运行时间的影响 (27)
6.4 算法的发展与展望 (27)
7 总结 (29)
致谢 (30)
参考文献 (31)
1概论
1.1背景介绍
1.1.1 非线性规划简介
具有非线性约束条件或目标函数的数学规划，是运筹学的一个重要的分支，非线性规划研究一个n元实函数在一组等式或不等式的约束条件下的机制问题且目标函数和约束条件至少有一个是未知量的非线性函数，目标函数和约束条件都是线性函数的情形则属于线性规划。
非线性规划是20世纪50年代才开始形成的一门新兴学科。1951年H.W库恩和A.W塔克发表的关于最优性条件的论文是非线性规划正式诞生的一个重要标志。在50年代可得出了可分离规划和二次规划的n种解法，它们大都是以G.B.丹齐克提出的解线性规划的单纯形法为基础的。50年代末到60年代末出现了许多解非线性规划问题的有效的算法，70年代又得到进一步的发展。非线性规划在工程、管理、经济、科研、军事等方面都有广泛的应用，为最优设计提供了有力的工具。
非线性规划问题广发存在于科学与工程领域，是一类比较难以解决的优化问题，没有普遍使用的解法。传统的求解该问题的方法（如罚函数，可行方向法，以及变尺度法等）是基于梯度的方法所以目标函数与约束式必须是可微的，并且这些方法只能保证求的局部最优解。
1.1.2 粒子群算法简介
粒子群算法（Particle Swarm optimization，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 非线性规划相关的概念
定义：如果目标函数或约束条件中至少有一个是非线性规划函数时的最优化问题就叫做非线性规划问题。
一般形式：min ()X f
()()???===≥.,...,2,1 0 m;1,2,..., 0.. l j X h i X g t s j i （2-1）
其中j i n T n h g f E x x x ,,,),,,(X 21∈∧=是定义在n E 上的实值函数，简记：
111:,:,:E E h E E g E E f n j n i n →→→
其它情况：求目标函数的最大值或约束条件为小于等于零的情况，都可通过取其相反数化为上述一般形式。
定义1 把满足问题(2-1)中条件的解)(X n E ∈称为可行解（或可行点），所有可行点的集合称为可行集（或可行域）．记为D ．即
},0)(,0)(/{n j i E X X h X g X D ∈=≥= 问题(2-1)可简记为)(min X f D
X ∈ 定义2 对于问题(2-1)，设D X ∈*，若存在0>δ，使得对于一切D X ∈且‖*X X -‖<δ，都有)()(*X f X f ≤则称*X 是)(X f 在D 上的局部极小值点（局部最优解）。特别地当*X X ≠时，若)()(*X f X f <，则称*X 在D 上的严格局部极小值点（严格局部最优解）。
定义3 对于问题(2-1),设D X ∈*，对于任意的D X ∈，都有)()(*X f X f ≤则称*X 是)(X f 在D 上的全局极小值点（全局最优解）。特别地当*X X ≠时，若
)()(*X f X f <，则称*X 是)(X f 上的严格全局极小值点（严格全局最优解）
。 2.4 凸函数与凸规划
在最优化理论中，凸集与凸函数占有非常重要的地位。通过对凸函数的学习了解求解非线性规划的基础知识。
2.4.1 凸函数定义
设n S E ?为凸集，()f X 是定义在凸集S 上的函数，如果12,X X S ?∈恒有1212((1))()(1)(),(0,1)f X X f X f X λλλλλ+-≤+-∈，则称()f X 是凸集S 上的凸函数，如果上式取严格不等式，则称()f X 是凸集S 上的严格凸函数，将上式的不等号反向，即可得到凹函数和严格凹函数的定义。
凸函数的性质如下：
（1） 设()f X 是定义在凸集S 上的凸函数，则(1,...,)i X S i k ?∈=，以及
10,1k i i i λλ=≥=∑，恒有11()()k k
i i i i i i f X f X λλ==≤∑∑。
（2） 设()(1,...,)i f X i k =是定义在凸集S 上的凸函数，如果0i α≥，那么
1()()k
i i i f X f X α==∑仍是凸集S 上的凸函数。 （3） 设()f X 是定义在凸集S 上的凸函数，那么对任意实数α，集合
{|,()}
S X X S f X αα=∈≤是S 的凸子集，称为水平集。 凸函数的判定：设n 元函数12()(,,...,)n f X f x x x =可微，称列向量
12[,,...,]T n
f f f x x x ??????为 f 在X 处的梯度，记作()f X ?。若()f X 二阶连续可微，则称f 的所有二阶偏导数构成的n 阶方阵22221
1212222212222221
2.....................n n n n n f f f x x x x x f f f x x x x x f f f x x x x x ?????????????????????????????????????????????
为f 在X 处的二阶导数矩阵或称海赛（Hessian ）矩 阵，记作2()f X ?或()H X 。f 在X 处沿梯度方向有最快的上升趋势。一阶可微的函数()f X 是凸集S 上的凸函数的充分必要条件是：12,X X S ?∈，恒有
21121()()()()T f X f X f X X X ≥+?-类似地，
()f X 是在凸集S 上的严格凸函数的充分必要条件是上式不等号严格成立。二阶连续可微的函数()f X 是凸集S 上的凸函数的充分必要条件是：2,()X S f X ?∈?为半正定矩阵。类似地，()f X 是凸集S 上的严格凸函数的充分必要条件是2()f X ?为正定矩阵。
2.4.2 凸规划
若()f X 是凸函数，1()(1,...,)g X i m =是凹函数（即所有()i g X -全为凸函数），则称这种规划问题为凸规划。显然，线性规划是一种凸规划，其性质有如以下：
（1）可行解集为凸集。
（2）最优解集为凸集（假定最优解存在）。
（3）中心任何局部最优解也是其全局最优解。
（4）若目标函数为严格凸函数，且最优解存在，则其最优解必唯一。
3 基本非线性规划算法
3.1 罚函数法概述
罚函数法基本思想是通过构造罚函数把约束问题转化为一系列无约束最优化问题，进而用无约束最优化方法去求解。这类方法称为序列无约束最小化方法，简称为SUMT 法。
其一为SUMT 外点法，其二为SUMT 内点法。
SUMT 外点法其基本思想是：利用目标函数和约束条件组成辅助函数
对一般的非线性规划：min )(X f
()()???===≥.
,...,2,1 0 m;1,2,..., 0.. l j X h i X g t s j i
(3.1)
可设： ()()()()()22
11,min 0, m l i j i j T X M f X M g X M h X ==???
?=++????∑∑ (3.2)将问题(3.1)转化为无约束问题：() ,min M X T n E
X ∈ (3.3)
其中T(X,M)称为罚函数，M 称为罚因子，带M 的项称为罚项，这里的罚函数只对不满足约束条件的点实行惩罚：当X D ∈时，满足各()0,()0i i g X h X ≥=故罚项=0，不受惩罚，当X D ?时，必()0i g X <或()0i h X ≠约束条件，故罚项>0，要受惩罚。
SUMT 外点法（罚函数法）的迭代步骤：
1、任意给定初始点0X ，取11M >，给定允许误差0ε>，令k=1；
2、求无约束极值问题min (,)n X E
T X M ∈的最优解，设为()k k X X M =，即min (,)(,)n k k X E
T X M T X M ∈=； 3、若存在(1)i i m ≤≤，使()k i g X ε->，则取1(,10)k k M M M M αα+>==令k=k+1返回(3.2)，否则，停止迭代。取得最优解*k X X ≈。计算时也可将收敛性判别准则()k
i g X ε->改为21[min(0,())]0m
i i M g X =≤∑。 罚函数法的缺点是：每个近似最优解k X 往往不是容许解，而只能近似满足约束，在实际问题中这种结果可能不能使用；在解一系列无约束问题中，计算量太大，特别是随着k M 的增大，可能导致错误。
SUMT 内点法（障碍函数法）其基本思想是：迭代过程中总是从可行域内的 出发，并保持在可行域内进行搜索。该方法适用于只有不等式约束的问题。
考虑问题： m i n ()..()0,1,2,...,i f X s t g X i m ??≥=?
(3.4)
设集合0{|()0,1,2,,}i D X g X i m =>=Λ≠?，
0D 是可行域中所有严格内点的集合。
构造障碍函数
1(,):(,)()ln ()m i i I X r I X r f X r g X ==+∑或11(,)()()
m i i I X r f X r g X ==+∑其中称1ln ()m i i r g X =∑或11()
m i i r g X =∑为障碍项，r 为障碍因子。这样问题(3.4)就转化
为求一系列极值问题：0min (,)k X D
I X r ∈得()k k X r 。
内点法的迭代步骤：
1、给定允许误差0ε>，取10,01r β><<；
2、求出约束集合D 的一个内点00X D ∈，令k=1；
3、以10k X D -∈为初始点，求解0min (,)k X D
I X r ∈，其中0X D ∈的最优解，设为0()k k X X r D =∈；
4、检验是否满足1|ln ()|m k
i i r g X ε=-≤∑或11||()
m k i i r g X ε=≤∑，满足，停止迭代，*k X X ≈；否则取1k k r r β+=，令k=k+1，返回3。
3.2 无约束非线性规划求解方法
无约束非线性规划问题的求解方法分为解析法和直接法两类。解析法需要计算函数的梯度，直接法仅通过比较目标函数值的大小来移动迭代点。其中最速下降法、共轭梯度法、牛顿法、变尺度法等解析方法和步长加速法、旋转方法、方向加速法等直接方法。
一般来说，无约束非线性规划问题的求解是通过一系列一维搜索来实现。因此，如何选择搜索方向是求解无约束非线性规划问题的核心问题，搜索方向的不同选择，形成不同的求解方法。
3.2.1最优速下降法
最速下降法是由法国著名数学家Cauchy 于1847年首次提出。该方法将目标函数()f X 在k X 的负梯度方向()k f X -?作为下降迭代法的迭代公式1k k k k X X P λ+=+中的k P ，并通过求解0min ()k k f X P λλ>+，确定最佳步长k λ。 若()f X 具有二阶连续偏导，在k X 处作(())k k f X f X λ+?的二阶泰勒展开式(())()()()1/2()()()T T k k k k k k k k f X f X f X f X f X f X H X f X λλλλ+?≈-??+??对
λ求导令其等于零，得最佳步长()()()()()
T k k k T k k k f X f X f X H X f X λ??=??。 最速下降法的计算步骤如下：
（1）给定初始点0X ，允许误差0ε>，置k=0
（2）计算搜索方向()k k P f X =-?。
（3）若||k P ε<，则停止计算，得近似极小点k X ；否则，确定最佳步长k λ，转第（4）步
（4）令1k k k k X X P λ+=+，置k=k+1，转第（2）步。
3.2.2 共轭梯度法
共轭梯度法最初由Hesteness 和Stiefel 于1952年为求解非线性方程组而提出，后来成为求解无约束非线性规划问题的一种重要的方法。其基本思想是：把共轭性与最速下降方法相结合，利用已知点处的梯度构造一组共轭方向，并沿这组方向进行搜索，求出目标函数的极小点。该方法对于正定二次函数能在有限步内达到极小点，即该算法具有二次终结性。
对于问题1min{}2
T T X AX b X c ++，由于()f X AX b ?=+，可推出其唯一极小点*1X A b -=-。
如果已知某共轭向量组011,,...,n p p p -， 由
**1min ()()(0,1,2,...,1)k k k k k k k k k f X p f X p k n X X p λλλλ+?+=+?=-?=+??
（3.1） 可知，问题1
min{}2T T
X AX b X c ++的极小点*X 可通过下列算法得到 1*,(0,1,2,...,1):min ()k k k k k k k n X X p k n f X p X X λλλλ+?=+=-??+??=??
（3.2）该算法称为共轭方向法。它要求搜索方向011,,...,n p p p -必须共轭，确定各近似极小点时必须按最佳一维搜索进行。
共轭梯度法是共轭方向的一种，它的 方向是利用一维搜索所得极小点处的梯度生成的。由于()f X AX b ?=+，故11()()()k k k k f X f X A X X ++?-?=+，又因为1k k k k X X p λ+=+故1()(),(0,1,2,...,1)k k k k f X f X Ap k n λ+?-?==-。任取初始近似点0X ，并取初始搜索方向的负梯度方向，即00()p f X =-?，沿射线00X X p λ=+进行一维搜索，得到1X ，其中1X 满足
1000000:min ()X X p f X p λ
λλλ=+???+??，计算1()f X ?，由1010()()()0T T f X p f X f X ?=-??=，
从而1()f X ?和0()f X ?正交，构成正交系，在由它构成的子空间中搜寻1p ，令1100()()p f X a f X =-?+?，0a 为待定系数，欲使1p 和0p 为A 共轭，从而可求的
11000()()()()
T T f X f X a f X f X ??-=??。令00a β=-由此可得1100()p f X p β=-?+。综合以上步骤可以得到共轭梯度法德一般计算公式如下：
11111(),(0,1,2,...,1)()()()()()k k k k T k k k T k k k k k T k k k T k k X X p f X p k n p Ap p f X p f X f X f X f X λλββ+++++=+????=-=-???=-?+????=?????
(3.3)其中0X 为初始近似，00()p f X =-?。
对于正定二次函数，从理论上说，进行n 次迭代即可达到极小点。但是，在实际计算中，由于数据的输入以及计算误差的积累，往往做不到这一点。此外，由于n 维问题的共轭方向最多只有n 个，在n 步以后继续加上进行是没有意义的。因此，在实际应用时，如迭代到n 步还不收敛，就将n X 作为新的初始近似，重
新开始迭代。
共轭梯度法的计算步骤如下：
（1）选择初始近似0X ，给出允许误差0ε>。
（2）计算00()p f X =-?，置k=0。
（3）用式(3.3)计算11,,,k k k k X p λβ++。
（4）若k （5）若1()k f X ε+?<，停止计算，1k X +即为近似极小点；否则，令01k X X +=， 并转向第（2）步。 3.2.3 牛顿法 牛顿法在搜索方向上比梯度法有所改进，它不但利用了目标函数的搜索点的梯度，而且还利用了目标函数的二阶偏导数。也就是说，它不但考虑了函数的梯度，还考虑了梯度的变化趋势，所以在更大范围内考虑了函数的性质。 与梯度法一样，牛顿法也有其缺陷。例如对一般多变量非线性函数的极小化问题，它可能收敛不到所寻找的极小值点。因而，有些在实践中被认为非常成功的方法，是由牛顿法经过修改后得到的。 假定()f X 是二阶连续可微函数，在给定点k x 附近取()f X 的二阶泰勒多项式作逼近21()()()()()2k T k T k f X f X f X X X f X ≈+???+??? (3.4) 式中，k X X X ?=-，2()k f X ?为函数在点k X 的n 阶海赛矩阵，设为非奇异阵。 ()f X 的极小点处，必然满足()0f X ?=，将k X X X ?=-代入式(3.4)，然后求一阶微分得： 2()()()()0k k k f X f X f X X X ?=?+??-= (3.5)可解得点 1k k k X X d +=+ (3.6)式中，k d 为函数()f X 在点k X 的搜索方向，称为牛顿方向，即1[()]()k k d H X f X -=-?。 若令()f X 为二次函数，有()1/2T T f X a b X X QX =++（Q 为对称非奇阵）则2()f X Q ?=，即为海赛矩阵，它是一个常数矩阵。用k X X X =+?代入(3.4)右边，可知该式是一个等式而不是近似式。若再设Q 为正定矩阵，则()f X 有一极小值点*X ，并且*()0f X ?=，因此有()k k f X b QX ?=+。令0k b QX +=综合这两个方程得*121()[()]()k k k k k X X Q f X X f X f X --=-?=-??将此式与(3.6)式比较可知，从任意点k X 出发，用牛顿法只要一步就达到一个二次函数的极小值点，如果这个二次函数存在极小值的话。但对一般的非线性函数，一步是达不到()f X 的极小点的。迭代中往往也会有一些问题。例如2()f X ?在k X 点非正定，或者由式(3.6)得到的点1k X +不靠近k X ，以致()f X 在k X 附近的二阶近似在1k X +处无效，还可能出现1()()k k f X f X +>的情况等等。为了补救这些问题，人们往往用 一个限步牛顿公式：121[()]() k k k k k X X f X f X λ+-=-??来代替式(3.6)，其中1k E λ∈的选择有各种方法， 总是使1()()k k f X f X +<。一般也多用使()f X 沿牛顿方向取极小的一维搜索法。 牛顿法迭代步骤如下： （1）取初始点0n X E ∈，允许误差0δ>，令k ：=0。 （2）检验是否满足收敛性判别准则()k f X δ?<，若满足判别准则，迭代 停止，得到*:k X X =。否则进行（3）。 （3）令21[()]()k k k d f X f X -=-??。 （4）求单变量极值问题的最优解1k E λ∈，0 min ()()k k k k k f X d f X d λλλ>+=+。 （5）令1k k k k X X d λ+=+，k ：=k+1。转到（2）。 3.3 算法性能优缺点分析 （1）梯度法优点：计算量少，存储变量较少，初始点要求不高。梯度法缺点：初值依赖，收敛慢，最速下降法适用于寻优过程的前期迭代或作为间插步骤，越接近极值点时，收敛熟读越慢，后期宜选用收敛快的算法。 （2）牛顿迭代法优点：收敛速度很快。牛顿迭代法缺点：当维数较高时，计算[]12)(-?-k X f 的工作量很大，初值依赖，当初值选择不好时，有可能计算出现异常，导致迭代无法进行，该法需要修正。所以此算法在计算复杂，要计算二次偏导数，又要计算逆矩阵。尤其在变量较多时，计算量就更大了。 （3）罚函数法在实际应用中，由于外点法的初始点可任意选择，不必保证在可行域内，迭代过程中也不要求在可行域内，而是逐步向可行域靠近，因此它 比内点法优越。内点法要求初始点在可行域内，在搜索过程中要控制中要控制每次的搜索步长，以保持迭代点的可行性，因此，在实现上要比外点法困难，但它的最终收敛点总在可行域内，即使最后只得到一个粗略的近似最优点，这个点也必是可行的。 4基本粒子群算法 4.1粒子群算法概述 4.1.1粒子群算法发展 1995年美国电气工程师Eberhart和社会心理学家Kenndy基于鸟群觅食行为提出了粒子群优化算法（particle swarm optimization，PSO），简称粒子群算法。由于该算法概念简明、实现方便、收敛速度快、参数设置少，是一种高效的搜索算法。 PSO是模拟鸟群随机搜寻食物的捕食行为。假设在搜索食物区域里只有一块食物，所有的小鸟都不知道食物在什么地方，所以Kenndy等认为鸟之间存在着互相交换信息，通过估计自身的适应度值，它们知道当前的位置离食物还有多远，所以搜索目前离食物最近的鸟的周围区域是找到食物的最简单有效的办法，通过鸟之间的集体协作使群体达到最优。PSO就是从这种模型中得到启示并用于解决优化问题。在PSO中每个优化问题的潜在解都可以想象成搜索空间中的一只鸟，我们称之为“粒子”。粒子主要追随当前的最优粒子在解空间中搜索，PSO初始化为一群随机粒子（随机解），然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个“极值”来更新自己，第一个就是粒子本身所找到的最优解，这个解叫做个体极值pbest，另一个极值是整个种群目前找到的最优解，这个极值是全局极值gbest。这两个最优变量使得鸟在某种程度上朝着这些方向靠近，此外也可以不用整个种群而只用其中一部分作为粒子的邻居，那么所有邻居的极值就是局部极值，粒子始终跟随这两个极值变更自己的位置和速度直到找到最优解。 到目前为止粒子群算法的发展得到越来越多的众多领域学者的关注和研究，称为解决许多问题的热点算法的研究重点。其中对PSO算法的改进也非常多，有增强算法自适应性的改进、增强收敛性的改进、增加多种群多样性的改进、增强局部搜索的改进、与全局优化算法相结合、与确定性的局部优化算法相融合等。以上所述的是对于算法改进的目的的讨论的，实际改进中应用的方法有基于参数的改进，即对PSO算法的迭代公式的形式上做改进；还有从粒子的行为模式进行 改进，即粒子之间的信息交流方式，如拓扑结构的改进、全局模式与局部模式相结合的改进等；还有基于算法融合的粒子群算法的改进，算法融合可以引入其他算法的优点来弥补PSO 算法的缺点，设计出更适合问题求解的优化算法。 4.1.2 粒子群算法简介 粒子群算法是一个非常简单的算法，且能够有效的优化各种函数。从某种程度上说，此算法介于遗传算法和进化规划之间。此算法非常依赖于随机的过程，这也是和进化规划的相识之处，此算法中朝全局最优和局部最优靠近的调整非常的类似于遗传算法中的交叉算子。此算法还是用了适应值的概念，这是所有进化计算方法所共有的特征。 在粒子群算法中，每个个体称为一个“粒子”，其实每个粒子代表着一个潜在的解。例如，在一个D 维的目标搜索空间中，每个粒子看成是空间内的一个点。设群体由m 个粒子构成。m 也被称为群体规模，过大的m 会影响算法的运算速度和收敛性。 PSO 算法通常的数学描述为：设在一个D 维空间中，由m 个粒子组成的种群1(,...,,...,)i D X x x x =，其中第i 个粒子位置为12(,,...,)T i i i iD x x x x =，其速度为12(,,...,,...,)T i i i id iD V v v v v =。它的个体极值为12(,,...,)T i i i iD p p p p =，种群的全局极值为12(,,...,)T g g g gD p p p p =，按照追随当前最优例子的原理，粒子i x 将按(4.1)、(4.2)式改变自己的速度和位置。 ))()()(())()()(()()1(2211t x t p t r c t x t p t r c t v t v ij gj ij ij ij ij -+-+=+ (4.1) )1()()1(++=+t v t x t x ij ij ij (4.2)式中j=1,2,…,D ，i=1,2,…m ，m 为种群规模，t 为当前进化代数，12,r r 为分布于[0,1]之间的随机数；12,c c 为加速常数。从式(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）工程设计问题。工程设计问题在许多情况下所建立起来的数学模型难以精确求解，即使经过一些简化之后可以进行求解，也会因简化得太多而使得求解结果与实际相差甚远。现在粒子群算法已成为解决复杂调度问题的有效工具， 基本粒子群算法的原理和matlab程序 作者——niewei120（nuaa） 一、粒子群算法的基本原理 粒子群优化算法源自对鸟群捕食行为的研究，最初由Kennedy和Eberhart提出，是一种通用的启发式搜索技术。一群鸟在区域中随机搜索食物，所有鸟知道自己当前位置离食物多远，那么搜索的最简单有效的策略就是搜寻目前离食物最近的鸟的周围区域。PSO 算法利用这种模型得到启示并应用于解决优化问题。PSO 算法中，每个优化问题的解都是粒子在搜索 空间中的位置，所有的粒子都有一个被优化的目标函数所决定的适应值，粒子还有一个速度值决定它们飞翔的方向和距离，然后粒子群就追随当前的最优粒子在解空间中搜索。 PSO 算法首先在给定的解空间中随机初始化粒子群，待优化问题的变量数决定了解空间的维数。每个粒子有了初始位置与初始速度。然后通过迭代寻优。在每一次迭代中，每个粒子通过跟踪两个“极值”来更新自己在解空间中的空间位置与飞翔速度。第一个极值就是单个粒子本身在迭代过程中找到的最优解粒子，这个粒子叫做个体极值。另一个极值是种群所有粒子在迭代过程中所找到的最优解粒子，这个粒子是全局极值。上述的方法叫全局粒子群算法。如果不用种群所有粒子而只用其中一部分作为该粒子的邻居粒子，那么在所有邻居粒子中的极值就是局部极值，该方法称为局部PSO 算法。 速度、位置的更新方程表示为： 每个粒子自身搜索到的历史最优值p i ，p i=(p i1,p i2,....,p iQ)，i=1,2,3,....,n。所有粒子搜索到的最优值p g，p g=(p g1,p g2,....,p gQ)，注意这里的p g只有一个。 是保持原来速度的系数，所以叫做惯性权重。 是粒子跟踪自己历史最优值的权重系数，它表示粒子自身的认识，所以叫“认知”。通常设置为2。 是粒子跟踪群体最优值的权重系数，它表示粒子对整个群体知识的认识，所以叫做“社会知识”，经常叫做“社会”。通常设置为2。 是[0,1]区间内均匀分布的随机数。 是对位置更新的时候，在速度前面加的一个系数，这个系数我们叫做约束因子。通常设 置为1 。 安康学院 学年论文（设计） 题目_____________________________________________ 学生姓名_______________ 学号_____________________________ 所在院（系）_______________________________________ 专业班级__________________________________________________ 指导教师_____________________________________________ 年月曰 基于粒子群优化算法的图像分割 （作者：） （） 指导教师： 【摘要】本文通过对粒子群优化算法的研究，采用Java编程，设计出一套用于图像分割的系统。 基于粒子群优化算法的图像分割系统，可以将一幅给定的图像进行分割，然后将分割结果保存。图像分割的目的是将感兴趣的区域从图像中分割出来，从而为计算机视觉的后续处理提供依据。图像分割的方法有多种，阈值法因其实现简单而成为一种有效的图像分割方法。而粒子群优化（PSO）算法是一类随机全局优化技术，它通过粒子间的相互作用发现复杂搜索空间中的最优区域缩短寻找阈值的时间。因此，基于粒子群优化算法的图像分割以粒子群优化算法为寻优工具，建立具有自适应和鲁棒性的分割方法。从而可以在最短的时间内，准确地确定分割阈值。 关键词：粒子群优化（PSO，图像分割，阈值法，鲁棒性 Abstract T his paper based on the particle swarm optimizati on algorithm, desig ns a set of system for image segme ntati on using Java program min g. Image segme ntati on system based on particle swarm optimizati on algorithm, the image can be a given segmentation, and then the segmentation results would be saved. Image segmentation is the purpose of the interested area from the image, thus providing the basis for the subsequent processing of computer vision. There are many methods of image segmentation, threshold method since its simple realization, becomes a kind of effective method in image segmentation. Particle swarm optimization （PSO） algorithm is a stochastic global optimization technique; it finds optimal regions of complex search spaces for threshold time shorte ned through the in teractio n betwee n particles. Therefore, particle swarm optimization algorithm of image segmentation based on particle swarm optimization algorithm based on optimizati on tools; establish segme ntati on method with adaptive and robust. Therefore, it is possible for us in the shortest possible time to accurately determ ine the segme ntati on threshold. Key word s: PSO, image segmentation, threshold method, robust. 1引言 1.1研究的背景和意义 技术的不断向前发展，人们越来越多地利用计算机来获取和处理视觉图像信息。据统计，人类 毕业论文 题目粒子群算法及其参数设置专业信息与计算科学 班级计算061 学号3060811007 学生xx 指导教师徐小平 2016年 I 粒子群优化算法及其参数设置 专业：信息与计算科学 学生： xx 指导教师：徐小平 摘要 粒子群优化是一种新兴的基于群体智能的启发式全局搜索算法，粒子群优化算法通过粒子间的竞争和协作以实现在复杂搜索空间中寻找全局最优点。它具有易理解、易实现、全局搜索能力强等特点，倍受科学与工程领域的广泛关注，已经成为发展最快的智能优化算法之一。论文介绍了粒子群优化算法的基本原理，分析了其特点。论文中围绕粒子群优化算法的原理、特点、参数设置与应用等方面进行全面综述，重点利用单因子方差分析方法，分析了粒群优化算法中的惯性权值，加速因子的设置对算法基本性能的影响，给出算法中的经验参数设置。最后对其未来的研究提出了一些建议及研究方向的展望。 关键词：粒子群优化算法；参数；方差分析；最优解 II Particle swarm optimization algorithm and its parameter set Speciality: Information and Computing Science Student: Ren Kan Advisor: Xu Xiaoping Abstract Particle swarm optimization is an emerging global based on swarm intelligence heuristic search algorithm, particle swarm optimization algorithm competition and collaboration between particles to achieve in complex search space to find the global optimum. It has easy to understand, easy to achieve, the characteristics of strong global search ability, and has never wide field of science and engineering concern, has become the fastest growing one of the intelligent optimization algorithms. This paper introduces the particle swarm optimization basic principles, and analyzes its features. Paper around the particle swarm optimization principles, characteristics, parameters settings and applications to conduct a thorough review, focusing on a single factor analysis of variance, analysis of the particle swarm optimization algorithm in the inertia weight, acceleration factor setting the basic properties of the algorithm the impact of the experience of the algorithm given parameter setting. Finally, its future researched and prospects are proposed. Key word：Particle swarm optimization; Parameter; Variance analysis; Optimal solution III 主函数源程序（main.m） %------基本粒子群优化算法（Particle Swarm Optimization）-----------%------名称：基本粒子群优化算法（PSO） %------作用：求解优化问题 %------说明：全局性，并行性，高效的群体智能算法 %------初始格式化--------------------------------------------------clear all; clc; format long; %------给定初始化条件---------------------------------------------- c1=1.4962;%学习因子1 c2=1.4962;%学习因子2 w=0.7298;%惯性权重 MaxDT=1000;%最大迭代次数 D=10;%搜索空间维数（未知数个数） N=40;%初始化群体个体数目 eps=10^(-6);%设置精度(在已知最小值时候用) %------初始化种群的个体(可以在这里限定位置和速度的范围)------------for i=1:N for j=1:D x(i,j)=randn;%随机初始化位置 v(i,j)=randn;%随机初始化速度 end end %------先计算各个粒子的适应度，并初始化Pi和Pg----------------------for i=1:N p(i)=fitness(x(i,:),D); y(i,:)=x(i,:); end pg=x(1,:);%Pg为全局最优 for i=2:N if fitness(x(i,:),D) 粒子群优化算法(1)—粒子群优化算法简介 PSO算法就是模拟一群鸟寻找食物的过程，每个鸟就是PSO中的粒子，也就是我们需要求解问题的可能解，这些鸟在寻找食物的过程中，不停改变自己在空中飞行的位置与速度。大家也可以观察一下，鸟群在寻找食物的过程中，开始鸟群比较分散，逐渐这些鸟就会聚成一群，这个群忽高忽低、忽左忽右，直到最后找到食物。这个过程我们转化为一个数学问题。寻找函数y=1-cos(3*x)*exp(-x)的在[0,4]最大值。该函数的图形如下： 当x=0.9350-0.9450，达到最大值y=1.3706。为了得到该函数的最大值，我们在[0, 4]之间随机的洒一些点，为了演示，我们放置两个点，并且计算这两个点的函数值，同时给这两个点设置在[0, 4]之间的一个速度。下面这些点就会按照一定的公式更改自己的位置，到达新位置后，再计算这两个点的值，然后再按照一定的公式更新自己的位置。直到最后在y=1.3706这个点停止自己的更新。这个过程与粒子群算法作为对照如下： 这两个点就是粒子群算法中的粒子。 该函数的最大值就是鸟群中的食物。 计算两个点函数值就是粒子群算法中的适应值，计算用的函数就是粒子群算法中的适应度函数。 更新自己位置的公式就是粒子群算法中的位置速度更新公式。 下面演示一下这个算法运行一次的大概过程： 第一次初始化 第一次更新位置 第二次更新位置 第21次更新 最后的结果（30次迭代） 最后所有的点都集中在最大值的地方。 粒子群优化算法(2)—标准粒子群优化算法 在上一节的叙述中，唯一没有给大家介绍的就是函数的这些随机的点（粒子）是如何运动的，只是说按照一定的公式更新。这个公式就是粒子群算法中的位置速度更新公式。下面就介绍这个公式是什么。在上一节中我们求取函数y=1-cos(3*x)*exp(-x)的在[0, 4]最大值。并在[0,4]之间放置了两个随机的点，这些点的坐标假设为x1=1.5，x2=2.5；这里的点是一个标量，但是我们经常遇到的问题可能是更一般的情况—x 为一个矢量的情况，比如二维z=2*x1+3*x22的情况。这个时候我们的每个粒子均为二维，记粒子P1＝(x11,x12),P2=(x21,x22),P3=(x31,x32)，......Pn=(xn1,xn2)。这里n 为粒子群群体的规模，也就是这个群中粒子的个数，每个粒子的维数为2。更一般的是粒子的维数为q ，这样在这个种群中有n 个粒子，每个粒子为q 维。 由n 个粒子组成的群体对Q 维（就是每个粒子的维数）空间进行搜索。每个粒子表示为：x i ＝（x i1,x i2,x i3,...,x iQ ），每个粒子对应的速度可以表示为v i =(v i1,v i2,v i3,....,v iQ )，每个粒子在搜索时要考虑两个因素： 1. 自己搜索到的历史最优值 p i ，p i =(p i1,p i2,....,p iQ )，i=1,2,3,....,n ； 2. 全部粒子搜索到的最优值p g ，p g =(p g1,p g2,....,p gQ )，注意这里的p g 只有一个。 下面给出粒子群算法的位置速度更新公式： 112()()()()k k k k i i i i v v c rand pbest x c rand gbest x ω+=+??-+??-, 11k k k i i i x x av ++=+. 这里有几个重要的参数需要大家记忆，因为在以后的讲解中将会经常用到，它们是： ω是保持原来速度的系数，所以叫做惯性权重。1c 是粒子跟踪自己历史最优值的权重系数，它表示粒子自身的认识，所以叫“认知”。通常设置为2。2c 是粒子跟踪群体最优值的权重系数，它表示粒子对整个群体知识的认识，所以叫做“社会知识”，经常叫做“社会”。通常设置为2。()rand 是[0,1]区间内均匀分布的随机数。a 是对位置更新的时候，在速度前面加的一个系数，这个系数我们叫做约束因子。通常设置为1。这样一个标准的粒子群算法就介绍结束了。下图是对整个基本的粒子群的过程给一个简单的图形表示。 判断终止条件可是设置适应值到达一定的数值或者循环一定的次数。 注意：这里的粒子是同时跟踪自己的历史最优值与全局（群体）最优值来改变自己的位置预速度的，所以又叫做全局版本的标准粒子群优化算法。 智能控制技术 课程论文 中文题目: 粒子群算法的研究现状及其应用姓名学号: 指导教师： 年级与专业： 所在学院： XXXX年XX月XX日 1 研究的背景 优化问题是一个古老的问题，可以将其定义为：在满足一定约束条件下，寻找一组参数值，使系统的某些性能指标达到最大值或最小值。在我们的日常生活中，我们常常需要解决优化问题，在一定的范围内使我们追求的目标得到最大化。为了解决我们遇到的最优化问题，科学家，们进行了不懈的努力，发展了诸如牛顿法、共轭梯度法等诸多优化算法，大大推动了优化问题的发展，但由于这些算法的低运行效率，使得在计算复杂度、收敛性等方面都无法满足实际的生产需要。 对此，受达尔文进化论的影响，一批新的智能优化算法相继被提出。粒子群算法（PSO ）就是其中的一项优化技术。1995 年Eberhart 博士和Kennedy 博士[1]-[3]通过研究鸟群捕食的行为后，提出了粒子群算法。设想有一群鸟在随机搜索食物，而在这个区域里只有一块食物，所有的鸟都不知道食物在哪里。那么找到食物最简单有效的办法就是鸟群协同搜寻，鸟群中的每只鸟负责离其最近的周围区域。 粒子群算法是一种基于群体的优化工具，尤其适用于复杂和非线性问题。系统初始化为一组随机解，通过迭代搜寻最优值，通过采用种群的方式组织搜索，同时搜索空间内的多个区域，所以特别适合大规模并行计算，具有较高的效率和简单、易操作的特性。 目前使用的粒子群算法的数学描述[3]为：设粒子的寻优空间是m 维的，粒子的数目为ps ，算法的最大寻优次数为Iter 。第i 个粒子的飞行速度为T i i1i2im v [v v ]= ,,,v ，位置为T i i1i2im x [x x x ]= ,,,，粒子的个体极值T i i1i2im Pbest [,]P = ,P ,P ，全局极值为 T i i1i2im Gbest [,]g = ,g ,g 。 粒子群算法的寻优过程主要由粒子的速度更新和位置更新两部分组成，其更新方式如下： i+11122v ()()i i i i i v c r Pbest x c r Gbest x =+?+?； i+1i+1i x x v =+， 式中：12c c ，为学习因子，一般取2；12r r ，是均与分布着[0,1]上的随机数。 对于函数f=x*sin(x)*cos(2*x)-2*x*sin(3*x)，求其在区间[0,20]上该函数的最大值。 ?初始化种群 已知位置限制[0,20],由于一维问题较为简单，因此可以取初始种群N 为50，迭代次数为100,当然空间维数d 也就是1。 位置和速度的初始化即在位置和速度限制内随机生成一个N×d 的矩阵，对于此题，位置初始化也就是在0~20内随机生成一个50×1的数据矩阵，而对于速度则不用考虑约束，一般直接在0~1内随机生成一个50×1的数据矩阵。 此处的位置约束也可以理解为位置限制，而速度限制是保证粒子步长不超限制的，一般设置速度限制为[-1,1]。 粒子群的另一个特点就是记录每个个体的历史最优和种群的历史最优，因此而二者对应的最优位置和最优值也需要初始化。其中每个个体的历史最优位置可以先初始化为当前位置,而种群的历史最优位置则可初始化为原点。对于最优值，如果求最大值则初始化为负无穷，相反地初始化为正无穷。 每次搜寻都需要将当前的适应度和最优解同历史的记录值进行对比，如果超过历史最优值，则更新个体和种群的历史最优位置和最优解。 ?速度与位置的更新 速度和位置更新是粒子群算法的核心，其原理表达式和更新方式如下: 每次更新完速度和位置都需要考虑速度和位置的限制，需要将其限制在规定范围内，此处仅举出一个常规方法，即将超约束的数据约束到边界（当位置或者速度超出初始化限制时，将其拉回靠近的边界处）。当然，你不用担心他会停住不动，因为每个粒子还有惯性和其他两个参数的影响。 代码如下： clc;clear;close all; %% 初始化种群 f= @(x)x .* sin(x) .* cos(2 * x) - 2 * x .* sin(3 * x); % 函数表达式figure(1);ezplot(f,[0,0.01,20]); N = 50; % 初始种群个数 d = 1; % 空间维数 ger = 100; % 最大迭代次数 limit = [0, 20]; % 设置位置参数限制 vlimit = [-1, 1]; % 设置速度限制 w = 0.8; % 惯性权重 c1 = 0.5; % 自我学习因子 c2 = 0.5; % 群体学习因子 for i = 1:d 基本粒子群算法的原理和matlab 程序 作者—— niewei120 （nuaa） 一、粒子群算法的基本原理 粒子群优化算法源自对鸟群捕食行为的研究，最初由Kennedy 和 Eberhart 提出，是一种通 用的启发式搜索技术。一群鸟在区域中随机搜索食物，所有鸟知道自己当前位置离食物多远， 那么搜索的最简单有效的策略就是搜寻目前离食物最近的鸟的周围区域。PSO 算法利用这种模型得到启示并应用于解决优化问题。PSO 算法中，每个优化问题的解都是粒子在搜索 空间中的位置，所有的粒子都有一个被优化的目标函数所决定的适应值，粒子还有一个速度值决定它们飞翔的方向和距离，然后粒子群就追随当前的最优粒子在解空间中搜索。 PSO 算法首先在给定的解空间中随机初始化粒子群，待优化问题的变量数决定了解空间的维数。每个粒子有了初始位置与初始速度。然后通过迭代寻优。在每一次迭代中，每个粒子通过跟踪两个“极值”来更新自己在解空间中的空间位置与飞翔速度。第一个极值就是单个粒子本身在迭代过程中找到的最优解粒子，这个粒子叫做个体极值。另一个极值是种群所有粒子在迭代过程中所找到的最优解粒子，这个粒子是全局极值。上述的方法叫全局粒子群算法。如果不用种群所有粒子而只用其中一部分作为该粒子的邻居粒子，那么在所有邻居粒子中的极值就是局部极值，该方法称为局部PSO 算法。 速度、位置的更新方程表示为： 每个粒子自身搜索到的历史最优值p i，p i=(p i1 ,p i2 ,....,p iQ )， i=1,2,3,....,n 。所有粒子搜索到的最优值p g， p g=(p g1 ,p g2,....,p gQ )，注意这里的p g只有一个。 是保持原来速度的系数，所以叫做惯性权重。 是粒子跟踪自己历史最优值的权重系数，它表示粒子自身的认识，所以叫“认知”。通常设置为 2 。 是粒子跟踪群体最优值的权重系数，它表示粒子对整个群体知识的认识，所以叫做“社会知识”，经常叫做“社会”。通常设置为2。 是[0,1] 区间内均匀分布的随机数。 是对位置更新的时候，在速度前面加的一个系数，这个系数我们叫做约束因子。通常设 置为 1 。 4.1粒子群算法基本原理 粒子群优化算法[45]最原始的工作可以追溯到1987年Reynolds 对鸟群社会系统Boids （Reynolds 对其仿真鸟群系统的命名）的仿真研究 。通常，群体的行为可以由几条简单的规则进行建模，虽然每个个体具有简单的行为规则，但是却群体的行为却是非常的复杂，所以他们在鸟类仿真中，即Boids 系统中采取了下面的三条简单的规则： （1）飞离最近的个体(鸟)，避免与其发生碰撞冲突； （2）尽量使自己与周围的鸟保持速度一致； （3）尽量试图向自己认为的群体中心靠近。 虽然只有三条规则，但Boids 系统已经表现出非常逼真的群体聚集行为。但Reynolds 仅仅实现了该仿真，并无实用价值。 1995年Kennedy [46-48]和Eberhart 在Reynolds 等人的研究基础上创造性地提出了粒子群优化算法，应用于连续空间的优化计算中 。Kennedy 和Eberhart 在boids 中加入了一个特定点，定义为食物，每只鸟根据周围鸟的觅食行为来搜寻食物。Kennedy 和Eberhart 的初衷是希望模拟研究鸟群觅食行为，但试验结果却显示这个仿真模型蕴含着很强的优化能力，尤其是在多维空间中的寻优。最初仿真的时候，每只鸟在计算机屏幕上显示为一个点，而“点”在数学领域具有多种意义，于是作者用“粒子（particle ）”来称呼每个个体，这样就产生了基本的粒子群优化算法[49]。 假设在一个D 维搜索空间中，有m 个粒子组成一粒子群，其中第i 个粒子的空间位置为123(,,,...,)1,2,...,i i i i iD X x x x x i m ==，它是优化问题的一个潜在解，将它带入优化目标函数可以计算出其相应的适应值，根据适应值可衡量i x 的优劣；第i 个粒子所经历的最好位置称为其个体历史最好位置，记为123(,,,...,)1,2,...,i i i i iD P p p p p i m ==，相应的适应值为个体最好适应值 Fi ；同时，每个粒子还具有各自的飞行速度123(,,,...,)1,2,...,i i i i iD V v v v v i m ==。所有粒子经历过的位置中的最好位置称为全局历史最好位置，记为 粒子群算法 题目：求∑==10 12)(i i x x f 的最小值 1粒子群简介 粒子群优化算法PSO 也是起源对简单社会系统的模拟。最初设想是模拟鸟群觅食的过程。粒子群优化算法是由Kennedy 和Eberhart 通过对鸟群、鱼群和人类社会某些行为的观察研究，于1995年提出的一种新颖的进化算法。 PSO 算法属于进化算法的一种，和遗传算法相似，它也是从随机解出发，通过迭代寻找最优解，它也是通过适应度来评价解的品质，但它比遗传算法规则更为简单，它没有遗传算法的“交叉”和“变异” 操作，它通过追随当前搜索到的最优值来寻找全局最优。这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视，并且在解决实际问题中展示了其优越性。 2算法的原理 PSO 从这种模型中得到启示并用于解决优化问题。PSO 中，每个优化问题的潜在解都是搜索空间中的一只鸟，称之为粒子。所有的粒子都有一个由被优化的函数决定的适值( fitness value) ，每个粒子还有一个速度决定它们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。 PSO 初始化为一群随机粒子(随机解)，然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个极值来更新自己；第一个就是粒子本身所找到的最优解，这个解称为个体极值；另一个极值是整个种群目前找到的最优解，这个极值是全局极值。另外也可以不用整个种群而只是用其中一部分作为粒子的邻居，那么在所有邻居中的极值就是局部极值。 假设在一个D 维的目标搜索空间中，有N 个粒子组成一个群落，其中第i 个 粒子表示为一个D 维的向量 ),,,(21iD i i i x x x X =，N i ,,2,1 = 第i 个粒子的“飞行 ”速度也是一个D 维的向量，记为 ),,21i iD i i v v v V ，（= ，3,2,1 =i 第i 个粒子迄今为止搜索到的最优位置称为个体极值，记为 ),,,(21iD i i best p p p p =，N i ,,2,1 = 整个粒子群迄今为止搜索到的最优位置为全局极值，记为 ),,,(21gD g g best p p p g = 在找到这两个最优值时，粒子根据如下的公式(2.1)和( 2.2)来更新自己的速度和位置： ())(2211id gd id id id id x p r c x p r c v w v -+-+*= (2.1) id id id v x x += (2. 2) 其中：1c 和2c 为学习因子，也称加速常数，1r 和2r 为[0，1]范围内的均匀随机数。式(2.1)右边由三部分组成，第一部分为“惯性”或“动量”部分，反映了粒子的运动“习惯”，代表粒子有维持自己先前速度的趋势；第二部分为“认知”部分，反映了粒子对自身历史经验的记忆或回忆，代表粒子有向自身历史最佳位置逼近的趋势；第三部分为“社会”部分，反映了粒子间协同合作与知识共享的群体历史经验，代表粒子有向群体或邻域历史最佳位置逼近的趋势，根据经验，通常221==c c 。D i ,,2,1 =。id v 是粒子的速度，],[max max v v v id -∈，max v 是常数，由用户设定用来限制粒子的速度。1r 和2r 是介于[0,1]之间的随机数。 探索是偏离原来的寻优轨迹去寻找一个更好的解，探索能力是一个算法的全 粒子群算法(1)----粒子群算法简介 二、粒子群算法的具体表述 上面罗嗦了半天，那些都是科研工作者写论文的语气，不过，PSO的历史就像上面说的那样。下面通俗的解释PSO算法。 PSO算法就是模拟一群鸟寻找食物的过程，每个鸟就是PSO.中的粒子，也就是我们需要求解问题的可能解，这些鸟在寻找食物的过程中，不停改变自己在空中飞行的位置与速度。大家也可以观察一下，鸟群在寻找食物的过程中，开始鸟群比较分散，逐渐这些鸟就会聚成一群，这个群忽高忽低、忽左忽右，直到最后找到食物。这个过程我们转化为一个数学问题。寻找函数y=1-cos(3*x)*exp(-x)的在[0,4]最大值。该函数的图形如下： 当x=0.9350-0.9450，达到最大值y=1.3706。为了得到该函数的最大值，我们在[0，4]之间随机的洒一些点，为了演示，我们放置两个点，并且计算这两个点的函数值，同时给这两个点设置在[0，4]之间的一个速度。下面这些点就会按照一定的公式更改自己的位置，到达新位置后，再计算这两个点的值，然后再按照一定的公式更新自己的位置。直到最后在y=1.3706这个点停止自己的更新。这个过程与粒子群算法作为对照如下： 这两个点就是粒子群算法中的粒子。 该函数的最大值就是鸟群中的食物 计算两个点函数值就是粒子群算法中的适应值，计算用的函数就是粒子群算法中的适应度函数。 更新自己位置的一定公式就是粒子群算法中的位置速度更新公式。 下面演示一下这个算法运行一次的大概过程： 第一次初始化 第一次更新位置 第二次更新位置 第21次更新 最后的结果（30次迭代） 最后所有的点都集中在最大值的地方。 //粒子群PSO算法 #include 粒子群算法(1)----粒子群算法简介 一、粒子群算法的历史 粒子群算法源于复杂适应系统（Complex Adaptive System,CAS）。CAS理论于1994年正式提出，CAS中的成员称为主体。比如研究鸟群系统，每个鸟在这个系统中就称为主体。主体有适应性，它能够与环境及其他的主体进行交流，并且根据交流的过程“学习”或“积累经验”改变自身结构与行为。整个系统的演变或进化包括：新层次的产生（小鸟的出生）；分化和多样性的出现（鸟群中的鸟分成许多小的群）；新的主题的出现（鸟寻找食物过程中，不断发现新的食物）。 所以CAS系统中的主体具有4个基本特点（这些特点是粒子群算法发展变化的依据）： 首先，主体是主动的、活动的。 主体与环境及其他主体是相互影响、相互作用的，这种影响是系统发展变化的主要动力。 环境的影响是宏观的，主体之间的影响是微观的，宏观与微观要有机结合。 最后，整个系统可能还要受一些随机因素的影响。 粒子群算法就是对一个CAS系统－－－鸟群社会系统的研究得出的。 粒子群算法（Particle Swarm Optimization, PSO）最早是由Eberhart和Kennedy于1995年提出，它的基本概念源于对鸟群觅食行为的研究。设想这样一个场景:一群鸟在随机搜寻食物，在这个区域里只有一块食物，所有的鸟都不知道食物在哪里，但是它们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢?最简单有效的就是搜寻目前离食物最近的鸟的周围区域。 PSO算法就从这种生物种群行为特性中得到启发并用于求解优化问题。在PSO中，每个优化问题的潜在解都可以想象成d维搜索空间上的一个点，我们称之为“粒子”（Particle），所有的粒子都有一个被目标函数决定的适应值(Fitness Value )，每个粒子还有一个速度决定他们飞翔的方向和距离，然后粒子们就追随当前的最优粒子在解空间中搜索。Reynolds对鸟群飞行的研究发现。鸟仅仅是追踪它有限数量的邻居但最终的整体结果是整个鸟群好像在一个中心的控制之下.即复杂的全局行为是由简单规则的相互作用引起的。 二、粒子群算法的具体表述 上面罗嗦了半天，那些都是科研工作者写论文的语气，不过，PSO的历史就像上面说的那样。下面通俗的解释PSO算法。 PSO算法就是模拟一群鸟寻找食物的过程，每个鸟就是PSO中的粒子，也就是我们需要求解问题的可能解，这些鸟在寻找食物的过程中，不停改变自己在空中飞行的位置与速度。大家也可以观察一下，鸟群在寻找食物的过程中，开始鸟群比较分散，逐渐这些鸟就会聚成一群，这个群忽高忽低、忽左忽右，直到最后找到食物。这个过程我们转化为一个数学问题。寻找函数y=1-cos(3*x)*exp(-x)的在[0,4]最大值。该函数的图形如下： 摘自：人工智能论坛 1. 引言 粒子群优化算法(PSO)是一种进化计算技术(evolutionary computation)，有Eberhart博士和kennedy博士发明。源于对鸟群捕食的行为研究 PSO同遗传算法类似，是一种基于叠代的优化工具。系统初始化为一组随机解，通过叠代搜寻最优值。但是并没有遗传算法用的交叉(crossover)以及变异(mutation)。而是粒子在解空间追随最优的粒子进行搜索。详细的步骤以后的章节介绍 同遗传算法比较，PSO的优势在于简单容易实现并且没有许多参数需要调整。目前已广泛应用于函数优化，神经网络训练，模糊系统控制以及其他遗传算法的应用领域 2. 背景: 人工生命 "人工生命"是来研究具有某些生命基本特征的人工系统. 人工生命包括两方面的内容 1. 研究如何利用计算技术研究生物现象 2. 研究如何利用生物技术研究计算问题 我们现在关注的是第二部分的内容. 现在已经有很多源于生物现象的计算技巧. 例如, 人工神经网络是简 化的大脑模型. 遗传算法是模拟基因进化过程的. 现在我们讨论另一种生物系统- 社会系统. 更确切的是, 在由简单个体组成的群落与环境以及个体之间的 互动行为. 也可称做"群智能"(swarm intelligence). 这些模拟系统利用局部信息从而可能产生不可预测的群体行为 例如floys 和boids, 他们都用来模拟鱼群和鸟群的运动规律, 主要用于计算机视觉和计算机辅助设计. 在计算智能(computational intelligence)领域有两种基于群智能的算法. 蚁群算法(ant colony optimization)和粒子群算法(particle swarm optimization). 前者是对蚂蚁群落食物采集过程的模拟. 已经成功运用在很多离散优化问题上. 粒子群优化算法(PSO) 也是起源对简单社会系统的模拟. 最初设想是模拟鸟群觅食的过程. 但后来发现PS O是一种很好的优化工具. 3. 算法介绍 如前所述，PSO模拟鸟群的捕食行为。设想这样一个场景：一群鸟在随机搜索食物。在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢。最简单有效的就是搜寻目前离食物最近的鸟的周围区域。 PSO从这种模型中得到启示并用于解决优化问题。PSO中，每个优化问题的解都是搜索空间中的一只鸟。 基于粒子群优化算法的神经网络在农药定量构效关系建模中的应用 张丽平 俞欢军3 陈德钊 胡上序 (浙江大学化工系,杭州310027) 摘 要 神经网络模型能有效模拟非线性输入输出关系,但其常规训练算法为BP 或其它梯度算法,导致训练时间较长且易陷入局部极小点。本实验探讨用粒子群优化算法训练神经网络,并应用到苯乙酰胺类农药的定量构效关系建模中,对未知化合物的活性进行预测来指导新药的设计和合成。仿真结果表明,粒子群优化算法训练的神经网络不仅收敛速度明显加快,而且其预报精度也得到了较大的提高。关键词 粒子群优化算法,神经网络,定量构效关系 2004201204收稿;2004207225接受 本文系国家自然科学基金资助项目(N o.20276063) 1 引 言 药物定量构效关系(QS AR )是研究药物生理活性和药物分子结构参数间的量变规律并建立相应的 数学模型,进而研究药物的作用机理,从而用于预测未知化合物的生物活性,探讨药物的作用机理,指导新药的设计和合成,在药物和农药的研究与设计中已经显示出广阔的应用前景1。以往QS AR 的建模方法大多基于统计原理,局限于线性模型,只进行简单的非线性处理,由此所建立的模型很难契合实际构效关系,并且其处理过程都比较繁琐2。神经网络通过学习将构效关系知识隐式分布在网络之中,适用于高度非线性体系。 在药物QS AR 中采用神经网络(NN )始于20世纪80年代末3,此后得到迅速的发展,目前已发展为除多重线性回归和多元数据分析之外的第3种方法4。通常多层前传网络采用BP 算法,通过误差反传,按梯度下降的方向调整权值。其缺点是可能陷入局部极小点,且对高维输入收敛速度非常缓慢。 粒子群优化算法(particle swarm optimization ,PS O )是K ennedy 等5源于对鸟群、鱼群和人类社会行为的研究而发展的一种新的进化型寻优技术。PS O 已成为进化寻优算法研究的热点,其最主要特点是简单、收敛速度快,且所需领域知识少。本实验拟将该方法初始化前传神经网络为苯乙酰胺类农药建立良好适用的QS AR 模型。 2 苯乙酰胺类农药的Q SAR 问题 苯乙酰胺类化合物是除草农药,其除草活性与其分子结构密切相关。所有的N 2(12甲基212苯乙基)苯乙酰胺都可用相应的羧酸酰胺通过霍夫曼反应生成。N 2(12甲基212苯乙基)苯乙酰胺的基本结构式为 : 其中X 为Me 、F 、Cl 、OMe 、CF 3和Br 等,Y 为Me 、Cl 、F 和Br 等,由不同的X 和Y 取代基可构成不同的化合物。常用以下7个理化参数描述化合物的分子组成和结构:log P 、log 2P (疏水性参数及其平方项)、 σ(电性效应参数)、E s (T aft 立体参数)、MR (摩尔折射度),1χ、2 χ(分子连接性指数)。于是这类化合物的QS AR 就转化为上述理化参数与除草活性间的关系。为研究这种关系,选用具有代表性的50个化合物, 他们的活性值取自文献1,见表1。 第32卷2004年12月分析化学(FE NXI H UAX UE ) 研究报告Chinese Journal of Analytical Chemistry 第12期1590～1594 程序1 当22111==c c ，5.12212==c c ，2.1=w 。 a)%主函数源程序（main.m ） %------基本粒子群算法 （particle swarm optimization ） %------名称： 基本粒子群算法 %------初始格式化 clear all ; %清除所有变量 clc; %清屏 format long ; %将数据显示为长整形科学计数 %------给定初始条条件------------------ N=40; %3初始化群体个数 D=10; %初始化群体维数 T=100; %初始化群体最迭代次数 c11=2; %学习因子1 c21=2; %学习因子2 c12=1.5; c22=1.5; w=1.2; %惯性权重 eps=10^(-6); %设置精度（在已知最小值的时候用） %------初始化种群个体（限定位置和速度）------------ x=zeros(N,D); v=zeros(N,D); for i=1:N for j=1:D x(i,j)=randn; %随机初始化位置 v(i,j)=randn; %随机初始化速度 end end %------显示群位置---------------------- figure(1) for j=1:D if (rem(D,2)>0) subplot((D+1)/2,2,j) else subplot(D/2,2,j) end plot(x(:,j),'b*');grid on xlabel('粒子') ylabel('初始位置') tInfo=strcat('第',char(j+48),'维'); if(j>9) tInfo=strcat('第',char(floor(j/10)+48)，char(rem(j,10)+48),'维'); end title(tInfo) end %------显示种群速度 figure(2) for j=1:D if(rem(D,2)>0) subplot((D+1)/2,2,j) else subplot(D/2,2,j) end plot(x(:,j),'b*');grid on xlabel('粒子') ylabel('初始速度') tInfo=strcat('第,char(j+48),'维'); if(j>9) tInfo=strcat('第',char(floor(j/10)+48), char(rem(j,10)+48),'维); end title(tInfo) end figure(3) %第一个图 subplot(1,2,1)(完整word版)基本粒子群算法的原理和matlab程序
基于粒子群优化算法的图像分割
粒子群优化算法及其参数设置
基本粒子群算法的matlab源程序
粒子群优化算法介绍及matlab程序
粒子群算法的研究现状及其应用
基于MATLAB的粒子群优化算法的应用示例
(完整word版)基本粒子群算法的原理和matlab程序.doc
粒子群算法基本原理
粒子群算法简介和使用
粒子群算法(1)----粒子群算法简介
c语言实现的粒子群算法代码及解释
粒子群算法详解-附matlab代码说明
粒子群算法的论文
基于粒子群优化算法的神经网络在
6种粒子群算法程序
相关主题
文本预览