改進的人工魚群混合算法在智能組卷中的應(yīng)用

吳 旭，洪聯(lián)系，魏德志，郭劍平

(集美大學誠毅學院，福建廈門361021)

改進的人工魚群混合算法在智能組卷中的應(yīng)用

吳 旭，洪聯(lián)系，魏德志，郭劍平

(集美大學誠毅學院，福建廈門361021)

現(xiàn)有的智能組卷多采用單一算法，而每種算法都有其各自的缺點，針對此缺陷提出了結(jié)合人工魚群算法和遺傳算法的優(yōu)點組成混合智能組卷算法．在智能組卷開始時，采用人工魚群算法快速靠近組卷目標，在組卷過程中，當最優(yōu)個體在連續(xù)多個迭代過程中無變化或變化極小時采用遺傳算法對人工魚個體進行跳變，提高收斂速度．通過模擬計算證明，該混合智能算法能有效地優(yōu)化其中單一算法獨自進行智能組卷的成效．

智能組卷;人工魚群;遺傳算法;混合智能算法

0 引言

隨著信息技術(shù)的發(fā)展，傳統(tǒng)的人工組卷方式已經(jīng)不能滿足許多新出現(xiàn)的考核需求．例如，駕校理論考試機考、高校計算機等級考試機考、英語四六級機考、GRE機考和眾多網(wǎng)絡(luò)在線考試等．這些考試系統(tǒng)的共同特征就是題庫量大、考核內(nèi)容全面，在考核期間可隨時無限量提供既符合考核指標要求又互不相同的試卷，具有隨機性、科學性、合理性，尤其在交互式環(huán)境下可滿足用戶對組卷速度高的要求等．智能組卷問題實質(zhì)上是一個多重約束條件的優(yōu)化問題，目標的約束越多，問題的復(fù)雜度就越大．組卷過程是智能化、自動化的不斷試探往復(fù)的過程．智能組卷主要有隨機抽取法［1］、回溯法［2］、遺傳算法［3］、模擬退火算法［4］、粒子群算法［5］等．在智能組卷研究起步早期較多采用隨機抽取法、回溯法，目前智能組卷較多采用遺傳算法、模擬退火算法、粒子群算法等．這些算法都存在約束條件的局部滿足、參數(shù)不確定、組卷時間過長等問題．

人工魚群算法 (AFSA)只需要比較目標函數(shù)值，具備對初值要求不高，可隨機產(chǎn)生或設(shè)置固定值，收斂快等優(yōu)點［6］．目前該算法已經(jīng)由解決一維靜態(tài)優(yōu)化問題發(fā)展到解決多維動態(tài)組合優(yōu)化問題，并在神經(jīng)網(wǎng)絡(luò)、電力系統(tǒng)、通風系統(tǒng)、油田定位、模糊控制器設(shè)計、灌區(qū)優(yōu)化配水、數(shù)據(jù)挖掘、多用戶檢測、湖泊富營養(yǎng)綜合評價、路由優(yōu)化、任務(wù)調(diào)度和數(shù)字圖像信號處理、非線性復(fù)雜函數(shù)最優(yōu)化等方面得到了一定的應(yīng)用，并取得了較好的應(yīng)用效果．人工魚群算法雖然具有上述的優(yōu)良特性，但是人工魚群算法前期搜索較快，后期較慢，且隨著人工魚數(shù)量增加，計算量相應(yīng)增大，尋優(yōu)精度難以提高［7］，因此也限制了單純依靠人工魚群算法行業(yè)應(yīng)用的進一步發(fā)展．針對這個問題，研究者開始在人工魚群算法中引入其他算法，利用不同算法的優(yōu)勢形成互補，從而較大地提高人工魚群算法的效率．遺傳算法 (GA)是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優(yōu)解的方法，最初由美國Michigan大學J.Holland教授于1975年首先提出來［8］．遺傳算法具有同時處理群體中的多個個體，覆蓋面大，減少了陷入局部最優(yōu)解的風險，利于全局擇優(yōu)，具有良好的自組織、自適應(yīng)和自學習等優(yōu)點．湖南農(nóng)業(yè)大學的任劍等［10］設(shè)計了基于層次分析方法與人工魚群算法相結(jié)合的智能組卷算法，主要通過層次分析法確定各組卷目標的權(quán)重，進而通過線性加權(quán)求和將多目標規(guī)劃模型轉(zhuǎn)換為單目標規(guī)劃模型，最后利用改進的人工魚群算法求解模型得到最優(yōu)組卷方案;許昌學院的李娟等［11］采用基于人工魚群模型的自動組卷抽題算法研究了智能組卷方式，并對魚群的聚群追尾行為進行了改進．

