基于蟻群遺傳算法的屬性約簡(jiǎn)

夏先智，杜新宇，鄭揚(yáng)飛

(華北計(jì)算技術(shù)研究所公共安全信息化事業(yè)部，北京 100083)

0 引言

屬性約簡(jiǎn)是確定與給定問題最相關(guān)的屬性，去除不相關(guān)、冗余的屬性，從而減少數(shù)據(jù)的維度，降低相關(guān)算法的復(fù)雜度，從而提高數(shù)據(jù)處理的效率。目前，屬性約簡(jiǎn)已在數(shù)據(jù)挖掘、自然語言處理和機(jī)器學(xué)習(xí)等領(lǐng)域中得到很多研究者的關(guān)注。

Z.Pawlak提出的粗糙集理論[1-4]為屬性約簡(jiǎn)提供了理論基礎(chǔ)。人們期望從一個(gè)知識(shí)系統(tǒng)中的多個(gè)約簡(jiǎn)集中找到一個(gè)屬性最少且保證其正確率的最小約簡(jiǎn)，但求解最小約簡(jiǎn)已被證明是一個(gè)NP-Hard問題。

蟻群算法是模擬螞蟻群體覓食的仿生優(yōu)化算法，在求解組合優(yōu)化問題的方面表現(xiàn)了突出的適用特征，已經(jīng)成功地在大量領(lǐng)域獲得了應(yīng)用，如機(jī)器人系統(tǒng)、圖像處理、制造系統(tǒng)、車輛路徑系統(tǒng)、通信系統(tǒng)等領(lǐng)域。文獻(xiàn)[5-8]將蟻群優(yōu)化應(yīng)用于屬性約簡(jiǎn)問題，但均是針對(duì)蟻群算法的狀態(tài)轉(zhuǎn)移規(guī)則和信息素更新規(guī)則的調(diào)優(yōu)，沒有考慮到蟻群算法本身的缺點(diǎn):蟻群需要迭代多次獲取足夠的信息素濃度來選擇路徑，因此導(dǎo)致算法迭代次數(shù)多，收斂慢。

本文將復(fù)制、交叉、變異等遺傳算法因子引入到蟻群算法，改進(jìn)螞蟻尋解的過程，使得蟻群更快地?cái)U(kuò)算到全局問題空間，以提高算法的收斂速度和全局搜索能力。

1 相關(guān)理論

1.1 粗糙集相關(guān)概念[9-11]

定義1 假設(shè)S為待約簡(jiǎn)的知識(shí)系統(tǒng)，U為S中帶有屬性的對(duì)象集合，那么知識(shí)系統(tǒng)可以表示為S=(U，A，V，f)。其中A表示U中對(duì)象的屬性集合，用C表示條件屬性的集合，D表示決策屬性的集合，則有A=C∪D，C∩D=φ。V表示屬性約簡(jiǎn)后最優(yōu)解的屬性集合。f:U×A→V表示全部屬性到最優(yōu)解的屬性集合的映射，且有?x∈U，?a∈A，f(x，a)∈Va其中Va為屬性a的值域。

定義2 對(duì)于屬性集合P和Q，P?U，Q?U，定義Q對(duì)P的依賴度為:

其中，|U|表示U的屬性個(gè)數(shù);POSU(P，Q)表示Q的P正區(qū)域，0≤γp(Q)≤1。依賴度反應(yīng)了屬性之間的相關(guān)性，γp(Q)越大，則Q對(duì)P的依賴度就越高，Q的獨(dú)立度就越低，被約簡(jiǎn)的可能性就越高。

定義3 設(shè)屬性集合R?C，?a?C－R，定義a對(duì)于決策表屬性D的重要度為:

其中，γR(D)，γ(R∪{a})(D)分別為決策屬性D對(duì)屬性集合R和R∪{a}的依賴度。在R已知的情況下，SGF(a，R，D)越大，屬性a對(duì)于決策屬性D就越重要。

