改進(jìn)遺傳算法對醫(yī)學(xué)題庫組卷問題的應(yīng)用研究

肖桂霞，彭春富

(常德職業(yè)技術(shù)學(xué)院 現(xiàn)代教育技術(shù)中心，湖南 常德415000)

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

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

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

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

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

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

1.1 占位符編碼方案

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

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

1.2 擴位交叉算子

簡單的兩點交叉算子容易使某題型編碼段產(chǎn)生局部交叉，如果局部交叉落在一般題型段，其結(jié)果往往產(chǎn)生重題，這一點可以通過重題優(yōu)化策略[7]來解決；然而如果局部交叉落在了分支題段，會大大破壞該編碼段的結(jié)構(gòu)和質(zhì)量，使該編碼段總分支題量無法達(dá)標(biāo)，同時出現(xiàn)重題。

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

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

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

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

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

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

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

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

1.3 重題優(yōu)化策略

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

其中Son1個體出現(xiàn)了重題T3，假設(shè)在此基礎(chǔ)上再對Son2在位置8進(jìn)行變異，取與 T13同題型的 T12進(jìn)行替換，得到的Son2也將出現(xiàn)重題。

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

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

2 仿真結(jié)果及分析

為檢驗本文提出的改進(jìn)遺傳算法的實用性，分別對不含分支題的一般題庫和含分支題的醫(yī)學(xué)題庫進(jìn)行仿真實驗。并采用標(biāo)準(zhǔn)遺傳算法（算法1）和本文提出的改進(jìn)算法（算法2）分別從題庫抽取一定題量的題組成試卷做對比實驗，仿真結(jié)果均為算法嵌入系統(tǒng)運行30次所得的平均性能指標(biāo)。

2.1 一般題庫的仿真結(jié)果

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

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

表1 各算法抽取100道試題的性能指標(biāo)對比

表2 各算法抽取200道試題的性能指標(biāo)對比

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

2.2 醫(yī)學(xué)題庫的仿真結(jié)果

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

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

表3 算法抽取100道試題的性能指標(biāo)對比

表4 算法抽取200道試題的性能指標(biāo)對比

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

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

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

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

[2]鄭金華.多目標(biāo)進(jìn)化算法及其應(yīng)用[M].北京：科學(xué)出版社，2007.

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

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

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

[6]黃小明，劉長安.改進(jìn)遺傳算法在自動組卷系統(tǒng)中的應(yīng)用[J].科學(xué)技術(shù)與工程，2010，10(8)：1999-2006.

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