考試系統(tǒng)中的組卷算法

5考試系統(tǒng)中的組卷算法5.1遺傳算法概述5.1.1遺傳算法的基本概念遺傳算法(GeneticAlgorithm.GA)是模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進(jìn)化過程的計(jì)算模型，是一種通過模擬自然進(jìn)化過程搜索最優(yōu)解的方法【27】。所以，遺傳算法吸取了自然界中“適者生存，優(yōu)勝劣汰''的進(jìn)化理論，為解決許多傳統(tǒng)的優(yōu)化方法難以解決的優(yōu)化問題提供了新的途徑。由于遺傳算法的整體搜索策略和優(yōu)化搜索方法在計(jì)算中不依賴于梯度信息或其他輔助知識(shí)，而只需要影響搜索方向的目標(biāo)函數(shù)和相應(yīng)的適應(yīng)度函數(shù)，所以遺傳算法提供了一種求解復(fù)雜系統(tǒng)問題的通用框架，它不依賴于問題的具體領(lǐng)域，對(duì)問題的種類有很強(qiáng)的魯棒性。如今，遺傳算法不論是在算法設(shè)計(jì)上還是在基礎(chǔ)理論上，均己取得了長足的發(fā)展，已成為信息科學(xué)、計(jì)算機(jī)科學(xué)、運(yùn)籌學(xué)和應(yīng)用數(shù)學(xué)等諸多學(xué)科所共同關(guān)注的熱點(diǎn)研究領(lǐng)域【281。遺傳算法作為一種概率搜索算法，借鑒了生物學(xué)中自然選擇和遺傳機(jī)制的高度并行、隨機(jī)、自適應(yīng)的性質(zhì)，它利用某種編碼技術(shù)作用于被稱作染色體的二進(jìn)制數(shù)據(jù)串，其基本思想是模擬由這些染色體組成的群體進(jìn)化過程。由于遺傳算法是由進(jìn)化論和遺傳學(xué)理論相結(jié)合而產(chǎn)生的直接搜索優(yōu)化算法【291，因此，在遺傳算法中也借鑒了許多生物學(xué)中的術(shù)語。個(gè)體(Individual):也稱基因型個(gè)體，個(gè)體是遺傳過程中帶有遺傳特征的實(shí)體，也是遺傳算法中的所處理基本對(duì)象和結(jié)構(gòu)?；?Gene):基因是攜帶遺傳信息的基本單位，用于表示個(gè)體的特征。位串(String)：與遺傳學(xué)中的染色體的概念相對(duì)應(yīng)，是個(gè)體的表現(xiàn)形式。種群(Population):一定數(shù)量的個(gè)體的集合叫做種群。群體規(guī)模(PopulationSize)：在群體中個(gè)體的數(shù)量稱為群體大小。適應(yīng)度(Fitness)：適應(yīng)度表示某一個(gè)體對(duì)于生存環(huán)境的適應(yīng)程度，對(duì)于生存環(huán)境適應(yīng)程度較高的個(gè)體將獲得更多的繁殖機(jī)會(huì)，而對(duì)生存環(huán)境適應(yīng)程度較低的物種，其繁殖的機(jī)會(huì)就會(huì)相對(duì)減少，甚至逐漸滅絕。遺傳操作(GeneticOperation):遺傳算法是一種群體型操作，該操作以群體中的所有個(gè)體為對(duì)象。遺傳操作由選擇(Selection)、交叉(Crossover)和變異(Mutation)三個(gè)基本操作算子組成。選擇：根據(jù)遺傳學(xué)的理論，對(duì)生存環(huán)境適應(yīng)程度較高的物種遺傳到下一代的機(jī)會(huì)相對(duì)較高。所以在遺傳算法中，應(yīng)用選擇算子對(duì)群體中的個(gè)體進(jìn)行優(yōu)勝劣汰操作，父代中適應(yīng)度較高的個(gè)體被遺傳到子代群體中的概率較大，而適應(yīng)度較低的被遺傳到子代群體中的概率較小。交叉：遺傳算法中的交叉算子使得在原始群體中的優(yōu)良個(gè)體的特性能夠在一定程度上繼續(xù)得到保持，而另一方面，又使得算法能夠探索新的基因空間，使新的群體中的個(gè)體更加多樣性。變異：變異算子能夠?qū)θ后w中個(gè)體串的某些基因位置上的基因值作變動(dòng)。遺傳算法中，變異算子的應(yīng)用使得算法具有了局部的隨機(jī)搜索能力，并且可以使遺傳算法始終維持群體的多樣性。5.1.2遺傳算法的流程遺傳算法的運(yùn)行過程是一種的典型的迭代過程，遺傳算法在整個(gè)進(jìn)化過程中的遺傳操作是隨機(jī)的，但是算法能夠有效地利用歷史信息來預(yù)測(cè)下一代期望性能有所提高的尋優(yōu)點(diǎn)集。所以，在這一不斷進(jìn)化的過程中，群體中的個(gè)體地得以逐代優(yōu)化，并逐漸地收斂到一個(gè)最適應(yīng)環(huán)境的個(gè)體上面，即獲得最優(yōu)解。以下為遺傳算法的一般流程。選擇編碼策略，將參數(shù)集合轉(zhuǎn)換成位串結(jié)構(gòu)空間。定義適應(yīng)度函數(shù)和遺傳策略，并計(jì)算交叉概率、變異概率等遺傳參數(shù)。采用隨機(jī)初始化的方式生成初始群體。計(jì)算群體中的個(gè)體在通過位串編碼后的適應(yīng)度函數(shù)值。依據(jù)設(shè)定好的遺傳控制參數(shù)，使選擇、交叉和變異算子作用于群體，產(chǎn)生下一代的群體。迭代執(zhí)行，直到群體性能滿足需要。根據(jù)算法的流程，在遺傳算法的運(yùn)行過程中，對(duì)自變量的編碼、初始群體的設(shè)定、適應(yīng)度函數(shù)的設(shè)計(jì)、遺傳操作(選擇、交叉和變異)、遺傳控制參數(shù)(包括群體規(guī)模、執(zhí)行遺傳操作的概率等)的設(shè)定是遺傳算法中的核心內(nèi)容。5.2基于遺傳算法的組卷算法一份高質(zhì)量的試卷，應(yīng)該在題型、難度、區(qū)分度和知識(shí)點(diǎn)分布等各項(xiàng)指標(biāo)之間達(dá)到相對(duì)平衡。并能夠最大程度滿足用戶要求。所以，組卷問題實(shí)際上是一個(gè)復(fù)雜的多目標(biāo)組合優(yōu)化問題，問題的求解精度越高，表明試卷質(zhì)量越好【301。而傳統(tǒng)的組卷方法往往很難解決這個(gè)問題，甚至很難描述這樣復(fù)雜的帶約束優(yōu)化的問題。因此，選用一種合理組卷方法，可以保證系統(tǒng)自動(dòng)生成的試卷能最大程度地滿足出題者對(duì)試卷的需要，并使試基于遺傳算法的考試系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)卷具有較高的隨機(jī)性、科學(xué)性和合理性。此外，在對(duì)響應(yīng)速度要求較高的網(wǎng)絡(luò)交互環(huán)境下，算法的效率也是自動(dòng)組卷的關(guān)鍵。在考試系統(tǒng)進(jìn)行自動(dòng)組卷的時(shí)候，首先要將難度、知識(shí)點(diǎn)等相對(duì)模糊的要求進(jìn)行量化，轉(zhuǎn)化成計(jì)算機(jī)可以理解的要求，然后依據(jù)組卷算法從試題庫中抽取一定數(shù)量并且滿足要求的題目組成試卷。5.2.1組卷算法的數(shù)學(xué)模型組卷問題的數(shù)學(xué)模型是組卷算法的基礎(chǔ)。因此需要在分析組卷問題的基礎(chǔ)上建立一。個(gè)性能優(yōu)良的數(shù)學(xué)模型。對(duì)于自動(dòng)組卷功能來說，其要求實(shí)現(xiàn)的是通過獲取用戶的對(duì)試卷需求信息后，建立相應(yīng)的試卷模式，然后根據(jù)該試卷模式建立組卷算法的數(shù)學(xué)模型。用戶的需求對(duì)組卷系統(tǒng)來說是一種模糊的約束，因此，首先需要把這些模糊的約束量化成具體的并且能夠被計(jì)算機(jī)識(shí)別的量化指標(biāo)。考試系統(tǒng)中的所有試題都被存放在試題庫中，而題目本身也有其固定的屬性，試題各項(xiàng)屬性的確定能夠直接影響到組卷系統(tǒng)的準(zhǔn)確性和效率。試題的屬性指標(biāo)定量地描述了每一道試題的內(nèi)在屬性、外部特征以及它在考試測(cè)試中的功能，是計(jì)算機(jī)進(jìn)行自動(dòng)抽題組卷的基礎(chǔ)。在組卷前，首先要給定的試卷的相關(guān)約束條件，例如卷面分?jǐn)?shù)、難度系數(shù)、區(qū)分度以及不同題型、能力層次和知識(shí)點(diǎn)的題目所占比例等，并據(jù)其從大量的試題庫中抽取出最優(yōu)的試題組合。所以，用q代表題目的分值，a：代表題目難度，q代表能力層次，口。代表題目所考察的知識(shí)點(diǎn)、a。代表題目的區(qū)分度，a。代表題型。那么，組成一份總共有彤道試題的試卷，如果每道試題有n項(xiàng)屬性，就相當(dāng)于構(gòu)建了一個(gè)肌X刀的目標(biāo)矩陣S。S=alla12a21a22amlam2口椰(5.1)目標(biāo)矩陣S其實(shí)是一個(gè)問題求解的目標(biāo)狀態(tài)矩陣，且目標(biāo)狀態(tài)不是惟一的。目標(biāo)矩陣應(yīng)滿足以下的約束條件【31】：試卷總分為Z：%%一z=Z研，(5.2)試卷難度系數(shù)為D：D=Z□,,口,：//!口訂(5.3)?.一”。'?-一”Z。為第P教學(xué)要求的分?jǐn)?shù)，教學(xué)要求(了解、理解、掌握、應(yīng)用)和所占分?jǐn)?shù)由用戶給定，即教學(xué)要求約束。m中C3j--｛：)麓1二；Zp-Ec,,口，，(5.4),=1試卷區(qū)分度為Q：Q二睜％檐％\j=1//,=1c5,乙為第g種題型的分?jǐn)?shù)，其中氣，二0聊乙二￡c6,%。,=1c6,乙為第辦知識(shí)點(diǎn)的分?jǐn)?shù)，其中c4,=0：二i：；(5.5)(5.6)Zh=￡c。，口，。(5.7)i--I5.2.2組卷算法的設(shè)計(jì)在考試系統(tǒng)中，采用了基于遺傳算法的組卷算法。遺傳算法的幾個(gè)主要特點(diǎn)，如直接對(duì)結(jié)構(gòu)對(duì)象進(jìn)行抽象，不存在求導(dǎo)和函數(shù)連續(xù)性的限定；具有內(nèi)在的隱并行性和更好的全局尋優(yōu)能力；采用導(dǎo)向式概率化的尋優(yōu)方法，能自動(dòng)獲取和指導(dǎo)優(yōu)化的搜索空間；自適應(yīng)地高速搜索方向，并且不需要確定規(guī)則等都適宜于處理自動(dòng)組卷的問題。但是傳統(tǒng)的遺傳算法首先生成?定規(guī)模的初始群體，然后使其中的個(gè)體以一定的概率進(jìn)行交叉與變異，實(shí)現(xiàn)個(gè)體結(jié)構(gòu)的重組，再按預(yù)定的評(píng)價(jià)函數(shù)選擇復(fù)制優(yōu)秀個(gè)體，組成新的一代，如此循環(huán)迭代，以期最終找到滿足尋優(yōu)條件的全局最優(yōu)解。但是，這樣的算法存在著越道搜索后期效率越低下，并且容易產(chǎn)生末成熟即收斂的情況。針對(duì)系統(tǒng)自動(dòng)組卷的具體情況，本文主要從適應(yīng)度函數(shù)、初始種群、控制參數(shù)等幾個(gè)方面對(duì)遺傳算法加以改進(jìn)，使其能夠很好滿足各項(xiàng)組卷需求。初始種群初始種群的特性對(duì)遺傳算法的計(jì)算結(jié)果和計(jì)算效率均有重要影響，算法要實(shí)現(xiàn)全局最優(yōu)，初始種群在解空間中應(yīng)該盡量分散。而在傳統(tǒng)遺傳算法中，初始種群是隨機(jī)產(chǎn)生的，所以，為了加快遺傳算法的收斂并減少迭代次數(shù)，初始種群的生成要滿足題型、題量和試卷總分的要求，這樣能夠有效提高求解速度。適應(yīng)度函數(shù)在遺傳算法中，采用適應(yīng)度函數(shù)值是來評(píng)判群體中的個(gè)體優(yōu)劣，一般情況下，適應(yīng)度函數(shù)值越大的個(gè)體越好，即表示這個(gè)試題的組合的各項(xiàng)約束條件越接近用戶指定的理想值。適應(yīng)度函數(shù)值是遺傳算法進(jìn)行優(yōu)化所用的主要信息，它與個(gè)體的目標(biāo)值存在一種對(duì)應(yīng)關(guān)系。遺傳算法科用適應(yīng)度值這一信息來指導(dǎo)搜索方向，根據(jù)約束條件，建立目標(biāo)函數(shù)為誤差函數(shù)，另外，根據(jù)實(shí)際組卷經(jīng)驗(yàn)，對(duì)不同的約束條件可給定不同的允許誤差(0.01〃-.，0.05)，只要試卷個(gè)體滿足第i項(xiàng)組卷要求的誤差在容差范圍內(nèi)，即可認(rèn)為第i項(xiàng)組卷要求的誤差為0，這樣以加快搜索到合理解的速度，由目標(biāo)函數(shù)來設(shè)計(jì)適應(yīng)度函數(shù)，而不需要適應(yīng)度函數(shù)連續(xù)或可導(dǎo)以及其它輔助信息。我們采用以下形式的適應(yīng)度函數(shù)：其中e，(o^P，^1)對(duì)應(yīng)為第f項(xiàng)組卷因素對(duì)組卷約束程度的歸一化相對(duì)誤差，Ji｝，(。忍t^1)為的相應(yīng)的誤差權(quán)值系數(shù)，適應(yīng)度函數(shù)可以較好的反映求解組卷問題的特征，當(dāng)試卷個(gè)體對(duì)各項(xiàng)組卷約束條件的相對(duì)誤差越小時(shí)，它的適應(yīng)度函數(shù)值就越大，則表示試卷個(gè)體越接近組卷目標(biāo)。遺傳算子①選擇算子：選擇操作指從群體中按個(gè)體的適應(yīng)度函數(shù)值選擇出較適應(yīng)環(huán)境的個(gè)體。選擇將使適應(yīng)度高的個(gè)體繁殖下一代的數(shù)目較多，而適應(yīng)度較小的個(gè)體，繁殖下一代的數(shù)目較少，甚至被淘汰。本文采用期望值模型選擇機(jī)制，首先計(jì)算出群體中所有個(gè)體期望被選中的次數(shù)WJ：M一形⑴為群體規(guī)模，f為第f個(gè)個(gè)體的適應(yīng)值)，然/ZFi/i=I后根據(jù)M的整數(shù)部分確定個(gè)體f被選中的次數(shù)。然后對(duì)W『的小數(shù)部分作為概率進(jìn)行貝努利試驗(yàn)，如果試驗(yàn)成功，則該個(gè)體被選中。這樣，不但個(gè)體適應(yīng)值高的個(gè)體更容易被選中，而且即便是適應(yīng)值曉得個(gè)體也更有可能被選中。②交叉算子：在遺傳算法中，交叉算子將被選中的兩個(gè)個(gè)體的基因按一定的交叉概率，即P進(jìn)行交叉，從而生成兩個(gè)新的個(gè)體.這里將以上選出的個(gè)體進(jìn)行兩兩隨機(jī)配對(duì)，對(duì)每一對(duì)相互配對(duì)的個(gè)體采用有條件的“均勻交叉”，即兩個(gè)配對(duì)個(gè)體的每一個(gè)基因座上的基因都按設(shè)定的交叉概率P和一定的條件(確保交換后個(gè)體仍是有意義的組合)進(jìn)行交換，并產(chǎn)生兩個(gè)新個(gè)體。⑧變異算子：變異算子的基本內(nèi)容是對(duì)群體中的個(gè)體串的某些基因位置上的基因值作變動(dòng)。對(duì)變異算子的改進(jìn)主要是在同一題型段內(nèi)進(jìn)行有條件的單點(diǎn)變異，并且變異只針對(duì)交叉后的個(gè)體?？刂茀?shù)交叉是優(yōu)化新生中的一個(gè)重要步驟，在傳統(tǒng)遺傳算法中，交叉概率只是個(gè)常數(shù)，但在實(shí)際情況中，優(yōu)良的交叉率與遺傳代數(shù)間的關(guān)系較大。在迭代初期，只如果選的大，可以造成足夠的擾動(dòng)，從而增強(qiáng)遺傳算法的搜索能力；在迭代后期，只選的小，可以避免破壞優(yōu)良基因，加快收斂速度。同理，變異是優(yōu)化新生中的另一重要步驟，如果變異概率只是常數(shù)，則群體的性質(zhì)會(huì)趨于一致。因此，無論是交叉概率，還是變異概率都要隨著進(jìn)化的進(jìn)行而不斷調(diào)整?！旰椭坏倪x取直接影響算法的收斂性?！暝酱?，新個(gè)體產(chǎn)生的速度越快，而遺傳模式被破壞的可能性也越大，這樣高適應(yīng)度的個(gè)體結(jié)構(gòu)也可能被破壞;而只過小，會(huì)使搜索過程變慢。另一方面，如果己取值過大，遺傳算法就則成為了純粹的隨機(jī)搜索算法；而只過小，則不容易產(chǎn)生新的個(gè)體結(jié)構(gòu)，使算法早熟，陷入局部最優(yōu)。所以，為了加快遺傳算法的搜索效率，并有效地防止其陷入局部最優(yōu)，保披優(yōu)良試卷個(gè)體，在本論文中根據(jù)種群的進(jìn)化情況采用了自適應(yīng)函數(shù)來動(dòng)態(tài)地調(diào)整交叉概率只和變異概率己，交叉率和變異率隨著個(gè)體的適應(yīng)度在種群平均適應(yīng)度和最大適應(yīng)度之間進(jìn)行線性調(diào)性。公式如下所示：的適應(yīng)度值較大的一個(gè)，廠I變異個(gè)體的適應(yīng)度值。從公式可以看出，對(duì)于高于平均適應(yīng)度值的個(gè)體，其受破壞的可能性較小，而對(duì)于低于平均適應(yīng)函數(shù)值的個(gè)體，其受破壞的可能性較大，從而被淘汰掉。因此，自適應(yīng)的只和乞能夠?yàn)槊總€(gè)試卷個(gè)體提供一個(gè)最佳的只和己。這種自適應(yīng)遺傳算法在保持試卷群體多樣性的同時(shí)，保證遺傳算法的收斂性并防止遺傳算法陷入局部最優(yōu)。最優(yōu)個(gè)體保存策略最優(yōu)個(gè)體保存策略的改進(jìn)是將當(dāng)前解群體中的適應(yīng)度最高的個(gè)體結(jié)構(gòu)完整的復(fù)制到下一代種群中。這樣主要是為了使進(jìn)化過程中某一代的最優(yōu)解可以不被交叉或變異操作所破壞。在算法實(shí)現(xiàn)時(shí)，讓適應(yīng)度最高的個(gè)體直接進(jìn)入到下一代中，并將其設(shè)為種群中的第一個(gè)個(gè)體，其他不足種群數(shù)量的個(gè)體繼續(xù)進(jìn)行選擇，直到達(dá)到原始種群的數(shù)目。這種方法既可以保證優(yōu)良品種的個(gè)體得到更多的繁殖機(jī)會(huì)，又可以防止少數(shù)幾個(gè)優(yōu)良品種由于過度繁殖而控制整個(gè)種群，使得算法陷入到局部最小。迭代終止條件在改進(jìn)的遺傳算法中，設(shè)置了期望適應(yīng)度值，再設(shè)置最大迭代次數(shù)，把每一代計(jì)算出來的最大適應(yīng)度個(gè)體的適應(yīng)度值與期望適應(yīng)度值相比較，當(dāng)適應(yīng)度最高的個(gè)體的適應(yīng)度值比期望適應(yīng)度值大時(shí)，算法會(huì)停止迭代，否則繼續(xù)進(jìn)行遺傳操作、計(jì)算適應(yīng)度值、反復(fù)迭代直到適應(yīng)度值達(dá)到期望值或達(dá)到最大迭代次數(shù)則停止迭代，如達(dá)到期望適應(yīng)度值組卷成功，否則組卷失敗。5.3組卷算法的實(shí)現(xiàn)與分析5.3.1組卷算法的流程根據(jù)系統(tǒng)的具體需要，我們將上述組卷策略和改進(jìn)的遺傳算法應(yīng)用于組卷系統(tǒng)中，并在具體的應(yīng)用環(huán)境中對(duì)環(huán)境變量進(jìn)行改造，使得組卷算法更加高效。這種改進(jìn)的自動(dòng)組卷算法的具體算法流程圖如圖5.1所示。圖5.I自動(dòng)組卷算法流程圖Fig.5.1Theofalgorithmofautogeneratingpaperflowchart5.3.2組卷算法的實(shí)驗(yàn)分析建立測(cè)試題庫對(duì)該組卷算法進(jìn)行測(cè)試，題庫中共包含850道題目，分為四種題型，六項(xiàng)知識(shí)點(diǎn)，按照表5.1所示的試卷約束條件，進(jìn)行了組卷測(cè)試。其中，試卷中各題型的分值及分布如表5.2所示，試卷中各知識(shí)點(diǎn)的分值及分布如表5.3所示。表5.1試卷的約束條件Tab.5.IConstraintconditionsoftestpaper表5.2試卷中各題型的分值及分布Tab.5.2Everytypeofquestionsmarksanddistributionoftestpaper知識(shí)點(diǎn)知識(shí)點(diǎn)1知識(shí)點(diǎn)2知識(shí)點(diǎn)3知識(shí)點(diǎn)4知識(shí)點(diǎn)5知識(shí)點(diǎn)6分?jǐn)?shù)202020201010固定最大代數(shù)為300,群體規(guī)模為50,算法終止條件是迭代數(shù)達(dá)到最大代數(shù)或最好個(gè)體的目標(biāo)函數(shù)值，測(cè)試交叉概率只和變異概率己對(duì)程序收斂性的影響。當(dāng)交叉概率￡=0，變異概率己=0時(shí)，隨機(jī)運(yùn)行程序10次，組卷的成功率和效率很低。因?yàn)楫?dāng)只和已均為O時(shí)，算法過程中只有選擇操作而無交叉、變異操作，無法通過交叉、變異操作產(chǎn)生新的更優(yōu)的個(gè)體，只能簡單地復(fù)制每一代的優(yōu)勝個(gè)體到下一代中，因此搜索空間很小，很難找到全局最優(yōu)或較優(yōu)解。巴=0.001，對(duì)￡分別取不同值進(jìn)行12次組卷實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表5.4所示。可見，只在0.2?1之間取值均可，但組卷成功次數(shù)和平均迭代數(shù)隨只的增大呈現(xiàn)先增后降的趨勢(shì)。由于交叉條件的約束，P=1時(shí)并不是所有的個(gè)體都進(jìn)行交叉操作，故此時(shí)組卷效果也較好。表5.4參數(shù)P。對(duì)組卷的影響Tab.5.4InfluenceofparameterPctogeneratingpaper只=o.6,對(duì)己分別取不同的值進(jìn)行12次組卷實(shí)驗(yàn)，結(jié)果如表5.5所示，可見己大于O.05時(shí)，組卷效率明顯降低，這是因?yàn)樽儺愲m然增加了群體的多樣性，但是過多的變異會(huì)破壞群體的優(yōu)良模式，甚至?xí)惯z傳算法變成隨機(jī)搜索。若取值過小，產(chǎn)生新個(gè)體的速度又太慢。表5.5參數(shù)P。對(duì)組卷的影響Tab.5.5Influenceofparame