Computer Engineering and Applications ›› 2010, Vol. 46 ›› Issue (18): 240-243.DOI: 10.3778/j.issn.1002-8331.2010.18.073

• 工程与应用 • Previous Articles     Next Articles

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

SHI Hui,PENG Xiao-hong,WU Zhi-hong,SHU Yuan-zhong   

  1. School of Computing,Nanchang Hangkong University,Nanchang 330063,China
  • Received:2008-12-04 Revised:2009-02-23 Online:2010-06-21 Published:2010-06-21
  • Contact: SHI Hui

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

石 慧,彭晓红,邬志红,舒远仲   

  1. 南昌航空大学 计算机学院,南昌 330063
  • 通讯作者: 石 慧

Abstract: Many colleges or high schools have built new campuses,and they may run at the same time.In order to resolve conflicts 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 applicable to the multi-campus course arrangement.

Key words: genetic algorithm, genes exchange, timetable, multi-campus

摘要: 国内很多高校或中学都建设了新校区,形成了多校区同时运行的格局。为了更好地解决多校区排课时的冲突问题,通过改进编码、交叉、变异算子,改进适应度函数设计,使遗传算法更好地适用于多校区的排课环境。提出的算法采用了二维资源片十进制编码方式,既方便初始种群产生和检测冲突,又减小时间复杂度。通过采用基于基因对交叉和资源变异算子,保证了每次的交叉、变异都有实际意义,以减小交叉、变异后产生硬性冲突的概率,提高进化效率,缩短进化时间。以某高校为例,使用C#和Matlab7.0等工具,通过编码、初始种群的生成、适应度函数设计与计算和遗传进化,实现了对多校区排课系统进行优化。实验结果表明,改进后的遗传算法提高了在排课应用中的可行性,更能适用于多校区排课。

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

CLC Number: