基于蟻群優(yōu)化算法的屬性約簡方法

《基于蟻群優(yōu)化算法的屬性約簡方法》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、基于蟻群優(yōu)化算法的屬性約簡方法劉業(yè)政姜元春(合肥工業(yè)大學(xué)管理學(xué)院電子商務(wù)研究所合肥230009)摘要：為了獲得信息系統(tǒng)中條件屬性的最小約簡，本文將基于信息論的屬性重要度作為啟發(fā)信息引入蟻群算法，提出了一種基于蟻群算法的屬性約簡方法。首先分析了屬性約簡與TSP問題的差異，提出了屬性約簡的數(shù)學(xué)模型，在此基礎(chǔ)上對蟻群優(yōu)化算法中的啟發(fā)信息和信息素更新函數(shù)進(jìn)行重新定義，最后研究了屬性約簡中解的構(gòu)造過程。實(shí)驗(yàn)表明，本文方法能有效地對信息系統(tǒng)進(jìn)行最大程度的約簡。關(guān)鍵字：粗糙集；屬性約簡；蟻群優(yōu)化算法；信息論螞蟻k(k?1,2,?,m)在運(yùn)

2、動過程中，根據(jù)各條路徑k1引言上的信息量和啟發(fā)信息決定轉(zhuǎn)移方向，pij表示第t屬性約簡是粗糙集理論的核心內(nèi)容之一。由于代時(shí)螞蟻k由城市Ti轉(zhuǎn)移到城市Tj的概率屬性約簡可以刪除冗余信息，形成簡潔的規(guī)則庫，???(t)*??(t)ijij對人們的決策提供快速、準(zhǔn)確的支持，因此，屬性????Tj?allowedkpk????is(t)*?is(t)（1）?約簡成為粗糙集理論研究的熱點(diǎn)，并提出了許多有ij?Ts?allowedk效的方法。其中，文獻(xiàn)[3]提出了一種基于互信息??0else的知識相對約簡算法，文獻(xiàn)[4]提出了基于遺傳算

3、其中，tabuk用來記錄螞蟻k已路過的城市，并隨法的屬性約簡的方法，文獻(xiàn)[5,6]也在屬性約簡方面著進(jìn)化過程作動態(tài)調(diào)整。allowedk＝做了許多工作。然而，作為一類NP組合優(yōu)化難題，屬性約簡至今尚未找到高效、完備的解決方法。{T1,T2,?,Tn}?tabuk表示螞蟻k當(dāng)前可以選擇的蟻群優(yōu)化算法（ACO）是一種非常有效的全局城市集合。?ij是基于具體問題的啟發(fā)信息。在TSP尋優(yōu)的隨機(jī)搜索算法,具有并行性、魯棒性和全局問題中，??d(T,T)?1。?,?是信息素和啟發(fā)信ijij搜索等特點(diǎn)。近幾年來，蟻群優(yōu)化算法已經(jīng)被用來息對

4、螞蟻決策的影響權(quán)重。隨著時(shí)間的推移，以前求解二次分配問題等復(fù)雜組合優(yōu)化問題[7-9],取留下的信息素會慢慢地?fù)]發(fā)，如果參數(shù)1??表示得了很好的結(jié)果，顯示出蟻群優(yōu)化算法在求解組合信息素的揮發(fā)程度，則t?1代各路徑上的信息素按優(yōu)化問題方面的優(yōu)越性。式（2）進(jìn)行調(diào)整：受蟻群優(yōu)化算法成功解決眾多組合優(yōu)化難題?ij(t?1)???ij(t)???ij（2）的啟發(fā)，本文將從信息論角度定義的屬性重要度作m為啟發(fā)信息引入蟻群優(yōu)化算法，提出了一種基于蟻k群優(yōu)化算法的屬性約簡新方法，實(shí)驗(yàn)表明該方法適??ij????ij（3）k?1?合于求解大規(guī)

5、模數(shù)據(jù)集的屬性約簡問題。k其中，??ij表示路徑(Ti,Tj)上的信息素增量，??ij2蟻群優(yōu)化算法表示螞蟻k在周游過程中釋放在路徑(Ti,Tj)上的蟻群優(yōu)化算法是由意大利學(xué)者M(jìn)Dorigo等人信息素??Q若第k只螞蟻經(jīng)過路徑(T,T)提出的一種新型啟發(fā)式隨機(jī)優(yōu)化搜索模型[1,2]，其??k?Lij（4）ij?K思想是模擬蟻群的正反饋機(jī)制，通過個(gè)體之間的信??0else息交流與相互協(xié)作達(dá)到優(yōu)化的目的。本文以求解其中，Q為常數(shù)，Lk表示螞蟻k在本次周游中所TSP問題為例說明蟻群優(yōu)化算法的基本原理。走回路的長度。已知n個(gè)城市T?

6、(T1,T2,?,Tn)以及城市之間蟻群優(yōu)化算法進(jìn)化的過程為：m只螞蟻同時(shí)從的距離，TSP問題就是要尋找一條經(jīng)過每個(gè)城市僅m個(gè)不同城市出發(fā)，根據(jù)(1)選擇下一個(gè)旅行的城一次且最后回到出發(fā)點(diǎn)的最短路徑。設(shè)m為螞蟻的市，已去過的城市放入tabuk中，一次循環(huán)完成后，數(shù)量，?ij(t)表示第t代時(shí)路徑(Ti,Tj)上的信息量，由公式(2)，(3)，(4)更新每條路徑上的信息素，重初始時(shí)刻各條路徑上的信息量相等，?ij(0)為常數(shù)。復(fù)上述過程，直到終止條件成立。3基于蟻群優(yōu)化算法的屬性約簡?基金項(xiàng)目：國家自然科學(xué)基金(7047104

7、6)和教育部博士點(diǎn)基由于蟻群優(yōu)化算法在求解復(fù)雜組合優(yōu)化問題金(20040359004)所表現(xiàn)出的優(yōu)越性，本文將蟻群優(yōu)化算法應(yīng)用于屬相對決策屬性的重要度可以通過添加某個(gè)條件屬性約簡。但是，與TSP等組合優(yōu)化問題不同，屬性所引起的互信息的變化大小來衡量[3]：性約簡有其自身的特點(diǎn)，主要體現(xiàn)在三個(gè)方面。第SGF(a,R,D)?I(R?{a};D)?I(R;D)(7)一，在解的構(gòu)造過程中，每只螞蟻無需搜索所有的這一結(jié)果度量了屬性a的重要性，也就是說在已知屬性，只要搜索到的屬性子集構(gòu)成了一個(gè)約簡，螞R的情況下，SGF(a,R,D)的值

8、越大，屬性a對于蟻就可以結(jié)束本次搜索；第二，在屬性約簡問題的決策D就越重要?？尚薪庵?，屬性排列的順序并不重要。而在TSP本文將此結(jié)果引入蟻群優(yōu)化算法中，將向集合中，城市的排列順序?qū)β窂降馁|(zhì)量是非常關(guān)鍵的；kSP中添加屬性ci所引起的互信息的變化第三，由于信息系統(tǒng)的約簡不唯一，因此蟻群算法j