劉長騫

(淄博職業(yè)學(xué)院現(xiàn)代教育技術(shù)中心,山東淄博255314)

計算機智能組卷的實質(zhì)是求解出滿足用戶輸入?yún)?shù)的一套最優(yōu)試卷,因此組卷問題是一個典型的約束滿足問題的求解過程.遺傳算法則由于自身具有全局搜索性、隨機性、較好的編碼方式和高度的并行性的特點,因此當(dāng)前許多組卷算法都在考慮使用遺傳算法進行求解.國內(nèi)外已有許多學(xué)者進行了這方面的研究,D.B.Fogeol提出把遺傳算法用于試題組卷,GordbergM.W應(yīng)用遺傳算法的尋優(yōu)特性為組卷問題建立了尋優(yōu)模型等.

1 改進遺傳算法

遺傳算法一般采用定長二進制串編碼方式,問題的一個解對應(yīng)一個長度為k的二進制串.從初始種群出發(fā),采用一定的選擇策略,在當(dāng)前種群中選擇個體,使用雜交和變異遺傳算子來產(chǎn)生下一代種群.如此一代代遺傳下去,直到滿足期望的終止條件.

傳統(tǒng)遺傳算法可以從很差的個體逐漸搜索到較好的個體,對領(lǐng)域知識要求也很少,是一種通用的有效的解決方法,但它的求解質(zhì)量和效率都不理想,計算時間也很長,還存在著以下幾個問題亟待解決:

遺傳算法用適應(yīng)度作為選種的選擇壓力,如果群體的適應(yīng)度變化不大或者過大,會引起選擇壓力不足或者波動,導(dǎo)致迭代過程過早收斂或發(fā)生振蕩.

由于后代完全替換雙親,優(yōu)良基因結(jié)構(gòu)被交叉破壞的可能性較大,以致延緩群體性能的進化.

各代群體中的最優(yōu)個體未得到保護,劣質(zhì)個體有可能會取代優(yōu)良個體.

求解的終止條件一般采用繁衍代數(shù)(迭代次數(shù))作為準則,含有很大的人為因素,使算法可能收斂不到極值點.

鑒于傳統(tǒng)遺傳算法存在的不足,為提高遺傳操作在組卷算法中的搜索能力,我們從遺傳操作、控制參數(shù)等方面對其加以改進,使其功能更為強大.

1.1 動態(tài)調(diào)整交換算子和變異算子

遺傳算法在很多具體應(yīng)用中容易出現(xiàn)所謂“早熟收斂”現(xiàn)象,即在早期可以迅速地達到次優(yōu)解接近最優(yōu)解,但此后搜索到最優(yōu)解的速度就慢下來了.其原因是遺傳算法主要通過交換算子繁殖后代.由于交換算子所作用的兩個個體相同時,不能產(chǎn)生有意義的新的個體,因此初始種群一般都要求具有廣泛多樣性.應(yīng)用中一般都采用較大的交換概率和較小的變異概率,并且這兩個概率參數(shù)在整個搜索過程中往往不變,算法可以迅速接近最優(yōu)解.但在最優(yōu)解附近,當(dāng)群體進化到其中的各個個體均相同時,交換算子無效,此時僅靠變異算子產(chǎn)生新的個體,由于較小的變異概率缺乏較強的局部搜索能力,以致步長過大很難找到最優(yōu)解,遺傳迭代難以進行下去.

針對這種情況,采用動態(tài)參數(shù)自適應(yīng)調(diào)整方法,即在算法開始執(zhí)行時采用較大的交換概率pc,小的變異概率pm,算法搜索速度放慢時動態(tài)調(diào)整概率大小,使pc適當(dāng)減小,而pm適當(dāng)增大.

1.2 局部爬山

混合遺傳算法是在傳統(tǒng)遺傳算法中將局部優(yōu)化作為其輔助成分.在混合算法中,每一個新產(chǎn)生的后代在進入種群之前需要進行局部優(yōu)化使其移動到局部最優(yōu)點上,由于遺傳算法和局部搜索方法的互補特性,所以混合方法的效果更好.

其中最典型的是Lamarckian進化[1-2],它的理論依據(jù)是環(huán)境變化引起的生物體生命過程中的結(jié)構(gòu)變化可以傳遞到其后代去,因此算法中個體在整個生命過程(一代)中都進行學(xué)習(xí)(爬山),個體爬山后被重新放回到種群中.在這種混合方法中,人工生物體首先經(jīng)歷Darwin的生物進化,然后經(jīng)歷Lamarckian的智能進化.在Lamarckian進化過程中的評價階段之前,用傳統(tǒng)的爬山程序來將某種“知識”注入到后代生物體中.

