基于混合算法的校園網絡測評系統開發與研究

郭耀輝

（江蘇聯合職業技術學院徐州經貿分院 江蘇省徐州市 221004）

1 測評系統的基本功能與基本約束

1.1 校園網絡測評系統的基本功能

網絡測評系統要能夠實現在線考試、在線閱卷以及試卷分析匯總、分數轉換等基本功能。

（1）考試前的準備功能：允許實現考生基本信息的輸入，作為后期在線測試的登錄驗證標準。建立試題庫，支持通過EXCEL文件導入以及手工輸入等輸入方式，建立題庫。允許在考試前生成試卷，進行檢測判斷試卷是否符合在線測試標準的操作，也支持實時生成試卷的方式。創建考試科目、時間、在線考試時間等準備信息。

（2）網絡在線測評功能：發生在實時考試階段，實現考生通過瀏覽器，進行身份驗證登錄測評系統的過程。在線分發試卷，考生在瀏覽器端進行答題，并且提供自主收卷以及到達規定時間自動收卷兩種收卷方式。在即將達到自動收卷時間點前設置提醒功能。

（3）試卷評閱與分析功能：實現自動化閱卷自動核算分數模式，如果加入主觀試題，可采用照片方式，加入人工閱卷的參與。對類型題、小題的得分情況進行統計與分析，有價值的參數融入到難度變化數值中。

1.2 試卷的基本約束

試卷的基本約束根據考試科目何內容的不同，可以進行靈活調整。大體包含有：試卷總分、試卷類型題、試卷題目數量、類型題數量、對應分數等基本的約束條件。

2 混合算法在本測評系統中的作用以及混合算法的優勢

2.1 算法作用體現

針對早期的測評系統，試卷僅能滿足基本約束，試題難度無法控制，試題覆蓋度低，造成考生分數集中，無法進行區分，同時對考生的考查目的難以實現的問題。采用混合算法，目的就是控制試卷難度，讓難度體現在合理或者設計范圍內，能夠讓優秀、中等、偏差的考生通過考試進行區分，發現不足。體現考試目的。同時通過混合算法還要提升試卷生成的速度和成功率。

2.2 遺傳算法的優勢

2.2.1 遺傳算法與傳統算法對比

遺傳算法是測評系統智能體現出現早、應用廣的算法之一。在此之前測評系統的試卷生成策略常常使用隨機算法和回溯算法。隨機算法特點是隨機對試題進行抽取，不斷往復進行，形成符合條件約束的試卷。優點是試卷生成速度快，算法實現簡單。缺點是高概率出現重復試題，如果要求試卷體現智能化特點，試卷生成成功率低，耗費大量時間。而回溯算法可以視為隨機算法的一種改進算法，隨機算法在試卷完全生成后，可能常常出現不滿足條件，組卷失敗從而重新進行的現象。耗費了大量的時間。而回溯算法可以避免這個問題，通過記錄上一狀態的相關參數，更早的發現失敗沖突，從而回溯到上一步驟，重新進行生成。這種方式時間復雜度與空間復雜度耗費大，算法實現相對繁瑣。智能體現不足。

2.2.2 遺傳算法的思想與實現

遺傳算法的基本思想是利用生物學中達爾文優勝略汰的思想模式，通過與計算機的結合，實現染色體確認、種群規模限定、選擇算子、交叉算子、變異算子的下一代繁衍過程。遺傳算法的實現目標不是最優解，而是最接近優勢解的解的集合，是面向全局的算法。

遺傳算法的實現過程：

第一步，二進制編碼實現染色體確認：染色體確認在計算機編碼中不僅僅有二進制編碼方式，也可以巧妙的利用實數形式或者分段方式。但是目前公認的使用二進制編碼模式便于理解，也讓后面的編程過程更加規范，便于實現。其中通常使用的規則為1 為選中模式，0 為未選中模式。舉例說明某8 位染色體位10101001，代表著初始編碼長度為8，可能對應8 道試題，初次選中第一、三、五、八題目，共選中四道題目。選中位置是1 出現的編碼位置。

