楊勛

摘要：在現(xiàn)代教學(xué)活動(dòng)當(dāng)中，網(wǎng)絡(luò)應(yīng)用也將成為越來越普遍地一個(gè)重要的發(fā)展趨勢(shì)。但是，在教學(xué)活動(dòng)中的有一個(gè)重要環(huán)節(jié)就是考試，如何讓一些課程的考試在網(wǎng)絡(luò)中進(jìn)行卻是一個(gè)難題。其中，組卷算法更是考試系統(tǒng)能否設(shè)計(jì)成功的關(guān)鍵所在。自動(dòng)組卷系統(tǒng)中組卷算法的好壞直接影響到組卷的效率和質(zhì)量，所以如何選擇一個(gè)高效、科學(xué)、強(qiáng)壯的算法是自動(dòng)組卷的核心問題。該文詳細(xì)介紹了目前經(jīng)常使用的幾種組卷算法。

關(guān)鍵詞： 在線考試；自動(dòng)組卷；組卷算法； 隨機(jī)抽題；遺傳算法

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）32-7621-03

Abstract：Modern social development is inseparable from Internet，Network application has increasingly become an important development trend in modern teaching activities. However， how to conduct examination on Internet is a difficult problem since it's an important procedure in teaching activities. And moreover， test paper composition algorithm is the key of online examination 's success. Test paper composition algorithm in system of automatic test paper construction can affect the efficiency and the quality of test paper composition.So， How to choose an efficient and scientific and strong algorithm is the core problem of automatic test paper composition.In this paper， some of test paper composition algorithm which are often used are introduced in detail.

Key words： online examination； automatic test paper composition； test paper composition algorithm； choosing questions at random； genetic algorithm

我們國家傳統(tǒng)的各種類型考試，從開始生成試卷，印刷，然后安排考務(wù)，學(xué)生正式考試，收取試卷，再到閱卷，最后成績發(fā)布，涵蓋了諸多復(fù)雜的環(huán)節(jié)。這樣造成整個(gè)工作量復(fù)雜而繁重，要消耗非常大的人力資源和物力資源。開發(fā)設(shè)計(jì)使用網(wǎng)絡(luò)考試系統(tǒng)，可以使得考試沒有這么多復(fù)雜繁重的環(huán)節(jié)，可以在各個(gè)試題庫中抽取適當(dāng)?shù)脑囶}來組成質(zhì)量合格的試卷。這樣組卷的效果好，比較靈活，并且節(jié)省了大量的成本。考試的知識(shí)點(diǎn)覆蓋面也更加地廣泛，可以全方位的對(duì)學(xué)生的學(xué)習(xí)效果進(jìn)行比較全面的考察。此外，在線考試系統(tǒng)可以進(jìn)行自動(dòng)評(píng)分，這樣可以有效地避免了人工統(tǒng)計(jì)分?jǐn)?shù)過程中出現(xiàn)的差錯(cuò)問題，確保整個(gè)考試的公平和公正，大大降低了教師的工作量，提高了教學(xué)效率。在線考試系統(tǒng)具有自動(dòng)化的程度高、穩(wěn)定性好、評(píng)分快速、公正、準(zhǔn)確，保密性高和便于組織大規(guī)模在線考試等優(yōu)勢(shì)。在線考試系統(tǒng)還可以對(duì)學(xué)生的考試成績進(jìn)行統(tǒng)計(jì)和分析，考察整個(gè)課程學(xué)生的學(xué)習(xí)效果，對(duì)教師的教學(xué)手段和方法的改進(jìn)提供了良好的數(shù)據(jù)支持。

基于網(wǎng)絡(luò)的在線考試系統(tǒng)的組卷問題是整個(gè)考試系統(tǒng)的核心問題，要求用戶根據(jù)考試要求設(shè)置相應(yīng)的組卷?xiàng)l件，然后使用合適的組卷算法，從原來做好的試題庫中抽取滿足條件并且按照最優(yōu)組合的方式生成一份合格的考試試卷。如何組成試卷是在特定的多約束條件下的許多目標(biāo)參數(shù)的如何組合優(yōu)化問題。在這當(dāng)中，組卷的算法問題是基于網(wǎng)絡(luò)的在線考試系統(tǒng)能否成功設(shè)計(jì)并應(yīng)用的核心問題。下面介紹目前最為流行的四種組卷算法。

