1 绪论
最优化问题是在满足一定约束条件下，寻找一组参数值，以使某些最优性度量得到满足，即使系统的某些性能指标达到最大或者最小。它广泛存在于农业、国防、工程、交通、金融、化工、能源、通信、材料等许多领域。最优化技术在上述领域的应用已经产生了巨大的经济效益和社会效益。国内外的实践表明，在同样条件下，经过优化技术的处理，对系统效率的提高、能耗的降低、资源的合理利用及经济效益提高均有显著的效果，而且随着处理对象规模的增大，这种效果也更加显著。传统的优化方法根据问题的性质不同，通常将问题划分为线性规划问题、非线性规划问题、整数规划问题和多目标规划问题。相应的有一些成熟的常规算法，如应用于线性规划问题的单纯形法，应用于非线性规划的牛顿法、共轭梯度法等，应用于整数规划的分枝定界法、动态规划法等。
目前，基于严格机理模型的开放式方程建模与优化已成为国际上公认的主流技术方向。许多工程公司和各大科研机构纷纷投入大量的人力物力对系统的建模与优化进行深入细致的研究，希望取得突破性的进展。然而，基于严格机理模型所得到的优化命题往往具有方程数多、变量维数高、非线性强等特点，这使得相关变量的存储、计算及求解都相当困难。在国民经济的各个领域中都存在着相当多的涉及因素多、规模大、难度高和影响广的优化命题，如流程工业系统优化、运输中的最优调度、生产流程的最优排产、资源的最优分配、农作物的合理布局、工程的最优设计以及国土的最优开发等等，所有这些问题的解决也必须有一个强有力的优化工具来进行求解。而前述传统的优化算法面对这样的大型问题已无能为力，无论是在计算速度、收敛性、初值敏感性等方面都远不能满足要求。
人们从生命现象中得到启示，发明了许多智能的优化方法来解决上述复杂优化问题。例如遗传算法(Genetic Algorithm)参考了生物种群通过遗传和自然选择不断进化的功能、人工免疫系统(Artificail Immune Systems)模拟了生物免疫系统的学习和认知功能、蚁群优化(Ant colony Optimization)算法模仿了蚂蚁群体在路径选择和信息传递方面的行为，粒子群优化（Particle swarm optimization)算法模拟了鸟群和鱼群觅食迁徙中个体与群体协调一致的机理，群落选址算法(colony Location Algorithm)模拟了植物群落的形成机制等，这类借鉴模拟了生命系统的行为、功能和特性的科学计算
方法称之为人工生命计算(Artifieial Life Computation)。人工生命计算是生命科学、信息科学和运筹学的交叉研究学科，是进化计算的一个新的分支，是由具有生命特性的多智能体以特定计算目标为依据，有序组合起来所形成的计算方法。按照此定义，人工神经网络(Artificial Neural Network)，文化算法(Cultural Algorithm)、人工生命算法(Artifieial Life Algorithm)、捕食搜索策略(Predatory Search Strategy)等都可以被归纳为人工生命计算。
粒子群优化(PSO)算法是其中较新的一种人工生命计算方法。它同遗传算法类似，是一种基于迭代的优化工具。系统初始化为一组随机解，通过迭代搜索最优值。同遗传算法等其他人工生命计算方法相比，粒子群优化算法概念简单、容易实现，没有很多参数需要调节。目前粒子群算法越来越引起人们的关注，已成为国际上一个新的研究热点。粒子群优化算法的研究还处于初级阶段，还有很多领域需要研究。
在这篇文章中，首先提出了标准的粒子群算法，标准的粒子群算法由于其简单和解决问题的有效能力而被应用到很多的领域。但在实际应用当中，也表现出了一些不尽人意的问题。这些问题中最主要的是它容易产生早熟收敛、局部寻优能力较差等。实际上这些缺点也是几乎所有随机算法的弊病。本文将梯度信息引入标准PSO算法，并在群体最优信息陷入停滞时将群体进行部分初始化来保持群体的活性，防止群体陷入局优，构造出带有梯度加速的PSO算法。带有梯度加速优化算法却具有很强的局部搜索能力，一种带有梯度加速的PSO算法是对标准PSO算法进行改进。并通过实验讨论了改进算法的适用范围。实验表明，对于单峰函数和多峰函数，带有梯度加速的PSO都能够取得更好的优化效果。
2 粒子群优化算法及其理论基础
2.1概述
长久以来，人们向往着设计的人工系统像自然系统那样健壮，高效灵活，具有适应性、自组织和再生能力。近几十年来，一些新颖的优化算法，如人工神经网络、遗传算法及蚁群算法、粒子群算法等通过模拟或揭示某些自然现象或过程而得到发展，其思想和内容涉及数学、生物进化、人工智能、神经科学和量子统计学等方面，为解决复杂工程问题提供了新的思路和手段.这些算法独特的优点和机制，引起了国内外学者的广泛重视并掀起了该领域的研究热潮，且在许多领域得到了成功应用。在优化领域，由于这些算法构造的直观性与自然机理，被称作为智能优化算法。
在这些智能优化方法中，有一类是模拟某些群体的智能行为，虽然群体中的个体仅具有简单的智能，但通过个体与个体和个体与环境的信息交流以及个体的简单行为，从而使群体表现出复杂的自组织、分布式控制、可扩展、健壮的智能体，实现对空间的高效搜索。也就是说，群体智能可以在适当的进化机制引导下通过个体交互以某种突现形式发挥作用，这是个体的智能难以做到的。
在群体智能优化算法的框架下，大量基于不同物理背景的算法纷纷被提出，如，遗传算法，粒子群算法等，并进行了广泛的应用尝试。
粒子群算法(Particle Swarm Optimization.简称PSO)，是一种基于群体智能的进化计算方法.是由PSO由Kennedy和Eberhart博士于1995年提出。
PSO的基本概念源于对鸟群捕食行为的研究:一群鸟在随机搜寻食物，在这个区域里只有一块食物，所有鸟都不知道食物在哪里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢?最简单有效的就是搜寻目前离食物最近的鸟的周围区域.PSO从这种模型中得到启示并用于解决优化问题.在PSO中，每个优化问题的潜在解都是搜索空间中的一只鸟，称之为“粒子”，即问题的解空间对应于搜索空间粒子群。所有的粒子都有一个由被优化的问题(如，函数)决定的适应值，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子群们就追随当前的最优粒子在解空间中搜索.PSO初始化为一群随机粒子也就是随机解，然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪“两个极值”来更新自己。第一个就粒子本身所找到的最优解，这个解称为个体极值，另一个极值是整个种群目前找到的最优解，这个极值是全局极值。另外也可以不用整个种群而是用其中一部分作为粒子的邻居，那么在所有邻居中的极值就是局部极值。
PSO一经提出，立刻引起了进化计算领域学者们的广泛关注，形成一个研究热点，目前己广泛应用于函数优化、神经网络训练、模式分类、模糊控制等领域，取得了较好的效果。
2.2原始粒子群优化算法的基本概念
为了更好地描述粒子群优化算法，在此作如下定义
定义1 粒子
类似于遗传算法中的染色体，PSO中粒子为基本的组成单位，代表解空间的一个候选解。
定义2种群
粒子种群由n个粒子组成，代表n个候选解。
定义3粒子速度
粒子速度表示粒子在单位迭代次数位置的变化即为代表解变量的粒子在d维空间的位移。
定义4适应度函数
一般由适应度函数由优化目标决定，用于评价粒子的搜索性能，指导粒子种群的搜索过程。算法迭代停止时适应度函数最优的解变量即为优化搜索的最优解。
定义5个体极值
个体极值是单个粒子从搜索初始到当前迭代对应的适应度最优的解。
定义6 全局极值
全局极值是整个粒子种群从搜索开始到当前迭代对应的适应度最优的解。
2.3粒子群优化算法的一般数学模型
粒子群算法的基本思想是:用随机解初始化一群随机粒子，然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个“极值”来更新自己:第一个就是粒子本身所找到的最好解，即个体极值(Pbest)，另一个极值是整个粒子群中所有粒子在历代搜索过程中所达到的最优解(Gbest)，即全局极值，在找到这两个最好解后，接下来是PSO 中最重要的“加速”过程，每个粒子不断地改变其在解空间中的速度，以尽可能地朝Pbest 和Gbest 所指向的区域“飞”去。基本的粒子群模型由一个m 维变量空间内n 个粒子(位置，速度)=（k i X ,k i V )组成的群体构成，表示为:
()12,,...,,...,T
k k k k k i i i ij im X X X X X = (2.1) ()12,,...,,...,T
k k k k k i i i ij im V V V V V = (2.2) 式中 ， i=1,2,…,n ，n 为粒子群中粒子的个数:j=1,2,…,m ，m 为解向量的维 数;k 是进化代数.粒子根据如下的式(2.3)和式(2.4)来更新自己的速度和位置.
11122()()k k k k k k ij ij ij ij ij ij V V c rand pbest X c rand gbest X +=+-+- (2.3)
11k k k ij ij ij X X V ++=+ (2.4)
k ij V 、1k ij V +分别表示第i 个粒子在j 维方向上的当前速度和修正后的速度;
k ij
X 、1k ij X +分别为第i 个粒子在j 维方向上的当前坐标和修正后的坐标;c1, c2是加速系数，分别调节向全局最好粒子和个体最好粒子方向飞行的最大步长;
1k ij
pbest +是第i 个粒子在第j 维的个体极值点的位置，1k ij gbest +是到第k 代为止，所有粒子在第j 维的全局极值点的位置:rand1,和rand2为两个在[0, 1]范围内变化的随机函数。
2.4粒子群优化算法的设计步骤和算法流程
设计步骤:
(1) 确定问题的表示方案
粒子群算法在求解问题时，其首要步骤是将问题的解从解空间映射到具有某种
结构的表示空间，即用特定的编码表示问题的解，这和遗传算法是类似的。粒子群算法的大部分研究均集中在数值优化领域中，其位置一速度计算模型使用于具有连续特征的问题函数，因此，目前算法大多采用实数向量的编码方式，以粒子的位置向量来表示问题的解。
(2) 确定优化问题的评价函数
在求解问题时，必须根据问题的具体特征，选取适当的目标函数来计算适应值，适应值是唯一能够反映并引导优化过程不断进行的参量。
(3) 选择控制参数
粒子群算法的控制参数通常包括粒子种群数量、算法执行的最大代数、惯性权重系数其他一些辅助控制参数，如粒子位置和速度的控制范围等。
(4) 选择粒子群模型
目前，粒子群算法己经发展了多种位置一速度计算模型，如惯性权重PSO模型、二进制PSO模型等等，在求解不同类型优化问题时，不同PSO模型的优化性能也有差异。
（5）确定算法的终止准则
与其他进化算法一样，PSO算法中最常用的终止准则时预先设定一个最大的迭代次数，或者当搜索过程中解的适应值在连续多少代后不再发生明显改变时，终止算法。PSO 的算法流程如下:
Step 1 :设定加速常数C1和C2，最大进化代数等参数，将当前进化代数置为t=1,初始化一群微粒(群体规模为N)，包括随机位置和速度;
Step 2 :评价每个微粒的适应度;
Step 3 :对每个微粒，将其适应值与其经历过的最好位置pbest作比较，如果较好，则将其作为当前的最好位置pbest;
Step 4 :对每个微粒，将其适应值与全局所经历的最好位置gbest作比较，如果较好，则重新设置gbest;
Step5 : 根据方程(2.3)和(2.4)变化微粒的速度和位置;
Step6 :检查结束条件，若满足，则结束寻优，如未达到结束条件(通常为足够好的适应值或达到一个预设最大代数T)，则返回Step 2.
从上述粒子群优化算法寻优过程可以看出其有如下特性:粒子群中的群体随着时间的
变化而进行空间位置的计算;粒子群中的群体对环境中的品质因素做出响应，这种品质因素是通过PSO 中每个粒子的最好位置和种群中的最优粒子来反映的;粒子群通过一定方式(即通过对个体最优粒子的记忆和对全局最优粒子的学习的方式)分配这种响应而体现出种群的多样性，仅仅当粒子群中的最优粒子发生改变时，粒子群中粒子的行为才发生改变，这正体现出了粒子群的稳定性和适应性。
2.5 标准的粒子群算法
为了改善算法收敛性能，Shi 和Eberhart 在1998年的论文中引入了惯性权重的概念，引入惯性权重因子w 后，公式(2.3).(2 .4)就变为
11122()()k k k k k k ij ij ij ij ij ij V wV c rand pbest X c rand gbest X +=+-+- (2.5) 11k k k ij ij ij X X V ++=+ (2.6)
显见 ， 惯性权重W 描述了粒子上一代速度对当前代速度的影响，控制其取值大小可
调节PSO 算法的全局与局部寻优能力。w 值较大，全局寻优能力强，局部寻优能力弱，反之，则局部寻优能力增强，而全局寻优能力减弱。刚开始惯性权重为常数，但后来的试验发现，动态惯性权值能够获得比固定值更为好的寻优结果。动态惯性权值可以在PSO 搜索过程中线性变化，亦可根据PSO 性能的某个测度而动态改变。惯性权重的引入，可从不同的角度调整算法全局和局部搜索能力，使PSO 算法的性能得到了很大提高，也使PSO 算法得以比较成功地应用于很多实际问题。
2.6粒子群优化的研究现状
（1）理论研究现状
在算法的理论研究方面，有部分研究者对算法的收敛性进行了分析，更多的研究者致力于研究算法的结构和性能改善，包括参数分析，拓扑结构，粒子多样性保持，算法融合和性能比较等。
在收敛性研究方面，Clerc 和Knenedy 将PSO 基本公式简化为一维空间中的单个粒子，分析了其在离散时间和连续时间的移动情况，并提出了完全描述系统的五维模型，里面包含的参数能够控制系统收敛的趋势。Ozcan 和Mohan 在假设w=1,C1和C2为常数，i P 和g P 为固定点情况下，通过理论分析将一个微粒随时间变化描述为波的运行，并
对不同区域进行了轨迹分析。Trealea 应用离散动态系统理论对简化PSO 模型的动态行为和收敛性进行了分析，推导出对参数选择的参考准则。
PSO 的早期版本没有惯性权重，Shi 和Ebehart 首次提出了惯性权重的概念，来对基本算法中的速度更新公式进行修正。修正后的公式已成为PSO 的标准版本，为大多数研究者所使用。惯性权重常被设置为随时间递减的时变权重来提高算法性能，如将权重设为1.4到0，0.9到0.4，0.95到0.2等。shi 和Eberhart 还提出一个模糊系统来一调节惯性权重，取得较好效果。
Kennedy 把Cl 和C2分别设置为0，得到了PSO 的“只有社会(social only)的模型”(Cl=0)，“只有认知(cognition only)的模型”(C2=0)和“无私(selfless)的模型”(C2=0，且自己的最好解不包含在邻域内)，并分析了几种模型的表现。Suganthan 的研究表明C1和C2为常数时可以取得较好的解，但不一定为2。有研究者在实验中将C1和C2取为1.494，1.7等。EI 一Gallad 等对种群规模，迭代次数和粒子速度的选择进行了分析并给出选择的基本原则，并通过对约束问题的求解来验证这些参数的基本影响。
在算法的拓扑结构研究方面，Angeline发现PSO可以比其他演化算法更快找到较好解，但后期精确搜索性能不好，为此suganthan引入一个变化的邻域算子(neighborhood operator)来改善解的质量，在优化初始阶段，粒子邻域就是其本身，随着迭代次数增加，邻域逐渐增大，直至包括所有粒子。基本PSO算法中邻域是基于索引号划分的，Suganthan使用了基于空间位置划分的方案，称为空间邻域(space neighborhoods)法。Kennedy对几种拓扑结构的实验表明拓扑非常影响算法性能，且最佳拓扑结构因问题而定。Knenedy还提出了混合空间邻域和环形拓扑方法的局部PSO 版本，称为社会趋同(social stereotyping)法。Kennedy和Mendes系统分析了不同的拓扑结构对算法性能的影响，说明了构造种群结构的基本原则。
为克服早熟现象，保持粒子群体的多样性是提高算法性能的重要途径，很多学者对此进行了研究。Riget和Vestersrtom将排斥过程引入标准PSO，通过多样性度量控制种群特征，从而实现粒子间吸引和排斥平衡以避免早熟现象。Lovbjerg和Krink 将自组织临界控制引入PSO来增加种群的多样性，实验结果表明可以使算法有更快收敛速度和找到更好的解。Krink等还提出一种粒子空间扩展的方法来解决粒子间的冲突和聚集问题，并增强了粒子逃脱局优的能力。Al一kazemi和Mohan通过在求解离散和连续问题的不同阶段设置不同的阶段性目标建立了多阶段(multi一phase)PSO，这种算法在实验中表现出比标准PSO，GA和进化规划更好的性能。Xie等将负嫡(negative entropy)概念引入标准PSO，通过将混沌因素加入到粒子更新过程建立了开放消耗系统，两个多峰函数的优化实验结果表明了其有效性。
在PSO和其他算法的融合以及性能的比较方面，也有很多研究成果出现。Angeline 提出了采用进化计算中的选择操作的混合PSO(HPSO)模型。Lovbjerg等将PSO与进化算法的思想融合，通过将繁殖和子种群的概念引入PSO，建立了两种混合型粒子群优化器，获得了更快的收敛速度和发现更好解的潜力。Natasuki等提出了带有高斯变异的PSO算法。Eberhart和shi将PSO与标准GA进行了分析和性能比较。国内也有很多学者进行了这方面的研究，提出了基于模拟退火的PSO算法，免疫粒子群算法，基于群体适应度方差自适应变异的PSO算法，将PSO与差别进化算法结合等。
PSO最初多用于解决连续优化问题，Eberhart和Kennedy又提出了PSO的离散二进制版本，用于解决组合优化问题。Knenedy和spears还利用多峰问题产生器把PSO的二进制版本和三种版本的GA进行了比较。Mohan等提出了几种二进制方法，但是实验有
限，没有得到确定性的结论。Hu等介绍了解决数列问题的改进PSO。目前关于PSO的离散版本的研究还很有限，并没有一个较好的解决方案，离散变量如何进行加法和乘法处理是个严重的问题，并且离散型PSO非常容易陷入局优。
（2）应用研究现状
PSO最早应用于非线性连续函数的优化和神经元网络的训练，后来也被用于解决约束优化问题。Eberhart用PSO来分析人类的帕金森综合怔等颤抖类疾病。Yoshida等通过PSO对各种离散个连续变量的优化，达到控制核电机组输出稳定电压的目的。Robinson 等将PSO用于剖面波状喇叭天线的优化，并与GA的优化效果进行了比较，研究了二者混合应用的可行性。
Ciuprina提出一种智能PSO(Intelligent PSO)用于电磁线圈尺寸的优化。Abido将
PS0用于解决最优功率通量(OPF)问题。国内也有越来越多的学者关注PSO的应用，将其应用于非线性规划，同步发电机辩识，车辆路径，约束布局优化，新产品组合投入，广告优化，多目标优化等问题。
还有一些学者尝试将PSO算法应用于解决动态优化问题，也取得了较好效果。PSO 由于其算法的简单，易于实现，无需梯度信息，参数少等特点在连续非线性优化问题和组合优化问题中都表现出良好的效果。在多目标优化、数据分类、数据聚类、模式识别、电信QOS管理、生物系统建模、流程规划、信号处理、机器人控制、决策支持以及仿真和系统辩识等方面，都表现出良好的应用前景。
2.7 标准粒子群优化算法存在的问题
根据文献和我们进行实验得到的结果，将标准PSO算法在优化过程中表现出来的问题总结如下:
(l)参数控制：对不同的问题，如何选择合适的参数来达到最优效果。
(2)缺乏速度的动态调节：爬山能力不强，有时在达到一定的精度后，很难再找到更好的解。
(3)早熟:粒子群过早收敛，使寻优停滞。
3 带有梯度加速的粒子群算法
3.1引言
标准PSO 算法具有很强的通用性，适用于各种优化问题，特别是实优化问题。但是这种广泛的适应性也导致对具体问题的特性考虑不够，比如没有考虑很多问题中有效的梯度信息。也有研究表明标准PSO 算法与遗传算法相比，早期的迭代表现较好，能够更快的发现质量好的解存在的区域。但是后期迭代搜索效率不高。这是因为标准粒子群优化缺乏速度的动态调节，爬山能力不强。针对如上问题，本文提出一种带有梯度加速的PSO 算法，对标准PSO 算法进行了改进。在粒子的速度更新中以一定概率加入梯度信息，使粒子的移动更有针对性，移动更有效率。同时为了减小粒子陷入局优的可能性，对群体最优值进行观察。在寻优过程中，当最优信息出现停滞时，对部分粒子进行重新初始化，从而保持群体的活性。通过实验对带有梯度加速的PSO 算法的适用范围进行了讨论。
3.2带有梯度加速的粒子群算法
3.2.1原理与步骤
与其他进化算法一样，标准PSO 算法利用种群进行随机搜索，没有考虑具体问题的特性，不使用梯度信息，而梯度信息往往包含目标函数的一些重要信息． 对于函数()f x ,12(,,...,)n X X X X =其梯度可表示为12()()()()[
,,...,]n
T f x f x f x f x x x x δδδδδδ?=函数值的最速下降方向是负梯度方向。
带有梯度加速的粒子群算法的思想：通过引入梯度信息来影响粒子速度的更新，构造出一种带有梯度加速的PSO 算法．每次粒子进行速度和位置更新时，每个粒子以概率P 按式(2.5)和式(2.6)更新，并以概率(1一P)按梯度信息更新，在负梯度方向进行一次直线搜索来确定移动步长。直线搜索采用黄金分割法，这一步骤可以详述如下： 产生一伪随机数，若大于P ，则按照公式（2.5）和（2.6）更新粒子速度和位置； 否则，①试探方式确定一单谷搜索区间{a ，b }
②计算2()t a b a β=+-，22()f f t =
③计算12t a b t =+-， 11()f f t =
④若12t t ε-<，（ε为终止限），则122
t t +即为粒子的下一位置；否则转⑤ ⑤判别12f f ≤是否满足，若满足，则置2a t =，21t t =，21f f =，然后转③；否则若12f f >，则置1b t =，12t t =，12f f =，2()t a b a β=+-，22()f f t =，然后转④。
同时，为防止陷入局优，在群体最优信息陷入停滞时，对群体进行部分重新初始化，以保持群体的活性，减小群体陷入局优的可能性。
梯度信息的加入使粒子的移动更具针对性和效率，进一步提高了PS0算法的收敛速度，但也会增加算法对问题的依赖性，特别是有些梯度信息极易将粒子引入局优。所以带有梯度加速的PSO 算法需要根据问题的性质来调整梯度信息对于粒子移动的影响程度。
综上，带有梯度加速的PSO 算法主要步骤如下：
1)在初值范围内随机初始化粒子种群，包括随机位置和速度
2)评价每个粒子的适应值
3)将每个粒子的适应值与其经历过的最好值进行比较，如果更好，则将其作为当前粒子的个体最优值
4)将每个粒子的个体最优值与群体最优值进行比较，如果更好，则将其作为群体最优值；若规定迭代次数内群体最优值未得到更新，则按一定概率将部分粒子重新初始化
5)对于每个粒子的速度和位置，以概率P 按（2.5）和（2.6）更新，并以概率 (1一p)按梯度信息更新，在负梯度方向进行一次直线搜索来确定移动步长
6)若未达到终止条件，则转步骤2)
3.2.2梯度加速的流程图
改进PSO 算法的梯度加速过程体现在上面的第5步，为直观说明，这里将其详细表示为图3.1：
图3.1梯度加速的流程图
3.3实验与结果分析
3.3.1实验设置
为了对标准PSO 算法和带有梯度加速的PSO 算法进行比较，并对改进后算法的问题依赖性进行研究，这里采用2个测试函数Schaffer ’s f6函数和Sphere 函数。 2
)n x x =∑
标准PSO 算法及带有梯度加速的PSO 算法分别选取种群30和种群10并选取不同的惯性权重(这里均采用时变权重)，为了全面比较优化效果，采用两种停止准则: 用两种停止准则:
(1)是否达到规定的达优值(观察其达优率、平均迭代次数及平均计算
时间);
(2)迭代4000次(观察其取得的最优值)。
改进PSO算法中，当20次迭代未取得更好的群体最优值时，认为群体最优信息陷入停滞，在粒子群体中随机选取30%进行重新初始化，重新初始化的方式为在初值范围内随机产生一个新的粒子代替原粒子。对于每个粒子的速度和位置以概率1%按照梯度信息进行更新。每种参数情况两种算法各运行100次。
3.3.2实验结果
将对两个函数的优化结果列于表1和表2。表中符号意义为:SPSO表示标准PSO，PISO表示改进PSO即带有梯度加速的PSO。惯性权重标明的是时变权重取值范围，递减率均设为:变化范围/1000。迭代次数为平均迭代次数。运行时间为平均运行时间，单位为秒。
表1 两种PSO算法对Schaffer’s f6的优化结果
Schaffer’s f6
表2 两种PSO算法对Sphere的优化结果
Sphere
3.3.3实验分析
sphere为单峰函数，改进PSO算法对这个函数的优化效果优于标准PSO算法, Schaffer’s是多峰函数，改进PSO算法也可以取得更好的优化效果。特别是在不同的惯性权重设置下都能够取得更好的达优率，迭代4000次所取得的最优值也都比标准PSO有很大的改进。由于要计算梯度，改进算法每次迭代计算时间要长于标准PSO算法，但是由于达优率的提高，对于，Schaffer’s、sphere基本上平均运行时间要小于标准PSO算法(Sphere效果最好)。在种群10下上述结论仍然成立，并且表现的更加明显，改进的PSO算法仍然有不错的达优率，并且种群的减小直接导致计算时间的大幅缩短。由于篇幅原因种群10下的结果这里没有列出。
从上述结果我们可以看出，带有梯度加速的PSO算法有很小的问题依赖性，梯度以1%的概率对粒子的更新施加影响对所有例子都可以取得更好的效果。并且，由于梯度信息可以使粒子的搜索更有效率，使改进算法的种群依赖性减小。
基本粒子群算法的原理和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研究的背景和意义 技术的不断向前发展，人们越来越多地利用计算机来获取和处理视觉图像信息。据统计，人类
粒子群算法综述 【摘要】：粒子群算法(pso)是一种新兴的基于群体智能的启发式全局搜索算法，具有易理解、易实现、全局搜索能力强等特点，倍受科学与工程领域的广泛关注，已得到广泛研究和应用。为了进一步推广应用粒子群算法并为深入研究该算法提供相关资料，本文对目前国内外研究现状进行了全面分析，在论述粒子群算法基本思想的基础上，围绕pso的运算过程、特点、改进方式与应用等方面进行了全面综述，并给出了未来的研究方向展望。 【关键词】：粒子群算法优化综述 优化理论的研究一直是一个非常活跃的研究领域。它所研究的问题是在多方案中寻求最优方案。人们关于优化问题的研究工作，随着历史的发展不断深入，对人类的发展起到了重要的推动作用。但是，任何科学的进步都受到历史条件的限制，直到二十世纪中期，由于高速数字计算机日益广泛应用，使优化技术不仅成为迫切需要，而且有了求解的有力工具。因此，优化理论和算法迅速发展起来，形成一门新的学科。至今已出现线性规划、整数规划、非线性规划、几何规划、动态规划、随机规划、网络流等许多分支。这些优化技术在诸多工程领域得到了迅速推广和应用，如系统控制、人工智能、生产调度等。随着人类生存空间的扩大，以及认识世界和改造世界范围的拓宽，常规优化法如牛顿法、车辆梯度法、模式搜索法、单纯形法等已经无法处理人们所面的复杂问题，因此高效的
优化算法成为科学工作者的研究目标之一。 1.粒子群算法的背景 粒子群算法(particle swarm optimization，pso)是一种新兴的演化算法。该算法是由j.kennedy和r.c.eberhart于1995年提出的一种基于群智能的随机优化算法。这类算法的仿生基点是：群集动物(如蚂蚁、鸟、鱼等)通过群聚而有效的觅食和逃避追捕。在这类群体的动物中，每个个体的行为是建立在群体行为的基础之上的，即在整个群体中信息是共享的，而且在个体之间存在着信息的交换与协作。如在蚁群中，当每个个体发现食物之后，它将通过接触或化学信号来招募同伴，使整个群落找到食源；在鸟群的飞行中，每只鸟在初始状态下处于随机位置，且朝各个方向随机飞行，但随着时间推移，这些初始处于随机状态的鸟通过相互学习(相互跟踪)组织的聚集成一个个小的群落，并以相同的速度朝着相同的方向飞行，最终整个群落聚集在同一位置──食源。这些群集动物所表现的智能常称为“群体智能”，它可表述为：一组相互之间可以进行直接通讯或间接通讯(通过改变局部环境)的主体，能够通过合作对问题进行分布求解。换言之，一组无智能的主体通过合作表现出智能行为特征。粒子群算法就是以模拟鸟的群集智能为特征，以求解连续变量优化问题为背景的一种优化算法。因其概念简单、参数较少、易于实现等特点，自提出以来已经受到国内外研究者的高度重视并被广泛应用于许多领域。
摘要 在智能领域，大部分问题都可以归结为优化问题。常用的经典优化算法都对问题有一定的约束条件，如要求优化函数可微等，仿生算法是一种模拟生物智能行为的优化算法，由于其几乎不存在对问题的约束，因此，粒子群优化算法在各种优化问题中得到广泛应用。 本文首先描述了基本粒子群优化算法及其改进算法的基本原理,对比分析粒子群优化算法与其他优化算法的优缺点，并对基本粒子群优化算法参数进行了简要分析。根据分析结果,研究了一种基于量子的粒子群优化算法。在标准测试函数的优化上粒子群优化算法与改进算法进行了比较,实验结果表明改进的算法在优化性能明显要优于其它算法。本文算法应用于支持向量机参数选择的优化问题上也获得了较好的性能。最后,对本文进行了简单的总结和展望。 关键词：粒子群优化算法最小二乘支持向量机参数优化适应度
目录 摘要...................................................................... 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)
基本粒子群算法的原理和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 。
对于函数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
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 ==，它是优化问题的一个潜在
t0=clock; >>citys=[565 575;25 185;345 750;945 685;845 655;880 660;25 230;525 1000;580 1175;650 1130;1605 620;1220 580;1465 200;1530 5;845 680;725 370;145 665;415 635;510 875;560 365;300 465;520 585;480 415;835 625;975 580;1215 245;1320 315;1250 400;660 180;410 250;420 555;575 665;1150 1160;700 580;686 595;685 610;770 610;795 645;475 960;95 260;875 920;700 500;555 815;830 485;1170 65;830 610;605 625;695 360;1340 725;1740 245]; >> n=size(citys,1); >> D=zeros(n,n); >> for i=1:n for j=1:n if i~=j D(i,j)=sqrt(sum(citys(i,:)-citys(j,:).^2)); else D(i,j)=1e-4; end end end >> m=31; >> alpha=1; >> beta=5; >>vol=0.2; >> Q=10;
>>Heu_F=1./D; >> Tau=ones(n,n); >> Table=zeros(m,n); >>iter=1; >>iter_max=100; >>Route_best=zeros(iter_max,n); >>Length_best=zeros(iter_max,1); >>Length_ave=zeros(iter_max,1); >>Limit_iter=0; >> while iter<=iter_max start=zeros(m,1); for i=1:m temp=randperm(n); start(i)=temp(1); end Table(:,1)=start; citys_index=1:n; for i=1:m for j=2:n tabu=Table(i,1:(j-1)); allow_index=~ismember(citys_index,tabu); allow=citys_index(allow_index)
基于粒子群优化算法的神经网络在农药定量构效关系建模中的应用 张丽平 俞欢军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
粒子群算法介绍 优化问题是工业设计中经常遇到的问题,许多问题最后都可以归结为优化问题. 为了解决各种各样的优化问题,人们提出了许多优化算法,比较著名的有爬山法、遗传算法等.优化问题有两个主要问题:一是要求寻找全局最小点,二是要求有较高的收敛速度. 爬山法精度较高,但是易于陷入局部极小. 遗传算法属于进化算法( Evolutionary Algorithms) 的一种,它通过模仿自然界的选择与遗传的机理来寻找最优解. 遗传算法有三个基本算子:选择、交叉和变异. 但是遗传算法的编程实现比较复杂,首先需要对问题进行编码,找到最优解之后还需要对问题进行解码,另外三个算子的实现也有许多参数,如交叉率和变异率,并且这些参数的选择严重 影响解的品质,而目前这些参数的选择大部分是依靠经验.1995 年Eberhart博士和kennedy博士提出了一种新的算法;粒子群优化(Particle Swarm Optimization -PSO) 算法. 这种算法以 其实现容易、精度高、收敛快等优点引起了学术界的重视,并且在解决实际问题中展示了其优越性。 粒子群优化(Particle Swarm Optimization - PSO) 算法是近年来发展起来的一种新的进化算法( Evolutionary Algorithm - EA) .PSO 算法属于进化算法的一种,和遗传算法相似,它也是从随机解出发,通过迭代寻找最优解,它也是通过适应度来评价解的品质. 但是它比遗传算法规则更为简单,它没有遗传算法的“交叉”(Crossover) 和“变异”(Mutation) 操作. 它通过追随 当前搜索到的最优值来寻找全局最优。 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) 也是起源对简单社会系统的模拟. 最初设想是模拟鸟群觅食的 过程. 但后来发现PSO是一种很好的优化工具.
粒子群算法原理及其在函数优化中的应用 1粒子群优化(PSO)算法基本原理 1.1标准粒子群算法 假设在一个D 维的目标搜索空间中，有 m 个代表问题潜在解的粒子组成一 个种群x [X i ,X 2,...,X m ],第i 个粒子的信息可用D 维向量表示为 X i [X ii , X i2,..., X iD ]T ，其速度为V i [V ii ,V i2,...,V iD ]T 。算法首先初始化m 个随机粒 子，然后通过迭代找到最优解。每一次迭代中，粒子通过跟踪2个极值进行信息 交流，一个是第i 个粒子本身找到的最优解，称之为个体极值，即 P i [P il , P i2,...,厢]丁 ；另一个是所有粒子目前找到的最优解，称之为群体极值， 即P g [P gi ,P g2,..., P gD 「。粒子在更新上述2个极值后，根据式(1)和式(2)更新自 己的速度和位置。 t 1 t t t t t\ V i WV i C 1「1（P i X i ） C 2「2（P g X i ） 式中，t 代表当前迭代次数，「1,「2是在[0,1]之间服从均匀分布的随机数，C 1,C 2 称为学习因子，分别调节粒子向个体极值和群体极值方向飞行的步长， w 为惯性 权重，一般在0.1~0.9之间取值。在标准的PSO 算法中，惯性权重w 被设为常数, 通常取w 0.5。在实际应用中，x 需保证在一定的范围内，即x 的每一维的变化 范围均为[X min ,X max ],这在函数优化问题中相当丁自变量的定义域 1.2算法实现步骤 步骤1:表示出PSO 算法中的适应度函数fitness(x)；(编程时最好以函数的 形式保存，便丁多次调用。) 步骤2:初始化PSO 算法中各个参数(如粒子个数，惯性权重，学习因子， 最大迭代次数等)，在自变量x 定义域内随机初始化x ，代入fitness(x)求得适应 度值，通过比较确定起始个体极值P i 和全局极值P g 。 步骤3:通过循环迭代更新x 、p i 和p g : ① 确定惯性权重w 的取值(当w 不是常数时)。 ② 根据式(1)更新粒子的速度V ：1,若速度中的某一维超过了 V max ，则取为 V max - ③ 根据式(2)更新自变量x ,若x 的取值超过其定义域，则在其定义域内重新 初t 1 X i t t 1 X i V i
1 绪论 最优化问题是在满足一定约束条件下，寻找一组参数值，以使某些最优性度量得到满足，即使系统的某些性能指标达到最大或者最小。它广泛存在于农业、国防、工程、交通、金融、化工、能源、通信、材料等许多领域。最优化技术在上述领域的应用已经产生了巨大的经济效益和社会效益。国内外的实践表明，在同样条件下，经过优化技术的处理，对系统效率的提高、能耗的降低、资源的合理利用及经济效益提高均有显著的效果，而且随着处理对象规模的增大，这种效果也更加显著。传统的优化方法根据问题的性质不同，通常将问题划分为线性规划问题、非线性规划问题、整数规划问题和多目标规划问题。相应的有一些成熟的常规算法，如应用于线性规划问题的单纯形法，应用于非线性规划的牛顿法、共轭梯度法等，应用于整数规划的分枝定界法、动态规划法等。 目前，基于严格机理模型的开放式方程建模与优化已成为国际上公认的主流技术方向。许多工程公司和各大科研机构纷纷投入大量的人力物力对系统的建模与优化进行深入细致的研究，希望取得突破性的进展。然而，基于严格机理模型所得到的优化命题往往具有方程数多、变量维数高、非线性强等特点，这使得相关变量的存储、计算及求解都相当困难。在国民经济的各个领域中都存在着相当多的涉及因素多、规模大、难度高和影响广的优化命题，如流程工业系统优化、运输中的最优调度、生产流程的最优排产、资源的最优分配、农作物的合理布局、工程的最优设计以及国土的最优开发等等，所有这些问题的解决也必须有一个强有力的优化工具来进行求解。而前述传统的优化算法面对这样的大型问题已无能为力，无论是在计算速度、收敛性、初值敏感性等方面都远不能满足要求。 人们从生命现象中得到启示，发明了许多智能的优化方法来解决上述复杂优化问题。例如遗传算法(Genetic Algorithm)参考了生物种群通过遗传和自然选择不断进化的功能、人工免疫系统(Artificail Immune Systems)模拟了生物免疫系统的学习和认知功能、蚁群优化(Ant colony Optimization)算法模仿了蚂蚁群体在路径选择和信息传递方面的行为，粒子群优化（Particle swarm optimization)算法模拟了鸟群和鱼群觅食迁徙中个体与群体协调一致的机理，群落选址算法(colony Location Algorithm)模拟了植物群落的形成机制等，这类借鉴模拟了生命系统的行为、功能和特性的科学计算
//#pragma warning (disable: 4786) //#pragma comment (linker, "/STACK:16777216") //HEAD #include
const double W_VAL = 0.729;/// struct SO{ int x, y; SO(){} SO(int x, int y): x(x), y(y){} }; struct Point{ double x, y; Point(){} Point(int x, int y):x(x), y(y){}; void read() { scanf("%lf%lf", &x, &y); } }; inline int randomI(int x){ return rand()%x; } inline double randomD(){ return (double)rand()/RAND_MAX; } inline double getDist(Point a, Point b) { return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); } struct PSO{ double w; int scale; int cityNum;
4.1粒子群算法基本原理 粒子群优化算法昭最原始的工作可以追溯到1987年Reynolds对鸟群社会 系 统Boids （Reyn olds对其仿真鸟群系统的命名）的仿真研究。通常，群体的行 为可以由几条简单的规则进行建模，虽然每个个体具有简单的行为规则，但是却 群体的行为却是非常的复杂，所以他们在鸟类仿真中，即Boids系统中采取了下 面的三条简单的规则： （1 ）飞离最近的个体（鸟），避免与其发生碰撞冲突； （2）尽量使自己与周围的鸟保持速度一致； （3）尽量试图向自己认为的群体中心靠近。 虽然只有三条规则，但Boids系统已经表现出非常逼真的群体聚集行为。但Reynolds仅仅实现了该仿真，并无实用价值。 1995 年Kennedy [46-48]和Eberhart在Reynolds等人的研究基础上创造性地提出了粒子群优化算法，应用于连续空间的优化计算中。Kennedy和Eberhart在 boids中加入了一个特定点，定义为食物，每只鸟根据周围鸟的觅食行为来搜寻食物。Kennedy和Eberhart的初衷是希望模拟研究鸟群觅食行为，但试验结果却显示这个仿真模型蕴含着很强的优化能力，尤其是在多维空间中的寻优。最初 仿真的时候，每只鸟在计算机屏幕上显示为一个点，而“点"在数学领域具有多 种意义，于是作者用"粒子（particle ）"来称呼每个个体，这样就产生了基本 [49] 的粒子群优化算法。 假设在一个D维搜索空间中，有m个粒子组成一粒子群，其中第i个粒子 的空间位置为X （ x , x ,x，…,x ） i 1,2,..., m，它是优化问题的一个潜在解， i i1 i 2 i 3 iD 将它带入优化目标函数可以计算出其相应的适应值，根据适应值可衡量X的优 i
2007年第2期空间电子技术收稿日期：2006-04-03；收修改稿日期：2006-04-30 粒子群算法和蚁群算法的结合及其在 组合优化中的应用 张长春苏昕易克初 （西安电子科技大学综合业务网国家重点实验室，西安710071） 摘要文章首次提出了一种用于求解组合优化问题的PAAA 算法。该算法有效地 结合了粒子群算法和蚁群算法的优点，先利用粒子群算法的随机性、快速性、全局性得到 初始信息素分布（即粗搜索），再利用蚁群算法的并行性、正反馈性、求解精度高等优点求 精确解（即细搜索）。将文中提出的算法用于经典TSP 问题的求解，仿真结果表明PAAA 算 法兼有两种算法的优点，同时抛弃了各自的缺点。该算法在时间效率上优于蚁群算法，在 求精效率上优于粒子群算法，是综合了两种算法长处的一种新的启发式算法，达到时间性 能和优化性能上的双赢，获得了非常好的效果。 主题词蚁群算法粒子群算法旅行商问题PAAA 0引言 近年来对生物启发式计算（Bio-inspired Computing ）的研究，越来越引起众多学者的关注和兴趣，产生了神经网络、遗传算法、模拟退火、粒子群算法、蚁群算法等许多用于解决复杂优化问题的新方法。然而，面对各种问题的特殊性和复杂性，每种算法都表现出了自身的优势和缺陷，都存在时间性能和优化性能不能兼得的矛盾。 粒子群优化（Particie Swarm Optimization ，PSO ）算法[1， 2]是由Eberhart 和Kennedy 于1995年提出的一种全局优化算法，该算法源于对鸟群觅食行为的模拟。它的优势在于：（1） 算法简洁，可调参数少，易于实现；（2） 随机初始化种群，具有较强的全局搜索能力，类似于遗传算法；（3）利用评价函数衡量个体的优劣程度，搜索速度快；（4）具有较强的可扩展性。其缺点是：不能充分利用系统中的反馈信息，求解组合优化问题的能力不强。 蚁群算法[3，4]（Ant Coiony Optimization ，ACO ） 是由意大利学者M.Dorigo ，V.Maniezzo 和A.Coiorni 于20世纪90年代初提出的一种新型的智能优化算法，已经被应用到TSP 问题[5，6]、二次分配问题、工 件调度问题、图着色问题等许多经典组合优化问题中，取得了很好的效果。它的优点是：（1）采用一种正反馈机制，通过信息素的不断更新，达到最终收敛于最优路径上的目的；（2）是一种分布式的优化方法，易于并行实现；（3）是一种全局优化的方法，不仅可用于求解单目标优化问题，而且可用于求解多目标优化问题；（4）适合于求解离散优化问题；（5）鲁棒性强。但由于在算法的初始阶段信息素匮乏，所以求解速度较慢。 文章将粒子群算法和蚁群算法有机地结合，提出了PAAA 算法。它利用粒子群算法的较强的全局搜索能力生成信息素分布，再利用蚁群算法的正反馈机制求问题的精确解，汲取各自的优势，以达空间电子技术 SPACE ELECTRONIC TECHNOLOGY !"
粒子群算法原理及其在函数优化中的应用 1 粒子群优化（PSO ）算法基本原理 1.1 标准粒子群算法 假设在一个D 维的目标搜索空间中，有m 个代表问题潜在解的粒子组成一个种群12[,,...,]m =x x x x ，第i 个粒子的信息可用D 维向量表示为 12[,,...,]T i i i iD x x x =x ，其速度为12[,,...,]T i i i iD v v v =v 。算法首先初始化m 个随机粒子，然后通过迭代找到最优解。每一次迭代中，粒子通过跟踪2个极值进行信息交流，一个是第i 个粒子本身找到的最优解，称之为个体极值，即 12[,,...,]T i i i iD p p p =p ；另一个是所有粒子目前找到的最优解，称之为群体极值，即12[,,...,]T g g g gD p p p =p 。粒子在更新上述2个极值后，根据式(1)和式(2)更新自己的速度和位置。 11122()()t t t t t t i i i i g i w c r c r +=+-+-v v p x p x (1) 11t t t i i i ++=+x x v (2) 式中，t 代表当前迭代次数，12,r r 是在[0,1]之间服从均匀分布的随机数，12 ,c c 称为学习因子，分别调节粒子向个体极值和群体极值方向飞行的步长，w 为惯性权重，一般在0.1~0.9之间取值。在标准的PSO 算法中，惯性权重w 被设为常数，通常取0.5w =。在实际应用中，x 需保证在一定的范围内，即x 的每一维的变化范围均为min max [,]X X ，这在函数优化问题中相当于自变量的定义域。 1.2 算法实现步骤 步骤1：表示出PSO 算法中的适应度函数()fitness x ；（编程时最好以函数的形式保存，便于多次调用。） 步骤2：初始化PSO 算法中各个参数(如粒子个数，惯性权重，学习因子，最大迭代次数等)，在自变量x 定义域内随机初始化x ，代入()fitness x 求得适应度值，通过比较确定起始个体极值i p 和全局极值g p 。 步骤3：通过循环迭代更新x 、i p 和g p ： ①确定惯性权重w 的取值（当w 不是常数时）。 ②根据式(1)更新粒子的速度1k i +v ，若速度中的某一维超过了max V ，则取为 max V 。 ③根据式(2)更新自变量x ，若x 的取值超过其定义域，则在其定义域内重新
粒子群算法论文 SANY标准化小组 #QS8QHH-HHGX8Q8-GNHHJ8-HHMHGN#
粒子群算法的寻优算法 摘要：粒子群算法是在仿真生物群体社会活动的基础上，通过模拟群体生物相互协同寻优能力，从而构造出一种新的智能优化算法。这篇文章简要回顾了粒子群算法的发展历史；引入了一个粒子群算法的实例，对其用MATLAB进行编程求解，得出结论。之后还对其中的惯性权重进行了延伸研究，对惯性权重的选择和变化的算法性能进行分析。 关键词：粒子群、寻优、MATLAB、惯性权重 目录：
1.粒子群算法的简介 粒子群算法（Particle Swarm Optimization）是一种新的智能优化算法。谈到它的发展历史，就不得不先介绍下传统的优化算法，正因为传统优化算法自身的一些不足，才有新智能优化算法的兴起，而粒子群算法（PSO）就是在这种情况下发展起来的。 粒子群算法的研究背景 最优化是人们在科学研究、工程技术和经济管理等领域中经常遇到的问题。优化问题研究的主要内容是在解决某个问题时，如何从众多的解决方案中选出最优方案。它可以定义为：在一定的约束条件下，求得一组参数值，使得系统的某项性能指标达到最优（最大或最小）。传统的优化方法是借助于优化问题的不同性质，通常将问题分为线性规划问题、非线性规划问题、整数规划问题和多目标规划问题等。相应的有一些成熟的常规算法，如应用于线性规划问题的单纯形法，应用于非线性规划的牛顿法、共扼梯度法，应用于整数规则的分枝界定法、动态规划等。列举的这些传统的优化算法能够解决现实生活和工程上的很多问题，但工业和科学领域大量实际问题的困难程度正在日益增长，它们大多是根本无法在可接受的时间内找到解的问题。这类优化问题的困难性不仅体现在具有极大的规模，更为重要的是，它们多数是非线性的、动态的、多峰的、具有欺骗性的或者不具有任何导数信息。因此，发展通用性更强、效率更高的优化算法总是需要的。 起源 在自然界中，鸟群运动的主体是离散的，其排列看起来是随机的，但在整体的运动中它们却保持着惊人的同步性，其整体运动形态非常流畅且极富美感。这些呈分布状态的群体所表现出的似乎是有意识的集中控制，一直是许多研究者感兴趣的问题。有研究者对鸟群的运动进行了计算机仿真，他们通过对个体设定简单的运动规则，来模拟鸟群整体的复杂行为。 1986 年 Craig ReynolS 提出了 Boid 模型，用以模拟鸟类聚集飞行的行为，通过对现实世界中这些群体运动的观察，在计算机中复制和重建这些运动轨迹，并对这些运动进行抽象建模，以发现新的运动模式。之后，生物学家Frank Heppner 在此基础上增加了栖息地对鸟吸引的仿真条件，提出了新的鸟群模型。这个新的鸟群模型的关键在于以个体之间的运算操作为基础，这个操作也就是群体行为的同步必须在于个体努力维持自身与邻居之间的距离为最优，为此每个个体必须知道自身位置和邻居的位置信息。这些都表明群体中个体之间信息的社会共享有助于群体的进化。