試題庫平臺的設計與實現(xiàn)本科畢業(yè)論文

.3.2試卷參數(shù)分析模塊在生成試卷之前先要進行參數(shù)分析，參數(shù)分析主要包括以下幾個方面：（1）分析章節(jié)中的題數(shù)分配，并按不同題型依次檢查該題型的章節(jié)題量分配是否有效；（2）小題數(shù)通過檢驗，統(tǒng)計各類難度試題數(shù)量，按不同難度等級分別檢查題量分配是否合理[13]。部分核心代碼（以選擇題為例，難度以難為例）：（1）檢查單選題題量分配是否有效objRsSingle.Filter=strFilterIfobjRsSingle.RecordCount<Int(cmbChapter(i).ItemData(j))*_txtCount(i)/100)ThenMsgBox"<"&News(i)&"><"&objRsChapter!名稱&">中只有<"_&objRsSingle.RecordCount&">道試題，小題百分比最多<"_&Int(objRsSingle.RecordCount/Val(txtCount(i))*100)_&">",vbCriticalcmbChapter(i).ListIndex=jEndIf（2）小題數(shù)通過檢驗，統(tǒng)計各類難度試題數(shù)量Fork=0To4objRsSingle.Filter=strFilter&"and難度="&kChapter(i,k)=Chapter(i,k)+objRsSingle.RecordCountNext（3）按難度檢查題量分配是否合理Fori=0To5…………（4）檢查難度屬于“難”的題題量分配是否有效IfChapter(i,0)<Int(Val(txtCount(i))*txtLevel0(i)/100)ThenMsgBoxNews(i)&"題庫中難度屬于“難”的題只有<"_&Chapter(i,0)&">道，難度百分比最大可為<"_&Int(Chapter(i,0)/Val(txtCount(i))*100)_&">",vbCriticaltxtLevel0(i).SetFocusExitSubEndIf4.3.3試卷生成模塊功能實現(xiàn)試卷生成模塊的功能主要是從試題庫中的試題中抽取一部分自動生成試卷，并通過VB程序自動調入WORD中排版打印，實現(xiàn)試卷的自動生成。試卷生成的程序功能框圖如圖4.7所示。試題庫VB的ADO調用試題庫VB的ADO調用WordApplication使用WORD圖4.7試卷生成程序框圖試卷高級程序設計語言ＶＢ中提供了MicrosoftWord9.0（或10.0）對象庫，通過創(chuàng)建和定義WORD.APPLICATION對象，可以實現(xiàn)用VB程序對WORD文檔的操作和控制。ADO是一種高層次的，獨立于編程語言的，可以訪問所有種類企業(yè)信息的數(shù)據(jù)訪問接口。VB通過ADO接口可以很方便的與數(shù)據(jù)庫進行數(shù)據(jù)通信，實現(xiàn)數(shù)據(jù)的管理和調用。所以，通過ADO數(shù)據(jù)接口的橋梁作用，利用VB程序可以實現(xiàn)將數(shù)據(jù)從數(shù)據(jù)庫表到WORD的自動調入，完成試卷的自動生成[11]。4.3.4實現(xiàn)所需步驟實現(xiàn)試卷的自動生成，需經過數(shù)據(jù)庫連接，ADO調用，操控WORD.APPLICATION對象，排版打印等步驟[12]。（1）數(shù)據(jù)庫連接OptionExplicitDimWithEventsdb1AsADODB.ConnectionPrivateConstcn1=“provider=microsoft.jet.oledb.4.0；datasource=”cstring=cn1+App.Path+“\”+“tiku.mdb”Setdb1=NewADODB.Connectiondb1.ConnectionString=cstringdb1.Open（2）ADO調用ADO調用主要利用ADO的RECORDSET或COMMAND對象實現(xiàn)。按試卷編號主鍵從試題數(shù)據(jù)表中挑選出對應試卷的試題作為數(shù)據(jù)源，以備調入WORD.APPLICATION對象使用，以調入選擇題為例，代碼如下：Setrsdy1=NewADODB.Recordsetssql1=“select*fromzongbiaowherelx=’選擇題’”.Setrsdy1.ActiveConnection=dbdyrsdy1.Source=ssql1rsdy1.CursorLocation=adUseClientrsdy1.CursorType=adOpenStaticrsdy1.LockType=adLockOptimisticrsdy1.Open（3）操控WORD.APPLICATION對象通過VB程序操控WORD主要包括定義和建立WORD.APPLICATION對象，向DOCUMENT對象自動填充文檔數(shù)據(jù)等功能，數(shù)據(jù)自動填充完畢，由用戶在當前WORD文檔中排版和打印。DimwrdappAsWord.ApplicationDimrngparagraphsAsRangeSetwrdapp=NewWord.ApplicationWrdapp.Documents.OpenFileName:=App.Path+“\”+“dayin.doc”Wrdapp.Visible=TrueSetrngparagraphs=wrdapp.ActiveDocument.Paragraphs（5）.RangeRngparagraphs.InsertAfterText:=rs.Fields（“mc”）Rngparagraphs.InsertParagraphAfterdimwrdappasword.applicationsetwrdapp=newword.applicationwrdapp.Documents.openfilename:=App.Path+“\”+“dayin.doc”

