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

(西安電子科技大學(xué)智能感知與圖像理解教育部重點(diǎn)實(shí)驗(yàn)室,陜西西安 710071)

?

求解多目標(biāo)考試時(shí)間表問(wèn)題的NNIA改進(jìn)算法

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

(西安電子科技大學(xué)智能感知與圖像理解教育部重點(diǎn)實(shí)驗(yàn)室,陜西西安 710071)

摘要:針對(duì)多目標(biāo)考試時(shí)間表問(wèn)題,提出了一種用于求解多目標(biāo)考試時(shí)間表問(wèn)題的非支配鄰域免疫改進(jìn)算法.采用經(jīng)典多目標(biāo)進(jìn)化算法非支配鄰域免疫的算法框架,為改善該算法的收斂性和多樣性,利用超啟發(fā)方法生成初始種群,同時(shí)采用一種新的資源分配模型,在克隆過(guò)程中動(dòng)態(tài)調(diào)節(jié)優(yōu)秀個(gè)體的克隆比例,來(lái)改善算法的性能.采用10組標(biāo)準(zhǔn)測(cè)試數(shù)據(jù)對(duì)算法的性能進(jìn)行測(cè)試.實(shí)驗(yàn)結(jié)果表明,該算法對(duì)多目標(biāo)考試時(shí)間表問(wèn)題十分有效,并且在某些測(cè)試數(shù)據(jù)上可得到令人滿意的結(jié)果.

關(guān)鍵詞:多目標(biāo)優(yōu)化;考試時(shí)間表;進(jìn)化算法;資源分配模型;非支配鄰域免疫算法

解決考試時(shí)間表問(wèn)題的主要方法可歸納為圖著色方法[1]、基于種群方法[2-3]、局部搜索方法[4-5]、變鄰域搜索及混合和超啟發(fā)方法[6-7]等.關(guān)于考試時(shí)間表問(wèn)題的建模,通常是將考試時(shí)間表問(wèn)題的時(shí)間表長(zhǎng)度固定,將各個(gè)考試的沖突關(guān)系作為惟一的目標(biāo)函數(shù),然后將此問(wèn)題作為一個(gè)單目標(biāo)優(yōu)化問(wèn)題處理.這種建模方式的優(yōu)勢(shì)是許多經(jīng)典成熟的單目標(biāo)優(yōu)化算法都可處理此問(wèn)題,并且可最終獲得一個(gè)確定的最優(yōu)值.然而,若需要得到多個(gè)不同時(shí)間長(zhǎng)度的考試安排,仍要采用單目標(biāo)方式建模,則必須多次運(yùn)行算法,這無(wú)疑增加了一定的資源成本.隨著進(jìn)化多目標(biāo)技術(shù)的發(fā)展[8-10],文獻(xiàn)[11]在2009年提出了一種解決考試時(shí)間表的進(jìn)化多目標(biāo)優(yōu)化算法,并且將時(shí)間表長(zhǎng)度和考試間的沖突關(guān)系作為兩個(gè)目標(biāo)函數(shù),將考試時(shí)間表問(wèn)題建模為一個(gè)多目標(biāo)優(yōu)化問(wèn)題.采用此種方法,算法只需運(yùn)行1次,便可得到多個(gè)不同長(zhǎng)度的考試時(shí)間表,而管理者只需要挑選其中最為符合實(shí)際情況的一種考試安排表即可.針對(duì)多目標(biāo)考試時(shí)間表問(wèn)題,出現(xiàn)了一些以經(jīng)典進(jìn)化多目標(biāo)算法為基本框架的優(yōu)化算法[12-13].上述論文的仿真實(shí)驗(yàn)顯示,采用多目標(biāo)進(jìn)化算法處理多目標(biāo)考試時(shí)間表問(wèn)題是可行的,但需要設(shè)計(jì)出更加高效的算法,以便更好地解決多目標(biāo)考試時(shí)間表問(wèn)題.因此,在文獻(xiàn)[12]提出的解決考試時(shí)間表的非支配鄰域免疫算法(Nondominated Neighbor Immune Algorithm,NNIA)基礎(chǔ)上,筆者設(shè)計(jì)了一種資源分配模型,引入了超啟發(fā)方法的相關(guān)技術(shù),提出了一種用于處理多目標(biāo)考試時(shí)間表問(wèn)題的NNIA改進(jìn)算法.

