多種人工智能算法的數據庫技術課程自動組卷比較①

彭康華, 黃裕鋒, 姚江梅

(廣東工程職業技術學院 信息工程學院,廣州 510520)

現階段的數據庫技術專業課程的考試中,有學校用機試,也有用筆試,其操作過程為個人出卷、發卷,考生考完后,需回收試卷,再交到改卷老師手里,工作量巨大且效率低下,耗費了大量人力、物力和財力. 因此,開發數據庫技術專業課程考試資源庫與在線考試系統刻不容緩,以期推行無紙化組卷及考試,提高工作效率同時降低人財物力. 要推行無紙化在線考核,關鍵技術為自動化組卷問題,其組卷結果及效率是眾多學者關心和研究熱點[1-3]. 在學者們研究的基礎上,對多種組卷技術及方法進行對比和研究,主要有隨機變量法、回溯試探法及人工智能法. 最早所使用的隨機變量算法,顧名思義為隨機選擇題目實施試卷組合,后與目標期望值來比對,達到要求即形成考試試卷,該方法易于操作,但因為僅僅是排列組合,故試卷組裝的質量不佳,費時費力,失敗率極高. 回溯試探算法進一步優化了組卷效率,無效試卷得到控制,但缺點是題庫數目大時,回溯的數量大大增加,使用時間更長,耗費大量的系統內存. 為了更好組成高質量的試卷,滿足在線考試的要求,本文更多的是討論和研究人工智能算法,主要是遺傳算法及蟻群算法. 通過對比,使用更加高效的算法應用于自動組卷,從而更好的促進在線考試和遠程教育的發展.

1 遺傳算法與蟻群算法組卷簡介

求解遺傳算法的關鍵是在多目標求解時引入了競爭機制及變異機制,關鍵問題是優化遺傳算子、交叉算子和變異算子. 而求解蟻群算法的關鍵是在蟻群爬過的路段上釋放信息素,其濃度可以反映出路段的優劣,得出最佳解[4,5]. 與遺傳算法和蟻群算法相類似,自動化組卷的過程即為求得多目標最優解的過程[6].

2 構建組卷質量指標體系

數據庫技術專業課程組卷關鍵是按試卷的要求及期望來形成試卷,指標體系主要有平均難度指標、區分度指標、信度指標等.

2.1 平均難度指標

數據庫技術課程組卷平均難度指標指參加考試的全部學生在題目上的失分率,以符號A描述. 平均難度指標見公式(1).

2.2 區分度指標

2.3 信度指標

該指標描述的是可信度,為考試結果是否可靠的量化指標,如公式(3)所示.

3 人工智能自動組卷

3.1 自動化組卷數學模型

通過預先設定數據庫技術專業課程的組卷約束和質量目標,包括組卷題型、知識點、難度等指標和要求,并以此為屬性按要求展開組卷. 組卷期望值及約束一般有試卷題型、試卷難度水平、試卷知識點要求及排列等. 本文的數據庫技術試題庫的一份試卷的題目數量為m,每一試題為n個指標或屬性,由此構建或組成的試卷T為m×n矩陣,如公式(4)所示.

其中,根據組卷要求,T矩陣必須滿足的約束條件主要有：

(1)分數約束,見公式(5)所示.該約束一般由使用者確定.

(2)題型約束,見公式(6)所示.

Fi為第i題型分數,t為題型號,P為選擇、填空、判斷、操作題,該約束的題目類型及各題分數比例由使用者確定.

(3)總時間約束,見公式(7)所示.

(4)題目難度分布約束,見公式(8)所示.

式中,Di為難度約束. 假設αi1在第i個難度等級范圍內,則A1i即為1,其他情況即為0.

(5)知識點分數約束,見公式(9)所示.

M1和M2為掌握題型和理解題型等的集合,相對的分數范圍分別為[M1,N1]和[M2,N2],其公式為式(9)所示.

(6)知識點覆蓋約束,見公式(10)所示.

其中,

通過加權與乘積,求和后獲得組卷的目標函數,如公式(12)所示.

3.2 改進遺傳算法自動組卷

以遺傳算法和相關技術為依據,按照上述的組卷歸一化函數為目標,重新設計及改進遺傳算法的編碼形式、適應度函數、遺傳算子及組卷策略.

3.2.1 改進編碼形式

