苏州大学本科生毕业设计(论文)

前言 ........................................................... 1

第一章概述 ..................................................... 2

1.1 引言 ...................................................... 2

1.2 研究背景 .................................................. 2

1.2.1 人工生命计算 ............................................ 2

1.2.2 粒子群算法与遗传算法 .................................... 3

1.2.3 人工神经网络与粒子群优化算法 ............................ 3

第二章粒子群优化算法 ........................................... 5

2.1 基本粒子群优化算法 ........................................ 5

2.2 算法流程 .................................................. 5

2.3 基本粒子群优化算法的缺点及改进方法 ........................ 6

2.3.1 基本粒子群优化算法的缺点 ................................ 6

2.3.2 几种改进算法 ............................................ 6

2.3.2.1 标准粒子群优化算法 .................................... 6

2.3.2.2 带有收缩因子的粒子群优化算法 .......................... 7

2.3.2.3 采用微分扰动的粒子群 .................................. 8

2.3.2.4 带有小生境拓扑结构的粒子群优化算法 .................... 9

2.3.2.5 带有梯度加速因子的粒子群优化算法 ................... 10

第三章基于多种群的粒子群优化算法 .............................. 11

3.1 算法基本改进方法 ......................................... 11

3.2 算法伪代码 ............................................... 11

第四章实验分析 ................................................ 14

4.1 几种常用改进算法 ......................................... 14

4.2 标准测试函数 .............................................. 14

4.3 收敛速度实验分析 .......................................... 15

4.3.1 实验设置 ................................................ 16

4.3.2 实验结果 ................................................ 16

4.4 收敛性能实验分析 .......................................... 17

4.4.1 实验设置 ................................................ 17

4.4.2 实验结果 ................................................ 18

4.5 算法参数分析 ............................................. 19

4.5.1 实验设置 ................................................ 19

4.5.2 实验结果 ................................................ 20

第五章

5.1

5.2

5.3

第六章

6.1

6.2 基于多种群的粒子群优化算法的应用 ....................... 21 生产计划问题描述 ........................................ 21 实例 .................................................... 22 运行结果 ................................................ 23 总结与展望 ............................................. 24 课题总结 ................................................ 24 后续研究展望 ............................................ 24

参考文献 ........................................................ 25

致谢 ............................................................ 27

摘要

在智能领域，大部分问题都可以归结为优化问题。常用的经典优化算法都对问题有一

定的约束条件，如要求优化函数可微等，仿生算法是一种模拟生物智能行为的优化算法，

由于其几乎不存在对问题的约束，因此，得到广泛应用。

本文首先描述了基本粒子群优化算法及其几种改进算法的基本原理, 并对基本粒子群

优化算法参数进行了简要分析. 根据分析结果,提出了一种基于多种群的粒子群优化算法. 在5个标准优化函数上与基本粒子群优化算法及几种改进算法进行了比较, 实验结果表明

本文算法在优化多模式函数时性能明显要优于其它算法. 本文算法应用于生产计划安排问

题上也获得了较好的性能. 最后, 对本文进行了简单的总结和展望

关键词：粒子群优化，适应度，群智能

Abstract

In the field of artificial intelligence, most problems belong to the category of

optimization. The classical algorithms in common use are usually limited by certain optimizing problems such as the object optimization function, which has to be a continuous one. As bionic algorithm imitates the intellective actions of life free from the limits resulting from the optimizing problems, this kind of algorithm is commonly used.

At first place, this dissertation, basing on the particle swarm optimization,

illustrates the fundament of this algorithm. This paper also places emphasis on the analysis of parameter that may affect the performance of the algorithm. Also an introduction of improved algorithms and popular advanced improving strategies is shown, as well as the mastery of basic researching process and methods. According to the result of the analysis, the author put forward a new multi-swarms PSO algorithm to overcome the defects of the original. Through the simulation, the results show that, compared with other PSO variants, the algorithm proposed by the author has attained a better solution to the same problems. Finally, the paper gave some further expectations concerning the PSO algorithm research.

Keywords: Particle Swarm Optimization, Fitness , Group Intelligence

前言

优化是个古老的问题，其研究的问题是在众多方案中寻找最优方案。长期以来，优化

问题一直受到广泛关注, 是研究的热点问题。早在17世纪，英国Newton和德国Leibnitz

发明的微积分就蕴涵了优化的内容。而法国数学家Cauchy则首次采用最速梯度下降法解

决了无约束优化问题。后来针对约束优化问题又提出了Lagrange乘数法。人们关于优化问

题的研究工作，随着历史的发展不断深入。但是，任何科学的进步都要受到历史条件的限

制，直到二十世纪四十年代，由于科学技术突飞猛进的发展，尤其是高速数字计算机日益

广泛应用，使得优化问题的研究不仅成为一种迫切需要，而且有了求解的有力工具。因此，优化理论和算法迅速发展起来，成为一门新的学科。至今已出现线性规划、整数规划、非

线性规划、几何规划、动态规划、随机规划等许多分支。这些优化技术在实际应用中正发

挥越来越大的作用。

随着人们生存空间的扩大, 这些常规的优化方法已经无法处理人们所面对的复杂问

题。因此，高效的优化算法成为科学工作者的研究目标之一。本文研究的粒子群优化算法

(particle swarm optimization,简称PSO)是Kennedy和Eberhart源于群体智能和人类

认知学习过程而发展的一种智能优化算法。它与遗传算法(GA)同属群体优化技术，但PSO

比GA更简单、操作更方便。因此，PSO算法从诞生起，就引起了国内外学者的广泛关

注，并掀起了该方法的研究热潮，且在诸多领域得到了成功应用。但是，PSO的发展历史

尚短，在理论基础与应用推广上都还存在一些问题，如早熟，种群单一化等，有待于解决。

针对上述的问题，本文通过对PSO算法原理进行分析，在深入理解几种PSO改进算

法的基础上，对PSO存在的问题提出了新的改进方法，并将改进的算法应用于实际优化问

题中。

本文主要通过MATLAB7系列作为工作环境，实现算法以及相应的问题模拟。

全文共分五章。第一章概述，主要介绍PSO算法研究背景。第二章粒子群优化算法，

