教學(xué)資源配置優(yōu)化中遺傳算法的應(yīng)用與改進(jìn)

嚴(yán) 宏

(1.中國民用航空飛行學(xué)院,四川 廣漢 618307;2.四川大學(xué) 視覺合成圖形圖像技術(shù)國家重點(diǎn)學(xué)科實(shí)驗(yàn)室,四川 成都 610064)

教學(xué)資源配置優(yōu)化中遺傳算法的應(yīng)用與改進(jìn)

嚴(yán) 宏1,2

(1.中國民用航空飛行學(xué)院,四川 廣漢 618307;2.四川大學(xué) 視覺合成圖形圖像技術(shù)國家重點(diǎn)學(xué)科實(shí)驗(yàn)室,四川 成都 610064)

對(duì)于臨時(shí)新增教學(xué)任務(wù)，教學(xué)資源安排不同于學(xué)期開始前的教學(xué)資源配置，通常具有特定的配置需求。在教學(xué)資源有限的情況下，為了使新增教學(xué)班級(jí)配置的教室更加一致或接近，避免頻繁變動(dòng)教室給教學(xué)帶來的不便，使用遺傳算法進(jìn)行教室資源的分配，并根據(jù)應(yīng)用需求進(jìn)行了改進(jìn)。其中設(shè)計(jì)了更加適宜的十進(jìn)制編碼，提出的適應(yīng)度函數(shù)能有效地對(duì)教室資源的一致或接近程度進(jìn)行量化計(jì)算。根據(jù)染色體編碼特點(diǎn)和優(yōu)化目標(biāo)，對(duì)遺傳算子進(jìn)行選擇和改進(jìn)，特別對(duì)單點(diǎn)交叉進(jìn)行改進(jìn)盡可能地提高交叉后的適應(yīng)度，同時(shí)保持種群的多樣性。實(shí)驗(yàn)結(jié)果表明，改進(jìn)的遺傳算法相對(duì)于標(biāo)準(zhǔn)遺傳算法在用時(shí)更少的情況下得到的教學(xué)資源分配更加滿足優(yōu)化目標(biāo)，計(jì)算效率得以提高，并且成功應(yīng)用于實(shí)際的教學(xué)資源配置。

資源配置；遺傳算法；十進(jìn)制編碼；適應(yīng)度函數(shù)；交叉算子

0 引 言

近年來，隨著部分高校招生專業(yè)的新增和招生規(guī)模的擴(kuò)大，在一時(shí)難以增加相關(guān)教學(xué)資源的情況下，如何高效利用現(xiàn)有教學(xué)資源已成為教學(xué)實(shí)施過程中亟需解決的問題，關(guān)系著教學(xué)質(zhì)量的保證和提高。教學(xué)資源配置的高效合理除了在學(xué)期開始前的排課過程中需要考慮外，對(duì)于開學(xué)后臨時(shí)增加的教學(xué)計(jì)劃，比如在職人員培訓(xùn)班、補(bǔ)修班或者重修班，由于此時(shí)教學(xué)資源更為有限，更需要進(jìn)行資源的配置優(yōu)化。從本質(zhì)上講，這些新增教學(xué)班級(jí)的安排其實(shí)是排課問題，而排課問題已被S. Even以及Cooper等證明為NP完全問題[1-2]。對(duì)于這類完全多項(xiàng)式非確定性問題，雖然可以在多項(xiàng)式時(shí)間內(nèi)進(jìn)行驗(yàn)算，然后再使用窮舉法得到問題的解，但是這種方式下計(jì)算時(shí)間隨問題復(fù)雜程度呈指數(shù)增長，因此這種求解算法不具有實(shí)際的應(yīng)用價(jià)值。為了滿足實(shí)際應(yīng)用中對(duì)于計(jì)算性能的要求，對(duì)于NP完全問題通常采用求近似解的策略，此類算法中的遺傳算法正是通過模擬自然進(jìn)化過程搜索近似最優(yōu)解，具有成熟的理論作為基礎(chǔ)，應(yīng)用較為廣泛。

