遗传算法在求解时间表问题中的应用研究  

Research on the application of genetic algorithm in solving TTP

作　　者：郑月锋[1] 黄德才[1] 刘端阳[1] 

机构地区：[1]浙江工业大学信息工程学院

出　　处：《浙江工业大学学报》2006年第2期162-165,共4页Journal of Zhejiang University of Technology

基　　金：浙江省自然科学基金(601076)

摘　　要：时间表问题(TTP)是一类特殊的资源调度问题,属于NP完全问题.排课问题是时间表问题的一个实例,属于多目标优化问题,本文给出了其数学模型.由于遗传算法具有良好的全局搜索能力,在优化问题中有着广泛的应用.本文根据排课问题的特点对普通遗传算法作了改进,设计了一种新的染色体编码方法,通过线性加权法将各目标优化函数进行整合转化成为单目标优化问题,并将此作为遗传算法的适应度函数.最后给出了一个计算实例,用MATLAB进行了仿真,算法最终收敛到稳定状态,所得的结果能够满足要求.Time table problem （TTP） is a special problem concerning resource management which fails into the category of NP. Arrangement of curriculum schedule is an example of TTP which aims to optimize the relevant decision-making on multi-objectives. A mathematic model is presented here. Due to its high capability of overall search, genetic algorithm has been extensively applied in optimization. In this article, the general genetic algorithm is modified in accordance with the characteristics of arrangement of curriculum schedule and a new chromosome coding is designed. Distinctive objective optimization functions are integrated into a single-objective function through weighted sum method. It is taken as the function of adaptation for genetic algorithm. A demonstration is presented employing simulation by MATLAB at the end. The modified genetic algorithm will converge to a stable condition. The results can satisfy the demands.

关 键 词：时间表问题 遗传算法 排课 

分 类 号：TP312[自动化与计算机技术—计算机软件与理论]