最近聽ES聽的有點多，想著了解一下。
從幾篇博客里摘抄了筆記：
適合初學(xué)者
帶了實現(xiàn)代碼
CMA-ES

這兩個算法都是用進(jìn)化理論來解決復(fù)雜的問題. 遺傳算法是進(jìn)化算法的一個分支. 它將達(dá)爾文的進(jìn)化理論搬進(jìn)了計算機.

遺傳算法

遺傳算法（Genetic Algorithm, GA）起源于對生物系統(tǒng)所進(jìn)行的計算機模擬研究。它是模仿自然界生物進(jìn)化機制發(fā)展起來的隨機全局搜索和優(yōu)化方法，借鑒了達(dá)爾文的進(jìn)化論和孟德爾的遺傳學(xué)說。其本質(zhì)是一種高效、并行、全局搜索的方法，能在搜索過程中自動獲取和積累有關(guān)搜索空間的知識，并自適應(yīng)地控制搜索過程以求得最佳解。

相關(guān)術(shù)語

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

應(yīng)用
尋路問題
8數(shù)碼問題
囚犯困境
動作控制
找圓心問題（在一個不規(guī)則的多邊形中，尋找一個包含在該多邊形內(nèi)的最大圓圈的圓心）
TSP問題
生產(chǎn)調(diào)度問題
人工生命模擬

GA簡介

• 遺傳算法中每一條染色體，對應(yīng)著遺傳算法的一個解決方案。一般我們用適應(yīng)性函數(shù)（fitness function）來衡量這個解決方案的優(yōu)劣。
• 所以從一個基因組到其解的適應(yīng)度形成一個映射。可以把遺傳算法的過程看作是一個在多元函數(shù)里面求最優(yōu)解的過程（多維曲面求極值）。

問題舉例
一元函數(shù)求最大值：

image.png

我們把函數(shù)曲線理解成一個一個山峰和山谷組成的山脈?？梢栽O(shè)想所得到的每一個解就是一只袋鼠，我們希望它們不斷的向著更高處跳去，直到跳到最高的山峰（盡管袋鼠本身不見得愿意那么做）。所以求最大值的過程就轉(zhuǎn)化成一個“袋鼠跳”的過程。

下面簡單介紹“袋鼠跳”的幾種方式。

1. 爬山法（類似梯度法）：

• 從搜索空間中隨機產(chǎn)生鄰近的點，從中選擇對應(yīng)解最優(yōu)的個體，替換原來的個體，不斷重復(fù)上述過程。
• 因為爬山法只對“鄰近”的點作比較，所以目光比較“短淺”，常常只能收斂到離開初始位置比較近的局部最優(yōu)解上面。

2. 模擬退火：

• 這個方法來自金屬熱加工過程的啟發(fā)。在金屬熱加工過程中，當(dāng)金屬的溫度超過它的熔點（Melting Point）時，原子就會激烈地隨機運動。
• 與所有的其它的物理系統(tǒng)相類似，原子的這種運動趨向于尋找其能量的極小狀態(tài)。在這個能量的變遷過程中，開始時，溫度非常高， 使得原子具有很高的能量。隨著溫度不斷降低，金屬逐漸冷卻，金屬中的原子的能量就越來越小，最后達(dá)到所有可能的最低點。
• 利用模擬退火的時候，讓算法從較大的跳躍開始，使到它有足夠的“能量”逃離可能“路過”的局部最優(yōu)解而不至于限制在其中，當(dāng)它停在全局最優(yōu)解附近的時候，逐漸的減小跳躍量，以便使其“落腳 ”到全局最優(yōu)解上。
• 就是說一開始步長大一些，經(jīng)過一些step之后慢慢縮小步長，就有可能跳出局部極值。

3. 遺傳算法：

• 模擬物競天擇的生物進(jìn)化過程，通過維護(hù)一個潛在解的群體執(zhí)行了多方向的搜索，并支持這些方向上的信息構(gòu)成和交換。
• 是以面為單位的搜索，比以點為單位的搜索，更能發(fā)現(xiàn)全局最優(yōu)解。（在遺傳算法中，有很多袋鼠，它們降落到喜瑪拉雅山脈的任意地方。這些袋鼠并不知道它們的任務(wù)是尋找珠穆朗瑪峰。但每過幾年，就在一些海拔高度較低的地方射殺一些袋鼠，并希望存活下來的袋鼠是多產(chǎn)的，在它們所處的地方生兒育女。過了許多年之后，只有爬的越高的袋鼠才能存活的越久，自然就找到的極值）

