佟婷婷 長沙理工大學(xué) 湖南交通職業(yè)技術(shù)學(xué)院

隨著計(jì)算機(jī)相關(guān)技術(shù)的發(fā)展以及教育教學(xué)水平的不斷提高，考試類型和考試標(biāo)準(zhǔn)也隨之發(fā)生改變，采用傳統(tǒng)的考試已經(jīng)不能滿足當(dāng)前教育教學(xué)的需要，因此在線考試系統(tǒng)在很多領(lǐng)域逐漸取代了紙質(zhì)考試，成為水平測試和技能考核的基本工具。科學(xué)有效的組卷算法是在線考試系統(tǒng)的核心，目前主要有人工組卷和自動組卷兩類方法。顯然，人工組卷與傳統(tǒng)紙質(zhì)制卷并無本質(zhì)的區(qū)別，要充分發(fā)揮在線考試系統(tǒng)的功效，還需要依賴自動組卷算法。根據(jù)自動組卷算法的特點(diǎn)，分為傳統(tǒng)組卷方法和智能組卷算法兩種。

1 傳統(tǒng)組卷方法

傳統(tǒng)的自動組卷方法主要包括隨機(jī)算法和回溯算法兩種。

1.1 隨機(jī)組卷算法

隨機(jī)組卷算法是根據(jù)預(yù)設(shè)參數(shù)，隨機(jī)從題庫中抽取符合要求的試題，并不斷重復(fù)這一過程達(dá)到組卷的目的。因?yàn)殡S機(jī)組卷算法的穩(wěn)定性不高，因此為了防止組卷失敗，一般都會設(shè)置盡可能少的條件，所以，這種算法只適用于一般的簡單組卷系統(tǒng)。

1.2 回溯組卷算法

回溯算法可以認(rèn)為是隨機(jī)算法的一種改進(jìn)，與隨機(jī)算法不同的是，回溯算法設(shè)置一個(gè)條件，當(dāng)隨機(jī)選擇的題目不滿足條件時(shí)，進(jìn)行“回溯”返回并嘗試選擇別的題目。相比隨機(jī)組卷方法，回溯算法在一定程度上提高了組卷穩(wěn)定性，但因?yàn)樵跇O端的情況下也有可能歷遍所有題目，所以其效率不如隨機(jī)算法，基于回溯算法的組卷過程一般適用于題量和題型都較少的情況。

2 智能組卷方法

智能組卷是利用智能算法進(jìn)行組卷的方法，應(yīng)用于組卷的智能算法主要有遺傳算法、粒子群算法、蟻群算法和人工魚群算法等幾種。由于智能算法的求解過程不依賴于梯度信息，因此智能算法適用于于傳統(tǒng)組卷算法不能解決的大規(guī)模題庫的組卷問題。

2.1 遺傳算法

遺傳算法是計(jì)算數(shù)學(xué)中應(yīng)用最廣泛的方法，該方法通過模擬生物進(jìn)化過程中的“優(yōu)勝劣汰，適者生存”法則，經(jīng)過多個(gè)種群的不斷迭代，即復(fù)制、交叉和變異等行為，最終得到最優(yōu)解。作為一個(gè)多目標(biāo)優(yōu)化問題，自動組卷問題適合采用遺傳算法來進(jìn)行。相對來說，遺傳算法計(jì)算較為簡單、魯棒性也較強(qiáng)，但容易陷入“早熟”現(xiàn)象，其參數(shù)的確定也不容易，通過改進(jìn)算法可以一定程度上解決這些問題。

2.2 蟻群算法

蟻群算法是一種針對離散優(yōu)化問題的元啟發(fā)式算法，其本質(zhì)是一種全局優(yōu)化算法。蟻群算法通過模擬螞蟻群體的覓食行為來尋找最優(yōu)解，這種算法具有分布計(jì)算、信息正反饋和啟發(fā)式搜索的特征。蟻群算法一般都是為了得到一個(gè)最優(yōu)解，但因?yàn)榻M卷問題是一個(gè)多目標(biāo)優(yōu)化問題，所以在實(shí)際應(yīng)用中，需要對蟻群算法進(jìn)行改進(jìn)。

