基于改進遺傳算法的解剖類課程組卷研究

張迪, 容道君, 馬勇超

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

0 引言

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

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

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

1 解剖課程試題庫

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

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

識圖題的圖片來源于課題研究團隊研發構建的系統解剖和局部解剖的骨骼、骨連結、肌肉、動脈、靜脈、神經系統、呼吸系統、消化系統、泌尿系統、淋巴系統、皮膚等三維模型3700多個,設計試題3000多道。

表1 試題庫

2 遺傳算法設計與數學模型

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

(1) 試卷編碼

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

(2) 初始化種群

在初始化種群時,設產生初始種群A,a為試卷,w為試題[2]。

(1)

(3) 適應度函數的設計

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

(2)

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

(3)

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

(4)

(4) 選擇算子設計

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

(5)

(5) 交叉算子設計

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

(6)

(7)

(8)

(6) 變異算子設計

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

(9)

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

3 遺傳算法的改進

3.1 改進變異算子

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

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

ALGORITHM 1 Improved algorithm pseudo code

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

圖3 改進的動態變異算法流程圖

2 Paper max_paper;

3 //此代試卷個體

4 Paper paper

5 //變異概率

6 double mutationRate=0.055;

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

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的適應度=paper的適應度)

17 {

18 mutationRate=0.065;

19 }

20 else

21 {

22 mutationRate=0.055;

23 }

24 }

25 //計算適應度

26 setAdaptationDegree();

27 }

4 實驗驗證

4.1 算例設置

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

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

圖4 不同變異概率測試結果

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

圖6 動態變異概率下測試結果

4.2 算例結果與分析

實驗發現,在單一固定的變異概率中,變異概率為0.055時,測試的不同概率對平均迭代次數,平均運行時間,最大連續重復迭代次數及迭代兩百代仍未達到期望適應度的次數,實驗結果相對最優,變異概率為0.065及0.085效果次之。

由圖7可知,將在區間[0.055～0.065]動態調整的變異概率與最優的固定概率0.055、文獻[1]中的固定概率0.085進行對比發現,動態的將變異概率在區間[0.055～0.065]調整會使得未達到期望適應度的次數降低,平均迭代次數更少,出現重復迭代的次數也大大減少,極大的提高了變異效率,提升了組卷的效率和穩定性。

圖7 基準實例測試結果比較

5 總結

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