石慧升 王彥志

[摘要]本文針對智能組卷問題的特點(diǎn)對基本人工魚群算法進(jìn)行了相應(yīng)的改進(jìn)與優(yōu)化，為群體智能算法應(yīng)用于組合優(yōu)化問題進(jìn)行了一些探索。

[關(guān)鍵詞]智能組卷 組合優(yōu)化問題 人工魚群算法

引言：隨著計(jì)算機(jī)技術(shù)、互聯(lián)網(wǎng)技術(shù)、多媒體技術(shù)的迅速發(fā)展，計(jì)算機(jī)廣泛應(yīng)用于各種領(lǐng)域，尤其是在教育領(lǐng)域，計(jì)算機(jī)科學(xué)技術(shù)與教育學(xué)的融合在計(jì)算機(jī)輔助教育，方面得到了突飛猛進(jìn)的發(fā)展，本文在對基本人工魚群算法分析研究的基礎(chǔ)上，針對其不足之處研究了人工魚群算法的改進(jìn)方法，并采用實(shí)現(xiàn)了相應(yīng)的改進(jìn)算法。通過對比遺傳算法實(shí)驗(yàn)結(jié)果表明，改進(jìn)的人工魚群算法的組卷成功率略低于遺傳算法，但是組卷所需時(shí)間小于遺傳算法且滿意度由增加到，它在一定程度上提高了基本人工魚群算法的尋優(yōu)精度，為計(jì)算機(jī)輔助教學(xué)系統(tǒng)的實(shí)際應(yīng)用進(jìn)行了一些探索。

1智能組卷問題的幾種智能算法

1.1隨機(jī)組卷法：隨機(jī)組卷法是出現(xiàn)最早的組卷算法，其基本思想是：首先根據(jù)用戶輸入的試卷約束標(biāo)準(zhǔn)，利用計(jì)算機(jī)和數(shù)據(jù)庫技術(shù)從試題庫中任意抽取一道試題，然后判斷該試題是否滿足用戶設(shè)置的難度系統(tǒng)、區(qū)分度等約束條件，若滿足則添加到試卷中，若不滿足，則繼續(xù)試探直到生產(chǎn)滿足用戶需求的試卷為止。隨機(jī)組卷法的優(yōu)點(diǎn)是簡單易實(shí)現(xiàn)，缺點(diǎn)是算法執(zhí)行過程中，抽不到滿足要求的試題時(shí)，容易陷入死循環(huán)、算法精度不高、對試題庫要求較高，隨機(jī)組卷算法要求數(shù)據(jù)庫中的試題量不大，以及試題分布良好;當(dāng)試題庫較大，且分布不是很均勻的情況下，隨機(jī)組卷的成功率較低。因此，隨機(jī)組卷的整體效率和組卷成功率均較低，不能很好地滿足用戶的需要。

1.2遺傳算法：遺傳算法：其基本思想是借鑒自然界中生物進(jìn)化過程中適者生存優(yōu)勝劣的自然淘汰機(jī)制而形成的一種自適應(yīng)優(yōu)化搜索算法，模擬生物群體的繁殖、交配和變異現(xiàn)象，從一個(gè)種群開始，產(chǎn)生更適應(yīng)環(huán)境的一些個(gè)體。以此一代一代地迭代，最后隨著時(shí)間的推移收斂到一個(gè)最適應(yīng)環(huán)境的一些個(gè)體遺傳算法是使用頻率較高的一種組卷算法，自提出以來受到國內(nèi)外學(xué)者的廣泛關(guān)注，在智能組卷問題中，中的一個(gè)個(gè)體代表一套試卷，個(gè)體的適應(yīng)值大小反應(yīng)了試卷滿足用戶要求的程度。適應(yīng)度與目標(biāo)函數(shù)值的成反比即目標(biāo)函數(shù)值越小，個(gè)體的適應(yīng)度越大，相應(yīng)生成的試卷則越滿足實(shí)際用戶的要求。遺傳算法中選擇不同的染色體編碼策略對算法性能影響較大，也是將遺傳算法應(yīng)用于某一具體問題時(shí)，首要解決的關(guān)鍵問題。常見的編碼策略有：二進(jìn)制編碼、十進(jìn)制編碼、混合編碼等。在實(shí)際應(yīng)用中應(yīng)根據(jù)需要解決的問題的特點(diǎn)，在進(jìn)行大量分析研究的基礎(chǔ)上選擇最適合的編碼策略。

2人工魚群算法理論

