一種改進遺傳算子的遺傳算法組卷策略

張凈宇，王 靖，吳志雄，王 旭，丁 宇

（長江大學 計算機科學學院，湖北 荊州 434020）

0 引言

近年來，計算機、人工智能技術在不同領域得到了廣泛的應用，與現代教學方式的結合，彌補了傳統教學方式的缺陷與不足。在線教學與考核在現代教學方式中的占比不斷提升，利用計算機輔助教師出題組卷進行在線考核成為當下研究的熱點［1］。與傳統試卷命題相比，計算機智能組卷具有以下優點：

（1）智能組卷系統可減輕任課教師在試卷命題的工作量；

（2）有效避免教師在試卷命題上的主觀性因素，試卷依據設定的參數自動生成，難度系數和考點范圍相對均衡，試卷的實際效用得到提升。

目前，考試組卷大多是從試題庫中抽取相應題型的試題進行組卷，通常有以下3 種形式：

（1）人工手動抽取試題；

（2）系統隨機完成試題組合；

（3）采用智能組卷策略［2］。

人工選取試題組卷允許任課教師根據教學實際情況進行針對性的訓練測試。但這種方式一般需要教師耗時數天來完成試卷命題，且難以滿足不同教學大綱要求。

系統隨機組合試題常用的方法有隨機抽取法和回溯試探法。隨機抽取法是從題庫中選取出符合條件的試題進行組合，簡單、易于實現且抽取速度快，多用于小型的在線考試系統，但組卷過程隨機性較大，成功率較低，試卷質量非可控因素較多；回溯試探法則是基于隨機抽取法的一種改進方式，該算法記錄每次隨機抽取的結果，若組卷不成功則返回上一步另行試探，直至組卷成功［3］。回溯試探法的成功率高于隨機抽取方式，但時間和空間復雜度較高且生成的試卷質量難以有效保證。

使用智能組卷策略的命題系統普遍采用的是遺傳算法。遺傳算法的性能主要與算法中設定的選擇算子、交叉算子和變異算子有關。選擇算子決定了種群進化的方向；交叉算子與變異算子則影響著種群進化的速度。利用傳統遺傳算法組卷，若選擇算子設置不當可能會致使種群收斂到局部最優處或算法難以收斂到最優點，形成“早熟”問題，在組卷實際應用中表現為生成的試卷不能滿足用戶要求。

為解決傳統遺傳算法早熟的問題，提高遺傳算法在組卷應用中的性能，本文以《C 語言程序設計》組卷為例，提出了一種改進遺傳算子的遺傳算法組卷策略：種群初始化階段摒棄了傳統遺傳算法的二進制編碼方式，改用十進制實數對試題編碼以降低交叉變異的計算難度；改進的選擇算子摒棄輪盤賭算法，采用了輪盤賭與最優個體保存策略結合的綜合選擇方法以保留優良基因型；改進的交叉、變異算子摒棄傳統遺傳算法初始設定的固定概率，根據種群進化過程中的適應度值自適應動態調整交叉與變異概率，以控制種群進化的速度。將改進遺傳算子的遺傳算法與標準遺傳算法進行實驗比較，結果表明改進遺傳算子后的遺傳算法不僅組卷速度更快，在最優解和算法的穩定性方面，也呈現出顯著優勢。

1 組卷問題的數學建模

組卷問題實質上是在多重約束條件下的函數尋優問題，屬于典型的CSP（Constraint Satisfaction Problem）問題，同時也屬于NP-Hard 問題，要求滿足一定前提條件下，在試題庫中抽選出合理的試題組合，快速高效地生成一套標準試卷。在解決此類問題過程中，需要設定多個評價指標和一個反映試卷質量的目標函數。設某套試卷題量為m，每道題有n個指標，則此套試卷可視為一個m × n的矩陣。

其中，tij代表本套試卷第i道題的第j個屬性。

本文取n為4，分別對應本文建立的組卷數學模型的難度系數、答題時間、區分度和知識點覆蓋率的評價指標，試卷評價指標條件定義見表1。

表1 試卷評價指標條件定義Tab.1 Definition of test paper evaluation indicators

在試卷生成中，重點考慮其難度系數、答題時間和區分度與用戶設定的期望相近，以滿足實際需要，希望生成的試卷知識點覆蓋率盡可能的大，以便試卷能綜合考察學生對知識點掌握情況。為滿足用戶需要，根據試卷的4 個評價指標定義給出以下4 項指標的量化評價函數，公式（2）～公式（5）：

其中，D?、H?、Q?分別為用戶設定的難度系數、答題用時和區分度，D、H、Q為算法組卷達到的難度系數、答題用時和區分度。

