基于遺傳算法的自動組卷系統的策略優化設計及實現

鄭道博，寧慧，張汝波

1. 哈爾濱工程大學 計算機科學與技術學院，黑龍江 哈爾濱 150001

2. 大連民族大學 機電工程學院，遼寧 大連 116600

在互聯網覆蓋率擴大以及電子設備普及的今天，在線教育己經逐漸被大多數人所接受。特別是在疫情肆虐，無法進行傳統教育的背景下，為了能夠繼續學習，在線教育被廣泛使用。而為了使在線教育達到良好的教學效果，實現高效的在線考試功能就顯得尤為重要。其中，如何能實現既科學又迅速的自動組卷功能一直是研究的重點。本文研究和實現了基于遺傳算法的自動組卷系統。

在傳統教育中，試卷一般是由許多出題教師分工完成，并且需要在考試日期的前一個月開始準備。這對于人力物力有著很大的要求。另外，試卷的試題內容和試題順序不可避免地會受到出題老師的主觀因素的影響。因此需要一種調整過的組卷方式來保證試卷內容的科學性。

本系統中自動組卷問題的實質是求解多約束條件下的多目標優化問題[1]。遺傳算法作為一種高效的全局并行搜索算法，其過程簡單、個體選擇具有隨機性的特點使其非常適于用來解決此類多目標優化問題。

1 相關算法

1.1 遺傳算法

遺傳算法（genetic algorithm，GA）是20 世紀70 年代初由美國Michigan 大學Holland 教授提出的一種借鑒達爾文進化論體系中種群的自然選擇和遺傳機制的隨機搜索算法。該算法計算過程清晰，經過合適的編碼后對搜索空間表現出廣泛的適應性[2]，且求解效率較高，尤其適用于處理傳統搜索方法難以解決的復雜和非線性問題和一些原本只能由啟發式算法解釋的問題。

由于依照生物進化論和遺傳學設計數學計算模型，遺傳算法能夠通過數學的方式來模擬生物自然進化的過程。遺傳算法將問題求解的過程與生物進化過程中染色體基因的選擇、交叉、變異等一一對應，從而用來尋求多組合優化的最優解。遺傳算法的流程一般包括初始化、計算適應度、選擇、交叉、變異和每次迭代后的判斷。其表現為每代生成隨機的種群，然后淘汰不符合適應度的種群，接著在已生存下來的種群基礎上再次繁殖、淘汰，多次迭代直到出現符合要求的種群。由于是模擬種群的進化過程，加上計算機的性能限制，遺傳算法的判斷退出條件一般為適應度是否達到期望值以上或者迭代次數是否達到最大值，從而避免無限迭代。遺傳算法執行過程如圖1 所示。遺傳算法中每次判斷時要使用每代種群的適應度值，而適應度值的計算需要使用每代種群的具體約束條件值。所以約束條件設計的優劣直接影響著迭代效率和結果的準確度。冗余又量化不合理的約束條件會使最終迭代結果與組卷要求大相徑庭。因而在設計約束條件時應當盡量減少實際參與計算的約束條件個數和使用能讓適應度快速收斂于目標適應度的約束條件。

圖1 遺傳算法流程

1.2 改進的遺傳算法

考慮到存在學生記憶歷年試題以降低考試難度的情況，并為了提高種群迭代效率，本文通過修改約束條件來改進自動組卷策略，從而實現了對基于遺傳算法的自動組卷算法的改進[3]。

為了加快迭代速度[4]，本算法在生成初始種群時不采用隨機組合的方式，而是直接采用已設定的具體約束條件，這樣可以使初始種群的適應度值更接近期望適應度值，進而提高迭代效率。在自動組卷的場景中，這種方式會加快迭代速度。例如在自動組卷前設定好要生成的試卷的題目數量和總分數，算法就會在此基礎上生成符合要求的隨機初始試卷(即初始種群)，之后的試卷都是和最終期望試卷題目數量相同且總分相同。接下來的迭代便主要依據試題內容和難度等約束條件。若初始題目數量各不相同，隨后的迭代需要向期望試題數量靠近。所以這種方式比起完全隨機生成題目數量不一的初始試卷策略會更加節約算法運行時間。

除此之外，在種群迭代過程中[5]，會出現適應度值緩慢趨近期望適應度值的情況。這表現為算法的后半段雖然使用了整體迭代時間的一半，但適應度值的增長十分微小且十分接近期望適應度值。為此需要使用能讓適應度快速收斂于目標適應度的約束條件。結合算法性能要求又考慮到要保證試卷的科學性，本算法增加了試題曝光度這個約束條件。試題曝光度是指試題相對于當前試卷的新舊程度。本策略旨在使用最近未出現過的試題。每次抽取試題組成種群時，算法會剔除存在于當前試卷的前3 套之內的試題，并重新選擇其他試題。而每成功生成一次試卷，算法就會為每道試題在數據庫中的試題記錄里寫入當前試卷序號，以供后續組卷時進行計算和比較。這種策略有利于增大組成當前試卷的試題之間的差別，從而盡量減少出現迭代一次后前代試卷和后代試卷的適應度值差別很小的情況，進而使適應度值快速收斂。同時也能在某種程度上避免學生記憶歷年試題以降低考試難度的情況。