定義4 設(shè)R為條件屬性集合C的一個(gè)約簡(jiǎn)，則它必須滿足條件:

其中，γR(D)、γC(D)、γR－r(D)分別表示決策屬性集合D對(duì)條件屬性集合R、C、R-r的依賴度。公式(3)等價(jià)于γC-R(D)=0，表示D不依賴于被約簡(jiǎn)的屬性集合C－R的任一屬性。由于C的約簡(jiǎn)并不唯一，所有約簡(jiǎn)的交集，即約簡(jiǎn)R必須包含的屬性集合稱為屬性核，記為Rcore，而具有最少屬性的約簡(jiǎn)，稱為最小約簡(jiǎn)，記為Rmin。

1.2 蟻群算法

蟻群算法(Ant Colony Optimization，ACO)，是由Marco Dorigo于1992年在他的博士論文中提出，是一種用來在圖中尋找優(yōu)化路徑的機(jī)率型算法，最初在求解旅行商問題取得較好的效果，是從螞蟻協(xié)作發(fā)現(xiàn)食物的過程中得到的靈感。大量螞蟻組成的群體集體行為表現(xiàn)出了正反饋的現(xiàn)象:越多的螞蟻從同一條路徑上走過，該路徑積累的分泌物濃度就越大，之后的螞蟻選擇該路徑的可能性就越大。螞蟻就是通過這種分泌物的指引，判斷前進(jìn)的方向，找到通向食物的最短路徑。在蟻群算法中，算法假設(shè)螞蟻會(huì)在每一條它走過的路徑上留下一些信息素，它也會(huì)根據(jù)路徑的信息素強(qiáng)度來選擇下一步路徑，選擇的概率取決于路徑上信息素的強(qiáng)度。蟻群算法是模仿真實(shí)蟻群的正反饋原理，模擬螞蟻的行為，從而實(shí)現(xiàn)尋優(yōu)。

2 蟻群遺傳算法求解屬性約簡(jiǎn)

2.1 約簡(jiǎn)目標(biāo)

根據(jù)定義4，屬性約簡(jiǎn)的結(jié)果R必須滿足:

而最小約簡(jiǎn)Rmin可以表示為:

在求解最小約簡(jiǎn)之前，首先要求解屬性核，屬性核Rcore為所有約簡(jiǎn)的交集，是每個(gè)約簡(jiǎn)不可缺少的部分，因此決策屬性集D，完全依賴于Rcore的任一屬性，即滿足:

因?yàn)閨U|為常數(shù)，本文直接比較正區(qū)域的基數(shù)大小來求解屬性核，其過程如下:

(1)計(jì)算正區(qū)域 POSU(C，D)以及所有的 POSU(C －{i}，D)，其中 i為條件屬性，i∈C;

(2)計(jì)算每一個(gè)條件屬性的正區(qū)域基數(shù)差值|POSU(C，D)|－ |POSU(C －{i}，D)|;

(3)將上一步結(jié)果排序，選擇差值為零的條件屬性組成屬性核Rcore。

另記B=C－Rcore表示可選條件屬性集，最小約簡(jiǎn)的條件公式(5)和公式(6)可以變換為:

因此，屬性約簡(jiǎn)問題可以定義為從可選條件屬性集B中，選擇滿足公式(9)的屬性集合，按照公式(8)求解最小約簡(jiǎn)R'min。

2.2 基本蟻群算法求解過程

基本蟻群算法模擬了蟻群協(xié)作覓食的過程。算法需要定義螞蟻信息素的表示方式和信息素的分泌和揮發(fā)規(guī)則，確定狀態(tài)轉(zhuǎn)移規(guī)則(螞蟻選擇路徑的方式)，設(shè)置迭代停止條件?；鞠伻核惴ǖ牧鞒踢^程是，算法首先按照一定規(guī)則初始化信息素和算法參數(shù)，然后開始迭代為每一只螞蟻構(gòu)造可行解。每次螞蟻從初始節(jié)點(diǎn)出發(fā)，開始迭代，然后可選節(jié)點(diǎn)的信息素信息，根據(jù)狀態(tài)轉(zhuǎn)移規(guī)則選擇下一個(gè)節(jié)點(diǎn)，直到最大迭代次數(shù)或得到可行解為止。

