戴上平，姬盈利，王華

1.華中師范大學(xué) 計(jì)算機(jī)科學(xué)系，武漢 430079

2.武漢大學(xué) 資源與環(huán)境科學(xué)學(xué)院，武漢 430079

利用多群交叉變異人工魚群算法生成分類規(guī)則

戴上平1，姬盈利1，王華2

1.華中師范大學(xué) 計(jì)算機(jī)科學(xué)系，武漢 430079

2.武漢大學(xué) 資源與環(huán)境科學(xué)學(xué)院，武漢 430079

1 引言

人工魚群算法是通過將需要解決的現(xiàn)實(shí)問題抽象為人工魚，模仿魚類底層的覓食、聚群、追尾等行為來(lái)實(shí)現(xiàn)尋優(yōu)的群體智能優(yōu)化算法[1-3]。該算法由于具有對(duì)初值、參數(shù)選擇要求不高，對(duì)啟發(fā)式函數(shù)不敏感，簡(jiǎn)單易實(shí)現(xiàn)，魯棒性強(qiáng)等優(yōu)點(diǎn)在函數(shù)優(yōu)化、參數(shù)估計(jì)、模式識(shí)別、神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化、分類預(yù)測(cè)等諸多領(lǐng)域得到了廣泛應(yīng)用[4-9]。

分類是數(shù)據(jù)挖掘領(lǐng)域研究的一個(gè)重要問題，其目的是通過分析數(shù)據(jù)集合，生成能夠?qū)?shù)據(jù)進(jìn)行區(qū)分的特征描述，從而對(duì)未知數(shù)據(jù)進(jìn)行分類預(yù)測(cè)，它對(duì)指導(dǎo)人們解決現(xiàn)實(shí)生活的很多問題有重要意義。常用的分類方法有統(tǒng)計(jì)機(jī)器學(xué)習(xí)、決策樹、神經(jīng)網(wǎng)絡(luò)、支持向量機(jī)、粗糙集、貝葉斯方法等[10-13]。

本文嘗試將人工魚群算法應(yīng)用于解決分類問題，在對(duì)基本人工魚群算法思想分析的基礎(chǔ)上，引入交叉變異策略，構(gòu)建了能夠生成連續(xù)空間變量分類規(guī)則的多群交叉變異人工魚群算法（Multi Artificial Fish Warm Algorithm with Cross and Mutation，MAFWA_CM）。與傳統(tǒng)魚群算法提取分類規(guī)則方法相比，本文利用多種群人工魚群中的每一魚群對(duì)應(yīng)于一條規(guī)則的提取，其收斂速度更快，求解精度更高。并且由于多群人工魚群在數(shù)據(jù)以及任務(wù)分割上的簡(jiǎn)便性，使其在將來(lái)算法的并行性實(shí)現(xiàn)上更為簡(jiǎn)單。最后，利用仿真實(shí)驗(yàn)證明了本文算法在連續(xù)變量空間內(nèi)生成分類規(guī)則的可行性。與基本人工魚群規(guī)則提取算法相比[14]，本文提出的MAFWA_CM算法具有更快的收斂速度并能獲得較高的規(guī)則精度。此外，實(shí)驗(yàn)還給出了本文算法與多群體微粒群規(guī)則提取算法的結(jié)果比較分析。

2 基本人工魚群算法

基本人工魚群算法原理可參考文獻(xiàn)[1-3]。本章重點(diǎn)介紹基本人工魚群的相關(guān)參數(shù)定義以及幾類基本行為。

2.1 人工魚參數(shù)意義

擁擠度（?）用來(lái)控制魚群個(gè)體之間不會(huì)過分擁擠；步長(zhǎng)（step）表示人工魚每次移動(dòng)的長(zhǎng)度；距離（d(i，j)）表示兩條人工魚個(gè)體之間的距離；感知范圍（visual）表示人工魚的可視范圍；試探次數(shù)（trynumber）表示人工魚每次選擇移動(dòng)方向的最大試探次數(shù)。

2.2 人工魚行為描述