1 回溯試探法

回溯試探法是在考試系統(tǒng)隨機(jī)抽取試題的時(shí)候，首先驗(yàn)證一下系統(tǒng)所選擇的試題是否滿足給定的條件，然后再做決定看是否抽取此試題。如果沒有滿足給定條件的試題，并且考試試卷又未完全生成，考試系統(tǒng)回溯試探，舍掉剛才所做的一部分操作，然后重新再組卷。因?yàn)橹皇巧岬袅艘恍〔糠值牟僮鳎蟠蠼档土藷o用組卷的次數(shù)?；厮菰囂椒ńM卷的成功率雖然高，但這是在消耗了大量的時(shí)間的基礎(chǔ)上的。回溯試探法是下面將要介紹的隨機(jī)抽題方法的一種改良算法。

回溯試探法在隨機(jī)抽題法的基礎(chǔ)上抽取試題，如果搜索失敗，就會(huì)舍掉該狀態(tài)掉，重新開始下一輪的試卷組成?；厮莘ǖ墓ぷ髁鞒倘鐖D1所示。

考試系統(tǒng)如果采用回溯法來抽取試題，則會(huì)造成整個(gè)程序的結(jié)構(gòu)設(shè)計(jì)非常復(fù)雜，抽取的試題隨機(jī)效果不明顯，生成的試卷時(shí)間較長，與許多考試系統(tǒng)生成試卷的要求不符，但是對(duì)一些小型的考試系統(tǒng)效果還是比較好的。

2 隨機(jī)抽題法

目前大部分的考試系統(tǒng)都在使用隨機(jī)抽題法作為考試系統(tǒng)的算法。此算法是采用隨機(jī)函數(shù)對(duì)題庫中的滿足條件的題目逐一的抽取出來，組成試卷。使用這種組卷算法實(shí)現(xiàn)起來比較簡單，而且使用也比較廣泛。此算法要求建立兩個(gè)數(shù)組，一個(gè)數(shù)組用來存儲(chǔ)試卷的狀態(tài)空間，一個(gè)數(shù)組用來存儲(chǔ)試卷題目，是空數(shù)組。第一步把試卷的某些控制參數(shù)存放到試卷狀態(tài)的數(shù)組里面，如題目的難易程度、題目類型、題目分值等等。第二步由考試系統(tǒng)根據(jù)數(shù)組試卷的控制參數(shù)，隨機(jī)抽題。第三步把抽出來的題目放到空數(shù)組里面。如此反復(fù)的抽取題目，直到試卷最終生成為止。需要注意的是，考試系統(tǒng)每當(dāng)抽取完一道題目，需要設(shè)置抽取標(biāo)識(shí)，表明該題目已經(jīng)被抽取，防止下次再被抽到。以下是抽取題目的公式。

抽取試題的公

其實(shí)在現(xiàn)實(shí)的情況里，組卷要對(duì)題目的抽取有著某些特定的要求。那么怎樣才能合理地使用rand隨機(jī)函數(shù)，能夠在相同的題庫中組成適合不同要求的試卷呢？顯然rand函數(shù)并不能解決所有的問題，但卻能夠創(chuàng)造出一個(gè)良好的組卷環(huán)境，在這個(gè)環(huán)境里rand函數(shù)利用計(jì)算公式和算法來組成適應(yīng)不同要求的試卷。而這種環(huán)境是由兩個(gè)方法來實(shí)現(xiàn)的，一個(gè)是修改表的結(jié)構(gòu)，另一個(gè)是建立一個(gè)界面，來適應(yīng)不同要求的試卷抽取條件。

現(xiàn)在的大多數(shù)的網(wǎng)絡(luò)考試系統(tǒng)是現(xiàn)場(chǎng)抽取題目的，采用剛才介紹的算法來隨機(jī)抽取，題目是不同的，當(dāng)然也有的網(wǎng)絡(luò)考試系統(tǒng)中的題目是提前抽取的，所有考生的題目都一樣，只是題目的順序不同而已。對(duì)于這種方式，實(shí)現(xiàn)起來也比簡單，先用隨機(jī)抽題法抽取一套試題，然后再利用隨機(jī)函數(shù)從抽出來的題目里再重新抽取，這樣題目的順序就不同了。