由美國的J. Holland教授在1975年提出的遺傳算法[3]借鑒了基因遺傳和生物進(jìn)化的思想，通過選擇、交叉、變異等遺傳算子使種群不斷進(jìn)化，從而得到局部最優(yōu)解或全局最優(yōu)解。它是一種有效的隨機(jī)搜索優(yōu)化算法，具有并行性、自適應(yīng)和學(xué)習(xí)性、魯棒性以及易于與其他算法結(jié)合改進(jìn)的特點(diǎn)，被廣泛用于排課這類資源配置的組合優(yōu)化問題。

文獻(xiàn)[4]提出了遺傳算法在課程安排問題中多點(diǎn)式搜索和優(yōu)化方法；文獻(xiàn)[5]論述了使用遺傳算法解決排課問題中教師優(yōu)先權(quán)的問題；文獻(xiàn)[6]在遺傳算法中引入排課規(guī)則解決了按優(yōu)先級(jí)排課的問題；文獻(xiàn)[7]在遺傳算法應(yīng)用于排課過程中提出優(yōu)勢(shì)群體有限策略和最優(yōu)個(gè)體替換策略；文獻(xiàn)[8]對(duì)用于排課系統(tǒng)的遺傳算法在染色體編碼和交叉變異概率選擇方面進(jìn)行了改進(jìn)；文獻(xiàn)[9]主要針對(duì)多校區(qū)排課問題進(jìn)行優(yōu)化；文獻(xiàn)[10]在遺傳算法中采用了群體優(yōu)勢(shì)策略。

文中論述的新增教學(xué)班級(jí)的教學(xué)資源配置優(yōu)化問題雖然在實(shí)質(zhì)上為排課問題，但是不同于多個(gè)班級(jí)的整體性排課，在應(yīng)用環(huán)境及優(yōu)化目標(biāo)方面存在區(qū)別，比如上課時(shí)間事先已經(jīng)確定和需要盡量固定的教室，難以完全利用針對(duì)整體性排課的編碼方式、適應(yīng)度函數(shù)以及交叉和變異算子，需要進(jìn)行改進(jìn)以便更好地符合應(yīng)用需求。

1 數(shù)學(xué)模型和優(yōu)化目標(biāo)

1.1 數(shù)學(xué)模型

教學(xué)資源配置在教學(xué)過程中一項(xiàng)常見的工作就是進(jìn)行課程安排，而排課涉及到的教學(xué)資源主要是教師、教室、課程、班級(jí)和上課時(shí)段。在此設(shè)定條件下，排課過程中教學(xué)資源配置優(yōu)化問題可以描述為求構(gòu)成解空間的五元組(C,O,T,R,S)。其中,C表示班級(jí)，O表示課程，T表示教師，R表示教室，S表示上課時(shí)段。

對(duì)于上述開學(xué)后臨時(shí)增加的教學(xué)計(jì)劃安排問題，由于教學(xué)資源的有限性，在新增教學(xué)班級(jí)的教學(xué)資源配置優(yōu)化時(shí)必然存在資源的約束性，其中與現(xiàn)有排課數(shù)據(jù)之間存在上課時(shí)段和教室使用方面的約束關(guān)系。對(duì)應(yīng)于現(xiàn)有排課數(shù)據(jù)和新增教學(xué)班級(jí)安排的兩個(gè)五元組(Ci,Oi,Ti,Ri,Si)和(Cj,Oj,Tj,Rj,Sj)，必須滿足如下關(guān)系：

Si=Sj→Ti≠Tj

(1)

Si=Sj→Ri≠Rj

(2)

上述兩個(gè)關(guān)系式中，式(1)表示不同教學(xué)班級(jí)在同一時(shí)段的教師不應(yīng)相同，否則造成沖突，同樣式(2)表示不同教學(xué)班級(jí)在同一時(shí)段安排的教室應(yīng)該分屬不同的教室。在實(shí)際的教學(xué)資源配置過程中，對(duì)于這類新增的教學(xué)班級(jí)，通常已通過教師上課時(shí)間的協(xié)調(diào)或外聘教師等方法做好上課時(shí)段和上課教師的安排，那么上述約束關(guān)系式(1)可以不予考慮，而約束關(guān)系式(2)必須滿足，否則將引起教室使用方面的沖突。

1.2 優(yōu)化目標(biāo)