傳統的遺傳算法的編碼形式使用的是二進制,但編碼形式為二進制對線性函數的優化有某些誤差. 因此,本文進行了修正,編碼方式采取了段式設計,其中,試卷和染色體對應和映射,題目即和基因對應和映射,同類型的題目,其所處的分段區間相同.

圖1顯示的是數據庫技術專業課程按分段實數編碼進行求解的人工智能方法,這樣的好處是縮減解碼程序,提升算法效率.

圖1 數據庫技術專業課程題目分段編碼方法

3.2.2 適應度函數設計

當試卷的差值達到最小值,甚至為零時即為最優解,這時,與組卷預期完全一致. 組卷的預期要求函數定義成.為組卷難度分布預期,它的值小,則更接近難度分布預期,定義如公式(13)所示.

T描述的是難度值,Di描述的是難度i相差的值,Xi描述難度i占的分值,Yi描述難度i實占的分值,Zi描述難度i允許分值誤差. 同理,F2求認知分值分布的組卷預期,F3求單元分值分布的組卷預期. 傳統的遺傳算法的收斂性有所缺陷,原因是傳統遺傳算法對適應度函數的取值問題,其范圍一般沒有太多限定,通常是正數即可. 上述的改進遺傳算法引用指數比來構造出適應度函數,如公式(14)所示.

圖6是不同粘結劑LFP電極的CV和EIS曲線。從圖6a中可以看出，相比于PVDF和PVA-g-PAA，交聯的PVA-g-PAA-c-5% PER的氧化還原電位差更小，對應的電流更大，說明對應電極的極化更小，可逆性更好，有更好的電化學動力學性能。圖6b為使用不同粘結劑的LFP電極在0.2 C倍率下循環100圈后的EIS圖，可以看出，PVA-g-PAA-c-5%PER的電阻要比PVDF和PVA-g-PAA的電阻要小很多。說明交聯后的 PVA-g-PAA-c-5%PER擁有更低的鋰離子電阻，可以減少LFP電極的極化，提供一個良好的動力學過程。

f描述的是目標函數,α通常設定為-0.03,f值增大,則F值減少,F>0; 對組卷函數優化后,其分值分布與期望值差距縮小,f值隨之縮小,F值相應增大;一旦組卷與期望值一致,f值等于0,F值為最大值,Fmax=e3,求得其值約為20. 因為指數比轉換法的適應度函數滿足目標期望,體現組卷質量好壞,因此能很好的應用在遺傳算法組卷中.

3.2.3 改進遺傳算子

對于遺傳算法來說,選擇算子是遺傳基因決定因素,適應度高的組卷元素將優先被選擇,相反,較低的元素將逐漸被淘汰. 傳統遺傳算法的選擇算子通常是輪盤選擇,其特點是取決于概率,統計學上有誤差,不一定都能收斂.

本文的改進錦標賽選擇算子操作方法是每次均選取適應度函數大的因子進化,使得形成種群的適應度值為最大,重復n次后,最終得到最優的種群. 改進均勻交叉算子在新種群里選擇2個配對的題目,以題目一為起始,依據交叉概率對每個題目進行交換與比較,若比較值為大,即放棄交換,否則,先判斷是否為重復題目,若發現重復,即取消,否即交叉交換. 改進均勻變異算子以初始化概率起始變異,將值來比對,若比較值為大,即放棄,若為否,檢查有沒有重復,若有,重復步驟再比對. 終止條件為無重復,為真即進行變異操作.

3.3 蟻群算法自動組卷

3.3.1 試卷編碼方式

數據庫技術課程試題庫的題目一般由事先確定,同一題型其屬性相同,可以使用分塊式二進制表示,每一題型均表示一塊. 假如數據庫技術課程的試題庫有m種題型,每一題型有n個題目,這樣每個螞蟻K的編碼長度就是m×n,數據庫技術課程組卷編碼方式與遺傳算法編碼大體相同,具體見圖1數據庫技術專業課程題目分段編碼方法.

3.3.2 適應度函數設計

評價組卷群體的個體是否合適用的是適應度函數,關于本文,指的就是組卷的質量. 數據庫技術課程的組卷是對試卷要求和期望的實現,即多目標期望值的優化和求解. 若求得的多目標解為最小值,即為最佳值,如公式(15).

3.3.3 信息素更新規則與狀態轉移概率

