实验十遗传算法与优化问题 一、问题背景与实验目的 遗传算法（Genetic Algorithm—GA），是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，它是由美国Michigan大学的J.Holland教授于1975年首先提出的．遗传算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强、适于并行处理及应用范围广等显着特点，奠定了它作为21世纪关键智能计算之一的地位． 本实验将首先介绍一下遗传算法的基本理论，然后用其解决几个简单的函数最值问题，使读者能够学会利用遗传算法进行初步的优化计算． 1．遗传算法的基本原理 遗传算法的基本思想正是基于模仿生物界遗传学的遗传过程．它把问题的参数用基因代表，把问题的解用染色体代表（在计算机里用二进制码表示），从而得到一个由具有不同染色体的个体组成的群体．这个群体在问题特定的环境里生存竞争，适者有最好的机会生存和产生后代．后代随机化地继承了父代的最好特征，并也在生存环境的控制支配下继续这一过程．群体的染色体都将逐渐适应环境，不断进化，最后收敛到一族最适应环境的类似个体，即得到问题最优的解．值得注意的一点是，现在的遗传算法是受生物进化论学说的启发提出的，这种学说对我们用计算机解决复杂问题很有用，而它本身是否完全正确并不重要（目前生物界对此学说尚有争议）． （1）遗传算法中的生物遗传学概念
由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在这个算法中要用到各种进化和遗传学的概念． 首先给出遗传学概念、遗传算法概念和相应的数学概念三者之间的对应关系．这些概念如下：
（2）遗传算法的步骤 遗传算法计算优化的操作过程就如同生物学上生物遗传进化的过程，主要有三个基本操作（或称为算子）：选择（Selection）、交叉（Crossover）、变异（Mutation）． 遗传算法基本步骤主要是：先把问题的解表示成“染色体”，在算法中也就是以二进制
粒子群算法解决函数优化问题 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 年，高鹰和谢胜利将混沌寻优思想引入到粒子群优化算法中，首先对当前群体中的优粒子进行混沌寻优, 再用混沌寻优的结果随机替换群体中的一个粒子，这样提出另一种混沌粒子群优化算法。
蚁群算法 学号：1101500449 姓名：赵亮民 摘要：蚁群算法是优化领域中新出现的一种仿生进化算法。该算法采用分布式并行计算机制，具有较强的鲁棒性；但有搜索时间较长，易陷入局部最优解的缺点。本文首先讲述蚁群算法的来源和基本原理，然后讨论蚁群算法的几种改进策略，并简单介绍近年来蚁群算法在许多新领域中的发展应用，最后对今后进一步研究的方向作了展望。 关键词：蚁群算法；蚂蚁；信息素；优化 Abstract：Ant colony algorithm is a novel category of bionic algorithm for optim ization problems．Parallel computation mechanism is adopted in this algorithm．It has strong robustness and is easy to combinewith other methods in optimization，but it has the limitation of stagnation，and is easy to fall into local optimums．Firstly，the basic principle of ant colony algorithm is introduced．Then。a series of schemes on improving the ant colony algorithm are discussed，and the new applications are also provided．Finally，somerem arks on the further research and directions are presented． Key words：ant colony algorithm ；ant；pheromone；optimization 概念 各个蚂蚁在没有事先告诉他们食物在什么地方的前提下开始寻找食物。当一只找到食物以后，它会向环境释放一种挥发性分泌物pheromone (称为信息素,该物质随着时间的推移会逐渐挥发消失，信息素浓度的大小表征路径的远近)来实现的，吸引其他的蚂蚁过来，这样越来越多的蚂蚁会找到食物。有些蚂蚁并没有象其它蚂蚁一样总重复同样的路，他们会另辟蹊径，如果另开辟的道路比原来的其他道路更短，那么，渐渐地，更多的蚂蚁被吸引到这条较短的路上来。最后，经过一段时间运行，可能会出现一条最短的路径被大多数蚂蚁重复着。原理 设想，如果我们要为蚂蚁设计一个人工智能的程序，那么这个程序要多么复杂呢？首先，你要让蚂蚁能够避开障碍物，就必须根据适当的地形给它编进指令让他们能够巧妙的避开障碍物，其次，要让蚂蚁找到食物，就需要让他们遍历空间上的所有点；再次，如果要让蚂蚁找到最短的路径，那么需要计算所有可能的路径并且比较它们的大小，而且更重要的是，你要小心翼翼地编程，因为程序的错误也许会让你前功尽弃。这是多么不可思议的程序！太复杂了，恐怕没人能够完成这样繁琐冗余的程序。 然而，事实并没有你想得那么复杂，上面这个程序每个蚂蚁的核心程序编码不过100多行！为什么这么简单的程序会让蚂蚁干这样复杂的事情？答案是：简单规则的涌现。事实上，每只蚂蚁并不是像我们想象的需要知道整个世界的信息，他们其实只关心很小范围内的眼前信息，而且根据这些局部信息利用几条简单的规则进行决策，这样，在蚁群这个集体里，复杂性的行为就会凸现出来。这就是人工生命、复杂性科学解释的规律！那么，这些简单规则是什么呢？ 现今有哪些关于蚁群算法的应用呢？ 1大规模集成电路的线网布局 在大规模集成电路的线网布局中，需要根据电路和工艺的要求完成芯片上单元或功能模块的布局，然后实现它们之间的互连。此问题可看作是寻找一个网格平面上两端点之间绕过障碍的最短路径问题。线网上的每个Agent根据启发策略．像蚂蚁一样在开关盒网格上爬行，所经之处便设置一条金属线．历经一个线网的所有引脚之后．线网便布通了。应用蚁群算法，可以找到成本最低、最合理的线网布局．而且由于其本身的并行性。比较适合于解决此类问题。 2通信网络路由
粒子群优化算法的收敛性研究综述 摘要:给出了粒子群与改进算法的分类及其进展，指出了粒子群算法收敛性理论分类及其进展，最后对各粒子群算法的收敛条件进行了对比。 关键词：粒子群算法粒子群算法分类收敛条件 粒子群优化算法(PSO:Particle Swarm Optimization)是一种优化计算技术。起源于对鸟群和鱼群群体运动行为的研究，是一种基于迭代的优化工具，是一种基于群只能方法的演化计算技术。PSO算法概念简单容易实现，并且没有许多参数需要调整，短短十几年里，PSO 算法已经取得了很大的发展，目前已广泛应用于函数优化、神经网络的训练、模糊系统的控制、以及其他遗传算法的应用领域。。但是它由于容易陷入局部极小点，搜索精度不高，科研工作者对其作了各种各样的改进。目前已提出了多种PSO改进算法[1]。如自适应PSO算法,混合PSO算法，协同PSO算法，离散PSO算法。一些学者从数学的角度对算法的收敛性进行了初步分析[13] 。 本文以下部分的组织是：第1节介绍粒子群算法的分类及其当前研究进展；第2节介绍粒子群算法收敛性理论分类及其进展；最后对比各粒子群算法的收敛条件。 1 粒子群与改进算法的分类及其进展 1.1 自适应PSO(Adaptive Particle Swarm Optimization,APSO) 由于较大的惯性因子W值有利于跳出局部极小点，而较小的W值有利于算法收敛，于是科研工作者就提出了自适应调整W的方法，即随着迭代的进行，线性地减小W值。这种方法的进一步发展就是采用模糊规则动态地修改W的值[4]。即构造2个输入，一个输出的模糊推理机来动态修改惯性因子W。模糊推理机的两个输入分别是当前W值，输出为W的增量。通过自适应调整全局系数，兼顾搜索效率和搜索精度，是一类有效的算法。但是对许多复杂的非线性优化问题，试图通过自适应调整一个全局系数提高搜索精度的余地是有限的。 1.2 混合PSO(Hybrid Particle Swarm Optimization,HPSO) 受到遗传算法的启示，文献[5,6]最早提出了混合PSO算法。混合PSO算法是将基本PSO 算法和选择机制相结合而得到的，基本的PSO算法的搜索过程很大程度说那上依赖pbest 和gbest,它的搜索区域受到gbest和gbest的限制。在一般的进化算法中，选择机制用来选择相对较好的区域和淘汰较差的区域。可以更合理地分配有限的资源。
遗传算法及对于过早收敛的改进 摘要遗传算法是模拟达尔文生物进化论中的自然选择与遗传学机理的生物过程的一种计算模型。该模型通过模拟自然进化过程来搜索最优解，其应用非常广泛。但是在运用遗传算法的过程之中经常遇到过早收敛的问题，为了改进该问题，在文中对遗传算法进行了介绍，并在此基础上就如何改进过早收敛进行探讨。 关键词遗传算法；过早收敛；改进 中图分类号TP18 文献标识码 A 文章编号2095-6363（2017）15-0023-01 遗传算法（Genetic Algorithm，GA）是自然科学与工程科学互相结合的产物，是一类借鉴达尔文自然选择机理（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。 遗传算法求解优化问题的性能与交叉概率（Pc）、变异概率（Pm）等参数的选择有着很大的联系。本文基于传统思路，对GA的交叉概率和变异概率参数进行自适应控制，对过早收敛问题进行了适当优化。 1 遗传算法综述 1.1 遗传算法思想 通常来说，遗传算法包括三个算子，即选择、交叉和变
异。选择算子的作用是为了提升整个群体的平均适度值，在整个群体中选择那些评价值高的个体组成交配池的主要群体：交叉算子的主要作用是选择交配池中的优良基因遗传给下一代，先将交配池中个体进行两两配对，再有目的的交换部分基因，生成基因性状更加复杂的个体；变异算子是对个体某一个或是几个按照某一较小的概率进行反转二进制字符。从而实现对自然界中基因突变现象的模拟。 1.2 遗传算法的思想流程 1）初始化群体；2）计算群体上每个个体的适应度值；3）针对于个体适应度值，依据某个规则选择将进入下一代的个体；4）通过概率Pc进行交叉操作；5）通过概率Pm进行突变操作；6）未达到终止条件，则返回2）步，否则进入下一步；7）输出群体中适应度值最大的个体作为问题的满意解或最优解。 2 过早收敛及其特点 过早收敛在早期的选择过程，种群中就出现了“完美”个体，该类个体的适应度值特别大，然而选择压力很大，后期变异概率比较小。继而在后期的繁殖中占主体地位，种群的多样性会很快的降低进而导致种群多样化的丧失。 过早收敛对于整个种群来说弊大于利，因为结果并非是全局最优，仅仅是局部最优。特别是到了算法进行的后期，进过算法的多代进化，完美的个体已经在种群中占据绝大多
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 ==，它是优化问题的一个潜在
《智能计算—蚁群算法基本综述》 班级：研1102班 专业：计算数学 姓名：刘鑫 学号： 1107010036 2012年
蚁群算法基本综述 刘鑫 （西安理工大学理学院，研1102班，西安市，710054） 摘要:蚁群算法( ACA)是一种广泛应用于优化领域的仿生进化算法。ACA发展背景着手，分析比较国内外ACA研究团队与发展情况立足于基本原理,分析其数学模型,介绍了六种经典的改进模型，对其优缺点进行分析，简要总结其应用领域并对其今后的发展、应用做出展望。 关键词:蚁群；算法；优化；改进；应用 0引言 专家发现单个蚂蚁只具有一些简单的行为能力。但整个蚁群却能完成一系列复杂的任务。这种现象是通过高度组织协调完成的1991年。意大利学者M.Dorigo 首次提出一种新型仿生算法ACA。研究了蚂蚁的行为。提出其基本原理及数学模型。并将之应用于寻求旅行商问题(TSP)的解。 通过实验及相关理论证明,ACA有着有着优化的选择机制的本质。而这种适应和协作机制使之具有良好的发现能力及其它算法所没有的优点。如较强的鲁棒性、分布式计算、易与其他方法结合等；但同时也不应忽略其不足。如搜索时间较长，若每步进行信息素更新，计算仿真时所占用CPU时间过长：若当前最优路径不是全局最优路径，但其信息素浓度过高时。靠公式对信息素浓度的调整不能缓解这种现象。会陷人局部收敛无法寻找到全局最优解：转移概率过大时，虽有较快的收敛速度，但会导致早熟收敛。所以正反馈原理所引起的自催化现象意在强化性能好的解，却容易出现停滞现象。笔者综述性地介绍了ACA对一些已有的提出自己的想法，并对其应用及发展前景提出了展望。 1 蚁群算法概述 ACA源自于蚁群的觅食行为。S.Goss的“双桥”实验说明蚂蚁总会选择距食物源较短的分支蚂蚁之间通过信息素进行信息的传递,捷径上的信息素越多,吸引的蚂蚁越多。形成正反馈机制,达到一种协调化的高组织状态该行为称集体自催化目前研究的多为大规模征兵，即仅靠化学追踪的征兵。 1 .1 蚁群算法的基本原理
一、本课题研究现状及可行性分析 目前通用的数学分析教材（如华东师范大学，复旦大学，吉林大学，北京师范大学等）其介绍的主要内容如下：M 判别法，狄利克雷判别法，阿贝尔判别法，柯西收敛准则等，用来判别一些级数的一致收敛性问题，其他一些数学方面的工作者对某些特殊级数的收敛性进行了讨论。当前对级数的收敛性的讨论研究已经到达比较高级阶段，分枝也比较细，发展也相对较完善。但在许多实际解题过程中，往往不是特定的级数，用特殊的方法不能解决。故需对特殊级数情况要总结和发展。 函数项级数的一致收敛性的判定是数学分析中的一个重要知识点，函数项级数既可以被看作是对数项级数的推广，同时数项级数也可以看作是函数项级数的一个特例。它们在研究内容上有许多相似之处，如研究其收敛性及和等问题，并且它们很多问题都是借助数列和函数极限来解决，同时它们敛散性的判别方法也具有相似之处，如Cauchy 判别法，阿贝尔判别法，狄利克雷判别法等。教材中给出了对于()n u x 一致收敛性的判别法，如Cauchy 判别法，阿贝尔判别法，狄利克雷判别法等，但在具体进行一致收敛的判别时，往往会有一定的困难，这就需要我们有效地运用函数项级数一致收敛的判别法。而此课题除了叙述以上判别法外，还对这些判别方法进行了一些推广，从而进一步丰富了判别函数项级数一致收敛的方法。 二、本课题研究的关键问题及解决问题的思路 关键问题：对函数项级数一致收敛性判别法总结和推广。 基本思路：首先从定义出发，让读者了解函数项级数及一致收敛的定义，对函数项级数一致收敛有一个大致的认识，并对其进行一定的说明，且将收敛与一致收敛做一个比较，使读者对其有一个更深刻的认识。随后给出一些常见的一致收敛的判别法，并附上例题加以说明。当熟悉了一般的判别法后，我将其加以推广，得到一些特殊的判别法，如比式判别法，根式判别法，对数判别法等。
函数项级数一致收敛性判别法及其应用 栾娈 20111101894 数学科学学院 数学与应用数学11级汉班 指导老师：吴嘎日迪 摘要:本文证明了常用的函数项级数一致收敛性的判别法,并通过例题给出了它的应用.另外,仿照极限的夹逼原理,得到函数项级数一致收敛的夹逼判别法. 关键词:一致收敛,函数项级数,和函数 1.函数列与一致收敛性 (1)函数项级数一致收敛性的定义:设有函数列{S n （x ）}(或函数项级数∑∞ =1 )(n n x u 的 部分和序列)。若对任给的0>ε，存在只依赖于ε的正整数N （ε），使n > N （ε）时，不等式 ε<-)()(x S x S n 对X 上一切x 都成立，则称{S n （x ）}（∑∞ =1 )(n n x u ）在X 上一致收敛于S （x ）. 一致收敛的定义还可以用下面的方式来表达： 设 =-S S n X x ∈s u p )()(x S x S n -， 如果 0lim =-∞ →S S n n 就称S n （x ）在X 上一致收敛于S(x ). 例1 讨论 = +=X x n nx x S n 在2 2 1)([0，1]的一致收敛性 由于S （x ）=0, 故 2 11)(m a x 1 = ?? ? ??==-≤≤n S x S S S n n x o n ， 不收敛于零，故在[0，1]上非一致收敛 (2)函数项级数一致收敛的几何意义:函数列{f n }一致收敛于的f 几何意义：对任 给的正数ε ，存 N ，对一切序号大于N 的曲线y=f n (x )都落在以曲 线y= f (x )+ε与y=f (x )-ε为上，下边界的带形区域内. 2.函数列一致收敛的判别准则（充要条件）
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 个粒子的空间位置为X( x , x ,x,..., x ) i 1,2,..., m ，它是优化问题的一个潜在解， i i1 i 2 i 3 iD 将它带入优化目标函数可以计算出其相应的适应值，根据适应值可衡量x的优 i 劣；第i 个粒子所经历的最好位置称为其个体历史最好位置，记为 P ( p , p , p , ... p,) i 1, 2 ,，m..相,应的适应值为个体最好适应值Fi ；同 i 1i i2 3i i D 时，每个粒子还具有各自的飞行速度V(v ,v ,v,..., v ) i 1,2,..., m 。所有粒 i i1 i 2 i 3 iD
RLS 与 LMS 算 法 的 收 敛 性 比 较 分 析 学号：S120101057 姓名：贾雪婷
摘要：介绍了自适应滤波器的基本原理，对最小均方(LMS, Least Mean Squares)和递归最小二乘(RLS, RecursiveL east Squares)自适应算法进行仿真分析及对比研究。仿真结果及实例均表明，两种算法都能有效抑制和抵消各种干扰，但相比之下，RLS算法具有更好的收敛性能及稳定性，除收敛速度快于LMS算法和NLMS 算法以及稳定性强外，而且具有更高的起始收敛速率、更小的权噪声和更大的抑噪能力。 关键词：自适应滤波；最小均方；递归最小二乘；收敛性；对比研究Abstract: Introducing the basic principle of adaptive filter,as for the minimum mean square(LMS, Least Mean Squares)and Recursive Least Squares(RLS, RecursiveL east Squares) adaptive algorithm is applied to the simulation analysis and comparative study. The simulation results and examples indicate that the, two kinds of algorithm can effectively restrain and offset all kinds of interference, but in contrast, RLS algorithm has better convergence performance and stability, In addition to convergence speed faster than LMS algorithm and NLMS algorithm and the stability, but also have higher initial rate of convergence、smaller right noise and more noise suppression ability. Key words: adaptive filtering;LMS;RLS; astringency; Comparative study
一种保证全局收敛的PSO算法* 曾建潮崔志华 （太原重型机械学院系统仿真与计算机应用研究所山西太原 030024） (zengjianchao@https://www.doczj.com/doc/1111955714.html,) 摘要：在对基本PSO算法分析的基础上，提出了一种能够保证以概率1收敛于全局最优解的PSO算法—随机PSO算法（Stochastic PSO,简称SPSO）,并利用F.Solis和R.Wets的研究结果对其全局收敛性进行了理论分析，给出了两种停止进化微粒的重新产生方法。最后以典型优化问题的实例仿真验证了SPSO算法的有效性。 关键词：微粒群算法（PSO算法），全局最优性，收敛性，模拟退火 中图法分类号：TP18 A Guaranteed Global Convergence Particle Swarm Optimizer ZENG Jian-Chao CUI Zhi-Hua (Division of system simulation and computer application,Taiyuan Heavy Machinery Institute,030024) Abstract: A new particle swarm optimizer, called stochastic PSO, that is guaranteed to convergence to the global optimization solution with probability one, is presented based on the analysis of the standard PSO. And the global convergence analysis is made using the F.Solis and R.Wets’ research results, and two methods the stopping evolution particle regenerated are given. Finally, several examples are simulated to show that SPSO is more efficient than the standard PSO. Keywords: Particle Swarm Optimizer, Global Optimility, Convergence, Simulated-Annealing *本文的研究没有基金资助
蚁群算法与粒子群算法优缺点 蚁群算法(ACO)是受自然界中蚂蚁搜索食物行为的启发，是一种群智能优化算法。它基于对自然界真实蚁群的集体觅食行为的研究，模拟真实的蚁群协作过程。算法由若干个蚂蚁共同构造解路径，通过在解路径上遗留并交换信息素提高解的质量，进而达到优化的目的。蚁群算法作为通用随机优化方法，已经成功的应用于TSP等一系列组合优化问题中，并取得了较好的结果。但由于该算法是典型的概率算法，算法中的参数设定通常由实验方法确定，导致方法的优化性能与人的经验密切相关，很难使算法性能最优化。 蚁群算法中每只蚂蚁要选择下一步所要走的地方，在选路过程中，蚂蚁依据概率函数选择将要去的地方，这个概率取决于地点间距离和信息素的强度。 (ｔ+ｎ) = (t)+ Δ(ｔ+ｎ) 上述方程表示信息素的保留率，1－表示信息素的挥发率，为了防止信息的无限积累，取值范围限定在0～1。Δij 表示蚂蚁k在时间段t到(t +n)的过程中，在i到j的路径上留下的残留信息浓度。 在上述概率方程中，参数α和β:是通过实验确定的。它们对算法性能同样有很大的影响。α值的大小表明留在每个节点上信息量受重视的程度，其值越大，蚂蚁选择被选过的地点的可能性越大。β值的大小表明启发式信息受重视的程度。 这两个参数对蚁群算法性能的影响和作用是相互配合，密切相关的。但是这两个参数只能依靠经验或重复调试来选择。 在采用蚁群－粒子群混合算法时，我们可以利用PSO对蚁群系统参数α和β的进行训练。具体训练过程：假设有n个粒子组成一个群落，其中第i个粒子表示为一个二维的向量xi = ( xi1 , xi2 ) , i = 1, 2, ?,n，即第i个粒子在搜索空间的中的位置是xi。换言之，每个粒子的位置就是一个潜在的解。将xi带入反馈到蚁群系统并按目标函数就可以计算出其适应值，根据适应值的大小衡量解的优劣。 蚁群算法的优点： 蚁群算法与其他启发式算法相比，在求解性能上，具有很强的鲁棒性（对基本蚁群算法模型稍加修改，便可以应用于其他问题）和搜索较好解的能力。 蚁群算法是一种基于种群的进化算法，具有本质并行性，易于并行实现。 蚁群算法很容易与多种启发式算法结合，以改善算法性能。 蚁群算法存在的问题： TSP问题是一类经典的组合优化问题，即在给定城市个数和各城市之间距离的条件下，找到一条遍历所有城市且每个城市只能访问一次的总路程最短的路线。蚁群算法在TSP问题应用中取得了良好的效果，但是也存在一些不足： （1），如果参数α和β设置不当，导致求解速度很慢且所得解的质量特别差。 （2），基本蚁群算法计算量大，求解所需时间较长。 （3），基本蚁群算法中理论上要求所有的蚂蚁选择同一路线，该线路即为所求的最优线路；但在实际计算中，在给定一定循环数的条件下很难达到这种情况。 另一方面，在其它的实际应用中，如图像处理中寻求最优模板问题，我们并不要求所有的蚂蚁都找到最优模板，而只需要一只找到最优模板即可。如果要求所有的蚂蚁都找到最优模板，反而影响了计算效率。 蚁群算法收敛速度慢、易陷入局部最优。蚁群算法中初始信息素匮乏。蚁群算法一般需要较长的搜索时间，其复杂度可以反映这一点；而且该方法容易出现停滞现象，即搜索进行到一定程度后，所有个体发现的解完全一致，不能对解空间进一步进行搜索，不利于发现更好的解。
函数项级数一致收敛性的判别法 摘 要 函数项级数是数学分析中的重点和难点,因此讨论和分析它的性质和判别方法显得尤为重要,本文给出了函数项级数的定义以及函数项级数一致收敛性的判别定理，并用之来解决函数项级数一致收敛性的一些问题比较容易. 关键词 函数项级数；一致收敛性；判别法. 中图分类号 O173.1 Function Seies Convergence Criterion Abstrac t ：Function is a mathematical analysis of series of focus and difficult, so the discussion and analysis of its nature and it is particularly important to identify methods.In this paper, the definition of Function series and uniform convergence of Function series of discriminant theorem,and used to solve the series of uniform convergence of Function of some of the problems is easier. Key words ：Function series; Uniform convergence of; Discriminance 1 引言及预备知识 如果函数项级数具有一致收敛性,函数项级数的和函数或余和易于求得,判别它的一致收敛性可应用一致收敛定义,如果很难求得它的和函数或余和，就根据函数自身的结构,找到判别一致收敛性的判别法. 定义1.1[1] 设()12(),,u x u x …()n u x ,…是一列定义在D 上的函数,把这些函数的各项用加号连接起来的表达式 ()()12u x u x ++…+()n u x +…或()1n n u x ∞ =∑, (1) 称为函数项级数.a D ?∈ 函数级数在a 对应一个数值级数 1 ()U n a ∞ =∑ =12()()u a u a ++...+()n u a +. (2) 它的敛散性可用数值级数敛散性的判别法判别,若级数(2)收敛,则称a 是函数级数(1)的收敛点;若级数(2)发散,则称a 是函数级数(1)的发散点. 定义 1.2[1] 函数项级数(1)的收敛点的集合,称为函数项级数(1)的收敛域,若收敛域是一个区间,则称此区间是函数项级数的收敛区间. 定义 1.3[1] 设数集E 为函数项级数()1 n n u x ∞ =∑的收敛域,则对每个x E ∈记S(x)= ()1 n n u x ∞=∑称S(x)为函数项级数()1 n n u x ∞ =∑的和函数.
含参量反常积分一致收敛的判别法 王 明 星 （德州学院数学科学学院,山东德州 253023） 摘 要： 含参量反常积分是研究和表达函数特别是非初等函数的有力工具.本文通过对含参量反常积分一致收敛性的分析和研究,总结出了判别含参量反常积分一致收敛的几种简单而有效的方法和定理（柯西准则,M 判别法,确界法,狄利克雷判别法等）,从而方便了含参量反常积分一致收敛性的学习和掌握. 关键词： 含参量反常积分; 一致收敛; 判别法 含参量反常积分包括含参量无穷限反常积分和含参量无界函数反常积分,两种反常积分一致收敛性的判别法是相似的,所以我们下面仅仅讨论含参量无穷限反常积分一致收敛性的判别法. 1 含参量无穷限反常积分一致收敛的概念 1.1 含参量无穷限反常积分 设函数(,)f x y 定义在无界区域(){},,R x y a x b c y =|≤≤≤<+∞上,若对每一个固定的[],x a b ∈,反常积分 (,)c f x y dy +∞ ? 都收敛,则它的值是x 在[],a b 上取值的函数,当记这个函数为()I x 时,则有 ()(,)c I x f x y dy +∞=?,[],x a b ∈ 称(,)c f x y dy +∞? 为定义在[],a b 上的含参量无穷限反常积分. 1.2 含参量无穷限反常积分收敛 若含参量无穷限反常积分(,)c f x y dy +∞? 与函数()I x 对每一个固定的 [],x a b ∈,任给的正数ε,总存在某一实数N c >,使得M N >时,都有 (,)()M c f x y dy I x ε-
标准粒子群优化算法收敛性能分析与参数选择1 林川，冯全源 西南交通大学信息科学与技术学院，成都（610031） E-mail ：lin_langai@https://www.doczj.com/doc/1111955714.html, 摘 要：基于离散时间线性动态系统理论，推导了确定性标准粒子群优化（PSO ）算法收敛，临界稳定与发散的充分必要条件，并用若干个粒子运动轨迹的仿真结果对理论结果进行了验证。根据理论分析结果，给出了参数选择的指导方法，讨论了随机参数对PSO 算法性能的影响，分析了不同收敛阶段PSO 算法探索与开发能力的平衡问题。同时本文指出，目前较普遍认为的：PSO 算法的惯性权越小则局部搜索能力越强这一观点严格说来并不够准确，在实际中应小心使用。 关键词：粒子群，随机优化，收敛性，参数选择 中图分类号：TP18 粒子群优化（PSO ）算法是J. Kennedy 与Eberhart 提出的一种基于群体智能的随机优化方法，它模拟了鸟类或鱼群觅食过程的社会行为[1]，已在许多领域获得了广泛应用[2]。PSO 算法的参数设置对算法性能有很大的影响，而这些参数设置又常与待优化问题密切相关。虽然目前已有许多学者通过大量仿真实验对PSO 算法的参数选择进行了研究，但为了更深入地理解PSO 算法并提供参数选择的指导方法，近年来，一些学者开始对PSO 算法的粒子运 动轨迹及其稳定性进行深入的理论分析[3~7]， 这些理论研究大部分集中在PSO 算法稳定收敛的充分条件方面。本文利用离散时间线性动态系统理论，从理论上推导了确定性PSO 算法收敛，临界稳定与发散的充分必要条件。根据理论分析结果，给出了PSO 算法参数选择的指导方法，讨论了随机参数对算法性能的影响，分析了PSO 算法获得成功的一些关键因素。本文指出目前较普遍认为的：惯性权越小则PSO 算法的局部搜索能力越强这一观点严格说来并不够准确，它只在一定条件下成立。同时，本文还给出了若干个粒子运动轨迹的仿真结果，对理论分析结果进行了验证。 1．PSO 算法 PSO 算法中的每个粒子代表D 维搜索空间中的一个潜在解，它在搜索空间以一定的速度飞行，这个速度根据它先前的飞行速度，本身及同伴的飞行经验进行动态调整。具体说来，标准PSO 算法中第i 个粒子第d 维的速度与位置按如下的表达式进行更新[8]： ） （）（)()()()()()1(21t x p t t x p t t wv t v id gd d id id d id id ?+?+=+φφ (1) )1()()1(++=+t v t x t x id id id (2) 其中，i =1,…, m , d =1,…., D ，m 为种群规模，D 维向量x i (t )与v i (t )分别为粒子i 在t 时刻的位置与速度，p i 为粒子i 曾经历过的个体最优位置，p g 为粒子i 的所有邻域个体曾经历过的全 局历史最优位置。w 为惯性权，)()(111t r c t d d =φ, ) ()(222t r c t d d =φ，c 1，c 2为加速系数，r 1d ，r 2d 为在[0, 1]内均匀分布的随机数。 由于本文主要分析确定性PSO 算法的收敛性能，因此我们将随机变量)(1t d φ，)(2t d φ简化为常数1φ，2φ。为了便于分析，不失一般性，我们将粒子位置与速度的维数从D 维简化为1维[4]。这样，式（1）与式（2）可简化为： 1本课题得到国家自然科学基金（基金号：60371017）的资助。
LMS 算法的稳定性分析和算法收敛条件 1最小均方法LMS 简介 LMS （Least Mean Square ）算法是Widrow 和Hoff 于1960年首次提出的，目前仍然是实际中使用的最广泛的一种算法。 LMS 算法是在最陡下降法的基础上实现的，它是维纳滤波和最速下降算法互相结合而生成的一种新的算法。通过维纳滤波所求解的维纳解,.必须在已知输入信号与期望信号的先验统计信息,以及再对输入信号的自相关矩阵进行求逆运算的情况下才能得以确定。因此,这个维纳解仅仅是理论上的一种最优解。但是通过借助于最速下降算法,LMS 算法以递归的方式来逼近这个维纳解,从而避免了矩阵求逆运算。 2LMS 算法的导出 在LMS 算法中用瞬时误差的平方来代替均方误差是LMS 算法最主要的思想,以瞬时误差信号平方的梯度作为均方误差函数梯度的估计。 在最陡下降法中其维纳解方程如下 (1)()k k k μξ +=-?w w （1-1） 其中ξk ?为梯度矢量，此时的 2[()]E e n ξ=, 此时取性能函数()n e 2=ξ来代替之前的性能函数， 则新的维纳方程变为如下形式 2(1)()()n n e n μ+=-?w w （1-2） 同时又可以求得 22 ()()()2()2()()e n e n e n e n e n n ???===-??x w w （1-3） 所以LMS 算法的权值更新方程可写成下式 (1)()()()n n e n n μ+=+w w x （1-4） 为了了解LMS 算法与最速下降法所得到的权矢量之间的关系,需要重写LMS 算法的递推公式，
因为)()()()(n w n x n d n e T -=代入LMS 算法的权值更新方程可得 )())()()()(()()1(n x n w n x n d n u n w n w T -+=+ 即)()()())()(()1(n d n ux n w n x n ux I n w T +-=+ 对上式求均值，又因为w （n ）和x （n ）不相关，所以 )] ()([)]([)])()([()]1([n d n x uE n w E n x n x uE I n w E T +-=+ （1-5） 其中互相关矢量 T L p p p n d n E ],...,,[)]()([121-==x p 自相关矩阵 ()()T E n n ??=??R x x 把P 和R 代入1-5式可得 uP n w E uR I n w E +-=+)]([)()]1([ （1-6） 由式1-6可知LMS 算法的权矢量的平均值E[w(n)]的变化规律和最速下降法的权矢量w(n)完全一样。最速下降法根据确定性轨迹沿着误差性能曲面计算权向量w(n),最后终止于维纳解w0。而在LMS 算法中,由于每步迭代过程中梯度估值是带噪的,因而权值运动轨迹并不是严格的与真正梯度方向一致。因此LMS 算法的解不是终止于维纳解。 3 LMS 算法的性能指标及性能分析 收敛性 收敛性,即当n 趋于无穷大时,让滤波器权矢量处于某个最优值或者在它的一个邻域范围内而不是越来越远,也就是让w(n)趋于w0所需满足的收敛条件。对任意自适应滤波系统,收敛性是实现其自适应功能的根本保证。 类似于最速下降法,定义权值误差矢量v(n)=w0-w(n),并利用 P=Rwo 。,则将式(1-6)写成v(n)的表达式为 )]([)()]1([n v E uR I n v E -=+ （2-1） 当R 为实数阵时有T =R Q ΛQ ,代入上式可得 )]([)()]1([n v E Q u I Q n v E T Λ-=+ (2-2)