混合自適應(yīng)性遺傳算法

白 鷺

(沈陽(yáng)大學(xué) 信息工程學(xué)院,遼寧 沈陽(yáng) 110044)

混合自適應(yīng)性遺傳算法

白 鷺

(沈陽(yáng)大學(xué) 信息工程學(xué)院,遼寧 沈陽(yáng) 110044)

設(shè)計(jì)了一種混合自適應(yīng)遺傳算法·將信息論中信息和熵的概念應(yīng)用在遺傳算法中,將遺傳算法中群體的實(shí)際熵值與期望熵值的比作為負(fù)反饋,使遺傳算法具有自適應(yīng)性·

遺傳算法;自適應(yīng)性;熵

1 遺傳算法分析

遺傳算法(Genetic Algorithm,GA)是基于自然選擇和遺傳變異的全局性隨機(jī)搜索算法,與傳統(tǒng)搜索算法相比,它具有不需要專(zhuān)業(yè)知識(shí)、隱含并行性、形式簡(jiǎn)單、魯棒性強(qiáng)和群體進(jìn)化的優(yōu)點(diǎn),已經(jīng)被成功應(yīng)用于人工智能、信息處理、組合優(yōu)化和管理科學(xué)等領(lǐng)域·

但是,從標(biāo)準(zhǔn)遺傳算法(Standard GA,SGA)的機(jī)理分析,其存在以下問(wèn)題:第一,交叉算子和變異算子都是在一定概率下隨機(jī)地、無(wú)指導(dǎo)地迭代搜索,因此它們?cè)跒槿后w提供進(jìn)化機(jī)會(huì)的同時(shí),也不可避免地產(chǎn)生退化的可能,影響了 GA的局部搜索能力;第二,基于適應(yīng)度的選擇壓力使群體得到進(jìn)化而收斂,但選擇壓力過(guò)大容易破壞個(gè)體多樣性而陷于早熟收斂,要保證算法趨于全局最優(yōu),必須在群體收斂性和個(gè)體多樣性之間取得平衡·源于以上兩個(gè)問(wèn)題,SGA的參數(shù)設(shè)置復(fù)雜,且缺乏統(tǒng)一的指導(dǎo)方針·大多數(shù)遺傳算法的應(yīng)用采用的是固定參數(shù)·參數(shù)值的選擇采用的是設(shè)置-測(cè)試的方法[1]·

2 遺傳算法的自適應(yīng)性分析

基于以上的分析,遺傳算法的性能由在搜索空間進(jìn)行的深度搜索(exploitation)和廣度搜索(exploration)的平衡決定[2]·本算法所采用的解決方法為:確定性適應(yīng)性(deterministic adaptation)和有適應(yīng)能力的適應(yīng)性(adaptive adap tation)相結(jié)合的混合適應(yīng)性(mixed adap tation)·確定性適應(yīng)性是指策略性參數(shù)的值由確定性規(guī)則來(lái)修改,通常采用根據(jù)遺傳代數(shù)來(lái)進(jìn)行改變的時(shí)變性策略·比如,隨著傳代數(shù)的增長(zhǎng),變異率逐漸下降,如式(1):

式中,t—當(dāng)前遺傳代數(shù);

G—最大代數(shù)·

隨著遺傳代數(shù)增長(zhǎng)為G,變異率會(huì)從0.5下降為0.2·式(1)由 Holland首先提出[3]·有適應(yīng)能力的適應(yīng)性是從進(jìn)化過(guò)程中獲取某種形式的反饋并用來(lái)確定策略性參數(shù)的改變方向和大小·下面為具體算法·

基本遺傳算法定義為一個(gè)8元組:

式中,C—編碼方式;

E—適應(yīng)度評(píng)價(jià)函數(shù);

P0—初始群體;

M—群體大小;

Pe—選擇算子;

Pc—交叉算子;

Pm—變異算子;

T—終止條件·

混合適應(yīng)性遺傳算法步驟:

①隨機(jī)生成初始化種群;

②評(píng)價(jià)種群中個(gè)體的適應(yīng)度;

