李國安

摘 要：智能組卷的方法有很多，目前應(yīng)用遺傳算法、模擬退火算法、隨機抽取算法、回溯試探法等方法進行組卷，對比發(fā)現(xiàn)遺傳算法在智能組卷問題上的解決方法具有一定的優(yōu)越性。為了避免遺傳算法的“早熟”，引入聚類思想，形成質(zhì)心集，最終得到最優(yōu)解，提高算法的性能。

關(guān)鍵詞：遺傳算法；智能組卷

【中圖分類號】G 【文獻標(biāo)識碼】B 【文章編號】1008-1216（2016）10C-0065-02

生成試卷的方法有很多，可以通過手工或通過算法智能組卷進行組合，滿足一定規(guī)則下進行組卷。手工組卷不能高效、合理地完成組卷，智能組卷可以通過一定約束條件，完成一個組合問題，組合效率比較高。如何通過某種算法使組卷過程智能化，使試卷更有科學(xué)性、合理性？

智能組卷在國內(nèi)從20世紀(jì)90年代開始逐漸增多，在中國知網(wǎng)搜索的“智能組卷”算法種類比較多，目前研究比較多的方法有遺傳算法、模擬退火算法、隨機抽取算法等。

隨機抽取算法在組卷算法中是比較常用的一種算法，根據(jù)約束條件，滿足用戶需求，隨機抽取試題，進行判斷，滿足條件，則生成試卷成功，否則，重新生成一組試卷，直到滿足條件為止。這種算法的特點是在語言實現(xiàn)上比較容易，但是這種方式的組卷重復(fù)率高、成功率低，效率比較低，所需時間長。

回溯試探法是基于深度及廣度搜索的算法，它建立在隨機抽取算法的基礎(chǔ)上，此算法對所有的情況進行窮盡搜索。在題庫中存在滿足約束條件的試題，系統(tǒng)最終一定會找出它的解。這種算法的結(jié)構(gòu)復(fù)雜，運行起來比較耗費時間，所以適用于題量較少的情況。

遺傳算法是解決并行計算問題，并逐步得到優(yōu)化的解題過程，它通過模擬生物進化過程，對問題進行求解，迭代過程中找到最優(yōu)解。操作步驟有選擇、交叉和變異，完成這三個基本操作并抽取試題，最終得到滿足約束條件的試卷集合。它具有運行效率高、靈活性大的特點，適用于具有多種約束條件的求解問題。

遺傳算法是智能組卷中比較靈活的方法，將不確定的問題進行求解，這種但是在應(yīng)用遺傳算法過程中，應(yīng)避免“早熟”，這也是遺傳算法在智能組卷過程中值得研究的。目的就是解決組合優(yōu)化問題，提高算法的執(zhí)行效率。

一、改進遺傳算法在組卷問題中的研究

組卷目標(biāo)是從一個試題庫集合中，通過某種方式重新組合成一組科學(xué)合理的組合試卷。

根據(jù)題目類型進行順序排序，并在滿足其他規(guī)則的情況下，根據(jù)確定的參數(shù)，從題庫中根據(jù)算法組合成一組試卷，為了讓試卷具有科學(xué)性，更接近確定的試卷，本文討論的試卷生成主要滿足題量、難度系數(shù)、區(qū)分度、知識點和題型等相關(guān)參數(shù)，使用遺傳算法組合生成試卷，避免遺傳算法“早熟”現(xiàn)象，將遺傳算法進行改進。

（一）改進遺傳算法基本思想

以遺傳算法進行組合試卷，主要避免初始群體“早熟”現(xiàn)象發(fā)生，找到最優(yōu)解。此過程中引入聚類思想，在不影響種群的情況下，將初始種群使用聚類算法，群體中的每個染色體代表一個初始聚類的中心集，根據(jù)評價函數(shù)（根據(jù)試題的屬性完成聚類算法K-Means，得到一個數(shù)值）對每個染色體進行評價，得到適應(yīng)值，染色體的適應(yīng)值越大，說明染色體代表的中心集的聚類效果越好。根據(jù)約束條件進行選擇，隨機生成一組染色個體。進行交叉操作，染色體長度會發(fā)生變化，染色體長度的變化說明在遺傳算法過程中，中心集的選擇在發(fā)生變化，正是因為這一操作，經(jīng)過多次迭代，可以得到聚類劃分?jǐn)?shù)目和最優(yōu)的質(zhì)心集。最后根據(jù)變異概率，進行變異操作，在尋找最優(yōu)質(zhì)心集迭代過程中，找到的個體具有多樣性，從而保證了搜索全局，避免了“早熟”現(xiàn)象，找到最優(yōu)解。