基于多维编码方案的遗传算法在高校排课系统中的应用硕士论文.pdf

四川师范大学 硕士学位论文 基于多维编码方案的遗传算法在高校排课系统中的应用 姓名 汪晓飞 申请学位级别 硕士 专业 计算机软件与理论 指导教师 王玲 李晓宁 20080406 基于多维编码方案的遗传算法在高校排课系统中的应用 基于多维编码方案的遗传算法 在高校排课系统中的应用 计算机软件与理论专业 研究生汪晓飞指导教师王玲教授 李晓宁副教授 摘要排课问题是典型的多重约束和组合优化问题 并且早在7 0 年代已经 被证明是一个n p 完全问题 遗传算法是一种借鉴生物界自然选择和进化机制发 展起来的自适应随机搜索算法 它具有良好的并行性 通用性 稳定性 是一 种非常有效的解决n p 完全问题的方法 本文将遗传算法应用于求解排课问题 主要进行了以下几个方面研究工作 首先 系统分析了排课问题的各要素及多重约束条件 提出了排课问题的 求解难点和优化目标 并完整设计了排课问题的数学模型 其次 着重分析比较常用的遗传算法编码方案并研究其在排课系统中的应 用 在综合各种编码方案优缺点基础上 设计了一种更适合解决排课问题的多 维编码方案 较之传统编码方案 该编码方案更简单 更高效 更易于理解 并且 根据设计的编码方案 重新设计了与之对应的交叉算子和变异算子 再次 结合排课问题具体数学模型 以v i s u a lc 6 o 为主要开发工具 将 多维编码方案以及与之对应的改进遗传算子应用到排课系统中 设计并实现了 基于上述改进型遗传算法的自动排课系统 最后 以实际排课数据测试了本论文设计的多维编码方案及对应的遗传算 子在实际排课问题中的应用 并对测试结果从时间复杂度和排课结果两方面进 行了性能分析 效果令人满意 关键词 排课问题 遗传算法 多维编码方案 多重约束 基于多维编码方案的遗传算法在高校排课系统中的应用 t h e a p p l i c a t i o no f g e n e t i ca l g o r i t h mba s e do n m u l t i d i m e n s i o nc o d es c h e m eo nc u r r i c u l u m s c h e d u l i n gs y s t e m o f u n i v e r s i t y m a j o rc o m p u t e rs o f t w a r ea n dt h e o r y g r a d u a t ew a n gx i a o f e i s u p e r v i s o r w a n g l i n gl i x i a o n i n g a b s t r a c tc u r r i c u l u m s c h e d u l i n gp r o b l e m i sat y p i c a l p r o b l e m a b o u t m u l t i r e s t r a i n t sa n dc o m b i n a t i o n o p t i m i z a t i o n a n d h a sb e e np r o v e dt ob ea n o n d e t e r m i n i s t i cp o l y n o m i a lc o m p l e t e d n p c p r o b l e mi nt h e19 7 0 s t h eg e n e t i c a l g o r i t h m g a b a s e do nt h eb i o l o g i c a lm e c h a n i s mo fn a t u r a ls e l e c t i o n h e r e d i t g i sa na d a p t i v ea n ds t o c h a s t i cs e a r c ha l g o r i t h m i tc a l lb eh i g h l yi m p l e m e n t e di n p a r a l l e l f o rt h es t a b i l i t ya n dg e n e r a l i t yo fg a g a i so f t e nu s e dt os o l v ec o m l i c a t e d n p cp r o b l e m i nt h i sp a p e rg e n e t i ca l g o r i t h m g a i sa p p l i e dt os o l v ec u r r i c u l u ms c h e d u l i n g f o ra u n i v e r s i t y t h em a i nw o r k sa sf o l l o w s f i r s t l y a l lk i n d so fp o t e n t i a lf a c t o r s m u l t i r e s t r i c t i o n so fc u r r i c u l u ms c h e d u l i n g p r o b l e m a r ed i s c u s s e d w h a t sm o r e t h ed i f f i c u l t i e st or e s o l v et h ec u r r i c u l u m s c h e d u l i n gp r o b l e ma n dt h eo p t i m a lo b j e c ta r er e p r e s e n t e d a n dt h em a t h e m a t i cm o d e l a b o u tc u r r i c u l u ms c h e d u l i n gp r o b l e mi sd e s i g n e d s e c o n d l y s o m ec l a s s i cg ac o d i n gs c h e m e s a sw e l la st h e i ra p p l i c a t i o n si n c u r r i c u l u ms c h e d u l i n gs y s t e ma r ea n a l y z e da n dc o m p a r e di nd e t a i l s b a s e do nt h e i l 基于多维编码方案的遗传算法在高校排课系统中的应用 s t u d i e sa b o u ta l lc o d i n gs c h e m e s s t r e n g t h sa n dw e a k n e s s e s a l li m p r o v e dg e n e t i c a l g o r i t h mf o rs o l v i n gc u r r i c u l u ms c h e d u l i n gp r o b l e m si sp r o p o s e d c o m p a r e dt o t r a d i t i o n a lc o d i n gs c h e m e s t h i ss c h e m ei ss i m p l e r m o r ee f f e c t i v ea n de a s i e rt o u n d e r s t a n d m e a n w h i l e t h e c r o s sa n dm u t a t i o n g e n e t i co p e r a t i o n sa r ea l l c o m p r e h e n s i b l yr e d e s i g n e dt oc o r r e s p o n dt ot h i sc o d es c h e m e t h i r d l y c o m b i n e dw i t ht h em a t h e m a t i cm o d e la b o u tc u r r i c u l u ms c h e d u l e a n a u t o m a t i cc u r r i c u l u m s c h e d u l i n gs y s t e m b a s e do nt h i sm u l t i d i m e n s i o nc o d i n g s c h e m ea n dt h ec o r r e s p o n d i n gg e n e t i co p e r a t i o n si sr e a l i z e do nt h ew i n d o w sp l a t f o r m u s i n gv s i a u lc 6 0 f i n a l l y r e a lc o u r s ed a t ai su s e dt ot e s tt h i sm u l t i d i m e n s i o nc o d i n gs c h e m ea n d t h ec o r r e s p o n d i n gg e n e t i co p e r a t i o n si nt h ea p p l i c a t i o no fr e a lc u r r i c u l u ms c h e d u l i n g p r o b l e m a n dt h er e s u l ti ss a t i s f y i n gi nt h ew a yo ft h et i m ec o m p l e x i t ya n dc u r r i c u l u m s c h e d u l i n gr e s u l t k e y w o r d s c u r r i c u l u ms c h e d u l i n gp r o b l e m m u l t i d i m e n s i o nc o d i n gs c h e m e i i i g e n e t i ca l g o r i t h m m u l t i c o n s t r a i n t s 基于多维编码方案的遗传算法在高校排课系统中的应用 四 r a i n 范大学学位论文 独创性及使用授权声明 本人声明 所呈交学位论文 是本人在导师王坠塾攫 奎壁主副麴握指 导下 独立进行研究工作所取得的成果 除文中已经注明引用的内容外 本论 文不含任何其他个人或集体己经发表或撰写过的作品或成果 对本文的研究做 出重要贡献的个人和集体 均已在文中以明确方式标明 本人承诺 已提交的学位论文电子版与论文纸本的内容一致 如因不符而 引起的学术声誉上的损失由本人自负 本人同意所撰写学位论文的使用授权遵照学校的管理规定 学校作为申请学位的条件之一 学位论文著作权拥有者须授权所在大学拥 有学位论文的部分使用权 即 1 已获学位的研究生必须按学校规定提交印刷 版和电子版学位论文 可以将学位论文的全部或部分内容编入有关数据库供检 索 2 为教学 科研和学术交流目的 学校可以将公开的学位论文或解密后的 学位论文作为资料在图书馆 资料室等场所或在有关网络上供阅读 浏览 fb t 论文作者签名 切 跏g 年年月 日 基于多维编码方案的遗传算法在高校排课系统中的应用 1 引言 1 1 课题背景与研究意义 排课问题又称为时间表问题 t i m e t a b l ep r o b l e m s t t p 它是一个涉及多 因素 如班级 课程 教师 教学资源 时间等 多重约束的组合优化问题 排课问题由于涉及约束众多 内部关系复杂 同时人为要求也较多 因此往往 令教务处管理人员感到棘手 近年来 随着高校扩招力度的加大 各高校都面 临着教室资源紧张的问题 对高校的教务人员来说 短时间内拿出一份统调全 校教学资源的课表是一个很艰巨的任务 随着校园信息化建设的逐步开展 校 园网的普及和校园办公自动化的一步步实现 很多数据可以通过校园网传递 所以根据实际教务工作的需求以及硬件设施的配套进一步完善 全面实现依赖 于计算机的智能排课势在必行 排课问题本质上属于n p 完全问题 此类问题的常用解决方案主要有遗传算 法 贪婪算法 模拟退火遗传算法 蚁群算法 专家系统算法 图论算法等 然而 遗传算法凭借群体搜索策略 群体中个体之间的信息交换不依赖于初始 参数的特点和良好的并行性 通用性 稳定性 成为求解排课问题的主流方法 目前 一些高校虽然采用了自动排课系统 但大多运用传统程序设计思想 排课所用数据与程序结合过于紧密 系统重用性和可扩展性不强 并且 这些 排课系统重点考虑的是一般性排课原则 初排后的课表往往需要针对各种特殊 情形进行人工调整 不能充分体现计算机排课的优越性 本课题着重对当前遗传算法在求解排课问题中还有待提高的领域进行分析 研究 以编码方案为重点突破口 设计一种改进的遗传算法来解决排课问题 并实现一个基于该改进算法的自动排课系统 因此 不论从理论层次还是实用 性分析 都具有较高的研究价值 另外 如何更有效的解决排课问题 对于解 决其它多约束 大规模的时间问题也具有重要意义 1 2 排课问题研究现状 2 0 世纪5 0 年代末 国外就有人开始研究课表编排问题 1 9 6 3 年c c g o t l i e b 基于多维编码方案的遗传算法在高校排课系统中的应用 在文章 t h ec o n s t r u c t i o no f c l a s s t e a c h e rt i m e t a b l e s i l j 中提出了时间表问题 的数学模型 它标志着关于时间表这一课题的研究正式跨入了庄严的科学殿堂 但由于在实践中遇到的许多困难 使人们对时间表问题的求解是否存在产生了 疑问 4 0 多年来 人们对课表问题的计算机解决方法做了许多尝试 其中 课 表编排的整数规划模型 2 将问题归结为求一组0 1 变量的解 但是其计算量非常 大 1 9 7 6 年s e v e n 在论文 o nt h ec o m p l e x i t yo ft i m e t a b l ea n dm u l t i c o m m o d i t yf l o wp r o b l e m s 3 j 中 第一次证明了时间表问题是n p 完全问题 正 式确立了时间表问题的学术地位 把对时间表制定的复杂性认识提高到了理论 高度 这虽然回答了计算机制定时间表在实践中遇到困难的原因 但同时等于 宣布计算机编排时间表问题无法实现 因为计算机难解性的理论研究指出 现 代计算机尚未找到解决n p 完全问题的多项式算法 另外 b o n d y 于1 9 7 6 年提 出了一个简单的排课表问题 将问题归结为一个图的边染色问题 并且对提出 的简单排课表问题给出了一个算法 4 j 此后关于这一课题的研究大多离开理论研 讨的轨道而转向经验方式 这使8 0 年代的许多时间表制定系统缺乏普适性 进入2 0 世纪9 0 年代 印度v a s t a p u r 大学管理学院的a r a b i n d at r i p a t h y t 5 1 加拿大m o n t r e a l 大学的j e a na u b i n 和j a c q u e sa f e r l a n d 以及c h a r l e sf l e u t e n t 等 都对时间表问题进行了研究 a r a b i n d at r i p a t h y 的工作是以 人 为单位进行时 间表编排 他运用拉格朗日松弛法和分支定界技术求解 这种方法的缺点是为 了减少变量的个数 人为造成科目间的冲突 j e a n a u b i n 研究了研究生时间表问 题 他采用多重课组的方法来处理冲突 即根据学生选课的矛盾情况 将人数多 的课程在一星期内开多次 j a c q u e s a f e r l a n d 等人则把排课表问题分成两个子问 题 时间表问题和分组问题 在时间表问题中 根据学生注册情况 教师和教 室的可利用情况形成一个主时间表 对于选课人数较多的课程 一个星期要分 成几个时间段来上 分组问题就是将学生分给各个时间段 两个问题相关联 通过惩罚因子来构造启发函数 他们研制的s a p h l r 课程调度决策系统分为数 据处理 自动优化 交互优化等几个模块 该系统解决矛盾的主要方法也是采 用多重课组 这与西方的教学管理体制是不可分的 另外一批学者还将模拟退 火算法 s i m u l a t e da 1 1 l l e a l i n g 应用到时间表问题的研究中 6 7 模拟退火算法是 k i r k p a t r i c k 等人于1 9 8 3 年首次提出的 它是人们从自然界固体退火过程中得到 2 基于多维编码方案的遗传算法在高校排课系统中的应用 启发并从中抽象出来的一种随机优化算法 模拟退火算法用于求解优化问题的 出发点是基于物理中国体物质的退火过程与一般优化问题之间的相似性 在对 固体物质进行退火处理时 常常先将它加温使其粒子可自由运动 以后随着温 度的逐渐下降 粒子逐渐形成低能态晶格 若在凝结点附近的温度下降速率足 够慢 则固体物质定会形成最低能量的基态 优化问题也存在类似过程 模拟 退火算法被用来解决许多实际应用中优化问题 取得了不错的效果 但用其解 决排课问题 现在仍处在模型实验阶段 还有许多问题需要解决 国内对排课问题的研究开始于2 0 世纪8 0 年代初期 1 9 8 4 年 林漳希和林 尧瑞 8 1 在 清华大学学报 上发表了在该课题上的实验性研究成果 接着当时的 南京工学院 大连理工学院等高等院校都相继开展了这方面的研究工作 国内 其他一些高等院校也进行了很多相关软件的开发研制工作 例如 西南交通大 学在分析高校课表编排所遵循的基本原则和模糊性原则的基础上 提出以课元 相关运算和课元的候选时空片计算为核心的计算机排课算法1 9 j 武汉大学分析了 排课问题的数学模型 提出利用回溯算法进行计算机处理的算法思想 l 叫 中南 民族大学在比较了各种不同算法的基础上提出了一种使用局部杂交算子的演化 算法 并采用矩阵编码方案实现了排课表问题求解 l u 山东科技大学针对传统 回溯法在求解排课问题中的不足 提出了利用动态规划的算法解决策略 l2 j 东 南大学利用遗传算法建立了排课问题数据模型 定义一个四维的染色体编码方 式 通过切片算子对传统遗传算法进行局部优化 l 驯 西安交通大学提出了针对 课程表问题的一种基于概率型启发式算法 h a 的混合模拟退火算法 该算法进 一步优化克服了启发式算法不具有全局收敛性的缺点1 1 4 延边大学根据高校课 程表的制作特点 设计了计算机自动排课的数据结构与算法 l 别 沈阳电力高等 专科学校研制了基于c 1 l e n t s e r v e r 的开放式智能排课系纠1 6 j 山西大学在总 结排课工作经验的基础上提出了一种解决问题的形式化描述 并在这种想法上 实现了基于知识推理的排课系统 i7 等等 在国内高校排课系统中 大连理工大学是从事此类软件系统开发较早的单 位 1 9 8 7 年该校开发了 教学组织管理及课程调度系统 1 0 0 版本 并于1 9 8 9 年通过了省级科技成果鉴定 这一系统是国内类似系统中出现比较早的 相对 比较成熟的作品 之后 他们在 教学组织管理及课程调度系统 1 o o 版本的 基于多维编码方案的遗传算法在高校排课系统中的应用 基础上 1 9 9 0 年 又推出 教学组织管理及课程调度系统 2 o o 版本 1 9 9 2 年推出 教学组织管理及课程调度系统 2 0 1 版本和安排考试补考的 考试调 度系统 即二合为一的 教学调度系统 1 9 9 4 年推出了 教学调度系统 2 2 0 版本 1 9 9 8 年推出了在w i n d o w s 下运行的3 0 0 版本 现在在各高校中 使用比较多 反映较好的除了大连理工大学开发的系统外 还有清华大学开发 的 综合教务排课系统 以及北京大学开发的一套比较新的排课管理系统 1 3 遗传算法研究现状及特点 1 3 1 遗传算法研究现状 2 0 世纪纪6 0 年代 j o h nh o l l a n d 教授和数位博士受到生物模拟技术的启 发 认识到自然遗传可以转化为人工遗传算法 g e n e t i ca l g o r i t h m g a 1 9 6 2 年 j o h nh o l l a n d 提出了利用群体进化模拟适应性系统的思想 18 引进了群体 适 应度 选择 变异 交叉等基本概念 1 9 6 7 年 b a g l e y t 坶 第一次提出 遗传算 法 一词并发表了第一篇有关遗传算法应用的论文 在其开创性的博士论文中 采用双倍体编码 发展了与目前类似的复制 交换 突变 显性 倒位等基因 操作 与此同时 r o s e n b e r g 2 0 在博士论文中进行了单细胞生物群体的计算机仿 真研究 并发展了自适应交换策略 c a v i c c h i o 2 1 1 1 9 7 0 年研究了基于遗传算法的 子程序选择和模式识别问题 并提出了以预选择策略保证群体多样性 对遗传 算法参数进行中心控制的方法 同年 w e i n b e r g 2 2 研究了生物体的计算机仿真 并提出运用多层遗传算法来实现遗传算法的参数自优化 1 9 7 2 年 f r a n t z l 2 3 的 博士论文中研究了许多新的问题 如基因非线性 异位显性 现象 基因迁移操 作及多点交换操作等 由于没有设计出诸如g a d e c e p t i o n 2 4 1 之类合适的非线性 优化问题 实验结果并不具备说服力 这一年 b o s w o r t h f o o 和z e i g l e r 2 5 开 创性地采用一个基因一个参数的方法 并把相应的基因操作改成适合实数操作 的形式 1 9 7 5 年遗传算法发展史上树立了两块里程碑 一是h o l l a n d 出版了经 典著作 2 6 a d a p t a t i o ni nn a t u r ea n da r t i f i c i a ls y s t e m 该书详细阐述了 遗传算法的理论 并为其奠定了数学基础 发展了一整套模拟生物自适应系统 的理论 二是d e j o n g 完成了具有指导意义的博士论文 2 7 a na n a l y s i so f t h e 4 基丁二多维编码方案的遗传算法在高校排课系统中的应用 b e h a v i o ro fac l a s so fg e n e t i ca d a p t i v es y s t e m 文中做了大量严格的有 关模式定理的实验 给出了明确的结论 并建立了著名的d e j o n g 五函数测试平 厶 口 进入8 0 年代 神经网络 机器学习和遗传算法等从生物系统底层模拟智能 的研究重新复活并获得繁荣 2 引 g o l d b e r g 在1 9 8 3 年的博士论文中第一次把遗传 算法用于实际的工程系统 煤气管道的优化 从此 遗传算法的理论研究更 为深入和丰富 应用研究更为广泛和完善 从1 9 8 5 年起 遗传算法及其应用国 际会议 2 9 每两年召开一次 有关人工智能的会议和刊物上大多有遗传算法的专 题 g o l d b e r g 的课本 3 0 及其他学者的专著 2 6 3 1 3 2 1 的出版有力地推动了遗传算法 的传播 进入9 0 年代 由于遗传算法能有效地求解属于n p 类型的组合优化问题及 非线性多模型 多目标的函数优化问题 从而得到了多学科的广泛重视 一些 学者也认识到求解复杂问题最优解是不现实的 故而寻求满意例3 3 l 而遗传算 法凭借群体搜索策略 群体中个体之间的信息交换不依赖于初始参数的特点和 良好的并行性 通用性 稳定性 全局优化等优点 成为求解复杂问题的最佳 工具 随着遗传算法的不断深入和发展 关于遗传算法的国际学术活动越来越多 遗传算法已成为一个多学科 多领域的重要研究方向 遗传算法在求解复杂问题时有许多其他算法无法媲美的优点 对目标函数 及约束既不要求连续 也不需要可微 仅要求该问题能计算即可 具有良好的 并行性 很强的通用性 良好的全局优化和稳定性 对于传统优化方法无法或 很难解决的非线性 不可微分问题 遗传算法都能很好的解决 并且 遗传算 法提供了一种求解复杂系统优化问题的通用框架 它不依赖于问题的具体领域 对问题的种类有很强的鲁棒性 所以 随着对遗传算法研究的不断深入 有关 遗传算法的各种应用研究进一步成熟和发展 其应用领域也愈加广泛 遗传算 法的主要应用领域包括 3 4 函数优化 组合优化 生产调度问题 自动控制 机器人学 图像处理 人工生命 遗传编程 机器学习 数据挖掘等 其中 函数优化是遗传算法的经典应用领域 也是对遗传算法进行性能评 价的常用算例 很多人构造出了各种各样的复杂形式的测试函数 有连续函数 基于多维编码方案的遗传算法在高校排课系统中的应用 也有离散函数 有凸函数也有凹函数 有低维函数也有高维函数 有确定函数 也有随机函数 有单峰值函数也有多峰值函数等 用这些几何特性各具特色的 函数来评价遗传算法的性能 更能反映算法的本质效果 对于一些非线性 多模型 多目标的函数优化问题 用其他优化方法较难 求解 而遗传算法却可以方便地得到较好的结果 随着问题规模的增大 组合 优化问题的搜索空间也急剧扩大i 有时在目前的计算机上用枚举法很难或甚至 不可能求出其精确最优解 对这类复杂问题 人们已意识到应把主要精力放在 寻求其满意解上 而遗传算法是寻求这种满意解的最佳工具之一 实践证明 遗传算法已经在求解旅行商问题 背包问题 装箱问题 布局优化 图形划分 问题等各种具有n p 难度的问题上得到成功的应用 生产调度问题在很多情况下建立起来的数学模型难以精确求解 即使经过 一些简化之后可以进行求解 也会因简化得太多而使得求解结果与实际相差甚 远 目前在现实生产中主要是靠一些经验来进行调度 现在遗传算法己成为解 决复杂调度问题的有效工具 在流水线生产间调度 生产规划 任务分配等方 面 遗传算法都得到了有效的应用 在自动控制领域中有很多与优化相关的问题需要求解 遗传算法已在其中 得到了初步的应用 并显示出良好的效果 例如用遗传算法进行航空控制系统 的优化 使用遗传算法设计空间交换控制器 基于遗传算法的模糊控制器的优 化设计 基于遗传算法的参数辨识 基于遗传算法的模糊控制规则的学习 利 用遗传算法进行人工神经网络的结构优化设计和权值学习等 都显示出了遗传 算法在这些领域中应用的可能性 机器人是一类复杂的难以精确建模的人工系统 而遗传算法的起源就来自 于人工自适应系统的研究 所以 机器人学理所当然地成为遗传算法的一个重 要应用领域 例如 遗传算法已经在关节机器人运动轨迹规划 机器人逆运动 学求解 细胞机器人的结构优化和行为协调 机器手臂系统 3 5 3 6 和机器人路径 规划 3 7 3 8 等方面得到研究和应用 图像处理是计算机视觉中的一个重要研究领域 在图像处理过程中 如扫 描 特征提取 图像分割1 3 9 3 7 等不可避免地会存在一些误差 从而影响图像的 效果 如何使这些误差最小是计算机视觉达到实用化的重要要求 遗传算法在 6 基于多维编码方案的遗传算法在高校排课系统中的应用 这些图像处理中的优化计算方面找到了用武之地 目前己在模式识别 包括汉字 识别 图像重建 4 0 1 图像恢复 图像边缘特征提取等方面得到了应用 人工生命是用计算机 机械等人工媒体模拟或构造出的具有自然生物系统 特有行为的人造系统 自组织能力和自学习能力是人工生命的两大主要特征 人工生命与遗传算法有着密切关系 基于遗传算法的进化模型是研究人工生命 现象的重要基础理论 虽然人工生命的研究尚处于启蒙阶段 但遗传算法已在 其进化模型 学习模型 行为模型 自组织模型等方面显示出了初步的应用能 力 并且必将得到更为深入的应用和发展 人工生命与遗传算法相辅相成 遗 传算法为人工生命的研究提供一个有效的工具 人工生命的研究也必将促进遗 传算法的迸一步发展 1 9 8 9 年 美国s t a n d f o r d 大学的k o z a 教授发展了遗传编程的概念 其基本 思想是 采用树型结构表示计算机程序 运用遗传算法的思想 通过自动生成 计算机程序来解决问题 虽然遗传编程的理论尚未成熟 应用也有一些限制 但它已成功地应用于人工智能 机器学习等领域 目前公开的遗传编程实验系 统有十多个 例如 k o z a 开发的a d f 系统 w h i t e 开发的g p e l s t 系统等 学习能力是高级自适应系统所具备的能力之一 基于遗传算法的机器学习 特别是分类器系统 在很多领域中都得到了应用 例如 遗传算法被用于学习 模糊控制规则 利用遗传算法来学习隶属度函数 从而更好地改进了模糊系统 的性能 基于遗传算法的机器学习可用来调整人工神经网络的连接权 也可用 于人工神经网络结构优化设计 模糊控制器设计 模糊神经网络设计 分 类器系统也在学习式多机器人路径规划系统中得到了成功的应用 数据挖掘是近几年出现的数据库技术 它能够从大型数据库中提取隐含的 先前未知的 有潜在应用价值的知识和规则 许多数据挖掘问题可看成是搜索 问题 数据库看作是搜索空间 挖掘算法看作是搜索策略 因此 应用遗传算 法在数据库中进行搜索 对随机产生的一组规则进行进化 直到数据库能被该 组规则覆盖 从而挖掘出隐含在数据库中的规则 s u n i l 已成功地开发了一个基 于遗传算法的数据挖掘工具 利用该工具对两个飞机失事的真实数据库进行了 数据挖掘实验 结果表明遗传算法是进行数据挖掘的有效方法之一 9 0 年代初期 c o l o m i 4 3 j 等人首先尝试应用遗传算法来解决排课问题 引进 基于多维编码方案的遗传算法在高校排课系统中的应用 了矩阵表方案及相应的交叉 变异算子 后来c o l o m i 删又将其成功地应用到了 意大利米兰市的一所规模较大的学校中 b u r k e 4 5 对将进化算法分阶段用于排课 问题做了初步的研究 得到一些颇有价值的成果 c h upc 和b e a s l e y 对一般的 排课问题使用了遗传算法进行求解 4 6 1 他们着重于遗传算法的全局最优解的搜 索能力 避免了问题的局部最优解 日本的s i g e r u 用具有控制约束的遗传算法 优化了教室的合理利用 解决了在教室较少的情况下 如何对教师进行合理的 分配 47 1 p h i l i p p i n e s 的h os u n gc l e e 使用遗传算法对p h i l i p p i n e s 大学的数学学 院时间表问题进行了求解 4 引 蒲保兴 4 9 在论文中提出基于遗传算法的 动态罚 值权定标方法 和 分块遗传策略 解决排课问题 朱冠宇掣5 0 j 在论文中分析 了中学课程情况 采用一种三维编码方式及相应的遗传算子构成的遗传算法求 解中学课表安排问题 业宁等在论文中提出并实现了一种高校自动排课算法 利用遗传算法建立数据模型 定义一个四维的染色体编码方式和包含学生人数 教室座位 特殊课程 教师 班级 一门课的时间间隔等因素的适应度函数 通过切片算子 生成指定要求的基因型个体 用交叉算子和变异算子对基因型 个体进行运算 再利用选择算子选择适应度函数值较高的染色体编码方案 最 后对优化的染色体按指定方向切片 生成教师课表 学生课表和教室课表 1 3 2 遗传算法特点 遗传算法是基于自然选择和基因遗传学原理的搜索算法 它将 优胜劣汰 适者生存 的生物进化原理引入待优化参数形成的编码群体中 按照一定的适 应度函数及一系列遗传操作对各个体进行筛选 从而使适应度高的个体被保留 下来 组成新的群体 新群体包含上一代的大量信息 并且引入了新的优于上 一代的个体 这样周而复始 群体中各个体适应度不断提高 直至满足一定的 极限条件 此时 群体中适应度最高的个体即为待优化参数的最优解 正是由 于遗传算法独特的工作原理 使它能够在复杂空间进行全局优化搜索 并且具 有较强的鲁棒性 另外 遗传算法对于搜索空间 基本上不需要什么限制性的 假设 如连续 可微等 与常规优化算法相比 遗传算法有以下特剧5 i 1 遗传算法是对参数的编码进行操作 而非对参数本身 遗传算法首先基 基于多维编码方案的遗传算法在高校排课系统中的应用 于一个有限的字母表 把优化问题的自然参数集编码为有限长度的字符串 优 化过程的第一步是把参数编码为有限长度的字符串 通常是二进制字符串 随 机生成n 个字符串组成初始群体 对群体中的串进行遗传操作 直至满足一定 的终止条件 求得的最终群体中适应度最大的字符串对应的参数即为所求解 遗传算法是对一个参数编码群体进行操作 这样提供的参数信息量大 优化效 果好 2 遗传算法是从许多点开始并行操作 而非局限于一点 因而可以有效地 防止搜索过程收敛于局部最优解 3 遗传算法通过目标函数来计算适应度 而不需要其他推导和附加信息 从而对问题的依赖性较小 4 遗传算法的寻优规则是由概率决定的 而非确定性的 5 遗传算法在解空间进行高效启发式搜索 而非盲目地穷举或完全随机搜 索 6 遗传算法对于待寻优的函数基本无限制 它既不要求函数连续 也不要 求函数可微 既可以是数学解析式所表达的显函数 也可以是映射矩阵甚至是 神经网络等隐函数 因而应用范围较广 7 遗传算法具有并行计算的特点 因而可通过大规模并行计算来提高计算 速度 8 遗传算法更适合大规模复杂问题的优化 9 遗传算法计算简单 功能强 1 4 排课问题常用解决方案及遗传算法优势 1 4 1 排课问题常用解决方案 从1 9 6 2 年g o t l i e b 提出第一个排课问题的数学模型提出之后 人们对排课 问题的算法作了许多探索 但由于排课问题是n p 完全问题 并且易受具体情况 的影响 大多数求解结果都不理想 下面是一些常用解决方案简介 5 2 1 1 遗传算法 g e n e t i ca l g o r i t h m 简称g a 遗传算法借鉴生物界自然选择和自然遗传机制 使用群体搜索技术 适用 9 基于多维编码方案的遗传算法在高校排课系统中的应用 于处理传统搜索方法难以解决的复杂和非线性问题 经过近4 0 年的发展 遗传 算法在理论研究与实际应用两方面都取得了巨大的成功 许多人通过对遗传算 法进行改进和优化 较好地解决了课程表编排问题 2 贪婪算法 聂小东 5 3 在论文中提出了基于贪婪算法的排课系统 该系统对于贪婪准则 的确定还是建立在人工排课考虑的因素上 没有充分考虑提高课表质量的其它 人文因素 并且目前实现的排课系统只是满足用户现在的排课要求 还没有实 现真正的智能排课 有待进一步的研究 3 模拟退火遗传算法 任学惠等 5 4 在论文中提出了利用模拟退火遗传算法解决课程表安排优化问 题的算法 这种方法结合了遗传算法和模拟退火算法的优点 使得两种算法的 搜索能力得到相互补充 克服了遗传算法中参数选择不当易陷入 早熟 和模 拟退火算法对 退温 过程的限制条件苛刻的缺点 可以避免搜索过程陷入局 部最优 4 蚁群算法 张林 5 5 在论文中采用了蚁群算法来解决课程表问题 蚁群算法是通过模拟 蚁群在觅食过程中寻找最短路径的方法来求解优化问题 目前在旅行商问题等 组合优化问题中有成功的应用 蚁群算法目前有a s a c s m m a s 三种常用 的模型 但是在排课问题上这三种蚁群算法都有易于陷入局部最优解的缺陷 从而使得排课问题的求解过程过早地停止 5 增强学习算法 郭方铭 5 6 5 6 在论文中给出了基于增强学习算法的课表编排模型的实现思路 增强学习算法是一种机器学习的框架 其智能体通过一系列的活动影响其外部 环境 并收到活动的回报 智能体通过状态映射到动作来选择能获得最大回报 的动作 增强学习算法的优点 a 在应用增强学习算法编排课表时 不需要对 排课问题做过多的分析 也就是说 增强学习算法避开了课表编排问题本身的 复杂性 b 排课智能体能在一定程度上自主学习并决策 大大降低了人工排课 的劳动强度 而且在安排课表的同时也在进 步学习人工决策的结果 系统的 性能得以逐步提高 但是由于排课问题的复杂性 该算法的运用中还存在一些 1 0 基于多维编码方案的遗传算法在高校排课系统中的应用 问题有待进一步的改进 a 排课任务的顺序是该算法中的一个关键问题 不同 的顺序对应不同的学习效果 因而 如何针对不同的教学情况提供尽可能合适 的排序原则是一个有待改进的问题 b 系统的排课是在学年学分制体系下 按 专业教学计划进行安排的 没有考虑学分制选课模式下的排课 如何在学分制 选课模式下根据选课情况对教室资源的需求量进行估算以提高教室利用率也是 有待深入研究的问题 6 专家系统算法 胡小兵等 5 7 l 在论文中所用的专家系统算法的特色是实现了知识与程序的分 离 该算法把知识集中在知识库中 事实数据集中在综合数据库中 程序则构 成推理机 排课的数据 原则与程序分别对应专家系统的综合数据库 知识库 和推理机 排课数据 排课原则从推理程序中分离出来 便于进行修订和补充 排课算法重点解决逻辑推理 使得程序结构简练清晰 便于维护 但逻辑推理 过程比较繁琐 7 图论算法 胡顺仁等 5 8 在论文中针对排课问题的现状 将教师 班级 教室之间的关 系转化为集合关系 提出了图论的观点 并据此将排课问题进行数学建模 把 教师 班级 教室 每节课等元素转换成图形元素之间的匹配关系 提出了较 为可行的排课算法 然而 图的染色问题本身是n p h a r d 完全问题 因此算法 的实现比较繁琐 8 其它算法 还有许多学者 从资源匹配算法 5 9 分支限界算法 关联规则算澍6 分组逐次算法 引 多阶段自动排课算法 m a c a 算法 6 引 并行机任务调度算法 6 4 矩阵编码方案 智能回溯 边着色 分层结构模型等不同的角度给出了其 它许多求解排课问题的算法 许多方案具有一定的独创性 给研究同类问题提 供了借鉴作用 但这些方案中大部分都是只针对特定的办学单位和特定的教学 资源 有很大的局限性 基于多维编码方案的遗传算法在高校排课系统中的应用 1 4 2 遗传算法解决排课问题优势 通过分析比较上述各算法特点 可以认为用遗传算法解决排课问题是一种 较好的选择 主要原因有如下几点 1 遗传算法是高效智能算法 遗传算法在确定了编码方案 适应度函数及 遗传算子以后 算法利用演化过程中获得的信息自行组织搜索 适应度大的个 体具有较高的生存概率 适应度小的个体则具有较低的生存概率 遗传算法是 具有 潜在学习能力 的自适应搜索技术 2 遗传算法具有群体搜索策略 群体中个体之间的信息交换不依赖于初始 参数的特点和较好的通用性 稳定性 3 遗传算法具有并行性 由于遗传算法采用种群的方式进行搜索 从而可 以同时搜索解空间内的多个区域 并相互交流信息 这种搜索方式使得它虽然 每次只执行与种群规模成比例的计算 而实际上 据g o l d b e r gd e 的推算进行了 o n 3 次的有效搜索 这使得遗传算法能以较少的计算获得较大的收益 4 遗传算法在解决排课问题这类多重约束的组合优化问题时 能够得到基 本满足各种需求的课表 5 遗传算法解法能够较好地解决各级各类学校对课表编排的特殊要求 使 复杂的排课约束条件能够通过评价函数值和适应度函数值的方式得以量化 这 有利于解决类似于排课这种模糊的不确定问题 6 遗传算法易于使用v i s u a lc v i s u a lb a s i c 等常用开发工具实现 而 掌握了这些开发工具的计算机 或电子信息技术 教师较为普遍 1 5 现有基于遗传算法的排课系统常见不足 与其他常用排课问题解决方案相比较 遗传算法解决排课问题具有较大的 优势 并且 随着遗传算法不断成熟和完善 遗传算法在解决排课问题上也取 得了较好的成果 但综合考虑求解情况 仍存在以下几点不足 1 编码方案 一种较好的遗传算法编码方案 不仅能够反映解空间完备并 无歧义的遗传信息 而且操作应当尽量简单 从而可以快速地进行遗传操作和 基于多维编码方案的遗传算法在高校排课系统中的应用 适应度评定 继而缩短算法的整体收敛时间 然而在现有的应用中 采用的编 码大多都是传统的编码方案 并不能很好地反映排课问题中更多的实际情况 而且操作不方便 2 遗传算子 遗传算子主要包括选择算子 交叉算子和变异算子 遗传算 法在解决排课问题时 遗传算子的设计与编码方案的设计同等重要 通常情况 下 不同的编码方案应该有相对应的遗传算子与之对应 并且 遗传算子的设 计好坏直接影响到整个遗传算法的执行效率 但是 现有的应用中 采用的遗 传算子很多都是传统的遗传算子 在具体操作 表现排课问题上并不能取得很 好的效果 因此 不论从时间还是空间角度上分析 效率都不太令人满意 3 多重约束条件 由于各自的研究背景不同 他们往往考虑的只是排课问 题的一般情况 有些甚至是理想状态的排课 对于排课中更多的约束条件未予 以考虑 4 排课求解规模 排课问题的求解规模普遍偏小 使得实用程度较低 很 难在学校中展开实际应用 5 求解目标 在现有的应用中 处理的都是单目标问题 即使有多个目标 也往往线性地聚合成单个目标进行处理 这样求得的往往是一个非劣解 而忽 略了一组非劣解1 6 5 i 1 6 论文研究内容和目标 论文研究的目标是通过在排课问题中充分应用改进的更为高效的遗传算法 编码方案及相应的遗传操作 更好的提高排课速度 教学资源利用率和排课质 量 实践证明 遗传算法求解组合优化中的n p 完全问题非常有效 已有人尝试 利用遗传算法求解课程表编排问题 但都存在一些缺陷 因此 通过改进遗传 算法求解诸如课程表编排这类n p 完全问题 可以为更高效地解决其他类似的时 间表问题提供理论依据 为实现上述目标 达到预期效果 本文主要进行以下几方面的研究工作 1 系统分析排课问题的各要素及多重约束条件 准备提出排课问题的求解 基于多维编码方案的遗传算法在高校排课系统中的应用 难点和优化目标 完整设计排课问题的数学模型 并着重分析比较常用的遗传 算法编码方案并研究其在排课系统中的应用 在综合各种编码方案优缺点基础 上 从编码方案角度寻求突破口 2 改进遗传算法传统编码方案 设计一种更适合解决排课问题的编码方 案 根据改进的编码方案 重新设计与之对应的交叉算子和变异算子 5 结合排课问题数学模型 以v i s u a lc 6 0 为主要开发工具 将该编码 方案以及与之对应的改进遗传算子应用到排课系统中 设计并实现基于上述改 进型遗传算法的自动排课系统 6 以实际排课数据测试本论文设计的编码方案及对应的遗传算子在实际 排课问题中的应用 从时间