2 系統設計與實現

本系統中，自動組卷是依據教師在網頁中設定的規則信息和試卷信息去抽取題庫表中與預期試卷特征參數相匹配的試題，從而得到符合條件的試題組成的試卷。

由于傳統的遺傳算法存在進化后期效率變低、進化方向可能出現逆向、容易陷入局部最優解等問題。為了避免這些問題，查閱資料后，本系統應用了對傳統的遺傳算法做出的一些調整策略，具體為：使用精英主義模式、采用實數編碼方式和優化選擇算子。

本系統使用的題庫中的試題全部為分值為2 分、一共有5 個章節且難度不等的單選題。其中每個章節代表一個知識點。所組成的試卷特征由參數決定，允許試題總數不等和總分不足100分。之后拓展題庫中題目數量，本系統仍可繼續正常使用。在通過實驗驗證后，本系統所組試卷達到了要求，能很好地滿足課程考核的需求。

2.1 染色體編碼的設計

使用遺傳算法生成試卷，首先要將試卷包含的題目id 序列映射成一組字符串，即染色體的編碼問題。在傳統的遺傳算法樣例中，一般使用二進制編碼。就本系統而言，如果采用二進制編碼，對應的染色體會代表整個題庫中的所有試題。具體而言，二進制編碼按照題庫中試題的順序將題庫編碼成一個由01 字符組成的字符串，1 代表試題出現，0 代表沒有。顯然，對于一個大型的題庫而言，這樣的編碼規模太冗長。

經過查閱相關資料，本系統決定采用實數編碼方式，將試題庫中的試題id 作為基因，試卷中的每道試題由試題id 代表，它和染色體的某個基因一一對應，然后將每張試卷映射為一個染色體。每個章節的題號組合成一段，在進化過程中對遺傳算子的操作也按段進行，這樣保證了每個章節的題目總數不變。比如，要組一套題目數為10 的試卷，每個章節有2 道題，其基因序列分布表示為

(16、66 | 18、25 | 52、67 | 31、32 | 99、45)

章節1 章節2 章節3 章節4 章節5

2.2 初始化種群設計

初始化種群時采取不完全隨機的方式。通過需求分析，本系統生成新試卷有試題總數量、總分數、章節知識點分布、難度系數和試題曝光度這5 個約束條件。在算法第1 步初始化試卷種群時，根據教師給定的參數形成的規則隨機從試題表抽取固定數量的試題，由于每道題目都是2 分，這樣算法生成的初始種群中的個體數量就滿足了題目數量和總分的約束條件。

試題曝光度的約束是指本次考試不會出現近3 年內考試中出現過的題目，由于其完全由底層數據庫查詢和后臺判斷實現，所以不參與適應度函數的計算。這樣，參與適應度函數計算的約束條件減少為2 個：知識點分布和難度系數。這樣算法的迭代次數被減少，收斂也將加快。

2.3 適應度函數設計

適應度值由多個約束條件作為自變量進行運算后獲得。它的大小代表著種群中個體的優劣程度。由于在算法開始時，已經滿足了試卷種群中題目數量和總分這2 個條件，而曝光度在適應度函數中不能用來計算，所以試卷個體的適應度大小只與章節知識點的分布和難度系數直接相關。在生成試卷的過程中，試卷的難度系數計算公式為

式中：i=1,2,···,N，N為生成試卷參數中設定的題目為總數；Ci、Si分別為某張試卷中第i題的難度系數和分數。本題庫中都是分值為2 分的選擇題，故Si恒為2 分。

章節知識點分布使用某張試卷中現在包含的章節知識點的比重來衡量，例如期望某張試卷包含x個章節知識點，而某張試卷中包含的章節知識點的并集中包含y個（y≤x），則章節知識點的分布為y/x。對于一張符合生成新試卷參數的試卷，教師的期望難度系數ED應與試卷當前難度系數D之差很小，章節知識點比重應很大，因此適應度函數f設計為[6]

式中：k1為章節知識點分布的權重，k2為難度系數所占權重。用戶可根據自己的需求設置這2 個參數，但要保證這2 個參數的和是1[7]。

2.4 選擇算子設計

選擇的目的是為了增加種群中優秀個體的數量，使后代染色體具有較高的適應度值。在進化過程中，選擇操作會很大程度地影響種群的進化方向。本系統的選擇策略是設定一個淘汰種群，記該淘汰種群大小為A。從原試卷種群中隨機挑選A個試卷組成一個淘汰種群，通過適應度的計算和排序后將該淘汰種群中的最優試卷個體作為選擇算子的結果。

2.5 交叉算子設計

交叉操作是種群產生新個體的主要方法，交叉的實質是染色體上基因的重組，其直接決定了算法的全局搜索能力。交叉算子可以在每代進化中產生隨機的表現型，即生成隨機的試題組合。在每代的進化過程中，每次執行交叉算子會由2 個染色體生成2 個不同的染色體。重復執行交叉算子若干次，使得到的新的個體數等于上一代種群的個體數[8]，實現該次進化的主要工作。

