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

曹波， 蔣宗禮， 張津麗

(北京工業大學 計算機學院，北京 100124)

?

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

曹波， 蔣宗禮， 張津麗

(北京工業大學 計算機學院，北京 100124)

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

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

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

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

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

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

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

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

1.1 線性遺傳編程算法

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

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];

}

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

1.2 種群年齡分層模型

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

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

AgeLimiti=AGEGAP×schemei

(1)

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

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

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

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

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

種群年齡分層模型限制年齡相仿的個體在同一層競爭進化，因此該模型保護低年齡層的個體(適應度通常較低)以免受到高年齡層個體(適應度通常較高)的排擠，因此得以生存更長時間以搜索更廣的區域；同時，該模型在L0層源源不斷隨機生成的新個體，隨著年齡增長逐層升遷并替換高年齡層適應度低的個體。可見，在該模型中，種群不會由于出現超級個體而造成種群多樣性喪失，甚至發生早熟收斂。因此，該模型是提高種群多樣性的有效模型。

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

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

2.1 基于雙層錦標賽的分層子種群多樣性策略

2.1.1 有效運算符序列編輯距離及計算算法

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

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

(2)

則個體Xi和個體Xj的有效運算符編輯距離可以表示為

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

(3)

假設成本函數λ(·)=1，求解有效運算符序列effOpi與effOpj的編輯距離的動態規劃算法如算法1所示：

算法1：

輸入: 有效運算符序列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)};

其中，當effOpi的第i個運算符不等于effOpj的第j個運算符時，f(i，j)=1；否則，f(i，j)=0。

2.1.2 雙層錦標賽的分層子種群多樣性策略

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

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

圖1 雙層錦標賽示意圖Fig.1 Two-layer tournament

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

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

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

算法2：

1)設定算法參數，包括：

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

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

2)種群在GenMax代內，執行以下進化過程：

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

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

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

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

a)計算每個個體的適應度；

b)用下述遺傳算子產生新個體：

復制：采用雙層錦標賽，從父代種群中選擇M′×Pr個優良個體進行復制，加入子代種群，并刪除父代種群同等數量的劣質個體，復制算子選擇的個體，如果該個體沒有參與變異和交叉操作，年齡不變，否則年齡+1；

交叉：執行M′×Pc次交叉操作，每次交叉操作采用雙層錦標賽選擇個體，從父代種群中選取兩個個體進行交叉，交叉所產生新個體加入子代種群中，交叉所產生新個體的年齡為父代個體年齡最大者的年齡加1;

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

3 實驗及結果分析

3.1 測試問題及實驗參數設置

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

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

表2 實驗參數設置

測試函數為GP領域的基準函數，所選用的測試函數以及相應的訓練集、測試集均采用文獻[18-19]的建議，如表3所示。

3.2 評測指標

表3 符號回歸測試函數

注：U[a，b，c]表示在a與b之間的c個隨機樣本；E[a，b，c]表示從a開始直到b，每間隔c取一個樣本；訓練集和測試集相互獨立。

3.3 實驗結果及分析

在實驗中，LGP、ALPS-LGP以及2LT-ALPS-LGP 3種算法對每個測試函數均獨立測試30次，種群多樣性和種群膨脹程度的結果為所有測試結果的平均值。

圖2比較了3種算法控制種群膨脹的效果。在所測試的函數中，應用3種算法時，種群的膨脹程度均隨著進化進程逐漸增大。對于測試函數Keijzer-6、Korns-12和Vladislavleva-4，應用LGP算法時，種群的膨脹程度接近個體最大長度，而應用ALPS-LGP以及2LT-ALPS-LGP兩種算法時，種群的膨脹程度遠小于應用LGP算法時種群的膨脹程度。對于測試函數Nguyen-7和Pagie-1，應用3種算法時種群的膨脹程度比較接近，并且遠小于個體最大長度。可見，對于Keijzer-6、Korns-12和Vladislavleva-4這些復雜的測試函數，在搜索最優解過程中，種群傾向于進化得更加膨脹。此種情況下，應用ALPS-LGP以及2LT-ALPS-LGP兩種算法能夠有效控制種群的膨脹程度。對于Nguyen-7和Pagie-1這些簡單的測試函數，應用3種算法時，種群只需進化少量的代數就可搜索到適應度較高的解，因此種群的膨脹程度較輕。

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

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

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

表4描述3種算法在訓練集和測試集的適應度情況(函數名稱和算法名稱均進行縮寫)。

表4 3種算法在訓練集和測試集的適應度

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

函數算法訓練集測試集最小值平均值標準差最小值平均值標準差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

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

4 結論

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

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

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

[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]. 智能系統學報，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.

國家自然科學基金項目(61133003).

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

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

10.11990/jheu.201602025

TP391

A

1006-7043(2017)04-0610-07

曹波，蔣宗禮，張津麗.基于種群年齡分層模型的線性遺傳編程算法[J]. 哈爾濱工程大學學報， 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.

網絡出版地址：http://kns.cnki.net/kcms/detail/23.1390.u.20170310.1348.004.html