網(wǎng)絡(luò)考試系統(tǒng)中基于遺傳算法的數(shù)據(jù)庫設(shè)計(jì)研究

摘 要：互聯(lián)網(wǎng)已經(jīng)成為21世紀(jì)最重要的信息交互平臺，更多的終端設(shè)備如計(jì)算機(jī)、智能手機(jī)、平板電腦等都可入網(wǎng)，傳統(tǒng)以紙質(zhì)試卷為主的考試手段費(fèi)時(shí)耗力，其劣勢逐漸顯現(xiàn)，那么就需要新的考試平臺來分享互聯(lián)網(wǎng)平臺高速發(fā)展帶來的成果。隨著教育信息化的不斷普及，利用先進(jìn)的網(wǎng)絡(luò)和計(jì)算機(jī)技術(shù)，網(wǎng)絡(luò)考試系統(tǒng)自然得到長足發(fā)展。而網(wǎng)絡(luò)考試系統(tǒng)中最重要的環(huán)節(jié)就是利用遺傳算法進(jìn)行自動組卷。網(wǎng)絡(luò)考試系統(tǒng)中數(shù)據(jù)庫平臺的設(shè)計(jì)是否適合遺傳算法的實(shí)際需要，并且同時(shí)要保證數(shù)據(jù)的獨(dú)立性、完整性和高共享性，值得我們?nèi)ヌ接憽?/p>

關(guān)鍵詞：網(wǎng)絡(luò)考試系統(tǒng)；組卷；遺傳算法（GA）；數(shù)據(jù)庫設(shè)計(jì)

中圖分類號：TP311.52

1 遺傳算法的簡單介紹

遺傳算法（Genetic Algorithm，縮寫為GA）是模擬生物在自然環(huán)境中的遺傳和進(jìn)化過程而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法。它能夠模擬生命進(jìn)化機(jī)制進(jìn)行并行、智能全局隨機(jī)搜索。遺傳算法可以使用簡明的代碼和“繁殖機(jī)制”進(jìn)行說明繁雜的情況，不會影響對具體問題的闡述，比較適合使用到那些其它搜索方法難于解決的繁雜及優(yōu)化組合問題。遺傳算法的主要應(yīng)用領(lǐng)域如下圖1：

圖1

2 遺傳算法的進(jìn)化過程

在自然界中，經(jīng)過染色體間的交叉和變異，促進(jìn)了生物進(jìn)化，與之相類似，遺傳編程算法是通過遺傳算子間的選擇、交叉和變異操作來達(dá)到實(shí)現(xiàn)最優(yōu)解的搜索過程。經(jīng)過實(shí)際操作，一個(gè)新群體G（t+1）就會通過遺傳從老群體G（t）繼承相關(guān)屬性優(yōu)化生成。具體步驟如下：

2.1 編碼。解決遺傳算法組卷的首要問題是編碼，利用編碼將問題的解空間映射到GA算法的編碼空間。說簡單點(diǎn)，是對遺傳算法的搜索目標(biāo)的表示。遺傳算法的特長就是，可對問題可行解的個(gè)體編碼進(jìn)行選擇、交叉、變異的遺傳運(yùn)算。最終達(dá)到最優(yōu)化結(jié)果。編碼的不同形式對遺傳動作的操作效率有著直接的影響?，F(xiàn)在用的比較多的是分段整數(shù)編碼方案，也就是說，把一類相似題歸為一個(gè)段，每類型段的編碼是獨(dú)立的，每種題型只能在本編碼段進(jìn)行遺傳操作，這樣就形成了以題號作為基因組成染色體用于分段整數(shù)編碼的遺傳算法，沒有編碼和解碼的情況，可以很大程度上降低了搜索的復(fù)雜度，提高了目標(biāo)卷的生成效率。另一種是采用傳統(tǒng)的二進(jìn)制編碼，雖然存在時(shí)間復(fù)雜度大，編碼和編碼過程復(fù)雜，并容易出現(xiàn)早熟等問題，但它有操作簡單、易于實(shí)現(xiàn)的等優(yōu)點(diǎn)。具體來說，一份試卷看作一個(gè)染色體，該染色體由多個(gè)試題基因組成。試題的數(shù)量就是該試卷的染色體的長度。

2.2 初始化種群。要求從試題庫中選出符合條件的試題組成的種群的過程就是種群初始化，亦即染色體初始化。種群的大小一般是靠經(jīng)驗(yàn)和估值來定，合理設(shè)置種群規(guī)模的大小，能夠充分體現(xiàn)遺傳算法的優(yōu)點(diǎn)所在。如果種群過少，表示的樣本就越少，就不能搜索到很精確的解，很可能就不能滿足實(shí)際需求。所以，種群規(guī)模也要合理設(shè)置，找到一個(gè)平衡點(diǎn)。

2.3 染色體適應(yīng)值計(jì)算。染色體初始化后，要進(jìn)行評估和計(jì)算，即看看這些染色體是否達(dá)到目標(biāo)要求。我們可以先利用計(jì)算公式2-1得到個(gè)體的適應(yīng)度 （適應(yīng)度大小可以區(qū)分群體中個(gè)體的優(yōu)劣），最終得到終卷指標(biāo) 。

