計(jì)算機(jī)組卷算法研究

郝運(yùn)來(lái)

隨著教育改革的不斷深入，設(shè)計(jì)一個(gè)相對(duì)科學(xué)的考試系統(tǒng)對(duì)促進(jìn)人才質(zhì)量具有重要意義。本文介紹了當(dāng)前較為流行的幾種組卷算法，對(duì)其進(jìn)行了優(yōu)缺點(diǎn)分析，并對(duì)未來(lái)組卷算法的發(fā)展進(jìn)行了預(yù)測(cè)。

【關(guān)鍵詞】考試系統(tǒng) 自動(dòng)組卷 組卷算法

1 引言

當(dāng)前教學(xué)改革正在如火如荼展開，而考試是教學(xué)過(guò)程中的重要環(huán)節(jié)，是對(duì)師生“教”與“學(xué)”成果的檢驗(yàn)，將計(jì)算機(jī)及互聯(lián)網(wǎng)等現(xiàn)代科技應(yīng)用到考試中去，可以克服傳統(tǒng)考試耗費(fèi)人力物力、效率低下的缺點(diǎn)，使出卷、考試、評(píng)閱、成績(jī)統(tǒng)計(jì)與分析更加科學(xué)、客觀。而組卷算法是其最為關(guān)鍵的部分，研究組卷算法并將其應(yīng)用到考試系統(tǒng)中具有重要意義。

基于試題庫(kù)的考試系統(tǒng)中，組卷問(wèn)題是一個(gè)多目標(biāo)、多約束條件組合優(yōu)化問(wèn)題，傳統(tǒng)組卷方法包括基于隨機(jī)算法、回溯算法的組卷算法。作為NP問(wèn)題，當(dāng)前研究解決此問(wèn)題的熱門智能組卷算法主要基于遺傳算法、粒子群算法和蟻群算法。本文針對(duì)這幾種算法進(jìn)行了詳細(xì)的分析，為組卷算法的進(jìn)一步研究做好鋪墊。

2 基于隨機(jī)算法的組卷方法

該組卷方法的核心思想是利用隨機(jī)函數(shù)rand（n），產(chǎn)生服從均勻分布的從1到n的隨機(jī)數(shù)，將其作為要抽取的試題在試題庫(kù)中的編號(hào)，之后按照試題類型、試題難度、知識(shí)點(diǎn)、區(qū)分度等約束條件進(jìn)行判斷，選擇符合要求的記錄錄入試卷，重復(fù)該過(guò)程直到題目數(shù)量滿足要求或無(wú)法從試題庫(kù)中抽取滿足控制指標(biāo)的試題，最后輸出試卷。

該算法結(jié)構(gòu)簡(jiǎn)單、易于理解、實(shí)現(xiàn)容易；但是隨著試題數(shù)量的增加，選擇試題過(guò)程中沒(méi)有目標(biāo)，導(dǎo)致組卷成功率低，組卷耗時(shí)，不確定性和用戶滿意度差。

3 基于回溯算法的組卷方法

回溯組卷算法是在隨機(jī)組卷算法的基礎(chǔ)上，利用深度優(yōu)先搜索算法改進(jìn)而來(lái)。組卷過(guò)程中，從試題庫(kù)中隨機(jī)抽取一道試題，如果試題滿足組卷約束，則將其按照先后順序放入棧中，并標(biāo)記成功狀態(tài)；否則，返回到上一個(gè)成功狀態(tài)，并按照新的狀態(tài)繼續(xù)搜索。

該算法繼承了隨機(jī)組卷算法簡(jiǎn)單和易于實(shí)現(xiàn)等優(yōu)點(diǎn)，避免了其方法重復(fù)搜索試題的缺點(diǎn)，理論上可以搜索所有試題組合，形成最優(yōu)試卷集，當(dāng)試題庫(kù)較小時(shí)，成功率較高，試卷質(zhì)量較好，但試題庫(kù)較大時(shí)，時(shí)空復(fù)雜度較高，成功概率低。

4 基于遺傳算法的組卷方法

遺傳算法是基于自然界選擇原理和自然遺傳機(jī)制的搜索算法。其原理是模擬自然界中的生命進(jìn)化機(jī)制，在人工系統(tǒng)中實(shí)現(xiàn)特定目標(biāo)的優(yōu)化。該算法的組卷方法對(duì)試題庫(kù)中的試題采用十進(jìn)制或二進(jìn)制編碼，之后隨機(jī)生成規(guī)模適當(dāng)?shù)某跏挤N群；然后運(yùn)用適應(yīng)度函數(shù)對(duì)初始種群進(jìn)行優(yōu)劣評(píng)估，并進(jìn)行選擇。接著對(duì)群體進(jìn)行交叉和變異等遺傳操作，生成新一代的試題群體。重復(fù)上述過(guò)程，直到算法滿足終止條件，輸出試卷。

遺傳算法采用并行處理，可以同時(shí)搜索試題庫(kù)中的多個(gè)區(qū)域，不易陷入局部最優(yōu)解當(dāng)中而過(guò)早收斂，效率上優(yōu)于搜索法，但容易產(chǎn)生早熟現(xiàn)象，因此需要對(duì)其進(jìn)行改進(jìn)，當(dāng)前改進(jìn)遺傳算法的組卷算法較多。

