基于图模型与遗传算法相结合的排课问题研究  

A study on the problem of university timetabling based on graph model and genetic algorithm

作　　者：邓志杰[1] 

机构地区：[1]河海大学计算机与信息学院,南京211100

出　　处：《信息技术》2014年第1期146-149,154,共5页Information Technology

摘　　要：排课问题是典型的NP问题,文中以顶点着色为基础,通过引入动态边,扩展了现有的排课问题图模型。初始化中采用了特殊适应和最先适应策略,同时定义了团集的概念,将其作为交叉变异算子的操作对象。通过实验结果分析,针对平均适应值、教室利用率以及冲突次数等评价指标,文中提出的初始化和遗传操作方法均能取得较好的结果。Timetabling problem is a typical NP problem.Based on the vertex-coloring theory,this paper extended the existing timetable graph model by introducing dynamic edge.The special fit strategy and first fit strategy are used to the process of initialization,and then the concept of click is defined as the solving object for the crossover and mutation operators.Through the analysis of the experimental results,the proposed method of initialization and genetic manipulation method can get good results under the evaluation of average penalty cost,utilization rate of classroom and the number of conflicts.

关 键 词：排课问题 遗传算法 图模型 顶点着色 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]