按照數據庫技術課程組卷的要求和期望,在組卷題庫里抽取題目,初始化信息素濃度及揮發值,求得螞蟻爬行角度. 將螞蟻選好的個體(題目)將先存到內存,直到求解出所有的解,后與約束條件進行比較. 假如與約束條件不符,即需對解執行修正動作,至符合約束條件為止. 在實際操作中,往往先對區域最優解進行搜索,從而得到區域最優解為此輪目標值. 如果這一輪最優解(最優試卷)比全局的解更優,即取代全局最優,同時更新信息素,直到全局最優或結束條件到達. 在開始時,設定的初始化濃度相同,搜索過程中,按照信息素濃度及揮發值作為移動方向,其值大,按該題目移動,同樣,移動方向的機會多,濃度增高.

螞蟻在移動時,轉移概率見公式(17).

3.3.4 蟻群算法的自動組卷過程

蟻群算法自動組卷方法是先設定并檢查自動組卷的約束條件和期望. 初始化蟻群算法及蟻群路徑,設定題目路徑的初始值(信息素)為0,開始時間t為0,從數據庫技術試題庫中搜索題目并放進相應的禁忌列表,設定該螞蟻在表中Index等于1,執行i++操作(循環數的遞增),按照轉態轉移概率公式,決定螞蟻下一爬行的路徑,則搜索下一題目的編號,螞蟻決定了路徑,即選擇了新題目后,需將該題目編碼排進禁忌表,并對該表的索引號進行修正. 蟻群算法自動組卷步驟示意圖見圖2.

圖2 蟻群算法自動組卷流程

3.4 人工智能算法組卷非法個體的修正

人工智能算法自動組卷過程中,可能會有不符合期望值的試卷,這就要求對算法產生的不符合個體做必要的修正. 即在蟻群對數據庫技術試題庫求解完畢及路徑上信息素執行更新前,需把與約束條件相勃的個體(試題)優化及修正,具體做法見以圖3給出的步驟.

圖3 對算法產生的非法個體的修正

以上步驟的修正完成判斷依據為： 一是達到了最大迭代次數,二是已得到最優解,符合原來要求和預期值. 這兩個條件的達成則自動組卷完成,生出最終試卷.

4 人工智能組卷實驗結果分析

4.1 遺傳算法實驗結果

與遺傳算法為基礎的人工智能組卷方法,關鍵指標主要有種群規模、交叉概率及變異概率,這些指標決定了組卷質量,應依據組卷實驗來設置符合要求的組卷指標. 因此,本文通過大量的實驗數據,分析和選擇符合本數據庫技術試題庫組卷參數及指標.

4.1.1 實驗數據說明

本文以數據庫技術課程的自動化組卷為案例,根據前述的組卷模型、指標及期望值展開試驗驗證. 設定總分為一百,組卷要求及約束如表1所列.

在總分100分不變情況下,已知各種題型的分值、分值分布,可得到各個題目的數量.

4.1.2 實驗結果分析

以文獻為參考,對組卷使用的各項參數進行設定,種群規模、交叉概率和變異概率分別設定為40、0.6和0.01.

以種群規模為例來試驗,分別設置40、80、160、280和400,并以此對照組裝試卷,每組數例分別實施3次試卷組裝,對各數例的組裝時間及適應度函數均值實施研究,見圖4的折線分析圖.

根據圖4結果,分析發現當種群規模為400時,組卷適應度函數值最高,而組卷時間相差不顯著.

表1 數據庫技術課程組卷約束條件表

圖4 不同種群規模組卷試驗

以交叉概率為例來試驗,分別設置0.2、0.4、0.6和0.8,以此來對照組裝試卷,每組數例分別實施3次試卷組裝,對各數例的組裝時間及適應度函數均值實施研究,見圖5折線分析圖.

根據圖5結果,分析發現交叉概率值為0.6時,組卷適應度函數值最高,而組卷時間相差不顯著.

關于變異概率的設定,其值分別設定為0.004、0.016、0.1、0.16、0.32和0.64,并進行對照組卷試驗,實施3次組卷對各參數的組卷時間和最大適應度值進行研究,見圖6折線分析圖.

圖5 不同交叉概率組卷試驗

圖6 不同變異概率組卷試驗

根據圖6結果,分析發現變異概率值為0.1時,組卷適應度函數值最高,而組卷時間相差不顯著. 按照圖4至圖6的實驗結論,可以得到最佳參數設置的種群規模、交叉概率和變異概率的值為別為400、0.6和0.1.該參數比例,本文的數據庫技術組卷達到最優組合,組卷的平均時間可以低至10 s完成一份合符期望的卷子.

