張迪, 容道君, 馬勇超

(1.西安歐亞學(xué)院, 信息工程學(xué)院, 陜西, 西安 710000; 2.西安交通大學(xué), 電子信息學(xué)部, 陜西, 西安 710000)

0 引言

IT技術(shù)的不斷發(fā)展使醫(yī)學(xué)領(lǐng)域在檢測、治療、診斷等方面達到了前所未有的高度,在醫(yī)學(xué)教學(xué)方面,基于3D技術(shù)構(gòu)建的人體解剖模型有力支持了解剖類課程的教學(xué)需求[1],在尸體資源相對缺乏的環(huán)境下具有重要實際意義。各大醫(yī)學(xué)院在局部解剖、系統(tǒng)解剖學(xué)等基礎(chǔ)課程的教學(xué)中往往面對較大的學(xué)生量,教師反饋學(xué)生作業(yè)情況時耗時較多,且解剖學(xué)課程大量的知識點需要學(xué)生反復(fù)記憶、大量練習以扎實基礎(chǔ),所以教師在此類課程建設(shè)中更適宜基于IT技術(shù)的支持,一方面積累試題資源庫,另一方面建立智能組卷系統(tǒng),基于各類優(yōu)化算法設(shè)定知識點、試卷難度更加科學(xué)、高效地生成作業(yè)及試卷,減少時間和空間上對學(xué)生學(xué)習環(huán)境的約束,提高學(xué)生學(xué)習效果[2]。智能組卷系統(tǒng)的核心技術(shù)是生成試卷的算法,算法的性能決定了生成試卷的開銷大小以及是否滿足教師設(shè)定參數(shù)的要求。因此,研究試卷生成算法在解剖類課程題庫中的性能表現(xiàn),對解剖類課程教學(xué)提升學(xué)生學(xué)習效果,以及相關(guān)類型的課程教學(xué)有重要意義。國內(nèi)外目前應(yīng)用的算法有隨機選取法、回溯試探法、遺傳算法、知識圖譜的多策略方法[3]等。

本文選取遺傳算法生成試卷,遺傳算法(GA)最早是由美國的 John holland于20世紀70年代提出,該算法是根據(jù)大自然中生物體進化規(guī)律而設(shè)計提出的,是一種通過模擬自然進化過程搜索最優(yōu)解的方法。與傳統(tǒng)組卷算法相比,遺傳算法具有全局搜索特性、復(fù)雜問題簡單化等特點而被廣泛應(yīng)用于試卷生成中。

然而,遺傳算法作為一種智能優(yōu)化算法存在一些局限性,如迭代過程緩慢和早熟收斂等問題,本文基于此類問題提出了動態(tài)變異的改進方案,以提升算法的性能。

1 解剖課程試題庫

系統(tǒng)解剖課程包括骨學(xué)、關(guān)節(jié)學(xué)、肌學(xué)、內(nèi)臟學(xué)總論、消化系統(tǒng)、呼吸系統(tǒng)、泌尿系統(tǒng)、生殖系統(tǒng)、腹膜、會陰、心血管系統(tǒng)總論、心等章節(jié),局部解剖課程包括頭部、頸部、腹部、盆部與會陰等章節(jié),題目類型設(shè)置為單選題、多選題、識圖題,題目類型的設(shè)置滿足學(xué)生加深知識記憶的同時,通過對圖片更深入形象地理解人體各部位的解剖性狀。肝門靜脈和肩部識圖題,如圖1所示。

圖1 肝門靜脈和肩部識圖題

識圖題的圖片來源于課題研究團隊研發(fā)構(gòu)建的系統(tǒng)解剖和局部解剖的骨骼、骨連結(jié)、肌肉、動脈、靜脈、神經(jīng)系統(tǒng)、呼吸系統(tǒng)、消化系統(tǒng)、泌尿系統(tǒng)、淋巴系統(tǒng)、皮膚等三維模型3700多個,設(shè)計試題3000多道。

表1 試題庫

2 遺傳算法設(shè)計與數(shù)學(xué)模型

遺傳算法通常先初始化隨機產(chǎn)生一個包含20張試卷個體的集合作為初始種群,然后對每一個試卷個體計算相應(yīng)的適應(yīng)度,用來衡量一個試卷個體的優(yōu)劣。操作步驟包括選擇、交叉、變異、計算適應(yīng)度。首先是對初始化種群進行選擇方法篩選優(yōu)秀個體作為父代,再對篩選過后的父代個體進行交叉方法產(chǎn)生子代,然后進行個體變異操作,經(jīng)過選擇、交叉和變異后判斷是否有滿足需求個體產(chǎn)生,否則一直循環(huán)重復(fù)選擇,交叉,變異操作,直到迭代次數(shù)達到規(guī)定次數(shù),或者有達到滿足要求的個體產(chǎn)生。