假定人工魚當(dāng)前的狀態(tài)表示形式為Fish(X1,X2,…，Xn,C)，計(jì)算食物濃度的適應(yīng)值函數(shù)為y=f(x)，人工魚迭代選擇執(zhí)行覓食行為、聚群行為、追尾行為中能使自身狀態(tài)達(dá)到最優(yōu)的一種行為來(lái)執(zhí)行。在不斷地比較判斷更新自身狀態(tài)的過程中，使得人工魚的下一狀態(tài)最優(yōu)，每個(gè)人工魚個(gè)體通過這樣的方法局部尋優(yōu)，最終使全局最優(yōu)值在群體中突現(xiàn)出來(lái)。下面詳細(xì)描述幾種行為。

覓食行為：設(shè)定人工魚當(dāng)前狀態(tài)為xi，在其鄰域(d(i，j)＜visual)內(nèi)隨機(jī)選擇另外一個(gè)狀態(tài)xj，比較xi、xj處食物濃度的大小yi、yj，如果yi＜yj，則人工魚向xj處前進(jìn)一步；否則就再選擇一個(gè)新的狀態(tài)xj，重新進(jìn)行食物濃度大小的比較。如果試探了trynumber次仍然找不到食物濃度比較大的點(diǎn)，就隨機(jī)移動(dòng)一步。

聚群行為：設(shè)定人工魚當(dāng)前狀態(tài)為xi，在其鄰域(d(i，j)＜visual)內(nèi)搜索中心位置xc及伙伴數(shù)目nf，如果yc/nf＞?×yi，則向伙伴中心位置隨即移動(dòng)一個(gè)步長(zhǎng)；否則執(zhí)行覓食行為。

追尾行為：設(shè)定人工魚當(dāng)前狀態(tài)為xi，在其鄰域(d(i，j)＜visual)內(nèi)搜索食物濃度ymax最大的人工魚xmax，如果ymax/nf＞?×yi，則向xmax方向隨機(jī)移動(dòng)一個(gè)步長(zhǎng)；否則執(zhí)行覓食行為。

3 多群交叉變異人工魚群分類規(guī)則提取算法

多群人工魚群分類規(guī)則提取算法的特點(diǎn)是通過將數(shù)據(jù)與任務(wù)進(jìn)行分割，每一個(gè)魚群對(duì)應(yīng)負(fù)責(zé)某一類數(shù)據(jù)特征的提取任務(wù)，多個(gè)魚群并行計(jì)算，魚群之間無(wú)需進(jìn)行復(fù)雜的通信，在滿足一定規(guī)則精度或者達(dá)到預(yù)先設(shè)定的迭代次數(shù)時(shí)，再將各魚群提取的規(guī)則進(jìn)行綜合，便形成完整的置信度較高的用于分類預(yù)測(cè)的規(guī)則集合。在此算法基礎(chǔ)上引入交叉變異算子，即為多群交叉變異人工魚群分類規(guī)則提取算法。為實(shí)現(xiàn)多群交叉變異人工魚群分類規(guī)則提取算法，需明確分類規(guī)則表達(dá)形式及評(píng)價(jià)、人工魚構(gòu)造、交叉變異算子設(shè)計(jì)三類問題。

3.1 規(guī)則表達(dá)形式及評(píng)價(jià)

3.1.1 規(guī)則表示形式

一般分類的規(guī)則表示形式為：

式中，規(guī)則前件Ai代表數(shù)據(jù)集的特征屬性集合；規(guī)則后件Ci代表數(shù)據(jù)集類別；RP(Ai，Ci)代表隸屬規(guī)則的優(yōu)先級(jí)，用于解決某一個(gè)數(shù)據(jù)個(gè)體符合多項(xiàng)判別規(guī)則的問題。當(dāng)某一個(gè)實(shí)例的特征屬性集合與規(guī)則前件匹配，并且用該規(guī)則分類得出的實(shí)例類別與該實(shí)例所屬的類別一致時(shí)候，就說明這個(gè)實(shí)例被正確分類。

3.1.2 分類規(guī)則評(píng)價(jià)

要提取到最優(yōu)的規(guī)則，就要在訓(xùn)練過程中確定合適的適應(yīng)度函數(shù)對(duì)規(guī)則進(jìn)行評(píng)估。規(guī)則的支持度（support）和規(guī)則的可信度（confidence）是衡量規(guī)則好壞的兩個(gè)重要指標(biāo)，因此在確定適應(yīng)度函數(shù)之前引入這兩個(gè)指標(biāo)的相關(guān)定義：

