（计算机应用技术专业论文）蛙跳算法的研究与应用.pdf

摘要 摘要 随着计算机科学与技术的迅速发展，人类生存空间的扩大以及认识与改造世 界范围的拓宽，人们对科学技术提出了新的、更高的要求，其中高效的优化技术 和智能计算的要求日益迫切。蛙跳算法是一种新兴的群智能优化算法，概念简单， 易于实现。自从2 0 0 3 年e u s u f f 和l a n s e y 首次提出之后，蛙跳算法在一些领域获 得了成功应用。尽管蛙跳算法具有较强的全局搜索能力，但对于一些复杂问题的 求解仍存在收敛速度较慢、易于陷入局部极值的缺陷。此外，传统的蛙跳算法模 型较适合于解决连续优化问题，不太适合于解决离散的组合优化问题。为此，根 据蛙跳算法的优化机理，本文提出了一种新的离散化蛙跳求解算法，并结合简化 邻域搜索算法给出了三种改进的策略，在旅行商问题、考试时间安排问题、零空 闲流水线调度问题上的仿真实验验证了所提方法的有效性。主要研究成果和内容 如下： 首先，分析了蛙跳算法的优化机理，提出了一种适合求解复杂组合优化问题 的离散蛙跳算法，新算法通过采用新的个体产生方法扩展了传统蛙跳算法的求解 模型。 其次，为了提高离散蛙跳算法的求解性能，给出了三种改进策略：1 ) 根据 算法中种群对局部极值和全局极值依赖性较大的特点，结合邻域搜索算法，改进 了算法的收敛速度；2 ) 通过增加扰动策略，扩大局部极值和全局极值的搜索范 围，提高了算法的时间性能；3 ) 利用模拟退火算法具有较强局部搜索能力的特 点，将离散蛙跳算法与模拟退火的思想相结合，既能有效地克服陷入局部最优， 又能获得好的搜索效率。 最后，针对旅行商、考试时间安排、零空闲流水线调度这三种受约束的、离 散的组合优化问题，采用所提出的离散蛙跳算法及其改进算法进行了仿真实验， 结果表明了所提算法及改进策略的有效性。 关键词离散蛙跳算法；组合优化问题；旅行商问题；考试时间安排；零空闲流 水线调度 a b s 仃a c t a b s tr a c t w i t ht h er a p i dd e v e l o p m e n to ft h ec o m p u t e rs c i e n c ea n dt e c h n o l o g y , p e o p l e s l i v i n gs p a c eh a sb e e ne n l a r g e d ，a n dt h ef i e l di nw h i c hp e o p l er e c o g n i z ea n dc h a n g et h e 。 w o r l dh a sb e e nb r o a d e n t h ed e m a n df o rs c i e n c ea n dt e c h n o l o g yi si ni n c r e a s e t h e r e f o r eh i g h p e r f o r m a n c eo p t i m i z i n gt e c h n o l o g ya n di n t e l l i g e n c eo p t i m i z a t i o ni si n u r g e n tn e e d t h es h u f f l e df r o gl e a p i n ga l g o r i t h m ( s f l a ) i sak i n do fr i s i n g s w a r m i n t e l l i g e n c eo p t i m i z e r i t sc o n c e p ti ss i m p l ea n di t i se a s yt ob ei m p l e m e n t e d a f t e r b e i n gp r e s e n t e db ye u s u f fa n dl a n s e yi n2 0 0 3 ，i th a sb e e ns u c c e s s f u l l ya p p l i e dt o s o m ef i e l d s t h es h u f f l e df r o gl e a p i n ga l g o r i t h mh a sas t r o n ga b i l i t yt oa c h i e v et h e m o s to p t i m i s t i cr e s u l t m e a n w h i l ei th a sad i s a d v a n t a g es of a ra si t sl o c a lm i n i m u mi s c o n c e r n e dw h e nu s e do ns o m ec o m p l i c a t e dc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m s a n d t h et r a d i t i o n a lm o d e lo fs f l ai sa p p l i e dt oc o n t i n o u so p t i m i z a t i o n p r o b l e m s ，i ti sn o tf i tf o rd i s c r e t ec o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m s s ob a s e d o nt h e s t u d y o ft h em e c h a n i s mo f s f l a ，d i s c r e t e s h u f f l e d f r o gl e a p i n g a l g o r i t h m ( d s f l a ) i sp r o s e n t e d ，a n de m p l o y st h es i m p l en e i g h b o r h o o ds e a r c h t o p r e s e n t t h r e ei m p r o v e m e n t s t r a t e g i e s t h ee x p e r i m e n t s o nt r a v e l l i n gs a l e s m a n p r o b l e m ( t s p ) 、e x a m i n a t i o nt i m e t a b l i n gp r o b l e m ( e t p ) a n dn oi d l ep e r m u t a t i o nf l o w s h o pp r o b l e m ( n i f s ) h a v eb e e nd o n e ，a n dt h er e s u l t s s h o wt h a tt h e p r o p o s e d a l g o r i t h ma n di t si m p r o v e m e n t sa r ee f f e c t i v ea n de f f i c i e n t t h ep r i m a r yc o n t e n t sa n d r e s u l t sa r ef o l l o w i n g f i r s t ，b a s e do nt h ea n a l y s i so f t h es f l a so p t i m i z a t i o nm e c h a n i s m ，d i s c r e t e s h u f f l e df r o ga l g o r i t h mf o rc o m p l e xc o m b i n a t i o n a lo p t i m i z a t i o np r o b l e m sw a sp u t f o r w a r d t h en e wa l g o r i t h ma d o p t san e wm e t h o do fi n d i v i d u a lp r o d u c t i o nt oe x t e n d t h et r a d i t i o n a lm o d e lo fs f l a s e c o n d l y , t oi m p r o v ed s f l a sp e r f o r m a n c e ，t h r e ei m p r o v e m e n ts t r a t e g i e sa r e p r e s e n t e d ：1 ) t h es w a r md e p e n d se x t r e m e l yo nt h el o c a lb e s jr e s u l ta n dt h eg r o u pb e s t r e s u l t b a e s e do nt h i sc h a r a c t e r , t h ei m p r o v e da l g o r i t h mw a sp r o p o s e de m p l o y st h e s i m p l en e i g h b o r h o o ds e a r c h ，a n di tc a ni m p r o v et h ec o n v e r g e n c er a t eo fd s f l a 2 ) a c c o r d i n gt oa d dt h ed i s t u r b a n c es t r a t e g yc a ne x p a n dt h es e a r c hs c o p eo fl o c a la n d g l o b a le x t r e m er e s u l t ，t h ea l g o r i t h m st i m ep e r f o r m a n c ew a sf u r t h e re n h a n c e d 3 ) s i m u l a t e da n n e a l i n ga l g o r i t h mh a sas t r o n ga b l i t yt oa c h i e v et h el o c a lo p t i m i s t i c r e s u l t s oc o m b i n a t i o ns aw i t hd s f l ac a nn o to n l ya v o i dl o c a lm i n i m u m i i i 北京工业大学工学硕士学位论文 e f f e c t i v e l y , b u ta l s og e tg o o ds e a r c he f f i c i e n c y f i n a l l y , t s p , e t pa n dn i f sw h i c ha r ec o n s t r a i n e da n dd i s c r e t ec o m b i n a t o r i a l o p t i m i z a t i o np r o b l e m s a r ed i s c u s s e di nt h e p a p e r u s i n gd s f l aa n dt h r e e i m p r o v e m e n ts t r a t e g i e s t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h ep r o p o s e da l g o r i t h m a n di t s i m p r o v e m e n t sa r ee f f e c t i v ea n de f f i c i e n t f o rd i f f e r e n ts c a l eb e n c h m a r k s p r o b l e m s k e yw ordsd i s c r e t es h u f f l e df r o gl e a p i n ga l g o r i t h m ；c o m b i n a t o r i a lo p t i m i z a i o n p r o b l e m s ；t r a v e l l i n g s a l e s m a np r o b l e m ；e x a m i n a t i o n t i m e t a b l i n g ；n o i d l e p e r m u t a t i o nf l o ws h o p i v 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：乏圣查女日期：竺芝：苎签名：芝丝随日期：竺互：苎 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：主至蚤延导师签名：垄5 延翌：日期：迦窆：之 第1 章绪论 第1 章绪论 优化是个古老的课题，它所研究的问题是在众多方案中寻找最优方案。长期 以来，人们对优化问题进行探讨和研究。早在1 7 世纪，英国n e w t o n 和德国 l e i b n i t z 发明的微积分就蕴含了优化的内容。而法国数学家c a u c h y 则首次采用 梯度下降法解决无约束优化问题，后来针对约束优化问题又提出了l a g r a n g e 乘 数法。人们关于优化问题的研究工作，随着历史的发展不断深入。但是，任何科 学的进步都受到历史条件的限制，直n - 十世纪四十年代，由于科学技术突飞猛 进地发展，尤其是高速数字计算机日益广泛应用，使优化问题的研究不仅成为一 种迫切需要，而且有了求解的有力工具。因此，优化理论和算法迅速发展起来， 形成一门新的学科。至今已出现线性规划、整数规划、非线性规划、几何规划、 动态规划、随机规划、网络流等许多分支。这些优化技术在实际应用中正发挥越 来越大的作用。不过随着人类生存空间的扩大，以及认识世界和改造世界范围的 拓宽，常规优化方法已经无法处理人们所面对的复杂问题，因此高效的优化算法 成为科学工作者的研究目标之一。 1 1 最优化问题 1 1 。1 最优化问题分类 优化方法涉及的工程领域很广，问题种类与性质繁多。归纳而言，最优化问 题可以分为无约束问题与约束优化问题两大类。若决策变量x 的解空间为r n ， 则该问题为无约束最优化问题；若决策变量x 的解空间受到一些约束函数的限 制，则该问题被称为约束优化问题。 按对象是连续状态还是离散状态，最优化问题也可分为函数优化问题和组合 优化问题两大类，其中函数优化问题的对象是一定区域内的连续变量，而组合优 化问题是解空间中的离散状态。 1 无约束最优化与约束优化 最优化问题的一般形式为 m i n f ( x ) j f j x 其中x r ”是决策变量，f ( x ) 为目标函数，xcr 一为约束集或可行域。特 别地，如果约束集x = r ”，则最优化问题( 1 1 ) 称为无约束最优化问题： 北京工业大学工学硕士学位论文 m i n f ( x ) 砌。 约束最优化问题通常写为 m i n f ( x ) ( 1 2 ) 毗( 力= 0 ，f e( 1 3 ) q ( x ) o , i e i 这里e 和分别是等式约束的指标集和不等式约束的指标集，q ( x ) 是约束 函数。 当目标函数和约束函数均为线性函数时，问题称为线性规划。当目标函数和 约束函数中至少有一个是变量x 的非线性函数时，问题称为非线性规划。此外， 根据决策变量、目标函数和要求的不同，最优化还分成了整数规划、动态规划、 网络规划、非光滑规划、随机规划、几何规划、多目标规划等若干分支。 2 函数优化与组合优化 函数优化问题通常可描述为：令5 ，为尺”上的有界子集( 即变量的定义域) ， f ：s r 为n 维实值函数，所谓函数厂在s 域上全局最小化就是寻求k s 使得 在s 域上全局最小，即垓s ：厂( 瓦。) 厂( 彳) 。 组合优化问题通常可描述为：令q s 。，s ：，s 。) 为所有状态构成的解空间， c ( s j ) 为状态j ，对应的目标函数值，要求寻找最优解j ，使得 v s q ，c ( s ) = m i n c ( s ，) 。组合优化往往涉及排序、分类、筛选等问题，它是运 筹学的一个重要分支，也一直是优化领域关注的主要对象。 典型的组合优化问题有旅行商问题( t r a v e l i n gs a l e s m a np r o b l e m ，t s p ) 、时间 表问题( t i m e t a b l i n gp r o b l e m ，t t p ) 、加工调度问题( s c h e d u l i n gp r o b l e m ，如 f l o w - s h o p ，j o b - s h o p ) 、o 一1 背包问题( k n a p s a c kp r o b l e m ) 、装箱问题( b i np a c k i n g p r o b l e m ) 、图着色问题( g r a p hc o l o r i n gp r o b l e m ) 、聚类问题( c l u s t e r i n gp r o b l e m ) 诂 c ro 1 1 2 局部极小和全局最小 极小点的类型有局部极小点和全局最小点两种i l j 。 定义1 1 如果存在万 0 ，使得对所有满足x r ”和p xl f ( x ) ，则称x 为，阳的严格全局最小点。 2 第1 章绪论 1 2 最优化方法 最优化理论与方法是- f - 应用性很强的年轻学科。它研究某些数学上定义的 问题的最优解，即对于给出的实际问题，从众多的方案中选出最优方案。但是线 性规划、非线性规划以及随机规划、非光滑规划、多目标规划、几何规划、整数 规划等这些传统的经典算法的计算复杂性一般很大，只适于求解小规模问题，在 工程中往往不实用。2 0 世纪8 0 年代以来，一些新颖的优化算法得到了迅速发展。 如人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k s ，a n n ) 在一定程度上模拟了人脑的组 织结构【2 j ；模拟退火( s i m u l a t e da n n e a l i n g ，s a ) 算法思路源于物理学中固体物质的 退火过程 3 】；禁忌搜索( t s ) 模拟了人类有记忆过程的智力过程 4 】等等。这些算法 有个共同点：都是通过模拟或揭示某些自然界的现象和过程得到发展，在优化领 域，有人称之为智能优化算法( i n t e l l i g e n to p t i m i z a t i o n a l g o r i t h m s ) 。而其中又有受 社会性生物行为启发产生的群智能算法。 群智能( s w a r mi n t e l l i g e n c e ) 中的群体( s w a n n ) 指的是“一组相互之间可以进行 直接通信或者间接通信( 通过改变局部环境) 的主体，这组主体能够合作进行分布 问题求解 。而所谓群集智能指的是“无智能的主体通过合作表现出智能行为的 特性”。群集智能在没有集中控制并且不提供全局模型的前提下，为寻找复杂的 分布式问题的解决方案提供了基础。如模拟自然生物进化这一“适者生存，优胜 劣汰 过程而得到的遗传算法【5 】( g e n e t i ca l t o r i t h m ，g a ) ，受到蚂蚁觅食时的通 信机制的启发d o r i g o 提出的蚁群优化算法( a n tc o l o n yo p t i m i z a t i o n ，a c o ) 嘲，对 鸟群捕食行为模拟的粒子群算法( p a r t i c l es w a r mo p t i m i z a t i o n ，p s o ) 1 7 1 8 1 ，另外还 有m e m e t i c 算法( m e m e t i ca l g o r i t h m ，m a ) 、蛙跳算法( s h u f f l e df r o gl e a p i n g a l g o r i t h m ，s f l a ) 等等。 蛙跳算法是最近发展起来的一种群智能算法，这种算法通过模拟青蛙觅食过 程中信息共享和交流的特点而产生。目前关于该算法的研究成果还很少。蛙跳算 法具有收敛速度快、算法模型简单、易于实现等特点。但是已有的蛙跳算法模型 不适合处理离散的组合优化问题，本文将着重解决蛙跳算法的离散化问题，并提 出相应的改进策略。 1 3 群智能技术发展现状 群智能有如下特点和优点：( 1 ) 无集中控制约束，不会因个别个体的故障影 响整个问题的求解，确保了系统具有更强的鲁棒性；( 2 ) 以非直接的信息交流方 式确保了系统的扩展性，由于系统中个体的增加而增加的通信开销也较少；( 3 ) 并行分布式算法模型，可充分利用多处理器，这样的分布模式更适合网络环境下 北京工业大学工学硕士学位论文 的工作状态；( 4 ) 对问题定义的连续性无特殊要求；( 5 ) 系统中每个个体的能力十 分简单，每个个体的执行时间也比较短，并且算法实现简单【9 j 。 不过群智能研究还处于萌芽阶段，存在很多问题。首先，它们都是概率算法， 从数学上对于它们的正确性与可靠性的证明还是比较困难的，所做的工作也比较 少。其次，这些算法都是专用的算法，一个算法只能解决某一类问题，各种算法 之间的相似性很差。其中，基于主体的仿真还存在着缺陷，虽说基于主体的仿真 已经取得了一定的成果，但是有一些研究者对于这种方法仍然存在一定质疑，主 要有三点：首先，并不是总能从涌现的群体行为中推导出个体的行为；其次，真 实生物个体如此复杂，以至于几乎不可能在一个仿真系统中完成复制；第三，简 单的规则产生类似生命的群体行为并不能保证真实的生态系统的确遵循这些简 单的规则。 由此可见，群智能的研究还处于初级阶段，并且存在许多困难，但是可以预 言群智能的研究代表了以后计算机研究发展的一个重要方向。国外的学者发明了 很多群智能仿生算法并利用其解决复杂的工程问题，国内的很多学者主要研究方 向在算法的改进和应用，很少有学者提出过得到广泛认可的群智能算法。归结起 原因，主要是对技术背景和算法发现规律认识不够。 1 4 本文的组织 本文共六章，具体内容的组织如下： 第一章对s f l a 相关的基础知识进行回顾，主要介绍了优化问题、进化计算 和群体智能技术的发展现状。 第二章主要介绍蛙跳算法的相关内容，如理论基础、优化机理以及相关研究 成果，并主要介绍了蛙跳算法的步骤、模型，以及算法参数的设置，另外，阐述 了蛙跳算法的进一步发展情况等。 第三章提出适合解决旅行商等组合优化问题的离散蛙跳算法( d i s c r e t e s h u f f l e df r o gl e a p i n ga l g o r i t h m ，d s f l a ) ，并结合邻域搜索算法和模拟退火的思 想对算法进行了改进。通过旅行商问题进行仿真试验，结果表明了离散蛙跳算法 及其改进策略的有效性。 第四章首先对于考试时间安排问题( e x a m i n a t i o nt i m e t a b l i n gp r o b l e m ，e t p ) 这一复杂的多约束问题进行了介绍，然后通过基于时间序列的解编码方式和新的 更新算子，建立e t p 问题的离散蛙跳算法求解模型，接着结合简化邻域搜索算 法以及增加扰动给出了改进策略，最后应用d s f l a 算法求解e t p 问题。 第五章介绍了零空闲流水线调度问题的概况，结合相关文献中的邻域搜索方 法以及模拟退火算法的思想，应用离散蛙跳算法进行求解，并通过仿真试验进行 4 第1 章绪论 验证，表明了算法的有效性。 第六章对全文进行了总结，并给出了一些关于未来研究的展望。 第2 章蛙跳算法 2 1 算法的理论基础 第2 章蛙跳算法 蛙跳算法是新发展起来的一类算法。是一种启发式算法，它通过启发函数( 某 一数学函数) 进行启发式搜索，从而找到问题的解【1 0 】。事实上，蛙跳算法结合 了以遗传行为为基础的m e m e t i c 算法和以社会行为为基础的粒子群优化p s o 算 法的优点【1 1 1 。 2 1 1m e m e t i c 算法 m e m e t i c 算法是一种通过启发式搜索解决优化问题的群智能算法，受 d a w k i n 提出的m e m e 概念的启发而出现的。1 9 8 9 年，由m o s c a t o 第一次使用这 种算法。“m e m e t i c ”来自于单词“m e m e 1 2 】，m e m e 指的是寄存于人或动物的 大脑中能指导他们的行为并能传播的信息。m e m e 的内容，被称为m e m o t y p e ， 类似于基因中的染色体。一个想法或信息直到它被重复或传播才能成为一个 m e m e 。所有可传播的知识都是m e m e t i c 。这种算法和遗传算法相似，不同的是， 在g a s 中，组成染色体的元素被称为m e m e s ，而不是基因。m e m e t i c 算法的特 征是所有的染色体和后代可以在进化之前通过局部搜索获得一些经验【l 引。这样， m e m e t i c 算法通常被描述为增加了局部搜索的遗传算、法【1 4 j 。 2 1 2 粒子群算法 粒子群优化( p a r t i c l es w a r mo p t i m i z e ，p s o ) 算法由k e n n e d y 和e b e r h a r t 于19 9 5 年提出的【7 】【8 】，是一种基于群智能( s w a r mi n t e l l i g e n c e ) 方法的演化计算技术。p s o 算法通过模拟鸟群的捕食行为来实现优化问题的求解。首先在解空间内随机初始 化乌群，鸟群中的每一只鸟称为“粒子 ，这些“粒子”具有位置和速度两个特 征，在解空间内以某种规律移动，经过若干次迭代后找到所求解问题的最优解。 在每一次迭代中，粒子通过跟踪两个极值来更新自己的速度和位置。第一个是粒 子本身的最优解只。，另一个极值是整个粒子群目前找到的最优解g 胁，。p s 0 的速度、位置算式表示如下： 旷1 = g ) k - i v i + q r a n d ( 一x ；) + c 2 r a n d ( 霹) ( 2 1 ) 对= 对+ k “1( 2 2 ) 式中，形t 为粒子f 在第k 次迭代中的速度；彳j 为粒子f 在第k 次迭代中的位 北京工业大学工学硕士学位论文 置；f 为粒子i 的个体极值；g 为在第k 次迭代中的全局极值；g a n d o 为在区 问【o ，l 】上的髓机数；为惯性权重：q 是认知系数调节向芹的飞行步长；c ：是 社会系数，调节向g 的飞行步长。迭代过程中，粒子的速度和位置都限制在特 定的范围内，同时一和g 不断更新，最后输出萨就是全局最优解。 2 2 蛙跳算法的机理 图2 - 1 是蛙跳算法的原理示意图 图2 - 1 蛙跳算法的图解“ f i g u r e2 - 1s h u f f l e d f r o g l e a p i n g 1 1 】 如图所示，在s f l a 中，种群由很多青蛙组成，每只青蛙代表一个解。种群 被分成了多个子群，每个子群包括一定数量的青蛙，称为一个m c m e p l e x 。不同 的m e m e p l e x 可以看作是具有不同文化的青蛙群，分别执行局部搜索。在每个 m e m e p l e x 中，每只青蛙都有自己的想法，并且还受其它青蛙想法的影响，通过 m e m e t i e 算法来进化发展。这样，经过一定的m e m e t i c 进化以及跳跃过程，这些 想法思路就在各个m e m e p l e x 中传播开来【1 5 i 。然后，继续局部搜索和跳跃，直到 收敛标准满足为止。 2 3 算法的相关研究现状 目前仅有很少的关于蛙跳算法的研究，相关的成果如下： 2 0 0 3 年e u s u f f 和l a n s e y 【1 0 首次将这种算法用来解决管道网络扩充中的管道 尺寸最小化问题，在s f l a 基础上提出了一个计算模型s f l a n e t ，并且为了评 价该模型的性能在一些实例上进行了测试。 2 0 0 5 年e l b e l t a g i 等在连续优化和离散优化方面将遗传算法、m e m e t i c 算法、 微粒群算法、蚁群算法和蛙跳算法五种进化算法的模型和结果进行了比较【。 实验结果表明：蛙跳算法在解决某些连续函数问题时成功率和收敛速度优于遗传 算法，近似于粒子群算法。 2 0 0 6 年e u s u f f 等将发展了的蛙跳算法用于解决组合优化问题【l q ，通过具体 第2 章蛙跳算法 应用得出：蛙跳算法是一种解决组合优化问题的有效工具，在收敛效果和速度上 优于遗传算法。 2 0 0 7 年，a l i r e z ar a h i m i v a h e d 等提出了混合多目标蛙跳算法h m o s f l a 用 于解决多目标的混合型装配线排序问题，并与p s n cg a ，n s g a i i ，和 s p e a i i 三种多目标遗传进化算法m o g a 相比较，得出：h m o s f l a 的性能优 于m o g a ，这一优势在求解大型问题时尤为突出【l 7 1 。 国内学者直到2 0 0 7 年才开始对蛙跳算法予以关注，相关成果更是很少，主 要成果包括： 2 0 0 7 年，王辉，钱锋讨论了四种群体智能优化算法一蚁群算法、微粒群 算法、人工鱼群算法和混合蛙跳算法，对其算法的原理、发展及应用进行了综述。 提出了群体智能优化算法统一框架模式，并对群体智能优化算法进一步发展进行 了讨论l 博j 。 2 0 0 7 年，李英海等针对蛙跳算法局部更新策略引起的更新操作前后个体空 间位置变化较大，容易降低收敛速度这一问题，提出了一种基于阈值选择策略的 改进混合蛙跳算法。通过不满足阈值条件的个体分量不予更新的策略，减少了个 体空间差异，从而改善算法性能【l 9 1 。 2 4 标准蛙跳算法的步骤 全局搜索 s t e p0 初始化。选择m 和以，m 表示m e m e p l e x 的数量，即子群的数量，n 表示每个m e m e p l e x 中青蛙的个数。那么，整个种群的数量f = mx n 。 s t e p1 生成一个虚拟种群。在可行解空间qc 吼d ，生成，个青蛙u d ) ， 矾矽，研功，其中d 为维变量，每一个青蛙( f r o g ) 原本代表青蛙的当前位置， 对于优化问题则表示解空间的一个候选解。第f 个青蛙可以表示为 u ( i ) = ( 叫，昕，g ) 。计算出的u ( i ) 的性能用刑表示。 s t e p2 对青蛙划分等级。将f 只青蛙按照性能好坏依次排列，生成数组 炸 喇。删，i = l ，2 j ：毋，这样的话，i = l 表示这只青蛙的位置( 性能) 最好，记 录下种群中最好青蛙的位置最= 泖) 。 s t e p3 将青蛙分组，放入不同的m e m e p l e x 。将数组肖分成m 个m e m e p l e x ： x ，蔓，匕。 每个 m e m e p l e x中包含 以个青蛙， 即： k = u ( ) ，( ，) i u ( ) t = u ( k + m ( j 一1 ) ) ，厂( ，) 。= f ( k + m ( j 1 ) ) ，j = 1 7 2 ，z ) ， 其中k = l ，z ：聊；比如m = 3 ，那么第1 只青蛙进入m e m e p l e x l ，第2 只青蛙进 入m e m e p l e x 2 ，第3 只青蛙进入m e m e p l e x 3 ，第4 只青蛙进入m e m e p l e x l ，等等。 s t e p4 每组m e m e p l e x 中执行m e m e t i c 进化。在每组m e m e p l e x 中，每只青 9 北京工业大学工学硕士学位论文 蛙受到其它青蛙想法的影响，通过m e m e t i c 进化，使得每只青蛙朝目标位置逼近。 以下是每个m e m e p l e x 中m e m e t i c 进化的详细步骤。 l o c a le x p l o r a t i o n 局部搜索 s t e p4 - 0 设i m - - o ，i m 表示对m e m e p l e x 的计数，在0 到m 之间变化，与 m e m e p l e x 的数量m 比较。设n - - 0 ，i n 表示进化次数，与每组m e m e p l e x 中允 许的最大进化次数比较。在每组m e m e p l e x 中，用尸6 和尸w 分别表示性能( 位 置) 最好的和最坏的青蛙，用最表示整个种群中最好的青蛙。在每一轮的进化 中，改善最坏青蛙凡的位置，注意，并非对所有的青蛙都优化。 s t e p4 一l m = m + l 。 s t e p4 - 2f = f + 1 。 s t e p4 3 调整最坏青蛙的位置，方法如下： 青蛙移动的距离d i - - r a n d 0 枣( p b - p w )( 2 3 ) 新的位置p w - - p w ( 当前位置) + d f ，( d 一d i 一d i 。) ( 2 - 4 ) 其中，r a n d 0 是0 到1 之间的随机数，d ，麟是允许青蛙移动的最大距离。 s t e p4 - 4 如果上述过程能够使得青蛙有一个更好的位置，即能够产生一个更 好的解，那么就用新位置的青蛙取代原来的青蛙；否则，用乓代替n ，重复上 述过程。 s t e p4 5 如果上述方法仍不能生成更好的青蛙，那么就随机生成一个新解取 代原来最坏的青蛙尸w 。 s t e p4 6 如果i n n ，那么执行4 2 。 s t e p4 - 7 如果m m ，那么执行4 1 ，否则青蛙跳跃，重新执行全局搜索。 s t e p5 青蛙在m e m e p l e x 之间跳跃移动。在每个m e m e p l e x 中执行了一定的 m e m e t i c 进化之后，将各个子群r l ，k ，匕合并到疋即x = k ，k = 1 7 2 ，m ) 。将 x 重新按降序排列，并更新种群中最好的青蛙以。 s t e p6 检查终止条件。如果迭代终止条件满足，则停止。否则，重新执行 s t e p 3 。一般情况下，当执行了一定次数的循环进化，代表最好解的青蛙不再改 变的时候，算法停止。有时也通过定义最大的进化次数作为停止标准。 下面描述蛙跳算法的流程：图2 2 ( a ) 是蛙跳算法的流程图【2 0 】，图2 - 2 ( b ) 是蛙 跳算法流程中局部搜索m e m e t i c 算法的具体步骤。 1 0 第2 章蛙跳算法 确定种群大小f ，m e m e p l e x 的数量m ，每组m e m e p l e x 中最 大迭代次数甜，每组m e m e p l e x 中青蛙的个数刀 j 初始化种群 0 计算每只青蛙的适配值 0 将所有青蛙按适配值降序排列 - l 将f 只青蛙分别放在m 组m e m e p l e x 中 0 用m e m e t i c 算法局部搜索( a ) 上 青蛙在不同m e m e p l e x 中跳跃：重新汇合、排序 上 构造下一代的新种群 输出最优解尸g 图2 - 2 ( a ) 蛙跳算法流程图 f i g u r e2 - 2 ( a ) s h u f f l e df r o gl e a p i n ga l g o r i t h mf l o wd i a g r a m 北京工业大学工学硕士学位论文 图2 - 2 ( b ) 局部搜索中m e m e t i c 算法流程图 f i g u r e 2 2 ( b ) m e m e t i ca l g o r i t h mf l o wd i a g r a m i nl o c a ls e a r c h 1 2 第2 章蛙跳算法 2 5 蛙跳算法的模型 图2 3 显示了算法的局部和全局搜索过程。 图2 3 一个小规模的蛙跳算法模型【l 卅 ( a ) 种群的初始情况( 第一次循环开始时)( b ) 每个子群分别进化( 第一次循环结束时) ( c ) 蛙群跳跃( 第二次循环开始时)( d ) 每个子群分别进化( 第二次循环结束时) f i g u r e2 3i l l u s t r a t i o no fs f l ao nas m a l ls c a l e 1 0 】 ( a ) i n i t i a lp o p u l a t i o no f v i r t u a lf r o g s ( a tt h eb e g i n n i n go f t i m el o o p1 ) ( b ) i n d e p e n d e n t l ye v o l v e dm e m e p l e x e s ( a tt h ee n do ft i m el o o p1 ) ( c ) s h u f f l e df r o g s ( a tt h eb e g i n n i n go ft i m el o o p2 ) ( d ) i n d e p e n d e n t l ye v o l v e dm e m e p l e x e s ( a tt h ee n do fl o o p2 ) 在图2 - 3 ( a ) q b ，随机选择了1 5 只具有不同思想( m e m e ) 的青蛙，它们被分成 了3 个子群( m e m e p l e x ) ，分别用三角形、正方形和圆圈来表示。在每个子群中， 性能较差的青蛙会向性能优越的青蛙学习，从而提高自身的思想。在每个子群中， 选择合适的参数n ，即每个子群中进化的代数，使得所有的青蛙都有机会交流思 想。图2 - 3 ( b ) 显示了在一轮循环结束后每只青蛙的位置，可以看出，每个子群 都分别独立的进化，各自进行局部搜索。 在这个过程中，可能会发现有个别青蛙不适合它所在的群体，如图2 - 3 ( b ) 中 圆圈标注的用正方形表示的这只青蛙，那么这时就随机产生一只有不同思想的青 北京工业大学工学硕士学位论文 蛙替代原来的青蛙。 每个子群经过步进化后，所有的青蛙再进行跳跃，重新分组；形成不同 的子群，如图2 - 3 ( e ) 所示。这样，拥有思想不同的青蛙又汇集在各个子群中，然 后，每个子群再分别进化。图2 3 ( d ) 显示了经过一定次数的进化后三个青蛙子群 的情况，除了个别青蛙外，几乎所有的青蛙都聚集在最优解附近。显然，所有青 蛙都受到代表最优解的青蛙的影响。 2 6 算法参数 和其它的算法一样，参数的选择也是十分重要的。在蛙跳算法中，共有五个 参数【1 1 】：种群中青蛙的数量f ；子群( m e m e p l e x ) 的数量聊；每个子群中进化的 代数；允许青蛙移动的最大距离d 一；允许整个种群进化的最多代数h e r 。 根据相关实验研究分析，通常情况下，样本容量，也就是种群中青蛙的数量 f ，是最重要的参数。f 的值一般和问题的复杂性相关，样本容量越大，算法找 到或接近全局最优的概率也就越大。对于子群数量聊的选择，很重要的一点是 要确保子群中青蛙的数量珂( 庐聊力) 不能太小。如果门太小，局部进行m e m e t i c 进化搜索的优点就会丢失。参数的选择也要大小适中，如果太小，会使得 青蛙子群频繁的跳跃，减少了信息之间的交流，相反，如果太大，又会使得 每个子群更容易陷入局部最优。第四个参数，允许青蛙移动的最大距离巩甜，可 以控制算法进行全局搜索的能力。如果设置d 聊甜太小，会减少算法全局搜索的 能力，使得算法容易陷入局部搜索，而如果d 一太大，又很可能使得算法错过 真正的最优解。最后一个参数i t e r 的设置，一般也和问题的规模相关，问题规模 越大，i t e r 的值相应的也越大。 对于参数的设置，目前没有指导性的原则，大部分都是通过试验测试得到。 如何设置合适的参数，也是蛙跳算法下一步的一个研究方向。 2 7 蛙跳算法的进一步发展 蛙跳算法是一种新兴的群智能算法，对于该算法的研究还处于非常初步的阶 段，仅有极少的文献，不过已经显示出较大的潜力，存在很大的发展空间。 1 ) 适用范围。s f l a 的应用仅在函数优化、聚类、组合优化、多目标优化方 面有较少的应用，并且其应用大多数还和具体问题相关，仅停留在研究阶 段，其它的很多应用还尚未开始。显然，s f l a 不会仅仅局限于目前的这 些领域。如果将s f l a 引入机器学习、自动控制等领域，将大大地促进算 法的研究和发展。 1 4 第2 章蛙跳算法 2 ) 数学基础。s f l a 的有效性在一