雷 雨,焦李成,公茂果,李玲玲

(西安电子科技大学智能感知与图像理解教育部重点实验室,陕西西安 710071)



求解多目标考试时间表问题的NNIA改进算法

雷 雨,焦李成,公茂果,李玲玲

(西安电子科技大学智能感知与图像理解教育部重点实验室,陕西西安 710071)

摘要:针对多目标考试时间表问题,提出了一种用于求解多目标考试时间表问题的非支配邻域免疫改进算法.采用经典多目标进化算法非支配邻域免疫的算法框架,为改善该算法的收敛性和多样性,利用超启发方法生成初始种群,同时采用一种新的资源分配模型,在克隆过程中动态调节优秀个体的克隆比例,来改善算法的性能.采用10组标准测试数据对算法的性能进行测试.实验结果表明,该算法对多目标考试时间表问题十分有效,并且在某些测试数据上可得到令人满意的结果.

关键词:多目标优化;考试时间表;进化算法;资源分配模型;非支配邻域免疫算法

解决考试时间表问题的主要方法可归纳为图着色方法[1]、基于种群方法[2-3]、局部搜索方法[4-5]、变邻域搜索及混合和超启发方法[6-7]等.关于考试时间表问题的建模,通常是将考试时间表问题的时间表长度固定,将各个考试的冲突关系作为惟一的目标函数,然后将此问题作为一个单目标优化问题处理.这种建模方式的优势是许多经典成熟的单目标优化算法都可处理此问题,并且可最终获得一个确定的最优值.然而,若需要得到多个不同时间长度的考试安排,仍要采用单目标方式建模,则必须多次运行算法,这无疑增加了一定的资源成本.随着进化多目标技术的发展[8-10],文献[11]在2009年提出了一种解决考试时间表的进化多目标优化算法,并且将时间表长度和考试间的冲突关系作为两个目标函数,将考试时间表问题建模为一个多目标优化问题.采用此种方法,算法只需运行1次,便可得到多个不同长度的考试时间表,而管理者只需要挑选其中最为符合实际情况的一种考试安排表即可.针对多目标考试时间表问题,出现了一些以经典进化多目标算法为基本框架的优化算法[12-13].上述论文的仿真实验显示,采用多目标进化算法处理多目标考试时间表问题是可行的,但需要设计出更加高效的算法,以便更好地解决多目标考试时间表问题.因此,在文献[12]提出的解决考试时间表的非支配邻域免疫算法(Nondominated Neighbor Immune Algorithm,NNIA)基础上,笔者设计了一种资源分配模型,引入了超启发方法的相关技术,提出了一种用于处理多目标考试时间表问题的NNIA改进算法.

1 考试时间表问题

考试时间表问题是一个典型NP难的组合优化问题.问题可描述为:将一定数量的考试安排在一个固定的时间段中,并且安排过程中必须满足一定的约束条件.即将一组考试E={e1,e2,…,eE}排入一个长度为P={1,2,…,P}的时间段内.具体数学描述如下:

其中,式(1)表示此问题的最小化冲突值;式(2)为此问题的约束条件之一,表示同一学生在某一时段只能参加一门考试;式(3)为另一约束条件,指出每一门考试科目只能在整个时间段中安排1次.若考试ei被排在时间段p中,则aij=1,eij代表同时参加考试ei与ej的学生总数.

文中将考试时间表建模为两目标优化问题,将在单目标考试时间表问题中十分常见的惩罚函数作为目标函数1,将时间表长度P作为目标函数2,可表示为

其中,ωs=2s,s=0,1,2,3,4,表示被安排的冲突考试的时间间隔为4,3,2,1,0的相应惩罚值;Ns表示参加这些考试的学生总数;S表示学生总人数.

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

图1 算法流程图

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

2.1 资源分配模型

NNIA是一种经典的进化多目标优化算法,在此算法的运行过程中,只是采用少数的非支配个体进行操作,考虑到文中采用的多目标考试时间表的建模方式,在算法运行过程中,当出现非支配解数量不足的情况时,必然会对NNIA框架下的算法性能产生十分明显的影响.文中在采用NNIA算法框架的基础上,在个体克隆阶段,设计了一种基于博弈论的资源分配模型,通过动态控制优势个体的克隆数量手段,更加合理地分配计算资源.

在资源分配模型中,根据非支配排序关系,待克隆的个体首先被划分为不同的等级(Rank1,…,Rankn),其中,Ranki代表了第i等级的个体的数量.通常情况下,Rank1中的个体优于其他个体.根据Rank1个体在所有待克隆个体中所占的比例r,将资源分配模型分解为早期模型、中期模型和后期模型.算法在运行过程中,根据不同的模型,采用相应的克隆策略.