定義1（支持度）對(duì)于規(guī)則if(Ai)then(Ci)，如果某種群中有s%的個(gè)體滿足規(guī)則即包含，Ai∪Ci則稱該規(guī)則的支持度為s%，記為support(Ai)即：

定義2（信任度）若規(guī)則if(Ai)then(Ci)的支持度為support(Ai)，則規(guī)則的信任度為support(Ai∪Ci)/support(Ai)記為：

定義1說明規(guī)則的支持度及規(guī)則的普遍性反映了正確分類的個(gè)體數(shù)目占種群中個(gè)體總數(shù)的比例。規(guī)則的支持度度越高表明該規(guī)則能夠?qū)?shí)例進(jìn)行正確分類的數(shù)目越多。定義2說明規(guī)則的信任度即規(guī)則的準(zhǔn)確度反映一條規(guī)則能將一個(gè)個(gè)體正確分類的概率。規(guī)則的信任度表明個(gè)體用該規(guī)則能夠正確分類的概率大。因此確定適應(yīng)度函數(shù)為：

式（3）通過支持度和置信度來(lái)綜合評(píng)估規(guī)則的質(zhì)量。式中a為支持度系數(shù)，值域?yàn)椋?，1），通過該系數(shù)保證生成的規(guī)則即能將大部分的樣本正確分類，同時(shí)也有較高的概率能將單個(gè)樣本正確分類，保證生成的規(guī)則向最優(yōu)的方向發(fā)展。

3.2 人工魚構(gòu)造

為將人工魚群用于連續(xù)空間變量的數(shù)據(jù)分類規(guī)則提取問題中，需要在基本人工魚算法的基礎(chǔ)上對(duì)人工魚編碼、人工魚距離、人工魚的鄰居及聚類中心進(jìn)行相關(guān)的定義。

3.2.1 人工魚編碼

本文算法中每條人工魚代表一條候選規(guī)則，在算法實(shí)現(xiàn)中，對(duì)人工魚的編碼需要能夠直觀的表達(dá)規(guī)則。因此用Fish(X1，X2，…，Xn，C)這種編碼形式來(lái)代表一條人工魚，其中前n維的具體編碼可以見表1，每一維均分別定義其特征上下界。第n+1維C代表類別屬性。將其解碼為規(guī)則表現(xiàn)形式：if X1_min＜X1＜X1_maxand X2_min＜X2＜X2_maxand…and Xn_min＜Xn＜Xn_maxthen C。

表1 人工魚編碼

3.2.2 人工魚的相關(guān)概念

在算法的迭代進(jìn)化過程中，人工魚距離、鄰域、聚群中心位置、食物濃度是幾類非常重要的概念，本文定義了這四類概念在分類規(guī)則提取中的具體實(shí)現(xiàn)方式。

（1）人工魚距離：人工魚的距離表示兩個(gè)規(guī)則之間的差異性，本文定義了基于歐幾里得距離的人工魚距離計(jì)算公式。例如，人工魚Fishi和Fishj之間的距離可通過下式來(lái)計(jì)算：

其中，n代表特征維數(shù)，Xik_max代表人工魚i的第k個(gè)屬性的上界，Xik_min代表人工魚i的第k個(gè)屬性的下界。

（2）鄰域：在人工魚距離的基礎(chǔ)上定義人工魚Fishi的鄰域?yàn)椋?/p>

其中，i′代表鄰域內(nèi)其他個(gè)體，φ代表鄰域距離，G代表整個(gè)魚群。

（3）中心位置：一個(gè)人工魚聚群的中心位置，在算法中分別取所有人工魚的每一維特征值上下界的平均值。

式中，m代表聚群中人工魚個(gè)體數(shù)。

（4）食物濃度：食物濃度就表示規(guī)則質(zhì)量，通過公式（3）進(jìn)行計(jì)算。

3.3 交叉變異算子設(shè)計(jì)

當(dāng)人工魚群算法迭代進(jìn)行到一定代數(shù)，算法容易陷入局部最優(yōu)解，為了保持種群的多樣性，更好地獲得全局極值，針對(duì)MAFWA_CM算法的具體應(yīng)用，設(shè)計(jì)了人工魚規(guī)則編碼的交叉變異算子。

