基于種群年齡分層模型的線性遺傳編程算法

曹波， 蔣宗禮， 張津麗

(北京工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，北京 100124)

?

基于種群年齡分層模型的線性遺傳編程算法

曹波， 蔣宗禮， 張津麗

(北京工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，北京 100124)

針對常規(guī)線性遺傳編程算法易發(fā)生早熟收斂與膨脹的不足，提出了一種改進(jìn)的線性遺傳編程算法——種群年齡分層模型的線性遺傳編程算法。算法采用種群年齡分層模型對種群進(jìn)行分層提高種群的整體多樣性，并進(jìn)一步采用雙層錦標(biāo)賽提高各分層子種群局部的多樣性，以種群多樣性的提高減少算法早熟收斂的發(fā)生頻率；算法采用種群分層的方法限制長度較長個(gè)體的數(shù)量，從而減輕種群的膨脹程度。在5個(gè)符號回歸基準(zhǔn)函數(shù)進(jìn)行測試的結(jié)果表明，所提方法能夠有效減少早熟收斂的發(fā)生頻率，同時(shí)有效控制種群的膨脹程度。

早熟收斂；過擬合；多樣性；膨脹；雙層錦標(biāo)賽；線性遺傳編程算法；遺傳編程算法；種群年齡分層模型

線性遺傳編程算法(linear genetic programming， LGP)[1]是遺傳編程算法(genetic programming， GP)[2]的變種算法之一，該算法繼承了遺傳編程算法的高度并行處理能力、強(qiáng)魯棒性和全局搜索能力而被廣泛地應(yīng)用于諸多領(lǐng)域[3-5]，并與其他智能優(yōu)化算法[6]成為近期研究的熱點(diǎn)。

早熟收斂與膨脹是線性遺傳編程算法的兩大問題。種群進(jìn)化代數(shù)越多，膨脹程度越嚴(yán)重，計(jì)算適應(yīng)度所需代價(jià)也越多。一般通過增加種群多樣性減少早熟收斂的發(fā)生，但是算法需進(jìn)化更多代才能收斂，加重種群的膨脹程度。因此，在增加種群多樣性的過程中同時(shí)控制膨脹程度，對提高線性遺傳編程算法的整體性能有著重要意義。

在增加種群多樣性的研究問題上，主要有增加結(jié)構(gòu)多樣性和增加語義多樣性兩類方法。增加結(jié)構(gòu)多樣性是指增加種群在基因型方面的差異程度，此種方法首先定義結(jié)構(gòu)距離度量個(gè)體間的差異程度，并在進(jìn)化過程中增大個(gè)體間的結(jié)構(gòu)距離，提高種群的多樣性[7-9]。增加語義多樣性是指增加種群在表現(xiàn)型方面的差異程度，并在進(jìn)化過程中增大個(gè)體間的語義差異程度，以此提高種群的多樣性[10-12]。

在控制種群膨脹程度的研究問題上，主要有限制個(gè)體的最大長度[2]、簡約壓力項(xiàng)[13-14]、雙層錦標(biāo)賽和比例錦標(biāo)賽[15]等方法。這些方法主要通過限制個(gè)體的長度或使種群在搜索過程中偏向長度短的個(gè)體。

以上文獻(xiàn)僅從增加種群多樣性和控制種群膨脹的某一方面對線性遺傳編程算法進(jìn)行研究，但是增加種群的多樣性會加重種群的膨脹程度，而控制種群的膨脹程度并不能保證保持種群的多樣性。在線性遺傳編程算法領(lǐng)域，鮮有文獻(xiàn)對提高種群的多樣性和控制膨脹結(jié)合起來綜合研究。本文在優(yōu)化種群年齡分層模型[16-17]的基礎(chǔ)上，將該模型應(yīng)用于線性遺傳編程算法，用于減少算法早熟收斂的發(fā)生頻率，同時(shí)控制種群的膨脹程度。

1 線性遺傳編程算法及種群年齡分層模型

