基于最小熵產(chǎn)生選擇策略的遺傳算法研究

高 晶 李元香 紀(jì)道敏 項正龍

(武漢大學(xué)計算機(jī)學(xué)院 湖北 武漢 430072)

0 引 言

遺傳算法是由美國的Holland教授于1975年首先提出的一種借鑒達(dá)爾文的“優(yōu)勝劣汰，適者生存”生物進(jìn)化理論的隨機(jī)優(yōu)化算法[1]。它是一種啟發(fā)式搜索和優(yōu)化技術(shù)，可直接對結(jié)構(gòu)對象進(jìn)行操作，不需要對目標(biāo)函數(shù)的連續(xù)性進(jìn)行限定。主要特點是整個求解過程從群體出發(fā)，具有較高的魯棒性和全局搜索能力，對優(yōu)化問題的領(lǐng)域沒有局限性，可擴(kuò)展性強(qiáng)[2]。遺傳算法被證明非常適合于高度非線性問題的優(yōu)化，可以在復(fù)雜的多維搜索空間中找到全局最優(yōu)解，在許多問題中都得到了廣泛的應(yīng)用，如背包問題、旅行商TSP問題、n皇后問題[3]等。近年來，從簡單的PID控制，到復(fù)雜的最優(yōu)控制[4]、自適應(yīng)控制[5]等工程控制問題，遺傳算法都有著較為成功的應(yīng)用案例?，F(xiàn)如今，隨著人工智能熱度的上升，遺傳算法再次成為研究的熱點，遺傳算法等演化算法和人工智能相結(jié)合，可進(jìn)行自然災(zāi)害的評估[6]、建立醫(yī)學(xué)藥物劑量預(yù)測模型[7]、規(guī)劃最優(yōu)路徑[8]等。

遺傳算法雖然應(yīng)用廣泛，但在解決較為復(fù)雜的問題時，由于它本身的隨機(jī)搜索特點，依然存在收斂速度慢和過早收斂兩方面的困擾[9]。Whitley[10]提出遺傳算法中最重要的兩個因素是“選擇壓力”和“種群多樣性”。近年來，很多學(xué)者在遺傳算法緩解“選擇壓力”、增加“種群多樣性”上做了很多研究。Alabsi等[11]使用了穩(wěn)態(tài)替換策略來緩解選擇壓力；王麗萍等[12]提出了角度懲罰距離精英選擇策略防止精英選擇產(chǎn)生過大的壓力；Zhang等[13]通過適應(yīng)度共享創(chuàng)造小生境進(jìn)化環(huán)境，以此增加種群多樣性；Li等[14]將遺傳算法中的種群視為一個動力學(xué)系統(tǒng)，個體視為粒子，遺傳操作視為離子的碰撞或移動，驅(qū)動所有粒子盡可能地運(yùn)動來保持種群多樣性。已有方法從多個角度緩解選擇壓力，從而保持種群多樣性，但是，它們大多都是直接將函數(shù)適應(yīng)值作為評價函數(shù)，這樣很難從根源上緩解選擇壓力從而提高種群多樣性。

為了解決直接將函數(shù)適應(yīng)值作為評價函數(shù)而導(dǎo)致的選擇壓力過大問題，本文將函數(shù)適應(yīng)值通過種群中的個體密度轉(zhuǎn)化為群體熵產(chǎn)生，通過驅(qū)使群體熵產(chǎn)生最小從而求得最優(yōu)的函數(shù)適應(yīng)值。本文將遺傳算法中的種群視為被外界強(qiáng)加固定壓力的非孤立系統(tǒng)，種群在進(jìn)化的每一代都看成非平衡定態(tài)。將物理學(xué)中最小熵產(chǎn)生[15]的概念引入到遺傳算法中，利用非孤立系統(tǒng)在非平衡定態(tài)[16]下遵循最小熵增原理，對傳統(tǒng)遺傳算法的選擇策略進(jìn)行改進(jìn)，提出了一種基于最小熵增原理的選擇策略。在該策略中，采用個體密度來衡量種群多樣性，用精英策略驅(qū)動種群朝熵產(chǎn)生[17]最小的方向快速下降。最后在背包問題和數(shù)值優(yōu)化問題上驗證了這種選擇策略的有效性。