對(duì)于這類新增的教學(xué)班級(jí)，由于講授的內(nèi)容和參加學(xué)習(xí)的人員早已確定，對(duì)應(yīng)于五元組(C,O,T,R,S)中課程O和班級(jí)C的值得以確定，而從以上論述可知對(duì)于新增教學(xué)班級(jí)的上課時(shí)段和上課教師已做好安排，即五元組(C,O,T,R,S)中上課時(shí)段S和教師T的值得以確定，那么就需要對(duì)五元組中還未確定的教室進(jìn)行組合配置。

而對(duì)于這類新增教學(xué)班級(jí)的教室配置，滿足上述式(2)這個(gè)硬性約束的解是可行解，求解的目標(biāo)是從可行解中找出更加優(yōu)化的解，優(yōu)化的目標(biāo)是盡量配置為同一教室或者相近的教室，也就是說最好將教室這個(gè)教學(xué)資源配置為同一教室，這樣可以避免給參與教學(xué)的教師和學(xué)生帶來教室變動(dòng)的不便，也是為了盡量減少教室安排帶來其他方面的事宜，如減輕物業(yè)管理工作量。在教室資源緊張難以配置為同一教室的情況下，不同時(shí)段配置的教室變動(dòng)盡量減少，使教師和學(xué)生在教學(xué)任務(wù)的參與當(dāng)中更加方便高效，這是文中使用遺傳算法進(jìn)行優(yōu)化的目標(biāo)，也是遺傳算法中適應(yīng)度函數(shù)設(shè)計(jì)的參考依據(jù)。

2 算法設(shè)計(jì)及流程

使用遺傳算法求解問題通常包含如下的關(guān)鍵步驟：染色體編碼、種群初始化、適應(yīng)度函數(shù)的設(shè)計(jì)、選擇操作、交叉操作、變異操作以及終止條件的確定。

2.1 可行解空間及染色體編碼

在優(yōu)化求解問題中，滿足所有約束條件的解便是該問題的一個(gè)可行解，而所有的可行解便構(gòu)成了可行解空間。優(yōu)化解便是其中能夠更好滿足優(yōu)化目標(biāo)的可行解，因此尋求優(yōu)化解需要確定可行解空間，非可行解即使能更好地滿足優(yōu)化目標(biāo)也不能稱之為優(yōu)化解。

從上述論述可知，可行解中五元組(C,O,T,R,S)的C,O,T和S已確定，剩下R對(duì)應(yīng)的教室應(yīng)不和現(xiàn)有的排課數(shù)據(jù)沖突，而文中針對(duì)的教務(wù)管理系統(tǒng)能夠提供接口獲取在指定時(shí)段內(nèi)空閑的所有教室，也就是說能獲取上課時(shí)段S內(nèi)滿足約束的空閑教室R，從而組成五元組構(gòu)成可行解。

為了便于描述并且不失一般性，假設(shè)新增教學(xué)班級(jí)有N個(gè)上課時(shí)段，這些時(shí)段按時(shí)間先后的順序排序并表示成S1,S2,…,SN，那么可以通過系統(tǒng)接口獲取各個(gè)上課時(shí)間段對(duì)應(yīng)的空間教室集合，同樣對(duì)應(yīng)時(shí)間先后順序依次表示為{R1},{R2},…,{RN}，依次選取各個(gè)集合中的教室組成五元組(Ci,Oi,Ti,Ri,Si)，通過這樣的組合方式形成的所有五元組就構(gòu)成了可行解空間。

遺傳算法采用仿生過程搜索優(yōu)化解，模擬的是基因重組與進(jìn)化的過程，把待解決問題的解轉(zhuǎn)換成特定形式的編碼，這種形式編碼中特定一段對(duì)應(yīng)的稱之為基因，這樣若干基因中組成一個(gè)染色體，一個(gè)染色體便可以對(duì)應(yīng)優(yōu)化問題的一個(gè)解。染色體編碼是把優(yōu)化問題的解從其解空間中的形式轉(zhuǎn)換到遺傳算法所能處理的搜索空間中的形式，這個(gè)過程是應(yīng)用遺傳算法進(jìn)行優(yōu)化過程的首要步驟，關(guān)系到后續(xù)遺傳操作算子的設(shè)計(jì)和效率,也和遺傳算法的收斂速度緊密相關(guān)。

