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

彭康華, 黃裕鋒, 姚江梅

(廣東工程職業(yè)技術(shù)學(xué)院 信息工程學(xué)院,廣州 510520)

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

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

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

2 構(gòu)建組卷質(zhì)量指標(biāo)體系

數(shù)據(jù)庫技術(shù)專業(yè)課程組卷關(guān)鍵是按試卷的要求及期望來形成試卷,指標(biāo)體系主要有平均難度指標(biāo)、區(qū)分度指標(biāo)、信度指標(biāo)等.

2.1 平均難度指標(biāo)

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

2.2 區(qū)分度指標(biāo)

2.3 信度指標(biāo)

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

3 人工智能自動組卷

3.1 自動化組卷數(shù)學(xué)模型

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

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

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

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

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

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

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

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

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

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

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

其中,

通過加權(quán)與乘積,求和后獲得組卷的目標(biāo)函數(shù),如公式(12)所示.

3.2 改進遺傳算法自動組卷

以遺傳算法和相關(guān)技術(shù)為依據(jù),按照上述的組卷歸一化函數(shù)為目標(biāo),重新設(shè)計及改進遺傳算法的編碼形式、適應(yīng)度函數(shù)、遺傳算子及組卷策略.

3.2.1 改進編碼形式

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

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

圖1 數(shù)據(jù)庫技術(shù)專業(yè)課程題目分段編碼方法

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

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

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

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

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

3.2.3 改進遺傳算子

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

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

3.3 蟻群算法自動組卷

3.3.1 試卷編碼方式

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

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

評價組卷群體的個體是否合適用的是適應(yīng)度函數(shù),關(guān)于本文,指的就是組卷的質(zhì)量. 數(shù)據(jù)庫技術(shù)課程的組卷是對試卷要求和期望的實現(xiàn),即多目標(biāo)期望值的優(yōu)化和求解. 若求得的多目標(biāo)解為最小值,即為最佳值,如公式(15).

3.3.3 信息素更新規(guī)則與狀態(tài)轉(zhuǎn)移概率

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

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

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

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

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

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

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

圖3 對算法產(chǎn)生的非法個體的修正

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

4 人工智能組卷實驗結(jié)果分析

4.1 遺傳算法實驗結(jié)果

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

4.1.1 實驗數(shù)據(jù)說明

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

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

4.1.2 實驗結(jié)果分析

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

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

根據(jù)圖4結(jié)果,分析發(fā)現(xiàn)當(dāng)種群規(guī)模為400時,組卷適應(yīng)度函數(shù)值最高,而組卷時間相差不顯著.

表1 數(shù)據(jù)庫技術(shù)課程組卷約束條件表

圖4 不同種群規(guī)模組卷試驗

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

根據(jù)圖5結(jié)果,分析發(fā)現(xiàn)交叉概率值為0.6時,組卷適應(yīng)度函數(shù)值最高,而組卷時間相差不顯著.

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

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

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

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

4.2 蟻群算法實驗結(jié)果

4.2.1 實驗數(shù)據(jù)說明

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

4.2.2 實驗結(jié)果分析

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

4.3 組卷效率比較

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

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

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

4.4 組卷成功率比較

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

圖8 比較4種算法成功率

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

5 結(jié)束語

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

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

2李阿紅. 基于遺傳算法的自動組卷系統(tǒng)設(shè)計與實現(xiàn)[碩士學(xué)位論文]. 楊凌： 西北農(nóng)林科技大學(xué),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馮秀梅. 基于遺傳算法的智能組卷考試系統(tǒng)研究與實現(xiàn)[碩士學(xué)位論文]. 濟南： 山東師范大學(xué),2016.

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

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