（通信与信息系统专业论文）拟梯度技术及其在群体搜索中的应用.pdf

摘要 单纯形算法是一种直接搜索优化算法。它不需要目标函数解析，且运算简单， 是一种有效的局部搜索方法，在很多领域得到了成功的应用。但是单纯形算法也 存在搜索速度不够快、不易收敛、全局搜索能力差等缺点。 进化算法( 如粒子群算法、遗传算法) 是一种生物启发式随机搜索算法。算 法基于仿生原理，简单通用、鲁棒性强、适合于并行处理，是有效的全局搜索方 法，在多个方面得到了成功的应用。但常见的进化算法也存在易早熟、局部搜索 能力差等缺点。 在对单纯形算法和进化算法进行深入分析的基础上，本文做了如下研究工 作： 第一，基于梯度搜索在局部寻优中的高效性，提出了拟梯度的概念，并将其 应用于基本单纯形算法中，形成了一种单纯形拟梯度搜索算法，提高了寻优速度 和寻优质量。 第二，在遗传算法中引入单纯形空间划分思想，实现了个体的单纯形遗传。 测试结果表明，该方法能有效地防止早熟收敛。 第三，将单纯形思想引入粒子群算法之中，实现了粒子的单纯形定位。实验 表明，在相同测试条件下，此单纯形粒子群算法在搜索速度和精度上都有较大的 提高。 最后，将基于单纯形的进化算法应用于电信网络的动态路由优化。 关键词：单纯形算法；遗传算法；粒子群算法；拟梯度；动态路由 a b s t r a c t n l es i m p l e xm e t h o df s m ) i sa no p t i m i z a t i o na l g o r i t h mf o rd i r e c t l y s e a r c h i n g w h i c hi ss i m p l ea n de f f e c t i v ei nl o c a ls e a r c ha n dh a sb e e ns u c c e s s f u l l ya p p l i e di n m a n yf i e l d s i td o e s n tr e q u i r ew h e t h e rt h eo b j e c t i v ef u n c t i o ni sa n a l y t i c a l b u ti th a s s o m ed i s a d v a n t a g e ss u c ha sl o ws e a r c hs p e e d ，b a dc o n v e r g e n c e ，l i m i t e dg l o b a ls e a r c h c a p a b i l i t y e v o l u t i o n a r ya l g o r i t h m s ，s u c ha sp a r t i c l es w a r mo 砸i i l i z a t i o n ( p s o ) a n dg e n e t i c a l g o r i t h m ( g a ) ，a r er a n d o ms e a r c hm e t h o d si n s p i r e db yb i o l o g i c a le v o l u t i o n t h e y a r es i m p l e ，r o b u s ta n da r ef i tt ob eu s e di nt h ep a r a l l e lc o m p u t a t i o n e v o l u t i o n a r y a l g o r i t h m sa r ev e r ye f f e c t i v ei ng l o b a ls e a r c h ，a n dh a v eb e e ns u c c e s s f u l l ya p p l i e di n m a n ye n g i n e e r i n g h o w e v e r t h ec o m m o ne v o l u t i o n a r ya l g o r i t h m sh a v es o m e d i s a d v a n t a g e ss u c ha sp r e m a t u r e ，b a dl o c a ls e a r c hc a p a b i l i 妙 t h es ma n de v o l u t i o n a r ya l g o r i t h m sa r ea n a l y z e dd e e p l yi nt h i st h e s i s 1 1 1 em a i n w o r k sa r ea sf o l l o w ： f i r s t l y , b a s e do nt h eh i g he f f i c i e n c yo ft h eg r a d i e n ts e a r c hi nl o c a ls e a r c h ，t h e c o n c e p t i o no fp s e u d o - g r a d i e n t i s p r e s e n t e da n da p p l i e dt ot h es m t h e n a p s e u d o g r a d i e n ts mi sp r o p o s e d i ta c c e l e r a t e st h ec o n v e r g e n c ea n dm e l i o r a t e st h e q u a l i t yo f t h eo p t i m i z a t i o n s e c o n d l y , t h ei d e ao ft h es p a c ep a r t i t i o nb ym e a n so ft h es mi si n t r o d u c e di nt h e g a ，s ot h a tt h ei n d i v i d u a l so ft h ep o p u l a t i o na r eo p e r a t e di nt h es mf o r m t h e e x p e r i m e n t ss h o wt h a tt h ep r o p o s e dm e t h o dc a np r e v e n tp r e m a t u r ec o n v e r g e n c e t h i r d l y ，t h ei d e ao ft h es mi si n t r o d u c e di nt h ep s o ，s ot h a tt h ep a r t i c l e si nt h e s w a r t ha r e1 0 c a t e di nt h es mf o r m u n d e rt h es a m ec o n d i t i o n t h ee x p e r i m e n t ss h o w t h a tt h es m p s oa l g o r i t h mi m p r o v e st h e c o n v e r g e n c ea n dt h eq u a l i t y o ft h e o p t i m i z a t i o n a tt 1 1 ee n do ft h i st h e s i s ，t h ee v o l u t i o n a r ya l g o r i t h mm o d i f i e db yt 1 ”s mi s a p p l i e dt ot h eo p t i m i z a t i o no f t h ed y n a m i cr o u t i n go f t h et e l e c o m m u n i c a t i o nn e t w o r k k e yw o r d s ：s i m p l e xm e t h o d ；p a r t i c l es w a r mo p t i m i z m i o n ；g e n e t i ca l g o r i t h m ； p s e u d o g r a d i e n t ；d y n a m i cr o u t i n g i i 学位论文独创性声明： 本人所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果。与我一同工作的同事对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。如不实，本人负全部责任。 论文作者( 签名) ： ( 注：手写亲笔签名) 刎年；月衫日 学位论文使用授权说明 河海大学、中国科学技术信息研究所、国家图书馆、中国学术期刊( 光盘 版) 电子杂志社有权保留本人所送交学位论文的复印件或电子文档，可以采用 影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内容 相一致。除在保密期内的保密论文外，允许论文被查阅和借阅。论文全部或部 分内容的公布( 包括刊登) 授权河海大学研究生院办理。 论文作者( 签名) ： ( 注：手写亲笔签名)爿， 貌一叩 弓月髟e t 河海大学硕上学位论文第一章绪论 第一章绪论 i 1 优化算法概述 许多实际问题的求解大多都可转化为用最优化方法来求解。最优化方法即 是解决最优化问题的方法。最优化闯题是指在一定的约束条件下，决定某个或 某些可控制的因素应有的合理取值，使所选定的目标达到最优的问题。最优化 方法在数学上是一种求极值的方法，为应用数学的一个分支，是新兴的数学理 论之一。虽然最优化方法的最优值是一个相对概念，并不完全等于数学上的极 值，但在大多数用最优化方法处理和解决的问题中，最优值都是用最大值或最 小值来表示。现今，最优化方法在： 程技术及管理领域的发展已经形成了一门 重要的技术科学，它是现代工程分析最佳设计的四种主要方法1 1 ( 有限元分析、 最优化方法、动态设计和数值仿真) 之一。 最优化方法的出现，可以追溯到牛顿( n e w t o n ) 、拉格朗日( l a g r a n g e ) 和柯西( c a u c h y ) 时代。由于牛顿和莱布尼兹( l e i b n i t z ) 对微积分的贡献， 才使具有最优化思想的微分学的发展成为可能；而伯努利( b e r n o u l l i ) 、欧拉 ( e u l e r ) 和拉格朗日等人则奠定了变分学的基础；柯西最早应用最速下降法求 解无约束极小化问题。在二次世界大战期自j ，出于满足军事上的需要产生了运 筹学。战后运筹学开始转向民用工业的应用，并不断取得进展。在此基础上， 到2 0 世纪6 0 年代，最优化方法发展并形成为一门新兴的基础学科。而后，随着 近代科学技术发展的需要，特别使由于计算机技术的飞速发展，促迸了最优化 的迅速发展。很快这门新兴的基础科学便渗透到各种技术领域，形成了最优化 方法或最优化技术这门应用科学。 在传统的最优化方法中，大致分为梯度搜索和非梯度搜索【l 】。对于梯度搜 索，首先需要已知目标函数是否连续可导，且需要可导的解析表达式，需要利 用函数的一阶、二阶导数及偏导数矩阵来确定最优方向和最优步长。其代表性 的方法有最优梯度法，共轭梯度法，牛顿法及变尺度法等等。梯度搜索，一般 利用函数在某一点附近的梯度信息，这是目标函数的一种局部的性质，并不是 全局的性质。所以初始值的选取会影响到是否收敛到全局最优点。相对于非梯 度搜索，梯度搜索收敛速度快，但是应用条件苛刻，不能广泛应用，且计算复 杂。对于非梯度搜索，只需要进行函数值的计算与比较来确定最优化的方向和 步长。其代表性的方法有进退法，黄金分割法，坐标轮换法，单纯形算法等等。 此类方法无需知道函数的解析式，是否连续、可导等等，只需要知道该点的函 数值即可。所以应用范围广泛，适应性强，计算简单易行。但相对于梯度搜索 来说，其搜索速度相对较慢。梯度搜索和非梯度搜索都是局部搜索能力较强的 河海大学硕士学位论文 拟梯度技术及其在群体搜索中的应用 算法，都有共同的缺点：易陷入局部极值。 以梯度为基础的优化方法占了很重要的位置。这类方法基于的理论是，沿 梯度方向函数值增长最快；沿负梯度方向函数值下降最快，为最速下降方向。 此类方法一般都有收敛速度快，这是因为相对与直接搜索的传统最优化方法，其 通常要计算目标函数的一阶或二阶偏导数，而不是直接比较函数值的大小，利 用了更多的函数信息，所以比直接搜索方法更有效。但是这类方法主要适用于 连续可导的目标函数，而且有时计算量相当大。对于不可解析的目标函数或某 点不可知其导数时，此类方法就无能为力，但是用其他的传统优化方法又存在 收敛速度慢，优化效果不好的情况。针对这些情况本文结合梯度的意义提出一 种拟梯度的概念：利用函数的多点信息，拟合出一搜索方向，沿该方向函数值 迅速下降或上升。从而使寻优摆脱对目标函数是否可解析的依赖，加速非梯度 搜索。 除传统优化算法外，还有用于全局搜索的智能优化算法【2 】。智能优化算法 是一种借鉴和利用自然界中自然现象或生物体的各种原理和机理而开发的并 具有自适应环境能力的计算方法。其代表性的方法有模拟退火法( s a ) 、遗传 算法( o a ) 、粒子群算法( p s o ) 、神经网络( n n ) 等。以粒子群算法【3 j ( p s o ) 为例， i d e b e r h a r t 博i j f f i k e n n e d y 博士发明，源于对鸟群捕食的行为研究。p s o 把系统初始化为一组随机解，通过迭代在解空问追随最优的粒子并行搜寻最优 值。由于此类算法自身是启发式随机算法，因此具有一般性及易用性，对初始 值的选取没有要求，整体搜索速度较快且易于获得满意的全局最优点。但是对 局部最优值搜索馒及搜索效率低，比较复杂。 1 2 单纯形算法概述及其研究现状 针对无约束极小化问题，s p l e n d l e y 等 4 j 于1 9 6 2 年首先提出了基于正规单纯 形( s i m p l e xm e t h o d ，s m ) 的求解方案。n e l d e r 和m e a d 5 j 在s p l e n d l e y 等人的工 作基础上，通过增加了延伸和压缩步骤，将正规单纯形扩展至任意单纯形，成为 现代数值方法中一种有效的最优化方法_ n m 单纯形算法。 为了提高n m 单纯形算法的搜索效率，不少学者在初始值的确定、扩展系 数的自适应、反射点的选取1 6 。j ，单纯形的重构1 8 j 等方面做了大量工作，增强了 单纯形算法的实用性。随着搜索空间复杂度增加，单纯形算法的局限性逐渐显露 出来，一些新的搜索算法( 如：遗传算法、蚁群算法、粒子群算法等一类受生物 启发的进化算法) 逐渐成为人们关注的重点。单纯形算法不需要待求优化问题的 可解析或可微，并能利用群体信息进行搜索，与进化算法具有极大的相似性。为 此，有不少学者将单纯形算法与进化算法相结合，提出了一些高效的搜索算法【9 河海大学硕士学位论文第一章绪论 1 ”。由此可见，单纯形算法不仅可以作为一些常见问题的优化工具，而且还可以 成为进化算法的一些改迸方法。 1 3 本文主要研究内容 本文主要是针对单纯形算法和粒子群算法进行改进，来满足实际需求。作者 主要对两种算法进行如下几方面的研究： 第一，通过分析基本单纯形算法的原理及其优缺点，结合梯度相关的思想方 法提出了拟梯度的概念，并将拟梯度应用于基本单纯形算法中，提高了基本单纯 形算法中各点信息的利用率，也提高了基本单纯形算法的寻优速度和寻优质量。 第二，签于单纯形算法易陷入局部极值点的缺点，通过研究全局搜索能力强 的如粒子群算法、遗传算法、蚁群算法等智能进化算法，将其中一些进化机制 引入单纯形算法，提出了单纯形遗传算法。测试结果表明，单纯形遗传算法既保 持了单纯形算法搜索速度快的特点，又在相当程度上克服了易于陷入局部极值的 缺点。 第三，比较单纯形算法和粒子群算法的原理，发现其中有相通的地方，但前 者是局部搜索能力强搜索速度快，后者是全局搜索能力强搜索速度慢，于是尝试 将单纯形算法的相关机制引入粒子群算法之中，提出单纯形粒子群算法。测试结 果表明，在相同测试条件下，此混合机制算法在搜索速度和精度上都有了较大的 提高。 第四，将单纯形遗传算法应用于实时性要求较高的电信网络的动态路由中， 通过在对5 个节点的全向网络的仿真实验，既满足了实时性要求，又得到了较好 的结果。 1 4 章节安排 本文章节安排如下： 第一章：绪论。介绍本文的研究背景、研究现状和本文的主要研究内容等。 第二章：基本单纯形算法。 第三章：拟梯度单纯形算法。将拟梯度技术引入单纯形算法。 第四章：单纯形遗传算法。将进化智能算法的机制引入到单纯形算法之中。 第五章：单纯形粒子群算法。将单纯形算法机制与粒子群算法机制混合。 第六章：单纯形遗传算法在动念路由中的应用 第七章：结论与展望。 河海大学硕士学位论文 拟梯度技术及其存群体搜索中的应用 第二章基本单纯形算法 2 1 单纯形算法概述 2 1 1 单纯形算法简介 单纯形是指设计空间中有n + 1 个顶点的几何体。 单纯形算法作为直接搜索数值解法之一，是利用单纯形的顶点，计算其函数 值，按一定的规则进行探测性搜索。通过对搜索区域内单纯形顶点的函数值进行 直接比较，可以判断目标函数的变化趋势，确定有利的搜索方向和步长，通过迭 代从一个顶点转换到另一个顶点，使目标函数下降函数。 2 1 2 单纯形算法基本步骤 n m 单纯形算法包括反射、扩展和压缩的计算过程【1 0 以求解二维函数的极 小值为例，图2 - 1 中日、厶g 为函数空间中的3 个初始候选解，其中日为最差 点、上为最好点、g 为次好点，即3 点函数值满足f n j 0 f z 。这样a h g l 构成一 个初始的二维单纯形。 s h e 图2 - 1n m 单纯形原理图 a ) 反射过程 取g 、l 连线的中点f 为反射中心， x f = x g + 勘( 2 - 1 ) 则在f 坍延长线上求出点h 关于点f 的反射点r 。若五魄，后) ，则点r 、g 、l 构成新的单纯形。 b ) 扩展过程 若五瓴，则说明沿原反射方向搜索有利，可将r 点扩展至e 点：若f z f g ，则说明点日沿原反射方向走的太远，应以指定的 步长退到点s ，形成新单纯形s g l 。若f r f 1 - 1 ，则以指定的步长退到点s ，形成 新单纯形s h l 。 若h r 上各点的函数值均大于詹，说明h r 是脊线，不能按日点的反对称 方向搜索，而应将初始单纯形压缩，保留最低点为顶点，形成单纯形h f l ，或 h3 g 1 l 。 形成一个新单纯形之后，按上述方法重复计算，直到满足精度要求。算法流 程如图2 2 所示： 图2 - 2n m 单纯形算法流程图 2 2 单纯形算法思想及其应用 单纯形算法概念简单，容易实现，在局部搜索极值具有快速、准确的特点， 应用十分广泛。一方面单纯形算法直接应用于实际工程项目，另一方面可以和其 他全局搜索算法融合来改善全局优化算法的寻优速度和寻优质量。 河海大学硕士学位论文拟梯度技术及其在群体搜索中的应用 第三章基于拟梯度的单纯形算法 3 1 拟梯度的概念 3 1 1 梯度的概念及其相关算法 一个n 维非线性函数冗p 的梯度定义为： v ，( 四2 面a f = 善，瓦a f 差 1 这是一个n 维偏导向量。令梯度向量p = 嘲，梯度的单位向量为： 。vr(j)p 壮丽网2 丽网 显然，梯度方向也就是函数的法线方向( 图3 - 1 ) ，负梯度方向与一s 同向。 x(k-i)x 图3 - 1 梯度示意图 另外，l i v j ( x ) l l , q 做梯度v j ( x ) 的模，亦称之为范数。模的计算公式为 i i v s ( x ) l l丽确 梯度方向的性质有：沿梯度方向函数值增长最快，为最速上升方向；沿负梯度方 向函数值下降最快，为最速下降方向。 基于梯度思想的无约束非线性最优化算法主要有最优梯度法，共轭梯度法、 牛顿法和变尺度法等。这些算法的思想都是利用梯度方向的性质，计算目标函数 的一阶或二阶偏导数，构造寻优方向，计算最优寻优步长。这种梯度算法利用了 根多的函数信息，一般比非梯度的直接搜索算法要快速高效。但是梯度算法必须 要求目标函数可解析，在实际问题中往往碰到的对象都是不可解析的。 河海大学硕士学位论文 第三章基于拟梯度的单纯形算法 3 1 2 拟梯度的概念 基于梯度思想的算法虽然高效，但是要求目标函数必须可解析，这大大限制 了其应用的范围。有没有一种算法既能像梯度算法那么高效，又不需要目标函数 解析呢? x1)x 图3 - 2 拟梯度示意图 将目光投向非梯度直接搜索算法中的单纯形算法( 如图3 - 2 所示) ，如本文 第二章所描述的单纯形算法有三个步骤，其中反射步骤中计算反射点的计算公式 为； x r = x f + y ( x f x h l 式中，7 是反射系数，凰是反射点，琢是反射中点，蜘是原单纯形中最差点，。 将3 一l 式整理得： x r = 一x h + ( 1 + ，) 爿_ 砾是新生成取代j 白的新点，厨相当于搜索方向向量，因此根据单纯形算法原理， 最差点目的下一个搜索位置可用如下通用公式描述： x ( _ 】 ) = x ( k 一1 ) + 五8 ( t 一1 )( 3 1 ) 其中，x ( k - b 为最差点日；柳动为日点的下一个搜索点( s 、s 、r 和e 中之) ： 口( 尼一1 ) 为胛向量的方向；五为压缩、反射或扩展系数。将式( 3 1 ) 与基于梯度搜 索的算法： x ( k ) = x ( k 一1 ) 一z v 丁( x ( 七一1 ) )( 3 2 ) 进行比较不难发现，单纯形算法在形式上与梯度搜索算法具有极大的相似之处。 其中充当方向向量的x f 点与梯度搜索算法中的梯度方向起的作用完全一致。 河海大学硕士学位论文 拟梯度技术及其在群体搜索中的应用 因此，借鉴梯度的意义，本文提出拟梯度的概念：通过有限的函数信息，拟 合成一拟梯度方向，沿此方向函数值快速下降。此拟梯度不需要求导数或偏导数， 只需要利用现有的函数值相关信息来确定。 3 2 基于拟梯度思想的单纯形算法 经过研究比较传统的最优化方法，发现单纯形算法的思想与拟梯度的思想不 谋而合。单纯形算法，是利用单纯形的顶点，计算其函数值，通过对搜索区间单 纯形顶点的函数值进行直接比较，可以判断目标函数的变化趋势，确定有利的搜 索方向和步长。单纯形的算法思想是最差点的反方向就是最优点，通过反射、扩 展、压缩三种过程来实现优化搜索。其中最差点的前进方向就是拟梯度方向。但 是原始的单纯形算法只利用了函数值的信息，利用到的信息量太少，对搜索步长 的选取不灵活，而且易于陷入局部极值。根据拟梯度的思想本文拟改进原始单纯 形算法的搜索过程，使搜索方向沿着函数值变化地更快的拟梯度方向，加速算法 的收敛速度。 基于这种相似的形式，单纯形算法中f 的作用就相当于梯度算法中日点的 负梯度方向。因此，f 点的确定十分重要。 根据n m 单纯形算法的搜索思想：“最优点应该在最差点的对立面”，则日 点搜索区域应该在一g h l 所张成的夹角内。由于点比g 点更靠近最优点，因 此，反射中心f 应该更靠近三点( 如图3 - 3 所示) 。遗憾的是，在单纯形算法中， 一直采用g l 中点来确定f 点位置。由此提出以下几种的改进方法【1 2 。 图3 - 3 拟梯度单纯形算法示意图 卜 x a ) 黄金分割单纯形算法 黄金分割方法。单纯形算法中通常采用二分法即第二章中式( 2 1 ) 对g 三进 行分割，现采用黄金分割率对g l 进行重新分割： 河海大学硬士学位论文 第三章基于拟梯度的