1.1 線性遺傳編程算法

線性遺傳編程算法通過錦標(biāo)賽選擇適應(yīng)度較大的個(gè)體參與復(fù)制、交叉和變異等遺傳操作，以適應(yīng)度為指引逐代搜索問題的最優(yōu)解。線性遺傳編程算法的個(gè)體采用程序指令序列的線性表示方式。設(shè)P(g)={X1，X2，…，XM}是規(guī)模為M的第g代種群，Xi=(xi1，xi2，…，xin)為種群的第i個(gè)個(gè)體，長度為n，xij表示第i個(gè)體的第j行指令，線性遺傳編程算法的個(gè)體表示如下：

void gp(doublef[2])

{

r[4]=r[2]/r[0];

r[2]=f[0]-r[4];

//r[1]=r[0]/f[1];

r[4]=r[2]/7;

r[0]=r[0]+r[4];

}

根據(jù)對輸出結(jié)果是否產(chǎn)生影響，指令分為有效指令和無效指令(示例中選定r[0]作為個(gè)體的輸出，第3行指令為無效指令)。有效指令中的運(yùn)算符構(gòu)成的序列稱為有效運(yùn)算符序列，表示為effOp(示例中，effOp=)。

1.2 種群年齡分層模型

種群年齡分層模型由分層規(guī)則、L0層(第0層)新個(gè)體生成規(guī)則、個(gè)體年齡增長規(guī)則和個(gè)體升遷規(guī)則構(gòu)成，分別定義如下：

分層規(guī)則：種群劃分為L0～Lmax層，每層的子種群規(guī)模為M。每層的最大年齡限制AgeLimiti的計(jì)算為：

AgeLimiti=AGEGAP×schemei

(1)

式中：AGEGAP用于控制各分層子種群的進(jìn)化，第AGEGAP×(i-1)代～第AGEGAP×i代(i≥1)，各分層的個(gè)體(包括超齡個(gè)體)在層內(nèi)進(jìn)化。schenmei表示元模式中第i層的值。Lmax層的個(gè)體沒有最大年齡限制。元模式如表1所示。例如，元模式采用多項(xiàng)式，AGEGAP=20，每層允許的最大年齡分別為20、 40、 80、 180、…

表1 分層元模式(AGEGAP=1)

L0層新個(gè)體生成規(guī)則：在第AGEGAP×i代(i≥0)，在L0層隨機(jī)生成新個(gè)體，用于填補(bǔ)原L0層中的個(gè)體升遷到L1層留下的空缺位置。

個(gè)體年齡增長規(guī)則：個(gè)體的年齡按照如下規(guī)則增長：1)L0層新生成的個(gè)體年齡為0；2)變異算子產(chǎn)生的子代個(gè)體年齡為父代個(gè)體年齡加1；3)交叉算子產(chǎn)生的子代個(gè)體年齡為父代個(gè)體年齡最大者的年齡加1；4)復(fù)制算子選擇的個(gè)體年齡加1。個(gè)體在同一代內(nèi)發(fā)生多次復(fù)制、交叉和變異等遺傳操作，年齡只增長一次。

個(gè)體升遷規(guī)則：第AGEGAP×i代(i≥0)，從Lmax-1～L0層，年齡超出本層允許最大年齡限制的個(gè)體將升遷到上一層，并替換上一層中適應(yīng)度比該個(gè)體小的個(gè)體，如果該個(gè)體比上一層中所有個(gè)體適應(yīng)度都小，則刪除該個(gè)體。

種群年齡分層模型限制年齡相仿的個(gè)體在同一層競爭進(jìn)化，因此該模型保護(hù)低年齡層的個(gè)體(適應(yīng)度通常較低)以免受到高年齡層個(gè)體(適應(yīng)度通常較高)的排擠，因此得以生存更長時(shí)間以搜索更廣的區(qū)域；同時(shí)，該模型在L0層源源不斷隨機(jī)生成的新個(gè)體，隨著年齡增長逐層升遷并替換高年齡層適應(yīng)度低的個(gè)體?？梢姡谠撃Ｐ椭?，種群不會由于出現(xiàn)超級個(gè)體而造成種群多樣性喪失，甚至發(fā)生早熟收斂。因此，該模型是提高種群多樣性的有效模型。

