基于多準則的鏈式智能體遺傳算法用于特征選擇

摘要：針對簡單遺傳算法用于特征選擇精度不高、過早收斂的問題，提出了一種新的遺傳算法——鏈式智能體遺傳算法（LAGA），并與多準則（MC）相結合，從而提出了基于多準則競爭策略的鏈式智能體遺傳算法（LAGA+MC）用于特征選擇。LAGA引入了鏈式智能體結構，智能體相互進行競爭選擇和自適應交叉，自身進行自適應變異，從而使得該算法能夠獲得更精確的搜索結果；MC通過對基于單準則進行選擇得到的特征子集進行特征位判斷，從而確定出最終特征子集，以達到更全面的評價選擇結果，獲得識別率更穩(wěn)定的特征子集。實驗結果表明，LAGA搜索精度更高，LAGA+MC獲得的特征子集分類準確率更高、更穩(wěn)定。

關鍵詞：多準則； 遺傳算法； 鏈式； 特征選擇； 智能體

中圖分類號：TP301文獻標志碼：A

文章編號：1001-3695(2008)05-1315-04

0引言

遺傳算法是一種基于生物進化理論的全局優(yōu)化搜索方法，它借用了生物遺傳學的觀點，通過自然選擇、遺傳、變異等作用機制實現(xiàn)各個個體的適應性的提高。特征選擇是一類典型的組合優(yōu)化問題。遺傳算法用于特征選擇有許多優(yōu)于傳統(tǒng)特征選擇方法的特點，具有全局尋優(yōu)能力，能搜索最優(yōu)的特征組合。目前遺傳算法在特征選擇方面得到了廣泛的應用，如文本識別、反映電力系統(tǒng)運行狀態(tài)的特征變量選擇、人臉識別特征選擇、指紋識別特征選擇、儲糧害蟲的形態(tài)特征提取等。

簡單的遺傳算法存在收斂速度慢、早熟收斂等缺陷，因此目前已經有很多文獻報道了關于遺傳算法的改進工作。文獻[1]用自適應交叉變異的方法(AGA)，根據(jù)每代個體適應度的情況來自適應地改變交叉和變異概率，較

好地保持了進化種群的多樣性。文獻[2]的改進遺傳算法采用基于海明距離的近親交叉回避策略(HMGA)，提高了遺傳操作的效率，加快了收斂速度；但它沒有考慮自適應改變變異概率以及選擇方面的改進，因此改進的效果是有限的。Zhong Wei－cai等人[3]針對超高維函數(shù)優(yōu)化問題，提出了智能體遺傳算法(MAGA)。其方法是將個體作為智能體設置在Lattice網格中，相鄰的智能體進行競爭選擇、交叉和變異。實驗表明，該算法函數(shù)優(yōu)化能力優(yōu)于其他幾個常用遺傳算法，但它是十進制編碼，未討論其用于特征選擇的研究，并且Lattice網格是否是最優(yōu)的局部環(huán)境尚需進一步研究。

目前，關于遺傳算法用于特征選擇的研究工作也有較多的報道。任江濤等人[4]提出基于相關性分析的特征過濾方法，其主要思想是基于特定的相關性定義，逐個度量單個特征與類別標簽的相關性，選出分類能力高的特征子集，在一定程度上消除與分類弱相關甚至無關的特征，實現(xiàn)降維。S.Doan等人[5]針對文本識別中的特征選擇問題，提出了多評價準則，提高了算法的穩(wěn)定性，但他未就遺傳算法用于特征選擇作進一步的研究和討論。

本文在上述兩方面工作的基礎上，提出了一種新的遺傳算法——鏈式競爭策略的智能體遺傳算法，并將其與多評價準則相結合，共同完成特征選擇，即LAGA+MC。LAGA引入了鏈式智能體結構，智能體鄰域降為兩個智能體，減小了計算代價，并減小了局部極值過渡擴散的可能性；同時引入了自適應交叉和變異操作，加快了搜索速度和精度。MC是基于多個評價準則來評價搜索結果的好壞，評價更全面。

1算法原理分析

基于遺傳算法的特征選擇主要分為以下三個方面：搜索策略、評價準則和終止條件。本文從三個方面考慮：引入了鏈式競爭策略，加快收斂速度；提出了多評價準則，從多個方面評價選擇結果的優(yōu)劣；設定了自適應停止條件，能得到較穩(wěn)定的搜索結果。

1．1鏈式競爭策略的智能體遺傳算法

1．1．1鏈式智能體結構

