求解多校区排课问题的基因对交叉遗传算法  

Genetic algorithm of genetic-couple cross for curriculum scheduling in multi-campus

作　　者：石慧[1] 彭晓红[1] 邬志红[1] 舒远仲[1] 

机构地区：[1]南昌航空大学计算机学院,南昌330063

出　　处：《计算机工程与应用》2010年第18期240-243,共4页Computer Engineering and Applications

基　　金：江西省教育科学"十五"规划重点项目No.04ZD085;江西省教育厅科技计划项目No.2006-161~~

摘　　要：国内很多高校或中学都建设了新校区,形成了多校区同时运行的格局。为了更好地解决多校区排课时的冲突问题,通过改进编码、交叉、变异算子,改进适应度函数设计,使遗传算法更好地适用于多校区的排课环境。提出的算法采用了二维资源片十进制编码方式,既方便初始种群产生和检测冲突,又减小时间复杂度。通过采用基于基因对交叉和资源变异算子,保证了每次的交叉、变异都有实际意义,以减小交叉、变异后产生硬性冲突的概率,提高进化效率,缩短进化时间。以某高校为例,使用C#和Mat-lab7.0等工具,通过编码、初始种群的生成、适应度函数设计与计算和遗传进化,实现了对多校区排课系统进行优化。实验结果表明,改进后的遗传算法提高了在排课应用中的可行性,更能适用于多校区排课。Many colleges or high schools have built new campuses,and they may run at the same time.In order to resolve con-flicts of the multi-campus course-arranging,the encoding,crossover,mutation operators and fitness function design should be improved.It is necessary to apply the genetic algorithm into the multi-campus class-scheduling environment.This paper uses decimal encoding method based on two-dimensional resource-piece.It not only conveniently initializes population and tests the conflict,but reduces the complexity of time.The using of gene-based crossover and mutation of resources ensures that the each cross and variation has practical meaning.It can reduce the probability of hard conflict after cross and variation,and improve the efficiency of evolution.Taking a certain college for example,the C # and Matlab7.0 tools will be used.The multi-campus class-scheduling system can be optimized through the coding,generation of initial population,designing of fitness function and genetic evolution.The result indicates that the reformed genetic algorithms can improve feasibility in the class-scheduling application and be more ap-plicable to the multi-campus course arrangement.

关 键 词：遗传算法 基因对交叉 排课 多校区 

分 类 号：TP183[自动化与计算机技术—控制理论与控制工程]