遗传算法研究及其在排课问题中的应用
|
摘要
随着计算机技术的飞速发展，人们已经可以让计算机完成一些过去无法想象的任务。但现代科学理论研究与实践中存在着大量与组合优化，自适应等相关的问题。使用常规方法解决这些问题，除了一些简单的情况之外，人们对于大型复杂系统的优化和自适应问题显得无能为力。
遗传算法借鉴生物界自然选择和自然遗传机制，使用群体搜索技术，尤其适用于处理传统搜索方法难以解决的复杂的和非线性的问题。经过近40年的发展，遗传算法在理论研究与实际应用中取得了巨大的成功，但相对其鲜明的生物基础，其数学基础还是相对不完善的。
本文从遗传算法的基本理论入手，针对基本遗传算法(SGA)不以概率1收敛于最优解的问题，提出了一些改进方法并对其收敛性进行证明。主要有以下几方面工作：
(1)将二进制编码遗传算法的模式定理扩展到由有限整数、字母或取值个数有限的浮点数编码，或它们混合编码的遗传算法范围；
(2)提出最佳个体替换策略遗传算法(RECGA)、优势群体优先策略遗传算法(SCFGA)，对遗传算法进行改进；
(3)使用随机过程理论Markov链对RECGA进行了收敛性分析；
(4)使用泛函分析理论压缩映射原理对SCFGA进行了收敛性分析；
(5)使用遗传算法设计了解决NP类问题(排课问题)的测试程序(CAP)，并根据RECGA对算法进行改进并进行测试。
CAP测试程序的实验结果表明，使用最佳个体替换策略(REC)改进遗传算法明显地提高了算法效率。同时，对RECGA、SCFGA的收敛性证明在遗传算法研究中具有一定的理论意义。
Today witnesses the rapid development of computer technology. Some tasks that were impossible in the past can be accomplished with computer. However, there are still many issues to be tackled with in modern scientific theory research and practice, with regard to Combination & Optimization and self-adaptation etc. Routine methods are quite helpful resolving simple optimization and self-adaptation problems but helpless for complicated large-scale systems.
Genetic Algorithms, based on the biological mechanism of natural selection & heredity and leveraging colony searching technology, is particularly applicable for the resolution of complicated & non-linear problems intractable with traditional searching methods. For nearly 40 years' development, Genetic Algorithms has made great achievements in both theory research and practical applications. However, its mathematical foundation is still incomplete compared with the distinctive and sound biologic foundation.
This paper starts with the basic theory of Genetic Algorithms. Then, some modification methods are advanced and some convergence proofs made, aiming at the problem that the probability of Simple Genetic Algorithm (SGA) converged to optimal solution is less than 1. The major tasks include:
(1) Expand the schema theorem for GA. The schema theorem with binary coding advanced by Professor Holland is expanded to limited integer, letter, floating point numbers the number of which value is limited, and their hybrid coding.
(2) Put forward Replacing by the Excellent Chromosome GA (RECGA), Superiority Colony First GA(SCFGA) and improve the GA;
(3) Make probability convergence analysis of RECGA using the theory of Markov Chain, Random Process;
(4) Make convergence analysis of SCFGA using the principle of Contractive Mapping in functional analysis theory;
(5) Design the test programs (CAP) to resolve NP problems (Course Arrangement) with GAs; Based on RECGA, modify the Arithmetic and then conduct tests.
The experiment result for CAP test programs illustrates that the Genetic
Algorithms becomes more efficient being improved with REG Moreover, the convergence proofs of RECGA and SCFGA are theoretically meaningful in the research of Genetic Algorithms.
遗传算法借鉴生物界自然选择和自然遗传机制，使用群体搜索技术，尤其适用于处理传统搜索方法难以解决的复杂的和非线性的问题。经过近40年的发展，遗传算法在理论研究与实际应用中取得了巨大的成功，但相对其鲜明的生物基础，其数学基础还是相对不完善的。
本文从遗传算法的基本理论入手，针对基本遗传算法(SGA)不以概率1收敛于最优解的问题，提出了一些改进方法并对其收敛性进行证明。主要有以下几方面工作：
(1)将二进制编码遗传算法的模式定理扩展到由有限整数、字母或取值个数有限的浮点数编码，或它们混合编码的遗传算法范围；
(2)提出最佳个体替换策略遗传算法(RECGA)、优势群体优先策略遗传算法(SCFGA)，对遗传算法进行改进；
(3)使用随机过程理论Markov链对RECGA进行了收敛性分析；
(4)使用泛函分析理论压缩映射原理对SCFGA进行了收敛性分析；
(5)使用遗传算法设计了解决NP类问题(排课问题)的测试程序(CAP)，并根据RECGA对算法进行改进并进行测试。
CAP测试程序的实验结果表明，使用最佳个体替换策略(REC)改进遗传算法明显地提高了算法效率。同时，对RECGA、SCFGA的收敛性证明在遗传算法研究中具有一定的理论意义。
Today witnesses the rapid development of computer technology. Some tasks that were impossible in the past can be accomplished with computer. However, there are still many issues to be tackled with in modern scientific theory research and practice, with regard to Combination & Optimization and self-adaptation etc. Routine methods are quite helpful resolving simple optimization and self-adaptation problems but helpless for complicated large-scale systems.
Genetic Algorithms, based on the biological mechanism of natural selection & heredity and leveraging colony searching technology, is particularly applicable for the resolution of complicated & non-linear problems intractable with traditional searching methods. For nearly 40 years' development, Genetic Algorithms has made great achievements in both theory research and practical applications. However, its mathematical foundation is still incomplete compared with the distinctive and sound biologic foundation.
This paper starts with the basic theory of Genetic Algorithms. Then, some modification methods are advanced and some convergence proofs made, aiming at the problem that the probability of Simple Genetic Algorithm (SGA) converged to optimal solution is less than 1. The major tasks include:
(1) Expand the schema theorem for GA. The schema theorem with binary coding advanced by Professor Holland is expanded to limited integer, letter, floating point numbers the number of which value is limited, and their hybrid coding.
(2) Put forward Replacing by the Excellent Chromosome GA (RECGA), Superiority Colony First GA(SCFGA) and improve the GA;
(3) Make probability convergence analysis of RECGA using the theory of Markov Chain, Random Process;
(4) Make convergence analysis of SCFGA using the principle of Contractive Mapping in functional analysis theory;
(5) Design the test programs (CAP) to resolve NP problems (Course Arrangement) with GAs; Based on RECGA, modify the Arithmetic and then conduct tests.
The experiment result for CAP test programs illustrates that the Genetic
Algorithms becomes more efficient being improved with REG Moreover, the convergence proofs of RECGA and SCFGA are theoretically meaningful in the research of Genetic Algorithms.
引文
[1] 王正志．进化计算．长沙，国防科技大学出版社，2000
[2] J Thompson and KA Dowsland. Variants of simulated annealing for the examination timetabling pmblem.[C]Annals of Operations Research.1995
[3] 王小平，曹立明．遗传算法．西安西安交通大学出版社，2002
[4] Holland,J.H.Adaptation in natural and artificial systems:An introductory analysis with application to biology, control,and artificial intelligence. 1~(st) edition,Ann Arbor, MI:The University of Michigan Press, 1975;2~(nd) edition,Cambridge,MA:MIT Press, 1992
[5] 唐飞，滕弘飞，孙治国，王文忠．十进制编码遗传算法的模式定理研究[J]．小型微型计算机系统，2000，21(4)：364-367
[6] 赵舒展．遗传算法研究与应用．浙江工业大学硕士学位论文．2001-12
[7] 周明，孙树东，遗传算法原理及应用．北京，国防工业出版社，2000
[8] Radcliffe N.J. The Aleghra Of Genetic Algorithms.Annals Of Math,&AI,10(1994),339-384.
[9] Rudolph G.Convergence Analysis Of Canonical Genetic Algorithm[J].IEEE Trans Neural Networks, 1994,5(1).
[10] 张恭庆，林源渠．泛函分析讲义．北京大学出版社，北京：1987．
[11] 熊大国．随机过程理论与应用．北京，国防工业出版社，1991
[12] RF Weare.Automated examination timetableling.[D]PhD Thesis,Department of Computer Science,University of Nottingham,UK, June 1995
[13] EK Burke.DG Elliman,and RF Weare.Examination timetabling in british universities-a survey.[e]Proceedings of the 1~(st) International Conference on the Practice and Theory of Automated Timetabling. ICPAT'95,Napier University, Edinburgh,30th Aug-1~(st) Sept 1995
[14] Burke E.K.,Elliman D.G. and Weare R.F.,A University timetabling system based on graph colouring and constraint manipulation.[J]The Journal of Research on Computing in Education, Vol.26,issue 4,1993
[15] Graping Huang,Juan Liu,A Heuristic algorithm to solve timetabling problem.[J]Wuhan University Journal of National Sciences,Vol.42,No.1,71～74,Feb.1996
[16] Boizumanlt P.,Gueret C. and Jussien N.,Efficient labeling and constraint
relaxation for solving time tabling problems.[C]Internationai Logic Programsing Symposium-Workshop on Constraint Languages and their use in Problem Modelling, 116～130,1994
[17] D Johnson,Adatabase approach to course timetabling.[J]Journal of the Opcrational Rcscarch Society, Vol.44,No.5,425～433,Operatinal Research Society, 1993
[18] WL Winston,Operational research:applications and algurithms.2~(nd) ed.,PWS-Kent,Boston,Massachusetts,1991
[19] 王祜民，赵致格．排课表问题中的分组优化决策算法[J]．控制与决策，1999，14(2)：109-114．
[20] Garey M R Johnson D S.Computers and Intractablity. A Gilide to the Theory of NP-Completeness[M].San Francisco CA. Freeman 1979.
[21] MWCarter, GLaporte,and Chinneck.Ageneralexaminationschedulingsystem. (J) INTERFACES,Vol.24,No.3,109～120,May-June1994.
[22] Even,S.,et.al.,On the Complexity of Timetable and Multicomsodity Flow Problems,SIAM Journal on computing,Vol.5,No.4,pp.691-703,1976
[23] Colormi,A.,et.al.,Genctic Algorithms and Highly Constrained Problems:The Time-Table Case,in[121],pp.55-59,1991.
[24] Paechter, B.,et.al.,Two Solutions to the General Timetable Problem Using Evoluationary Mcthods,in[95],1994
[25] FWeare.Automated examination timetabling. [D] PhD Thesis, Department of Computer Science,University of Nottingham,UK,June1995
[26] Burke E.K,Elliman D.G.and Weare R.F.,A University timetabling system based on graph colouring and constraint manipulation.[J]The Journal of Research on Computing in Education,Vol.26,issue 4,1993
[27] D Johnson,A database approach to course timetabling.[J]Journal of the Operational Research Society, Vol.44,No.5,425～433,Operatinal Research Society,1993.
[28] WL Winston. Opcrational research:applications and algurithms.2~(nd) ed.,PWS-Kent, Boston, Massachusetts, 1991.
[29] J Thompson and KA Dowsland. Variants of simulated annealing for the examination timetabling problem.[C]Annals of Operations Research.1995.
[30] Mitchell M.,An Introduction to genetical gorithms.[M] Cambridge. MIT
Press. 1996.
[31] Michalewicz Z. Genetic Algorithms + Data Structures = Evolution Programs. Springer-Verlang, Berlin,1992
[32] Zhengjun Pan,Lishan Kang and Yuping Chen. Evolutionary Computation.[M]Tsinghua University Press. 1998
[33] Mitchell M.,An Introduction to genetic algorithms.[M]Cambridge. MIT Press.1996
[34] 周培德，周忠平，张欢．寻求中国货郎担问题最短回路的多项式时间算法[J]．北京理工大学学报，2000，20(2)：201-204．
[35] 喻摘，凌捷，谢晓峰．用遗传算法求解CTSP[J]．广东工业大学学报，2000，17(3)：52-55．
[36] 毕军，付梦印，周培德．一种适于车辆导航系统的快速路径规划算法[J]．北京理工大学学报，2002，22(2)：188-191．
[37] 姚朝灼．实验回溯问题的算法模版设计[J]．福州大学学报(自然科学版)，2000，28(3)：31-34．
[38] 王潮，宣国荣．人工神经网络求解TSP问题新方法[J]．计算机应用与软件，2001，18(4)：59-65．
[39] 程国忠，张世禄．三个典型问题的回溯算法[J]．四川师范学院学报(自然科学版)，2000，21(2)：187-191．
[40] 付雪峰，何渝．时间优先的中小学课表编排算法[J]．北京工商大学学报(自然科学版)，2002，20(1)：37-40．
[41] 周荣敏，雷延峰．基于遗传算法的最小生成树的参数优化研究[J]，郑州大学学报(工学版)，2002，23(2)：9-12．
[42] 吴浩扬，常柄国，朱长纯，刘君华．基于模拟退火机制的多种群并行遗传算法[J]．软件学报，2000，11(3)：416-420．
[43] 于洋，查建中，唐晓君．基于学习的遗传算法及其在布局中的应用[J]．计算机学报，2001，24(12)：1242-1249．
[44] 张春梅，行飞．用自适应的遗传算法求解大学课表安排问题[J]．内蒙古大学学报(自然科学版)，2002，33(4)：459-464．
[45] 张银明．元素判别值分配法在求解TSP问题中的应用[J]．华侨大学学报(自然科学版)，2002，24(2)：191-197．
[46] 熊伟清，魏平，赵杰熠．用遗传算法求解时间表问题[J]．微电子学与计算机，2001，4：29-31．
[47] 黄干平，姚自珍，张静．使用模拟退火算法解课表问题[J]．武汉大学学报(自然科学版)，2000，46(5)：559-563．
[48] 胡顺仁，邓毅，王铮．基于高校排课系统中的图论问题研究[J]．计算机工程与应用，2002，4：221-222．
[49] 汪红星，康立山，陈硫屏．基于演化算法的一类时间表问题的自动求解[J]．小型微型计算机系统，2000，21(5)：469-470．
[50] 吴金荣．求解课程表问题的分支定界算法[J]．运筹与管理，2002，11(1)：17-22．
[51] 龙一飞，郭文宏．基于知识推理的排课系统[J]．电脑开发与应用，2000，13(6)：35-37．
[52] 洪力奋．基于人工智能原理的大学课表编排模型[J]．合肥工业大学学报(自然科学版)，1999，22(4)：101-103．
[53] 孙晏．基于时间位图迭加匹配的课表编排算法[J]．华东船舶工业学院学报(自然科学版)，2001，15(6)：58-62．
[54] 王祜民，赵致格．时间表问题中的定额匹配算法[J]．清华大学学报(自然科学版)，1998,38(6)：8-11．
[55] 陶滔，李都，熊正为．多维冲突在排课算法中的应用[J]．华东地质学院学报，2001，24(3)：256-259．
[56] 李明．一个基于智能化搜索的排课表算法及其Client/Server实现[J]．研究与开发，1997，59(6)：21-22．
[57] 马允宜，刘志镜．图与图着色在计算机辅助排课表中的应用[J]．西安工业学院学报，1994，14(4)：314-318．
[58] 于标．排课问题的一种近似算法[J]．扬州职业大学学报，2001，5(1)：30-34．
[59] 傅清祥，王晓东．算法与数据结构．北京，电子工业出版社，2000
[60] 周培德．算法设计与分析．北京，机械工业出版社，1996
[61] 孙焕纯，汪跃方．货郎担问题的人工智能—人机交换解法[J]．系统工程理论与实践，2000，5：1-10．
[62] 魏平，熊伟清．计算机辅助课表编排技术的研究[J]．甘肃工业大学学报，1997，23(4)：77-81．
[63] 董艳云，钱晓群，张宇舒．基于课元相关运算的高校排课算法[J]．西南交通大学学报，1998，33(6)：670-673．
[63] 马良，项培军．蚂蚁算法在组合优化中的应用[J]．管理科学学报，2001，4(2)：32-36．
[64] 唐勇，唐雪飞，王玲．基于遗传算法的排课系统[J]．计算机应用，2002，22(10)：93-97．
[65] 周建新，王科俊，王文武，张建波．课表编排专家系统[J]．计算机应用，2000，20(5)：76-78．
[66] 傅志斌．基于组件的网上课表编排查询系统[J]．河北大学学报(自然科学版)，2001，21(2)：171-175．
[67] 石连栓．离散变量结构优化设计算法研究综述[J]．天津职业技术师范学院学报，2001，11(1)：5-9．
[68] 鄢烈祥．列队竞争算法解组合优化问题[J]．湖北工业学院学报，2000，15(2)：1-4．
[69] 王俊海．TSP 问题的一种高效 Memetic算法[J]．交通与计算机，2002，20(1)：14-17．
[70] 王力．高校通用排课管理信息系统的设计与实现[J]．贵州工业大学学报，2002，12(2)：8-12．
[71] 段刚，余贻鑫．电力系统NP难问题全局优化算法的研究[J]．电力系统自动化，2001，25(5)：14-18．
[72] 许可，李末．随机k-SAT问题的回溯算法分析[J]．计算机学报，2000，23(5)：454-458．7
[2] J Thompson and KA Dowsland. Variants of simulated annealing for the examination timetabling pmblem.[C]Annals of Operations Research.1995
[3] 王小平，曹立明．遗传算法．西安西安交通大学出版社，2002
[4] Holland,J.H.Adaptation in natural and artificial systems:An introductory analysis with application to biology, control,and artificial intelligence. 1~(st) edition,Ann Arbor, MI:The University of Michigan Press, 1975;2~(nd) edition,Cambridge,MA:MIT Press, 1992
[5] 唐飞，滕弘飞，孙治国，王文忠．十进制编码遗传算法的模式定理研究[J]．小型微型计算机系统，2000，21(4)：364-367
[6] 赵舒展．遗传算法研究与应用．浙江工业大学硕士学位论文．2001-12
[7] 周明，孙树东，遗传算法原理及应用．北京，国防工业出版社，2000
[8] Radcliffe N.J. The Aleghra Of Genetic Algorithms.Annals Of Math,&AI,10(1994),339-384.
[9] Rudolph G.Convergence Analysis Of Canonical Genetic Algorithm[J].IEEE Trans Neural Networks, 1994,5(1).
[10] 张恭庆，林源渠．泛函分析讲义．北京大学出版社，北京：1987．
[11] 熊大国．随机过程理论与应用．北京，国防工业出版社，1991
[12] RF Weare.Automated examination timetableling.[D]PhD Thesis,Department of Computer Science,University of Nottingham,UK, June 1995
[13] EK Burke.DG Elliman,and RF Weare.Examination timetabling in british universities-a survey.[e]Proceedings of the 1~(st) International Conference on the Practice and Theory of Automated Timetabling. ICPAT'95,Napier University, Edinburgh,30th Aug-1~(st) Sept 1995
[14] Burke E.K.,Elliman D.G. and Weare R.F.,A University timetabling system based on graph colouring and constraint manipulation.[J]The Journal of Research on Computing in Education, Vol.26,issue 4,1993
[15] Graping Huang,Juan Liu,A Heuristic algorithm to solve timetabling problem.[J]Wuhan University Journal of National Sciences,Vol.42,No.1,71～74,Feb.1996
[16] Boizumanlt P.,Gueret C. and Jussien N.,Efficient labeling and constraint
relaxation for solving time tabling problems.[C]Internationai Logic Programsing Symposium-Workshop on Constraint Languages and their use in Problem Modelling, 116～130,1994
[17] D Johnson,Adatabase approach to course timetabling.[J]Journal of the Opcrational Rcscarch Society, Vol.44,No.5,425～433,Operatinal Research Society, 1993
[18] WL Winston,Operational research:applications and algurithms.2~(nd) ed.,PWS-Kent,Boston,Massachusetts,1991
[19] 王祜民，赵致格．排课表问题中的分组优化决策算法[J]．控制与决策，1999，14(2)：109-114．
[20] Garey M R Johnson D S.Computers and Intractablity. A Gilide to the Theory of NP-Completeness[M].San Francisco CA. Freeman 1979.
[21] MWCarter, GLaporte,and Chinneck.Ageneralexaminationschedulingsystem. (J) INTERFACES,Vol.24,No.3,109～120,May-June1994.
[22] Even,S.,et.al.,On the Complexity of Timetable and Multicomsodity Flow Problems,SIAM Journal on computing,Vol.5,No.4,pp.691-703,1976
[23] Colormi,A.,et.al.,Genctic Algorithms and Highly Constrained Problems:The Time-Table Case,in[121],pp.55-59,1991.
[24] Paechter, B.,et.al.,Two Solutions to the General Timetable Problem Using Evoluationary Mcthods,in[95],1994
[25] FWeare.Automated examination timetabling. [D] PhD Thesis, Department of Computer Science,University of Nottingham,UK,June1995
[26] Burke E.K,Elliman D.G.and Weare R.F.,A University timetabling system based on graph colouring and constraint manipulation.[J]The Journal of Research on Computing in Education,Vol.26,issue 4,1993
[27] D Johnson,A database approach to course timetabling.[J]Journal of the Operational Research Society, Vol.44,No.5,425～433,Operatinal Research Society,1993.
[28] WL Winston. Opcrational research:applications and algurithms.2~(nd) ed.,PWS-Kent, Boston, Massachusetts, 1991.
[29] J Thompson and KA Dowsland. Variants of simulated annealing for the examination timetabling problem.[C]Annals of Operations Research.1995.
[30] Mitchell M.,An Introduction to genetical gorithms.[M] Cambridge. MIT
Press. 1996.
[31] Michalewicz Z. Genetic Algorithms + Data Structures = Evolution Programs. Springer-Verlang, Berlin,1992
[32] Zhengjun Pan,Lishan Kang and Yuping Chen. Evolutionary Computation.[M]Tsinghua University Press. 1998
[33] Mitchell M.,An Introduction to genetic algorithms.[M]Cambridge. MIT Press.1996
[34] 周培德，周忠平，张欢．寻求中国货郎担问题最短回路的多项式时间算法[J]．北京理工大学学报，2000，20(2)：201-204．
[35] 喻摘，凌捷，谢晓峰．用遗传算法求解CTSP[J]．广东工业大学学报，2000，17(3)：52-55．
[36] 毕军，付梦印，周培德．一种适于车辆导航系统的快速路径规划算法[J]．北京理工大学学报，2002，22(2)：188-191．
[37] 姚朝灼．实验回溯问题的算法模版设计[J]．福州大学学报(自然科学版)，2000，28(3)：31-34．
[38] 王潮，宣国荣．人工神经网络求解TSP问题新方法[J]．计算机应用与软件，2001，18(4)：59-65．
[39] 程国忠，张世禄．三个典型问题的回溯算法[J]．四川师范学院学报(自然科学版)，2000，21(2)：187-191．
[40] 付雪峰，何渝．时间优先的中小学课表编排算法[J]．北京工商大学学报(自然科学版)，2002，20(1)：37-40．
[41] 周荣敏，雷延峰．基于遗传算法的最小生成树的参数优化研究[J]，郑州大学学报(工学版)，2002，23(2)：9-12．
[42] 吴浩扬，常柄国，朱长纯，刘君华．基于模拟退火机制的多种群并行遗传算法[J]．软件学报，2000，11(3)：416-420．
[43] 于洋，查建中，唐晓君．基于学习的遗传算法及其在布局中的应用[J]．计算机学报，2001，24(12)：1242-1249．
[44] 张春梅，行飞．用自适应的遗传算法求解大学课表安排问题[J]．内蒙古大学学报(自然科学版)，2002，33(4)：459-464．
[45] 张银明．元素判别值分配法在求解TSP问题中的应用[J]．华侨大学学报(自然科学版)，2002，24(2)：191-197．
[46] 熊伟清，魏平，赵杰熠．用遗传算法求解时间表问题[J]．微电子学与计算机，2001，4：29-31．
[47] 黄干平，姚自珍，张静．使用模拟退火算法解课表问题[J]．武汉大学学报(自然科学版)，2000，46(5)：559-563．
[48] 胡顺仁，邓毅，王铮．基于高校排课系统中的图论问题研究[J]．计算机工程与应用，2002，4：221-222．
[49] 汪红星，康立山，陈硫屏．基于演化算法的一类时间表问题的自动求解[J]．小型微型计算机系统，2000，21(5)：469-470．
[50] 吴金荣．求解课程表问题的分支定界算法[J]．运筹与管理，2002，11(1)：17-22．
[51] 龙一飞，郭文宏．基于知识推理的排课系统[J]．电脑开发与应用，2000，13(6)：35-37．
[52] 洪力奋．基于人工智能原理的大学课表编排模型[J]．合肥工业大学学报(自然科学版)，1999，22(4)：101-103．
[53] 孙晏．基于时间位图迭加匹配的课表编排算法[J]．华东船舶工业学院学报(自然科学版)，2001，15(6)：58-62．
[54] 王祜民，赵致格．时间表问题中的定额匹配算法[J]．清华大学学报(自然科学版)，1998,38(6)：8-11．
[55] 陶滔，李都，熊正为．多维冲突在排课算法中的应用[J]．华东地质学院学报，2001，24(3)：256-259．
[56] 李明．一个基于智能化搜索的排课表算法及其Client/Server实现[J]．研究与开发，1997，59(6)：21-22．
[57] 马允宜，刘志镜．图与图着色在计算机辅助排课表中的应用[J]．西安工业学院学报，1994，14(4)：314-318．
[58] 于标．排课问题的一种近似算法[J]．扬州职业大学学报，2001，5(1)：30-34．
[59] 傅清祥，王晓东．算法与数据结构．北京，电子工业出版社，2000
[60] 周培德．算法设计与分析．北京，机械工业出版社，1996
[61] 孙焕纯，汪跃方．货郎担问题的人工智能—人机交换解法[J]．系统工程理论与实践，2000，5：1-10．
[62] 魏平，熊伟清．计算机辅助课表编排技术的研究[J]．甘肃工业大学学报，1997，23(4)：77-81．
[63] 董艳云，钱晓群，张宇舒．基于课元相关运算的高校排课算法[J]．西南交通大学学报，1998，33(6)：670-673．
[63] 马良，项培军．蚂蚁算法在组合优化中的应用[J]．管理科学学报，2001，4(2)：32-36．
[64] 唐勇，唐雪飞，王玲．基于遗传算法的排课系统[J]．计算机应用，2002，22(10)：93-97．
[65] 周建新，王科俊，王文武，张建波．课表编排专家系统[J]．计算机应用，2000，20(5)：76-78．
[66] 傅志斌．基于组件的网上课表编排查询系统[J]．河北大学学报(自然科学版)，2001，21(2)：171-175．
[67] 石连栓．离散变量结构优化设计算法研究综述[J]．天津职业技术师范学院学报，2001，11(1)：5-9．
[68] 鄢烈祥．列队竞争算法解组合优化问题[J]．湖北工业学院学报，2000，15(2)：1-4．
[69] 王俊海．TSP 问题的一种高效 Memetic算法[J]．交通与计算机，2002，20(1)：14-17．
[70] 王力．高校通用排课管理信息系统的设计与实现[J]．贵州工业大学学报，2002，12(2)：8-12．
[71] 段刚，余贻鑫．电力系统NP难问题全局优化算法的研究[J]．电力系统自动化，2001，25(5)：14-18．
[72] 许可，李末．随机k-SAT问题的回溯算法分析[J]．计算机学报，2000，23(5)：454-458．7