1、基于改良遺傳算法的自動組卷研究摘要通過詳細分析試卷的各項約束條件，建立了一個以知識點、難度系數、區分度等為核心屬性的自動組卷數學模型，并利用改良的遺傳算法實現了自動組卷。關鍵詞自動組卷；數學模型；遺傳算法自動組卷就是根據用戶的要求，采用一定的算法自動地從試題庫中抽取一定數量的試題組成試卷。自動組卷算法的好壞直接影響到試卷的質量，如何從試題庫中選出試題組成符合用戶要求的試卷，并使組卷具有較高的效率和成功率是當前研究的熱門課題。現有的自動組卷算法一般有三種：隨機選取法、回溯試探法和遺傳算法。遺傳算法是一種新開展起來的并行優化算法，它很合適解決自動組卷問題。在自動組卷系統中，一些試題庫設置了試題的各

2、類屬性，如章節、層次、要求、題型、難度系數、難度級別、各章節分值等屬性，其實過多的屬性會增加實際組卷的難度，降低效率。以教育學理論為指導，選擇以下屬性作為試題的核心屬性。(1)題號。試題的編號，用來唯一標識試題。(2)題型。試題的類型。(3)知識點。某道題屬于某門課程的哪個知識點，知識點的設置不以章節為根據，從而可以防止教材的不同對組卷造成影響。(4)難度系數。難度系數1是表示某一試題的難易程度，通常用未通過率來表示，即一次考試中未答對某道試題的考生數在其總體中所占的比例。一般來說，難度系數值為0.5時，是中等難度，假如小于0.3試題太簡單，假如大于0.7試題太難，對考生都會做或都不會做難度系

3、數為0或為1的試題，屬于無意義的試題，必須淘汰。(5)區分度。區分度2是指某道題對不同程度考生加以區分的才能。區分度高的試題，對學生程度有較好的鑒別力。區分度的計算公式為：其中，B表示試題的區分度，H表示樣本中高分組在某題上所得的平均分，L表示樣本中低分組在某題上所得的平均分，K表示某題總分值。高分組和低分組一般各占樣本的25%30%，最好取27%。一般來說，試題的區分度在0.4以上就被認為是很好的。在0.30.39之間，認為良好；在0.20.29之間，認為可以；在0.19以下，認為差，必須淘汰或加以修改。對在校學生的達標考試，試卷的區分度不宜太高，因為它不是選拔性質的考試。但也不能過低，否那

4、么對學生的鑒別效果差，不能很好的到達考試的目的。一般區分度控制在0.20.3之間為宜。(6)分值。某小題的分數。(7)答題時間。完成某題估計所需的時間。自動組卷中決定一道試題，其實就是決定一個包含題號、題型、知識點、難度系數、區分度、分值、答題時間的七維向量a1，a2，a3，a4，a5，a6，a7。假設一套試卷中包含n道試題，一套試卷就決定了一個n7的矩陣S：這就是問題求解中的目的矩陣，其中ai1、ai2、ai3、ai4、ai5、ai6、ai7分別表示試卷中第i道題的題號、題型、知識點、難度系數、區分度、分值、答題時間。從矩陣S可以看出組卷問題是一個多重約束目的的問題求解，且目的狀態不是唯一的

5、。在實際組卷時，用戶會對試卷提出多方面的要求，用戶的每一個要求對應試卷的一個約束條件。要組成一份符合要求的、高質量的試卷，目的矩陣的分布要滿足以下試卷約束條件。(1)試卷中包含的題型以及每種題型的題量要與用戶的設置相符。k種題型的題量=(2)試卷中包含知識點即考核知識點以及各考核知識點所占分數的比例要與用戶設置相符。K種考核知識點所占分數=(3)試卷的難度系數要滿足用戶的要求，試卷的難度系數一般用試卷中每道試題的難度系數的加權平均來計算。即：試卷的難度系數=/總分(4)試卷的區分度要滿足用戶的要求，試卷的區分度一般用試卷中每道試題的區分度的加權平均來計算。即：試卷的區分度=/總分(5)試卷的總

6、分要與設置相符。即：試卷的總分=(6)試卷的總答題時間要與用戶設置相符。即：試卷的總答題時間=在實際組卷時，試卷的總分、考核知識點、各題型每題分值、試卷中包含的題型、各題型的題量都應該是準確到達的。試卷中各考核知識點所占的分數、試卷的難度系數、區分度和試卷的總答題時間這四個約束條件可以存在一定的誤差。誤差的大小由用戶的期望值和各約束條件的重要性決定。在實際應用中，各約束條件的重要性是不同的，因此，目的函數就取各項誤差的加權和。目的函數f可以表示為：為了不至于各項誤差互相抵消，實際值與用戶要求值的誤差都取絕對值。其中，試卷中各考核知識點所占的分數和試卷的總答題時間這兩項的誤差為實際值與用戶要求值

7、的誤差絕對值與用戶要求值的比，試卷的難度系數和區分度這兩項的誤差為實際值與用戶要求值的誤差的絕對值。i表示第i個約束條件的權值，i通常由專家經歷或試驗給出，0i1，。由上式可知，目的函數f的值越小，即誤差越小，問題的解越優，即生成的試卷越接近用戶的需求。遺傳算法3，4，5是以適應度函數或目的函數為根據，通過對群體中的個體進展遺傳操作實現群體內個體構造重組的迭代處理過程。在這一過程中，群體中的個體一代一代地得以優化，并逐漸地逼近最優解，最終獲得最優解。傳統遺傳算法的主要步驟包括初始染色體群體生成、適應度評估和檢測、選擇操作、穿插操作和變異操作。傳統遺傳算法流程圖如圖1所示其中t為進化代數，t0為

