时间表问题又称课表问题，就是解决对时间和空间资源争夺而引发冲突。20世纪70年代中期，美国S.Even等人论证了课表问题是NP完全类问题。理论和时间表明，只要课表所涉及的任何信息量稍有变化，就会导致课表编排选择方案的剧增，即“组合爆炸”。一般作法是针对具体的应用环境，忽略一些限制条件，但这样会造成使用效果的不理想。本文中提出利用特定条件对课程与教室分批，采用遗传算法对时间表问题进行求解，给出了编码形式、遗传算子规则及适应度函数，通过对某学校课表编排数据的计算，验证了算法的有效性。对时间表问题的优化求解，起到一定的效果。
1 课表编排问题的描述
结合上述课表编排的4个条件，课表问题就转化为二部复图Hb(V，E)的匹配问题。
2 课表编排问题的遗传算法
遗传算法是基于生物的进化与选择机制的优化算法。遗传算法通过维持一个群体，并按个体的适应度的大小重复的进行选择。交叉和变异等操作来实现群体内个体结构的重组，将性能良好的解结构遗传下去，提高后代的适应能力，从而进化到最优或次优解。遗传算法的基本步骤：确定编码方案，确定适应函数，确定选择策略，控制参数的选择，遗传算子的设计，算法终止准则的确定等。
2.1 编码方案
二进制编码是最常用的编码方案，他类似于生物染色体的组成，从而易于用生物遗传理论来解释并使得遗传操作容易表现。且采用二进制编码时，算法处理的模式数最多。(设采用k进制编码，码长为1，则所表示的最大整数为k1，模式数为(k+1)1。可以证明k=2时使得k1=const(常数)时(k+1)1取得最大值)。但该种编码方案有相邻整数的二进制编码可能具有较大的海明距离，如：7和8的二进制表示为：0111，1000。这种缺陷在解决连续化问题时降低搜索效率。故在本问题求解中，采用格雷码相邻整数仅有一位不同的特性可克服二进制编码相邻证书可能具有较大海明距离的缺陷。他的解码过程如下：
设有一格雷码串(bnbn-1…b0)其解码过程如下：
串长为m1×n1，m1为各参数(即课程)的编码长度；n1为参数的个数(即课程的门数)，串中个参数所对应的值为该门课程所选“时间一教室对”集的序号，这样构造串结构m1最短，故串长也最短。
2.2 控制参数选择
(1)种群规模N：笔者经过反复实验发现：N值大进化较慢，但易搜索到全局较优解，而N值小时进化速度快，但不易搜索到较优解，权衡效率和性能，一般N取值为20～100，经过实验问题N取值为40比较合适。
(2)杂交操作
(3)变异操作
变异算子一般一次只改变一条染色体上的一个基因，比如，染色体Xt=(1，8，3，6，5)，变异的基因是第3位，则变异后Xt+1=(1，8，7，6，5)。
2.3 适应度函数
由于课表编排问题是求目标函数最大值，适应度函数定义如下：
其中Wij为第i个体串中对应第j门课所选”时间—教室对”集的权重。Count为第i个个体所对应的各门课程之间的冲突次数。C为一负数，其绝对值足够大，以致于只要出现一次冲突，该适应只便为负，这样便于终止准则的选定(因为所求解即要求无任何冲突)。但容易造成各个体间适应值相差过大的情况，所以采用线形排名的选择策略。终止条件为：
(1)该种群中最大适应值为一正数；
(2)2当前种群中最大适应值与以前各代中最大适应值相差不大，这时说明效果不太显著，再进化下去没有必要。
3 实验结果及结论
本算法用C语言进行验证，交叉概率均为0.8，变异概率0.2，种群规模设为70。对某学校课表编排数据进行实验，算法运行2 000代，获得了满意的结果，所获得的时刻表没有冲突。当算法运行超过4 000代以后，其结果会出现几处冲突外，但总体结果是比较满意的。通过手工调整很容易获得一个一个满意的时间表。
时间表问题是一个典型的NP完全问题，本文通过对该问题的数学模型的分析，提出以遗传算法进行求解，算法的运行结果说明了该方法是可行的。实际应用中，还要考虑更多的约束条件，这将是下一步的工作重点。
