應(yīng)用人工生命模型Bug／BACO求解組卷問題研究

錢 乾

(安徽工程大學(xué)計(jì)算機(jī)與信息學(xué)院，安徽 蕪湖241000安徽商貿(mào)職業(yè)技術(shù)學(xué)院電子信息工程系，安徽 蕪湖241002)

周鳴爭(zhēng)

（安徽工程大學(xué)計(jì)算機(jī)與信息學(xué)院，安徽 蕪湖241000）

程美英

（安徽商貿(mào)職業(yè)技術(shù)學(xué)院電子信息工程系，安徽 蕪湖240002）

趙傳信

（安徽師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)學(xué)院，安徽 蕪湖241002）

自20世紀(jì)90年代初意大利學(xué)者Dorigo M提出蟻群優(yōu)化算法（ACO）以來，許多學(xué)者致力于該算法的改進(jìn)。文獻(xiàn)［1］將遺傳算法交替在搜索空間及解空間中工作的方式與使用自定義搜索空間的連續(xù)域蟻群優(yōu)化算法相集合，提出了二進(jìn)制蟻群優(yōu)化算法（或稱二元蟻群優(yōu)化算法），并在連續(xù)域（如函數(shù)優(yōu)化）及離散域（0／1背包問題、組卷問題、二次分配問題等）［2］優(yōu)化問題中均得到了較好的應(yīng)用。“探索和利用”的沖突是二元蟻群優(yōu)化算法固有的缺陷，而擁塞控制策略［3］、捕食與區(qū)域劃分算子［4］、搜索偏向控制函數(shù)［5］等的引入可以彌補(bǔ)其早熟收斂的缺陷，但這在一定程度上導(dǎo)致算法評(píng)價(jià)次數(shù)的增加，從算法執(zhí)行時(shí)間來看，這種偽并行（順序）算法的計(jì)算復(fù)雜性嚴(yán)重阻礙其在大規(guī)模優(yōu)化問題中的應(yīng)用。下面，筆者從人工生命的角度對(duì)二元蟻群優(yōu)化算法重新進(jìn)行描述。

1 Bug－BACO算法

圖1 一維Bug人工生命模型

圖2 Bug－BACO算法原理圖

假設(shè)有一個(gè)人工生命叫作Bug，它爬行在一條長(zhǎng)長(zhǎng)的紙帶上（見圖1，其實(shí)質(zhì)是一個(gè)一維二元細(xì)胞自動(dòng)機(jī)），紙帶上每個(gè)方格的顏色 ｛黑、白｝可用細(xì)胞狀態(tài)0／1代替（黑色代表細(xì)胞的狀態(tài)為0，白色代表細(xì)胞的狀態(tài)為1），Bug遍歷完一趟圖1的紙帶，實(shí)質(zhì)上就是完成了一次對(duì)候選解的選擇過程。因此，可以將圖1的一維二元細(xì)胞自動(dòng)機(jī)引入到蟻群算法中，讓螞蟻在圖1所示的一維網(wǎng)格上移動(dòng)，將螞蟻?zhàn)裱臄?shù)學(xué)模型作為細(xì)胞自動(dòng)機(jī)的轉(zhuǎn)換函數(shù)。探索和利用的沖突是蟻群優(yōu)化固有的缺陷，為防止算法陷入局部最優(yōu)，在算法中引入了更多的隨機(jī)擾動(dòng)因素，提出了基于Bug人工生命模型的二元蟻群優(yōu)化算法Bug－BACD算法（見圖2）。

假設(shè)在一條直線上均勻分布著L個(gè)細(xì)胞，螞蟻種群的規(guī)模為m；細(xì)胞狀態(tài)集合Q∈｛0，1｝，?t，螞蟻k，第i（i＝1，2，…，L）個(gè)細(xì)胞狀態(tài)0上分布的信息素為第i個(gè)細(xì)胞狀態(tài)1上分布的信息素為：Pp為預(yù)先設(shè)定的一個(gè)擾動(dòng)概率，任意時(shí)刻，若則螞蟻選擇狀態(tài)0（即Q ＝0），反之選擇狀態(tài)1（即Q＝1）。經(jīng)過t時(shí)刻，當(dāng)所有螞蟻完成一次對(duì)細(xì)胞內(nèi)部狀態(tài)的選擇后，細(xì)胞內(nèi)部的信息素按下列公式進(jìn)行更新調(diào)整：

為了改善算法的全局收斂性，將信息素設(shè)置了上、下界，若信息素更新之后大于τmax，則將其置為τmax，反之將其置為τmin。

2 Bug－BACO算法求解組卷問題

2.1 組卷問題數(shù)學(xué)模型描述