人工魚群算法是李曉晶博士等通過對自然界魚群的長期觀察而提出的一種啟發(fā)式搜索算法。主要利用魚群的覓食、追尾、聚群、隨機(jī)游行為，通過魚群中單個(gè)個(gè)體的局部尋優(yōu)達(dá)到最終尋找全局最優(yōu)解的目的。算法具有全局收斂性好、對初值要求不高、魯棒性強(qiáng)等優(yōu)點(diǎn)并且算法只需對目標(biāo)函數(shù)的函數(shù)值優(yōu)劣進(jìn)行比較，不需要目標(biāo)函數(shù)的適應(yīng)度等特殊信息，有著較快的收斂速度，能很好解決非線性函數(shù)優(yōu)化等問題。人工魚模型中的人工魚是自然界中魚的一個(gè)模擬實(shí)體，常用作問題的說明和分析。人工魚模型可以將人工魚看成是封裝了自身數(shù)據(jù)和一系列行為的實(shí)體。

3人工魚群算法求解智能組卷問題

求解智能組卷問題是本文重點(diǎn)研究的內(nèi)容，使用算法進(jìn)行智能組卷涉及到算法收斂速度和尋找全局最優(yōu)解的問題。如何使人工魚群算法快速有效的搜索到全局最優(yōu)解是本文研究的重要內(nèi)容。隨機(jī)組卷法對數(shù)據(jù)庫的要求比較苛刻;遺傳算法容易出現(xiàn)早熟現(xiàn)象;故不能很好的滿足實(shí)際組卷的要求。人工魚群算法具有實(shí)現(xiàn)簡單、只需比較目標(biāo)函數(shù)值優(yōu)劣、初值要求低、收斂速度快的特點(diǎn)，本文將應(yīng)用于智能組卷系統(tǒng)。嘗試對中人工魚的覓食行為、聚群行為、追尾行為進(jìn)行設(shè)計(jì)，實(shí)驗(yàn)結(jié)果表明基本的人工魚群算法組卷成功率不高，但滿意度相對于隨機(jī)組卷有所提高。

智能組卷問題在傳統(tǒng)的教學(xué)中，試卷通常采用教師根據(jù)教學(xué)大綱和實(shí)際教學(xué)情況的方式進(jìn)行組卷的。每次考試前，教師需要花費(fèi)很多的精力和時(shí)間組出一份難易程度適中、能準(zhǔn)確檢測學(xué)生學(xué)習(xí)情況的試卷。隨著計(jì)算機(jī)輔助教育的廣泛推廣，計(jì)算機(jī)技術(shù)不僅僅是一門學(xué)科，而逐漸成為教學(xué)活動(dòng)中必不可少的教學(xué)工具和進(jìn)行教學(xué)管理的重要手段之一。利用計(jì)算技術(shù)和智能算法進(jìn)行組卷，有助于減輕教師的負(fù)擔(dān)，使教師將更多的精力用在教學(xué)或者科研上。智能組卷系統(tǒng)是指將教育專家的組卷經(jīng)驗(yàn)和人工智能算法結(jié)合起來，根據(jù)用戶設(shè)置的組卷約束參數(shù)，利用組卷算法搜索試題庫中滿足組卷約束條件的試題，從而生成滿足用戶要求的試卷。智能組卷基礎(chǔ)理論主要涉及：組卷目標(biāo)約束、組卷問題的數(shù)學(xué)模型、試卷的評價(jià)指標(biāo)、自動(dòng)組卷算法、算法的編碼方式及試題庫中試題的結(jié)構(gòu)等內(nèi)容。目前，自動(dòng)組卷算法是組卷系統(tǒng)研究的難點(diǎn)與重點(diǎn)，也是本文所要進(jìn)行討論的主要內(nèi)容。

4人工魚群算法的改進(jìn)

人工魚群算法是近幾年發(fā)展起來的一種新型尋優(yōu)算法，它主要是通過模擬魚群的覓食、追尾、聚群等行為進(jìn)行尋優(yōu)，利用單個(gè)個(gè)體局部最優(yōu)信息，從而尋找全局最優(yōu)解的目的，基本的人工魚算法具有良好的跳出局部極值、尋找到全局極值的能力、對算法的初始化要求不高，該算法簡單，易于編程程序?qū)崿F(xiàn)，具有較好的收斂性能。由于人工魚的行為是局部尋優(yōu)行為，算法在執(zhí)行過程中可能會(huì)陷于局部極值，難以找到全局最優(yōu)解。為了提高人工魚群算法的尋優(yōu)能力和算法的尋優(yōu)精度，本文從改進(jìn)人工魚的覓食、聚群、追尾行為及引入人工魚跳躍行為的方向改進(jìn)，幫助算法更精確、更快的尋找到全局最優(yōu)解，提局尋優(yōu)能力。

5結(jié)論：本文雖然在人工魚群算法應(yīng)用于智能組卷模塊的技術(shù)實(shí)現(xiàn)上做了一定的探索，但今后依然有許多問題有待于做進(jìn)一步的研究和改進(jìn)。人工魚群算法是仿生優(yōu)化算法的一種，目前對人工魚群算法的研究還處在初始階段，有很多不足的地方。尋優(yōu)的不足之處是，在本系統(tǒng)中當(dāng)組卷約束條件設(shè)置的極端且精度要求高的情況下，組卷成功率有所降低。