（式2-1）

對于我們組卷過程來說，選用合適的適應(yīng)度函數(shù)來判斷某試卷染色體是否已經(jīng)滿足用戶的需求，具體參數(shù)一般為：總分值，難易度，知識點(diǎn)覆蓋率等，如果試卷個(gè)體的適應(yīng)度函數(shù)值較大，表示試卷個(gè)體接近組卷目標(biāo)。

2.4 選擇（selection）操作。根據(jù)個(gè)體適應(yīng)度值，按照要求，把迭代多次的優(yōu)良個(gè)體向下一代群體遺傳。

2.5 交叉（crossover）操作。為了得到更多優(yōu)質(zhì)的遺傳個(gè)體，就把每個(gè)個(gè)體隨機(jī)組合，以一定的交叉概率進(jìn)行交換部分染色體，會形成新的優(yōu)良個(gè)體。

2.6 變異（mutation）操作。同樣為了得到更多優(yōu)質(zhì)的遺傳個(gè)體，以一定的變異概率改變某個(gè)體的部分基因位的值就完成了變異。

總的來說，遺傳算法的過程是先對群體初始化；然后，迭代未結(jié)束前對染色體進(jìn)行適應(yīng)值得評估和計(jì)算、選擇、交叉以及變異，最后生成新的高質(zhì)量的染色體群體，完成遺傳操作過程。

3 數(shù)據(jù)庫設(shè)計(jì)

自動組卷過程中，遺傳算法的首要任務(wù)是對染色體編碼，試題就是基因，當(dāng)題庫的試題越多，組卷操作時(shí)間和空間復(fù)雜度就越高。試題庫的屬性越多，組卷難度更高，運(yùn)行效率就相對低。所以數(shù)據(jù)庫的最終設(shè)計(jì)是否滿足和適應(yīng)遺傳算法的需要，就要充分考慮到平衡度的把握，盡量精簡試題記錄數(shù)量，合理控制試題屬性個(gè)數(shù)。具體設(shè)計(jì)準(zhǔn)則如下：

3.1 數(shù)據(jù)庫設(shè)計(jì)說明書和命名規(guī)范。精細(xì)制作數(shù)據(jù)庫設(shè)計(jì)說明書，進(jìn)一步強(qiáng)化命名規(guī)范。在數(shù)據(jù)字典設(shè)計(jì)中反映出數(shù)據(jù)庫相關(guān)的各種標(biāo)識。

3.2 數(shù)據(jù)庫建模。實(shí)體關(guān)系中，建模中數(shù)據(jù)的整合方式一般有三種，即以屬性聚集的方式、面向?qū)ο蟪橄髮傩院唾N源方式。在考試系統(tǒng)中建議采用以屬性聚集方式來建模，其優(yōu)點(diǎn)為穩(wěn)定性好、減少大量的數(shù)據(jù)冗余。

（1）實(shí)體關(guān)系的建立。如果題庫由多種題型組成，在建立關(guān)系的時(shí)候，一類試題就對應(yīng)一個(gè)關(guān)系，并且主、客試題分開。這樣可以避免出現(xiàn)大量重復(fù)的屬性。提煉核心屬性，一般的考試系統(tǒng)常見核心屬性有：題號、題目內(nèi)容、所屬課程編號、知識點(diǎn)、難度系數(shù)、分值等。（2）試題庫的建立。建議按照試題類型獨(dú)立建立試卷題庫，在生成試卷過程中，采用分步完成，如依次生成單選題T1、多選題T2、程序改錯(cuò)題T3、簡單題T4和綜合題T5，最后進(jìn)行組合T=T1+T2+T3+T4+T5。這樣一份完整的目標(biāo)卷就可以得到。

4 結(jié)束語

經(jīng)過實(shí)踐經(jīng)驗(yàn)和跟蹤測試，按照此原則設(shè)計(jì)的數(shù)據(jù)庫，在遺傳算法的操作過程中表現(xiàn)穩(wěn)定，生成目標(biāo)卷的成功率和時(shí)間效率大大提高。

參考文獻(xiàn)：

[1]賈兆紅.一種基于混合遺傳算法的聚類方法[J].計(jì)算機(jī)應(yīng)用軟件，2008，25（4）：82-85.

[2]William A shay.Understanding Data Communications and Networks[M].Physician Law Weekly，2005，5（3）：226-228.

[3]賈海龍.智能組卷考試系統(tǒng)的研究與實(shí)現(xiàn)[D].北京工業(yè)大學(xué)，2010.

[4]陸億紅，柳紅.基于整數(shù)編碼和自適應(yīng)遺傳算法的自動組卷[J].計(jì)算機(jī)工程，2005（12）：1-3.

作者簡介：程開固（1975.11-），男，實(shí)驗(yàn)師，碩士，從事計(jì)算機(jī)方面實(shí)踐實(shí)習(xí)教學(xué)多年；潘慧（1979.1-），女，實(shí)驗(yàn)師，碩士，從事計(jì)算機(jī)方面實(shí)踐實(shí)習(xí)教學(xué)多年。

作者單位：武昌理工學(xué)院，武漢 430223