智能組卷指計(jì)算機(jī)按照用戶輸入的要求，自動(dòng)抽取滿足用戶需求的一套試卷的過程。試卷中的每一道題目，由n維向量來描述（ai1，ai2，ai3，ai4，ai5，ai6…，ain），其中，ai1為第i題的題型；ai2為第i題的題分；ai3為題目難度；ai4為教學(xué)要求；ai5為知識(shí)單元；ai6為估時(shí)；…。一份試卷就決定一個(gè)m×n矩陣Sg＝（aij）n×m，其中，m 是試卷所含的題目數(shù)，則組卷的數(shù)學(xué)模型可描述如下［6］：

表1 Bug－BACO算法求解組卷問題試驗(yàn)結(jié)果表

2.2 Bug－BACO算法求解組卷問題性能分析

算法執(zhí)行時(shí)間需通過依據(jù)該算法編制的程序在計(jì)算機(jī)上運(yùn)行時(shí)所消耗的時(shí)間來度量，而度量一個(gè)程序的執(zhí)行時(shí)間通常有事前統(tǒng)計(jì)法和事后統(tǒng)計(jì)法。筆者使用事后統(tǒng)計(jì)方法中的cl ock／CLOCKS＿PER＿SEC，且所有程序均在3.0 GHZ、3.25 GB內(nèi)存的計(jì)算機(jī)上運(yùn)行。題庫(kù)規(guī)模為500（題型為填空題、選擇題、判斷題、改錯(cuò)題和編程題，每種題型各100道），卷面總分為100，時(shí)間100 min，試卷難度0.6，教學(xué)要求分值分布為（識(shí)記10分、理解35分、綜合35分、應(yīng)用20分），知識(shí)單元共10個(gè)，其相應(yīng)的知識(shí)分值分布為（10分、4分、10分、10分、14分、8分、12分、8分、10分、14分），試卷中各種題型要求的個(gè)數(shù)分別為：填空題10道、選擇題10道、編程題2道、改錯(cuò)題5道、判斷題5道。假設(shè)種群規(guī)模m＝30，ρ＝0.95，Pp＝0.5，每隔10代運(yùn)行10次，求解平均最優(yōu)值及平均運(yùn)行時(shí)間（以毫秒ms為計(jì)量單位）如表1所示。

由表1可知，利用Bug－BACO算法雖然能在多項(xiàng)式時(shí)間內(nèi)逃離局部最優(yōu)的陷阱并得到問題的最優(yōu)滿意解，但是實(shí)際運(yùn)行算法得到平均最優(yōu)值19.5547的時(shí)間為373837.2 ms，這在實(shí)際應(yīng)用中用戶是無(wú)法忍受的。因此，降低算法的運(yùn)行時(shí)間成為首要解決的關(guān)鍵問題。

3 Bug－PBACO算法

3.1 Bug－PBACO算法模型

圖3 Bug－BACO算法基本模型

并行策略的選擇對(duì)蟻群算法的并行實(shí)現(xiàn)至關(guān)重要。目前蟻群算法的并行策略有如下5種［7］，即并行獨(dú)立蟻群、并行交互蟻群、并行螞蟻、解決方案元素的并行評(píng)估以及螞蟻和解決方案元素的并行結(jié)合。根據(jù)研究需要，筆者采用并行螞蟻的并行策略。假設(shè)并行機(jī)群中，處理器的數(shù)目為n，種群規(guī)模為m，細(xì)胞狀態(tài)集合Q＝｛0，1｝，Pp為預(yù)先設(shè)定的一個(gè)概率。初始時(shí)刻，主處理機(jī)將原始螞蟻群體平分為n個(gè)子種群，每個(gè)子種群的規(guī)模為m／n，將n個(gè)子種群發(fā)送到n個(gè)處理機(jī)中，各處理機(jī)獨(dú)立運(yùn)行Bug人工生命模型二元蟻群優(yōu)化算法，并將各子種群的最優(yōu)個(gè)體適應(yīng)值發(fā)送給主處理機(jī)，主處理機(jī)收集整理并得出全局最優(yōu)解（見圖3）。

3.2 Bug－PBACO算法求解組卷問題計(jì)算時(shí)間分析

假設(shè)并行群集系統(tǒng)中共用m只螞蟻，問題的規(guī)模為題庫(kù)的規(guī)模lc·vm（其中，vm為題型數(shù)目；lc為題庫(kù)中每種題型的個(gè)數(shù)），并行機(jī)群中處理機(jī)的個(gè)數(shù)為n，且Bug－BACO算法和Bug－PBACO算法都迭代了相同的次數(shù)Nc，所需要的時(shí)間為Times（m，Nc），那么針對(duì)Bug－PBACO算法，每個(gè)處理機(jī)上的計(jì)算時(shí)間為Times（m，Nc）／n，因各處理機(jī)獨(dú)立并行地工作，不進(jìn)行信息的交換，故迭代次的Bug－PBACO算法所花費(fèi)的時(shí)間為Time（n）＝Times（m，Nc）。