為了減小染色體編碼的長度，縮小搜索空間，對(duì)于五元組中已確定的C,O,T和S不再編碼，而只對(duì)各個(gè)上課時(shí)段的教室進(jìn)行編碼。為了實(shí)現(xiàn)存取的高效，將獲取的各個(gè)時(shí)段空閑教室集合分別采用數(shù)組方式存儲(chǔ)，那么對(duì)各個(gè)時(shí)段的配置教室就只需對(duì)相應(yīng)的數(shù)組下標(biāo)進(jìn)行編碼。文中采用十進(jìn)制編碼而并未采用最為常見的二進(jìn)制編碼方法[11]，原因在于二進(jìn)制編碼除了編碼較長、搜索空間較大和編解碼比較費(fèi)時(shí)的缺點(diǎn)，還存在漢明懸崖(HammingCliff)的問題[12]，即相鄰整數(shù)的二進(jìn)制代碼之間有很大的漢明距離，使得遺傳算法的交叉和突變都難以跨越，而使用十進(jìn)制編碼對(duì)于數(shù)組下標(biāo)來說更加直接高效。具體的編碼方式為每一個(gè)可行解對(duì)應(yīng)的染色體由多個(gè)基因構(gòu)成，每個(gè)基因?qū)?yīng)課程安排中的一個(gè)上課時(shí)段，其十進(jìn)制編碼經(jīng)過解碼轉(zhuǎn)換后為對(duì)應(yīng)時(shí)段空閑教室集合中配置教室的所在下標(biāo)。染色體的編碼方式和空閑教室集合的存儲(chǔ)方式如圖1所示。

圖1 染色體的編碼方式和空閑教室集合的存儲(chǔ)方式

基因編碼的十進(jìn)制整數(shù)Di并未直接用于表示所選教室的下標(biāo)Ei，而是需要進(jìn)行如下轉(zhuǎn)換：

Ei=DiMODAi

其中，Ai為基因?qū)?yīng)時(shí)段空閑教室集合中教室的總數(shù)，即存儲(chǔ)教室集合的數(shù)組大小。

由于每個(gè)時(shí)段的空閑教室總數(shù)不同，那么每個(gè)基因?qū)?yīng)數(shù)組的大小不一，選擇這種取模的方式，可以在隨機(jī)生成初始種群和后續(xù)交叉及變異操作中不用分別考慮每個(gè)數(shù)組的下標(biāo)越界問題，編碼和轉(zhuǎn)換的方法更加統(tǒng)一和高效。

2.2 初始種群的生成

在確定好染色體編碼方式后，遺傳算法首先需要獲得一組處于初始狀態(tài)的染色體，這組染色體是后續(xù)選擇、交叉、變異等操作的基礎(chǔ)，是最終優(yōu)化解獲取的數(shù)據(jù)來源，通常被稱為初始種群。進(jìn)行初始種群的生成主要涉及兩個(gè)方面的問題：種群規(guī)模的大小和初始種群各染色體的生成方式。其中，種群規(guī)模的大小直接影響到遺傳算法的收斂性和計(jì)算效率。規(guī)模太小，染色體多樣性的欠缺容易導(dǎo)致收斂到局部最優(yōu)解；規(guī)模太大，計(jì)算復(fù)雜費(fèi)時(shí)且難以收斂。

文中根據(jù)文獻(xiàn)[12]中種群規(guī)模的建議范圍，將群體規(guī)模設(shè)定為200。根據(jù)上述對(duì)編碼方式的描述可知，在不考慮數(shù)組下標(biāo)越界問題的情況下，可以使用隨機(jī)生成的十進(jìn)制無符號(hào)整數(shù)作為基因編碼，按照新增教學(xué)計(jì)劃所需的上課時(shí)段總數(shù)生成相同數(shù)量的基因，然后將這些基因連接從而生成初始種群中的染色體。

2.3 適應(yīng)度函數(shù)的實(shí)現(xiàn)