2 種群年齡分層模型在線性遺傳編程算法的應(yīng)用

在種群年齡分層模型中，同批次生成的個(gè)體從L0層升遷到Lmax層過程中年齡一般相仿，因此這些個(gè)體有較大概率在整個(gè)升遷過程中保持在同一層，如果同批次生成的個(gè)體在低層出現(xiàn)了早熟收斂，有比較大的概率在整個(gè)升遷過程中都維持早熟收斂的狀態(tài)，導(dǎo)致重復(fù)計(jì)算。為了提高各個(gè)分層子種群的多樣性，本文首先定義個(gè)體間的有效運(yùn)算符序列編輯距離，然后基于該編輯距離設(shè)計(jì)了雙層錦標(biāo)賽提高分層子種群的多樣性。

2.1 基于雙層錦標(biāo)賽的分層子種群多樣性策略

2.1.1 有效運(yùn)算符序列編輯距離及計(jì)算算法

定義1 有效運(yùn)算符序列編輯距離：設(shè)effOpi、effOpj分別為個(gè)體Xi和個(gè)體Xj的有效運(yùn)算符序列，將effOpi轉(zhuǎn)換成effOpj所需的刪除、插入和替換操作的集合稱為effOpi到effOpj的編輯路徑，而最短的編輯路徑稱為effOpi和effOpj的編輯距離。操作集合許可的編輯包括3種操作：將一個(gè)運(yùn)算符替換成另一個(gè)運(yùn)算符a→b，插入一個(gè)運(yùn)算符Λ→b，刪除一個(gè)運(yùn)算符a→Λ(a，b表示為一個(gè)運(yùn)算符，Λ表示空運(yùn)算符)。

上述所提的3種操作中，每一個(gè)操作都有相應(yīng)成本λ(·)，分別以成本函數(shù)λ(a→Λ)、λ(Λ→b)、λ(a→b)表示。假設(shè)將effOpi轉(zhuǎn)換成effOpj，需要經(jīng)過e1e2e3e4…en個(gè)操作，每個(gè)ei(i=1，2，…，n) 為一次操作。取E=e1e2e3e4…en為一連續(xù)的操作序列。因此，將effOpi經(jīng)由操作集合E轉(zhuǎn)換成effOpj總成本為λ(E)：

(2)

則個(gè)體Xi和個(gè)體Xj的有效運(yùn)算符編輯距離可以表示為

edit(Xi，Xj)=min{λ(E)|E是其中的一條路徑}

(3)

假設(shè)成本函數(shù)λ(·)=1，求解有效運(yùn)算符序列effOpi與effOpj的編輯距離的動態(tài)規(guī)劃算法如算法1所示：

算法1：

輸入: 有效運(yùn)算符序列effOpi及effOpj。

輸出: edit (i，j)，其中i=|effOpi|，j=|effOpj|。

1) ifi=0 andj=0

2) return 0;

3) ifi=0 andj!=0

4) return edit(i，j-1)+1;

5) ifi!=0 andj=0

6) return edit(i-1，j)+1;

7) else

8) return

min{edit(i-1，j)+1，edit(i，j-1)+1，edit(i-1，j-1)+f(i，j)};

其中，當(dāng)effOpi的第i個(gè)運(yùn)算符不等于effOpj的第j個(gè)運(yùn)算符時(shí)，f(i，j)=1；否則，f(i，j)=0。

2.1.2 雙層錦標(biāo)賽的分層子種群多樣性策略

