當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

组合优化求解方法

發布時間：2024/8/1 编程问答 44 豆豆

生活随笔收集整理的這篇文章主要介紹了组合优化求解方法小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

1. 離散優化/整數規劃

整數規劃，或者離散優化（Discrete Optimization），是指數學規劃問題中自變量存在整數。

混合整數規劃（Mixed Integer Programming, MIP），即自變量既包含整數也有連續變量

求解復雜度

求解整數規劃的精確解是NP難的，也就是指數級算法復雜度（Exponential Time Solvable）

假設這里的整數是0,1變量，那么我們可以簡單地理解為算法復雜度是2^{n（需要解2}n個線性規劃問題）。也就是說，每增加一個0，1變量，求解的速度就有可能要增加一倍！例如求解n=100的整數規劃問題需要1小時，那么求解n=101的規模可能會需要2小時，n=102需要4小時，n=105需要32小時。。這就是指數爆炸！

其它解決方案

近似算法（Approximation Algorithms），啟發式算法（Heuristic Algorithms），遺傳算法（Evolution Algorithms, Meta-Heuristic）等等。它們雖然不能求得整數規劃的最優解，但是卻能在短時間（通常多項式時間）內給出一個較好的可行解

組合優化是整數規劃的子集。的確，絕大多數組合優化問題都可以被建模成（混合）整數規劃模型來求解

2. 組合優化求解方法：

精確方法——無法應用于大規模實例
近似算法——本質上都是貪心算法，而且通常都是多項式時間的算法
啟發式方法——以問題為導向（通常依賴于人工選取 heuristics； –難以調整何時何地應用 heuristics；般只能求得局部最優解；啟發式算法的設計過程需要特殊的領域知識，并可能需要反復試驗來調整算法。實際上，每當問題設置變化時，算法通常需要被重新修訂，這需要我們重新優化系統，故而啟發式算法在這時變得不切實際）
元啟發算法——如遺傳算法、蟻群算法、進化算法、智能算法；可以將它當作一個黑箱子對幾乎任何問題適用；可以控制算法的迭代次數
神經網絡
RL方法

3. 元啟發算法Meta-heuristic

也被稱為智能優化算法(Intelligent optimization algorithm)

舉例：

(1) 遺傳算法；

遺傳算法以一種群體中的所有個體為對象，并利用隨機化技術指導對一個被編碼的參數空間進行高效搜索。其中，選擇、交叉和變異構成了遺傳算法的遺傳操作；參數編碼、初始群體的設定、適應度函數的設計、遺傳操作設計、控制參數設定五個要素組成了遺傳算法的核心內容。

種群——由經過基因（gene）編碼的一定數目的個體(individual)組成
個體——是染色體(chromosome)；遺傳物質的主要載體，即多個基因的集合
由于仿照基因編碼的工作很復雜，我們往往進行簡化，如二進制編碼
染色體長度為二進制編碼的長度。chromosomes 每一條染色體是一個字典，該字典有兩個內容，分別是包含基因的Gene類和適應度函數值fitness

初代種群產生之后，按照適者生存和優勝劣汰的原理，逐代（generation）演化產生出越來越好的近似解，在每一代，根據問題域中個體的適應度（fitness）大小選擇（selection）個體，并借助于自然遺傳學的遺傳算子（genetic operators）進行組合交叉（crossover）和變異（mutation），產生出代表新的解集的種群。這個過程將導致種群像自然進化一樣的后生代種群比前代更加適應于環境，末代種群中的最優個體經過解碼（decoding），可以作為問題近似最優解。

生物學術語