使用遺傳算法進(jìn)行優(yōu)化求解，目標(biāo)是為了獲取更好滿足優(yōu)化目標(biāo)的可行解，體現(xiàn)為通過遺傳算法使初始種群通過進(jìn)化后得到對(duì)于優(yōu)化目標(biāo)來說更加優(yōu)秀的染色體，在此過程中就需要度量指標(biāo)去計(jì)算染色體的優(yōu)化程度。在遺傳算法的命名慣例中，適應(yīng)度是群體中各個(gè)染色體優(yōu)劣程度的量化指標(biāo)。文中優(yōu)化的目標(biāo)是讓可行解中各個(gè)時(shí)段選擇的教室盡量一致或接近，其程度可以通過教學(xué)樓、樓層以及樓層中位置這三個(gè)參數(shù)計(jì)算。這個(gè)問題可以分解為逐次分析每個(gè)時(shí)段與后續(xù)時(shí)段在教室配置方面的一致或接近程度，并使用以下目標(biāo)函數(shù)進(jìn)行量化：

f(Ri,Ri+1)=0.5b(Ri,Ri+1)+0.3e(Ri,Ri+1)+ 0.2m(Ri,Ri+1)

其中，Ri和Ri+1分別表示前后兩個(gè)時(shí)段配置的教室；b(Ri,Ri+1)、e(Ri,Ri+1)和m(Ri,Ri+1)三個(gè)函數(shù)分別對(duì)前后兩個(gè)教室的所在教學(xué)樓、所在樓層以及樓層中位置的一致或接近程度進(jìn)行量化計(jì)算，前面對(duì)應(yīng)的系數(shù)可以實(shí)現(xiàn)按權(quán)重求和，系數(shù)對(duì)應(yīng)的權(quán)重目前根據(jù)實(shí)際工作經(jīng)驗(yàn)對(duì)教學(xué)樓、所在樓層以及樓層中位置的重要性來確定，待以后研究中再進(jìn)行優(yōu)化改進(jìn)。f(Ri,Ri+1)的值越小，表示前后兩個(gè)教室越接近，當(dāng)f(Ri,Ri+1)的值為零時(shí)，前后兩個(gè)教室相同。而遺傳算法中染色體的適應(yīng)度越大，該染色體對(duì)應(yīng)可行解能更好地滿足優(yōu)化目標(biāo)，也就是說染色體表示各個(gè)時(shí)段配置的教室更加接近，所以需要將目標(biāo)函數(shù)進(jìn)行適當(dāng)?shù)霓D(zhuǎn)換形成如下的適應(yīng)度函數(shù)：

Fit(R1,R2,…,RN)=

該適應(yīng)度函數(shù)的設(shè)計(jì)思路為依次將前N-1個(gè)時(shí)段的目標(biāo)函數(shù)f累加，然后除以N-1求平均值，這樣針對(duì)上課時(shí)段總數(shù)不同的情況更加公平，最后通過乘以系數(shù)β(文中取0.05)進(jìn)行指數(shù)比例變換。這樣當(dāng)各個(gè)時(shí)段配置的教室越接近時(shí)，適應(yīng)度越大，特別是在所有配置的教室相同時(shí)，適應(yīng)度取得理想的最大值1，可以確定得到該種情況下教學(xué)資源配置的最優(yōu)解。

2.4 遺傳算子的實(shí)現(xiàn)

2.4.1 選擇算子

從本質(zhì)上講，達(dá)爾文的自然選擇學(xué)說是遺傳算法的理論基礎(chǔ)，其中選擇是在群體中選擇生命力強(qiáng)的個(gè)體產(chǎn)生新的群體的過程，為保留優(yōu)良個(gè)體和種群多樣性提供驅(qū)動(dòng)力。目前，遺傳算法中常用的選擇算子有輪盤賭選擇[13]、隨機(jī)競爭選擇、最佳保留選擇、穩(wěn)態(tài)復(fù)制等。

文中使用最佳保留選擇作為選擇算子，具體操作為：將所有個(gè)體按適應(yīng)度從大到小排序，然后按一定比例選出前面適應(yīng)度較大的個(gè)體直接復(fù)制到下一代，不足種群規(guī)模的個(gè)體用隨機(jī)生成的方法補(bǔ)充。最佳保留選擇的實(shí)現(xiàn)簡單高效，既保留了進(jìn)化過程中出現(xiàn)的優(yōu)良個(gè)體并及時(shí)淘汰不良個(gè)體，又實(shí)現(xiàn)了個(gè)體的多樣性，避免了優(yōu)化過程過早地陷入局部最優(yōu)解。文中使用的最佳保留選擇比例因子為0.3。