基本蟻群算法容易出現(xiàn)早熟、迭代次數(shù)過多的問題，因此引入遺傳算法中復(fù)制、交叉和變異等遺傳因子，改進(jìn)其狀態(tài)轉(zhuǎn)移過程，使得信息素能夠快速積累，且螞蟻不出現(xiàn)集群現(xiàn)象。

2.3 信息素的定義和更新規(guī)則

信息素定義和更新規(guī)則是蟻群算法的基礎(chǔ)，一個(gè)可選屬性的信息素濃度決定了它被螞蟻選擇的概率。因此，信息素更新規(guī)則的目標(biāo)是使螞蟻傾向于選擇最優(yōu)解中包含的屬性來構(gòu)建可行解。

假設(shè)任意兩個(gè)屬性i，j之間存在一虛擬的弧段，弧段記錄兩端屬性之間的信息素強(qiáng)度τij，顯然，可行解屬性之間的弧段實(shí)際上表示了螞蟻在屬性空間上所走的路徑，而屬性約簡(jiǎn)就是為了在這屬性空間中找到滿足公式(5)的最短路徑。信息素強(qiáng)度τij表示當(dāng)解集包含屬性i時(shí)，螞蟻選擇屬性j的期望。由于屬性之間沒有順序關(guān)系，因此τij與τji是等價(jià)的，在求解過程中，算法只需計(jì)算τij。而算法初始時(shí)刻，屬性之間的關(guān)系是未知的，因此算法初始化時(shí)，設(shè)置所有屬性之間的信息素強(qiáng)度τij(0)=τ0。

在找到可行解后，螞蟻會(huì)對(duì)信息素進(jìn)行更新。螞蟻已經(jīng)選擇的屬性之間信息素信息會(huì)增加，所有屬性之間的信息素隨時(shí)間流逝而減少。信息素衰減只與時(shí)間有關(guān)，而與螞蟻的行為無關(guān)。信息素的更新主要增加信息素濃度。

記Rmin1和Rmin2分別為當(dāng)前迭代為止，選出的最優(yōu)解和次優(yōu)解。螞蟻下次迭代應(yīng)該優(yōu)先在Rmin1和Rmin2區(qū)域?qū)ふ易顑?yōu)解。信息素更新規(guī)則將分別增強(qiáng)Rmin1和Rmin2中兩兩屬性節(jié)點(diǎn)間的信息素濃度。這樣，如果螞蟻構(gòu)造的新解中已經(jīng)包含了Rmin1或Rmin2中的部分屬性，那么螞蟻應(yīng)該優(yōu)先選擇Rmin1或Rmin2中的其它屬性。信息素更新規(guī)則定義為:

其中，p(0＜p＜1)表示信息素存留系數(shù)，pτij(t)是信息素衰減之后剩余的信息素濃度;Δτij(t)表示第t次迭代中屬性i和j之間信息素的增量，它反比于Rmin1或Rmin2中包含的屬性個(gè)數(shù)。顯然，最優(yōu)解Rmin1中屬性之間的信息素增量最多，次優(yōu)解Rmin2中的屬性之間的信息素增量比最優(yōu)解的少。其它屬性之間的信息素增加為零。

2.4 狀態(tài)轉(zhuǎn)移規(guī)則

狀態(tài)轉(zhuǎn)移規(guī)則決定了螞蟻如何選擇下一個(gè)屬性來構(gòu)造可行解，它直接影響了最優(yōu)解的質(zhì)量，也決定了算法的收斂速度和迭代次數(shù)。本文中，螞蟻是根據(jù)賭輪算法來選擇下一個(gè)屬性，狀態(tài)轉(zhuǎn)移規(guī)則需要確定每一個(gè)屬性被選擇的概率。