通過讓某些個體的經(jīng)驗傳遞到未來的個體中去,將遺傳算法的搜索領(lǐng)域集中到最有希望的區(qū)域,改進算法的性能.采用了Lamarckian方法,傳統(tǒng)的爬山程序可以采用后代作為初始點并對其進行快速的局部優(yōu)化.個體學(xué)會在局部解空間中爬山后,其后代就可以經(jīng)歷評價和選擇階段.利用普通的雜交將其經(jīng)驗傳遞到后代中去.這種方式使優(yōu)良基因結(jié)構(gòu)得到保護,最大程度上避免了各代群體中的劣質(zhì)個體取代優(yōu)良個體.

爬山算法是基于鄰域搜索技術(shù)的、沿著有可能改進解的質(zhì)量的方向進行單方向搜索(爬山)的搜索方法.該方法的局部搜索能力很強,是常用的尋找局部最優(yōu)解的方法.可以針對遺傳算法這種全局搜索能力很強而局部搜索能力不足的算法形成互補.

1.3 改進后的算法流程

通過以上的改進方法,可以得到如圖1所示的算法流程。

圖1 改進后的遺傳算法流程

2 自動組卷試驗

通過以上的改進方法,可以得到如圖一所示的算法流程圖.

利用上述改進后的遺傳算法,采用asp.net技術(shù)開發(fā)了基于web的考試系統(tǒng),并對淄博職業(yè)學(xué)院《大學(xué)英語》題庫進行自動組卷實驗.

將600道試題按要求存入題庫,給出生成試卷的要求.組卷中決定一道試題,就要決定k項指標(biāo),這里我們考慮5維向量(知識單元a1,題型a2,難度,題分,區(qū)分度)相當(dāng)于第i項指標(biāo),決定一份試卷,就決定一個n*k(這里k=5)的矩陣[3].其中n是試卷所含的題目數(shù),k為試題控制指標(biāo)的數(shù)目.其中(i=1…n,j=1…5)表示試題庫中第i道試題的第j項指標(biāo).因此組一份n道試題的試卷就是從題庫中抽取n道試題,每道試題的5個屬性決定一個n*5的組卷參數(shù)矩陣S一行元素的值.

組卷參數(shù)矩陣S的列元素的分布分別滿足用戶指定的試卷的總體要求,即試卷中各種題型的題數(shù)、所有試題的分數(shù)總和、各種難度的試題所占的分數(shù)比例、各篇章所占的分數(shù)、各種區(qū)分度的試題所占的分數(shù)比例,這5個指標(biāo)都應(yīng)等于用戶指定的要求,或者誤差最小.在實際應(yīng)用中,設(shè)定個體的整卷指標(biāo)f來綜合反映這5個指標(biāo)與用戶要求的誤差,由于它們的重要程度不同,所以整卷的指標(biāo)f就是5個指標(biāo)的加權(quán)和,為了不至于各個誤差相互抵消,這5個指標(biāo)與用戶要求的誤差都取絕對值.用下式表示:

2.1 問題解的編碼表示

試題庫中共有600道題X1,X2,…,Xm,組卷就是從這些題中選出n道題,使得整卷指標(biāo)f最小.在此,用一個600位的二進制串來表示問題解.如果F1為1則表示該題被選中,若為0則表示該題未被選中.假設(shè)該套試卷要求有n道試題,則串中有n個1.這樣,一份試卷可表示為形如0101110…10的600位的二進制串.問題解本身并不直接包含試題屬性,第i(i=1…n)道題的試題屬性可以在組卷參數(shù)矩陣S中找到,即Xi=[ai1,ai2,…,ai5] .

2.2 初始化群體

為了使系統(tǒng)在初始搜索時,對于每一個狀態(tài)空間都有平等的機會,通過隨機的方法生成初始化的串群體.對一個有n*5個基因的染色體,初始種群的產(chǎn)生方式為從試題庫里隨機抽題.初始種群的規(guī)模一般由實際問題的具體性質(zhì)決定,按經(jīng)驗或?qū)嶒灲o出.在實際組卷中,將群體規(guī)模設(shè)為n,每個個體都是通過random(m)這個隨機函數(shù)在1至600中隨機選擇n道題,其中600為題庫中試題的題量.

初始化過程如下:

fori=1topop_sizedo

random(600),隨機生成第i個染色體形式的初始試卷

end

2.3 計算當(dāng)前群體中個體適應(yīng)度

首先通過解碼,得到個體的組卷參數(shù)矩陣S.具體過程如下:根據(jù)串F1F2…F600的值,可知試卷中包含的試題的題號,然后把這些試題的屬性寫到組卷參數(shù)矩陣S中,然后調(diào)用適應(yīng)度評估函數(shù)計算個體適應(yīng)度.這里通過計算個體的整卷指標(biāo)f來反映個體的適應(yīng)度.根據(jù)自動組卷的要求,希望組成的試卷各種性能指標(biāo)最接近用戶的要求,即整卷指標(biāo)f越小,個體的適應(yīng)度越高.

