基于遺傳算法的組卷研究

劉長騫

(淄博職業學院現代教育技術中心,山東淄博255314)

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

1 改進遺傳算法

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

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

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

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

各代群體中的最優個體未得到保護,劣質個體有可能會取代優良個體.

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

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

1.1 動態調整交換算子和變異算子

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

針對這種情況,采用動態參數自適應調整方法,即在算法開始執行時采用較大的交換概率pc,小的變異概率pm,算法搜索速度放慢時動態調整概率大小,使pc適當減小,而pm適當增大.

1.2 局部爬山

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

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

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

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

1.3 改進后的算法流程

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

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

2 自動組卷試驗

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

利用上述改進后的遺傳算法,采用asp.net技術開發了基于web的考試系統,并對淄博職業學院《大學英語》題庫進行自動組卷實驗.

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

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

2.1 問題解的編碼表示

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

2.2 初始化群體

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

初始化過程如下:

fori=1topop_sizedo

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

end

2.3 計算當前群體中個體適應度

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

2.4 選擇

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

2.5 交換

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

2.6 變異

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

2.7 非法解

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

2.8 判斷終止條件是否滿足

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

2.9 采用基因換位算子實現爬山

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

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

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

③重復步驟①②到達到一定的交換次數為止.

2.10 近似滿足

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

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

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

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

[3] 余勝泉,何克抗.網絡題庫系統的設計與實現[J] .中國遠程教育,2000(9):53-57.

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

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

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