（计算机应用技术专业论文）基于遗传算法的智能组卷研究.pdf

哈尔滨丁程大学硕十学位论文 摘要 随着计算机辅助教育研究的不断深入，计算机考试系统作为计算机辅助 教学管理的重要组成部分越来越受到人们的关注。智能组卷算法的研究也成 为计算机辅助教育中的一个重要课题。 组卷问题是一个在一定约束条件下的多目标参数优化问题，采用传统的 数学方法求解十分困难，智能组卷的效率和质量完全取决于试题库设计以及 抽题算法的设计。在对国内外大量相关文献分析研究的基础上，本文选择遗 传算法作为组卷算法。遗传算法是模拟自然界生物化机制的概率性搜索算法， 其优势在于可以高效的处理传统搜索方法难以解决的复杂的非线性问题。其 不受搜索空间的限制性假设的约束，具有广泛的适应性、并行性等特点。 本文首先介绍了遗传算法的基本概念和理论，研究了遗传算法早熟的成 因、常见预防措施及种群多样性度量方法。针对传统算法存在的早熟收敛和 遗传算子无方向性的问题，在传统遗传算法的基础上，提出了一种在宏观上 基于种群分割策略，在微观上基于基因库策略并引入新个体策略的改进的遗 传算法。这种算法可以有效的增加群体的模式再生能力，同时也提高群体的 收敛速度，从而使算法的寻优性能提高。 文中对组卷过程进行了分析，形成了组卷问题的数学模型，将改进算法 与组卷问题的具体情况相结合，设计了一种智能组卷系统。该系统能够按照 试题类型、试题数量、知识点、难度系数、区分度、曝光度、最近出题时间、 答题时间等约束条件进行快速搜索，采用了一种符合组卷问题特点的分段实 数编码方法，并提出了相应的交叉、变异算子。从而找到最佳组卷方案，组 出理想的试卷。并进行了实验分析，表明基于改进遗传算法的智能组卷算法 组卷速度快，组卷质量较好，能够满足实际组卷需求。 关键词：遗传算法；种群分割；基因库策略；模式再生能力 哈尔滨工程大学硕十学位论文 a b s t r a c t w i t ht h ed e v e l o p m e n to fc o m p u t e rb a s e de d u c a t i o n ，c o m p u t e re x a m i n a t i o n s y s t e ma sa l li m p o r t a n tc o m p o n e n to fc o m p u t e rm a n a g e di n s t r u c t i o ng e t sm o r e a n dm o r ea t t e n t i o n t h e s t u d y o fg e n e r a t i n g a l g o r i t h m t o g e n e r a t ep a p e r i n t e l l i g e n t l yi sas i g n i f i c a n tt o p i co fc o m p u t e rb a s e d e d u c a t i o n t h et e s t p a p e rg e n e r a t i n g i sa l l o p t i m i z e dp r o b l e m t om u l t i o b j e c t i v e p a r a m e t e rw i t hc e r t a i nc o n s 仃m n t i t i sv e r yd i f f i c u l tt h a tt h eo p t i m i z a t i o ni s i m p l e m e n t e db yt r a d i t i o n a lm e t h o d t h eq u a l i t y a n de f f i c i e n c yo fi n t e l l i g e n t g e n e r a t i n gt e s tp a p e ri sa l ld e t e r m i n e db yt h et e s tq u e s t i o n s - d a t a b a s ed e s i g n sa n d g e tp r o b l e m s - t e r m sa l g o r i t h m ag r e a td e a lo fa r t i c l e sf r o mi n s i d ea n do u t s i d e a n a l y z e d ，g e n e t i ca l g o r i t h mi ss e l e c t e da st h ew a yt og e n e r a t et e s tp a p e r t h e g e n e t i ca l g o r i t h m i sak i n do fs e a r c h i n gm e t h o du s i n gp r o b a b i l i t yw h i c hs i m u l a t e s t h en a t u r a le v o l u t i o n i t sp r e d o m i n a n c el i e si ne f f e c t i v er e s o l v i n gc o m p l i c a t ea n d n o n 1 i n e a rp r o b l e m s ，w h i c ha r ed i f f i c u l tf o rt r a d i t i o n a ls e a r c h i n gm e t h o d s i th a s f e wl i m i t a t i o n so nt h ep r e s u m p t i o no ft h es o l u t i o ns p a c e ，a n do w n sp r e d o m i n a n c e i na d a p t a b i l i t ya n dp a r a l l e l i s m t h i st h e s i sb d e f l ys u m m a r i z e st h er a t i o n a l e so fg e n e t i ca l g o r i t h mf i r s t l y t h e n , r e s e a r c ho nt h ec a u s eo fp r e m a t u r ec o n v e r g e n c ei nt h i sa l g o r i t h m a n a l y s e s t h ef a m i l i a rd e f e n d a b l es t e pa n dm e a s u r ei t sv a r i e t y t os o l v et h ep r o b l e m so f p r e m a t u r ec o n v e r g e n c ea n db l i n dg e n e t i co p e r a t o r s ，b a s e d 0 1 1t h et r a d i t i o n a l g e n e t i ca l g o r i t h m ，t h i sp a p e rm a k eaa l g o r i t h mw h i c hl i eo nd i v i d e ds w a r m t a c t i c i nm a c m s t r u c t u r ea n dl i eo ng e n es t o r et a c t i ci nm i c r o s t r u c t u r ea s s i s t e db yt h e n e wu n i tt a c t i c t h en e wa l g o r i t h mi m p r o v e sc a p a c i t yo fr e g e n e r a t i o ns c h e m aa n d p a c e st h ea l g o r i t h mc o n v e r g e b ya n a l y z i n gt h ep r o c e s so fg e n e r a t et e x tp a p e r , i te s t a b l i s h e sam a t h e m a t i c m o d e lw h i c hc o m b i n et h en e wg e n e t i ca l g o r i t h mw i t hg e n e r a t i n gp a p e rp r o b l e m u l t i m a t e l yd e s i g nai n t e l l i g e n tg e n e r a t i n gp a p e rs y s t e mf o rt e s t t h es y s t e mc a l l s e a r c hf o rt h eb e s ta n s w e ra c c o r d i n gt os u c hr e s t r i c t i o nc o n d i t i o n sa st e s tq u e s t i o n 哈尔滨工程大学硕七学位论文 t y p e s ，t e r m ss c a l a r , k n o w l e d g ep o i n t s ，d i f f i c u l t yd e g r e e ，d i s t i n g u i s h ，e x p o s i t i o n , t h el a t e s tt i m ea n da n s w e rt i m e ac o r d i n gm e t h o dn a m e dp a r a g r a p h e di n t e g e r c o r d i n gi su s e d d u et ot h ec o r d i n gs t r a t e g y , c r o s s o v e ra n dm u t a t i o no p e r a t o ra l e d e s i g n e d t h ea c t u a lt e s ti n d i c a t e st h a tt h ei n t e l l i g e n tg e n e r a t i n gt e s tp a p e rb a s e d o ni m p r o v e dg e n e t i ca l g o r i t h mc a ns a t i s f yt h en e e d sf o ra c t u a le x a m i n a t i o n s ，t h e s p e e di sf a s t e re n o u g ha n dt h eq u a l i t yo ft e s tp a p e ri sb e t t e r k e y w o r d s ：g e n e t i ca l g o r i t h m ，d i v i d e ds w a m it a c t i c ，g e n es t o r et a c t i c ，c a p a c i t yo f r e g e n e r a t i o ns c h e m a 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除文中已 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 作者( 签字) 望盟 e t 期：如8 年弓月易日 哈尔滨_ 程大学硕十学位论文 1 1 课题背景 第1 章绪论 1 1 1 智能组卷的研究背景 随着计算机技术、网络技术、人工智能、多媒体处理技术的高速发展， 计算机在各种领域都得到了广泛的应用。尤其是在教育方面，计算机技术与 信息论与教育科学的融合，在计算机辅助教育方面更是得到了突飞猛进的发 展。 教学手段、教学方法、教材观念与形式、课堂教学结构、以至教学思想 与教学理论都发生了变革，由此相应形成了许多新的知识并正日渐积累、日 益丰富，从而形成一门新的、综合的、把教育学知识与计算机科学技术知识 相结合的研究领域计算机辅助教育。目前，计算机辅助教育己逐渐发展 成为一门集教育学、心理学、学习理论、信息论、控制理论、计算机科学、 数学等多学科知识于一身的新兴交叉学科并受到各国教育界的的广泛重视。 计算机辅助教育中包括了两个重要的分支领域：计算机辅助教学和计 算机管理教学。 计算机辅助教学是指用计算机帮助或代替教师执行部分教学任务，向学 生传授知识和提供技能训练，直接为学生服务。计算机管理教学是利用计算 机来实施教育管理功能，帮助教师及教育管理人员监测、评价和控制调节教 学和教育管理过程，提供教育决策，实施学校及整个教育系统现代化的一种 新型管理手段。它包括课堂信息处理系统、计算机辅助测验 ( c o m p u t e r - a s s i s t e dt e s t i n g ，c a t ) 系统、计算机辅助教务管理、计算机辅助 教育行政管理、图书资料管理和现代远程教育管理。 ， 计算机辅助测验是计算机在测验及其评价中的应用，近年来在教育领域 的应用发展得很快。在计算机辅助测验的构成中题库是重要的内容【2 j 。目前， 题库建设中使用的测量理论有两种，即经典测量理论和项目反应理论。计算 机辅助测验还包括计算机辅助阅卷和试卷分析，而提出一份高质量的试卷才 是辅助测验的基础，从而人们进行了智能组卷的研究。 哈尔滨下程大学硕士学位论文 随着计算机技术和人工智能的发展，智能组卷的研究被越来越多的被专 家所关注t 3 。它不仅涉及到组卷数学模型的建立问题，还包括对其应用的算 法进行研究。如何设计一个算法使得从题库中既快又好的抽出一组最佳解或 是抽出一组非常接近最佳解的实体，涉及到全局寻优和收敛速度快慢等问题。 一个良好的组卷系统对于教学活动起着非常重要的作用，而如何保证生 成的试卷能最大程度地满足用户的不同需求，并具有随机性、科学性、合理 性，是实现中的一个重点和难点。 1 1 2 智能组卷的研究现状 组卷系统最初是从计算机用于教学开始的，主要是为了把计算机技术应 用到教学领域以提高教学水平和教学质量，它研究的目的是建造教学系统。 最初的系统有电子翻页器以及句型和练习监控程序。 国外早期比较有名的是s c h o l a r 系统，它应用人工智能的知识表达方式， 其知识库采用语义网络形式，并由事实、概念和过程组成，教学方式采用苏 格拉底对话式，根据学生的回答，通过推理机制产生更多提问并评价学生的 解答，系统能诊断学生的一些错误概念并引导学生自己思考后纠正错误。随 着人工智能的发展以及在计算机辅助教学系统的知识表示、推理方法和自然 语言处理等方面的应用。 2 0 多年来计算机辅助测验系统发展迅速。8 0 年代，人们将c a t 系统应用 于大规模等级考试，形成了计算机等级考试系统。典型的有美国的t o e f l 、 g r e 和g m a t 等计算机考试系统，在国内己研制成功的计算机考试系统有高等 数学试题库系统m a t b a s ，南京大学计算机科学与技术系研发的队p a s c a l 题 库系统。但是这些系统中大多数自动组卷功能还处于初级阶段。 由于计算机考试系统的迅速发展，极大的推动了智能组卷系统的研究。 国外和国内的许多科研单位、学校机构都对智能组卷进行了研究。虽然智能 组卷是个被探讨了很长时的问题，但至今也没有一个很好的解决其自动出题 的算法方案。 自动组卷问题涉及算法分析、数学建模、优化控制、人工智能等诸多领 域。8 0 年代中后期，荷兰的林顿等人针对组卷问题的特点率先把随机线性规 划法引入测验编制领域，经过十几年的发展，产生了多种以线性规划为基础 2 哈尔滨工程大学硕士学位论文 的自动组卷策略。其中具有代表性的有优先权策略、弱并行策略、误差补偿 策略、随机抽题法及回溯试探法等晗1 矧。 自动组卷的效率和质量很大程度上取决于选题算法的设计口，。如何设计 一个算法从试题库即快又好的抽出一组最符合考生要求的试题，涉及到一个 全局寻优和收敛速度快慢的问题。以往的有自动组卷功能的考试系统大多采 用随机选取法和回溯试探法，虽然都能最终组出试卷，都存在不足和缺点。 现存的智能组卷系统按照试题的数据结构和生成算法大致可分为三类： ( 1 ) 基于随机函数或随机变量算法的智能组卷系统； ( 2 ) 基于深度及广度搜索算法的智能组卷系统； ( 3 ) 基于智能搜索算法的智能组卷系统。 不少研究人员对前两种系统进行了研究，如对组卷参数进行编码优化， 将约束条件转化为屏蔽码和条件码完成随机抽取过程；基于分割策略的随机 组卷方法；提出一种集合随机抽选组卷算法，每次抽题均从满足抽取条件的 试题集合中选取最优试题：利用题库中试题的基本信息，通过对题量、试题 历史信息及知识点分布的调整和控制实现试题的智能筛选；将众多试题数据 进行分段处理，在各段内随机抽取。这些改进算法在一定程度上提高了组卷 算法的效率和组卷结果的有效性，对一些小规模的试题库有着较好的性能， 但是这些算法没有从根本上改变传统组卷算法的缺陷，对于大规模题库仍显 得力不从心，具有很大的盲目性，缺乏智能性，难以满足组卷需求陋1 0 1 。 随着人工智能研究的不断发展，目前比较流行的组卷算法大多采用智能 搜索算法，基本的算法是：根据用户输入的试卷总体要求，分别匹配试卷的 知识分布、题型分布、认知分类分布、难度分布、区分度分布、时间分布、 分数分布，形成组卷参数表，然后根据该参数表从试题库中选题。这类方法 在形成最终的组卷参数表时，没有考虑知识点分布、题型分布、难度分布等 各种参数之间的相互制约关系，因此在组卷时题库中经常会出现找不到满足 所有属性的试题，只好用具有近似属性的试题替代，最终会降低组卷的指标。 智能搜索算法具有全局寻优和收敛速度快的特点，但是其有些技术和理 论还不成熟，必须从中挑选出适合智能组卷的算法。面对传统组卷算法存在 的不足，很多研究人员将遗传算法、模拟退火算法、神经网络、单亲算法、 禁忌搜索算法等智能优化算法及其改进算法应用到组卷问题中，楼玉萍等提 3 哈尔滨工程大学硕士学位论文 出的基于p b i l 进化算法的自动组卷算法陋1 ；刘仁金等提出的基于粒度合成计 算原理的智能组卷策略等，都取得了很好的效果。 1 1 3 遗传算法在组卷问题中的应用 经过研究发现，遗传算法作为智能搜索算法的一种，具有全局寻优和智 能搜索技术，以及收敛速度快的特性，能够很好的满足自动组卷的需要，有 效的解决随机函数选取法和深度广度回溯试探法组卷的不足【9 】。 遗传算法是模仿自然界生物进化进制发展起来的随机全局搜索和优化方 法，它借鉴了达尔文的物竞天选、适者生存的进化理论和孟德尔的遗传学说。 其本质是一种高效、并行的全局搜索方法，它能够在搜索过程中自动获取和 积累有关搜索空间的知识，并自适应地控制搜索过程以求得最优解。该算法 模拟了自然选择和遗传中发生的复制、交叉和变异等现象，从任一初始种群 出发，通过随机选择、交叉、变异等遗传操作，淘汰不适应环境的个体，使 种群进化到搜索空间中更好的区域，通过一代代的繁衍进化，最后收敛到一 群更适应环境的个体，求得问题的最优解。 与传统优化算法不同，遗传算法是一种借鉴生物界自然选择和自然遗传 机制的随机搜索算法，它通过模拟自然进化过程搜索最优解。与传统优化算 法相比，遗传算法对变量的编码进行操作，直接以目标函数值作为搜索信息， 同时使用多个搜索点的搜索信息，使用概率搜索技术。编码处理方式灵活多 样；搜索范围集中于适应度较高的搜索空间，提高了搜索效率；增加了搜索 过程的灵活性，能够以较少的计算获得较大的收益。 正是因为遗传算法与传统优化算法相比具有简单通用、鲁棒性强、适于 并行处理、全局寻优等特点，较之传统组卷方法，遗传算法更适用于组卷问 题。近年来，已有不少研究人员将遗传算法及其改进算法应用于组卷问题， 并取得了一定的成绩，为智能组卷问题提供了新的解决办法。在系统分析组 卷理论的基础上提出了一种基于自适应多点变异混合算法的智能组卷方法 【1 1 1 ；改变了传统的遗传算法编码方式，根据组卷问题的特点提出了十进制编 码，实验表明该方法取得了比传统二进制编码更好的效果【l2 j ；项目反应理论 与自适应遗传算法相结合，有效地解决了基于l r t 的智能组卷问题；将遗传 算法与模拟退火算法【删相结合的混和算法应用于自动组卷系统的设计，较好 4 哈尔滨下程大学硕十学何论文 一i i 的发挥了两种算法的长处；将启发式思想应用于遗传算法，确保进化过程沿 着有利于最终问题求解的方向进行，有效地降低了非可行解造成的系统开销。 遗传算法也存在着自身的不足。由于计算机条件的限制，遗传算法的种 群规模是有限的，并且在算法运行过程中通常保持群体规模不变，而遗传操 作中的选择操作往往使优良个体呈指数级增长l l5 1 ，因此，在进化初期，种群 中往往会出现大量相同的优良个体，种群多样性丧失，导致算法只能收敛于 局部最优解，引起“早熟”现象的发生【1 7 j 。另外，遗传算法中参数的确定没 有通用的方法，通常只能通过大量的实验来确定，而不恰当的参数又往往导 致算法的搜索性能不高。 针对遗传算法存在的不足，众多学者致力于推动遗传算法的发展，改善 遗传算法的性能，提出了各种改进的遗传算法，比如：结合了精英选择、异 物种重组、大变异的改进遗传算法；采用变长染色体的遗传算法；交叉、变 异概率可变的自适应遗传算法；基于小生境技术的遗传算法；根据问题自身 特点引入非标准遗传操作算子；与传统启发式算法相结合的混和遗传算法以 及并行遗传算法等1 1 3 刎。 1 2 论文所做的工作 本文首先对智能组卷的发展及应用现状进行系统的总结，分析现有组卷 算法的不足，立足于遗传算法进行研究，进一步研究现有的基于遗传算法的 智能组卷，分析出此类算法的优势和不足，从另外一个角度提出一种改进的 遗传算法来弥补这种算法的不足之处。 对提出的改进的遗传算法进行试验，验证算法寻优性能；详细分析组卷 的各项约束指标，并且建立组卷数学模型，并把改进的遗传算法应用到组卷 中。 1 遗传算法的研究 对遗传算法的基本概念和基本理论的研究。研究了基本遗传算法，算法 流程和基本实现。通过对模式定理，隐含并行性，积木块假设理论的研究，对 遗传算法的“早熟 现象有了基本的认识。 2 遗传算法的改进策略 5 哈尔滨t 程大学硕十学何论文 改进遗传算法，对实际的多目标优化问题( 即智能组卷问题) 进行检验 求解，并将求解的结果与性能与传统的多目标优化遗传算法进行比较。使改 进算法能够起到加速收敛的性能，缩短算法求解的时间上起到一定的作用。 3 智能组卷数学模型的研究 智能组卷算法实现的关键在于构建合理的自动组卷模型。组卷过程实质 上是一个多重属性约束条件下复杂的多目标寻优过程。将用户对试题数量、 试题内容、试题难度等属性的要求进行量化，建立试卷模式，得到各个属性 的分数分布列，这些分布列联立起来就构成了自动组卷的数学模型。 4 智能组卷数学模型的求解 智能组卷模型是一个多目标优化的数学模型，模型结构复杂，能否正确、 快速求解成为关键内容，常规的求解多重约束条件下的高维方程组，在理论 和实践上都有一定的难度。因为遗传算法有较好的全局寻优能力，相对传统 的方法而言，可以快速而准确的得到较优解。因此选择遗传算法进行智能组 卷数学模型的求解。 5 建立一个基于改进了的遗传算法的智能组卷系统，实际分析这种算法 的复杂度和优缺点。 1 3 本文组织结构 第1 章绪论从整体上介绍了论文提出的思想依据以及论文所做的工作。 第2 章介绍了遗传算法的基本理论。着重介绍了基本遗传算法，算法流 程和基本实现。通过对模式定理，隐含并行性，积木块假设理论的研究，对遗 传算法的“早熟 现象有了基本的认识。 第3 章对“早熟 现象进行了进一步研究，并在此基础上对目前比较流 行的改进遗传算法进行了研究分析。提出了一种新的改进策略，在宏观上采 用群体分割策略提高种群的多样性，在微观上改良了基因进化方式，增强了 模式的再生能力，提高了模式多样性，而又保证了算法收敛速度不受到大的 影响。并在最后给出了相应的算法。从理论和应用上给予了这个改进遗传算 法以有力的论证。 第4 章对基本组卷模型进行了分析建模，透彻的分析了组卷的各个要素 6 哈尔滨工程大学硕十学位论文 和属性，然后提出基于改进遗传算法的智能组卷模型的详细模型，并对改进 遗传算法中应用的参数进行了设计。 第5 章提出的数学模型进行了具体实现，并对改进的遗传算法在组卷的 实际过程进行了评估。 7 哈尔滨+ t 程大学硕士学位论文 第2 章遗传算法的研究 2 1 遗传算法的历史和应用 遗传算法的产生归功于美国m i c h i g a n 大学的h o l l a n d 在2 0 世纪6 0 年代 末、7 0 年代初的开创性工作，其本意是在人工适应系统中设计的一种基于自 然演化原理搜索机制。另外两种是基于自然演化原理的算法，演化程序和演 化策略。这三种算法构成了目前演化计算领域的三大分支，它们从不同层次、 不同角度模拟自然演化原理，以达到求解问题的目的。h o l l a n d 不仅设计了遗 传算法的模拟与操作原理，更重要的是，他运用统计决策理论对遗传算法的 搜索机理进行了理论分析，建立了著名的s c h e m a 定理和隐含并行性( i m p l i c i t p a r a l l e l i s m ) 原理，为遗传算法的发展奠定了基础。1 9 7 5 年，h o l l a n d 出版了 专著( a d a p t a t i o ni n n a t u r a la n da r t i f i c i a l s y s t e m s ) ) ，标志着遗传算法的正 式诞生。 进入8 0 年代，遗传算法迎来了兴盛发展时期，理论研究和应用研究都成 了十分热门的话题。h o l l a n d 实现了第一个基于遗传算法的机器学习系统分类 器系统( c l a s s i f i e rs y s t e m s ) ，开创了遗传算法的机器学习的新概念。1 9 5 9 年， g o l d b e r g 出版了专著( ( g e n e t i ca l g o r i t h mi ns e a r c h ，o p t i m i z a t i o na n dm a c h i l i e l e a r n i n g 。该书总结了遗传算法的主要研究成果，全面而完整地论述了遗传 算法的基本原理及其应用，为现代遗传算法的发展奠定了科学基础。 2 0 世纪9 0 年代，人们提出了很多新的遗传算子，并对其进行了深入的 研究。h o l l a n d 除了使用交叉和变异两种算子，还引入倒置算子，倒置算子的 思想在于产生次序关系以使得优良的序列能够更好地保留。随着分子生物学 的兴起，一些学者在基因重组的启发下认为需要研究更多的遗传算子。这些 学者认为类似于联结、换位、移植的算子应该加以仔细研究并将之应用于进 化计算中。 我国有关遗传算法的研究，从2 0 世纪9 0 年代以来一直处于不断上升的 时期，特别是近年来，遗传算法、进化计算的应用在许多领域取得了令人瞩 目的成果，集中在基本遗传算法及其改进方面做了许多工作，开发出许多应 8 哈尔滨t 稗大学硕士学位论文 i 用系统。熊辉等提出了基于神经网络的遗传算法，宋维等提出了一种与小生 境技术和单纯搜索相结合的混合遗传算法；张著洪等提出了一种免疫算法； 韩炜等提出了一种与单纯形法相结合的混合遗传算法；唐巍等提出了一种混 沌遗传算法，算法利用混沌运动的随机性、遍历性和对初始条件的敏感性等 特性进行群体的混沌初始化和最有个体的混沌变尺度载波寻优：模拟退火和 多种群并行遗传进化思想分别被引入遗传算法中，也显现出良好的应用前景。 2 2 基本遗传算法 遗传算法的基本思想是基于达尔文进化论和孟德尔的遗传变异理论的。 d a n 航n 进化论最重要的是“物竞天择，适者生存 原理。它认为自然界总是 延续适应性强的物种，淘汰不适应的物种，每一物种在发展中越来越适应环 境。基于对自然界中生物遗传与进化机理的模仿，很多学者设计了许多不同 的编码方法来表示问题的可行解，开发出许多不同的遗传算子来模仿不同环 境下的生物遗传特性，由不同的编码方法和不同的遗传算子就构成了各种不 同的遗传算法。但是这些遗传算法都有共同的特点，即通过对生物遗传和进 化过程中选择、交叉和变异机理的模仿，来完成对问题最优解的自适应搜索 过程。基于这个共同特点，g o l d b e r g 总结出了一种统一的最基本的遗传算法 基本遗传算法( s g a ，s i m p l eg e n e t i ca l g o r i t h m s ) 。基本遗传算法只使用 选择算子、交叉算子和变算子这三种基本遗传算子来模拟现实世界中的“优 胜劣汰 ，交配繁殖以及基因变异现象，是其他一些遗传算法的雏形和基础。 2 2 1 遗传算法的基本概念与构成要素 1 基因( g e n e ) ：基因是携带遗传信息的基本单位，基因用于表示个体的 特征。例如个体s = i o l l ，则其中的1 0 1 1 这4 个元素分别称为基因。 2 基因型个体( i n d i v i d u a l ) ：基因型个体就是遗传过程中带有遗传特征的 实体，也叫基因串，简称个体，对应于遗传学中的染色体( c h r o m o s o m e ) 。 3 种群( p o p u l a t i o n ) ：个体的集合称为种群，个体是种群中的元素。 4 种群大d 、( p o p u l a t i o ns i z e ) ：在种群中个体的数量称为种群的大小， 也叫群体规模。 5 基因座( 1 0 c u s ) ：基因座就是基因在个体中所占据的位置。同一基因座 9 哈尔滨t 程大学硕士学位论文 可能有的全部基因称为等位基因( a l l e l e s ) 。基因座在个体中由左向右计算，例 如在串s = 1 1 0 1 中，0 的基因座是3 。 6 适应度( f i t n e s s ) ：表示某一个体对于生存环境的适应程度，对生存环 境适应程度较高的个体将获得更多的繁殖机会，而对生存环境适应程度低较 低的物种，其繁殖机会就会相对减少，甚至逐渐灭绝。 7 遗传子型：基因组合的模型叫遗传子型，它是染色体的内部表现，又 称基因型。 8 表现型：由染色体决定性状的外部表现，根据遗传子型形成的个体。 9 编码：从表现型到遗传子型的映射。 1 0 解码：从遗传子型到表现型的映射。 基本遗传算法主要有以下几个部分组成： ( 1 ) 染色体编码方法。由于遗传算法不能直接处理解空间的数据，因此必 须通过编码将它们表示成遗传空间的基因型结构数据。基本遗传算法使用固 定长度的二进制符号串来表示群体中的个体，其等位基因是6 - 值符号集 0 ， 1 所组成的。初始群体中各个个体的基因值可用均匀分布的随机数来生成。 ( 2 ) 个体适应度评价。基本遗传算法按与个体适应度成正比的概率来决定 当前群体中每个个体遗传到下一代群体中的机会多少。为正确计算这个概率， 这里要求所有个体的适应度必须为正数或零。这样，根据不同种类的问题， 必须预先确定好由目标函数值到个体适应度之间的转换规则，特别是要预先 确定好当目标函数值为负数时的处理方法。 ( 3 ) 遗传算子。基本遗传算子使用下述三种遗传算子： 1 ) 选择运算：选择运算使用比例选择算子。目的是为了从当前群体中选 出优良的个体，使它们有机会作为父代繁殖后代子孙。判断个体优劣的准则 是个体的适应度值。选择运算模拟了达尔文适者生存、优胜劣汰原则，个体 适应度越高，被选择的机会也就越多； 2 ) 交叉运算：交叉运算使用单点交叉算子。交叉运算相当于生物进化过 程中的有性繁殖的基因重组过程； 3 ) 变异运算；变异运算使用基本位变异算子或均匀变异算子；变异运算 模拟了生物进化过程中的基因突变方法，将某个基因座上的基因变异为其等 位基因； 1 0 哈尔滨工程大学硕士学位论文 选择运算不产生新的个体，交叉运算和变异运算都产生新的个体，因此， 选择运算完成的是复制操作，而交叉运算和变异运算则完成繁殖操作。 ( 4 ) 基本遗传算法的运行参数。基本遗传算法有下述4 个运行参数需要提 前设定。主要的参数有： 1 ) 群体大小n ，即群体中所含个体的数量。群体规模影响遗传优化的最 终结果以及遗传算法的执行效率。当群体规模n 太小时，遗传算法的优化性 能一般不会太好，而采用较大的群体规模则可减少遗传算法陷入局部最优解 的机会，但较大的群体规模意味着计算复杂度高。一般取为2 0 1 0 0 ； 2 ) 遗传运算的终止进化代数，一般取为1 0 0 5 0 0 ； 3 ) 交叉概率p 。，交叉概率p 。控制着交叉操作被使用的频度。较大的交叉 概率可增强遗传算法开辟新的搜索区域的能力，但高性能的模式遭到破坏的 可能性增大；若交叉概率太低，遗传算法搜索可能陷入迟钝状态。一般取为 0 4 , - , 0 9 9 ； 4 ) 变异概率p m ，变异在遗传算法中属于辅助性的搜索操作，它的主要目 的是维持解群体的多样性。一般，低频度的变异可防止群体中重要的、单一 基因的可能丢失，高频度的变异将使遗传算法趋于纯粹的随机搜索。一般取 为0 0 0 0 1 - - 0 1 ； ( 5 ) 初始种群的生成，由于遗传算法的群体操作需要，所以进化开始前 必须准备一个由若干初始解组成的初始群体； ( 6 ) 终止条件，终止条件就是遗传进化结束的条件。基本遗传算法的终 止条件可以是最大进化代数或最优解所需满足的精度； 需要指出的是，运行参数对遗传算法的求解结果和求解效率都有一定的 影响，但目前尚无合理选择它们的理论依据。在遗传算法的实际应用中，往 往需要经过多次试验后，才能确定出这些参数合理的取值大小或取值范围。 2 2 2 基本遗传算法的流程 遗传算法模拟了自然选择和遗传中发生的复制、交叉和变异等现象，从 任一初始种群( p o p u l a t i o n ) 出发，通过随机选择、交叉和变异操作，产生一群 更适应环境的个体，使群体进化到搜索空间中越来越好的区域，这样一代代 地不断繁衍进化，最后收敛到一群最适应环境的个体( i n d i v i d u a l ) ，求得问题 1 1 哈尔滨1 = 程大学硕士学位论文 一i i _ 的最优解。 基本遗传算法( 也称为标准遗传算法或简单遗传算法，b a s eg e n e t i c a l g o r i t h m ，简称b g a ) 是一种群体型操作，该操作以群体中的所有个体为对 象，是其他遗传算法的基础，给其他遗传算法提供了一个基本的框架。 基本遗传算法流程图如图2 1 所示： 最 优 解 图2 1 基本遗传算法流程图 2 2 3 基本遗传算法的一般实现描述 1 个体适应度评价 遗传算法中，以个体适应度的大小来确定该个体被遗传到下一代群体中 的概率。基本遗传算法使用比例选择算子来确定群体中各个个体遗传到下一 代群体中的数量。为正确计算不同情况下各个个体的遗传概率，要求所有个 体的适应度必须为正数或零，不能是负数。实际优化问题的目标函数值有正 也有负，优化目标有求函数最大值，也有求函数最小值，需要通过一定的转 换关系，由此将保证所有个体适应度总取非负值。 对于求目标函数最大值的优化问题，变换方法为： f ( x ) ：j 职) + ，+ 知 一 【o ，f ( x ) + e r a o c m i n 为一个适当地相对比较小的数，c m 舣为一个适当地相对比较大的数。 选取方法总结为：预先指定的一个较大较小的数。进化到当前代为止的 最大最小目标函数值。获得当前代或最近几代群体中的最小目标函数值最大 目标函数值。 2 比例选择算子 选择算子是模拟自然界“优胜劣汰现象而形成的一种算子。最常用和 最基本的选择算子是比例选择算子。所谓比例选择算子是指个体被选中并遗 传到下一代群体中的概率与该个体的适应度大小成正比。比例选择实际上是 一种有退还随机选择，也叫做赌盘选择。 其具体执行过程是：首先计算出群体中所有个体适应度的总和。再计算 出每个个体的相对适应度的大小，它即为各个体被遗传到下一代的概率。最 后再使用模拟赌盘操作来确定各个体被选中的次数。 3 单点交叉算子 交叉算子是模拟自然界杂交而形成的一种算子。交叉算子是最常用和最 基本的交叉操作算子，单点交叉算子的个体执行过程： 对群体中的个体进行两两随机配对。对每一对相互配对的个体，随机选 择某一位置为交叉点。对每一对相互配对的个体，依设定的交叉概率在其交 叉点处相互交换两个个体的部分染色体，从而产生出两个新的个体。 4 基本位变异算子 变异算子是模拟自然界基因变异而形成的一种算子。基本位变异算子是 最简单和最基本的变异操作算子。对于基本遗传算法中用二进制编码符号串 所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0 ，则 变异操作将该基因值变为l ；反之，若原有基因值为1 ，则变异操作将其变为 0 。 基本位变异算子的具体执行过程是：对个体的每一个基因座，依变异概 1 3 哈尔滨工程大学硕士学位论文 i _ _ 一 率指定其为变异点。对每一个指定的变异点，对其基因值做取反运算或用其 他等位基因值来代替，从而产生出一个新的个体。 5 二进制编码 二迸制编码方法是遗传算法中最常用的一种编码方法，它使用的编码符 号集是由二进制符号0 和l 所组成的二值符号集 o ，1 ) ，它所构成的个体基 因型是一个二迸制编码符号串。二进制编码符号串的长度与问题所要求的求 解精度有关。 假设某一参数的取值范围是 u n i i l ，u 嘣】，用长度为l 的二进制编码符号 串来表示该参数，则它总共能够产生2 l 种不同的编码，则二进制编码的精 度为： u 麟一u 曲 t 一。 2 1 6 约束条件处理 实际应用中的优化问题一般都含有一定的约束条件，它们的描述形式各 种各样。在遗传算法的应用中，必须对这些约束条件进行处理，而目前还未 找到一种能够处理各种约束条件的一般化方法。所以对约束条件进行处理时， 只能是针对具体应用问题及约束条件的特征，再考虑遗传算法中遗传算法的 运行能力，选用不同的处理方法。现有的处理方法主要有：搜索空间限定法、 可行解变换法和罚函数法。 搜索空间限定法的基本思想是对遗传算法搜索空间的大小加以限制，使 得搜索空间中表示一个个体的点与解空间中表示一个可行解的点有一一对应 的关系：对一些简单的约束条件( a x b ) ，在个体染色体的编码方法上着手， 就能够达到这种搜索空间与解空间之间的一一对应的要求。用这种处理方法 能够在遗传算法中设置最小的搜索空间，所以它能够提高遗传算法的搜索效 率。 可行解变换法的基本思想是在由个体基因型到个体表现型的变换中，增 加使其满足约束条件的处理过程。即寻找出一种个体基因型和个体表现型之 间的多对一的变换关系，使进化过程中所产生的个体总能够通过这个变换而 转化成解空间中满足约束条件的个可行解。这种处理方法对个体的编码方 1 4 哈尔滨工程大学硕士学位论文 法、交叉运算、变异运算等没有附加的要求。 罚函数法的基本思想是对在解空间中无对应可行解的个体，计算其适应 度时，处以一个罚函数，从而降低该个体适应度，使该个体被遗传到下一代 群体中的机会减少。 2 3 遗传算法的基础理论 遗传算法有效性的理论依据为模式定理和积木块假设。模式定理保证了 较优的模式( 遗传算法的较优解) 的样本呈指数级增长，从而满足了寻找最优 解的必要条件，即遗传算法存在着找到全局最优解的可能性。而积木块假设 指出，遗传算法具备找到全局最优解的能力，即具有低阶，短距、高平均适 应度的模式( 积木块) 在遗传算子作用下，相互结合，能生成高阶、长距、高 平均适应度的模式，最终生成全局最优解。 2 3 1 模式定理 模式定理是遗传算法的理论基础，它描述了遗传算法的搜索策略。 定义2 1 模式：基于三值字符集 0 ，1 ，) 所产生的能描述具有某些结构 相似性的0 、1 字符串集的字符串称作模式。 以二进制编码方式为例，个体是由二值字符集v = 0 ，1 ) 中的元素所组成 的一个编码串，而模式却是由三值字符集u = ，0 ，1 ) 中的元素所组成的一 个编码串，其中 表示通配符，它既可被当作“l ，也可被当作“0 。那 么模式h = l l * * l 描述了长度为5 ，且在位置1 、2 、5 取值为“l 的所有字符 串的集合 1 1 0 0 1 ，1 1 0 1 1 ，1 1 1 0 1 ，1 1 1 1 1 。 根据模式的定义，长度为l 的二进制串隐含着2 1 个模式。一个模式可以 隐含在多个串中，不同的串之间通过模式而互相联系。遗传算法中串的运算， 实际上是模式的运算。 定义2 2 模式阶：在模式h 中具有确定基因值的位置数目称为该模式的 模式阶，记为o ( h ) 。 以二进制编码为例，模式阶就是模式中听含有的1 和0 的数目，例如， o ( 1 0 1 ) = 3 。一个模式的阶数越高，其样本数就越少，因而确定性越高。 定义2 3 定义距：模式h 中第一个确定基因值的位置和最后一个确定基 1 5 哈尔滨工程大学硕士学位论文 因值的位置之间的距离称为该模式的模式定义长度，记为6 ( h ) 。 有了上面的基本概念就可以讨论模式在遗传操作下的变化。 定理2 1 模式定理：在遗传算子选择、交叉和变异的作用下，具有低阶、 短定义距以及平均适应度高于群体平均适应度的模式在子代中将得以指数级 增。 在随机搜索中，要获得最优