畢業(yè)論文---試卷自動(dòng)生成系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)

1、<p>　　試卷自動(dòng)生成系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)</p><p><b>　　摘 要 </b></p><p>　　隨著計(jì)算機(jī)技術(shù)的發(fā)展和智能優(yōu)化算法研究的深入，組卷系統(tǒng)的研究正被越來越多的專家學(xué)者所注意。它不僅涉及到組卷數(shù)學(xué)模型建立的問題，而且還包括相應(yīng)組卷算法的研究。組卷問題是一個(gè)在一定約束條件下的多目標(biāo)參數(shù)優(yōu)化問題，采用傳統(tǒng)的數(shù)學(xué)方法求解十分困難，自動(dòng)組卷的效

2、率和質(zhì)量完全取決于試題庫(kù)的設(shè)計(jì)以及組卷算法的設(shè)計(jì)。因此如何設(shè)計(jì)一個(gè)算法從試題庫(kù)中既快又好地抽出一組最符合考試要求的試題，并基于此實(shí)現(xiàn)智能組卷系統(tǒng)，是本文的研究目的。</p><p>　　遺傳算法(Genetic Algorithm)是一種模擬大自然生物進(jìn)化過程的智能算法，它以其簡(jiǎn)單、魯棒性強(qiáng)、全局尋找以及不受搜索空間限制性條件約束等特點(diǎn)而備受關(guān)注。遺傳算法的群體搜索策略為多目標(biāo)優(yōu)化提供了非常合適的解決方案，因此將

3、其應(yīng)用于組卷問題能取得良好的效果。</p><p>　　本文為實(shí)現(xiàn)試卷自動(dòng)生成系統(tǒng)，從教育測(cè)量學(xué)、人工智能、軟件工程等領(lǐng)域出發(fā)，基于改進(jìn)遺傳算實(shí)現(xiàn)了自動(dòng)組卷算法，建立了試卷自動(dòng)生成系統(tǒng)，驗(yàn)證了該算法的可行性和有效性。</p><p>　　關(guān)鍵詞：遺傳算法，自動(dòng)組卷，數(shù)學(xué)模型，目標(biāo)約束</p><p>　　design and implememtation of te

4、st paper automatic generating system </p><p><b>　　ABSTRACT</b></p><p>　　With the development of computer technology and intelligent in-depth study of optimization algorithm, the rese

5、arch of automatic generating test paper system is being paid attention to by more and more experts and scholars. It not only refers to the establishment of test paper generating mathematical model, but also includes the

6、research of corresponding algorithms. The test paper auto-generating is an optimized problem to multi-objective parameter with a certain constraints. The optimization is </p><p>　　Previous paper generating a

7、lgorithms are mostly based on random selective strategy and recall-test strategy. The former is easy to realize with high time complexity, the latter occupies high space complexity while total question number is comparat

8、ively large, neither has the intelligence. Genetic Algorithm (GA) is an intelligent algorithm, which simulates the natural process of biological evolution. It is being paid more and more attention to with the characteris

9、tics of simple, strong robustness</p><p>　　In order to realize test paper automatic generating system, this paper starts from the fields of education surveying, artificial intelligence, software engineering,

10、 realizes the auto-generation algorithm with the basis of improved Genetic Algorithm, and establishes the test paper automatic generating system to verify the feasibility and effectiveness of this algorithm. </p>

11、<p>　　Key Words: Genetic Algorithms, automatic generating test paper，mathematical model，goal constraints</p><p><b>　　目 錄</b></p><p><b>　　摘 要1</b></p><p&

12、gt;　　ABSTRACT2</p><p><b>　　第一章 緒論1</b></p><p>　　1.1 課題研究背景1</p><p>　　1.2 課題研究現(xiàn)狀2</p><p>　　1.2.1 基于隨機(jī)抽取的自動(dòng)組卷算法2</p><p>　　1.2.2 基于深度與廣度搜索算法的

13、自動(dòng)組卷算法3</p><p>　　1.2.3 基于項(xiàng)目放映理論的自動(dòng)組卷算法3</p><p>　　1.2.4 基于數(shù)據(jù)挖掘和知識(shí)發(fā)現(xiàn)的自動(dòng)組卷算法4</p><p>　　1.2.5 基于遺傳算法的自動(dòng)組卷算法4</p><p>　　1.3 課題研究目的及成果5</p><p>　　1.4 論文內(nèi)容概述6

14、</p><p>　　第二章 組卷的評(píng)價(jià)體系與建模7</p><p>　　2.1 組卷的基本原則7</p><p>　　2.2 試題的幾個(gè)重要屬性指標(biāo)7</p><p>　　2.2.1 題型8</p><p>　　2.2.2 知識(shí)點(diǎn)8</p><p>　　2.2.3 難度8</

15、p><p>　　2.2.4 認(rèn)知層次9</p><p>　　2.2.5 時(shí)間10</p><p>　　2.2.6 曝光度10</p><p>　　2.3 指標(biāo)體系10</p><p>　　2.4 試卷指標(biāo)11</p><p>　　2.4.1 試卷的平均難度11</p>&l

16、t;p>　　2.4.2 效度12</p><p>　　2.4.3 信度12</p><p>　　2.4.4 考試目的12</p><p>　　2.5 試卷模式13</p><p>　　2.5.1 難度-分?jǐn)?shù)分布13</p><p>　　2.5.2 知識(shí)點(diǎn)-分?jǐn)?shù)分布14</p><p

17、>　　2.5.3 題型-分?jǐn)?shù)分布15</p><p>　　2.5.4 認(rèn)知層次-分?jǐn)?shù)分布15</p><p>　　2.5.5 總時(shí)間16</p><p>　　2.5.6 總分?jǐn)?shù)16</p><p>　　2.6 偏差的計(jì)算16</p><p>　　2.7 解得偏好關(guān)系定義17</p>&l

18、t;p>　　2.8 目標(biāo)函數(shù)18</p><p>　　第三章 遺傳算法20</p><p>　　3.1 遺傳算法的概述20</p><p>　　3.2 遺傳算法的特點(diǎn)20</p><p>　　3.3 遺傳算法的運(yùn)用領(lǐng)域21</p><p>　　3.4 遺傳算法中的基本概念22</p>&

19、lt;p>　　3.5 遺傳算法中的基本操作23</p><p>　　3.5.1 選擇23</p><p>　　3.5.2 交叉24</p><p>　　3.5.3 變異24</p><p>　　3.6 遺傳算法中的主要步驟25</p><p>　　3.7 遺傳算法應(yīng)用中的關(guān)鍵問題26</p>

20、;<p>　　3.7.1 編碼方式26</p><p>　　3.7.2 適應(yīng)度函數(shù)的確定27</p><p>　　3.7.3 遺傳算法主要參數(shù)設(shè)定28</p><p>　　第四章 自動(dòng)組卷算法設(shè)計(jì)29</p><p>　　4.1 組卷策略分析29</p><p>　　4.2 組卷約束條件分析2

21、9</p><p>　　4.3 組卷問題數(shù)學(xué)模型的分析29</p><p>　　4.4 組卷過程分析30</p><p>　　4.5 基于改進(jìn)遺傳算法的自動(dòng)組卷的研究31</p><p>　　4.5.1 染色體編碼方案31</p><p>　　4.5.2 生成初始種群32</p><p&g

22、t;　　4.5.3 適應(yīng)度函數(shù)設(shè)計(jì)32</p><p>　　4.5.4 遺傳算子的改進(jìn)32</p><p>　　4.5.5 遺傳算法控制參數(shù)34</p><p>　　4.5.6 最優(yōu)個(gè)體保存策略34</p><p>　　4.5.7 各難度級(jí)別分?jǐn)?shù)的計(jì)算35</p><p>　　4.5.8 自動(dòng)組卷算法的實(shí)現(xiàn)