2.4.2 交叉算子

模仿兩個(gè)染色體通過交配而重組形成新的個(gè)體的過程，遺傳算法使用交叉算子來產(chǎn)生新的染色體，是區(qū)別于其他進(jìn)化算法的重要特征。交叉算子的設(shè)計(jì)包括交叉點(diǎn)定位和基因交換方式兩方面的內(nèi)容。標(biāo)準(zhǔn)遺傳算法中的交叉算子是使用單點(diǎn)交叉[14]，文中實(shí)現(xiàn)也采用此交叉算子并在如何確定交叉點(diǎn)的位置方面進(jìn)行了改進(jìn)，不再簡單地直接使用隨機(jī)確定的交叉點(diǎn)位置，而是從交換后是否可以得到一個(gè)適應(yīng)度更大的染色體來考慮，具體流程描述如下：

(1)對(duì)于隨機(jī)配對(duì)的兩個(gè)染色體a和b，按交叉概率Pc進(jìn)行下面的交叉互換操作。

(2)隨機(jī)選擇一個(gè)位置作為參考點(diǎn)i。

(3)從參考點(diǎn)i開始向后搜索一個(gè)位置k使得交叉配對(duì)的兩個(gè)染色體a和b滿足條件：

(4)如果向后未找到符合條件的位置k，則從參考點(diǎn)i向前搜索符合步驟(3)中條件的位置k；

(5)如果向前還是未找到符合條件的位置k，則k=i；

(6)使用k為交叉點(diǎn)位置，交換交叉配對(duì)的兩個(gè)染色體的部分基因。

使用上述交叉算子，除了未找到符合條件的交叉點(diǎn)k的情況，都能夠使交叉互換后的一個(gè)染色體在位置k和k+1上對(duì)應(yīng)的教室相同，從而進(jìn)一步提高適應(yīng)度，得到更加優(yōu)良的個(gè)體。另外對(duì)于交叉互換后的另一個(gè)染色體也保持了原有的單點(diǎn)交叉方式，用于維持種群的多樣性。

2.4.3 變異算子

模仿生物遺傳和進(jìn)化過程中某些基因發(fā)生變異的環(huán)節(jié)，遺傳算法使用變異算子在種群中產(chǎn)生出新的染色體，可以改善局部搜索能力和維持群體的多樣性。針對(duì)文中染色體采用十進(jìn)制編碼的特點(diǎn)，為了更好地改善局部搜索能力以及防止搜索陷入局部次優(yōu)解，設(shè)計(jì)的變異算子在借鑒現(xiàn)有常用變異算子的基礎(chǔ)上實(shí)現(xiàn)針對(duì)性的改進(jìn)，流程如下：

(1)按變異概率Pm選取進(jìn)行變異操作的染色體；

(2)隨機(jī)選擇一個(gè)位置作為變異位置；

(3)根據(jù)位置的奇偶性分別對(duì)變異位置的十進(jìn)制編碼進(jìn)行加1和減1，然后按編碼范圍取模，將所得結(jié)果替代原有十進(jìn)制編碼。

2.5 終止條件的確定

在種群的進(jìn)化過程中需要制定優(yōu)化終止的條件，從而能在適當(dāng)?shù)臅r(shí)間內(nèi)得到優(yōu)化解，滿足計(jì)算性能方面的可行性。文中在常見的進(jìn)化終止代數(shù)的基礎(chǔ)上，還考慮到可能出現(xiàn)所有配置教室相同的最優(yōu)解，設(shè)計(jì)的適應(yīng)度函數(shù)將會(huì)出現(xiàn)最大值1，因此制定了以下兩個(gè)條件：

(1)進(jìn)化代數(shù)達(dá)到指定的最大進(jìn)化代數(shù)；

(2)出現(xiàn)了適應(yīng)度等于1的個(gè)體。

當(dāng)這兩個(gè)條件其中之一滿足時(shí)，種群的進(jìn)化過程終止，輸出種群中適應(yīng)度最大的個(gè)體對(duì)應(yīng)的優(yōu)化解。

