第一章 绪 论
1.1 最优化问题
所谓最优化问题，就是在满足一定的约束条件下，寻找一组参数值，以使某些最优性度量得到满足，即使系统的某些性能指标达到最大或最小。最优化问题的应用可以说遍布工业、社会、经济、管理等各个领域，其重要性是不言而喻的。
最优化问题根据其目标函数、约束函数的性质以及优化变量的取值等可以分成许多类型，每一种类型的最优化问题根据其性质的不同都有其特定的求解方法。
不失一般性，设所考虑的最优化问题为：
}
,,10
)(|{..)
(min m j X g X S X t s X f i …=≤=∈=σ (1.1)
其中，)(X f =σ为目标函数，为约束函数，S 为约束域，)(X g i X 为n 维优化变量。通常最大化问题很容易转换为最小化问题()(X f ?=σ)，对于的约束和等式约束也可转换为
的约束，所以(1.1)式所描述的最优化问题不失一般性。
0)(≥X g i 0)(≤?X g i 当、为线性函数，且时，上述最优化问题即为线性规划问题，其求解方法有成熟的单纯形法和Karmarc 方法。
)(X f )(X g i 0≥X 当、中至少有一个函数为非线性函数时，上述问题即为非线性规划问题。非线性规划问题相当复杂，其求解方法多种多样，但到目前仍然没有一种有效的适应所有问题的方法。 )(X f )(X g i 当优化变量X 仅取整数值时，上述问题即为整数规划问题，特别是当X 仅能取0或1时，上述问题即为0－1整数规划问题。由于整数规划问题属于组合优化范畴，其计算量随变量维数的增长而指数增长，所以存在着“维数灾难”问题。
当),,1(0)(m j X g i …=≤所限制的约束空间为整个n 维欧氏空间，即R n 时，上述最优化问题为无约束优化问题，即
n
R S X t s X f ?∈=..)
(min σ (1.2)
非线性规划问题（包括无约束优化问题和约束优化问题），由于函数的非线性，使得问题的求解变得十分困难，特别是当目标函数在约束域内存在多峰值时。常见的求解非线性问题的优化方法，其求解结果与初值的选择关系很大，也就是说，一般的约束或无约束非线性优化方法均是求目标函数在约束域内的近似极值点，而非真正的最小点。
1.1.1局部优化算法
定义1.1 如果存在，使得对B X B ∈*
B X ∈?有
B X X f X f B ∈≤),()(*
(1.3)
成立，其中，S 为由约束函数限定的搜索空间，则称为在B 内的局部极小点，为局部极小值。
n
R S B ??*
B X )(X f )(*
B X f 常见的优化方法大多为局部优化方法，都是从一个给定的初始点S X ∈0开始，依据一定的方法寻找下一个使得目标函数得到改善的更好解，直至满足某种停止准则。
成熟的局部优化方法很多，如Newton-Raphson 法、共轭梯度法、Fletcher-Reeves 法、Polar-Ribiere 法、Davidon-Fletcher-Power(DFP)法、Broyden-Fletcher-Goldfarb-Shann(BFGS)方法等等，还有专门为求解最小二乘问题而发展的Levenberg-Marquardt(LM)算法。所有这些局部优化算法都是针对无约束优化问题而提出的，而且对目标函数均有一定的解析性质要求，如Newton-Raphson 法要求目标函数连续可微，同时要求其一阶导数连续。
对于约束非线性优化问题，除了根据一阶最优化必要条件直接将最优化问题转换为非线性代数方程组，然后采用非线性代数方程组的数值解法进行求解外，还有序列线性规划法、可行方向法、拉格朗日乘子法等等。最常用的方法是将约束问题通过罚函数法转换为无约束优化问题，然后再采用无约束优化方法进行求解。这些具体方法请读者参阅有关最优化理论与方法方面的文献。
1.1.2全局优化算法
定义1.2 如果存在，使得对S X ∈*
S X ∈?，有：
S X X f X f ∈≤),
()(* (1.4)
成立，其中为由约束条件限定的搜索空间，则称n
R S ?*
X 为在S 内的全局极小点，为其全局极小值。
)(X f )(*
X f 前面指出，已发展成熟的最优化方法大多为局部优化方法，其求解结果与初始值相关。对于目标函数为凸函数、约束域为凸域的所谓凸规划问题，局部最优与全局最优等效。而对于非凸问题，由于在约束域内目标函数存在多峰值，因而其全局最优与局部最优相差甚远。
目前为止，全局优化问题也已存在了许多算法，如填充函数法等，但比起局部优化问题的众多成熟方法，其间还有很大差距。
另外，解析性优化方法对目标函数及约束域均有较强的解析性要求，对于诸如目标函数不连续、约束域不连通、目标函数难以用解析函数表达或者难以精确估计(如仿真优化问题)等问题时，解析确定性优化方法就难以适应。
为了可靠解决全局优化问题，人们试图离开解析确定型的优化算法研究，转而探讨对函数解析性质要求较低甚至不作要求的随机型优化方法。最早的随机型优化方法是基于Monte-Carlo 方法的思想，针对具体问题性质的特点，构造以概率1收敛于全局最小点的随机搜索算法。真正有效且具有普遍适应性的随机全局优化方法，是近十多年来人们模拟自然界的一些自然现象而发展起来的一系列仿生型智能优化算法，如模拟退火方法、进化类算法、群体智能算法等等。
1.1.3无免费午餐定理(No Free Lunch Theorem)
在最优化理论研究领域中，最值得一提的是Wolpert 和Macready 于1997年在IEEE Transactions on Evolutionary Computation 上发表了题为“No Free Lunch Theorems for Optimization ”
的论文，提出并严格论证了所谓的无免费午餐定理，简称NFL 定理。
NFL 定理的简单表述为：对于所有可能的问题，任意给定两个算法A ，A ’，如果A 在某些问题上表现比A ’好(差)，那么A 在其它问题上的表现就一定比A ’差(好)，也就是说，任意两个算法A 、A ’对所有问题的平均表现度量是完全一样的。
有关NFL 定理的推导与证明请参阅文献[Wolpert 1997]。
自从NFL 定理提出以来，有关定理本身及其相关结论的争论在学术界一直持续未断，因为 NFL 定理本身涉及到了优化算法最基本的问题，而且其结论多少有点出人意料。
NFL 定理的主要价值在于它对研究与应用优化算法时的观念性启示作用。虽然NFL 定理是在许多假设条件下得出的，但它仍然在很大程度上反映出了优化算法的本质。当我们所面对的是一个大的而且形式多样的适应值函数类时，就必须考虑算法间所表现出的NFL 效应。即若算法A 在某些函数上的表现超过算法A ’，则在这类的其它适应值函数上，算法A ’的表现就比A 要好。因此，对于整个函数类，不存在万能的最佳算法，所有算法在整个函数类上的平均表现度量是一样的。
有了上述讨论，关于优化算法的研究目标就应该从寻找一个大的函数类上的优化算法转变为：
(1) 以算法为导向，从算法到问题。对于每一个算法，都有其适用和不适用的问题；给定一个算法，尽可能通过理论分析，给出其适用问题类的特征，使其成为一个“指示性”的算法。 (2) 以问题为导向，从问题到算法。对于一个小的特定的函数集，或者一个特定的实际问题，可以设计专门适用的算法。
实际上，大多数在进化算法方面的研究工作可以看作是属于这一范畴的，因为它们主要是根据进化的原理设计新的算法，或者将现有算法进行部分改进，以期对若干特定的函数取得好的优化效果。
读者可能会产生这样的疑问，既然NFL 定理表明，进化算法并不比一般随机搜索算法好，那么为什么还要去研究进化算法呢？实际上，NFL 定理只是否定了去寻找一个万能的最佳算法的可能性，但对于某些小的函数集合，NFL 定理则认为存在一个在该集合上的好算法。在求解某些或某个特定的复杂优化问题时，可能会出现现有大多数优化方法都不适用、而适用的少数方法效果又不理想的情况。这时，进化算法就大有用武之地。由于所有进化类算法均具有很强的通用性，对目标函数的解析性质几乎没有要求，因此将进化类算法作为求解优化问题的一个候选算法将是非常有意义的。
1.2 进化计算
近十余年来，遗传算法(Genetic Algorithm ，GA)、进化策略(Evolutionary Strategy ，ES)、进化规划(Evolutionary Programming ，EP)和遗传程序设计(Genetic Programming ，GP)等进化类算法在理论和应用两方面发展迅速、效果显著，并逐渐走向了融合，形成了一种新颖的模拟进化的计算理论，统称为进化计算(Evolutionary Computation ，EC)，进化计算的具体实现方法与形式称为进化算法(Evolutionary Algorithm ，EA)。进化算法是一种受生物进化论和遗传学等理论启发而形成的求解优化问题的随机算法，虽然出现了多个具有代表性的重要分支，但它们各自代表了进化计算的不同侧面，各具特点。
1.2.1.进化算法的一般框架
下面给出求解优化问题(1.1)的进化算法的一般框架。首先将待优化的目标函数在保持整体极值点不变的前提下变换为适应值函数(fittness-value function) R s →Φ:。用A 表示包含附加的搜索状态信息的适当表示空间，通常A 是需要自适应调整的策略参数。在进化算法EA 中，搜索群
体中的任一个体均是笛卡尔集S ×A 中的一个元素，其中),(a X A a S X ∈∈,。个体的
适应值由优化变量),(a X X 的适应值给出。μ≥1表示父代群体的大小，λ≥1表示子代群体的大小。将进化过程中第t 代的群体记为
)(X Φ)},(,,),(,),{()(,,2,2,1,1,u t u t t t t t a X a X a X t P …= (1.5)
则用EA 求解问题(1.1)的过程如下： Begin
确定编码的形式并生成搜索空间，选择遗传算子的类型和所有控制参数值； 设置代数t=0；
随机生成初始化群体
)},(,,),(,),{()0(,0,02,02,01,01,0n n a X a X a X P …=
计算每个个体的适应值； )(,0i X Φwhile (终止条件不满足) do
t=t+1；
对P(t-1)进行重组操作生成群体P’(t)；
对P’(t)进行变异操作生成群体P’’(t)，并计算每个个体的适应值)(,i t X Φ； 对(Q ∪P’’(t))进行选择操作生成群体
)},(,,),(,),{()(,,2,2,1,1,u t u t t t t t a X a X a X t P …=（其中Q 表示P(t-1)的某个子集）；
END while
END Begin
上述进化算法的一般框架基本上包括了所有标准的进化类算法，但仍有一些EA 的变形或扩展无法包含在内，如稳定态(steady-state)EA 等。下面我们分别就进化计算的几个重要分支进行简单的介绍。
1.2.2.遗传算法(Genetic Algorithm ，GA)
遗传算法最早是由美国Michigan 大学的J.Holland 博士提出的。1975年，他出版了其开创性的著作“Adaptive in Natural and Artificial Systems ”[Holland 1975]，标志着遗传算法的正式诞生。
遗传算法的操作对象是一组二进制串，即种群(Population)。每一个二进制串称为染色体(Chromosome)或个体(Individual)，每个染色体或个体都对应于问题的一个解。从初始种群出发，采用基于适应值比例的选择策略在当前种群中选择个体，并使用交叉(Crossover)和变异(Mutation)来产生下一代种群，如此一代一代进化下去，直至满足期望的终止条件。
遗传算法可以形式化描述为：
GA ＝(P(0)，N ，l ，S ，g ，p ，f ，t) (1.6)
其中：
P(0)＝(a 1(0)，a 2(0)，…， a N (0))∈I N ，表示初始种群；
I ＝B l ＝{0，1}l 表示长度为l 的二进制串全体，称为位串空间； N 表示种群中含有的个体数目，即群体规模； l 表示二进制串的长度； S ：I N →I N 表示选择策略；
g表示遗传算子，通常它包括复制算子O r：I→I，交叉算子O c：I×I→I×I和变异算子O m：I→I p表示遗传算法的操作概率，包括复制概率p r、交叉概率p c和变异概率p m
f：I→R+是适应值函数
t：I N→｛0，1｝是终止条件。
有关遗传算法的研究成果已相当丰富，包括编码方案、遗传算子的设计以及操作概率的自适应性控制策略等等，各种各样的改进算法层出不穷，其应用范围几乎可以涉及优化问题的所有领域，有关遗传算法方面的专著在国内外也出现了很多。
1.2.3.进化策略(Evolutionary Strategies，ES)
进化策略是由德国柏林工业大学的I.Rechenberg和H.-P.Schwefel等在20世纪60年代初提出的。早期的演化策略，其种群中只包含一个个体且只使用变异操作。具体在每一操作代中，变异后的个体与其父代个体进行比较，从中择优选取作为新一代个体，这就是所谓的(1＋1)策略。它所使用的变异算子主要是基于正态分布的变异操作[Schwefel 1981]。
由于(1＋1)策略难以收敛到最优解，且搜索效率相对较低。其改进的方法就是增加种群内个体的数量，即(μ＋1)进化策略。此时种群内含有μ个个体，随机抽取一个个体进行变异，然后取代群体中最差的个体。为了进一步提高搜索效率，后来又提出了(μ＋λ)进化策略和(μ，λ)进化策略。(μ＋λ)进化策略是根据种群内的μ个个体采用变异和重组产生λ个个体，然后将这μ＋λ个个体进行比较选择μ个最优者；而(μ，λ)进化策略则是在新产生的λ(≥μ)个个体中比较选择μ个最优者。
进化策略与遗传算法相比，其主要不同之处在于：遗传算法是将原问题的解空间映射到位串空间上，然后再进行遗传操作，它强调的是个体基因结构的变化对其适应度的影响，而进化策略则是直接在解空间上进行遗传操作，它强调的是父代到子代行为的自适应性和多样性。
1.2.4.进化规划(Evolutionary Programming，EP)
进化规划方法最初是由美国科学家Lawrence J.Fogel等人在20世纪60年代提出的[Fogel 1966]。它在求解连续参数优化问题时与ES的区别很小。进化规划仅使用变异与选择算子，而绝对不使用任何重组算子。其变异算子与进化策略的变异相类似，也是对父代个体采用基于正态分布的变异操作进行变异，生成相同数量的子代个体。即μ个父代个体总共产生μ个子代个体。EP 采用一种随机－竞争选择方法，从父代和子代的并集中选择出μ个个体构成下一代群体。其选择过程如下：对于由父代个体和子代个体组成的大小为2μ的临时群体中的每一个个体，从其它2μ－1个个体中随机等概率地选取出q个个体与其进行比较。在每次比较中，若该个体的适应值不小于与之比较的个体的适应值，则称该个体获得一次胜利。从2μ个个体中选择出获胜次数最多的μ个个体作为下一代群体。
1.2.5.遗传程序设计(Genetic Programming，GP)
遗传程序设计是由Stanford大学的J.R.Koza在20世纪90年代初提出的，并于1992年出版了专著“Genetic Programming”[Koza 1992]。GP采用遗传算法的基本思想，使用一种更为灵活的分层结构来表示解空间。这种分层结构的叶结点是问题的原始变量，中间结点则是组合这些原始变量的函数。它们很类似于LISP语言中的S－表达式。这样的每一个分层结构对应问题的一个解，也可以理解为求解该问题的一个计算机程序。遗传程序设计是使用一些遗传操作动态地改变这些结构以获得解决该问题的可行的计算机程序。
遗传程序设计所采用的主要遗传操作是选择与交叉算子，GP的选择操作是自然选择，适者生存的基本动因，其操作对象是父代S－表达式，产生的结果是子代S－表达式，选择操作方法与遗
传算法相同。
GP 交叉操作的对象是两个父代S －表达式，交叉操作的结果产生两个子代S －表达式，其中每一个体(S －表达式)都含有来自两个父代个体的部分基因。对每一个父代个体，采用均匀分布随机选择交叉点，然后相互交换交叉点以下的子树。由于GP 染色体结构的形状和大小不是固定的，因而参与交叉的两个父代个体的大小一般是不相同的。
为了动态修改染色体的结构，GP 提供了变异操作、排列操作、编辑操作、封装操作、＋中抽－等辅助算子。
1.3. 群体智能算法(Swarm Intelligence Algorithm)
群体智能算法的研究开始于上世纪90年代初，其基本思想是模拟自然界生物的群体形为来构造随机优化算法。典型的方法有M.Dorigo 提出的蚁群算法和J.Kennedy 与R.Eberthart 提出的微粒群算法。
1.3.1. 蚁群算法(Ant Colony Algorithm)
蚁群算法也称蚂蚁算法，是在20世纪90年代初由意大利学者M.Dorigo 提出的，它是根据蚂蚁觅食原理而设计的一种群体智能算法。下面首先简单介绍一下蚂蚁觅食的方法，然后以TSP 问题为例给出求解其最短回路蚁群算法。
据研究，当蚂蚁找到食物并将它搬回来时，就会在它经过的路上留下一种“外激素”，其它蚂蚁闻到这种激素的“味道”，就沿该路线去觅食，而且还会沿着最短的路径奔向食物。下面以n 个城市的TSP 问题为例，简要地介绍一下人们根据蚂蚁觅食原理设计出的求解最短回路的蚁群算法。
设共有m 个蚂蚁，第i 城市在t 时刻有蚂蚁a i (t)个，在t 时刻在第i ，j 两城市间的道路上留下的外激素量为b ij (t)。假设每个蚂蚁在未完成一个回路时，不重复已走过的城市，则第k 个蚂蚁从城市i 到城市j 的概率为：
∑=
)
()
(t b t b p ij ij k ij
(1.7)
其中外激素量b ij (t)可定义为，c >0；或定义为：
ct
e
t b ?=)()(1t a L e d k
ij m
k k
ij ∑
== (1.8) 其中 是第k 只蚂蚁求得的回路长度。
k L ij ij ij d t b c t b +?=+)()1( (1.9)
??
?=Else j i k t t a k
ij 0
),(1)(只蚂蚁经过边轮第第 (1.10)
这样，每只蚂蚁经过n 次迁移后就得到一条回路，其长度为。再利用(1.7)~(1.10)重新计算各条路径的外激素浓度，进行下一步搜索。
k L 蚁群算法自提出以来，已成功应用于许多领域，如TSP 、重建通讯路由、连续系统优化等许
多领域。
1.3.
2.微粒群算法(Particle Swarm Optimization, PSO)
微粒群算法是在1995年由美国社会心理学家James Kennedy和电气工程师Russell Eberhart 共同提出的[Kennedy 1995]，其基本思想是受他们早期对鸟类群体行为研究结果的启发，并利用了生物学家Frank Heppner的生物群体模型。
有关微粒群算法的详细介绍是本书后续各章节的内容，在这里就不作阐述，下一节将对微粒群算法的发展历史及研究方向作一简单介绍。
1.4. 微粒群算法的发展
自微粒群算法提出以来，由于它的计算快速性和算法本身的易实现，引起了国际上相关领域众多学者的关注和研究，其研究大致可以分为：算法的改进、算法的分析以及算法的应用。下面就这三个方面的研究情况作一简单的介绍。
1.4.1．微粒群算法综述
在微粒群算法的改进方面，首先是由Kennedy和Eberhart在1997年提出的二进制PSO算法[Kenney 1997]，为PSO算法与遗传算法的性能比较提供了一个有用的方式，该方法可用于神经网络的结构优化，其具体方法参见第三章。
其次，为了提高算法的收敛性能，Shi和Eberhart于1998年对PSO算法的速度项引入了惯性权重w[Shi 1998]，并提出在进化过程中动态调整惯性权重以平衡收敛的全局性和收敛速度，该进化方程已被相关学者称之为标准PSO算法。Clerc于1999年在进化方程中引入收缩因子以保证算法的收敛性[Clerc 1999]，同时使得速度的限制放松。有关学者已通过代数方法对此方法进行了详细的算法分析，并给出了参数选择的指导性建议。
Angeline于1999年借鉴进化计算中的选择概念，将其引入PSO算法中。通过比较各个微粒的适应值淘汰掉差的微粒，而将具有较高适应值的微粒进行复制以产生等数额的微粒来提高算法的收敛性。而Lovbjerg等人进一步将进化计算机制应用于PSO算法，如复制、交叉等，给出了算法交叉的具体形式，并通过典型测试函数的仿真实验说明了算法的有效性。
为了提高PSO算法收敛的全局性，保证微粒的多样性是其关键。为了保证进化过程中群体中微粒的多样性，Suganthan在标准PSO算法中引入了空间邻域的概念，将处于同一个空间领域的微粒构成一个子微粒群分别进行进化，并随着进化动态地改变选择阈值以保证群体的多样性；Kennedy引入邻域拓扑的概念来调整邻域的动态选择，同时引入社会信念将空间邻域与邻域拓扑中的环拓扑相结合以增加邻域间的信息交流，提高群体的多样性。Lovbjerg等人于2001年将遗传算法中的子群体概念引入PSO算法中，同时引入繁殖算子以进行子群体的信息交流。
在PSO算法的行为分析和收敛性分析方面进行了大量的研究工作。首先是采用代数方法对几种典型的PSO算法的运行轨迹进行了分析，给出了保证收敛性的参数选择范围。在收敛性方面，Frans van den Bergh引用Solis和Wets关于随机性算法的收敛准则，证明了标准PSO算法不能收敛于全局最优解，甚至于局部最优解。证明了保证收敛的PSO算法能够收敛于局部最优解，而不能保证收敛于全局最优解。
在PSO算法的应用方面，PSO算法最早应用于人工神经网络的训练方法，Kennedy和Eberhart 成功地将PSO算法应用于分类XOR问题的神经网络训练。随后，PSO算法在函数优化、约束优化、极大极小问题、多目标优化等问题中均得到了成功的应用。特别是在电力系统、集成电路设计、系统辨识、状态估计等问题中的应用均有报导。有兴趣的读者可参考相关文献[Yoshida 1999, Fukuyama 2001]。
1.4.
2.微粒群算法的研究方向
根据作者对国内外关于微粒群算法研究的相关文献以及进化算法领域的发展趋势的分析，认为目前主要有以下几个研究方向：
1) 微粒群算法的改进。
标准微粒群算法主要适用于连续空间函数的优化问题，如何将PSO算法应用于离散空间优化问题，特别是一类非数值优化问题，将是微粒群算法的主要研究方向。另外充分吸引其它进化类算法的优势，以改进PSO算法存在的不足也是值得研究的问题。
2) 微粒群算法的理论分析
到目前为止，PSO算法的分析方法还很不成熟和系统，存在许多不完善和未涉及到的问题。如何利用有效的数学工具对PSO算法的运行行为、收敛性及计算复杂性进行分析是目前的研究热点之一。
3) 微粒群算法的生物学基础
如何根据群体进化行为完善PSO算法，同时分析群体智能行为，如何将其引入PSO算法中，以充分借鉴生物群体进化规律和进化的智能性也是目前的研究方向之一。
4) 微粒群算法与其它类进化算法的比较研究
5) 微粒群算法的应用
算法研究的目的是应用，如何将PSO算法应用于更多领域，同时研究应用中存在的问题也是值得关注的热点。
由于PSO算法提出的时间并不长，存在的问题很多，本书的目的在于对目前的研究状况作一比较系统的介绍，肯定存在挂一漏百的现象。同时，作者们从事这一研究也仅仅两年多时间，掌握的资料有限，难免有许多不当之处，敬请读者提出宝贵意见。
第二章基本微粒群算法
2.1引言
自然界中各种生物体均具有一定的群体行为，而人工生命的主要研究领域之一就是探索自然界生物的群体行为从而在计算机上构建其群体模型。通常，群体行为可以由几条简单的规则进行建模，如鱼群、鸟群等。虽然每一个个体具有非常简单的行为规则，但群体的行为却非常复杂。Reynolds将这种类型的个体称为boid，并使用计算机图形动画对复杂的群体行为进行仿真。他在仿真中采用了下列三条简单规则：
（1）飞离最近的个体，以避免碰撞
（2）飞向目标
（3）飞向群体的中心
群体内每一个体的行为可采用上述规则进行描述，这是微粒群算法的基本概念之一。
Boyd和Richerson在研究人类的决策过程时，提出了个体学习和文化传递的概念。根据他们的研究结果，人们在决策过程中使用两类重要的信息。一是自身的经验，二是其他人的经验。也就是说，人们根据自身的经验和他人的经验进行自己的决策。这是微粒群算法的另一基本概念。
微粒群算法最早是在1995年由美国社会心理学家James Kennedy和电气工程师Russell Eberhart 共同提出的，其基本思想是受他们早期对许多鸟类的群体行为进行建模与仿真研究结果的启发。而他们的模型及仿真算法主要利用了生物学家Frank Heppner的模型。
Frank Heppner的鸟类模型在反映群体行为方面与其它类模型有许多相同之处，所不同之处在于：鸟类被吸引飞向栖息地。在仿真中，一开始每一只鸟均无特定目标进行飞行，直到有一只鸟飞到栖息地，当设置期望栖息比期望留在鸟群中具有较大的适应值时，每一只鸟都将离开群体而飞向栖息地，随后就自然地形成了鸟群，。
由于鸟类使用简单的规则确定自己的飞行方向与飞行速度（实质上，每一只鸟都试图停在鸟群中而又不相互碰撞），当一只鸟飞离鸟群而飞向栖息地时，将导致它周围的其它鸟也飞向栖息地。这些鸟一旦发现栖息地，将降落在此，驱使更多的鸟落在栖息地，直到整个鸟群都落在栖息地。
由于James Kennedy和 Russell Eberhart所具有的专业背景，就能很容易理解他们为什么会对Hepper的鸟类模型感兴趣。鸟类寻找栖息地与对一个特定问题寻找解很类似，已经找到栖息地的鸟引导它周围的鸟飞向栖息地的方式，增加了整个鸟群都找到栖息地的可能性，也符合信念的社会认知观点。
Eberhart和Kennedy对Heppner的模型进行了修正，以使微粒能够飞向解空间并在最好解处降落。其关键在于如何保证微粒降落在最好解处而不降落在其它解处，这就是信念的社会性及智能性所在。
信念具有社会性的实质在于个体向它周围的成功者学习。个体与周围的其它同类比较，并模仿其优秀者的行为。将这种思想用算法实现将导致一种新的最优化算法。
要解决上述问题，关键在于在探索（寻找一个好解）和开发（利用一个好解）之间寻找一个好的平衡。太小的探索导致算法收敛于早期所遇到的好解处，而太小的开发会使算法不收敛。
另一方面，需要在个性与社会性之间寻求平衡，也就是说，既希望个体具有个性化，像鸟类模型中的鸟不互相碰撞，又希望其知道其它个体已经找到的好解并向它们学习，即社会性。
Eberhart和Kennedy较好地解决了上述问题，提出了微粒群优化算法(Particle Swarm Optimization, PSO)[Kennedy 1995]。
2.2基本微粒群算法
Kennedy和Eberhart在1995年的IEEE国际神经网络学术会议上正式发表了题为“Particle
Swarm Optimization ”的文章，标志着微粒群算法的诞生。
2.2.1算法原理
微粒群算法与其它进化类算法相类似，也采用“群体”与“进化”的概念，同样也是依据个体（微粒）的适应值大小进行操作。所不同的是，微粒群算法不像其它进化算法那样对于个体使用进化算子，而是将每个个体看作是在n 维搜索空间中的一个没有重量和体积的微粒，并在搜索空间中以一定的速度飞行。该飞行速度由个体的飞行经验和群体的飞行经验进行动态调整。
设
),......,,(21in i i i x x x X =为微粒i 的当前位置； ),......,,(21in i i i v v v V =为微粒i 的当前飞行速度；
),......,,(21in i i i p p p P =为微粒i 所经历的最好位置，也就是微粒i 所经历过的具有最好适应
值的位置，称为个体最好位置。对于最小化问题，目标函数值越小，对应的适应值越好。
为了讨论方便，设f(X)为最小化的目标函数，则微粒i 的当前最好位置由下式确定：
??
?
<++≥+=+))
(())1(()1())(()1(()()1(t P f t X f t X t P f t x f t P t P i i i i i i i 若若 (2.1) 设群体中的微粒数为s ，群体中所有微粒所经历过的最好位置为，称为全局最好位置。则
)(t P g ))}(()),......,(()),((min{))((|)}(),......,(),({)(1010t P f t P f t P f t P f t P t P t P t P s g s g =∈ (2.2)
有了以上定义，基本微粒群算法的进化方程可描述为：
))()()(())()()(()()1(2211t x t p t r c t x t p t r c t v t v ij gj j ij ij j ij ij ?+?+=+ (2.3)
)1()()1(++=+t v t x t x ij ij ij (2.4)
其中：下标“j ”表示微粒的第j 维，“i ”表示微粒i ，t 表示第t 代，c 1、c 2为加速常数，通常在0~2间取值，r 1 ~U(0,1)，r 2 ~U(0,1)为两个相互独立的随机函数。
从上述微粒进化方程可以看出，c 1调节微粒飞向自身最好位置方向的步长，c 2调节微粒向全局最好位置飞行的步长。为了减少在进化过程中，微粒离开搜索空间的可能性，v ij 通常限定于一定范围内，即。如果问题的搜索空间限定在[-x ],[max max v v v ij ?∈max ，x max ]内，则可设定v max =k ·x max ，0.1≤k ≤1.0。
基本微粒群算法的初始化过程为：
1） 设定群体规模N
2） 对任意i ，j ，在[-x m a x ，x m a x ]内服从均匀分布产生x i j ； 3） 对任意i ，j ，在[-v m a x ，v m a x ]内服从均匀分布产生v i j ； 4） 对任意i ，设y i =x i 。
2.2.2算法流程
基本微粒群算法的流程如下：
step1，依照初始化过程，对微粒群的随机位置和速度进行初始设定； step2，计算每个微粒的适应值；
step3，对于每个微粒，将其适应值与所经历过的最好位置P i 的适应值进行比较，若较好，则将其作为当前的最好位置；
step4，对每个微粒，将其适应值与全局所经历的最好位置的适应值进行比较，若较好，则将其作为当前的全局最好位置；
g P step5，根据方程（2-3）(2-4)对微粒的速度和位置进行进化；
step6，如未达到结束条件通常为足够好的适应值或达到一个预设最大代数（Gmax ），则返回step2。
基本微粒群算法的源程序具体见附录1。
2.3基本微粒群算法的社会行为分析
在(2.3)式所描述的速度进化方程中，其第一部分为微粒先前的速度；其第二部分为“认知”部分，因为它仅考虑了微粒自身的经验，表示微粒本身的思考。如果基本微粒群算法的速度进化方程仅包含认知部分，即：
))()()(()()1(11t x t p t r c t v t v ij ij j ij ij ?+=+ (2.5)
则其性能变差。主要原因是不同的微粒间缺乏信息交流，即没有社会信息共享，微粒间没有交互，
使得一个规模为N 的群体等价于运行了N 个单个微粒，因而得到最优解的概率非常小。 （2.3）式的第三部分为“社会”部分，表示微粒间的社会信息共享。若速度进化方程中仅包含社会部分，即：
))()()(()()1(22t x t p t r c t v t v ij gj j ij ij ?+=+ (2.6)
则微粒没有认识能力，也就是“只有社会(social-only)”的模型。这样，微粒在相互作用下，有能力到达新的搜索空间，虽然它的收敛速度比基本微粒群算法更快，但对于复杂问题，则容易陷入局部最优点。
Kennedy 以XOR 问题的神经网络训练为例进行了仿真实验，证明了上述结论。
总之，基本微粒群算法的速度进化方程由认识和社会两部分组成。虽然目前的一些研究表明，对一些问题，模型的社会部分显得比认识部分更重要，但两部分的相对重要性还没有从理论上给出结论。
2.3.1与其它进化算法的比较
很显然，微粒群算法与其它进化算法有许多共同之处。首先，微粒群算法和其它所有进化类算法相同，均使用“群体”概念，用于表示一组解空间中的个体集合。如果将微粒所经历的最好位置y i 看作是群体的组成部分，则微粒群的每一步进化呈现出弱化形式的“选择”机制。在（μ+λ）进化策略算法中，子代与父代竞争，若子代具有更好的适应值，则用来替换父代，而PSO 算法的进化方程（2.1）式具有与此相类似的机制，其唯一的差别在于，只有当微粒的当前位置与所经历的最好位置y i 相比具有更好的适应值时，其微粒所经历的最好位置（父代）才会唯一地被该微粒的当前位置（子代）所替换。总之，PSO 算法隐喻着一定形式的“选择”机制。
其次，（2.3）式所描述的速度进化方程与实数编码遗传算法的算术交叉算子相类似，通常，算术交叉算子由两个父代个体的线性组合产生两个子代个体，而在PSO 算法的速度进化方程中，假如先不考虑v i j (t )项，就可以将该方程理解为由两个父代个体产生一个子代个体的算术交叉运算。从另一个角度，在不考虑v i j (t )项的情况下，速度进化方程也可以看作是一个变异算子，其变异的强度（大小）取决于两个父代微粒间的距离，即代表个体最好位置和全局最好位置的两个微粒的距离。至于v i j (t )项，也可以理解为一种变异的形式，其变异的大小与微粒在前代进化中的位
置相关。
通常在进化类算法的分析中，人们习惯于将每一步进化迭代理解为用新个体（即子代）代替旧个体（即父代）的过程。这里，如果我们将PSO 算法的进化迭代理解为一个自适应过程，则微粒的位置x i 就不是被新的微粒所代替，而是根据速度向量v i 进行自适应变化。这样，PSO 算法与其它进化类算法的最大不同点在于：PSO 算法在进化过程中同时保留和利用位置与速度（即位置的变化程度）信息，而其它进化类算法仅保留和利用位置的信息。
另外，如果将（2.4）看作一个变异算子，则PSO 算法与进化规划很相似。所不同之处在于，在每一代，PSO 算法中的每个微粒只朝一些根据群体的经验认为是好的方向飞行，而在进化规划中可通过一个随机函数变异到任何方向。也就是说，PSO 算法执行一种有“意识（Conscious ）”的变异。从理论上讲，进化规划具有更多的机会在优化点附近开发，而PSO 则有更多的机会更快地飞到更好解的区域，如果“意识”能提供有用的信息。
从以上分析可以看出，基本PSO 算法也呈现出一些其它进化类算法所不具有的特性，特别是，PSO 算法同时将微粒的位置与速度模型化，给出一组显式的进化方程，是其不同于其它进化类算法的最显著之处，也是该算法所呈现出许多优良特性的关键点。
2.3.2两种基本进化模型
在基本PSO 算法中,根据直接相互作用的微粒群定义可构造PSO 算法的两种不同版本,也就是说，可以通过定义全局最好微粒（位置）或局部最好微粒（位置）构造具有不同社会行为的PSO 算法。
1. Gbest 模型（全局最好模型）
Gbest 模型以牺牲算法的鲁棒性为代价提高算法的收敛速度，基本PSO 算法就是该模型的具体实现。在该模型中，整个算法以该微粒为吸引子，将所有微粒拉向它，使所有微粒将最终收敛于该位置。这样，如果在进化过程中，该最好解得不到有效地更新，则微粒群将出现类似于遗传算法中的早熟现象。为了讨论方便，将PSO 的进化方程重新表述如下：
))}(()),......,(()),((min{))((|)}(),......,(),({)(1010t P f t P f t P f t P f t P t P t P t P s g s g =∈ (2.7)
)]()()[()]()()[()()1(2211t x t p t r c t x t p t r c t v t v ij gj j ij ij j ij ij ?+?+=+ (2.8)
其中，称为全局最好位置，对应于称之为全局最好微粒所处的位置。
)(t P g 2.Lbest 模型（局部最好模型）
为了防止Gbest 模型可能出现的早熟现象，Lbest 模型采用多吸引子代替Gbest 模型中的单一吸引子。首先将整个微粒群分解为若干个子群，在每一子群中保留其局部最好微粒，称之为局部最好位置或邻域最好位置。假设第i 个子群处于长度为l 的领域内，则Lbest 模型的进化方程可描述为：
)(t P i )}(),(),......,(),(),(),......,(),({1111t P t P t P t P t P t P t P N l i l i i i i l i l i i +?++?+??= (2.9)
i i i i N a a f t P f N t P ∈?=+∈+)},(min ))1((|{)1( (2.10)
)]()()[()]()()[()()1(2211t x t P t r c t x t p t r c t v t v ij gj j ij ij j ij ij ?+?+=+ (2.11)
注意：子群N i 中的微粒与其在搜索空间域内所处的位置无关，仅依赖微粒的索引数或者微粒的编码。这样一方面避免了微粒间的聚类分析，节省了计算时间，另一方面能够加快更好解信息在整个群体间的扩散。
很容易看出，Gbest 模型实际上是Lbest 模型在l=s 时的特殊情况。实验证明：l=1时的Lbest 模型，其收敛速度低于Gbest 模型，而1 2.4带惯性权重的PSO 算法 为了改善基本PSO 算法的收敛性能，Y ．Shi 与R ．C ．Eberhart 在1998年的IEEE 国际进化计算学术会议上发表了题为“A Modified Particle Swarm Optimizer ”的论文，首次在速度进化方程中引入惯性权重，即： )]()()[()]()()[()()1(2211t x t p t r c t x t p t r c t wv t v ij gj j ij ij j ij ij ?+?+=+ (2.12) 式中w 称为惯性权重，因此，基本PSO 算法是惯性权重w =1的特殊情况。惯性权重w 使微粒保持运动惯性，使其有扩展搜索空间的趋势，有能力探索新的区域。 引入惯性权重w 可清除基本PSO 算法对v m a x 的需要，因为w 本身具有维护全局和局部搜索能力的平衡的作用。这样，当v m a x 增加时，可通过减少w 来达到平衡搜索。而w 的减少可使得所需的迭代次数变小。从这个意义上看，可以将v m a x ,d 固定为每维变量的变化范围，只对w 进行调节。 对全局搜索，通常的好方法是在前期有较高的探索能力以得到合适的种子，而在后期有较高的开发能力以加快收敛速度。为此，可将w 设定为随着进化而线性减少，例如由0.9到0.4等等。Y ．Shi 和R ．C ．Eberhart 的仿真实验结果也表明w 线性减少取得了较好的实验结果。有关这一方面的详细讨论将在第六章进行。 目前，有关PSO 算法的研究大多以带惯性权重的PSO 算法为基础进行扩展和修正。为此，在大多文献中将带惯性权重的PSO 算法称之为PSO 算法的标准版本，或简称标准PSO 算法；而将基本PSO 算法称为PSO 的初始版本。 第三章 改进的微粒群算法 3.1对基本微粒群算法进化方程的改进 3.1.1基本微粒群算法分析 为了方便起见，我们将基本微粒群算法的形式表述如下： ))(())(()()1(2211t X P r c t X P r c t V t V i g i i i i ?+?+=+ (3.1) )1()()1(++=+t V t X t X i i i (3.2) 其中表示第i 个微粒所经历过的最好位置，表示所有微粒所经历过的最好位置，c i P g P 1、c 2为常数，为均匀分布的随机数。 ]1,0[,21∈r r 为了更好地分析基本微粒群算法，我们将（3.1）式改写为： 321)1(G G G t V i ++=+ (3.3) 其中 )(1t V G i = ))((112t X P r c G i i ?= ))((223t X P r c G i g ?= 从（3.3）可以看出，其右边可以分成三部分：第一部分为原先的速度项；第二、三部分分别表示对原先速度的修正。其中，第二部分考虑该微粒历史最好位置对当前位置的影响，而第三部分考虑微粒群体历史最好位置对当前位置的影响。为了考虑、、对微粒群搜索能力的影响，我们首先将（3.3）修改为： 1G 2G 3G 1)1(G t V i =+ (3.4) （3.4）式表示微粒速度的进化方程仅保留第一部分，此时，微粒将会保持速度不变，沿该方向一直“飞”下去直至到达边界。因而，在这种情形下，微粒很难搜索到较优解。 接着我们将（3.3）修改为： 32)1(G G t V i +=+ (3.5) （3.5）式表示微粒速度的进化方程保留第二、三部分，由于微粒的速度将取决于其历史最优位置与群体的历史最优位置，从而导致速度的无记忆性。假设在开始时，微粒j 处于整体的最优位置，则按照（3.5）式它将停止进化直到群体发现更好的位置。此时，对于其它微粒而言， 。这表明，整个微粒群的搜索区域将会收缩到当前最优位置附近，即如果没有第 一项，则整个进化方程具有很强的局部搜索能力。 g i t P t X =∞ →)(lim 对于基本微粒群算法而言，其具有全局搜索能力，这表明，微粒速度的进化方程的第一项是 用于保证算法具有一定的全局搜索能力。通过以上的分析，我们发现，、使得微粒群算法具有局部收敛能力，而则是用于保证算法的全局收敛性能。 2G 3G 1G 3.1.2带有惯性因子的改进微粒群算法 1、一般的惯性因子设计。 对于不同的问题，如何确定局部搜索能力与全局搜索能力的比例关系，对于其求解过程非常重要。甚至对于同一个问题而言，进化过程中也要求不同的比例。为此，Yuhui Shi[Yuhui Shi1998]提出了带有惯性权重的改进微粒群算法。其进化方程为： ))(())(()()1(2211t X P r c t X P r c t wV t V i g i i i i ?+?+=+ (3.6) )1()()1(++=+t V t X t X i i i (3.7) 当惯性权重1=w 时，式（3.6）与（3.1）相同，从而表明带惯性权重的微粒群算法是基本微粒群算法的扩展。文献[Yuhui Shi1998]建议的取值范围为，但实验结果表明当取 时，算法收敛速度更快，而当时，算法则较多地陷入局部极值。 w ]4.1,0[w ]2.1,8.0[2.1>w 惯性权重表明微粒原先的速度能在多大程度上得到保留。假设微粒j 的初始速度非零，当 且时，则微粒将会加速直至；当w 021==c c 0>w max v 0 惯性权重类似模拟退火中的温度，较大的有较好的全局收敛能力，而较小的则有较强的局部收敛能力。因此，随着迭代次数的增加，惯性权重应不断减少，从而使得微粒群算法在初期具有较强的全局收敛能力，而晚期具有较强的局部收敛能力。在[Yuhui Shi1999]中，惯性权重满足 w w w w w 5.09.0)(×? =MaxNumber t t w （3.8） 其中，MaxNumber 为最大截止代数，这样，将惯性权重看作迭代次数的函数，可从0.9到0.4 线性减少，从对四个测试函数的测试结果来看，效果很好。 w 2、基于模糊系统的惯性因子的动态调整。 对于惯性权重来说，对于不同的问题，其每一代所需要的比例关系并不相同，这样，线性递减关系只对某些问题有效，对于其它问题而言显然不是最佳的。为此，[Yuhui Shi2001]提出了基于模糊系统的惯性权重的动态调整。该模糊系统需要两个输入参数：当前种群最优性能指标（the current best performance evaluation, CBPE ）和当前的惯性权重，输出为惯性权重的调节量。具体操作时，首先假设所优化的问题为求解最小值的问题，其次对性能指标规范化操作，即 w min max min CBPE CBPE CBPE CBPE NCBPE ??= （3.9） 其中，全局最小值（或估计值）为，所得到的某个上界为。三个变量（两个输入变量，一个输出变量）分为低、中、高三种状态。对于每种状态，其隶属度函数分别称为： min CBPE max CBPE triangle left f _，，，具体定义为： triangle f triangle right f _????? ??>≤≤??<=) (,0)(,)(,12211221_x x if x x x if x x x x x x if f triangle left (3.10) ? ????????>≤≤+??+≤≤??<=) (,0) 2(,2)2(,2)(,022 211222111211x x if x x x x if x x x x x x x x if x x x x x x if f triangle (3.11) ????? ??>≤≤??<=) (,1)(,)(,02211211_x x if x x x if x x x x x x if f triangle right (3.12) 其中，、为两个参数用以确定函数的形状和位置。 1x 2x 整个模糊系统可以如下表示： 9 2 1 NCBPE 3 0 1 LeftTriangle 0 0.06 Triangle 0.05 0.4 RightTriangle 0.3 1 Weight 3 0.2 1.1 LeftTriangle 0.2 0.6 Triangle 0.4 0.9 RightTriangle 0.6 1.1 W_change 3 -0.12 0.05 LeftTriangle –0.12 –0.02 Triangle –0.04 –0.04 RightTriangle 0.0 0.05 1 1 2 1 2 1 1 3 1 2 1 3 2 2 2 2 3 1 3 1 3 3 2 2 3 3 1 其中，第一行的“9”表示共有九条规则。第二行的“2 1”表示有两个输入变量和一个输出变量。第三行的“NCBPE 3 0 1”表示第一个输入变量是个NCBPE 变量（规范化操作），有三个模糊集，取值范围为。当使用隶属度函数时，参数，取0.0和0.06；使用隶属度函数 时，参数，取0.05和0.4；使用隶属度函数时，参数，取0.3和1.0。 这四行完整的定义了第一个输入变量。第二个输入变量为weight ，输出变量为w_change ，分别进行了定义。定义完之后，又给出了具体的九条模糊规则。在规则中“1”代表低状态，“2”表示中状态，“3”表示高状态。因此，第一条规则“1 1 2”就表示输入变量NCBPE 为低，weight 为低，输出变量w_change 为中的情形。 )1,0(triangle left f _1x 2x triangle f 1x 2x triangle right f _1x 2x 3.1.3 带有收缩因子的微粒群算法 在Clerc[M.Clerc1999,D.Corne1999]的研究中，提出了收缩因子的概念。该方法描述了一种选择，c w 1和 c 2 的值的方法，以确保算法收敛。通过正确地选择这些控制参数，就没有必要将v i,j 的值限制在[-v max,, v max ]之中。接下来首先讨论一个与带有收缩因子的微粒群算法相关的收敛模式特例。 一个与某个收敛模式相符合的改进了的速率方程式以以下形式提出： (),))()()(())()()(()()1(,,,22,,,11,,t x t p t r c t x t p t r c t v t v j i j g j j i j i j j i j i ?+?+=+χ (3.13) 这里， 4222 ???= χ (3.14) 且 4,21>+= c c 设，将05.221==c c 1.421=+=c c 带入（3.14），得出 χ=0.7298并带入方程式（3.13），同 时省略参数t ，结果为： ())(05.2)(05.27298.0)1(,,,2,,,1,,j i j g j j i j i j j i j i x p r x p r v t v ?×+?×+=+ (3.15) 因为20.5×0.7298=1.4962，所以这个方程式与在改进的PSO 速率更新方程式使用 和w =0.7298所得到的方程式是等价的。 4962.121==c c Eberhart 和Shi 将分别利用和收缩因子来控制微粒速度的两种算法性能作了比较，结果表明，后者比前者通常具有更好的收敛率。然而在有些测试函数的求解过程中，使用收缩因子的PSO 在给定的迭代次数内无法达到全局极值点。按照Eberhart 和Shi 的观点，这是由于微粒偏离所期望的搜索空间太远而造成的。为了降低这种影响，他们建议在使用收缩因子时首先对算法进行限定，比如设参数=，或者预先设置搜索空间的大小。这样几乎可以改进算法对所有测试函数的求解性能——不管是在收敛率方面还是在搜索能力方面。 max v max v max x 3.2 基于遗传思想改进PSO 3.2.1 利用选择的方法 在一般微粒群算法中，每个微粒的最优位置的确定相当于隐含的选择机制，因此，[Perter J.Angeline1998]引入了具有明显选择机制的改进微粒群算法，仿真结果表明算法对某些测试函数具有优越性。 改进算法所使用的选择算子为锦标赛选择算子（Tournament Selection Method ），将每个个体的适应度，基于其当前位置，与k 个其他个体进行比较，并记下最差的一个点。群体再用这个记录排序，最高的得分出现在群体的头部。 算法的流程为： 1) 从种群选择一个个体。将该个体的适应度与种群中的其他个体的适应度逐一进行比较，如果当前个体的适应度优于某个个体的适应度，则每次授予该个体一分。对每一个个体重复这一过程。 2) 根据前一步所计算的分数对种群中的个体进行由大到小的排列。 3) 选择种群中顶部的一半个体，并对他们进行复制，取代种群底部的一半个体，在此过程 中最佳个体的适应度并未改变。 为了测试算法的性能，[Perter J.Angeline1998]使用了四个测试函数，它们分别是 ∑== n j j x x f 120)( ∑=+?+?= n j j j j x x x x f 12 21 1))1()(100()( ∑=+?= n j j j x x x f 1 2 2)10)2cos(10()(π 1)cos(40001)(1 12 3+?=∏∑==n j j n j j j x x x f 在仿真试验中，初始种群使用了两种不同的选择方式[D.Gehlhaar 1996]，用以比较两种算法 的性能。一种使用典型的对称区域，具体的数据见表 3.1。另一种使用不对称的定义区域，见表3.2。 表3.1、对称区域的范围 表3.2、不对称区域的范围Function Initialization Range 0f n )15,15(? 1f n )15,15(? 2f n )15,15(? 3f n )600,600(? Function Initialization Range 0f n )15,5.7( 1f n )15,5.7( 2f n )15,5.7( 3f n )600,300( 图3.1、定义域为对称区域在 的性能比较 图3.2、定义域为对称区域在的性能比较 0f 1f 图3.3、定义域为对称区域在 的性能比较 图3.4、定义域为对称区域在的性能比较 2f 3f 表3.3、定义域为对称区域仿真结果 函数 维数 最大截止代数 方差 标准差 F0 10 500 0.7022 0.3823 F0 20 750 4.8467 2.2405 F0 30 1000 11.949 5.2181 F1 10 500 75.482 38.049 F1 20 750 640.16 253.65 F1 30 1000 1993.68 711.04 F2 10 500 11.214 10.965 F2 20 750 27.730 25.747 F2 30 1000 47.275 42.844 F3 10 500 0.4115 11.985 F3 20 750 0.3060 1.5058 F3 30 1000 0.4527 2.5145 图3.1-3.4表示的是初始种群为对称区域的实验结果。从图中可以看出，对于函数20f f ?而言，虽然开始基本微粒群算法的速度较快，但在25代以内，带有选择的改进微粒群算法效率提高很快，并超过基本微粒群算法的结果。但对于函数而言，性能并没有提高很多。 3f 对于初始种群为不对称区域，其实验结果可参考图3.5-3.8，其结果与图3.1-3.4比较相似，这 里就不再赘述。 表3.4、定义域为不对称区域仿真结果 函数 维数 最大截止代数 方差 标准差 F0 10 500 0.7120 0.4016 F0 20 750 4.8669 2.2714 F0 30 1000 11.674 5.1870 F1 10 500 76.186 39.506 F1 20 750 674.64 269.22 F1 30 1000 1988.3 669.98 F2 10 500 11.305 10.972 F2 20 750 27.739 26.101 F2 30 1000 47.897 42.950 F3 10 500 1.2666 60.433 F3 20 750 0.3463 39.267 F3 30 1000 0.4425 50.704 图3.5、定义域为不对称区域在 的性能比较 图3.6、定义域为不对称区域在的性能比较 0f 1f 图3.7、定义域为不对称区域在 的性能比较 图3.8、定义域为不对称区域在的性能比较 2f 3f 3.2.2借鉴杂交的方法 Angeline[Angeling 1998]提出了杂交微粒群算法，微粒群中的微粒被赋予一个杂交概率，这个杂交概率是用户确定的，与微粒的适应值无关。在每次迭代中，依据杂交概率选取指定数量的微粒放入一个池中。池中的微粒随机地两两杂交，产生相同数目的子代，并用子代微粒取代父代微粒，以保持种群的微粒数目不变。 让a 和b 表示被选择的两个亲代个体的指针，那么杂交算法的计算公式表示如下： )()0.1()()1(11t X r t X r t X b a a ?+=+ (3.16) 目录 １绪论 (2) 1.1研究的背景和意义 (2) 1.2常用的参数整定法 (2) 1.3PID参数优化法 (3) １.４微粒群PID参数优化 (3) ２微粒群算法 (4) 2.1算法起源 (4) 2.2算法原理 (4) 2.3算法流程 (5) 2.4算法特点 (6) 2.5全局模型和局部模型 (7) 2.6带惯性权重的微粒群算法 (7) 2.7微粒群算法的研究现状 (8) 3 PSO算法优化PID参数 (8) 3.1PID控制原理 (8) 3.2PID控制特点 (9) 3.3优化设计简介 (9) 3.4目标函数的选取 (10) 3.5大迟滞系统简介 (11) 3.6加温炉控制简介 (14) 4 系统仿真 (14) 4.1工程上的参数整定 (14) 4.2微粒群算法参数整定 (16) 4.3结果比较 (16) 结论与展望 (16) １ 绪论 1.1 研究的背景和意义 效率是人们追求的最终目标，不断提高解的质量和求解的速度，尽可能地提 高效率以节省时间,顺应现代工业的发展，PID 控制器在智能控制方面起着越来越重要的作用，因为其具有结构简单，鲁棒性好，可靠性高等特点。在工业控制过程中，大多控制都是高阶，时滞和非线性的，所以对PID 控制的参数整定是非常困难的，PID 的控制性能与控制器参数d i p K K K ,,的优化整定直接相关，其参数的整定已成为PID 控制器应用需要解决的首要问题[1]。为解决各种优化问题，人们提出了许多优化算法，比较著名的有蚁群算法、神经网络算法[2]和遗传算法等。优化问题有两个主要问题。一是要求寻找全局最小点，二是要求有较高的收敛速度。蚁群算法适合在图上搜索路径问题，但计算开销会大。神经网络算法，编程和解码过程需要大量CPU 时间，算法易早熟，收敛易陷入局部最优。遗传算法，涉及到繁琐的编码解码过程和很大的计算量。所以到现在还没有万能的优化算法，不同的问题要用合适的算法。 1.2 常用的参数整定法 常用的参数整定方法：实验凑试法、衰减曲线法、临界比例度法、反应曲线 法。实验凑试法是通过闭环运行或模拟，观察系统的响应曲线，然后根据各参数对系统的影响，反复凑试参数，直至出现满意的响应，从而确定PID 控制参数。用衰减曲线法整定调节器参数的方法是：在纯比例作用下，i T 为∞，d T 为0，目的是要得到4:1，衰减振荡过度过程曲线。根据所得曲线，若衰减大于4:1 应调整δ朝小比例带方向；若小于4:1，应调整δ朝大比例带方向。记下4:1的比例带δ，并在记录曲线上求得4:1衰减时的调节周期P T ，然后计算δ，i T ，d T 各值。临界比例度法考虑的实质是通过现场试验找到等幅振荡的过渡过程，得到临界比例度和等幅振荡周期。当操纵变量作阶跃变化时，被控变量随时间变化的曲线称为反应曲线。对有自衡的非振荡过程，广义对象传递函数常可用 毕业论文 题目粒子群算法及其参数设置专业信息与计算科学 班级计算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 粒子群算法程序 tic D=10;%粒子群中粒子的个数 %w=0.729;%w为惯性因子 wmin=1.2; wmax=1.4; c1=1.49445;%正常数，成为加速因子 c2=1.49445;%正常数，成为加速因子 Loop_max=50;%最大迭代次数 %初始化粒子群 for i=1:D X(i)=rand(1)*(-5-7)+7; V(i)=1; f1(i)=X(i)^2; f2(i)=(X(i)-2)^2; end Loop=1;%迭代计数器 while Loop<=Loop_max%循环终止条件 %对粒子群中的每个粒子进行评价 for i=1:D k1=find(1==Xv(i,:));%找出第一辆车配送的城市编号 nb1=size(k1,2);%计算第一辆车配送城市的个数 if nb1>0%判断第一辆车配送城市个数是否大于0，如果大于0则 a1=[Xr(i,k1(:))];%找出第一辆车配送城市顺序号 b1=sort(a1);%对找出第一辆车的顺序号进行排序 G1(i)=0;%初始化第一辆车的配送量 k51=[]; am=[]; for j1=1:nb1 am=find(b1(j1)==Xr(i,:)); k51(j1)=intersect(k1,am);%计算第一辆车配送城市的顺序号 G1(i)=G1(i)+g(k51(j1)+1);%计算第一辆车的配送量 end k61=[]; k61=[0,k51,0];%定义第一辆车的配送路径 L1(i)=0;%初始化第一辆车的配送路径长度 for k11=1:nb1+1 L1(i)=L1(i)+Distance(k61(k11)+1,k61(k11+1)+1);%计算第一辆车的配送路径长度end else%如果第一辆车配送的城市个数不大于0则 G1(i)=0;%第一辆车的配送量设为0 L1(i)=0;%第一辆车的配送路径长度设为0 end 智能控制技术 课程论文 中文题目: 粒子群算法的研究现状及其应用姓名学号: 指导教师： 年级与专业： 所在学院： 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]上的随机数。 解决批量流水线调度问题的离散微粒群算法 3 潘玉霞 潘全科 桑红燕 武 磊 (聊城大学计算机学院,山东聊城252059) 摘 要 提出了解决以makespan 为目标的批量流水线调度问题的离散微粒群优化算法.该算 法采用了基于工序的编码方式,设计了新的粒子生成公式,通过局部搜索来提高算法的开发能力,从而使微粒群算法可以直接应用于调度问题.仿真实验表明了上述算法的有效性.关键词 批量流水线调度,离散微粒群算法,局部搜索中图分类号 TP181 文献标识码 A 文章编号 167226634(2009)0320090204 0 前言 复杂生产过程的智能优化调度理论与方法是目前国际学术和工业界一个跨学科的前沿研究方向.有效调度算法和优化技术的研究与应用,是提高生产效益与市场竞争力的基础和关键.批量流水线调度问题(Lot -st reaming Flowshop Scheduling Problem ,L FSP )是许多实际问题的简化模型,具有广泛的工程应用背景.目前,解决L FSP 的算法可大致区分为构造式启发算法[1,2]和智能优化算法[1].优先分配规则等构造式方法虽然能快速求解,但是解的质量往往不高.因此,能在合理时间内求得满意解的智能优化算法就成为求解调度问题的主要方法.微粒群优化(Particle Swarm Optimization ,PSO )算法源于对鸟群或鱼群行动时,透过个体间特有的信息传递方式,使整个群体朝同一目标聚集现象的模仿.由于其实现简单,并有较好的优化性能,根据PSO 的优化原理,提出了一种离散微粒群算法(Discrete PSO ,DPSO )来解决批量流水线调度问题.同时,结合基于Pairwise 局部搜索来平衡算法的全局开发和局部搜索能力.仿真试验表明了所得算法的优越性和高效性. 图1 L FSP 调度模型 1 批量流水线调度模型 L FSP 除了符合传统流水线调度的条件 外,还要把每个工件分成若干个小批量.批量的分配原则对调度的性能有重要影响,常见的批量分配原则有:等量分配、一致分配和可变分配.调查表明[3]等量分配原则在应用中取得了较好效果,故采用小批量的等量分配原则.各个工件的小批量加工完成后就能被 传送到下一台机床上加工,所有小批量的加工顺序都相同.每个工件在每台机床上加工完成后,在不影响 各工件最后一个小批量开始加工时间的条件下,推迟加工各个小批量,使得同一机床上同一工件相邻两个小批量之间没有等待时间.调度模型如图1所示. 第22卷 第3期2009年9月 聊城大学学报(自然科学版) Journal of Liaocheng University (Nat.Sci.)Vol.22No.3 Sep.2009 3 收稿日期:2009204206 基金项目:国家自然科学基金项目(60874075,70871065);山东省教育厅科研发展计划(J 09L F29)通信作者:潘玉霞,E 2mail :panyuxia2008@https://www.doczj.com/doc/f317752243.html,. 粒子群算法解决函数优化问题 1、群智能算法研究背景 粒子群优化算法（Particle Swarm Optimization，PSO）是由Kennedy 和Eberhart 在研究鸟类和鱼类的群体行为基础上于1995 年提出的一种群智能算法，其思想来源于人工生命和演化计算理论，模仿鸟群飞行觅食行为，通过鸟集体协作使群体达到优。 PSO算法作为一种新的群智能算法，可用于解决大量非线性、不可微和多峰值的复杂函数优化问题，并已广泛应用于科学和工程领域，如函数优化、神经网络训练、经济调度、模式识别与分类、结构设计、电磁场和任务调度等工程优化问题等。 PSO算法从提出到进一步发展，仅仅经历了十几年的时间，算法的理论基础还很薄弱，自身也存在着收敛速度慢和早熟的缺陷。如何加快粒子群算法的收敛速度和避免出现早熟收敛，一直是大多数研究者关注的重点。因此，对粒子群算法的分析改进不仅具有理论意义，而且具有一定的实际应用价值。 2、国内外研究现状 对PSO算法中惯性权重的改进：Poli等人在速度更新公式中引入惯性权重来更好的控制收敛和探索，形成了当前的标准PSO算法。 研究人员进行了大量的研究工作，先后提出了线性递减权值( LDIW)策略、模糊惯性权值( FIW) 策略和随机惯性权值( RIW) 策略。其中，FIW 策略需要专家知识建立模糊规则，实现难度较大，RIW 策略被用于求解动态系统，LDIW策略相对简单且收敛速度快， 任子晖，王坚于2009 年，又提出了基于聚焦距离变化率的自适应惯性权重PSO算法。 郑春颖和郑全弟等人，提出了基于试探的变步长自适应粒子群算 法。这些改进的PSO算法既保持了搜索速度快的特点, 又提高了全局搜索的能力。 对PSO算法的行为和收敛性的分析：1999 年采用代数方法对几种典型PSO算法的运行轨迹进行了分析，给出了保证收敛的参数选择范围。在收敛性方面Fransvan den Bergh引用Solis和Wets关于随机性算法的收敛准则，证明了标准PSO算法不能收敛于全局优解，甚至于局部优解；证明了保证收敛的PSO算法能够收敛于局部优解，而不能保证收敛于全局优解。 国内的学者：2006 年，刘洪波和王秀坤等人对粒子群优化算法的收敛性进行分析，指出它在满足收敛性的前提下种群多样性趋于减小，粒子将会因速度降低而失去继续搜索可行解的能力，提出混沌粒子群优化算法。 2008 年，黄翀鹏和熊伟丽等人分析惯性权值因子大小对PSO算法收敛性所带来的影响，对粒子群算法进行了改进。2009 年，高浩和冷文浩等人，分析了速度因子对微粒群算法影响，提出了一种基于Gaussian 变异全局收敛的粒子群算法。并证明了它能以概率 1 收敛到全局优解。 2010 年，为提高粒子群算法的收敛性,提出了基于动力系统的稳定性理论，对惯性权重粒子群模型的收敛性进行了分析，提出了使得在算法模型群模型收敛条件下的惯性权重和加速系数的参数约束关系，使算法在收敛性方面具有显著优越性。在PSO算法中嵌入别的算法的思想和技术。 1997年，李兵和蒋慰孙提出混沌优化方法； 1998年，Angeline在PSO算法中引入遗传算法中的选择算子，该算法虽然加快了算法的收敛速度，但同时也使算法陷入局部优的概率大增，特别是在优化Griewank 基准函数的优值时得到的结果不理想； 2004 年，高鹰和谢胜利将混沌寻优思想引入到粒子群优化算法中，首先对当前群体中的优粒子进行混沌寻优, 再用混沌寻优的结果随机替换群体中的一个粒子，这样提出另一种混沌粒子群优化算法。 摘要 在智能领域，大部分问题都可以归结为优化问题。常用的经典优化算法都对问题有一定的约束条件，如要求优化函数可微等，仿生算法是一种模拟生物智能行为的优化算法，由于其几乎不存在对问题的约束，因此，粒子群优化算法在各种优化问题中得到广泛应用。 本文首先描述了基本粒子群优化算法及其改进算法的基本原理,对比分析粒子群优化算法与其他优化算法的优缺点，并对基本粒子群优化算法参数进行了简要分析。根据分析结果,研究了一种基于量子的粒子群优化算法。在标准测试函数的优化上粒子群优化算法与改进算法进行了比较,实验结果表明改进的算法在优化性能明显要优于其它算法。本文算法应用于支持向量机参数选择的优化问题上也获得了较好的性能。最后,对本文进行了简单的总结和展望。 关键词：粒子群优化算法最小二乘支持向量机参数优化适应度 目录 摘要...................................................................... I 目录....................................................................... II 1.概述. (1) 1.1引言 (1) 1.2研究背景 (1) 1.2.1人工生命计算 (1) 1.2.2 群集智能理论 (2) 1.3算法比较 (2) 1.3.1粒子群算法与遗传算法(GA)比较 (2) 1.3.2粒子群算法与蚁群算法(ACO)比较 (3) 1.4粒子群优化算法的研究现状 (4) 1.4.1理论研究现状 (4) 1.4.2应用研究现状 (5) 1.5粒子群优化算法的应用 (5) 1.5.1神经网络训练 (6) 1.5.2函数优化 (6) 1.5.3其他应用 (6) 1.5.4粒子群优化算法的工程应用概述 (6) 2.粒子群优化算法 (8) 2.1基本粒子群优化算法 (8) 2.1.1基本理论 (8) 2.1.2算法流程 (9) 2.2标准粒子群优化算法 (10) 2.2.1惯性权重 (10) 2.2.2压缩因子 (11) 2.3算法分析 (12) 2.3.1参数分析 (12) 2.3.2粒子群优化算法的特点 (14) 3.粒子群优化算法的改进 (15) 3.1粒子群优化算法存在的问题 (15) 3.2粒子群优化算法的改进分析 (15) 3.3基于量子粒子群优化(QPSO)算法 (17) 3.3.1 QPSO算法的优点 (17) 3.3.2 基于MATLAB的仿真 (18) 3.4 PSO仿真 (19) 3.4.1 标准测试函数 (19) 3.4.2 试验参数设置 (20) 3.5试验结果与分析 (21) 4.粒子群优化算法在支持向量机的参数优化中的应用 (22) 4.1支持向量机 (22) 4.2最小二乘支持向量机原理 (22) 第二章基本微粒群算法 2.1引言 自然界中各种生物体均具有一定的群体行为，而人工生命的主要研究领域之一就是探索自然界生物的群体行为从而在计算机上构建其群体模型。通常，群体行为可以由几条简单的规则进行建模，如鱼群、鸟群等。虽然每一个个体具有非常简单的行为规则，但群体的行为却非常复杂。Reynolds将这种类型的个体称为boid，并使用计算机图形动画对复杂的群体行为进行仿真。他在仿真中采用了下列三条简单规则： （1）飞离最近的个体，以避免碰撞 （2）飞向目标 （3）飞向群体的中心 群体内每一个体的行为可采用上述规则进行描述，这是微粒群算法的基本概念之一。 Boyd和Richerson在研究人类的决策过程时，提出了个体学习和文化传递的概念。根据他们的研究结果，人们在决策过程中使用两类重要的信息。一是自身的经验，二是其他人的经验。也就是说，人们根据自身的经验和他人的经验进行自己的决策。这是微粒群算法的另一基本概念。 微粒群算法最早是在1995年由美国社会心理学家James Kennedy和电气工程师Russell Eberhart 共同提出的，其基本思想是受他们早期对许多鸟类的群体行为进行建模与仿真研究结果的启发。而他们的模型及仿真算法主要利用了生物学家Frank Heppner的模型。 Frank Heppner的鸟类模型在反映群体行为方面与其它类模型有许多相同之处，所不同之处在于：鸟类被吸引飞向栖息地。在仿真中，一开始每一只鸟均无特定目标进行飞行，直到有一只鸟飞到栖息地，当设置期望栖息比期望留在鸟群中具有较大的适应值时，每一只鸟都将离开群体而飞向栖息地，随后就自然地形成了鸟群，。 由于鸟类使用简单的规则确定自己的飞行方向与飞行速度（实质上，每一只鸟都试图停在鸟群中而又不相互碰撞），当一只鸟飞离鸟群而飞向栖息地时，将导致它周围的其它鸟也飞向栖息地。这些鸟一旦发现栖息地，将降落在此，驱使更多的鸟落在栖息地，直到整个鸟群都落在栖息地。 由于James Kennedy和 Russell Eberhart所具有的专业背景，就能很容易理解他们为什么会对Hepper的鸟类模型感兴趣。鸟类寻找栖息地与对一个特定问题寻找解很类似，已经找到栖息地的鸟引导它周围的鸟飞向栖息地的方式，增加了整个鸟群都找到栖息地的可能性，也符合信念的社会认知观点。 Eberhart和Kennedy对Heppner的模型进行了修正，以使微粒能够飞向解空间并在最好解处降落。其关键在于如何保证微粒降落在最好解处而不降落在其它解处，这就是信念的社会性及智能性所在。 信念具有社会性的实质在于个体向它周围的成功者学习。个体与周围的其它同类比较，并模仿其优秀者的行为。将这种思想用算法实现将导致一种新的最优化算法。 要解决上述问题，关键在于在探索（寻找一个好解）和开发（利用一个好解）之间寻找一个好的平衡。太小的探索导致算法收敛于早期所遇到的好解处，而太小的开发会使算法不收敛。 另一方面，需要在个性与社会性之间寻求平衡，也就是说，既希望个体具有个性化，像鸟类模型中的鸟不互相碰撞，又希望其知道其它个体已经找到的好解并向它们学习，即社会性。 Eberhart和Kennedy较好地解决了上述问题，提出了微粒群优化算法(Particle Swarm Optimization, PSO)[Kennedy 1995]。 2.2基本微粒群算法 Kennedy和Eberhart在1995年的IEEE国际神经网络学术会议上正式发表了题为“Particle 什么是粒子群优化算法 根据电为系统无功优化问题非线性、多约束、多目标、连续和离散变量共存的 特点［３］，目前无功优化研究的关键点主要集中在两个问题上，第一个是建立合适的无功优化数学模型，第二个是选择合适的无功优化方法。针对第一个问题，一般采 取的是具体问题具体分析，建立的数学模型首先要符合电力系统的运行情况和各项 约束，其次再根据个人偏好确定所需的目标函数。针对第二个问题，目前广泛使用 的无功优化方法主要分为两类：经典数学优化方法和新型人工智能优化方法，这两 类方法在电力系统无功优化问题上都得到了广泛的应用。 １．２．１经典数学优化算法 经典数学优化算法的基本思路大致都是：先选定某一合适的初值，进行不断迭 代，当满足迭代结束条件时，收敛到局部或者全局最优解。无功优化中最常见的数 学优化算法主要包括线性规划法Ｗ、非线性规划法Ｗ、混合整数规划法及动态规 划法ｍ等等。 线性规划法的原理是对目标函数和约束条件运用泰勒公式进行数学变换，变换 后略去高次项，这样就把电力系统无功优化这一非线性问题转换为线性问题。典型 的线性规划法主要有内点法Ｗ和灵敏度分析法Ｗ。这类方法的优势在于方法成熟、 模型简单、求解速度快、收敛性好。但是把非线性问题运用线性化的方法解决必然 会带来一系列误差。首先是对于大型电网，线性规划法的收敛精度可能存在较大的 误差，其次是步长的选择问题，步长过大会导致反复偏离最优解而产生振荡，步长 过小则会导致算法的收敛速度变慢。显然，要针对不同系统选择合适的步长，因此 算法的通用性不强。最后，线性规划法对初值和函数的凹凸性都有一定要求，Ｗ上 这些缺陷使其在应用和发展上都存在一定局限性。 （２）非线性规划法 非线性规划法的原理是通过引入拉格朗日系数或惩罚系数将含约束的优化问题 转换为序列无约束优化问题或者线性规划问题求解，是一种能处理系统优化模型中 各类约束条件或目标函数至少有＾个是非线性函数的规划方法。因为电力系统无功 优化问题本身就是非线性优化问题，所Ｌ乂非线性规划法更加适合求解电力系统无功优化问题。典型的非线性规划法主要有简化梯度法Ｗ、牛顿法和二次规划法Ｕ２３。这类方法优势主要是模型精确，方法简单，计算精度高，但其缺点也十分明显，如 计算量大、稳定性不好、某些不等式和高维问题难ＬｊＡ处理等等，尤其是电力系统无功优化的控制变量既有连续变量又有离散变量且各类等式不等式约束较多，这就大 大限制了非线性规划法的作用。 （３）混合整数规划法 混合整数规划法是一种处理含离散变量问题的方法，主要的原理是先取好整数 变量，再用上述线性或非线性规划法处理连续变量。送比直接将离散变量当做连续 变量优化，然后再对其取整有一定优势。因此，混合整数规划法十分适合优化电刀 系统无功优化的某些控制变量，如变压器的抽头位置和电容器组的投切数目。这类 方法的优势主要是能更精确的处理优化过程中的离散变量，但也存在一系列问题， 如随着维数提升，计算量成倍増加，容易产生＂维数灾＂，尤其随着电力系统规模 的不断增大，混合整数规划法的作用将会大大受限。所ｔＵ兑，混合整数规划法一般适用于规模较小的电力系统无功优化研究。典型的混合整数规划法主要有分支界定 法山］。 ３ 摘要：，粒子群算法据自己的速度来决定搜索过程，只有最优的粒子把信息给予其他的粒子，整个搜索更新过程是跟随当前最优解的过程，所有的粒子还可以更快的收敛于最优解。由于微粒群算法简单，容易实现，与其它求解约束优化问题的方法相比较，具有一定的优势。实验结果表明，对于无约束的非线性求解，粒子群算法表现出较好的收敛性和健壮性。 关键词：粒子群算法；函数优化；极值寻优 0 引言 非线性方程的求根问题是多年来数学家努力解决的问题之一。长期以来，人们已找出多种用于解决方程求根的方法，例如牛顿法、弦割法、抛物线法等。然而，很多传统的方法仅能运用于相应的小的问题集，推广性相对较差。对于一个现实世界中的优化问题，必须尝试很多不同的方法，甚至要发明相应的新的方法来解决，这显然是不现实的。我们需要另外的方法来克服这样的困难。 粒子群算法是一种现代启发式算法，具有推广性强、鲁棒性高等特点[1]。该算法具有群体智能、内在并行性、迭代格式简单、可快速收敛到最优解所在区域等优点[2]。本文采用粒子群算法，对函数的极值进行寻优计算，实现了对函数的极值求解。 1 粒子群算法 1.1 基本原理 粒子群算法（PSO）是一种基于群体的随机优化技术，它的思想来源于对鸟群捕食行为的研究与模拟。粒子群算法与其它基于群体的进化算法相类似，选用“群体”和“进化”的概念，按照个体的适应度值进行操作，也是一种基于迭代的寻优技术。区别在于，粒子群算法中没有交叉变异等进化算子，而是将每个个体看作搜索空间中的微粒，每个微粒没有重量和体积，但都有自己的位置向量、速度向量和适应度值。所有微粒以一定的速度飞行于搜索空间中，其中的飞行速度是由个体飞行经验和群体的飞行经验动态调整，通过追踪当前搜索到的最优值来寻找全局最优值。 1.2 参数选择 粒子群算法需要修改的参数很少，但对参数的选择却十分敏感。El-Gallad A, El-Hawary M, Sallam A, Kalas A[3]主要对算法中的种群规模、迭代次数和粒子速度的选择方法进行了详细分析，利用统计方法对约束优化问题的求解论证了这3 个参数对算法性能的影响，并给出了具有一定通用性的3 个参数选择原则[4]。 种群规模：通常根据待优化问题的复杂程度确定。 最大速度：决定粒子在一次迭代中的最大移动距离,通常设定为不超过粒子的范围宽度。 加速常数：加速常数c1和c2通常是由经验值决定的，它代表粒子向pbest和gbest靠拢的加速项的权重。一般取值为：c1=c2=2。 中止条件：达到最大迭代次数或得到最小误差要求，通常要由具体问题确定。 惯性权重：惯性权重能够针对待优化问题调整算法的局部和全局搜索能力。当该值较大时有利于全局搜索，较小时有利于局部搜索。所以通常在算法开始时设置较大的惯性权重，以便扩大搜索范围、加快收敛。而随着迭代次数的增加逐渐减小惯性权重的值，使其进行精确搜索，避免跳过最优解。 1.3 算法步骤 PSO算法步骤如下： Step1：初始化一个规模为m 的粒子群，设定初始位置和速度。 初始化过程如下： （1）设定群体规模m; （2）对任意的i，s，在[-xmax, xmax]内均匀分布，产生初始位置xis； （3）对任意的i，s，在[-vmax, vmax]内均匀分布，产生速度vis； 篇一：基于粒子群算法的电力系统无功优化开题报告 附件 基于粒子群算法的电力系统无功优化 一、选题背景及其意义 电力系统无功优化，一般是指在满足电网的安全运行约束的前提下，通过变压器分接头的合理选择，发电机机端电压的理想配合以及无功补偿的优化配置等措施，使系统无功潮流达到最优分布，减少有功损耗。它对于提高系统电压质量，减少有功损耗，保证系统安全、可靠和经济运行有重要意义。 在我国，随着电力系统的迅速发展，电网规模越来越大，结构也日趋复杂，使系统的稳定性问题更加突出，而单凭经验进行无功配置已不能适应现代系统的需要，需要在现代电子与计算机技术的基础上，研究建立无功优化的数学模型、提出相应的算法，在电网的规划建设和实际调度运行中实现无功优化，并在满足电网安全运行条件下，减少有功损耗和投资。同时对于电力公司而言，减少有功网损就是增加利润，在电力公司由粗放型经营向集约化经营方式转变的今天，进行无功优化就显的更加必要和重要了。本论文通过分析电力系统无功优化中各类主要影响因素，结合当前电力系统无功优化主要的研究方法，建立电力系统无功优化的数学模型。采用智能优化算法——粒子群算法求解数学模型，选取实际的电网作为计算算例，得到无功优化的结果，并与优化前的无功配置方案进行对比，分析粒子群算法在无功优化应用中的优缺点，为今后实际电网的无功规划提供一定的参考价值。 二、国内外研究动态 早在六十年代，电力系统无功优化就受到了国内外学者的关注，经过多年的研究，已经取得了大量成果。总的来看，电力系统的无功优化问题可以分为两类：一类是对系统稳态运行情况下的运行状态进行优化，目的是进行无功平衡，以提高运行电压水平、降低损耗；另一类是研究系统在扰动情况下的电压稳定性。前者根据所研究问题的时间跨度、目标函数和解决方法又可以进一步细分。本文的研究内容为稳定运行时的无功优化及电压控制，不涉及暂态和动态情况下的电压稳定性。 电力系统无功优化问题有离散性、非线性、大规模、收敛性依赖于初值的特点，针对无功优化的特点，近年来许多专家学者就此做了大量的研究，并将各种优化算法应用于这一领域，目前已取得了许多成果。文献[3]提出将一种改进的 tabu 搜索算法用于电力系统无功优化，考虑有功损耗费用和补偿费用，使得总费用最小。在一般的 tabu 搜索算法的基础上，对搜索步长、禁忌表、不同循环点的选择以及算法终止判据等问题做了改进，更容易跳出局部最优解，保证可以搜索整个可行域，从而得到全局最优解的可能性更大。与线性规划算法相比具有更强的全局寻优能力。文献[4]运用改进的模拟退火算法求解高中压配电网的无功优化问题，采用了记忆指导搜索方法来加快搜索速度。采用模拟法来进行局部寻优以增加获得全局最优解的可能性，从而能够以较大概率获得全局最优解，收敛稳定性较好。文献[5]提出了一种应用于电力系统无功规划优化问题的改进遗传算法，该算法采用十进制整数与实数混合的编码方式，在选择算子中使用最优保存策略，并对群体规模的选取加以改进。为了使解更快进入可行解域，作者提出了利用专家知识辅助搜寻可行解，并提出罚因子自适应调整，大大加快了算法的收敛性。 相对模拟退火算法、禁忌搜索算法和遗传算法而言，粒子群算法是模拟鸟群觅食的一种新型算法。粒子群优化(pso) 最初是处理连续优化问题的, 目前其应用已扩展到组合优化问题[6]。由于其简单、有效的特点, pso 已经得到了众多学者的重视和研究，并在电力系统优化中得到广泛应用。文献[7]对粒子群算法经行了改进，用于变电站的选址；文献[8]采用粒子群算法优化分布式电源的接入位置和容量；文献[9]利用改进的粒子群算法进行网络重构的优化。从以上文献的研究可以看出，粒子群算法在求解优化问题时有其自身特有的诸多优点。 粒子群算法 摘要：粒子群优化算法是由James Kennedy和 Russell Eberbart 设计的一种仿生优化计算方法。PSO算法的基本设计思想来源于两个方面分别是人工生命和进化计算，设计者通过研究动物群体以及人类行为模式的计算机模拟，然后不断的试错、修改而逐渐的到算法的原型。PSO算法的运行机理不是依靠个体的自然进化规律，而是对生物群体的社会行为进行模拟。它最早源于对鸟群觅食行为的研究。在生物群体中存在着个体与个体、个体与群体间的相互作用、相互影响的行为，这种相互作用和影响是通过信息共享机制体现的。PSO算法就是对这种社会行为的模拟即利用信息共享机制，使得个体间可以相互借鉴经验，从而促进整个群体朝着更好的方向发展。 关键词：粒子群优化算法；社会行为；鸟群觅食；信息共享 1 粒子群算法设计思想 粒子群算法的思想来源于对鸟捕食行为的模仿，虽让鸟群在捕食过程中会发生改变飞行方向、聚集等一系列不可预测的行为但整体还是呈现一种有序性，研究证明是因为鸟群中存在一种信息共享机制。可以设想一群鸟在随机搜索食物，刚开始每只鸟均不知道食物在哪里，所以均无特定的目标进行飞行，但是它们知道哪只鸟距离食物最近，还有自己曾经离食物最近的位置，每只鸟开始通过试图通过这两个位置来确定自己往哪个方向飞行。因此可以将鸟群觅食行为看做一个特定问题寻找解的过程。 如果我们把一个优化问题看做是空中觅食的鸟群，那么粒子群中每个优化问题的可行解就是搜索空间中的一只鸟，称为“粒子”，“食物”就是优化问题的最优解。个体找到食物就相当于优化问题找到最优解。当然这里的鸟群（粒子）是经过人工处理的，它们均有记忆功能，没有质量和体积，不占空间，每个粒子均有速度和位置两个属性，同时每个粒子都有一个由优化问题决定的适应度来评价粒子的“好坏”程度，显然，每个粒子的行为就是总追随者当前的最优粒子在解空间中搜索。 粒子群优化算法(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。这样一个标准的粒子群算法就介绍结束了。下图是对整个基本的粒子群的过程给一个简单的图形表示。 判断终止条件可是设置适应值到达一定的数值或者循环一定的次数。 注意：这里的粒子是同时跟踪自己的历史最优值与全局（群体）最优值来改变自己的位置预速度的，所以又叫做全局版本的标准粒子群优化算法。微粒群算法
粒子群优化算法及其参数设置
用粒子群算法求解多目标优化问题的Pareto解
粒子群算法的研究现状及其应用
解决批量流水线调度问题的离散微粒群算法
粒子群算法解决函数优化问题
粒子群优化算法及其应用研究
基本微粒群算法-Read
粒子群优化算法
粒子群优化算法(Particle Swarm optimization,PSO)又翻译为粒子群算法、微粒群算法、或 粒子群优化算法 微粒群优化算法。是通过模拟鸟群觅食行为而发展起来的一种基于群体协作的随机搜索算法。通 常认为它是群集智能 (Swarm intelligence, SI) 的一种。它可以被纳入多主体优化系统 (Multiagent Optimization System, MAOS). 是由 Eberhart 博士和 kennedy 博士发明。 PSO 模拟鸟群的捕食行为。一群鸟在随机搜索食物，在这个区域里只有一块食物。所有的 鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是 什么呢。最简单有效的就是搜寻目前离食物最近的鸟的周围区域。 PSO 从这种模型中得到启示并用于解决优化问题。PSO 中，每个优化问题的解都是搜索空 间中的一只鸟。我们称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值 (fitnessvalue)，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最 优粒子在解空间中搜索。 PSO 初始化为一群随机粒子(随机解)，然后通过叠代找到最优解，在每一次叠代中，粒子通 过跟踪两个“极值”来更新自己。第一个就是粒子本身所找到的最优解，这个解叫做个体极值 pBest，另一个极值是整个种群目前找到的最优解，这个极值是全局极值 gBest。另外也可以不 用整个种群而只是用其中一部分最优粒子的邻居，那么在所有邻居中的极值就是局部极值。 [编辑]
PSO 算法介绍[1]
如前所述，PSO 模拟鸟群的捕食行为。设想这样一个场景：一群鸟在随机搜索食物。在这 个区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多 远 那么找到食物的最优策略是什么呢 最简单有效的就是搜寻目前离食物最近的鸟的周围区域 。 。 。 PSO 从这种模型中得到启示并用于解决优化问题。PSO 中，每个优化问题的解都是搜索空 间中的一只鸟。我们称之为“粒子”。所有的例子都有一个由被优化的函数决定的适应值(fitness value)，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子 在解空间中搜索 PSO 初始化为一群随机粒子(随机解)。然后通过叠代找到最优解。在每一次叠代中，粒子通 过跟踪两个"极值"来更新自己 第一个就是粒子本身所找到的最优解 这个解叫做个体极值 pBest. 。 。 另一个极值是整个种群目前找到的最优解。这个极值是全局极值 gBest。另外也可以不用整个种 群而只是用其中一部分最为粒子的邻居，那么在所有邻居中的极值就是局部极值。 在找到这两个最优值时, 粒子根据如下的公式来更新自己的速度和新的位置经典算法优缺点
粒子群算法
优化算法开题报告
粒子群算法
粒子群优化算法介绍及matlab程序【精品文档】(完整版)
相关主题
文本预览