[發明專利]一種基于進化激勵算子的遺傳算法

在審

• 申請號: 201510388233.8
• 申請日: 2015-07-06
• 公開（公告）號: CN104951835A
• 公開（公告）日: 2015-09-30
• 發明（設計）人: 黃健;孔江濤;郝建國;龔建興;項鳳濤;吳白冰;張中杰
• 申請（專利權）人: 中國人民解放軍國防科學技術大學
• 主分類號: G06N3/12
• 分類號: G06N3/12
• 代理公司: 北京中濟緯天專利代理有限公司 11429
• 代理人: 胡偉華

技術領域

本發明屬于實數編碼的遺傳算法領域，特別涉及一種基于進化激勵算子的遺傳算法。

技術背景

目前關于帶限制條件的實數參數優化問題的求解方法研究比較多，主要的求解方法是進化算法，遺傳算法就是比較成熟的一種進化算法，遺傳算法是美國Michigan大學的Holland教授于1969年首次提出，后經歸納總結形成的一類模擬進化算法，其源于進化論、物種選擇說和群體遺傳學。

遺傳算法具有很好的魯棒性和高效性，是一種隱性的并行計算方法，并廣泛應用于計算科學和工程設計領域，適合解決復雜的非線性和多維空間尋優問題。

雖然遺傳算法具有很多優點并有大量的成功應用，高瑋提出的自適應交叉變異概率遺傳算法(具體參考文獻，改進的快速遺傳算法及其性能研究[J]，系統工程與電子技術，2003，25(11):1427-1430)，以及Lin?Wen-Yang提出的PRGA算法(具體參考文獻，Lin?W?Y,Lee?W?Y,Hong?T?P,Adapting?Crossover?and?Mutation?Rates?in?Genetic?Algorithms，Journal?of?Information?Science?and?Engineering?79,2003.)，但其自身也存在不足，如局部搜索能力不足和隨機游走就是需要解決的問題。通過動態調整交叉變異率，可以一定程度克服隨機游走問題，通過規劃個體可以提高算法的搜索能力。

發明內容

本發明的目的在于提供一種基于進化激勵算子的遺傳算法，提高遺傳算法的局部搜索能力和一定程度的克服算法隨機游走問題，從每代種群目標函數值的分布總體出發，預測出進化激勵算子，并利用進化激勵算子對種群的進化進行調整和指導。

具體技術方案如下：

一種基于進化激勵算子的遺傳算法，包括以下步驟：

(1)初始化種群規模，設置遺傳代數，初始遺傳代數為第一代，轉入步驟(2)；

(2)記當前代種群為父代種群，計算當前代種群中每個個體的目標函數值，將最小的B個目標函數值對應的個體儲存下來，B為整數，并按照從大到小的順序對所有的目標函數值進行排列，得到目標函數值序列；

(3)選擇調制函數，將目標函數值序列調制成調制后序列；

(4)采用灰色預測模型GM(1,1)模型，計算進化激勵算子；

(5)根據激勵算子，計算進化激勵算子對應的代種群中每個個體的變化率；

(6)設定規劃種群大小和幅度控制因子，根據每個個體的變化率，計算得到每個父代個體對應的規劃后代包含的個體個數，并從父代個體及其對應的規劃后代個體中選擇出目標函數值取值最小的個體替換父代個體，更新父代種群中的所有個體，得到規劃后的父代種群；

(7)對規劃后的父代種群，利用上述(2)至(5)的步驟計算得到該種群每個個體的變化率，并計算交叉率和變異率；

(8)用每個個體的交叉率和變異率控制其交叉變異過程，并進行交叉變異操作，得到新的子代種群后，計算子代種群中所有個體的目標函數值，并將所有個體按照其對應的目標函數值從大到小排列，用步驟(2)中存儲的B個個體替換此時種群中的前B個個體，得到替換后的種群；判斷遺傳代數是否大于最大的遺傳代數或者得到某個個體的目標函數值是否滿足要求，如果達到最大遺傳代數或者滿足要求，則算法停止，否則遺傳代數完成自加1的操作，并以替換后的種群作為下一代父代種群進入步驟(2)。

進一步地，所述步驟(3)的具體過程為：選擇嚴格單調遞增的指數函數作為調制函數，調制后序列為X⁽⁰⁾，

X⁽⁰⁾(k)＝a·e^b·S(k)

其中，a、b為調制函數的參數，k為個體的編號，k為整數，取值范圍為從1到PS，PS為每代種群的規模，種群規模大小是固定不變的；S(k)為經過排列的目標函數序列中第k個目標函數值，X⁽⁰⁾(k)為S(k)對應的調制數值。

進一步地，所述步驟(4)的具體過程為，設Bi為迭代次數標識，表示第Bi次迭代計算，Bi為正整數，初始值為1，具體步驟為，

(41)對調制后序列X⁽⁰⁾進行累加處理，得到對應第Bi次迭代的1-GAO序列X⁽¹⁾，具體過程如下