基于遺傳模擬退火算法的智能組卷研究

趙建勛 黃繼海

摘要：考試數(shù)據(jù)庫(kù)中的智能測(cè)試組卷是在一定約束條件下的多目標(biāo)參數(shù)優(yōu)化問(wèn)題。通過(guò)應(yīng)用傳統(tǒng)的數(shù)學(xué)方法，很難解決這個(gè)問(wèn)題。該文給了一個(gè)數(shù)學(xué)模型，并提出了一種新的遺傳模擬退火算法來(lái)解決這個(gè)問(wèn)題。通過(guò)對(duì)該算法的測(cè)試表明，新算法能夠很好地提高組卷的成功率，并且在組卷的收斂速度和防止早收斂方面有了很明顯地改善。

關(guān)鍵詞：智能組卷；多目標(biāo)參數(shù)；遺傳模擬；退火算法

中圖分類號(hào)：TP391.6文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2012)21-5183-04

Research of Intelligent Grouping Based on Genetic Simulated Annealing Algorithm

ZHAO Jian-xun, HUANG Ji-hai

(Information & Engineering College of Zhongzhou University, Zhengzhou 450044, China）

Abstract:The intelligent testpaper in the examination database optimizationproblem inmulti-targetparameters under certain con? straints. Through the application of traditional mathematical methods, it is difficult to solve this problem. The article gave a mathemati? cal model, and proposes a new genetic simulated annealing algorithm to solve this problem. Tests show that this algorithm, the new algo? rithm can improve the success rate of the test paper,and the convergence rate in the test paper to prevent early convergence as? pects have clearly improved.

Key words：intelligent test paper composition; multi target parameter; genetic simulated annealing algorithm

當(dāng)前的教學(xué)內(nèi)容、教學(xué)手段和教學(xué)方法伴隨著計(jì)算機(jī)技術(shù)的快速發(fā)展，已經(jīng)出現(xiàn)了一定程度的不適應(yīng)性，人們?cè)絹?lái)越多地借助于計(jì)算機(jī)輔助考試系統(tǒng)來(lái)替代傳統(tǒng)意義的考試，這也決定了計(jì)算機(jī)輔助考試系統(tǒng)已經(jīng)成為人們關(guān)注和研究的熱點(diǎn)之一。計(jì)算機(jī)輔助考試系統(tǒng)主要是通過(guò)計(jì)算機(jī)自動(dòng)生成試卷以及自動(dòng)評(píng)閱試卷，從而減少傳統(tǒng)考試中的多個(gè)環(huán)節(jié)，達(dá)到了節(jié)約人力、財(cái)力和物力的效果。同時(shí)，通過(guò)計(jì)算機(jī)評(píng)閱試卷還能保證考試成績(jī)的客觀性，提高考試成績(jī)的公平性。

目前計(jì)算機(jī)輔助考試系統(tǒng)所采用的最多的算法是遺傳算法，由于遺傳算法具有自適應(yīng)尋優(yōu)和良好的搜索特性，得到了眾多學(xué)者的青睞。學(xué)者們通過(guò)理論推導(dǎo)和實(shí)踐運(yùn)用，發(fā)現(xiàn)遺傳算法的收斂速度是非?？斓?，同時(shí)尋優(yōu)的效率也非常高。遺傳算法在許多領(lǐng)域內(nèi)的應(yīng)用都取得了卓越的成果[1-2]，在遺傳算法的改進(jìn)和理論研究方面也出現(xiàn)了許多成功的探索。

組卷算法的設(shè)計(jì)與實(shí)現(xiàn)是影響組卷效率和組卷質(zhì)量的核心[3-5]，如何通過(guò)建立全新的數(shù)學(xué)模型，設(shè)置不同組卷的指標(biāo)，從而使組卷模型具有較好的通用性；以及在該模型的基礎(chǔ)上構(gòu)造新的遺傳算法編碼方法，在避免出現(xiàn)適應(yīng)值的重復(fù)計(jì)算和解碼過(guò)程的復(fù)雜過(guò)度運(yùn)算，提高運(yùn)算效率方面達(dá)到良好的組卷效果，該文將給出具體的解決方法。

2.1基因庫(kù)的構(gòu)造

為了減少遺傳算法的迭代次數(shù)同時(shí)加快遺產(chǎn)算法的收斂，應(yīng)根據(jù)試卷題型的比例和總分的要求，從初始化后并且包含知識(shí)點(diǎn)約束屬性的試題庫(kù)中隨機(jī)產(chǎn)生試卷的初始試題，這樣不僅能夠滿足試卷題型和總分的要求，同時(shí)也能夠滿足試卷對(duì)知識(shí)點(diǎn)的要求。基因庫(kù)的具體構(gòu)造步驟如下：