1 遺傳算法和最小熵增原理

1.1 遺傳算法

遺傳算法是一種啟發(fā)式算法，來源于達(dá)爾文的生物學(xué)原理，最早是由John Holland 引入的，為了解釋自然系統(tǒng)的適應(yīng)性過程，以及在類似基礎(chǔ)上產(chǎn)生的人工系統(tǒng)。在自然界中，新生物通過進(jìn)化來適應(yīng)環(huán)境，遺傳算法用類似的方式演化出給定問題的解。

為了得到優(yōu)化問題的解決方案，遺傳算法的流程如下：

1) 確定編碼方式，初始化n個隨機(jī)編碼染色體的種群；

2) 計算種群中每個個體的目標(biāo)函數(shù)，對個體進(jìn)行評價；

3) 根據(jù)個體適應(yīng)值，從種群中選擇個體(一般適應(yīng)值越好被選中的可能性越大)進(jìn)行繁殖；

4) 交叉操作；

5) 變異操作；

6) 產(chǎn)生m個新個體；

7) 從m+n個個體中選擇適應(yīng)值最優(yōu)的n個個體作為下一代種群；

8) 當(dāng)滿足最后的終止條件時，輸出整個過程中找到的最優(yōu)解，沒達(dá)到終止條件時，重復(fù)2—7。

遺傳算法以生物進(jìn)化為原型，和傳統(tǒng)的優(yōu)化方法(枚舉、啟發(fā)式等)相比，整個求解過程從群體出發(fā)，具有較高的魯棒性和全局搜索能力，能并行搜索多個峰值；求解過程和最終結(jié)果和問題領(lǐng)域以及初始化無關(guān)；使用概率機(jī)制進(jìn)行迭代，具有隨機(jī)性；算法具有較強(qiáng)的可擴(kuò)展性，能靈活地和其他算法和策略進(jìn)行融合，適合于求解復(fù)雜的優(yōu)化問題。

1.2 最小熵增原理

一個孤立的熱力學(xué)體系，隨著內(nèi)部粒子的自由運(yùn)動，不論其初始處于何種狀態(tài)，最終總會達(dá)到平衡狀態(tài)。達(dá)到平衡狀態(tài)后，體系的熵為極大值，最終體系中可以引起熵增的所有熱力學(xué)流和熱力學(xué)力均為零。但如果不是孤立體系，環(huán)境對體系施加某種限制。如保持一定的溫度差或濃度差等，這時，體系不可能達(dá)到熱力學(xué)平衡態(tài)。如果外界施加的條件是固定的，如一定的溫度差或一定的濃度差，體系開始會因外界的限制條件而發(fā)生變化，但最后會達(dá)到一種相對穩(wěn)定的狀態(tài)，這種狀態(tài)被稱為非平衡定態(tài)。

熵產(chǎn)生是非平衡態(tài)熱力學(xué)中非常重要的物理變量，在Prigogine等[18]提出的耗散結(jié)構(gòu)中，把熱力學(xué)第二定律由封閉體系推廣到了敞開體系，把熵變分為了兩個部分：(1) 由體系與環(huán)境的相互作用(物質(zhì)和能量交換)而引起的，稱為熵流；(2) 由體系內(nèi)部的不可逆過程產(chǎn)生的，稱為熵產(chǎn)生。熵產(chǎn)生的表達(dá)式為：

(1)

式中：Jk表示第k種不可逆過程的流；Xk表示第k種不可逆過程的推動力。

非平衡定態(tài)具有一些特殊的性質(zhì)，Prigogine在1945年提出了非平衡定態(tài)的最小熵增原理：在接近平衡的條件下，與外界強(qiáng)加的限制相適應(yīng)的非平衡定態(tài)的熵產(chǎn)生具有極小值。

2 最小熵增原理在遺傳算法上的應(yīng)用

