基于LT-backfilling算法的智能題庫(kù)系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)*

張舒虹，孫宏健，夏 鋒，孔祥杰

（大連理工大學(xué) 軟件學(xué)院，遼寧 大連 116620）

一、引言

本系統(tǒng)是運(yùn)用可視化程序設(shè)計(jì)和數(shù)據(jù)庫(kù)進(jìn)行開(kāi)發(fā)的一個(gè)基于Web的智能題庫(kù)系統(tǒng)，包括系統(tǒng)管理，題庫(kù)管理，組卷管理和試卷管理等功能。本系統(tǒng)在教學(xué)實(shí)踐中的優(yōu)越性體現(xiàn)在兩個(gè)方面，一是教學(xué)管理上的，試題庫(kù)具有高效、經(jīng)濟(jì)、靈活和保密的特點(diǎn)；二是教學(xué)測(cè)試上的，由題庫(kù)生成的試卷具有質(zhì)量高、可預(yù)控等特點(diǎn)。

二、系統(tǒng)設(shè)計(jì)

本智能題庫(kù)系統(tǒng)采用模塊化的設(shè)計(jì)方法，根據(jù)系統(tǒng)功能來(lái)進(jìn)行模塊劃分，保證模塊內(nèi)聚性高、模塊之間耦合性低。本系統(tǒng)的用戶(hù)群包括四大類(lèi)，即系統(tǒng)管理員、教師、助教和學(xué)生。本系統(tǒng)將核心業(yè)務(wù)大致劃分為四個(gè)主要模塊，分別是題庫(kù)管理、試卷管理、組卷管理和系統(tǒng)管理。其中，題庫(kù)管理模塊主要滿(mǎn)足了在校教師對(duì)試題庫(kù)中各試題的試題屬性的增加、修改和刪除等管理，以及題庫(kù)中試題的隨時(shí)上傳、適時(shí)更新、及時(shí)刪除和數(shù)量統(tǒng)計(jì)等需求；組卷管理則同時(shí)兼顧了傳統(tǒng)的人工式手動(dòng)組卷和自動(dòng)的智能組卷功能；試卷管理模塊主要是基于對(duì)整套試卷上傳存儲(chǔ)和已考試卷下載預(yù)覽的現(xiàn)實(shí)需求；系統(tǒng)管理模塊主要保證了系統(tǒng)管理員對(duì)整個(gè)智能題庫(kù)系統(tǒng)的用戶(hù)審核、管理和日常的系統(tǒng)維護(hù)工作。其結(jié)構(gòu)如圖1所示，本章接下來(lái)會(huì)分模塊介紹智能題庫(kù)系統(tǒng)的設(shè)計(jì)及功能，以及用戶(hù)的權(quán)限設(shè)置等。

圖1 系統(tǒng)結(jié)構(gòu)圖

1.系統(tǒng)管理

系統(tǒng)管理模塊的功能是管理系統(tǒng)用戶(hù)和進(jìn)行系統(tǒng)維護(hù)，只有管理員有權(quán)使用該模塊。通過(guò)系統(tǒng)管理模塊，系統(tǒng)管理員可以管理系統(tǒng)的所有用戶(hù)，維護(hù)整個(gè)系統(tǒng)的安全性和完整性，提供系統(tǒng)幫助，保證系統(tǒng)正常運(yùn)行[1]。

2.題庫(kù)管理

題庫(kù)管理模塊的功能是管理試題庫(kù)，用戶(hù)需通過(guò)已注冊(cè)的郵箱和密碼進(jìn)行登陸。教師有權(quán)限對(duì)試卷、試題、學(xué)科、題型、章節(jié)和知識(shí)點(diǎn)進(jìn)行管理，助教僅有部分權(quán)限。主要功能如下：

（1）試題管理

試題管理模塊包括添加、刪除、修改試題，查看試題分布和試題詳細(xì)信息，搜索試題，管理已刪除試題等功能?？紤]到試題的保密性，只有教師和助教兩類(lèi)用戶(hù)可以管理試題，并且具有不同的權(quán)限設(shè)置。

（2）試題屬性管理