1）構(gòu)造試題庫(kù)的多個(gè)不同子集。子集中應(yīng)該包含試題的知識(shí)點(diǎn)、題型和難度要求相關(guān)的屬性，知識(shí)點(diǎn)、題型和難度相同或者相近的試題應(yīng)該劃在同一個(gè)子集中；

2）計(jì)算各題型包含的題目數(shù)以及在整套試卷中所占的分?jǐn)?shù)比例。題目數(shù)應(yīng)該滿足用戶對(duì)總分的要求、對(duì)題型覆蓋情況的要求以及標(biāo)準(zhǔn)化題庫(kù)中同種題型的試題分?jǐn)?shù)是否相同的特點(diǎn)；

3）計(jì)算已經(jīng)生成的試卷中是否需要同種難度題型的試題以及試題的數(shù)量，可以將此試題的數(shù)量設(shè)定為R；

4）去掉已經(jīng)存在的試題，保證數(shù)據(jù)存儲(chǔ)對(duì)象的低冗余性；

5）檢查試題是否滿足限制條件，試題需要隨機(jī)地從各個(gè)子集中抽取，以保證不同知識(shí)點(diǎn)和難度的試題出現(xiàn)在生成的試卷中；

6）刪除不滿足限制條件的試題，轉(zhuǎn)到5）繼續(xù)；

7）將滿足條件的試題插入到試卷中，并使R減1；

8）判斷當(dāng)前章節(jié)中的試題是否能夠加入到當(dāng)前的試卷中，如果能夠加入到當(dāng)前的試卷中，說(shuō)明當(dāng)前的知識(shí)點(diǎn)試題已經(jīng)存在，需要從數(shù)據(jù)對(duì)象中全部刪除，然后轉(zhuǎn)到5）繼續(xù)；如果該章節(jié)已經(jīng)不能夠加入試題了，說(shuō)明該章節(jié)中的試題數(shù)量已經(jīng)達(dá)到了試卷要求的最大值，則刪除對(duì)應(yīng)章節(jié)的全部試題，然后轉(zhuǎn)到6）繼續(xù)；

9）退出循環(huán)。退出循環(huán)的條件是R為0或者數(shù)據(jù)存儲(chǔ)對(duì)象中的試題數(shù)量已經(jīng)不能滿足試卷的要求，當(dāng)R為0時(shí)，表示生成試卷

5184

3.1實(shí)驗(yàn)參數(shù)

通過(guò)測(cè)試混合遺傳模擬退火算法的性能，給出了兩個(gè)具體問(wèn)題的實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)環(huán)境是MathLab7.0模擬器和奔騰四2.8G/ 512M配置的電腦。在遺傳模擬退火算法實(shí)驗(yàn)中，我們?cè)O(shè)置的最大遺傳代數(shù)50，交叉概率為0.85，變異概率為0.005，懲罰因子1.2，退火初始溫度是1，溫度系數(shù)K為0.95。

3.2實(shí)驗(yàn)數(shù)據(jù)

作為遺傳算法的控制參數(shù)之一，群體規(guī)模的大小將影響遺傳算法的性能。我們?cè)趯?shí)驗(yàn)中設(shè)置的群體規(guī)模為：10,20,30,40,50,60, 70,80,90,100,120,150,180和200。相應(yīng)地，我們進(jìn)行了多次實(shí)驗(yàn)。其中兩次實(shí)驗(yàn)結(jié)果如圖1、圖2和圖3所示。圖表中的數(shù)據(jù)分別為10次試驗(yàn)的平均值。

圖3群體規(guī)模和算法平均耗時(shí)之間的關(guān)系

遺傳模擬退火算法中，染色體的長(zhǎng)度主要取決于解決問(wèn)題的精度要求。更高的精度和更長(zhǎng)的染色體，搜索空間更大。從這些數(shù)字中，我們可以看到，問(wèn)題數(shù)量增加，但搜索空間變得更大，而所耗費(fèi)的時(shí)間是有限的。仿真結(jié)果表明，遺傳模擬退火算法的收斂速度快，可以采取。

該文主要研究組卷生成算法的使用。通過(guò)對(duì)測(cè)試文件中的每個(gè)約束條件進(jìn)行仔細(xì)分析后，給出了一個(gè)新的基于遺傳模擬退火算法的智能組卷問(wèn)題的數(shù)學(xué)模型。試驗(yàn)結(jié)果證明，在論文中的算法是正確的，并為實(shí)際問(wèn)題提供了妥善解決的方法，它可廣泛應(yīng)用于教學(xué)活動(dòng)。