遺傳算法大學(xué)計算機基礎(chǔ)的自動組卷方法

前言：想要寫出一篇引人入勝的文章？我們特意為您整理了遺傳算法大學(xué)計算機基礎(chǔ)的自動組卷方法范文，希望能給你帶來靈感和參考，敬請閱讀。

摘要：針對傳統(tǒng)組卷方法效率、成功率低等難題，設(shè)計基于遺傳算法的大學(xué)計算機基礎(chǔ)自動組卷方法。首先設(shè)計大學(xué)計算機基礎(chǔ)自動成卷適應(yīng)度函數(shù)，采用編碼對組卷過程中題型及與其數(shù)量分布相關(guān)的約束條件進(jìn)行處理，然后設(shè)計選擇算子、交叉算子以及變異算子，將適應(yīng)度作為評價群體多樣性的指標(biāo)，求出交叉概率與變異概率，給出遺傳算法終止條件。實驗結(jié)果表明，該方法提高了大學(xué)計算機基礎(chǔ)自動組卷方法的效率和成功率。

關(guān)鍵詞：遺傳算法；計算機基礎(chǔ)；自動組卷；適應(yīng)度函數(shù)；約束條件；編碼

0引言

大學(xué)計算機基礎(chǔ)自動組卷是實現(xiàn)在線考試系統(tǒng)的核心技術(shù)，當(dāng)前很多學(xué)校機構(gòu)都對自動組卷進(jìn)行了大量研究，盡可能使最終形成的試卷達(dá)到用戶要求，同時保證科學(xué)性[1]。在大學(xué)計算機基礎(chǔ)題庫試題質(zhì)量要求高的情況下，自動組卷的效率和質(zhì)量只和組卷方法有關(guān)。因此，設(shè)計一種科學(xué)有效的自動組卷方法非常關(guān)鍵，其涉及全局尋優(yōu)問題，具有重要研究價值[2⁃3]。當(dāng)前常用的自動組卷方法有隨機生成方法和回溯試探方法。隨機生成方法通過隨機抽取的方式從試題庫中抽取試題，對其是否滿足試卷要求進(jìn)行判斷，該方法有很高的不確定性，在試題數(shù)量多的情況下，效率極低[4]?；厮菰囂椒椒ò凑漳骋粶?zhǔn)則對當(dāng)前組卷狀態(tài)進(jìn)行轉(zhuǎn)換，試探性的選擇試題破壞了選擇試題的隨機性，同時組卷所需時間長。為此，提出一種新的基于遺傳算法的大學(xué)計算機基礎(chǔ)自動組卷方法。

1遺傳算法的大學(xué)計算機基礎(chǔ)自動組卷方法

1.1大學(xué)計算機基礎(chǔ)自動組卷模型

組卷問題可描述為：采用相應(yīng)軟件程序把成卷要求與資料庫中試題特征參數(shù)匹配，得到符合成卷條件的試卷。組卷的目標(biāo)為尋找最優(yōu)解，確定最符合輸入要求的組卷策略[5]。在大學(xué)計算機基礎(chǔ)自動組卷過程中，命題人會事先輸入多個限制條件，主要含有以下幾個方面：1）試卷總分：試卷的總分?jǐn)?shù)，通過命題人設(shè)定；2）考試時間：學(xué)生參與試卷解答時間，通過命題人設(shè)定；3）試卷難易程度：通過難度系數(shù)體現(xiàn)，是學(xué)生關(guān)于試題失分狀況的體現(xiàn)；4）試卷區(qū)分度：區(qū)分度為試卷對考生情況的辨識能力，通常大小為[-1，1]，該值越大表示區(qū)分效果越好。一般情況下，當(dāng)試題區(qū)分度高于0.39時，則認(rèn)為試卷存在較好的區(qū)分度；當(dāng)試題區(qū)分度低于0.2時，則認(rèn)為試卷區(qū)分度很差。計算區(qū)分度采用的方法為：對分?jǐn)?shù)進(jìn)行排列，Q1=27%×dh，dh表示高分組的難度，Q2=27%×dl，dl表示低分組的難度，則區(qū)分度為ξ=(Q)1-Q2總分?jǐn)?shù)；5）試卷涵蓋度：試卷中涉及知識點占所學(xué)課本的比重，是根據(jù)教學(xué)大綱與考試大綱設(shè)定的；6）試卷試題結(jié)構(gòu)：試卷中包含的題型通常包括單選題、填空題、計算題、簡答題等。對上述組卷限制條件進(jìn)行分析。試卷的涵蓋度為最關(guān)鍵條件，在確定試題過程中，依據(jù)試題的知識點屬性，通過考試大綱決定知識點在試卷中出現(xiàn)的形式和比重；試卷難易程度通過各考生分?jǐn)?shù)情況確定，依據(jù)以往的測試結(jié)果對題庫內(nèi)各試題的難度級別進(jìn)行劃分，并賦予相應(yīng)的難度系數(shù)值[6]。通常要求全部考生的成績服從正態(tài)分布，由于二項分布在一定條件下與正態(tài)分布類似，因此，本節(jié)通過離散型隨機變量的二項分布體現(xiàn)試卷難度與分?jǐn)?shù)的關(guān)系，公式描述為：Ws(g)=Fgswg()1-ws-g（1）式中：s為正整數(shù)，表示最大難度級別；Ws(g)表示難度級別為g的試題總分?jǐn)?shù)占整個試卷總分?jǐn)?shù)的比例；Fgs表示難度級別為g的試題總分?jǐn)?shù)；wg表示各難度級別的難度比例；w表示難度系數(shù)。