隨機(jī)抽題法適合那些比較簡單的網(wǎng)絡(luò)考試系統(tǒng)，對(duì)試卷的組成要求不是很高的考試系統(tǒng)。此算法比較容易實(shí)現(xiàn)，而且組卷速度快，因?yàn)樗鼪]有最優(yōu)化的思想在里面。但是此算法的缺點(diǎn)是，隨著題目一步一步的被抽取出來，它很難再界定剩下哪些區(qū)域適合再次抽題，從而進(jìn)入了死循環(huán)，試卷最終無法生成。此算法抽取的題目重復(fù)率比較高，成功率也低，智能性較差。

3 啟發(fā)式搜索法

此種方法是在存放試題狀態(tài)空間的數(shù)組里，首先對(duì)每個(gè)搜索位置進(jìn)行測(cè)評(píng)，找到一個(gè)最好的最合適的位置，然后在此位置繼續(xù)進(jìn)行搜索，直到找到目標(biāo)為止。使用此種算法能夠省去一些無用的工作量，大大提高了組卷工作效率。在這種算法里，對(duì)每個(gè)位置的測(cè)評(píng)是重中之重，用不一樣的方法測(cè)評(píng)會(huì)得到不一樣的效果。那么測(cè)評(píng)是如何表示出來的呢？啟發(fā)式搜索法的測(cè)評(píng)用的是測(cè)評(píng)函數(shù)。f（n）=g（n）+h（n），在這里f（n）是n的測(cè)評(píng)函數(shù)，而g（n）是在狀態(tài)空間數(shù)組里從初始節(jié)點(diǎn)到n節(jié)點(diǎn)的實(shí)際路徑，h（n）則是從n到目的節(jié)點(diǎn)的最佳的測(cè)評(píng)路徑。在這個(gè)函數(shù)里面，h（n）主要體現(xiàn)了搜索的啟發(fā)的信息，在這當(dāng)中g(shù)（n）是已知的。

啟發(fā)式搜索法相比起回溯試探法和隨機(jī)抽題法，它的成功率要比后兩者高，適合需要抽取各種復(fù)雜題目的網(wǎng)絡(luò)考試系統(tǒng)。但是使用啟發(fā)式搜索法設(shè)計(jì)開發(fā)程序比較的復(fù)雜，花費(fèi)的時(shí)間長，所以生成試卷的效率不如后兩者算法好。

4 遺傳算法

遺傳算法是在1975年美國密歇根州大學(xué)由John H.HoUand教授第一次提出來的算法。此算法是模擬自然界的生物進(jìn)化過程的自由隨機(jī)搜索的方法，它是一種新型的優(yōu)化算法。遺傳算法利用比較簡單的編碼表示各式的復(fù)雜結(jié)構(gòu)，而且用編碼來表示一些遺傳操作，再利用優(yōu)勝劣汰的自然選擇指導(dǎo)搜索方向。此算法是一種群體式的操作方式，把所有個(gè)體作為操作對(duì)象。它的三個(gè)主要操作運(yùn)算分別是遺傳、交叉、變異。進(jìn)行完操作運(yùn)算后下一代種群就保留了上一代的優(yōu)良個(gè)體基因，體現(xiàn)出符合自然界規(guī)律的“自然選擇、適者生存”的生存原則。

首先進(jìn)行選擇操作，它的作用是大大提高了種群的平均適應(yīng)值，但是這個(gè)操作只是選擇，并沒有產(chǎn)生出新的個(gè)體，所以在種群中最好的適應(yīng)值并沒有改進(jìn)。第二步交叉是把在交配池當(dāng)中的個(gè)體進(jìn)行隨機(jī)的配對(duì)，再把配對(duì)好的個(gè)體用特定的方式來相互交互一部分的基因，此操作產(chǎn)生出新的個(gè)體，因此它決定了整個(gè)算法的搜索能力的強(qiáng)弱。第三步變異是針對(duì)個(gè)體的，把個(gè)體中的某個(gè)或者某部分基因按照特定的較小概率，進(jìn)行改變，從而產(chǎn)生了新的個(gè)體的輔助方法。第二步交叉和第三步變異互相配合操作，從而完成了整個(gè)遺傳算法的全局搜索能力。