23、35</p><p>　　第五章 自動(dòng)組卷系統(tǒng)實(shí)現(xiàn)與實(shí)驗(yàn)結(jié)果37</p><p>　　5.1 數(shù)據(jù)庫(kù)結(jié)構(gòu)的設(shè)計(jì)37</p><p>　　5.2 遺傳算法核心模塊38</p><p>　　5.3 試卷自動(dòng)生成系統(tǒng)的運(yùn)行演示42</p><p>　　第六章 總結(jié)與展望49</p><p>

24、　　6.1 論文總結(jié)49</p><p>　　6.2 進(jìn)一步工作49</p><p><b>　　參考文獻(xiàn)51</b></p><p><b>　　致謝53</b></p><p><b>　　附錄54</b></p><p>　　附錄1 畢

25、業(yè)設(shè)計(jì)文獻(xiàn)綜述54</p><p>　　附件2 畢業(yè)設(shè)計(jì)開題報(bào)告54</p><p>　　附件3 畢業(yè)設(shè)計(jì)外文翻譯(中文譯文與外文原文)54</p><p><b>　　第一章 緒論</b></p><p><b>　　課題研究背景</b></p><p>　　在教

26、育領(lǐng)域中，考試是整個(gè)教育過程中的重要環(huán)節(jié)，它是對(duì)學(xué)生所學(xué)知識(shí)和能力的一種評(píng)價(jià)，也是衡量教師教學(xué)效果優(yōu)劣的一種教育測(cè)量手段。目前的許多考試的實(shí)施過程并不完全科學(xué)，考試手段落后，命題內(nèi)容、評(píng)分標(biāo)準(zhǔn)等由于受各種人為因素的干擾，缺乏普遍的可比性，考試信度和效度較低。例如，傳統(tǒng)的檢驗(yàn)型考試是由任課教師分別主持，命題原則不同，評(píng)分標(biāo)準(zhǔn)和評(píng)分方法不同，帶有較大的主觀性，不夠客觀和準(zhǔn)確。</p><p>　　并且組卷這一過程是一

27、項(xiàng)非常繁重的腦力勞動(dòng)，從收集資料到試題的選取、試題分值的設(shè)置等工作非常繁瑣。因此如果仍然采用傳統(tǒng)的組卷方式就很難跟上時(shí)代的步伐，隨著計(jì)算機(jī)科學(xué)的迅速發(fā)展和廣泛應(yīng)用，計(jì)算機(jī)輔助教學(xué)CAI（Computer Aided Instruction）的產(chǎn)生與發(fā)展對(duì)促進(jìn)教育、教學(xué)技術(shù)的變革與發(fā)展具有巨大的推動(dòng)作用。利用計(jì)算機(jī)建立試題庫(kù)，實(shí)現(xiàn)計(jì)算機(jī)自動(dòng)選題組卷，是CAI工程的重要組成部分，是實(shí)現(xiàn)考試規(guī)范化、科學(xué)化的重要措施，更是實(shí)現(xiàn)教考分離的一個(gè)重要

28、手段。</p><p>　　自動(dòng)組卷系統(tǒng)，不僅能節(jié)省教師寶貴的時(shí)間，提高工作效率，還能消除人為因素的干擾，使考試更加標(biāo)準(zhǔn)化，更能客觀、真實(shí)、全面地反映教學(xué)的實(shí)際效果。有利于促使任課教師必須按照教學(xué)大綱的要求認(rèn)真?zhèn)湔n，認(rèn)真組織教學(xué)內(nèi)容，改進(jìn)教學(xué)方法，因此對(duì)教學(xué)質(zhì)量和整體教學(xué)水平的提高有著重要意義。還可利用智能組卷系統(tǒng)對(duì)試卷和考試分?jǐn)?shù)進(jìn)行分析和評(píng)價(jià)，使考試這一教學(xué)環(huán)節(jié)更加科學(xué)化。為了提高考試的科學(xué)化程度，把數(shù)理統(tǒng)計(jì)的

29、方法引入考試工作，對(duì)試卷的編制和考試的質(zhì)量進(jìn)行定量分析。建立試題庫(kù)，實(shí)現(xiàn)智能組卷得以實(shí)施科學(xué)化的考試，有助于是對(duì)教學(xué)工作加強(qiáng)宏觀指導(dǎo)和管理，將課程教學(xué)的科學(xué)管理變成現(xiàn)實(shí)。</p><p>　　設(shè)計(jì)實(shí)現(xiàn)自動(dòng)組卷系統(tǒng)，是一項(xiàng)自然科學(xué)與教育科學(xué)，學(xué)術(shù)研究與教學(xué)研究相結(jié)合的研制課題，它運(yùn)用教育測(cè)量學(xué)、考試學(xué)、教育統(tǒng)計(jì)學(xué)的理論和方法，總結(jié)教師的考試經(jīng)驗(yàn)，建立科學(xué)的組卷理論，從而借助于計(jì)算機(jī)的先進(jìn)技術(shù)來實(shí)現(xiàn)。</p&g

30、t;<p><b>　　課題研究現(xiàn)狀</b></p><p>　　在國(guó)外，一些標(biāo)準(zhǔn)化考試系統(tǒng)，如美國(guó)的TOEFL、GRE等考試系統(tǒng)早已建立并成功運(yùn)行了幾十年，一直都能科學(xué)地測(cè)試出學(xué)生的實(shí)際水平。這說明自動(dòng)組卷式可能的而且有效地，但這些系統(tǒng)所涉及到的具體內(nèi)容以及其設(shè)計(jì)思想與原理幾乎都是保密的。因此我們必需依靠自己的努力研制一套符合中國(guó)國(guó)情的試題庫(kù)組卷系統(tǒng)。</p>

31、<p>　　在國(guó)內(nèi)，已研制成功的計(jì)算機(jī)考試系統(tǒng)有高等數(shù)學(xué)試題庫(kù)系統(tǒng)MATBAS[1],南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系研制的PASCAL題庫(kù)系統(tǒng)，高教司的重點(diǎn)項(xiàng)目基于知識(shí)的成卷系統(tǒng)使用外殼軟件[2]等系統(tǒng)，但是這些系統(tǒng)大多數(shù)沒有自動(dòng)組卷功能，考試所需的試題仍需要人工定制，因此在近十幾年又出現(xiàn)了大量針對(duì)各種考試的計(jì)算機(jī)考試系統(tǒng)。計(jì)算機(jī)考試系統(tǒng)的發(fā)展同時(shí)推動(dòng)了組卷系統(tǒng)的研究。</p><p>　　組卷問題是一個(gè)帶

32、約束的多目標(biāo)優(yōu)化問題，采用經(jīng)典的數(shù)學(xué)方法很難解決這個(gè)難題，自動(dòng)組卷的效率和質(zhì)量完全取決于抽題算法的設(shè)計(jì)。如何設(shè)計(jì)一個(gè)算法從試題庫(kù)既快又好地抽出一組最符合考試要求的試題，涉及到一個(gè)全局尋優(yōu)和收斂速度慢的問題。目前的自動(dòng)組卷系統(tǒng)根據(jù)其所使用的組卷策略大致分為五類：</p><p>　　基于隨機(jī)抽取的自動(dòng)組卷算法[3]</p><p>　　基于深度與廣度搜索算法的自動(dòng)組卷</p>

33、<p>　　基于項(xiàng)目反映理論的自適應(yīng)測(cè)試</p><p>　　基于數(shù)據(jù)挖掘和知識(shí)發(fā)現(xiàn)的自動(dòng)組卷理論</p><p>　　基于遺傳算法的自動(dòng)組卷</p><p>　　1.2.1 基于隨機(jī)抽取的自動(dòng)組卷算法</p><p>　　由于用戶在操作該系統(tǒng)生成試卷時(shí)會(huì)提出一系列的約束條件，如試卷專業(yè)類別、題目類型、難度分布、知識(shí)點(diǎn)分布、試題分值