第二步，確定種群范圍：種群范圍其實是遺傳算法很關鍵的一個步驟，涉及到遺傳算法相應適應度函數以及相關指標，進行數學迭代的次數以及遺傳算法結束的條件。如果單純的使用遺傳算法需要設置控制的范圍，計算迭代的次數，以及未曾滿足次數情況下是否觸發算法繼續進行的條件（多次運行未得到進一步優化的情形）。

第三步，遺傳與變異（選擇、交叉、變異算子）：首先，選擇算子，也就是對下一代的生父母進行選擇，從種群中進行選擇，采用輪盤賭的算法選擇，利用輪盤滾動的思想，不同的滾動對應不同的區域，多次到達的輪盤區域代表適應性更強，更利于繁衍優秀的下一代算子。其次，交叉算子，采用數學的方式進行邏輯計算，產生下一代，最后根據變異率，從產生變異的算子中選擇優秀的，適合優解的繼續進行迭代過程。

2.2.3 遺傳算法的具體優點

從遺傳算法的思想以及實現過程我們可以總結出，遺傳算法是一種全局算法，適合求解優勢的解的集合。魯棒性能強，可以在多方面得到應用。在算法前期執行優化的過程迅速。當然任何算法都有自身的不足，比如遺傳算法是全局算法，那么它針對局部解的能力就弱。由于是針對優勢解集而不是最優解，在算法后期進化求解的過程就過慢，甚至出現無效運算的現象。遺傳算法已經初步的可以根據適應度函數實現試卷難度的控制，體現測評系統的智能性。

2.3 蟻群算法進行混合的合理性分析

為了讓試卷具有難度控制和區分度體現的智能目標，采用遺傳算法，但是遺傳算法的不足，使得試卷生成成功率不足夠高，生成效率也需要進一步優化。而使用蟻群算法可以讓兩種算法的優勢結合。提升試卷生成成功率以及試卷生成速度。

2.3.1 蟻群算法的思想

篇幅限制，這里簡單用文字進行說明。蟻群思想借用的是生物學螞蟻尋找食物選擇優化路徑的過程。螞蟻在尋找食物過程中，總是能在一定時間內找出相對短的可行路徑。通過的是氣味（信息熵）的散發，在初始過程中，隨機進行路徑選擇。并且在走過的路徑上分泌信息熵，如果路徑短，那么信息熵揮發的速度慢，濃度也就相對高。從而吸引更多的螞蟻選擇相應路徑。而更多的螞蟻又分泌出更多的信息熵。這毫無疑問是一種有效的正反饋機制。路途較遠的路徑在濃度對比中信息熵越來越低，從而被放棄。

蟻群算法的優勢：從蟻群算法思想我們可以看出，第一點，也是最為重要的一點，是蟻群算法具有高效的正反饋機制，能夠快速尋找最優解。第二點，魯棒性也很強，適合不同領域，適合算法進行融合。第三點，從蟻群尋找路徑的過程，可以看出該算法屬于分布式算法。具有分布式算法優勢。

當然蟻群算法也有自己的不足，那就是初期的路徑遍歷過程緩慢，具有很強的隨機性。

2.3.2 蟻群算法融合的作用

從遺傳算法和蟻群算法的優缺對比，就可以看出兩種算法融合實現最優解集尋找的可行性。遺傳算法運行在初期收斂快，全局算法，但是在后期因為是針對較優解集，所以迭代過程中可能存在多次進行，但無法繼續優化的問題。浪費算法時間。而且這個迭代發生的具體次數，無法具體提前精確預估。而蟻群算法初期遍歷過程緩慢，但是在前期過程完成后，形成高效的正反饋，利于高效的獲取最優解集。所以通過前期遺傳算法解決初期遍歷問題，然后融入蟻群算法，尋找成功試卷的組卷，是又實際算法應用價值的。

2.4 混合算法融合點的設置與判斷

到此兩種算法的融合的作用和可行性，已經完成介紹，但是在實際應用中的難點，也就是兩種算法運行的具體融合點，才是應用的關鍵。如何定義這個融合點呢？

（1）算法的先后順序已經理清，前期使用遺傳算法，到達融合點后轉入蟻群算法，利用正反饋機制實現高效優化作用。

（2）遺傳算法實現過程無疑問進行編碼，種群確定，選擇、交叉與變異。

