大学课表安排问题的PBIL算法[1].pdf

立即下载 作者: 冷月如霜·胡狼
上传时间: 2025-06-26
关键词: 算法 进化 PBIL 大学 过程 浙江 安排 方法 2004 课程
大小 217.4 KB
描述
第 27 卷第 3 期 浙江师范大学学报 (自然科学版) Vol . 27 , No. 3
2004 年 8 月 　　　　　　JOURNAL OF ZHEJ IANG NORMAL UNIVERSITY(Nat . Sci . ) 　　　　　　 Aug. 2004
　　文章编号 :1001250512(2004) 0320257204
大学课表安排问题的 PBIL 算法Ξ
徐云青1 , 　陈建明2
(1. 衢州职业技术学院 ,浙江 衢州 　323000 ;2. 浙江师范大学 信息科学与工程学院 ,浙江 金华 　321004)
摘 　要 :课程表问题是时间表问题中重要的应用内容. 采用一种新的基因编码方法 ,可以更客观地反映大学课
程安排的实际 ,并采用先进的 PBIL 算法进行实验 ,实验的结果表明该算法的可行性和有效性.
关键词 :课程表问题 ;进化算法 ;PBIL 算法
中图分类号 :TP30 　　　　文献标识码 :A
0 　引 　言
课程表安排问题是组合规划中典型的优化决策问题 ,已被证明是 NP 难题[1 ] ,至今为止 ,人们没有
找到求解此问题的精确方法. 20 世纪 90 年代初 ,Colorni 等人首先尝试应用遗传算法解决课程表问题 ,开
创了进化计算在时间表问题中的应用 ,并取得了令人满意的结果. 近几年中 ,国内也有部分学者对此问
题做了许多探索工作[1 ] ,并取得了较好的成果. 但由于问题的复杂性 ,这个问题并没有得到一个完善的
解决方法. 笔者尝试对此问题进行进一步的探讨 ,以求能获得更好的结果.
1 　PBIL 算法描述
PBIL (Population2Based Incremental Learning) 算法是美国卡内基梅龙大学 Baluja 提出的一种进化算
法[2 ] ,它将进化过程由原来的生物进化过程转变为一种学习过程 ,用学习所获取的知识 ———学习概率来
指导产生后代 ,这种概率是整个进化过程信息的积累 ,这样的进化过程产生的后代 ,比起 GA 的双亲基
因重组以及 EP、ES 的单个父代 Gaussian 变异会更优生 ,因而能在许多问题中获得更快的收敛速度和更
好的结果.
设 S 为表示解的长度为 n 的二进制位串 , S i (1 ≤i ≤n) 是 S 的第 i 位 ,在
目录
算法/进化/PBIL/大学/过程/浙江/安排/方法/2004/课程/ 算法/进化/PBIL/大学/过程/浙江/安排/方法/2004/课程/