（1）交叉算子

假定交叉概率為P_Cross，在一個(gè)種群中，隨機(jī)選擇P_Cross×m個(gè)人工魚個(gè)體兩兩執(zhí)行交叉操作。例如，選擇人工魚個(gè)體Fishi、Fishj，根據(jù)3.2.1小節(jié)人工魚的編碼規(guī)則，對(duì)兩個(gè)人工魚個(gè)體的前n維的上下界執(zhí)行如公式（7）所示的交叉操作：

其中，r為每一維隨機(jī)產(chǎn)生的范圍為[0，1]之間的數(shù)字。

（2）變異算子

假定變異概率為P_Mutation，在一個(gè)種群中，隨機(jī)選擇P_Mutation×m個(gè)人工魚個(gè)體執(zhí)行變異操作。將選擇出來(lái)的人工魚個(gè)體Fishi執(zhí)行如式（8）所示的高斯變異[15]：

其中，F(xiàn)ishi_與Fishi_是變異后第i維特征屬性的上下界值，N(0,1)為服從均值為0，方差為1的高斯分布隨機(jī)變量。

3.4 算法的整體描述

在上述定義的基礎(chǔ)上，本文算法的整體實(shí)現(xiàn)流程見圖1。

圖1 MAFWA_CM分類規(guī)則提取算法流程圖

步驟1通過數(shù)據(jù)采樣將數(shù)據(jù)集分為訓(xùn)練數(shù)據(jù)集和測(cè)試數(shù)據(jù)集。

步驟2設(shè)置魚群欲提取規(guī)則的類別及步長(zhǎng)、可視范圍等參數(shù)，根據(jù)3.2.1小節(jié)的人工魚編碼方式進(jìn)行種群的初始化。

步驟3對(duì)魚群，按公式（4）、（5）、（6）來(lái)進(jìn)行覓食、追尾、聚群等行為。

步驟4根據(jù)公式（3）計(jì)算每一人工魚的適應(yīng)值，對(duì)規(guī)則質(zhì)量進(jìn)行評(píng)估，將最優(yōu)個(gè)體放入公告板。

步驟5按公式（7）、（8）對(duì)種群執(zhí)行交叉變異操作。

步驟6判斷算法是否達(dá)到最大迭代次數(shù)或者連續(xù)幾代公告板未發(fā)生變化，則認(rèn)為達(dá)到算法終止條件執(zhí)行步驟7；否則執(zhí)行步驟3。

步驟7將生成的規(guī)則加入到規(guī)則集合中。

重復(fù)執(zhí)行步驟1到步驟7直到找到較優(yōu)規(guī)則。最后用測(cè)試數(shù)據(jù)集檢驗(yàn)規(guī)則集合精度，如果不滿足要求則重新進(jìn)行步驟1。

4 實(shí)驗(yàn)仿真及分析

4.1 實(shí)驗(yàn)數(shù)據(jù)集

為驗(yàn)證算法的性能，采取來(lái)自UCI機(jī)器學(xué)習(xí)知識(shí)庫(kù)中的Wine和Iris數(shù)據(jù)集來(lái)進(jìn)行測(cè)試實(shí)驗(yàn)。植物數(shù)據(jù)集Iris由分別屬于3種植物（setosa、versicolor、virginica）的150個(gè)樣本組成，每個(gè)樣本包含4個(gè)特征屬性：花瓣長(zhǎng)度、花瓣寬度、花萼長(zhǎng)度、花萼寬度。Wine數(shù)據(jù)集包含178個(gè)樣本，每個(gè)樣本包含13個(gè)特屬性，3個(gè)類別。如表2所示。

表2 UCI數(shù)據(jù)集

4.2 實(shí)驗(yàn)結(jié)果與分析

本文采用的是5折交叉驗(yàn)證法進(jìn)行實(shí)驗(yàn)，用n%5的策略把數(shù)據(jù)分成5份，其中n為數(shù)據(jù)的記錄號(hào)，即將行號(hào)除以5所得余數(shù)相等的數(shù)據(jù)歸為一個(gè)子集，設(shè)為D1，D2，…，D5，訓(xùn)練和測(cè)試輪流進(jìn)行5次，每一次訓(xùn)練都選用不同的數(shù)據(jù)集子作為測(cè)試集，其余的4個(gè)子集都用于訓(xùn)練集，取5次的平均值作為最終的實(shí)驗(yàn)結(jié)果。