主要介绍PSO算法基本原理，简要分析PSO主要缺陷，并介绍几种常用的改进PSO方

法。第三章基于多种群的粒子群优化算法，针对PSO的主要缺陷提出相应改进策略，并

给出伪代码。第四章实验分析，为了检测本文算法性能，选择了三种常用改进PSO算法与

本文算法进行了实验比较, 并对实验结果进行了简要分析。同时对本文算法中主要参数设

置方法进行了实验分析，以给出算法参数设置指导思想。第五章基于多种群粒子群优化算

法的应用，本文算法被用于优化生产计划问题并得出结果。第六章对课题进行总结，并对

未来的改进进行展望。

第一章概述

1.1 引言

最优化问题是在满足一定约束条件下，寻找一组参数值，使得系统的某些性能指标达

到最大或者最小。它广泛的存在于农业，国防，工程，交通，金融，能源，通信，材料等

诸多领域。最优化技术在上述领域的应用已经产生了巨大的经济效益和社会效益。国内外

的实践证明，在同样条件下，经过优化技术的处理，对系统效率的提高，能耗的降低，资

源的合理利用及经济效益提高均有显著的效果，而且随着处理对象规模的增大，这种效果

也更加显著。但随着处理对象规模的增大，优化问题也越来越复杂，而经典的优化技术对

问题的约束比较大，如梯度下降法要求优化函数是可导等，因此，对于新型优化算法的研

究具有重要的意义。

1.2 研究背景

1.2.1 人工生命计算

人们从生命现象中得到启示，发明了许多智能的优化方法来解决复杂优化问题。现在

已有很多源于生物现象的计算技巧。例如，人工免疫[1]模拟生物免疫系统的学习和认知功

能，人工神经网络[2~6]是简化的大脑模型, 遗传算法[7]是模拟基因进化的过程。在计算智

能(computational intelligence)领域有两种基于群体智能swarm intelligence[8~13]的算

法，粒子群优化算法(particle swarm optimization)[14]和蚁群算法(ant colony optimization)。[9,13,15]蚁群优化算法模拟了蚂蚁群体在路径选择和信息传递方面的行为，而粒子群优化算法模拟群居动物觅食迁徙等群体活动中个体与群体协调合作的工作过程。这类借鉴了模拟生命系统行为功能和特性的科学计算方法称为人工生命计算。人工生命计

算包括两方面的内容，研究如何利用计算技术研究生物现象和研究如何利用生物技术研究

计算问题。人工神经网络，粒子群优化算法，遗传算法，蚁群优化算法等都属于人工生命

计算的范畴。

本文详细介绍的粒子群优化算法是其中的一种新兴计算方法。它同遗传算法类似，同

属随机迭代优化工具。同遗传算法等其他人工生命计算相比，粒子群算法概念简单，容易

实现，调节参数较少。目前粒子群算法越来越引起人们的关注。

1.2.2 粒子群算法与遗传算法

大多数迭代优化技术都有相似的流程：

1. 种群元素随机初始化。

2. 计算种群个体位置适应值(fitness value)。适应值体现与最优解的差异。

3. 种群依适应值进行相应演化。

4. 达到停止条件，停止，否则转2。

通过对上述步骤观察，可见粒子群算法和遗传算法有很多相似之处。两者都随机

初始化种群(遗传算法则是染色体)。使用适应函数评价系统，且根据其得出的结果进

行多次随机寻优。

然而，粒子群算法没有遗传算法中的交叉(cross over)和变异(mutation)行为。他

根据变化的粒子速度进行每一轮的搜索。再者，粒子群算法中的粒子还有一个重要的

特色，粒子具有记忆能力。

在搜索个体信息共享方面，粒子群算法和遗传算法的做法也是非常不同的。在遗

传算法中，其粒子个体染色体(chromosomes)俩俩之间共享信息，因此其整体是比较

均匀的向最优区移动。粒子群算法通过全局最优粒子指引其他粒子向本轮迭代最优位

置移动，这是一种单向的信息流动。对于第二种机制，较多情况下，算法可能具有更

快的收敛速度。

1.2.3 人工神经网络与粒子群优化算法

人工神经网络是基于生物学中神经网络的基本原理而建立的一种模仿人脑工作方式

的计算模型，可以被视为一种具有大量连接的并行分布式处理器，它可以通过学习获取知

识并解决问题，并且将知识分布存储在连接权中(对应生物神经元的突触)。由于人工神经

网络具有较强的自适应性，学习能力和大规模并行计算能力，目前已被广泛应用于各种研

究及实际工程领域中，如模式识别，信号处理，控制与优化，预测建模，通信等领域。

近年来，随着进化计算研究热潮的兴起，人们逐渐将进化计算与人工神经网络相结合，利

用各种进化方法去训练神经网络。由于进化算法具有较强的全局收敛能力和较强的稳定

性，且不需要借助问题的特征信息，如导数等梯度信息。因此，将两者相结合，不仅能发

挥神经网络的泛化映射能力而且能够提高神经网络的收敛速度和学习能力。进化计算用于

神经网络优化主要有两个方面：一是用于网络训练，即各层之间的连接权值；二是优化网

络的拓扑结构。具体的研究方法有如下三种：

1. 通过优化连接权值来训练神经网络

针对特定的神经网络，列出所有的神经元，并将所有的神经元可能存在的连接权值编

码成二进制编码或是实数码串表示的个体，随机生成这些码串的群体，按照常规的方法执

行进化操作。将新形成的码串解码构成神经网络，计算所有训练样本通过此神经网络产生

平均误差，以此来确定每一个体的适应度。这种方法思路简单，但是用于优化的计算量较

大尤其是在优化解决复杂问题的大规模神经网络时，随着神经元的怎多，连接权的总数也

随之增多，从而造成进化计算的搜索空间增大。

2. 优化神经网络的结构和学习规则

利用进化算法计算优化设计神经网络的结构，同时包括网络的学习规则以及与之关联

的参数。这种方法直接将未经训练的神经网络的结构模式和学习规则编码成码串表示的个

体，再执行进化操作。与前一种方法相比，器搜索空间相对较小，但是也存在着一定的缺