1.2目標(biāo)函數(shù)

設(shè)k為試卷試題數(shù)量，F(xiàn)z為試卷總分?jǐn)?shù)，按照二項分布試卷難度與分?jǐn)?shù)的映射關(guān)系，通過難度系數(shù)求出每個難度級別的難度比例wg，T為考試時間，Tj為各試題作答時間。設(shè)PFN為大綱內(nèi)第N章知識點占試卷的比率，M為總章節(jié)數(shù)，F(xiàn)N為相應(yīng)章節(jié)試題的分?jǐn)?shù)，ζj為試題的區(qū)分度，則大學(xué)計算機基礎(chǔ)自動成卷的初始目標(biāo)函數(shù)如下：f=∑g=0s||||||wg-∑FgNFz+()∑N=1M||||||||∑gFNFz-PFNs.t.ìíîïïïï||||||||T-∑j=1kTjT≤0.15()∑j=1kζj×FNFz≥0.3（2）把考試時間與試卷區(qū)分度當(dāng)成目標(biāo)函數(shù)的約束條件，以減少運行時間。

1.3遺傳算法適應(yīng)度函數(shù)的確定

依據(jù)上述目標(biāo)函數(shù)確定適應(yīng)度函數(shù)。適應(yīng)度函數(shù)的復(fù)雜度為遺傳算法復(fù)雜度的重要構(gòu)成部分[7]，因此，當(dāng)設(shè)計適應(yīng)度函數(shù)時需確保計算時間復(fù)雜度最低，把目標(biāo)函數(shù)描述成計算最大值形式，保證適應(yīng)度函數(shù)為非負(fù)函數(shù)。上述成卷的目標(biāo)函數(shù)為求最小值函數(shù)，依據(jù)各函數(shù)特點，確定兩函數(shù)間的映射關(guān)系為：f*=1(1+f)（3）式中：f*表示適應(yīng)度函數(shù)；f表示目標(biāo)函數(shù)。針對任意個體，判斷考試時間和試卷區(qū)分度是否符合約束條件，如果兩者符合約束條件，則進(jìn)行適應(yīng)度計算；反之，停止計算。

1.4遺傳算法編碼

通過基因分段式編碼實現(xiàn)問題解的編碼描述，采用編碼對組卷過程中的題型及其數(shù)量分布相關(guān)的約束條件進(jìn)行處理，由此實現(xiàn)問題的簡化。詳細(xì)編碼過程為：先對每種題型進(jìn)行獨立編碼，組成相應(yīng)基因段，基因段的個數(shù)取決于題型的種數(shù)，這里用K描述；基因段中基因數(shù)取決于題庫中此種題型的試題數(shù)量。若題庫中存在ε道試題，則編碼為a1,a2,⋯,aε，其中：ai=ìíî1,第i道試題被選中0,第i道試題未被選中（4）對于被選中的全部試題需滿足∑i=1εai=k，k為試卷中的試題數(shù)量；被選中的每種題型試題需滿足∑i=1u1ai=b1,∑i=1u2ai=b2,⋯,∑i=1uKai=bK。其中，u1,u2,⋯,uK表示題庫內(nèi)相應(yīng)題型的試題數(shù)量；b1,b2,⋯,bK表示試卷中每種題型試題需要的數(shù)量。

1.5遺傳算子設(shè)計

