摘  要： 對含分支題的醫(yī)學(xué)題庫進行研究，并對遺傳算法做了改進，提出了占位符編碼方案、擴位交叉算子和重題優(yōu)化策略。占位符編碼方案能分段定長編碼的同時累計各題型段的實際分支題量；擴位交叉算子能智能擴展落在分支題段的交叉點，避免因分支題段局部交叉而出現(xiàn)重題和實際分支題量與條件不符等情況；重題優(yōu)化策略能快速替換重題，有效縮短組卷時間。仿真結(jié)果表明，改進的算法能適應(yīng)不同題型，在不影響一般題型段抽取與進化的同時，精確控制分支題段的總分支題量和質(zhì)量，是解決醫(yī)學(xué)題庫智能組卷問題的一種有效途徑。
關(guān)鍵詞： 智能組卷；遺傳算法；醫(yī)學(xué)題庫；重題優(yōu)化策略；占位符編碼；擴位交叉算子

   隨著國家新醫(yī)改政策的推行與深入，從事醫(yī)療衛(wèi)生事業(yè)的人才隊伍不斷壯大，給這類考試的組考和閱卷帶來很大的困難。目前國家醫(yī)師、護士執(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)實意義。
    遺傳算法是一種模擬生物進化過程和自然遺傳機制的過程搜索最優(yōu)解的算法，與傳統(tǒng)的算法相比，遺傳算法具有內(nèi)在并行性、高魯棒性、全局尋優(yōu)和收斂速度快的特點。它尤其適用于處理傳統(tǒng)搜索方法難以解決的非線性、多約束等復(fù)雜問題[1-2]。智能組卷問題是一個典型的多約束問題，遺傳算法已經(jīng)廣泛應(yīng)用于求解該類問題[3-6]。
    本文主要對含一個病例描述、多個分支子題的醫(yī)學(xué)混合題庫進行研究，針對分支題型和總分支題量難以控制的問題，對遺傳算法進行了改進。提出了占位符編碼方案、擴位交叉算子和重題優(yōu)化策略，仿真結(jié)果表明，改進后的遺傳算法能有效地解決上述問題，完成各種復(fù)雜題型題庫的抽題組卷任務(wù)，具有很好的實用價值。
1 改進的遺傳算法
    標(biāo)準(zhǔn)遺傳算法是針對只含一般題型的題庫設(shè)計的，如果應(yīng)用于醫(yī)學(xué)類專業(yè)含一般題型和分支題型的混合題庫，將出現(xiàn)個體編碼長度不定、個體編碼中題型分段界限難以判斷、不同題型間可能進行了交叉變異操作而導(dǎo)致染色體混亂等問題；更令人困擾的是，分支題段因局部交叉會破壞該編碼段題目的總分支題量，導(dǎo)致出現(xiàn)重題。
    綜上所述，一種更通用、能適應(yīng)各種不同題型的智能抽題算法對醫(yī)學(xué)題庫來說將是非常具有現(xiàn)實意義的。為說明問題，此處約定題數(shù)和題量的含義，題數(shù)指題目個數(shù)，題量指一個題目所含分支數(shù)，此分支要記入試卷總題量。只含一般題型的題庫其題數(shù)和題量是一致的，但含分支題的題庫卻并非如此，組卷時應(yīng)該嚴(yán)格按照題量進行組卷而不是題數(shù)。
1.1 占位符編碼方案
    為解決上述問題，提出一種基于占位符的編碼方案。該方案根據(jù)組卷條件中要求的每種題型的題量統(tǒng)一各題型段的染色體長度。在分題型段進行定長編碼的基礎(chǔ)上，加入一種占位符。初始化種群時，邊抽題邊累計某題型段的實際題量，如果該段染色體還未達到指定長度時實際題量已經(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ì)量，使該編碼段總分支題量無法達標(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)，交叉點被擴位后再進行交叉操作使得分支題型段只要有交叉，一定是該題型段的整體交叉。這樣一來，該題型段的總分支題量和題目結(jié)構(gòu)都是整體交換的，只要父代是合法的，子代也一定是合法的。

    對于重題的處理，大多在每次進化后檢查重題，并進行替換[6]。每代種群更新后都必須對整個種群進行一次重題檢測與替換，這樣會耗費大量的時間；另外算法在進化過程中，不進行去重題干予能最大限度地保護進化成果，帶重題的試卷和不帶重題的試卷同屬于一個進化空間[6]，減少干予能幫助算法搜索更大范圍的進化空間；如果只選擇同一張試卷中未曾出現(xiàn)的新題進行替換，有可能會破壞現(xiàn)有的進化成果，降低原本優(yōu)秀個體的適應(yīng)值。
    為解決上述問題，本文提出一種重題優(yōu)化策略，該策略包含重題甄別和重題替換兩部分。重題甄別能快速甄別并替換試卷中的重題。重題替換只對進化后的最優(yōu)解進行去重題操作[7]。
2 仿真結(jié)果及分析
    為檢驗本文提出的改進遺傳算法的實用性，分別對不含分支題的一般題庫和含分支題的醫(yī)學(xué)題庫進行仿真實驗。并采用標(biāo)準(zhǔn)遺傳算法（算法1）和本文提出的改進算法（算法2）分別從題庫抽取一定題量的題組成試卷做對比實驗，仿真結(jié)果均為算法嵌入系統(tǒng)運行30次所得的平均性能指標(biāo)。
2.1 一般題庫的仿真結(jié)果
    首先對1 000題的數(shù)學(xué)題庫進行實驗。題庫中題型1占500題，題型2占300題，題型3占200題，且所有題均只有一個分支。組卷時要求難度級別“易”占30%、“中”占50%、“難”占20%；章節(jié)分布可自行設(shè)置也可選擇按照在題庫中所占比例抽取。
    表1是從中抽取100題的仿真結(jié)果，其中3種題型比例為5:3:2，卷面分100分。表2是抽取200題的仿真結(jié)果，題型比例不變，卷面分200分。

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

    對醫(yī)學(xué)題庫的仿真結(jié)果表明，算法2的綜合性能較好，本文提出的編碼方案和遺傳算子對解決醫(yī)學(xué)類含多分支題題庫的組卷問題非常有效。
    從不同題庫的仿真結(jié)果來看，本文提出的改進遺傳算法不僅可以廣泛應(yīng)用于一般題庫的組卷問題，更重要的是它解決了含分支題題庫抽題組卷時如何精確控制總分支題量的難題，算法對各種不同類型的題庫以及各種復(fù)雜的題型都具有很好的適應(yīng)和求解能力。改進的算法已經(jīng)集成于我院護理系題庫系統(tǒng)并投入使用，主要用于期末組卷和自主招生的專業(yè)組考。今后的工作將致力于設(shè)計動態(tài)的變異池來提高算法的收斂速度與精度。
參考文獻
[1] 陳國良，王煦法，莊鎮(zhèn)泉，等.遺傳算法及其應(yīng)用[M].北京：人民郵電出版社，1996.
[2] 鄭金華.多目標(biāo)進化算法及其應(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] 黃小明，劉長安.改進遺傳算法在自動組卷系統(tǒng)中的應(yīng)用[J].科學(xué)技術(shù)與工程，2010，10(8)：1999-2006.
[7] 肖桂霞，趙武初，朱偉，等.基于遺傳算法智能組卷的去重題方法[J].計算機工程，2012，38(11)：150-152.