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

   隨著國家新醫(yī)改政策的推行與深入，從事醫(yī)療衛(wèi)生事業(yè)的人才隊(duì)伍不斷壯大，給這類考試的組考和閱卷帶來很大的困難。目前國家醫(yī)師、護(hù)士執(zhí)業(yè)資格考試等理論考核部分仍采用紙質(zhì)試卷考核方式，各大高校醫(yī)學(xué)專業(yè)考核中僅極少數(shù)采用了在線抽題組卷的方式，且題型簡單暫未擴(kuò)展到病例分析和標(biāo)準(zhǔn)配伍等分支題題型。設(shè)計(jì)符合醫(yī)學(xué)題庫特點(diǎn)的智能組卷算法對未來醫(yī)學(xué)類網(wǎng)絡(luò)考試系統(tǒng)的建立有著重要的應(yīng)用價(jià)值和現(xiàn)實(shí)意義。
    遺傳算法是一種模擬生物進(jìn)化過程和自然遺傳機(jī)制的過程搜索最優(yōu)解的算法，與傳統(tǒng)的算法相比，遺傳算法具有內(nèi)在并行性、高魯棒性、全局尋優(yōu)和收斂速度快的特點(diǎn)。它尤其適用于處理傳統(tǒng)搜索方法難以解決的非線性、多約束等復(fù)雜問題[1-2]。智能組卷問題是一個(gè)典型的多約束問題，遺傳算法已經(jīng)廣泛應(yīng)用于求解該類問題[3-6]。
    本文主要對含一個(gè)病例描述、多個(gè)分支子題的醫(yī)學(xué)混合題庫進(jìn)行研究，針對分支題型和總分支題量難以控制的問題，對遺傳算法進(jìn)行了改進(jìn)。提出了占位符編碼方案、擴(kuò)位交叉算子和重題優(yōu)化策略，仿真結(jié)果表明，改進(jìn)后的遺傳算法能有效地解決上述問題，完成各種復(fù)雜題型題庫的抽題組卷任務(wù)，具有很好的實(shí)用價(jià)值。
1 改進(jìn)的遺傳算法
    標(biāo)準(zhǔn)遺傳算法是針對只含一般題型的題庫設(shè)計(jì)的，如果應(yīng)用于醫(yī)學(xué)類專業(yè)含一般題型和分支題型的混合題庫，將出現(xiàn)個(gè)體編碼長度不定、個(gè)體編碼中題型分段界限難以判斷、不同題型間可能進(jìn)行了交叉變異操作而導(dǎo)致染色體混亂等問題；更令人困擾的是，分支題段因局部交叉會破壞該編碼段題目的總分支題量，導(dǎo)致出現(xiàn)重題。
    綜上所述，一種更通用、能適應(yīng)各種不同題型的智能抽題算法對醫(yī)學(xué)題庫來說將是非常具有現(xiàn)實(shí)意義的。為說明問題，此處約定題數(shù)和題量的含義，題數(shù)指題目個(gè)數(shù)，題量指一個(gè)題目所含分支數(shù)，此分支要記入試卷總題量。只含一般題型的題庫其題數(shù)和題量是一致的，但含分支題的題庫卻并非如此，組卷時(shí)應(yīng)該嚴(yán)格按照題量進(jìn)行組卷而不是題數(shù)。
1.1 占位符編碼方案
    為解決上述問題，提出一種基于占位符的編碼方案。該方案根據(jù)組卷?xiàng)l件中要求的每種題型的題量統(tǒng)一各題型段的染色體長度。在分題型段進(jìn)行定長編碼的基礎(chǔ)上，加入一種占位符。初始化種群時(shí)，邊抽題邊累計(jì)某題型段的實(shí)際題量，如果該段染色體還未達(dá)到指定長度時(shí)實(shí)際題量已經(jīng)滿足要求，則后面的題就用占位符代替。為方便操作，一般選取題庫中不存在的題號作為占位符。
    以下舉例以更好地闡述。題庫中T1～T6為選擇題，T7(2)、T8(5)、T9(3)、T10(4)、T11(2)、T12(2)為分支題(括號中的數(shù)字為每題題量，即分支數(shù))，T13～T20為計(jì)算題。抽取10題，分題型段題量要求分別為3、5、2。首先隨機(jī)抽取10題為T2、T5、T1、T9、T7、T8、T12、T11、T19和T20；設(shè)占位符為Z，編號為-1。則試卷組成為T2T5T1T9T7ZZZT19T20，個(gè)體編碼為2 5 1 9 7 -1 -1 -1 19 20。
1.2 擴(kuò)位交叉算子
    簡單的兩點(diǎn)交叉算子容易使某題型編碼段產(chǎn)生局部交叉，如果局部交叉落在一般題型段，其結(jié)果往往產(chǎn)生重題，這一點(diǎn)可以通過重題優(yōu)化策略[7]來解決；然而如果局部交叉落在了分支題段，會大大破壞該編碼段的結(jié)構(gòu)和質(zhì)量，使該編碼段總分支題量無法達(dá)標(biāo)，同時(shí)出現(xiàn)重題。
    為此設(shè)計(jì)了一種擴(kuò)位交叉算子，這種交叉算子不影響一般題型段的交叉，同時(shí)分支題型段交叉后也不會打亂原有題量和出現(xiàn)重題。具體步驟如下：
    (1)隨機(jī)生成染色體長度以內(nèi)的兩個(gè)交叉點(diǎn)P1和P2。通過交換交叉點(diǎn)的操作確保P1小于P2；
    (2)獲取當(dāng)前題型段的起始位置L1和L2，并判斷此題型段是否為分支題型；
    (3)若是，則繼續(xù)判斷P1是否落在[L1，L2]區(qū)間。是則擴(kuò)位P1為L1；若否，則轉(zhuǎn)步驟(5)；
    (4)判斷P2是否在[L1，L2]區(qū)間內(nèi)，若是則擴(kuò)位P2為L2；
    (5)判斷題型段指針是否已經(jīng)指向末尾，若是則結(jié)束交叉點(diǎn)的擴(kuò)位，否則指針向后移，并且轉(zhuǎn)步驟(2)。
    圖1～圖3為交叉點(diǎn)被擴(kuò)位的示例圖。其中，實(shí)心點(diǎn)為當(dāng)前分支題型段的起始界標(biāo)L1和L2，空心點(diǎn)為交叉算子的交叉點(diǎn)P1和P2。從圖中可以發(fā)現(xiàn)，交叉點(diǎn)被擴(kuò)位后再進(jìn)行交叉操作使得分支題型段只要有交叉，一定是該題型段的整體交叉。這樣一來，該題型段的總分支題量和題目結(jié)構(gòu)都是整體交換的，只要父代是合法的，子代也一定是合法的。

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

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

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