本文算法的參數(shù)設(shè)置：最大迭代次數(shù)為50，單群人工魚個(gè)數(shù)30，可視范圍為2，步長(zhǎng)為0.5，最大嘗試次數(shù)是30，支持度系數(shù)為0.5，交叉概率0.3，變異概率0.01。其中，用本文提出算法對(duì)Iris數(shù)據(jù)集的提取規(guī)則結(jié)果如下：

為驗(yàn)證算法的改進(jìn)效果，本文將基本多群體人工魚群（MAFWA）分類規(guī)則提取算法與引入了交叉變異算子的MAFWA_CM算法進(jìn)行了性能的對(duì)比分析。兩類算法的主要參數(shù)設(shè)置一致，并且在相同數(shù)據(jù)集上進(jìn)行測(cè)試，將結(jié)果進(jìn)行比較。分類精度及計(jì)算時(shí)間結(jié)果如表3所示；以Iris數(shù)據(jù)集為例，繪制了兩類算法在類別規(guī)則提取時(shí)的適應(yīng)值收斂圖，如圖2所示。

表3 MAFWA與MAFWA_CM算法分類結(jié)果對(duì)比

如表3，從分類精度上來(lái)看，MAFWA_CM在兩類數(shù)據(jù)集上均優(yōu)于MAFWA算法，其主要原因是交叉變異算子的引入能夠有效提高種群多樣性，具有更好的全局最優(yōu)解的獲取機(jī)制。在計(jì)算時(shí)間方面，MAFWA_CM算法在Iris數(shù)據(jù)集上要略遜于MAFWA，其主要原因是由于MAFWA_CM的交叉變異操作增加了時(shí)間復(fù)雜度，算子的時(shí)間開銷超過了提前收斂（圖2所示）所節(jié)省的時(shí)間；而其在Wine數(shù)據(jù)集上的計(jì)算時(shí)間則略優(yōu)于MAFWA算法，說明在多維數(shù)據(jù)集上的快速收斂性能所節(jié)省的時(shí)間要多于交叉變異算子的時(shí)間開銷。

由圖2可以看出：在對(duì)規(guī)則1的生成中，本文提出的MAFWA_CM算法在第4代開始收斂，MAFWA算法則收斂于第6代；在規(guī)則2的生成中，雖然MAFWA_CM算法初始化時(shí)的群體最優(yōu)適應(yīng)值低于MAFWA算法，但是只經(jīng)過1代的進(jìn)化，最佳適應(yīng)值就明顯超過MAFWA算法，并且最終收斂于第7代，而MAFWA算法收斂于第9代，并且其最優(yōu)適應(yīng)值0.95略小于MAFWA_CM算法的0.97；在規(guī)則3的生成中，同樣MAFWA_CM算法初始化時(shí)的群體最優(yōu)適應(yīng)值低于MAFWA算法，但是經(jīng)過2代的進(jìn)化，最佳適應(yīng)值就明顯超過MAFWA算法，并且最終收斂于第8代，其最佳適應(yīng)值為0.94，略優(yōu)于MAFWA算法的0.92，MAFWA算法則在第10代開始收斂。該結(jié)果直觀地說明了MAFWA_CM算法的收斂性能優(yōu)于MAFWA算法，交叉變異算子的引入是有效的。

圖2 MAFWA與MAFWA_CM算法收斂對(duì)比圖

同時(shí)，本文還將分類結(jié)果與文獻(xiàn)[16]中的多群體微粒群算法（MPSO）進(jìn)行了比較，如表4所示。

表4 MAFWA、MAFWA_CM與MPSO算法分類結(jié)果對(duì)比

