蘇小兵 李天平

山東師范大學(xué)傳播學(xué)院 濟(jì)南 250014

近年來(lái)，計(jì)算機(jī)技術(shù)和人工智能得到快速發(fā)展，隨著教育測(cè)量理論研究的不斷深入，基于遺傳算法組卷系統(tǒng)的研究與開發(fā)得到越來(lái)越多的專家學(xué)者的關(guān)注。本文從教學(xué)要求出發(fā)，結(jié)合項(xiàng)目反應(yīng)理論，以遺傳算法為基礎(chǔ)，提出基于項(xiàng)目反應(yīng)理論的數(shù)學(xué)模型。用此組卷算法實(shí)現(xiàn)的在線考試系統(tǒng)的數(shù)據(jù)表明，算法能夠有效解決自動(dòng)組卷問題，有效提高組卷的質(zhì)量和速度。

1 教育測(cè)量理論

試題庫(kù)是按照一定的教育測(cè)量理論利用計(jì)算機(jī)技術(shù)構(gòu)成的某學(xué)科試題的集合。目前常用的教育測(cè)量理論主要有兩種，一種是經(jīng)典測(cè)量理論（Classical Test Theory，CTT），另一種是項(xiàng)目反應(yīng)理論（Item Response Theory，IRT）。

項(xiàng)目反應(yīng)理論是克服經(jīng)典測(cè)量理論的各種局限性而發(fā)展起來(lái)的一種全新的測(cè)量學(xué)理論[1]。項(xiàng)目測(cè)量理論在20世紀(jì)50年代初正式確立，它的基本思想是：確定考生的心理特質(zhì)值和他們對(duì)于項(xiàng)目反映之間的關(guān)系，這種關(guān)系的數(shù)學(xué)形式就是“項(xiàng)目反映模型”。這種模型不是確定性模型，而是概率模型，其原因是考生對(duì)于測(cè)驗(yàn)項(xiàng)目的反映除了受到某種特定的“能力”的支配外，還受到許多隨機(jī)因素的影響，如焦慮、動(dòng)機(jī)、考試技能等。項(xiàng)目反映模型是表示考生能力和考生對(duì)考試項(xiàng)目正答概率之間關(guān)系的數(shù)學(xué)形式，主要有拉希模型、Logistic雙參數(shù)模型，還有探索使用的等級(jí)積分模型、分布評(píng)分模型等。

2 遺傳算法

遺傳算法（Genetic Algorithm，GA）是一類借鑒生物界的進(jìn)化規(guī)律（適者生存、優(yōu)勝劣汰遺傳機(jī)制）演化而來(lái)的隨機(jī)化搜索方法。它由美國(guó)的J.Holland教授于1975年首次提出[2]，其主要特點(diǎn)是直接對(duì)結(jié)構(gòu)對(duì)象進(jìn)行操作，不存在求導(dǎo)和函數(shù)連續(xù)性的限定，具有內(nèi)在的隱含并行性和更好的全局尋優(yōu)能力。采用概率化的尋優(yōu)方法，能自動(dòng)獲取和指導(dǎo)優(yōu)化的搜索空間，自適應(yīng)地調(diào)整搜索方向，不需要確定的規(guī)則。遺傳算法的這些性質(zhì)已被人們廣泛地應(yīng)用于組合優(yōu)化、機(jī)器學(xué)習(xí)、信號(hào)處理、自適應(yīng)控制和人工生命等領(lǐng)域，是現(xiàn)在有關(guān)智能計(jì)算的關(guān)鍵技術(shù)之一[3]。

以Holland1975年提出的稱為傳統(tǒng)的GA為例，簡(jiǎn)述它的主要步驟。

編碼：GA在進(jìn)行搜索之前先將解空間的解數(shù)據(jù)表示成遺傳空間的基因型串結(jié)構(gòu)數(shù)據(jù)，這些串結(jié)構(gòu)數(shù)據(jù)的不同組合便構(gòu)成不同的點(diǎn)。

初始群體的生成：隨機(jī)產(chǎn)生N個(gè)初始串結(jié)構(gòu)數(shù)據(jù)，每個(gè)串結(jié)構(gòu)數(shù)據(jù)稱為一個(gè)個(gè)體。N個(gè)個(gè)體構(gòu)成一個(gè)群體。GA以這N個(gè)串結(jié)構(gòu)數(shù)據(jù)作為初始點(diǎn)開始迭代。

選擇：選擇的目的是為了從當(dāng)前群體中選出優(yōu)良的個(gè)體，使它們有機(jī)會(huì)作為父代為下一代繁殖子孫。判斷個(gè)體優(yōu)良與否的標(biāo)準(zhǔn)是各自的適應(yīng)度值的大小。