③根據(jù)個(gè)體的適應(yīng)度進(jìn)行選擇、交叉、變異;

④評(píng)價(jià)種群中個(gè)體的適應(yīng)度;

⑤修改算法中的策略參數(shù)的方向、大小;

⑥測(cè)試終止條件,若“是”則轉(zhuǎn)至⑦,“否”則轉(zhuǎn)至③;

⑦結(jié)束·

由于參數(shù)適應(yīng)性遺傳算法各步驟與SGA基本相同,此處不再敘述·現(xiàn)將修改算法中的策略參數(shù)的方向、大小的算法介紹如下·

2.1 確定性適應(yīng)性

遺傳算法的參數(shù)中交叉概率Pc和變異概率Pm的選擇是影響遺傳算法行為和性能的關(guān)鍵,直接影響算法的收斂性·Pc越大,新個(gè)體產(chǎn)生的速度就越快·而Pc過(guò)大使得遺傳模式被破壞的可能性增大,使高適應(yīng)度的個(gè)體結(jié)構(gòu)被破壞的可能性增大;過(guò)小,會(huì)使搜索過(guò)于緩慢·pm過(guò)小,不易產(chǎn)生新的個(gè)體;Pm過(guò)大,遺傳算法就變成純粹的隨機(jī)搜索算法[4]·所以,為了滿足算法的需求,使Pc和Pm可以自適應(yīng)地改變·當(dāng)種群各個(gè)體適應(yīng)度趨于一致時(shí),使Pc和Pm增加,當(dāng)種群各個(gè)體適應(yīng)度分散時(shí),使Pc和Pm減小·Pc和Pm可以按式(3)、式(4)自適應(yīng)調(diào)整:

式中,fmax—群體中最大的適應(yīng)度值;

favg—群體的平均適應(yīng)度值;

f′—要交叉的兩個(gè)個(gè)體中較大的適應(yīng)度值;

f—要變異的適應(yīng)度值·

k1,k2,k3,k4取(0,1)區(qū)間的值·在一般的遺傳算法中,k1,k2,k3,k4是憑借經(jīng)驗(yàn)賦值的·

經(jīng)過(guò)以上調(diào)整,算法具有了確定性適應(yīng)性,但是仍然不能使其脫離經(jīng)驗(yàn)函數(shù)的束縛·下面介紹有適應(yīng)能力的適應(yīng)性·

2.2 有適應(yīng)能力的適應(yīng)性

將遺傳算法中的種群視為系統(tǒng),則此系統(tǒng)的個(gè)體編碼的信息量的總和是可以計(jì)算的·遺傳算法的收斂過(guò)程,是系統(tǒng)信息逐漸減少、系統(tǒng)熵值逐漸增大的過(guò)程·所以,將香農(nóng)(C.E.Shannon)于1948年提出的信息論中信息量(Information)和熵值(Entropy)的概念引入遺傳算法[5],將系統(tǒng)信息量的實(shí)際減小量與期望減小量之商作為系統(tǒng)的負(fù)反饋,用以修改遺傳算法的策略參數(shù)·

根據(jù)信息論,系統(tǒng)的信息量可以定義為

根據(jù)信息論的負(fù)熵原理,即信息量的增加量=熵S的減少=負(fù)熵N的增加·有了以上的定義,就可以計(jì)算系統(tǒng)的信息量關(guān)于遺傳算法進(jìn)化代數(shù)的函數(shù)關(guān)系式了·由于在遺傳算法中,信息量的減少和熵值的增加速度先慢后快,所以可以用指數(shù)函數(shù)近似模擬這一過(guò)程·由于算法中信息量的單位是bit,所以選擇以2為底的指數(shù)函數(shù)2bn,其中n為進(jìn)化的代數(shù),b為待定系數(shù)·設(shè)遺傳算法的最大代數(shù)為G,初始種群信息量為I0,則b的值可由式(6)估計(jì)出:

式(6)左邊為等比數(shù)列的和,所以有b是下列方程組的解:

其中,x是中間變量,G和I0是已知常數(shù)·解出b的值后,可以估計(jì)每步進(jìn)化的熵值為:

式中,i為遺傳算法進(jìn)化的代數(shù)·Si是第i代的熵值·若遺傳算法種群第i-1代,第i代的信息量為I′i-1,I′i,實(shí)際熵值為S′i=I′i-1-I′i·

其中,Pc和Pm是修正后的參數(shù),p′c和P′m是修正前的參數(shù)·由于參數(shù)先后經(jīng)歷了確定性適應(yīng)性修正和有適應(yīng)能力的適應(yīng)性修正,所以叫混合修正,算法叫混合適應(yīng)性遺傳算法(mixed adaptation GA)·

3 算法的應(yīng)用

將本算法應(yīng)用在數(shù)據(jù)挖掘中的數(shù)據(jù)聚類(lèi)上·由于在數(shù)據(jù)聚類(lèi)中,參數(shù)設(shè)置的問(wèn)題用傳統(tǒng)的算法難以確定,所以應(yīng)用混合適應(yīng)性遺傳算法計(jì)算聚類(lèi)數(shù),求出最優(yōu)解·

某市的環(huán)保監(jiān)測(cè)站于1982年在全市均勻布置了16個(gè)監(jiān)測(cè)點(diǎn),每日3次定時(shí)抽取大氣樣品,測(cè)量大氣中二氧化硫、氮氧化物和飄塵的含量·前后5天,每個(gè)取樣點(diǎn)每種污染元素實(shí)測(cè)15次,取15次實(shí)測(cè)值的平均值作為該取樣點(diǎn)的含量(數(shù)據(jù)見(jiàn)表1)·應(yīng)用本文提出的算法對(duì)數(shù)據(jù)進(jìn)行聚類(lèi)·數(shù)據(jù)來(lái)源見(jiàn)參考文獻(xiàn)[6]·

表1 原始數(shù)據(jù)表

首先按照本文中的公式對(duì)表1中的數(shù)據(jù)進(jìn)行預(yù)處理·數(shù)據(jù)經(jīng)預(yù)處理后到[0,1]區(qū)間內(nèi)后的數(shù)據(jù)見(jiàn)表2·

表2 預(yù)處理后的數(shù)據(jù)表

對(duì)數(shù)據(jù)的預(yù)處理包括數(shù)據(jù)的標(biāo)準(zhǔn)化和數(shù)據(jù)的規(guī)范化,標(biāo)準(zhǔn)化使數(shù)據(jù)擁有同一量綱,規(guī)范化使數(shù)據(jù)影射到[0,1]區(qū)間內(nèi)·經(jīng)過(guò)標(biāo)準(zhǔn)化和規(guī)范化的數(shù)據(jù)分布在邊長(zhǎng)為1的多維立方體中,對(duì)此多維立方體的劃分就是對(duì)數(shù)據(jù)的聚類(lèi)·

現(xiàn)假設(shè)每個(gè)數(shù)據(jù)是由d個(gè)標(biāo)量組成的向量,則每個(gè)數(shù)據(jù) Si(i=1,…,n,n表示待聚類(lèi)數(shù)據(jù)的個(gè)數(shù))可表示為

對(duì)數(shù)據(jù) Si進(jìn)行標(biāo)準(zhǔn)化,即對(duì)數(shù)據(jù) Si的每一個(gè)分量sj減去均值μj,除以標(biāo)準(zhǔn)差σj·

將式(2),式(3)表示成矢量的形式:

其中,μ=(μ1μ2…μd)T,σ=diag(1/σ11/σ2…1/σd)·

再將已經(jīng)標(biāo)準(zhǔn)化的數(shù)據(jù)進(jìn)行規(guī)范化,使所有數(shù)據(jù)落入[0,1]區(qū)間內(nèi)·規(guī)范方法為:將矩陣 B=(B1B2… Bn)T按列進(jìn)行分塊 B=(C1C2…Cd),每個(gè)列向量 Ci=(c1c2…cn)T(i=1,…,d),對(duì)每個(gè)分量進(jìn)行最大最小規(guī)范[3],成為列向量 Fi=(f1f2…fn)T·