設(shè)ts為算法啟動(dòng)時(shí)間，tw為傳輸每個(gè)字節(jié)的時(shí)間，P為傳輸?shù)男虐L(zhǎng)度，則進(jìn)行一次群集通信所需要的時(shí)間為（ts＋P·tw）·log n，因在Bug－PBACO算法中只有2次群集通信，即初始時(shí)刻主處理機(jī)向各子種群散發(fā)信息素初始矩陣以及結(jié)束時(shí)主處理機(jī)收集各子種群的最優(yōu)適應(yīng)值，假設(shè)個(gè)體最優(yōu)適應(yīng)值所占的字節(jié)為2，共有（lc·vm·2＋2）字節(jié)，那么一次迭代的時(shí)間為Tc＝［2·ts＋（lc·vm·tw）］·log n，由此，整個(gè)Bug－PBACO算法運(yùn)行的時(shí)間為：

3.3 處理機(jī)數(shù)目的選擇及算法的加速比

式（2）反映了Bug－PBACO算法的并行計(jì)算時(shí)間與處理機(jī)數(shù)目之間的函數(shù)關(guān)系，由此可以通過對(duì)Time（n）關(guān)于變量n求導(dǎo)來求解算法應(yīng)該選擇最優(yōu)處理機(jī)的個(gè)數(shù)，從而使得計(jì)算時(shí)間最短。

令Time′（n）＝0，即：

則算法的加速比：

因Bug－BACO算法求解組卷問題的時(shí)間復(fù)雜度為O（Nc·m·lc·vm），帶入式（5）中，則有：

由式（5）可知，隨著處理機(jī)數(shù)目的增加，加速比呈遞增趨勢(shì)，算法的效率反而減小。

4 仿真試驗(yàn)

題庫(kù)規(guī)模為500，計(jì)算機(jī)配置時(shí)節(jié)點(diǎn)之間通過以太網(wǎng)互連，每個(gè)節(jié)點(diǎn)均安裝windows操作系統(tǒng)及MPI并行函數(shù)庫(kù)，采用C語(yǔ)言綁定MPI函數(shù)庫(kù)進(jìn)行測(cè)試，相關(guān)配置信息可參考文獻(xiàn)［8］。

試驗(yàn)中，處理機(jī)數(shù)目n＝4，每個(gè)處理機(jī)上的螞蟻數(shù)目為30，ρ＝0.95，Pp＝0.5，每隔10代運(yùn)行10次。

表2所示為運(yùn)行Bug－PBACO算法求解組卷問題的試驗(yàn)結(jié)果。從表2可以看出，對(duì)Bug－BACO算法實(shí)施并行化處理技術(shù)能有效地縮短算法的運(yùn)行時(shí)間，同時(shí)沒有降低算法的求解質(zhì)量。

表2 運(yùn)行Bug－PBACO求解組卷問題試驗(yàn)結(jié)果

5 結(jié) 語(yǔ)

Bug－BACO算法作為蟻群算法改進(jìn)的一種，對(duì)于中小規(guī)模的優(yōu)化應(yīng)用問題，一般能夠在許可的時(shí)間內(nèi)得到滿意解，而對(duì)于大規(guī)模的優(yōu)化應(yīng)用問題，如組卷問題在許可的時(shí)間內(nèi)則很難得到滿意解。利用蟻群算法固有的并行特性，將并行化處理技術(shù)與Bug－BACO算法相結(jié)合形成Bug－PBACO算法，其求解大規(guī)模優(yōu)化問題的能力明顯優(yōu)于Bug－BACO算法，這為提高二元蟻群優(yōu)化算法的執(zhí)行效率提供了一種新的作用機(jī)制。

［1］熊偉清，魏平 .二進(jìn)制蟻群進(jìn)化算法［J］.自動(dòng)化學(xué)報(bào)，2007，33（3）：259－264.

［2］熊偉清，魏平，趙杰煜 .傳遞信號(hào)的二元蟻群算法［J］.模式識(shí)別與人工智能，2007，20（1）：15－20.

［3］嚴(yán)彬，熊偉清，程美英，等 .帶擁塞控制的多種群二元蟻群算法［J］.控制理論與應(yīng)用，2009，26（4）：387－394.

［4］葉青，熊偉清，李綱 .多目標(biāo)優(yōu)化的多種群混合行為二元蟻群算法［J］.計(jì)算機(jī)工程與應(yīng)用.2011，47（17）：37－41.

［5］胡鋼，熊偉清，張翔，等 .可控搜索偏向的二元蟻群算法［J］.控制理論與應(yīng)用，2011，28（8）：1071－1080.

［6］程美英，熊偉清，魏平 .基于二元蟻群算法求解組卷問題［J］.計(jì)算機(jī)應(yīng)用研究，2008，25（9）：2637－3639.

［7］章春芳 .自適應(yīng)的并行蟻群算法及其應(yīng)用［D］.揚(yáng)州：揚(yáng)州大學(xué)，2006.

［8］胡珂 .基于MPI的并行蟻群算法研究［D］.昆明：昆明理工大學(xué)，2011.