摘  要： 針對遺傳算法組卷易陷入早熟、難以收斂的問題進行研究，結合進化環(huán)境對進化過程的影響和引導，對動態(tài)進化環(huán)境進行建模，提出了一種基于動態(tài)變異池的策略。該策略的種群不共享變異池，在每次變異前，根據(jù)每個個體的弱點動態(tài)生成該個體的變異基因庫，以此改善當前變異環(huán)境，實施引導性變異，提高解質量。該策略能加速收斂，并在很大程度上提高收斂精度。實驗數(shù)據(jù)表明，采用了該策略的組卷算法能快速生成各項指標都與約束條件十分貼近的試卷，具有很好的實用價值。

　　關鍵詞： 組卷；進化環(huán)境；遺傳算法；動態(tài)變異池；收斂精度；題庫系統(tǒng)

0 引言

　　隨著信息技術的不斷發(fā)展應用，考試模式將面臨著巨大的變化。在線學習、考試系統(tǒng)層出不窮，如何自動實時地從題庫中隨機抽取合適的試題是這類系統(tǒng)要解決的首要問題，同時這也是一個多約束的NP難題。目前常用的組卷方法主要有隨機抽取法、回溯試探法、最大權法和遺傳算法[1-6]。其中，遺傳算法[7-8]因其內(nèi)在并行性和全局尋優(yōu)能力被廣泛應用于傳統(tǒng)搜索方法難于解決的非線性、多約束等復雜問題。

　　然而，實際應用中發(fā)現(xiàn)，遺傳算法生成試卷經(jīng)常會出現(xiàn)早熟、收斂慢等問題，特別是當試卷約束較復雜時，算法會更加難以收斂，其結果往往是生成試卷的時間長、與客戶要求的偏差大等。為解決這些問題，本文對動態(tài)進化環(huán)境進行設計和建模，提出了一種稱為動態(tài)變異池的策略，該策略一方面監(jiān)測試卷性能指標；另一方面根據(jù)試卷性能指標監(jiān)測結果，結合客戶偏好，為每個個體生成不同的變異池實施引導性變異。實驗表明，動態(tài)變異池策略能加速收斂，提高收斂精度，生成滿意度比較高的試卷。

1 遺傳算法解組卷問題

　　1.1 編碼設計

　　采用分題型段編碼。取題號為染色體基因，一張試卷的題目數(shù)量決定了試卷個體的染色體長度。同時對染色體進行分段，一個題型對應一段，段的長度即根據(jù)題型約束計算而來的每種題型的題目數(shù)量。

　　分題型段編碼有以下兩點好處：

　?。?）編碼長度適中，進化過程快。

　?。?）個體初始即滿足題型題量和卷面分約束，這使得試卷個體具有“合法性”，并且這種“合法性”不會被進化操作所打亂，無論如何交叉和變異，個體均能滿足題型題量的約束。

　　1.2 適應度函數(shù)設計

　　設組卷的題量要求為n，卷面分約束為G。采用分題型段編碼后對應的題號分別為m1、m2、m3、…、mn。根據(jù)組卷的各項約束參數(shù)為每張試卷建立n×6的目標狀態(tài)矩陣A=[A1 A2 A3 A4 A5 A6]，如式（1）所示，該目標狀態(tài)矩陣決定著試卷個體的優(yōu)劣。

　　其中，A1為題目分數(shù)指標，A2為課程指標，A3為難度指標，A4為章節(jié)指標，A5為知識點指標，A6為已抽過的頻度指標。

　　可用式（2）計算第j門課程實際所占比例與理想百分比的誤差：

　　其中，IPcj為第j門課程所占試卷總分的理想百分比，ai1為第i道題的分值。如果ai2為第j門課程，則δij為1，否則為0。式（2）還可以用來計算難度約束誤差和章節(jié)約束誤差?？捎檬剑?）來計算試卷是否命中第j號知識點的誤差：

　　其中，Nk為總共需要命中的知識點個數(shù)；IPkj為j號知識點的理想比例，一般為1/NK。如果ai5為j號知識點，則δij=1，否則δij=0。另外，組卷時，為保障隨機性和多樣化，盡可能每次能夠優(yōu)先抽取被抽中次數(shù)較少的“新鮮”題，可以用式（4）來計算整張試卷的新鮮程度：

　　其中，ai6為mi已被抽中的次數(shù)，min和max為題庫中的題被抽中最少和最多的次數(shù)。設所有誤差之和為E，適應度函數(shù)可表示為1/（E+1）。如有其他的約束，也可計算之后加入總計誤差E中。誤差越小，適應值越大，表明試卷個體與理想試卷偏差越小，競爭能力越強。

　　1.3 遺傳算子設計

　　采用標準遺傳算法的賭輪選擇、兩點交叉、單點變異和精英保留策略[7]。單點變異時選取與變異位置同題型的題目進行變異替換。值得一提的是，交叉和變異操作可能導致個體出現(xiàn)重題。如下所示，父代個體P1、P2在位置3~7處進行交叉，產(chǎn)生子代個體S1、S2。