8、最大進化代數。圖1傳統遺傳算法流程圖傳統的遺傳算法采用二進制編碼，用1表示某題被選中，0表示某題沒有被選中，這種編碼非常簡單，但在進展穿插和變異操作時，各題型的題量很難控制，而且當試題庫題量很大時編碼很長。傳統的遺傳算法以進化代數等于最大進化代數作為終止條件，但是在實際組卷過程中并不知道種群進化到第幾代就能得到試卷的最優組合。因此用遺傳算法實現自動組卷時，要對傳統遺傳算法進展一些改良。4.1改良的遺傳算法4.1.1染色體編碼通過對編碼的大量分析，提出了一種分段實數編碼機制，首先將染色體分成假設干段，每一段對應一種題型，組成試卷的各道試題題號直接映射為基因，編碼時將同一題型的試題放在同一段，同一

9、段內題號各不一樣。以題號編碼的方法所表達的意義清楚、明確、不需解碼，從而可以進步算法性能，進步運算效率。而且穿插和變異操作都在各段內部進展，因此可以保證組卷過程中各題型題量的正確匹配。4.1.2適應度函數設計遺傳算法在進化搜索中僅以適應度函數為根據，利用種群中每個個體的適應度值來進展搜索。因此，適應度函數的選擇至關重要，一般而言，適應度函數是由目的函數變換而成的。上面提出的自動組卷模型是最小化問題，采用如下方法可將目的函數f轉換成適應度函數F。由上式可知，F的取值范圍為01，適應度函數F的值越大，說明個體越好，個體越接近問題的最優解。4.1.3初始化染色體群體隨機生成初始染色體群體，在初始染色

10、體群體中，染色體的長度為n，群體的大小為，太小時，難以求出最優解，太大時那么增長收斂時間。群體的大小一般根據需要，按經歷或試驗給出，一般=30160。4.1.4遺傳算子(1)選擇算子在遺傳操作中，為了保存較優的個體，以概率1完全地復制每一代群體中按適應度值從大到小依次排列的前面2個個體。為了保持群體大小不變，同時刪除適應度排列的后面的2個個體。然后從排列在前面的-2個個體中隨機抽取p(p-2)個個體進展穿插和變異操作。這種選擇策略使得適應度小的個體也有可能被選中，這樣有助于增加下一代群體的多樣性。(2)穿插算子在遺傳操作中，采用了分段的思想，穿插的時候按題型段進展穿插，因此穿插后不存在段內試題

11、重復的問題，也不會改變每種題型的題量。穿插概率p太小時難以向前搜索，太大時那么容易破壞高適應度的構造。一般p=0.40.6。(3)變異算子在遺傳操作中，變異在染色體的題型段內進展。變異概率p太小時難以產生新的基因構造，太大時使遺傳算法成了單純的隨機搜索。一般p=0.010.2。4.1.5終止條件在改良的遺傳算法中，設置了期望適應度值，把每一代計算出來的最高適應度個體的適應度值與期望適應度值相比擬，當適應度最高的個體的適應度值大于或等于期望適應度值時那么停頓進化，否那么繼續進展遺傳操作、計算適應度值、反復迭代直到組卷成功。4.2主要算法描繪基于改良遺傳算法的自動組卷的主要算法描繪如算法1所示。算

12、法1：intGJGA(p，p，f0)t=0；initialize(p(t)；/隨機產生初始染色體群體計算初始染色體群體的適應度值；hile(axff0)/當適應度最高的染色體的適應度值小于期望適應度值時seletin(p(t)；/選擇操作rssver(p(t)；/穿插操作utatin(p(t)；/變異操作得到下一代染色體群體q(t+1)，計算下一代染色體群體的適應度值；t+；輸出當前染色體群體中適應度最高的染色體；4.3遺傳算法復雜度分析在遺傳算法中，絕大局部處理都集中在適應度的計算上，因此可以用計算個體適應度操作的時間復雜度作為算法的時間量度。遺傳算法的時間復雜度為(t*n)。因為試題庫中的

13、題量一般都很大，所以改良后的遺傳算法的時間復雜度一般要比傳統遺傳算法的時間復雜度校遺傳算法的空間復雜度可以用初始染色體群體所占的空間來衡量，遺傳算法的空間復雜度為(*n)。因為改良后的遺傳算法的染色體的長度遠比傳統遺傳算法的染色體的長度小，所以改良后的遺傳算法的空間復雜度遠比傳統遺傳算法空間復雜度校算法的改良往往不能顧及問題每一個方面，假如算法設計的核心是進步解的精度，那么算法可能在搜索范圍和搜索精度上花去更多的時間，假如算法的設計主要在于盡快收斂，得到結果，那么在解的精度上考慮很少，算法往往側重于減少進化代數。改良后的遺傳算法使生成試卷的質量得到了保證，但要使組卷的收斂速度得到進一步改良，還需進一步研究。1文海英.智能型試卷自動生成系統中試卷難度控制技術的研究(J).湖南科技學院學報，2022，26(5)：153-1562常振江.學生成績分布與一種簡便的評估試卷命題質量的方法(J).遼寧師范大學學報：自然科學版，2022，26(1)：109-1123