5通用組卷要設計一個性能良好的通用試卷生成系統(tǒng)，選擇一種好的組卷算法是關鍵。本章首先介紹組卷算法的發(fā)展，接著簡單介紹了目前比較常見的幾種主要的組卷算法，最后重點論述了基于遺傳算法的組卷算法。5.1通用組卷系統(tǒng)的算法5.1.1組卷算法的發(fā)展和概述組卷算法或者說選題算法，都是由試題庫系統(tǒng)的組卷模型來決定的，不同組卷模型有不同的組卷算法，但相同的組卷模型亦有不同的組卷算法。通過翻閱一些學術文章及在互聯(lián)網上查找到的資料，可以對當前流行的試題庫系統(tǒng)組卷算法作一個總結。自80年代以來，建立計算機試題庫系統(tǒng)已經成為CAI的一個重要環(huán)節(jié)，為實現(xiàn)考試的規(guī)范化與科學化提供了有力的工具。眾所周知，自動組卷的效率與質量取決于抽題算法的設計。而如何保證生成的試卷能最大程度的滿足用戶的不同需要，并具有隨機性、科學性、合理性，這是實現(xiàn)中的一個難點。因此，選擇一個高效、科學、合理的算法是自動組卷的關鍵。如何設計一個算法能從題庫中既快又好地抽出一組最符合考方要求的試題，涉及到一個全局尋優(yōu)和收斂速度快慢的問題，很多學者對其進行了研究。目前在試題庫系統(tǒng)中主要存在4種組卷方式：一是人工組卷，這種方式速度太慢，質量低，當試題庫題量大時，這種方式非常不合適；二是隨機選取組卷，這是試題庫系統(tǒng)普遍使用的方法，這種方法要求控制試題庫的參數(shù)比較集中，對試卷的適用等級范圍限制較大；三是智能組卷，這方法建庫比較困難，要相應建立專家系統(tǒng)和推理機制，缺乏通用性；四是優(yōu)化目標組卷，這是根據(jù)考試要求，命題時從試題庫中選取一組滿足試卷參數(shù)的試題構成試卷?，F(xiàn)在最流行的且最多系統(tǒng)采用的是隨機選題的組卷算法，這是因為很多試題庫系統(tǒng)都是針對專門的科目而設計，這些試題庫系統(tǒng)的題庫結構相對簡單，題量不大，因此不用設計復雜的算法來組卷。例如一些題庫系統(tǒng)它只有單選和多選題，且考試范圍小，因此采用隨機選題算法，這種算法雖然簡單，但成卷效果一般很難令人滿意，因為用戶的期望沒有被算法考慮[14]。也有一些試題庫系統(tǒng)采用了一些比較好的算法，它們都是建立在一個好的組卷模型基礎上。如考慮了用戶對試卷期望及試卷中各項參數(shù)的專家分布曲線，又如松弛法，前移法和隨機抽取法等。選題選題修正模式結束否是圖5.1隨機選取法的基本流程圖分析上述算法，特別是隨機選取法和回溯試探法算法的優(yōu)缺點，不難發(fā)現(xiàn)，在限制條件狀態(tài)空間的控制下，隨機選取法有時能夠抽取出一組令用戶滿意的試題。但是由于它隨機選取的范圍太大，無法確定目前條件下哪些區(qū)域能夠抽取合適的試題，反而可能在那些已經證明是無法抽取合適試題的區(qū)域內反復選題，進行大量的無效操作進入死循環(huán)，最終導致組卷失敗?；厮菰囂椒ńM卷成功率高，但它是以犧牲大量的時間為代價的，對于現(xiàn)今越來越流行的考生網上隨機即時調題的考試過程來說，它已不符合要求。另外，數(shù)據(jù)發(fā)掘和知識發(fā)現(xiàn)作為一門新興的技術雖然已開始用在組卷系統(tǒng)中，但是對它的研究目前都還停留在理論上，缺乏成熟的技術和理論。因此，必須結合以上幾種方法尋找一種新的改進算法，這種算法要具有全局尋優(yōu)和智能搜索技術，并且收斂速度快特點。遺傳算法以其具有自適應全局尋優(yōu)和智能搜索技術，并且收斂性好的特性能很好地滿足自動組卷的要求。所以，它們雖然都能最終組出試卷，但是在實際的操作過程中，卻發(fā)現(xiàn)它們不是耗費的時間很大就是容易進入死循環(huán)。計算機輔助考試系統(tǒng)的自動組卷的效率與質量完全取決于抽題算法的設計，如何設計一個算法從題庫中既快又好的抽出一組最佳解或是抽出一組非常接近最佳解的實體，涉及到一個全局尋優(yōu)和收斂速度快慢的的問題，很多學者對其進行了研究。遺傳算法以其自適應尋優(yōu)及良好的智能搜索技術，受到了廣泛的運用。PottsJC等人基于變異和人工選擇的遺傳算法對最優(yōu)群體規(guī)模進行了論述；HamiltonMA等結合遺傳算法把其運用到神經網絡中，并取得了良好的效果。也有眾多的學者對保留最佳狀態(tài)的遺傳算法的收斂速度做了討論。通過理論推導和事實運用，發(fā)現(xiàn)遺傳算法在尋優(yōu)和收斂性方面都是非常有效的。本文結合遺傳算法的原理和思想，對考試自動出題組卷的問題進行了研究，找到了一種獲得與考試試題控制指標符合的試題模型的解決方法。5.1.2遺傳算法基本知識遺傳算法GA（GeneticAlgorithm）是一種新型的、模擬自然界生物進化過程的隨機化搜索、優(yōu)化方法。它是模擬達爾文的遺傳選擇和自然淘汰的生物進化過程的計算模型，是由美國Michigan大學的JohnH.Holland教授于1975年首先提出的。它采用簡單的編碼技術來表示各種復雜的結構，并通過對一組編碼表示進行簡單的遺傳操作和優(yōu)勝劣汰的自然選擇來指導學習和確定搜索的方向。由于它采用種群的方式組織搜索，這使得它可以同時搜索解空間內的多個區(qū)域。而且用種群組織搜索方式使得遺傳算法特別適合大規(guī)模并行。在賦予遺傳算法自組織、自適應、自學習等特征的同時，優(yōu)勝劣汰的自然選擇和簡單的遺傳操作使遺傳算法具有不受其搜索空間限制性條件（如可微、連續(xù)、單峰等）的約束、不需要其它輔助信息（如導數(shù)）、搜索過程不易陷入局部最優(yōu)點的特點。這些嶄新的特點使得遺傳算法不僅能獲得較高的效率而且具有簡單、易于操作和通用的特性。目前，該算法已滲透到許多領域，并成為解決各領域復雜問題的有力工具。遺傳算法是具有“生成+檢測”（generate-and-test）的迭代過程的搜索算法。在遺傳算法中，將問題空間中的決策變量通過一定編碼方法表示成遺傳空間中的一個個體，它是一個基因型串結構數(shù)據(jù)。同時，將目標函數(shù)值轉換成適應值，它用來評價個體的優(yōu)劣，并作為遺傳操作的依據(jù)。遺傳操作包括三個算子：選擇、交叉和變異。選擇用來實施適者生存的原則，即把當前群體中的個體按與適應值成比例的概率復制到新的群體中，構成交配池（當前代與下一代之間的中間群體）。選擇算子的作用效果是提高了群體的平均適應值。由于選擇算子沒有產生新個體，所以群體中最好個體的適應值不會因選擇操作而有所改進。交叉算子首先將交配池中的個體隨機配對，然后將兩兩配對的個體按某種方式相互交換部分基因。交叉算子是產生新個體的主要方法，它決定了遺傳算法的全局搜索能力。變異是對個體的某一個或某一些基因值按某一較小概率進行改變。變異算子是產生新個體的輔助方法。交叉和變異相配合，共同完成對搜索空間的全局搜索。遺傳算法是一種群體型操作，該操作以群體中的所有個體為對象，選擇、交叉和變異構成的遺傳操作，使遺傳算法有了其它傳統(tǒng)方法所沒有的特征。遺傳操作的設計與參數(shù)編碼、初始群體的生成、適應度函數(shù)的設計、控制參數(shù)設定一起構成了遺傳算法的核心內容，一般將它們稱之為遺傳算法的五大要素[15]。遺傳算法的基本步驟如下：（1）在一定編碼方案下，隨機產生一個初始種群；（2）用相應的編碼方法，將編碼后的個體轉換成問題空間的決策變量，并求得個體的適應值；（3）按照個體適應值的大小，從種群中選出適應值較大的個體構成交配池；（4）由交叉和變異這兩個遺傳算子對交配池中的個體進行操作，并形成新一代的種群；（5）反復執(zhí)行步驟（2）—（4），直至滿足收斂判據(jù)為止。遺傳算法的基本處理流程如圖5.2所示。群體中個體適應度的檢測群體中個體適應度的檢測滿足終止條件？滿足終止條件？是是否否選擇選擇交叉交叉變異變異輸出結果輸出結果圖5.2遺傳算法的基本流程使用遺傳算法需要決定的運行參數(shù)有：編碼串長度、種群大小、交叉和變異概率。編碼串長度由優(yōu)化問題所要求的求解精度決定。種群大小表示種群中所含個體的數(shù)量，種群較小時，可提高遺傳算法的運算速度，但卻降低了群體的多樣性，可能找不出最優(yōu)解；種群較大時，又會增加計算量，使遺傳算法的運行效率降低。一般取種群數(shù)目為20－100。交叉概率控制著交叉操作的頻率，由于交叉操作是遺傳算法中產生新個體的主要方法，所以交叉概率通常應取較大值；但若過大的話，又可能破壞群體的優(yōu)良模式。一般取0.4－0.99。變異概率也是影響新個體產生的一個因素，變異概率小，產生新個體少；變異概率太大，又會使遺傳算法變成隨機搜索。一般取變異概率為0.0001－0.1。遺傳算法常采用的收斂判據(jù)有：規(guī)定遺傳代數(shù)；得到的最優(yōu)個體已滿足搜索要求；連續(xù)幾次得到的最優(yōu)個體的適應值沒有變化或變化很小等[16]。圖5.2遺傳算法的基本流程5.1.3遺傳算法設計的基本步驟在應用遺傳算法求解問題時，需要確定并盡可能地改進算法，以獲得更可靠、高效的解，我們稱這個過程為算法設計。算法設計應在適用性、可靠性、收斂性、穩(wěn)定性以及生物類比等原則下對遺傳算法的編碼表示、適應性度量方法、選擇策略、算子設計、控制參數(shù)選擇及其他改進措施進行設計和改進。設計時一般可以按以下基本步驟進行：（1）確定編碼方案：遺傳算法求解問題不是直接作用在問題的解空間上，而是利用解的某種編碼表示。選擇何種編碼表示有時將對算法的性能、效率等產生很大的影響。（2）確定適應函數(shù)：適應值是對解的質量的一種度量，它通常依賴于解的行為與環(huán)境（即種群）的關系。一般以目標函數(shù)或費用函數(shù)的形式來表示。解的適應值是演化過程中進行選擇的唯一依據(jù)。（3）選擇策略的確定：優(yōu)勝劣汰的選擇機制使得適應值大的解有較高的存活概率，這是遺傳算法與一般搜索算法的主要區(qū)別之一。不同的選擇策略對算法的性能也有較大的影響。（4）控制參數(shù)的選?。嚎刂茀?shù)主要包括種群的規(guī)模、算法執(zhí)行的最大代數(shù)、執(zhí)行不同遺傳操作的概率以及其它一些輔助性控制參數(shù)。（5）遺傳算子的設計：主要包括選擇、交叉、變異以及其它高級操作的設計。（6）確定算法的終止準則：由于遺傳算法沒有利用目標函數(shù)的梯度等信息，所以在演化過程中，無法確定個體在解空間的位置。從而無法用傳統(tǒng)的方法來判定算法的收斂與否以終止算法。常用的辦法是預先規(guī)定一個最大的演化代數(shù)或算法在連續(xù)多少代以后解的適應值沒有什么明顯的改進時，即終止。（7）編程上機運行：完成上述工作以后，即可以按照演化計算的算法結構編程去進行問題求解。上述各基本步驟是密切相關的，編碼方案與遺傳算子的設計等應是同步考慮的[17]。5.1.4遺傳算法應用于組卷系統(tǒng)的優(yōu)勢作為一種優(yōu)化與搜索算法，遺傳算法相比于其它算法應用于組卷系統(tǒng)所具有的優(yōu)勢在于：（1）遺傳算法的操作對象是一組可行解，而非單個可行解，搜索軌道有多條，而非單條，因而具有良好的并行性。（2）遺傳算法只需利用目標的取值信息，而無需梯度等高價值信息，因而適用于任何大規(guī)模、高度非線性的不連續(xù)多峰函數(shù)的優(yōu)化以及解析式的目標函數(shù)的優(yōu)化，具有很強的通用性。（3）遺傳算法擇優(yōu)機制是一種“軟”選擇，加上其良好的并行性，使它具有良好的全局優(yōu)化性和穩(wěn)健性。（4）遺傳算法操作的可行解是經過編碼化的，目標函數(shù)解釋為編碼化個體的適應值，因而具有良好的可操作性與簡單性。（5）遺傳算法易于和別的技術（如神經網絡、模糊推理、混沌行為和人工生命等）相結合，形成性能更優(yōu)的問題求解方法。正是由于遺傳算法的諸多優(yōu)點，很多學者把其應用到組卷系統(tǒng)的研究中，如D.B.Fogeol在神經網絡的進化學習方法的研究中首次提出把遺傳算法用于試題組卷，GordbergM.W應用遺傳算法的尋優(yōu)特性為組卷問題建立了尋優(yōu)模型等。國內的遺傳算法發(fā)展較晚，但也已有將其用于組卷之中的，文獻[17]，[18]，[19]都研究了遺傳算法在組卷問題的應用。5.2基于遺傳算法的組卷方法本文設計了一種新的適用于組卷問題的遺傳算法。實驗結果表明：所設計的組卷方法性能好、效率高，又能很好地避免同一試卷中同一道試題的重復出現(xiàn)，是一種實用有效的組卷方法。5.2.1智能組卷模型組卷系統(tǒng)最基本的目的是根據(jù)用戶的要求，組出一份符合要求的、高質量的試卷。所以首先要做的事便是獲取用戶的組卷要求。一般而言，要出一份試卷，我們總是先確定考試時間ZSJ、試卷的滿分值MFZ和所用的題型以及各種題型的題目數(shù)和分數(shù)，而且對一種考試而言，這種題型—分數(shù)分布曲線LT常保持相對穩(wěn)定，如自學考試、英語等級考試、各種職稱考試等都是這樣。例如，計算機等級考試一級筆試試卷包括判斷題、單選題、多選題、填空題四種題型，其題型—分數(shù)分布曲線LT：（10，30，20，40），各題型分數(shù)允許的誤差為0。然后獲取難度—分數(shù)分布曲線LD、內容—分數(shù)分布曲線LC、教學要求度—分數(shù)分布曲線LR及其各自允許的誤差。曲線LC，LR及其允許的誤差均由用戶給出，或者采用系統(tǒng)的默認曲線（根據(jù)各課程的教學大綱給出的）。曲線LD在很大程度上決定了考試成績的分布，是很重要的一條曲線，高等數(shù)學試題庫系統(tǒng)MATBAS中，將它稱為中心曲線，系統(tǒng)的默認曲線不一定滿足用戶要求，但是要用戶用難度分布曲線LD來表示對試卷的難度要求又比較困難，為此，我們考慮能否找到或建立一個數(shù)學模型，在組卷時，只要求用戶輸入期望的平均分p，由系統(tǒng)計算得到難度分布曲線Ldo。文獻[20]給出了一種用正態(tài)分布方式計算難度分布曲線LD的模型，我們利用該模型進行了測試，試題難度采用五級分檔，試卷滿分值為100，期望的平均分為75時，用該模型計算得到的曲線LD為：｛0，63，7，0，0｝，我們認為這樣的難度曲線是不理想的，試題過分集中在第一、二檔難度，而第四、五檔難度的題都沒有，試卷的區(qū)分度必然較小。我采用離散型隨機變量的二項分布函數(shù)B（n，p）建立了一個由試卷的期望平均分P計算難度分布曲線LD的模型。離散型隨機變量的二項分布函數(shù)B（n，p）：（5-1）其中k=0,1,2,…,n，n為正整數(shù)，p>0，q>0，p+q=1。令q=期望的平均分Ｐ／滿分值ＭＦＺ（即用q表示期望的平均得分率，也就是試卷的平均難度系數(shù)），p=1-q，n=v+1（其中v為難度級別數(shù)，即若試題難度采用五級分檔，就取n=6），代入公式5-1，求得P（k），k=0,1,2,…,n，因為一般而言q>0.6，所以P（n），P（n-1）通常很小，可以將它們加到P（n-2）上，將處理后得到的P（k）（k=0,1,2,…,n）作為難度級別為k+l的分數(shù)比例，再將它們乘以滿分值，便得到難度曲線LD。下面舉例說明：試題難度采用五級分檔，即難度級別為1（易）、2（較易）、3（中等）、4（較難）、5（難），試卷滿分值為100，期望平均分為76時，q=0.76，p=0.24，由公式5-1得到：由于P（5）和P（6）相對很小，可以根據(jù)情況略去或加到P（4）中，P（0），P（1），P（2），P（3），P（4）即是難度級別為1，2，3，4，5的題在試卷中所占的分數(shù)比例，將它們乘以滿分值100，便得到難度分數(shù)分布曲線LD：｛19，37，29，12，31｝，得到的曲線分布合理，與專家給出的曲線相似。我們用此模型進行了很多測試，結果表明，它是非常有效的。例如：對滿分為100分的試卷，期望平均分為80時，得到的難度分數(shù)分布曲線LD為：｛26，39，25，8，2｝，期望平均分為70時，得到的難度分數(shù)分布曲線LD為：｛12，30，32，19，7｝，這些曲線都與專家給出的曲線極為相似。組卷中決定一道試題，也就是決定一個包含有題號、題型、難度、知識點、教學要求度、建議分值的六維向量（a1,a2,a3,a4,a5,a6）（為敘述方便，暫不考慮試題的其它屬性，如區(qū)分度、答題時間、最近使用時間等）。決定一份試卷n道題，就決定了一個n×6的矩陣S：這就是問題求解中的目標狀態(tài)矩陣。下面根據(jù)試題參數(shù)和組卷要求設計建立目標函數(shù)。設ci、xi、ei（i=1,2,…,m，m為章或節(jié)的數(shù)目）分別表示用戶要求的各章節(jié)應占的分數(shù)，實際生成試卷中各章節(jié)所占的分數(shù)，用戶允許各章節(jié)的分數(shù)誤差。對于用戶選定的不需考查的章節(jié)，只要將其ci、ei置為0即可。生成的試卷滿足用戶關于內容—分數(shù)分布要求的程度可以用式5-2值的大小來評價：（5-2）其中由上式可以看出f1的值越小，則生成的試卷越接近于用戶關于內容分數(shù)分布的要求。同樣，設bj,yj,hj（j=1,2,3,…,k；k為教學要求度的檔數(shù)），本文中（k=4）分別表示用戶要求的教學要求度為j檔的題應占的分數(shù)，實際生成試卷中教學要求度為J檔的題應占的分數(shù)，用戶允許教學要求度為j檔的題的分數(shù)誤差。生成的試卷滿足用戶關于教學要求度分數(shù)分布要求的程度可以用式5-3值的大小來評價：（5-3）其中 由公式5-3可以看出f3的值越小，則生成的試卷越接近于用戶關于各教學要求度應占分數(shù)要求。同樣的方法設計函數(shù)f3來反映用戶關于難度的要求，f3的值越小，則生成的試卷越接近于用戶關于試卷難度的要求。對于如何使生成的試卷中各種題型的題目數(shù)滿足用戶的要求，由于題庫中的題目可以按題型進行索引，因此，只要題庫題量充裕，這一要求很容易滿足。綜上所述，得到求解組卷問題的目標函數(shù)：minf=f1+f2+f3。5.2.2智能組卷的遺傳算法設計與實現(xiàn)1、染色體編碼及群體的初始化用遺傳算法求解問題，首先要將問題的解空間映射成一組代碼串。文獻[17]，[18]采用二進制編碼，用1表示該題被選中，0表示該題未被選中，這種編碼簡單明了，但是進行交換等遺傳操作時，各題型的題目數(shù)難以精確控制，而且，當題庫中題量很大時，編碼很長。已有大量實驗表明，在解決數(shù)值優(yōu)化問題時，采用實數(shù)編碼的遺傳算法的效率要好得多，因此本文采用實數(shù)編碼。在組卷中所得的可行解就為一份試卷，所以本文將一份試卷映射為一個染色體，組成試卷的各個試題映射為基因，基因的值直接用試題的題號表示，這樣染色體的編碼可表示為：（Ｇ1,Ｇ2,Ｇ3,…,Ｇn），其中Ｇi（i=1,2,3,…,n，n為試卷的總題目數(shù)）為試題的題號。注意編碼時應將同一題型的題目放在一起，并且為保證一份試卷中知識點不重復，每條染色體中，各基因的知識點編碼必須各不相同。根據(jù)用戶選定的考試內容及各種題型的題目數(shù)，按同一試卷中知識點不重復的原則，隨機生成初始群體，群體的大小按經驗或實驗給出[17]。2、適應度函數(shù)在遺傳算法中，以適應值大小來區(qū)分群體中個體的優(yōu)劣。一般情況下適應值越大的個體越好，適應值越小的個體越差。本文提出的組卷模型是最小化問題，采用如下方法將目標函數(shù)f轉換為適應度函數(shù)Ｆ’：因為指數(shù)比例既可以讓非常好的個體保持多的復制機會，同時又限制了其復制數(shù)目，以免其很快控制整個群體，提高了相近個體間的競爭，所以對上述適應度函數(shù)Ｆ’采取如下指數(shù)比例變換方法轉換為適應度函數(shù)Ｆ：Ｆ＝exp(－βF’)，β取值為－0.03。3、遺傳算子設計（1）選擇算子采用期望值模型選擇機制，即先計算群體中各個個體期望被選中的次數(shù)。M為群體規(guī)模，F(xiàn)i為第i個個體的適應值，用Ni的整數(shù)部分［Ｎi］安排個體i被選中的次數(shù)，這樣共選出個個體，然后對N的小數(shù)部分作為概率進行貝努利試驗，若試驗成功，則該個體被選中，不斷重復，直至選滿為止。顯然，個體適應值愈高，被選中的概率愈大。但是，適應值小的個體也有可能被選中，這樣有助于增加下一代群體的多樣性。（2）交叉算子將以上選出的個體進行兩兩隨機配對，對每一對相互配對的個體采用有條件的“均勻交叉”，即兩個配對個體的每一個基因座上的基因都按設定的交叉概率PC和一定的條件（確保交換后個體仍是有意義的組合）進行交換，產生兩個新個體。具體的操作是：對兩個配對個體的每一個基因座上的基因，先隨機產生一個0－１的實數(shù)r1，如果r1<PC并且滿足交換條件（即交換后個體的各個基因的知識點不重復），則交換該基因座上的基因，否則不交換。（3）變異算子由于普通的變異操作可能會使用戶指定范圍外的題目出現(xiàn)在染色體中，也會使各題型的題數(shù)難以保證，本文采用有條件的變異算子，即每個個體的每一個基因座上的基因都按設定的變異概率Pm在一定范圍內（考試范圍內與該基因題型相同且知識點與本個體其它題的知識點不重復）變異。對經以上交換操作后產生的每一個個體的每一個基因座上的基因，具體的變異操作是：①確定搜索新題的最大次數(shù)s0，令當前搜索新題的次數(shù)s=0；②隨機產生一個0－1的實數(shù)r2，如果r2>Pm，則保持該基因不變；否則，根據(jù)該基因的值（題號），判斷所屬題型；③搜索次數(shù)s加1，若s>s0，則結束搜索新題，保持該基因不變，否則，在該題型的題號范圍內隨機產生一個與該基因值不同的整數(shù)作為新題的題號；④判斷新題的知識點是否在考試范圍內，若否，轉③；⑤判斷新題的知識點是否與本個體其它題的知識點重復，若是，轉③；⑥用新題的題號替換該基因的值。（4）最優(yōu)保存策略進行了選擇、交叉、變異操作后，比較新一代的最好個體與上一代的最好個體的適應值，如下降，則以上一代最好個體替換新一代的最差個體。此策略可以保證迄今為止的最優(yōu)個體不會被交叉、變異等遺傳運算所破壞，它是遺傳算法收斂性的一個重要保證條件。4、算法分析確定參數(shù)：最大代數(shù)MaxGen，群體規(guī)模PopSize，交叉概率PC，變異概率Pm；接收用戶的組卷要求；產生初始群體；當前代數(shù)gen=0；計算群體中各個體的適應值；While（gen<MaxGen&&最好個體的目標函數(shù)值未達到要求）｛根據(jù)個體適應值及選擇策略從當前群體中選擇生成下一代的父體；執(zhí)行交換操作和變異操作生成新一代群體；計算新一代群體中各個體的適應值：比較新一代的最好個體與上一代的最好個體的適應值，如下降，則以上一代最好個體替換新一代的最差個體；輸出當前代數(shù)，群體的平均目標函數(shù)值，最好個體的目標函數(shù)值；gen++；｝輸出最好個體的編碼，計算各章節(jié)分數(shù)、各難度級別的分數(shù)等指標，輸出這些指標的值并與用戶的要求值相比較。在組成的試卷達到用戶要求后，可對所抽取的試卷進行排版打印，并將此試卷所對應的試卷號和試卷名稱以及排版后此試卷所對應的試卷題目、答案所對應的文件的路徑存入試卷庫中。并保存此試卷所對應的試題情況到試卷的情況表中，以便將來考試后進行試卷的統(tǒng)計分析。最后，為了防止組出雷同的試卷應對試題庫進行修改，即對所抽取的試題的使用次數(shù)和最近使用時間進行修改，以便保證試題在一段時間內或連續(xù)的幾份試卷中不重復出現(xiàn)。若對此次抽取的試卷不滿意或只是進行一次試驗，并不利用此次抽取的試卷，可不對它進行修改，但下次抽取的試卷與此次抽取試卷中試題的重復性將提高。5.3實驗結果及分析為驗證上述遺傳算法的可行性和有效性，以我校學生計算機等級考試筆試試卷為模板（試卷結構見表5.3），按照上述思想編制了程序，進行組卷實驗。表5.3我校學生計算機等級考試筆試試卷結構題型判斷題單選題多選題填空題題目數(shù)10301020每小題分數(shù)1122本次實驗題庫共有350道題，有判斷、單選、多選、填空共4種題型，這四種題型的題目數(shù)分別為50，150，50，100；含6章內容，各章分數(shù)比例為：105：66：121：109：33：66。其中題目難度分布情況見表5.4。表5.4試題庫題目難度分布情況難度系數(shù)（得分率）0.0-0.550.55-0.650.65—0.750.75-0.850.85-1難度級別5（難）4（較難）3（中等）2（較易）1（容易）題目數(shù)30501309050分數(shù)589618411050程序的輸入?yún)?shù)有群體規(guī)模、交換概率、最大進化代數(shù)、整卷的難度系數(shù)（期望平均得分率）、各種題型在試卷中的題目數(shù)、各章在試卷中所占的分數(shù)及允許的誤差。組卷要求為：滿分為100，整卷難度系數(shù)0.76（即期望平均得分為76分），各題型題目數(shù)及分數(shù)要求見表5.3。各章所占分數(shù)比例為：20：15：25：5：5：10，允許的誤差為±2，對教學要求度分布參數(shù)未作要求。進行下列組卷實驗，研究基于遺傳算法的組卷程序的收斂性及不同輸入?yún)?shù)對程序收斂性的影響。（1）固定最大代數(shù)MaxGen=250，群體規(guī)模PopSize=80，測試交叉概率PC和變異概率Pm對程序收斂性的影響。①當交叉概率Pc=0，變異概率Pm=0時，隨機運行程序10次，均未能生成滿足組卷要求的試卷。這是因為當PC，Pm均為零時，進化過程中只有選擇操作，只能簡單地將每一代中的優(yōu)勝個體復制到下一代中，無法通過配對交叉、變異產生新的更優(yōu)的個體，搜索空間很小，很難找到全局最優(yōu)或較優(yōu)解。②PC、Pm取非零值，進行了大量實驗，實驗表明：當Pc在0.6－1間，Pm在0.001－0.01間取值時，組卷效果非常好，一般只要經過30－60代的進化，就能組出滿足上述組卷要求的試卷。這里由于交換條件的約束，Pc=l時也并不是所有的基因都進行交換，所以這時組卷效果也很好。③固定PC=0.6，Pm取不同的值進行測試。實驗表明，Pm大于0.05時，組卷效率明顯降低，當Pm大于0.1時，不僅組卷效率大大降低，而且在250代內組卷成功的概率也大大降低。當PC=0.6，Pm=0.01進行20次實驗，組卷成功率為100%，平均所需的進化代數(shù)為30；當PC=0.6，Pm=0.1進行20次實驗，組卷成功率為60%，平均所需的進化代數(shù)為160。這是因為變異雖然增加了群體的多樣性，但是，過多的變異會破壞群體的優(yōu)良模式，甚至會使遺傳算法變成隨機搜索。（2）固定ＭaxGen=250，PC=0.8，Pm=0.005，PopSize分別取10，20，40，80，100，120，150，200，250進行大量實驗，實驗表明：群體規(guī)模大小的選取對算法收斂性的影響較大。當群體規(guī)模取較小值10時，獲得有效試卷的概率較小，隨著群體規(guī)模的擴大，獲得有效試卷的概率增大。這是由于群體規(guī)模太小時，群體中的個體缺乏多樣性，算法的搜索空間分布范圍有限，因而搜索可能停止在未成熟階段，引起未成熟收斂現(xiàn)象。隨著群體規(guī)模的增大，算法的搜索空間增大，獲得最優(yōu)解的機會提高，生成滿足要求試卷所需的進化代數(shù)趨于減少。但這并不能說明群體規(guī)模越大越好。群體規(guī)模太大，會使得搜索空間很大，降低程序的運行效率。由實驗得到，本例中PopSize在40～80間取值，效果最好。本實驗表明，當選擇合適的參數(shù)，即交叉概率取0.6～1.0，變異概率取0.001～0.01，群體規(guī)模取40～80時，用本文所設計的遺傳算法可以有效解決組卷問題，很快找到滿足用戶要求的試卷。由于遺傳算法實行了全局并行搜索，搜索空間大，并且在搜索過程中不斷向可能包含最優(yōu)解的方向調整搜索空間，從而易于找到最優(yōu)解。從實驗結果可以看出，遺傳算法能有效地解決試題庫智能組卷問題。5.4通用組卷系統(tǒng)實現(xiàn)界面5.4.1參數(shù)輸入在生成試卷之前先要設置試卷生成的參數(shù)，包括各種題型的分值，題數(shù)，難度比例以及各種題型在章節(jié)中的試題分配和題量百分比，在輸入時要保證數(shù)據(jù)的完整性和一致性，還要注意百分比之和必須為百分之百。生成試卷之前先要進行參數(shù)分析，參數(shù)分析通過后，才可以生成試卷，如果不行則提示。其界面如圖5.5所示。圖5.5信息輸入界面5.4.2試卷生成預覽界面生成試卷之后，可以對生成的試卷進行預覽，在預覽過程中，如果有需要修改的地方可以進行修改，如果滿意的話，可以直接打印，或者選擇保存。見圖5.6所示。圖5.6試卷生成后預覽界面