2.1 熱力學(xué)系統(tǒng)與遺傳算法

借鑒熱力學(xué)系統(tǒng)在趨于非平衡定態(tài)的過程中熵產(chǎn)生的變化規(guī)律，將遺傳算法中的種群類比為加了固定壓力差的熱力學(xué)系統(tǒng)，兩者之間的對應(yīng)關(guān)系如表 1所示。

表1 熱力學(xué)系統(tǒng)與遺傳算法對應(yīng)關(guān)系

2.2 改進(jìn)的遺傳算法

2.2.1原理描述

基本的遺傳算法通過選擇、交叉和變異從父代中生成子代，直接選取適應(yīng)值最好的個體作為下一代種群。本文提出基于最小熵增原理的遺傳算法(Minimum Entropy Production Genetic Algorithm, MEPGA)就是把非平衡定態(tài)下的熵產(chǎn)生最小的原理應(yīng)用到遺傳算法中新種群的選取中，以保證種群的多樣性。其基本原理如下：用個體密度衡量種群多樣性，當(dāng)種群的多樣性過低時，利用貪婪選擇策略，從新產(chǎn)生的子代和父代個體中選擇使群體熵產(chǎn)生最小的新種群作為下一代種群，以此來保證種群多樣性，從而有利于跳出局部最優(yōu)。

改進(jìn)的遺傳算法MEPGA的基本流程如下：

1) 確定編碼方式，產(chǎn)生初始種群，設(shè)置種群大小N、進(jìn)化代數(shù)、交叉變異概率等。

2) 對種群中的個體進(jìn)行評估(計算個體的適應(yīng)度值、計算個體的密度)。

3) 采用輪盤賭方法從父代種群中選擇產(chǎn)生子代的個體。

4) 對選出的個體進(jìn)行交叉、變異操作，產(chǎn)生M個子代。

5) 對M+N個個體先使用精英保留策略選取n′個適應(yīng)度值最好的個體，然后對剩下的個體使用貪婪選擇機(jī)制，逐個往n′個個體中加入剩下的個體，直到個體數(shù)達(dá)到N，始終保持種群的熵產(chǎn)生最小。

6) 判斷是否達(dá)到迭代終止條件，迭代結(jié)束輸出最優(yōu)解個體和最優(yōu)解值，否則重復(fù)2—5。

求解流程如圖 1所示。

圖1 改進(jìn)的MEPGA流程圖

2.2.2個體密度和群體熵

群體熵產(chǎn)生計算公式最終可轉(zhuǎn)化為密度變化的計算，因此首先需要對群體中個體的密度進(jìn)行定義。

定義1(絕對適應(yīng)值)設(shè)S為搜索空間，f:S→R為目標(biāo)函數(shù)，Xi是種群中的第i個個體。當(dāng)求解的是最大優(yōu)化問題時，e(Xi)=-f(Xi)；當(dāng)求解的是最小優(yōu)化問題時，e(Xi)=f(Xi)。

借鑒等級熵[19]的劃分方式，對活躍窗口和等級進(jìn)行如下定義：

定義2(活躍窗口)設(shè)Pt=(X1,X2,…,XN)∈SN為基于最小熵增原理遺傳算法的第t代種群，Ot=(XN+1,XN+2,…,XN+M)表示由第t代種群產(chǎn)生的M個子代個體。第t代種群的活躍窗口wt由如下規(guī)則生成：1)w0=[l0,u0]，l0是初始種群中絕對適應(yīng)值的下限，u0是初始種群中的上限。2)wt=[lt,ut]表示第t代的活躍窗口，wt+1=[lt+1,ut+1]表示第t+1代活躍窗口，其中l(wèi)t+1=min(lt,min(e(Xj))),j∈(N+1,N+M)，ut+1=max(ut,max(e(Xj))),j∈(N+1,N+M)。

本文提出的基于最小熵增原理的遺傳算法直接對活動窗口進(jìn)行固定的均勻劃分，劃分份數(shù)為常數(shù)K，則種群在第t代第j個區(qū)間的范圍可表示為：

