基于種間競爭遺傳算法的改進及其應用

[摘 要] 在簡單遺傳算法的基礎上，提出了一種基于種間競爭的分類規則挖掘算法。通過改進適應度函數、雙群體結構和遺傳算子等方法，將其應用于收入分類的數據挖掘研究中，能夠高效地得到性能好的規則。

[關鍵詞] 遺傳算法 分類規則 種間競爭

一、引言

遺傳算法(Genetic Algorithm， GA)是由美國J.Holland教授于1975年在其論文“自然系統和人工系統的適配”中提出，并已得到了廣泛的應用，不過它仍然存在過早收斂和局部最優等問題。本文在引入“種間競爭”的思想的同時對其進行改進，在一定程度上解決了其“早熟”的問題。基于種間競爭的基本遺傳算法的計算步驟大部分與單種群基本遺傳算法一致，不同的是在產生初始群體時，不是產生1個群體，而是2個群體。在遺傳操作后插入群體之間的信息交換，即種間競爭。

二、種間競爭算法的改進

1.改進思想

(1)初始種群:個體按照適應值降序排列，將前三分之一放入群體1而剩余的三分之二放入群體2。群體1比群體2優秀，這樣就能較快地在群體1中挖掘到優秀的個體。

(2)群間比較和交換方法:相隔幾代相互替換個體一次，本文是用群體2中較優秀的個體去交換1中較差的個體，這樣既保持了群體1的多樣性又保持了其優秀性。

(3)自適應變異算子：變異概率（Pm）能夠控制新基因導入群體的比例。Srinivas等提出變異概率自適應改變的方法:當種群各個個體適應度差別小并趨于收斂時，增大Pm參數值；當種群適應度較為發散時，降低Pm參數，使個體趨于收斂。

(4)適應度函數：本文采用適應度函數 F=W1*Conf+W2*Sup（0w2，且W1+W2=1），即：F= W1*Conf+ (1-W1)*Sup。一般W1取0.7，這樣得到的規則正確性高，而且也不會產生大量的細節規則。

2.改進算法描述

Step1：求個體適應值并降序排列并生成兩個初始群體。

Step2：兩個群體獨立執行遺傳算子產生后代。

Step3：種間競爭：競爭頻率C，群間比較個數R。

Step3.1：若進化代數能整除C進入種間競爭。

Step3.2：排序：群體1升序，群體2降序。

Step3.3：群間比較：群體1中最差的R個體同群體2中最好的R個體進行比較，再將其中優秀的個體都放到群體1中。

Step3.4:當比較個數大于等于R或群體1中當前個體適應值已經優于群體2中的，則執行Step4，否則循環執行Step3.2～Step3.4。

Step4:兩群體分別進入下一代的基本遺傳操作。待算法完成后從群體1中簡化并打印分類規則。

三、改進算法在收入分類規則挖掘中的應用

1.系統運行環境和測試用的數據

算法用Microsoft Visual C++ 6.0開發實現，并使用了UCI(University of California， Irvine)機器學習數據庫中的收入統計(adult)數據集進行實驗。此數據集用于統計收入“>50K”和“<=50K”的人口模式。

2.數據預處理

分別對數據進行了空值、簡化屬性、離散化等預處理。并隨機地將數據集分為訓練集和測試集，訓練集占三分之二，共32561條實例，測試集占三分之一，共16281條實例。

3.算法參數

種群大小為100，最大進化代數為50，交叉概率PC為0.5，適應度函數權值W1為0.7，競爭頻率C為3，替換個數R為5。

4.實驗結果

算法運行30次，在測試集上準確率最高的規則集如下。分別列出規則、訓練集上的適應度和測試集上的適應度。

IF(marital-status=Never-married) THEN class=”<=50k” 0.952 0.951

IF(workclass=private)and (native-country=United-States) THEN class=”<=50k” 0.846 0.839

IF(workclass=private)and(sex=male) THEN class=”<=50k” 0.827 0.812

IF(marital-status=Married-civ-spouse)and(native-country=United-States) THEN class=”>50K”0.712 0.707

如果一條規則在測試集上的適應度與訓練集上適應度相差不超過0.1，就認為這條規則能夠很好地推廣到測試集上。列出的規則集大部分能很好地推廣到測試集上。關于“<=50K”的模式適應度較高，而關于“>50K”的模式適應度較低，通過觀察數據集可以看出，類“>50K”的實例在數據集中所占的比例較低，只占總數據集的23.93%。

四、結束語

本文在簡單遺傳算法的基礎上，引入并改進了基于種間競爭的分類規則挖掘算法。從而避免了種群內部的“封閉競爭”，提高了全局和局部搜索能力和進化速度。但算法引入了一些新的參數，如何優化設置這些參數還要做進一步的研究。

參考文獻:

[1]John H．Holland ，adaptation in natural and artificial systems[m]， University of Michigan press， 1975

[2]陳建能:基于種間競爭的遺傳算法的改進.福建農林大學學報，2003， 32(1):127～129

[3]M Srinivas， L Patnaik， Adaptive Probabilities of Crossover and Mutation in Genetic Algorithm IEEE Trans. On Systems， Man， and Cybernetics， 24， pp 656～666， 1994

[4]王小平 曹立明:遺傳算法－理論、應用與軟件實現. 西安:西安交通大學出版社，2002，74～76