改進遺傳算法對醫學題庫組卷問題的應用研究

肖桂霞，彭春富

(常德職業技術學院 現代教育技術中心，湖南 常德415000)

隨著國家新醫改政策的推行與深入，從事醫療衛生事業的人才隊伍不斷壯大，給這類考試的組考和閱卷帶來很大的困難。目前國家醫師、護士執業資格考試等理論考核部分仍采用紙質試卷考核方式，各大高校醫學專業考核中僅極少數采用了在線抽題組卷的方式，且題型簡單暫未擴展到病例分析和標準配伍等分支題題型。設計符合醫學題庫特點的智能組卷算法對未來醫學類網絡考試系統的建立有著重要的應用價值和現實意義。

遺傳算法是一種模擬生物進化過程和自然遺傳機制的過程搜索最優解的算法，與傳統的算法相比，遺傳算法具有內在并行性、高魯棒性、全局尋優和收斂速度快的特點。它尤其適用于處理傳統搜索方法難以解決的非線性、多約束等復雜問題[1-2]。智能組卷問題是一個典型的多約束問題，遺傳算法已經廣泛應用于求解該類問題[3-6]。

本文主要對含一個病例描述、多個分支子題的醫學混合題庫進行研究，針對分支題型和總分支題量難以控制的問題，對遺傳算法進行了改進。提出了占位符編碼方案、擴位交叉算子和重題優化策略，仿真結果表明，改進后的遺傳算法能有效地解決上述問題，完成各種復雜題型題庫的抽題組卷任務，具有很好的實用價值。

1 改進的遺傳算法

標準遺傳算法是針對只含一般題型的題庫設計的，如果應用于醫學類專業含一般題型和分支題型的混合題庫，將出現個體編碼長度不定、個體編碼中題型分段界限難以判斷、不同題型間可能進行了交叉變異操作而導致染色體混亂等問題；更令人困擾的是，分支題段因局部交叉會破壞該編碼段題目的總分支題量，導致出現重題。

綜上所述，一種更通用、能適應各種不同題型的智能抽題算法對醫學題庫來說將是非常具有現實意義的。為說明問題，此處約定題數和題量的含義，題數指題目個數，題量指一個題目所含分支數，此分支要記入試卷總題量。只含一般題型的題庫其題數和題量是一致的，但含分支題的題庫卻并非如此，組卷時應該嚴格按照題量進行組卷而不是題數。

1.1 占位符編碼方案

為解決上述問題，提出一種基于占位符的編碼方案。該方案根據組卷條件中要求的每種題型的題量統一各題型段的染色體長度。在分題型段進行定長編碼的基礎上，加入一種占位符。初始化種群時，邊抽題邊累計某題型段的實際題量，如果該段染色體還未達到指定長度時實際題量已經滿足要求，則后面的題就用占位符代替。為方便操作，一般選取題庫中不存在的題號作為占位符。

以下舉例以更好地闡述。題庫中T1～T6為選擇題，T7(2)、T8(5)、T9(3)、T10(4)、T11(2)、T12(2)為 分 支 題 (括 號 中的數字為每題題量，即分支數)，T13～T20為計算題。抽取10題，分題型段題量要求分別為3、5、2。首先隨機抽取10 題 為 T2、T5、T1、T9、T7、T8、T12、T11、T19和 T20； 設 占 位 符為 Z，編號為-1。則試卷組成為 T2T5T1T9T7ZZZT19T20，個體編碼為 2 5 1 9 7-1-1-1 19 20。

1.2 擴位交叉算子

簡單的兩點交叉算子容易使某題型編碼段產生局部交叉，如果局部交叉落在一般題型段，其結果往往產生重題，這一點可以通過重題優化策略[7]來解決；然而如果局部交叉落在了分支題段，會大大破壞該編碼段的結構和質量，使該編碼段總分支題量無法達標，同時出現重題。

為此設計了一種擴位交叉算子，這種交叉算子不影響一般題型段的交叉，同時分支題型段交叉后也不會打亂原有題量和出現重題。具體步驟如下：

(1)隨機生成染色體長度以內的兩個交叉點P1和P2。通過交換交叉點的操作確保P1小于P2；

(2)獲取當前題型段的起始位置 L1和 L2，并判斷此題型段是否為分支題型；

(3)若是，則繼續判斷P1是否落在[L1，L2]區間。是則擴位 P1為 L1；若否，則轉步驟(5)；

(4)判斷 P2是否在[L1，L2]區間內，若是則擴位 P2為L2；

(5)判斷題型段指針是否已經指向末尾，若是則結束交叉點的擴位，否則指針向后移，并且轉步驟(2)。

圖1～圖3為交叉點被擴位的示例圖。其中，實心點為當前分支題型段的起始界標L1和L2，空心點為交叉算子的交叉點P1和P2。從圖中可以發現，交叉點被擴位后再進行交叉操作使得分支題型段只要有交叉，一定是該題型段的整體交叉。這樣一來，該題型段的總分支題量和題目結構都是整體交換的，只要父代是合法的，子代也一定是合法的。