種群年齡分層模型中各個(gè)分層子種群均采用標(biāo)準(zhǔn)的線性遺傳編程算法。分層子種群通過錦標(biāo)賽選擇策略選擇適應(yīng)度高的父代個(gè)體參與復(fù)制、交叉和變異等遺傳操作，從而產(chǎn)生子代個(gè)體。僅以適應(yīng)度單一標(biāo)準(zhǔn)確定優(yōu)勝個(gè)體容易導(dǎo)致種群在基因型上多樣性的迅速減少，因此有必要以適應(yīng)度和多樣性兩個(gè)標(biāo)準(zhǔn)確定優(yōu)勝個(gè)體，以在不改變進(jìn)化方向的前提下增加種群的多樣性，從而減少早熟收斂的發(fā)生。

本文采用雙層錦標(biāo)賽選擇策略融合適應(yīng)度和多樣性兩個(gè)選擇標(biāo)準(zhǔn)。在第1層中，每組錦標(biāo)賽選擇適應(yīng)度較高的個(gè)體進(jìn)入第2層；在第2層中，用算法1求出的有效運(yùn)算符編輯距離衡量個(gè)體間的差異程度，選擇有效運(yùn)算符編輯距離最大的兩個(gè)個(gè)體，作為最終的錦標(biāo)賽選擇結(jié)果。雙層錦標(biāo)賽選擇策略如圖1所示。在第1層中，隨機(jī)選擇6個(gè)個(gè)體，分成3組分別進(jìn)行錦標(biāo)賽，每組錦標(biāo)賽選擇適應(yīng)度較高的個(gè)體作為優(yōu)勝個(gè)體，因此第1層錦標(biāo)賽中共產(chǎn)生3個(gè)適應(yīng)度相對較高的個(gè)體進(jìn)入第2層錦標(biāo)賽。在第2層中，選擇有效運(yùn)算符編輯距離最大的兩個(gè)個(gè)體，作為整個(gè)錦標(biāo)賽的選擇結(jié)果。這樣，雙層錦標(biāo)賽選擇出在適應(yīng)度高的前提下(保證進(jìn)化方向)，差異程度盡量大(提高多樣性)的兩個(gè)個(gè)體。

圖1 雙層錦標(biāo)賽示意圖Fig.1 Two-layer tournament

2.2 種群年齡分層模型的線性遺傳編程的應(yīng)用及算法描述

本文將種群年齡分層模型應(yīng)用于線性遺傳編程算法，用于提高該算法的種群多樣性，同時(shí)控制種群的膨脹程度。對于種群的多樣性，通過限制年齡相仿的個(gè)體在同一層競爭進(jìn)化以提高種群整體多樣性；通過雙層錦標(biāo)賽提高分層子種群的局部多樣性，從而從整體和局部兩個(gè)維度提高種群的多樣性，減少早熟收斂的發(fā)生頻率。對于種群膨脹程度的控制，通過將種群按照年齡進(jìn)行分層，限制進(jìn)化代數(shù)比較大(年齡較大，長度一般比較長)的個(gè)體的數(shù)量，并且在第AGEGAP×i代(i≥0)在L0層隨機(jī)生成長度較短的新個(gè)體，新個(gè)體隨著年齡的增長逐層升遷并替換高年齡層(長度一般比較長)中適應(yīng)度低的個(gè)體，減輕種群的膨脹程度。

在基于種群年齡分層模型的線性遺傳編程算法中，通過AGEGAP控制進(jìn)化進(jìn)程。第AGEGAP×i代(i≥0)，將每層中的超齡個(gè)體升遷至上一層，并在L0層隨機(jī)生成新個(gè)體。第AGEGAP×(i-1)代～第AGEGAP×i代(i≥1)，各分層的個(gè)體在層內(nèi)執(zhí)行傳統(tǒng)的進(jìn)化，并且在遺傳算子中根據(jù)年齡增長規(guī)則增加個(gè)體的年齡。算法2是基于種群年齡分層模型的線性遺傳編程算法。

算法2：

1)設(shè)定算法參數(shù)，包括：

種群年齡分層模型的參數(shù)：分層層數(shù)Lmax，AGEGAP，分層元模式scheme，通過式(1)計(jì)算每層最大年齡限制AgeLimit；