1 考試時(shí)間表問(wèn)題

考試時(shí)間表問(wèn)題是一個(gè)典型NP難的組合優(yōu)化問(wèn)題.問(wèn)題可描述為:將一定數(shù)量的考試安排在一個(gè)固定的時(shí)間段中,并且安排過(guò)程中必須滿足一定的約束條件.即將一組考試E={e1,e2,…,eE}排入一個(gè)長(zhǎng)度為P={1,2,…,P}的時(shí)間段內(nèi).具體數(shù)學(xué)描述如下:

其中,式(1)表示此問(wèn)題的最小化沖突值;式(2)為此問(wèn)題的約束條件之一,表示同一學(xué)生在某一時(shí)段只能參加一門(mén)考試;式(3)為另一約束條件,指出每一門(mén)考試科目只能在整個(gè)時(shí)間段中安排1次.若考試ei被排在時(shí)間段p中,則aij=1,eij代表同時(shí)參加考試ei與ej的學(xué)生總數(shù).

文中將考試時(shí)間表建模為兩目標(biāo)優(yōu)化問(wèn)題,將在單目標(biāo)考試時(shí)間表問(wèn)題中十分常見(jiàn)的懲罰函數(shù)作為目標(biāo)函數(shù)1,將時(shí)間表長(zhǎng)度P作為目標(biāo)函數(shù)2,可表示為

其中,ωs=2s,s=0,1,2,3,4,表示被安排的沖突考試的時(shí)間間隔為4,3,2,1,0的相應(yīng)懲罰值;Ns表示參加這些考試的學(xué)生總數(shù);S表示學(xué)生總?cè)藬?shù).

2 求解考試時(shí)間表問(wèn)題的進(jìn)化多目標(biāo)優(yōu)化算法

圖1 算法流程圖

筆者是在文獻(xiàn)[12]的基礎(chǔ)上,針對(duì)算法的種群初始化操作,引入了超啟發(fā)方法;在算法的克隆操作中,設(shè)計(jì)了一種新的資源分配模型,是一種關(guān)于多目標(biāo)考試時(shí)間表問(wèn)題的NNIA改進(jìn)算法,所以除種群初始化操作與克隆操作外,算法中的其他所有操作算子及算法流程與文獻(xiàn)[12]的完全相同,算法流程如圖1所示.

2.1 資源分配模型

NNIA是一種經(jīng)典的進(jìn)化多目標(biāo)優(yōu)化算法,在此算法的運(yùn)行過(guò)程中,只是采用少數(shù)的非支配個(gè)體進(jìn)行操作,考慮到文中采用的多目標(biāo)考試時(shí)間表的建模方式,在算法運(yùn)行過(guò)程中,當(dāng)出現(xiàn)非支配解數(shù)量不足的情況時(shí),必然會(huì)對(duì)NNIA框架下的算法性能產(chǎn)生十分明顯的影響.文中在采用NNIA算法框架的基礎(chǔ)上,在個(gè)體克隆階段,設(shè)計(jì)了一種基于博弈論的資源分配模型,通過(guò)動(dòng)態(tài)控制優(yōu)勢(shì)個(gè)體的克隆數(shù)量手段,更加合理地分配計(jì)算資源.