結束語經過三個多月的努力，本系統(tǒng)終于完成了！我認為本系統(tǒng)具有如下特點：（1）符合教學改革的要求現(xiàn)代教育教學要求教考分離，試卷規(guī)范化，本系統(tǒng)正是依據(jù)這些原則而設計的。系統(tǒng)針對任課教師與教務處工作人員設置了不同的訪問限制，教師只能錄入，修改試題而沒有出卷的權力。教務處工作人員只能根據(jù)工作要求出試卷，而無權瀏覽題庫中的試題，更無權對題目進行修改，這樣就真正實現(xiàn)了教考分離。系統(tǒng)還為用戶設計了一套標準的試卷卷面模板，確保了卷面的規(guī)范。（2）安全性本系統(tǒng)設置了三類訪問權限：管理員，命題人員（出卷）和錄入人員。通過身份認證機制有效地控制不同人員對系統(tǒng)的訪問級別，確保了系統(tǒng)運行的安全，可靠。（3）通用性本系統(tǒng)可應用于各級各類學校和各種教學機構，幫助各種教學單位實現(xiàn)考務工作的規(guī)范化，自動化。為學校的信息化建設提供一個實用的信息管理平臺。但是，這個系統(tǒng)也存在著一些問題，有待改進：（1）題型是固定的，不能依用戶自由的輸入各種題型。（2）試題錄入時只能單個輸入，不能整套試題輸入。

