（计算机应用技术专业论文）基于干扰因子的qpso算法改进及其应用.pdf

摘要 摘要 群体智能算法是一种进化类算法，是解决优化问题特别是复杂优化问题的有效手 段。q p s o 是具有全局收敛性的一种新的群体智能算法，并且许多实际应用结果证明， q p s 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 ) 。因此，本文的 研究内容对于群体智能的发展具有一定的学术意义和应用价值。 本文首先阐述了传统进化算法一遗传算法( g e n e t i ca l g o r i t h m ，简称g a ) 、群体智能 算法中的粒子群算法( p s o ) 和具有量子行为粒子群算法( q u a n t u m b e h a v e dp a r t i c l e s w a r mo p t i m i z a t i o n ，简称q p s o ) ，针对具有量子行为粒子群算法存在的早熟现象，提 出了改进的q p s o 算法一基于干扰因子的量子粒子群算法( q u a n t u m b e h a v e dp a r t i c l e s w a r mo p t i m i z a t i o nw i t hd i s t u r b a n c e ) 。 在改进的q p s o 算法中引入干扰因子，使得算法能够持续地搜索解空间从而提高算 法的全局收敛能力，并且能够有效地避免早熟的发生。在算法搜索过程中引进了判断基 准一早熟因子，同时对粒子群的早熟因子设置阈值，当无效迭代高于该阈值时，采用干 扰因子操作改变群体的搜索空间，跳出局部收敛。通过几个常用标准测试函数的测试表 明，改进的q p s o 算法无论是算法性能还是算法稳定性都优于q p s o 和p s o 算法，因 此可以得出以下结论：q p s o 算法引入的干扰因子是解决算法早熟问题的有效途径。 其次，本文还研究了粒子群算法( p s o ) 和具有量子行为粒子群算法( q p s o ) 在 图像插值中的应用。图像插值是数字图像处理中的一项基础性技术，有着广泛的应用。 基于p s o 算法和q p s o 算法的图像插值方法，是在以线性最小均方差( l m m s e ) 所形 成的模型中寻找符合条件的最优高分辨率图像估计。图像插值结果表明，将p s o 和q p s o 应用于图像插值中，能够有效的保护边缘锐化，抑制虚假信息；在相同迭代次数和粒子 群规模的前提下，q p s o 算法能够得到比p s o 算法更优的插值图像。因此，q p s o 算法 是解决图像插值问题的一种有效方法。 关键词：遗传算法；粒子群算法；量子行为的粒子群算法；干扰因子；早熟；图像插值； 边缘保护 a b s t r a c t an o v e lc l a s so fe v o l u t i o n a r yc o m p u t a t i o nt e c h n i q u e s w a r mi n t e l l i g e n c ea l g o r i t h mi s d i s c u s s e d ，a m o n gw h i c ht h eq u a n t u m b e h a v e dp a r t i c l e s w a r mo p t i m i z a t i o n ( q p s 0 ) a l g o r i t h mi s ar e c e n t l yp r o p o s e da p p r o a c ha n di sav a r i a n to fo r i g i n a lp a r t i c l es w a r m o p t i m i z a t i o n ( p s o ) q p s oi sg l o b a lc o n v e r g e n ta n dw i l lb eap r o m i s i n gs o l v e rf o rc o m p l e x o p t i m i z a t i o np r o b l e m ，w h i c hi ss h o w nb ys o m ep r e v i o u sw o r k t h u s ，t h er e s e a r c ho ft h i s p a p e rw i l lb eo fs o m e w h a ts i g n i f i c a n c ei ne v o l u t i o n a r yc o m p u t a t i o n a r e a t h et r a d i t i o n a l e v o l u t i o n a r ya l g o r i t h mc a l l e d g e n e t i ca l g o r i t h m ( g a ) i sf i r s t l y f o r m u l a t e di np a r t i c u l a ra n di nt u r nt h es w a r mi n t e l l i g e n c ea l g o r i t h mi n c l u d i n gp s oa n d q p s o a sw ek n o w n ，t h em o s tc o m p l a i n e dp r o b l e ma b o u te v o l u t i o n a r yc o m p u t a t i o ni s p r e m a t u r ec o n v e r g e n c e ( p c ) ，w h i c hi sa l s oi n e v i t a b l ei nq p s o t h u st h i sw o r kf o c u s e so n h o wt oo v e r c o m ei ta n dc o n s e q u e n t l yp r o p o s e se n h a n c e dq p s o ：a ni m p r o v e dq p s ow i t l l d i s t u r b a n c e i ni m p r o v e dq p s o ，a na p p r o a c ho fu s i n gd i s t u r b a n c ef o rt h es w a r l t li sp r o p o s e dt o e n h a n c et h eg l o b a ls e a r c ha b i l i t yo ft h eq p s oa l g o r i t h m w h e ni m p l e m e n t i n gt h ei m p r o v e d q p s o ，t h ew h o l ep a r t i c l es w a l t nc o u l du n d e r t a k ep e r s i s t e n ts e a r c hi nt h es o l u t i o ns p a c e ， l e a d i n gt oa na l g o r i t h mt h a tc a na v o i dp r e m a t u r ec o n v e r g e n c ee f f e c t i v e l y t h ed i s t u r b a n c ei s i n t r o d u c e dw h e np r e m a t u r eo c c u r s am a t u r ef a c t o ri ns e a r c hp r o c e s si si n t r o d u c e d a n da l l i g hb o u n dv a l u ei ss e tf o rt h em a t u r ef a c t o rm e a s u r e t h a tm e a n st h ei n v a l i di t e r a t i o n g e n e r a t i o n sw i l lb em a i n t a i n e dl o w e rt h a nt h ef i i g hb o u n d w h e nt h ei n v a l i d i t e r a t i o n g e n e r a t i o n se x c e e dt h eh i g hb o u n d ，t h ed i s t u r b a n c ew i l lf u n c t i o n t h ee x p e r i m e n tr e s u l t so n s e v e r a lb e n c h m a r kf u n c t i o ns h o wt h a tt h ei m p r o v e dq p s ow i t hd i s t u r b a n c em e t h o dm a yb ea g o o dt e c h n i q u et oa v o i dp r e m a t u r ec o n v e r g e n c ea n dm a yr e s u l ti np e r f o r m a n c ei m p r o v e m e n t o ft h eq p s oi nm a n yc a s e s t h ea p p l i c a b i l i t yo fp s oa n dq p s oi sa l s oe x p l o r e dt oi m a g ei n t e r p o l a t i o np r o b l e m s t h ei m a g ei n t e r p o l a t i o np r o b l e mi sb a s i c a l l yi ni m a g ep r o c e s s i n g i tc a nb em o d e l e db yl i n e a r m i n i m u mm e a ns q u a r e e r r o r ( l m m s e ) p s oa n dq p s oa r eu s e dt os e e kt h eb e s th i g h r e s o l u t i o ni m a g e t h es i m u l a t i o nr e s u l t ss h o wt h a tt h en e wi n t e r p o l a t i o nt e c h n i q u e sc a t l p r e s e r v ee d g es h a r p n e s sa n dr e d u c ea r t i f a c t s i th a sa l s ob e e ns h o w nt h a tq p s oc o u l d g e n e r a t eb e t t e rs o l u t i o n st h a np s o o ni m a g ei n t e r p o l a t i o np r o b l e m s s oq p s oi sg o o df o r i m a g ei n t e r p o l a t i o np r o b l e m k e y w o r d s ：g e n e t i ca l g o r i t h m ，p a r t i c l es w a r mo p t i m i z a t i o n ，q u a n t u m - b e h a v e dp a r t i c l e s w a r m ，d i s t u r b a n c e ，p r e m a t u r e ，i m a g ei n t e r p o l a t i o n ，e d g ep r e s e r v a t i o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 本人为获得江南大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名o 看垒量选 日 期妒、岁，据 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规 定：江南大学有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅，可以将学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文，并且本人电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 签名：绘、炙f 0 导师签名： l ：圣量f 送 日 期：硼气 第一章绪论 第一章绪论 1 1 进化算法的研究现状 如今，科学技术正处于多学科相互交叉和渗透的时代。随着信息技术和生物技术的 迅速发展，人们对高效的优化控制技术和智能计算的要求日益迫切。 优化控制技术是一种以数学为基础，用于求解各种工程问题优化解的应用技术。作 为一个重要的科学分支，它一直受到人们的广泛重视，并在诸多工程领域得到迅速推广和 应用。鉴于系统的高度非线性、时变性、模型的不确定性、复杂相关性、建模困难等特 点，给该领域的研究带来了重重困难。虽然有各种优化控制方法和算法，但在实际使用 中都会碰到各种具体问题。寻求具有智能特征的新的算法已成为相关学科的一个主要研 究目标和引人注目的研究方向。 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 、进化策略( e v o l u t i o n a r ys t r a t e g y , e s ) 、进化规划 ( e v o l u t i o n a r yp r o g r a m m i n g ，e p ) 和遗传程序设计( g e n e t i cp r o g r a m m i n g ，g p ) 等进化类算法 在理论和应用两方面发展迅速，并逐渐走向了融合，形成了一种新颖的模拟进化的计算 理论，统称为进化计算( e v o l u t i o n a r yc o m p u t a t i o n ，e c ) ，进化计算的具体实现方法与形式 称为进化算法( e v o l u t i o n a r ya l g o r i t h m ，e a ) 。进化算法是一种受生物进化论和遗传学等理 论启发形成的求解优化问题的随机算法，虽然出现了多个具有代表性的重要分支，但它 们各自代表了进化计算的不同侧面，各具特点。 群体智能算法( s w a r mi n t e l l i g e n c ea l g o r i t h m ) 的研究开始于2 0 世纪9 0 年代初， 其基本思想是模拟自然界生物的群体行为来构造随机优化算法。典型的方法有m d o r i g o 提出的蚁群算法和j k e n n e d y 与r e b e r t h a r t 提出的粒子群算法。蚁群算法( a n tc o l o n y a l g o r i t h m ) 也称蚂蚁算法，它是根据蚂蚁觅食原理而设计的一种群体智能算法。粒子群 算法( 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 ) 的基本思想是受他们早期对鸟类群体行为研究 结果的启发，并利用了生物学家f r a n kh e p p n e r 的生物群体模型。 自粒子群算法提出以来，由于它的计算快速性和算法本身的易实现性，引起了国际 上相关领域众多学者的关注和研究，其研究大致可以分为：算法的改进、算法的分析以 及算法的应用。p s o 算法最早应用于人工神经网络的训练方法，j k e n n e d y 与r e b e r t h a r t 成功地将之应用于神经网络训练。随后，p s o 算法在函数优化、约束优化、极大极小值 问题、多目标优化等问题中均得到了成功的应用。特别是在电力系统、集成电路设计、 系统辨识、状态估计等问题中的应用均有报道。根据国内外关于粒子群算法研究的相关 文献以及进化算法领域发展趋势的分析，目前主要有以下几个研究方向： ( 1 ) 粒子群算法的改进 标准粒子群算法主要适用于连续空间函数的优化问题，如何将p s o 算法应用于离 散空间优化问题，特别是一类非数值优化问题，将是粒子群算法的主要研究方向。另外 充分吸收其他进化类算法的优势，以改进p s o 算法存在的不足也是值得研究的问题。 ( 2 ) 粒子群算法的理论分析 江南大学硕士学位论文 到目前为止，p s o 算法的分析方法还很不成熟和系统，存在许多不完善和未涉及到 的问题。如何利用有效的数学工具对p s o 算法的运行行为、收敛性及计算复杂性进行 分析是目前的研究热点之一。 ( 3 ) 粒子群算法的生物学基础 如何根据群体进化行为完善p s o 算法，同时分析群体智能行为，如何将其引入p s o 算法中，以充分借鉴生物群体进化规律和进化的智能性也是目前的研究方向之一。 ( 4 ) 粒子群算法与其他进化算法的比较研究。 ( 5 ) 粒子群算法的应用。 算法研究的目的是应用，如何将p s o 算法应用于更多领域，同时研究应用中存在 的问题也是值得关注的热点。 p s o 算法不是一个全局收敛的优化算法，这个已经被ev a nd e nb e r g h 1 】证明，一种 称之为具有量子行为的粒子群算法( q u a n t u m b e h a v e dp a r t i c l es w a r mo p t i m i z a t i o n ，q p s o ) 的新型的p s o 算法被提出，这种算法是由量子力学产生的，它经过数学证明，是一个 保证全局收敛的算法，参数个数少，随机性强，并且能覆盖所有解空间，是一个很有前 景的优化问题的解决算法。 1 2 图像插值的发展与现状 图像插值是图像处理中的一项基础性技术，有着广泛的应用。所谓图像插值就是根 据原始低分辨率图像数据生成更高分辨率的图像数据。这可分为两类问题：( 1 ) 图像内 的插值( 图像放大) ；( 2 ) 图像间的插值( 医学切片序列成像) 。从数据来说，图像插值 使得图像数据变多；从视觉上说，图像插值则使得原始图像更为清晰和易辨。数字图像 处理涉及到社会的很多领域，而图像插值技术作为其中的基本内容，它在工业等领域有 着相当广泛的应用，研究新的图像插值方法有其必要性。 传统的图像插值方法有最邻近插值法、双线性插值法和双三次插值法等。传统的图 像插值方法都是先经过补零疏化、后经内插滤波实现的。由于这些内插滤波器并没有完 成理想的低通滤波功能，插值后的图像增加了一定的虚假信息，导致图像锯齿和模糊。 另外内插滤波器是确定的，因而这些插值算法就缺乏利用图像本身信息的机制【1 6 】。 针对传统插值图像方法存在着的上述不足和局限，现代图像插值技术借鉴模式识别 1 2 1 1 、多信道处理【2 2 1 、分形拓扑【2 3 4 】、小波多分辨率分析f 2 5 】、有理滤波【2 6 1 、神经网络f 2 7 1 、 图像最佳复原1 2 8 j 等技术，分析图像局部的频率成分和连续性以调节插值系数，建立局部 自适应的空间移变插值算法，大大改善了重建图像的质量。如基于局部分形相似变换插 值方法【1 7 】，在常用的局部分形自相似变换基础上增加了矩形图像块的自相似变换，采用 二元函数的极值方法求最佳相似变换，它能克服传统线性或样条插值所产生的方块效 应，并且比一些随机插值算法比如随机中点偏移插值算法失真度小；基于小波的图像插 值方法1 1 8 , 1 9 1 是使用一种小波作为插值基函数进行插值：子带插值方法1 2 0 1 是从分层子带变 换的逆变换过程出发，利用分层子带变换中高分辨率频带与低分辨率频带之间存在的相 似特征，由低分辨率频带近似高分辨率频带，得到比原来图像分辨率更高的图像。从视 2 第一章绪论 觉效果这一主观评价标准来看，子带内插具有较高的图像质量，图像中细节丰富，同原 始图像相比分辨率有所提高，并且图像没有明显的畸变。 1 3 本论文的研究内容和研究方法 当群体进化的时候，群体的多样性不可避免地减少，这是因为当粒子群进化时，有 一部分粒子由于速度越来越小而变得没有活力，这样在下一轮进化中它们将失去全局搜 索能力。也就是说，与标准的p s o 算法一样，在具有量子行为粒子群算法中同样存在早 熟的趋势。本文就对目前的研究热点群体智能优化算法粒子群优化算法进行研究， 并 提出改进型的粒子群算法一基于干扰因子的q p s o 算法。该方法是防止早熟收敛的有效 方法并且可能在很多方面导致q p s o 的性能的提高。 图像插值是数字图像和数字视频处理的一项关键技术，它一直是图像处理技术的研 究热点。插值计算时兼顾图像中背景区域的平滑连续和边缘细节的清晰是图像插值算法 研究的难点。本文研究了经典的图像插值方法，提出基于粒子群算法的图像插值方法， 该方法是在以线性最小均方差( l m m s e ) 所形成的模型中，寻找符合条件的最优高分 辨率图像估计。 江南大学硕士学位论文 第二章几种进化算法的研究 2 1 优化问题 为了使系统达到最优的目标所提出的各种求解方法称为最优化方法。最优化方法是 在第一次世界大战前后，在军事领域中对导弹、雷达控制的研究中逐渐发展起来的。它 对促进运筹学、管理科学、控制论和系统土程等新兴学科的发展起到了重要的作用。在 经济管理学上就是在一定人力、物力和财力资源条件下，使经济效果( 如产值、利润等) 达到最大，并使投入的人力和物力达到以最小的系统科学方法。近几年来，随着计算机 的发展，一些过去无法解决的复杂优化问题已经能够通过计算机来求得近似解，所以， 计算机求解优化问题的方法研究也就显得越来越重要了。 最优化问题根据其目标函数、约束函数的性质以及优化变量的取值等可以分成许多 类型，每一种类型的最优化问题根据其性质的不同都有其特定的求解方法。不失一般性， 设所考虑的最优化问题为 m i nc r = 厂( x ) s j x s = i xig ，( x ) 0j = 1 ，m ( 2 1 ) 其中，仃= 厂( x ) 为目标函数，g ，( x ) 为约束函数，s 为约束域，x 为门为优化变 量。通常最大化问题很容易转换为最小化问题p = 一厂( x ) ) ，对于g ，( x ) 0 的约束和等 式约束也可转换为一g ，( x ) 0 的约束，所以式( 2 1 ) 所描述的最优化问题不失一般性。 当f ( z ) 、g ，( x ) 为线性函数，且x 0 时，上述最优化问题即为线性规划问题， 其求解方法有成熟的单纯形法和k a r m a r c 方法。 当厂( x ) 、g ，( x ) 中至少有一个函数为非线性函数时，上述问题即为非线性规划问 题。非线性规划问题相当复杂，其求解方法多种多样，但到目前仍然没有一种有效的适 合所有问题的方法。 当优化变量x 仅取整数值时，上述问题即为整数规划问题，特别是当x 仅能取o 或1 时，上述问题即为0 1 整数规划问题。由于整数规划问题属于组合优化范畴，其计 算量随变量维数的增长而指数增长，所以存在着“维数灾难 问题。 当g ，( x ) 0 ( j = l ，m ) 所限制的约束空间为整个刀维欧式空间，即r ”时，上述最 优化问题为无约束优化问题，即 m i n c r = ( x ) s j x scr ” ( 2 2 ) 非线性规划问题( 包括无约束优化问题和约束优化问题) 由于函数的非线性，使得 问题的求解变得十分困难，特别是当目标函数在约束域内存在多峰值时。常见的求解非 线性问题的优化方法，其求解结果与初值的选择关系很大，也就是 兑，一般的约束或无 约束非线性优化方法均是求目标函数在约束域内的近似极值点，而非真正的最小点。 局部优化算法 定义：如果存在x ：b ，使得对栅b 有 4 第二章几种进化算法的研究 厂( x ：) f ( x ) ，x b ( 2 3 ) 成立，其中bc s r ”，s 为由约束函数限定的搜索空间，则称x ：为f ( x ) 在b 内的 局部极小点，f ( x * b ) 为局部极小值。 常见的优化方法大多为局部优化方法，都是从一个给定的初始点x 。s 开始，依据 一定的方法寻找下一个使得目标函数得到改善的更好解，直至满足某种停止准则。成熟 的局部优化方法很多，如n e w t o n r a p h s o n 法、共轭梯度法、f l e t c h e r - r e e v e s 法、 p o l a r - r i h i e r e 法、d a v i d o n f l e t c h e r - p o w e r ( d f p ) 法、b r o y d e n f l e t c h e r - g o l d f a r b s h a n n ( b f g s ) 方法等，还有专门为求解最小二乘问题而发展的l e v e n b e r g - m a r q u a r d t ( l m ) 算法。所有这些局部优化算法都是针对无约束优化问题而提出的，而且对目标 函数均有一定的解析性质要求，如n e w t o n r a p h s o n 法要求目标函数连续可微，同时要 求其一阶导数连续。 对于约束非线性优化问题，除了根据一阶最优化必要条件直接将最优化问题转换为 非线性代数方程组，然后采用非线性代数方程组的数值解法进行求解外，还有序列线性 规划法、可行方向法、拉格朗日乘子法等。最常用的方法是将约束问题通过罚函数法转 换为无约束优化问题，然后再采用无约束优化方法进行求解。 全局优化算法 定义：如果存在x 。s ，使得对栅s 有 f ( x ) 厂( x ) ，x s ( 2 4 ) 成立，其中s 互尺”为由约束条件限定的搜索空间，则称x 为( x ) 在s 内的全局极小点， f ( x ) 为其全局极小值。 己发展成熟的最优化方法大多为局部优化方法，其求解结果与初始值相关。对于目 标函数为凸函数、约束域为凸域的所谓凸规划问题，局部最优与全局最优等效。而对于 非凸问题，由于在约束域内目标函数存在多峰值，因而其全局最优与局部最优相差甚远。 全局优化问题已存在了许多算法，如填充函数法等。真正有效且具有普遍适应性的 随机全局优化算法，是近十多年来人们模拟自然界的一些自然现象而发展起来的一系列 仿生型智能优化算法，如模拟退火方法、进化类算法、群体智能算法等。 2 2 遗传算法的研究 生物在自然界中的生存繁衍，显示出了其对自然环境的优异自适应能力。受其启发， 人们致力于对生物各种生存特性的机理研究和行为模拟，为人工自适应系统的设计和开 发提供了广阔的前景。遗传算法( g e n e t i c a l g o r i t h m ，简称g a ) 就是这种生物行为的计算 机模拟中令人瞩目的重要成果。基于对生物遗传相进化过程的计算机模拟，遗传算法使 得各种人工系统具有优良的自适应能力和优化能力。遗传算法所借鉴的生物学基础就是 生物的遗传和进化。 江南大学硕士学位论文 2 2 1 遗传算法的基本概念 遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优 化概率搜索算法。它最早由美国密执安大学的h o l l a n d 教授提出，起源于6 0 年代对自然 和人工自适应系统的研究。7 0 年代d ej o n g 基于遗传算法的思想在计算机上进行了大 量的纯数值函数优化计算实验。在一系列研究工作的基础上，8 0 年代由g o l d b e r g 进行 归纳总结，形成了遗传算法的基本框架。 生物进化是一个奇妙的优化过程，它通过选择淘汰、自然变异、基因遗传等规律产 生适应环境变化的优良物种。遗传算法g a ( g e n e t i ea l g o r i t h m ) 就是根据生物进化思想的 启发而得出的一种全局优化算法。它模拟达尔文自然进化论与孟德尔遗传变异理论的仿 生优化技术，它借喻生物进化过程特别是遗传学的术语与原理来求解问题。近二十年来， 遗传算法不论是在应用上，还是在基础理论上都取得了长足的发展，已成为信息科学、 计算机科学、运筹学和应用数学等诸多学科所共同关注的热点研究领域，在各个不同的 应用领域，人们为了取得更好的结果，对遗传算法进行了大量的改进。遗传算法的常用 基本概念如下： 将维决策向量x = x ，x 2 ，x n 】t 用个记号x f ( i = 1 ，2 ，n ) 所组成的符号串x 来表示： x = x j x 2 拍jx = 【x l ，x 2 , - - x n 】t ( 2 5 ) 其中第f 个符号与第f 个决策变量相对应，每一个x ，被看作是一个遗传基因，它的 所有可能取值称为等位基因。这样，x 就可看作是由个遗传基因所组成的一个染色 体( 即个体) 。一般情况下，染色体的长度是固定的，但对一些特殊问题n 也可以是 变化的。根据不同的情况，这里的等位基因或是某一范围内的一组整数，或是某一范围 内的一组实数，或是一个记号。最简单的等位基因是由0 和1 这两个整数组成的，相应 的染色体就可表示为一个二进制符号串。这种编码所形成的排列形式x 是个体的基因 型，通常个体的基因型和其表现型是一一对应的。每一个基因型个体x ，都要按照一定 的规则确定其适应度，表现型x 越接近目标函数的最优点，则基因型个体x 的适应度 越大；反之，其适应度就越小。在遗传算法中，对问题最优解的搜索就是通过对染色体 x 的搜索来实现的，这样所有可能的染色体x 就组成了问题的搜索空间，即个体空间。 遗传算法的运算对象是由m 个个体所组成的集合，称为群体。m 被称为种群规模。 与生物的自然进化过程相似，遗传算法的运算过程也是一个反复迭代的过程，第f 代群 体记做尸，经过一代遗传操作后得到第什1 代群体，记做p ( t + 1 ) ，称p ( t ) 是p ( t + 1 ) 的父 代，称p ( t + 1 ) 是p ( t ) 的子代。 生物的进化过程主要是通过染色体的交叉和变异来完成的。遗传算法中最优解的搜 索过程也模仿生物的这个进化过程，使用所谓的遗传操作数作用于群体p ( t ) ，即进行下 述的有序遗传操作选择、交叉和变异得到新一代群体p ( t + 1 ) 。根据各个个体的适应度， 按照一定的规则和方法，从第，代群体p ( t ) 中选择出一些优良的个体用于遗传变异产生 下一代群体p ( t + 1 ) 。选择的方法很多，常用的方法有：轮盘赌法、择优选择法等等。一 6 第二章几种进化算法的研究 般而言，每选择一对父代个体经过下述的交叉和变异过程产生两个子代个体，也可以只 产生一个子代个体，选择时父代群体中有些优良个体往往被多次选中，这一过程被称之 为选择( s e l e c t i o n ) 。被选择的一对父代个体以一定的概率( 称为交叉概率) 随机地交换它 们之间的部分基因序列，这一过程被称之为交叉( c r o s s o v e r ) 。对经过交叉操作后的每 一个个体，以一定的概率( 称为变异概率) 随机地改变一定数量的基因值，从而变为其 它的等位基因，这一过程被称之为变异( m u t a t i o n ) 。 2 2 2 遗传算法的基本原理 遗传算法的基本原理是：把问题的解表示成染色体，在算法中染色体被表示成二进 制编码串，或者是十进制编码串，在算法开始时随机地给出一群染色体( 称为初始种群) ， 即一组假设解，然后把假设解置于问题的环境中，计算每个个体的适应度值，按照适者 生存的原则从中选择适应环境能力强的个体进行交叉、变异过程产生适应能力更强的新 一代种群。如此一代一代地进化，最后将收敛到一个染色体上，即得到问题的最优解【2 l 。 1 编码 遗传算法的工作对象是字符串，因此编码是一项基础性工作。从生物学角度看，编 码相当于选择遗传物质，每个字符串对应一个染色体。 遗传算法大多采用二进制的0 1 字符编码。当问题比较简单，例如只描述大，j 、好 坏等布尔型性质时，每一位0 1 变量就代表一个性质。当问题的性质要用数值描述时， 则涉及二进制数与十进制数的转换。对于长度( 位数) 为l 的0 1 字符串，按数学的排 列组合计算，它可以表达2 x 2 x 2 2 - 2 。个数，扣除零点，为2 。一1 ，根据内插计算， 十进制与二进制数有如下关系： x = x 曲+ 垒专j 坠d e c ( y ) ( 2 6 ) zl 式中z 蛐、x 一一最小及最大的十进制数值； p 相应于x 的二进制数。 d e c 一将二进制数转换为十进制数。 在这种换算关系下，二进制表示法的精度万= 垒辛。 ( 2 7 ) zl 采用十进制字符编码。当问题的性质要用数值描述时，不需要二进制与十进制之间 的转换。直接用十进制即可。 2 产生初始群体 初始群体是遗传算法搜索寻优的出发点。群体规模m 越大，搜索的范围越广，但 是每代的遗传操作时间越长。反之，m 越小，每代的运算时间越短，搜索空间也越小。 初始群体中的每个个体是按随机方法产生的。根据字符串的长度三，随机产生三个 0 1 字符组成初始个体。初始个体的数目为m 。 3 计算适应值 适应度是衡量个体优劣的标志，它是执行遗传算法“优胜劣汰”的依据，因此，适 应度也是驱使遗传算法向前发展的动力。 7 江南大学硕士学位论文 通常，遗传算法中个体的适应度也就是所研究问题的目标函数。但是，有时适应度 是目标函数转换后的结果。 4 选择 在遗传算法中通过复制，将优良个体插入下一代新群体，体现“优胜劣汰 的原则。 近年来，在遗传算法中常常采用择优选择法。这种方法没有明显的复制操作，而是 r， 根据个体的相对适应度，乓r 反复地从群体中选择m 个个体组成下一代群体。当然， ，l ) t 个体的适应度越高，它被重复选中的可能性越大，而重复选中的就相当于复制。相反， 适应度小的个体往往未能选中，它就被淘汰。 5 交叉 在遗传算法中，交叉是产生新个体的主要手段。它类似于生物学的杂交，使不同个 体的基因互相交换，从而产生新个体。 交叉方法a ：二进制代码法( 假设染色体用两个字节表示) 父代个体：五= 0 0 0 1 1 0 0 10 1 0 1 1 1 0 0x = 1 1 0 0 1 0 0 10 11 0 0 1 0 1 产生三个随机正整数：m l - 4 ，m 2 = 1 2 ，l = 5 ( 要求：m a x ( m l ，m 2 ) + l 1 7 ，l 8 ) 交叉新个体：石。= 0 0 0 0 0 1 0 10 1 0 11 1 0 0x k l l 0 0 1 0 0 10 111 1 0 0 1 即：石。0 0 0 1 1 0 0 10 1 0 111 0 0 乃。11 0 0 1 0 0 10 11 0 0 1 0 1 石7 = 0 0 0 而而0 1 0 1 1 1 0 0 乃7 = 1 1 0 0 1 0 0 10 1 1 i 1 0 0 l 交叉方法b ：十进制代码法( 假设染色体由八个基因组成) 父代食诲：x = x t l xt 2xi 3x i 4xi 5xi 6x i 7x1 8 ；x j2x j l x j 2x j 3x j 4 聱5x j 6y j 7x j 8 产生两组随机正整数：2 ，7 ；6 ，5 ( 各组随机数的个数是随机的，但必须相同) 瓿个体：x = x i l 玛6 x t 3 x 4 x i 5 x i 6 x j 5 x i 8耳= x j l 蜀2 玛3x j 4 x i 7 x i 2 x j 7 x j 8 即：x = x i l x i 2 x i 3 x i 4 x i 5 x i 6 x i 7 x i 8 乃= x j i x j 2 x j 3 x j 4 x j 5 x j 6 x j 7 x j 8 x = x i l 6 变异 变异是遗传算法产生新个体的另一种方法。它对某个字符进行补运算，将字符1 变 为o ，或将0 变为l 。 变异方法a ：二进制代码法，x 7 各位以一定的概率变异，假设第5 ，1 5 位发生变异， 则x 。结果如下变异后变成子代个体x 2 。 x i l = 0 0 0 0 0 1 0 10 1 0 1 11 0 0 x ；2 ：。 1 0 10 j 。，。 变异方法b ：十进制代码法，x 7 各染色体以一定的概率变异，假设第2 ，6 个基因 第二章几种进化算法的研究 发生变异，则x 。结果如下变异后变成子代个体砰。 x i l = x i lx j 6 xi 3xi 4xi 5xi 6x j 5 xi 8 2 ：。) l = b xi 3xi 4xi 5 5 xi 8 7 终止 遗传算法是一个反复迭代的过程，每次迭代期间，要执行适应度计算、复制、交叉、 变异等操作，直至满足终止条件。 使遗传算法终止的方法有三种： ( 1 ) 规定最大迭代次数。一旦遗传算法的迭代次数达到，则停止操作，输出结 果。通常取2 0 0 5 0 0 次。 ( 2 ) 规定最小的偏差万。对于适应度目标己知的遗传算法，如用方差作为适应度计 算的曲线拟合问题，可用最小的偏差万制定终止条件，即： l 麟一f l 万 ( 2 8 ) 式中 厂一己知的适应度目标，l 每代最大的适应度 ( 3 ) 观察适应度的变化趋势。在遗传算法的初期，最优个体的适应度以及群体的平 均适应度都较小，以后随着复制、交叉、变异等操作，适应度值增加。到了遗 传算法后期，这种增加已趋缓和或停止，一旦这种增加停止，即中止遗传算法。 算法流程图如下： 图2 1 遗传算法流程图 f i g 2 1 f l o wc h a r to fg e n e t i ca l g o r i t h m 2 2 3 遗传算法的特点 1 遗传算法从问题解的中集开始嫂索，而不是从单个解开始。这是遗传算法与传 统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部 9 江南大学硕士学位论文 最优解。遗传算法从串集开始搜索，覆盖面大，利于全局择优。 2 遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。由于遗传 算法使用适应值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。遗传 算法只需适应值和串编码等通用信息，故几乎可处理任何问题。 3 遗传算法有极强的容错能力。遗传算法的初始串集本身就带有大量与最优解甚 远的信息；通过选择、交叉、变异操作能迅速排除与最优解相差极大的串；这是一个强 烈的滤波过程；并且是一个并行滤波机制。故而，遗传算法有很高的容错能力。 4 遗传算法中的选择、交叉和变异都是随机操作，而不是确定的精确规则。这说 明遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解迫近，交叉体现了最 优解的产生，变异体现了全局最优解的复盖。 5 遗传算法具有隐含的并行性。遗传算法的每一代都是对一组个体同时进行，而 不是对单一个体操作，从而它可以同时搜索解空间的多个区域，并通过遗传操作数交流 信息，这种搜索方式使得它对初始解的选取不敏感，能以较大的概率跳出局部最优，并 找出整体最优，因而对解决多目标搜索或多峰值函数的情形非常有效。 2 2 4 遗传算法的应用 遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖问题的具体领 域，对问题的种类有很强的鲁棒性，所以广泛应用于很多学科。下面是遗传算法的一些 主要领域： 1 函数优化 函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用算 列。人们用几何特性各异的函数来评价遗传算法的性能，而对于一些非线性、 多目标的函数优化问题，用其他优化方法较难求解，遗传算法可以得到较好的 结果。 2 生产调度问题 生产调度问题在许多情况下所建立起来的数学模型难以精确求解，遗传算法在 单件生产车间调度、流水线调度等方面得到有效的应用。 3 人工生命 自组织能力和自学习能力是人工生命的两大主要特征。人工生命与遗传算法有 着密切的关系，基于遗传算法的进化模型是研究人工生命现象的重要理论基础。 可见，遗传算法在人工生命及自适应系统的模拟与设计、复杂系统突现性理论 研究中将得到更为深入的发展。 2 3 群体智能算法的研究 智能计算技术是近年来在人工智能界兴起的新的研究方向和热点。 生命在长期进化过程中，积累了很多新奇的功能，人类从自然界得到启迪，模仿其结 构进行发明创造，这就是仿生学。这是人们向自然界学习的一个方面。另一个方面，还 可以利用自然的规律进行设计( 包括设计算法) ，这就是智能计算的思想。 l o 第二章几种进化算法的研究 智能计算就是借用自然界( 生物界) 规律的启迪，根据其原理，模仿设计求解问题的 算法。目前这方面的内容很多，如：人工神经网络技术、遗传算法、群体智能技术等。 群体智能算法( s w a r mi n t e l l i g e n c ea l g o r i t h m ) 的研究始于上世纪9 0 年代初，其基 本思想是模拟自然界的群体行为来构造随机优化算法。典型的算法如：j k e n n e d y 与 r e b e r h a r t 提出的粒子群算法1 4 j 。 2 3 1 粒子群算法( p s o ) 1 、经典的粒子群算法( p s o ) 简介1 5 l 粒子群算法( 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 ) 是由美国社会心理学家j a m e s k e n n e d y 和电气工程师r u s s e l le b e r h a r t 在1 9 9 5 年共同提出的，是继蚁群算法之后的又一种 新的群体智能算法，目前已成为进化算法的一个重要分支。经典粒子群算法的基本思想 是模拟鸟类群体行为，并利用了生物学家的