[發明專利]一種解決0-1背包問題的自適應遺傳退火計算方法

無效

• 申請號: 201210413829.5
• 申請日: 2012-10-26
• 公開（公告）號: CN102930340A
• 公開（公告）日: 2013-02-13
• 發明（設計）人: 呂學勤;陳樹果;姜英杰;段利偉
• 申請（專利權）人: 上海電力學院
• 主分類號: G06N3/12
• 分類號: G06N3/12
• 代理公司: 上海申匯專利代理有限公司 31001
• 代理人: 吳寶根

技術領域

本發明涉及一種，特別涉及一種。

背景技術

0-1背包：給定一個載重量為w的包，n個物品，其重量為w_i，價值為v_i，1<=i<=n，要求:把物品裝入背包，并使包內物品價值最大。在0-1背包問題中，物體或者被裝入背包，或者不被裝入背包，只有兩種選擇。求解取出哪些物品可以使背包中裝的物品最值錢又不超出背包容量。

0-1背包問題（Zero-one?Knapsack?Problem，簡稱ZKP）是運籌學中一個典型的NP（Non.deterministic?Polynomia）完全問題，即多項式復雜程度的非確定性問題，NP完全問題是NP類中最難的問題，其涵義是只要有一個NP完全問題存在多項式時間算法，則整個NP類問題都存在多項式時間算法。

目前，解決0/1背包的常規方法包括窮舉法、動態規劃法和遞歸回溯法等，但只能處理小規模背包問題。啟發式算法是模擬自然界和生物行為的新型算法，具有模型靈活，求解速度快、解的質量高等一系列優點，因而被獲得廣泛應用。但遺傳算法、蟻群算法、差分進化算法等優化算法收斂速度慢、全局收斂性差，而模擬退火算法（Simulated?Annealing?Algorithm,?簡稱SA）能改善陷入局部最優解的缺陷，使算法快速地收斂于全局最優解。因此，有必要將進行自適應遺傳退火算法(Adaptive?Genetic?Annealing?Algorithm,?簡稱AGAA)的研究，即將模擬退火算法SA和遺傳算法GA相結合，并改進交叉變異策略，使得改進后的算法既保持了GA的高速并行性，又保持了SA跳出局部最優值的能力。

發明內容

本發明是針對標準遺傳算法易早熟收斂以及收斂速度慢的問題，提出了一種解決0-1背包問題的自適應遺傳退火計算方法，具有收斂速度、尋優能力和穩定性高的優點，特別適合解決解決高維約束優化問題。

本發明的技術方案為：一種解決0-1背包問題的自適應遺傳退火計算方法，具體包括如下步驟：

1）設定算法參數，包括群體規模popsize，染色體長度chromlong，退火初始溫度T0，退溫系數k等；

2）產生初始種群pop(0)；

3）根據適應函數對群體中每一個個體的適應度值作出評價，并判斷其是否符合優化準則，若符合，輸出最佳個體及其代表的最優解，并結束計算；否則執行以下步驟；

a）進行遺傳操作，選擇策略采用輪盤賭和最優保存策略相結合的選擇機制，最優保存數目設為2，交叉、變異操作采用自適應交叉、變異概率，產生SA初始群體sa-pop；

b）模擬退火操作，接受條件采用Metropolis準則并判別能否進入下一代群體；進行popsize次迭代產生下一代群體pop(i+1)；

c）執行退溫操作，并令i=i+1；判斷是否達到終止條件，是的話則終止，否則返回第3）步。

所述步驟a）中采用輪盤賭和最優保存策略相結合的選擇機制，以保留當前最優染色體，即從當前種群中保留2個最佳染色體直接復制到下一代種群中，余下的種群通過輪盤賭方法選擇進入下一代種群中，以提高算法的收斂性。

所述步驟a）中交叉、變異操作采用自適應交叉、變異概率，交叉概率Pc和變異概率Pm按如下公式對應進行自適應調整：

?????????????????????　　　　　　　　　　　　　

式中的P_c1=0.9，P_c2?=0.6，P_m1=0.1，P_m2?=0.001，f_max-為種群中最大的適應度值；f_avg為每代種群的平均適應度值；f₁為需要交叉的兩個個體中較大的適應度值；f為需要變異個體的適應度值。

本發明的有益效果在于：本發明解決0-1背包問題的自適應遺傳退火計算方法，引入自適應交叉、變異和退火策略的混合遺傳算法（AGAA），加據了染色體之間的競爭，提高了收斂速度，同時擴大種群的搜索范圍，加強了種群跳出局部最優的能力，特別適用于解決高維約束優化問題，具有較好的搜索效率。

附圖說明