教師有權(quán)限對(duì)試題屬性，包括學(xué)科、章節(jié)、知識(shí)點(diǎn)、題型等進(jìn)行管理，可以進(jìn)行增加、刪除、瀏覽和修改，同時(shí)也會(huì)對(duì)試題庫(kù)中所屬學(xué)科、章節(jié)、知識(shí)點(diǎn)、題型的試題進(jìn)行統(tǒng)計(jì)和計(jì)算，便于了解當(dāng)前試題庫(kù)中試題的分布情況。在進(jìn)行題型添加時(shí)，可以根據(jù)題型選擇相應(yīng)的試題模板，題型和模板是多對(duì)一的關(guān)系，以增加試題上傳的靈活性。

3.組卷中心

只有教師有權(quán)限使用該模塊，組卷管理模塊包含兩種組卷方式：自動(dòng)組卷和手動(dòng)組卷。組卷系統(tǒng)生成的試卷若是用于期末考試，則需要避免近三年考過(guò)的試題重復(fù)被使用，所以在組卷時(shí)，需要考慮去除出近三年考過(guò)的試題。

手動(dòng)組卷按題型查詢(xún)?cè)囶}，在試題查詢(xún)和瀏覽過(guò)程中，教師可以按照試題的各個(gè)屬性選擇符合要求的試題，添加到試卷中，最后組成一份試卷。在試卷預(yù)覽時(shí)，若發(fā)現(xiàn)組成的試卷存在某些問(wèn)題，可以通過(guò)試卷調(diào)整功能刪除已選試題，并重新添加符合條件的試題或者重排試題順序，調(diào)整層次結(jié)構(gòu)。這種做法效率比較低，而且也不容易控制試卷的總體難度和試卷的知識(shí)點(diǎn)覆蓋范圍。當(dāng)試題庫(kù)中試題數(shù)量較多時(shí)，這種缺陷更明顯。所以，這種方法只適合作為經(jīng)驗(yàn)豐富的教師進(jìn)行人工組卷的輔助工具[1]。

自動(dòng)組卷是一種智能化的組卷方式，可以根據(jù)用戶(hù)設(shè)置的試卷要求自動(dòng)的進(jìn)行組卷。用戶(hù)對(duì)試卷的期望將以參數(shù)的形式通過(guò)系統(tǒng)提供的人機(jī)交互式界面輸入系統(tǒng)并作為組卷的依據(jù)。

4.試卷管理

只有教師有權(quán)限使用該模塊，試卷管理包括兩個(gè)子模塊：試卷上傳和試卷下載。試卷上傳是對(duì)組卷模塊生成的試卷進(jìn)行排版和編輯后，連同試卷答案和試卷信息概覽表上傳到服務(wù)器進(jìn)行存檔。試卷下載是從服務(wù)器上下載曾經(jīng)考過(guò)的試卷。

三、系統(tǒng)關(guān)鍵技術(shù)實(shí)現(xiàn)

本系統(tǒng)的關(guān)鍵性技術(shù)問(wèn)題是教師進(jìn)行自動(dòng)組卷時(shí)采用的智能組卷算法，該模塊研究的主要難題是如何保證自動(dòng)生成的試卷既能滿(mǎn)足用戶(hù)的需要，又能保證其科學(xué)性、隨機(jī)性、客觀性，以及遠(yuǎn)程網(wǎng)絡(luò)交互式環(huán)境下的實(shí)時(shí)性。因此，高效、簡(jiǎn)單通用的智能組卷算法是實(shí)現(xiàn)自動(dòng)組卷的關(guān)鍵技術(shù)和研究重點(diǎn)。

目前常用的智能組卷算法主要有隨機(jī)抽取法、回溯試探法、遺傳算法[2]。遺傳算法可以用于求解智能組卷問(wèn)題[2]，但基本遺傳算法存在容易早收斂[3-4]、進(jìn)化后期搜索效率較低的缺點(diǎn)，故無(wú)法得到真正最優(yōu)解[5]。而隨機(jī)抽取法、回溯試探法算法常因約束條件的局部滿(mǎn)足而導(dǎo)致整體組卷失敗，或選取試題缺乏隨機(jī)性，組卷過(guò)程所需時(shí)間也較長(zhǎng)，無(wú)法滿(mǎn)足實(shí)時(shí)性要求?；诖?，本文提出了一種基于LT-backfilling算法的智能組卷算法。