（3）如何判斷遺傳算法終止，轉入蟻群算法。采用了兩種方式。第一種根據遺傳算法中數學迭代設置的最大次數。如果達到最大迭代次數，遺傳算法運行完整結束，轉入蟻群算法。這個迭代次數通常是根據試卷對應題庫的數量與相對實驗進行預估的，有一定的合理性，并且保證迭代次數的最大值通常能讓遺傳算法應用得到滿足。但這個迭代次數是不可能精確的，設置中可能通常也會設置數值偏大。第二種方式，就是設置進化率。也就是在不斷的下一代繁衍過程中，子代與父代差異的數值，當多次差異數值小于規定數值后，也就是下一代的繁衍優化非常不明顯，也就意味著可以允許遺傳算法結束，后續過程視為無意義。這就是融合的關鍵點。當然在一些運算中，為了避免局部優解出現，也就是在幾次過程中沒有出現優化，但遺傳算法實際運轉不久，還沒有產生優勢解集的問題，也可以給遺傳算法設置一個最小迭代次數，當最小迭代次數未達到時，進化率不能成為結束的融合點。這樣保證了試卷生成的成功率更高。

3 算法中的指標與公式的使用

3.1 試卷難度公式

實現測評系統試卷智能化的第一個點就是控制試卷難度。試卷難度可以根據具體考試與考查目標進行合理修改。這里設置在0.45-0.55 之間，考試難度適中，試卷價值較高。

從公式中我們可以看出，K 代表的我們所尋找的試卷的難度數值，k 代表不同試題的難度權值，公式中的g 代表著不同試題的分值，公式分子為題目分值與對應題目難度系數乘積的累加和，分母為試題分值的累加和。

3.2 試卷區分度的公式

利用同樣的思路，我們能夠求解出試卷的區分度，是否能夠將得分的高低，成績優秀的和成績差的，成績居中的考生區分出來。當然試題的難度可以設置為5 檔、3 檔甚至根據需要更多的檔。比如五檔就可以設置為（極簡、簡單、普通、難、極難），三檔就更容易理解，這里就不再贅述。

Q 為試卷整體的區分度，其中q 代表對應試題的區分度，g 仍然為對應試題的分數。通過累加數值的比例求出試卷整體的區分度。

3.3 試卷整體難度和試卷整體區分度的公式支持

從整體公式可以看出，試卷整體難度和整體區分度都根據具體每個題目的難度和區分度進行累加和求比。試題難度k 和試題區分度q

都可以采用兩種方式進行公式標注，就是對應的人數和總體人數比值以及對應得分和總體得分比值得出。

試題難度公式：k=1-sd/sa或者 k=1-ave/A

試題區分度公式：q=(sg-sd)/s 或者q=(aveg-aved/A)

試題難度公式的含義分別是，用整體1 減去作對試題的人數除以總人數。所以作對試題的人越多，難度數值越低。反之作對試題的人數越少難度數值越高。用另外一個公式，代表試題的平均得分數除以試題分值，平均分越高，試題難度越小，反之亦然。（sd代表得分人數，sa代表總人數，ave 代表平均得分）。

試題區分度公式的含義是，高分人數減去低分人數，除以高低分組人數和，代表區分度。相差越大區分度越大。高分組平均得分減去低分組平均得分，除以題目對應的滿分數值。

對于客觀化試題，兩種公式都能起到試題區分度、試題難度的測試作用。所以給出兩組公式是作為未來拓展主觀化試卷做準備。

3.4 區分度和難度權值的確定

從上文可以看出，不同試題對應不同的難度權值和區分度權值。這些權值并不是完全用后面的試題公式計算出來的，試題公式是通過多次測試，不斷的提供權值變化的參考。真正的權值應該有一定的采樣和教師做出修正。從系統實際應用角度，初始化的權值是沒有的，因為一次測試也沒有，需要教師的參與。同時一次或者幾次的測試，也不能準確的確定權值。很多因素也影響著對應的權值。這里簡單說明，例如題目的曝光度，也就是題目在試卷中出現的次數，出現次數越多，受到關注越多，掌握的人越多，這種題目就不能準確的反應出難度系數。所以曝光度高的題目權值應該下降。再比如在某次測試中，題目得分率很低，但題目難度并不大，存在題目理解的問題。這些都需要關注，合理修訂試題難度權值和區分度權值。