多目标考试时间表改进算法范文

《西安电子科技大学学报》2016年第二期

1求解考试时间表问题的进化多目标优化算法

本文是在文献12的基础上，针对算法的种群初始化操作，引入了超启发方法；在算法的克隆操作中，设计了一种新的资源分配模型，是一种关于多目标考试时间表问题的NNIA改进算法，所以除种群初始化操作与克隆操作外，算法中的其他所有操作算子，以及算法流程与文献12完全相同，算法流程如图1所示。

1.1资源分配模型NNIA是一种经典的进化多目标优化算法，在此算法的运行过程中，只是采用少数的非支配个体进行操作，考虑到本文采用的多目标考试时间表的建模方式，在算法运行过程中，当出现非支配解数量不足的情况时，必然会对NNIA框架下的算法性能产生十分明显的影响。顾本文在采用NNIA算法框架的基础上，在个体克隆阶段，设计了一种基于博弈论的资源分配模型，通过动态控制优势个体的克隆数量手段，更加合理的分配计算资源。在资源分配模型中，根据非支配排序关系，待克隆的个体首先被划分为不同的等级（R1,…,Rn）。其中，Ri代表了第i等级的个体的数量。通常情况下，R1中的个体优于其他个体。根据R1个体在所有待克隆个体中所占的比例r，将资源分配模型分解为早期模型、中期模型和后期模型。算法在运行过程中，根据不同的模型，采用相应的克隆策略。早期模型(r≤1/3)：在此阶段只有很少的优秀个体（R1个体）。根据博弈论的相关概念，需要抑制R2中个体的克隆数量，以保证其无法影响到R1中的个体。如公式(5)所示，其中Si表示原始的克隆尺寸，Mi表示资源分配模型计算过后，克隆后第i级别的克隆规模。

1.2基于超启发方法的种群初始化许多学者的研究及仿真实验表明[1]，基于图着色的超启发方法十分适合处理单目标考试时间表问题。采用超启发方法拥有更大几率快速找到可行解或潜在的优势个体。针对本文所面对的多目标考试时间表问题，若能快速得到可行解或潜在的优势个体，在固定的算法迭代次数的条件下，则更加有利于得到更好的结果。因此，本文采用基于图着色的超启发方法生成初始种群。其中，初始种群是由一定数量的初始解(时间表)构成的。首先，随机产生由不同图启发算法构成的启发式链表，根据启发式链表，产生初始解（考试时间表）。在产生初始解的过程中，每当产生一个新的考试时间表示，通过这些不同的启发式算法，可以产生一个考试科目安排顺序，在不违反硬约束的条件下，根据考试安排顺序，每门考试随机安排在时间段中。具体的超启发方法请参看文献[1]。另外，本文采用二进制编码方式，其中每一列代表一个时间段，每一行代表一门考试，数字1表示在此时段安排某门考试，0表示在此时段未安排考试。

2仿真实验

本文选取Carter标准数据集[14]进行测试。近几十年来，几乎所有关于考试时间表算法的研究都采用此数据集进行性能测试，但此数据仍是开放数据，理论最优解仍然未知。本文选取了该数据集中的十个具有代表性的数据，对提出的算法进行仿真实验。以下仿真均为10次独立运行实验，运行环境为2.8GHzCorePersonalComputer。具体参数如表1所示：针对10个测试数据，算法经过10次独立运行，随机选取一组解集，其pareto前沿面如图2所示。少数几个测试集（car91,car92,ear83等）在个别区域没有找到非支配解。除上述测试集，大部分的测试集基本上能够完整勾勒出2目标优化的pareto前沿面，并且对于每一组数据的pareto解都可以较为均匀的分布在其前沿面上。表2记录了现今这些测试集的最好的运行结果，需要注意的是，此结果均为在单目标优化(固定时间表长度，只优化考试间冲突关系)的环境下产生的。我们选取的运行结果则是根据单目标环境下的时间表长度(P),在我们的多目标算法运行的结果中，选取的对应结果。从对比结果来看，除数据集york83，我们的算法均能找到与单目标模型中相同的时间段。从具体结果上来说，我们的结果的确与其他几种最优秀的单目标优化结果尚存一定差距，但差距并不明显。重要的是采用本文提出的多目标优化算法，经过一次运行就可提供不同时间段的多个解，运行效率是单目标优化的数十倍。上述结果表明，将考试时间表问题按照多目标优化问题建模有效且可以极大地提高计算效率。本文在NNIA框架下，在克隆阶段采用了资源分配模型，此模型对于整个算法的影响可由下列实验得出结论。图3为十组测试数据分别来自为采用资源分配模型的RA-NNIA和未采用此模型的原始NNIA进行十次独立运行后，非支配解个数的统计盒图。针对每一个测试数据，左边采用RA-NNIA，右边采用NNIA。我们可以明显看出，采用资源分配模型的RA-NNIA的非支配个体数量明显的好于未采用的NNIA。图4为十组测试数据，分别采用RA-NNIA和NNIA，经过十次独立实验后，spacing指标的统计盒图对比。由图可知，除少数几组数据(car92,ear83)，采用RA-NNIA算法的均匀性指标都要优于采用NNIA的运行结果。根据以上两组实验结果分析可知，对于如此建模的多目标考试时间表问题，非支配解的数量本身就十分的有限，传统的NNIA仅采用当前的非支配个体进行克隆，而后进行进化操作，导致种群的多样性难以保持，很有可能进一步导致最终的非支配解数目不足，而RA-NNIA克隆阶段，在非支配个体数量不足时，还会利用少部分较好的支配个体，共同进行克隆操作，并且，资源分配模型还会根据当前非支配个体所占的比例，动态控制每一部分个体的克隆比例，此种策略在一定的情况下可以很好地改善传统NNIA在这方面上的不足。所以，采用资源分配模型的NNIA是有利于非支配个体的产生与保留，有利于算法的多样性的保持，此策略十分适合用于求解多目标考试时间表问题的多目标进化算法。

3结束语

本文提出了一种解决多目标考试时间表问题的NNIA改进算法。在非支配邻域免疫算法的框架下，提出了一种资源分配模型，用来动态控制个体的克隆比例，利用超启发技术构造初始种群。实验结果表明，采用笔者所提出的改进的NNIA能够更加有效的解决多目标考试时间表问题。另外，笔者也注意到，原始的解决此问题的NNIA方法的局部搜索策略可以在一定程度上改善种群的质量，但仍有提高的空间。因此，针对此问题，以及类似的调度问题，如何来设计更加合理、出色的局部搜索策略将是今后有待研究的重要问题。

作者：雷雨 焦李成 公茂果 李玲玲 单位：西安电子科技大学综合业务网理论及关键技术国家重点实验室