在本文中，一個智能體就表示一個個體L1，i，所有智能體均被放在一個規(guī)模為1×popsize的循環(huán)鏈上，每個個體占一個格點，且位置不能移動。由于智能體只有局部感知能力，它只能與周圍的智能體發(fā)生相互作用，這就構成了如圖1 所示的循環(huán)鏈式結構。

2實驗結果與分析

為了驗證本文算法的性能，筆者進行了基于MATLAB的實驗。實驗分為兩部分：a)通過與SGA、AGA、HMGA、MAGA比較，驗證LAGA對函數(shù)優(yōu)化的能力；b)通過與SGA、AGA、HMGA比較，驗證基于準則θ1的LAGA及LAGA+MC的特征選擇能力。

實驗平臺：基于Windows XP操作系統(tǒng)；CPU：2．66 GHz；內存：512 MB。

2．1比較LAGA與其他算法的函數(shù)優(yōu)化能力

平均最小值(MIN)，評估50次后的統(tǒng)計平均最小值；b)最優(yōu)解出現(xiàn)平均代數(shù)(G1)，評估50次后的最小值第一次出現(xiàn)的代數(shù)統(tǒng)計平均；c)平均遺傳代數(shù)(G2)，評估50次后的統(tǒng)計平均遺傳代數(shù)；d)平均執(zhí)行時間(T)，評估50次后的統(tǒng)計平均執(zhí)行時間。

測試結果如表1 所示。

從表3和4可以看出，用LAGA+MC進行特征選擇，得到的特征子集用于BP訓練、識別，減少了網絡達到預定目標的步數(shù)，加快了BP網絡的收斂速度；同時提高了兩類數(shù)據(jù)的識別正確率。

3結束語

關于遺傳算法用于特征選擇的研究，本文給出了結合多評價準則和鏈式智能體遺傳算法進行特征選擇的算法。通過典型復雜函數(shù)的優(yōu)化測試和標準數(shù)據(jù)集的特征選擇實驗表明，該遺傳算法的尋優(yōu)能力優(yōu)于文獻[1~3]，本文提出的特征選擇算法選擇的結果優(yōu)于使用文獻[1，2]的算法進行選擇的結果。通過該算法選擇得到的最優(yōu)特征子集具有較好的穩(wěn)定性和較高的識別準確率。

參考文獻：

[1]SRINIVAS M， PATNAIK L M. Adaptive probabilities of crossover and mutation in genetic algorithms[J]. IEEE Trans on Systems， Man and Cybernetics， 1994， 24(4):656-659.

[2]鞏敦衛(wèi)，孫曉燕，郭西進.一種新的優(yōu)勝劣汰遺傳算法[J].控制與決策，2002，17(6):908-909.

[3]ZHONG Wei－cai， LIU Jing， XUE Ming－zhi， et al. A multiagent genetic algorithm for global numerical optimization[J].IEEE Trans on Systems， Man and Cybernetics: Part B， 2004，34(2):1128－1141.

[4]任江濤，黃煥宇，孫婧昊，等.基于相關性分析及遺傳算法的高維數(shù)據(jù)特征選擇[J].計算機應用，2006，26(6):1403－1404.

[5]DOAN S， HORIGUCHI S. An efficient feature selection using multi－criteria in text categorization[J].IEEE Computer Society， 2004(11):86-91.

[6]MICHALEWICZ Z， FOGEL D B. How to solve it: modern heuristics[M].[S.l.]: Springer－Verlag， 2000.

[7]張文修，梁怡.遺傳算法的數(shù)學基礎[M].西安：西安交通大學出版社，2000.

[8]張葛祥，金煒東，胡來招.基于量子遺傳算法的特征選擇算法[J].控制理論與應用，2005，22(5):810-811.

[9]喬立巖，彭喜元，馬云彤. 基于遺傳算法和支持向量機的特征子集選擇方法[J].電子測量與儀器學報，2006，20(1):1-2.

[10]ZHU Fang－ming， GUAN S. Feature selection for modular GA－based classification[J].Appl Soft Comput， 2004，4(4):381-393.

[11]SHAH S C， KUSIAK A. Data mining and genetic algorithm based gene/SNP selection[J]. Artificial Intelligence in Medicine， 2004，31(3):183－196.

[12]HONG J H， CHO S B. Efficient huge－scale feature selection with speciated genetic algorithm[J].Pattern Recognition Letters，2006，27(2):143－150.

[13]郭昭輝，劉紹翰，武港山.基于神經網絡的中文文本分類中的特征選擇技術[J].計算機應用研究，2006，23(7):161－164.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”