根據(jù)Prigogine對熱力學(xué)第二定律的推廣，非孤立系統(tǒng)的熵產(chǎn)生是系統(tǒng)內(nèi)各種流和產(chǎn)生這種流所對應(yīng)力的乘積之和。對于一個兩組分體系，在體系兩端保持一定的溫度差，由于熱擴(kuò)散現(xiàn)象，會引起體系的濃度差，此時體系中同時存在兩種力：X熱與X擴(kuò)，和兩種相應(yīng)的流：J熱流和J擴(kuò)散流，所以熵產(chǎn)生可表示為：σ=J熱流X流+J擴(kuò)散流X擴(kuò)。

當(dāng)本文討論的體系達(dá)到不隨時間變化的非平衡定態(tài)時，熱流J熱流等于零，因此熵產(chǎn)生可表示為：σ=J擴(kuò)散流X擴(kuò)，擴(kuò)散流的產(chǎn)生源于體系粒子密度的變化，壓力導(dǎo)致密度差，因此對群體的熵產(chǎn)生可定義如下：

(2)

式中：ρi表示個體Xi的密度；ρ0是初始種群的個體密度均值；k是熱力學(xué)中的常量。

2.2.3基于最小熵增原理的貪婪熱力學(xué)替換

從父代種群Pt=(X1,X2,…,XN)的N個個體與產(chǎn)生的M個子代種群Ot=(XN+1,XN+2,…,XN+M)，共N+M個體中挑選出N個個體組成下一代種群Pt+1，使其具有的熵產(chǎn)生σ(Pt+1)最小。

按照貪婪的策略[22]逐個往下一代種群中填充使臨時種群熵產(chǎn)生最小的個體，具體的算法實現(xiàn)如算法1所示。

算法1基于最小熵增的貪婪熱力學(xué)替換

輸入：第t代父種群Pt，第t代子種群Ot

輸出：第t+1代種群Pt+1

1) 將父種群Pt和子種群Ot合并得到大小為N+M的中間種群P′t + 1

2) fori=1 toN

//采用貪婪策略逐個往Pt+1中填充個體，直到N個

3) forj=1 toN+M-i

//尋找本輪最優(yōu)的個體

4) 計算將P′t + 1中的第j個個體加到Pt+1后的熵產(chǎn)生σ(Pt+1∪P′t+1[j])

5) 記錄本次循環(huán)中使熵產(chǎn)生最小的個體Xj

6) end

7) 將個體Xj填充到Pt+1中，同時將其從中間種群P′t + 1中移除

8) end

2.2.4基于最小熵增原理的遺傳算法

以上個體密度、群體熵產(chǎn)生和基于最小熵增原理的替換規(guī)則是本文改進(jìn)遺傳算法的主要構(gòu)成部分。它們保證了種群能在保持一定多樣性的前提下快速向群體熵產(chǎn)生最小的方向進(jìn)化。本文提出的算法稱為基于最小熵產(chǎn)生的熱力學(xué)遺傳算法，算法2給出了本文算法的主要流程。

算法2基于最小熵增原理的遺傳算法(MEPGA)

輸入：搜索空間和目標(biāo)函數(shù)

輸出：最優(yōu)解

1) 確定個體編碼，設(shè)置交叉和變異概率Pc和Pm，區(qū)間劃分等級數(shù)K，迭代次數(shù)T

2) 隨機(jī)生成N個個體作為初始種群P0，對P0中的個體進(jìn)行評估

3) 計算初始活躍窗口w0

4) fori=0 toT

5) 通過輪盤賭從Pi中選擇父代個體進(jìn)行交叉、變異產(chǎn)生M個子個體

6) 評估M個子個體

7) 更新活躍窗口得到wi+1

8) 計算種群中個體的密度分布狀況

9) 利用基于最小熵增的貪婪熱力學(xué)選擇機(jī)制，從N+M個個體中選擇N個個體作為Pi+1

10) end

11) 將迭代過程中得到的使目標(biāo)函數(shù)最優(yōu)的個體作為最優(yōu)解輸出