2.6 遺傳算法的實(shí)現(xiàn)

在上述幾個(gè)遺傳算法重要步驟的基礎(chǔ)上，進(jìn)一步確定各個(gè)步驟的執(zhí)行條件和順序，總結(jié)實(shí)現(xiàn)的遺傳算法流程，如圖2所示。

圖2 遺傳算法流程

3 實(shí)驗(yàn)結(jié)果及分析

將針對(duì)文中應(yīng)用環(huán)境進(jìn)行改進(jìn)的遺傳算法(DGA)和標(biāo)準(zhǔn)遺傳算法(SGA)進(jìn)行實(shí)驗(yàn)對(duì)比，試驗(yàn)中SGA使用和DGA一樣的適應(yīng)度函數(shù)，但是在染色體編碼方面使用二進(jìn)制編碼，編碼方法將DGA初始種群中的十進(jìn)制編碼轉(zhuǎn)換為二進(jìn)制編碼，這樣可以使對(duì)比實(shí)驗(yàn)在相同初始種群的條件下進(jìn)行，更加公平。

SGA中選擇算子使用經(jīng)典遺傳算法中常采用的輪盤賭選擇[13]，交叉算子和變異算子分別使用針對(duì)二進(jìn)制編碼單點(diǎn)交叉和基本位變異。另外，DGA和SGA使用如下相同的參數(shù)：上課時(shí)段數(shù)為32，群體規(guī)模設(shè)為200，最大進(jìn)化代數(shù)設(shè)為500，交叉概率Pc設(shè)為0.6，變異概率Pm設(shè)為0.05。

為了對(duì)比DGA與SGA在進(jìn)化中的適應(yīng)度變化情況，每進(jìn)化5代就記錄種群中的最大適應(yīng)度。考慮到遺傳算法的隨機(jī)性，DGA與SGA的對(duì)比實(shí)驗(yàn)一共進(jìn)行20次，取這20次數(shù)據(jù)的平均值作對(duì)比，結(jié)果如圖3所示。

從圖3中可以看出，DGA相對(duì)于SGA在進(jìn)化過程中能產(chǎn)生更為優(yōu)化的解，而且SGA相對(duì)較快地收斂到一個(gè)適應(yīng)度較小的解，體現(xiàn)了SGA早熟的缺點(diǎn)。

為了對(duì)比DGA和SGA的用時(shí)，在上述實(shí)驗(yàn)中每進(jìn)化5代就記錄一個(gè)總共耗費(fèi)時(shí)間，對(duì)比結(jié)果如圖4所示。

由圖4得知，DGA相對(duì)于SGA用時(shí)更少，主要原因在于針對(duì)文中應(yīng)用環(huán)境，十進(jìn)制編碼相對(duì)二進(jìn)制編碼編解碼更加簡單高效，提高了計(jì)算效率，而且十進(jìn)制編碼長度更短，這也降低了算法的空間復(fù)雜度。

圖3 DGA和SGA的適應(yīng)度對(duì)比

圖4 DGA和SGA的用時(shí)對(duì)比

4 結(jié)束語

改進(jìn)后的遺傳算法除了已在中國民航飛行學(xué)院教學(xué)工作中滿足了實(shí)際應(yīng)用需求，還在對(duì)比試驗(yàn)中相對(duì)于標(biāo)準(zhǔn)遺傳算法用時(shí)更少，而且得到的解更加優(yōu)化。另外，量化教室配置優(yōu)化程度的適應(yīng)度函數(shù)可以在不同應(yīng)用需求下進(jìn)行改進(jìn)，比如權(quán)重系數(shù)調(diào)整。這種根據(jù)應(yīng)用環(huán)境特點(diǎn)改進(jìn)遺傳算法的思路還可以針對(duì)其他類型的教學(xué)資源配置優(yōu)化進(jìn)行功能拓展。

[1]EvenS,ItaiA,ShamirA.Onthecomplexityoftimetableandmulti-commodityflowproblems[C]//ProcofIEEEsymposiumonfoundationsofcomputerscience.[s.l.]:IEEE,1975:184-193.

[2]TimB,CooperJ,KingstonH.Thecomplexityoftimetableconstructionproblems[C]//ProcofICPTAT’95.[s.l.]:[s.n.],1995.