人工魚群算法和遺傳算法的特性決定了其同樣適合解決智能組卷的相關(guān)問題．采用人工魚群與遺傳混合算法進行人工智能組卷的研究目前還很少，但在其他領(lǐng)域已經(jīng)有了一些應(yīng)用．郭衛(wèi)等［12］采用人工魚群算法模擬梯級水庫優(yōu)化調(diào)度，再用遺傳算法進行局部細化搜索，實例結(jié)果表明該混合算法行之有效．本文擬提出結(jié)合兩種算法的優(yōu)點來解決目前智能組卷中的算法缺陷，在組卷前期采用人工魚群算法快速靠近組卷目標，當人工魚群中的最優(yōu)個體在連續(xù)迭代過程中沒有變化或者變化較小時，采用遺傳算法中的選擇運算、交叉運算、變異運算實現(xiàn)人工魚的跳變．

1 智能組卷數(shù)學模型的建立

智能組卷模型約束條件的目標函數(shù)如下．

其中，fi代表第i個屬性指標與用戶指定指標的誤差絕對值;wi代表不同屬性在組卷中重要程度的權(quán)值;ei代表組卷各個目標的屬性;mi代表允許誤差范圍．f的值越小，說明組卷結(jié)果越接近設(shè)定的目標要求．

各屬性約束條件的設(shè)定如下．

1)總分約束條件S的值由教師設(shè)定，通常S=100．

2)各章節(jié)分約束條件SCk的值由教師設(shè)定．定義Cc為章節(jié)知識點覆蓋率，Cc=試卷包含章節(jié)數(shù)/總章節(jié)數(shù)，C值約束條件由教師設(shè)定，一般情況Cc≥65%．

3)每種題型總分約束條件由教師設(shè)定．定義Cq為題型覆蓋率，Cq=1．

4)各知識點總分SKk約束由教師設(shè)定．定義Ck為知識點覆蓋率，Ck=試卷所包含知識點/考綱要求知識點數(shù)，一般設(shè)定Ck≥80%．

5)約束條件為各難度范圍內(nèi)的試題期望分值在教師限定范圍內(nèi)．

6)試卷區(qū)分度條件由教師設(shè)定．

7)考試時間T約束條件由教師設(shè)定，通常T=120 min．

2 人工魚群算法與遺傳算法的混合算法 (HIOA－GFA)

2.1 AFSA和GA的設(shè)計

2.1.1 AFSA的設(shè)計

人工魚個體狀態(tài)X=(x1，x2，…，xn)，其中xi(i=1，2，…，n)為尋優(yōu)變量，人工魚視野范圍用Visual表示，人工魚移動步長最大值用Step表示，擁擠度因子用δ表示．魚群規(guī)模用Np表示．

1)覓食行為，可以認為魚是通過感知水中的食物量或濃度來選擇趨向的．在算法中表現(xiàn)為魚經(jīng)過試探，在人工魚當前狀態(tài)的d領(lǐng)域距離內(nèi)搜索得到更優(yōu)解，如果在次數(shù)k以內(nèi)無法找到更優(yōu)解則執(zhí)行隨機行為．

2)聚群行為，大量或少量的魚都能聚集成群，用這種生存方式可以進行集體覓食和迷惑敵害．魚聚群時所遵守的規(guī)則有三條，分別是分隔規(guī)則 (盡量避免與臨近伙伴過于擁擠)、對準規(guī)則 (盡量與臨近伙伴的平均方向一致)、內(nèi)聚規(guī)則 (盡量朝臨近伙伴的中心移動)．在算法中表現(xiàn)為，人工魚在當前狀態(tài)Xi的d距離領(lǐng)域內(nèi)發(fā)現(xiàn)中心位置食物濃度更高且不太擁擠，則向中心位置移動．

3)追尾行為，當某一條魚或幾條魚發(fā)現(xiàn)食物時，附近的魚會尾隨其后快速游過來，進而導(dǎo)致更遠處的魚也尾隨過來．在算法描述中表現(xiàn)為魚在當前狀態(tài)的d距離領(lǐng)域內(nèi)搜索最優(yōu)解Xmax，如果對應(yīng)位置的食物濃度Ymax更高且不太擁擠，則向該位置前進一步．

4)隨機行為，魚在水中悠閑的自由游動，基本上是隨機的，其實也是為了在更大范圍中尋覓食物或同伴．在算法中表現(xiàn)為魚向任意方向前進一步．

5)使用公告板記錄當前最優(yōu)函數(shù)值．

6)魚群經(jīng)過覓食、聚群、追尾、隨機行為選擇后生成新魚群．