34、等等。而在理論與實(shí)際應(yīng)用中都無(wú)法將這些約束條件用一種單一的表達(dá)式進(jìn)行綜合處理，因此也不存在最優(yōu)化的思想。隨機(jī)抽取的策略，通常是從試題庫(kù)中隨機(jī)抽取某個(gè)試題與用戶提出的約束條件進(jìn)行比較，取出滿足某項(xiàng)約束指標(biāo)的加入試卷，若所有試題都試探過多不能滿足當(dāng)前試卷約束條件，則組卷過程失敗。</p><p>　　1.2.2 基于深度與廣度搜索算法的自動(dòng)組卷算法</p><p>　　該類型的自動(dòng)組卷算法又被

35、稱為回溯試探法。它在組卷過程中采用隨機(jī)的方法抽取試題，而在抽取過程中通過驗(yàn)證所選擇的試題是否滿足給定的約束條件來決定是否抽取，當(dāng)發(fā)現(xiàn)目前沒有任何試題滿足要求而組卷過程又沒有完成時(shí)，則采用回溯試探方法，通過廢棄前一段時(shí)間所做的組卷來重新組卷。由于這種方法在組卷過程中通過廢棄部分工作而不是廢棄本次組卷過程中的全部操作，從而有效地降低了無(wú)效組卷的次數(shù)，使得自動(dòng)組卷算法性能得到提高，同時(shí)算法實(shí)現(xiàn)也容易。</p><p>

36、　　熊文清等于1999年通過對(duì)試題按某個(gè)性能指標(biāo)進(jìn)行排序，當(dāng)發(fā)生組卷失敗情況時(shí)，將發(fā)生組卷失敗的試題與前面的試題進(jìn)行呼喚，以調(diào)整原有的組卷次序，重新進(jìn)行組卷過程[4]；葉勇等于1998年分析了三種基于回溯算法的組卷匹配方法，并進(jìn)行了相應(yīng)的比較，在其基礎(chǔ)上給出了智能試題庫(kù)管理系統(tǒng)的設(shè)計(jì)思想[5]。</p><p>　　1.2.3 基于項(xiàng)目放映理論的自動(dòng)組卷算法</p><p>　　項(xiàng)目反映理

37、論（Item Response Theory, IRT）是一系列心理統(tǒng)計(jì)學(xué)模型的總稱，是針對(duì)經(jīng)典測(cè)量理論（Classical Test Theory, CTT）的局限性提出來的。基于IRT的自動(dòng)組卷算法是由最早的適應(yīng)性測(cè)試發(fā)展而來的。William W. Turn Bull于1951年最早提出了適應(yīng)性測(cè)試這一概念，當(dāng)時(shí)，適應(yīng)性測(cè)試是指針對(duì)被試先前經(jīng)驗(yàn)或者說被試先前測(cè)試的歷史信息選取適合被試的題目進(jìn)行組卷測(cè)試，作答后立即評(píng)分，并以上一題的

38、作答情況決定下一道被使用的測(cè)試試題，直至測(cè)試結(jié)束為止。測(cè)試的整個(gè)過程即是從題庫(kù)中選取符合被試能力水平的題目進(jìn)行測(cè)試的過程。</p><p>　　在考試開始時(shí)，系統(tǒng)被測(cè)者的潛在特質(zhì)一般一無(wú)所知，所以通常的方法是選取中等難度的試題，即假定所有考生的能力值為中等，在題庫(kù)中隨機(jī)抽取難度為中等的題目，作為測(cè)試的開始點(diǎn)。隨后，每當(dāng)考生回答一道題后，系統(tǒng)將對(duì)學(xué)生的能力值重新評(píng)估并修正原先的能力值，然后從試題庫(kù)中選取下一道試題，

39、該過程直到對(duì)考生能力的測(cè)量精度達(dá)到指定的水平。</p><p>　　Win J.vander Linden等在2000年試圖利用學(xué)生的實(shí)際參與考試的情況對(duì)試題庫(kù)中的各個(gè)單元實(shí)體的性能指標(biāo)進(jìn)行評(píng)估，以便得到較為真實(shí)反映單元試題難度、時(shí)間等性能指標(biāo)的標(biāo)準(zhǔn)值，提出了利用基于項(xiàng)目發(fā)音理論的方法，通過建立一個(gè)反映考生做大反應(yīng)與題目質(zhì)量及水平間的線性模型，對(duì)考生的能力水平進(jìn)行估算，從而得出該考生能力的測(cè)量[6，7]。<

40、/p><p>　　1.2.4 基于數(shù)據(jù)挖掘和知識(shí)發(fā)現(xiàn)的自動(dòng)組卷算法</p><p>　　數(shù)據(jù)挖掘和知識(shí)發(fā)現(xiàn)作為一門新的研究領(lǐng)域，涉及到機(jī)器學(xué)習(xí)、模式識(shí)別、統(tǒng)計(jì)學(xué)、數(shù)據(jù)庫(kù)和人工智能等學(xué)科。特別是它被看作是數(shù)據(jù)庫(kù)理論和機(jī)器學(xué)習(xí)的交叉學(xué)科[8]。作為一種獨(dú)立于應(yīng)用的技術(shù)，受到了廣泛的關(guān)注，有著廣泛的前景，可以應(yīng)用于商業(yè)管理、科學(xué)研究、智能決策、故障診斷等方面，當(dāng)然也被應(yīng)用于組卷系統(tǒng)中。目前國(guó)內(nèi)數(shù)據(jù)挖

41、掘的研究重點(diǎn)是找出頻繁項(xiàng)目集(frequent item-sets)。典型的關(guān)聯(lián)規(guī)則挖掘算法有R.AGRAWAL等人提出的Apriori 算法 DHP算法等。它們都屬于數(shù)據(jù)庫(kù)遍歷類算法。R.AGRAWAL提出的Apriori-Hybrid算法，Park[9]等人提出的DHP算法(Direct Hashing and Pruning)使用哈希(Hashing) 技術(shù)有效地改進(jìn)了候選集Ck的產(chǎn)生過程。SavaSers等人在1995年提出了一

42、種把數(shù)據(jù)庫(kù)分割處理的算法，降低采掘過程中的I/O次數(shù)，減輕了CPU的負(fù)擔(dān)。H.Toivoen使用抽樣(sampling)的方法可以用較小的代價(jià)從大型數(shù)據(jù)庫(kù)中找出關(guān)聯(lián)規(guī)則[10]。</p><p>　　1.2.5 基于遺傳算法的自動(dòng)組卷算法</p><p>　　遺傳算法（Genetic Algorithm, GA）是模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進(jìn)化過程的計(jì)算模型[11]，它的產(chǎn)生歸功

43、于美國(guó)的Michigan大學(xué)的Holland在20世紀(jì)60年代末、70年代初的開創(chuàng)性工作，其本意是在人工適應(yīng)系統(tǒng)中設(shè)計(jì)的一種基于自然演化原理搜索機(jī)制。它通過模擬達(dá)爾文“優(yōu)勝劣汰、適者生存”的原理激勵(lì)好的結(jié)構(gòu)：通過模擬孟德爾遺傳變異理論的迭代過程中保持已有的結(jié)構(gòu)，同時(shí)尋找更好的結(jié)構(gòu)。從某種程度上說遺傳算法是對(duì)生物進(jìn)化過程進(jìn)行的數(shù)學(xué)方式仿真。遺傳算法作為一種新的全局優(yōu)化搜索算法，以其簡(jiǎn)單通用、適用于并行處理以及應(yīng)用范圍廣等顯著特點(diǎn)，奠定了它

44、作為21世紀(jì)關(guān)鍵智能計(jì)算方法之一的地位。</p><p>　　遺傳算法是具有“生成+檢測(cè)”迭代過程的搜索算法，其基本出流程如圖1.1所示。</p><p>　　圖1.1 遺傳算法基本流程圖</p><p>　　遺傳算法是一種群體型操作，該操作以群體中的所有個(gè)體為對(duì)象，選擇（Selection）、交叉（Crossover）和變異（Mutation）是遺傳算法的三個(gè)主要