在屬性約簡(jiǎn)中，解集是屬性的集合，屬性順序是無關(guān)的，下一個(gè)屬性的選擇只能由已經(jīng)選擇的屬性來決定。設(shè)Rk為已選屬性的集合，k為迭代次數(shù)，j為待選屬性，則選擇j的概率為:

其中，集合Jk=C－Rk為第k次迭代后剩余可選條件屬性;ηij表示屬性j對(duì)屬性i的重要性，根據(jù)定義3，則有 ηij=SGF(j，{i}，D)，β(β≥0)表示重要性的權(quán)重。因此可以認(rèn)為是屬性i對(duì)屬性j的期望，表示集合 Rk對(duì)屬性 j的期望?！苖∈Jk表示集合R從J中選擇任一可選條件屬kk性的期望之和。P(j|Rk)表示了螞蟻在Rk為已選屬性的集合情況下，從剩余可選條件屬性中選擇屬性j的概率。

2.5 蟻群的復(fù)制、交叉和變異

蟻群算法是一種模仿了蟻群行為的算法。這種正反饋原理會(huì)導(dǎo)致螞蟻在求解過程中，向同一個(gè)解聚集，從而導(dǎo)致算法早熟，最優(yōu)解其實(shí)為局部最優(yōu)、因此，本文引入復(fù)制、交叉和變異這些遺傳因子來改進(jìn)蟻群算法的狀態(tài)轉(zhuǎn)移規(guī)則，旨在解決蟻群算法局部最優(yōu)、早熟、迭代次數(shù)過多的問題。

在遺傳算法中，復(fù)制的目標(biāo)是保留父代優(yōu)質(zhì)個(gè)體，因?yàn)樗赡芨咏肿顑?yōu)解。蟻群算法中，復(fù)制的目標(biāo)是保留交叉或變異操作要求保留的螞蟻個(gè)體。

為了防止螞蟻的聚集，通過引入交叉和變異，為蟻群增加一些“膽大”的螞蟻，它們?cè)诋?dāng)前最優(yōu)解區(qū)域之外構(gòu)造可行解，增加蟻群算法的全局搜索能力，避免局部最優(yōu)。

交叉操作是在螞蟻構(gòu)造可行解過程中進(jìn)行的，每當(dāng)所有未完成可行解構(gòu)造的螞蟻選擇了一個(gè)新的屬性，則計(jì)算決策屬性D對(duì)這些螞蟻解集的依賴度，選出依賴度最高的2個(gè)解集，記為R1和R2，按照交叉概率pc將其進(jìn)行交叉操作，交叉規(guī)則如下:

(1)首先分別從R1和R2中隨機(jī)選取k個(gè)條件屬性，各自構(gòu)成的集合記為S1和S2，其中k大于0，小于 min(|R1|，|R2|);

(2)將S2加入到最優(yōu)解R1中，然后刪除重復(fù)的屬性，得到解R3;

(3)同樣的方法，將S1加入到次優(yōu)解R2中，刪除出現(xiàn)重復(fù)的屬性，得到解R4;

(4)按照定義2計(jì)算決策屬性D對(duì)解R3和R4的依賴度，如果R(R3或R4)的依賴度大于R1或R2，則創(chuàng)建新的螞蟻，解集初始化為R，加入迭代。

變異操作是增加遺傳算法中個(gè)體的多樣性。遺傳算法中，變異一般是通過調(diào)整解編碼的順序完成。但是在屬性約簡(jiǎn)中，屬性之間的順序是沒有意義的，因此無法更改可行解中的屬性順序來完成變異操作。因此，在本算法中，可行解的變異操作過程為:信息素獎(jiǎng)勵(lì)之后，可行解R按照變異概率pm來決定是否進(jìn)行變異，如果需要變異，則從可行解中隨機(jī)選擇km個(gè)條件屬性刪除，然后復(fù)制該螞蟻，螞蟻進(jìn)入下一次迭代。