在資源分配模型中,根據(jù)非支配排序關(guān)系,待克隆的個(gè)體首先被劃分為不同的等級(jí)(Rank1,…,Rankn),其中,Ranki代表了第i等級(jí)的個(gè)體的數(shù)量.通常情況下,Rank1中的個(gè)體優(yōu)于其他個(gè)體.根據(jù)Rank1個(gè)體在所有待克隆個(gè)體中所占的比例r,將資源分配模型分解為早期模型、中期模型和后期模型.算法在運(yùn)行過(guò)程中,根據(jù)不同的模型,采用相應(yīng)的克隆策略.

(1)早期模型(r≤1/3).在此階段只有很少的優(yōu)秀個(gè)體(Rank1個(gè)體),根據(jù)博弈論的相關(guān)概念,需要抑制Rank2中個(gè)體的克隆數(shù)量,以保證其無(wú)法影響到Rank1中的個(gè)體,即

其中,Si表示原始的克隆尺寸,Mi表示資源分配模型計(jì)算過(guò)后,克隆后第i級(jí)別的克隆規(guī)模.

(2)中期模型(1/3＜r＜2/3).在此階段優(yōu)秀個(gè)體的數(shù)量增多,但依然無(wú)法忽視其他級(jí)別的個(gè)體對(duì)其影響,因此,需要抑制除Rank1外的其他個(gè)體的克隆數(shù)量,即

(3)后期模型(r≥2/3).在此階段優(yōu)秀個(gè)體已經(jīng)占據(jù)了很大的比例,其他個(gè)體對(duì)其影響可忽略不計(jì),因此,只需按照所有個(gè)體之間的擁擠度距離進(jìn)行等比例克隆.

2.2 基于超啟發(fā)方法的種群初始化

許多學(xué)者的研究及仿真實(shí)驗(yàn)表明[1],基于圖著色的超啟發(fā)方法十分適合處理單目標(biāo)考試時(shí)間表問(wèn)題.采用超啟發(fā)方法擁有更大幾率快速找到可行解或潛在的優(yōu)勢(shì)個(gè)體.針對(duì)文中所面對(duì)的多目標(biāo)考試時(shí)間表問(wèn)題,若能快速得到可行解或潛在的優(yōu)勢(shì)個(gè)體,在固定的算法迭代次數(shù)的條件下,則更加有利于得到更好的結(jié)果.因此,文中采用基于圖著色的超啟發(fā)方法生成初始種群,初始種群是由一定數(shù)量的初始解(時(shí)間表)構(gòu)成的.首先,隨機(jī)產(chǎn)生由不同圖啟發(fā)算法構(gòu)成的啟發(fā)式鏈表,根據(jù)啟發(fā)式鏈表,產(chǎn)生初始解(考試時(shí)間表).在產(chǎn)生初始解的過(guò)程中,每當(dāng)產(chǎn)生一個(gè)新的考試時(shí)間,表示通過(guò)這些不同的啟發(fā)式算法,可產(chǎn)生一個(gè)考試科目安排順序,在不違反硬約束的條件下,根據(jù)考試安排順序,每門(mén)考試隨機(jī)安排在時(shí)間段中.具體的超啟發(fā)方法請(qǐng)參看文獻(xiàn)[1].另外,文中采用二進(jìn)制編碼方式,其中,每一列代表1個(gè)時(shí)間段,每一行代表1門(mén)考試,數(shù)字1表示在此時(shí)段安排某門(mén)考試,0表示在此時(shí)段未安排考試.

3 仿真實(shí)驗(yàn)