所以我們總結(jié)出遺傳算法的一般步驟：

開始循環(huán)直至找到滿意的解。
1.評估每條染色體所對應(yīng)個體的適應(yīng)度。
2.遵照適應(yīng)度越高，選擇概率越大的原則，從種群中選擇兩個個體作為父方和母方。
3.抽取父母雙方的染色體，進(jìn)行交叉，產(chǎn)生子代。
4.對子代的染色體進(jìn)行變異。
5.重復(fù)2，3，4步驟，直到新種群的產(chǎn)生。
結(jié)束循環(huán)。

遺傳算法細(xì)節(jié)

編制袋鼠的染色體----基因的編碼方式
（1）二進(jìn)制編碼法：010010011011011110111110
（2）浮點數(shù)編碼法：1.2 –3.3 – 2.0 –5.4 – 2.7 – 4.3
（3）符號編碼法
重要特征：袋鼠的位置
評估標(biāo)準(zhǔn)：海拔高度
建立二進(jìn)制編碼到一個實數(shù)的映射：有點類似模數(shù)轉(zhuǎn)換
物競天擇－－適應(yīng)性評分與及選擇函數(shù)：
（1）物競――適應(yīng)度函數(shù)（fitness function）：生物相互間的搏斗與及生物與客觀環(huán)境的搏斗過程。直接用袋鼠的海拔高度作為它們的適應(yīng)性評分。
（2）天擇――選擇函數(shù)（selection）：自然界中，越適應(yīng)的個體就越有可能繁殖后代。從概率上體現(xiàn)。
（3）遺傳變異――基因重組（交叉）與基因突變。二進(jìn)制編碼的基因交換過程非常類似高中生物中所講的同源染色體的聯(lián)會過程，浮點數(shù)編碼也類似，如果對于單個浮點數(shù)的基因交叉，就有其它不同的重組方式了，比如中間重組：比如5.5和6交叉，產(chǎn)生5.7，5.6?；蛲蛔儯憾M(jìn)制編碼是01交換，浮點數(shù)編碼一般是對原來的浮點數(shù)增加或者減少一個小隨機數(shù)

1. 選擇的作用：優(yōu)勝劣汰，適者生存；
2. 交叉的作用：保證種群的穩(wěn)定性，朝著最優(yōu)解的方向進(jìn)化；
3. 變異的作用：保證種群的多樣性，避免交叉可能產(chǎn)生的局部收斂。

微生物遺傳算法（Microbial GA）

“升級版GA”，由Inman Harvey于2009年提出，原文:《The Microbial Genetic Algorithm》

問題
解決遺傳算法中，無法有效保留“好父母”的問題(Elitism)：分析GA可是無論父母多么優(yōu)秀，都不會被保留，只能將各自基因的一部分進(jìn)行重組，但是重組后的子代并不會一定優(yōu)于父母。

改進(jìn)
1.把種群中表現(xiàn)好的基因不做任何改變放入子代中
2.只對表現(xiàn)較差的基因序列進(jìn)行交叉/變異處理
3.交叉方法：表現(xiàn)較差的在表現(xiàn)較好的基因序列中抽取一部分替換進(jìn)來
4.變異方法：只在表現(xiàn)較差的基因序列中挑選變異點
注：表現(xiàn)好壞由fitness的得分決定

做法
1.生成初始種群
2.在初始種群中隨機抽取兩個基因序列A/B，對比fitness（假定A的fitness值高）
3.從A中截取部分基因序列替換掉B中對應(yīng)位置
4.隨機在B中抽取位置，進(jìn)行變異
5.將A與處理后的B‘放回種群中
6.自定義每一代進(jìn)行多少次抽取/放回操作

進(jìn)化策略（Evolution Strategy）

與遺傳算法的相同之處：
都是利用進(jìn)化理論進(jìn)行優(yōu)化，即利用遺傳信息一代代傳承變異適者生存，從而得到最優(yōu)解。

與遺傳算法的不同之處：
1.DNA序列采用實數(shù)編碼，而非0-1二進(jìn)制碼