終止條件判斷，當達到最大搜索次數(shù)后取公告板值或公告板上函數(shù)值滿足條件則停止搜索［13］．

2.1.2 GA的設(shè)計

一個生物種群是由經(jīng)過基因編碼的一定數(shù)目的個體組成．每個個體是帶有特征染色體的實體．染色體作為遺傳物質(zhì)的主要載體決定了個體性狀的外部表現(xiàn)．遺傳算法采納了自然進化模型如選擇、交叉、變異、遷移、局域與臨域等隨機初始化生成一定數(shù)目個體種群，通過計算個體適應(yīng)度，不斷比較和優(yōu)化個體產(chǎn)生新生代直至滿足最優(yōu)解．

1)初始化，設(shè)置進化代數(shù)計數(shù)器n=0，設(shè)置最大進化代數(shù)K，隨機生成M個個體作為初始群體P(0)．

2)個體評價，計算群體P(t)中各個個體的適應(yīng)度．

3)選擇運算，將選擇算子作用于群體．選擇的目的是把優(yōu)化的個體直接遺傳到下一代或通過配對交叉產(chǎn)生新的個體再遺傳到下一代．

4)交叉運算，將交叉算子作用于群體．所謂交叉是指把兩個父代個體的部分結(jié)構(gòu)加以替換重組而生成新個體的操作．

5)變異運算，將變異算子作用于群體，即對群體中的個體串的某些基因值作變動．

6)群體P(t)經(jīng)過選擇、交叉、變異運算之后得到下一代群體P(t1)．

終止條件判斷，當達到最大搜索次數(shù)，則以進化過程中所得到的具有最大適應(yīng)度個體作為最優(yōu)解輸出，或適應(yīng)度函數(shù)值滿足條件則結(jié)束運算輸出對應(yīng)解．

2.2 HIOA－GFA的編碼

本混合算法是基于人工魚群算法與遺傳算法的混合算法．在人工魚群算法運行到連續(xù)不變化或變化極小時將使用遺傳算法進行收斂．由于遺傳算法本身的生物學特性，使用二進制編碼有利于遺傳操作，所以本HIOA－GFA使用二進制編碼形式．選中的題目用1表示，未被選中則用0表示．例如題庫有10道題，其中6道被選中，分別是第1、3、4、6、8、9道試題，則該份試卷二進制編碼為1011010110．采用人工魚群算法運行時，將每一套生成的試卷視作為一條候選魚．采用遺傳算法運行時，將每一套生成的試卷視作為一個染色體．

2.3 HIOA－GFA的組卷流程

1)初始化公告板．根據(jù)滿足分數(shù)、題型、二項基本要求隨機產(chǎn)生n條魚．

組卷時，可首先設(shè)置為生成僅滿足分數(shù)為100分，題型覆蓋單選、多選、判斷、問答、設(shè)計5個題型的 n條魚，即 n套如下試卷:X1=001010111000…1，X2=110001000110…0，……，Xn=011000110111…1．

不采用完全隨機生成初始魚群是因為這樣可以加快魚群收斂速度;設(shè)置4個參數(shù)，分別是stopIterate代表人工魚狀態(tài)連續(xù)不變化或變化很小時的迭代次數(shù)，初始值為0;maxStopIterate代表魚群最大允許連續(xù)不變化次數(shù);iterateNum代表遺傳操作迭代次數(shù)計數(shù)器，初始值為0;maxIterateNum代表遺傳操作最大允許迭代次數(shù)．最后設(shè)置人工魚的相關(guān)參數(shù)如Visual(可視域)、Step(步長)、δ(擁擠度因子)、tryNum(試探次數(shù))等．

2)計算初始魚群各個體當前狀態(tài)值，選取最小值的魚進入公告板，并把該人工魚狀態(tài)值賦予公告板．

組卷時，由計算機分別計算出這n套試卷的目標函數(shù)f值，并將f值最小的那套試卷所對應(yīng)的二進制編碼存入字符串變量bestFish，同時將最小的f值賦予變量board，即記錄到公告板．

3)根據(jù)人工魚群算法進行追尾、聚群、覓食行為或隨機行為的選擇．如果行為選擇之后，最小值無變化，則人工魚再進行隨機行為，并且設(shè)置stopIterate=stopIterate+1．