線性遺傳編程算法參數(shù)：最大進(jìn)化代數(shù)GenMax，各分層子種群規(guī)模M，初始個(gè)體最大長度LenInitMax，個(gè)體最大長度LenIndMax，計(jì)算寄存器register個(gè)數(shù)，復(fù)制概率Pr，交叉概率Pc，變異概率Pm，函數(shù)集F，變量集T；

2)種群在GenMax代內(nèi)，執(zhí)行以下進(jìn)化過程：

①如果 generation%AGEGAP=0，執(zhí)行以下操作：

a)從Lmax-1層至L0層，將年齡超出最大年齡限制的個(gè)體升遷至上一層，并替換上一層中適應(yīng)度比自己小的個(gè)體，如果該個(gè)體的適應(yīng)度比上一層中所有個(gè)體的都小，則刪除該個(gè)體；

b)在L0層隨機(jī)生成新個(gè)體，新生成的個(gè)體年齡設(shè)置為0，用于填補(bǔ)原L0層中的個(gè)體升遷到L1層留下的空缺位置。

②如果 generation%AGEGAP！=0，對每一層的子種群分別執(zhí)行以下操作：

a)計(jì)算每個(gè)個(gè)體的適應(yīng)度；

b)用下述遺傳算子產(chǎn)生新個(gè)體：

復(fù)制：采用雙層錦標(biāo)賽，從父代種群中選擇M′×Pr個(gè)優(yōu)良個(gè)體進(jìn)行復(fù)制，加入子代種群，并刪除父代種群同等數(shù)量的劣質(zhì)個(gè)體，復(fù)制算子選擇的個(gè)體，如果該個(gè)體沒有參與變異和交叉操作，年齡不變，否則年齡+1；

交叉：執(zhí)行M′×Pc次交叉操作，每次交叉操作采用雙層錦標(biāo)賽選擇個(gè)體，從父代種群中選取兩個(gè)個(gè)體進(jìn)行交叉，交叉所產(chǎn)生新個(gè)體加入子代種群中，交叉所產(chǎn)生新個(gè)體的年齡為父代個(gè)體年齡最大者的年齡加1;

變異：執(zhí)行M′×Pm次變異操作，每次變異操作從父代種群中隨機(jī)選取一個(gè)個(gè)體，隨機(jī)改變該個(gè)體某一部分基因，將變異產(chǎn)生的新個(gè)體加入子代種群中，變異產(chǎn)生的新個(gè)體年齡為父代個(gè)體年齡加1。

3 實(shí)驗(yàn)及結(jié)果分析

3.1 測試問題及實(shí)驗(yàn)參數(shù)設(shè)置

為了驗(yàn)證所提方法的有效性，本文選用符號回歸問題作為測試問題，分別測試標(biāo)準(zhǔn)線性遺傳編程算法 (linear genetic programming，LGP)、基于種群年齡分層模型的線性遺傳編程算法 (age layered population structure-linear genetic programming， ALPS-LGP)以及在分層子種群中用雙層錦標(biāo)賽選擇策略的線性遺傳編程算法Two Layer (tournament-age layered population structure-linear genetic programming， 2LT-ALPS-LGP)在提高種群多樣性、控制種群膨脹程度以及在訓(xùn)練集和測試集的適應(yīng)度情況。

LGP、ALPS-LGP以及2LT-ALPS-LGP共同的參數(shù)取值相同，3種算法共同的參數(shù)設(shè)置如表2所示。LGP設(shè)置1 000個(gè)個(gè)體，ALPS-LGP和2LT-ALPS-LGP每層100個(gè)個(gè)體；ALPS-LGP與2LT-ALPS-LGP都分10層，AGEGAP取值10，分層元模式采用多項(xiàng)式。

表2 實(shí)驗(yàn)參數(shù)設(shè)置