45、操作算子（Genetic Operation），它們構(gòu)成了所謂的遺傳操作，使遺傳算法具有了其他方法所沒有的特性。</p><p>　　基于遺傳算法的自動(dòng)組卷將每道試題作為一個(gè)獨(dú)立的編碼位，利用遺傳算法的三個(gè)基本操作：遺傳、交叉與變異并最終完成試題的選取，從而得到滿足各種條件的試題集合，完成組卷工作。</p><p>　　在目前的計(jì)算機(jī)自動(dòng)組卷算法研究中，許多研究者利用遺傳算法在計(jì)算機(jī)自動(dòng)組

46、卷方法的應(yīng)用展開了大量的研究。魏平、毛秉毅等[12，13]采用傳統(tǒng)的遺傳算法(SGA)來實(shí)現(xiàn)試題庫(kù)的自動(dòng)組卷，取得了較好的效果。但傳統(tǒng)遺傳算法容易產(chǎn)生“早熟收斂”現(xiàn)象。目前已經(jīng)有很多研究人員把改進(jìn)的遺傳算法應(yīng)用到組卷中，以提高組卷運(yùn)行效率。劉彬等[14]對(duì)題型確定過程中的知識(shí)進(jìn)行改進(jìn)，相對(duì)于簡(jiǎn)單遺傳算取得了較好的結(jié)果。</p><p><b>　　課題研究目的及成果</b></p>

47、;<p>　　本課題的研究目的：對(duì)組卷算法進(jìn)行深入研究，在高校題庫(kù)管理系統(tǒng)的基礎(chǔ)上，將遺傳算法實(shí)現(xiàn)并運(yùn)用到智能組卷系統(tǒng)中，實(shí)現(xiàn)自動(dòng)組卷系統(tǒng)的基本功能。</p><p><b>　　本課題的成果：</b></p><p>　　(1) 在傳統(tǒng)遺傳算法的基礎(chǔ)上對(duì)編碼方式、適應(yīng)度函數(shù)、遺傳算子進(jìn)行了一些研究和改進(jìn)；</p><p>　　(

48、2) 根據(jù)遺傳算法自動(dòng)組卷的需要設(shè)計(jì)了相應(yīng)的試題庫(kù)結(jié)構(gòu)；</p><p>　　(3) 建立了一個(gè)以難度系數(shù)、知識(shí)點(diǎn)、題型等為核心屬性的智能組卷數(shù)學(xué)模型；</p><p>　　(4) 設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)基于改進(jìn)遺傳算法實(shí)現(xiàn)自動(dòng)組卷的方法。</p><p><b>　　論文內(nèi)容概述</b></p><p>　　論文主要分為6個(gè)

49、章節(jié)：第1章緒論，主要是本課題研究背景、研究現(xiàn)狀的介紹，對(duì)幾種組卷算法作了介紹，然后給出了畢業(yè)課題的研究目的和成果。第2章介紹了自動(dòng)組卷系統(tǒng)的組卷基本原則，分析了試題的屬性指標(biāo)、試卷的評(píng)價(jià)指標(biāo)、各項(xiàng)指標(biāo)的作用及幾個(gè)重要指標(biāo)間的關(guān)系。第3章介紹了遺傳算法的基本概念和基礎(chǔ)知識(shí)、遺傳算法的設(shè)計(jì)與實(shí)現(xiàn)等。第4章基于遺傳算法建立了自動(dòng)組卷的數(shù)學(xué)模型，并將遺傳算法具體應(yīng)用于試題抽取。第5章基于遺傳算法自動(dòng)組卷系統(tǒng)的研究對(duì)試卷生成系統(tǒng)進(jìn)行了分析設(shè)計(jì)，

50、并基于Java技術(shù)實(shí)現(xiàn)了算法原型。第6章對(duì)文章進(jìn)行了總結(jié)，提出了自動(dòng)組卷過程中還存在的其他問題，并對(duì)論文下一步的工作進(jìn)行了展望。</p><p>　　第二章 組卷的評(píng)價(jià)體系與建模</p><p><b>　　組卷的基本原則</b></p><p>　　對(duì)于一般的測(cè)試來說，一方面主要是用于學(xué)生自測(cè)，檢驗(yàn)自己對(duì)學(xué)科知識(shí)的掌握程度；另一方面用于教師對(duì)

51、學(xué)生進(jìn)行考試，考察教學(xué)效果，進(jìn)而改進(jìn)教學(xué)方法。這兩個(gè)方面的用處均在于考察學(xué)生知道什么、能做什么，因此屬于目標(biāo)參照性測(cè)驗(yàn)。對(duì)于大規(guī)模的人才選拔，考慮到公平性和保密性，一般不會(huì)采用自動(dòng)組卷系統(tǒng)；而對(duì)于小規(guī)模的人才考核，一般也不會(huì)采用這種復(fù)雜的考察方式，而是采用最新的項(xiàng)目反應(yīng)理論進(jìn)行測(cè)試。因此本文研究的自動(dòng)組卷系統(tǒng)主要側(cè)重于目標(biāo)參照性測(cè)驗(yàn)。</p><p>　　對(duì)于目標(biāo)參照性測(cè)驗(yàn)，組卷的基本原則[15]主要體現(xiàn)在：&l

52、t;/p><p>　　組卷的主要依據(jù)是考試大綱，組卷必須全面反映大綱的廣度和深度；</p><p>　　組卷要利于考核考生能力和促進(jìn)考生智力發(fā)展；</p><p>　　組卷要講究層次，要有難度臺(tái)階，才能在分?jǐn)?shù)上拉開距離；</p><p>　　命題要注重發(fā)揮考題對(duì)考生學(xué)習(xí)方法的引導(dǎo)；</p><p>　　考試不能出現(xiàn)偏題、怪

53、題，但要有一定得深度，要能測(cè)量出考生的不同知識(shí)水平和智能差異；</p><p>　　命題的表達(dá)語(yǔ)或指導(dǎo)語(yǔ)要清楚無(wú)誤，以提高考試的信度。</p><p>　　組卷工作是一項(xiàng)復(fù)雜的智力勞動(dòng)，組卷者首先要研究考試大綱和命題計(jì)劃，明確考試的目的、對(duì)象、性質(zhì)，試題的形式、數(shù)目，試題數(shù)量和分?jǐn)?shù)在各部分中的分配比例，考查的重點(diǎn)和其它要求。其次，根據(jù)命題計(jì)劃編制試題，給出答案，并對(duì)編出的試題進(jìn)行審查、修改

54、和篩選，同時(shí)注明各試題的預(yù)計(jì)難度、所屬知識(shí)點(diǎn)和認(rèn)知層次，分?jǐn)?shù)及預(yù)計(jì)答題時(shí)間。</p><p>　　試題的幾個(gè)重要屬性指標(biāo)</p><p>　　試題都是存放在試題庫(kù)中，而試題本身含有固有的屬性，試題各項(xiàng)屬性指標(biāo)的確定直接影響到組卷系統(tǒng)的準(zhǔn)確性和工作效率。試題庫(kù)中的內(nèi)容將直接用于試卷之中，所以試題庫(kù)結(jié)構(gòu)的設(shè)計(jì)師組卷問題的重要內(nèi)容。試題的屬性指標(biāo)定量地描述了每一道試題的內(nèi)在屬性、外部特征以及它在

55、考試測(cè)驗(yàn)中的功能，是計(jì)算機(jī)進(jìn)行抽題組卷的基礎(chǔ)。試題的難度、區(qū)分度都是試題的重要質(zhì)量指標(biāo)，然而考慮到區(qū)分度需由試題被使用后統(tǒng)計(jì)計(jì)算所得，一般難以在試題入庫(kù)之時(shí)確定，而試題難度可在試題入庫(kù)時(shí)由輸題教師預(yù)測(cè)下故本文未采用，本文定義的試題指標(biāo)體系為B={題型，知識(shí)點(diǎn)，難度，認(rèn)知層次，答題時(shí)間，曝光度}，以下對(duì)試題指標(biāo)體系的構(gòu)成進(jìn)行詳細(xì)的闡述。</p><p><b>　　2.2.1 題型</b>&l