2.變異時無法進(jìn)行簡單的0-1互換，思考：實數(shù)值該怎么變？隨機？
變異思路：為DNA序列上的每一個實數(shù)值添加變異強度。根據(jù)這個變異強度決定DNA序列上的實數(shù)值該變成多少

3.編碼：
由第2點可知，進(jìn)化策略在編碼時，不僅要有表示解決方案的實數(shù)編碼鏈A1，還得有一條表示每個實屬值對應(yīng)的變異強度值組成的鏈A2（也就是說，遺傳給后代的信息有兩種）

4.交叉：
兩條鏈都要交叉，即A1與B1交叉形成表示子代解決方案的C1鏈，A2與B2交叉形成表示C1鏈對應(yīng)位置實數(shù)值變異強度的C2鏈（父：A，母：B，子：C）

5.C1鏈上值的變異方法：
將C1鏈上的值看作正態(tài)分布的均值μ;
將C2鏈上變異強度值看作標(biāo)準(zhǔn)差σ;
用正態(tài)分布產(chǎn)生一個與C1鏈上選定位置相近的數(shù)，進(jìn)行替換;

6.C2鏈上值的變異方法：
因為隨著不斷遺傳迭代，種群中個體1號鏈的值不斷逼近最優(yōu)解，變異的強度也應(yīng)當(dāng)不斷減小。所以也需要根據(jù)需求自定義2號鏈的變異方法。

7.選擇：
將生成的孩子加入父代中，形成一個包含兩代DNA的種群U;
對U種群中每個DNA序列的1號鏈（表示解決方案）進(jìn)行fitness計算（打分），并根據(jù)分值從大到小排列（用U‘表示排列后的混合種群）;
截取U’中的分值高的前n位（n表示一代種群中的個體數(shù)目）形成新種群;

協(xié)方差自適應(yīng)調(diào)整的進(jìn)化策略（CMA-ES）

• 簡介
  （1）協(xié)方差自適應(yīng)調(diào)整的進(jìn)化策略(Covariance Matrix Adaptation Evolution Strategy, CMA-ES)是最有名，應(yīng)用最多，性能最好的ES之一
  （2）在中等規(guī)模（變量個數(shù)大約在 3-300范圍內(nèi)）的復(fù)雜優(yōu)化問題上具有很好的效果。
  （3）是Google Vizier: A Service for Black-Box Optimization 包含的四種用于調(diào)hyper-parameter 的方法之一。

• 幾個應(yīng)用文章
  （1）Path Integral Policy Improvement with Covariance Matrix Adaptation, ICML, 2012.
  （2）Optimizing Walking Controllers for Uncertain Inputs and Environments, ACM Transactions on Graphics 29. 4 (2010)
  （3）Flexible Muscle-Based Locomotion for Bipedal Creatures ， ACM Transactions on Graphics 32.6 (2013)
  （4）在強化學(xué)習(xí)和不確定環(huán)境下的行走控制取得了極好的效果。視頻2013年 Flexible Muscle-Based Locomotion for Bipedal Creatures

• 基本特點
  （1）無梯度優(yōu)化，不使用梯度信息,
  （2）局部搜索中無梯度算法通常比梯度算法慢，通常需要O(n)倍的評估,
  （3）在復(fù)雜優(yōu)化問題non-separable, ill-conditioned, or rugged/multi-modal 上表現(xiàn)良好。

• 算法步驟：核心想法是通過對正態(tài)分布N(mt, θt2Ct)中協(xié)方差矩陣C的調(diào)整來處理變量之間的依賴關(guān)系和scaling。分成以下三步：
  （1）采樣產(chǎn)生新解；
  （2）計算目標(biāo)函數(shù)值；
  （3）更新分布參數(shù) mt, θt，Ct
  ES算法設(shè)計的核心就是如何對這些參數(shù)進(jìn)行調(diào)整，尤其是步長參數(shù)和協(xié)方差矩陣的調(diào)整，以達(dá)到盡可能好的搜索效果。對這些參數(shù)的調(diào)整在ES算法的收斂速率方面有非常重要的影響。CMA-ES調(diào)整參數(shù)的基本思路是，調(diào)整參數(shù)使得產(chǎn)生好解的概率逐漸增大（沿好的搜索方向進(jìn)行搜索的概率增大）。

CMA-ES搜索過程