上述算法中初始化時需要設(shè)置的參數(shù)和基于模擬退火的遺傳算法[20]相比減少了溫度，從而在迭代過程中也就不需要設(shè)置相關(guān)的冷卻進(jìn)度表[21]，簡化了進(jìn)化過程中參數(shù)的設(shè)置。為了平衡“選擇壓力”和“種群多樣性”之間的關(guān)系，本文算法使用了種群中個體密度的分布對種群多樣性進(jìn)行度量，只有當(dāng)種群多樣性較低時才使用基于最小熵增的貪婪熱力學(xué)選擇機(jī)制進(jìn)行后代的篩選，控制群體向熵產(chǎn)生最小的方向進(jìn)化，以保證種群的多樣性。

3 實 驗

為了驗證基于最小熵增原理遺傳算法的適用性，并且希望通過實驗獲得該方法的進(jìn)一步改進(jìn)和推廣思路，本文選取了幾個典型的測試問題進(jìn)行了實驗驗證，主要包括0-1背包問題和數(shù)值優(yōu)化問題。除了本文提出的算法，主要對比的算法有簡單遺傳算法(Genetic algorithm, GA)、穩(wěn)態(tài)遺傳算法(Steady state genetic algorithm, SSGA)和小生境遺傳算法(Niche genetic algorithm, NGA)。

3.1 測試函數(shù)和參數(shù)設(shè)置

數(shù)值優(yōu)化問題選取了8個數(shù)值優(yōu)化測試函數(shù)，分別是經(jīng)典的測試函數(shù)Sphere函數(shù)、Rosenbrock函數(shù)、Rastrigin函數(shù)和Ackley函數(shù)，以及CEC 2013測試函數(shù)集[23]中的9、15、25和26號函數(shù)，分別記為f2、f3、f4、f5、f6、f7、f8、f9，這其中有單峰函數(shù)、多峰函數(shù)、多模函數(shù)和組合函數(shù)。表2為8個數(shù)值測試函數(shù)的表達(dá)式/名稱和變量取值范圍。

表2 數(shù)值優(yōu)化測試問題

本文實驗中運(yùn)用第2節(jié)中描述的基于最小熵增原理的遺傳算法，交叉概率Pc=0.9，變異概率Pm=0.2。對0-1背包問題f1分別選取50和100個物品個數(shù)進(jìn)行實驗驗證。對數(shù)值測試函數(shù)分別在10維和20維下進(jìn)行測試。每個測試問題都在上述參數(shù)設(shè)置下獨立運(yùn)行50次，取每次運(yùn)行結(jié)果的平均值作為最終求解結(jié)果。

3.2 實驗結(jié)果分析

將四種算法在相同參數(shù)下對不同的測試問題、不同的測試問題維度，獨立運(yùn)行50次，分別從最優(yōu)解均值和最優(yōu)解方差兩個方面來對這兩種算法的性能進(jìn)行對比，最終的統(tǒng)計結(jié)果如表3所示。

表3 算法在背包問題上的結(jié)果統(tǒng)計

可以看出，MEPGA算法所求的最優(yōu)解均值和方差在這四個算法中都占據(jù)優(yōu)勢，可見算法在尋找簡單背包問題的求解上有一定改進(jìn)效果。

表4為四種算法在數(shù)值函數(shù)問題中的測試結(jié)果，分析統(tǒng)計結(jié)果可知，MEPGA算法在所測的大多數(shù)數(shù)值函數(shù)問題上最優(yōu)解的均值和方差都能得到較好的結(jié)果，在少數(shù)多峰多模問題上結(jié)果和改進(jìn)的遺傳算法(SSGA、NGA)沒有明顯優(yōu)勢，但比簡單遺傳算法(GA)所得結(jié)果好。所選測試問題覆蓋范圍廣、有一定代表性，因此可以說明本文算法改進(jìn)策略的有效性。

表4 算法在數(shù)值函數(shù)測試的結(jié)果統(tǒng)計

續(xù)表4

