基于最小熵產生選擇策略的遺傳算法研究

高 晶 李元香 紀道敏 項正龍

(武漢大學計算機學院 湖北 武漢 430072)

0 引 言

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

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

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

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

1.1 遺傳算法

遺傳算法是一種啟發式算法，來源于達爾文的生物學原理，最早是由John Holland 引入的，為了解釋自然系統的適應性過程，以及在類似基礎上產生的人工系統。在自然界中，新生物通過進化來適應環境，遺傳算法用類似的方式演化出給定問題的解。

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

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

2) 計算種群中每個個體的目標函數，對個體進行評價；

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

4) 交叉操作；

5) 變異操作；

6) 產生m個新個體；

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

8) 當滿足最后的終止條件時，輸出整個過程中找到的最優解，沒達到終止條件時，重復2—7。

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

1.2 最小熵增原理

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

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

(1)

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

非平衡定態具有一些特殊的性質，Prigogine在1945年提出了非平衡定態的最小熵增原理：在接近平衡的條件下，與外界強加的限制相適應的非平衡定態的熵產生具有極小值。

2 最小熵增原理在遺傳算法上的應用

2.1 熱力學系統與遺傳算法

借鑒熱力學系統在趨于非平衡定態的過程中熵產生的變化規律，將遺傳算法中的種群類比為加了固定壓力差的熱力學系統，兩者之間的對應關系如表 1所示。

表1 熱力學系統與遺傳算法對應關系

2.2 改進的遺傳算法

2.2.1原理描述

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

改進的遺傳算法MEPGA的基本流程如下：

1) 確定編碼方式，產生初始種群，設置種群大小N、進化代數、交叉變異概率等。

2) 對種群中的個體進行評估(計算個體的適應度值、計算個體的密度)。

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

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

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

6) 判斷是否達到迭代終止條件，迭代結束輸出最優解個體和最優解值，否則重復2—5。

求解流程如圖 1所示。

圖1 改進的MEPGA流程圖

2.2.2個體密度和群體熵

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

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

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

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

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

根據Prigogine對熱力學第二定律的推廣，非孤立系統的熵產生是系統內各種流和產生這種流所對應力的乘積之和。對于一個兩組分體系，在體系兩端保持一定的溫度差，由于熱擴散現象，會引起體系的濃度差，此時體系中同時存在兩種力：X熱與X擴，和兩種相應的流：J熱流和J擴散流，所以熵產生可表示為：σ=J熱流X流+J擴散流X擴。

當本文討論的體系達到不隨時間變化的非平衡定態時，熱流J熱流等于零，因此熵產生可表示為：σ=J擴散流X擴，擴散流的產生源于體系粒子密度的變化，壓力導致密度差，因此對群體的熵產生可定義如下：

(2)

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

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

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

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

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

輸入：第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

//尋找本輪最優的個體

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

5) 記錄本次循環中使熵產生最小的個體Xj

6) end

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

8) end

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

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

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

輸入：搜索空間和目標函數

輸出：最優解

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

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

3) 計算初始活躍窗口w0

4) fori=0 toT

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

6) 評估M個子個體

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

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

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

10) end

11) 將迭代過程中得到的使目標函數最優的個體作為最優解輸出

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

3 實 驗

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

3.1 測試函數和參數設置

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

表2 數值優化測試問題

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

3.2 實驗結果分析

將四種算法在相同參數下對不同的測試問題、不同的測試問題維度，獨立運行50次，分別從最優解均值和最優解方差兩個方面來對這兩種算法的性能進行對比，最終的統計結果如表3所示。

表3 算法在背包問題上的結果統計

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

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

表4 算法在數值函數測試的結果統計

續表4

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

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

圖2 f1 最優點變化趨勢

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

圖3和圖4是本文提出的算法和GA、SSGA、NGA分別在10維和20維的f6～f9數值測試函數上最優值的收斂軌跡。可以看出,MEPGA在數值測試問題上也有較明顯的效果，而且比簡單遺傳算法(GA)、改進遺傳算法(SSGA、NGA)搜索到的最優值更好。

圖3 f6 ～f7測試函數 問題維數n=10

圖4 f8 ～f9測試函數 問題維數n=20

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

4 結 語

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