(1)早期模型(r≤1/3).在此阶段只有很少的优秀个体(Rank1个体),根据博弈论的相关概念,需要抑制Rank2中个体的克隆数量,以保证其无法影响到Rank1中的个体,即

其中,Si表示原始的克隆尺寸,Mi表示资源分配模型计算过后,克隆后第i级别的克隆规模.

(2)中期模型(1/3＜r＜2/3).在此阶段优秀个体的数量增多,但依然无法忽视其他级别的个体对其影响,因此,需要抑制除Rank1外的其他个体的克隆数量,即

(3)后期模型(r≥2/3).在此阶段优秀个体已经占据了很大的比例,其他个体对其影响可忽略不计,因此,只需按照所有个体之间的拥挤度距离进行等比例克隆.

2.2 基于超启发方法的种群初始化

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

3 仿真实验

文中选取Carter标准数据集[14]进行测试.近几十年来,几乎所有关于考试时间表算法的研究都采用此数据集进行性能测试,但此数据仍是开放数据,理论最优解仍然未知.文中选取了该数据集中的10个具有代表性的数据,对提出的算法进行仿真实验.以下仿真均为10次独立运行实验,运行环境为2.8 GHz Core Personal Computer.具体参数为:种群大小m=100,每一种启发式算法所要安排的考试数量e=2,交叉概率Pc=0.8,变异概率Pm=0.2,算法最大迭代次数Gmax=100.

表1 不同算法的实验结果对比

针对10个测试数据,算法经过10次独立运行,随机选取一组解集,其Pareto前沿面如图2所示.少数几个测试集(Car91,Car92,Ear83等)在个别区域没有找到非支配解.除上述测试集,大部分的测试集基本上能够完整勾勒出两目标优化的Pareto前沿面,并且对于每一组数据的Pareto解都可较为均匀地分布在其前沿面上.表1记录了这些测试集最好的运行结果,需要注意的是,此结果均为在单目标优化(固定时间表长度,只优化考试间冲突关系)的环境下产生的.笔者选取的运行结果则是根据单目标环境下的时间表长度(P),在文中的多目标算法运行的结果中,选取的对应结果.从对比结果来看,除数据集York83、文中算法均能找到与单目标模型中相同的时间段.从具体结果上来说,文中结果的确与其他几种最优秀的单目标优化结果尚存一定差距,但差距并不明显.重要的是采用文中提出的多目标优化算法,经过1次运行就可提供不同时间段的多个解,运行效率是单目标优化的数十倍.上述结果表明,将考试时间表问题按照多目标优化问题建模有效,且可极大提高计算效率.

图2 10组测试数据的Pareto前沿面示意图

图3 非支配解个数的统计盒图

在NNIA框架下,在克隆阶段采用了资源分配(Resource Assignment,RA)模型,此模型对于整个算法的影响可由下列实验得出结论.图3为10组测试数据分别来自采用资源分配模型的RA-NNIA和未采用此模型的原始NNIA进行10次独立运行后,非支配解个数的统计盒图.针对每一个测试数据,左边采用RA-NNIA,右边采用NNIA.可明显看出,采用资源分配模型的RA-NNIA的非支配个体数量明显好于未采用此模型的NNIA的.图4为10组测试数据,分别采用RA-NNIA和NNIA经过10次独立实验后,Spacing指标的统计盒图对比.由图4可知,除少数几组数据(Car92,Ear83)外,采用RA-NNIA算法的均匀性指标都要优于采用NNIA的运行结果.

根据以上两组实验结果分析可知,对于如此建模的多目标考试时间表问题,非支配解的数量本身就十分有限,传统的NNIA仅采用当前的非支配个体进行克隆,而后进行进化操作,导致种群的多样性难以保持,很可能会进一步导致最终的非支配解数目不足,而RA-NNIA克隆阶段,在非支配个体数量不足时,还会利用少部分较好的支配个体,共同进行克隆操作.并且,资源分配模型还会根据当前非支配个体所占的比例,动态控制每一部分个体的克隆比例,此种策略在一定的情况下可很好地改善传统NNIA在这方面上的不足.所以,采用资源分配模型的NNIA是有利于非支配个体的产生与保留,有利于算法的多样性的保持,此策略十分适合用于求解多目标考试时间表问题的多目标进化算法.

图4 Spacing指标的统计盒图

4 结束语

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

参考文献:

[1]BURKE E K,MCCOLLUM B,MEISELS A,et al.A Graph-based Hyper-heuristic for Educational Timetabling Problems[J].European Journal of Operational Research,2007,176(1):177-192.

