基于遺傳算法和蟻群算法融合的在線測評系統

文/姚楠

在線測評系統在我國一些領域已經得到了一定的應用，尤其是在高校當中，很多高校已經采用在線測評系統來進行多種科目的成績考核與評估。但是在應用過程中仍然存在著一些問題，那就是試卷的試題是從試題庫進行抽取的，很多測評都是通過隨機算法實現，這樣雖然能夠快速的實現試卷的生成，但是無法控制試卷的難度和覆蓋范圍，試卷質量不高，會出現部分測評不能真正體現考核目的的現象。

1 基于遺傳算法和蟻群算法的在線測評系統開發的作用與意義

1.1 在線測評系統的作用

在線測評系統主要是完成客觀還試題的測試作用，目前開發的常見架構主要是瀏覽器服務器模式，同時還伴有瀏覽器服務器模式與客戶服務器模式共用的模式，能夠實現參考者在規定時間內登錄瀏覽器進行考試的過程。降低了組織考試過程中，教室、紙質試卷等物質的消耗，減少了教師監考，人工閱卷等人力資源的使用。同時減少了組織考試必須進行的教師編排、試卷封裝、巡考等考試的環節。

1.2 基于遺傳算法和蟻群算法融合的在線測評系統作用

本系統中，遺傳算法與蟻群算法的應用主要體現在組卷策略模塊當中，算法的應用目的是為了實現試卷試題的難度控制，將難度控制在需求的難度區間之內，從而提升試卷的質量，讓測評具有實際的評估價值。試卷難度過高，或者試卷難度過低，都不能體現應試者的真實水平，也不能給試卷組織題庫組織者很好的反饋，無法對試卷的試題做出準確評價。應用算法則可以控制難度范圍，使得測試范圍和測試難度適中，合理對應試者水平進行區分。而使用兩種算法并進行融合的目的，是為了彌補算法本身的弱點，實現高效率快速的試卷生成策略，并總體的提升試卷組卷的成功率。簡單概括的話，蟻群算法便于易于求出優勢解的集合，適合全局算法，但是在算法初期的路徑選擇過程中耗費大量時間，而遺傳算法可以快速的實現初期的路徑選擇過程，兩者合作，提升試卷生成的效率和成功率。后文會詳細介紹。

2 蟻群算法與遺傳算法簡介

2.1 蟻群算法簡介

蟻群算法顧名思義，是借鑒了生物群體螞蟻的路徑選擇而形成的算法思想，螞蟻由于個體微小，在搬運物品與食物的過程中，都是通過群體合作完成，而大量的螞蟻群體在這個過程中卻能夠選擇較短的合理的路徑。這種原理的思想源于螞蟻本身的氣味分泌功能，螞蟻可以分泌出特殊氣味并附著在經過的路徑當中，這種物質我們定義為信息熵。信息熵具有迭加和揮發的特性，這也就意味著經過這條路徑的螞蟻越多，信息熵濃度越高，同樣的路徑越短，經過的時間也越短，信息熵的揮發也越少。形成了有效的正反饋機制。如圖1。

螞蟻群體在起點A處出發，可以通過若干路徑的集合1或者若干的路徑結合2到達目的地B處，這兩條路徑集合的選擇就是一群算法的體現。初始路徑選擇中，由于沒有可以借鑒的信息，對路徑的選擇是困難的，是隨意出發的，甚至會出現錯路信息，無法到達目的地。而伴隨初期路徑選擇過程的實現，兩條路徑當中，相對通過實踐較短的會被選中。這是因為時間T越短，單位時間內平均通過的螞蟻數量多，信息熵的濃度增大，同時時間T越短，信息熵揮發越少，濃度也性對更高。那么蟻群的選擇標準是信息熵濃度相對高的路徑，不斷循環這個過程，路程短、通過時間短的路徑信息熵濃度會越來越高，也會受到更多的螞蟻選擇，正反饋機制幫助找出相對優解。

蟻群算法優勢與不足：

算法優點：

（1）算法屬于正反饋機制：濃度高則提升被選擇度，而被選擇度高，也會提升路徑濃度，是一種正向反饋機制，便于快速收斂，求出優勢解集。但快速收斂其實也是一把雙刃劍，過于快速收斂容易形成無解集合，在開發過程中應該注意。避免系統工作出現錯誤。

（2）求解過程并不是尋求最優解，而是進行較優解的范圍與集合目標探索，全局性能高。

（3）蟻群算法魯棒性強，在多個領域得到應用，適合進行優勢集合的問題解決，例如貨郎問題，組卷問題、考場安排問題、工業控制問題等等。

存在的不足：任何算法都有其不足之處，蟻群算法也不例外。在試卷生成策略當中，我們也可以看出蟻群算法的缺點，在路徑進行選擇的初期，沒有有效的辦法，需要通過長時間的信息熵的積累，才能達到辨別的濃度，應用到算法生成中，耗費大量算法時間。當然蟻群算法實現試卷生成也可能出現收斂速度快而造成的誤解狀態，這就需要題庫的題目數量足夠，當然通過遺傳算法進行配合，也是實現試卷組卷成功率保障的一個有效方法。

2.2 遺傳算法簡介

遺傳算法的思想來源于生物學，是通過群體的進化規律而進行最優解的求解過程。遺傳算法的實現過程是首先，產生生物學中的染色體，生物特性是通過染色體實現的，而算法中的染色體是通過二進制編碼的形式進行區別和實現的。不同的編碼對應不同的染色體。編碼完成之后，遺傳算法就通過設置迭代次數實現選擇、交叉、變異三個過程。選擇是對編碼后的染色體進行選擇，挑選出適合求解的優秀遺傳個體，而交叉是通過迭代過程，將選出的算子進行數學操作，獲得新解，產生新的下一代。而變異過程則產生更加優秀的個體。

遺傳算法的隨機性能強，通過隨機性能對初期的路徑進行快速的優解，具有一定的作用。

3 算法公式說明

3.1 算法在試卷生成模塊中的具體功能

要使用公式，就要分析算法的具體功能，在試卷生成中，首先要實現試卷的最基本約束條件，也就是普通試卷中的各種設置約束，例如分值、試題類型、試題數量等等。這種功能實現相對簡單，多種算法都可以實現。其次，要進行難度控制，也就是實現應試者學習程度的區分，讓難度數值控制在中等難度區間，從而使得應試者的考試表現不同，讓試卷更加具有實際應用價值。最后，在一些考試中，要注意考點的覆蓋，對不同章節覆蓋程度大為佳。這里算法融合主要是針對難度的控制，產生區分。

3.2 具體公式說明與使用

篇幅有限，這里簡單羅列幾個重點公式：

這個公式為難度控制公式，通過公式求出評卷難度，也就是設置難度的具體指標。N為難度，n為每道試題的難度，C為成績得分項。將總得分除以所有題目難度和，求出評卷難度指標。

算法實現過程中，通過概率來實現新路徑的選擇可能性。S為最終信息熵的具體數值。也就是說明數值的大小與新路徑的選擇有關，結果大選擇新路徑，結果小，直到得出相同選擇，算法實現，得到優勢解集。

4 算法融合實現的說明

算法初期，使用遺傳算法，降低初期路徑選擇的時間復雜度。遺傳算法的實現在于迭代次數的設置。也就相當于設置最小的進化率，如果算法中實際的進化率小于了我們設置的數值，并且一直小于，則遺傳算法完成任務，使用蟻群算法，利用正反快機制和快速收斂等特點，進行快速求解。從而提升試卷生成效率并且提升成功概率。