在整個(gè)遺傳算法當(dāng)中，“生成+檢測(cè)”的搜索算法運(yùn)用在迭代過程里。用一些編碼方案表示出空間里的一個(gè)一個(gè)的個(gè)體，并且把目標(biāo)函數(shù)的值轉(zhuǎn)變成適應(yīng)的值。用它來評(píng)價(jià)每個(gè)個(gè)體的優(yōu)劣，以此當(dāng)做遺傳的依據(jù)。

種群方式搜索是遺傳算法采用的搜索方法。此方式能夠搜索出空間里面的多個(gè)區(qū)域，所以它具有內(nèi)在并行性的特點(diǎn)，它可以解決程序計(jì)算量比較大的問題，從而提高了效率。適者生存，還有比較簡單的遺傳操作讓遺傳算法不再受到搜索空間的限制，搜索過程不會(huì)輕易的陷入局部的最優(yōu)點(diǎn)。因此，遺傳算法組卷的效率比較高，操作起來比較簡單。但是遺傳算法也有兩個(gè)較為明顯的缺點(diǎn)。第一，對(duì)一些特殊情況遺傳算法計(jì)算的速度比較慢。第二，比較容易產(chǎn)生試卷早熟的情況。正因?yàn)橛羞@兩個(gè)缺點(diǎn)，所以很多專家提出了一些改良方案。比如編碼改進(jìn)方案、交叉算子或者變異算子的自適應(yīng)改進(jìn)等等。

5 結(jié)束語

智能組卷算法是實(shí)現(xiàn)快速組卷、科學(xué)組卷的基本保障。如何組成試卷是在特定的多約束條件下的許多目標(biāo)參數(shù)的如何組合優(yōu)化問題。而這些約束條件用數(shù)學(xué)的方法很難進(jìn)行描述，所以用傳統(tǒng)的數(shù)學(xué)方法解決起來比較困難。該文詳細(xì)介紹了在網(wǎng)絡(luò)考試系統(tǒng)中常見的四種組卷算法，通過分析可以發(fā)現(xiàn)，遺傳算法是比較適合網(wǎng)絡(luò)考試系統(tǒng)采用的組卷算法，是最優(yōu)化組卷最為合適的一種算法。

參考文獻(xiàn)：

[1] 焦瑞，李祥生.試卷自動(dòng)生成系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].山西醫(yī)科大學(xué)學(xué)報(bào)，2005（4）.

[2] 王燦輝.計(jì)算機(jī)自動(dòng)組卷算法研究[J].福州大學(xué)學(xué)報(bào)，2001（S1）.

[3] 李敏強(qiáng)，寇紀(jì)淞.遺傳算法的基本理論與應(yīng)用[M].北京：科學(xué)出版社，2002.

[4] 徐運(yùn)玲.在線考試系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].科技信息，2010（9）.

[5] 文嫻.試題庫系統(tǒng)智能組卷與試卷分析的研究[D].長沙：湖南師范大學(xué)，2007.

[6] 劉亞瓊.基于加強(qiáng)學(xué)習(xí)的自動(dòng)組卷算法的研究[D].天津：天津大學(xué)，2006.

[7] 曾一，冉忠，郭永林.試題庫中自動(dòng)組卷的算法及試卷測(cè)評(píng)策略[J].計(jì)算機(jī)工程與設(shè)計(jì)，2006（16）.

[8] 武蕾娜.組卷算法的研究[J].福建電腦，2009（3）.

抽取試題的公

其實(shí)在現(xiàn)實(shí)的情況里，組卷要對(duì)題目的抽取有著某些特定的要求。那么怎樣才能合理地使用rand隨機(jī)函數(shù)，能夠在相同的題庫中組成適合不同要求的試卷呢？顯然rand函數(shù)并不能解決所有的問題，但卻能夠創(chuàng)造出一個(gè)良好的組卷環(huán)境，在這個(gè)環(huán)境里rand函數(shù)利用計(jì)算公式和算法來組成適應(yīng)不同要求的試卷。而這種環(huán)境是由兩個(gè)方法來實(shí)現(xiàn)的，一個(gè)是修改表的結(jié)構(gòu)，另一個(gè)是建立一個(gè)界面，來適應(yīng)不同要求的試卷抽取條件。

