PBIL進化算法在考試系統(tǒng)中的應(yīng)用

高 俊

（江西冶金職業(yè)技術(shù)學(xué)院 江西 新余 338000）

0 引言

隨著計算機應(yīng)用的迅猛發(fā)展，人們迫切要求利用現(xiàn)代信息技術(shù)來進行在線考試。在線考試系統(tǒng)極大地提高了教學(xué)的靈活性，它在許多領(lǐng)域已經(jīng)有了廣泛的應(yīng)用。現(xiàn)階段在線考試系統(tǒng)種類繁多，但目前已有的網(wǎng)上考試系統(tǒng)題型單一，沒有真正通用的集自動組卷、在線答卷、自動評卷、成績管理與統(tǒng)計分析、題庫管理、用戶管理、記錄查詢、在線審批于一體的綜合考試系統(tǒng)，為了積極適應(yīng)新形勢的發(fā)展和信息網(wǎng)絡(luò)化的發(fā)展趨勢，科學(xué)有效地利用信息網(wǎng)絡(luò)的資源和技術(shù)優(yōu)勢，開發(fā)一個在線考試系統(tǒng)是非常必要和可行的。

1 國內(nèi)外研究現(xiàn)狀

目前大多數(shù)考試系統(tǒng)的系統(tǒng)結(jié)構(gòu)：比較流行的是C/S結(jié)構(gòu)和B/S結(jié)構(gòu)。

C/S結(jié)構(gòu)，即Client/Server(客戶機/服務(wù)器)結(jié)構(gòu)。它通過將任務(wù)合理分配到Client端和Server端，降低了系統(tǒng)的通訊開銷。這種結(jié)構(gòu)的考試系統(tǒng)要求在服務(wù)器和客戶端單機上都安裝考試應(yīng)用軟件，客戶端軟件具有考題的顯示，考試計時及與服務(wù)器通信聯(lián)絡(luò)等功能。服務(wù)器端軟件則負(fù)責(zé)維護題庫、抽取試題及考后的閱卷、成績的收取、統(tǒng)計、匯總等工作。考生在單機上參加考試，考試結(jié)果被系統(tǒng)收集到服務(wù)器中的指定目錄下。

B/S結(jié)構(gòu)，即Browser/Server(瀏覽器／服務(wù)器)結(jié)構(gòu)。該結(jié)構(gòu)的核心是WEB服務(wù)器，它負(fù)責(zé)接收瀏覽器的WEB頁請求和數(shù)據(jù)請求，并處理WEB頁請求，同時將數(shù)據(jù)請求通過數(shù)據(jù)庫接口程序轉(zhuǎn)換成數(shù)據(jù)庫服務(wù)器能夠接受的形式，之后送到數(shù)據(jù)庫服務(wù)器，數(shù)據(jù)庫服務(wù)器執(zhí)行相應(yīng)的數(shù)據(jù)庫操作，并將結(jié)果通過數(shù)據(jù)庫接口程序的轉(zhuǎn)換送回WEB服務(wù)器，WEB服務(wù)器將結(jié)果處理成瀏覽器能夠接受的形式后，送回發(fā)出請求的瀏覽器，顯示結(jié)果。

2 基于PBIL進化算法組卷

2.1 算法的原理

PBIL算法基本原理[2]：設(shè)定S代表解的二進制編碼，其長度為N，第 i個基因位 si(1≤i≤N)的取值為 0 或 1，P＝(p1,p2,p3,……,pn)代表一個N維的概率向量(Probability Victor)，向量中各元素表示當(dāng)前種群中的個體在對應(yīng)基因位上不同取值時的學(xué)習(xí)概率；對于二進制編碼的情況，pi(1≤i≤N)代表第i個基因位取值為1時的學(xué)習(xí)概率；r是算法的學(xué)習(xí)速率(Learning Rate)，M是種群規(guī)模。初始概率Pini中學(xué)習(xí)概率pi，大小都為0.5，即各基因位上取值為0或1的機會均等。

