优化算法综述
目錄
- 優化算法綜述
- 數學規劃法
- 精確算法（exact algorithm）
- 啟發式 VS. 元啟發式
- 啟發式算法
- 元啟發式算法
- What is the difference between heuristics and meta-heuristics?
- 多目標智能優化算法
- 模擬進化算法與傳統的精確算法（確定性算法）的區別
- 優化算法分類
- 算法介紹
- 帝國競爭算法（Imperialist Competitive Algorithm，ICA）
- 分支定界法（Branch and Bound, BB）
- NSGA-Ⅱ算法
- 遺傳算法（Genetic Algorithm, GA）
- 禁忌搜索算法（Tabu Search，TS）
- 文化基因算法（Memetic Algorithm，MA）
- 機器學習中的最優化模型
- 梯度下降法（Gradient Descent）
- 牛頓法和擬牛頓法（Newton's method & Quasi-Newton Methods）
- 共軛梯度法（Conjugate Gradient）
- 拉格朗日乘數法（Lagrange Multiplier Method）
優化算法綜述
| 依據 | 分類 | 具體算法 |
| 1 | 全局優化 | 遺傳算法（GA）、帝國競爭算法（ICA）、 粒子群優化（PSO） |
| 局部優化 | 模擬退火（SA）、貪婪算法（Greedy）、 鄰域搜索（NS） | |
| 2 | 精確算法 | 線性規劃（LP）、分支定界法（BB） |
| 模擬進化算法 | v | |
| 群體仿生類算法、又稱為群體智能優化算法 | GA、PSO | |
| 數學規劃方法： | 動態規劃（DP）、線性規劃、整數規劃、 混合整數規劃、 分支定界法、 割平面法 | |
| v | ||
| v | ||
| 啟發式算法（Heuristic Algorithms） | v | |
| 元啟發式算法（Meta-Heuristic Algorithms） | v |
數學規劃法
數學規劃法：通常將多目標問題轉化為單目標問題來解決。
精確算法（exact algorithm）
精確算法：通常將待解決的優化問題轉換為數學規劃問題，進行精確求解。如：分支定界法（BB）。
- 優點：在問題規模較小時，精確算法能在合理的時間內找到問題的最優解；
- 缺點：但當問題規模較大時（是NP-Hard問題），精確算法的計算復雜度高，求解時間呈指數級增長，不能容忍（指數爆炸）。
啟發式 VS. 元啟發式
問題描述：現實中很多問題的優化都可以建模為基于序列的組合優化，如旅行商問題（TSP）、排產問題、各類資源分配問題等。尋找最優序列的問題是NP難問題（NP-Hard問題）（其解空間為n!）。
解決這類問題常用的方法有兩種：
- （1）一種方法是啟發式算法，啟發式算法是基于問題本身的規則得到較好的可行解，本質是貪心算法（貪婪算法，greedy）。這種方法速度較快，但因與問題本身聯系緊密（problem specific, problem dependent），導致其通用性較差。
- （2）另一種方法是元啟發式算法，例如遺傳算法、禁忌搜索算法、蟻群算法、模擬退火算法等都是元啟發式算法。這類方法從生物進化、物理、化學等過程中受到啟發，得到一種解空間的搜索策略，因其搜索策略獨立于問題本身（problem independent），因此通用性強。元啟發式這類算法有兩個最本質的操作：①選擇操作（從當前種群中選出優秀的個體，選擇的策略有精英保留、輪盤賭、錦標賽等）；②改變操作（如交叉、變異、災變操作等，它們本質上都是從一個可行解改變為另一個可行解，用來擴大搜索范圍，避免陷入局部最優）。（詳見：元啟發式算法常用操作詳解：https://bbs.huaweicloud.com/blogs/195717）
啟發式算法
啟發式策略（heuristic）是一類在求解某個具體問題時，在可以接受的時間和空間內能給出其可行解（或近優解），但又不保證求得最優解（以及可行解與最優解的偏離）的策略的總稱。
許多啟發式算法是相當特殊的，它依賴于某個特定問題。啟發式策略在一個尋求最優解的過程中能夠根據個體或者全局的經驗來改變其搜索路徑，當尋求問題的最優解變得不可能或者很難完成時（e.g. NP-C問題），啟發式策略就是一個高效的獲得可行解（即近優解）的辦法。
啟發式算法包括：包括構造型方法、局部搜索算法、松弛方法、解空間縮減算法、貪婪策略、隨機化貪婪策略、近鄰策略、最大飽和度策略等。
元啟發式算法
元啟發式策略（Meta-heuristic）則不同，元啟發式策略通常是一個通用的啟發式策略，它們通常不借助于某種問題的特有條件，從而能夠運用于更廣泛的方面。元啟發式是啟發式策略的增強改進版，它是隨機算法與局部搜索算法相結合的產物?！霸笨梢岳斫鉃橐粋€哲學概念，大概是“事物的本原”。
元啟發式策略通常會對搜索過程提出一些要求，然后按照這些要求實現的啟發式算法便被稱為元啟發式算法。許多元啟發式算法都從自然界的一些隨機現象取得靈感（e.g. 模擬退火、遺傳算法、粒子群算法）?，F在元啟發式算法的重要研究方向在于防止搜索過早得陷入局部最優，已經有很多人做了相應的工作，例如禁忌搜索（tabu）和非改進轉移（模擬退火）。
元啟發式算法是相對于最優化算法提出來的，一個問題的最優化算法可以求得該問題的最優解，而元啟發式算法是一個基于直觀或經驗構造的算法，它可以在可接受的花費(指計算時間和空間)下給出問題的一個可行解(近優解)，并且該可行解與最優解的偏離程度不一定可以事先預計。
元啟發式算法(Meta-heuristic)是基于計算智能的機制求解復雜優化問題最優解或滿意解(近優解)的方法，有時也被稱為智能優化算法(Intelligent optimization algorithm)，智能優化通過對生物、物理、化學、社會、藝術等系統或領域中相關行為、功能、經驗、規則、作用機理的認識，揭示優化算法的設計原理，在特定問題特征的引導下提煉相應的特征模型，設計智能化的迭代搜索型優化算法。
常見的Meta-Heuristic Algorithms（有基于個體和基于群體兩類）：
一、基于個體（Single solution-based heuristics）
1、模擬退火（Simulated Annealing，SA）
2、禁忌搜索（Tabu Search，TS）
3、變鄰域搜索（Variable Neighborhood Search）
4、自適應大規模領域搜索（Adaptive Large Neighborhood Search）
二、基于群體（Population-based heuristics）
1、遺傳算法（Genetic Algorithm，GA）
2、蟻群優化算法（Ant Colony Optimization，ACO）
3、粒子群優化算法（Particle Swarm Optimization，PSO）
4、差分進化算法（Differential Evolution, DE）
4、人工蜂群算法（ABC）、人工魚群算法、狼群算法等
5、人工神經網絡算法（ANN）
另外還有：免疫算法、蛙跳算法、帝國競爭算法（Imperialist Competitive Algorithm，ICA）、和聲搜索算法、分布估計算法、Memetic算法、文化算法、灰狼優化算法、人工免疫算法、進化規劃、進化策略、候鳥優化算法、布谷鳥搜索算法、花朵授粉算法、引力搜索算法、化學反應優化算法、頭腦風暴優化算法（Brain Storm Optimization Algorithm，BSO）等等。
附：元啟發式算法時間表（部分）
What is the difference between heuristics and meta-heuristics?
- 啟發式算法和元啟發式算法，一般都是用來解決NP-H問題，目的是求得組合優化問題的近優解（可行解、滿意解），但不一定是最優解?！舅鼈兒妥顑灮惴ㄏ鄬?#xff0c;最優化算法是用來求得問題的最優解的。】
- 啟發式算法是 problem dependent（依賴于問題的，與問題有關）或者叫 problem specific（面向特定問題的，與特定問題有關），故適應面窄； 而元啟發式算法是problem independent（與問題無關的），元啟發法是與問題無關的技術，可以應用于廣泛的問題，適用范圍廣。
- 啟發式方法利用問題相關信息來找到特定問題的"足夠好"的解決方案，根據給定問題制定啟發式規則，故與該問題特性有關；而元啟發式方法則像設計模式一樣，是一般的算法思想，可以應用于各種各樣的問題,與問題無關。
- 復雜性方面，啟發式算法簡單，就是用簡單策略（如：貪婪策略、隨機化貪婪策略、近鄰策略、最大飽和度策略）構造可行集的過程。而元啟發式則是一種高層次的多個算法模塊的聚合算法。
有段英文可以讀讀，理解一下：
A locally optimal solution is better than all neighbouring solutions. A globally optimal solution is better than all solutions in the search space. A neighbourhood is a set of solutions that can be reached from the current solution by a simple operator. A neighbourhood is a subset of the search space. (局部最優解、全局最優解與鄰域的概念)
A heuristic is a rule of thumb method derived from human intuitions. For example, we can use the nearest neighbour heuristic to solve the TSP problem and use the maximal saturation degree heuristic to solve the graph colouring problem.(其次，我們可以利用啟發式算法搜索并得到一個局部最優解（不保證是全局最優解）)
Meta-heuristics are methods that orchestrate an interaction between local improvement procedures and higher-level strategies to create a process capable of escaping from the local optima and performing a robust search in the solution space. Single-point meta-heuristics include Simulated Annealing, Tabu Search, and Variable Neighbourhood Search. Population-based meta-heuristics include Genetic Algorithm, Ant Colony Optimization, and Particle Swarm Optimization.(最后，我們可以利用元啟發式算法更好地探索解空間，從而避免算法陷入局部最優)
多目標智能優化算法
多目標進化算法（Multi-Objective Evolutionary Algorithm，MOEA），如：增強多目標灰狼優化算法、多目標粒子群優化算法、多目標遺傳算法、NSGA-Ⅱ算法（即帶有精英保留策略的快速非支配多目標優化算法，是一種基于Pareto最優解的多目標優化算法，是多目標遺傳算法的一種）。
多目標優化算法，它主要針對同時優化多個目標（兩個及兩個以上）的優化問題，這方面比較經典的算法有NSGAII算法、MOEA/D算法以及人工免疫算法等。這部分內容的介紹已經在博客《[Evolutionary Algorithm] 進化算法簡介》進行了概要式的介紹，有興趣的博友可以進行參考（2015.12.13）-Poll的筆記。
模擬進化算法與傳統的精確算法（確定性算法）的區別
優化算法分類
所以說，你接觸的很多算法，既是仿生算法，又是啟發式算法，又是智能算法，這都對！只是分類方法不同而已。
算法介紹
帝國競爭算法（Imperialist Competitive Algorithm，ICA）
帝國競爭算法（ICA）是Atashpaz-Gargari和Lucas于2007年提出的一種基于帝國主義殖民競爭機制的進化算法，屬于社會啟發的隨機優化搜索方法。目前，ICA已被成功應用于多種優化問題中，如調度問題、分類問題和機械設計問題等。
帝國主義競爭算法，借鑒了人類歷史上政治社會殖民階段帝國主義國家之間的競爭、占領、吞并殖民殖民地國家從而成為帝國國家的演化，是一種全局性的優化算法。該算法把所有初始化的個體都稱作國家，按照國家勢力分成帝國主義國家及殖民地兩種，前者優勢大于后者。
其實，從另一個角度來看，ICA可以被認為是遺傳算法(GA)的社會對應物。ICA是基于人類社會進化的過程，而GA是基于物種的生物進化過程。二者其實有異曲同工之妙。
不過話說回來，大多數群體仿生類算法都有異曲同工之妙。
分支定界法（Branch and Bound, BB）
For instance, since the space of possible solutions is still too vast, a branch and bound type algorithm is proposed to further decimate the number of potential solutions to evaluate.
例如，由于可行解的參數空間很大，一種分支限界算法被用來減少需要考察的可行解的數目。
Branch and bound (BB or B&B) is an algorithm design paradigm for discrete and combinatorial optimization problems, as well as general real valued problems. A branch-and-bound algorithm consists of a systematic enumeration of candidate solutions by means of state space search: the set of candidate solutions is thought of as forming a rooted tree with the full set at the root. The algorithm explores branches of this tree, which represent subsets of the solution set. Before enumerating the candidate solutions of a branch, the branch is checked against upper and lower estimated bounds on the optimal solution, and is discarded if it cannot produce a better solution than the best one found so far by the algorithm.
NSGA-Ⅱ算法
NSGA（Non-dominated Sorting Genetic Algorithm，非支配排序遺傳算法）、NSGA-II（帶精英策略的快速非支配排序遺傳算法），都是基于遺傳算法的多目標優化算法，是基于pareto最優解討論的多目標優化。
NSGA-Ⅱ算法，即帶有精英保留策略的快速非支配多目標優化算法，是一種基于Pareto最優解的多目標優化算法。
NSGA-Ⅱ算法是進化算法中的一種，進化算法是在遺傳算法的基礎上改進而來的，所以，你得先弄懂遺傳算法是什么。
NSGA-Ⅱ是最流行的多目標遺傳算法之一，它降低了非劣排序遺傳算法的復雜性，具有運行速度快，解集的收斂性好的優點，成為其他多目標優化算法性能的基準。
NSGA-Ⅱ算法是 Srinivas 和 Deb 于 2000 年在 NSGA 的基礎上提出的，它比 NSGA算法更加優越：它采用了快速非支配排序算法，計算復雜度比 NSGA 大大的降低；采用了擁擠度和擁擠度比較算子，代替了需要指定的共享半徑 shareQ，并在快速排序后的同級比較中作為勝出標準，使準 Pareto 域中的個體能擴展到整個 Pareto 域，并均勻分布，保持了種群的多樣性；引入了精英策略，擴大了采樣空間，防止最佳個體的丟失，提高了算法的運算速度和魯棒性。
NSGA-Ⅱ就是在第一代非支配排序遺傳算法的基礎上改進而來，其改進主要是針對如上所述的三個方面：
這個算法是本人接觸科研學習實現的第一個算法，因此想在這里和大家分享一下心得。 講解的很詳細，讀個大概，有個思路和印象即可，不必深究。
site：https://blog.csdn.net/qq_40434430/article/details/82876572/
遺傳算法（Genetic Algorithm, GA）
遺傳算法（Genetic Algorithm，簡稱GA）是一種最基本的進化算法，它是模擬達爾文生物進化理論的一種優化模型，最早由J.Holland教授于1975年提出。
遺傳算法中種群分每個個體都是解空間上的一個可行解，通過模擬生物的進化過程，從而在解空間內搜索最優解。
禁忌搜索算法（Tabu Search，TS）
遺傳算法是具有全局搜索能力的算法，但是傳統遺傳算法求解調度問題并不是很成功，主要原因在于它的局部搜索能力較差，且容易早熟收斂。而禁忌搜索(Tabu Search, TS)是一種優秀的局部搜索算法。因此，可以結合遺傳算法（GA）和禁忌搜索算法（TS）兩者的優點，將“適者生存”的遺傳準則嵌入到多起點的禁忌搜索算法中，構成混合遺傳禁忌搜索算法(GATS)。
由于遺傳算法和禁忌搜索算法具有互補的特性，因此混合遺傳禁忌搜索算法（GATS）在性能上能夠超越它們單獨使用時的性能。
文化基因算法（Memetic Algorithm，MA）
文化基因（Meme）的概念是由Hawkins于1976年提出的，Pablo Moscato于1989年提出了Memetic Algorithm。Memetic Algorithm，是基于群體的計算智能方法與局部搜索相結合的一類算法的總稱。文化基因算法的簡單介紹。
文化基因算法（Memetic Algorithm，簡稱MA），也被稱為是“密母算法”（Meme），它是由Moscato在1989年提出的。文化基因算法MA是一種基于種群的全局搜索和基于個體的局部啟發式搜索的結合體，它的本質可以理解為：
MA= GA + Local Search
即MA算法實質上是為遺傳算法（全局搜索算法）加上一個局部搜索（Local Search）算子。局部搜索算子可以根據不同的策略進行設計，比如常用的爬山機制、模擬退火、貪婪機制、禁忌搜索等。
Pablo Moscato認為：在遺傳算法（GA）中，變異操作可以看作是含有一定噪聲的爬山搜索，實際上模擬遺傳編碼和自然選擇的過程不應包含變異操作，因為在文化進化的過程中，在眾多的隨機變化步驟中得到一個正確的、可提高整體性能的一步進展是非常困難的，只有此領域的擁有足夠的專業知識的精通者們，才有可能創造新的進展，并且這樣的事情發生的頻率是很低的。 因此，文化基因的傳播過程應是嚴格復制的，若要發生變異，那么每一步的變異都需要有大量的專業知識支撐，而每一步的變異都應帶來進展而不是混亂，這就是為什么我們觀察到的文化進化速度要比生物進化速度快得多的原因。 對應于模擬生物進化過程的遺傳算法，Moscato提出了模擬文化進化過程的文化基因算法，文化基因算法用局部啟發式搜索來模擬由大量專業知識支撐的變異過程。因此說，文化基因算法是一種基于種群的全局搜索和基于個體的局部啟發式搜索的結合體。
文化基因算法的這種全局搜索和局部搜索的結合機制，使其搜索效率在某些問題領域比傳統遺傳算法快幾個數量級，可應用于廣泛的問題領域并得到滿意的結果。 很多人將文化基因算法看作混合遺傳算法、 遺傳局部搜索或是拉馬克式進化算法。實際上，文化基因算法提出的只是一種框架、 是一個概念，在這個框架下，采用不同的搜索策略可以構成不同的文化基因算法。如全局搜索策略可以采用遺傳算法、 進化策略、 進化規劃等，局部搜索策略可以采用爬山搜索、模擬退火、貪婪算法、禁忌搜索、導引式局部搜索等。 這種全局與局部的混合搜索機制顯然要比單純在普通個體間搜索的進化效率高得多。
機器學習中的最優化模型
我們每個人都會在我們的生活或者工作中遇到各種各樣的最優化問題，比如每個企業和個人都要考慮的一個問題“在一定成本下，如何使利潤最大化”等。最優化方法是一種數學方法，它是研究在給定約束之下如何尋求某些因素(的量)，以使某一(或某些)指標達到最優的一些學科的總稱。隨著學習的深入，博主越來越發現最優化方法的重要性，學習和工作中遇到的大多問題都可以建模成一種最優化模型進行求解，比如我們現在學習的機器學習算法，大部分的機器學習算法的本質都是建立優化模型，通過最優化方法對目標函數（或損失函數）進行優化，從而訓練出最好的模型。常見的最優化方法有梯度下降法、牛頓法和擬牛頓法、共軛梯度法、最速下降法等等。
梯度下降法（Gradient Descent）
牛頓法和擬牛頓法（Newton’s method & Quasi-Newton Methods）
共軛梯度法（Conjugate Gradient）
拉格朗日乘數法（Lagrange Multiplier Method）
詳見：[Math & Algorithm] 拉格朗日乘數法
總結
- 上一篇： 板绘萌新拿到数位板之后，不知道先做什么？
- 下一篇： SM2算法概述