一种基于遗传算法的时间表问题求解算法.doc

一种基于遗传算法的时间表问题求解算法.doc一种基于遗传算法的时间表问题求解算法摘要:排课问题是一个多因素的优化决策问题,是组合规划中的典型问题,其属于NP完全类问题。给出了该问题的数学模型。遗传算法借鉴生物界自然选择和遗传机制,使用群体搜索技术,处理传统搜索方法难以解决的复杂的非线性问题。针对时间表问题,提出一种基于遗传算法的解决方法,定义了一个新颖的染色体编码方式,基于该编码,进一步分析并设计出交叉和变异2个遗传操作,运行结果显示该方法可行。?? 关键词:时间表问题;组合规划;遗传算法;多因素优化决策;编码方案?? 中图分类号::B 文章编号:1004-373X(2008)08-082-02?? AlgorithmforSlovingTimeTableQuestionsBasedonGA?? WANGTing,WUChenwen?? (SchoolofElectronicandInformationEngineering,LanzhouJiaotongUniversity,Lanzhou,730070,China)?? Abstract:(GA)isbasedonthebiologicalmechanismofnaturalselectionandheredity,leveragingcolonysearchingtechnology,,anewmethodchromosomeencodingisdesigned,.?? Keywords:timetablequestion;icalgorithm;multifactoroptimizeddecision;encodingscheme 时间表问题又称课表问题,就是解决对时间和空间资源争夺而引发冲突[1]。20世纪70年代中期,。理论和时间表明,只要课表所涉及的任何信息量稍有变化,就会导致课表编排选择方案的剧增,即“组合爆炸”。一般作法是针对具体的应用环境,忽略一些限制条件,但这样会造成使用效果的不理想。本文中提出利用特定条件对课程与教室分批,采用遗传算法对时间表问题进行求解,给出了编码形式、遗传算子规则及适应度函数,通过对某学校课表编排数据的计算,验证了算法的有效性。对时间表问题的优化求解,起到一定的效果。?? 1课表编排问题的描述?? 设有班级集合??C={c1,c2,…,ca},教师集合P={p1,p2,…,pβ},教室集合R={r1,r2,…,rγ}和时间的集合??T={t1,t2,…,tμ}。时间与教师的笛卡尔积称为N=T×R={(