2.4 選擇

選用最優(yōu)個體保留選擇策略,即采用最優(yōu)個體保留和輪盤選擇的方式進行.根據(jù)適應(yīng)度對群體中的個體排序,依據(jù)每個個體的適應(yīng)度的高低決定個體進入到下一代的概率.種群中最優(yōu)個體直接復(fù)制到下一代中,其他個體通過輪盤法進行選擇.該方法既可以保證優(yōu)良品種的個體得到更多的繁殖機會,又能在一定程度上防止少數(shù)幾個優(yōu)良品種由于過度繁殖而控制整個種群,使得算法陷入到局部最小.

2.5 交換

采用列優(yōu)先編碼的單點交叉算子,交叉點的位置隨機地在第三列到第五列之間選取,這樣可以保持知識單元和題型屬性不變.先在群體中隨機地選擇兩個串,然后對每對串隨機地在第三列到第五列之間選擇一個交換點.如果交換概率pc滿足random(1)

2.6 變異

變異算子的選用上使用均勻變異.對交叉后種群中個體Xi隨機產(chǎn)生一個0至1之間的隨機數(shù),若大于突變概率p600,則保留原染色體的性狀不變;否則在組卷參數(shù)矩陣S中使用隨機方式在試卷中抽選出一行,得到這道試題的題型屬性.然后在試題庫中隨機選擇一道同題型的題目,替代變異的個體.這里較小可小于0.001.

2.7 非法解

每個問題的解(個體)進行遺傳操作以后,可能變?yōu)榉欠?比如串經(jīng)過交換或變異后,串中1的個數(shù)可能大于或小于n,這時這個串對應(yīng)的解就是非法的,須對解進行處理.這里采用拒絕方法[5-6],直接拋棄進化過程中產(chǎn)生的所有不可行解.

2.8 判斷終止條件是否滿足

g=g+1,g為進化的代數(shù),并按照第3步的方法計算當(dāng)前群體的每個個體的適應(yīng)度,如果g等于指定的進化代數(shù),或者某個個體的適應(yīng)度達到要求就退出,否則轉(zhuǎn)第4步繼續(xù)執(zhí)行.該算法要經(jīng)過至少320次迭代算法才能生成滿意的試卷,有時還會出現(xiàn)震蕩,特別是最后收斂速度緩慢.

2.9 采用基因換位算子實現(xiàn)爬山

操作采用基因換位算子實現(xiàn)爬山操作的方法如下:

①在個體中隨機選擇兩個基因交換它們位置.

②判斷基因換位后其適應(yīng)度是否增加,若適應(yīng)度增加,則以換位后的個體取代原個體.

③重復(fù)步驟①②到達到一定的交換次數(shù)為止.

2.10 近似滿足

由于遺傳算法不是自動終止,因此無法得知該算法是否已經(jīng)收斂到極值點.為此可以修改終止條件為:①出現(xiàn)種群滿足f=0要求的;②當(dāng)?shù)趃代與第g+1代全體中最大適應(yīng)度個體的適應(yīng)度滿足如下條件時說明遺傳算法進化效果已不明顯,停止遺傳操作.

實驗表明一般迭代250代左右就能生成滿足符合要求的試卷.該改進的遺傳算法實現(xiàn)了全局并行搜索,搜索空間較大,并且搜索過程中不斷向可能包含最優(yōu)解的方向調(diào)整搜索空間,從而易于找到最優(yōu)解,能有效的解決試題庫的智能組卷問題,它特別適合分A卷,B卷甚至C卷的情況.

[1] 王小平,曹立明.遺傳算法—理論、應(yīng)用與軟件實現(xiàn)[M] 西安:西安交通大學(xué)出版社,2002:69-87

[2] 楊路明,陳大鑫.改進遺傳算法在試題自動組卷中的應(yīng)用研究[J] .計算機與數(shù)字工程,2004,32(5):76-79

[3] 余勝泉,何克抗.網(wǎng)絡(luò)題庫系統(tǒng)的設(shè)計與實現(xiàn)[J] .中國遠程教育,2000(9):53-57.

[4] Gen M,Cheng R.遺傳算法與工程優(yōu)化[M] .予歆杰,周根貴譯.北京:清華大學(xué)出版社,2004:83-86.

[5] Michalewicz Z.Genetic algorithms,numerical optimization,and constraints[M] .1999:151-158.

[6] 陸億紅,柳紅.基于整數(shù)編碼和自適應(yīng)遺傳算法的自動組卷[J] .計算機工程,2005,31(23):232-233.