(1) 試卷編碼

試卷編碼采用實數(shù)編碼方案,將一份試卷映射為一個染色體,試卷里每一道題映射為一個基因,題號即為基因的值,每一道題在數(shù)據(jù)庫內(nèi)有難度與對應(yīng)知識點兩個參數(shù),每種題型分段存放。由于題庫龐大采用二進制編碼需要對題庫每一個題目進行編碼,選中為1不選中為0,題庫越大解碼過程越久,所以本算法采用的是實數(shù)編碼。

(2) 初始化種群

在初始化種群時,設(shè)產(chǎn)生初始種群A,a為試卷,w為試題[2]。

(1)

(3) 適應(yīng)度函數(shù)的設(shè)計

試卷難度P指一張試卷的整體難度,k是試卷所含的題目數(shù),Di和Si分別是第i題的難度系數(shù)和分數(shù)。

(2)

知識點覆蓋率R是期望知識點個數(shù)除以試卷總知識點的并集,M是一張試卷所有題目知識點的并集,N是期望包含的知識點。

(3)

式中,適應(yīng)度函數(shù)為F,知識點的覆蓋率為R,試卷難度為P,用戶期望難度為EP,其中f1為知識點分布的權(quán)重,f2為難度系數(shù)所占權(quán)重。當f1=0時退化為只限制試題難度系數(shù),當f2=0時退化為只限制知識點分布。

(4)

(4) 選擇算子設(shè)計

選擇算子采用了最優(yōu)選擇方法,最優(yōu)選擇法模擬了自然界中適者生存的自然現(xiàn)象,直接從種群中獲取適應(yīng)度最高個體保留到下一代。最優(yōu)選擇法使種群中最優(yōu)秀個體不經(jīng)過交叉操作,把優(yōu)良基因直接保留到子代,有效的對整體的進化方向起到較好的作用。適應(yīng)度最高試卷L,a為試卷,F為適應(yīng)度。

(5)

(5) 交叉算子設(shè)計

交叉算子采用了兩點交叉,由兩個父代隨機獲取兩個點分成三段,每個父代選出一部分組成一個新的個體。采用兩點交叉出現(xiàn)相同試卷個體的幾率會比單點交叉明顯降低。tp0、tp1為父代,進行兩點交叉過程后生成子代tp01。

(6)

(7)

(8)

(6) 變異算子設(shè)計

變異算子在遺傳算法中起到了很大的作用,變異能夠讓種群產(chǎn)生新的試題來保證種群的多樣性,使劣質(zhì)個體能變異后適者生存[4]。種群中每一張試卷每一道題進行概率變異,遍歷每道題時隨機產(chǎn)生一個數(shù)如果小于Z,就從題庫抽取一道與變異題目類型相同的題目進行交換[5]。

(9)

如Z=0.085,an為試卷,wnk為一道題目,遍歷到wnk時產(chǎn)生的隨機值小于Z,就對wnk進行變異。

3 遺傳算法的改進

3.1 改進變異算子

在突變算子中,由于每個個體的每個基因都有突變的的可能性,隨著種群和個體基因的擴大,在變異概率過小時,會使重復(fù)迭代的次數(shù)增多,頻繁的發(fā)生迭代很多次仍達不到期望的適應(yīng)度[6],變異度過大會因為頻繁的數(shù)據(jù)比對,造成迭代效率的下降,總體都會影響組卷的效率。因此,選擇一個合適的變異概率,會極大的提高組卷的效率。

有研究表明,對于變異概率的選擇,在0.1～0.001最佳,通過對該限定范圍內(nèi)概率的大量實驗,得出使變異概率在區(qū)間[0.055～0.065]動態(tài)變換,會使迭代達不到期望適應(yīng)度的概率大大減小,提升了迭代效率[7]。初始規(guī)定變異概率為0.055,當?shù)霈F(xiàn)重復(fù)適應(yīng)度時,立即改變變異概率為0.065,促進變異更快,減少出現(xiàn)重復(fù)適應(yīng)度而帶來的開銷,當適應(yīng)度恢復(fù)正常的增長時立刻將變異概率調(diào)回0.055,提升迭代速度,進而改進算法效率。改進后的遺傳算法流程如圖2所示。改進的動態(tài)變異算法流程如圖3所示。

ALGORITHM 1 Improved algorithm pseudo code

圖2 改進后的遺傳算法流程圖

圖3 改進的動態(tài)變異算法流程圖