測試函數(shù)為GP領(lǐng)域的基準(zhǔn)函數(shù)，所選用的測試函數(shù)以及相應(yīng)的訓(xùn)練集、測試集均采用文獻(xiàn)[18-19]的建議，如表3所示。

3.2 評測指標(biāo)

表3 符號回歸測試函數(shù)

注：U[a，b，c]表示在a與b之間的c個(gè)隨機(jī)樣本；E[a，b，c]表示從a開始直到b，每間隔c取一個(gè)樣本；訓(xùn)練集和測試集相互獨(dú)立。

3.3 實(shí)驗(yàn)結(jié)果及分析

在實(shí)驗(yàn)中，LGP、ALPS-LGP以及2LT-ALPS-LGP 3種算法對每個(gè)測試函數(shù)均獨(dú)立測試30次，種群多樣性和種群膨脹程度的結(jié)果為所有測試結(jié)果的平均值。

圖2比較了3種算法控制種群膨脹的效果。在所測試的函數(shù)中，應(yīng)用3種算法時(shí)，種群的膨脹程度均隨著進(jìn)化進(jìn)程逐漸增大。對于測試函數(shù)Keijzer-6、Korns-12和Vladislavleva-4，應(yīng)用LGP算法時(shí)，種群的膨脹程度接近個(gè)體最大長度，而應(yīng)用ALPS-LGP以及2LT-ALPS-LGP兩種算法時(shí)，種群的膨脹程度遠(yuǎn)小于應(yīng)用LGP算法時(shí)種群的膨脹程度。對于測試函數(shù)Nguyen-7和Pagie-1，應(yīng)用3種算法時(shí)種群的膨脹程度比較接近，并且遠(yuǎn)小于個(gè)體最大長度?？梢姡瑢τ贙eijzer-6、Korns-12和Vladislavleva-4這些復(fù)雜的測試函數(shù)，在搜索最優(yōu)解過程中，種群傾向于進(jìn)化得更加膨脹。此種情況下，應(yīng)用ALPS-LGP以及2LT-ALPS-LGP兩種算法能夠有效控制種群的膨脹程度。對于Nguyen-7和Pagie-1這些簡單的測試函數(shù)，應(yīng)用3種算法時(shí)，種群只需進(jìn)化少量的代數(shù)就可搜索到適應(yīng)度較高的解，因此種群的膨脹程度較輕。

圖2 種群膨脹程度控制效果Fig.2 The effects of population bloat control

圖3比較了3種算法控制種群多樣性的效果。在用ALPS-LGP算法優(yōu)于應(yīng)用LGP算法。對于測試函數(shù)Keijzer-6、Korns-12和Vladislavleva-4，應(yīng)用LGP算法時(shí)，種群的多樣性在進(jìn)化后期提高的幅度較小，而應(yīng)用ALPS-LGP以及2LT-ALPS-LGP兩種算法時(shí)，種群的多樣性提高的幅度較大。對于測試函數(shù)Nguyen-7和Pagie-1，應(yīng)用三種算法時(shí)種群的多樣性進(jìn)化少量的代數(shù)后就基本保持穩(wěn)定?？梢?，對于Keijzer-6、Korns-12和Vladislavleva-4這些復(fù)雜的測試函數(shù)，應(yīng)用ALPS-LGP以及2LT-ALPS-LGP兩種算法能夠有效提高種群的多樣性。對于Nguyen-7和Pagie-1這些簡單的測試函數(shù)，應(yīng)用3種算法時(shí)，種群均只需進(jìn)化比較少的代數(shù)就可以搜索到適應(yīng)度較高的解，種群多樣性均保持在比較低的水平。 由上述結(jié)果可以看出，雙層錦標(biāo)賽選擇策略和年齡分層的方法均有效提高了種群的多樣性。

圖3 種群多樣性提升效果Fig.3 The effects of population diversity improvement

表4描述3種算法在訓(xùn)練集和測試集的適應(yīng)度情況(函數(shù)名稱和算法名稱均進(jìn)行縮寫)。

表4 3種算法在訓(xùn)練集和測試集的適應(yīng)度

