【文章內(nèi)容簡介】 統(tǒng)的組卷方式就很難跟上時(shí)代的步伐，隨著計(jì)算機(jī)科學(xué)的迅速發(fā)展和廣泛應(yīng)用，計(jì)算機(jī)輔助教學(xué) CAI（ Computer Aided Instruction）的產(chǎn)生與發(fā)展對促進(jìn)教育、教學(xué)技術(shù)的變革與發(fā)展具有巨 大的推動(dòng)作用。利用計(jì)算機(jī)建立試題庫，實(shí)現(xiàn)計(jì)算機(jī)自動(dòng)選題組卷，是 CAI 工程的重要組成部分，是實(shí)現(xiàn)考試規(guī)范化、科學(xué)化的重要措施，更是實(shí)現(xiàn)教考分離的一個(gè)重要手段。 自動(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é)方法，因此對教學(xué)質(zhì)量和整體教學(xué)水平的提高有著重要意義。還可利用智能組卷系統(tǒng)對試卷和考試分?jǐn)?shù)進(jìn)行分析和評價(jià)，使考試這一教學(xué)環(huán)節(jié)更加科學(xué)化。為了 提高考試的科學(xué)化程度，把數(shù)理統(tǒng)計(jì)的方法引入考試工作，對試卷的編制和考試的質(zhì)量進(jìn)行定量分析。建立試題庫，實(shí)現(xiàn)智能組卷得以實(shí)施科學(xué)化的考試，有助于是對教學(xué)工作加強(qiáng)宏觀指導(dǎo)和管理，將課程教學(xué)的科學(xué)管理變成現(xiàn)實(shí)。 設(shè)計(jì)實(shí)現(xiàn)自動(dòng)組卷系統(tǒng)，是一項(xiàng)自然科學(xué)與教育科學(xué)，學(xué)術(shù)研究與教學(xué)研究相結(jié)合的研制課題，它運(yùn)用教育測量學(xué)、考試學(xué)、教育統(tǒng)計(jì)學(xué)的理論和方法，總結(jié)教師的考試經(jīng)驗(yàn)，建立科學(xué)的組卷理論，從而借助于計(jì)算機(jī)的先進(jìn)技術(shù)來實(shí)現(xiàn)。 2 課題研究現(xiàn)狀 在國外，一些標(biāo)準(zhǔn)化考試系統(tǒng)，如美國的 TOEFL、 GRE 等考試系統(tǒng)早已建立并成功運(yùn)行 了幾十年，一直都能科學(xué)地測試出學(xué)生的實(shí)際水平。這說明自動(dòng)組卷式可能的而且有效地，但這些系統(tǒng)所涉及到的具體內(nèi)容以及其設(shè)計(jì)思想與原理幾乎都是保密的。因此我們必需依靠自己的努力研制一套符合中國國情的試題庫組卷系統(tǒng)。 在國內(nèi)，已研制成功的計(jì)算機(jī)考試系統(tǒng)有高等數(shù)學(xué)試題庫系統(tǒng) MATBAS[1],南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系研制的 PASCAL 題庫系統(tǒng)，高教司的重點(diǎn)項(xiàng)目基于知識的成卷系統(tǒng)使用外殼軟件 [2]等系統(tǒng)，但是這些系統(tǒng)大多數(shù)沒有自動(dòng)組卷功能，考試所需的試題仍需要人工定制，因此在近十幾年又出現(xiàn)了大量針對各種考試的計(jì)算機(jī)考 試系統(tǒng)。計(jì)算機(jī)考試系統(tǒng)的發(fā)展同時(shí)推動(dòng)了組卷系統(tǒng)的研究。 組卷問題是一個(gè)帶約束的多目標(biāo)優(yōu)化問題，采用經(jīng)典的數(shù)學(xué)方法很難解決這個(gè)難題，自動(dòng)組卷的效率和質(zhì)量完全取決于抽題算法的設(shè)計(jì)。如何設(shè)計(jì)一個(gè)算法從試題庫既快又好地抽出一組最符合考試要求的試題，涉及到一個(gè)全局尋優(yōu)和收斂速度慢的問題。目前的自動(dòng)組卷系統(tǒng)根據(jù)其所使用的組卷策略大致分為五類： (1) 基于隨機(jī)抽取的自動(dòng)組卷算法 [3] (2) 基于深度與廣度搜索算法的自動(dòng)組卷 (3) 基于項(xiàng)目反映理論的自適應(yīng)測試 (4) 基于數(shù)據(jù)挖掘和知識發(fā)現(xiàn)的自動(dòng)組卷理論 (5) 基于遺傳算法的自動(dòng)組卷 基于隨機(jī)抽取的自動(dòng)組卷算法 由于用戶在操作該系統(tǒng)生成試卷時(shí)會(huì)提出一系列的約束條件，如試卷專業(yè)類別、題目類型、難度分布、知識點(diǎn)分布、試題分值等等。而在理論與實(shí)際應(yīng)用中都無法將這些約束條件用一種單一的表達(dá)式進(jìn)行綜合處理，因此也不存在最優(yōu)化的思想。隨機(jī)抽取的策略，通常是從試題庫中隨機(jī)抽取某個(gè)試題與用戶提出的約束條件進(jìn)行比較，取出滿足某項(xiàng)約束指標(biāo)的加入試卷，若所有試題都試探過多不能滿足當(dāng)前試卷約束條件，則組卷過程失敗。 3 基于深度與廣度搜索算法的自動(dòng)組卷算法 該類型的自動(dòng)組卷算法又被稱為回溯試探法。它 在組卷過程中采用隨機(jī)的方法抽取試題，而在抽取過程中通過驗(yàn)證所選擇的試題是否滿足給定的約束條件來決定是否抽取，當(dāng)發(fā)現(xiàn)目前沒有任何試題滿足要求而組卷過程又沒有完成時(shí)，則采用回溯試探方法，通過廢棄前一段時(shí)間所做的組卷來重新組卷。由于這種方法在組卷過程中通過廢棄部分工作而不是廢棄本次組卷過程中的全部操作，從而有效地降低了無效組卷的次數(shù)，使得自動(dòng)組卷算法性能得到提高，同時(shí)算法實(shí)現(xiàn)也容易。 熊文清等于 1999 年通過對試題按某個(gè)性能指標(biāo)進(jìn)行排序，當(dāng)發(fā)生組卷失敗情況時(shí)，將發(fā)生組卷失敗的試題與前面的試題進(jìn)行呼喚，以調(diào)整原有的 組卷次序，重新進(jìn)行組卷過程 [4]；葉勇等于 1998 年分析了三種基于回溯算法的組卷匹配方法，并進(jìn)行了相應(yīng)的比較，在其基礎(chǔ)上給出了智能試題庫管理系統(tǒng)的設(shè)計(jì)思想 [5]。 基于項(xiàng)目放映理論的自動(dòng)組卷算法 項(xiàng)目反映理論（ Item Response Theory, IRT）是一系列心理統(tǒng)計(jì)學(xué)模型的總稱，是針對經(jīng)典測量理論（ Classical Test Theory, CTT）的局限性提出來的?；?IRT 的自動(dòng)組卷算法是由最早的適應(yīng)性測試發(fā)展而來的。 William W. Turn Bull 于 1951 年最早提出 了適應(yīng)性測試這一概念，當(dāng)時(shí)，適應(yīng)性測試是指針對被試先前經(jīng)驗(yàn)或者說被試先前測試的歷史信息選取適合被試的題目進(jìn)行組卷測試，作答后立即評分，并以上一題的作答情況決定下一道被使用的測試試題，直至測試結(jié)束為止。測試的整個(gè)過程即是從題庫中選取符合被試能力水平的題目進(jìn)行測試的過程。 在考試開始時(shí)，系統(tǒng)被測者的潛在特質(zhì)一般一無所知，所以通常的方法是選取中等難度的試題，即假定所有考生的能力值為中等，在題庫中隨機(jī)抽取難度為中等的題目，作為測試的開始點(diǎn)。隨后，每當(dāng)考生回答一道題后，系統(tǒng)將對學(xué)生的能力值重新評估并修正原先的能力值， 然后從試題庫中選取下一道試題，該過程直到對考生能力的測量精度達(dá)到指定的水平。 Win Linden等在 2020 年試圖利用學(xué)生的實(shí)際參與考試的情況對試題庫中的各個(gè)單元實(shí)體的性能指標(biāo)進(jìn)行評估，以便得到較為真實(shí)反映單元試題難度、時(shí)間等性能指標(biāo)的標(biāo)準(zhǔn)值，提出了利用基于項(xiàng)目發(fā)音理論的方法，通過建立一個(gè)反映考生做大反應(yīng) 4 與題目質(zhì)量及水平間的線性模型，對考生的能力水平進(jìn)行估算，從而得出該考生能力的測量 [6， 7]。 基于數(shù)據(jù)挖掘和知識發(fā)現(xiàn)的自動(dòng)組卷算法 數(shù)據(jù)挖掘和知識發(fā)現(xiàn)作為一門新的研究領(lǐng)域，涉 及到機(jī)器學(xué)習(xí)、模式識別、統(tǒng)計(jì)學(xué)、數(shù)據(jù)庫和人工智能等學(xué)科。特別是它被看作是數(shù)據(jù)庫理論和機(jī)器學(xué)習(xí)的交叉學(xué)科 [8]。作為一種獨(dú)立于應(yīng)用的技術(shù)，受到了廣泛的關(guān)注，有著廣泛的前景，可以應(yīng)用于商業(yè)管理、科學(xué)研究、智能決策、故障診斷等方面，當(dāng)然也被應(yīng)用于組卷系統(tǒng)中。目前國內(nèi)數(shù)據(jù)挖掘的研究重點(diǎn)是找出頻繁項(xiàng)目集 (frequent itemsets)。典型的關(guān)聯(lián)規(guī)則挖掘算法有 等人提出的 Apriori 算法 DHP 算法等。它們都屬于數(shù)據(jù)庫遍歷類算法。 提出的 AprioriHybrid 算法， Park[9]等人提出的 DHP 算法 (Direct Hashing and Pruning)使用哈希 (Hashing) 技術(shù)有效地改進(jìn)了候選集 Ck 的產(chǎn)生過程。 SavaSers 等人在 1995 年提出了一種把數(shù)據(jù)庫分割處理的算法，降低采掘過程中的 I/O 次數(shù)，減輕了 CPU 的負(fù)擔(dān)。 使用抽樣 (sampling)的方法可以用較小的代價(jià)從大型數(shù)據(jù)庫中找出關(guān)聯(lián)規(guī)則 [10]。 基于遺傳算法的自動(dòng)組卷算法 遺傳算法（ Geic Algorithm, GA）是模擬達(dá)爾文的遺傳選擇和自然淘汰的生 物進(jìn)化過程的計(jì)算模型 [11]，它的產(chǎn)生歸功于美國的 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)。從某種程度上說遺傳算法是對生物進(jìn)化過程進(jìn)行的數(shù)學(xué)方式仿真。遺傳算法作為一種新的全局優(yōu)化搜索算法，以其簡單通用、適用于并行處理以及應(yīng)用范圍廣等顯著特點(diǎn)，奠定了它作為 21 世紀(jì)關(guān)鍵智能計(jì)算方法之 一的地位。 遺傳算法是具有“生成 +檢測”迭代過程的搜索算法，其基本出流程如圖 所示。 5 圖 遺傳算法基本流程圖 遺傳算法是一種群體型操作，該操作以群體中的所有個(gè)體為對象，選擇（ Selection）、交叉（ Crossover）和變異（ Mutation）是遺傳算法的三個(gè)主要操作算子（ Geic Operation），它們構(gòu)成了所謂的遺傳操作，使遺傳算法具有了其他方法所沒有的特性。 基于遺傳算法的自動(dòng)組卷將每道試 題作為一個(gè)獨(dú)立的編碼位，利用遺傳算法的三個(gè)基本操作：遺傳、交叉與變異并最終完成試題的選取，從而得到滿足各種條件的試題集合，完成組卷工作。 在目前的計(jì)算機(jī)自動(dòng)組卷算法研究中，許多研究者利用遺傳算法在計(jì)算機(jī)自動(dòng)組卷方法的應(yīng)用展開了大量的研究。魏平、毛秉毅等 [12， 13]采用傳統(tǒng)的遺傳算法 (SGA)來實(shí)現(xiàn)試題庫的自動(dòng)組卷，取得了較好的效果。但傳統(tǒng)遺傳算法容易產(chǎn)生“早熟收斂”現(xiàn)象。目前已經(jīng)有很多研究人員把改進(jìn)的遺傳算法應(yīng)用到組卷中，以提高組卷運(yùn)行效率。劉彬等 [14]對題型確定過程中的知識進(jìn)行改進(jìn)，相對于簡單遺傳算取 得了較好的結(jié)果。 N Y 開 始 編碼，生成初試群體 滿足停止 準(zhǔn)則？ 選 擇 交 叉 變 異 結(jié) 束 6 課題研究目的及成果 本課題的研究目的：對組卷算法進(jìn)行深入研究，在高校題庫管理系統(tǒng)的基礎(chǔ)上，將遺傳算法實(shí)現(xiàn)并運(yùn)用到智能組卷系統(tǒng)中，實(shí)現(xiàn)自動(dòng)組卷系統(tǒng)的基本功能。 本課題的 成果 ： (1) 在傳統(tǒng)遺傳算法的基礎(chǔ)上對編碼方式、適應(yīng)度函數(shù)、遺傳算子進(jìn)行了一些研究和改進(jìn)； (2) 根據(jù)遺傳算法自動(dòng)組卷的需要設(shè)計(jì)了相應(yīng)的試題庫結(jié)構(gòu)； (3) 建立了一個(gè)以難度系數(shù)、知識點(diǎn)、題型等為核心屬性的智能組卷數(shù)學(xué)模型； (4) 設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)基于改進(jìn)遺傳算法實(shí)現(xiàn)自動(dòng)組卷的方法。 論文內(nèi)容概述 論文主要分為 6 個(gè)章節(jié)： 第 1 章緒論，主要是本課題研究背景、研究現(xiàn)狀的介紹，對幾種組卷算法作了介紹 ，然后給出了畢業(yè)課題的研究目的和成果。第 2 章 介紹了自動(dòng)組卷系統(tǒng)的組卷基本原則，分析了試題的屬性指標(biāo)、試卷的評價(jià)指標(biāo)、各項(xiàng)指標(biāo)的作用及幾個(gè)重要指標(biāo)間的關(guān)系 。第 3 章 介紹了遺傳算法的基本概念和基礎(chǔ)知識、遺傳算法的設(shè)計(jì)與實(shí)現(xiàn)等 。第 4 章 基于遺傳算法建立了自動(dòng)組卷的數(shù)學(xué)模型，并將遺傳算法具體應(yīng)用于試題抽取 。第 5 章 基于遺傳算法自動(dòng)組卷系統(tǒng)的研究對試卷生成系統(tǒng)進(jìn)行了分析設(shè)計(jì)，并基于 Java 技術(shù)實(shí)現(xiàn)了算法原型 。 第 6 章對文章進(jìn)行了總結(jié)，提出了自動(dòng)組卷過程中 還存在的其他問題，并對論文下一步的工作進(jìn)行了展望。浙江工業(yè)大學(xué)本科畢業(yè)設(shè)計(jì)說明書 (論文 ) 7 第二章 組卷的評價(jià)體系與建模 組卷的基本原則 對于一般的測試來說，一方面主要是用于學(xué)生自測，檢驗(yàn)自己對學(xué)科知識的掌握程度；另一方面用于教師對學(xué)生進(jìn)行考試，考察教學(xué)效果，進(jìn)而改進(jìn)教學(xué)方法。這兩個(gè)方面的用處均在于考察學(xué)生知道什么、能做什么，因此屬于目標(biāo)參照性測驗(yàn)。對于大規(guī)模的人才選拔，考慮到公平性和保密性，一般不會(huì)采用自動(dòng)組卷系統(tǒng)；而對于小規(guī)模的人才考核，一般也不會(huì)采用這種復(fù)雜的考察方式，而是采用最新的項(xiàng)目反應(yīng)理論進(jìn)行測試。因此本文研究的自動(dòng)組卷系統(tǒng)主要 側(cè)重于目標(biāo)參照性測驗(yàn)。 對于目標(biāo)參照性測驗(yàn)，組卷的基本原則 [15]主要體現(xiàn)在： (1) 組卷的主要依據(jù)是考試大綱，組卷必須全面反映大綱的廣度和深度； (2) 組卷要利于考核考生能力和促進(jìn)考生智力發(fā)展； (3) 組卷要講究層次，要有難度臺階，才能在分?jǐn)?shù)上拉開距離； (4) 命題要注重發(fā)揮考題對考生學(xué)習(xí)方法的引導(dǎo)； (5) 考試不能出現(xiàn)偏題、怪題，但要有一定得深度，要能測量出考生的不同知識水平和智能差異； (6) 命題的表達(dá)語或指導(dǎo)語要清楚無誤，以提高考試的信度。 組卷工作是一項(xiàng)復(fù)雜的智力勞動(dòng)，組卷者首先要研究考試大綱和命題計(jì)劃，明確考試的目的、對象、性質(zhì)， 試題的形式、數(shù)目，試題數(shù)量和分?jǐn)?shù)在各部分中的分配比例，考查的重點(diǎn)和其它要求。其次，根據(jù)命題計(jì)劃編制試題，給出答案，并對編出的試題進(jìn)行審查、修改和篩選，同時(shí)注明各試題的預(yù)計(jì)難度、所屬知識點(diǎn)和認(rèn)知層次，分?jǐn)?shù)及預(yù)計(jì)答題時(shí)間。 試題的幾個(gè)重要屬性指標(biāo) 試題都是存放在試題庫中，而試題本身含有固有的屬性，試題各項(xiàng)屬性指標(biāo)的浙江工業(yè)大學(xué)本科畢業(yè)設(shè)計(jì)說明書 (論文 ) 8 確定直接影響到組卷系統(tǒng)的準(zhǔn)確性和工作效率。試題庫中的內(nèi)容將直接用于試卷之中，所以試題庫結(jié)構(gòu)的設(shè)計(jì)師組卷問題的重要內(nèi)容。試題的屬性指標(biāo)定量地描述了每一道試題的內(nèi)在屬性、外部特征以及它在考試測驗(yàn)中的功能， 是計(jì)算機(jī)進(jìn)行抽題組卷的基礎(chǔ)。試題的難度、區(qū)分度都是試題的重要質(zhì)量指標(biāo)，然而考慮到區(qū)分度需由試題被使用后統(tǒng)計(jì)計(jì)算所得，一般難以在試題入庫之時(shí)確定，而試題難度可在試題入庫時(shí)由輸題教師預(yù)測下故本文未采用，本文定義的試題指標(biāo)體系為 B={題型，知識點(diǎn)，難度，認(rèn)知層次，答題時(shí)間，曝光度 }，以下對試題指標(biāo)體系的構(gòu)成進(jìn)行詳細(xì)的闡述。 題型 試題的類型有多種形式，一般是指從試題形式上區(qū)分，具體的試題類型可分為：選擇題（包括單選、多選和不定項(xiàng)選擇）、填空題、判斷題、計(jì)算題、編程題、解答題等。 知識點(diǎn) 知 識點(diǎn)一般是以課程的章節(jié)進(jìn)行劃分的，考慮到同一科目可能前后會(huì)使用不同的教科書，所以本文采用對應(yīng)課程的單個(gè)知識要點(diǎn)作為試題指標(biāo)體系的知識點(diǎn)。知識點(diǎn)是考察能力的載體，因此以知識點(diǎn)的分值分布來組織試題是合理的。 難度 在組卷過程中，針對不同的考試目的、不同階段的考試，考試的命題難度應(yīng)該相應(yīng)地不同，這對試題來說是非常重要的一個(gè)屬性。本文設(shè)計(jì)的試題難度分為五個(gè)等