56、t;/p><p>　　試題的類型有多種形式，一般是指從試題形式上區(qū)分，具體的試題類型可分為：選擇題（包括單選、多選和不定項(xiàng)選擇）、填空題、判斷題、計(jì)算題、編程題、解答題等。</p><p><b>　　2.2.2 知識(shí)點(diǎn)</b></p><p>　　知識(shí)點(diǎn)一般是以課程的章節(jié)進(jìn)行劃分的，考慮到同一科目可能前后會(huì)使用不同的教科書，所以本文采用對(duì)應(yīng)課程的

57、單個(gè)知識(shí)要點(diǎn)作為試題指標(biāo)體系的知識(shí)點(diǎn)。知識(shí)點(diǎn)是考察能力的載體，因此以知識(shí)點(diǎn)的分值分布來組織試題是合理的。</p><p><b>　　2.2.3 難度</b></p><p>　　在組卷過程中，針對(duì)不同的考試目的、不同階段的考試，考試的命題難度應(yīng)該相應(yīng)地不同，這對(duì)試題來說是非常重要的一個(gè)屬性。本文設(shè)計(jì)的試題難度分為五個(gè)等級(jí)，具體參見表2.1所示。</p>

58、<p>　　表2.1 試題的難度級(jí)別和難度系數(shù)對(duì)照表</p><p>　　試題的難度[16]值是指全體被試對(duì)該題的失分率，用符號(hào)D表示。其計(jì)算公式為：</p><p><b>　?。?-1）</b></p><p>　　式中，D是試題的難度值；為全體被試在該題上得分的平均數(shù)；為該題的滿分值。從公式可知，越大，越小，當(dāng)；越小，越大，當(dāng)

59、。的取值范圍：。</p><p>　　上面公式中定義的難度，是指某道試題的難度；一次測(cè)驗(yàn)的難度，是指測(cè)驗(yàn)卷中所有試題的平均難度。測(cè)驗(yàn)的難度，要根據(jù)測(cè)驗(yàn)的目的、測(cè)驗(yàn)的性質(zhì)和測(cè)驗(yàn)項(xiàng)目的形式等因素來確定。</p><p>　　當(dāng)測(cè)驗(yàn)用于考查被試某種知識(shí)技能的掌握情況時(shí)，對(duì)難度可以不作嚴(yán)格限制，只要是應(yīng)該掌握的內(nèi)容，即使它的難度值為0或者難度值為接近1，也應(yīng)該采用；當(dāng)測(cè)驗(yàn)用于最大程度地區(qū)分考生時(shí)，

60、難度恒定在0.50左右最為合適。例如全國(guó)高等學(xué)校入學(xué)考試其難度規(guī)定為3:5:2，即較容易的題目占30%，中等難度的題目占50%，較難的題目占20%，整個(gè)試卷的平均難度大約為0.50。</p><p>　　2.2.4 認(rèn)知層次</p><p>　　認(rèn)知層次是反映學(xué)生對(duì)知識(shí)獨(dú)立獲取和駕馭的程度。布盧姆等人把認(rèn)知領(lǐng)域的教育目標(biāo)，從低級(jí)到高級(jí)共分為識(shí)記、領(lǐng)會(huì)、運(yùn)用、分析、綜合、評(píng)價(jià)六個(gè)層次、如下圖

61、2.1所示。</p><p>　　圖2.1 認(rèn)知領(lǐng)域教育目標(biāo)分類及層次結(jié)構(gòu)示意圖</p><p><b>　　2.2.5 時(shí)間</b></p><p>　　完成該試題所需的估計(jì)時(shí)間</p><p><b>　　2.2.6 曝光度</b></p><p>　　試卷中試題曾被考

62、過的次數(shù)愈多，該試題曝光度就愈大。一般要求曝光度值越小越好，以保證試題的保密性和有效性。</p><p>　　題目的已出題次數(shù)和最近使用時(shí)間兩個(gè)參數(shù)可以控制題目的曝光度。為了試卷的保密性、公平性和安全性起見，在抽取題目組成試卷的時(shí)候，需要控制題目的曝光度?？刂破毓舛扔袃煞矫娴目紤]，一方面，如果題目在規(guī)定的日期范圍之后被使用過，本次就不再使用；另一方面，如果有幾次同時(shí)都滿足條件的題目可供選擇，那么在抽取試題的時(shí)候應(yīng)

63、該選擇使用次數(shù)少的題目，以達(dá)到使用上的平衡和控制曝光度的目的。</p><p><b>　　指標(biāo)體系</b></p><p>　　指標(biāo)體系是指試題參數(shù)，是對(duì)試題的內(nèi)在屬性、外在特征及其在紅的功能進(jìn)行的定性的或定量的描述。它是建立是題庫(kù)管理系統(tǒng)，實(shí)現(xiàn)計(jì)算機(jī)自動(dòng)命題組卷的關(guān)鍵，實(shí)踐證明試題本身含有一些固有的特性參數(shù)。這些固有的特性參數(shù)都需要用相應(yīng)的指標(biāo)來刻畫；另外，對(duì)于組

64、卷來說這些指標(biāo)同時(shí)指導(dǎo)組卷的選題，因此，我們有必要建立一個(gè)試題的指標(biāo)體系，支持組卷模塊功能。整個(gè)指標(biāo)體系確定如表2.2所示。</p><p>　　表2.2 試題的指標(biāo)體系</p><p><b>　　試卷指標(biāo)</b></p><p>　　試題指標(biāo)是建立試題庫(kù)的基礎(chǔ)，試題庫(kù)的建立就是為了克服人為地主觀性和片面性，提高組卷的客觀性和科學(xué)性，以及組

65、卷的質(zhì)量和效率。試卷指標(biāo)也是組卷過程中的一個(gè)關(guān)鍵因素，用戶在提出組卷需求時(shí)，不能對(duì)單個(gè)試題指標(biāo)提出要求，但是可以對(duì)整份試卷提出相關(guān)要求，因此也需要了解試卷指標(biāo)。</p><p>　　本文定義的試卷指標(biāo)體系為S={試卷的平均難度，效度，信度，考試目的}。以下對(duì)試卷指標(biāo)體系的構(gòu)成進(jìn)行詳細(xì)的闡述。</p><p>　　2.4.1 試卷的平均難度</p><p>　　試卷的

66、平均難度即試卷的難度期望值，可采用題分題數(shù)加權(quán)法計(jì)算，公式為：</p><p><b>　?。?-2）</b></p><p>　　其中，n為試卷題目總數(shù)，為第i道題的分值，為第i道題的難度值。一份試卷的難度期望值也決定了考生的平均成績(jī)。通過對(duì)大量樣本試卷的分析表明，學(xué)生成績(jī)應(yīng)大致呈正態(tài)分布。</p><p><b>　?。?-3）

67、</b></p><p>　　其中，為學(xué)生的平均成績(jī)，為試卷的總分，通過給定試卷的平均難度，可以預(yù)估計(jì)考生的平均成績(jī)。</p><p><b>　　2.4.2 效度</b></p><p>　　即有效性，指考試實(shí)現(xiàn)時(shí)所要測(cè)量的知識(shí)、技能和能力的精確程度。對(duì)結(jié)果而言，效度反映了考試是否準(zhǔn)確、真實(shí)地測(cè)量了所要測(cè)量的內(nèi)容，它是綜合衡量系統(tǒng)

68、誤差和隨機(jī)誤差控制程度的指標(biāo)，由下面三種形式反映[17]。</p><p>　　內(nèi)容效度：側(cè)重于測(cè)驗(yàn)題目取樣的代表性，考查這些題目對(duì)所欲測(cè)量的內(nèi)容的有效程度；</p><p>　　結(jié)構(gòu)效度：側(cè)重于測(cè)驗(yàn)?zāi)軌驕y(cè)量到心理學(xué)和教學(xué)理論上的抽象概念和特質(zhì)的程度；</p><p>　　效標(biāo)效度：側(cè)重于測(cè)驗(yàn)分?jǐn)?shù)預(yù)測(cè)我們所關(guān)心的外在行為的準(zhǔn)確程度。</p><p