現(xiàn)在的大多數(shù)的網(wǎng)絡(luò)考試系統(tǒng)是現(xiàn)場(chǎng)抽取題目的，采用剛才介紹的算法來隨機(jī)抽取，題目是不同的，當(dāng)然也有的網(wǎng)絡(luò)考試系統(tǒng)中的題目是提前抽取的，所有考生的題目都一樣，只是題目的順序不同而已。對(duì)于這種方式，實(shí)現(xiàn)起來也比簡單，先用隨機(jī)抽題法抽取一套試題，然后再利用隨機(jī)函數(shù)從抽出來的題目里再重新抽取，這樣題目的順序就不同了。

隨機(jī)抽題法適合那些比較簡單的網(wǎng)絡(luò)考試系統(tǒng)，對(duì)試卷的組成要求不是很高的考試系統(tǒng)。此算法比較容易實(shí)現(xiàn)，而且組卷速度快，因?yàn)樗鼪]有最優(yōu)化的思想在里面。但是此算法的缺點(diǎn)是，隨著題目一步一步的被抽取出來，它很難再界定剩下哪些區(qū)域適合再次抽題，從而進(jìn)入了死循環(huán)，試卷最終無法生成。此算法抽取的題目重復(fù)率比較高，成功率也低，智能性較差。

3 啟發(fā)式搜索法

此種方法是在存放試題狀態(tài)空間的數(shù)組里，首先對(duì)每個(gè)搜索位置進(jìn)行測(cè)評(píng)，找到一個(gè)最好的最合適的位置，然后在此位置繼續(xù)進(jìn)行搜索，直到找到目標(biāo)為止。使用此種算法能夠省去一些無用的工作量，大大提高了組卷工作效率。在這種算法里，對(duì)每個(gè)位置的測(cè)評(píng)是重中之重，用不一樣的方法測(cè)評(píng)會(huì)得到不一樣的效果。那么測(cè)評(píng)是如何表示出來的呢？啟發(fā)式搜索法的測(cè)評(píng)用的是測(cè)評(píng)函數(shù)。f（n）=g（n）+h（n），在這里f（n）是n的測(cè)評(píng)函數(shù)，而g（n）是在狀態(tài)空間數(shù)組里從初始節(jié)點(diǎn)到n節(jié)點(diǎn)的實(shí)際路徑，h（n）則是從n到目的節(jié)點(diǎn)的最佳的測(cè)評(píng)路徑。在這個(gè)函數(shù)里面，h（n）主要體現(xiàn)了搜索的啟發(fā)的信息，在這當(dāng)中g(shù)（n）是已知的。

啟發(fā)式搜索法相比起回溯試探法和隨機(jī)抽題法，它的成功率要比后兩者高，適合需要抽取各種復(fù)雜題目的網(wǎng)絡(luò)考試系統(tǒng)。但是使用啟發(fā)式搜索法設(shè)計(jì)開發(fā)程序比較的復(fù)雜，花費(fèi)的時(shí)間長，所以生成試卷的效率不如后兩者算法好。

4 遺傳算法

遺傳算法是在1975年美國密歇根州大學(xué)由John H.HoUand教授第一次提出來的算法。此算法是模擬自然界的生物進(jìn)化過程的自由隨機(jī)搜索的方法，它是一種新型的優(yōu)化算法。遺傳算法利用比較簡單的編碼表示各式的復(fù)雜結(jié)構(gòu)，而且用編碼來表示一些遺傳操作，再利用優(yōu)勝劣汰的自然選擇指導(dǎo)搜索方向。此算法是一種群體式的操作方式，把所有個(gè)體作為操作對(duì)象。它的三個(gè)主要操作運(yùn)算分別是遺傳、交叉、變異。進(jìn)行完操作運(yùn)算后下一代種群就保留了上一代的優(yōu)良個(gè)體基因，體現(xiàn)出符合自然界規(guī)律的“自然選擇、適者生存”的生存原則。

首先進(jìn)行選擇操作，它的作用是大大提高了種群的平均適應(yīng)值，但是這個(gè)操作只是選擇，并沒有產(chǎn)生出新的個(gè)體，所以在種群中最好的適應(yīng)值并沒有改進(jìn)。第二步交叉是把在交配池當(dāng)中的個(gè)體進(jìn)行隨機(jī)的配對(duì)，再把配對(duì)好的個(gè)體用特定的方式來相互交互一部分的基因，此操作產(chǎn)生出新的個(gè)體，因此它決定了整個(gè)算法的搜索能力的強(qiáng)弱。第三步變異是針對(duì)個(gè)體的，把個(gè)體中的某個(gè)或者某部分基因按照特定的較小概率，進(jìn)行改變，從而產(chǎn)生了新的個(gè)體的輔助方法。第二步交叉和第三步變異互相配合操作，從而完成了整個(gè)遺傳算法的全局搜索能力。