5 基于粒子群優(yōu)化算法

粒子群算法模擬鳥集群飛行覓食的行為，鳥之間通過(guò)集體的協(xié)作使群體達(dá)到最優(yōu)目的，是一種基于Swarm Intelligence的優(yōu)化方法。首先從試題庫(kù)隨機(jī)抽取適量的試題，構(gòu)成初始粒子群，然后通過(guò)由組卷目標(biāo)確定的適應(yīng)度函數(shù)計(jì)算粒子本身最優(yōu)值和全局最優(yōu)值，粒子根據(jù)速度和位置更新公式改變速度信息和位置信息，經(jīng)有限次迭代后找到最優(yōu)解，輸出試卷。

該算法采用并行搜索，搜索速度快、效率高，受初始種群和迭代次數(shù)影響有可能陷入局部最優(yōu)，對(duì)于處理組卷這類多目標(biāo)問(wèn)題效果不理想，需要進(jìn)行改進(jìn)。

6 蟻群算法

蟻群算法是群智能理論研究領(lǐng)域的一種主要算法，通過(guò)模擬自然界螞蟻搜索路徑的行為搜索最優(yōu)解，成功解決了旅行商、圖著色等經(jīng)典組合優(yōu)化問(wèn)題。首先初始化試題信息素濃度，之后設(shè)置適當(dāng)數(shù)量的螞蟻在試題庫(kù)中隨機(jī)分布，之后用根據(jù)組卷目標(biāo)確定的轉(zhuǎn)移概率函數(shù)使螞蟻狀態(tài)進(jìn)行轉(zhuǎn)移，并更新信息素濃度，然后再次用螞蟻重復(fù)上述過(guò)程，直至滿足終止條件或達(dá)到迭代次數(shù)。

蟻群算法本身在求解復(fù)雜優(yōu)化問(wèn)題特別是離散優(yōu)化問(wèn)題具有優(yōu)勢(shì)，可以與多種啟發(fā)式算法結(jié)合來(lái)改善算法性能，缺點(diǎn)是計(jì)算量大，所需時(shí)間長(zhǎng)；參數(shù)設(shè)置不當(dāng)時(shí)，容易出現(xiàn)停滯現(xiàn)象，收斂速度變慢、陷于局部最優(yōu)等缺陷。

隨機(jī)組卷算法和回溯算法由于其簡(jiǎn)單實(shí)用的優(yōu)點(diǎn)，這兩類算在實(shí)際工程應(yīng)用較多，尤其在一些要求較低的系統(tǒng)中較多使用。遺傳算法提出時(shí)間較早，基于其進(jìn)行改進(jìn)的算法較多，是當(dāng)前智能算法應(yīng)用在組卷系統(tǒng)中研究最為深入的算法之一，且已經(jīng)在較為復(fù)雜度組卷系統(tǒng)中使用。其他兩種現(xiàn)代智能算法，由于提出時(shí)間較晚，對(duì)其研究還不夠深入，仍有巨大發(fā)展?jié)摿Α?/p>

7 結(jié)語(yǔ)

本文從產(chǎn)生歷史、算法流程、優(yōu)缺點(diǎn)等方面介紹了組卷算法的應(yīng)用，在人工智能產(chǎn)生巨大影響的背景下，考試系統(tǒng)正朝著規(guī)模化、智能化和并行化的方向發(fā)展，智能組卷算法也將對(duì)組卷產(chǎn)生巨大影響。綜合比較上述各種算法優(yōu)缺點(diǎn)，將多種算法組合，發(fā)揮不同算法的最大優(yōu)勢(shì)，互相取長(zhǎng)補(bǔ)短，將會(huì)使組卷算法在一個(gè)較短的時(shí)間內(nèi)對(duì)考試系統(tǒng)產(chǎn)生巨大影響，為更好的實(shí)現(xiàn)科學(xué)組卷打下很好基礎(chǔ)。

參考文獻(xiàn)

[1]高歡歡.分類分段回溯試探算法在計(jì)算機(jī)基礎(chǔ)在線考試系統(tǒng)中的應(yīng)用[J].軟件導(dǎo)刊，2016，15（05）：157-159.

[2]胡泊，劉欣.基于改進(jìn)隨機(jī)選取法的自動(dòng)組卷方法研究[J].海軍工程大學(xué)學(xué)報(bào)（綜合版），2013，10（03）：78-81.

[3]裴勝玉，周永權(quán).用于約束多目標(biāo)優(yōu)化問(wèn)題的混合粒子群算法[J].計(jì)算機(jī)工程與應(yīng)用，2011，47（15）：49-52+111.

[4]唐世文.基于蟻群算法的智能組卷算法研究[J].計(jì)算機(jī)時(shí)代，2011（10）：37-39.

[5]http：//doc.mbalib.com/view/737a90590a3abc56bb1d9a281e44adeb.

作者單位

陜西省西安市空軍工程大學(xué)信息與導(dǎo)航學(xué)院 陜西省西安市 710000