（计算机软件与理论专业论文）一种基于小生境的克隆选择算法.pdf

太原理工大学硕士研究生学位论文 一种基于小生境的克隆选择算法 摘要 许多实际工程问题可以抽象为相应的函数优化问题。目前己经有很多 启发式算法用于解决函数优化问题。遗传算法就是其中的一种，但由于在 实际应用中遗传算法早熟收敛，收敛速度慢的现象时有发生，这在一定程 度上限制了遗传算法的发展和应用。而免疫系统是一个分布式、自组织和 具有动态平衡能力的自适应复杂系统。人工免疫系统是与生物免疫系统相 对应的工程概念，人们从免疫系统中提取、发现有用机制用来解决工程和 科学问题，研究如何根据免疫优化理论以及模拟生物免疫优化行为来设计 新的有效优化算法是非常有意义的科研课题。 本文首先回顾了进化算法的发展历程，尤其是遗传算法分支领域。然 后详细介绍了自然免疫系统基本原理、人工免疫系统及各种免疫算法。其 中克隆选择原理是人工免疫系统中非常重要的一个原理，由此启发而得出 的免疫算法，能够比较好地解决函数优化问题。最后在分析克隆选择算法 的优越性与其不足的基础上，借鉴自然界共享小生境机制，提出了对克隆 选择算法的改进算法基于小生境的克隆选择算法。 针对克隆选择算法的漏峰问题，小生境克隆选择算法重新设计了评价 函数。本文通过引入共享函数来确定群体中个体之间的物种相似度，再以 共享函数为基础设计评价函数，替代原先简单的以适应度值为唯一标准的 评价函数，对群体中聚集成小块的个体可以通过施加共享函数进行惩罚， 使其适应值减小，这样就使得小规模物种的被选择概率会比适应值共享之 前有所提高，从而维护群体中小规模低适应度物种生存，使其也能顺利进 入下一代。小生境技术通过维护群体e p d , 规模低适应度物种的生存，增加了 i 奎堕望三查兰堡主里塞竺兰竺笙奎 物种多样性，使群体向优质个体分布良好的方向进化。 最后经过测试，表明该改进算法与标准遗传算法和克隆选择算法相比， 具有快速收敛、全局寻优能力强、增加种群多样性等优点。针对算法中的 某些步骤和参数，通过实验统计结果给出合理调整。 总之，优化问题是一个古老的问题，同时它也是一个困难的问题，而 自然界中包含着丰富有效的信息处理机制。我们可以模拟自然进化原理与 机制，模拟生物智能的生成过程，并用以求解问题，进而融合数学、生物、 计算机技术等各个领域的原理与技巧，使所设计的算法策略更为有效。这 是当前国际计算智能研究领域的热点之一。本文将生物免疫和生物小生境 技术相结合，建立了新型算法模型，而深入研究其理论基础和开拓算法的 应用领域将是我们下一步的研究重点和发展方向。 关键词：进化算法，免疫算法，克隆选择算法，小生境技术，共享函数， 基于小生境的克隆选择算法 太原理工大学硕士研究生学位论文 n i c h ec l o n as e l e c t i o n a l g o r n h m a b s t r a c t m a n yp r a c t i c a lp r o b l e m s c a l lb ef o r m u l a t e da sp r o b l e m so fo p t i m i z i n g f u n c t i o n sf o rw h i c ht h e r ea r en u m e r o u sh e u r i s t i ca l g o r i t h m ss of a r t h eg e n e t i c a l g o r i t h mi so n eo fs u c ha l g o r i t h m s h o w e v e r , t h ed e v e l o p m e n ta n da p p l i c a t i o n s o ft h eg e n e t i ca l g o r i t h ma r et oc e r t a i ne x t e n tl i m i t e db yi t sp r e m a t u r e c o n v e r g e n c ea n dl o wc o n v e r g e n ts p e e dt h a to c c y u f r e q u e n t l yi na p p l i c a t i o n so f t h i sa l g o r i t h m b u tt h ei m m u n es y s t e mi sad i s t r i b u t e d ，s e l f - a d a p t e dc o m p l e x s y s t e m f o r ms u c has y s t e m ，u s e f u ls t r a t e g i e sc a nb ef o u n dt os o l v ep r o b l e m si n e n g i n e e r i n ga n ds c i e n c e s a n di t i sas i g n i f i c a n ts u b j e c tt od e s i g ne f f e c t i v e a l g o r i t h m s f o ro p t i m i z a t i o n p r o b l e m sb ys i m u l a t i n gb i o l o g i c a l i n a l i l u n e a c t i v i t i e s i nt h i s p a p e r , w e f i r s tr e v i e wt h ed e v e l o p m e n to ft h ee v o l u t i o n a r y a l g o r i t h m s ，i np a r t i c u l a ro ft h eg e n e t i ca l g o r i t h m f o l l o w i n gt h i s , w ed e s c r i b e t h eb a s i cp r i n c i p l e so f n a t u r a li m m u n es y s t e m s ，t h ea r t i f i c i a li m m u n es y s t e ma n d v a r i o u sk i n d so fi m m u n ea l g o r i t h m s a m o n gt h e s ep r i n c i p l e s ，t h ec l o n a l s e l e c t i o np r i n c i p l ei st h em o s ti m p o r t a n tf o rt h ea r t i f i c i a li m m u n es y s t e m t h e i m m u n ea l g o r i t h mc a nb ed e r i v e df r o mt h i sp r i n c i p l ea n du s e dt os o l v et h e p r o b l e m so fo p t i m i z i n gf u n c t i o n si na ne f f e c t i v ew a y f i n a l l y , o nt h eb a s i so f a n a l y z i n gt h ea d v a n t a g e sa n dd i s a d v a n t a g e sa n db yr e f e r r i n gt ot h en a t u r a l s h a r i n gn i c h em e c h a n i s m , w ep r e s e n tf o rt h ec l o n a ls e l e c t i o na l g o r i t h ma n i m p r o v e da l g o r i t h mc a l l e dn i c h ec l o n a ls e l e c t i o na l g o r i t h m t h en i c h ec l o n a ls e l e c t i o na l g o r i t h mi sa na l g o r i t h mt h a tr e d e s i g n st h e m 查堕墨三奎兰堡主堡壅竺堂堡丝苎 e v a l u a t i o nf u n c t i o nw i t hr e g a r d t o p e a kl e a k i n g ”i nt h ec l o n a l s e l e c t i o n a l g o r i t h m t h i sp a p e rw i l lf i r s ti n t r o d u c et h es h a r i n gf u n c t i o nt od e t e r m i n e s p e c i e ss i m i l a r i t yb e t w e e nt h ei n d i v i d u a l so fac o m m u n i t y , a n dt h e nu s et h i s f u n c t i o na sab a s i st od e s i g nt h ee v a l u a t i o nf u n c t i o ni np l a c eo ft h eo r i g i n a l s i m p l ee v a l u a t i o nf u n c t i o nt h a ti sb a s e do n t h ef i t n e s sv a l u ea si t ss o l es t a n d a r d f o rt h ei n d i v i d u a l so f t h ec o m m u n i t yt h a tg a t h e ri n t oas c r a p ，t h ef i t n e s sv a l u ei s r e d u c e db ya p p l y i n gt h e s h a r i n gf u n c t i o n t op e n a l i z et h es c r a p ；t h u st h e p r o b a b i l i t yo fs e l e c t i o ni se n h a n c e df o rt h i ss m a l l s c a l es p e c i e s ，a n di sg r e a t e r t h a nt h ep r o b a b i l i t yw h e nt h eo r i g i n a la d a p t a t i o nv a l u ei ss h a r e d h e n c ei ti s p o s s i b l ef o rt h es m a l l s c a l es p e c i e sw i t hl o wf i t n e s st os u r v i v ea n dt oe n t e ri n t o t h en e x tg e n e r a t i o ns m o o t h l y i nt h i sw a y , t h en i c h et e c h n o l o g yw i l li n c r e a s et h e d i v e r s i t yo ft h es p e c i e sa n dc a u s ec o m m u n i t yt oe v o l v ei nt h ed i r e c t i o no f i n d i v i d u a ld i s t r i b u t i o n s 州t 1 1h i 曲q u a l i t i e s f i n a l l y , a f t e rt h ee x p e r i m e n t , i ti n d i c a t e st h a t , c o m p a r e d 、i t ht h es t a n d a r d g e n e t i ca l g o r i t h ma n dt h ec l o n a ls e l e c t i o na l g o r i t h m , t h ei m p r o v e m e n ta l g o r i t h m h a st h es u p e r i o r i t yo fr a p i dc o n v e r g e n c e ，s t r o n ga b i l i t yf o ro v e r a l ls i t u a t i o n o p t i m i z a t i o na n di n c r e a s ei np o p u l a t i o nd i v e r s i t y i nv i e wo fs o m es t e p sa n d p a r a m e t e r , i tw i l lg i v er e a s o n a b l ea d j u s t m e n tc o u n t i n go nt h ee x p e r i m e n tr e s u l t i n 文l m o p t i m i z a t i o ni s a l lo l da n dd i f f i c u l tp r o b l e m a n dt h en a t u l 屯 a b o u n d sw i t he f f e c t i v ei n f o r m a t i o n - p r o c e s s i n gm e c h a n i s m s t h e r e f o r e ，w ec a l l s i m u l a t et h ep r i n c i p l ea n dm e c h a n i s mo f n a t u r a le v o l u t i o na n dt h ep r o c e s so f t h e d e v e l o p m e n to f b i o l o g i c a li n t e l l i g e n c ei no r d e rt os o l v ep r o b l e m sa n dt a k eas t e p f u r t h e rt oi n t e g r a t et h ep r i n c i p l e sa n d t e c h n i q u e sf r o mm a t h e m a t i c s ，b i o l o g y , a n d c o m p u t e rs c i e n c es ot h a tt h ea l g o r i t h m sd e s i g n e da r em o r ee f f e c t i v e t 托si so n e o ft h ef o c u s e si nt h ei n t e r n a t i o n a lr e s e a r c ho nc o m p u t e ri n t e l l i g e n c e w ew i l l c o m b i n et h eb i o l o g i c a li n m l u n ea n dt h en i c h et e c h n o l o g yt od e v e l o pn e w m o d e l sf o ra l g o r i t h m si nt h i sp a p e r a n di nt h ef u t u r e ，t h et h e o r e t i c a lb a s e sw i l l b ee x p l o r e da n dt h ea p p l i c a t i o n sw i l lb ee x t e n d e d i v 太原理工大学硕士研究生学位论文 k e y w o r d s ：e v o l u t i o n a r y a l g o r i t h m ( e a ) ，i m m u n e a l g o r i t h m0 a ) ，c l o n a l s e l e c l i o na l g o r i t h m ( c s a ) ，n i c h et e c h n o l o g y , s h a r i n gf u n c t i o n ，n i c h ec l o n a l s e l e c t i o na l g o r i t h m ( n c s a ) v 声明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的 法律责任由本人承担。 论文作者签名：骂垦璺 日期： 关于学位论文使用权的说明 本人完全了解太原理工大学有关保管、使用学位论文的规定，其 中包括：学校有权保管、并向有关部门送交学位论文的原件与复印 件；学校可以采用影印、缩印或其它复制手段复制并保存学位论文： 学校可允许学位论文被查阅或借阅；学校可以学术交流为目的， 复制赠送和交换学位论文；学校可以公布学位论文的全部或部分内 容( 保密学位论文在解密后遵守此规定) o 日期： 日期： 太原理工大学硕士研究生学位论文 1 1 引言 第一章绪论 人工智能( a r t i f i c i a li n t e l l i g e n c e ) 于1 9 5 6 年作为- - i 7 单独的学科问世以来，已经取得 了许多重要成果。近年来，随着科技革命的进行，各个学科之间相互交叉、渗透，人们 不断把一个领域的研究成果应用于另一个领域中。其中，以计算智能或软计算为代表的 计算智能技术也迅速发展。历史证明，生物是计算问题的灵感源泉。研究人员从未停止 过对生物系统尤其是对人类自身功能及结构的探究模仿。其中最受关注的是生物的三大 信息处理系统：神经系统、遗传系统和免疫系统。在研究的过程中发展出了模拟大脑神 经结构的人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k ，简称a n n ) ，基于人类模糊思维的 模糊控制系统( f u z z yc o n t r o ls y s t e m ，简称f c s ) ，模仿生物生存演化的进化计算 ( s i m u l a t e de v o l u t i o n a r yc o m p u t a t i o n ，简称s e c ) ，以及基于生物免疫机理的人工免疫 系统( a r t i f i c i a li m m u n es y s t e m ，简称a i s ) 。 其中生物免疫系统是一个高度进化、由众多功能部件组成的复杂自适应生物系统， 它是完全分散的，通过免疫应答、免疫调节、免疫记忆等过程，区分外部有害抗原和自 身组织，自觉地保持自身的稳定性，高效地完成其重要而复杂的任务使生物体免受 微生物和蠕虫的攻击或者清除病原并保持有机体的稳定。它不依靠任何中心控制，具有 分布式任务处理能力，具有在局部采取行动的智能，它通过起交流作用的化学信息构成 网络，进而形成全局概念。从系统的角度来看，自然免疫系统是一个自组织、自适应并 具有高度并行处理能力的强鲁棒性系统；从信息处理的角度来看，自然免疫系统又是一 个具有多样性识别能力、增强学习机制和分布式联想记忆的强大信息处理系统。这些优 点已经引起许多不同领域研究人员的广泛兴趣。人们自然希望从生物免疫系统的运行机 制中获取灵感，开发面向应用的免疫系统计算模型人工免疫系统( a r t i 6 c i a li m 删m e s y s t e m ，a i s ) ，用于解决工程实际问题。目前，a i s 中的免疫算法【l 】已经用于参数优化、 模式识别、图象和信号处理、异常和故障诊断、人工生命、机器人控制、机器学习、网 络入侵检测、神经网络设计、多代理系统、数据挖掘、工业设计和工业生产等领域，并 表现出较卓越的性能和效率。 】 太原理工大学硕士研究生学位论文 1 2 课题的目的和意义 许多实际工程问题可以抽象为相应的函数优化问题。因此在优化问题的领域，旧算 法的各种改进与新算法的推出层出不穷。目前己经有很多启发式算法用于解决函数优化 问题。与传统算法相比较，启发式算法的优点在于其有较好的全局搜索能力，避免过早 收敛于局部最优解。而传统的遗传算法就是一种比较经典的解决函数优化的导向随机搜 索算法。但其本身还存在一些不足，例如局部搜索能力差、收敛速度慢和随机漫游等现 象，从而导致算法的收敛性能差，需要很长时间才能找到最优解。这些不足阻碍了遗传 算法的推广应用。如何改善遗传算法的搜索能力以使其更好地应用于实践，是各国学者 一直探索的个重要课题。而免疫系统是一个分布式、自组织和具有动态平衡能力的自适 应复杂系统。人工免疫系统是与生物免疫系统相对应的工程概念，人们从免疫系统中提 取、发现有用机制用来解决工程和科学问题。近年来在生物学领域的研究发现免疫行为 能够很好地防止早熟现象，有效地提高寻优速度，因而免疫原理对改进和提高遗传算法 的性能具有重要的启迪作用。研究如何根据免疫优化理论以及模拟生物免疫优化行为来 设计新的有效优化算法是非常有意义的科研课题。 但正如s t a n d f o r d 大学的w o l p e r t 和m a c r e a d y 教授1 9 9 7 年提出的n of r e el u n c h ( 简称 n f l ) 定理田，即“无免费午餐”定理中所描述的万能算法是不存在的。 n f l 定理概括如下： 假设有a ，b 两种任意( 确定或随机) 搜索算法，对于所有的问题集，它们的平均性 能( 如最优解、收敛速度等) 是相同的。精确地说，即： p i f , n , a ) - - ，o i ，n ，刃 ( 1 2 1 ) |j 其中c 为个体适应度的概率曲线，为适应度函数，为群体规模大小。 如果算法a 比算法b 有“较大机会”，发现“好的解”，那么算法a 比算法b 优越。因此， 通常使用概率来评价算法发现“好的解”的可能性。根据n f l 定理，一个算法“优化”，仅 仅是该算法对某一类问题具有较好的算法性能，对于其他问题，其性能必然下降。进一 步地说，如果算法对某一类问题具有好的特性，这只说明该算法的搜索机理适合这类问 题的结构，对于其他结构的问题则不适合。这个定理对特定的优化问题设计有效的算法 具有指导实践的重要意义。 2 太原理工大学硕士研究生学位论文 1 3 本文的主要工作 本文的主要工作是把小生境机制引入了免疫算法，在充分利用小生境内在多样性的 基础上，提出了基于小生境机制的克隆选择算法。对该算法进行了函数仿真测试，取得 了令人满意的效果。算法仿真结果表明：与标准遗传算法和克隆选择算法相比，改进算 法具有全局寻优能力强、增加种群多样性等优点。 本文的工作详细如下： 1 ) 在阅读大量文献的基础上，重点分析了进化算法( 尤其是遗传算法) 的发展、基 本原理、算法步骤、特性差异及其应用。并对软计算作了概要介绍。 2 ) 对免疫理论的生物学基础、免疫机理、免疫系统功能以及人工免疫系统的原理、 模型、应用等进行了详细的介绍。 3 ) 对各种免疫算法进行了介绍，将本文中将要改进的克隆选择算法使用m a t l a b 语 言实现，并对常见的复杂函数进行了寻优测试。 4 ) 在克隆选择算法中引入小生境技术，并针对测试函数进行了仿真实验。对小生 境克隆选择算法模型中的两种抗体距离选择方式进行了比较分析。对算法中的一些重要 参数进行了测试调整。 1 3 1 论文结构 论文共分为六大部分： 第一部分：绪论。课题的目的和意义以及本文的主要工作 第二部分：遗传算法。介绍遗传算法的历史及其发展，遗传的基本概念和原理，遗 传算法的一般框架、研究现状和意义最后是介绍软计算的概念。 第三部分：免疫学的理论基础。介绍了人工免疫系统的生物学基础及其运行机制， 生物免疫系统的各种机理、各种模型，以及人工免疫系统的应用。 第四部分：免疫算法。介绍各种免疫算法，并将本文中将要改进的克隆选择算法使 用m a t l a b 语言实现，然后对常见的复杂函数进行了寻优测试。 第五部分：算法改进。先介绍小生境技术，后在克隆选择算法的基础上引入小生境 技术加以改进。通过仿真数值实验，将克隆选择算法和遗传算法的优化结果进行了统计 3 太原理工大学硕士研究生学位论文 和讨论；研究了算法中的几个重要参数对该算法的影响。 第六部分：总结与展望。本文工作的总结，后续工作的展望。 1 _ 3 _ 2 创新 在克隆选择算法中引入小生境技术，增加原有算法的群体多样性。并针对测试函 数进行了仿真实验。对小生境克隆选择算法模型中的两种抗体距离选择方式进行了比较 分析。对算法中的一些重要参数进行了测试调整。 4 太原理工大学硕士研究生学位论文 第二章遗传算法 2 1 进化算法的分类及其发展历史 进化算法( e v o l u t i o n a r y a l g o r i t h m ，简称e a ) 也称为进化计算、模拟进化、进化优 化，是一种随机搜索与优化算法，主要用于各种优化问题求解。进化算法最初由三大分 支：h o l l a n d 创建的遗传算法( g e n e t i ca l g o r i t h m ，g a ) 、f o g e l 提出的进化规划 ( e v o l u t i o n a r yp r o g r a m m i n g ，e p ) 、r c c h e n b e r g 和s c h w e f e l 提出的进化策略( e v o l u t i o n a r y s t r a t e g y ，e s ) 发展而来。虽然三大分支在算法实现方面有一些细微差别，但它们有一个 共同的特点，即都是直接借助生物进化的基本思想和原理来设计、控制和优化人工系统， 并且随着彼此交融，算法之间的差别越来越模糊，我们统称为基本进化算法或标准进化 算法。 进化计算是计算智能( c o m p u t a t i o n a li n t e l l i g e n c e ，简称c i ) 的关键技术之一，它具 有模拟生物进化的强大的优化能力。“e v o l u t i o n a r yc o m p u t a t i o n ”一词产生于九十年 代初期，其目的是将模拟生物进化的不同分支的学者在思想上集中起来，促进它们的共 同发展【3 j 。在九十年代初期以前，不同分支问并没有交流，直至1 9 9 0 年，才在迸化计算 的一些国际会议上产生了相互之间的交流与切磋。现在，进化计算已经成为一门较独立 的新的计算技术学科，它主要研究模拟生物的进化规律来解决实际工程中的复杂优化问 题。以遗传算法为核心的进化计算会将二十一世纪的计算智能推向一个崭新的应用领 域。 进化计算与其他学科的关系如下图2 1 所示。 进化计算是一种基于自然选择和遗传变异等生物进化机制的全局性概率搜索算法。 在形式上，同其他启发式搜索方法一样，是一种迭代方法。它从选定的初始解出发，通 过不断迭代逐步改进当前解，直至最后搜索到最优解或满意解。在进化计算中，迭代计 算过程采用了模拟生物体的进化机制，从一组解( 群体) 出发，采用类似于自然选择和有 性繁殖的方式，在继承原有优良基因的基础上，生成具有更好性能指标的下一代解的群 体。进化算法的结构可用图2 2 描述。 5 太原理工大学硕士研究生学位论文 图2 - 1 进化计算与其他学科的关系 f i g 2 1t h er e l a t i o nb e t w c e ne v o l u t i o n a r y a l g o r i t h ma n do t h e rd i s c i p l i n e s 图2 - 2 进化算法流程图 f i g 2 2 t h e f l o w c h a r t f o r e v o l u l i o n a r y a l g o r i t h m 其中，初始种群是针对具体问题随机设定的；评价性能是根据预先定义的一个评价 函数来计算当前种群中各个个体在环境中的“适应度”( f i t n e s s ) ) 然后，通过采取一些进化 操作( 如选择、交叉和变异) 从当前种群和新产生的个体中产生下一代种群，这就完成了 一次迭代进化；最后，算法的终止条件是当前种群中存在某个候选解满足要求或允许进 化的代数已经达到。在这个过程中，选取不同的进化操作和策略决定了进化算法的不同 类型。 6 太原理工大学硕士研究生学位论文 2 2 进化算法各分支的区别 以遗传算法为代表的三种进化算法在本质上是相同的，但它们在算法实现方面又存 在一些区别。其中，进化规划与遗传算法的区别主要表现在以下四方面： 1 ) 在对待求解问题的表示方面，进化规划因为其变异操作不依赖于线性编码，所 以通常可以根据待求问题的具体情况而采取一种较为灵活的组织方式，直接以问题的可 行解作为个体的表现形式，无需再对个体进行编码处理；典型的遗传算法则通常要把问 题的解编码成为一串表达符号，即基因组的形式。 2 ) 在后代个体的产生方面，进化规划主要着眼于物种的进化过程。与遗传算法所 不同的是，它没有利用个体之间的信息交换，所以不使用交叉算子而主要依靠变异操作。 因此。在不考虑搜索效率的前提下，进化规划在应用方面更易于掌握，便于实现。 3 ) 在竞争与选择方面，进化规划着重于群体中个体之问的竞争选择。允许父代与 子代参与竞争。因此，进化规划可以保证以概率l 收敛于全局最优解；而经典遗传算法 若不采用保留父代最优解策略，则算法不能保证收敛。 4 ) 在处理对象方面，进化规划以n 维实数空间上的优化问题为主要处理对象。 而进化规划与进化策略的主要区别有以下两方面： 1 ) 在编码结构方面，进化规划是将种群类比为编码结构，而进化策略则是把个体 类比为编码结构。所以，前者无需再通过选择操作来产生新的候选解，而后者还要进行 这一操作。 2 ) 在竞争与选择方面，进化规划需要通过适当的选择机制，从父代和当前子代中 选取优胜者组成下一代群体；而进化策略则是通过一种确定性选择，按适应值的大小， 直接将当前优秀个体和父代最佳个体保留到下一代中。 综上所述，下表2 1 总结、比较了这三种典型的进化算法的主要特点。 7 太原理工大学硕士研究生学位论文 表2 - 1 遗传算法，进化策略和进化规划的主要特点 t a b l e 2 1t h em a i nc h a r a c t e r i s t i c so f g a ，e pa n de s 遗传算法g a进化策略e s进化规划e p 创始人 h o l l a n dr e c h e n b e r g 和f o g e l s c h w e f e l 常用编码 二进制和十进制十进制十进制 个体表现形式离散型 连续型连续型 参数调整无标准偏差、协方差 方差 适应度评价方变化目标函数值直接使用目标函数值变换目标函数 法值 变异算子辅助搜索方式主要搜索方式 唯一搜索方式 交叉算子主要搜索方式辅助搜索方式 不使用 选择算子概率的、保存确定的、不保存 概率的、不保存 遗传操作复制、交叉、变方差变异、交叉、确定 方差变异、随机 异性选择性选择 共同点直接借助生物进化的基本思想和原理来解决实际问题 进化算法具有如下特点1 4 ： ( 1 ) 进化算法的搜索过程是从一群初始点开始搜索，而不是从单一的初始点开始搜 索，这样，其获得全局最优解的概率就大大提高了； ( 2 ) 个体( 候选解) 是选择操作的主要目标； ( 3 ) 随机处理在进化中起着主要作用； “) 种类的改变主要由交叉和变异得到； ( 5 ) 新种是从旧种开始经历突变、自然选择和隔离过程的渐次分化；得到种类的 延续不是完全连续的； ( 6 ) 不是所有种类的改变都是自然选择的结果； ( 7 ) 种类的进化是适应其环境的结果，并且是多种多样的； ( 8 ) 在进化的过程中，具体选择哪一个个体或种类不是确定性的； ( 9 ) 进化算法具有显著的隐式并行性： 进化计算体现了优胜劣汰和自然选择的优化思想，为许多难以用传统数学方法和其 8 太原理工大学硕士研究生学位论文 他人工智能技术解决的科学和工程问题提供了全新的思路。某些学者研究了进化算法的 突现行为后声称，进化算法将与馄饨理论和分形几何一起成为人们研究非线性现象和复 杂系统的新的三大方法，并将与神经网络一起成为人们研究认知过程的重要工具 5 1 。 2 3 遗传算法的历史及其发展历程 遗传算法( g e n e t i c 舢g o r i t h m g a ) ，是一类以达尔文的自然进化论与遗传变异 理论为基础的求解复杂全局优化问题的仿生型算法。它借鉴生物界自然选择和自然遗传 机制，以概率论为基础在解空间中进行随机化搜索，最终找到问题的最优解。 遗传算法的兴起是在8 0 年代末9 0 年代初期，但是它的历史可以追溯到6 0 年代初 期。早期的研究大多以对自然遗传系统的计算机模拟为主。早期遗传算法的研究特点是 侧重于对一些复杂的操作的研究。其中像自动博弈、生物系统模拟、模式识别和函数优 化等给人以深刻的印象，但总的说来，这是一个无明确目标的发展时期，缺乏带有指导 性的理论和计算工具的开拓。这种现象直到7 0 年代中期由于h o l l a n d 和d e j o n g 的创造 性研究成果的发表才很到改观 6 1 1 7 1 。1 9 6 7 年，b a g l e y 在他的论文中首次提出了遗传算法 ( g e n e t i ca l g o r i t h m ) 这一术语，并讨论了遗传算法在自动博弈中的应用 s l 。1 9 7 0 年， c a v i c c h i o 把遗传算法应用于模式识别中【9 】第一个把遗传算法应用于函数优化的是 h o u s t i e n 埘，1 9 7 1 年他在论文 计算机控制系统中的人工遗传自适应方法中阐述了遗 传算法用于数字反馈控制的方法1 9 7 5 年在遗传算法研究的历史上是十分重要的一年， h o l l a n d 出版了他的著名专著自然系统和人工系统的适配 6 1 ，该书系统的阐述了遗传 算法的基本理论和方法，并提出了对遗传算法理论研究和发展极为重要的模式理论 ( s c h e m a t a t h e o r y ) ，该理论首次确认了结构重组遗传操作对于获得隐并行性的重要性。 j h o l l a n d 教授和他的研究小组围绕遗传算法进行研究的宗旨有两个：一是抽取和解释 自然系统的自适应过程，二是设计具有自然系统机理的人工系统。同年，d e j o n g 完成 了他的重要论文遗传自适应系统的行为分析。他把h o l l a n d 的模式理论和他的计算实 验结合起来，这可以看作遗传算法发展过程中的一个里程碑，尽管d e j o n g 和h o u s t i e n 一样主要侧重于函数优化的研究，但他将选择、交叉和变异操作进一步完善和系统化， 同时又提出了诸如代沟( g e n e r a t i o ng a p ) 等新的遗传操作技术，为遗传算法及其应用打 下了坚实的基础。进入8 0 年代，遗传算法迎来了若盛发展时期，应用范围不断扩展， 不同的研究者提出了基于浮点、格雷码的遗传算法基因编码方式，基于多点、均匀等不 9 太原理工大学硕士研究生学位论文 同交叉和变异算子。特殊算子的应用，以及不同再生和选择方法，使得遗传算法理论研 究和应用研究都成了十分热门的课题。1 9 8 9 年美国伊利诺大学的g o l d b e r g 所著的 “g e n e t i ca l g o r i t h m si ns e a r c h ，o p t i m i z a t i o na n dm a c h i n el e a r n i n g ”，这本书对于遗传 算法理论及其多领域的应用提供了较为全面的分析和例证。m i c h a l e w i c z 出版的另一本 很有影响力的著作“g e n e t i ca l g o r i t h m s + d a t as t r u c t u r e s = e v o l u t i o np r o g r a m s ”，对于遗 传算法应用起到了推波助澜的作用。 2 4 遗传算法的基本思想和原理 遗传算法的基本思想是基于d a r w i n 进化论和m e n d e l 遗传学说的。 d a r w i n 进化论最重要的是适者生存原理。它认为每一物种在发展中越来越适应环 境。物种每个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新变化。 在环境变化时，只有那些能适应环境的个体特征才能保留下来。 m e n d e l 遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中，并 以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质：所以，每个 基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的后 代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。 遗传算法g a 把问题的解表示成“染色体”，在经典算法中也就是表示成二进制编 码的串。并且，在执行遗传算法之前，给出一群“染色体”，也就是假设解。然后，把 这些假设解置于问题的。环境”中，并按适者生存的原则，从中选择出较适应环境的 “染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代。染色体”群。 这样，一代一代的进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题 的最优解。 为了更好地理解遗传算法表述上所借鉴的生物学术语，表2 2 给出了生物学术语在 遗传算法中的具体含义。 1 0 太原理工大学硕士研究生学位论文 t a b l e 表2 - 2 生物学术语在遗传算法中酊含义 生物学遗传算法 染色体 字符串 基因字符位 基因型 字符串结构 表现型字符串含义 杂交字符串片段的互换 变异字符位的改变 适应性适应函数值 2 5 遗传算法的步骤 孵：越 图2 3 遗传算法的计算流程图 f i g 2 - 3t h ef l o wc h a r tf o rg e n e t i ca l g o r i t h m 从上图2 - 3 可以看出遗传算法实质上是一个迭代计算过程( 线框内) ，其实施的主要 步骤包括编码、群体初始化、选择、遗传操作、评价和终止判定六步。 1 编码 编码的主要任务是建立解空间与染色体空间点的一一对应关系。遗传算法通常在染 色体空间中进行操作。在多数情况下，不同的编码方式决定了不同的遗传操作方式。对 编码的一般原则性要求主要有完备性、健全性和非冗余性。完备性是指解空间中的所有 点都能表示成为染色体空间中的点；健全性是指染色体空间中的所有点都能表示为解空 l l 太原理工大学硕士研究生学位论文 间中的点；非冗余性是指解空间到染色体空间的一一对应。 2 群体初始化 与传统优化方法相比，遗传算法一个显著的特点是对群体操作，所以在进化的开始 必须进行群体初始化，产生进化的起点群体。通常随机构造初始群体，当然也可以在初 始群体中植入一些具有特殊“性状”的个体，以加速算法向全局最优解的收敛。 3 选择 遗传算法的选择操作与生物的自然选择机制相类似，目的是用来重组种群个体，即 根据适者生存原则从群体中选择出较适应环境的个体。以及被选个体将产生多少个子代 个体，这些选中的个体用于繁殖下一代。故有时也称这一操作为再生( r e p r o d u c t i o n ) 实现原则为。性状”( 适应度) 优良的个体具有较多的机会被选进交配池产生后代，而“性 状”低劣的个体则具有较少的机会被选择。这里的“性状”( 适应度) 通过评价操作进 行定量化。最常用的选择方式是赌轮选择、联赛选择和排序选择。这样，就产生了对环 境适应能力较强的后代。从问题求解角度来讲，就是选择出和最优解较接近的中间解。 4 遗传操作 遗传操作被视为遗传算法的核心。它直接影响和决定了遗传算法的优化能力，是生 物进化机理在遗传算法中最主要的体现。目前，已有适合用于各种不同类型问题的多种 遗传操作算子。其中，杂交与变异是最常用的遗传操作，杂交体现了同一群体中不同个 体之间的信息交换，而变异则能维系群体中信息的多样性。它们在优化中的主要作用是 以不同的方式不断产生新的个体。 4 。1 交叉( c r o s s o v e r ) 、杂交或基因重组( r e c o m b i n a t i o n ) 这是在选中用于繁殖下一代的个体中，随机选择两个不同个体的相同位置的基因进 行交换，从而产生新的个体。即交叉或基因重组是结合来自父代交配种群中的信息产生 新的个体。依据个体编码表示方法的不同，有以下的算法：实值重组( r e a lv a l u e d r e c o m b i n a t i o n ) ；离散重组( d i s c r e t er e c o m b i n a t i o n ) ；中间重组( i n t e r m e d i a t e r e c o m b i n a t i o n ) ：线性重组( u n e a rr e c o m b i n a t i o n ) ；二进制交叉( b i n a r yv a l u e dc r o s s o v e r ) ； 单点交叉( s i n g l e p o i n t c r o s s o v e r ) ；多点交叉( m u l t i p l e p o i n t c r o s s o v i ) ；均匀交叉( u n i f o r m l t o $ 8 0 v e