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