求解多目標考試時間表問題的NNIA改進算法

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

(西安電子科技大學智能感知與圖像理解教育部重點實驗室,陜西西安 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