首先獲取用戶(hù)對(duì)試卷的整體期望，用戶(hù)選擇試卷學(xué)科，輸入試卷總分，選擇試卷章節(jié)并設(shè)置對(duì)應(yīng)分值，選擇題型并設(shè)置對(duì)應(yīng)分值（總分及每道題的分值），以及設(shè)置試卷的難度系數(shù)。在獲得試卷期望后，系統(tǒng)會(huì)自動(dòng)按照相應(yīng)條件進(jìn)行試題篩選。為了使每次選出的題目在滿(mǎn)足條件的同時(shí)保證隨機(jī)性，本文參考了CPU在進(jìn)行系統(tǒng)調(diào)度時(shí)的LT-backfilling算法[6]。

LT-backfilling算法的基本思想是均衡系統(tǒng)的負(fù)載，按照作業(yè)的優(yōu)先級(jí)對(duì)作業(yè)進(jìn)行排序插入到待調(diào)度作業(yè)隊(duì)列中，在節(jié)點(diǎn)中選取滿(mǎn)足作業(yè)所需資源的節(jié)點(diǎn)分配給作業(yè)，在選取節(jié)點(diǎn)的時(shí)候要考慮到該節(jié)點(diǎn)的負(fù)載，如果該節(jié)點(diǎn)的負(fù)載>最大負(fù)載，則此節(jié)點(diǎn)此時(shí)不再分配作業(yè)，如果該節(jié)點(diǎn)的負(fù)載≤最小負(fù)載，則將作業(yè)分配給此節(jié)點(diǎn)，如果此節(jié)點(diǎn)的負(fù)載在最大負(fù)載與最小負(fù)載之間，則根據(jù)節(jié)點(diǎn)上最長(zhǎng)作業(yè)的結(jié)束時(shí)間為依據(jù)，找出作業(yè)結(jié)束時(shí)間最早的節(jié)點(diǎn)，將作業(yè)派發(fā)到該節(jié)點(diǎn)。如果任何節(jié)點(diǎn)的資源都無(wú)法滿(mǎn)足該作業(yè)的需求，則該作業(yè)的優(yōu)先級(jí)將動(dòng)態(tài)地增加，直到該作業(yè)增加到最高優(yōu)先級(jí)。

系統(tǒng)中的每個(gè)作業(yè)在提交時(shí)都由用戶(hù)指定一個(gè)優(yōu)先級(jí)，該優(yōu)先級(jí)影響著讀作業(yè)的執(zhí)行順序，而作業(yè)優(yōu)先級(jí)不是固定的，在作業(yè)等待執(zhí)行期間優(yōu)先級(jí)是動(dòng)態(tài)增加的，直到增加到最高優(yōu)先級(jí)。

將上述理論運(yùn)用到題庫(kù)選題中，把對(duì)題目的選擇當(dāng)作CPU為每個(gè)進(jìn)程的調(diào)度。把每個(gè)作業(yè)當(dāng)作題目，節(jié)點(diǎn)的負(fù)載當(dāng)作題目的分?jǐn)?shù)，作業(yè)的優(yōu)先級(jí)當(dāng)作題目被選擇的優(yōu)先級(jí)。

下面再把優(yōu)先級(jí)的標(biāo)準(zhǔn)具體化：第一個(gè)優(yōu)先級(jí)的影響因素是該類(lèi)型（章節(jié)、題型、知識(shí)點(diǎn)）所占的分?jǐn)?shù)，分?jǐn)?shù)高的優(yōu)先級(jí)高。第二個(gè)優(yōu)先級(jí)的影響因素是它出現(xiàn)的次數(shù)。對(duì)于每一個(gè)出現(xiàn)過(guò)的類(lèi)型，為了防止“饑餓”現(xiàn)象，會(huì)適當(dāng)?shù)慕档退膬?yōu)先級(jí)（即在它原有優(yōu)先級(jí)的基礎(chǔ)上乘一個(gè)小數(shù)0.5～0.7），為在分?jǐn)?shù)上處于劣勢(shì)的類(lèi)型創(chuàng)造提前被選擇的機(jī)會(huì)。第三個(gè)優(yōu)先級(jí)的影響因素是它被選出，而數(shù)據(jù)庫(kù)中不存在此類(lèi)型，這種情況發(fā)生的次數(shù)。這種情況被視作選題失敗，會(huì)對(duì)優(yōu)先級(jí)造成很大影響，此時(shí)需要降低該類(lèi)型的優(yōu)先級(jí)，并由此重新組織對(duì)試卷的選擇。