為了防止學(xué)習(xí)概率過早地收斂到0或1附近而產(chǎn)生早熟現(xiàn)象，在每一代對學(xué)習(xí)概率修正后，再按變異率P隨機地選擇部分學(xué)習(xí)概率pi進行調(diào)整，rm是變異速率(Mutate shift)。算法的處理流程[2]如下：

1）初始化學(xué)習(xí)概率 P：pi=0.5(1≤i≤N)；

2）由學(xué)習(xí)概率P指導(dǎo)隨機產(chǎn)生M個個體；

3）計算機由2）產(chǎn)生的M個個體的目標(biāo)函數(shù)值；

4）根據(jù)3）計算的目標(biāo)函數(shù)值找出其中一個最優(yōu)解：fitness；

5）用4）找到的最優(yōu)解fitness修正學(xué)習(xí)概率P，修正方法如下：

pi=pi+(fitnessi-pi)×δ(δ 為修正常數(shù)，1≤i≤N)；

6）對P進行變異操作；

7）返回2），直到滿足結(jié)束條件為止。

2.2 試卷結(jié)構(gòu)分析

一份試卷一般涉及到總分、試題類型、試題類型分值、難度系數(shù)、各知識點分?jǐn)?shù)分布等因素。以《C語言程序設(shè)計》為例，試題類型可分為填空題、選擇題、程序填空題、寫出程序運行結(jié)果和編程題。一般將難度劃分為個4個等級(1,2,3,4級)。組卷算法就在以下幾個方面盡可能接近目標(biāo)值：

（1）試卷的總分應(yīng)等于用戶設(shè)定的總分，即：

其中n為試卷的題目總數(shù)，yi為第i個題目的分?jǐn)?shù)，M為用戶設(shè)定的試卷總分。

（2）各題型的總分之和應(yīng)等于試卷的總分，即：

其中n為題型的總數(shù)，fi為第i個題型的分值，F(xiàn)為用戶設(shè)定的試卷總分。

（3）試卷中同類知識點分?jǐn)?shù)之和應(yīng)等于用戶要求的分?jǐn)?shù)，即：

其中n為第k個知識點在試卷中的題目數(shù)量，zi為第k個知識點第i個題目的分?jǐn)?shù)，Zk為用戶設(shè)定的第k個知識點的分?jǐn)?shù)，m為知識點的個數(shù)。

（4）各題型的分?jǐn)?shù)應(yīng)等于用戶設(shè)定的分?jǐn)?shù)，即：

其中n為第j個題型的題目總數(shù)，li為第j個題型中第i個題目的分?jǐn)?shù)，Lk為用戶設(shè)定的第k個題型的分?jǐn)?shù)，m為題型總數(shù)。

（5）各題型的難度系數(shù)應(yīng)等于用戶設(shè)定的難度系數(shù)，即：

其中n為第j個題型的題目總數(shù)，si為第j個題型中第i個題目的難度系數(shù)，fi為對應(yīng)的分值，Sk為用戶設(shè)定的第k個題型的難度，m為題型總數(shù)。

2.3 目標(biāo)函數(shù)

現(xiàn)用指標(biāo)x1,x2,x3,x4,x5分別表示上述5項目標(biāo)值。則可知，當(dāng)x1,x2,x3,x4,x5越大時，說明目標(biāo)值與用戶要求的值相差越大；當(dāng)x1,x2,x3,x4,x5越小時，說明目標(biāo)值與用戶要求的值相差越小；當(dāng)x1,x2,x3,x4,x5等于0時，說明目標(biāo)值與用戶要求的值相等。再設(shè)各項指標(biāo)的權(quán)重為：d1,d2,d3,d4,d5，它們反映對上述各項指示的重要程度。所以 f=x1×d1+x2×d2+x3×d3+x4×d4+x5×d5表示整份試卷所有指示與用戶要求的指示的相差程度。

下面定義各項指示的目標(biāo)函數(shù)：

