（模式识别与智能系统专业论文）遗传计算模型及其在复杂数据处理中应用的研究.pdf

摘要 作为一种模拟物种进化和自然选择的进化计算方法，遗传算法( g e n e t i c a l g o r i t h m ，g a ) 在优化计算、数据挖掘、机器学习等领域内有着广泛的应用前景。 本文从生物信息学中海量基因数据处理的需要出发，研究了基于遗传算法的优化 计算模型，并将其应用于生物信息学复杂数据处理。本文所取得的主要研究成果 如下： ( 一) 一种基于遗传算法的进化计算模型 论文提出了一种基于遗传算法的进化计算模型( e v o l u t i o n a r yc o m p u t i n g m o d e l ，e c m ) 。在e c m 中，种群中的每一个成员都以不同的程度影响种群的进 化，具体表现在对于子代个体的形成和发展的影响上。e c m 定义了个体对进化 的影响因子，并以个体的影响因子为参数定义了个体的形成算予和发展算子。 e c m 通过群体的进化实现对复杂优化问题的解。论文设计了e c m 的神经网络拓 扑结构，在该拓扑结构中，交叉、突变、评价和竞争在内的全部遗传操作都通过 神经网络并行地实现，e c m 因而具有分布存储、并行计算和易于硬件实现的特 点。研究表明，e c m 是采用算术交叉算子的经典遗传算法以及采用频率扫描交 叉算子的多父辈交叉遗传算法的推广。在经典测试函数集上的实验结果显示，与 经典的遗传算法相比，e c m 具有更强的优化计算功能。 ( 二) 一种内嵌蚁群的基因联接学习遗传计算模型 论文提出了一种内嵌蚁群的基因联接学习遗传计算模型a n t g a 。在a n t g a 中，遗传算法的种群对应蚁群，遗传算法的每一个染色体同时又是一只蚂蚁，遗 传算法的染色体编码对应蚂蚁的一条路径。在a n t g a 中，基因联接强度的计算 以及联接学习均采用蚁群算法实现，即：基因的联接强度被定义为蚁群的信息素 浓度，蚁群的信息素矩阵用于描述和评价遗传算法中基因间的联接关系，基因间 的联接强度关系用作遗传操作中选择交叉和突变位点的依据，蚁群算法中调节信 息素的算子被用作基因联接学习算法。本文的研究表明，a n t g a 继承了h o l l a n d 关于紧密联接基因和松散联接基因的概念以及通过进化得出最优编码次序的思 想，可以较好地求解有乔难度问题。a n t g a 中的基因连接学习是并行进行的， 并且它的遗传操作能以较大的概率在基因联接强度较弱的位点上进行，避免了积 木块过多地被遗传操作所破坏，从而提高了遗传算法的效率。与基因联接学习遗 传算法相比，a n t g a 的个体编码长度不会随着等位基因数量的增加而成倍的增 加，具有较低的染色体编码复杂度，以及较低的联接学习复杂度和计算复杂度。 j b 意工业大学工学博士学位论文 ( 三) 基于e c m 的多序列比对算法 论文提出了基于遗传计算模型e c m 的多序列比对算法，采用了基于空位串 位置和长度的编码方案，使得染色体编码矩阵具有相同的大小，便于予代个体的 彤成和发展操作将交叉位点选择的计算复杂度南o ( 柳降低到o ( 1 ) 。论文提出 了完全比对块的概念和完全比对块加权的多序列比对目标函数，该目标函数有利 于 l 导遗传算法发现更多的完全比对块。本章在1 0 个测试序列集上对基于e c m 的多序列比对算法进行了实验研究，其中5 个测试集上的测试结果好于 c l u s r a lw 和m u l t a i i n 的测试结果，2 个坝i 试集上的测试结果与c l u s t a lw 或m u l t a l i n 的测试结果相同，3 个测试集上的测试结桨略次于c l u s t a lw 和 m u l t a l i n 的测试结柒。就总体效果而言，基于e c m 遗传计算模型的多序列比对 算法优于c l u s t a lw 和m u l t a l i n 豹多序列拢对算法。 ( 四) 基于a n i g a 的多发性骨懿瘤基因表达谱分析 论文提出了一种基于芷确分类样本数和错误分类样本数的分类准确度评价 函数，将基于基因表达谱的多发性骨髓瘤特征基嗣选择蚵题和分类规则提取问题 转化为优化计算问题，并应用内嵌蚁群的基因联接学习遗传计算模型a n t g a 从 基因表达数据中提取多发性骨髓瘤的特征基因和分类规则。论文以a r k a n s a s 癌 症研究中心的多发性骨髓癌基因表达数据集作为研究对象，应用a n t g a 从1 0 5 个基冈表达数据样本的7 1 2 9 个基因中鉴别出了3 个特征基因，以及基于这3 个 特征基因的3 条多发性骨髓瘤分类规则。应用这些规则对a r k a n s a s 癌症研究中 心的多发性膏髓瘤基因表达谱进行测试，取得了1 0 0 的正确率。就a r k a n s a s 数 据库中现有的多发性骨髓癌基因表选数据丽言，论文取得了目薄有关多发性骨髓 瘤基因表达谱分根的最好的研究结果。 本文的研究工作对于促进遗传算法本身( 包括遗传算法的模型、并行遗传算 法和硬件遗传算法等) 的发展以及遗传算法在生物信息学等复杂数据处理和机器 学习中的应用研究具有积极的意义。 关键词：遗传算法，复杂数据处理，神经溺络，蚁群算法，生物信息学 h a b s t r a c t a b s t r a c t t h i st h e s i ss t u d i e db o t ht h eg e n e t i ca l g o r i t h m ( g a ) 一b a s e d o p t i m i z a t i o nm o d e l s a n dt h e i ra p p l i c a t i o n si nb i o i n f o r m a t i c sc o m p l e xd a t ap r o c e s s i n g t h ea c h i e v e m e n t s o ft h e 恤e s i sc a nb es u m m a r i z e da sf o l l o w s ； ( 1 ) ag a b a s e de v o l u t i o n a r yc o m p u t i n gm o d e l t h i st h e s i s p r o p o s e dag a - b a s e de v o l u t i o n a r yc o m p u t i n gm o d e l _ ( e c m ) ，i n w h i c he v e r yi n d i v i d u a li nt h e p a r e n t a lp o p u l a t i o n c a r t i m p a c t t h ed i r e c t i o no f e v o l u t i o n ，i e 。e v e r yi n d i v i d u a lc a l li m p a c t t h ef o r m i n ga n d d e v e l o p i n g o f o f f s p r i n g i n ac e r t a i ne x t e n t a ni n d i v i d u a l se v o l u t i o n a r yi m p a c tf a c t o r , w h i c hi sd e f i n e do nb o t h t h ef i t n e s so ft h ei n d i v i d u a la n dt h et o t a lf i t n e s so ft h ep o p u l a t i o n ，i su s e dt od e c i d e h o w s t r o n gt h ei n d i v i d u a lc a ni m p a c t t h ef o r m i n ga n dd e v e l o p i n go ft h e o f f s p r i n g a n e u r a ln e t w o r kb a s e dt o p o l o g yf o re c mi sa l s o p r o p o s e d ，w h i c hc a ne x e c u t ea l l g e n e t i co p e r a t i o n si n c l u d i n gc r o s s o v e r , m u t a t i o n ，e v a l u a t i o na n dc o m p e t i t i o np a r a l l e l o nt h es c a l eo f p o p u l a t i o n c o n s e q u e n t l y , e c mp o s s e s s e s t h e p r o p e r t i e s 。o f d i s t r i b u t i n gm e m o r y , p a r a l l e lc o m p u t i n g a n d e a s i l yh a r d w a r er e a l i z a t i o n t h ea n a l y s i s r e s u l t si n d i c a t et h a te c mi st h eg e n e r a l i z a t i o no f t h ec l a s s i c a lr e a l c o d e dg aw i t i lt h e a r i t h m e t i c a lc r o s s o v e ro p e r a t o rm a dt h eb i n a r y - c o d e dm u l t i - p a r e n tr e c o m b i n a t i o n g aw i t ht h e s c a n n i n g c r o s s o v e r o p e r a t o r e x p e r i m e n t a l r e s u l t so nas u i to f b e n c h m a r kt e s tf u n c t i o n sv a l i d a t e dt h a te c m o u q ) e r f o r m s t h ec l a s s i c a lg a ( 2 ) a n a n tc o l o n ye m b e d d e d l i n k a g el e a r n i n gg e n e t i ca l g o r i t h m t h i st h e s i s p r o p o s e d a l la n t c o l o n y e m b e d d e dl i n k a g el e a r n i n g g e n e t i c a l g o r i t h m ( a n t g a ) ，i nw h i c ht h ep o p u l a t i o no f g a c o r r e s p o n d st ot h ea n tc o l o n y , e v e r yi n d i v i d u a l i sa tt h es a m et i m ea na n t ，a n dt h ec h r o m o s o m ec o d ec a nb e c o n s i d e r e da sar o u t eo fa na n t t h el i n k a g es t r e n g t ha m o n gg e n e si sd e f i n e da st h e p h e r o m o n e t r a i lo ft h ea n t c o l o n y , a n d t h e p h e r o m o n e m a t r i xo fa n tc o l o n y o p t i m i z a t i o n ( a c o ) i sa d a p t e d t od e s c r i b ea n dr e c o r dt h el i n k a g ea m o n gg e n e s t h e p h e r o m o n eu p d a t eo p e r a t o ro f a c oi sa d o p t e da st h el i n k a g el e a r n i n ga l g o r i t h ma n d t h ec r o s s o v e ra n dm u t a t i o ns i t e sa r es e l e c t e da c c o r d i n gt ot h el i n k a g ei n f o r m a t i o n t h e a n a l y s i sr e s u l t si n d i c a t et h a ta n t g a c a nd i s t i n g u i s ht h et i g h t l yl i n k e dg e n e sa n d l o o s e l yl i n k e dg e n e sa n dr e a l i z et h ei d e ao fe v o l v i n go p t i m a lc o d i n gs e q u e n c eo f h o l l a n d e x p e r i m e n t a lr e s u l t sv a l i d a t e d t h a ta n t g ac a ns o l v et h eb o u n d e dd i f f i c u l t y p r o b l e m sc o r r e c t l ya n de f f i c i e n t l y , i tc a n a l s ol e a r nt h el i n k a g ep a r a l l e la n dm a k et h e m 北京工业大学工学博士学位论文 g e n e t i co p e r a t i o n t a k ep l a c eo nt h ew e a k e r l i n k i n gs i t e sw i t h ah i g h e r p r o b a b i l i t y , a sa r e s u l t ，a n t g ac a na v o i dt h eb u i l d i n gb l o c k sb e i n gf r e q u e n t l yd i s r u p t e db yg e n e t i c o p e r a t i o na n di m p r o v et h ee f f i c i e n c yo fg a c o m p a r e dw i t ht h el i n k a g el e a r n i n g g ao fh a r i k ，a n t g ah a sb o t hal o w e rc o d i n gc o m p l e x i t ya n dl o w e rc o m p u t i n g c o m p l e x i t y ( 3 ) a ne c m - b a s e dm u r i p l es e q u e n c ea l i g n m e n ta l g o r i t h m t h i st h e s i s p r o p o s e d a ne c m b a s e d m u l t i p l es e q u e n c ea l i g n m e n t ( m s a ) a l g o r i t h m t h i sa l g o r i t h ma d o p t e dam a t r i xc o d i n gm e t h o db a s e do nt h e s i t ea n d l e n g t ho fg a p - s t r i n g , 。w h i c hm a k e se v e r yc h r o m o s o m ew i t ht h es a m es i z e f o rt h e c o n v e n i e n c eo fb r e e d i n g o f f s p r i n g ，a s ar e s u l t ，t h e c o m p u t a t i o nc o m p l e x i t y o f c r o s s o v e rs i t es e l e c t i o nc a nb er e d u c e df r o mo ( n ) t o o o ) t h i s t h e s i sa l s op r o p o s e d t h ec o n c e p to fa b s o l u t ea l i g n m e n tb l o c k ( a a b ) a n dt h ea a b w e i g h t e ds u m o f - p a i r o b j e c t i v ef u n c t i o n ，w h i c hc a nd r i v ee c m t of i n dm o r ea a bi nm s a ，e x p e r i m e n t a l r e s u l t so n1 0t e s ts e q u e n c es e t sv a l i d a t et h a tt h ee c m - b a s e dm s a a l g o r i t h ms l i g h t l y o u t p e r f o r m sc l u s t a lw a n dm u l t a l i n ，t h ef o r m e ri s s u p e r i o rt o ，e q u a l t oa n d i n f e r i o rt ot h el a t t e ro n5 2a n d3t e s ts e t sr e s p e c t i v e l y ( 4 ) a n a l y z i n g t h e m u l t i p l em y e l o m a ( m m ) g e n ee x p r e s s i o n d a t aw i t ha n t g a t h i st h e s i sp r o p o s e dac l a s s i f i c a t i o na c c u r a c ye v a l u a t i o nf u n c t i o nb a s e do nb o t h t h ec o r r e c t l yc l a s s i f i e da n dt h ei n c o r r e c t l yc l a s s i f i e ds a m p l e s ，w h i c ht r a n s l a t e st h e p r o b l e mo ft h em m sm a r k e rg e n es e l e c t i o na n dc l a s s i f i c a t i o nr u l ee x t r a c t i o ni n t oa o p t i m i z a t i o np r o b l e m ，a n da p p l y i n ga n t g a t os e l e c tt h em a r k e r g e n e sa n d t oe x t r a c t t h ec l a s s i f i c a t i o nr u l e so fm m t a k i n gt h em u l t i p l em y e l o m ag e n ee x p r e s s i o nd a t a f r o ma r k a n s a sc a n c e rr e s e a r c hc e n t e ra sad a t as e t ，t h i st h e s i sd i s c r i m i n a t e d3k e y g e n e s f r o mt h e7 1 2 9g e n e so f1 0 5g e n ee x p r e s s i o ns a m p l e s ，a n ds u m m e du p3 c l a s s i f i c a t i o nr u l e sf o rt h em m d i a g n o s i sa n dp r e d i c t i o n t h e s er u l e sc 姐c l a s s i f yt h e w h o l ed a t as e tw i t h o u te r r o ra n da c c o r dw i t ht h ek n o w nb i o l o g i c a lk n o w l e d g e t h i s t h e s i sa c h i e y e dt h eb e s tr e s u l to nt h ec u r r e n td a t ao ft h ed a t as e to ft h ea r k a n s a s c a n c e r r e s e a r c hc e n t e r t h e s t u d yp r e s e n t e di nt h i st h e s i sm a y m a k eas i g n i f i c a n tc o n t r i b u t i o nt ob o t ht h e d e v e l o p m e n t o fg ai t s e l fa n dt h ea p p l i c a t i o no f g a e s p e c i a l l yf o r 也ea p p l i c a t i o n s o f g ai nb i o i n f o r m a t i c sc o m p l e xd a t ap r o c e s s i n ga n dm a c h i n el e a r n i n g k e yw o r d s ：g e n e t i ca l g o r i t h m ，c o m p l e xd a t ap r o c e s s i n g ，n e u r a ln e t w o r k ， a n tc o l o n yo p t i m i z a t i o n ，b i o i n f o r m a t i c s 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：垒囊雄日期：! ! q 4 生! 旦! q 目 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：蕉建捌垂导师签名_ 幽日期：塑，笙，旦；。旦 第一章绪论 第1 章绪论 1 1 课题研究背景、目的和意义 本研究课题的基本目标是：研究和设计基于遗传算法的优化计算模型，并将 其应用于生物信息学( b i o i n f o r m a t i c s ) 复杂数据的分析和处理。本文的研究工作对 于促进遗传算法本身的发展，包括遗传算法的模型、并行遗传算法和硬件遗传算 法等的发展，以及遗传算法在生物信息学复杂数据处理和机器学习中的应用研究 都具有积极的意义。 本研究课题源于国家自然科学基因重点支持项目“复杂系统意义下的生物信 息学中若干问题研究( 6 0 2 3 4 0 2 0 ) ”。随着人类基因组计划的实施，生物信息学已 成为科学研究的重要领域。生物信息学的任务是综合运用计算机科学、数学和生 物学的方法对生物学数据进行加工、存储、分类、检索与分析，进而揭示数据所 蕴含的生物学意义。 人类基因组计划的实施和生物信息学的发展导致复杂生物学数据的剧增，基 因组相关数据大约每1 4 个月增加一倍。遗传算法在海量的复杂生物学数据处理 中无疑具有重要的价值。本文作者在应用遗传算法对生物学数据进行处理的研究 中发现，面对复杂的基因数据，经典遗传算法仍然存在一定的局限性。有鉴于此， 本文以强化计算功能为目的，对遗传算法进行了研究，设计了新的基于遗传算法 的优化计算模型，并将其成功地应用于多序列比对问题和肿瘤基因表达谱的分析 问题。 1 2 遗传算法的研究与发展 i 2 1 遗传算法发展简史 二十世纪7 0 年代，h o l l a n d 和他在密歇根州立大学的博士生们基于达尔文的 自然选择学说提出了一种模拟生物遗传机制的优化算法，导致了遗传算法的形成 1 】。 1 9 6 5 年，h o l l a n d 首次提出了人工遗传操作的概念，并将人工遗传操作应用 于自然系统和人工系统【2 】。 1 9 6 7 年，b a g l e y 首次使用了“遗传算法( g e n e t i c a l g o r i t h m s ，g a ) ”的术语，并 讨论了遗传算法在自动博弈中的应用【1 1 。 1 9 7 0 年，c a v i c c h i o 把遗传算法应用于模式识别【2 】。 1 9 7 5 年，h o l l a n d 出版了遗传算法的奠基性著作在自然和人工系统中的自 适应性【2 】，该书系统的阐述了遗传算法的基本理论和方法，并提出了遗传算法 北京工业大学工学博士学位论文 的模式定理，确认了结构重组遗传操作对于获得隐并行性的重要性。 1 9 7 5 年，d ej o n g 在其博士论文对于一类遗传自适应系统的行为分析f 3 】 中，进一步完善和系统化了选择、交叉和变异等遗传操作，提出了“代沟”等新的 遗传操作技术，建立了著名的d e j o n g 五函数测试平台，定义了性能评价标准。 d e j o n g 的工作为以后的遗传算法研究树立了范例，并为遗传算法的广泛应用奠 定了坚实的基础。 1 9 8 3 年，g o l d b e r g 第一次把遗传算法应用于实际的工程系统煤气管道的 优化，并于1 9 8 9 年在遗传算法与搜索、优化和机器学习1 4 j 一书中对于遗传 算法从理论上、方法上和应用上进行了系统地总结。 1 9 9 2 年，k o z a 在遗传编程【月一书中提出了遗传编程的概念，成功地把 遗传编程的方法应用于人工智能、机器学习、符号处理等领域。 1 9 9 4 年，e i b e n 等首次提出了多父辈交叉的概念，开展了关于多父辈交叉遗 传算法的研究【6 1 。 1 9 9 7 年，h a r i k 提出基因联接学习遗传算法，借用了基因联接的概念，并通 过采用独特的染色体编码方法和交叉操作算子进行基因联接学习，使遗传算法在 进化过程中获得最优的染色体编码次序【_ ”。 当前遗传算法的研究重点主要包括：多父辈遗传算法、并行遗传算法、硬件 遗传算法、基于马尔科夫模型的的遗传算法建模和分析、混杂遗传算法( h y b r i d g a ) 、进化多目标优化( e v o l u t i o n a r y m u l t i c r i t e r i o no p t i m i z a t i o n ) 及其应用研究等 【8 】。 1 2 2 关于交叉算子和多父辈交叉遗传算法的研究 1 2 2 1 关于交叉算子的研究 交叉算子是遗传算法中最主要的遗传操作算子【1 。从交叉操作的位点数量 来看，交叉算子可分为单点交叉、两点交叉、多点交叉和均匀交叉( u n i f o r m c r o s s o v e r ) 。 单点交叉操作是h o l l a n d 提出的最基础和最常用的一种交叉操作形式。单点 交叉操作在父代个体的编码全长上随机地选择一个交叉操作位点，拷贝每一个父 代个体在交叉位点之前的编码，拼接上另一个父代个体在交叉位点之后的编码从 而形成新的子代个体。 按照h o l l a n d 的思想，单点交叉的信息量比较少，不利于长距模式的保留和 重组，而且位串末尾的重要基因总是被交换，即具有尾点效应( e n d p o i n te f f e c t ) ， 因此在实际应用中又发展了两点交叉和多点交叉算子【9 1 ，并在此基础上提出了均 匀交叉算子( u r l i f o r mc r o s s o v e r ) 。均匀交叉对于所选择的染色体编码的每一位按 相同的概率进行随机均匀交叉。s y s w e r d a 从理论上分析比较了0 5 一均匀交叉、单 第一章绪论 点交叉和两点交叉算子，指出对于有些问题均匀交叉有明显的优势，但对于其他 问题则比两点交叉要差【1 0 】。s p e a r s 和d ej o n g 给出了p 均匀交叉的分析，认为 均匀交叉要优于多点交叉【l l 1 2 。根据e s h e l m a n 的实算结果，单点交叉相对而言 最差，而其他算子则各有优劣，它们对于某些特定问题效果突出，但对其他的问 题则不然1 。 1 2 2 2 关于多父辈交叉遗传算法的研究 在传统的遗传算法中，交叉操作通常是由两个父代个体通过分断和重组产生 两个子代。多父辈交叉( m u l t i - p a r e n tr e c o m b i n a t i o n ) 操作在近年来逐渐引起了研究 者的注意。通常认为，多父辈交叉操作有可能在产生子代个体的过程中综合更多 ( 相对于两父辈而言) 父代个体的信息，因而可能获得更好的解空间搜索效率和 寻优质量。m u h l e n b e i n 和v o i g t 研究了多父辈的基因池重组算子( g e n ep o o l r e c o m b i n a t i o n ) ”l 。1 9 9 4 年，e i b e n 等首次提出了多父辈交叉的概念，随后又提出 了二值编码遗传算法的多父辈扫描交叉( s c a n n i n gc r o s s o v e r ) 算子和对角线交叉 f d i a g o n a lc r o s s o v e r ) 算子，并采用一系列的测试函数对它们迸行了研究 6 1 4 ，1 5 , 1 6 o 他们的研究发现：对于绝大多数的优化问题，多父辈交叉要明显优于两父辈交叉， 只有极少量的结果不支持这个结论。他们特别强调指出，在这些多父辈交叉试验 中，很明显遗传算法这种优化性能的显著改善不仅仅根源予更多交叉位点的引 入，而且更多的是由于多个父辈参与交叉操作的结果。他们认为，随着在交叉操 作中多父辈的引入，降低了超级个体将自身复制到子代中的可能性，这就意味着 带来更为多样的解空间搜索结果从而减少了遗传算法早熟的危险【l5 1 。t s u t s u i 等提 出了在实数编码遗传算法中采用边界镜像延拓( b o u n d a r ye x t e n s i o nb ym i r r o r i n g ， b e m ) 的质心交叉( c e n t e ro fm a s sc r o s s o v e r , c m x ) 算子和单纯形交3 l ( s i m p l e x c r o s s o v e r ，s p x ) 算子，并通过测试函数对它们进行了研究。他们得出的结论是对 于c m x 算子，多父辈交叉操作的优化性能要明显优于两父辈交叉操作，但这种 性能改善的程度将因问题的不同而不同；而s p x 算子在参与交叉操作的父辈数量 为3 ( 对于低维的函数) 和4 ( 对于高维的函数) 时，对于多峰和或上位显性的函数具 有较好的优化性能2 1 ，2 2 1 。 扫描交叉算子( s c a n n i n gc r o s s o v e r ) 是e i b e n 提出的多父辈交叉算子之一，扫 描交叉操作的思想是，通过扫描选定的n 个父代个体来生成一个子代个体，在该 过程中，算子扫描这些父代个体的每一位基因编码，从中决定哪一个父代个体的 基因编码可以传递给子代个体从而作为子代个体的当前位基因编码。与传统的遗 传算法相比，在扫描交叉操作的予代个体的构建过程建立在对搜索空间更多 f h 2 1 的采样的基础上，并且子代个体的每一位基因都是根据某种机制选择的最 有希望的基因。所谓“最有希望”可以是与问题无关的，也可以是基于某种与具体 北京工业大学工学博士学位论文 问题有关的启发式信息的。 扫描交叉算子是均匀交叉( u n i f o r mc r o s s o v e r ) 算子的概括和推广。在扫描 交叉操作中， 2 个父代个体共同繁殖一个子代个体，从参与交叉操作的r 个父 代个体的第i 位基因编码中选择一个作为子代个体的第i 位基因编码。令 x 1 , x 2 ，为所选定的父代个体，其编码长度为l ，x 为子代个体，则扫描交叉 算子的操作过程如下： 显然，传统的均匀交叉算子的工作机理与扫描交叉算子的工作机理相同，所 不同的是，均匀交叉算子总是从父代个体的编码中随机地选择一个编码作为子代 个体的基因编码，而扫描交叉算子则是根据某种机制从这些父代个体的当前位编 码中选择一个作为子代个体的相应位编码。这种选择机制不是固定的，根据不同 的基因选择机制可以将扫描交叉算子分成不同的形式。与问题无关的选择机制包 括随机均匀选择( u n i f o r l r lr a n d o mc h o i c e ) ，投票选择( v o t i n g ) ，根据父代个体的适 应度值加偏的随机选择( r a n d o m c h o i c eb i a s e d b y t h ef i t n e s so f t _ h ep a r e n t s ) 等。在 e i b e n 的研究中，广泛采用的是均匀扫描交叉和基于出现频率的扫描交叉算子， 参与多父辈交叉操作的父辈数量也限制在1 0 个以内。现将这些扫描交叉算子的 具体操作介绍如下： ( 1 ) 均匀扫描交叉算子均匀扫描交叉算子( u n i f o r ms c a n n i n g ) 是两父辈的 均匀交叉算子在父辈数量维数上的推广。均匀交叉操作定义如下： 从左到右同时历经( 两个) 父代个体和( 两个) 子代个体的每一位编码； 在子代个体1 编码的每一个位置上，随机地决定是继承父代个体1 或 父代个体2 的相应位基因编码，子代个体2 的基因编码选择与此相反。 在均匀扫描交叉操作中，只生成一个子代个体。子代个体的每一位等位基因 都来自于父代个体，子代个体从每一个父代个体中继承遗传基因编码的概率相 等。即在均匀扫描交叉操作中，子代个体从父代个体f 中继承基因的概率为： 】、 p u j 2 n u m b e ro f p a r e n t s o 1j 第一章绪论 子代个体从父代个体i 中继承基因数量的期望为 e ( i ) = p ( i ) x c h r o m o s o m e l e n g t h( 1 2 ) ( 2 ) 基于出现频率的扫描交叉算子基于出现频率的扫描交叉( o c c u r r e n c eb a s e d s c a n n i n g ) 操作是基于如下的假定：对于根据个体的适应度值选择出来的父代个 体，在他们的特定编码位置上出现频率最高的编码很有可能就是该位置上最好的 编码。如果在这些父代个体的某一位编码中没有一个出现频率最大的编码存在， 则选择第一个父代个体的相应位编码。 在基于出现频率( 投票选择) 的扫描交叉操作中，子代个体继承父代个体在 当前位编码中出现频率最高的等位基因作为自己相应位的基因。该操作的一个示 例如下： p a r e n t1 ： p a r e n t2 ： p a r e n t3 ： p a r e n t4 ： c h i l d ： l l l l0101 1l00011o ll000l01010000l0 0ol 1lol0l0l0lol1 0lol0101o1l0o100 l lll0l01 1 1000010 ( 3 ) 基于适应度值的扫描交叉算子基于适应度值的扫描交3 z ( f i t n e s sb a s e d s c a n n i n g ) 操作以与父代个体的适应度值比例相同的概率分布继承父代个体的基 因编码。假定对于一个求极大值的问题，父代个体i 的适应度值为f ( i ) ，则根据 赌盘选择操作，子代个体从父代个体i 中继承编码值的概率为 阶舄 ( 1 3 ) 子代个体从父代个体i 中继承基因数量的期望为 e ( f ) = p ( i ) x c h r o m o s o m e l e n g t h( 1 4 ) 此外，e s h e l m a n 、m a t h i a s 和s e h a f f e r 在b l x 一口交叉算子的基础上提出了 b o x b l x 一口一、p o o l w i s eb o x - b l x 一口一卢以及d i r e c t i o n a l b l x 一口一卢一，算子 1 8 1 o o n o 和k o b a y a s h i 于1 9 9 7 年提出了实数编码遗传算法的u n i m o d a l n o r m a l d i s t r i b u t e dc r o s s o v e rf u n d x ) 交叉算子【1 9 1 。t s u t s u i 等提出了在实数编码遗传算法 中采用边界镜像延拓( b o u n d a r ye x t e n s i o nb ym i = o f i n g ，b e m ) 的质心交3 z ( c e n t e r o fm a s sc r o s s o v e r ，c m x ) 算子、m u l t i p a r e n tf e a t u r e w i s ec r o s s o v e r ( m f x ) 算子、 s e e d c r o s s o v e r ( s x ) 算子、和单纯形交叉( s i m p l e x c r o s s o v e r ，s p x ) 算子【2 0 | 2 1 , 2 2 1 。 这些交叉算子的一个共同特点是，由父代个体所确定的一个搜索子空间，然后通 北京工业文学工学博士学位论文 过一种随机地选择$ 制在该子空间及其一定程度上的外延空阔中选择一个点作 为子代个体的编码。由于与本文的研究缺乏相似之处，故不再赘述。 l2 3 关于并行遗传算法的研究 虽然遗传算法作为种广谱、鲁棒的优化算法在求解优化问题方面具有其独 特的优势1 3 j ，通常能在合理的时间盎找 i 满意解，但是随着求解闫题的复杂性及 难度的增加，当问题的解空间较大或者在实时性要求较高时，遗传算法就会面临 运行速度的瓶颈口，4 j ，提高g a 的运行速度便显得尤为突出。由于遗传算法是一 种种群依赖的优化算法，在它的每代中都有许多的个体组成，每一个个体都需 要根据其目标函数计算适应度值，这种频繁的适应度值计算使得遗传算法的应用 领域受到厂较大的限制。 遗传算法在每代中同时搜索解空间的许多个点，丽不是单个点，具有内在 的并行性，非常适合于在大规模并行计算机上实现，大规模并行计算枫的日益普 及为并行g a 奠定了物质基础。并萼亍遗传算法( p a r a l l e lg e n e t i ca l g o r i t h m ，p g a ) 的基本思想是将整个任务分解成为若于个子任务，并同时采用一组处理器分别求 解各个了任务，采用这种分而治之的策略旨在发挥遗传算法的内在并行机制，通 过并行处理提高遗传算法的运行效率。p o a 可以在计算机网络或大型的并行计 算机上实现。目前并行遗传算法的实现方案大致分为三类”q ： 123 l 主从式模型 主从式模型r m a s t e r s l a v em o d e l ) 的系统分为个主处理器和若干个从处理 器，主处理器监控整个染色体种群，并基于全局统计执行选择操作，各个从处理 器接收来自主妊理器的个体进行交叉和变异，产生薪一代个体，计算其适应度俊 并把计算结聚传给主处理器( 图1 - l a ) 。主从式模型易于实现，如果计算时间主 要罔在评价上，这是一种非常有效的并行化方法。此外，泛还保留了简单g a 的 搜索行为，因而可盲接应用简单g a 的理论成果。 1 2 32 粗粒度模型 粗粒度模型( c o a r s e - g r a i n e dm o d e l ) 是对经典g a 结构的扩展，具有不同的行 为它将群体划分为多个子群体( 又称区域) ，每个区域独自运行个g a 。此时， 交配和竞争受区域的限制，配偶取自同一区域，子代与同一区域中的亲本竞争。 因此，这种模型又称为孤岛模型( i s l a n dm o d e l ) 。这类p g a 通常在分布式存储 器m i m d 计算机上实现，赦也称为分布式遗传算法( d i s t r i b u t e dg e n e t i ca l g o r i t t u n ， d g a ) 是目前应埽最为广泛的一种并行遗传算法( 图i - t b ) ，除了基本的遗传 算子外，粗粒度模型；l 入了t 朔梦算子负责管理区域之闯的个体交换。p e 娃e y 等 证