參考文獻：[1]國家教委考試中心.題庫建設理論與實踐[M].北京:光明日報出版社,2000.[2]宋兆鴻等.現(xiàn)代教育測量[M].北京:教育科學出版社,1999.[3]梁曦.VB程序設計與應用開發(fā)案例教程[M].北京:中國電力出版社,2005.[4]于松濤徐振成等.精通SQLServer2000數(shù)據(jù)庫管理與開發(fā)[M].北京:人民郵電出版社,2001.[5]BobReselman.RichardPeasley,VisualBasic6.0使用指南[M].電子工業(yè)出版社,2003.[6]張海藩.軟件工程導論[M].北京:清華大學出版社,2003.[7]張金.盧勝等.試題庫系統(tǒng)分析[J]微計算機信息,2002,18（2）:72-73.[8]曾紅陳晶周揚.一個VB開發(fā)的試題庫系統(tǒng)[J].佳木斯大學學報,2005,10:552-554.[9]D.B.Forgel.Evolutionary[M].NewYork:IEEEPress.1995:100-120.[10]林永張樂強.VisualBasic6.0用戶編程手冊[M].北京:人民郵電出版社,2002:357-381.[11]北京博彥科技發(fā)展有限責任公司.OfficeVBA編程高手[M].北京:北京大學出版社,2002.[12]錢憶平.通用試卷生成系統(tǒng)的設計[J].江蘇:常熟理工學院學報,2005年,第19卷第四期:112-115.[13]施伯樂丁寶康汪衛(wèi).數(shù)據(jù)庫系統(tǒng)教程[M].高等教育出版社,2005,8.[14]潘志文.網絡試題庫系統(tǒng)的設計及其成卷算法的設計與實現(xiàn)[D].華南理工大學碩士學位論文.2000.[15]米凱利維茨Z,周家駒何險峰譯.演化程序--遺傳q法和數(shù)據(jù)編碼的結合[M].北京:科學出版社,2000.[16]李光明.VisualBasic6.0編程實例[M].北京:冶金工業(yè)出版社,2001.[17]全惠云范國闖等.基于遺傳算法的試題庫智能組卷系統(tǒng)研究[J].武漢大學學報(自然科學版),1999,45(5):758-760.[18]文忠林蔡清萬等.試題庫智能組卷的遺傳算法[J].湖北民族學院報(自然科學版),2000,18(3):53-55.[19]任長虹.基于遺傳算法的組卷方法[D].蘭州大學碩士研究生論文,2001.[20]HollandJH.AdaptationinNatureandArtificialSystem.TheUniversityofMichiganPress,1975.MITPress,1992.