交換：交換操作是遺傳算法中最主要的遺傳操作。通過交換操作可以得到新一代的個(gè)體，新個(gè)體組合了其父輩的個(gè)體特性。交換體現(xiàn)了信息交換的思想。

變異：變異首先在群體中隨機(jī)選擇一個(gè)個(gè)體，對(duì)于選中的個(gè)體以一定的概率隨機(jī)地改變串結(jié)構(gòu)數(shù)據(jù)中某個(gè)串的值。同生物界一樣，GA中變異發(fā)生的概率很低，通常取值在0.001～0.01。變異為新個(gè)體的產(chǎn)生提供了機(jī)會(huì)。

3 遺傳算法在在線考試系統(tǒng)中的應(yīng)用

基于IRT的組卷問題可以描述為一個(gè)最大化模型，此模型滿足測(cè)試條件的同時(shí)，匹配公式（1）中對(duì)目標(biāo)測(cè)驗(yàn)信息函數(shù)指定的形式，最大化測(cè)驗(yàn)信息函數(shù)[4]：

其中Xi表示試題是否被選進(jìn)試卷中。若被選中，Xi＝1；否則，Xi＝0。Ii是能力θk點(diǎn)的項(xiàng)目信息函數(shù)值，而rk是測(cè)驗(yàn)?zāi)繕?biāo)信息量，系數(shù)qin是題目i具有屬性n的參數(shù)值，Qn代表測(cè)驗(yàn)中包含屬性n的題目數(shù)。cim是題目i的類別決策值，即如果題目i屬于類別m則其值為l，否則為0。Cmn代表測(cè)驗(yàn)中允許包含的某一類別m的題目數(shù)范圍。而Lip是題目間約束關(guān)系的系數(shù)，Lp是約束邊界值。公式（1）用于表示題目之間的互斥或包含關(guān)系。

1）染色體編碼及初始種群的生成。染色體編碼就是對(duì)試題庫(kù)的某道題目進(jìn)行標(biāo)示，當(dāng)?shù)趇題被選中時(shí)，xi＝l；當(dāng)?shù)趇題未被選中時(shí)，xi＝0。初始化串群體就是隨機(jī)生成含有N個(gè)串的群體。在串群體中，串長(zhǎng)度都是相同的，群體大小根據(jù)需要給出，一般取個(gè)體編碼長(zhǎng)度數(shù)的一個(gè)線性倍數(shù)。

2）適應(yīng)度函數(shù)的確定。在遺傳算法中，適應(yīng)度函數(shù)的大小區(qū)分群體中個(gè)體的優(yōu)劣。通常，適應(yīng)度函數(shù)是通過目標(biāo)函數(shù)轉(zhuǎn)化而來(lái)，其值越大個(gè)體越好。通過對(duì)公式（1）的分析，適應(yīng)度函數(shù)定義為：

其中對(duì)于函數(shù)t(x)，當(dāng)x＞0時(shí)，函數(shù)值為x；當(dāng)x≤0時(shí)，函數(shù)值為0。

3）遺傳操作。選擇：常用的選擇算法為按比例的適應(yīng)度分配，主要包括繁殖池選擇、輪盤賭選擇等方法。本文采用的選擇算法是輪盤賭算法。交換：交換又叫基因重組，對(duì)于不同的編碼方式，交換算子是不同的。本文采用的是二進(jìn)制編碼的單點(diǎn)式交換算子，即在兩個(gè)父代個(gè)體上隨即產(chǎn)生一個(gè)交換點(diǎn)，再間接交換兩個(gè)父代個(gè)體的對(duì)應(yīng)片段，從而得到兩個(gè)子代個(gè)體。變異：變異是遺傳算法中保持物種種群多樣性的重要途徑。在二進(jìn)制編碼中就是將隨機(jī)選擇出來(lái)的基因座上的基因值由1變0，由0變1。

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

本文以項(xiàng)目反應(yīng)理論為理論基礎(chǔ)，使試題本身的參數(shù)與考生樣本無(wú)關(guān)，測(cè)試更加真實(shí)，評(píng)價(jià)更加合理。將遺傳算法應(yīng)用于在線考試系統(tǒng)，實(shí)現(xiàn)試題庫(kù)的自動(dòng)組卷，有效地提高組卷的質(zhì)量和速度。

[1]余嘉元.教育和心理測(cè)量[M].南京:江蘇教育出版社,1987

[2]Holland J. Adaptation in Natural and Artificial Systems[M].Ann Arbor: University of Michigan Press,1975

[3]張文修,梁怡.遺傳算法的數(shù)學(xué)基礎(chǔ)[M].西安:西安交通大學(xué)出版社,2000

[4]董敏,霍劍青,王曉蒲.基于IRT智能組卷的模型管理系統(tǒng)[J].中國(guó)科學(xué)技術(shù)大學(xué)學(xué)報(bào),2004,10(5):612-617