粒子群优化算法研究及应用(周先东)

粒子群优化算法研究及其应用学生姓名：周先东指导教师：杨大地副教授专业：运筹学与控制论2021.11ResearchandApplicationsofParticleSwarmOptimization〔PSO〕论文结构

PSO算法简介论文主要工作结论与展望致谢标准PSO算法在变分问题中的应用求解运输问题的GAPSO算法分层PSO算法绪论1论文的创新之处

1〕本文建立了求解两个经典变分问题以及含一阶导数变分问题的优化模型，从而成功地应用PSO算法求解了该类变分问题。根据变分原理，又将PSO算法应用到了求解二阶线性微分方程的两点边值问题当中。从而拓展了PSO算法的应用领域。2〕本文根据运输问题的特殊约束条件，设计了一种产生初始可行解的方法，同时基于遗传算法(GA)和PSO算法的思想，设计了求解运输问题的GAPSO算法。3〕针对PSO算法收敛速度较慢和后期局部搜索能力不强的问题，本文基于分层搜索的思想，提出了一种分层PSO算法。1论文的创新之处

2PSO算法简介群体智能算法〔SwarmIntelligenceAlgorithm〕的研究开始于20世纪90年代，其根本思想是模拟自然界生物的群体行为来构造随机优化算法。PSO算法是群体智能算法的一种。它是由美国社会心理学家Jameskennedy和电气工程师RussellEberhart在1995年提出的，该算法是以模拟鸟的群体智能为特征，以求解连续变量优化问题为背景的一种优化算法。2.2

标准PSO算法1998年,Y.Shi和R.C.Eberhart首次在速度进化方程中引入惯性权重，即：式中称为惯性权重，它使粒子保持运动惯性，使其有扩展搜索空间的趋势，有能力搜索新的区域。这种带惯性权重的PSO算法被称PSO算法的标准版本，简称标准PSO算法。PSO算法具有概念简单，易于实现的特点，同时它还具有深刻的智能背景，既适合科学研究，又特别适合工程应用。目前，PSO算法的研究大致可分为以下几个方向：算法的理论研究、算法的改进以及算法的应用研究。详见参考文献。2.3PSO算法研究和开展现状但是无论是理论还是实践应用都还不够成熟，还有大量问题需要研究。3标准PSO算法在变分问题中的应用本文主要工作虽然PSO算法在工程优化、自动控制等领域有着广泛的应用，但是在数学界却没能被认可，因为到目前为止，该算法还没能解决数学上的经典问题，同时该算法也还没有数学理论的支撑。本文那么对PSO算法在微分方程及变分问题中的应用做进行了初步研究。PSO算法微分方程变分问题变分原理泛函极值问题变分问题实际上是一个泛函极值问题。PSO算法在求解极值问题中有着广泛的应用。但是关于PSO算法在变分问题中的应用，目前尚没有相关的研究。

本文主要工作3.1变分问题概述目前已有的变分问题直接解法包括有限差分法、Ritz法、Kantorovich法、Galerkin法、最小二乘法、配置法和分区平均法等等。本文主要工作3.2标准PSO算法两个经典变分问题中的应用3.2.1标准PSO算法在最速降线问题中的应用根据问题的物理背景，本文采用离散化的思想建立了一个求解最速降线问题的最优化模型，然后利用标准PSO算法对该问题进行了求解。本文主要工作16等分结果比照图本文主要工作求点之间的最速降线。理论准确解为：从A到B的最短时间为1.84423.2.2标准PSO算法在曲面最短路径问题中的应用本文采用离散化思想，将曲线离散成假设干小段，提出了一个解决该问题的离散化模型。从而将复杂曲面上路径寻优问题，转化为了多元的单目标优化问题，使得PSO算法能够在该问题中发挥作用。本文主要工作例3.2求两点间最短路径的结果示意图本文主要工作例3.2本实例采用搜索空间D为100×100单位的正方形区域，用函数模拟实际地形，函数构造如下：3.3标准PSO算法在含一阶导数变分问题中的应用研究带有一阶导数的固定边界变分问题：定义2由可行函数构成的集合为可行函数类。定义1满足变分问题的边值条件的函数称为可行函数。本文主要工作3.3.1基于Hermite插值的求解模型将区间[a,b]等分为n段，各分点为：假设可行函数y(x)在各个分点的函数值及其一阶导数值：yi，y'i，其中i=1,2,…,n。在各小段内采用两点三次Hermite插值多项式来近似逼近可行函数y(x)。基于离散化的思想，本文采用两点三次Hermite插值来构造可行函数类中的近似可行函数，本文主要工作那么可行y(x)函数在区间[xi-1,xi]内的近似函数为：其中i=1,2,…,n，那么在整个区间[a,b]的可行函数y(x)的近似函数为：本文主要工作H(x)是一个分段三次多项式，对于各区间的一阶导数Hi'(x)很容易得到。由于积分是线性算子，故可以将变分问题〔3.6〕看成如下的近似问题：问题就转化为以y1,y2,…,yn,y0',y1',…,yn'为变量的单目标多元变量优化问题，对于这样的问题那么可以采用标准PSO算法来求解。本文主要工作

