基于改進(jìn)遺傳算法的自動(dòng)組卷問題研究

摘要：為了解決傳統(tǒng)遺傳算法在自動(dòng)組卷中容易出現(xiàn)未成熟收斂和收斂速度慢等問題，提出了一種基于改進(jìn)遺傳算法的自動(dòng)組卷方法。采用分段二進(jìn)制編碼策略，對(duì)每個(gè)子空間進(jìn)行初始種群選擇，保證了初始種群含有豐富的模式，從而增加搜索收斂于全局最優(yōu)的可能性。并對(duì)交叉算子和變異算子進(jìn)行了優(yōu)化，實(shí)現(xiàn)了交叉和變異概率隨解的變化而自適應(yīng)調(diào)整。實(shí)驗(yàn)結(jié)果表明，改進(jìn)的遺傳算法能有效地解決自動(dòng)組卷問題，提高了收斂速度和組卷的成功率。

關(guān)鍵詞：遺傳算法；自動(dòng)組卷；適應(yīng)度函數(shù)；分段二進(jìn)制編碼

中圖分類號(hào)：TN91134文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1004373X（2012）18008003

引言

自動(dòng)組卷是實(shí)現(xiàn)網(wǎng)上考試系統(tǒng)的核心技術(shù)之一，國(guó)內(nèi)外的許多學(xué)校機(jī)構(gòu)、科研單位都對(duì)組卷系統(tǒng)進(jìn)行了研究，要求生成的試卷能最大程度地滿足用戶的需要，并具有科學(xué)性、隨機(jī)性和合理性[1]。在題庫試題質(zhì)量高的前提下，自動(dòng)組卷的效率與質(zhì)量完全取決于抽題算法的設(shè)計(jì)。如何設(shè)計(jì)一個(gè)高效、合理、科學(xué)的算法，是自動(dòng)組卷的關(guān)鍵，涉及到一個(gè)全局尋優(yōu)和收斂速度快慢的問題，具有很高的研究?jī)r(jià)值[2]。

1組卷問題的數(shù)學(xué)描述

只有滿足一定條件的試題才能參與組卷，因此試題組卷時(shí)需要給出以下約束條件：總時(shí)間、試卷平均難度、試卷總分、知識(shí)范圍、各種題型比例等[3]。組卷中決定一道試題，就要決定n項(xiàng)約束條件，決定一份試卷，就決定一個(gè)m×n的矩陣，其中m是試卷所含的題目數(shù)[4]。本模型中n簡(jiǎn)化為5，即僅考慮總分、難度、題型、知識(shí)范圍和答題時(shí)間5項(xiàng)指標(biāo)。s=d11d12…d15

d21d22…d25

………

dm1dm2…dm52改進(jìn)遺傳算法的自動(dòng)組卷設(shè)計(jì)

針對(duì)試題組卷的具體情況，對(duì)標(biāo)準(zhǔn)遺傳算法進(jìn)行改進(jìn)后用于求解組卷問題，以下給出具體解決方法。

2.1編碼方案

本系統(tǒng)采用了分段二進(jìn)制編碼策略。將整個(gè)題庫劃分為不同的段，每一段反映一種題型，每一段長(zhǎng)度由題庫中該題型的數(shù)目決定，每一種題型單獨(dú)進(jìn)行傳統(tǒng)的二進(jìn)制編碼，編碼長(zhǎng)度由試題庫中所含試題數(shù)決定[5]。