陷。在优化过程中，每个被选择的个体都必须解码成未经训练的神经网络，再经过传统的

训练以确定其连接权值，因此收敛速度较慢。

3. 同时优化神经网络的结构和连接权值

同时优化神经网络的结构和连接权值进行编码以进行优化。Vittorio曾提出粒度编码方

法来提高连接权值的优化精度，但是粒度控制同时会加剧个体适应度的不连续变化，从而

影响到算法的收敛速度。

采用进化算法去优化神经网络，比起基于梯度的BP学习算法，无论是精度还是速度

上，均有了很大的提高。然而，作为一种仿生的随机算法，进化计算本身有具有不可克服

的缺陷。比如进化计算中研究最为充分的遗传算法，虽然它可以用来求解各类复杂问题，

但总是难以克服过早收敛的缺点，同时在采用遗传操作进化时，需要的控制参数过多，尤

其是在优化神经网络的时候，优化过程总是难以控制。因此，为神经网络的优化寻求更简

单，更有效的全局优化函数，是优化领域中的一个研究热点。

第二章粒子群优化算法

2.1 基本粒子群优化算法

James Kennedy 和 Russell Eberhart 在1995年的IEEE International

Conference on Neural Networks and 6th International Symposium on Micromachine and Human Science 上分别发表了“Particle swarm optimization”(粒

子群优化) and “A new optimizer using particle swarm theory”(一种使用粒子群理论

的新优化器)的论文，标志着粒子群优化算法的诞生。设想有这样的一个场景：一群鸟在一

个只有一块食物的区域内随机的搜索食物。所有的鸟都不知道食物在哪里。但是他们知道

当前位置和食物的距离。那么最简单有效的寻找策略就是搜索目前和食物距离最小的鸟的

周围区域。PSO从这种模型中得到启示并用其解决优化问题。PSO中，每个优化问题的

解都是搜索空间中的一只鸟，我们称之为“粒子”。所有粒子都有一个由被优化函数决定

的适应度值（fitness value），每个粒子还有一个速度决定他们飞翔速度的大小和方向。随

即，粒子们会追随当前的最优粒子在解空间内搜索。PSO初始化为一群随机粒子（随机解）。其最终最优解通过若干轮迭代求得。每一次迭代，每一粒子通过两个因素进行自我更新（通

过取得新速度而取得新位置）：粒子自身寻解过程中的最佳解，我们称它为“自我意识”，它往往和算法的局部搜索性能有很大的关系，另一个因素我们称之为“群体智慧”，是整

个群体所找到的最佳解，在速度更新中他能带领整个群体向问题的全局最优靠拢，在个体

和群体的共同协作下算法可以取得最优解。可用下面的公式来表示粒子每轮的更新行为：

Vid(t+1)=Vid(t)+C1⨯Φ1⨯(Plid-Xid(t))+C2⨯Φ2⨯(Pgd-Xid(t)) (2.1)

Vid(t+1)=Xid(t)+Vid(t+1) (2.2)

其中，Vid为粒子速度，Xid为粒子位置，C1，C2称为学习因子或加速常量，φ1，φ2 （0，

1）区间内两个随机正数，Plid为个体意识（个体最佳解位置），pg为群体最佳解位置。

2.2 算法流程

1. 初始化，设定加速常数C1和C2，最大进化代数Tmax将当前进化代数置为 t = 1 ，

在定义空间Rn中随机产生m个粒子X1,X2,…,Xn，组成初始种群X(t),随机产生各粒子初速

度V1，V2,…,VS组成位移变化矩阵V(t)。

2. 计算种群中所有粒子的适应值，初始化每粒子pbest为当前粒子，设定种群的gbest

为当前种群的最优粒子。

3. 种群X(t)演化，对种群中的每一个粒子：

(1) 按(2.1),(2.2)式更新粒子的位置和速度。

(2) 计算粒子的适应值。

(3) 比较粒子的适应值和自身的最优值pbest。如果当前值比pbest更优，则更

新pbest为当前值，并更新pbest位置到n维空间中的当前位置。

(4) 比较粒子适应值与种群最优值。如果当前值比gbest更优，则更新gbest为

当前种群最优粒子。。

4. 检查结束条件，若满足，则结束寻优；否则，t = t + 1，转至 2.。结束条件为寻

优达到最大进化代数Tmax，或评价值小于给定精度。

2.3 基本粒子群优化算法的缺点及改进方法

2.3.1 基本粒子群优化算法的缺点

首先，通过实验发现，PSO的实施过程与他所采用的参数取值有较大的关系，这些参

数取值仍然是一个亟待解决的问题。通常认为，对于不同的问题算法参数设置是不同的。然而如何设置，则主要依赖设计者的经验, 目前还没有理论用于指导算法的参数设置。

其次，PSO应用于高维复杂问题优化时，往往会遇上早熟收敛的问题，也就是说，种

群还没有达到全局最优点时已经聚集到一点停滞不动。从公式(2.1)中可以会发现，基本粒

子群算法存在一些缺陷，即容易出现早熟收敛，Vid较小和|Plid-Xid|和|pg-Xid|也很小时，粒

子的速度就会受到抑制，从而导致算法搜索停滞不前。这种情况甚至会发生在搜索的早期，当粒子是当前全局最佳解的时候，就会引起|Plid-Xid|，|Pg-Xid|成为零。这些早熟收敛点，有

可能是局部极小点，也有可能是局部极小点临域的一个点。换句话说，早熟收敛并不能保

证算法收敛到局部极小点。因而，对算法早熟收敛行为处理也是算法改进的一个难点。

此外，PSO在接近或进入最优点区域时的收敛速度也比较缓慢。实际上对PSO的研

究发现，PSO早期收敛速度较快，但到了寻优的后期，其结果改进则不甚理想。这主要归

因于算法收敛到局部极小，缺乏有效的机制使算法保持多样性或逃离局部极小点。

2.3.2 几种改进算法

2.3.2.1 标准粒子群优化算法

为了改善基本PSO算法的收敛性能，Y.Shi与R.C.Eberhart在1998年的IEEE国