通過多次運(yùn)行后的統(tǒng)計結(jié)果分析，本文中提出的算法在離散問題、數(shù)值優(yōu)化問題(包括單峰、多模、組合函數(shù)等)上大多都能獲得較好的結(jié)果，相較簡單遺傳算法(GA)而言，結(jié)果有了很大的改善。在少數(shù)測試函數(shù)上的處理結(jié)果和改善后的穩(wěn)態(tài)遺傳算法(SSGA)、小生境遺傳算法(NGA)不分伯仲，但多數(shù)情況下還是比這兩種算法效果要理想。由此可見，本文提出的選擇策略在一定程度上能改善種群在進(jìn)化過程中的選擇壓力，從而能夠找到更好的解。

以下隨機(jī)選取了實驗過程中比較有代表性的幾個測試問題在不同緯度下的收斂曲線圖。圖 2中分別是GA、SSGA、NGA和MEPGA在物品數(shù)n=50和n=100時的最優(yōu)點的變化趨勢。

圖2 f1 最優(yōu)點變化趨勢

由圖2中最優(yōu)點的變化趨勢來看，不管物品數(shù)是50還是100，MEPGA算法找到的最優(yōu)解和其他三種算法相比更有優(yōu)勢，說明基于最小熵增原理的遺傳算法在改進(jìn)背包問題上是可行的而且能保持較好的種群多樣性，能有效地跳出局部最優(yōu)解從而搜索到全局最優(yōu)解。

圖3和圖4是本文提出的算法和GA、SSGA、NGA分別在10維和20維的f6～f9數(shù)值測試函數(shù)上最優(yōu)值的收斂軌跡?？梢钥闯?MEPGA在數(shù)值測試問題上也有較明顯的效果，而且比簡單遺傳算法(GA)、改進(jìn)遺傳算法(SSGA、NGA)搜索到的最優(yōu)值更好。

圖3 f6 ～f7測試函數(shù) 問題維數(shù)n=10

圖4 f8 ～f9測試函數(shù) 問題維數(shù)n=20

從整體的實驗效果來看，MEPGA在組合優(yōu)化問題，單峰、多峰、多模、組合等數(shù)值優(yōu)化問題上都有一定的適用性。從統(tǒng)計結(jié)果中四個算法運(yùn)行的最優(yōu)值均值可以看出，本文算法在大多測試函數(shù)上都能找到比其他算法更優(yōu)的解，這很好地說明了本文的改進(jìn)在一定程度上緩解了種群在進(jìn)化過程中的選擇壓力，從而能更好跳出局部最優(yōu)找到更優(yōu)的解。統(tǒng)計結(jié)果中的最優(yōu)值方差則反映了本文的改進(jìn)策略具有更高的魯棒性。

4 結(jié) 語

針對遺傳算法在搜索過程中由于選擇壓力過大導(dǎo)致種群多樣性喪失，從而容易陷入局部最優(yōu)的問題，本文將熱力學(xué)非平衡定態(tài)下的最小熵增原理應(yīng)用到遺傳算法的選擇策略中，提出了一種基于最小熵產(chǎn)生的選擇策略，能在種群快速收斂的同時保持種群的多樣性，進(jìn)而跳出局部最優(yōu)。實驗表明，改進(jìn)后的算法MEPGA在0-1背包問題和單峰、多峰數(shù)值優(yōu)化問題上均能得到比GA和改進(jìn)的遺傳算法更好的結(jié)果。這說明基于最小熵增原理的選擇策略在緩解選擇壓力、保證種群平穩(wěn)進(jìn)化上是有一定效果的。由于本文使用的是貪婪選擇機(jī)制，因此計算時間復(fù)雜度比較高。本文的后續(xù)工作將著重研究算法計算效率的改進(jìn)，對基于最小熵產(chǎn)生原理選擇策略做進(jìn)一步完善。同時本文只是將基于最小熵增原理應(yīng)用于簡單的遺傳算法，驗證該策略的可行性，后續(xù)將嘗試將該策略推廣到其他演化算法，進(jìn)一步驗證本文中所提出改進(jìn)策略的普適性。