致謝本論文是在符開耀老師的悉心指導下完成的，所以首先在此對符老師致以衷心的感謝，他犧牲自己的周末時間給我耐心講解，在百忙的工作之余為我仔細的審閱論文，我才能夠順利完成論文。我還要感謝湖南科技大學，尤其是計算機學院的老師四年來對我的培養(yǎng)，有了他們的悉心教誨才有我今天的成績。同時我還要感謝同組的其他同學，特別是我的搭檔，一起做通用試題庫系統(tǒng)的曾艷蓮同學，有了他們的關心和幫助，讓我在畢業(yè)設計期間克服困難，最終順利完成設計。謝謝你們，所有關心、鼓勵與支持的朋友!

湖南科技大學本科生畢業(yè)設計（論文）任務書系（教研室）主任審批計算機科學與工程院計算機科學與技術系（教研室）簽名：日期：2006-3-6學生姓名：魏婧學號：202022243專業(yè)：計算機科學與技術設計（論文）題目及專題：試題庫平臺的設計與實現(xiàn)——通用試卷生成系統(tǒng)學生設計（論文）時間：自_3月_6日開始至6_月9日止設計（論文）所用資料和參考資料：[1].BobReselman,RichardPeasley，VisualBasic6.0使用指南[M].電子工業(yè)出版社