遺傳算法大學(xué)計(jì)算機(jī)基礎(chǔ)的自動(dòng)組卷方法

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

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

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

0引言

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

1遺傳算法的大學(xué)計(jì)算機(jī)基礎(chǔ)自動(dòng)組卷方法

1.1大學(xué)計(jì)算機(jī)基礎(chǔ)自動(dòng)組卷模型

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

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

設(shè)k為試卷試題數(shù)量，F(xiàn)z為試卷總分?jǐn)?shù)，按照二項(xiàng)分布試卷難度與分?jǐn)?shù)的映射關(guān)系，通過難度系數(shù)求出每個(gè)難度級(jí)別的難度比例wg，T為考試時(shí)間，Tj為各試題作答時(shí)間。設(shè)PFN為大綱內(nèi)第N章知識(shí)點(diǎn)占試卷的比率，M為總章節(jié)數(shù)，F(xiàn)N為相應(yīng)章節(jié)試題的分?jǐn)?shù)，ζj為試題的區(qū)分度，則大學(xué)計(jì)算機(jī)基礎(chǔ)自動(dòng)成卷的初始目標(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）把考試時(shí)間與試卷區(qū)分度當(dāng)成目標(biāo)函數(shù)的約束條件，以減少運(yùn)行時(shí)間。

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

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

1.4遺傳算法編碼

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

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

2自動(dòng)組卷實(shí)驗(yàn)結(jié)果分析

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

3結(jié)論

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

參考文獻(xiàn)

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

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

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

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

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

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

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

[8]潘剛，楊清平，蒲國(guó)林，等.遺傳算法在智能組卷系統(tǒng)中的應(yīng)用研究[J].云南民族大學(xué)學(xué)報(bào)（自然科學(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é)報(bào)，2005，20（5）：53⁃57.YANGXiuxia，ZHANGXiaofeng，ZHANGYi.Shipboardpowersystemservicerestorationbasedontheacceleratedgeneticalgorithm[J].TransactionsofChinaelectrotechnicalsociety，2005，20（5）：53⁃57.

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