組卷時，追尾活動表現(xiàn)為每條魚Xi即每套二進制編碼試卷查看在自己Visual(可視域)范圍內(nèi)的其他二進制編碼試卷，從中找出目標函數(shù)值f最小的試卷Xj，對應(yīng)目標函數(shù)值f記為Yj．Xj周圍在可視域內(nèi)其他試卷數(shù)量記為nf．若Yj*nf＜δ(擁擠度因子)*Yi，則認為Xj周圍“食物”較多而且不太擁擠，這個時候試卷Xi可以對自己和試卷Xj的不同位進行重新隨機取值，比如Xi=0011001，Xj=0010100，則把Xi的第四、第五和第七位隨機取值，從而使得Xi向Xj靠近．

在追尾失敗的情況下，聚群行為表現(xiàn)為每條魚Xi，即每套試卷找出自己可視域內(nèi)的其他試卷，形成小魚群，然后找出所在魚群中心點．找尋中心點具體表現(xiàn)為若魚群中半數(shù)以上試卷在第i位上取1，則中心點第i位也是1，否則設(shè)置為0．之后方式采用追尾行為中判斷食物濃度和擁擠度來決定是否向中心點靠近．

在聚群失敗的情況下進行覓食活動，即每套試卷隨機從自身選取visual(可視域)個位，并對所選取的這些位進行隨機變換，若新狀態(tài)更優(yōu)則向新狀態(tài)移動，否則重新進行覓食，重復(fù)tryNum(嘗試次數(shù))次后依然沒有更優(yōu)則進行隨機移動．

4)各人工魚行為選擇后比較自身f值和公告板board的值，如果f值優(yōu)于公告板board值，則用對應(yīng)試卷編碼取代bestfish，同時用自身f值更新公告，設(shè)置stopIterate=0．

5)判斷stopIterate的值是否等于maxStopIterate．如果兩者值相等，執(zhí)行遺傳操作，即跳轉(zhuǎn)到6)．否則判斷算法終止條件，即跳轉(zhuǎn)到7)．

6)除公告板上人工魚外，進行遺傳操作．將魚群進行適應(yīng)值降序排序．首先，選擇適應(yīng)值前30%的染色體直接進入子代;其次，選擇接下來69%的染色體進行單點雜交;最后，選擇尾部1%的染色體進行變異操作．計算新生成的各染色體個體值，并比較公告板，如果優(yōu)于則取代;設(shè)置stopIterate=0．

7)判斷是否滿足算法終止條件，即iterateNum的值是否等于maxIterateNum的值，如不滿足則設(shè)置iterateNum=iterateNum+1，并且跳轉(zhuǎn)到3)執(zhí)行．滿足則結(jié)束算法運行，輸出公告板上的最優(yōu)解［7］．

算法流程圖如圖1所示．

圖1 HIOA-GFA流程圖Fig.1 Flow chart for the HIOA-GF

3 HIOA－GFA實驗分析

3.1 實驗條件及算法參數(shù)設(shè)定

為了驗證HIOA－GFA算法的可行性和有效性，利用現(xiàn)有《大學計算機應(yīng)用基礎(chǔ)》題庫中1500套題目進行組卷實驗．該題庫包含了選擇題、填空題、判斷題、程序設(shè)計題、問答題等，每組試卷總分100分，考試時間120 min，試卷難度系數(shù)0.5．

實驗環(huán)境為Windows xp操作系統(tǒng)，CPU為Inter Core 2 Duo 2.4G主頻，2G內(nèi)存，Visiual Studio 2008環(huán)境下C#語言編程實現(xiàn)，數(shù)據(jù)庫使用SQL SERVER 2005．

HIOA－GFA參數(shù)設(shè)定為群體規(guī)模Np為30，AFSA中最大連續(xù)不變化次數(shù)maxStopIterate=10，視野Visual=4，步長Step=1，擁擠度因子δ=6，試探次數(shù)tryNum=3．GA中最大迭代次數(shù)maxIterate-Num=120．遺傳操作中選擇概率yc=0.30、交叉概率ym=0.69、變異概率yv=0.01．

抽題模型參數(shù)如表1所示．

表1 抽題模型參數(shù)Tab．1 Parameters for the extracting －title model

3.2 實驗結(jié)果

依據(jù)上述組卷要求，采用隨機抽取法 (SSA)、人工魚群算法 (AFSA)、遺傳算法 (GA)、人工魚群與遺傳混合算法 (HIOA－GFA)4種組卷算法進行對比實驗，對題庫為1500道題分別組卷20次，4類成功率對比如圖2所示，平均耗時對比如圖3所示．

圖2 4種算法20次組卷成功率對比圖Fig.2 The success rate's comparison chart for using the four algorithms to test papers 20 times

圖3 4種算法20次組卷平均耗時對比圖Fig.3 The average time-consuming comparison chart for using the four algorithms to test papers 20 times

3.3 結(jié)果分析

3.3.1 算法有效性分析

