（信号与信息处理专业论文）进化状态可控型遗传算法在学校课程表编排中的应用.pdf

摘要 遗传算法( g e n e t i ca l g o r i t h m s ，简称g a ) 是一种新发展起来的优化算法，它 是模拟自然界生物优胜劣汰进化过程的一种全局优化搜索算法。遗传算法可以利 用简单的编码技术和繁殖机制来表现复杂的现象，从而解决非常困难的问题，特 别是它的操作只面向编码串，与解空间的数学函数无关，使得遗传算法尤其适合 常规方法无法解决的、高度复杂的问题。目前遗传算法已被广泛应用于许多实际 问题，已成为人们用来解决高度复杂问题的一种新思路和新方法。 排课问题是一种非常复杂的问题，其目的是在教师、班级、学校硬件资源、 上课时间等多种因素条件限制下，找出尽可能的最佳方案。其排列组合的特性， 造成了其解的复杂性。 本文首先介绍了排课过程中要遵循的原则和注意的一些问题，然后介绍了遗 传算法的生物学方面的一些概念、基本思想、基本操作方法及相比其它算法的优 点特点，简述了遗传算法的数学基础理论，并对适应度函数进行了研究和总结了 各国学者针对遗传算法存在的问题进行了许多改进的方法，提出了进化状态可控 遗算法具有智能功能的方法。 最后以某学校的排课问题作为研究对象，引入遗传算法和进化状态可控型遗 传算法，通过计算机模拟的结果验证了可控型遗传算法的有效性和进行排课的可 行性。 关键词：遗传算法遗传操作排课多样度进化状态 a b s t r a c t g e n e t i c a l g o r i t h m s i san e w l y d e v e l o p e df u l l s c a l e o p t i m i z e ds e a r c h i n g a l g o r i t h m s ，w h i c hs i m u l a t e st h en a t u r e se v o l u t i o np r o c e s sw h i c hg o e so nt h e p r i n c i p l eo f “p r e s e r v i n gt h es u p e r i o ra n de l i m i n a t i n gt h ei n f e d o r g ac a nu t i l i z et h e s i m p l i f i e d c o d e t e c h n o l o g y a n dp r e v e n t i v e s y s t e m t oi l l u s t r a t e c o m p l i c a t e d p h e n o m e n a ，t h e r e f o r es o l v er a t h e rd i f f i c u l tp r o b l e m s m o s ti m p o r t a n t l y , i t so p e r a t i o n i so n l ya c c e s s i b l et ot h ec o d e c l u s t e r , i r r e l e v a n tt ot h em a t h e m a t i c a lf u n c t i o nf o r s p a c e s o ，g af i t si ne s p e c i a l l yw e l lw i t ht h o s eh i g l l l yc o m p l i c a t e dp r o b l e m si n e x t r i c a b l et o r e g u l a rm e t h o d s a tp r e s e n tg ah a sg o taw i d ea p p l i c a t i o ni n t om a n yp r a c t i c e s ， b e c o m i n gan e wm e t h o d o l o g yt oe x t r e m e l y - c o m p l i c a t e dp r o b l e m s t h el a y - o u to fac u r r i c u l u ms c h e d u l ei sa v e r yc o m p l i c a t e dp r o b l e m ，w i t ht h e p u r p o s eo ff i n d i n gt h eo p t i m i z e ds c h e m ep o s s i b l eu n d e rt h er e s t r i c t i o n so ft h e e l e m e n t sl i k e t e a c h e r s ，c l a s s e s ，t h eh a r d w a r eo f - t h es c h o o la n dt h et i m ee t c ，n l e f e a t u r eo ft h ep e r m u t a t i o na n dc o m b i n a t i o nc o n t r i b u t e st ot h ec o m p l i c a t i o no ft h e s o l u t i o n t h i sa r t i c l ef i r s ti n t r o d u c e st h ep r i n c i p l e st ob e k e p tt oa n dt h en o t i c e a b l e p r o b l e m si nt h ep r o c e s so fl a y i n go u tac u r r i c u l u ms c h e d u l e t h e ni tc o m e st os o m e c o n c e p t s ，b a s i ci d e a s ，b a s i co p e r a t i v em e t h o d sa sw e l la st h ec o m p a r a t i v ea d v a n t a g e s a n df e a t u r e so fg ai nt h ef i e l do fb i o l o g y w i t hab r i e fd e s c r i p t i o no fg a sb a s i c m a t h e m a t i c a lt h e o r i e s ，i tg i v e ss t u d yo nt h em o d e r a t ef u n c t i o na n ds u m m a r i z e sm a n y m e t h o d sp u tf o r w a r db ys c h o l a r sf r o md i f f e r e n tc o u n t r i e sf o ri m p r o v e m e n ta c c o r d i n g t ot h ep r o b l e m si ng a , am e t h o db yw h i c ht h ee v o l u t i o ns t a t ei sc o n t r o l l a b l ea n dt h e g e n e t i cw o r kp r o v i d e ss m a r tf u n c t i o n si sp u tf o r w a r d a st h er e s e a r c h i n go b j e c t ，t h el a y o u to fac u r r i c u l u ms c h e d u l ee l i c i t sg a a n dt h e e v o l u t i o ns t a t ei sc o n t r o l l a b l eg e n e t i c a l g o r i t h m s t h ee f f e c t i v e n e s so ft h e c o n t r o l l a b l ea l g o r i t h ma n df e a s i b l et ol a yo u tac u r r i c u l u ms c h e d u l eh a sa l s ob e e n p r o v e nb yc o m p u t e rs i m u l a t i o n k e y 。w o r d s ：g e n e t i ca l g o r i t h m s g e n e t i cw o r k d i v e r s i t y e v o l u t i o ns t a t e t h el a y - o u to fac u r r i c u l u ms c h e d u l e 声明尸明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取 得的成果，撰写成博士硕士学位论文竺进化丛态亘撞型速佳簋洼查 堂撞迟猩塞缠扫 虫的廑旦= = 。除论文中已经注明引用的内容外，对论 文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。 本论文中不包含任何未加明确注明的其他个人或集体已经公开发表 或未公开发表的成果。 本声明的法律责任由本人承担。 学位论文作者签名：帐 2 0 0 4 年7 月3 0 日 同济大学硕士学位论文 第一章绪论 1 1 课程和课程表概述1 教育活动是一种人类有目的的、有计划、有组织的社会实践活动，所以事前教 育活动是一种人类有目的的、有计划、有组织的社会实践活动，所以事前应有一个 规划或设想方案，才能体现出教育活动的目的性、计划性和系统性，课程实质上是 一种育人活动的规划方案。 课程是一种培养人的总体设计方案，它是教育机构为了实现教育目的和培养目 标而要实施的一切活动及其安排的总体规划，其表现形式主要是根据各种客观要求 而制作的一系列方案和文件。 课程是确定教育活动及其内容的选择方案，课程是规定教育活动内容的组织安 排的方案，课程是人为因素较大的教育活动的方案，课程是可以操作的一系列方案。 由此可见，课程就其实质而言，是一种主要由课程观、课程目标、课程内容和课程 结构所组成的培养人的总体设计方案；就其形式而言，它是教育机构赖以顺利开展 教育活动的一系列方案的文件。 课程是一个由多领域、多元素所组成的复杂系统，它有特定的组成部分，有一 定的结构，进行着独特的活动，发挥着特殊的功能。 课程同教学一样是教育活动的重要手段与途径。 课程表是学校学年( 学期) 教学计划的具体体现，是学校实施素质教育、完成 教育教学任务的保证。作为教学管理过程中的环节爿 课，是重要的、复杂的、 讲究的和很有学问的；是直接关系到全校师生教学双边活动开展得好与坏的关键； 整个过程中蕴藏着教育学与心理学知识，同时又包含了理论联系实际等哲学原理； 并且是时间紧，任务重，过程较为繁琐。因此，科学编排课表，充分发挥其应有的 功能，就显得尤为重要。 同济大学硕士学位论文 1 2 排课的现状 在学校的教务管理工作中，课程表的编排是一项十分复杂、棘手的工作。在排 课过程中，除了满足大量的制约条件以外，还必须解决许多冲突与矛盾，例如：两 位教师不能同一时间在同一班级上课、一位教师不能在同一时间上两门课等等。传 统的排课方法，是用手工来完成的，在整个过程中，需要不断地检查修改，直到课 表完成，这期间所耗的人力和时间，是难以估算的。据不完全统计，松江区内的所 有学校，目前的课程表的编排工作都是由人工来完成。 随着科技的发展和计算机技术的进步，人们开始尝试着用计算机的强大计算和 处理功能来进行课表编排工作，既提高了排课工作的科学性，又可大大减轻管理人 员的工作强度，提高工作效率，从而使学校教务管理现代化迈上了一个新台阶。 。 但大家也知道，要想进行计算机处理，则需要编制程序，先要把排课的算法编 写出来。只有在一个好的完整的算法基础上，才能编制程序。但实际上，排课问题 也是世上的一个难题，因为在排课的过程，所要涉及的各种要求、限制条件非常多， 要想构造一通用很好的算法很难。而且不同的学校对排课的要求也不尽相同，所以 排课程序的适用范围也有一定的局限性。 现在虽然有很多的排课软件，但通用的却没有，虽然每个软件都自称该软件能 达到很好的效果，但实际情况并不理想，因此现在绝大多的学校，仍然愿意进行人 工操作，主要原因还是因为那些所谓的排课软件，理论上还行，但实际使用中，并 不怎样，有的时候，反而越排越乱。 就本人曾用过的两个排课软件，稍作比较。 、排课大师 第一步输入课时安排数据：( 包括任课教师输入、任课班名输入、上课场地输入、 课时安排综合输入) ； 第二步运行排课生成课表； 第三步手动调整已排的课表： 当运行了第二步中的排课程序生成了课表后，您必须对计算机已经排好的课表 进行手动的调整某些课。因为计算机不是万能的机器，它对输入的课时安排数据没 2 同济大学硕士学位论文 理解透彻，而排出了某些不符合要求的课。自动排课完成率在9 6 左右，还有部分 课不能排入，必须用手动调整。 在排课大师这个软件中，仅仅考虑了教师不能上课时间，学生连堂课上课形式， 教师连堂课形式这三个限制条件。该软件所能考虑的排课因素太少，排出的课表有 时根本不能使用。 、洪仔排课专家 它是一款功能比较强大、排课效率、排课质量较好的排课软件。 它可设置某教师、场地、课程、班级优先排课，可预先安排课程，可设置课程 为尽量早些或尽量晚些，可进行文理兼排。可限制教师每天上午、下午、整天最多 上多少节课等。该软件在对实验室、操场等教学资源处理不够好，对有些要求隔一 天或两的课程不能处理。 上述两个现在使用率比较高的软件，也仅仅列出了通常j 隋况下，课表编排中要 注意的一些问题，在实际排课中，要考虑的因素可能有很多很多。 在通常的排课中，一般的方法都是采用枚举法，列出搜索空间，然后在这空间 中用搜索的方法去找能够排的课程，一开始时，比较容易搜索，随着问题的深入， 可供搜索空间的缩小，往往到一定程度，所剩下的就无法继续处理，得不到最优解 或者近似最优解。 我们学校现在的排课是由人工实现，我们现在学校有高职和中专两种不同类型 的班级八十多个班级，排课的工作量可想而知，对社会上的一些排课软件，使用下 来也不够理想，故学校领导希望我们计算机系能够开发一个适合我们学校的排课系 统，我现正在做遗传算法方面的研究课题，我想尝试利用遗传算法来解决排课问题。 1 3 在排课过程中要遵循几个原贝, , j t 4 j 。 1 、课时计划与实际情况相结合的原则 国家公布的课时计划，是在全国的教育教学实践中总结出来的，是经过教育专 家们反复论证过的，并以教育行政手段的形式下达到各学校，具有较强的政策性和 3 同济大学硕士学位论文 权威性；是否严格执行课时计划，是衡量一所学校是否贯彻党和国家教育方针的重 要标志。 当然，课时计划本身已经给予了学校一定的自主空间，任意选修课就是让学校 根据实际情况进行适当调整，可向基础学科、薄弱学科和学习难度较大的学科倾斜。 2 、优先原则 依据教育心理学原理，基础学科或较难学的学科，应安排在学习的最佳时间，如 每周的周二、三、四，每天的上午第一、二、三节课，根据学校的场地情况和教师 情况，应遵循以下优先原则： a 、语、数、外学科优先； b 、体育学科优先； c 、上课班级多或者周课时量多的教师优先； d 、跨年级的教师优先； e 、限制排课较多的教师优先。 3 、限 | ；0 爿 课原则 根据学校实际情况，相同类别的教师需要进行教研、学习和开会等活动，排课 过程中应该充分考虑到相同类别的教师在相同的某一时段进行限制排课。 同时还要考虑学校现有的教学资源，如体育场、计算机房、实验室等，不能超 过这些资源的承爱能力。 4 、体现“以人为本”的原则 全体教师在教学活动中，应团结、协作和谦让，体现“以人为本”的指导思想， 尽可能地考虑学生的发展和教师本人的利益，创造一个和谐的工作环境。 a 、担任多个班级的教师，应注意上课的周期性；在同一周期内，应注意各班 教学的先后应交替安排；文、理科的课应交替安排；较难的与较易的学科应交替安 排。 b 、同一学科中新老教师的课应不在同一节课中安排，便于他们学习与指导，如 果教师外出参加活动，便于安排代课。 c 、对家住校外的教师、身体健康状况不良的教师们和家庭需要照顾的教师，安 排课程时应尽可能地给予考虑。 4 同济大学硕士学位论文 总之，安排课程中，考虑的因素越多，运筹起来就越复杂，安排的难度就越大； 对安排课程的具体实施人员的要求就越高。因此，尽管在安排课程中做了充分的考 虑，课程表一旦安排确定之后，肯定还有这样那样不尽人意的地方，这就需要得到 老师们的理解、支持、宽宏和谅解。 1 4 编排课表应注意的几个问题【4 】。 1 、文理合理搭配科学研究表明，人的大脑表层的不同区域承担着不同的功能， 左半球语言、逻辑思维和计算功能占优势，右半球空间知觉与情绪活动占优势。要 使大脑皮层种种神经中枢交替工作，不使某一种神经过于疲劳，最有效的办法就是 变换学习内容和方式。因此，我们在编排课表时一定要考虑这些因素，做到文理搭 配编排。如第二节排了数学，下节就应排语文或英语，第三节排物理或化学。文理 搭配不但体现在每一天，且应体现在一周当中。只有这样才能改变学生因学习内容 单一易产生疲劳的弊病，使学生乐学，并提高其学习效率。 2 、音体美课与其他课程合理搭配 音体美课是素质教育的重要组成部分， 这 类课除具有一定的知识性、能力性和审美性，还具有较强的蚁乐性和趣味性，相对 其他课而言，学生上这类课时大脑较为放松，大脑可以得到一定的休息和恢复。因 此，我们在编排课表时，要有计划地将它们搭配在一周中，并且编排在学生大脑容 易产生疲劳的时间。这样既利于学牛的学习，又利于他们身心健康发展。 3 、注意实验条件和活动场地等因素理化生劳和音美等课，有时要到实验室或 音美室去上课，而学校实验室和音美室的数量是有限的，因此我们在编排这类课时， 要充分考虑这些因素，既要避免课程安排冲突，又要发挥实验设施的应有功能，努 力完成实验教学。在编排体育课时，要考虑操场因素，因为操场所容纳的上课班级 数有限，体育器材有限，如何在有限的活动空间和有限的运动器材条件下，让所有 班级上好体育课，我们在编排课表时就应多动脑子，将体育课统筹安排。 4 、注意同年级同科教师课程的编排 同级同科教师为开展教研，相互学习，教 学经验较丰富的教师，应靠前排课，年轻教师或经验不够丰富的教师，应靠后排课。 5 同济大学硕士学位论文 这样既给了青年教师或经验欠丰富的教师一个学习的机会，使他们迅速提高教育教 学水平，又给了学生一个平等学习的权利，使教学质量均衡发展。 5 、同教案上课的先后顺序同教案几个平行班上课，其先后顺序应交互编排， 特别是语数外等科。因教师上甲班时有一个二次备课的过程，课后又有一个反思的 过程，教师在甲班根据上课时的情况，对某些教学内容会作适当调整，再上乙班时 使教法和学法更加科学，教学效果会更好。所以，同一教案上课先后顺序交互编排， 非常有利于各班学习成绩的整体提高。 6 、注意同班同科前后间隔时间有些科目每周2 节或3 节，编排这类课时要考 虑间隔时间。每周2 节的以隔2 天为宜，周3 节的间隔一天为宣。这样编排，学生 有了课后复习巩固和预习的时间，教师有了备课和作业处理的更充分的机会，有利 于教学质量的提高。 总之，排课是一个复杂过程，在这过程中，会出现各种各样的问题和情况，我 们在排课中，一定要多方面的考虑，这样才能使课表更加合理。 1 5 本文工作。， 本论文共分五章，主体结构安排如下： 第一章绪论。主要介绍了在排课的现状以及在排课中所要遵循的原则和注意的 问题。 第二章主要介绍遗传算法的基本知识，基本操作，遗传算法的特点j 适应度函 数，遗传算法的数学基础。 第三章主要介绍常规遗传算法存在的缺点，简要介绍了目前常用的针对常规型 遗传算法缺陷改进的几种方法，提出了进化状态可控型遗传算法。 第四章利用遗传算法对课表的编排进行模式建立。 第五章通过计算机模拟结果表明利用遗传算法编排课表的可行性和进化状态可 控型遗传算法的改进作用。 在最后结论部分，对本文工作进行总结，并提出进一步研究方向。 6 同济大学硕士学位论文 第二章遗传算法 2 1 生物进化理论和遗传学的基本知识旧3 生命的基本特征包括生长、繁殖、新陈代谢、遗传与变异。生命是进化的产物， 现代的生物是在长期进化过程中发展起来的。达尔文( 1 8 5 8 年) 用自然选择( n a t u r a l s e l e c t i o n ) 来解释物种的起源和生物的进化，其自然选择学说包括以下三个方面： ( 1 ) 遗传( h e r e d i t y ) 这是生物的普遍特征，“种瓜得瓜，种豆得豆”，亲代把生物信 息交给子代，子代按照所得信息而发育、分化，因而予代总是和亲代具有相同或相 似的性状。生物有了这个特征，物种才能稳定存在。 ( 2 ) 变异( v a r i a t i o n ) 亲代和子代之间以及子代的不同个体之间总有些差异，这种 现象称为变异，变异的选择和积累是生命多样性的根源。 ( 3 ) 生存斗争和适者生存自然选择来自繁殖过剩和生存斗争。由于弱肉强食的 生存斗争不断地进行，其结果是适者生存，具有适应性变异的个体被保留下来，不 具有适应性变异的子体被淘汰，通过一代代的生存环境的选择作用，物种变异被定 向着一个方向积累，于是性状逐渐和原先的祖先种不同，演变为新的物种。这种自 然选择过程是一个长期的、缓慢的、连续的过程。 达尔文的进化理论是生物学史上的一个重要里程碑，它解释了自然选择作用下 生物的渐变式进化。1 8 6 6 年孟德尔发表了“植物杂交实验 的论文，他提出的遗 传学的两个基本规律分离律和自由组合律，奠定了现代遗传学的基础。随着细 胞学的发展，染色体、减数分裂和受精过程相继被发现，w a t e rs s u t t o n 发现染色 体的行为与基因的遗传因子行为是平行的，因此提出遗传因子是位于染色体上的。 美国遗传学家摩尔根口h m o r g a m ) 进一步确立了染色体的遗传学说，认为遗传形 状是由基因决定的，染色体的变化必然在遗传形状上有所反映。生物的形状往往不 是简单地决定于单个基因，而是不同基因相互作用的结果，基因表达要求一定的环 境条件，同一基因型在不同的环境条件下可以产生不同的表现型。2 0 世纪2 0 年代 以来，随着遗传学的发展，一些科学家用统计生物学和种群遗传学的成就重新解释 7 同济大学硕士学位论文 达尔文的自然选择理论，他们通过精确地研究种群基因频率由一代到下一代的变化， 来阐述自然选择是如何起作用的。种群遗传学是以种群为单位而不是以个体为单位 的遗传学，是研究种群中基因的组成及其变化的生物学。在一定地域中，一个物种 的全体成员构成一个种群，种群的主要特征是种群内的雌雄个体能够通过有性生殖 实现基因的交流。生物的进化实际上是种群的进化，个体总是要消亡，但种群则是 继续保留，每一代个体基因型的改变会影响种群基因库的组成。而种群基因库组成 的变化就是这一种群的进化，没有所谓的生存斗争问题，单是个体繁殖机会的差异 也能造成后代遗传组成的改变，自然选择也能够进行。综合进化论对达尔文式的进 化给予了新的更加精确的解释。 遗传算法模拟的是怎样的生物进化模型呢? 假设对相当于自然界中的一群人的 一个种群进行操作，第一步的选择是以现实世界中的优胜劣汰现象为背景的；第二 步的重组交叉则相当于人类的结婚和生育；第三步的变异则与自然界中偶然发生的 变异是一致的。我们再仔细分析遗传算法的操作对象种群，实际上它对应的是一群 人而不是整个人类。一群人随着时问的推移而不断地进化，并具备越来越多的优良 品质。经过相当一段时间后，他们将逐渐进化到某些特征相对优势的状态，我们称 之为平衡态。当一个种群进化到这种状态，这种种群的特性就不再有很火的变化了。 一个简单的遗传算法，从初始代开始，并且各项参数都设定，也会达到平衡态。 既然遗传算法效法基于自然选择的生物进化，是一种模仿生物进化过程的随机 方法。下面先给出几个生物学的基本概念与术语，这对于理解遗传算法是非常重要 的。 染色体( c h r o m o s o m e ) 生物细胞中含有的一种微小的丝状化合物。它是遗传物 质的主要载体，由多个遗传因子一一基因组成。 遗传因子( g e n e ) d n a 或r n a 长链结构中占有一定位置的基本遗传单位，也 称为基因。 个体( i n d i v i d u a l ) 指染色体带有特征的实体。 种群( p o p u l a t i o n ) 染色体带有特征的个体的集合称为种群。该集合内个体数称 为群件的大小。 进化( e v o l u t i o n ) 生物在其延续生存的过程中，逐渐适应其生存环境，使得其品 8 同济大学硕士学位论疵 质不断得到改良，这种生命现象称为进化。生物的进化是以种群的形式进行的。 适应度( f i t n e s s ) 在研究自然界中生物的遗传和进化现象时，生物学家使用适应 度这个术语来度量某个物种对于生存环境的适应程度。对生存环境适应程度较高的 物种将获得更多繁殖机会，而对生存环境适应程度较低的物种，其繁殖机会就会相 对较少，甚至逐渐灭绝。 选择( s e l e c t i o n ) 指决定以一定的概率从种群中选择若干个体的操作。一般而 言，选择的过程是一种基于适应度的优胜劣汰的过程。 复$ 1 ( r e p r o d u e t i o n ) 细胞在分裂时，遗传物质d n a 通过复制而转移到新产生 的细胞中，新细胞就继承了旧细胞的基因。 交叉( c r o s s o v e r ) 有性生殖生物在繁殖下一代时两个同源染色体之间通过交叉 丽重组，在两个染色体的某一相同位置处d n a 被切断，其前后两串分别交叉组合 形成两个新的染色体。 变异( m u t a t i o n ) 在细胞进行复制时可能以很小的概率产生某些复制差错，从 而使d n a 发生某种变异，产生出新的染色体，这些新的染色体表现出新的性状。 编码( c o d i n g ) d n a 中遗传信息在一个长链上按一定的模式排列，也即进行了 遗传编码。遗传编码可以看作从表现型到遗传子型的映射。 解码( d e c o d i n g ) 从遗传子型到表现型的映射。 2 2 遗传算法的诞生背景吲幻 遗传算法( g e n e t i c a l g o r i t h m s ，g a ) 是一种新发展起来的优化算法，它产生于 美国的m i c h i g a n 大学。从6 0 年代起，m i c h i g a n 大学的j o h n h o l l a n d 和他的学生就 开始从事如何使机器具有学习功能的研究。他们注意到学习不仅可以通过单个生物 体的适应而且通过一个种群的许多代的进化适应也能发生。受达尔文的适者生存进 化理论的启发，认识到，在机器学习的研究中，为了获得一个好的学习算法仅靠单 个策略的建立和改进是不够的，还要依赖一个包含许多侯选策略的群体的繁殖。这 一研究想法起源于遗传进化，j o h n h o l l a n d 将这个研究领域称之为遗传算法。 9 同济大学硕士学位论文 j o h n h o l l a n d 教授在上世纪七十年代出版的“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 l s y s t e m s ”书通常被认为是遗传算法的经典之作。因为该书给出了遗传算法的基本 定理和理论证明。遗传算法可以利用简单的编码技术和繁殖机制来表现复杂的现象， 从而解决非常困难的问题，特别是它的操作仅仅面向编码串，与解空间的数学特性 无关，使得遗传算法尤其适合常规方法无法解决的、高度复杂的问题。目前遗传算 法已被广泛应用于许多实际问题，如函数优化、自动控制、图象识别、机器学习、 人工神经网络、分子生物学、优化高度等许多领域中的问题。遗传算法已成为人们 用来解决高度复杂问题的一个新思路和新方法。 h o l l a n d 教授创建的遗传算法是基于自然选择和基因遗传学原理的一种概率搜 索算法。它利用某种编码技术作用于称为染色体的编码串，其基本思想是模拟由这 些串组成的群体的进化过程。遗传算法通过有组织地但又是随机地信息交换来重新 结合那些适应性好的串，利用上一代串结构中适应性好的的位和段来生成一个新的 串的群体。类似于自然进化，遗传算法通过作用于染色体上的基因，寻找好的染色 体来求解问题，算法对求解的问题本身一无所知，它所需要的仅是对染色体进行评 价，并基于适应度值来选择染色体，使适应性好的染色体比适应性差的染色体有更 多的繁殖机会。新一代个体中包含着上一代个体的大量信息，新一代的个体不断在 总体特性上胜过旧的一代，从而使整个群体向前进化发展。 遗传算法采纳了自然进化模型，如选择、交叉、变异、迁移、局域与邻域等。 计算开始时，一定数目n 个个体( 父个体1 、父个体2 、父个体3 、父个体4 ) 即种群随机地初始化，第一代也即初始代就产生了，并计算每个个体的适应度函数。 如果不满足优化准则，开始产生新一代的计算。为了产生下一代，按照适应度选择 个体，对父代交叉而产生子代。所有的子代按一定概率变异。然后子代的适应度值 又重新计算，子代被插入到种群中将父代取而代之，构成新的一代( 子个体1 、子 个体2 、子个体3 、子个体4 ) 。这一过程循环执行，直到满足优化准则为止。 1 0 同济大学硕士学位论文 2 3 遗传算法的基本操作哺1 3 j 毛1 5 1 明 遗传算法计算的第一步是将预优化变量进行编码，目前编码方法有很多，一般 采用二进制编码方式，也可以用实数型编码。然后利用随机方式产生初始种群。 遗传算法包括三个基本算子。 1 、选择算子。 选择是用来确定重组或交叉个体，以及被选个体将产生多少个子代个体。选择 是从一个父种群中，根据计算适应度，选择适应度大的个体产生新种群，适应度大 的个体被选中的机会就多。具体可以挑选以下的算法：轮盘赌选择；随机遍历 抽样；局部选择；截断选择；锦标赛选择。 下面通过轮盘赌选择方法举例。 个体染色体适应度选择概率累积概率 10 0 0 11 0 0 0 0 080 0 8 6 9 5 70 0 8 6 9 5 7 20 1 0 1 1 1 1 0 0 1 5 0 0 5 4 3 4 80 1 4 1 3 0 4 3 0 0 0 0 0 0 0 1 0 120 0 2 1 7 3 90 1 6 3 0 4 3 4 1 0 0 1 1 1 0 1 0 0 1 0 0 1 0 8 6 9 6 0 2 7 1 7 3 9 51 0 1 0 1 0 1 0 1 070 0 7 5 0 8 70 3 4 7 8 2 6 61 1 1 0 0 1 0 1 1 01 20 1 3 0 4 3 50 4 7 8 2 6 1 7 1 0 0 1 0 1 1 0 1 1 50 0 5 4 3 4 80 5 3 2 6 0 9 81 1 0 0 0 0 0 0 0 11 90 2 0 6 5 2 20 7 3 91 3 0 91 0 0 1 1 1 0 1 0 01 0 0 1 0 8 6 9 60 8 4 7 8 2 6 1 00 0 0 1 0 1 0 0 1 11 4 。0 1 5 2 1 7 41 0 0 0 0 0 0 上表是假设已有的染色体和其适应度值用选择概率。如图2 1 所示，个体适应 度按比例转化为选中概率，将轮盘分成1 0 个扇区，进行1 0 次选择，相当转动轮盘 1 0 次，每次指针停止在某一扇区，扇区代表的个体即被中。 同济大学硕士学位论文 图2 1 轮盘赌选择 假设产生随机数序列为0 0 7 0 2 2 1 ，0 5 4 5 9 2 9 ，0 7 8 4 5 6 7 ，0 4 4 6 9 3 4 ，0 5 0 7 8 9 3 ， 0 2 9 1 1 9 8 ，0 7 1 6 3 4 5 ，0 2 7 2 9 0 1 ，0 3 7 1 4 3 5 ，0 8 5 4 6 4 1 ，将该随机序列与上表中的累 积概率比较，则依次序号为：1 ，8 ，9 ，6 ，7 ，5 ，8 ，4 ，6 ，1 0 个体被选中。显然 适应度高的个体被中的概率在，而且可能被选中，而适应度低的个体则可能被淘汰。 2 、交叉算子。 交叉是结合来自父代交配种群中的信息产生新的个体。一般是从交配池中随机 取出要交配的一对，并根据位串的长度，随机产生一交叉位置，进行交配后产生一 对新的位串。在二进制交叉中有单点交叉、多点交叉、均匀交叉等。 以单点交叉方法如图2 2 所示： 交叉游个绺 l 0 0 0lll ：0 0 i 【ll ： 1 0 0 i 1 0 0 ；l ；l f ) ( ) 3 、变异算子 弋 戋：义伍援 图2 2 单点交叉操作 交义艨个体 l 0 0 0lli il l o ) o ( ) ；lj 0 0o ( ) l ；l 1 2 同济大学硕士学位论文 变异是从种群中随机取出一个位串，并在位串的某个任意位置上执行信息转换 ( 0 1 或1 - - 0 变化) 。如图2 3 所示。 4 、遗传算法流 爱弦瓣个体 i tf l0 0illc ! o ll ll1 0 0 专 变异位援 图2 3 变异操作 图2 4 遗传算法流程图 同济大学硕士学位论文 其中： m 表示代数。 按c 概率选取世代中个体进行复制到新种群中； 按只概率选取世代中个体，两两进行交叉，交叉后，两两复制到新种群中； 按己概率选取世代中个体进行变异，变异后复制到新种群中。 2 4 遗传算法的特点6 3 我们知道，传统的寻优方法主要有三种：枚举法、启发式算法和搜索算法。 l 、枚举法枚举出可行解集合内所有可行解，以求出精确最优解。对于连续函 数，该方法要求先对其进行离散化处理，这样就可能因离散处理而永远达不到最优 解。此外，当枚举空间比较大时，该方法的求解效率比较低，有时甚至在目前先进 计算工具上无法求解。 2 、启发式算法寻求一种能产生可行解的启发规则，以找到一个最优解或近似 最优解。该方法的求解效率比较高，但对每一个需求解的问题必须找出其特有的启 发式规则，这个启发式规则一般无通用性，不适合于其他问题。 3 、搜索算法寻求一种搜索算法，该算法在可行解集合的一个子集内进行搜索 操作，以找到问题的最优解或者近似最优解。该方法虽然保证不了一定能够得到问 题的最优解，但若适当地利用一些启发知识，就可在近似解的质量和效率上达到一 种较好的平衡。 随着问题种类的不同以及问题规模的扩大，要寻求一种能以有限的代价来解决 搜索和优化的通用方法，遗传算法正是为我们提供的一个有效的途径，它不同于传 统的搜索和优化方法。主要区别在于： 自组织、自适应和自学习性。应用遗传算法求解问题时，在编码方案、适应 度函数及遗传算子确定后，算法将利用进化过程中获得的信息自行组织搜索。进化 算法的这种自组织、自适应特征，使它同时具有能根据环境变化来自动发现环境的 特性和规律的能力。自然选择消除了算法设计过程中的一个最大障碍，即需要事先 1 4 同济大学硕士学位论文 描述问题的全部特点，并要说明针对问题的不同特点算法应采取的措施。因此，利 用遗传算法的方法，我们可以解决那些复杂的非结构化问题。 遗传算法的本质并行性。遗传算法按并行方式搜索一个种群数目的点，而不 是单点。它的并行性表现在两个方面，一是遗传算法是内在并行的，即遗传算法本 身非常适合大规模并行。二是遗传算法的内在并行性。这就使遗传算法能以较少的 计算获得较大的收益。 遗传算法不需要求导或其他辅助知识，而只需要影响搜索方向的目标函数和 相应的适应度函数，从而对问题的依赖性较小。 遗传算法强调概率转换规则，而不是确定的转换规则。 遗传算法在解空间内不是盲目的穷举或完全随机测试，而是一种启发式搜 索，其效率往往优于其他方法。 遗传算法对给定问题，可以产生许多的潜在解，最终选择可以由使用者确定。 遗传算法对于待寻优的函数基本无限制，它即不要求函数连续，更不要求可 微；即可是数学解析式所表达的显函数，又可是映射矩阵甚至是神经网络等隐函数， 因而应用范围较广。 遗传算法更适合大规模复杂问题的优化。 2 5 遗传算法的数学基础n 5 1 5 3 遗传算法在机理方面具有搜索过程和优化机制等属性，数学方面的性质可通过 模式定理和构造块假设等分析加以讨论，m a r k o v 链也是分析遗传算法的一个有效工 具。 在遗传算法中，各个个体由其基因型结构决定其表现型性状。遗传算法的选择 操作在个体适应度基础上以概率方式进行，属于非确定性过程，其中交叉为个体间 相互作用，根据环境中的适应度取值的不同，劣质的个体被淘汰，优秀的个体得以 保留，在该选择作用下自适应性也得到体现，同时在种群中也形成一定程序的有序 状态。随机搜索特性使得种群保持了一定的分散性，进化选择机制又通过环境下适 同济大学硕士学位论文 应度评价的方法，完成种群的自适应优化过程。所以遗传算法也可以从自律分布系 统的角度不定期进行分析和研究。遗传算法具有丰富的动态特性，从数学机理加以 探讨，有助于遗传算法的理论研究和应用。本章介绍遗传算法的基本数学理论和分 析工具。 2 5 1 模式定理 2 5 1 1 模式 遗传算法的执行过程中包含了大量的随机性操作，因此有必要对其数学机理进 行分析，我们将种群中的个体即基因串中的相似样板称为“模式 ，模式表示基因串 中某些特征位相同的结构，因此模式也可解释为相同的构形。它描述的是一个串的 子集，在二进制编码的串中，模式是基于三个字符集( 0 ，1 ，宰) 的字符串，符号叶 表任意字符，即0 或1 。例如模式宰1 掌描述了一个四个元的子集 0 1 0 ，0 1 1 ，1 1 0 ，1 1 1 。 对于二进制编码串，当串长为z 时，共有3 个不同的模式，遗传算法中串的运算 实际上是模式的运算。如果各个串的每一位按等概率生成0 或1 ，则规模为n 的种 群模式总数的期望值为 扣it 一1 - 魄y ) j 1 ) c 式2 1 ) 种群最多可以同时处理，l 2 个模式。 从图2 5 可以看同其内含并行性。如果独个体的变化 立地考虑种群中的各个串，则仅能得到，l 条信息。然而，当把适应值与各个串结合 起来考虑，发掘出串群体的相似点，我们受影响的模式 就得到大量的信息来帮助指导搜索，相似 l 10 1 1 0 0 1 l ，0 0 1 ，0 0 1 1 ，0 1 0 1 1 ，0 0 1 点的大量信息包含在规模不大的种群中。 图2 5 内含并行性 不失一般性，考虑由二元字母表v = 0 ，1 】- 编码的染色体，可以用带下标的字母 形式的表示。例如，一个7 位染色体a = 0 1 1 1 0 0 0 可以记为 1 6 同济大学硕士学位论文 a = a l a 2 a 3 a 4 a 5 a 5 a 7 ( 式2 2 ) 这里，每个a ；表示一个二元特征( 基因) ，可以取值为o 或1 ( 即含两个等位基因) ， 下标f 称为遗传子座。 遗传算法通过一个染色体的群体来演化搜索，用a ( t ) 表示在时间t 时的群体， 其中包含n 个染色体彳，j = 1 ，2 ，n 。 根据上面模式定义，例如考虑串长为7 的模式h = 1 1 o ，则上面的串 a = 0 1 1 1 0 0 0 是模式h 的一个表示，这是因为串a 与模式h 在确定位置2 ，3 和5 上相 匹配。 2 5 1 2 模式阶和定义距 定义2 1一个模式h 的阶就是出现在模式中确定位置的数目，记为o ( h ) 。 在二进制串中，一个模式的阶就是一个模式中所有确定的1 或0 的数目。以上 例中的模式为例，模式0 1 1 i * * 的阶为4 ，可记为o ( 0 1 1 1 宰) = 4 ，模式o 事木宰的阶为 1 。 定义2 2 一个模式的定义长度是模式中的第一个确定位置与最后一个确定位 置之间的距离，记为6 ( h ) 。 例如，模式0 1 1 i * * 的定义长度为6 = 9 ，这是因为第一个确定位置为1 ，最后一 个确定位置为5 ，它们之间的距离为6 ( h ) = 5 1 = 4 ；另一模式h = 0 掌事仅有一 个固定位置，即第一个和最后一个确定位置是同一个，因此其定义长度6 ( h ) = 0 。 模式、模式阶以及定义长度对于严格地讨论和区分串的相似性是有用的记号， 并且它们提供了一个基本的方法来分析遗传算子对包含在群体中的基因块的作用效 果。下面分别讨论复制、交叉和变异算子对包含在群体中的模式作用的单独效果和 联合效果。 2 5 1 3 模式定理 假定在给定的时间t ，一个特定的模式h 有m 个代表串包含在群体a ( t ) 中，记 1 7 同济大学硕士学位论文 为小mm ，f ) ( 在不同的时间t ，不同的模式h 可能有不同的数量) 。在复制阶段，每 个串根据它的适应值进行复制，或更确切的说，一个串4 的复制概率为 ( 式2 3 ) 当采用非重叠的，1 个串的群体替代群体a ( t ) 后，我们期待在时间步( t + 1 ) ，模式 h 在群体a ( t + 1 ) q a 有m ( n ，t + 1 ) 个代表串，这, - i p a 由下面的方程给出 川，f + 1 ) 。肌，f ) 疗掌趔n ( 式2 4 ) 乃 其中厂( h ) 是在时间步f 表示模式h 的串的平均适应值，由于整个群体的平均适 应度可记为 7 。翌 。式2 5 ， 故在遗传算法结构条件下，若遗传算法只选择转移到下一世代的话，则下式成 立： 机) 州训幸掣 ( 式2 6 ) 这表明，一个特定的模式按照其平均适应值与群体平均适应值之间的比率生长， 换而言之，那些适应值高于群体平均适应值的模式将在下一代中有更多的代表串， 而对于那些适应值在群体平均适应