基因型(genotype)：性狀染色體的內部表現；
表現型(phenotype)：染色體決定的性狀的外部表現，或者說，根據基因型形成的個體的外部表現；
進化(evolution)：種群逐漸適應生存環境，品質不斷得到改良。生物的進化是以種群的形式進行的。
適應度(fitness)：度量某個物種對于生存環境的適應程度。
選擇(selection)：以一定的概率從種群中選擇若干個個體。一般，選擇過程是一種基于適應度的優勝劣汰的過程。
復制(reproduction)：細胞分裂時，遺傳物質DNA通過復制而轉移到新產生的細胞中，新細胞就繼承了舊細胞的基因。
交叉(crossover)：兩個染色體的某一相同位置處DNA被切斷，前后兩串分別交叉組合形成兩個新的染色體。也稱基因重組或雜交；
變異(mutation)：復制時可能（很小的概率）產生某些復制差錯，變異產生新的染色體，表現出新的性狀。
編碼(coding)：DNA中遺傳信息在一個長鏈上按一定的模式排列。遺傳編碼可看作從表現型到基因型的映射。
解碼(decoding)：基因型到表現型的映射。
個體（individual）：指染色體帶有特征的實體；
種群（population）：個體的集合，該集合內個體數稱為種群

遺傳算法的一般步驟：

隨機產生種群。
根據策略判斷個體的適應度，是否符合優化準則，若符合，輸出最佳個體及其最優解，結束。否則，進行下一步。
依據適應度選擇父母，適應度高的個體被選中的概率高，適應度低的個體被淘汰。
用父母的染色體按照一定的方法進行交叉，生成子代。
對子代染色體進行變異。

選擇算子

輪盤賭選擇（Roulette Wheel Selection）
隨機競爭選擇（Stochastic Tournament）
最佳保留選擇
無回放隨機選擇（也叫期望值選擇Excepted Value Selection）
確定式選擇
……

遺傳算法的缺點

1、遺傳算法的編程實現比較復雜,首先需要對問題進行編碼,找到最優解之后還需要對問題進行解碼,

2、另外三個算子的實現也有許多參數,如交叉率和變異率,并且這些參數的選擇嚴重影響解的品質,而目前這些參數的選擇大部分是依靠經驗.

3、沒有能夠及時利用網絡的反饋信息,故算法的搜索速度比較慢，要得要較精確的解需要較多的訓練時間。

4、算法對初始種群的選擇有一定的依賴性，能夠結合一些啟發算法進行改進。

5、算法的并行機制的潛在能力沒有得到充分的利用，這也是當前遺傳算法的一個研究熱點方向。

常用混合遺傳算法，合作型協同進化算法等來替代，這些算法都是GA的衍生算法。

(2) 粒子群算法PSO；

PSO算法主要應用于連續問題，包括神經網絡訓練和函數優化等，而GA除了連續問題之外，還可應用于離散問題，比如TSP問題、貨郎擔問題、工作車間調度等

(3) 禁忌搜索算法；

(4) 蟻群算法；

(5) 人工蜂群算法；

(6) 模擬退火算法；*

(7) 差分進化算法；

(8) 免疫算法；

(9) 蛙跳算法；

(10) 帝國競爭算法；

(11) 和聲搜索算法；

(12) 分布估計算法；

(13) Memetic算法；

(14) 文化算法；

(15) 人工魚群算法；

(16) 灰狼優化算法；

(17) 進化規劃；

(18) 進化策略；

(19) 候鳥優化算法；

(20) 算法；

(21) 花朵授粉算法；

(22) 引力搜索算法；

(23) 化學反應優化算法；

3. 智能優化算法總結

蟻群算法，1991 年
粒子群算法，1994年
細菌覓食優化算法, Bacterial Foraging Optimization Algorithm，2002年
混合蛙跳算法， Shuffled Frog Leaping Algorithm，2003年
人工蜂群算法， Artificial Bee Algorithm，2005年
螢火蟲算法，第一種 Glowworm Swarm Optimization Algorithm 2005年，第二種Firefly Algorithm 2009年
布谷鳥搜索， Cuckoo Search，2009年
果蠅優化算法，Fruit Fly Optimization Algorithm，2011年
頭腦風暴優化算法，Brain Storm Optimization，2011年
蝙蝠算法， Bat Algorithm，2010 年
灰狼優化算法，Grey Wolf Algorithm，2014 年
蜻蜓算法，Dragonfly Algorithm，2015 年
鯨魚優化算法，Whale Algorithm，2016 年
蝗蟲優化算法,Grasshopper Algorithm，2017 年
麻雀搜索算法, Sparrow Algorithm ，2020 年