由表4可以看出，在分類精度上，Iris數(shù)據(jù)集上MAFWA算法的分類精度最低，但是較接近于MPSO算法。而MAFWA_CM算法的分類精度則要明顯優(yōu)于MPSO算法，在Wine數(shù)據(jù)集上，MAFWA算法的分類精度同樣最低，而MAFWA_CM算法的分類精度略高于MPSO算法，說明引入了交叉變異算子的MAFWA_CM算法在對(duì)多維特征的數(shù)據(jù)集的搜索最優(yōu)解的能力已達(dá)到MPSO算法的性能；在規(guī)則數(shù)目上，3種算法對(duì)Wine數(shù)據(jù)集均提取了4條規(guī)則，MAFWA與MAFWA_CM算法對(duì)Iris數(shù)據(jù)集提取了3條規(guī)則，而MPSO算法提取了5條規(guī)則，說明MAFWA與MAFWA_CM算法在低維數(shù)據(jù)集的學(xué)習(xí)能力上不遜于MPSO算法。

5 結(jié)論

實(shí)驗(yàn)結(jié)果表明，使用MAFWA_CM算法能夠以較快的收斂速率生成具有較高精度和較少數(shù)目的分類規(guī)則。與MAFWA算法相比，本文算法在收斂速度和分類精度上全面優(yōu)于MAFWA算法，但是在計(jì)算時(shí)間上，處理低維數(shù)據(jù)時(shí)由于交叉編譯操作的時(shí)間開銷超過了提前收斂所節(jié)省的時(shí)間，本文算法要遜于MAFWA算法；與MPSO算法相比，本文算法不僅在處理低維數(shù)據(jù)變量時(shí)規(guī)則的精度以及數(shù)目均明顯優(yōu)于MPSO算法，而且對(duì)多維特征數(shù)據(jù)集搜索全局最優(yōu)解的能力與MPSO算法也基本相當(dāng)。因此，本文MAFWA_CM算法在對(duì)連續(xù)變量空間分類規(guī)則提取問題中是可行并且有效的，尤其適用于解決高維連續(xù)空間變量的分類規(guī)則提取問題。

[1]李曉磊，邵之江，錢積新.一種基于動(dòng)物自治體的尋優(yōu)模式：魚群算法[J].系統(tǒng)工程理論與實(shí)踐，2002（11）：32-38.

[2]王聯(lián)國(guó)，洪毅，趙付青，等.一種改進(jìn)的人工魚群算法[J].計(jì)算機(jī)工程，2008，34（19）：192-194.

[3]Yazdani D，Toosi A N，Meybodi M R.Fuzzy adaptive artificial fish swarm algorithm[C]//Proceedings of the 23rd Australasian Joint Conference on Artificial Intelligence，Adelaide，Australia，2010：334-343.

[4]黃華娟，周永權(quán).改進(jìn)型人工魚群算法及復(fù)雜函數(shù)全局優(yōu)化方法[J].廣西師范大學(xué)學(xué)報(bào)，2008，26（1）：194-196.

[5]李曉磊，薛云燦，路飛，等.基于人工魚群算法的參數(shù)估計(jì)方法[J].山東大學(xué)學(xué)報(bào)，2004，34（3）：86-87.

[6]Shen W，Guo X，Wu C.Forecasting stock indices using radial basis function neural networks optimized by artificial fish swarm algorithm[J].Knowledge-Based Systems，2011，24（3）：378-385.

[7]師彪，李郁俠，于新花，等.彈性自適應(yīng)人工魚群-BP神經(jīng)網(wǎng)絡(luò)模型及在短期電價(jià)預(yù)測(cè)中的應(yīng)用[J].水力發(fā)電學(xué)報(bào)，2010，29（1）：107-113.

[8]Murak A K.Constrained parameter estimation with applications to blending operations[J].Journal of Process Control，2000，10（2）：195-202.

[9]劉雙印.免疫人工魚群神經(jīng)網(wǎng)絡(luò)的經(jīng)濟(jì)預(yù)測(cè)模型[J].計(jì)算機(jī)工程與應(yīng)用，2009，45（29）：226-229.

[10]謝娟英，劉芳，馮德民.基于GA與RST的分類規(guī)則挖掘算法[J].計(jì)算機(jī)科學(xué)，2006，33（11）：149-156.

[11]Tsumoto S.Automated extract ion of hierarchical decision rules fromclinicaldatabasesusingroughsetmodel[J].Expert Systems with Applications，2003，24（2）：189-197.

[12]Roubos J A，Setnes M，Abonyi J.Learning fuzzy classification rules from labeled data[J].Inf Sci，2003，150（1/2）：77-93.