擴位交叉操作后，變異算子也要做相應改進。為了控制各題型段的題量，需選擇與某題題量相等、題型一致，且在當前題型分段中還未出現過的題目進行變異替換，這樣可以保留擴位交叉的成果，同時實現分支題型段的微調與更新。

1.3 重題優化策略

上述算法設計中，交叉和變異操作可能導致重題出現。如父代個體Parent1、Parent2在位置3和位置7處進行兩點交叉，交叉后得到子代個體Son1、Son2：

其中Son1個體出現了重題T3，假設在此基礎上再對Son2在位置8進行變異，取與 T13同題型的 T12進行替換，得到的Son2也將出現重題。

對于重題的處理，大多在每次進化后檢查重題，并進行替換[6]。每代種群更新后都必須對整個種群進行一次重題檢測與替換，這樣會耗費大量的時間；另外算法在進化過程中，不進行去重題干予能最大限度地保護進化成果，帶重題的試卷和不帶重題的試卷同屬于一個進化空間[6]，減少干予能幫助算法搜索更大范圍的進化空間；如果只選擇同一張試卷中未曾出現的新題進行替換，有可能會破壞現有的進化成果，降低原本優秀個體的適應值。

為解決上述問題，本文提出一種重題優化策略，該策略包含重題甄別和重題替換兩部分。重題甄別能快速甄別并替換試卷中的重題。重題替換只對進化后的最優解進行去重題操作[7]。

2 仿真結果及分析

為檢驗本文提出的改進遺傳算法的實用性，分別對不含分支題的一般題庫和含分支題的醫學題庫進行仿真實驗。并采用標準遺傳算法（算法1）和本文提出的改進算法（算法2）分別從題庫抽取一定題量的題組成試卷做對比實驗，仿真結果均為算法嵌入系統運行30次所得的平均性能指標。

2.1 一般題庫的仿真結果

首先對1 000題的數學題庫進行實驗。題庫中題型1占500題，題型 2占 300題，題型 3占 200題，且所有題均只有一個分支。組卷時要求難度級別“易”占30%、“中”占50%、“難”占20%；章節分布可自行設置也可選擇按照在題庫中所占比例抽取。

表1是從中抽取100題的仿真結果，其中3種題型比例為5:3:2，卷面分100分。表2是抽取200題的仿真結果，題型比例不變，卷面分200分。

表1 各算法抽取100道試題的性能指標對比

表2 各算法抽取200道試題的性能指標對比

從表中可以發現，兩個算法最終獲得的最優解適應值差不多，并且都滿足組卷要求的題量。算法2的時間耗費明顯低于算法1，這是因為算法2采取了重題優化策略[7]的結果。

2.2 醫學題庫的仿真結果

構建內科護理1 000道題的題庫，其中一般題型題700道，分支題型題300道，且這些分支題所含的分支數均不超過 5，分支數為 2、3、4、5的題目在題庫中的比例為12:8:3:2；組卷時的難度級別要求、章節分布要求等均與2.1節中相同。

如果將題量要求綜合到適應值計算中，算法1將無法收斂，因此在下列對比中，題量要求從適應值計算中分解出來，單獨作為一個評價指標列出來以供分析。表3和表4分別為從內科護理題庫中抽取100道試題（分支題題量占30道）和200道試題（分支題題量占60道）的仿真結果。

表3 算法抽取100道試題的性能指標對比

表4 算法抽取200道試題的性能指標對比

從表3、表4中可以看出，算法2的時間耗費明顯低于算法1，這主要歸功于算法2采用的重題優化策略[7]，并且這種優勢在試卷題量更大時體現得更明顯。兩種算法雖然都能夠收斂，但題量指標并不符合組卷要求。

對醫學題庫的仿真結果表明，算法2的綜合性能較好，本文提出的編碼方案和遺傳算子對解決醫學類含多分支題題庫的組卷問題非常有效。

從不同題庫的仿真結果來看，本文提出的改進遺傳算法不僅可以廣泛應用于一般題庫的組卷問題，更重要的是它解決了含分支題題庫抽題組卷時如何精確控制總分支題量的難題，算法對各種不同類型的題庫以及各種復雜的題型都具有很好的適應和求解能力。改進的算法已經集成于我院護理系題庫系統并投入使用，主要用于期末組卷和自主招生的專業組考。今后的工作將致力于設計動態的變異池來提高算法的收斂速度與精度。

[1]陳國良，王煦法，莊鎮泉，等.遺傳算法及其應用[M].北京：人民郵電出版社，1996.

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

[3]董敏，霍劍青，王曉蒲.基于自適應遺傳算法的智能組卷研究[J].小型微型計算機系統，2004，25(1)：82-85.

[4]朱劍冰，李戰懷，趙娜.基于混合遺傳算法的自動組卷問題的研究[J].計算機仿真，2009，26(5)：328-331.

[5]全惠云，范國闖，趙霆雷.基于遺傳算法的試題庫智能組卷系統研究[J].武漢大學學報(自然科學版)，1999，45(5)：758-760.

[6]黃小明，劉長安.改進遺傳算法在自動組卷系統中的應用[J].科學技術與工程，2010，10(8)：1999-2006.

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