依據(jù)以上優(yōu)先級(jí)的設(shè)置標(biāo)準(zhǔn)進(jìn)行選題，直到按照要求選出和總分相同的試題，則選題成功?；蛘咴诮?jīng)過(guò)一定次數(shù)的循環(huán)后仍無(wú)法選出滿(mǎn)足條件的試題，則返回用戶(hù)一個(gè)提示，說(shuō)明由于題庫(kù)的限制，根據(jù)用戶(hù)設(shè)置的試卷期望無(wú)法生成符合要求的試卷，并要求用戶(hù)重新設(shè)置試卷期望。該智能組卷算法的程序流程圖，如圖2所示。

圖2 智能組卷算法的程序流程圖

本系統(tǒng)使用的智能組卷算法每次按照特定步驟生成滿(mǎn)足條件的題目列表，然后去數(shù)據(jù)庫(kù)中進(jìn)行選擇，這保證了每次選出的題目都是符合要求并且最小限度地去操作數(shù)據(jù)庫(kù)，在一定程度上節(jié)省了時(shí)間和系統(tǒng)消耗，具有成卷快、客觀性好、難易度可控、能同時(shí)生成多份試卷的特點(diǎn)。

四、系統(tǒng)運(yùn)行情況

在自動(dòng)組卷過(guò)程中，教師用戶(hù)選擇試卷學(xué)科，輸入試卷總分，選擇試卷章節(jié)并設(shè)置對(duì)應(yīng)分值，選擇題型并設(shè)置對(duì)應(yīng)分值（總分及每道題的分值），以及設(shè)置試卷的難度系數(shù)。通過(guò)對(duì)以上試題屬性的設(shè)置，用戶(hù)對(duì)試卷的期望將作為參數(shù)輸入系統(tǒng)并作為生成試卷的依據(jù)。系統(tǒng)運(yùn)行過(guò)程中試卷章節(jié)設(shè)置如圖3所示。

根據(jù)用戶(hù)設(shè)置的試卷期望，系統(tǒng)會(huì)自動(dòng)生成一份符合需求的試卷，并在每題題末注明分值，也可同時(shí)顯示試卷信息概覽以了解試卷的詳細(xì)信息。

五、結(jié)語(yǔ)

圖3 試卷章節(jié)設(shè)置

智能題庫(kù)系統(tǒng)改變了傳統(tǒng)的人工組卷方式，減少了主觀因素對(duì)試卷的影響，有利于實(shí)行教考分離，提高教學(xué)效率。這種新型考試模式的構(gòu)建和投入使用，可以極大提高考試的靈活性和考試的效率、公正性以及考試的可信度，是未來(lái)實(shí)現(xiàn)數(shù)字教學(xué)的基礎(chǔ)。

[1]祝建中,陳麗燕.智能題庫(kù)系統(tǒng)的研究與實(shí)現(xiàn)[D].2005.

[2]王友人,張巖,施玉霞,姚睿.題庫(kù)系統(tǒng)智能成卷理論和組卷方法研究[J].電子科技大學(xué)學(xué)報(bào),2006,35(3):363-366.

[3]Mei Yue,Tao Hu,Baoping Guo,Xuan Guo.The research of parameters of genetic algorithm and comparison with particle swarm optimization and shuffled frog-leaping algorithm [C].Power Electronics and Intelligent Transportation System(PEITS),2009,Volume 1:77-80.

[4]Genglie Zhou,Bo Chen,Chibing Hu,Wuyang Feng.Improved Adaptive Genetic Algorithm Based on Non-ferrous Metals Warehouse Routing Problem Stacker[C].Emerging Computation and Information teChnologies for Education Advances in Intelligent and Soft Computing(ECICE),2012,Volume 146:441-448.

[5]陳曉敏,梁靜,葛宇.基于改進(jìn)遺傳算法的智能組卷研究[J].西南師范大學(xué)學(xué)報(bào)(自然科學(xué)版),2012,37(5):98-101.

[6]張果桃,趙金雁,白中英.基于 LT-backfilling算法的集群作業(yè)調(diào)度系統(tǒng)[J].計(jì)算機(jī)工程,2007,33(21):69-71.