西南交通大学硕士研究生学位论文 第4 页 . 从表 5 可以 看出, - 4 实验组 1 变异概率为0 0) 2〔 . 1,实验组 " ( 0 变异概率 为0 1 . )的测试中, A 遗传算法的效率都较高,当 0 CP 变异概率为 0 2 ( . 时 实验 0 组1) 7,变异概率为0 01( . 0 实验组 1)则效率有了明显的下降. 0 6
究其原因, 一是P过大, 起 C P遗 . 引 人 传算法的 稳定. 不 例如: 在一条由
1 个基因组成的染色体当中, 0 0 当变异概率为0 时, . 就意味着每条染色体在侮 1
次进化操作过程中都平均会有约 1 个基因发生变异, 0 这样大量的变异不仅不能 进化出好的个体,相反会使得每条染色体极不稳定,就很难得到适应度值为 1
的结果 了.
表5 - 4变异概率变化对 C P A 运行效率的影响测试比较表
编号 实脸组 1 2 实挂组 3 1 实脸组 1 6
( 交叉概率 09 .:单位:m ) s
实脸组 7 1
1 2
3 4
5
6
7
8 9
1 0
变异概率:001 变异概率:00 .0 .1 52 18 20 13 2 16 55 36 45 390 43 16 0 34 21 74 15 8 95 33 65 165 09 3 64 73 81 92 2 3 团 386 82 24 4 37 } 293 94 1 18 24 5 」 13 8 21 26 53 55 17 }
平均
! 211 1 0. 63. 1 4 2 6 } 2 3
变异概率: .01 000 13 3 29 8 10 93 182 861 383 64 31 35 6 68 87 8 1 17 98 152 22 0 12 4 266 16 7 13 12 0 . 3 0 98
变异概串:00 .2 98 13 17 8 159 1 14 61 196 73 75 1 00 77 0 68 14 2 302 43 26 479 08 691 93 5 7 81 50.
其二, . 使 全局 难于 P过小 得 搜索 进行. 于P过 或为0 则很 有较 由 .小 , 难 好
的模式产生. 在实际程序中就可能导致某些资源配置不合理或不能被利用.因
此,在教学资源相对紧张的情况下,往往排不出或不易排出课表
55排课质里分析 .
表5 - 5是实验 1 ( sl )的排课结果,分析结果可以看出,此课表满足 7 ul r t e 5 节中的排课原则. . 1 课程尽童的安排在上午,而且多讲次课程分布较为合理. 学生人数少的 课程尽量的占 用小教室,且分布较为 合理, 教室利用率 10 . 0%
西南交通大学硕士研究生学位论文 表5 一排课结果 ( 1, u l 实验 7 r l ) e t s
编 号
1 2
第 41 页
2 3 4 5
5
6 6
7
7 8 9
1 0
1 0 1 1 1 1 1 2 1 3 1 4
教师 课程名称 人数 名称 6 0 画法几何: 徐培强 数字电子技术B 1 0 白天蕊 : 7 数字电子技术B 1 0 白天蕊 : 7 8 0 工程伦理学: 鲍洪刚 3 0 旅游 日语: 毕凌 4 0 日 语口语 2 : 毕凌 4 0 日语口语 2 : 毕凌 6 0 传热学 D : 蔡德源 6 0 传热学 D : 蔡德源 5 计算机控制系统 3 蔡淮 设计: 5 计算机控制系统 3 蔡淮 设计: 8 0 供电系统: 曹保江 0 路基工程 C D A : 3 曹新文 3 0 测量学 B : 岑敏仪 3 0 测量学 B : 岑敏仪 0 工程测量 AI : 3 岑敏仪 0 工程测量 AI : 3 岑敏仪 中国古代文学 3 3 : 0 常健 5 建筑设计基础 A 2 陈大乾
I:
时间 星期二 星期三 星期一 星期五 星期二 星期四 星期一 星期三 星期五 星期三 上午 上午 上午 上午 上午 上午 上午 下午 下午 下午
教室
610 (8) 610 (8) 610 ( ) 8 6 8) (0 1 30 () 3 24) (0 双6) 0 610 (8) 510 (0) 10 () 5
星期五 下午 星期二 星期三 星期一 星期三 星期三 星期四 星期二 星期二 上午 上午 下午 下午 上午 下午 下午 上午
610 ( ) 8
510 ( ) 0 10 () 5 10 () 5 510 ( ) 0 24) ( 0 10 () 5 10 () 5 46) ( 0
1 4
1 4 1 5 1 6 1 6 1 7 1 7
日 语精读 I : 日 语精读 1 : 日 语精读 I : 日 语视听 4 :
英语I : I 英语m: 美学概论: 美学概论;
4 0 4 0 4 0 3 0 2 5 2 5
3 0
3 0
陈动英 陈动英 陈动英 陈动英 陈芳 陈芳 陈国强 陈国强
星期五 星期三 星期一 星期三 星期一 星期五 星期五 星期一
上午 下午 下午 上午 上午 上午 上午 上午
10 () 5 4 ( 印) 40 () 6 30 () 3 30 () 3 《 印) 20 () 4 2 ( 如)
当 然, 测试程序忽略了许多实际的因素, 如教学楼的分布, 教室的分布, 连续两讲课之间 教室的距离等等,因 此惩罚函 数应涉及的内 容还很多, 这样的 排课在实际中的使用还受到很大的约束.但就测试程序所处理的诸多约束条件
西南交通大学硕士研究生学位论文 第4 2 页 来说,都能够方便的转化为惩罚函 数的一个变量, 进而对遗传算法的适应度函 数值产生相应权重的影响.
56时间复杂性分析 .
模式定理规定了遗传算法程序的进化方向, 这里将分析一下C P A 遗传算法 的时间复杂性.由于程序主要是基于随机性和概率上的运算,所以很难确切的 预测程序的运行时间, 但有一点可以 证明,就是随着排课规模的扩大, A 算 CP 法的时间增长规律是按照多项式时间增长,这也是是否成功解决 N P类问题的 关键,以下就来证明这一点. 不妨设原染色体长度为L( 基因个数) 排课规模扩大a , 倍后, 也即是L 增
长到 la 二 .以 ( )L 下分别考虑C P 影响时间 + A中 复杂性的 几个主要方面: 选择,
交叉,变异操作以及适应度计算操作. 1 选择操作: 轮盘赌" , " 选择操作是只与种群大小有关的操作,与染色体 长度无关,因此, L的增长没有增加选择操作的复杂性:
2 交 操作: 先交 概 . 涉及到 群中 首 叉 率P只 , 叉 对种 个体的 择, 染色体 选 与
长度无关,因此对C P A 遗传操作的效率没有影响;对于选中两染色体的交叉, 交叉位置随机,可能是 1 2 , ,…, ,…, 一 中任何位置.设在第i i L1 处进行交
叉, 需重新赋值的 个数有3( i ( 则 基因 x ) 两个交叉 体和一个临时变量 L一 个 染色 需 斌值, (一 ) 故L i 前面的 系数为3, 于交叉位置i 等概率分布在1 2 …, )由 是 , ,
L1 一 中,故需重新赋值的基因个数的期望值是:
1- .a
L 一1
'((' 万. 3L) 一
LL一_- 3 .3 -x 一l 1" L} x -} ; } `
3L 3L x-x
3L
一一
-2
(-) 54
由于交叉操作主要就是处理染色体斌值,由 (4 式( ) 看出,交叉操作需 5 可以 -
进行的操作与 L成正比.因此,当封 因 此,当 排课规模扩大到 ( a 后, 1 )L 需重新赋值 + x
1 ) + 的 因 数 期 值 旦(a三 即时间复杂性为先前的( a倍; 基 个 的 望 是 x+) , l x
Z
3 变异操作: 操作是对个体的 , 变异 每个基因进行概率为P 的 . 变异, 因此