4 個評價函數均經過正向化處理，函數值越大越接近用戶期望，反映出該套試卷的試題組合在該指標下表現越好。層次分析法（AHP）是一種定性分析和定量分析相結合的多屬性決策方法，廣泛應用于評價模型中確定指標權重。由于AHP 法用9個標度表示不同的重要程度，在構建判斷矩陣時重要程度劃分存在主觀因素的影響，判斷矩陣的一致性檢驗問題存在缺陷。而3 標度AHP 法較傳統AHP 法引入了判斷矩陣的最優傳遞矩陣，降低了主觀性對指標權重的影響。為對比各個指標的相對重要性，確定指標的權重，本文采取了3 標度的AHP對指標賦權，將多目標優化問題轉化為單目標的組合優化問題。確定目標函數如式（6）所示：

其中，w為通過改進的AHP 法得到的指標的客觀權重。

2 改進遺傳算子的遺傳算法組卷策略

用戶首先設定條件進行約束，在初始隨機生成的種群中，若有個體已滿足用戶設定的條件，則將種群中的最優個體輸出，算法結束；否則對其進行選擇操作：保存最優的30%個體后整個種群進行輪盤賭選擇；被選中的個體依據當前的交叉、選擇概率判定是否進行交叉操作和變異操作；將之前保留的30%最優個體替換掉，進行交叉變異后的種群中低于30%最優個體的部分個體，形成新一代種群，即為迭代一次；再檢查新種群中的最優個體是否滿足用戶條件或迭代次數是否達到最大次數。如此重復，直至種群進化完成。

改進遺傳算子的遺傳算法的流程圖如圖1所示。

圖1 改進遺傳算子的遺傳算法流程Fig.1 Process of genetic algorithms with improved genetic operators

2.1 初始化種群

首先，對試題（基因）進行編碼，通常采用二進制編碼方式。但在組卷實踐中，發現二進制編碼長度隨試題量的增加而增加，從而增加了計算難度，一定程度上降低了算法的性能，因此本文采用分段十進制實數編碼替代傳統二進制編碼，生成若干個不重復隨機數列，每個實數代表一道試題的題號。為了簡化后續交叉與變異的處理，每個數列分為4 小段，分別代表一套標準試卷中的4 種題型：選擇題、填空題、運行結果題與程序設計題，將這些數列作為初始種群以供進化。

其次，確定種群的規模，種群規模過小，算法的采樣點缺乏會限制算法的表現；種群規模較大，種群基因型豐富，可有效避免算法陷入局部最優，但不可避免地會增加計算量，致使算法收斂速度變慢［4］。一般種群規模設定范圍為20～100，本文取值為50。

2.2 選擇算子

選擇操作用于模擬自然選擇的“優勝劣汰”，適應度值高的個體更有機會存活下去，適應度值低的個體則難以遺傳至下一代，種群從而逐代進化。常見的選擇方法有輪盤賭法與最優個體保存策略，輪盤賭法根據個體適應度值在種群適應度值的比例確定，適應度越高的個體越容易被選中，適應度低的個體也有一定的機率得到遺傳，能較好地保持種群基因的多樣性，但隨機性較大，甚至可能丟棄掉最優個體，造成種群退化。

輪盤賭法中第i個個體被選中存活的概率，公式（7）：

顯然，適應度越高越容易被選中。同時，適應度低的個體也有一定的機率得到遺傳。

最優個體保存策略是將種群中最優個體直接保存下來，避免經交叉和變異后優良個體的良好基因型被破壞，并用其替換下一代中經交叉變異后適應度值最低的個體，能夠保證算法在一定程度上的收斂，但最優個體保存策略也難以排除局部最優解。

為保障遺傳算法能夠收斂，又能避免過快收斂陷入局部最優。本文改進的選擇算子將輪盤賭法與最優個體保存策略結合使用，保存30%適應度最高的最優個體，不參與交叉變異，解集中其余的解則由輪盤賭法選擇出來，最后用保存的30%的最優個體替換輪盤賭法選擇出來的低于30%的最優個體的部分。

2.3 交叉算子與變異算子

在生物進化的過程中，兩個個體間進行交配產生下一代，其實質就是染色體上部分基因進行交換重組，稱為交叉運算；產生新一代個體時，個體染色體上可能會發生等位基因的替換，即發生了基因突變。傳統的遺傳算法采用固定的參數作為交叉概率和變異概率，這種固定的取值方式沒有考慮到種群在迭代中的逐步優化，不能動態地適應種群在進化的不同時期的需要。種群迭代早期，個體間相似度較小，為充分進行基因交流，應當提高交叉概率而減小變異概率；隨著迭代的進行，種群趨向最優基因型，個體間相似度較高，為避免陷入局部最優，此時應當降低交叉概率而提高變異概率。交叉概率PC影響種群的豐富度，變異概率Pm影響算法解的優劣。Pc越大則種群越豐富，但也越容易破壞優良個體的基因型；Pm越大越容易找到全局最優解，跳出局部最優的陷阱，但Pm過大，算法將退化為隨機抽取法。同時，PC與Pm過小時，種群難以產生新個體，進化停滯不前［5］。