遺傳算子包括選擇算子、交叉算子以及變異算子，下面對其進(jìn)行設(shè)計。1）選擇算子。在進(jìn)行遺傳選擇時，通過最佳個體保存法與適應(yīng)度比例選擇法獲取算子[8]。具體過程為：先挑出最好的個體，并將其復(fù)制至下一代中，然后根據(jù)每個個體被選擇概率與其適應(yīng)度間的函數(shù)關(guān)系實現(xiàn)剩余個體的挑選。求出被選擇概率，其計算公式如下：P*i=Ei∑i=1ZEi（5）式中：Z用于描述種群大小；Ei用于描述適應(yīng)度。2）交叉算子。在進(jìn)行交叉時，結(jié)合編碼方案進(jìn)行分析，選用單點交叉方式，交叉主要在同種題型組卷時進(jìn)行。3）變異算子。變異算子能夠?qū)崿F(xiàn)局部檢索，為輔助型算子，在初始種群形成時已符合各項約束條件。為了不改變約束條件，在同種題型中進(jìn)行兩點變異，也就是每種題型在自身編碼段中進(jìn)行變異。1.6自適應(yīng)交叉與變異概率交叉概率po與變異概率pv對遺傳算法有極大影響，本節(jié)將適應(yīng)度作為評價群體多樣性的指標(biāo)，使po與pv隨適應(yīng)度的變化而變化。依次求出交叉概率po與變異概率pv：po=ìíîλ1⋅(E)max-Eo(E)max-Eˉ,Eo>Eˉλ2,Eo<Eˉ（6）pv=ìíîλ3⋅(E)max-Ev(E)max-Eˉ,Ev>Eˉλ4,Ev<Eˉ（7）式中：Eo，Ev表示被計算個體的適應(yīng)度；Emax，Eˉ分別表示上一代種群內(nèi)個體最大適應(yīng)度與平均適應(yīng)度；λ1，λ2，λ3，λ4均為系數(shù)，且λ1=λ2=1，λ3=0.2，λ4=0.4。1.7終止條件本文大學(xué)計算機基礎(chǔ)自動組卷方法選擇下述三種終止條件：1）搜尋到最優(yōu)解，也就是出現(xiàn)用戶滿意的試卷；2）相鄰兩代最大適應(yīng)度值的改變率低于閾值；3）達(dá)到既定進(jìn)化代數(shù)。1.8自動組卷過程基于遺傳算法的大學(xué)計算機基礎(chǔ)自動組卷方法詳細(xì)實現(xiàn)過程如下：1）確定初始參數(shù)和初始群體，接收用戶自動組卷請求；2）求出群體中不同個體的適應(yīng)值，依據(jù)個體適應(yīng)值和選擇策略形成下一代父體；3）執(zhí)行交換與變異操作，形成新一代群體，求出當(dāng)前群體中不同個體的適應(yīng)值；4）對新一代最優(yōu)個體與上一代最優(yōu)個體適應(yīng)值進(jìn)行比較，若降低，則用上一代最佳個體替換當(dāng)前最佳個體；5）輸出當(dāng)前代數(shù)、最優(yōu)目標(biāo)函數(shù)值及最優(yōu)個體編碼，求出不同難度級別和分?jǐn)?shù)等指標(biāo)。

2自動組卷實驗結(jié)果分析

為了驗證本文提出遺傳算法的可行性與有效性，針對大學(xué)計算機基礎(chǔ)課程，通過ASP+SQLServer2000，依據(jù)遺傳思想編寫程序，進(jìn)行自動組卷實驗。假設(shè)題庫共存在五種題型、六個章節(jié)、七個難度系數(shù)與四個認(rèn)知層次。題庫中有700題，其題型題量分布、章節(jié)題量分布、假設(shè)組卷要求為：試卷總分為120分，選題需達(dá)到題型與題量要求，不同題型分?jǐn)?shù)已給出。所有章節(jié)的分值誤差、難度分值誤差及不同認(rèn)知層次分值誤差都在±2分以內(nèi).自動組卷結(jié)果分析：1）在交叉概率為0.8，變異概率為0.1的情況下，令群體規(guī)模依次取20，30，40，50，60，運行代數(shù)在20~100范圍內(nèi)變化。群體規(guī)模對遺傳算法收斂性有很大的影響。在群體規(guī)模較小的情況下（20和30），參與遺傳算法的試題較少，搜索空間受到限制，適應(yīng)度值小，得到有效試卷的機會很小。在群體規(guī)模達(dá)到40的情況下，適應(yīng)度值明顯升高，而當(dāng)群體規(guī)模為50和60時，適應(yīng)度值無顯著區(qū)別，基本不增長，說明群體規(guī)模達(dá)到40時，即可達(dá)到收斂，而群體規(guī)模越大，則程序運行速度越低，所以本文實驗設(shè)定群體規(guī)模為40。除此之外，還可以看出，在運行代數(shù)為60代的情況下適應(yīng)度值已實現(xiàn)收斂，所以將運行代數(shù)設(shè)置為60代。2）令最大迭代數(shù)為60代，交叉概率為0.8，變異概率為0.1，群體規(guī)模為40。經(jīng)50次調(diào)試運行，獲取大學(xué)計算機基礎(chǔ)自動組卷結(jié)果。為了驗證本文方法的有效性，將隨機生成方法和回溯試探方法作為對比，在題庫量是700題的情況下，對三種方法的組卷時間、組卷成功率進(jìn)行比較.本文方法成功概率為100%，且所需時間明顯低于隨機生成方法和回溯試探方法，性能優(yōu)于其他兩種方法，驗證了本文基于改進(jìn)遺傳算法的大學(xué)計算機基礎(chǔ)自動組卷設(shè)計與實現(xiàn)方法的優(yōu)越性。

