鄭道博，寧慧，張汝波

1. 哈爾濱工程大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150001

2. 大連民族大學(xué) 機(jī)電工程學(xué)院，遼寧 大連 116600

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

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

本系統(tǒng)中自動組卷問題的實(shí)質(zhì)是求解多約束條件下的多目標(biāo)優(yōu)化問題[1]。遺傳算法作為一種高效的全局并行搜索算法，其過程簡單、個(gè)體選擇具有隨機(jī)性的特點(diǎn)使其非常適于用來解決此類多目標(biāo)優(yōu)化問題。

1 相關(guān)算法

1.1 遺傳算法

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

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

圖1 遺傳算法流程

1.2 改進(jìn)的遺傳算法

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

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

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

2 系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)

本系統(tǒng)中，自動組卷是依據(jù)教師在網(wǎng)頁中設(shè)定的規(guī)則信息和試卷信息去抽取題庫表中與預(yù)期試卷特征參數(shù)相匹配的試題，從而得到符合條件的試題組成的試卷。

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

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

2.1 染色體編碼的設(shè)計(jì)

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

經(jīng)過查閱相關(guān)資料，本系統(tǒng)決定采用實(shí)數(shù)編碼方式，將試題庫中的試題id 作為基因，試卷中的每道試題由試題id 代表，它和染色體的某個(gè)基因一一對應(yīng)，然后將每張?jiān)嚲碛成錇橐粋€(gè)染色體。每個(gè)章節(jié)的題號組合成一段，在進(jìn)化過程中對遺傳算子的操作也按段進(jìn)行，這樣保證了每個(gè)章節(jié)的題目總數(shù)不變。比如，要組一套題目數(shù)為10 的試卷，每個(gè)章節(jié)有2 道題，其基因序列分布表示為

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

章節(jié)1 章節(jié)2 章節(jié)3 章節(jié)4 章節(jié)5

2.2 初始化種群設(shè)計(jì)

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

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

2.3 適應(yīng)度函數(shù)設(shè)計(jì)

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

式中：i=1,2,···,N，N為生成試卷參數(shù)中設(shè)定的題目為總數(shù)；Ci、Si分別為某張?jiān)嚲碇械趇題的難度系數(shù)和分?jǐn)?shù)。本題庫中都是分值為2 分的選擇題，故Si恒為2 分。

章節(jié)知識點(diǎn)分布使用某張?jiān)嚲碇鞋F(xiàn)在包含的章節(jié)知識點(diǎn)的比重來衡量，例如期望某張?jiān)嚲戆瑇個(gè)章節(jié)知識點(diǎn)，而某張?jiān)嚲碇邪恼鹿?jié)知識點(diǎn)的并集中包含y個(gè)（y≤x），則章節(jié)知識點(diǎn)的分布為y/x。對于一張符合生成新試卷參數(shù)的試卷，教師的期望難度系數(shù)ED應(yīng)與試卷當(dāng)前難度系數(shù)D之差很小，章節(jié)知識點(diǎn)比重應(yīng)很大，因此適應(yīng)度函數(shù)f設(shè)計(jì)為[6]

式中：k1為章節(jié)知識點(diǎn)分布的權(quán)重，k2為難度系數(shù)所占權(quán)重。用戶可根據(jù)自己的需求設(shè)置這2 個(gè)參數(shù)，但要保證這2 個(gè)參數(shù)的和是1[7]。

2.4 選擇算子設(shè)計(jì)

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

2.5 交叉算子設(shè)計(jì)

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

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

2.6 變異算子設(shè)計(jì)

在進(jìn)化過程中，基因的變異產(chǎn)生了新的基因，有利于避免出現(xiàn)局部解。本變異策略中，每個(gè)試卷個(gè)體的每個(gè)試題基因都有可能變異。當(dāng)某一代隨機(jī)生成的隨機(jī)概率小于設(shè)定的變異概率，那么試題基因就可以突變。變異的基因所代表的試題以與原試題同分?jǐn)?shù)且同章節(jié)知識點(diǎn)為原則。查閱資料[9]知，確定變異概率時(shí)，在0.1~0.001[10]效果最好，本算法選取0.085 作為變異概率。

2.7 試題曝光度約束的設(shè)計(jì)

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

組卷時(shí)實(shí)現(xiàn)試題曝光度約束的代碼如下：

2.8 系統(tǒng)實(shí)現(xiàn)

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

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

圖2 試題管理頁面

圖3 自動組卷頁面

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

圖4 試卷管理頁面

圖5 學(xué)生考試頁面

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

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

圖6 算法收斂速度比較

3 結(jié)論

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