文中選取Carter標(biāo)準(zhǔn)數(shù)據(jù)集[14]進(jìn)行測(cè)試.近幾十年來(lái),幾乎所有關(guān)于考試時(shí)間表算法的研究都采用此數(shù)據(jù)集進(jìn)行性能測(cè)試,但此數(shù)據(jù)仍是開(kāi)放數(shù)據(jù),理論最優(yōu)解仍然未知.文中選取了該數(shù)據(jù)集中的10個(gè)具有代表性的數(shù)據(jù),對(duì)提出的算法進(jìn)行仿真實(shí)驗(yàn).以下仿真均為10次獨(dú)立運(yùn)行實(shí)驗(yàn),運(yùn)行環(huán)境為2.8 GHz Core Personal Computer.具體參數(shù)為:種群大小m=100,每一種啟發(fā)式算法所要安排的考試數(shù)量e=2,交叉概率Pc=0.8,變異概率Pm=0.2,算法最大迭代次數(shù)Gmax=100.

表1 不同算法的實(shí)驗(yàn)結(jié)果對(duì)比

針對(duì)10個(gè)測(cè)試數(shù)據(jù),算法經(jīng)過(guò)10次獨(dú)立運(yùn)行,隨機(jī)選取一組解集,其Pareto前沿面如圖2所示.少數(shù)幾個(gè)測(cè)試集(Car91,Car92,Ear83等)在個(gè)別區(qū)域沒(méi)有找到非支配解.除上述測(cè)試集,大部分的測(cè)試集基本上能夠完整勾勒出兩目標(biāo)優(yōu)化的Pareto前沿面,并且對(duì)于每一組數(shù)據(jù)的Pareto解都可較為均勻地分布在其前沿面上.表1記錄了這些測(cè)試集最好的運(yùn)行結(jié)果,需要注意的是,此結(jié)果均為在單目標(biāo)優(yōu)化(固定時(shí)間表長(zhǎng)度,只優(yōu)化考試間沖突關(guān)系)的環(huán)境下產(chǎn)生的.筆者選取的運(yùn)行結(jié)果則是根據(jù)單目標(biāo)環(huán)境下的時(shí)間表長(zhǎng)度(P),在文中的多目標(biāo)算法運(yùn)行的結(jié)果中,選取的對(duì)應(yīng)結(jié)果.從對(duì)比結(jié)果來(lái)看,除數(shù)據(jù)集York83、文中算法均能找到與單目標(biāo)模型中相同的時(shí)間段.從具體結(jié)果上來(lái)說(shuō),文中結(jié)果的確與其他幾種最優(yōu)秀的單目標(biāo)優(yōu)化結(jié)果尚存一定差距,但差距并不明顯.重要的是采用文中提出的多目標(biāo)優(yōu)化算法,經(jīng)過(guò)1次運(yùn)行就可提供不同時(shí)間段的多個(gè)解,運(yùn)行效率是單目標(biāo)優(yōu)化的數(shù)十倍.上述結(jié)果表明,將考試時(shí)間表問(wèn)題按照多目標(biāo)優(yōu)化問(wèn)題建模有效,且可極大提高計(jì)算效率.

圖2 10組測(cè)試數(shù)據(jù)的Pareto前沿面示意圖

圖3 非支配解個(gè)數(shù)的統(tǒng)計(jì)盒圖

在NNIA框架下,在克隆階段采用了資源分配(Resource Assignment,RA)模型,此模型對(duì)于整個(gè)算法的影響可由下列實(shí)驗(yàn)得出結(jié)論.圖3為10組測(cè)試數(shù)據(jù)分別來(lái)自采用資源分配模型的RA-NNIA和未采用此模型的原始NNIA進(jìn)行10次獨(dú)立運(yùn)行后,非支配解個(gè)數(shù)的統(tǒng)計(jì)盒圖.針對(duì)每一個(gè)測(cè)試數(shù)據(jù),左邊采用RA-NNIA,右邊采用NNIA.可明顯看出,采用資源分配模型的RA-NNIA的非支配個(gè)體數(shù)量明顯好于未采用此模型的NNIA的.圖4為10組測(cè)試數(shù)據(jù),分別采用RA-NNIA和NNIA經(jīng)過(guò)10次獨(dú)立實(shí)驗(yàn)后,Spacing指標(biāo)的統(tǒng)計(jì)盒圖對(duì)比.由圖4可知,除少數(shù)幾組數(shù)據(jù)(Car92,Ear83)外,采用RA-NNIA算法的均勻性指標(biāo)都要優(yōu)于采用NNIA的運(yùn)行結(jié)果.

