基于遺傳算法和蟻群算法融合的在線測評(píng)系統(tǒng)

文/姚楠

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

1 基于遺傳算法和蟻群算法的在線測評(píng)系統(tǒng)開發(fā)的作用與意義

1.1 在線測評(píng)系統(tǒng)的作用

在線測評(píng)系統(tǒng)主要是完成客觀還試題的測試作用，目前開發(fā)的常見架構(gòu)主要是瀏覽器服務(wù)器模式，同時(shí)還伴有瀏覽器服務(wù)器模式與客戶服務(wù)器模式共用的模式，能夠?qū)崿F(xiàn)參考者在規(guī)定時(shí)間內(nèi)登錄瀏覽器進(jìn)行考試的過程。降低了組織考試過程中，教室、紙質(zhì)試卷等物質(zhì)的消耗，減少了教師監(jiān)考，人工閱卷等人力資源的使用。同時(shí)減少了組織考試必須進(jìn)行的教師編排、試卷封裝、巡考等考試的環(huán)節(jié)。

1.2 基于遺傳算法和蟻群算法融合的在線測評(píng)系統(tǒng)作用

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

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

2.1 蟻群算法簡介

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

螞蟻群體在起點(diǎn)A處出發(fā)，可以通過若干路徑的集合1或者若干的路徑結(jié)合2到達(dá)目的地B處，這兩條路徑集合的選擇就是一群算法的體現(xiàn)。初始路徑選擇中，由于沒有可以借鑒的信息，對(duì)路徑的選擇是困難的，是隨意出發(fā)的，甚至?xí)霈F(xiàn)錯(cuò)路信息，無法到達(dá)目的地。而伴隨初期路徑選擇過程的實(shí)現(xiàn)，兩條路徑當(dāng)中，相對(duì)通過實(shí)踐較短的會(huì)被選中。這是因?yàn)闀r(shí)間T越短，單位時(shí)間內(nèi)平均通過的螞蟻數(shù)量多，信息熵的濃度增大，同時(shí)時(shí)間T越短，信息熵?fù)]發(fā)越少，濃度也性對(duì)更高。那么蟻群的選擇標(biāo)準(zhǔn)是信息熵濃度相對(duì)高的路徑，不斷循環(huán)這個(gè)過程，路程短、通過時(shí)間短的路徑信息熵濃度會(huì)越來越高，也會(huì)受到更多的螞蟻選擇，正反饋機(jī)制幫助找出相對(duì)優(yōu)解。

蟻群算法優(yōu)勢(shì)與不足：

算法優(yōu)點(diǎn)：

（1）算法屬于正反饋機(jī)制：濃度高則提升被選擇度，而被選擇度高，也會(huì)提升路徑濃度，是一種正向反饋機(jī)制，便于快速收斂，求出優(yōu)勢(shì)解集。但快速收斂其實(shí)也是一把雙刃劍，過于快速收斂容易形成無解集合，在開發(fā)過程中應(yīng)該注意。避免系統(tǒng)工作出現(xiàn)錯(cuò)誤。

（2）求解過程并不是尋求最優(yōu)解，而是進(jìn)行較優(yōu)解的范圍與集合目標(biāo)探索，全局性能高。

（3）蟻群算法魯棒性強(qiáng)，在多個(gè)領(lǐng)域得到應(yīng)用，適合進(jìn)行優(yōu)勢(shì)集合的問題解決，例如貨郎問題，組卷問題、考場安排問題、工業(yè)控制問題等等。

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

2.2 遺傳算法簡介

遺傳算法的思想來源于生物學(xué)，是通過群體的進(jìn)化規(guī)律而進(jìn)行最優(yōu)解的求解過程。遺傳算法的實(shí)現(xiàn)過程是首先，產(chǎn)生生物學(xué)中的染色體，生物特性是通過染色體實(shí)現(xiàn)的，而算法中的染色體是通過二進(jìn)制編碼的形式進(jìn)行區(qū)別和實(shí)現(xiàn)的。不同的編碼對(duì)應(yīng)不同的染色體。編碼完成之后，遺傳算法就通過設(shè)置迭代次數(shù)實(shí)現(xiàn)選擇、交叉、變異三個(gè)過程。選擇是對(duì)編碼后的染色體進(jìn)行選擇，挑選出適合求解的優(yōu)秀遺傳個(gè)體，而交叉是通過迭代過程，將選出的算子進(jìn)行數(shù)學(xué)操作，獲得新解，產(chǎn)生新的下一代。而變異過程則產(chǎn)生更加優(yōu)秀的個(gè)體。

遺傳算法的隨機(jī)性能強(qiáng)，通過隨機(jī)性能對(duì)初期的路徑進(jìn)行快速的優(yōu)解，具有一定的作用。

3 算法公式說明

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

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

3.2 具體公式說明與使用

篇幅有限，這里簡單羅列幾個(gè)重點(diǎn)公式：

這個(gè)公式為難度控制公式，通過公式求出評(píng)卷難度，也就是設(shè)置難度的具體指標(biāo)。N為難度，n為每道試題的難度，C為成績得分項(xiàng)。將總得分除以所有題目難度和，求出評(píng)卷難度指標(biāo)。

算法實(shí)現(xiàn)過程中，通過概率來實(shí)現(xiàn)新路徑的選擇可能性。S為最終信息熵的具體數(shù)值。也就是說明數(shù)值的大小與新路徑的選擇有關(guān)，結(jié)果大選擇新路徑，結(jié)果小，直到得出相同選擇，算法實(shí)現(xiàn)，得到優(yōu)勢(shì)解集。

4 算法融合實(shí)現(xiàn)的說明

算法初期，使用遺傳算法，降低初期路徑選擇的時(shí)間復(fù)雜度。遺傳算法的實(shí)現(xiàn)在于迭代次數(shù)的設(shè)置。也就相當(dāng)于設(shè)置最小的進(jìn)化率，如果算法中實(shí)際的進(jìn)化率小于了我們?cè)O(shè)置的數(shù)值，并且一直小于，則遺傳算法完成任務(wù)，使用蟻群算法，利用正反快機(jī)制和快速收斂等特點(diǎn)，進(jìn)行快速求解。從而提升試卷生成效率并且提升成功概率。