际进化计算学术会议上发表了题为“A Modified Particle Swarm Optimizer”[16]的论

文，首次在速度方程中引入了惯性权重的概念，即

Vid(t+1)=ω⨯Vid(t)+C1⨯Φ1⨯(Plid-Xid(t))+C2⨯Φ2⨯(Pgd-Xid(t)) (2.3) 式(2.3)中，w称为惯性权重，因此，基本PSO算法是惯性权重w = 1的特殊情况。惯性权重w使粒子保持运动惯性，使其有扩展搜索空间的趋势，有能力探索新的区域。

引入惯性权重w可清除基本PSO算法对速度最大值的需求，因为w本身具有维护全局和局部搜索能力的平衡的作用。这样，当速度最大值增加时，可通过减少w来达到平衡搜索。而w的减少可使得所需的迭代次数变少。从这个意义上看，可以将d维速度的最大值锁定为每维变量的变化范围，只对w进行调节。文献[6]建议w的取值范围为[0,1.4]。

对全局搜索，通常的好方法是在前期有较高的探索能力以得到合适的种子，而在后期有较高的开发能力以加快收敛速度。为此，可将w设定为随着进化迭代次数而线性减少，例如由0.9到0.4等。Y.Shi和R.C.Eberhart的仿真实验结果也表明w线性减少取得了较好的实验结果。在文献[14]中，这种线性的w可以模仿模拟退火的中的温度。（在某些情况下属实）在本文提出的算法中发现，有些情况下，对上轮迭代粒子速度给于不保留策略，能够有效提高整个种群的搜索能力。

2.3.2.2 带有收缩因子的粒子群优化算法

在Clerc[16,17]的研究中，提出了收缩因子的概念。该方法描述了一种选择w，c1和c2的值的方法，以确保算法收敛。通过正确的选择这些控制参数，就没有必要将粒子速度控制在速度的极值区间内。接下来首先讨论一个带有收缩因子的粒子群优化算法相关的收敛模式特例。

一个与某个收敛模式相符合的改进了的速率方程式以以下形式提出：

Vid(t+1)=X⨯(Vid(t)+C1⨯Φ1⨯(Plid-Xid(t))+C2⨯Φ2⨯(Pgd-Xid(t))) (2.4) 在这里X=2

2-1-l-4⨯l2且l =C1 + C2 = 4.1我们得出X = 0.7298并带入方程

(2.4)，同时省略参数t，结果为:

Vid(t+1)=0.7298⨯(Vid(t)+2.05⨯Φ1⨯(Plid-Xid(t))+2.05⨯Φ2⨯(Pgd-Xid(t))) (2.5)

因为2.05*0.7298 = 1.4962，所以这个方程式与在改进的PSO速率更新方程式使用C1 = C2 = 1.4962和w = 0.7298所得到的方程式是等价的。

Eberhart和Shi将分别利用速度极值和收缩因子来控制粒子速度的两种算法性能做了比较，结果表明，后者比前者通常具有更好的收敛率。然而在有些测试函数的求解过程

中，使用收缩因子的算法在给定的迭代次数内无法达到全局极值点。按照Eberhart和Shi的观点，这是由于粒子偏移所期望的搜索空间太远而造成的。为了降低这种影响，他们建议在使用收缩因子时首先对算法进行限定，比如使得速度极值等于搜索域极值或者预先设置搜索空间的大小这样可以改进算法对所有测试函数的求解性能——不管是在收敛率方面还是在搜索能力方面。

2.3.2.3 采用微分扰动的粒子群

Swagatam Das，Amit KonarUday，K. Chakraborty对于PSO的研究发现，通过从微分进化[18]中引入微分扰动[19]因子取代公式中(2.1)中粒子的个体意识部分。该因子形成于群体中随机选择的两个粒子的位置差异向量。同时，与标准PSO算法不同，在该算法中只有当粒子在新位置的适应度值优于原来位置时，粒子位置才会更新，具体描述如下：

在他们提出的算法中，对于每一个粒子i，随机选取两个不同于i且互不相同的粒子j，k。他们之间的差异用向量δ来表示。

δ=Xk-Xj (2.6)

第i个粒子的第d维速度更新公式为：

Vid(t+1)=ω⨯Vid(t)+β⨯δd+C2⨯ϕ2⨯(Pgd-Xid(t)),

if rand d (0,1)

=Vid(t) otherwise

CR是交叉选择概率，δd是(2.7)式中的差异向量δ的第d维分量。ß是在[0，1]上随机数，为了获得额外探索能力，公式(2.6)中向量微分运算符代替了粒子“个体意识”部分。当每轮迭代产生的随机概率时，算法使用(2.8)式更新粒子速度，从而得到新的位置Tr。

然而只有新位置体现出更好的适应值时，粒子才会变迁到那里。因此，如果在一个n

维搜索空间中寻找最小值。f(x1,x2,...,xn)=f(X) , 那么目标粒子的位置将会被更新为:

Xi(t+1)=Tr if(f(Tri)

Xi(t+1)=Xi(t) otherwise

即粒子只限于移动到更优的位置，或不动。粒子的位置始终为至今最佳解。另一方面，

为了保持粒子搜索活跃性。如果粒子在搜索域中变迟钝（如果他在预定迭代次数内停滞不前），该粒子就会被赋予一随机位置，具体方法如下：

if((Xi(t)=Xi(T+1))=Xi(t+2)=...=Xi(t+N))

and(f(Xi(t+N))≠f*))then

for(r=1ton)Xir(t+N+1)=Xmin+randr(0,1)⨯(Xmax-Xmin) (2.10)

在这里f* 是适应函数的全局最小值，N是该算法中设置的最大迭代次数,(Xmax，Xmin)定义算法每一轮所允许的搜索区域。

2.3.2.4 带有小生境拓扑结构的粒子群优化算法

基于粒子群优化算法中的局部优化模型，根据粒子的下标将粒子群体分割成若干个相邻的区域，也就是说，粒子x1和x2在一个半径为1的临近区域内可以看成是相邻的，而不管他们的空间位置如何，根据粒子的空间位置，每个粒子都会选出其特定的最佳邻居粒子，并用他和最佳邻居的差异向量代替标准PSO速度更新公式中的“个体意识部分”。