　　P1=3 5 |1 6 9 10 12| 15 18 19

　　P2=2 4 |3 7 9 11 10| 13 19 20

　　S1=3 5 |3 7 9 11 10| 15 18 19

　　S2=2 4 |1 6 9 10 12| 13 19 20

　　交叉以后，S1個體出現(xiàn)了重題3，若繼續(xù)對S2在位置8進行變異，取與13題同題型的12題進行替換，變異后的S2也將出現(xiàn)重題。

　　對于重題現(xiàn)象，一般有兩種處理方法：進化操作后檢查子代個體是否有重題并進行簡單替換[9]；或者放棄本次進化，重新進化[10]。這兩種處理方式都將耗費大量時間。本文的處理是在整個進化迭代結束后只對最優(yōu)解進行重題優(yōu)化。所謂重題優(yōu)化是指找到與重題同題型并且各項約束指標最接近的題去替換重題，將去重題操作對個體適應度的影響減到最小。重題優(yōu)化策略比前兩種處理方式更節(jié)省進化時間，并且在題庫規(guī)模越大時優(yōu)勢更明顯[11]。

2 動態(tài)進化環(huán)境建模

　　“孟母三遷”的故事告訴人們環(huán)境因素不容忽視，同樣，源于生物進化的遺傳算法也不能忽視進化環(huán)境的影響。組卷問題是一個典型的組合優(yōu)化問題，其約束很多，若忽略進化環(huán)境的引導性作用，進化過程會顯得異常緩慢，其結果是出現(xiàn)早熟現(xiàn)象并且最優(yōu)解的質量無法達標。表現(xiàn)在具體應用上，生成的試卷可能會與用戶要求存在嚴重的偏差，比如某次生成試卷要求某重點章節(jié)占總題量的30%，然而實際抽出的題卻只占5%，這樣一些非重點章節(jié)（如選學章節(jié)）卻抽出了嚴重過剩的題，這樣的偏差是用戶無法接受的，考生也無法適應。當組卷約束比較苛刻時，這種偏差會更明顯。

　　進化環(huán)境對進化過程的影響主要體現(xiàn)在“優(yōu)勝劣汰”和“基因突變”上，可歸結為偏好一詞。歸根結底，這會指引進化個體產(chǎn)生和保留更好的基因。伴隨進化過程的進行，這種偏好也在動態(tài)變化著，該如何對動態(tài)的偏好信息進行建模，引導進化過程更快地找到缺失基因呢？

　　改進變異算子的研究源于變異算子在進化計算中起主導作用的認識[12]。遺傳算法進行組卷具有全局收斂性，但也有一定概率的不穩(wěn)定性，特別是當組卷約束參數(shù)比較復雜和苛刻時，這種不穩(wěn)定的概率就會增加。造成不穩(wěn)定性的主要原因之一是有效基因的缺失，變異可有效解決這一問題。

　　目前應用的遺傳算法的變異池是通用的，一般直接選取可用題庫作為變異池。在組卷約束參數(shù)較為復雜時，這種通用變異池就會放慢有效基因恢復的步伐。為此，對變異算子做出改進，在每次變異前先改善當前的變異環(huán)境，設計了動態(tài)變異池策略，使每次變異都會產(chǎn)生比父輩更優(yōu)秀的個體。

　　動態(tài)變異池的具體建模過程如下：

　?。?）取通用變異池（可用題集）作為舊變異池。

　?。?）根據(jù)組卷約束參數(shù)計算并記錄當前個體嚴重缺失的基因。具體為：依次取約束參數(shù)（如章節(jié)約束），計算當前試卷與該類約束各項指標的實際誤差，即計算該試卷各章節(jié)比例相對于約束參數(shù)要求的各章節(jié)比例的實際誤差，并記錄實際誤差最大的指標項（章節(jié)編號）。

　?。?）重復步驟（2），直至各類約束都計算完畢。

　?。?）生成空的新變異池。

　?。?）根據(jù)步驟（2）、（3）中記錄的指標項集合，對當前變異池進行優(yōu)化。依次從舊變異池中挑出屬于該指標項的題集加入到新的變異池中。每次挑選不改變舊變異池的內(nèi)容。

　?。?）重復步驟（5），直至所有指標項都處理完畢，當前試卷“急缺基因庫”形成，即當前個體此次變異的新變異池生成。

　　這種每個個體每次變異前都根據(jù)個體的缺點重新生成變異池的策略稱為動態(tài)變異池策略。這樣一來，算法的變異池很大程度上引導著變異朝著好的方向進行，從而改進個體質量，加速收斂。

　　需重點說明的是，動態(tài)變異池的生成過程中，對舊變異池的每次篩選都不能改變舊變異池的內(nèi)容，這使得同時具有多個有效基因的題有可能重復進入變異池，增加被選中的概率，即增加了缺失的有效基因進入下一代的概率。實驗表明，這能有效強化缺失基因，加大搜索力度和精度。