在交叉過程中，要保證交叉點位的選擇滿足隨機性。本交叉策略采用2 點交叉和隨機點位策略，在試卷染色體的基因序列(0,N) 之間調用python 的隨機數函數產生2 個整數n1、n2，母親基因序列上n1~n2的基因全部遺傳給子代，父親基因序列上的n1~n2之外的基因遺傳給子代。為了保證試卷個體中不出現重復試題，每次交叉后都會進行判斷。如果出現重復試題，交叉函數會從試題庫中隨機選擇一道與重復試題的章節知識點相同且分值相同的試題替換第1 次出現的相同試題。

2.6 變異算子設計

在進化過程中，基因的變異產生了新的基因，有利于避免出現局部解。本變異策略中，每個試卷個體的每個試題基因都有可能變異。當某一代隨機生成的隨機概率小于設定的變異概率，那么試題基因就可以突變。變異的基因所代表的試題以與原試題同分數且同章節知識點為原則。查閱資料[9]知，確定變異概率時，在0.1~0.001[10]效果最好，本算法選取0.085 作為變異概率。

2.7 試題曝光度約束的設計

由于學生中會出現記憶歷年題以降低考試中出現重復試題的作答難度的情況。為了保證考試的科學性，本系統在與數據庫交互的底層中設置了組卷選擇試題時不接受近3 次試卷中出現過的重復試題的限制。在本系統中，當前試卷表中已有的試卷總數記為當前次數。在數據庫的設計中，在試題表加入使用記錄字段，它記錄該試題最新在第幾次組卷時被使用。每次在組成新試卷時，對新試卷的試題進行查找和比較，在抽取到的試題的使用記錄字段值與當前次數的差的絕對值大于3 時才會被使用。在組卷成功后，后臺會把當前次數更新到所選用的試題的使用記錄字段中，供下次組卷作為參考。同理，在變異算子中選擇新題目也要保證不出現近3 次重復試題的限制。

組卷時實現試題曝光度約束的代碼如下：

2.8 系統實現

本系統基于Django 框架[11-12]，采用服務器-客戶機(server/client, C/S)架構，使用Python 語言進行程序編寫，使用MTV(model, template, view)設計模式[13]來實現功能。另外，本系統使用Bootstrap框架[14]編寫前端頁面，通過MySQL 來實現數據庫存取功能。

本系統分為教師端和學生端，教師端負責管理功能，學生端負責在線考試功能。學生在登錄系統后，可以點擊考試進行考試。系統自動判分后[15]，學生可以查看個人成績。教師在登錄系統后，可以在系統上管理試題、自動組卷[16]、管理試卷。教師管理試題庫在試題管理頁面中實現，不必在數據庫軟件中進行，試題管理頁面如圖2 所示。自動組卷時教師需要提供試卷相關的信息和試卷參數，如考試名、難度系數、每個章節的題目數量、總分、考試時間等，輸入完成后點擊生成按鈕，后臺就會自動生成試卷并將其存入數據庫的試卷表中。本次實驗中，教師將期望試卷難度設置為0.7，題目總數為30。自動組卷界面如圖3 所示。

圖2 試題管理頁面

圖3 自動組卷頁面

教師生成新試卷之后，返回到試卷管理頁，教師在此頁面可以查看生成的最新試卷及其相關信息，試卷管理界面如圖4 所示。學生登錄學生端進行考試時的考試界面如圖5 所示。

圖4 試卷管理頁面

圖5 學生考試頁面

根據圖4 的試卷管理頁面，第6 次考試的試卷的試題數量和總分與設定的數值一致。根據圖5 的學生考試頁面，經檢測在該次考試的30 道題中未出現前5 次考試中出現過的試題。因此，可以認為該組卷算法生成的試卷能夠滿足用戶的要求，試卷的質量能夠得到保證。

在另外的算法效率實驗中，本系統使用包含600 道試題的MySQL 數據庫為實驗材料，進行關于最簡遺傳算法(simple genetic algorithm, SGA)和本文優化后的遺傳算法收斂速度的比較，分別記錄兩者在遺傳進化到100 代的過程中不同階段的最優個體的適應度值。經過仿真實驗，可以看出本文算法較最簡遺傳算法SGA 略有優勢，實驗結果如圖6 所示。

圖6 算法收斂速度比較

3 結論

本文研究和實現了基于遺傳算法的自動組卷系統，克服了傳統制作試卷方式的工作量大、試卷缺乏科學性的問題。本文根據現有試卷還存在試題不唯一的問題，除了給出通過遺傳算法實現自動組卷系統的詳細設計過程，還對算法做出了相應改進以限制出現近3 次考試中的試題。經實驗驗證，該算法自動生成的試卷滿足設定的組卷規則，保證了試卷在連續3 次組卷時的唯一性，試卷的質量能夠很好地滿足課程的考核的要求。