從圖2對比數(shù)據(jù)看出，隨機抽取算法在題庫量大時，成功率明顯偏低，在本案例中只有45%．單獨采用人工魚群算法和遺傳算法成功率分別提高至78%和69%，但是成功率依然不高．采用HIOA－GFA進行組卷，成功率達到了100%．所以采用HIOA－GFA組卷可以很好地滿足用戶的組卷需求．

3.3.2 算法組卷效率分析

從圖3對比數(shù)據(jù)看出，隨機抽取法組卷速度慢，平均每次組卷耗時198 s．單獨采用AFSA或GA組卷，效率有所提高，但是時間消耗依然較長，不能夠很好滿足用戶需要．采用HIOA－GFA進行組卷，時間則大為縮短，耗時分別只有前3種算法的11.6%，26.7%，31.9%．因此可以看出，采用HIOA－GFA進行智能組卷可以快速提高組卷速度．

［1］王萌，金漢均，王曉榮，等．集合隨機抽選法在智能組卷中的研究 ［J］．計算機工程與設(shè)計，2006，27(19):3584－3585．

［2］王文發(fā)，馬燕，李宏達．回溯法求解多約束分配問題［J］．江西師范大學學報:自然科學版，2008，32(6):729－732．

［3］張琦，鄭河榮，劉志．基于優(yōu)化遺傳算法的智能組卷系統(tǒng)研究［J］．浙江工業(yè)大學學報，2009，37(3):307－310．

［4］周艷聰，劉艷柳，顧軍華．小生境自適應(yīng)遺傳模擬退火智能組卷策略研究［J］．小型微型計算機系統(tǒng)，2011，32(2):323－326．

［5］閻峰，安曉東．基于粒子群優(yōu)化算法的智能抽題策略研究［J］．中北大學學報:自然科學版，2008，29(4):334－337．

［6］李廣水，馬青霞，陳愛萍，等．分布式遺傳算法在智能組卷中的Web services實現(xiàn) ［J］．計算機應(yīng)用研究，2010，27(11):4185－4186．

［7］張漢強．人工魚群混合智能優(yōu)化算法及其應(yīng)用研究［D］．浙江:浙江工業(yè)大學控制系，2010．

［8］周艷麗．基于改進遺傳算法的自動組卷問題研究 ［J］．計算機仿真，2010，27(9):320－321．

［9］黃艷峰，陳濤．基于改進遺傳算法的智能組卷系統(tǒng)的設(shè)計與實現(xiàn) ［J］．煤炭技術(shù)，2009，28(10):150－151．

［10］任劍，卞燦，全惠云．基于層次分析方法與人工魚群算法的智能組卷 ［J］．計算機應(yīng)用研究，2010，27(4):1293－1300．

［11］李娟，田勝利．基于人工魚群模型的自動組卷抽題算法研究 ［J］．許昌學院學報，2008，27(5):92－97．

［12］郭衛(wèi)，方國華，黃顯峰．基于人工魚群遺傳算法的梯級水庫優(yōu)化調(diào)度研究 ［J］．水電能源科學，2011，29(6):49－51．

［13］張梅鳳．人工魚群智能優(yōu)化算法的改進及應(yīng)用研究［D］．大連:大連理工大學電子與信息工程學院，2008．

(責任編輯 朱雪蓮 英文審校 黃振坤)

Improved AFSA for Solving Intelligent Test Problem

WU Xu1，HONG Lian-xi2，WEI De-zhi3，GUO Jian-ping4
(Chenyi College，Jimei University，Xiamen 361021，China)

Intelligent auto－generating paper was a optimization problem which had multi－target parameter in certain constraint conditions．There had been many algorithms to realize intelligent auto－generating paper．But，most of the methods achieving the target used only a single algorithm．Since each of the algorithm had its own shortcomings，so in the process of intelligent auto －generating paper，it sometimes can't avoid the defects of a single algorithm．By incorporating AFSA and GA's advantages into a mathematical model for intelligent auto-generating paper，a HIDA algorithm was proposed．In the course of generating paper，the AFSA was adopted to approach to the target first．When the best individual didn't change or changed very small continually，the GA was used to make the fish jump to increase the convergence speed．The results of experiments showed that the HIOA －GFA was better than single one of the Algorithms to generate paper．

intelligent auto－generating paper;AFSA;GA;HIOA

TP 301.6

A

1007－7405(2012)05－0394－07

2012－01－18

2012－06－10

集美大學誠毅學院重點教學改革基金資助項目 (P10222)

吳旭 (1981—)，男，實驗師，碩士，主要從事智能算法、網(wǎng)絡(luò)安全、云計算等方向研究．