基于種間競(jìng)爭(zhēng)遺傳算法的改進(jìn)及其應(yīng)用

[摘 要] 在簡(jiǎn)單遺傳算法的基礎(chǔ)上，提出了一種基于種間競(jìng)爭(zhēng)的分類規(guī)則挖掘算法。通過(guò)改進(jìn)適應(yīng)度函數(shù)、雙群體結(jié)構(gòu)和遺傳算子等方法，將其應(yīng)用于收入分類的數(shù)據(jù)挖掘研究中，能夠高效地得到性能好的規(guī)則。

[關(guān)鍵詞] 遺傳算法 分類規(guī)則 種間競(jìng)爭(zhēng)

一、引言

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

二、種間競(jìng)爭(zhēng)算法的改進(jìn)

1.改進(jìn)思想

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

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

(3)自適應(yīng)變異算子：變異概率（Pm）能夠控制新基因?qū)肴后w的比例。Srinivas等提出變異概率自適應(yīng)改變的方法:當(dāng)種群各個(gè)個(gè)體適應(yīng)度差別小并趨于收斂時(shí)，增大Pm參數(shù)值；當(dāng)種群適應(yīng)度較為發(fā)散時(shí)，降低Pm參數(shù)，使個(gè)體趨于收斂。

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

2.改進(jìn)算法描述

Step1：求個(gè)體適應(yīng)值并降序排列并生成兩個(gè)初始群體。

Step2：兩個(gè)群體獨(dú)立執(zhí)行遺傳算子產(chǎn)生后代。

Step3：種間競(jìng)爭(zhēng)：競(jìng)爭(zhēng)頻率C，群間比較個(gè)數(shù)R。

Step3.1：若進(jìn)化代數(shù)能整除C進(jìn)入種間競(jìng)爭(zhēng)。

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

Step3.3：群間比較：群體1中最差的R個(gè)體同群體2中最好的R個(gè)體進(jìn)行比較，再將其中優(yōu)秀的個(gè)體都放到群體1中。

Step3.4:當(dāng)比較個(gè)數(shù)大于等于R或群體1中當(dāng)前個(gè)體適應(yīng)值已經(jīng)優(yōu)于群體2中的，則執(zhí)行Step4，否則循環(huán)執(zhí)行Step3.2～Step3.4。

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

三、改進(jìn)算法在收入分類規(guī)則挖掘中的應(yīng)用

1.系統(tǒng)運(yùn)行環(huán)境和測(cè)試用的數(shù)據(jù)

算法用Microsoft Visual C++ 6.0開發(fā)實(shí)現(xiàn)，并使用了UCI(University of California， Irvine)機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)中的收入統(tǒng)計(jì)(adult)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。此數(shù)據(jù)集用于統(tǒng)計(jì)收入“>50K”和“<=50K”的人口模式。

2.數(shù)據(jù)預(yù)處理

分別對(duì)數(shù)據(jù)進(jìn)行了空值、簡(jiǎn)化屬性、離散化等預(yù)處理。并隨機(jī)地將數(shù)據(jù)集分為訓(xùn)練集和測(cè)試集，訓(xùn)練集占三分之二，共32561條實(shí)例，測(cè)試集占三分之一，共16281條實(shí)例。

3.算法參數(shù)

種群大小為100，最大進(jìn)化代數(shù)為50，交叉概率PC為0.5，適應(yīng)度函數(shù)權(quán)值W1為0.7，競(jìng)爭(zhēng)頻率C為3，替換個(gè)數(shù)R為5。

4.實(shí)驗(yàn)結(jié)果

算法運(yùn)行30次，在測(cè)試集上準(zhǔn)確率最高的規(guī)則集如下。分別列出規(guī)則、訓(xùn)練集上的適應(yīng)度和測(cè)試集上的適應(yīng)度。

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

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

四、結(jié)束語(yǔ)

本文在簡(jiǎn)單遺傳算法的基礎(chǔ)上，引入并改進(jìn)了基于種間競(jìng)爭(zhēng)的分類規(guī)則挖掘算法。從而避免了種群內(nèi)部的“封閉競(jìng)爭(zhēng)”，提高了全局和局部搜索能力和進(jìn)化速度。但算法引入了一些新的參數(shù)，如何優(yōu)化設(shè)置這些參數(shù)還要做進(jìn)一步的研究。

參考文獻(xiàn):

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

[2]陳建能:基于種間競(jìng)爭(zhēng)的遺傳算法的改進(jìn).福建農(nóng)林大學(xué)學(xué)報(bào)，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]王小平 曹立明:遺傳算法－理論、應(yīng)用與軟件實(shí)現(xiàn). 西安:西安交通大學(xué)出版社，2002，74～76