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

　　關鍵詞： 組卷；進化環境；遺傳算法；動態變異池；收斂精度；題庫系統

0 引言

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

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

1 遺傳算法解組卷問題

　　1.1 編碼設計

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

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

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

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

　　1.2 適應度函數設計

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

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

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

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

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

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

　　1.3 遺傳算子設計

　　采用標準遺傳算法的賭輪選擇、兩點交叉、單點變異和精英保留策略[7]。單點變異時選取與變異位置同題型的題目進行變異替換。值得一提的是，交叉和變異操作可能導致個體出現重題。如下所示，父代個體P1、P2在位置3~7處進行交叉，產生子代個體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個體出現了重題3，若繼續對S2在位置8進行變異，取與13題同題型的12題進行替換，變異后的S2也將出現重題。

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

2 動態進化環境建模

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

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

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

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

　　動態變異池的具體建模過程如下：

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

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

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

　　（4）生成空的新變異池。

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

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

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

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

3 實驗

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

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

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

4 結論

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

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

參考文獻

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

　　[2] 李大輝.基于廣度優先回溯算法的試題搜索算法[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] 陳國良，王煦法，莊鎮泉，等.遺傳算法及其應用[M].北京：人民郵電出版社，1996.

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

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

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

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

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