根據(jù)以上兩組實(shí)驗(yàn)結(jié)果分析可知,對(duì)于如此建模的多目標(biāo)考試時(shí)間表問(wèn)題,非支配解的數(shù)量本身就十分有限,傳統(tǒng)的NNIA僅采用當(dāng)前的非支配個(gè)體進(jìn)行克隆,而后進(jìn)行進(jìn)化操作,導(dǎo)致種群的多樣性難以保持,很可能會(huì)進(jìn)一步導(dǎo)致最終的非支配解數(shù)目不足,而RA-NNIA克隆階段,在非支配個(gè)體數(shù)量不足時(shí),還會(huì)利用少部分較好的支配個(gè)體,共同進(jìn)行克隆操作.并且,資源分配模型還會(huì)根據(jù)當(dāng)前非支配個(gè)體所占的比例,動(dòng)態(tài)控制每一部分個(gè)體的克隆比例,此種策略在一定的情況下可很好地改善傳統(tǒng)NNIA在這方面上的不足.所以,采用資源分配模型的NNIA是有利于非支配個(gè)體的產(chǎn)生與保留,有利于算法的多樣性的保持,此策略十分適合用于求解多目標(biāo)考試時(shí)間表問(wèn)題的多目標(biāo)進(jìn)化算法.

圖4 Spacing指標(biāo)的統(tǒng)計(jì)盒圖

4 結(jié)束語(yǔ)

筆者提出了一種解決多目標(biāo)考試時(shí)間表問(wèn)題的NNIA改進(jìn)算法.在非支配鄰域免疫算法的框架下,提出了一種資源分配模型,用來(lái)動(dòng)態(tài)控制個(gè)體的克隆比例,利用超啟發(fā)技術(shù)構(gòu)造初始種群.實(shí)驗(yàn)結(jié)果表明,采用筆者所提出的改進(jìn)的NNIA能夠更加有效地解決多目標(biāo)考試時(shí)間表問(wèn)題.另外,筆者也注意到,原始的解決此問(wèn)題的NNIA方法的局部搜索策略可在一定程度上改善種群的質(zhì)量,但仍有提高的空間.因此,針對(duì)此問(wèn)題,以及類似的調(diào)度問(wèn)題,如何來(lái)設(shè)計(jì)更加合理、出色的局部搜索策略將是今后有待研究的重要問(wèn)題.

參考文獻(xiàn):

[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]董寧,王宇平.求解約束優(yōu)化問(wèn)題的偏好多目標(biāo)進(jìn)化算法[J].西安電子科技大學(xué)學(xué)報(bào),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的多目標(biāo)時(shí)間表調(diào)度問(wèn)題研究[D].西安:西安電子科技大學(xué),2014.

[13]孫娜娜.基于MOEA/D的多目標(biāo)考試時(shí)間表調(diào)度算法研究[D].西安:西安電子科技大學(xué),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)

作者簡(jiǎn)介:雷 雨(1985-),男,西安電子科技大學(xué)博士研究生,E-mail:xdleiyu@gmail.com.

基金項(xiàng)目:國(guó)家自然科學(xué)基金資助項(xiàng)目(61273317)

收稿日期:2015-01-08 網(wǎng)絡(luò)出版時(shí)間:2015-05-21

doi:10.3969/j.issn.1001-2400.2016.02.027

中圖分類號(hào):TP18

文獻(xiàn)標(biāo)識(shí)碼:A

文章編號(hào):1001-2400(2016)02-0157-05

網(wǎng)絡(luò)出版地址:http://www.cnki.net/kcms/detail/61.1076.TN.20150521.0902.024.html