經(jīng)過(guò)以上計(jì)算,矩陣 B變換為矩陣 P,將 P按行分塊 P=(p1p2… pn)T,pi(i=1,…,n)為完成預(yù)處理的數(shù)據(jù)·至此,數(shù)據(jù)的預(yù)處理完成,下面進(jìn)行數(shù)據(jù)聚類(lèi)·

應(yīng)用混合適應(yīng)性遺傳算法計(jì)算聚類(lèi)數(shù),使聚類(lèi)后各類(lèi)的計(jì)數(shù)測(cè)度的方差最大·

C—編碼方式:采用格雷編碼;

M—群體大小:16;

P0—初始群體;

E—適應(yīng)度評(píng)價(jià)函數(shù):各類(lèi)計(jì)數(shù)測(cè)度的方差;

Pc—選擇算子;

Pm—變異算子:

由于系統(tǒng)的初始信息量為I0=4×(-0.5lb0.5)=8,算法的最大代數(shù)G=200,將其帶入方程組(7)得b=0.001 5,則每步的期望熵值為Si=20.001 5i·

T-終止條件:編碼收斂于一個(gè)值,即群體內(nèi)的個(gè)體全部相同·或者算法進(jìn)化了200步·

經(jīng)計(jì)算機(jī)編程,實(shí)現(xiàn)以上算法,計(jì)算結(jié)果為4·則可將其分為4類(lèi),聚類(lèi)結(jié)果為:{X4,X5,X11,X12,X16},{X1,X2},{X3,X7,X10,X14,X15},{X6,X8,X9,X13}·

從結(jié)果分析,{X4,X5,X11,X12,X16}對(duì)應(yīng)的污染最輕,{X3,X7,X10,X14,X15}對(duì)應(yīng)的污染較輕,{X1,X2}對(duì)應(yīng)的污染較重,{X6,X8,X9,X13}對(duì)應(yīng)的污染最重·將聚類(lèi)結(jié)果在空間中表示,如圖1所示·

圖1 聚類(lèi)結(jié)果

4 結(jié) 論

混合適應(yīng)性遺傳算法通過(guò)確定性適應(yīng)性和有適應(yīng)能力的適應(yīng)性的混合使用,使遺傳算法具有自適應(yīng)性,經(jīng)檢驗(yàn)是可行的·

[1] 韋巍,何衍.智能控制基礎(chǔ)[M].北京:清華大學(xué)出版社,2008:279-297.

[2] 玄光男,程潤(rùn)偉.遺傳算法與工程優(yōu)化[M].于歆杰,周根貴,譯.北京:清華大學(xué)出版社,2004:13-14.

[3] Holland J.Adap tation in Natural and A rtificial Systems[M].Cambridge,MA:M IT Press,1992:73-77.

[4] Xie M C.Properties and characteristicsof genetic algorithm as a p roblem solving method[D].Fukui:Fukui University,1996:45-48.

[5] 姜丹.信息論與編碼[M].北京:中國(guó)科學(xué)技術(shù)出版社,2004:1-25.

[6] 高惠璇.應(yīng)用多元統(tǒng)計(jì)分析[M].北京:北京大學(xué)出版社,2005:214-215.

A M ixed Self-adaption Genetic Algorithm

BA IL u
(School of Information Engineering,Shenyang University,Shenyang 110044,China)

A m ixed self-adaption genetic algorithm is designed.Information and entropy of information theory are used in genetic algorithm.The quotient of real group entropy and expected group entropy forms negative feedback,and parameters of genetic algorithm are adjusted.Thus self-adaption of genetic algorithm is realized.

genetic algorithm;self-adaption;entropy

TN 911.1

A

1008-9225(2010)03-0014-04

2009-11-23

白 鷺(1982-),男,遼寧沈陽(yáng)人,沈陽(yáng)大學(xué)碩士研究生·

【責(zé)任編輯 李 艷】