3結(jié)論

本文提出基于遺傳算法的大學(xué)計算機基礎(chǔ)自動組卷方法。介紹了大學(xué)計算機基礎(chǔ)自動組卷模型，給出通過遺傳算法實現(xiàn)大學(xué)計算機基礎(chǔ)自動組卷的詳細(xì)過程。經(jīng)實驗驗證，所提方法效率和成功率較高。

參考文獻(xiàn)

[1]陳國彬，張廣泉.基于改進(jìn)遺傳算法的快速自動組卷算法研究[J].計算機應(yīng)用研究，2015，32（10）：2996⁃2998.CHENGuobin，ZHANGGuangquan.Newalgorithmforintelligenttestpapercompositionbasedonimprovedgeneticalgorithm[J].Applicationresearchofcomputers，2015，32（10）：2996⁃2998.

[2]吳愛婷，官伯然.一種基于遺傳算法的超寬帶天線自動設(shè)計方法[J].微波學(xué)報，2015，31（3）：22⁃26.WUAiting，GUANBoran.Anautomationdesignmethodoftheultra⁃widebandantennabasedonthegeneticalgorithm[J].Journalofmicrowaves，2015，31（3）：22⁃26.

[3]李瑞森，張樹有，伊國棟，等.可拓集成模式的工程圖學(xué)試題庫組卷方法研究[J].圖學(xué)學(xué)報，2016，37（6）：851⁃856.LIRuisen，ZHANGShuyou，YINGuodong，etal.Researchonthetestpapergeneratingmethodofengineeringgraphicsbasedontheextensionandintegrationmode[J].Journalofgraphics，2016，37（6）：851⁃856.

[4]王寧，蔡順燕.基于隨機相位重構(gòu)的智能組卷混疊均衡算法[J].科技通報，2016，32（5）：236⁃239.WANGNing，CAIShunyan.Smartgroupaliasingequalizationalgorithmbasedontherandomphasereconstruction[J].Bulletinofscienceandtechnology，2016，32（5）：236⁃239.

[5]席衛(wèi)文，張春輝，王飛，等.一種基于改進(jìn)遺傳算法的醫(yī)學(xué)題庫自動組卷設(shè)計與實現(xiàn)[J].中國醫(yī)學(xué)物理學(xué)雜志，2016，33（8）：861⁃864.XIWeiwen，ZHANGChunhui，WANGFei，etal.Designandimplementationofimprovedgeneticalgorithmforautomatictestpapergeneration[J].Chinesejournalofmedicalphysics，2016，33（8）：861⁃864.

[6]徐海東.基于遺傳算法的自動組卷算法的研究[J].微型電腦應(yīng)用，2016，32（3）：60⁃62.XUHaidong.Researchonautomatictestpaperbasedongeneticalgorithm[J].Microcomputerapplications，2016，32（3）：60⁃62.

[7]呂海燕，周立軍，宦婧，等.通用在線考試系統(tǒng)智能組卷遺傳算法設(shè)計[J].計算技術(shù)與自動化，2016，35（4）：85⁃90.LÜHaiyan，ZHOULijun，HUANJing，etal.Designofintelligenttestpapergeneratinggeneticalgorithmforcommononlineexaminationsystem[J].Computingtechnologyandautomation，2016，35（4）：85⁃90.

[8]潘剛，楊清平，蒲國林，等.遺傳算法在智能組卷系統(tǒng)中的應(yīng)用研究[J].云南民族大學(xué)學(xué)報（自然科學(xué)版），2016，25（6）：579⁃584.PANGang，YANGQingping，PUGuolin，etal.Applicationofthegeneticalgorithmintheintelligenttestpapergenerationsystem[J].JournalofYunnanUniversityofNationalities（naturalsciencesedition），2016，25（6）：579⁃584.

[9]楊秀霞，張曉鋒，張毅.基于加速遺傳算法的艦船電力系統(tǒng)故障恢復(fù)[J].電工技術(shù)學(xué)報，2005，20（5）：53⁃57.YANGXiuxia，ZHANGXiaofeng，ZHANGYi.Shipboardpowersystemservicerestorationbasedontheacceleratedgeneticalgorithm[J].TransactionsofChinaelectrotechnicalsociety，2005，20（5）：53⁃57.

作者:楊春哲 常涵吉 單位:吉林醫(yī)藥學(xué)院