4.2 蟻群算法實驗結果

4.2.1 實驗數據說明

同樣是對數據庫技術課程實施組卷,數據庫技術試題庫的題型同樣有選擇題、填空題、判斷題及操作題5類題目. 組卷題型等約束條件的設定與遺傳算法的設定一致,可以參考表1數據庫技術課程組卷約束條件表所示.

4.2.2 實驗結果分析

參照相關文獻和經驗,初始化蟻群算法的組卷參數,設置螞蟻數為10,,迭代最大值為100.為了更好對比各種算法的優劣,將螞蟻算法分別與隨機變量算法、回溯試探法、遺傳算法進行對比研究.

4.3 組卷效率比較

在實際應用中,組卷方法有很多,本文將遺傳算法、蟻群算法與隨機變量法、回溯試探法的組卷效率進行對比研究,如圖7所示.

圖7 比較4種算法組卷效率

通過分析和對比,發現隨機變量法的組卷效率要遠遠低于其它3種算法,耗費的時間也遠遠高于其它算法. 其次較低的是回溯試探法,耗費的時間相對也比較長. 究其原因,可能是由于該2種算法均是隨機搜索算法,沒有人工智能加入,一旦題目數量很大時,存儲的內存占用較大,計算起來相當復雜. 從圖中分析可知,遺傳算法組裝試卷所耗費的時間比隨機變量法和回溯試探法要短,算法效率等到了提升. 而蟻群算法在所有算法里面,效率最高,組卷時間也最短,其為最智能的搜索算法,全局搜索能力更強,并且可以并行,從而縮短搜尋時間,在一定程度上解決了遺傳算法的收斂慢問題,并可以避免局部最優——即“早熟”問題,因此,組卷效率最高.

4.4 組卷成功率比較

四種算法組卷成功率對比如圖8所示.

圖8 比較4種算法成功率

分析圖8可以發現,人工智能算法的成功率最高,平均達到98%以上(含蟻群算法100%,遺傳算法96%),而非人工智能的算法成功率較低,隨機變量法62%,回溯試探法84%. 通過對比研究,結論是蟻群算法成功率及效率均為最高,收斂速度快,質量高,滿足組卷要求和期望值.

5 結束語

數據庫技術試題庫組卷的本質是對多約束、多目標的問題求最優解. 以數據庫技術課程的自動組卷為例,文中使用了隨機變量法、回溯試探法組裝試卷,也用了遺傳算法、蟻群算法等人工智能算法用于自動組裝試卷. 遺傳算法和蟻群算法由于引入了人工智能,應用了更好的系統框架,高效的實現了求解功能. 本文對數據庫技術課程的試卷組裝重新編碼、修正各種函數及應用,并且通過建立求解目標約束矩陣來構建組卷的數學模型,達到線性化求解組卷的約束條件及期望值. 對遺傳算法,修正遺傳算子及組裝試卷方法; 對蟻群算法,完善信息素設計、狀態轉移概率、非法個體修正等. 本文通過對數據庫技術課程試卷組裝試驗,大量數據表明,選擇合適試卷組裝參數,多種人工智能的試卷組裝時間花費及可靠性均比隨機變量法、回溯試探法有很大的改善,縮短了組卷時間,提高了成功率,很好的適應組卷需求和期望,具備適應性及實用性,在計算機輔助考試和遠程網絡學習中應用廣泛.

1石靜,劉欣亮. 在線考試系統隨機抽題策略的討論與實現.電腦編程技巧與維護,2015,(18)： 23-25. [doi： 10.3969/j.issn.1006-4052.2015.18.014]

2李阿紅. 基于遺傳算法的自動組卷系統設計與實現[碩士學位論文]. 楊凌： 西北農林科技大學,2016.

3Song HF,Yang WW. The research of auto-composing test paper technology based on genetic algorithm. Applied Mechanics and Materials,2014,519-520： 1188-1192. [doi：10.4028/www.scientific.net/AMM.519-520]

4馮秀梅. 基于遺傳算法的智能組卷考試系統研究與實現[碩士學位論文]. 濟南： 山東師范大學,2016.

5江軍強. 基于遺傳算法的信息技術類課程自動組卷應用研究. 大慶師范學院學報,2013,33(3)： 152-156.

6傅思苑,貝玉葉,刁清洪. 深圳市育新學校矯正未成年“問題學生”狀況調查. 預防青少年犯罪研究,2012,(4)： 14-20.