2.3 粒子群算法

粒子群算法是模擬鳥群覓食行為，通過鳥群的集體協(xié)作和競爭，而完成最優(yōu)目標(biāo)的一種智能算法。與其它智能算法一樣，粒子群算法首先隨機(jī)生成初始種群作為可行解，在每次迭代中，每個(gè)粒子根據(jù)自身所尋找的最優(yōu)解和整個(gè)種群的最優(yōu)解兩個(gè)極值來更新自己，通過不斷迭代達(dá)到最優(yōu)解。粒子群算法容易實(shí)現(xiàn)、收斂速度快，而且不需要過多的參數(shù)調(diào)整。在應(yīng)用于自動組卷中，粒子群算法往往比遺傳算法更快完成組卷，但需要解決精度低的問題。

2.4 人工魚群算法

人工魚群算法是一種利用魚群的覓食行為、群聚行為、追尾行為和隨機(jī)行為等特點(diǎn)，通過構(gòu)造人工人工魚來實(shí)現(xiàn)尋優(yōu)的過程。作為一種新型的仿生學(xué)算法，人工魚群算法具有收斂速度快、穩(wěn)定性好等特點(diǎn)。自提出以來，人工魚群算法廣泛用于電力系統(tǒng)規(guī)劃和多級階梯物流中轉(zhuǎn)運(yùn)輸系統(tǒng)優(yōu)化等領(lǐng)域。將人工魚群算法引入自動組卷問題中，能有效解決編碼太長、適應(yīng)度函數(shù)計(jì)算復(fù)雜等問題。此外，人工魚群算法與其它方法，例如遺傳算法相結(jié)合，能進(jìn)一步提高組卷效率。

3 總結(jié)

除了以上算法，專家系統(tǒng)法和項(xiàng)目反應(yīng)理論等方法也被應(yīng)用于自動組卷中。專家系統(tǒng)法可以利用用戶參與試卷指標(biāo)設(shè)定增強(qiáng)組卷的可控性和靈活性，項(xiàng)目反應(yīng)理論與其它的算法不同，它主要側(cè)重于對應(yīng)試者實(shí)際能力水平的衡量。各種組卷算法均有其優(yōu)缺點(diǎn)，在實(shí)際的應(yīng)用中，應(yīng)根據(jù)需要采取適應(yīng)的自動組卷方法。為了提高組卷效率，往往要結(jié)合多種方法來完成組卷過程，例如粒子群和遺傳算法相結(jié)合，人工魚群與遺傳算法相結(jié)合等等。

[1]戴亞非，李曉明.計(jì)算機(jī)自動組卷算法分析[J].小型微型計(jì)算機(jī)系統(tǒng)2012,16(9):50-55

[2]魏平，熊偉潔.用遺傳算法解組卷問題的設(shè)計(jì)與實(shí)現(xiàn)[J].微電子學(xué)與計(jì)算機(jī),2012(4):48-50

[3]肖豆.智能組卷系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D].電子科技大學(xué)，2017

[4]喬東平，裴杰，肖艷秋，周坤.蟻群算法及其應(yīng)用綜述[J].軟件導(dǎo)刊，2017,12(16)

[5]陳新.基于人工魚群算法的柔性作業(yè)車間調(diào)度研究[D].大連理工大學(xué)，2015

[6]李躍松，樊金生，張巧迪.用改進(jìn)的人工魚群算法求解TSP問題[J]. 石家莊鐵道大學(xué)學(xué)報(bào)自然科學(xué)版，2011,24(2)

[7]單美靜，劉琴.基于項(xiàng)目反應(yīng)理論的組卷算法研究[J].軟件工程,2017(12)