基于自適應罰函數的改進遺傳算法

[摘 要]遺傳算法（Gnectic Algorithm，GA）是由60年代美國的Mcihigna大學的Hollnad教授首先提出。其原理是借助于自然演化原則和人工自適應系統(tǒng)的原則，通過模擬孟德爾的遺傳理論以及達爾文的自然進化論從而創(chuàng)造出的求解極值問題的方法，但是基本遺傳算法在全局最優(yōu)收斂方面仍存在部分漏洞。本文將傳統(tǒng)遺傳算法改進，以便盡可能保留遺傳過程中的最優(yōu)解。

[關鍵詞]遺傳算法；算子；自適應罰數

作為一種搜索算法，雖然遺傳算法可以通過優(yōu)化過程中的各個環(huán)節(jié)進行適當的設計和操作從而實現全局和局部均衡的搜索，在某些問題上也達到了理想的效果，但是基本遺傳算法在全局最優(yōu)收斂方面仍存在部分漏洞。如最優(yōu)解往往處于可行區(qū)域和不可行區(qū)域邊界，而優(yōu)化過程中很可能就把最接近最優(yōu)解的那些個體規(guī)劃入不可行解的區(qū)域從而淘汰掉。特別是應用于本文的非均勻信道增益優(yōu)化以及功率控制的約束優(yōu)化問題，在約束條件的制約下，如何高效率地搜索得到可行解以及最優(yōu)解將是算法面臨的首要問題。針對該問題，本文在基本遺傳算法的基礎上，設計了包含動態(tài)交叉變異算子、精英個體保存、自適應罰函數的改進遺傳算法（modify Genetic Algorithm，mGA），并將其應用于柔性轉發(fā)器的非均勻信道增益調整及功率控制優(yōu)化問題。

一、動態(tài)交叉及變異算子及倒序算子

基本遺傳算法中交叉概率和變異概率是恒定值的這一特點，往往會使某些優(yōu)化問題提前陷入早熟的境地，從而影響算法收斂性，降低算法的搜索效率。為此本文引入了交叉概率和變異概率隨種群變化的動態(tài)交叉及變異算子，能夠在一定程度上提高優(yōu)化算法的收斂速度和運行效率。

動態(tài)交叉算子中，采用多點交叉和均勻交叉兩種基本的基因操作，隨著進化次數的增加，逐步均勻交叉的概率；多點交叉的意思是在基因交叉過程中，設定多個交叉點進行交叉運算，該算法中選擇交叉點數為決策變量的兩倍；均勻交叉即一致交叉，就是在交叉過程中兩個配對的個體基因都以相同的概率進行交換，從而形成新的個體。在交叉過程中，首先生成一個與個體染色體長度一致的屏蔽字，屏蔽字每一位只有0和1兩種選擇，然后個體根據屏蔽字分別選擇對應位的父代基因，進而完成交叉。

倒序基因操作通過選取少量的個體中的某段染色體進行倒序處理，從而使得算法獲得更加廣泛的搜索能力，一定程度地降低算法早熟概率，其有著和變異類似的機理，只是處理的染色體段并不做內容的改變，而是順序的調整。

二、精英個體保留

在求最優(yōu)解的搜索過程中，由于受到各個運算過程隨機性的影響，通過交叉、變異運算產生新個體的過程中存在一定概率的破壞性，如破壞掉當前群體中適應度最優(yōu)解的個體，這樣會導致整個群體的平均適應度的大幅度降低，并且對遺傳算法的運行效率產生不利的影響，故為了避免此類現象發(fā)生，使得種群中最優(yōu)的個體能夠完整地遺傳給下一代，算法設計了精英個體的保留操作。由于本文針對的是約束優(yōu)化問題，某一代的最優(yōu)解并不一定是可行解，對于不可行解的最優(yōu)保存并不在基本遺傳算法的設計范圍，故本文針對性地設計了包含約束問題的精英保留操作如下：1、如果種群中存在可行解，找到可行解最小的個體，將其隨機地替換子代的某個個體；2、如果種群中無不可行解，找到約束違反最小的解集，隨機選取一個替換子代的某個個體。實施最優(yōu)保存策略是保證遺傳算法收斂的重要保證，對不可行解的隨機選擇而不是選擇相同條件下目標函數最小的值是一定程度上在搜索前期盡量擴大搜索的范圍，對約束邊界的適應性更強，也使得算法不易陷入局部最優(yōu)。

三、自適應罰函數

在實際的工程實踐中，一般情況下，優(yōu)化算法問題往往存在著各種約束條件，最優(yōu)解的首要條件是要滿足各種約束條件，才能規(guī)劃進可行解范疇。

對于優(yōu)化算法中的約束問題的處理，目前主要的方法包括：拒絕法、修補方法和罰函數方法。其中拒絕方法是指丟棄進化過程中所有不可行解，顯而易見，該方法運行效率低下。修補方法將不可行個體進行修補成為可行解，其往往受到優(yōu)化問題的制約，對于組合問題容易使用，而大多數問題，修補往往難以實施。罰函數方法是最為常用和典型的約束處理方法，該方法通過對不可行解的目標函數值進行修改，加入一定的懲罰量，從而使其一定程度地劣于可行個體，進而使得搜索算法向可行解的方向搜索。罰函數的優(yōu)點在于在種群中有了一定數量的不可行解，從而使得搜索從可行區(qū)域和不可行區(qū)域兩個方向搜索最優(yōu)解，有利于提高搜索效率。罰函數的罰因子設計一直是罰函數設計的難題，如何確定懲罰項，從而使得算法在選擇壓力（拒絕一些不可行解）和信息保留（保持一些不可行解）之間保持良性的平衡，避免過度懲罰或者懲罰不足的現象出現。

通常罰因子參數設定非常困難，其值的大小，將直接影響搜索，所以針對罰因子設計的困難，本文采用了一種無需設定任何參數的自適應罰函數方法，該方法通過種群中的不可行比例動態(tài)調整懲罰的大小。算法的思想是約束優(yōu)化問題的最優(yōu)解往往處于可行區(qū)域和不可行區(qū)域邊界，不可行個體攜帶了大量的有利于搜索最優(yōu)解的信息，利用好該信息將有助于算法的搜索。當種群中出現不可行個體數目較多的時候，加大對不可行個體的懲罰力度，使得算法搜索方向指向可行解區(qū)域；而當種群中可行解個數較多，適當降低不可行個體的懲罰力度，有利于發(fā)掘不可行個體所攜帶的信息，使得算法從不可行區(qū)域向最優(yōu)解搜索。

作者簡介：曹強（1967-），男，浙江嘉興人，武警士官學校教授，研究方向：船舶輪機、船舶通信技術。endprint