[3]HollandJH.Adaptationinnatureandartificialsystems[M].Michigan:UniversityofMichiganPress,1975.

[4]LimkarS,KhalwadekarA,TekaleA,etal.Geneticalgorithm:paradigmshiftoveratraditionalapproachoftimetablescheduling[C]//Proceedingsofthe3rdinternationalconferenceonfrontiersofintelligentcomputing:theoryandapplications.[s.

l.]:Springer,2015:771-780.

[5]SbeityI,DboukM,KobeissiH.Combiningtheanalyticalhierarchyprocessandthegeneticalgorithmtosolvethetimetableproblem[J].EprintArxiv,2014,5(4):39-50.

[6] 郭俊恩,刁文廣.基于規(guī)則和遺傳算法的實(shí)驗(yàn)室排課算法研究[J].河南大學(xué)學(xué)報(bào):自然科學(xué)版,2014,44(3):355-359.

[7] 劉仁誠,馮秀蘭.基于改進(jìn)遺傳算法的排課問題研究[J].科技通報(bào),2013,29(5):160-163.

[8] 于 娟,尹積棟.面向排課系統(tǒng)的遺傳算法改進(jìn)研究[J].太原理工大學(xué)學(xué)報(bào),2012,43(5):572-574.

[9] 石 慧,彭曉紅,鄔志紅,等.求解多校區(qū)排課問題的基因?qū)徊孢z傳算法[J].計(jì)算機(jī)工程與應(yīng)用,2010,46(18):240-243.

[10] 李紅嬋,戶 剛,朱顥東.基于群體優(yōu)勢(shì)遺傳算法的高校排課問題研究[J].計(jì)算機(jī)工程與應(yīng)用,2011,47(10):233-236.

[11] 孫 彤,郭倩倩.基于新型免疫遺傳算法的高校排課仿真研究[J].計(jì)算機(jī)仿真,2012,29(2):386-391.

[12] 雷英杰,張善文.MATLAB遺傳算法工具箱及應(yīng)用[M].西安:西安電子科技大學(xué)出版社,2014.

[13] 祝勇仁,曹煥亞.應(yīng)用遺傳算法求解排課問題[J].計(jì)算機(jī)應(yīng)用與軟件,2007,24(12):130-132.

[14] 劉青鳳.遺傳算法在教學(xué)任務(wù)分配中的應(yīng)用[J].制造業(yè)自動(dòng)化,2010,32(10):203-205.

Application and Improvement of Genetic Algorithm for Optimization in Allocating Teaching Resources

YAN Hong1,2

(1.Civil Aviation Flight University of China,Guanghan 618307,China;2.National Key Laboratory of Fundamental Science on Synthetic Vision,Sichuan University,Chengdu 610064,China)

For temporarily added curriculum,the arrangement of teaching resources which usually has some specific requirements is different from that done before a semester begins.In the case of limited teaching resources,an improved genetic algorithm was proposed for optimizing the consistency and nearness of the classrooms allocated for temporary curriculum,with aim to avoid the inconvenience to teaching caused by frequent change of classrooms.Based on the requirement of the given application in this paper,a more efficient decimal encoding was developed.Correspondingly,a suitable fitness function was proposed to quantitatively calculate the consistency and nearness of the allocated classrooms.According to the characteristic of the chromosome encoding and the optimization goal,the algorithm selected existing genetic operators and improved them,especially the modified one-point crossover that attempts to enhance the fitness value and maintain the diversity of population.The experimental results show that the improved genetic algorithm,which has been successfully applied,can achieve more optimal solution within a shorter period of time when compared with the standard genetic algorithm.

resources allocation;genetic algorithm;decimal encoding;fitness function;crossover operator

2015-05-20

2015-08-21

時(shí)間：2016-01-

中國民用航空局民航科技創(chuàng)新引導(dǎo)資金(C2013041)

嚴(yán) 宏(1984-),男,講師,博士研究生,研究方向?yàn)樽顑?yōu)化計(jì)算、機(jī)器學(xué)習(xí)。

TP18

A

1673-629X(2016)03-0130-05

10.3969/j.issn.1673-629X.2016.03.031