Table 4 The fitness in the training and testing sets of three algorithms

函數(shù)算法訓(xùn)練集測試集最小值平均值標(biāo)準(zhǔn)差最小值平均值標(biāo)準(zhǔn)差Kei6LGP0.100.150.030.350.450.08ALPS0.090.160.080.090.410.322TL0.080.100.010.090.270.18Kor12LGP0.891.000.071.071.030.90ALPS1.031.040.021.151.100.952TL0.060.070.030.900.950.03Vla4LGP0.190.190.000.190.190.00ALPS0.180.180.000.180.180.002TL0.170.180.010.170.180.01Ngu7LGP0.050.060.020.050.060.02ALPS0.050.060.020.050.060.022TL0.040.060.010.040.060.01Pag1LGP0.090.100.000.090.100.00ALPS0.070.080.010.070.080.012TL0.040.080.030.040.080.03

對所有測試函數(shù)，總體上，2LT-ALPS-LGP算法無論在訓(xùn)練集還是測試集上均表現(xiàn)最好，ALPS-LGP算法次之，LGP算法表現(xiàn)最差，說明種群年齡分層的方法以及雙層錦標(biāo)賽選擇策略提高種群多樣性有利于搜索全局最優(yōu)解。對比3種算法在所有測試函數(shù)的訓(xùn)練集和測試集的表現(xiàn)情況，2LT-ALPS-LGP算法和ALPS-LGP算法并沒有與LGP算法形成明顯的優(yōu)劣關(guān)系。可見同時(shí)提高種群的多樣性和控制種群膨脹程度對線性遺傳編程算法的泛化能力影響較小。

4 結(jié)論

1)對于復(fù)雜的測試函數(shù)，采用雙層錦標(biāo)賽選擇策略的種群年齡分層模型能夠明顯提高種群多樣性，同時(shí)控制種群的膨脹程度；

2)而對于簡單的測試函數(shù)雖有提高，但是不明顯，主要是由于種群只需進(jìn)化少量的代數(shù)就可以搜索到適應(yīng)度較高的解造成的。

3)訓(xùn)練集和測試集的適應(yīng)度測試情況表明種群年齡分層的方法以及雙層錦標(biāo)賽選擇策略提高種群多樣性有利于搜索全局最優(yōu)解，對算法的泛化能力影響較小。

[1]BRAMEIER M， BANZHAF W. Linear genetic programming[M]. New York Springer Science，Business Media， 2007: 1-8.

[2]KOZA J R. Genetic programming: on the programming of computers by means of natural selection[M]. Cambridge: MIT Press， 1992:17-63.

[3]GANDOMI A H，DANIAL M S，ALAVI A H， et al. Linear genetic programming for shear strength prediction of reinforced concrete beams without stirrups[J]. Applied soft computing， 2014， 19(2): 112-120.

[4]MEHR A D，KAHYA E， YERDELEN C. Linear genetic programming application for successive-station monthly streamflow prediction[J]. Computers and geosciences， 2014， 70(9): 63-72.

[5]TROIANO L， Birtolo C， ARMENISE R. Searching optimal menu layouts by linear genetic programming[J]. Journal of ambient intelligence and humanized computing， 2015:1-18.

[6]吳昌友.一種改進(jìn)的人工魚群優(yōu)化算法[J]. 智能系統(tǒng)學(xué)報(bào)，2015，10(3): 465-469. WU Changyou. An improved artificial fish swarm optimization algorithm[J]. CAAI transactions on intelligent systems， 2015，10(3): 465-469.

[7]BRAMEIER M， BANZHAF W. Explicit control of diversity and effective variation distance in linear genetic programming[C]//5th European Conference on Genetic Programming. Kinsale， Ireland， 2002: 3-5.

[8]GAUDESI M， SQUILLERO G， TONDA A. An efficient distance metric for linear genetic programming[C]//15th Annual Conference on Genetic and Evolutionary Computation. Amsterdam， The Netherlands， 2013: 6-10.