在整個(gè)遺傳算法當(dāng)中，“生成+檢測(cè)”的搜索算法運(yùn)用在迭代過程里。用一些編碼方案表示出空間里的一個(gè)一個(gè)的個(gè)體，并且把目標(biāo)函數(shù)的值轉(zhuǎn)變成適應(yīng)的值。用它來評(píng)價(jià)每個(gè)個(gè)體的優(yōu)劣，以此當(dāng)做遺傳的依據(jù)。

種群方式搜索是遺傳算法采用的搜索方法。此方式能夠搜索出空間里面的多個(gè)區(qū)域，所以它具有內(nèi)在并行性的特點(diǎn)，它可以解決程序計(jì)算量比較大的問題，從而提高了效率。適者生存，還有比較簡單的遺傳操作讓遺傳算法不再受到搜索空間的限制，搜索過程不會(huì)輕易的陷入局部的最優(yōu)點(diǎn)。因此，遺傳算法組卷的效率比較高，操作起來比較簡單。但是遺傳算法也有兩個(gè)較為明顯的缺點(diǎn)。第一，對(duì)一些特殊情況遺傳算法計(jì)算的速度比較慢。第二，比較容易產(chǎn)生試卷早熟的情況。正因?yàn)橛羞@兩個(gè)缺點(diǎn)，所以很多專家提出了一些改良方案。比如編碼改進(jìn)方案、交叉算子或者變異算子的自適應(yīng)改進(jìn)等等。

5 結(jié)束語

智能組卷算法是實(shí)現(xiàn)快速組卷、科學(xué)組卷的基本保障。如何組成試卷是在特定的多約束條件下的許多目標(biāo)參數(shù)的如何組合優(yōu)化問題。而這些約束條件用數(shù)學(xué)的方法很難進(jìn)行描述，所以用傳統(tǒng)的數(shù)學(xué)方法解決起來比較困難。該文詳細(xì)介紹了在網(wǎng)絡(luò)考試系統(tǒng)中常見的四種組卷算法，通過分析可以發(fā)現(xiàn)，遺傳算法是比較適合網(wǎng)絡(luò)考試系統(tǒng)采用的組卷算法，是最優(yōu)化組卷最為合適的一種算法。

參考文獻(xiàn)：

[1] 焦瑞，李祥生.試卷自動(dòng)生成系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].山西醫(yī)科大學(xué)學(xué)報(bào)，2005（4）.

[2] 王燦輝.計(jì)算機(jī)自動(dòng)組卷算法研究[J].福州大學(xué)學(xué)報(bào)，2001（S1）.

[3] 李敏強(qiáng)，寇紀(jì)淞.遺傳算法的基本理論與應(yīng)用[M].北京：科學(xué)出版社，2002.

[4] 徐運(yùn)玲.在線考試系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].科技信息，2010（9）.

[5] 文嫻.試題庫系統(tǒng)智能組卷與試卷分析的研究[D].長沙：湖南師范大學(xué)，2007.

[6] 劉亞瓊.基于加強(qiáng)學(xué)習(xí)的自動(dòng)組卷算法的研究[D].天津：天津大學(xué)，2006.

[7] 曾一，冉忠，郭永林.試題庫中自動(dòng)組卷的算法及試卷測(cè)評(píng)策略[J].計(jì)算機(jī)工程與設(shè)計(jì)，2006（16）.

[8] 武蕾娜.組卷算法的研究[J].福建電腦，2009（3）.

抽取試題的公

其實(shí)在現(xiàn)實(shí)的情況里，組卷要對(duì)題目的抽取有著某些特定的要求。那么怎樣才能合理地使用rand隨機(jī)函數(shù)，能夠在相同的題庫中組成適合不同要求的試卷呢？顯然rand函數(shù)并不能解決所有的問題，但卻能夠創(chuàng)造出一個(gè)良好的組卷環(huán)境，在這個(gè)環(huán)境里rand函數(shù)利用計(jì)算公式和算法來組成適應(yīng)不同要求的試卷。而這種環(huán)境是由兩個(gè)方法來實(shí)現(xiàn)的，一個(gè)是修改表的結(jié)構(gòu)，另一個(gè)是建立一個(gè)界面，來適應(yīng)不同要求的試卷抽取條件。