[2]ALZAQEBAH M,ABDULLAH S.An Adaptive Artificial Bee Colony and Late-acceptance Hill-climbing Algorithm for Examination Timetabling[J].Journal of Scheduling,2014,17(3):249-262.

[3]THEPPHAKORN T,PONGCHAROEN P,HICKS C.An Ant Colony Based Timetabling Tool[J].International Journal of Production Economics,2014,149:131-144.

[4]BURKE E,BYKOV Y,NEWALL J,et al.A Time-predefined Local Search Approach to Exam Timetabling Problems [J].IIE Transactions,2004,36(6):509-528.

[5]THOMPSON J M,DOWSLAND K A.A Robust Simulated Annealing Based Examination Timetabling System[J].Computers& Operations Research,1998,25(7):637-648.

[6]BURKE E K,ECKERSLEY A J,MCCOLLUM B,et al.Hybrid Variable Neighbourhood Approaches to University Exam Timetabling[J].European Journal of Operational Research,2010,206(1):46-53.

[7]SORIA-ALCARAZ J A,OCHOA G,SWAN J,et al.Effective Learning Hyper-heuristics for the Course Timetabling Problem[J].European Journal of Operational Research,2014,238(1):77-86.

[8]GONG M,JIAO L,DU H,et al.Multiobjective Immune Algorithm with Nondominated Neighbor-based Selection[J].Evolutionary Computation,2008,16(2):225-255.

[9]ZHANG Q,LI H.MOEA/D:a Multi-objective Evolutionary Algorithm Based on Decomposition[J].IEEE Transactions on Evolutionary Computation,2007,11(6):712-731.

[10]董宁,王宇平.求解约束优化问题的偏好多目标进化算法[J].西安电子科技大学学报,2014,41(1):98-104.DONG Ning,WANG Yuping.Multi-objective Evolutionary Algorithm Based on Preference for Constrained Optimization Problems[J].Journal of Xidian University,2014,41(1):98-104.

[11]CHEONG C Y,TAN K C,VEERAVALLI B.A Multi-objective Evolutionary Algorithm for Examination Timetabling [J].Journal of Scheduling,2009,12(2):121-146.

[12]康姝.基于NNIA的多目标时间表调度问题研究[D].西安:西安电子科技大学,2014.

[13]孙娜娜.基于MOEA/D的多目标考试时间表调度算法研究[D].西安:西安电子科技大学,2014.

[14]CARTER M W,LAPORTE G,LEE S Y.Examination Timetabling:Algorithmic Strategies and Applications[J].Journal of the Operational Research Society,1996,47(3):373-383.

[15]CARAMIA M,DELL’OLMO P,ITALIANO G F.Novel Local-search-based Approaches to University Examination Timetabling[J].INFORMS-Informs Journal on Computing,2008,20(1):86-99.

[16]BURKE E K,BYKOV Y.Solving Exam Timetabling Problems with the Flex-deluge Algorithm[EB/OL].[2014-12-20].http://www.docin.com/p-85694528.html.

[17]ABDULLAH S,TURABIEH H,MCCOLLUM B.A Hybridization of Electromagnetic-like Mechanism and Great Deluge for Examination Timetabling Problems[C]//Lecture Notes in Computer Science:5818 LNCS.Heiderlberg: Springer Verlage,2009:60-72.

(编辑:齐淑娟)

Enhanced NNIA for multi-objective examination timetabling problems

LEI Yu,JIAO Licheng,GONG Maoguo,LI Lingling
(Ministry of Education Key Lab.of Intelligent Perception and Image Understanding,Xidian Univ.,Xi’an 710071,China)

Abstract:Based on the nondominated neighbor immune algorithm(NNIA),an enhanced NNIA is introduced for multi-objective examination timetabling problems.With the framework of NNIA,the hyperheuristic approach is utilized to generate the initial population.In addition,the resource allocation model is designed to dynamically adjust the clone percentage of potential individuals.Experimental results on ten benchmark datasets prove that the proposed algorithm can solve examination timetabling problems effectively and obtaine competitive results.

Key Words:multi-objective optimization;examination timetabling;evolutionary algorithm;resource allocation model;nondominated neighbor immune algorithm(NNIA)

作者简介:雷 雨(1985-),男,西安电子科技大学博士研究生,E-mail:xdleiyu@gmail.com.

基金项目:国家自然科学基金资助项目(61273317)

收稿日期:2015-01-08 网络出版时间:2015-05-21

doi:10.3969/j.issn.1001-2400.2016.02.027

中图分类号:TP18

文献标识码:A

文章编号:1001-2400(2016)02-0157-05

网络出版地址:http://www.cnki.net/kcms/detail/61.1076.TN.20150521.0902.024.html