2.6 蟻群遺傳算法流程描述

(1)根據(jù)定義2，計(jì)算決策屬性集合D對(duì)條件屬性集合C的依賴度γC(D)。

(2)根據(jù)2.1節(jié)的算法求解核屬性集合Rcore，然后根據(jù)定義2計(jì)算D對(duì)屬性核的依賴度γRcore(D)。

(3)若γC(D)=γRcore(D)，取Rmin=Rcore，算法終止，否則轉(zhuǎn)步驟(4)，進(jìn)行蟻群遺傳算法求解屬性約簡(jiǎn)。

(4)蟻群算法進(jìn)行初始化，選取起始螞蟻數(shù)量為|C|，初始化所有屬性之間的信息素為τ0，計(jì)算任意兩屬性之間的重要度ηij，并設(shè)定最大迭代次數(shù)Tmax，當(dāng)前迭代次數(shù)t=0。

(5)開始第t次迭代，螞蟻開始構(gòu)造可行解，設(shè)螞蟻的解集合為Ri，i為螞蟻編號(hào)，將Ri初始化為屬性核Rcore。

(6)判斷Ri是否為可行解，若為可行解，保留該解，并標(biāo)記螞蟻個(gè)體為死亡狀態(tài)，轉(zhuǎn)步驟(8)，若不為可行解轉(zhuǎn)步驟(7)。

(7)根據(jù)狀態(tài)轉(zhuǎn)移規(guī)則計(jì)算Ri選擇C–Ri中每一個(gè)屬性的概率，并根據(jù)賭輪算法，選擇下一個(gè)屬性。計(jì)算D對(duì)每一只活著的螞蟻的解集Ri當(dāng)前的依賴度，選擇依賴度最高的2只螞蟻，復(fù)制，然后按照交叉概率pc進(jìn)行交叉操作。返回步驟(6)。

(8)當(dāng)所有螞蟻完成可行解的構(gòu)造時(shí)，按照變異概率pm對(duì)可行解進(jìn)行變異，然后復(fù)制變異成功的螞蟻，下一次迭代時(shí)，螞蟻繼續(xù)構(gòu)造可行解。

(9)從所有可行解中選出最優(yōu)解Rmin1和次優(yōu)解Rmin2，根據(jù)信息素更新規(guī)則，對(duì)屬性之間的信息素進(jìn)行更新。

(10)置 t=t+1，若 t＜ Tmax，則返回步驟(5)，否則取Rmin=Rmin1，終止算法。

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

為了驗(yàn)證算法的有效性，使用Python語言實(shí)現(xiàn)了文獻(xiàn)[12]的基本蟻群算法和本文的蟻群遺傳算法，并選擇了和文獻(xiàn)[12]相同的決策表對(duì)算法進(jìn)行測(cè)試，決策表數(shù)據(jù)可以從加州大學(xué)提供的機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)(UCI Machine Learning Repository)[13]下載到。

其中基本蟻群算法基本參數(shù)與文獻(xiàn)[12]一致，即 α =1.0、β =0.1、Nant=|C|、Tmax=250、τ0=20，遺傳操作中的參數(shù)設(shè)定為，交叉概率pc=0.667，變異概率 pm=0.015。

隨后重復(fù)對(duì)每個(gè)決策表進(jìn)行多次測(cè)試，記錄每次獲得最優(yōu)解的迭代次數(shù)和最小約簡(jiǎn)結(jié)果。如表1所示。

表1 蟻群遺傳和普通蟻群算法約簡(jiǎn)結(jié)果對(duì)比

本文算法和文獻(xiàn)[12]算法的主要差別在于，在狀態(tài)轉(zhuǎn)移之后，螞蟻需要復(fù)制和交叉，在螞蟻構(gòu)造可行解后，需要對(duì)可行解進(jìn)行變異，通過遺傳操作，擴(kuò)大螞蟻的搜索空間，優(yōu)化蟻群算法。