現(xiàn)在的大多數(shù)的網(wǎng)絡(luò)考試系統(tǒng)是現(xiàn)場(chǎng)抽取題目的，采用剛才介紹的算法來隨機(jī)抽取，題目是不同的，當(dāng)然也有的網(wǎng)絡(luò)考試系統(tǒng)中的題目是提前抽取的，所有考生的題目都一樣，只是題目的順序不同而已。對(duì)于這種方式，實(shí)現(xiàn)起來也比簡單，先用隨機(jī)抽題法抽取一套試題，然后再利用隨機(jī)函數(shù)從抽出來的題目里再重新抽取，這樣題目的順序就不同了。

隨機(jī)抽題法適合那些比較簡單的網(wǎng)絡(luò)考試系統(tǒng)，對(duì)試卷的組成要求不是很高的考試系統(tǒng)。此算法比較容易實(shí)現(xiàn)，而且組卷速度快，因?yàn)樗鼪]有最優(yōu)化的思想在里面。但是此算法的缺點(diǎn)是，隨著題目一步一步的被抽取出來，它很難再界定剩下哪些區(qū)域適合再次抽題，從而進(jìn)入了死循環(huán)，試卷最終無法生成。此算法抽取的題目重復(fù)率比較高，成功率也低，智能性較差。

3 啟發(fā)式搜索法

此種方法是在存放試題狀態(tài)空間的數(shù)組里，首先對(duì)每個(gè)搜索位置進(jìn)行測(cè)評(píng)，找到一個(gè)最好的最合適的位置，然后在此位置繼續(xù)進(jìn)行搜索，直到找到目標(biāo)為止。使用此種算法能夠省去一些無用的工作量，大大提高了組卷工作效率。在這種算法里，對(duì)每個(gè)位置的測(cè)評(píng)是重中之重，用不一樣的方法測(cè)評(píng)會(huì)得到不一樣的效果。那么測(cè)評(píng)是如何表示出來的呢？啟發(fā)式搜索法的測(cè)評(píng)用的是測(cè)評(píng)函數(shù)。f（n）=g（n）+h（n），在這里f（n）是n的測(cè)評(píng)函數(shù)，而g（n）是在狀態(tài)空間數(shù)組里從初始節(jié)點(diǎn)到n節(jié)點(diǎn)的實(shí)際路徑，h（n）則是從n到目的節(jié)點(diǎn)的最佳的測(cè)評(píng)路徑。在這個(gè)函數(shù)里面，h（n）主要體現(xiàn)了搜索的啟發(fā)的信息，在這當(dāng)中g(shù)（n）是已知的。

啟發(fā)式搜索法相比起回溯試探法和隨機(jī)抽題法，它的成功率要比后兩者高，適合需要抽取各種復(fù)雜題目的網(wǎng)絡(luò)考試系統(tǒng)。但是使用啟發(fā)式搜索法設(shè)計(jì)開發(fā)程序比較的復(fù)雜，花費(fèi)的時(shí)間長，所以生成試卷的效率不如后兩者算法好。

4 遺傳算法

遺傳算法是在1975年美國密歇根州大學(xué)由John H.HoUand教授第一次提出來的算法。此算法是模擬自然界的生物進(jìn)化過程的自由隨機(jī)搜索的方法，它是一種新型的優(yōu)化算法。遺傳算法利用比較簡單的編碼表示各式的復(fù)雜結(jié)構(gòu)，而且用編碼來表示一些遺傳操作，再利用優(yōu)勝劣汰的自然選擇指導(dǎo)搜索方向。此算法是一種群體式的操作方式，把所有個(gè)體作為操作對(duì)象。它的三個(gè)主要操作運(yùn)算分別是遺傳、交叉、變異。進(jìn)行完操作運(yùn)算后下一代種群就保留了上一代的優(yōu)良個(gè)體基因，體現(xiàn)出符合自然界規(guī)律的“自然選擇、適者生存”的生存原則。