69、><b>　　2.4.3 信度</b></p><p>　　又稱可靠性，是指考試的一致性程度。通常是以估計(jì)的方法得到信度系數(shù)，以它的大小來表示考試信度的高低，常用的估計(jì)方法[17]有：</p><p><b>　?。?-4）</b></p><p>　　其中，表示所有題目數(shù)，為題目i通過率，是考試總分的方差，為信度系

70、數(shù)。</p><p>　　2.4.4 考試目的</p><p>　　考試目的可分為一般綜合性考試、競(jìng)賽考試和單元測(cè)驗(yàn)等?？荚嚹康臎Q定下面兩個(gè)方面的內(nèi)容：</p><p>　　第一方面是組卷時(shí)試卷難易程度的設(shè)置。考試目的不同，試卷的平均難度不同，則不同難度等級(jí)試題的分?jǐn)?shù)比例分別不同。</p><p>　　第二方面是試題的各種考查要求比例設(shè)置。考

71、試目的不同，則不同考查要求的試題比例也不相同。</p><p><b>　　試卷模式</b></p><p>　　上述兩小節(jié)討論了試題和試卷各項(xiàng)屬性指標(biāo)。試卷模式是對(duì)用戶需求的一個(gè)定量反映，是建立在詳細(xì)分析試題和試卷各項(xiàng)指標(biāo)要求基礎(chǔ)之上。由用戶輸入對(duì)一份試卷的基本要求，組卷系統(tǒng)將用戶對(duì)試卷的命題要求量化處理生成當(dāng)前試卷模式，并將此模式作為抽題組卷的依據(jù)。</p&

72、gt;<p>　　試卷模式并不是可以任意構(gòu)造的。在系統(tǒng)分析的過程中，我們發(fā)現(xiàn)試卷模式必須體現(xiàn)如下三個(gè)因素[17]：</p><p><b>　　專家知識(shí)性；</b></p><p>　　與試題庫(kù)結(jié)構(gòu)分布相容性；</p><p>　　典型性，從而體現(xiàn)靈活性。</p><p>　　建立試卷模式的基本思想是：通過

73、研究專家對(duì)大量試卷的統(tǒng)計(jì)分析，獲得試卷屬性間的一些轉(zhuǎn)換關(guān)系，最終產(chǎn)生符合用戶命題信息設(shè)計(jì)要求的當(dāng)前試卷模式[17]。</p><p>　　試卷模式可通過確定性參數(shù)和分布曲線來描述。分布曲線是試題相應(yīng)的指標(biāo)在試卷中所占的比例，也稱之為“指標(biāo)曲線”，它是控制和描述試卷質(zhì)量的具體要求[17]。</p><p>　　本文用到的試卷模式是由文獻(xiàn)[18]提出的，其詳細(xì)描述如下：</p>

74、<p>　　2.5.1 難度-分?jǐn)?shù)分布</p><p>　　把難度級(jí)別劃分為五個(gè)等級(jí)，D={易，較易，中等，較難，難}，設(shè)難度-分?jǐn)?shù)分布為：</p><p>　　[18] （2-5）</p><p>　　其中，為第i個(gè)難度級(jí)別的分?jǐn)?shù)，為難度級(jí)別數(shù)。對(duì)于一套試卷，為試卷的總題數(shù)，為試卷

75、中的第i道試題。難度-分?jǐn)?shù)分布為：</p><p>　　[18] （2-6）</p><p>　　其中， </p><p>　　[18] （2-7）</p><p>　　其中，為

76、試題的分?jǐn)?shù)，為試題的難度級(jí)別數(shù)。</p><p>　　難度-分?jǐn)?shù)分布曲線LD反映試卷的難易程度。不同難度等級(jí)的試題在試卷中應(yīng)占有一定得比例。在試卷的期望難度值給定后，計(jì)算出不同難度等級(jí)試題的分?jǐn)?shù)。期望第j種難度等級(jí)的試題分?jǐn)?shù)為，則：</p><p><b>　　（2-8）</b></p><p>　　曲線LD在很大程度上決定了考試成績(jī)的分布，是

77、很重要的一條曲線，高等數(shù)學(xué)試題庫(kù)MATBAS中，將它稱為中心曲線，系統(tǒng)的默認(rèn)曲線不一定滿足用戶要求，但是要用戶用難度分布曲線LD表示對(duì)試卷的難度要求又比較困難，為此本文在4.5.7節(jié)建立了一個(gè)數(shù)學(xué)模型，在組卷時(shí)只要求用戶輸入期望的平均分S，由系統(tǒng)計(jì)算得到難度分布曲線LD。</p><p>　　2.5.2 知識(shí)點(diǎn)-分?jǐn)?shù)分布</p><p>　　知識(shí)點(diǎn)標(biāo)識(shí)該試題在這個(gè)學(xué)科的教學(xué)大綱中所述的知識(shí)

78、。在一份試卷中，出現(xiàn)的題目數(shù)可能會(huì)少于考試科目的所有章節(jié)數(shù)。以K代表知識(shí)點(diǎn)，設(shè)知識(shí)點(diǎn)-分?jǐn)?shù)分布為：</p><p>　　[18] （2-9）</p><p>　　對(duì)于一套試卷，計(jì)算知識(shí)點(diǎn)-分?jǐn)?shù)分布為：</p><p>　　[18]

79、 （2-10）</p><p>　　其中， </p><p>　　[18] （2-11）</p><p>　　知識(shí)點(diǎn)-分?jǐn)?shù)分布曲線LK反映試卷的內(nèi)容效度，是用來描述試卷中知識(shí)點(diǎn)的分布情況。學(xué)科的知識(shí)點(diǎn)代表考試內(nèi)容。一般一個(gè)知識(shí)點(diǎn)就是一個(gè)考察點(diǎn)，試卷應(yīng)合理涵蓋所有考查

80、內(nèi)容。同一知識(shí)點(diǎn)的題內(nèi)容相近，組卷系統(tǒng)應(yīng)保證任何情況下不出重題，除非當(dāng)知識(shí)點(diǎn)數(shù)目少于需要的試題數(shù)目。期望第i種知識(shí)點(diǎn)的總分為，則：</p><p><b>　?。?-12）</b></p><p>　　2.5.3 題型-分?jǐn)?shù)分布</p><p>　　根據(jù)考試科目不同，一套試卷的試題類型也不盡相同，試題類型一般有選擇、填空、判斷、改錯(cuò)、計(jì)算、編程

81、、解答、證明、分析等等。用TP標(biāo)識(shí)試題類型，設(shè)題型-分?jǐn)?shù)分布為：</p><p>　　[18] （2-13）</p><p>　　對(duì)于一套試卷，計(jì)算題型-分?jǐn)?shù)分布為：</p><p>　　[18] （2-14） &l

82、t;/p><p>　　其中， </p><p>　　[18] （2-15）</p><p>　　題型-分?jǐn)?shù)分布曲線LTP對(duì)一種考試而言經(jīng)常保持相對(duì)穩(wěn)定。描述考試所用的題型及每個(gè)題型的題目數(shù)和分?jǐn)?shù)。期望第k種題型的總分為，則：</p><p><b>　?。?-1

83、6）</b></p><p>　　2.5.4 認(rèn)知層次-分?jǐn)?shù)分布</p><p>　　按布盧姆等人對(duì)認(rèn)知領(lǐng)域的教育目標(biāo)的劃分，一般把認(rèn)知層次分為六個(gè)部分。A={識(shí)記，領(lǐng)會(huì)，運(yùn)用，分析，綜合，評(píng)價(jià)}，設(shè)認(rèn)知層次-分?jǐn)?shù)分布為：</p><p>　　[18] （2-17）</p>