对于种群中每个粒子与临域粒子的拓扑结构，事实上，我们可以看到，PSO算法中的局部优化模型实际上就是一种简单的临域结构，其每个临域均由粒子的下标决定，而与粒子的具体位置无关。为了进一步改善算法性能，避免过早收敛的现象，J.Kennedy[20]在1999年提出几种基本的临域结构[21]，即环形结构和轮型结构及他们的推广。

环形结构是一种最基本的临域结构，在该结构中，每个粒子仅与其附近的两个粒子相互交流信息，从而能有效地保证种群的多样性。比如，对于粒子j而言，其临域为粒子j+1和j-1，从而其信息只能在这两个微粒中交流。这时，对于粒子k和2k而言，其信息的交流至少需要经过k步才能完成，从而能保证算法充分对每个区域进行搜索，而不至于陷入过早收敛的情形。此外这里的临域仅与粒子的下标有关，而与粒子的真实位置无关，从而可以有效的对搜索空间进行搜索，但有时会影响算法效率。作为该结构的推广，随机环形结构强调了信息交流的迟滞性，但对环形结构的临域仅有粒子下标决定的缺点做了一定的调整，其临域虽然主体仍由粒子下标决定，但存在两个粒子的临域可以随机选择，从而在一定程度上提高了算法效率，对算法速度与精度的调整起了平衡作用。

但环形结构的信息交流非常慢，因而即使是随机环形结构，有时其问题的求解也比较慢。此时，可以考虑使用轮型结构。在该结构中，每个临域不再仅仅是三个粒子了，而是若干个。其中一个为中心，其余的粒子都与他相邻。也就是说，在每个临域中，只有中心粒子与该临域中的所有粒子可以交换信息，这样提高了信息的传播速度，避免了信息的丢失，从而能更好的提高算法效率。

2.3.2.5 带有梯度加速因子的粒子群优化算法

这种算法以一定概率加入梯度信息[22]，使粒子的移动更具针对性和效率。为减小粒子陷入局部极小的可能性，对群体最优质进行观察。在寻优过程中，当最优信息出现停滞时，对部分粒子进行重新初始化，从而保持群体的活性。对于函数F（x）的梯度可以表示为他的一阶导数F'（x）。每次粒子进行速度和位置更新时，每个粒子以概率p按标准PSO速度更新公式更新，以（1 – p）按梯度信息更新，在负梯度方向进行一次直线搜索来确定速度，直线搜索采用黄金分割法。为防止陷入局部极小。在群体最有信息陷入停滞时，对群体进行部分重新初始化，以保持群体活性，减少群体陷入具有的可能性。

梯度信息的加入使粒子的移动更具有针对性和效率，进一步提高了PSO算法的收敛速度，但也会增加算法对问题的依赖性，特别是有些梯度信息极易将粒子引入局优。所以带有梯度加速的PSO算法需要根据问题的性质来调整梯度信息对于粒子移动的影响程度。

第三章基于多种群的粒子群优化算法

3.1 算法基本改进方法

为了解决粒子群优化算法中普遍存在的种群单一化，收敛早熟化问题，本文提出的基于多种群的粒子群优化算法在以下几个方面进行了改进：

a) 该算法基于带有微分扰动因子的粒子群优化算法。引入多种群并行进化概念，即

初始化多个种群进行同时并行进化，在约定条件下进行种群间信息交互。

b) 通过实验分析发现，对于多峰函数，该算法速度更新公式中，若不保留粒子的上

轮迭代速度即惯性权重恒定取0，同时将学习因子取为1.205，往往会取得较好的

收敛效果。

c) 对于原单种群带有微分扰动的粒子群算法新的算法加入搜索域防越界控制。

d) 该算法中，为防止各种群粒子由于相互交互而引发种群粒子趋于单一，本算法在

达到一定迭代次数后，将选择全局最优较差的若干种群进行重新初始化。

e) 根据带有微分扰动的算法，如果粒子行动停滞不前，则给于该粒子一个在初始化

定义域之间的随机位置。根据作者分析发现，该方法并不科学，因为根据粒子群

算法寻优原理，为了增大寻优成功率，随机位置的发放范围应有目的的缩小。于

是本算法将随机位置放置于当前种群全局最优的位置范围之内。

f) 对于粒子的速度和位置使用一种新的初始化方法使得有较好的初始化效果。具体

如下：

P_siton粒子位置

P_ciy 粒子速度

P_siton=(1-2 * rand) *max;

P_ciy=1-2*rand*max-P_siton / 2;

3.2 算法伪代码

begin

initialize the parameter of the algorithm and the population and the position value and velocity of each particle in each swarm.

initialize globe best position of each swarm

while stopping condition not satisfied do

evaluate and store the fitness of each particle of each swarm store in FITVueAry[particleNo,swarmNo]

calculate the average fitness value of all particle in each swarm and keep it in avgFIT[swarmNo]

sort FITVueAry[particleNo,swarmNo]

chooseNo = rand(swarmNo)

for iter = 1:swarmNo

for itt = 1: particleNo

if fitness(avgFIT[iter]) - fitness(pg[iter])

particle(best,iter) = particle(worst,chooseNo)// or particle(worst,iter) = particle(best,chooseNo) end

end

for each swarm

calculate new pg value

end

for particle_tag = 1:particleNo

particle_A = rand(particleNo)

particle_B = rand(particleNo)

Vector = |A-B|

randNumber = rand(0,1)

if rand_Number

V(t+1) = rand[0,1]*Vector+c2*rand[0,1]*(pg-x)

else

V(t+1) = V(t)

end

TR = X（t+1） + V(t+1)

if（fitness（TR）

X(t+1) = TR;

else

X(t+1) = X(t);

end

sortpg(dimension) = sort(pg)

if Xi stagnates for N successive generations

for r = 1 to no_of_dimensions

Xir(t+1) = Xmin + randr(0, 1)*(sortpg(1),sort(dimension))

end

if reach condition (may be run for 400 generation?)

reinitialize three worse swarms

end

第四章实验分析