3 實驗

　　對采用通用變異池的遺傳算法（算法1）和采用動態(tài)變異池的遺傳算法（算法2）進行實驗對比，兩個算法均采用了重題優(yōu)化策略[11]。數(shù)據(jù)庫總題量為10 977，題型15種，難度級別5個。根據(jù)多次實驗，算法進化代數(shù)設置為2倍題量約束，下限為100，種群規(guī)模設置為2倍題量約束，下限為200。表1~表4為兩種遺傳算法按4組方案運行10次所得的平均性能詳細對比。4組方案涉及3門課程，其中課程1（方案1）的題量為  1 773，課程2（方案2）的題量為1 424，課程3（方案3和方案4）的題量為1 811。

　　表中數(shù)據(jù)表明，算法2對不同的組卷方案都能比算法1更快更好地收斂。特別對較復雜的約束參數(shù)，算法2的優(yōu)勢能得到更好的體現(xiàn)。如方案2中出現(xiàn)的知識點包含要求，算法2能比算法1更多地命中，如表2所示。再如方案4中的章節(jié)分布約束，由于課程3各章節(jié)題目在數(shù)據(jù)庫中存在比例較為均衡，面對組卷過程中常常出現(xiàn)的各章節(jié)要求比例偏頗的情況，一般算法很難得到與要求比例很貼近的解，但如表4所示，算法2找到的最優(yōu)解滿意程度很高，不僅章節(jié)比例，其他各項指標都與試卷約束參數(shù)很貼近，并且效率比算法1好。

　　目前該策略已經(jīng)集成于主要用于期考出卷的教務助手系統(tǒng)，運行穩(wěn)定，經(jīng)統(tǒng)計，50道題最差10 s能完成組卷，100道最差30 s能完成組卷，且抽取試卷質量好，滿意度高。

4 結論

　　試卷自動生成問題是一個多約束優(yōu)化問題，同時也是一個NP難問題，它的約束參數(shù)很難用數(shù)學形式表達，所以傳統(tǒng)算法無法對其求解，遺傳算法因其優(yōu)秀的搜索能力廣泛應用于求解這類問題。為克服遺傳算法易陷入早熟、難以收斂的問題，本文提出了基于動態(tài)變異池的遺傳算法，該算法已經(jīng)集成于教務系統(tǒng)運行，實驗數(shù)據(jù)表明，加入了進化環(huán)境和偏好設計的遺傳算法具有更好的魯棒性和收斂性，能更早更好地找到滿足條件的最優(yōu)解，并在很大程度上提高求解精度，加速算法收斂，具有很好的實用價值。

　　基于動態(tài)變異池的研究只是基于環(huán)境的進化算法的一個小的著眼點，研究更復雜的進化環(huán)境從而避免算法陷入局部最優(yōu)，跳出進化停滯是日后工作一個重要的開展方向。另外，如何一次產(chǎn)生n套高質量的不重復的試卷也是一個重要的后續(xù)實驗課題。

參考文獻

　　[1] 龔完全.基于最小回溯代價的智能組卷算法[D].長沙：湖南大學，2005.

　　[2] 李大輝.基于廣度優(yōu)先回溯算法的試題搜索算法[J].大慶石油學院學報，2006，30（3）：100-102.

　　[3] 金漢均，鄭世玨，吳明武.分段隨機抽選法在智能組卷中的研究與應用[J].計算機應用研究，2003，20（9）：102-126.

　　[4] Yan Song， Yang Guoxing. Item bank system and the test paper generation algorithm[C]. 2012 7th International Conference on Computer Science & Education（ICCSE）， IEEE， 2012：491-495.

　　[5] 尹常治，楊皓，趙立族.最大權法試卷組卷算法[J].工程圖學學報，2004，25（3）：106-110.

　　[6] Huang Wei， Wang Zhaohui. Design of examination paper generating system from item bank by using genetic algorithm[C]. International Conference on Computer Science and Software Engineering（CSSE）， Wuhan， 2008：1323-1325.

　　[7] 陳國良，王煦法，莊鎮(zhèn)泉，等.遺傳算法及其應用[M].北京：人民郵電出版社，1996.

　　[8] 鄭金華.多目標進化算法及其應用[M].北京：科學出版社，2007.

　　[9] 黃寶玲.自適應遺傳算法在智能組卷中的應用[J].計算機工程，2011，14（37）：161-163.

　　[10] 周艷聰，劉艷柳，顧軍華.小生境自適應遺傳模擬退火智能組卷策略研究[J].小型微型計算機系統(tǒng)，2011，32（2）：323-327.

　　[11] 肖桂霞，趙武初，朱偉，等.基于遺傳算法智能組卷的去重題方法[J].計算機工程，2012，11（38）：150-152.

　　[12] 霍紅衛(wèi)，許進，保錚.選擇和變異算子的作用分析[J].電子學報，2000，28（2）：31-34.