石慧升 王彥志

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

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

引言：隨著計(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ā)展，本文在對(duì)基本人工魚(yú)群算法分析研究的基礎(chǔ)上，針對(duì)其不足之處研究了人工魚(yú)群算法的改進(jìn)方法，并采用實(shí)現(xiàn)了相應(yīng)的改進(jìn)算法。通過(guò)對(duì)比遺傳算法實(shí)驗(yàn)結(jié)果表明，改進(jìn)的人工魚(yú)群算法的組卷成功率略低于遺傳算法，但是組卷所需時(shí)間小于遺傳算法且滿(mǎn)意度由增加到，它在一定程度上提高了基本人工魚(yú)群算法的尋優(yōu)精度，為計(jì)算機(jī)輔助教學(xué)系統(tǒng)的實(shí)際應(yīng)用進(jìn)行了一些探索。

1智能組卷問(wèn)題的幾種智能算法

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

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

2人工魚(yú)群算法理論

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

3人工魚(yú)群算法求解智能組卷問(wèn)題

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

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

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

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

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