遺傳算法大學計算機基礎的自動組卷方法的畢業(yè)論文
摘要：針對傳統(tǒng)組卷方法效率、成功率低等難題，設計基于遺傳算法的大學計算機基礎自動組卷方法。首先設計大學計算機基礎自動成卷適應度函數(shù)，采用編碼對組卷過程中題型及與其數(shù)量分布相關的約束條件進行處理，然后設計選擇算子、交叉算子以及變異算子，將適應度作為評價群體多樣性的指標，求出交叉概率與變異概率，給出遺傳算法終止條件。實驗結果表明，該方法提高了大學計算機基礎自動組卷方法的效率和成功率。
關鍵詞：遺傳算法；計算機基礎；自動組卷；適應度函數(shù)；約束條件；編碼
0引言
大學計算機基礎自動組卷是實現(xiàn)在線考試系統(tǒng)的核心技術，當前很多學校機構都對自動組卷進行了大量研究，盡可能使最終形成的試卷達到用戶要求，同時保證科學性[1]。在大學計算機基礎題庫試題質量要求高的情況下，自動組卷的效率和質量只和組卷方法有關。因此，設計一種科學有效的自動組卷方法非常關鍵，其涉及全局尋優(yōu)問題，具有重要研究價值[23]。當前常用的自動組卷方法有隨機生成方法和回溯試探方法。隨機生成方法通過隨機抽取的方式從試題庫中抽取試題，對其是否滿足試卷要求進行判斷，該方法有很高的不確定性，在試題數(shù)量多的情況下，效率極低[4]�；厮菰囂椒椒ò凑漳骋粶蕜t對當前組卷狀態(tài)進行轉換，試探性的選擇試題破壞了選擇試題的隨機性，同時組卷所需時間長。為此，提出一種新的基于遺傳算法的大學計算機基礎自動組卷方法。
1遺傳算法的大學計算機基礎自動組卷方法
1.1大學計算機基礎自動組卷模型
組卷問題可描述為：采用相應軟件程序把成卷要求與資料庫中試題特征參數(shù)匹配，得到符合成卷條件的試卷。組卷的目標為尋找最優(yōu)解，確定最符合輸入要求的組卷策略[5]。在大學計算機基礎自動組卷過程中，命題人會事先輸入多個限制條件，主要含有以下幾個方面：1）試卷總分：試卷的總分數(shù)，通過命題人設定；2）考試時間：學生參與試卷解答時間，通過命題人設定；3）試卷難易程度：通過難度系數(shù)體現(xiàn)，是學生關于試題失分狀況的體現(xiàn)；4）試卷區(qū)分度：區(qū)分度為試卷對考生情況的辨識能力，通常大小為[-1，1]，該值越大表示區(qū)分效果越好。一般情況下，當試題區(qū)分度高于0.39時，則認為試卷存在較好的區(qū)分度；當試題區(qū)分度低于0.2時，則認為試卷區(qū)分度很差。計算區(qū)分度采用的方法為：對分數(shù)進行排列，Q1=27%×dh，dh表示高分組的難度，Q2=27%×dl，dl表示低分組的難度，則區(qū)分度為=(Q)1-Q2總分數(shù)；5）試卷涵蓋度：試卷中涉及知識點占所學課本的比重，是根據(jù)教學大綱與考試大綱設定的；6）試卷試題結構：試卷中包含的題型通常包括單選題、填空題、計算題、簡答題等。對上述組卷限制條件進行分析。試卷的涵蓋度為最關鍵條件，在確定試題過程中，依據(jù)試題的知識點屬性，通過考試大綱決定知識點在試卷中出現(xiàn)的形式和比重；試卷難易程度通過各考生分數(shù)情況確定，依據(jù)以往的測試結果對題庫內各試題的難度級別進行劃分，并賦予相應的難度系數(shù)值[6]。通常要求全部考生的成績服從正態(tài)分布，由于二項分布在一定條件下與正態(tài)分布類似，因此，本節(jié)通過離散型隨機變量的二項分布體現(xiàn)試卷難度與分數(shù)的關系，公式描述為：Ws(g)=Fgswg()1-ws-g（1）式中：s為正整數(shù)，表示最大難度級別；Ws(g)表示難度級別為g的試題總分數(shù)占整個試卷總分數(shù)的比例；Fgs表示難度級別為g的試題總分數(shù)；wg表示各難度級別的難度比例；w表示難度系數(shù)。
1.2目標函數(shù)
設k為試卷試題數(shù)量，F(xiàn)z為試卷總分數(shù)，按照二項分布試卷難度與分數(shù)的映射關系，通過難度系數(shù)求出每個難度級別的難度比例wg，T為考試時間，Tj為各試題作答時間。設PFN為大綱內第N章知識點占試卷的比率，M為總章節(jié)數(shù)，F(xiàn)N為相應章節(jié)試題的分數(shù)，ζj為試題的區(qū)分度，則大學計算機基礎自動成卷的初始目標函數(shù)如下：f=∑g=0s||||||wg-∑FgNFz+()∑N=1M||||||||∑gFNFz-PFNs.t.ìí||||||||T-∑j=1kTjT≤0.15()∑j=1kζj×FNFz≥0.3（2）把考試時間與試卷區(qū)分度當成目標函數(shù)的約束條件，以減少運行時間。
1.3遺傳算法適應度函數(shù)的確定
依據(jù)上述目標函數(shù)確定適應度函數(shù)。適應度函數(shù)的復雜度為遺傳算法復雜度的重要構成部分[7]，因此，當設計適應度函數(shù)時需確保計算時間復雜度最低，把目標函數(shù)描述成計算最大值形式，保證適應度函數(shù)為非負函數(shù)。上述成卷的`目標函數(shù)為求最小值函數(shù)，依據(jù)各函數(shù)特點，確定兩函數(shù)間的映射關系為：f*=1(1+f)（3）式中：f*表示適應度函數(shù)；f表示目標函數(shù)。針對任意個體，判斷考試時間和試卷區(qū)分度是否符合約束條件，如果兩者符合約束條件，則進行適應度計算；反之，停止計算。
1.4遺傳算法編碼
通過基因分段式編碼實現(xiàn)問題解的編碼描述，采用編碼對組卷過程中的題型及其數(shù)量分布相關的約束條件進行處理，由此實現(xiàn)問題的簡化。詳細編碼過程為：先對每種題型進行獨立編碼，組成相應基因段，基因段的個數(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表示題庫內相應題型的試題數(shù)量；b1,b2,,bK表示試卷中每種題型試題需要的數(shù)量。
1.5遺傳算子設計
遺傳算子包括選擇算子、交叉算子以及變異算子，下面對其進行設計。1）選擇算子。在進行遺傳選擇時，通過最佳個體保存法與適應度比例選擇法獲取算子[8]。具體過程為：先挑出最好的個體，并將其復制至下一代中，然后根據(jù)每個個體被選擇概率與其適應度間的函數(shù)關系實現(xiàn)剩余個體的挑選。求出被選擇概率，其計算公式如下：P*i=Ei∑i=1ZEi（5）式中：Z用于描述種群大�。籈i用于描述適應度。2）交叉算子。在進行交叉時，結合編碼方案進行分析，選用單點交叉方式，交叉主要在同種題型組卷時進行。3）變異算子。變異算子能夠實現(xiàn)局部檢索，為輔助型算子，在初始種群形成時已符合各項約束條件。為了不改變約束條件，在同種題型中進行兩點變異，也就是每種題型在自身編碼段中進行變異。1.6自適應交叉與變異概率交叉概率po與變異概率pv對遺傳算法有極大影響，本節(jié)將適應度作為評價群體多樣性的指標，使po與pv隨適應度的變化而變化。依次求出交叉概率po與變異概率pv：po=ìíλ1(E)max-Eo(E)max-Eˉ,Eo>Eˉλ2,Eo
2自動組卷實驗結果分析
為了驗證本文提出遺傳算法的可行性與有效性，針對大學計算機基礎課程，通過ASP+SQLServer2000，依據(jù)遺傳思想編寫程序，進行自動組卷實驗。假設題庫共存在五種題型、六個章節(jié)、七個難度系數(shù)與四個認知層次。題庫中有700題，其題型題量分布、章節(jié)題量分布、假設組卷要求為：試卷總分為120分，選題需達到題型與題量要求，不同題型分數(shù)已給出。所有章節(jié)的分值誤差、難度分值誤差及不同認知層次分值誤差都在±2分以內.自動組卷結果分析：1）在交叉概率為0.8，變異概率為0.1的情況下，令群體規(guī)模依次取20，30，40，50，60，運行代數(shù)在20~100范圍內變化。群體規(guī)模對遺傳算法收斂性有很大的影響。在群體規(guī)模較小的情況下（20和30），參與遺傳算法的試題較少，搜索空間受到限制，適應度值小，得到有效試卷的機會很小。在群體規(guī)模達到40的情況下，適應度值明顯升高，而當群體規(guī)模為50和60時，適應度值無顯著區(qū)別，基本不增長，說明群體規(guī)模達到40時，即可達到收斂，而群體規(guī)模越大，則程序運行速度越低，所以本文實驗設定群體規(guī)模為40。除此之外，還可以看出，在運行代數(shù)為60代的情況下適應度值已實現(xiàn)收斂，所以將運行代數(shù)設置為60代。2）令最大迭代數(shù)為60代，交叉概率為0.8，變異概率為0.1，群體規(guī)模為40。經(jīng)50次調試運行，獲取大學計算機基礎自動組卷結果。為了驗證本文方法的有效性，將隨機生成方法和回溯試探方法作為對比，在題庫量是700題的情況下，對三種方法的組卷時間、組卷成功率進行比較.本文方法成功概率為100%，且所需時間明顯低于隨機生成方法和回溯試探方法，性能優(yōu)于其他兩種方法，驗證了本文基于改進遺傳算法的大學計算機基礎自動組卷設計與實現(xiàn)方法的優(yōu)越性。
3結論
本文提出基于遺傳算法的大學計算機基礎自動組卷方法。介紹了大學計算機基礎自動組卷模型，給出通過遺傳算法實現(xiàn)大學計算機基礎自動組卷的詳細過程。經(jīng)實驗驗證，所提方法效率和成功率較高。
參考文獻
[1]陳國彬，張廣泉.基于改進遺傳算法的快速自動組卷算法研究[J].計算機應用研究，2015，32（10）：29962998.CHENGuobin，ZHANGGuangquan.Newalgorithmforintelligenttestpapercompositionbasedonimprovedgeneticalgorithm[J].Applicationresearchofcomputers，2015，32（10）：29962998.
[2]吳愛婷，官伯然.一種基于遺傳算法的超寬帶天線自動設計方法[J].微波學報，2015，31（3）：2226.WUAiting，GUANBoran.Anautomationdesignmethodoftheultrawidebandantennabasedonthegeneticalgorithm[J].Journalofmicrowaves，2015，31（3）：2226.
[3]李瑞森，張樹有，伊國棟，等.可拓集成模式的工程圖學試題庫組卷方法研究[J].圖學學報，2016，37（6）：851856.LIRuisen，ZHANGShuyou，YINGuodong，etal.Researchonthetestpapergeneratingmethodofengineeringgraphicsbasedontheextensionandintegrationmode[J].Journalofgraphics，2016，37（6）：851856.
[4]王寧，蔡順燕.基于隨機相位重構的智能組卷混疊均衡算法[J].科技通報，2016，32（5）：236239.WANGNing，CAIShunyan.Smartgroupaliasingequalizationalgorithmbasedontherandomphasereconstruction[J].Bulletinofscienceandtechnology，2016，32（5）：236239.
[5]席衛(wèi)文，張春輝，王飛，等.一種基于改進遺傳算法的醫(yī)學題庫自動組卷設計與實現(xiàn)[J].中國醫(yī)學物理學雜志，2016，33（8）：861864.XIWeiwen，ZHANGChunhui，WANGFei，etal.Designandimplementationofimprovedgeneticalgorithmforautomatictestpapergeneration[J].Chinesejournalofmedicalphysics，2016，33（8）：861864.
[6]徐海東.基于遺傳算法的自動組卷算法的研究[J].微型電腦應用，2016，32（3）：6062.XUHaidong.Researchonautomatictestpaperbasedongeneticalgorithm[J].Microcomputerapplications，2016，32（3）：6062.
[7]呂海燕，周立軍，宦婧，等.通用在線考試系統(tǒng)智能組卷遺傳算法設計[J].計算技術與自動化，2016，35（4）：8590.LHaiyan，ZHOULijun，HUANJing，etal.Designofintelligenttestpapergeneratinggeneticalgorithmforcommononlineexaminationsystem[J].Computingtechnologyandautomation，2016，35（4）：8590.
[8]潘剛，楊清平，蒲國林，等.遺傳算法在智能組卷系統(tǒng)中的應用研究[J].云南民族大學學報（自然科學版），2016，25（6）：579584.PANGang，YANGQingping，PUGuolin，etal.Applicationofthegeneticalgorithmintheintelligenttestpapergenerationsystem[J].JournalofYunnanUniversityofNationalities（naturalsciencesedition），2016，25（6）：579584.
[9]楊秀霞，張曉鋒，張毅.基于加速遺傳算法的艦船電力系統(tǒng)故障恢復[J].電工技術學報，2005，20（5）：5357.YANGXiuxia，ZHANGXiaofeng，ZHANGYi.Shipboardpowersystemservicerestorationbasedontheacceleratedgeneticalgorithm[J].TransactionsofChinaelectrotechnicalsociety，2005，20（5）：5357.
作者:楊春哲 常涵吉 單位:吉林醫(yī)藥學院
【遺傳算法大學計算機基礎的自動組卷方法的畢業(yè)論文】相關文章：
7.大學計算機基礎題