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