鑒于此類問題，有學者提出了一種動態調整交叉與變異概率的自適應遺傳算法（Adaptive Genetic Algorithm），其基本思想：對于低于種群平均適應度的劣勢個體，為改善該個體適應度，采用較高的交叉概率與變異概率；對于高于種群平均適應度的個體，為保持其優良基因型，應采用較小的交叉概率和變異概率［6］。

公式表達如公式（8）和公式（9）：

其中，k1～k4為控制參數，取值范圍（0，1］；fmax是當前種群的最大適應度；favg是當前種群的平均適應度；f為交叉的一組個體中較優個體的適應度或發生變異的個體的適應度。

但這種自適應遺傳算法也存在著較明顯的缺點：首先，PC與Pm受控制參數k的影響較大，而k的值隨機性較強，影響了種群的個體質量；其次，當f ＝fmax時，PC與Pm均為0，即最優個體不再發生交叉和變異，這會導致種群進化停滯不前［7］。

有學者發現logistic 函數在區間兩端平滑收斂，趨于固定值，能夠較好地描述有界增長的現象，能平衡線性與非線性變化之間的平衡，且logistic 函數的函數值范圍從0 到1［8］。

一種簡化的logistic 函數如公式（10）：

本文利用logistic 函數的這種良好特性，針對交叉和變異算子進行改進，通過調整系數將其嵌入交叉與變異概率的調節公式中，改進后的自適應交叉與變異概率如公式（11）和公式（12）所示：

其中，α表示種群當前的顯示系數，定義為式（13）：

其中，期望EX反映出當前種群的平均適應度，公式（14）；方差DX反應出當前種群適應度的離散程度，公式（15）：

顯然，隨著迭代次數的增加，種群逐步進化，種群的平均適應度不斷提高，趨向于優良基因型，個體間的相似性越來越大，最優解趨于收斂，即離散程度一再降低，相似系數α隨之增加［9］。本文確定交叉概率的區間為［0.4，0.9］，變異概率的區間為［0.01，0.1］，因此各控制參數賦值為：k1＝1，k2＝1，k3＝0.4，k4＝0.9，k5＝0.198，k6＝1，k7＝0.001，k8＝0.1。采用自適應調整的交叉與變異概率進行交叉與變異操作，其過程如圖2、圖3 所示。

圖2 交叉操作Fig.2 Crossover operation

圖3 變異操作Fig.3 Mutation operation

3 仿真實驗與分析

為驗證本文策略在組卷實踐中性能上的提升，以《C 語言程序設計》試卷為例，設定用戶期望、標準遺傳算法參數與系統開發環境，見表2～表4。

表2 設定用戶期望Tab.2 Set user expectations

表3 設定標準遺傳算法參數Tab.3 Set standard genetic algorithm parameters

表4 系統開發環境Tab.4 System development environment

采用本文改進遺傳算子的遺傳算法在上述條件下組卷，種群進化過程中適應度的變化如圖4 所示。

圖4 改進算法適應度變化Fig.4 Improved algorithm adaptability variations

由圖4 可知，區別于標準遺傳算法采用的輪盤賭選擇方式導致進化曲線波折震蕩，本文的選擇算子采用最優個體保存策略與輪盤賭結合的方式，在種群不斷進化的過程中仍能保存優良個體的基因型，使得種群穩健的逐步提升，不會出現震蕩“退化”的現象。在迭代至第五代附近，即使沒有進化出更優的個體，仍能保持著最優基因型不退化。

按此要求生成的試卷樣例展示如圖5 所示。

圖5 生成試卷展示Fig.5 Generate test paper presentations

將其與同等條件下標準遺傳算法生成的試卷進行對比實驗，并就實驗結果進行分析：

（1）通過30 次的試驗，改進遺傳算子的遺傳算法達到收斂平均需要48 代，而標準遺傳算法收斂所需迭代次數約為本文算法的2～3 倍，顯然本文算法在計算速度方面優于標準遺傳算法，更適宜應用于組卷等實時請求場景；

（2）隨著進化次數的增加，本文算法最優個體的適應度值不斷提高，逐漸高于標準的遺傳算法最優個體適應度值，兩種算法對用戶不同期望的滿足程度如圖6 所示，本文算法生成的試卷在總體上更能滿足用戶的期望要求。

圖6 兩種算法對用戶不同期望的滿足程度Fig.6 The degree of satisfaction of the two algorithms to the different expectations of users

4 結束語

智能組卷策略是計算機輔助教學研究的熱點問題，需綜合考慮試卷難度、考試時長、區分度系數以及知識點覆蓋等多種約束條件。本文將改進的遺傳算子融于標準遺傳算法中，又基于組卷問題的實際需求，調整了編碼方式、加入了允許誤差，提出了一種多約束條件下的智能組卷策略。在以《C 語言程序設計》為例的試卷命題仿真對比實驗中，驗證了本文的組卷算法相較于傳統遺傳算法具有更高的應用價值。