（计算机应用技术专业论文）遗传算法求解约束满足问题的研究与应用.pdf

摘要 遗传算法广泛地应用在各种不同领域的优化问题上，且已 证明有不错 的求解结果。然而，遗传算法本身并没有处理约束条件的能力，但在实际 应用问题上常常包含约束条件。因此必须加入额外的机制使得遗传算法能 够处理约束满足问 题。 一般在遗传算法中处理约束条件的方法有四 种: ( 1 ) 拒绝策略、 ( 2 ) 应用修补策略、 ( 3 ) 改变遗传算子、( 4 ) 采用惩罚函数法。 本论文针对计算机组卷问题，提出了一种迪传算法求解约束问题的混 合策略。 这种混合策略遗传算法具有下列特点: ( 1 ) 初始解指导生成、 ( 2 ) 改变遗传算子、( 3 )修补策略。 初始解指导生成通过采用一定的和所求问 题领域相关的策略指导初始种群的生成;改变遗传算子设计与问题相关的 有特色的遗传算子，使得遗传算法能够较好地处理约束条件;修补策略对 无法满足的约束条件依权重由轻到重依次降低它的约束条件，以求得满足 约束条件的近似最佳解。 由于一个组卷策略的实现可以归结为约束满足问题 ( c o n s t r a in t s a t i s f a n t i o n p r o b l e m s c s p s ) ， 基本遗传算法本身又不具备解决约束问题的 能力。论文阐述了用混合策略应用到组卷策略中的具体实现方法，设计了 基于遗传算法的组卷模型。并以己建成的北京交通大学计算机基础课程题 库为数据源， 采用该方法进行了 模拟组卷试验。 通过对实验数据的分析和 比 较， 证明了混合策略遗传算法不仅使得遗传算法具有了求解约束条件满 足问题的能力，而且在求解的效率上要高于通常的二进制编码遗传算法和 随机组卷。 关键字: 约束满足问题、遗传算法、混合策略、组卷策略 未 经 作者、 导 师ta s 勿 全文 公布 ab s t r a c t t h e g e n e t i c a l g o r i t h m ( g a ) h a s b e e n w i d e l y a p p l i e d i n v a ri o u s o p t i m i z a t i o n p r o b l e m s a n d r e p o r t e d a s s a t i s f i e d i n m a n y c a s e s . i t i s w e l l k n o w n t h a t t h e c o n s t r a i n t f e a t u r e s a r e e v e r y w h e r e i n t h e r e a l p rob l e m. h o w e v e r , g a d o s e n o t h a v e t h e c a p a b i l i ty o f h a n d l i n g t h e c o n s t r a i n t s . t h e e x t r a m e c h a n i s m h a s t o b e a d d e d i n t h e g a t o m a k e i t c a n m a n a g e t h e c o n s t r a i n t s a t i s f a c t i o n p r o b l e m . ma n y r e s e a r c h h a v e b e e n t r i e d t o i n c l u d e t h e c o n s t r a i n t s h a n d l i n g c a p a b i l ity i n t h e g a p r o c e s s . t h e m e t h o d s t h a t a r e a l w a y s u s e d i n t h e g a t o d e a l w i t h c o n s t r a in t a r e : ( 1 ) d i s p o s a l o f t h e i n f e a s i b l e s o l u t i o n s , ( 2 ) a d o p t i n g t h e p e n a l ty f u n c t i o n , ( 3 ) m o d i f y i n g t h e g e n e t i c o p e r a t o r s , ( 4 ) a p p l y i n g t h e r e p a ir i n g p r o g r a m. a c c o r d i n g t o t h e i t e m s e l e c t i o n p r o b l e m , my r e s e a r c h b r i n g s f o r w a r d a h y b ri d s t r a t e g y t h a t c a n m a k e t h e g a t o m a n a g e t h e c o n s t r a i n t c o n d i t i o n s . t h e re a r e t h r e e c o n t e n t s t o b e i n c l u d e d i n i t : t h e mo d e wh i c h t h e i n i t i a l p o p u l a t i o n c o m e s in t o b e i n g， m o d i f y i n g t h e g e n e t i c o p e r a t o r s a n d t h e f in a l r e p a i r i n g p r o g r a m . i t a d d s s o m e s t r a t e g y i n t h e m o d e w h i c h t h e i n i t i a l p o p u l a t i o n g e n e r a t e s ; a n d i t d e s i g n s t h e g e n e t i c o p e r a t o r s t o h a v e t h e c h a r a c t e r o f t h e r e a l p r o b l e m s t h a t c a n m a k e t h e m a j o r i ty o f t h e s o l u ti o n s t o m e e t t h e c o n s t r a i n t s . f o r t h e u n f e a s i b l e c o n s t r a i n t s , t h e r e p a i r in g p r o g r a m r e d u c e s t h e c o n s t r a i n t a c c o r d i n g t o t h e w e i g h t o f t h e c o n s t r a i n t s . an i t e m s e l e c t i o n t a c ti c i s a co n s t r a i n t s a t i s f a c ti o n p r o b l e m i n f a c t . s i m p l e g e n e t i c a l g o r i t h m c a n n o t s o lv e c s p s . b y c o m b i n i n g g a a n d th e c o n s t r a i n t s o f t h e i t e m s e l e c t i o n p a r a m e t e r s , t h i s p a p e r d e s i g n s t h e d e t a i l e d s t e p a n d i m p l e m e n t a ti o n a p p r o a c h . t h e i t e m b a n k i s b a s e d o n c o m p u t e r f o u n d a t i o n c o u r s e s i t e m b a n k o f b e ij i n g j i a o t o n g u n i v e r s i ty . b a s e d o n t h e it e m b a n k , i t a k e t h e s i m u l a t e d e x p e ri m e n t b y t h e a p p r o a c h . a s c a n b e s e e n fr o m t h e l a t te r e x p e ri m e n t : a ft e r a p p ly i n g t h e h y b ri d s t r a t e g y , n o t o n l y c a n g a s o lv e t h e c o n s t r a i n t p r o b l e m s , w e w i l l a l s o s e e a m o r e e f fi c i e n t a n d s u c c e s s f u l s e t tl e m e n t c o m p a r e d w i t h s t o c h a s ti c s t r a t e g y a n d t h e b in a r y c o d i n g g e n e t ic a l g o ri t h m . k e y w o r d s : c o n s t r a i n t s a t i s f a c t i o n p r o b l e m , g e n e ti c a l g o r i t h m , h y b ri d s t r a t e g y , i t e m s e l e c t i o n p r o b l e m 北京交通大学硕士学位论文 第一章 绪论 1 . 1研究背景和动机 带有约束条件的问题的求解是现实生活中一个很重要也很复杂的问 题。 许多现实中的优化问题、满足问题都可以归结为一个问 题，即约束满 足问题 ( c o n s t r a i n t s a t i s f a c t i o n p r o b l e m s c s p s ) 。已 经有很多不同领域的学 者开始把约束满足问 题纳入其研究的范围之内。约束满足问 题 ( c s p s ) 在 数据库检索、集成电 路设计、计算机视觉、定理证明、机器人规划、机器 学习等诸多研究领域具有广泛的应用背景。教育专家所关心的组卷问题也 是一个典型的约束满足问题。一个试卷的组织可以认为在满足一定的目 标 参数下试题的分配问题。然而，在同一组约束条件下，可能会同时出现多 个不同的可行解 ( f e a s i b l e s o l u t i o n ) 。 一个可行解的好坏， 可以视为其能否 满足约束条件，最好的组卷结果是能够全部满足约束条件的最佳解。 遗传算法近年来快速发展，且具有全局搜索潜力的最佳化方法。此方 法采用多点同时搜索的技巧，能避免传统最佳化方法只能搜索到局部最佳 解的缺点，并提供接近系统的全局最佳解。遗传算法属于人工智能 ( a r tif ic i a l i n t e l l ig e n c e ) 的 范 畴 13 11 。 人 工 智 能 法 强 调 模 拟 生 物、 人 类 本 身 的一些思维和生活方式来解决复杂的实际问题。遗传算法的这些特点很适 合于解决约束满足问题这类复杂的真实世界问题。 在实际生产问题上，无约束条件的问 题并不多见，大部分为包含约束 条件的最佳化问题。而遗传算法为求解无约束条件问题的最佳化算法，并 无处理约束条件的能力，因此必须加上额外的机制将使得遗传算法能够处 理约束满足问 题。 一般在遗传算法中用来处理约束条件的方法有四种 1 1 , ( 1 ) 拒绝策略、( 2 ) 应用修补策略、( 3 )改变遗传算子、( 4 ) 采用惩罚函 数法。 尽管这些方法都可以使得遗传算法在一定程度上解决约束满足问题， 但是这些处理约束问题的方法的能力还不是很强。因此本论文提出了一种 北京交通大学硕士学位论文 混合策略来改善遗传算法处理约束条件的能力，并在第四章进行了验证。 在论文的第四章，将这个混合策略遗传算法应用到了目前考试系统中 非常重要的组卷环节中，通过试验结果可以看出，应用混合策略后的遗传 算法有很强的解决约束问题的能力，其组卷算法也比传统的随机组卷和二 进制编码遗传算法组卷效率高。 综上所述，本论文针对实际领域中经常出现的约束满足问题，根据遗 传算法全局寻优的特点，提出了 一种混合策略使得遗传算法能够很好的处 理约束满足问题，并将此混合策略应用于组卷系统这一约束满足问题，显 示出良好的组卷效率和组卷效果。 1 .2研究目的和意义 一般的实际问题中大都带有许多约束条件，而遗传算法适合用在设计 变量离散且不带有约束条件的情况。在此情况下，许多学者开始研究遗传 算法如何处理约束条件的 方法， 一般处理约束条件的 方法有四 种 i ) : 拒绝 策略、修正策略、改变遗传算子及惩罚函数。这些方法通过遗传算子产生 一个问题解，在与约束条件对比，确认是否符合约束条件，等于是在遗传 算法中多加入一个核对约束条件的机制，不同的是处理约束条件机制的不 同，每个方法也有其固有的一些应用领域和缺点。 本论文根据这些不同的策略，结合计算机组卷问题，提出了一种混合 策略遗传算法。这个策略主要从初始种群的产生方式、遗传算子的修改以 及修正策略方面进行了考虑， 使得这个策略能够较好地处理约束满足问题。 然后将这个混合策略应用于计算机组卷系统中，面对题量巨大的试题库， 探讨如何将改进后的遗传算法应用于组卷系统中，以快速、高质量地得到 一份满足用户要求的试卷。 1 . 3研究方法和步骤 本论文研究方法和步骤主要分为六个阶段， 各部分内容概述如下所示: ( 1 )研究背景及研究目的的建立 北京交通大学硕士学位论文 主要确认本论文的 研究目 的 和研究背景。 ( )约束满足问题的基本理论 收集国内外有关约束满足问题的文献资料，了解目 前的研究状况，文 献回顾的主要内容包括约束满足问 题的定义和求解技术。 ( 3 ) 遗传算法的基本理论 回顾了遗传算法的理论基础和求解步骤，根据约束满足问 题的特点分 析出遗传算法的不足以 及修补策略，比较这几种方法利弊和适用范围， 提 出了一种能够较好地求解约束满足问题的混合策略。 ( 4 )分析用遗传算法求解智能组卷系统的实现方案 根据组卷策略这个约束满足问题的具体特点，建立起遗传算法求解模 式。 确定问 题的 编码方法、初始种群的建立方式、目 标函数的具体形式、 遗传算子操作方式、终止条件以及修正程序。最后在问题空间中找出满足 约束条件的最优解， 然后以 此最优解作为参数抽出一份满足用户参数的最 优试卷或近似最优试卷。 ( 5 ) 遗传算法在智能组卷系统中的 程序实现和数据分析 本组卷系统用j a v a b e a n和j s p 程序实现了 这套智能组卷系统。 这套组 卷系统具有组卷、编辑、打印、统计等多种功能， 应用于复杂而庞大的计 算机基础课程试题库之上， 可以帮助教师进行智能组卷， 提高组卷的性能、 效率以及试卷的质量，并可以 对最后的试卷进行打印。通过和传统组卷算 法进行对比分析，显示出很好的组卷效果。 ( 6 )总结和展望 总结混合策略遗传算法在约束满足问题中的应用结果，并指出需要进 行的改进。 北京交通大学硕士学位论文 1 .4论文结构图 确定研究背景和目 的 参考约束条件满足问 题文献 参考遗传算法有关文献 讨论遗传算法求解约束条件的方法 提出一种棍合策略来求解约束满足 问题 使用混合策略遗传算法求解组卷问 题 分析用遗传算法求解智能组卷系统 的实现方案 遗传算法在智能组卷系统中的 程序 实现和系统展示 各种组卷算法性能比较 总结和展望 图1 . 1论文结构图 北京交通大学硕士学位论文 第二章 约束满足问题 ( c s p s ) 约束满足问 题( c s p s ) 在数据库检索、集成电 路设计、计算机视觉、定 理证明、机器人规划、机器学习等诸多研究领域具有广泛的应用背景。简 单的 说， 约束满足问 题( c s p s ) 就是要求对满足 一定约束条 件的 变量进 行赋 值的问 题。 约束满足问 题( c s p s ) 的实例很多， 如图着色、 线性图理解、产 生式系统中的模式匹配、 n 一 皇后问题等。在通常情况下， 检查 c s p s问题 的满足性或一致性是一个 n p完全问题。 2 . 1 c s p s 问题的定义 根 据t s a n g 2 1 中 所 提出 的 定 义: “ 一 个 约 束 满 足问 题 是由 一 组 有限 个 变 量所组成，每一个变量都有一个有限范围的值域和一组约束条件组成，这 些约束条件变量可以同时被指定一些值 ( v a l u e ) 。因此约束满足问题所要 解决的是为每一个变量指定一个合适的值，使其符合所有的约束条件。 ” 下面介绍一个通用的表达方式来定义一个约束满足问题: c s p ( z , d , c ) 其中 z :一 组 有限 个 数 的 变 量x 3 , x z ,., x ; 为 一 个有限 范围 的 值 域 d i , d z , d o, d * 表 示 第k 个 变量x 、 的 值 域; 为一组任意变量的组合，表示的是变量与变量间或变量本身的约束条 如 cx l.x : x ， 代 表 的 是 x i , x z , x 3 之 间 的 约 束 条 件 。 如 果 二 限 制 在 a , b , 。 三 个 c 二 可以记为c x = 衣 x , a ) , ( x , b ) , ( x , c ) . ( x , i ) 表示x 可以 设定为 dc件值 i ( i =a , b , c ) c s p s 的 工 作 就 是 找 到 一 组 解 :1 ( x 1 v i ) , ( x 7 , v z ) ,., ( x , v n ) ， 使 其 符 合 北京交通大学硕士学位论文 所 有 的 约 束 条 件c ， 其中v 为 指 定 变 量的 值iv , i v 2 ， 二 ，, v j i ， 为 第， 个 变 量x , 的指定值。 一个 c s p s 的 可行解 ( f e a s i b l e s o l u t i o n ) 是指在满足所有的约束条件 下， 从 每个变量的 值域范围内 找出 一 个给定值 ( a s s i g n m e n t )赋给变量。 若在此种情况下有可行解存在， 那么称这个c s p s 是可满足的( s a t i s fi a b l e ) , 否则 称此c s p s 是不可满足的 ( u n s a t i s fi a b l e ) . c s p s 的 解主 要 有下 面三种2 1 . ( 1 ) 只要找到一个解即可。 一个c s p s 可能 有很多解， 但只要找到其中 一个 即可。 ( 2 ) 找出所有解。 ( 3 ) 找到一个最佳解 ( o p t i m a l s o l u t i o n ) .即 针对某些变量，用一个目 标函 数( o b j e c t i v e f u n c t i o n ) 评估解的 优劣， 找到最符合目 标函数的解为止。 2 .2主要求解算法简介 求解 c s p s时通常结合各种不同的算法一起使用，主要包含系统搜索 技术和一致性检验技术3 2 1 2 .2 . 1 搜索算法 搜 索算法指的 是能够系统化 地( s y s t e m a t i c a l l y ) ， 完整 地( c o m p l e t e l y ) 搜寻问题的可行解空间。目 前最广为人知的系统化的算法为生成测试法 g e n e r a t e - a n d - t e s t ( g t ) 和回溯法 b a c k t r a c k in g ( b t ) 两种。 下面从两个角度分 析它们之间的差异。 从变量赋值角度来讲， g t是独立且同时一次赋给所有 决策变量一个可能值，而 b t则是独立但是按次序赋给每个变量一个可能 值; 从约束条件的角度来看， g t的约束条件的检验时机为当所有变量都被 赋值后才进行约束条件的检验，而 b t的检验时机为每当一个变量被赋于 一个可能值时就进行检验。所以就空间搜索效率而言，b t的执行效率比 g t要高。 1 . 测试生成法( g e n e r a t e a n d t e s t g t ) 北京交通大学硕士学位论文 g t 来源于数学上求解组合问 题的方法。 此这个算法中主要包含两个主 要部件，解生成器 ( g e n e r a t o r )和解检查器 ( t e s t e r ) 。算法系统地由生成 器产生每个变量的每个可能值的组合，然后由检查器测试其是否满足所有 的约束条件，最早产生那个满足所有约束条件的组合，便是 c s p s的解。 解检查器产生解的方式中并没有考虑变量之间的约束条件，因此 g t的解 产生器又可称为盲目 解产生器 ( b l i n d g e n e r a t o r ) . 很明显，此种方法的效率低下，它对每个变量产生了太多的无法满足 约束条件的给定值，而且搜索空间随着变量数量的增加成指数级增长，使 得此算法难以实行。 解产生器 检测器 _ _ _ _ _ 二 厂一 门 _/可 行 解 u c t 习 o 非可行解 图2 . 1 g t运行图 2 回溯算法( b a c k t r a c k i n g b t ) 回溯法为系统化搜索算法中最基本、最常用的算法之一，其算法的 特 点为: ( 1 ) 以树型搜索为核心搜索架构 ( 2 ) 以 深度优先算法 ( d e p t h f i r s t s e a r c h d f s ) 作为 搜索策略 ( 3 ) 以赋值决策变量 ( 从决策变量所对应的值域中选择一个值赋给该变 量)作为分枝的目的 ( 4 ) 以决策变量值域和约束条件之间的一致性检验与记录每个决策变量 目 前值域的状态为每个分枝节点的必要工作 ( 5 ) 以遇到死节点 ( s e a d e n d n o d e )作为换枝检验的准则 北京交通大学硕士学位论文 由于每个分枝节点记录每个决策变量的目 前值域状态，所以分枝节点 又可称为一个状态节点 ( s t a t e n o d e ) 。决策变量值域和约束条件之间的一 致性检验指的是新赋值变量与己赋值变量间的一致性;死节点指的是在决 策变量值域和约束条件间 进行一致性检验时若发生上述不一致现象则为一 个死节点;反之，则为一个分枝节点，能再进行分枝。换枝检验指的是因 遇到一死节点而回溯至此死节点的前一个分枝节点，并从此状态节点选择 另一个分枝进行搜索。 b t算法的运算流程是根据 d f s准则，依序地扩充 ( e x t e n d )一个部 分解 ( p a r ti a l s o l u t i o n ) ， 直到找到一个可行解为止。 若在扩充的过程中 遇 到死节点，则换枝的动作立即回溯至此节点的前一个分枝节点，以 进行另 一个分枝搜索。其中的扩充指的是从未赋值变量中，选择一个变量作为新 赋值变量，并从此新赋值变量的值域中选择一个值 ( v a l u e ) 作为此变量的 初始化值 ( i n i t i a l v a lu e ) . 就算法的搜索效率而言， b t算法比g t算法的执行效率要高的多。因 为从b t算法的运算流程中可以 看到， 当换枝检验发生时， 即表示b t算法 删除了一个不必要的搜索空间。 综上所述， 虽然b t算法比g t算法更加有效， 但是b t算法的运算方 式只能是通过死节点的发生而减少部分的搜索空间，回溯法 ( b t ) 算法搜 索的时间复杂度仍是变量个数的指数级的形式。尤其是当使用 b t算法求 解复杂度高且问 题规模大的组合优化或约束满足问题时，其效率越发显得 低效。 2 . 2 )一致性算法 一致性检验技术主要是在进行c s p s 求解之前， 对c s p s 的约束条件进 行检验，使其满足一定程度的一致性，以 减少搜索空间，因而减少在搜索 过程中陷入无效空间的可能性。 一致性检验技术主要包括: 节点 一致性 ( n o d e c o n s i s t e n c y ) ， 弧一 致 性( a r c c o n s i s t e n c y ) ， 路径一致 性( p a t h c o n s i s t e n c y ) 。 每 种一致性检验技 术的复杂度不同，越简单的一致性检验技术其运算时间越短，进行搜索所 北京交通大学硕士学位论文 需的空间越大，时间越长;相反，越复杂的一致性检验技术所耗费的运算 时间越长， 但搜索所需的有用空间越小。 每种检验技术都有其适用的范围， 根据不同的情况需选择不同的一致性检验技术。 一致性检验技术可以 在问 题搜索树上的根节点( r o o t n o d e ) 和任何一 个分支节点上使用， 但是使用哪种一致性检验技术，则视问 题的 特性和算 法的设计有关。但是一般情况下，每个节点上都会执行节点一致性和弧一 致性这两种最基本、 最简单的一致性检验技术。 下面简单介绍一下节点一 致性和弧一致性检验技术。 1 节点一致性检验技术 ( n o d e c o n s i s t e n c y ) 节点一致性检验技术是最简单的一致性检验技术。 如果一个 c s p s中 每个变量的 值域中的 值都满足该变量的 一元约束条件， 则表示该 c s p s已 经达到节点一致性的状态。它的算法即 对 c ps中的每个变量的值域删除 无法满足该变量一元约束条件的值。举例如下: 约 束 条 件c 是 : 二 x ; ) 满 足 弧 一 致 性 的 关 系 弧 一 致 性 具 有 方 向 性 ， 即 ( x ; , x 户 满 足 弧 一 致 性 并 不 代 表( x j , x ) 满 足 弧 一 致 性 。 例 如 : c : 二 y , d ( x ) = t1 ,2 ,3 ), d (y ) = tl ,2 ,3 1, 则如果c是弧一致性的， 则d ( x ) = 1 ,2 并且d ( y ) 二 2 ,3 北京交通大学硕士学位论文 2 . 3约束满足问题研究现状 约束满足问题作为人工智能领域的研究方向， 在经过几十年的研究后， 己经出现了很多求解算法， 其中搜索算法作为最终解决方法，在吸收了一 致性算法等新技术后，产生了许多新的 搜索算法。 下面简单介绍一些约束 满足问 题的 一些研究成果3 3 2 3 . 1 系统搜索 系统搜索是指对赋值空间的所有部分进行系统搜索，即遍历问题中的 每个变量。系统搜索的优点在于，如果问题的解确实存在，那么该解就一 定会被找到，对于不可求解问题也可以得到证明。系统搜索法中的测试生 成法和回溯法将已经在前面介绍过，下面介绍其余的几种。 ( 1 ) 回 跳 搜 索( b a c k j u m p in g b m ) 3 回跳策略首先由j . g as c h n i g 在1 9 7 9 年提出， 它的另一个叫 法是相关制 导回溯。它与传统回溯算法不同点在于:在出现死点时，它将回溯若干层 而不是按时间顺序返回到最近的一个节点上。回跳搜索的缺点在于在跳跃 时会丢失一部分有用的信息，造成对系统的影响。 ( 2 ) 动 态回 溯 搜索( 切 w a m ic b a c k t r a c k in g d b ) 4 1 动态回溯搜索在回跳搜索的基础上，避免了回跳的缺点，做了如下改 进:记录冲突发生的原因，根据冲突情况，对变量的赋值顺序进行了重新 排列。避免有用信息的丢失。 ( 3 ) 回 记 搜 索( b a c k m a r k in g b m) 5 7 b m使用函数m a r k ( x , 门记录当m为v时，与x发生冲突的 最远的一 个变量。 数据结构b a c k t o ( x ) 记录最近一次由 于为x赋值而发生回溯的 变 量中最远的一个。b m利用所记录的信息，在m a r k b a c k t o 和两种情况 下，分别对一些情况进行省略。由于使用了附加的数据结构，因此算法的 北京交通大学硕士学位论文 复杂性变大 2 3 )局部搜索 ( 1 ) 爬山 搜 索( h ill c l im b li n g h c ) tb t 爬山 算法是局部搜索算法中比较典型的一种算法。 它从任意状态开始， 向具有最优状态的临近状态移动。临近状态指的是被赋值的变量中任何一 个变量取值的变动。 ( 2 ) 最 小 冲 突搜 索 m i。 一 c o n f l ic t s m c ) l 爬山 搜索中， 临近状态的数量太多， 共有n ( d - 1 ) 个， 。 为变量的个数， d 为变量的可能取值。最小冲突法在选定临近状态时，选择引起冲突的变 量。这样，只需变动该变量的值来得到临近状态，将临近状态的数目降低 到d 一 1 个。 ( 3 ) 禁 忌 搜索( t a b u ) 8 9 1 禁忌搜索的基本原理式采用禁忌列表( t a b u l is t ) 记录已 经被访问 过的 状态，在以后的搜索中，不再访问这部分空间。当然与其还有一定的配套 机制与之协同工作。 2 3 3一致性技术 一致性算法主要包含节点一致性、弧一致性和路径一致性。 此外，还 有一些特殊情况下的一致性算法，如具有单向性的 弧一致性算法以 及由几 种一致性算法结合起来的一致性算法， 如受限路径一致性算法等5 1 1 ( 1 ) 节点 一致性和弧一 致性( n o d e a n d a r c c o n s is t e n c y ) 目 前使用的节点一致性的算法有一种:n c- 1 。 弧一致性算法有七种: ac一1 ac一7。 ( 2 ) 有方向 性的 弧一致性( d i r e c t e d a r c c o n s is t e n c y d a c ) 北京交通大学硕士学位论文 由于弧是具有方向性的， 而某些约束满足问题是没有方向性的。 因此， 造成了a c算法在约束判断上的重复工作。为此，定义具有方向性的弧一 致性为: 对于给定顺序的一组变量，当且仅当i - m (h , t)。 + c )l一 ， 二 s (h )1- 1 ( 3 - 5 ) 由 式( 3 - 5 ) 可知: s ( h ) 越小，m ( h , t ) 越容易呈指数级增长: s ( h ) 越大，m ( h , t ) 越不容易呈指数级增长。 ( 3 ) 变异算子的作用 以基本位变异算子为例进行研究，某一模式被破坏的概率是: 1 一 ( 1 一 p . ) o ( x l 当p m m, : f ( x ) : 各个认知分类的 试题分数之和与用户指定的各认知分类的分数 的误差总和 北京交通大学硕士学位论文 f 3 ( x ) 一 叉儿 ( x ) , 。 为 认 知 分 类 的 个 数 人( x ) 为第i 种认知分类的 分数总和与用户指定的 参数r f , 的误 差，即 y c 3, f j 一 r f yc 3j x j ， 一 r f , 一一 一一 1 x 了.、 儿 c j = 1 , r i = i o , r , # i 1 , x 1 3 = i o , xj3 # i 千记1 一一 护 3 c f 4 ( x ) : 各个难 度等级的 试题分数之和与用 户指定的 各难 度等级n f , 的 误差总和 凡 ( x ) 一 艺.f a l ( x ) , ， 为 难 度 等 级 的 个 数 f 4 i ( x ) 为 第i 种难度等 级的 分数总和与 用户指定的 参 数n f : 的 误 差，即 i x i : 一 n f , c .艺问 - i c , f , 一 n f 一 、，夕 x f4 c , ; ， = e o r c a ; = 书 i o , x,a * f 凡戈 f s 劝: 各个区分度的试题分数之和与用户指定的各区分度分数的 误差 总和 f ( x ) = 艺.f 5 , ( x ) , ， 为 区 分 度 的 个 数 儿( x ) 为 第i 种区 分 度的 分 数总 和与 用 户 指 定的 参 数以 的 误差， 北京交通大学硕士学位论文 c 6 ; 凡一 q f , = 一i c,;x ;7 - qfi 干 1 , x。 = i o rc 魂 . =代_ - l 0 x i s i 凡( x ) : 一 套试卷各 试题的 用时 总和与用 户指定的 考 试时间t 的 误差 f6 (x)一 客 f6i (x)一 州 ， 、 (x) 为 每 道 题 的 答 题 时 间 : ， 即 x i6 f , ( x ) : 一套试卷各试题的 分数之和与用户指定的总分f的 误差 。 (卜 客 ; (卜 f 一 : ，()为 每 道 题 的 分 数 f ,， 即 x , 对于w , 的 取值， 是根据每个约束条 件对生 成一份整体上符 合用户 参数 试卷 的重要程度而 定的。这里根据文献【 1 刀 和经验值 定义 、 _ 社1 0 生 . 生 与.11 。 对 于 组 卷 问 题 来 说 ， 误 差 越 小 越 好 ， 因 此 适 应 度 函 3 ”5 3 一 4一 数的值越小，个体的适应度越高。 4 .2 . 4约束条件说明 本组卷策略的约束条件为 ( 其中二为试卷中试题的总数) ( 1 ) 一份试卷的所有题目的分数总和要等于用户所给的总分数f. yf = i 戈 ， 二 f ( 2 )一份试卷所有题目 答题时间总和要等于用户所给的总时间t. m翻 艺t , = 艺 x ;。 二 t 1 世 !护 二 】 ( 3 ) 章节h 所占 的分数等于用户指定的分数z f 6 ( h = 1 , 2 , . .p ) , p 为章节 北京交通大学硕士学位论文 总数。 s , ( k 艺 c ,;f ,. = z f o r 艺c ,x i， 二 z f 其中 ( 1 , z ; = h : c 、 ， =i t o , z , # h 。 r c , ， 二 1 , x it = h 0 , x , # h ( 4)一 份试 卷 中题 型 k的总 的题 目数等 于 指 定 的题 目数 = 1 , 2 ， 二， 9 为题型总数。 艺c z,s h i = s k 其中:c z ， 二 1 , m, “k 0 , m; * k ( 5 )一份试卷中第1 个认知分类的试题分数比例要等于指定的比例 r f , ( l = 1 , 2 , . .o ) , o 为认知分类的总数 艺c 3i f , = 朋 o r 艺c 3,x ,7 = 期 其中:c 3 i = r ; = l o r c 3 i = 1 , x i3 = 1 o , x ; , * 1 ( 6 )一份试卷中难度等级为b 的试题分数比例要等于指定的比例 n f , ( b = 1 , 2 , . . .w ) , 、 为难度等级的 个数 艺c 4 , f ,. = n f , o r 艺c 4 ;x ;, = n f b 其 中 : q = 1, n ; = bc 4, = or c 4; _o,n ; ;tb 1 , x ;4 = b 0 , 龙4 # b ( 7 )一份试卷中区分度为d的试题分数比例要等于指定的比例 北京交通大学硕士学位论文 q f d ( d = 1 ,2 , . . .g ) , g 为区 分度等级的 个数 艺 c s;f ,. = q f d o r 艺c 5a n = q f d i 司1 =1 rles之lesl - q 1 , q ; = d or 0 , 2 #d 1 , x , = d 0 , x ;, # d rlwe、eel 一- 几 4 .3遗传算法设计 本节阐述了混合策略遗传算法的设计及其运算过程。首先将遗传算法 的运算过程以下图4 . 1 表示，在4 .3 .7 节对每一个步骤做详细说明。 开始 酬工奴 用户轴入初始奋数 定义适应度函数为所有组 卷参数的借权误差最小 变异 是 件止2日 条终、. 对狡色体进行编码 终 齿 否 1 1 设y种群的烧棋 产生初始种群 稚据最终护教衰是3 可以抽出一份试均? 否 针算种群中 各 个个体的 场函傲 1 2 进入到修正程序 1 3 择适应度最好的前两个个体 抽皿物出翻佳解 结束 图4 . 1遗传算法详细运算流程图 3 7 北京交通大学硕士学位论文 4 3 1 染色体的编码方式 在用遗传算法求解实际问题的时候，编码的选择是要解决的首要问题， 也是设计遗传算法时的一个重要步骤。编码方法除了决定个体的染色体的 排列形式，还决定了个体从搜索空间的基因型变换到解空间的表现型的解 码方法；另外，编码方法还影响到交叉算予、变异算子等遗传算子的设计 方式和运算方法【3 “。 4 3 1 1 传统编码 若试题库中共有m 道试题，用五，z ：，z 。表示这川道试题，那么组 卷就是从这m 道试题中选出”道试题组成一份试卷，使得适应度函数最小， 表示形式为：只，e ，。若f 为l ，表示该题被选中；f 为0 表示未被 选中。若一份试卷中共有v 道试题，则正，e ，l 中共有n 个1 。 这种编码方式对问题的具体领域的知识要求较少，是一种通用的求解 优化问题的方法。传统二进制编码的遗传算法的通用性必然也带来了它的 另外一个缺点，虽然它能够求解很多领域的问题，但是由于这种算法并没 有针对所要求解的问题进行个性编码，因此其编码长度过长，求解效率低 下，求解精度不高。有时生成一套满足要求的时间超过了人的忍受程度， 或者在约束条件程度较高时，甚至找不到解决方案。 如何根据问题的个性，即根据求解问题的具体特点进行编码，是一个 比较关键的一个步骤。在下面的4 3 1 2 节将会讨论针对组卷问题的特点而 编制出来的一种编码方案。第五章会对混合策略遗传算法的组卷方案和二 进制编码遗传算法以及随机抽卷的性能进行比较。 4 3 1 2 矩阵编码 从4 3 1 1 节二进制编码遗传算法求解组卷问题的运行方式可知，其编 码方式以题目是否从数据库中取出作为染色体中的基因是否为1 还是0 的 依据。因此染色体的长度是一定的，为题库中题目的数量。当题库中题目 北京交通大学硕士学位论文 的数量非常大时，其染色体的编码长度就会很长，严重地影响到遗传算法 的运行效率。而且，传统的二进制编码方法的遗传算予直接作用在试题串 e ，e ，只上，而这个染色体串本身并没有提供有关试题属性的更多信息； 另外抽卷的目标是为了使抽出的题目的各个属性满足用户定义的参数，因 此考虑到将遗传算予直接作用在试题的属性上。将一份试卷中的每个题目 x 。的n 个属性直接表示成x 。= i x u ，x 。，x 。】，则一套试卷中的m 道题目 可以表示成如下所示的一个二维矩阵x ： 口 二工 卫 x 王l x l j x 1 n x i lx i j x i n 。1x 即jx 肿 图4 2n 个属性的矩阵参数编码 其中每- n 表示试题的各个属性，每一行表示一套试卷的中的每个题 目，x 自表示第f 道题目中的第j 个属性，染色体的基因的个数为m h 个。 为了运算的方便，我们仍希望用一维数组的形式来表示。与c 语言中矩阵 在计算机内的存储类似，我们采用行优先或列优先的顺序对这个二维矩阵 进行一维染色体编码。例如采用行优先编码，则以矩阵形式编码的染色体x 可表示为： x = x 1 1 x 1 2 x 1 n x 2 1 x 2 2 x 2 n 爿l x m 2 x h 若采用列优先编码，则染色体x 可表示为： x = x 1 l x 2 1 z ，1 x 1 2 x 2 2 搿。2 h x 2 。x 这两种表示方法各有利弊，但考虑到交叉和变异的概率大小，我们决 定采用第二种编码即列优先编码方法。在4 3 3 节将会重点对遗传算子的设 计进行讨论。 宙 北京交通大学硕士学位论文 对本组卷算法而言，试题属性主要涉及试题的七个属性，分别为( 1 ) 章节，( 2 ) 题型，( 3 ) 知识分类，( 4 ) 难度等级，( 5 ) 区分度，( 6 ) 答题 时间，( 7 ) 分数。因此有m 道题目的一套试卷可以编码下列矩阵x ： 口 至工! 正口王工互 口 x 1 1 x 1 2x 1 3x 1 4x 1 5x 1 6x 17 x 1 lx i 2x i 3x i 4x i 5x i 6x 1 7 lx m 2) ( 3x m 4】( 啊5x m 6x 日7 图4 37 个属性的矩阵参数编码 采用列优先的染色体编码为图4 4 所示： 图4 4 列优先的染色体编码图 4 3 2 初始种群的建立 从4 3 1 节的编码方式上可以看出，一份试卷的所有试题属性组成了一 个染色体，遗传算法是一个群体搜索算法，因此需要产生一定数量的染色 体种群。为了使系统在初始搜索时，对于每一个状态空间( s t a t es p a c e ) 都 有相等的机会，一般要以随机方式产生初始种群。对一个有m n 个基因的 染色体，初始种群的产生方式为从试题库中随机抽题。初始种群的规模， 是种群中所有染色体的数量。初始种群的规模，一般由实际问题的具体性 质决定，它通常关系着算法运算的速度。种群过大会造成搜索效率的降低， 失去遗传算法的功能；种群过小，则会造成种群提早收敛。众多参考文献