從表1的統(tǒng)計(jì)結(jié)果看，對(duì)于大部分決策表，本文算法獲得的結(jié)果和迭代次數(shù)都優(yōu)于文獻(xiàn)[12]。也有少部分表結(jié)果并不理想，如Letters和Derm，但其結(jié)果也比較接近。因此，可以說本文引入的遺傳算法因子對(duì)蟻群算法改進(jìn)是有效的，能夠提高蟻群優(yōu)化處理屬性約簡(jiǎn)問題的效果。

4 結(jié)束語

本文將遺傳算法中的遺傳因子引入到蟻群優(yōu)化，應(yīng)用于決策表屬性約簡(jiǎn)的問題。通過復(fù)制、交叉、變異遺傳因子，保留優(yōu)質(zhì)解，同時(shí)提高了螞蟻的全局搜索能力。最后在多個(gè)決策表上的測(cè)試表明，本文設(shè)計(jì)的算法提高優(yōu)化了蟻群算法全局搜索能力，減少了迭代次數(shù)，能夠有效地解決屬性約簡(jiǎn)問題。

[1]汪杭軍，張廣群，方陸明.粗糙集屬性約簡(jiǎn)算法的實(shí)現(xiàn)與應(yīng)用[J].計(jì)算機(jī)工程與設(shè)計(jì)，2007，28(4):777-779.

[2]于冰，閻保平.關(guān)于粗糙集屬性約簡(jiǎn)的進(jìn)化算法研究和應(yīng)用[J].微電子學(xué)與計(jì)算機(jī)，2005，22(3):189-194.

[3]瞿彬彬，盧炎生.基于粗糙集的快速屬性約簡(jiǎn)算法研究[J].計(jì)算機(jī)工程，2007，33(11):7-9.

[4]瞿彬彬，盧炎生.基于粗糙集的屬性約簡(jiǎn)算法研究[J].華中科技大學(xué)學(xué)報(bào):自然科學(xué)版，2005，33(8):30-33.

[5]袁浩.基于量子蟻群算法的粗糙集屬性約簡(jiǎn)方法[J].計(jì)算機(jī)工程與科學(xué)，2010，32(5):82-84.

[6]于洪，楊大春.基于蟻群優(yōu)化的多個(gè)屬性約簡(jiǎn)的求解方法[J].模式識(shí)別與人工智能，2011，24(2):176-184.

[7]姚躍華，洪杉.基于自適應(yīng)蟻群算法的粗糙集屬性約簡(jiǎn)[J].計(jì)算機(jī)工程，2011，37(3):198-200.

[8]任志剛，馮祖仁，柯良軍.蟻群優(yōu)化屬性約簡(jiǎn)算法[J].西安交通大學(xué)學(xué)報(bào)，2008，42(4):440-444.

[9]Pawlak Z.Rough sets and data analysis[C]//Proceedings of the 1996 Asian Fuzzy Systems Symposium.1996.

[10]Pawlak Z.Theorize with data using rough sets[C]//Proceedings of the 26th Annual International Computer Software and Applications Conference.2002:1125-1128

[11]Pawlak Z.Why rough sets?[C]//Proceedings of the 5th IEEE International Conference on Fuzzy Systems.1996:738-743.

[12]Jensen R，Shen Q.Finding rough set reducts with ant colony optimization[C]//Proceeding of the 2003 UK Workshop on Computational Intelligence.2003:15-22.

[13]UCI.UCI Machine Learning Repository[EB/OL].http://archive.ics.uci.edu/ml/，2012-08-15.

[14]Liu Hongjie，F(xiàn)eng Boqin ，Li Wei.An approach to minimum attribute reduction[C]//IEEE International Conference on Automation and Logistics.2008:1589-1593.

[15]Xu Zhangyan，Gu Dongyuan，Yang Bo.Attribute reduction algorithm based on genetic algorithm[C]//Proceeding of the 2nd International Conference on Intelligent Computation Technology and Automation.2009:169-172.