（计算机应用技术专业论文）基于并行免疫遗传算法的无向排列的反转排序方法研究.pdf

摘要 生物的遗传物质随着进化而改变，相对于单个基因或少数几个基因组成的基因块的 点变化，越来越多的研究更加关注基因组水平的较大变化。 基因组重排是生物分子进化的一种重要模式，是计算分子生物学研究的一个重要闯 题，特别是基于反转的基因组重排的数学特征及算法的研究，一直受到广泛关注。由此 产生了借助于反转来排序无向排列的问题，即给定可以代表基因组的两个排列，找到由 一个排列转化到另一个排列的最优方案。 遗传算法是一种基于自然选择和基因遗传学原理的全局性概率搜索算法，它已经过 了三十多年的研究与实践。免疫学已成为- - 1 7 学科，引起了国内外学者的注意。对于并 行计算，这是一个充满活力的领域，它经过几十年的发展，这一领域的研究成果已在科 学与技术的众多领域中随处可见。 本文提出的是一种基于并行免疫遗传算法的无向排列的反转排序的方法，将一种免 疫算子加入到遗传算法的框架中，通过对个体接种疫苗来进步提升个体的存活能力， 免疫遗传算法作为集免疫机制和进化机制于一体的全新演化算法应用到反转基因组重排 的问题上是一种新的尝试，可以避免遗传算法存在的早熟缺点，同时使免疫遗传算法并 行化可以提高收敛速度，由于无向排列的基因组反转排序问题是n p 难题，现有的算法都 是近似算法，因此将提高近似解的精确度。 关键词：基因组重排：反转排序；遗传算法；并行免疫遗传算法；远程过程调用 a bs t r a c t n 坞g e n e t i cm a t e r i a lo f o r g a n i s m sc h a n g e s 舔t h e ye v o l v e a so p p o s e dt op o i n tc h a n g ea ta g e n eo rs e v e r a lg e n e s ，m o r ea n dm o r er e s e s r c h e r sw e r ec o n c e r n e dw i t hl a r g et r a n s f o r m a t i o i l sa t t h eg e n o m el e v e l g e n o m er e a r r a n g e m e n ti sa ui m p o r t a n tm o d eo fb i o l o g ym o l e c u l a re v o l u t i o na n da l s oa n i m p o r t a n tp r o b l e mo fe o m p u t a t m n a lm o l e c u l a rb i o l o g yr e s e a r c h e s p e c i a l l yt h em a t h e m a t i c s c h a r a c t e ra n da l g o r i t h mr e s e a r c hb a s e do n g e n o m er e a r r a n g e m e n tb yr e v e r s a l sa 地a l l a t t e n t i o n 。t h e r e o u t , t h ep r o b l e mo fs o r t i n gu n s i g n e dp e r m u t a t i o nb yr e v e r s a l si si n s p i r e db y g e n o m er e a r r a n g e m e n t g i v e nt w og e n o m e sr e s p r e s e n t e da st w op e r m u t a t i o n s ，t of r e dam o s t p a r s i m o n i o u ss c e n a r i oo f s o r t i n gb yr e v e r s a l st h a tt r a n s f o r m so n ep e r m u t a t i o ni n t ot h eo t h e r g e n e t i c a l g o r i t h mi s ap r o b a b i l i s t i cs e a r c ha l g o r i t h r ab a s e do nn a t u r es e l e c t i o na n d b i o l o g ye v o l u t i o nm e c h a n i s m i td e v e l o p sa n dr e s e a r c h sf o rm o r et h a nt l l i 啊y e a r s i m m u n o l o g y h a sa l r e a d yb e c o m eas u b j e c t ；m o r ea n dm o r er e s e a r c h e r sa l ep a y i n ga t t e n t i o nt oi t p a r a l l e l c o m p u t a t i o n a li sa l le n e r g yf i e l d ，i ta l s od e v e l o p sf o rs e v e r a ly e a r s t h ep r o d u c t i o no fp a r a l l e l c o m p u t a t i o n a lc a nb ef o u n de v e r y w h e r ei ns c i e n c ea n dt e c h n i q u e i nt h i sp a p e r , a ni m m u n eg e n e t i ca l g o r i t h mf o rt h ep r o b l e mo fg e n o m er e a r r a n g e m e n t so f t h es o r t i n gu n s i g n e dp e r m u t a t i o nb yr e v e r s a l sw a sp r o p o s e d ，i ta d d e da ni m m u n eo p e r a t o rt o t r a d i t i o n a lg e n e t i ca l g o r i t h ma n dp r o m o t e dt h ev i a b i l i t yo fs o m ei n d i v i d u a l si np o p u l a t i o nb y v a c c i n a t i o n t h ei m m u n eg e n e t i ca l g o r i t h mi san e wi n t e g r a t i v ea l g o r i t h mw h i c hc o n t a i n s i m m u n em e c h a n i s ma n de v o l u t i o nm e c h a n i s m i ti san e w a t t e m p tt ou s et h i sa l g o r i t h mt os o r t u n s i g n e dp e r m u t a t i o nb yr e v e r s a l s t h ep r e c o c i a lc h a r a c t e r i s t i co fg e n e t i ca l g o r i t h m 啪b e a v o i d ，a tt h es a m et i m e ，p a r a l l e lc o m p u t a t i o n a lc a ni m p r o v ea s t r i n g e n c y b e c a u s et h ep r o b l e m o fg e n o m er e a r r a n g e m e n t so ft h es o r t i n gu n s i g n e dp e r m u t a t i o nb yr e v e r s a l sh a sb e e np r o v e dt o b ean p - h a r dp r o b l e m t h ee x i s t i n ga l g o r i t h m sa r ea p p r o x i m a t ea l g o r i t h m s ；i tc a l lb ei m p r o v e t h ep r e c i s i o no f t h ea p p r o x i m a f i o n k e yw o r d s ：g e n o m er e a r r a n g e m e n t ；s o r t i n gb yr e v e r s a l s ；g e n e r i ca l g o r i t h m ；p a r a l l e li n l m a n e g e n e t i ca l g o r i t h m ；r e m o t ep r o c e d u r ec a l l 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究 成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经 发表或撰写过的研究成果，也不包含为获得东北师范大学或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示谢意。 学位论文作者签名： 学位论文版权使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位论文的规定，即：东 北师范大学有权保留并向国家有关部门或机构送交学位论文的复印件和磁盘，允许论 文被查阅和借阅。本人授权东北师范大学可以将学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或其它复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：马老友 日 期：磁吐垒丛 学位论文作者毕业后去向： 工作单位： 通讯地址： 指导教师签名： 日期： 电话： 邮编： 日 引言 ( 1 ) 研究背景 随着人类基因组计划的实施和深入，生物学数据积累出现了前所未有的飞跃，不仅 数据量呈指数级增长，而且数据的本质出现了从生理生化数据向遗传信息的飞跃以及进 一步向遗传与结构功能相互关联信息的飞跃。这种科学数据的急速海量积累，在人类的 科学研究历史中是空前的，如何从这些海量的生物学数据中提取有用的知识，成为了对 当前生物学家、数学家、计算机专家等的巨大挑战。由此引出了- - 1 7 新兴学科：计算分 子生物学。计算分子生物学是把开发和应用数据分析的方法、数学建模和计算机仿真技 术，用于生物学研究的- - 1 7 学科。随着重要性和复杂性的不断增长，计算分子生物学已 成为当今生命科学最具活力的新兴前沿学科之一。计算分子生物学运用大规模高效的理 论模型和数值计算来识剐基因组序列中代表蛋白质的编码区，破译隐藏在核酸序列中的 遗传语言规律；直接从蛋白质序列预测蛋白质三维结构以及动力学特征，研究生物大分 子结构与功能的关系、生物大分子之间相互作用以及与配体的相互作用，促进蛋白质工 程、蛋白质设计和计算机辅助药物设计的发展：归纳、整理与基因组遗传语言信息释放 及其调控相关的转录谱和蛋白质谱的数据，模拟生命体内的信息流过程，从而认识代谢、 发育、分化、进化的规律，将人类基因组计划的成功转化为医学领域。 运用计算分予生物学，科学家们有望鉴定基因在健康和疾病中的角色，挖掘它们与 环境因素之间的关系；发展、评价以及应用以基因组为基础的诊断方法来预测对疾病的 易感性，预测药物反应，疾病的早期诊断标记，疾病在分子水平上的发展机制；应用基 因组和代谢通路的知识，通过分子模拟等方法进行计算机辅助药物设计，缩短新药开发 周期，从丙开发有效的、新的疾病治疗方法：发展基于基因组的工具来改善大众的健康 状况，从而促进人类基因组计划造福于人类。 关于并行计算，这是一个充满活力的领域，它经过几十年的发展，这一领域的研究 成果已在科学与技术的众多领域中随处可见。现在，超级并行计算机在大规模科学与工 程计算，电子商务，网络搜索，数据挖掘等领域都得到了广泛的运用。同时，利用现有 的软硬件和网络技术制造机群式超级计算机也变得越来越方便。基于对并行计算的研究 有重大的学术和运用价值，本文的重点放在了对免疫遗传算法的并行化的讨论上，采用 的是基于远程过程调用的通信机制，用普通p c 机构建了简单的并行环境来对基因组重 排问题进行科学计算。由于我国还处在社会主义发展初级阶段，经济还不是很发达，而 很多企业又需要能进行大规模计算的计算机，但现在的并行计算机价格比较昂贵，一般 企业承受不起，故研究并行就有很大的商业价值。 希望对并行计算和基因组重排的深入研究和开发出的系统，能给更多领域进行并 行提供便利，同时给社会带来利益。 ( 2 ) 国内外研究现状 近十年来，有关基因组重排，特别是基于反转的基因组重排的数学特征及算法的研 究，一直是计算分子生物学广泛关注的误题。i - i a n n e n h a l l i s l l 】【2 】，f e v z n e r 只 3 1 【4 】 5 1 的很多 理论为后来的学者提供了很多有价值的信息，这两个人是基因组重排的最重要得早期学 者。如果基因有方向，反转基因组重排问题是多项式可解的，目前已经找到了十分有效 的算法，k s t 的f a s t e ra n ds i m p l e r a l g o r i t h m l 6 1 ，如果基因无方向，反转基因组重排问题 己被证明是n p 难题 7 1 【8 】，目前尚未找到有效的算法，较好的算法是d a v i d 的近似性能 比为3 2 的近似算法 9 1 ，a n d ya u y e u ga j i t ha b r a h a m 用遗传算法估计基因组重排的反转 排序并取得了较好的结果l jo j 。 2 第一章基因组重排基础 1 1 基因组重排及其生物学背景 1 1 1 生物学背景 生物信息学人类基因组计划( h g p ，h u m a n g e n o m e p r o j e c t ) 正式启动于1 9 9 0 年，这 是一个跨世纪、跨国界的最伟大的生命科学工程，经美、英、法、德、日、冲6 国的合 作和努力，于2 0 0 0 年完成全部序列测序工作，标志着二十一世纪是生命科学的世纪。 随着分子生物科学的长足进展，生命活动的物质基础已追溯到核酸和蛋白质两大类生物 大分子的序列上，它们是生物数据的主要部分。经过对它们的研究，产生了大量的生物 数据。为了更好地组织、发掘、利用这些海量的原始生物数据，以加速生命科学的进步 和发展，计算机技术越来越多地被应用到生物学研究中，从而产生了一个崭额的领域一 一生物信息学l ”】( b i o i n f o r m a t i c s ) ，它是应用计算机和信息技术搜集、储存、分析、整理 各种生物信息，并予以管理和利用的- ( 7 交叉学科。广义地说，生物信息除了基因组信 息之外，还包括基因产物( 蛋白质或核酸) 的结构和功能，以及生物之间的进化关系等 其它信息资源。生物信息学最终是- 1 7 研究生物系统中信息现象的学科，它的主要研究 内容包括： ( 1 ) 大规模基因组测序中的信息分析，新基因的发现和鉴定。 ( 2 ) 基因组相关信息的收集、储存、管理与提供。 ( 3 ) 遗传密码的起源与生物进化分析。 ( 4 ) 完整基因组的比较研究。 ( 5 ) 大规模基因功能表达谱的分析。 ( 6 ) 蛋白质分子空间结构预测、模拟与药物分子设计。 1 i 2 基因组重排 基因在染色体上的位置是非常重要的信息，术语“基因座”( g e n el o c u s ) 用来表示 基因在染色体上的位置。一个简单的问题：给定两个基因，它们是否为同源配对基因昵? 无需借助于分子生物学技术，只要基因能够影响可视的性状即可判定。如眼睛的颜色与 翅膀的形状。我们必须检测这些性状是否是独立遗传的。如果一个后代有5 0 的机会从 一个亲代获得全部两种性状，就可以说它们是独立遗传的。如果性状独立的分配，则基 因不连锁，即它们可能属于不同的染色体。而配对的基因应该一起分离，后代将可从亲 3 代中继承两种性状。事实上，生物学中的情况常常不是一清二楚的。并不是总有1 0 0 或5 0 的分离。由于交换( c r o s s i n go v e r ) ，各种百分比的分离都会发生。当细胞分裂产 生子代细胞时，会形成新的基因排列，我们称做基因重组( g e n o m er e o a r a n g e m e n t ) 。重 组之所以发生是因为同源染色体在分离之前会交叉并交换它们的末端部分。存在无数种 重组的可能性，所以我们实际看到的重组率变化很大，这些重组率给出了染色体上基因 间距离的信息。如果基因紧密相连，因交换而分离的机会就很小；反之，如果距离远， 分离的机会就增加，直至形成独立分配。 研究不同生物之间的相似性、同源性及其进化关系，典型的方法是将两个生物的 d n a 序列进行比较，通过对序列做插入、删除或替换单个字符( 核苷酸或空格符) 的 操作，计算出从一个序列转换到另一个序列所需的最少操作次数( 通常称为两个序列间 的编辑距离) ，该方法叫做序列比对( s e q u e n c e a l i g n m e n t ) ；一般只适合于对单个基因或 有少数几个基因组成的“基因块”的研究，因而是基因组的一种局部化方法。在8 0 年 代后期，分子生物学家们的研究发现，不同物种的基因组可能包含有完全相同或极为相 似的的基因，只是基因在染色体上的排列顺序可能不同。例如；卷心菜和芜菁这鼹稀生 物体就是如此i l 引。研究包含有基因相同但基因的排列顺序不问的两个基因组相似性或进 化关系，显然不能使用上述所说的局部化方法，否则将会导出错误的结论。但可以通过 对基因组中的单个基因或基因块作反转( r e v e r s a l ) 、易位( t m n s l o c a t i o n ) 、复制 ( d u p l i c a t i o n ) 、调换( t r a n s p o s i t i o n ) 等操作，将一个基因组转换到另一个基因组，上述这 种以基因为单位的操作称为基因组重排2 】1 1 3 】( g e n o m er e a r r a n g e m e n t ) 。 1 2 反转排序的基础知识 将一条染色体中的一段连续基因子序列的顺序反转，称为一次反转( r e v e r s a l ) 操作。 比较不同物种的全基因组时，需要计算物种闻的进化“距离”。例如在研究叶绿体和线 粒体基因组时，仅有的一种重排事件即反转，几乎是影响基因组进化的唯一方式。在这 种情况下，用把一个基因组转换为另一个基因组所需的反转操作的数量度量两个基因组 间进化距离是有道理的。对基因组重排的研究主要集中在解决一个组合“难题”寻 找一系列使某一基因组转化为另一基因组的重排方案。就最简单的形式而言，将一种基 因组转化为另一种基因组的重排可以用寻找最小转换次数的组合问题来模拟。 1 2 1 反转排序的相关概念 ( 1 ) 设g = ( g l 9 2 ，g n ) 是由n 个基因g l ，9 2 ，g n 组成的基因集合。为简单起见。用 数字k 来标记基因g k ( k = l ，2 ，n ) ，并记g = ( g l ，9 2 ，g 。) - - ( 1 ，2 ，n ) 。这样，一个基因 的有序列g = g l ，9 2 ，”j 舀1 ) 就可用 1 ，2 ，n 的个排列耳= ( 耳l ，“2 ，“jn 。) 来表示。从丽 将一个基因组重排的反转排序问题转化为一个排列的反转排序( s o r t i n gb yr e v e r s a l s ) 问 题【1 6 1 1 7 1 。 4 ( 2 ) 给定 1 ，2 ，n 的两个( 无向或有向) 排列，1 3 ，求一个反转序列p lp2 - p 。， 使得apipr pt _ b 且t 的值为最小的问题，称为基于反转的基因组重排问题( 简称反转 排序) ，称数t 为口关于b 的反转距离( r e v e r s a ld i s t a n c e ) ，记为d 。( b ) 。设q 和b 是 1 ，2 ， “j 1 3 的两个不同的( 无向或有向) 排列，p l p2 - p 。是一个反转序列。注意到，由ap i p2 pt 可以得到1 3d apip2 p t 爿( 或i ) ，这里0 。为b 的逆排列。若记；b4a ，则q 关于8 的反转距离d 。( 1 3 ) 等于关于恒等排列i 的反转距离d ，( i ) ，简记为r d ( 兀) ( 或 s r d ( ) ) 。因此，以下只考虑 l ，2 ，n ) 的任一个排列关于i 的反转距离问题而不失一 般性。 ( 3 ) 为了便于讨论，在排列= ( l ，“2 ，丌i i ) 的两端插入两个特定的元素丑o = o 和 耳l = n + 1 ，而得到排列( “o ，“l ，“2 ，n ，1 ) ，称其为n ( n ) 的延拓排列。 ( 4 ) 给定 l ，2 ，n 1 的一个排列= ( “l ，2 ，nn ) ，如果排列中的每个元索都有“十” 或“- ”标号，标记染色体中基因的方向，称为有向排列；如果排列中的元素没有标号， 称为无向排列。排列i = ( + l ，+ 2 ，+ n ) 称为有向的恒等排列；而排列i - ( 1 ，2 ，n ) 称为无 向的恒等排列。 ( 5 ) 无向排列的反转基因组重排问题是n p 难题，而有向排列的反转基因组重排问 题是多项式时间可解的。下面构造一种方法把无向排列转化为有向排列。在无向排列的 每一个元素上加上正号或负号。例如：无向排列= ( 2 ，1 ) ，那么生成有向排列集为 s i g n ( n ) = ( 一2 一1 ) ，( - 2 + 1 ) ，( + 2 - 1 ) ，( + 2 + 1 ) ) 这样对于含有n 个元素的无向排列丌= ( n l ，“2 ，。) ，可以生成含有2 n 个有向排列集s i g n ( 丌) ，其中每个有向排列含有n 个元 素。称无向排列n 中每个不含断点的子列为一个“条”( s t r i p ) 。若一个条中的元素值是 依次递增( 减) 的，则称其为上升( 下降) 条。只含一个元素的条，既称为上升条，也 称为下降条。 1 2 2 反转排序的相关定理 设丌。s i g n ( 丌) ，如果s r d ( ) = r a i n s r d ( ) ，s i g n ( ) ) ，则称a + 是s i g n ( ) 中具有最小反转距离的有向排列( 简称最小距离排列) ，或称最优排列。 无向排列与有向排列之间有如下结论： 定理l ：设丌= ( “i t “2 。，。) 是一个无向排列，则对于s i g n ( n ) 中的每一个有向 排列n = ( n l 玎4 2 ，。) ，n 。的反转序列也是n 的反转序列。 定理2 ：假设是无向排列，则必定存在有向排列n s i g n ( 丌) ，使得s r d ( 耳。) = r d ( 丌、。 定理l 和定理2 的证明见文献【l o 】。这两个定理保证了在s i g n ( ) 里至少存在一个最 小距离排列，它的反转序列是n 的最优反转序列。因此，求解无向排列的反转排序问题 可以转化为求解有向排列集s i g n ( ) 中的具有最小距离排序问题。 第二章免疫遗传算法基础 2 1 遗传算法的基本原理 生物的进化是一个奇妙的优化过程，它通过选择淘汰、变异、基因遗传等规律产生 适应环境变化的优良物种。遗传算法是根据生物进化思想启发而得出的一种全局优化算 法。它创立有两个目的：一是抽象和严谨地解释自然界的适应过程；二是为了将自然生 物系统的重要机理运用到工程系统中。遗传算法在计算机上模拟生物进化过程和基因操 作，通过目标函数来计算适配值，具有全局寻优的能力，能解决高度复杂的问题。 2 1 1 遗传算法的发展 在2 0 世纪5 0 年代和6 0 年代，随着人们在人工智能领域研究的深入，一些科学家 对自然进化的许多优良特性产生了极大兴趣，他们开始研究用模仿生物和人类进化的方 法来求解复杂的优化问题。早期的研究形成了遗传算法的雏形，如大多数系统都遵循“适 者生存”的仿自然法则，有些系统采用了基于种群的设计方案，并且加入了自然选择和 变异操作，但由于缺乏一种通用的编码方案，早期的算法收效甚微。 2 0 世纪6 0 年代中期，美国m i c h i g a n 大学的j o h nh o l l a n d 碍】在前人研究的基础上提 出了位串编码技术，这种编码即适用于变异操作，又适用于交叉操作，并且强调交叉作 为主要的遗传操作。随后，h o l l a n d 将该算法用于自然和人工系统的自适应行为的研究 中，并于1 9 7 5 年出版了其开创性著作”a d a p t a t i o ni nn a t u r a la n da r t i f i c i a ls y s t e m s ”。以后， h o l l a n d 等人将该算法加以推广，应用到优化及机器学习等问题中，并正式定名为遗传 算法( g e n e t i c a l g o r i t h m - g a ) 。遗传算法的通用编码技术和简单有效的遗传操作为其广泛 的应用奠定了基础。 2 0 世纪8 0 年代以来是遗传算法和进化计算的蓬勃发展期。从1 9 8 5 起，国际上开始 举行遗传算法的国际会议，以后则更名为进化计算的国际会议。1 9 9 7 年5 月，i e e e 出 版了进化计算的新杂志”t r a n s a c t i o ne v o l u t i o n a r yc o m p u t a t i o n ”。遗传算法由于求解的有 效性、现有仿真环境下易于实现、可扩充性和易于与其它方法相结合等优点，在机器学 习、过程控制、计算机科学、经济预测、工程优化等领域都得到了越来越多的研究和应 用。 6 2 1 2 遗传算法的基本概念及思想 由于遗传算法【1 9 】幽1 是由进化论和遗传学机理产生的直接搜索优化方法，故而在这 个算法中要用至0 各种进化和遗传学的概念。 其中主要概念如下： 位串( b “s t r i n g ) ：个体的表现形式。对应于遗传学中的染色体( c h r o m o s o m e ) 遗传物 质的主要载体，由多个遗传因子基因组成，在算法中为二进制。 基因( g e n e ) ：位串中的元素，表示不同的特征。对应于生物学中的基本遗传单位， 以d n a 序列形式把遗传信息译成编码。 基因型( g e n o t y p e ) ：基因组合的模型，是染色体性状的内部表现。 表现型( p h e n o t y p e ) ：染色体性状的外部表现，是根据基因形成的个体。对应于g a 中的位串解码后的参数。 基因座( 1 j 0 c a s ) ：遗传基因在染色体中所占有的位置。 位串结构空间( b i ts t r i n g ss p a c e ) ：等位基因任意组合构成的位串集合，基因操作在 位串结构空间进行，对应于遗传学中的基因型的集合。 参数空间( p a r a m e t e r ss p a c e ) ：位串空间在物理系统中的映射。对应于遗传学中的表 现性的集合。 个体( i n d i v i d u a l ) ：染色体带有特征的实体，它是g a 所处理的对象和结构。 种群( p o p u l a t i o n ) ：个体的集合称为种群。 进化( e v o l u t i o n ) ：生物在其延续生命的过程中，逐渐适应环境，使其品质不断得到 改善的生命现象。 适应度( f i t n e s s ) ：个体对环境的适应程度。 选择( s e l e c t i o n ) ：以一定概率从种群中选若干个体的操作。 复制( r e p r o d u c t i o n ) ：新细胞继承旧细胞中某些性状的过程。 交叉( c r o s s o v e r ) ：基因重组过程。 变异( m u t a t i o n ) ：细胞复制中产生新个体的现象。 逆转或到位( i n v e r s i o n ) ：反转位串上的一段基因的排列顺序。 遗传( h e r e d i t y ) ：父代通过有性方式向子代个体的特征传递过程。 解码( d e c o d i n g ) ：从基因型到表现型的映射。 遗传算法的一般流程如图2 1 所示： 7 图2 1 遗传算法的一般流程图 遗传算法把问题的解表示成“染色体”，在算法中也就是二进制编码的串。在执行 遗传算法之前，给出一群“染色体”( 初始种群) ，也就是假设解。然后，把这些假设解 置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进 行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一 代的进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。很 明显，遗传算法是一种最优化方法，它通过进化和遗传机理，从给出的原始解群中，不 断进化产生新的解，最后收敛到一个特定的串，即求出最优解。 遗传算法的一般求解步骤是： ( 1 ) 初始化 随机产生初始种群，个体数耳一定，每个个体表示为染色体的基因编码。 ( 2 ) 计算适应度 按照一定的适应度函数计算个体的适应度。遗传算法在进化搜索的过程中基本不利 用外部信息，仅以适应度函数为依据，利用种群中每个个体的适应度值来进行搜索。因 此，适应度函数的选择至关重要，直接影响到算法的收敛速度以及能否找到最优解。适 应度函数在设计的过程中一般要满足以下条件： a ) 单值、连续、非负、最大化； b ) 合理、一致性，适应度函数值应该能够反应对应解的优劣程度； c ) 计算量小，适应度函数设计时尽可能简单，可以减少计算的时间和空间复杂度； d ) 通用性强，适应度函数对某类具体问题，应尽可能通用。 ( 3 ) 选择 选择是用来确定重组或交叉个体，以及被选个体将产生多少个子代个体。根据适者 矗 生存原则选择下一代的个体。在选择时，以适应度为选择原则。适应度较高的个体放选 中的概率高，适应度较小的个体被选中的概率低，甚至被淘汰。适应度准则体现了适者 生存，不适应者淘汰的自然法则。 常用的选挥算法有；轮盘赌选择( r o u l e t t ew h e c ls e l e c t i o n ) ，随机遍历抽样 ( s t o c h a s t i cu n i v e r s a ls a m p l i n g ) ，局部选择( l o c a ls e l e c t i o n ) ，截断选择( t r u n c a t i o n s e l e c t i o n ) ，锦标赛选择( t o u r n a m e n ts e l e c t i o n ) 等算法。 ( 4 ) 交叉 对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率 p 。在选中的位置进行交换。这个过程反映了随机信息交换，目的在于产生新的基因组合， 即产生新的个体。例如有个体s 1 = 1 0 0 1 0 1 ，s 2 = 0 1 0 1 1 1 选择它们的左边3 位进行交叉操 作，则有s j = 0 1 0 1 1 1 ，$ 2 = 1 0 0 1 0 1 一般而言，交叉概率p 。取值为o 2 5 - 0 7 5 。 ( 5 ) 变异 根据生物遗传中基因变异的原理，以变异概率p 。对某些个体的某些位进行变异。 在变异时，对进行变异的串的对应位求反，即把1 变为0 ，把0 交为l 。变异概率碥与 生物变异极少的情况一致，所以，p 。的取值较小，一般取o 0 1 0 2 。例如有个s = 1 0 1 0 1 l 。 对其的第l ，4 位置的基因进行变异，则有s = 0 0 1 1 1 1 只靠变异不能在求解中得到好处。 但是，它能保证算法过程中不会产生无法进化的单一群体。因为当所有的个体一样时， 交叉是无法产生新的个体的，这时只能靠变异产生新的个体。 ( 6 ) 全局最优收敛 当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上 升时，则算法的迭代过程收敛，输出最佳个体及其代表的最优解，计算结束。否则，用 经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到第2 步继续循 环执行。 2 。1 3 基本遗传算法的描述及算法实现 基本遗传算法( s i m p l eg e n e t i ca l g o r i t h m s 简称s g a ) 是比较简单的抽象模型。个体 用固定长度的串表示，群体大小也是固定的。按概率选择群体中的个体来生成下一代个 体，选择的概率正比于个体适应度大小，通过交叉和变异产生新个体。 描述： 基本遗传算法可定义为一个八元组s g a = ( c ，e ，p o ，m ，巾，r ，v ，t ) 式中： c 一个体的编码方案； e 一个体适应度评价函数； p 旷初始群体； m 一群体大小； 耷一选择算子； r 一交叉算予； 9 1 1 一变异算子； t - 遗传运算终止条件； 算法实现： p r o c e d u r es g a b e g i n i n i t i a l i z ep ( o ) ； t = o ： w h i l e ( t ； ( 2 ) 生成宿主运用程序 生成可远程处理的类型主题中定义的r e m o t a b l e t y p e 类本身并不特殊。若要使其 它应用程序域中的对象能够在远程创建该对象的实例，必须生成宿主或侦听器应用程 序，以完成以下两项任务： 选择并注册一个信道，该信道是处理网络协议和序列化格式的对象。 将类型注册到n e t 远程处理系统，使它可以使用信道来侦听对类型的请求。 2 0 n e tf r a m e w o r k 包括两个默认的信道：h t t p c h a n n e l ( 它使用s o a p 格式化) 和 t c p c h a n n e l ( 它使用二进制格式化) 由于远程配置是基于每个应用程序域进行的，因此应用程序域必须处于运行状态才 能侦听请求。配置可以通过编程方式( 或者使用应用程序或计算机配置文件) 来进行。 以下代码实现一个简单的r e m o l a b | e t y p e 宿主应用程序域，该域使用一个配置文件( 利 用配置文件，可以更改远程处理配置，而无须重新编译可执行文件。) s y s t e m ：r u n t i m e ：r e m o t i n g ：r e m o t i n g c o n f i g u r a t i o n ：c o n f i g u r e s ”l i s t e n e r e x e c o n f i g ”) ； s e r v e r 类别必须能够找到s e r v e r e x e c o n f i g 文件，以加载r c m o t a b l c t y p e 类的配 置。该配置文件应该与s e r v e r e x e 保存在同一个目录中，否则将找不到该配置文件并且 会引发异常。以下代码显示此侦听或宿主应用程序域的s e r v e r e ) 【e c o n f i g 配置文件。 e h a r m e ! r e f = - ”t e p ”p o r t = ”8 6 8 6 压 远程处理系统使用该文件中的信息来侦听远程请求，并且将远程请求路由到可远程 处理类型的实例。该文件指定s i n g l e t o n 服务器激活模式、为其侦听的类型臼勺类型名称 和程序集，以及对象的统一资源标识符( u r i ) 或外部名称。该文件还指示远程处理系统 使用系统提供的t e p c h a n n e l 来侦听端1 28 6 8 6 上的请求。 ( 3 ) 生成客户端运用程序 在生成可远程处理的类型时定义了一个远程类型，在生成宿主应用程序时创建了一 个应用程序，现在需要生成该远程类型的客户端，并且要由该应用程序来承载；为此， 应用程序必须将其自身注册为该远程对象的客户端，然后就像该对象位于客户端的应用 程序域中一样调用它。n e t 远程处理系统将截获客户端调用，将其转发到远程对象， 并将结果返回到客户端。以下代码为如何生成简单的远程处理客户端。 r e m o t i n g c o n f i g u r a t i o n ：c o n f i g u r ec c l i e n t e x e c o n f i g ”) ； 2 l c l i e n t 类必须能够找到c l i e n t e x e c o r i n g 文件，以加载r e m o t a b l e t y p e 类的配置。 该文件应该与c l i e n t e x e 文件保存在同一个目录中，否则将找不到该配置文件并且会引 发异常。以下代码为此侦听或宿主应用程序域的c l i e n t e x e c o n f i g 配置文件。 w e l l k n o w n t y p e 5 ”r e m o t a b l e t y p e r e m o t a b l e t y p e ” 该文件使远程处理系统知道可以在r e m o t a b l e t y p e 程序集中找到r e m o t a b l e t y p e 远程对象的类型信息。 3 2 4 n e t 远程处理其它相关知识 ( 1 ) 使对象可远程处理：通过n e t 远程处理基础结构，可以跨越应用程序域和上 下文边界引用对象。 ( 2 ) 对象激活和生存期：通常不需要注意对象的确切创建时间；只需要对象在调用 它上面的方法时作出响应。在使对象对于客户端可用之前，远程处理系统需要知道需要 哪种类型的激活。 ( 3 ) 信道：信道是跨远程处理边界( 无论是在应用程序域、进程还是计算机之间) 在应用程序之间传输消息的对象。 信道必须实现i c h a n n e l 接口，该接口提供如c h a n n e l n a m e 和c h a n n e l p r i o r i t y 的信 息性属性。专用于在特定端口上侦听特定协议的信道实现i c h a n n e l r e e e i v e r ，而专用于 发送信息的信道实现i c h a n n e l s e n d e r 。t e p c h a n n e l 和h t t p c h a n n e l 对象都实现这两种接 口，因此它们可用于发送或接收信息。 如果正在发布可远程处理的对象，则在注册服务器对象之前调用： c h a n n e l s e r v i e e s r e g i s t e r c h a n n e l 如果正在使用可远程处理的对象的功能。则在创建服务器对象的实例之前调用： c h a r m e l s e r v i e e s r e g i s t e r c h a n n e l 。 信道还可以从远程处理配置文件加载。 ( 4 ) 信道规则：当客户端调用远程对象上的方法时，参数以及其它与调用相关的详 细信息将通过信道传输到远程对象。调用的任何结果均以相同的方式返回。客户端可以 选择在服务器上注册的任何信道与远程对象通信，这样就能够自由地选择最符合需要的 信道，也可以自定义任何现有信道或者生成使用不同通信协议的新信道。信道选择需要 遵循以下规则： 在可以调用远程对象之前，服务器上的远程处理系统必须注册了至少一个信道。必 须在注册对象之前注册信道。如果客户端上没有注册信道，则远程处理系统将选择或创 建一个以发送出站调用。 信道基于每个应用程序域进行注册。单个进程可以包含多个应用程序域。当进程结 束时，它注册的所有信道都自动销毁。 信道名称在应用程序域中必须是唯一的。 不能多次注册在特定端口上侦听的信道。 如果不能确定是否有可用的端口，那么在配置信道的端口时请使用0 ( 零) ，远程处 理系统将选择一个可用豹端口。 客户端可以使用任何已注册的信道与远程对象进行通信。当客户端尝试连接到远程 对象时，远程处理系统将确保该远程对象被连接到正确的信道。客户端负责在尝试与远 程对象通信之前调用c h a n n e l s e r v i c e s r e g i s t e r c h a n n e l 。如果客户端需要回调函数，则必 须注册信道和端口。 ( 5 ) 配置：为了远程处理能正常工作，n e t 远程处理基础结构需要某些特定的信 息。配置可远程处理的类型的方法有两种：可以在服务器和客户端代码中直接调用配置 方法，或者可以创建远程处理配置节，然后将其包含到应用程序的配置文件中。 若要使类型成为可远程处理的，必须向远程处理系统提供下列信息： 类型所需的激活类型： 描述类型的完整的元数据： 注册类型请求进行处理的信道： 唯一标识该类型的对象的u r l ； 客户端和服务器远程处理基础结构都必须了解这些信息，才能为远程服务器对象创 建代理并将方法调用到远程服务器对象。客户端也可能具有可用于它们的特别配置。如 果客户端应用程序请求客户端激活的对象，该客户端可以请求延长与该实例相关联的生 存期。如果客户端需要某种回调，客户端本身必须主动地注册信道以侦听该回调。 3 3 n e t 线程处理部分 操作系统使用进程将它们正在执行的不同应用程序分开。线程是操作系统分配处理 器时间的基本单元，进程中可以有多个线程同时执行代码。每个线程都维护异常处理程 序、调度优先级和一组系统用于在调度该线程前保存线程上下文的结构。线程上下文包 括使线程