[9]NGUYEN Q U，XUAN X H， O′NEILL M， et al. An investigation of fitness sharing with semantic and syntactic distance metrics[J]. Lecture notes in computer science， 2012， 7244:109-120.

[10]TOMASSINI M，VANNESCHI L， COLLARD P，et al. A study of fitness distance correlation as a difficulty measure in genetic programming[J]. Evolutionary computation，2005， 13(2): 213-239.

[11]BEADLE L， JOHNSON C G. Semantically driven crossover in genetic programming[C]//IEEE World Congress on Computational Intelligence， 2008:111-116.

[12]BEADLE L， JOHNSON C G. Semantically driven mutation in genetic programming[C]//IEEE Congress on Evolutionary Computation， 2009: 1336-1342.

[13]ZHANG B T， HLENBEIN H. Balancing accuracy and parsimony in genetic programming[J]. Evolutionary computation， 1995， 3(1): 17-38.

[14]LUKE S， PANAIT L. A comparison of bloat control methods for genetic programming[J]. Evolutionary computation， 2006， 14(3): 309 -344.

[15]SOTTO L F D P， MELO V V D. Studying bloat control and maintenance of effective code in linear genetic programming for symbolic regression[J]. Neurocomputing， 2015: 1-15.

[16]HORNBY G S. ALPS: the age layered population structure for reducing the problem of premature convergence[C]// 8th Annual Conference on Genetic and Evolutionary Computation， Washington， USA， 2006: 815-822.

[17]HORNBY G S. A steady-state version of the age-layered population structure EA[M]. [S.l.]: Springer， 2010: 87-102.

[18]MCDERMOTT J， WHITE D R，LUKE S，et al. Genetic programming needs better benchmarks[C]//14th Annual Conference on Genetic and Evolutionary Computation. Pennsylvania， USA， 2012， 283(3): 791-798.

[19]WHITE D R，MCDERMOTT J， CASTELLI M，et al. Better GP benchmarks: community survey results and proposals[J]. Genetic programming and evolvable machines， 2013， 14(1): 3-29.

Linear genetic programming based on an age-layered population model

CAO Bo， JIANG Zongli， ZHANG Jinli

(College of Information， Beijing University of Technology， Beijing 100124， China)

To alleviate premature convergence and bloat in general linear genetic programming， a modified linear genetic programming method based on an age-layered population model is proposed. To alleviate premature optimization of the population， we first applied an age-layered population model to linear genetic programming to improve the integral population diversity. We then used a two-layer tournament to improve the sub-population diversity in each layer， improving the local population diversity and decreasing the occurrence rate of premature optimization by increasing the diversity of the population. To control the bloat effect of the population， the age-layered population model segregated individuals into different layers based on age， so the quantity of long-length individuals was limited. The experimental results on five symbolic regression benchmark functions show that the proposed method can improve population diversity to reduce premature convergence and effectively control bloat.

premature convergence; over-fitting; diversity; bloat; two-layer tournament; linear genetic programming; genetic programming; age-layered population model

2016-02-23.

日期：2017-03-10.

國家自然科學(xué)基金項(xiàng)目(61133003).

曹波(1980-)， 男， 博士研究生； 蔣宗禮(1956-)， 男，教授，博士生導(dǎo)師.

曹波，E-mail：caobo@emails.bjut.edu.cn.

10.11990/jheu.201602025

TP391

A

1006-7043(2017)04-0610-07

曹波，蔣宗禮，張津麗.基于種群年齡分層模型的線性遺傳編程算法[J]. 哈爾濱工程大學(xué)學(xué)報(bào)， 2017， 38(4): 610-616.

CAO Bo， JIANG Zongli， ZHANG Jinli. Linear genetic programming based on an age-layered population model [J]. Journal of Harbin Engineering University， 2017， 38(4): 610-616.

網(wǎng)絡(luò)出版地址：http://kns.cnki.net/kcms/detail/23.1390.u.20170310.1348.004.html