首先進(jìn)行選擇操作，它的作用是大大提高了種群的平均適應(yīng)值，但是這個(gè)操作只是選擇，并沒有產(chǎn)生出新的個(gè)體，所以在種群中最好的適應(yīng)值并沒有改進(jìn)。第二步交叉是把在交配池當(dāng)中的個(gè)體進(jìn)行隨機(jī)的配對(duì)，再把配對(duì)好的個(gè)體用特定的方式來相互交互一部分的基因，此操作產(chǎn)生出新的個(gè)體，因此它決定了整個(gè)算法的搜索能力的強(qiáng)弱。第三步變異是針對(duì)個(gè)體的，把個(gè)體中的某個(gè)或者某部分基因按照特定的較小概率，進(jìn)行改變，從而產(chǎn)生了新的個(gè)體的輔助方法。第二步交叉和第三步變異互相配合操作，從而完成了整個(gè)遺傳算法的全局搜索能力。

在整個(gè)遺傳算法當(dāng)中，“生成+檢測(cè)”的搜索算法運(yùn)用在迭代過程里。用一些編碼方案表示出空間里的一個(gè)一個(gè)的個(gè)體，并且把目標(biāo)函數(shù)的值轉(zhuǎn)變成適應(yīng)的值。用它來評(píng)價(jià)每個(gè)個(gè)體的優(yōu)劣，以此當(dāng)做遺傳的依據(jù)。

種群方式搜索是遺傳算法采用的搜索方法。此方式能夠搜索出空間里面的多個(gè)區(qū)域，所以它具有內(nèi)在并行性的特點(diǎn)，它可以解決程序計(jì)算量比較大的問題，從而提高了效率。適者生存，還有比較簡單的遺傳操作讓遺傳算法不再受到搜索空間的限制，搜索過程不會(huì)輕易的陷入局部的最優(yōu)點(diǎn)。因此，遺傳算法組卷的效率比較高，操作起來比較簡單。但是遺傳算法也有兩個(gè)較為明顯的缺點(diǎn)。第一，對(duì)一些特殊情況遺傳算法計(jì)算的速度比較慢。第二，比較容易產(chǎn)生試卷早熟的情況。正因?yàn)橛羞@兩個(gè)缺點(diǎn)，所以很多專家提出了一些改良方案。比如編碼改進(jìn)方案、交叉算子或者變異算子的自適應(yīng)改進(jìn)等等。

5 結(jié)束語

智能組卷算法是實(shí)現(xiàn)快速組卷、科學(xué)組卷的基本保障。如何組成試卷是在特定的多約束條件下的許多目標(biāo)參數(shù)的如何組合優(yōu)化問題。而這些約束條件用數(shù)學(xué)的方法很難進(jìn)行描述，所以用傳統(tǒng)的數(shù)學(xué)方法解決起來比較困難。該文詳細(xì)介紹了在網(wǎng)絡(luò)考試系統(tǒng)中常見的四種組卷算法，通過分析可以發(fā)現(xiàn)，遺傳算法是比較適合網(wǎng)絡(luò)考試系統(tǒng)采用的組卷算法，是最優(yōu)化組卷最為合適的一種算法。

參考文獻(xiàn)：

[1] 焦瑞，李祥生.試卷自動(dòng)生成系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].山西醫(yī)科大學(xué)學(xué)報(bào)，2005（4）.

[2] 王燦輝.計(jì)算機(jī)自動(dòng)組卷算法研究[J].福州大學(xué)學(xué)報(bào)，2001（S1）.

[3] 李敏強(qiáng)，寇紀(jì)淞.遺傳算法的基本理論與應(yīng)用[M].北京：科學(xué)出版社，2002.

[4] 徐運(yùn)玲.在線考試系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].科技信息，2010（9）.

[5] 文嫻.試題庫系統(tǒng)智能組卷與試卷分析的研究[D].長沙：湖南師范大學(xué)，2007.

[6] 劉亞瓊.基于加強(qiáng)學(xué)習(xí)的自動(dòng)組卷算法的研究[D].天津：天津大學(xué)，2006.

[7] 曾一，冉忠，郭永林.試題庫中自動(dòng)組卷的算法及試卷測(cè)評(píng)策略[J].計(jì)算機(jī)工程與設(shè)計(jì)，2006（16）.

[8] 武蕾娜.組卷算法的研究[J].福建電腦，2009（3）.