84、;<p>　　對(duì)于一套試卷，計(jì)算認(rèn)知層次-分?jǐn)?shù)分布為：</p><p>　　[18] （2-18）</p><p>　　其中， </p><p>　　[18] （2-19）</p><

85、p>　　認(rèn)知層次-分?jǐn)?shù)分布曲線LA反映考試目的，是指測(cè)試考生不同能力的試題在試卷中應(yīng)占不同的比例。期望第i種認(rèn)知層次的總分為，則：</p><p><b>　?。?-20）</b></p><p><b>　　2.5.5 總時(shí)間</b></p><p>　　設(shè)考試的總時(shí)間為,完成試卷所需的預(yù)估時(shí)間為，預(yù)留檢查的時(shí)間為

86、，則完成試卷所需的實(shí)際時(shí)間</p><p>　　[18] （2-21）</p><p><b>　　2.5.6 總分?jǐn)?shù)</b></p><p>　　設(shè)試卷期望總分?jǐn)?shù)為，實(shí)際組成試卷的總分?jǐn)?shù)為，則：</p><p>　　[18]

87、 （2-22）</p><p><b>　　偏差的計(jì)算</b></p><p>　　(1) 難度-分?jǐn)?shù)分布偏差的計(jì)算</p><p>　　[18] （2-23）</p><p>　　(2) 知識(shí)點(diǎn)-分?jǐn)?shù)分布偏差

88、的計(jì)算</p><p>　　[18] （2-24）</p><p>　　(3) 題型-分?jǐn)?shù)分布偏差的計(jì)算</p><p>　　[18] （2-25）</p><p>　　(4) 認(rèn)知層次-分?jǐn)?shù)分布偏差的計(jì)算&

89、lt;/p><p>　　[18] （2-26）</p><p>　　(5) 總時(shí)間偏差的計(jì)算</p><p>　　[18] （2-27）</p><p><b>　　(6) 總分?jǐn)?shù)偏差</b></p>

90、<p>　　[18] （2-28）</p><p><b>　　解得偏好關(guān)系定義</b></p><p>　　令分別表示上述6個(gè)指標(biāo)的偏差，即</p><p>　　[18] （2-29）</p>

91、<p>　　設(shè)有兩個(gè)解，，則由它們的偏差可以定義它們的偏好關(guān)系：</p><p><b>　　若對(duì)任意 </b></p><p>　　[18] （2-30） </p><p>　　都成立，則稱比好。其意義是的組卷

92、模式擬合得比更好。</p><p><b>　　若對(duì)任意</b></p><p>　　[18] （2-31）</p><p>　　都成立，則稱和無(wú)差異。其意義是的組卷模式擬合效果和相同。</p><p><b>　　目標(biāo)函數(shù)

93、</b></p><p>　　組卷的目標(biāo)就是從一個(gè)試題庫(kù)中，尋找一個(gè)子集，使得這個(gè)子集滿足2.5節(jié)中所描述成卷模式中的各個(gè)約束分布。其中，是試題庫(kù)的總體量，為一套試卷中的總體量。</p><p>　　因此目標(biāo)函數(shù)就是要使實(shí)際得到的組卷中的各目標(biāo)分布與理論要求分布的偏差最小。這里采用對(duì)各分布的所有偏差加權(quán)求和，取該和的最小的方法來定義組卷問題的目標(biāo)函數(shù)。令：</p>

94、<p><b>　　（2-32） </b></p><p>　　其中，為各指標(biāo)的權(quán)重，且</p><p><b>　?。?-33）</b></p><p><b>　　所以目標(biāo)函數(shù)為：</b></p><p><b>　?。?-34）</b>&

95、lt;/p><p>　　至此，由式（2-34）的目標(biāo)函數(shù)和2.5節(jié)討論的成卷模式就已經(jīng)建立了實(shí)現(xiàn)成卷模塊的數(shù)學(xué)模型。</p><p><b>　　第三章 遺傳算法</b></p><p><b>　　遺傳算法的概述</b></p><p>　　遺傳算法(Genetic Algorithm, GA) [1

96、9]是一種模擬生物界自然選擇和遺傳變異的機(jī)制來求解復(fù)雜問題的隨機(jī)搜索和優(yōu)化方法。它模擬自然界生物體的進(jìn)化過程，采用“優(yōu)勝劣汰，適者生存”的自然法則選擇個(gè)體，通過交配、變異來產(chǎn)生下一代種群，逐代演化直到滿足條件為止。在演化計(jì)算中，我們不必非常明確地描述問題的全部特征，只根據(jù)自然法則來產(chǎn)生新的更好解，它采用簡(jiǎn)單的編碼技術(shù)來表示各種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，通過對(duì)相應(yīng)的編碼進(jìn)行簡(jiǎn)單的遺傳操作和自然選擇機(jī)制來確定搜索的方向。其主要特點(diǎn)是群體搜索策略和群體

97、中個(gè)體之間的信息交換，搜索不依賴于梯度信息。</p><p>　　遺傳算法的提出，可以追溯到1967年，兩位先驅(qū)者Bagley和Rosengerg在他們的博士論文中就提出了遺傳算法的概念，特別是在1975年John H.Holland對(duì)遺傳算法的理論和機(jī)理做出了出色的工作，發(fā)表了第一本比較系統(tǒng)論述遺傳算法的專著《自然系統(tǒng)與人工系統(tǒng)中的適應(yīng)性》(《Adaptation In Natural And Artifici

98、al Systems》)，奠定了遺傳算法的理論研究工作。遺傳算法最初被研究的出發(fā)點(diǎn)不是為專門解決最優(yōu)化問題而設(shè)計(jì)的，它與進(jìn)化策略、進(jìn)化規(guī)劃共同構(gòu)成了進(jìn)化算法的主要框架，都是為當(dāng)時(shí)人工智能的發(fā)展服務(wù)的。迄今為止，遺傳算法是進(jìn)化算法中最廣為人知的算法。</p><p><b>　　遺傳算法的特點(diǎn)</b></p><p>　　同常規(guī)優(yōu)化算法相比，遺傳算法具有以下特點(diǎn)[20，

99、21]：</p><p>　　(1) 是對(duì)參數(shù)的編碼進(jìn)行操作，而不是對(duì)參數(shù)本身。因此提供的參數(shù)信息量大，優(yōu)化效果好。</p><p>　　(2) 是從問題的解集開始搜索，而不是從單個(gè)解開始，因此覆蓋面大，適用于全局擇優(yōu)，可有效地防止搜索過程收斂于局部最優(yōu)解。</p><p>　　(3) 通過目標(biāo)函數(shù)來計(jì)算適應(yīng)值，而不需要其他的推導(dǎo)和附屬信息，從而對(duì)問題的依賴性

100、較小，故幾乎可處理任何問題，容易形成通用算法程序。</p><p>　　(4) 用隨機(jī)方法進(jìn)行最優(yōu)解搜索，選擇體現(xiàn)了向最優(yōu)解迫近，交叉體現(xiàn)了最優(yōu)解的產(chǎn)生，變異體現(xiàn)了全局最優(yōu)解的覆蓋。算法中的選擇、交叉和變異操作都是由概率決定的，即具有隨機(jī)操作算子，而不是確定的精確規(guī)則。</p><p>　　(5) 通過群體和遺傳算子（選擇、交叉、變異）可實(shí)現(xiàn)揚(yáng)棄性的搜索，克服局部陷阱和模式欺騙，實(shí)現(xiàn)在

101、整個(gè)解空間進(jìn)行高校啟發(fā)式搜索，提高全局尋優(yōu)能力，而不是盲目地窮舉或完全隨機(jī)搜索。</p><p>　　(6) 對(duì)于待尋優(yōu)的函數(shù)基本無(wú)限制，它既不要求函數(shù)連續(xù)，也不要求函數(shù)可微，既可以是數(shù)學(xué)解析式所表達(dá)的顯函數(shù)，又可是映射矩陣甚至是神經(jīng)網(wǎng)絡(luò)等隱函數(shù)，因而應(yīng)用范圍廣。</p><p>　　(7) 具有并行計(jì)算的特點(diǎn)，因而可通過大規(guī)模并行計(jì)算來提高計(jì)算速度。</p><p