标准PSO算法设计：y1,y2,…,yn-1,y0‘,y1’,y2‘,…,yn’被看作一个粒子，但问题是无约束问题，所以要将解空间限制在一个具有上下限的区域内[-M,M]内，其中M是一个足够大的正数。模型的最优化问题是一个极小值问题，且其目标函数是一个线性算子，故该目标函数就可作为适应度函数，即本文主要工作收敛图划分为4段时〔误差3.3252e-009〕〔点为准确值，线为近似值〕例3.3的计算结果本文主要工作例3.3对于变分问题其准确解为：划分为8段时〔误差0.0074〕划分为16段时〔误差0.0104〕〔点为准确值，线为近似值〕例3.3的计算结果本文主要工作〔红色*为准确值，O为近似值〕例3.4的计算结果本文主要工作例3.4对变分问题其准确解为：〔红色*为准确值，O为近似值〕例3.5的计算结果误差为：4.796748020400851e-005本文主要工作例3.5对于变分问题其用准确解为：3.4

标准PSO算法在二阶线性常微分方程两点边值问题中的应用根据变分原理，二阶线性常微分方程的两点边值问题可转化为等价的变分问题。因此，求解二阶线性常微分方程的两点边值问题可以转化为求解与之等价的变分问题。本文主要工作考虑二阶线性常微分方程的两点边值问题：其等价于变分问题含一阶导数的变分问题由两点三次Hermite插值的模型及标准PSO算法即可求解。本文主要工作例3.7结果〔同准确解的比较〕〔*是准确值，□是近似值〕本文主要工作例3.7对于两点边值问题其等价的变分问题为：其解析解为：11110.846963381691910.846964164508340.847004510008700.90.711410960082470.711412311440200.711479065117490.80.590985247364300.590986689947510.591068410877450.70.483480148916880.483481690074270.483568440746180.60.386818883970070.386820543468010.386904155022380.50.299033200484160.299034861760070.299108910848800.40.218243676221860.218245249455150.218304755783710.30.142640908858910.142642320776240.142683648276460.20.070467406877400.070468157313400.070489377251970.10000（准确值）（标准PSO算法结果）（差分法结果）例3.7结果〔同差分法的比较〕本文主要工作①差分法得到的近似解的精度最多只能够到达0.0001，而运用PSO算法求解的方法那么除一个点以外都到达了0.00001；②由于截断误差的原因，差分法得到的近似解的误差从0~1逐渐扩大，而运用PSO算法求解的方法那么不存在这样的问题；③差分法是用差商代替微商，而不是直接利用一阶导数，而运用PSO算法求解的方法那么是直接利用一阶导数和函数值构造出近似逼近极值函数的分段插值函数，具有比较好的光滑性。通过比较可以看出：本文主要工作0010.323346599201860.323522483537160.80.586330020560940.584886547507060.60.777938873042110.776790592662280.40.893698932126540.894019190968960.20.932347027189710.9334430856067700.893714428676060.89401919096896-0.20.777945952404600.77679059266228-0.40.586329769398440.58488654750706-0.60.323348441383770.32352248353716-0.800-1（PSO算法的结果）（Ritz法的结果）例3.6结果〔同Ritz法的比较〕本文主要工作例3.6对于两点边值问题其等价的变分问题为：其用Ritz法得到的第二近似解为：4求解运输问题的GAPSO算法运输问题是一个应用非常广泛的问题，传统方法对于大规模的运输问题求解比较复杂，而一些基于随机搜索算法的解法对于其约束条件的处理又比较困难。本文基于运输问题约束条件的特殊性，设计了一种产生可行解的方法，将对约束条件的处理转化到了算法设计之中。在此根底上，又设计了基于遗传算法和PSO算法的求解运输问题的GAPSO算法。本文主要工作4.1运输问题数学模型目标函数：产量约束：销售约束：当时为供销平衡的运输问题；时为供销不平衡的运输问题。当本文主要工作4.2GAPSO算法初始解的设计(供销平衡问题〕A1A2AnBmB2B1产地销售地a11a12a1jB1=B1-a11B2=B2-a12Bm=Bm-a1mBj=Bj-a1j第一次各销售地剩余需求量第一个产地分配a1m本文主要工作A1A2AnBmB2B1产地销售地a21a22a2ja2mB1=B1-a21B2=B2-a22Bm=Bm-a2mBj=Bj-a2j第二次各销售地剩余需求量第二个产地分配本文主要工作A1A2AnBmB2B1产地销售地ai1ai2aijaimB1=B1-ai1B2=B2-ai2Bm=Bm-aimBj=Bj-aij第i次各销售地剩余需求量Ai第个产地分配本文主要工作A1A2AnBmB2B1产地销售地B1B2BjBm第个产地分配本文主要工作由的随机性，显然，满足该约束条件的所有可行解都可用这种方法生成。由此便产生了一个满足约束条件的可行解：容易验证该方法生成的每一个初始解都满足：本文主要工作4.3

GAPSO算法算法设计在迭代过程中采用了混合迭代的方法，一方面选择一局部较优的个体进行遗传算法变异操作；另一方面采用轮盘赌方法选择一局部个体进行PSO算法搜索；同时为了防止陷入局部最优，另外在迭代过程中又利用产生初始解的方法生成一局部可行解参加到种群之中。但是每次迭代之后都保持种群总的数目不变。迭代过程设计：本文主要工作

算法中采用的遗传算法的变异主要是多点变异，其设计的原理和产生初始解的方法相同，都是基于供销平衡运输问题的特殊约束条件来设计。

算法中应用的PSO算法搜索过程是在标准PSO算法中加入了运输问题的约束条件，采用了算子：和选择机制。从而避免了迭代过程中产生非可行解的问题。本文主要工作100%100%收敛率392507平均收敛代数GA98%96%收敛率284453平均收敛代数PSO100%100%收敛率147357平均收敛代数GAPSO例4.2例4.1算法GAPSO，PSO，GA的收敛性比较本文主要工作

供销不平衡的问题一般都是假设一个虚拟的产地或者一个虚拟的销售地将其转化为供销平衡的问题来处理。5分层PSO算法5.1分层PSO算法提出背景PSO算法在求解复杂优化对象时，虽然能够搜索到较好的区域，却存在进化后期局部搜索能力不强、收敛速度变慢等问题。针对这些问题，国内外学者从各方面对PSO算法进行了大量的研究。实际上，提高算法的收敛速度和局部搜索能力还有别的途径。其中，缩小搜索区域即是一类有效的方法。本文主要工作5.2

分层PSO算法的思想本文主要工作全局搜索区域最优解搜索到一定程度第一次搜索得到的较优解标准PSO局部区域继续搜索第二次搜索得到的较优解标准PSO假设干次缩小搜索区域得到最优解标准PSO显然，算法很容易陷入局部最优。考虑到要保持标准PSO算法的全局收敛性，本文提出一种动态改变局部搜索区域的策略，该策略就是将对整个区域的全局搜索和对局部区域的局部搜索同时进行，发现全局搜索的最优个体比局部区域搜索的最优个体的更优，且该全局最优个体不在当前局部区域内，那么重新生成搜索的局部区域进行搜索，使其跳出局部最优。本文主要工作分层PSO算法流程图本文主要工作本文采用文献[87]中的三个典型的测试函数对算法进行了测试。本文主要工作Sphere函数：Rastrigin函数：Rosenbrock函数：函数在取得最小值0。函数在取得最小值0。函数在取得最小值0。Sphere函数的搜索过程本文主要工作测试函数的计算结果见表5.1和表5.2(P46-48)Rastrigin函数的搜索过程本文主要工作Rosenbrock函数搜索过程本文主要工作★首先对PSO算法在两个经典变分问题，以及含一阶导数的变分问题中的应用进行了初步研究。根据变分原理，又将标准PSO算法应用到了求解两点边值问题的二阶微分方程的问题当中，从而拓展了PSO算法的应用领域。结论结论与展望★本文根据运输问题的特殊约束条件，设计了一种产生可行解的方法，同时基于遗传算法和PSO算法的思想，设计了求解运输问题的GAPSO算法。实验说明该算法是完全可行的，且算法的效率也是非常令人满意的。结论结论与展望★本文基于分层遗传算法的进化思想，考虑到遗传算法与PSO算法的进化机理相