为了验证本文算法的性能,我们把本文提出的基于多种群的粒子群优化算法与粒子群优化算法的几种常用改进算法进行了比较, 在实验中, 选择了5个常用的标准优化函数作为验证函数。本文从三个方面设计了三个不同实验,实验一，用于验证本文算法的收敛性能,实验二用于验证本文算法的收敛速度,实验三讨论了本文算法参数的设置方法.

4.1 几种常用改进算法

本文选择2.3.2节中已介绍的带有小生境因子的PSO算法，在该算法中，粒子速度更新公式中的“个体意识”部分中，粒子不再向自己个体的最佳位置移动，而向着周围多个粒子中的一个最佳粒子移动；带有微分扰动的PSO算法中引入了微分扰动因子(两随机粒子位置向量差)代替标准粒子群算法中“个体意识部分”，以及标准PSO算法与本文算法进行比较。

4.2 标准测试函数

为了与其他改进算法比较，本文使用五个常用标准测试函数来评价算法的性能，每函数都使用10维搜索空间。函数如下：

1． F1 De Jone's function 1

2x(i)∑ i=1D

最简单的函数，连续单峰函数。全局极小点在于f(0)=0;

2. F2 Axis parallel hyper-ellipsoid

2i⨯x(i)∑ i=1D

本函数与F1相似，它往往被称为带有权重的Sphere model，同时也是连续的单峰函数。全局极小点在于f(0)=0;

3. F3 Sum of different Powers

∑i=1D(i+1)x(i)

常用单峰测试函数

全局极小点在于f(0)=0;

4. F4 Rastrigin's function 6

210+x(i)-10⨯cos(2⨯3.14⨯x(i)) ∑i=1D

在F1函数的基础上增加了余弦调制从而产生了很多局部极小。因此本函数为高度多峰函数，其局部极小是规律分布的。

全局极小点在于f(0)=0;

5. F5 Schwefel's function 7