102、>　　(8) 初始種群就帶有大量與最優(yōu)解相差甚遠(yuǎn)的信息，通過選擇、交叉、變異操作能迅速排除與最優(yōu)解相差極大地串，這是一個(gè)強(qiáng)烈的濾波過程，并且是一個(gè)并行濾波機(jī)制，因而有很強(qiáng)的容錯(cuò)能力。</p><p>　　(9) 更適合大規(guī)模復(fù)雜問題的優(yōu)化，在世紀(jì)領(lǐng)域中存在各種高復(fù)雜的優(yōu)化問題，其目標(biāo)函數(shù)可能表現(xiàn)形式為非連續(xù)或非處處可微、非凸、多峰壑帶噪聲等各種形式，傳統(tǒng)的方法很難解決這些復(fù)雜問題。</p>

103、<p>　　(10) 其可行解是經(jīng)過編碼化的，目標(biāo)函數(shù)解釋為編碼化個(gè)體的適應(yīng)值，因而具有良好的可操作性和簡(jiǎn)單性。</p><p>　　(11) 具有很強(qiáng)的魯棒性，不依賴于問題的具體領(lǐng)域，能使用不同領(lǐng)域的優(yōu)化問題求解，并在大多數(shù)情況下都能得到比較滿意的解。</p><p>　　(12) 易于和別的技術(shù)（如神經(jīng)網(wǎng)路、模糊推理、混沌行為和人工生命等）相結(jié)合，形成性能更優(yōu)的問題求解方法

104、。</p><p><b>　　遺傳算法的運(yùn)用領(lǐng)域</b></p><p>　　遺傳算法在本質(zhì)上是一種不依賴具體問題的直接搜索方法。近幾年來，遺傳算法主要在復(fù)雜優(yōu)化問題求解和工業(yè)工程領(lǐng)域應(yīng)用，取得了一些令人信服的結(jié)果，所以引起了很多人的關(guān)注，而且在發(fā)展過程中，進(jìn)化策略、進(jìn)化規(guī)劃和遺傳算法之間的差異越來越小。在模式識(shí)別、神經(jīng)網(wǎng)絡(luò)、圖像處理、機(jī)器學(xué)習(xí)、工業(yè)優(yōu)化控制、自適應(yīng)

105、控制、生物科學(xué)、社會(huì)科學(xué)等方面都得到廣泛的應(yīng)用。在人工智能研究中，現(xiàn)在人們認(rèn)為“遺傳算法、自適應(yīng)系統(tǒng)、細(xì)胞自動(dòng)機(jī)、混沌理論與人工智能一樣，都是對(duì)今后十年的計(jì)算機(jī)技術(shù)有重大影響的關(guān)鍵技術(shù)”。</p><p>　　遺傳算法中的基本概念</p><p>　　遺傳算法（Genetic Algorithm，簡(jiǎn)稱GA）[20，21]是由進(jìn)化論和遺傳學(xué)理論相結(jié)合而產(chǎn)生的直接搜索優(yōu)化算法[14]，因此，在

106、這種算法中會(huì)用到各種進(jìn)化和遺傳學(xué)的概念。下面來介紹幾個(gè)相關(guān)的概念。</p><p>　　(1) 個(gè)體（Individual）：GA的處理對(duì)象、結(jié)構(gòu)。</p><p>　　(2) 群體（Population）：個(gè)體的集合稱為群體。</p><p>　　(3) 位串（String）：對(duì)應(yīng)于遺傳學(xué)中的染色體，它是個(gè)體的表現(xiàn)形式。</p><p>　

107、　(4) 基因（Gene）：基因是串中的元素，基因用于表示個(gè)體的特征，對(duì)應(yīng)于生物學(xué)中的遺傳物質(zhì)單位，以DNA序列形式把遺傳信息譯成編碼。</p><p>　　(5) 群體大?。≒opulation Size）：在群體中的個(gè)體數(shù)量稱為群體大小。</p><p>　　(6) 基因位（Gene Position）：一個(gè)基因在染色體中的位置?；蛭辉谌旧w中從左向右計(jì)算。</p>&

108、lt;p>　　(7) 基因型（Genetype）：指用基因組定義遺傳特征和表現(xiàn)。對(duì)應(yīng)于GA中的位串。</p><p>　　(8) 表現(xiàn)型（Phenotype）：生物體的基因型在特定的環(huán)境下的表現(xiàn)特性。對(duì)應(yīng)于GA中的位串解碼后的參數(shù)。</p><p>　　(9) 參數(shù)空間（Parameter Space）：是位串空間在物理系統(tǒng)中的映射，對(duì)應(yīng)于遺傳學(xué)中的表現(xiàn)型的集合。</p>

109、<p>　　(10) 適應(yīng)度（Fitness）：表示某一個(gè)個(gè)體對(duì)于環(huán)境的適應(yīng)程度，或者在環(huán)境壓力下的生存能力，取決于遺傳特性，它通常表現(xiàn)為數(shù)值形式。</p><p>　　(11) 適應(yīng)度函數(shù)（Fitness Function）：通常是用戶所提供的目標(biāo)函數(shù)的一個(gè)合理的數(shù)學(xué)變換，目標(biāo)函數(shù)用能反映個(gè)體在種群中優(yōu)劣程度的數(shù)學(xué)表達(dá)式來?yè)?dān)任，適應(yīng)度函數(shù)是評(píng)價(jià)個(gè)體好壞的唯一標(biāo)準(zhǔn)，在遺傳算法中試一個(gè)非常重要的概念。

110、</p><p>　　(12) 選擇（Selection）：根據(jù)染色體對(duì)應(yīng)的適應(yīng)度值和問題的要求，篩選種群中的染色體，其目的是為了從當(dāng)前群體中選出優(yōu)良的個(gè)體，使它們有機(jī)會(huì)作為父代產(chǎn)生后代個(gè)體。</p><p>　　(13) 交叉（Crossover）：在一定條件下兩條染色體上的一個(gè)或幾個(gè)基因相互交換位置。</p><p>　　(14) 變異（Mutation）：在一

111、定條件下隨機(jī)改變一條染色體上的一個(gè)或幾個(gè)基因值。</p><p>　　(15) 后代（Next Generation）：染色體經(jīng)過交叉或變異后形成的新的個(gè)體。</p><p>　　綜上所述，從形式化上，基本遺傳算法可以定義為一個(gè)8元組[20]：</p><p>　　其中，表示個(gè)體編碼方法，表示個(gè)體適應(yīng)度評(píng)價(jià)函數(shù)，表示初始群體，表示群體大小，表示選擇算子，表示雜交算子

112、，表示變異算子，表示遺傳運(yùn)算的終止條件。</p><p>　　遺傳算法中的基本操作</p><p>　　一般的遺傳算法都包含三個(gè)基本操作：選擇（Selection）、交叉（Crossover）和變異（Mutation）。</p><p><b>　　3.5.1 選擇</b></p><p>　　選擇用來實(shí)施適者生存的原則

113、，即從上一代種群中選擇生命力強(qiáng)的個(gè)體產(chǎn)生新種群的過程。直觀地講，可以把適應(yīng)度函數(shù)作為度量來評(píng)價(jià)當(dāng)前種群個(gè)體的適應(yīng)度，顯示為不同個(gè)體適應(yīng)度值的不盡相同。其中適應(yīng)度值較高的個(gè)體更有可能在下一代中產(chǎn)生一個(gè)或多個(gè)子孫。顯然，這個(gè)操作是模仿自然選擇現(xiàn)象，將達(dá)爾文的適者生存理論運(yùn)用于個(gè)體的選擇。</p><p>　　作為一種算子，其作用效果是提高群體的平均適應(yīng)度值。選擇操作在遺傳算法中有多種實(shí)現(xiàn)方法，其中最簡(jiǎn)單的一種方法就是