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

高 俊

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

0 引言

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

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

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

2 基于PBIL進(jìn)化算法組卷

2.1 算法的原理

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

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

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

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

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

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

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

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

6）對(duì)P進(jìn)行變異操作；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.4 組卷實(shí)現(xiàn)

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

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

3 結(jié)束語(yǔ)

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

［1］張小艷,龔尚福.ASP技術(shù)在網(wǎng)上考試系統(tǒng)中的應(yīng)用[J].西安科技學(xué)院學(xué)報(bào),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ā)與實(shí)現(xiàn)[J].中國(guó)地質(zhì)教育,2005（2）:32-34.

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

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

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

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

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

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