∑-x(i)⨯sii=`Dx(i)

本函数的全局最小在搜索空间几何分布上是较疏远的，它临于次全局最优点，据有欺骗性。因此对于某些寻优算法更有可能陷入局部极小中。

)=418.9829; 全局极小点在于f(420.9687

本文的所使用的测试函数的初始化均使用标准初始化范围，但是对于某些函数为使其展示方便期间，我将其初始化范围缩小为[-1,1]。对于所有的函数我们都使用10维的搜索空间，表4.1，展示了个函数的初始化范围和搜索空间。

表4.1函数初始化设置表格 4.3 收敛速度实验分析

为考察新算法寻优收敛速率，本实验利用4.1中引用的四种算法优化标准测试函数(五个)，由于优化结果存在随机性，为科学比较算法性能，每算法对于每个测试函数均取50次独立运行结果之平均值。对于每次运行，迭代1000次，(某些算法迭代次数少于1000，因为其很快便陷入局部极小而无法前进。)对于运行最终寻优结果取平均值(对于本实验，有效数据为每次迭代寻得的全局最优值。)。最后将保存的结果绘成图形进行比较，各算法在matlab7环境下实现。

4.3.1 实验设置

在种群规模设置方面，Eberhart和Shi表示种群的规模设置对于初始化PSO的函数搜索范围的性能很难有任何的改善。Van den Bergh和Engelbrecht提出，尽管增大粒子群的种群大小对于提高解质量的贡献微乎其微，但是一个更大的群体提高了一个函数评估的容错本领。在微分进化研究的实践中，我们常常将种群规模设定为十倍于搜索空间的维度。本实验将各算法种群规模根据特定情况设置为40或50。

4.3.2 实验结果

F1 De Jone's function 1

图4.1 F1的50收敛结果

F3 Sum of different Powers

图4.3 F3的50收敛结果

F2 Axis parallel hyper-ellipsoid 图4.2 F2的50收敛结果 F4 Rastrigin's function 6 图4.4 F4的50收敛结果

F5 Schwefel's function 7

图4.5 F5的50收敛结果

实验结果表明，与其他参与比较的算法相比，本文提出的算法往往在搜索的初期就能很快的向最佳位置收敛，具有最佳收敛速度。

4.4 收敛性能实验分析

为考察新算法寻优效果程度，本实验利用4.1中引用的四种算法优化标准测试函数(五个)，由于优化结果存在随机性，为科学比较算法性能，每算法对于每个测试函数均取50次独立运行结果之平均值。对于每次运行，迭代1000次，(某些算法迭代次数少于1000，因为其很快便陷入局部极小而无法前进)。通过各算法50次运行得出的50个最终寻优结果比较算法收敛精度，最后将结果保存并绘制图形进行比较，同样在matlab7环境下实现。

4.4.1 实验设置

与收敛速度实验采用相同的设置方法。在种群规模设置方面，Eberhart和Shi表示种群的规模设置对于初始化PSO的函数搜索范围的性能很难有任何的改善。Van den Bergh和Engelbrecht提出，尽管增大粒子群的种群大小对于提高解质量的贡献微乎其微，但是一个更大的群体提高了一个函数评估的容错本领。在微分进化研究的实践中，我们常常将种群规模设定为十倍于搜索空间的维度。本实验将各算法种群规模根据特定情况设置为40或50。

4.4.2 实验结果

F1 De Jone's function 1 F2 Axis parallel hyper-ellipsoid 图4.1 F1的50收敛结果

F3 Sum of different Powers

图4.3 F3的50收敛结果

F5 Schwefel's function 7

图4.5 F5的50收敛结果图4.2 F2的50收敛结果

F4 Rastrigin's function 6 图4.4 F4的50收敛结果

通过观察可以发现，本文算法对于各算法均有较好的寻优能力，而其对于多峰函数的搜索能力远远高于其他的对比算法。但是由于本算法粒子速度更新公式中粒子个体意识部分被删除导致该算法在某些迭代运算中会陷入局部极小问题中。并且在单峰函数的优化中取得的最终的优化解精度会比某些算法要差一些。表格统计了各算法对于五个函数50次优化最佳解的平均值。

表4.2收敛平均值 4.5 算法参数分析

本文算法中的某些参数如单种群规模的设置可能对算法的性能有重要的影响，于是通过实验求算法参数与性能的关系。

4.5.1 实验设置

利用F5 Schwefel's function 7做为算法参数设置评价函数，对于新算法中的以下4参数进行设置分析：

1.单种群规模，单种群粒子个数，对于种群规模分别取30，40，50。

2.种群数，分别取四个，五个，六个种群。

3.交换粒子时机，交换时机分别取30代，40代，50代。

4.每次交换的粒子数量，交换粒子数分别取15，20，25个。

4.5.2 实验结果

图4.11 种群交换粒子数分析图4.12种群交换时机

图4.13 种群规模图4.14 种群个数

通过对于本算法中几个关键参数设置不同的数值进行实验，在单种群规模实验中，我们发现参数分别设置在(15,20,25)时寻优效果波动不大。然而，实验表明每次交换15个粒子时效果最好；在种群数设置实验中，参数设置分别设置为(4,5,6)时效果几乎没有什么不同，数据表示，四个种群的设置具有微度优势；在种群规模参数设置中，参数分别取(30,40,50)，在每种群30个粒子有最好收敛效果；对于种群交换时机参数实验中，参数分别取(30,40,50)，参数取到50时，算法无法收敛至全局极小。参数取30效果最佳。

第五章基于多种群的粒子群优化算法的应用

生产计划问题是指在不同的需求和费用的情况下，确定生产速率。许多学者对这一问题进行了研究，如Federgruen和Schechner[23]，Liu[24]，Luss[25]，Moinzadeh和Nahmias[26]以及Wang，Wilson和Odrey[27]。以前的工作主要是解决离散时间的生产计划问题，解决连续时间情况的方法较少。最近Gen和Liu研究了连续时间的生产计划问题，并提出了一种解决这一问题的进化方法[28,29]。本文则同样使用所提出的多种群粒子群进化算法解决这一问题。

5.1 生产计划问题描述

为准确描述这一问题，先介绍一些概念：

z(t)——在时间t的生产速率；

r(t)——在时间t的需求率；

y(t)——在时间t的库存水平；

c(z)——生产速率为z时间单位生产费用；

g(dz/dt)——生产速率改变的单位时间费用；

l(y)——库存水平为y时间单位库存费用。

如果y0，l(y)是存储量为y时的单位时间的存储费用。

时间t的生产总量为

Z(t)=⎰z(τ)dτ (5.1) 0t

时间t的总需求为

R(t)=⎰z(τ)dτ (5.2) 0t

则有

y(t) = Z(t) – R(t) (5.3)

连续时间生产计划是最小化问题

T⎧dz(t)⎫J(z)=⎰⎨c(z(t))+g()+l(y(t))⎬dt (5.4) 0dt⎩⎭

即制定生产计划z(t)(时间t的函数)，使得J(z)为最小。

在这个模型中，我们假设生产速率在任何连续区间上可以是不同的。在解释费用函数J(z)Tdz的积分⎰g()dt时，需要注意的是我们不希望限定生产策略函数是可微的甚至是连续 0dt

的。如果z(t)在某些点上是不连续的，则dz/dt不能定义，且差分g(z(t+0))-g(z(t-0))将被看作是那一点的积分的基值。因此，该积分是连续的z(t)的积分与不连续点的积分基值的和。

如果每次改变生产速率时需要一个正的装设费用，则优化生产速率必须是一个阶梯函数，即生产速率在有限时间内改变，且在每个时间区间内是常数。

5.2 实例

我们考虑下述例子：需求率是

tr(t)=1+sin(4π), 0

单位时间生产费用函数为

c(z) = c*z (5.6)

单位时间生产速率改变费用函数为

g(dzdz (5.7) )=k+w∙dtdt

单位时间存储费用为

⎧h∙y,y≥0 (5.8) l(y)=⎨s∙(-y),y 0⎩

编码方式：

每个粒子必须具有生产计划的三个要素以便表达问题的解。问题解决之前，总改变次数n我们定义为已知的，由于具有这种情况，一个定长串[x1+x2+…+x2n]作为表达问题解的一个粒子，其中偶数下标元素x2i,i=1,2,…,n代表生产速率，奇数下标元素x2i-1,i=1,2,…,n代表时段i延续时间与计划展望期T的比率。

从粒子得到的解如下：

t0=0

ti=x1+x3+...+x2i-1∙T; i = 1,2, … ,n (5.9) x1+x3+...+x2n-1

zi = x2i; i = 1,2,…,n

从5.9式可以看出粒子可以产生可行解。

参数设置为：T=50，c=5，w=20，k=100，h=3，s=10，初始化库存水平为y(0) = 0，pop_size = 50。粒子在[0,1.78]上初始化。

图5.1总费用优化图图5.2生产需求累计图

图5.3 生产需求图图5.4 库存图

5.3 运行结果

图5.1表明在3000次迭代中费用收敛情况，其中对于生产计划在[0,2.9987]上，生产速率为1.6922。在 [2.9987,5.9723]上，生产速率为0.71606，生产计划在[5.9723,6.4374]上时，生产速率为1e-007，生产计划在[6.4374,6.6052]上时，生产速率为1.5045，生产计划在

[6.6052+1.6706e-007]上时，生产速率为1.0813。生产计划在

[6.6052+1.6706e-007,6.6052+2*1.6706e-007]上时，生产速率为1.78。生产计划在

[6.6052+2*1.6706e-007,8.4487]上时，生产速率为1e-007。生产计划在[8.4487,8.4553]上时，生产速率为1.6457。生产计划在[8.4553,10]上时，生产速率为1.78。最好的速率变化10次的最小费用为1042.13。生产速率与需求图见图5.2，需求生产累加值见图5.3。

第六章总结与展望

6.1 课题总结

这里基于研究工作进行总结，本课题基于基本粒子群算法，通过分析算法工作原理和以及已有改进算法改进策略，从而提出一种新的多种群粒子群改进算法。本文算法在函数优化，尤其是在多峰函数极值寻找方面表现较为出色。并且有效的应用于实际工程应用中。

6.2 后续研究展望

本文的算法，仍有较大改进余地，鉴于新算法消除了标准PSO中粒子的个体意识部分，算法求解结果往往很接近于全局极小值，结果精度还有待遇更一步的提高，这一点尤其体现在在单峰函数的优化中，且算法程序可以进一步简化以减少算法运行时间。新算法中核心策略，种群间粒子交换条件过于简单，傻瓜且趋于单一，今后改进可使用动态的具有指导性的交换条件，根据算法优化情况，进行特定粒子交换操作。

参考文献

[1] Dasgupta D. Artificial neural networks and artificial immune systems: similarities and

differences. 1997 IEEE International Conference on Computational Cybernetics and Simulation. Institute of Electrical and Electronics Engineers, Incorporated, 1997,873~878

[2] James W. Psychology (Briefer Course). New York: Holt, 1890

[3] McCulloch W, Pitts W. A Logical Calculus of the Ideas Imminent in Nervous Activity.

Bulletin of Mathematical Biophysics, 1943, 5:115-133

[4] Hopfield J, Tank D. 'Neural' Computation of Decisions in Optimization Problems. Biological

Cybernetics,1985,52:141-152

[5] Hopfield J, Tank D. Computing with Neural Circuits: a Model. Science, 1986,233:625-633

[6] McClelland J, Rumelhart D. Explorations in Parallel Distributed Processing. Cambridge,

MA:MIT Press 1988

[7] Koza J R. Genetic Programming: On the Programming of Computers by Means of Natural

Selection. MIT press, Cambridge, 1992

[8] Colorni A, Dorigo M, Maffioli F, Maniezzo V, Righini G, and Trubian M. Heuristics from

nature for hard combinatorial problems. International Transactions in Operational Research,1996,3(1):1~21

[9] Dorigo M and Di Caro G. The ant Colony Optimization meta-heuristic. In Corne D, Dorigo

M, and Glover F, New Ideas in Optimization. London: McGraw Hill, 1999, 11~32

[10] Bonabeau E, Dorigo M, and Theraulaz G. Swarm intelligence: from nature to artificial

systems. New York: Oxford University Press,1999

[11] Kennedy J, Eberhart R C, and Yuhui Shi. Swarm Intelligence. San Francisco: Morgan

Kaufmann, 2001. 512

[12] Steven Johnson. Emergence: The connected Lives of Ants, Brains, Cities, and Software.

New York Simon & Schuster Adult Publishing Group, 2002.288

[13] Dorigo M and Stutzle T. Ant Colony Optimization. MIT Press, 2004. 288

[14] Kennedy J, Eberhart R. C. Particle Swarm Optimization. In: Proc. IEEE Int' l. Conf. on

Neural Networks, IV. Piscataway, NJ: IEEE Service Center, 1995, 1942-1948

[15] Dorigo M, Di Caro G, and Gambardella L M. Ant algorithms for discrete optimization.

Artificial Life, 1999,5(2): 137~172

[16] PSO Shi Y, Eberhart R C. A Modified Particle Swarm Optimizer. In: Proceedings of the

IEEE International Conference on Evolutionary Computation. Piscataway, NJ: IEEE Press, 1998, 69-73

[17] Clerc M. The Swarm and the Queen: Towards a Deterministic and Adaptive Particle Swarm

Optimization. In: Proc. 1999 Congress on Evolutionary Computation. Washington, DC, Piscataway, NJ:IEEE Service Center, 1999, 1951-1957

[18] Swagatam Das, Amit KonarUday, K. Chakraborty, Improving particle swarm optimization

with differentially perturbed velocity, Electronics & Telecom Eng Dept, Jadavpur University, 2005.

[19] Storn, R., Price, K. Differential evolution – a simple and efficient heuristic for global

optimization over continuous spaces, Journal of Global Optimization, 11(4) (1997) 341–359.

[20] Suganthan P N. Particle Swarm Optimizer with Neighborhood Operator. In: Proceedings of

the 1999 Congress on Evolutionary Computation. Piscataway, NJ, IEEE Service Center, 1999, 1958-1962

[21] Kennedy J. Small Worlds and Mega-minds: effects of neighborhood topology on particle

swarm performance. 1931-1938. 1999. Piscataway, NJ, IEEE Service Center. Proc. Congress on Evolutionary Computation 1999.

[22] 王俊伟，汪定伟，一种带有梯度加速的粒子群算法，东北大学，信息科学与工程学院，

2004.

[23] Federgruen, A. and Z. Schechner, Cost formulas for continuous review inventory models

with fixed delivery lags. Operations Research. vol. 31, no. 5, pp. 957-965,1983

[24] Liu, L., (s, S) continuous review models for inventory with random life-times, Operations

Research Letters, vol, 12, no. 3, pp. 161-167, 1990.

[25] Luss, H., Operations research and capacity expansion problems: a survey, Operations

Research, vol. 30, no. 5, pp. 904-947, 1982.

[26] Moinzadeh, K. and S. Nahmias, A continuous review model for an inventory system with

two supply modes, Management Science, vol. 34, pp. 761-773, 1988.

[27] Wang, P., G. Wilson, and N. Odrey, An on-line controller for production system with

seasonal demands, International Journal of Computers and Industrial Engineering, vol. 27, pp. 565-574, 1994.

[28] Gen, M. and B. Liu, Evolution program for production plan problem, Engineering Design

and Automation, vol. l, no. 3, pp. 199-204, 1995.

[29] Gen, M. and B. Liu, Evolution program for optimal capacity expansion, Journal of

Operations Research of Japan, 1997, in press.

苏州大学本科生毕业设计(论文)

致谢

在本文的书写过程中，作者受到很多老师和同学们的帮助，在此，首先，我想感谢我的指导老师，姚望舒老师，他耐心的指导和深厚的研究功底不止一次的令我折服，每次关于项目的讨论，他总是能给我很多新的思路和动力，他严谨的治学态度同样给我以很大的启发和触动，总之深深的感谢他一直以来对我的帮助。我还想感谢我的女朋友，每当遇到困难的时候，面对我的抱怨，她总是积极的鼓励我，陪我一同度过难关。同时在这里也要感谢外国语学院的卢威同学认真的帮我完成了论文摘要的翻译工作。最后还有所有在项目研究和论文撰写过程中帮助过我的同学们。