采用改进的混合遗传算法求解高校排课问题  

Improved hybrid genetic algorithm for university timetabling problem

作　　者：张赫男[1] 张绍文[1] 

机构地区：[1]北京林业大学经济管理学院,北京100083

出　　处：《计算机工程与应用》2015年第5期240-246,共7页Computer Engineering and Applications

摘　　要：为了解决一个存在大量合班现象的高校排课问题,建立了相应的数学模型并采用改进的混合遗传算法进行了求解。在产生初始种群的过程中进行了乱序处理,以提高初始种群中个体的多样性,避免早熟收敛现象的发生;为了防止种群的退化,引入了保留最优个体策略和竞争机制;根据问题的特点设计了与之相适应的遗传算子;为了提高种群进化的效率,交叉概率和变异概率都使用了自适应参数;为了提高算法的局部搜索能力,在交叉操作阶段采用了模拟退火算法。通过Matlab与Access混合编程,实现了对大规模数据的高效处理。实例结果表明,该算法能够有效地解决存在合班现象的高校排课问题。In order to solve a University Timetabling Problem（UTP）containing many combining classes, a corresponding mathematical model is established and an improved hybrid Genetic Algorithm（GA）is proposed to solve this problem. To improve the diversity of the initial population and avoid premature convergence, random processing is introduced during the process of generating the initial population. To avoid population degeneration, the strategy of keeping the best individual and a competition mechanism are introduced. Suitable genetic operators are designed based on the characteristics of the problem. To improve the efficiency of the population evolution, both the crossover probability and the mutation probability are adaptive parameters. To improve the local search ability of the algorithm, Simulated Annealing（SA）is adopted during the phase of crossover. Large-scale data is processed efficiently by hybrid programming with Matlab and Access. Example verification indicates that the proposed algorithm can solve UTP containing combining classes efficiently.

关 键 词：合班现象 高校排课问题 混合遗传算法 自适应参数 模拟退火算法 混合编程 

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