[13]覃俊，康立山，陳毓屏.用于分類規(guī)則提取的演化算法分析與設(shè)計(jì)[J].計(jì)算機(jī)工程與應(yīng)用，2004，40（2）：13-15.

[14]陳俊清，朱文興.基于人工魚群算法的分類規(guī)則發(fā)現(xiàn)[J].福州大學(xué)學(xué)報(bào)，2007，35（1）：25-30.

[15]曲良東，何登旭.基于自適應(yīng)高斯變異的人工魚群算法[J].計(jì)算機(jī)工程，2009，35（15）.

[16]延麗平，曾建潮.利用多群體PSO算法生成分類規(guī)則[J].計(jì)算機(jī)工程與科學(xué)，2007，29（1）.

DAI Shangping1,JI Yingli1,WANG Hua2

1.Department of Computer Science,Central China Normal University,Wuhan 430079,China
2.School of Resource and Environment Science,Wuhan University,Wuhan 430079,China

The Multi Artificial Fish Warm Algorithm（MAFWA）based on the work principle of basic Artificial Fish Warm（AFW）is presented for extracting the classification rules of continuous variable.The code of artificial fish is designed in terms of the characteristics of extracting the classification rules.Then the fitness function to evaluate the quality of the regular rule is established and some formulas to calculate some key parameters for its application in extracting classification rules are defined. Meanwhile,in order to avoid the MAFWA falling in the local optima,the crossover operator and mutation operator of the AFW are designed based on the mutation and crossover idea of Genetic Algorithm（GA）.Then the MAFWA with Cross and Mutation（MAFWA_CM）is proposed.At last,the algorithm is tested on the Iris and Wine data sets.The experimental results show:（1）the algorithm can extract the classification rules with high precision in a short time.（2）When referred to the efficiency of the convergence and the precision of the rule,the MAFWA_CM is superior to the single AFW and is closer to the multi particle swarm algorithm.

Multi Artificial Fish Warm Algorithm（MAFWA）;Cross and Mutation（CM）;classification rule

在基本人工魚群算法的基礎(chǔ)之上構(gòu)建了用于解決連續(xù)變量空間分類規(guī)則提取的多群體人工魚群算法，根據(jù)分類規(guī)則提取問題的特性設(shè)計(jì)了人工魚的編碼規(guī)則，并在此編碼基礎(chǔ)上定義了進(jìn)行規(guī)則評(píng)價(jià)的適應(yīng)值函數(shù)以及相關(guān)狀態(tài)更新公式。為克服人工魚群算法易陷入局部最優(yōu)解的缺陷，引入了遺傳算法中的交叉變異思想，設(shè)計(jì)了基于人工魚的交叉及變異算子，提出了利用多種群交叉變異人工魚群算法生成分類規(guī)則的算法思想。利用Iris和Wine數(shù)據(jù)集作為測(cè)試數(shù)據(jù)，結(jié)果表明：（1）該算法能夠快速生成精度較高的分類規(guī)則；（2）在收斂效率及規(guī)則精度上全面優(yōu)于基本多群體人工魚群算法，并達(dá)到了多群體微粒群算法的性能水平。

多群體人工魚群；交叉變異；分類規(guī)則

A

TP301.6

10.3778/j.issn.1002-8331.1110-0657

DAI Shangping,JI Yingli,WANG Hua.Extracting classification rules by using multi artificial fish warm algorithm with cross and mutation.Computer Engineering and Applications,2013,49（13）：100-104.

國(guó)家高技術(shù)研究發(fā)展計(jì)劃（863）（No.2011AA120304）。

戴上平（1961—），男，博士，副教授，研究領(lǐng)域?yàn)槿斯ぶ悄?，?shù)據(jù)挖掘；姬盈利，碩士研究生，研究領(lǐng)域?yàn)槿斯ぶ悄埽瑪?shù)據(jù)挖掘；王華，博士研究生，研究領(lǐng)域?yàn)榭臻g數(shù)據(jù)挖掘，智能地理計(jì)算。E-mail：lucky201199@163.com

2011-11-03

2012-01-02

1002-8331（2013）13-0100-05

CNKI出版日期：2012-03-21http://www.cnki.net/kcms/detail/11.2127.TP.20120321.1738.053.html