2 Paper max_paper;

3 //此代試卷個體

4 Paper paper

5 //變異概率

6 double mutationRate=0.055;

7 while(迭代次數(shù)未達到最大值and適應(yīng)度未達到期望值)

8 {

9 //選擇算子

The maximum number of persons with C/D lesions by TASC II were noted in the HS group; the minimum is in the EP group.

10 select();

11 //交叉算子

12 crossover();

13 //變異算子

14 mutate(max_paper,paper)

15 {

16 if(max_paper的適應(yīng)度=paper的適應(yīng)度)

17 {

18 mutationRate=0.065;

19 }

20 else

21 {

22 mutationRate=0.055;

23 }

24 }

25 //計算適應(yīng)度

26 setAdaptationDegree();

27 }

4 實驗驗證

4.1 算例設(shè)置

本文通過維薩里公司提供的題庫數(shù)據(jù)進行算法的驗證,題庫試題參數(shù)分別有題號、題型、知識點、題目、選項、答案、難度、分數(shù)。設(shè)置最大迭代次數(shù)為兩百代,將變異概率從0.035～0.095每隔0.010分十組進行測試驗證。

每組進行算法實驗100次,分別測試不同變異概率對平均迭代次數(shù)、平均運行時間、最大連續(xù)重復(fù)迭代次數(shù)及迭代兩百代仍未達到期望適應(yīng)度的次數(shù)的影響,再將變異概率設(shè)置在區(qū)間[0.055～0.065]動態(tài)調(diào)整,記錄變異概率從0.035～0.095每隔0.010分十組進行測試的實驗結(jié)果如圖4所示。從圖4可以得出,當變異概率在0.055時,可以理解為當環(huán)境給予物種的壓力處于中游的水平時,物種進化和適應(yīng)環(huán)境的能力較好,產(chǎn)生適應(yīng)環(huán)境的個體數(shù)目較多。圖5記錄了不同的變異概率下出現(xiàn)迭代至最大代數(shù)200代后仍然沒有達到要求的適應(yīng)度的個體出現(xiàn)的次數(shù),可以看到曲線呈現(xiàn)出兩邊高中間低的趨勢,說明變異概率在中游波動時,能夠得到較好的個體,所以基于以上實驗的數(shù)據(jù)結(jié)果,取區(qū)間[0.055～0.065]來設(shè)置變異概率。圖6為變異概率在區(qū)間[0.055～0.065]內(nèi)動態(tài)調(diào)整測試數(shù)據(jù),可以發(fā)現(xiàn)測試100次迭代到兩百代仍未達到期望適應(yīng)度值的次數(shù)僅為6次,平均迭代次數(shù)僅為46次,最大平均重復(fù)連續(xù)次數(shù)僅為27次,耗時10.4 s比最好實驗結(jié)果慢2.23 s,但獲得了較多的優(yōu)良試卷個體。

圖4 不同變異概率測試結(jié)果

圖5 不同變異概率下未達到期望次數(shù)

圖6 動態(tài)變異概率下測試結(jié)果

4.2 算例結(jié)果與分析

實驗發(fā)現(xiàn),在單一固定的變異概率中,變異概率為0.055時,測試的不同概率對平均迭代次數(shù),平均運行時間,最大連續(xù)重復(fù)迭代次數(shù)及迭代兩百代仍未達到期望適應(yīng)度的次數(shù),實驗結(jié)果相對最優(yōu),變異概率為0.065及0.085效果次之。

由圖7可知,將在區(qū)間[0.055～0.065]動態(tài)調(diào)整的變異概率與最優(yōu)的固定概率0.055、文獻[1]中的固定概率0.085進行對比發(fā)現(xiàn),動態(tài)的將變異概率在區(qū)間[0.055～0.065]調(diào)整會使得未達到期望適應(yīng)度的次數(shù)降低,平均迭代次數(shù)更少,出現(xiàn)重復(fù)迭代的次數(shù)也大大減少,極大的提高了變異效率,提升了組卷的效率和穩(wěn)定性。

圖7 基準實例測試結(jié)果比較

5 總結(jié)

為生成最優(yōu)試卷個體,降低時間成本和機器開銷,建立了解剖課程題庫模型,通過對遺傳算法進行高效組卷問題的研究,引入了改進變異算子,模擬自然界環(huán)境壓力的思想,找到適合產(chǎn)生更優(yōu)個體的變異概率,從而提出區(qū)間內(nèi)動態(tài)變異的方法,增強了尋優(yōu)能力,相較于其他改進算法,求解的穩(wěn)定性和速度得到提升,驗證了本改進算法的有效性。