其中n為題目總分，yi為第i個題目的分?jǐn)?shù)，M為用戶設(shè)定的試卷總分a表示算法生成的最大誤差。

其中n為題型的道數(shù)，fi為第i個題型的分值，F(xiàn)為用戶設(shè)定的試卷總分，b表示算法生成題型的最大誤差。

其中m為知識點的個數(shù)，n為第k個知識點在試卷中的題目數(shù)量，zi為第k個知識點在第i個題目的分?jǐn)?shù)，Zk為設(shè)定的第k個知識點的分?jǐn)?shù)，c表示算法生成的每個知識點分?jǐn)?shù)的最大誤差之和。

其中m為總題型數(shù)，n為第j個題型的題目總數(shù)，li為第j個題型中第i個題目的分?jǐn)?shù)，Lj為設(shè)定的第j個題型的分?jǐn)?shù)，d表示算法生成的每個題型分?jǐn)?shù)的最大誤差之和。

其中m為總題型數(shù)，n為第j個題型的題目總數(shù)，si為第j個題型中第i個題目的難度系數(shù)，fi為對應(yīng)的分值，Sj為設(shè)定的第j個題型的難度，e表示算法生成的每個題型難度系數(shù)的最大誤差之和。綜上所述，對于一個有M個個體，則總體目標(biāo)函數(shù)表示為：

其中，i∈[1,M]，M為種群規(guī)模，x1,x2,x3,x4,x5由以上目標(biāo)函數(shù)決定，d1,d2,d3,d4,d5為該項指標(biāo)的權(quán)重因子。

2.4 組卷實現(xiàn)

題庫中可以選取的試題的數(shù)量作為基因鏈的長度L，編碼方式采用二進制編碼方式。現(xiàn)假設(shè)題庫中有N道各種題型的試題，則L的長度就等于N，Li等于0時表示題庫中第i題未選中，Li等于1時表示題庫中第i題選中，其中1≤i≤N。

算法實現(xiàn)如下：

3 結(jié)束語

本設(shè)計是以《C語言程序設(shè)計》為例，介紹了PBIL進化算法在考試系統(tǒng)中的應(yīng)用。實現(xiàn)的考試可以加強規(guī)范性，提高質(zhì)量，減少組織考試工作的工作量，簡化工作手續(xù)。

［1］張小艷,龔尚福.ASP技術(shù)在網(wǎng)上考試系統(tǒng)中的應(yīng)用[J].西安科技學(xué)院學(xué)報,2002,22(l):53-55.

［2］Baluja S.Genetic Algorithms and Explicit Search Statistics.In:IEEE.Advances in Neural Information Processing System.MA:MIT Press.

［3］曹麗文,楊靜.“基礎(chǔ)工程與施工”網(wǎng)上考試系統(tǒng)的開發(fā)與實現(xiàn)[J].中國地質(zhì)教育,2005（2）:32-34.

［4］吉根林,崔海源.ASP.NET程序設(shè)計教程[M].北京:電子工業(yè)出版福,2004.

［5］胡勇輝,扶玉坤,張陽戩.ASP.NET基礎(chǔ)教程與上機指導(dǎo)[M].北京:清華大學(xué)出版社,2005.

［5］周紅曉.遺傳算法在試題庫智能組卷中的應(yīng)用[J].浙江師范大學(xué)學(xué)報：自然科版,2003,26(4):374-378.

［6］樓玉萍,金炳堯,駱紅波.PBIL進化算法在自動組卷系統(tǒng)中的應(yīng)用[J].計算機技術(shù)與發(fā)展,2006,16(6):81-82.

［7］袁鋒.遺傳算法在自動組卷系統(tǒng)中的應(yīng)用[J].山東師范大學(xué)學(xué)報：自然科學(xué)版,2006,21(1):53-56.

［8］劉衛(wèi)忠,徐重陽,薔薇.多層客戶機/服務(wù)器結(jié)構(gòu)分析[J].華中理工大學(xué)學(xué)報：自然科學(xué)版,2000,1.