演算法筆記答案

❶ 優化演算法筆記（八）人工蜂群演算法

（以下描述，均不是學術用語，僅供大家快樂的閱讀）
工蜂群演算法（Artificial Bee Colony Algorithm，ABC）是一種模仿蜜蜂采蜜機理而產生的群智能優化演算法。其原理相對復雜，但實現較為簡單，在許多領域中都有研究和應用。
人工蜂群演算法中，每一個蜜源的位置代表了待求問題的一個可行解。蜂群分為采蜜蜂、觀察蜂和偵查蜂。采蜜蜂與蜜源對應，一個采蜜蜂對應一個蜜源。觀察蜂則會根據采蜜蜂分享的蜜源相關信息選擇跟隨哪個采蜜蜂去相應的蜜源，同時該觀察蜂將轉變為偵查蜂。偵查蜂則自由的搜索新的蜜源。每一個蜜源都有開採的限制次數，當一個蜜源被采蜜多次而達到開采限制次數時，在寬檔該蜜源采蜜的采蜜蜂將轉變為偵查蜂。每個偵查蜂將隨機尋找一個新蜜源進行開采，並轉變成為采蜜蜂。

下面是我的實現方式（我的答案）：
1． 三種蜜蜂之間可以相互轉化。
采蜜蜂->觀察蜂：有觀察蜂在采蜜過程中發現了比當前采蜜蜂更好的蜜源，則采蜜蜂放棄當前蜜源轉而變成觀察蜂跟隨優質蜜源，同時該觀察蜂轉變為采蜜蜂。
采蜜蜂->觀察蜂：當該采蜜蜂所發現的蜜源被開采完後，它會轉變為觀察蜂去跟隨其他采蜜蜂。
采蜜蜂->偵查蜂：當所有的采蜜蜂發現的蜜源都被開采完後，采蜜蜂將會變為偵查蜂，觀察蜂也會變成偵查蜂，因為大家都無蜜可采。
偵查蜂->采蜜蜂、觀察蜂：偵查蜂隨機搜索蜜源，選擇較好的數個蜜源位置的蜜蜂為采蜜蜂，其他蜜蜂為觀察蜂。

2.蜜源的數量上限
蜜源的數量上限等於采蜜蜂的數量上限。初始化時所有蜜蜂都是偵查蜂，在這些偵查蜂所搜索到的蜜源中選出數個較優的蜜源，發現這些蜜源的偵查蜂變為采蜜蜂，其他蜜蜂變為觀察蜂。直到所有的蜜源都被開采完之前，蜜源的數量不會增加，因為這個過程中沒有產生偵查蜂緩配。所有的蜜源都被開采完後，所有的蜜蜂再次全部轉化為偵查蜂，新的一輪蜜源搜索開始。也可以在一個蜜源開采完時馬上產生一個新的蜜源補充，保證在整個開采過程中蜜源數量恆定不變。

蜜源的開采實際上就是觀察蜂跟隨采蜜蜂飛向蜜源的過程。得到的下一代的位置公式如下：

表示第i只觀察蜂在第t代時隨機選擇第r只採蜜蜂飛行一段距離，其中R為（-1，1）的隨機數。

一隻觀察蜂在一次迭代過程中只能選擇一隻采蜜蜂跟隨，它需要從眾多的采蜜蜂中選擇一隻來進行跟隨。觀察蜂選擇的策略很簡單，隨機跟隨一隻采蜜蜂，該采蜜蜂發現的蜜源越優，則選擇它的概率越大。
是不是很像輪盤賭，對，這就是輪盤賭，同時我們也可以稍作修改，比如將勤勞的小蜜蜂改為懶惰的小蜜蜂，小蜜蜂會根據蜜源的優劣和距離以及開采程度等因素綜合來選擇跟隨哪只採蜜蜂（雖然影響不大，但聊勝於無）。
忘記了輪盤賭的小夥伴可以看一下 優化演算法筆記（六）遺傳演算法 。
下面是我的人工蜂群演算法流程圖

又到了實驗環節，參數實驗較多，慎哪亂全部給出將會佔用太多篇幅，僅將結果進行匯總展示。

實驗1：參數如下

上圖分別為采蜜蜂上限為10%總數和50%總數的情況，可以看出當采蜜蜂上限為10%總群數時，種群收斂的速度較快，但是到最後有一個點死活不動，這是因為該點作為一個蜜源，但由於適應度值太差，使用輪盤賭被選擇到的概率太小從而沒有得到更佳的蜜源位置，而因未開采完，采蜜蜂又不能放棄該蜜源。
看了看采蜜蜂上限為50%總群數時的圖，發現也有幾個點不動的狀態，可以看出，這時不動的點的數量明顯多於上限為10%總數的圖，原因很簡單，采蜜蜂太多，「先富」的人太多，而「後富」的人較少，沒有帶動「後富者」的「先富者」也得不到發展。
看看結果

嗯，感覺結果並沒有什麼差別，可能由於問題較簡單，迭代次數較少，無法體現出采蜜蜂數對於結果的影響，也可能由於蜜源的搜索次數為60較大，總群一共只能對最多20*50/60=16個蜜源進行搜索。我們將最大迭代次數調大至200代再看看結果

當最大迭代次數為200時，人工蜂群演算法的結果如上圖，我們可以明顯的看出，隨著采蜜蜂上限的上升，演算法結果的精度在不斷的下降，這也印證了之前的結果，由於蜜源搜索次數較大（即搜索深度較深）采蜜蜂數量越多（搜索廣度越多），結果的精度越低。不過影響也不算太大，下面我們再來看看蜜源最大開采次數對結果的影響。
實驗2：參數如下

上圖分別是蜜源開采限度為1,20和4000的實驗。
當蜜源開采上限為1時，即一個蜜源只能被開采一次，即此時的人工蜂群演算法只有偵查蜂隨機搜索的過程，沒有觀察蜂跟隨采蜜蜂的過程，可以看出圖中的蜜蜂一直在不斷的隨機出現在新位置不會向某個點收斂。
當蜜源開采上限為20時，我們可以看到此時種群中的蜜蜂都會向一個點飛行。在一段時間內，有數個點一動不動，這些點可能就是采蜜蜂發現的位置不怎麼好的蜜源，但是在幾次迭代之後，它們仍會被觀察蜂開采，從而更新位置，蜜源開采上限越高，它們停頓的代數也會越長。在所有蜜蜂都收斂於一個點之後，我們可以看到仍會不斷的出現其他的隨機點，這些點是偵查蜂進行隨機搜索產生的新的蜜源位置，這些是人工蜂群演算法跳出局部最優能力的體現。
當蜜源開采上限為4000時，即不會出現偵查蜂的搜索過程，觀察蜂只會開采初始化時出現的蜜源而不會采蜜蜂不會有新的蜜源產生，可以看出在蜂群收斂後沒有出現新的蜜源位置。

看看最終結果，我們發現，當蜜源開采上線大於1時的結果提升，但是好像開采上限為5時結果明顯好於開采次數上限為其他的結果，而且隨著開采次數不斷上升，結果在不斷的變差。為什麼會出現這樣的結果呢？原因可能還是因為問題較為簡單，在5次開採的限度內，觀察蜂已經能找到更好的蜜源進行開采，當問題較為復雜時，我們無法知曉開采發現新蜜源的難度，蜜源開采上限應該取一個相對較大的值。當蜜源開采限度為4000時,即一個蜜源不可能被開采完(開采次數為20(種群數)*200(迭代次數)),搜索的深度有了但是其結果反而不如開采限度為幾次幾十次來的好,而且這樣不會有偵查蜂隨機搜索的過程,失去了跳出局部最優的能力。
我們應該如何選擇蜜源的最大開采次數限制呢？其實，沒有最佳的開采次數限制，當適應度函數較為簡單時，開采次數較小時能得到比較好的結果，但是適應度函數較復雜時，經過試驗，得出的結果遠差於開采次數較大時。當然，前面就說過，適應度函數是一個黑盒模型，我們無法判斷問題的難易。那麼我們應該選擇一個適中的值，個人的選擇是種群數的0.5倍到總群數的2倍作為蜜源的最大開采次數，這樣可以保證極端情況下，1-2個迭代周期內小蜜蜂們能將一個蜜源開采完。

人工蜂群演算法算是一個困擾我比較長時間的演算法，幾年時間里，我根據文獻實現的人工蜂群演算法都有數十種，只能說人工蜂群演算法的描述太過模糊，或者說太過抽象，研究者怎麼實現都說的通。但是通過實現多次之後發現雖然實現細節大不相同，但效果相差不多，所以我們可以認為人工蜂群演算法的穩定性比較強，只要實現其主要思想即可，細節對於結果的影響不太大。
對於人工蜂群演算法影響最大的因素還是蜜源的開采次數限制，開采次數限制越大，對同一蜜源的開發力度越大，但是分配給其他蜜源的搜索力度會相對減少，也會降低蜂群演算法的跳出局部最優能力。可以動態修改蜜源的開采次數限制來實現對演算法的改進，不過效果不顯著。
其次對於人工蜂群演算法影響是三類蜜蜂的搜索行為，我們可以重新設計蜂群的搜索方式來對演算法進行改進，比如采蜜蜂在開采蜜源時是隨機飛向其他蜜源，而觀察蜂向所選的蜜源靠近。這樣改進有一定效果但是在高維問題上效果仍不明顯。
以下指標純屬個人yy,僅供參考

目錄
上一篇 優化演算法筆記（七）差分進化演算法
下一篇 優化演算法筆記（九）杜鵑搜索演算法

優化演算法matlab實現（八）人工蜂群演算法matlab實現

❷ 優化演算法筆記（六）遺傳演算法

遺傳演算法(Genetic Algorithms，GA)是一種粗衡模擬自然中生物的遺傳、進化以適應環境的智能演算法。由於其演算法流程簡單，參數較少優化速度較快，效果較好，在圖像處理、函數優化、信號處理、模式識別等領域有著廣泛的應用。
在遺傳演算法（GA）中，每一個待求問題的候選解被抽象成為種群中一個個體的基因。種群中個體基因的好壞由表示個體基因的候選解在待求問題中的所的得值來評判。種群中的個體通過與其他個體交叉產生下一代，每一代中個體均只進行一次交叉。兩個進行交叉的個體有一定幾率交換一個或者多個對應位的基因來產生新的後代。每個後代都有一定的概率發生變異。發生變異的個體的某一位或某幾位基因會變異成其他值。最終將以個體的適應度值為概率選取個體保留至下一代。

遺傳演算法啟發於生物的繁殖與dna的重組，本次的主角選什麼呢？還是根據大家熟悉的孟德爾遺傳規律選豌豆吧，選動物的話又會有人疑車，還是植物比較好，本次的主角就是它了。

遺傳演算法包含三個操作（運算元）：交叉，變異和選擇操作。下面我們將詳細介紹這三個操作。
大多數生物的遺傳信息都儲存在DNA，一種雙螺旋結構的復雜有機化合物。其含氮鹼基為腺嘌呤、鳥嘌呤、胞嘧啶及胸腺嘧啶。

表格中表示了一個有10個基因的個體，它們每一個基因的值為0或者1。

生物的有性生殖一般伴隨著基因的重組。遺傳演算法中父輩和母輩個體產生子代個體的過程稱為交叉。

表中給出了兩個豌豆的基因，它們均有10個等位基因（即編號相同的基因）。
遺傳演算法的交叉過程會在兩個個體中隨機選擇1位或者n位基因進行交叉，即這兩個個體交換等位基因。
如，A豌豆和B豌豆在第6位基因上進行交叉，則其結果如下

當兩個個體交叉的等位基因相同時，交叉過程也有可能沒有產生新慧衡的個體，如交叉A豌豆和B豌豆的第2位基因時，交叉操作並沒有產生新的基因。

一般的會給群體設定一個交叉率，crossRate，表示會在群體中選取一定比例的個體進行交叉，交叉率相對較大，一般取值為0.8。

基因的變異是生物進化的一個主要因素。
遺傳演算法中變異操作相對簡單，只需要將一個隨機位基因的值修改就行了，因為其值只為0或1，那麼當基因為0時，變異操作會將其值設為1，當基因值為1時，變異操作會將其值設為0。

上圖表示了A豌豆第3位基因變異後的基因編碼。
與交叉率相似，變異操作也有變異率，alterRate，但是變異率會遠低於交叉率，否則會產生大量的隨機基因。一般變異率為0.05。

選擇操作是遺傳演算法中的一個關鍵操作，它的主要作用就是根據一定的策略隨機選擇個體保留至下一代。適應度越優的岩碧做個體被保留至下一代的概率越大。
實現上，我們經常使用「輪盤賭」來隨機選擇保留下哪個個體。

假設有4個豌豆A、B、C、D，它們的適應度值如下：

適應度值越大越好，則它們組成的輪盤如下圖：

但由於輪盤賭選擇是一個隨機選擇過程，A、B、C、D進行輪盤賭選擇後產生的下一代也有可能出現A、A、A、A的情況，即雖然有些個體的適應度值不好，但是運氣不錯，也被選擇留到了下一代。
遺產演算法的三個主要操作介紹完了，下面我們來看看遺傳演算法的總體流程：

前面我們說了遺傳演算法的流程及各個操作，那麼對於實際的問題我們應該如何將其編碼為基因呢？

對於計算機來所所有的數據都使用二進制數據進行存放，如float類型和double類型的數據。
float類型的數據將保存為32位的二進制數據：1bit（符號位） 8bits（指數位） 23bits（尾數位）
如-1.234567f，表示為二進制位

Double類型的數據將保存為64位的二進制數據：1bit（符號位） 11bits（指數位） 53bits（尾數位）
如-1.234567d，表示為二進制為

可以看出同樣的數值不同的精度在計算機中存儲的內容也不相同。之前的適應度函數 ，由於有兩個double類型的參數，故其進行遺傳演算法基因編碼時，將有128位基因。
雖然基因數較多，但好在每個基因都是0或者1，交叉及變異操作非常簡單。

相比二進制編碼，十進制編碼的基因長度更短，適應度函數 有兩個輸入參數，那麼一個個體就有2個基因，但其交叉、變異操作相對復雜。
交叉操作
方案1：將一個基因作為一個整體，交換兩個個體的等位基因。
交換前

交換第1位基因後

方案2：將兩個個體的等位基因作為一個整體，使其和不變，但是值隨機
交換前

交換第1位基因後

假設A、B豌豆的第一位基因的和為40，即 ,第一位基因的取值范圍為0-30，那麼A、B豌豆的第一位基因的取值范圍為[10,30],即 為[0,30]的隨機數， 。
變異操作，將隨機的一位基因設置為該基因取值范圍內的隨機數即可。

這個過程說起來簡單但其實現並不容易。

我們要將它們的值映射到一個軸上才能進行隨機選擇，畢竟我們無法去繪制一個輪盤來模擬這個過程

如圖，將ABCD根據其值按順序排列，取[0,10]內的隨機數r，若r在[0,1]內則選擇A,在(1,3]內則選擇B,在(3,6]內則選擇C,在(6,10]則選擇D。
當然這仍然會有問題，即當D>>A、B、C時，假如它們的值分布如下

那麼顯然，選D的概率明顯大於其他，根據輪盤賭的選擇，下一代極有可能全是D的後代有沒有辦法均衡一下呢？
首先我想到了一個函數，

不要問我為什麼我不知道什麼是神經什麼網路的，什麼softmax、cnn統統沒聽說過。

這樣一來，它們之間的差距沒有之前那麼大了，只要個體適應度值在均值以上那麼它被保留至下一代的概率會相對較大，當然這樣縮小了個體之間的差距，對真正優秀的個體來說不太公平，相對應，我們可以在每次選擇過程中保留當前的最優個體到下一代，不用參與輪盤賭這個殘酷的淘汰過程。

最令人高興的環節到了，又可以愉快的湊字數了。

由於遺傳演算法的收斂速度實在是太慢，區區50代，幾乎得不到好的結果，so我們把它的最大迭代次數放寬到200代。

使用二進制編碼來進行求解
參數如下：

求解過程如上圖，可以看出基因收斂的很快，在接近20代時就圖中就只剩一個點了，之後的點大概是根據變異操作產生。看一下最後的結果。

可以看出最好的結果已經得到了最優解，但是10次實驗的最差值和平均值都差的令人發指。為什麼會這樣呢？

問題出在二進制編碼上，由於double類型的編碼有11位指數位和52位小數位，這會導致交叉、變異操作選到指數位和小數位的概率不均衡，在小數位上的修改對結果的影響太小而對指數為的修改對結果的影響太大，
如-1.234567d，表示為二進制為

對指數為第5位進行變異操作後的結果為-2.8744502924382686E-10，而對小數位第5為進行變異操作後的結果為-1.218942。可以看出這兩部分對數值結果的影響太不均衡，得出較好的結果時大概率是指數位與解非常相近，否則很難得出好的結果，就像上面的最差值和均值一樣。
所以使用上面的二進制編碼不是一個好的基因編碼方式，因此在下面的實驗中，將使用十進制來進行試驗。

使用:十進制編碼來進行求解
參數如下：

我們可以看到直到40代時，所有的個體才收束到一點，但隨後仍不斷的新的個體出現。我們發現再後面的新粒子總是在同一水平線或者豎直線上，因為交叉操作直接交換了兩個個體的基因，那麼他們會相互交換x坐標或者y坐標，導致新個體看起來像在一條直線上。
我們來看看這次的結果。

這次最優值沒有得到最優解，但是最差值沒有二進制那麼差，雖然也不容樂觀。使用交換基因的方式來進行交叉操作的搜索能力不足，加之輪盤賭的選擇會有很大概率選擇最優個體，個體總出現在矩形的邊上。
下面我們先改變輪盤賭的選擇策略，使用上面的sigmod函數方案，並且保留最優個體至下一代。

使用:十進制編碼來進行求解
參數如下：

看圖好像跟之前的沒什麼區別，讓我們們看看最終的結果：

可以看出，最優值沒有什麼變化，但是最差值和平均值有了較大的提升，說明該輪盤賭方案使演算法的魯棒性有了較大的提升。在每次保留最優個體的情況下，對於其他的個體的選擇概率相對平均，sigmod函數使得即使適應度函數值相差不太大的個體被選到的概率相近，增加了基因的多樣性。

使用:十進制編碼來進行求解，改變交叉方案，保持兩個個體等位基因和不變的情況下隨機賦值。
參數如下：

上圖可以看出該方案與之前有明顯的不同，在整個過程中，個體始終遍布整個搜索空間，雖然新產生的個體大多還是集中在一個十字架型的位置上，但其他位置的個體比之前的方案要多。
看看結果，

這次的結果明顯好於之前的所有方案，但仍可以看出，十進制的遺傳演算法的精度不高，只能找到最優解的附近，也有可能是演算法的收斂速度實在太慢，還沒有收斂到最優解。

遺傳演算法的探究到此也告一段落，在研究遺傳演算法時總有一種力不從心的感覺，問題可能在於遺傳演算法只提出了一個大致的核心思想，其他的實現細節都需要自己去思考，而每個人的思維都不一樣，一萬個人能寫出一萬種遺傳演算法，其實不僅是遺傳演算法，後面的很多演算法都是如此。
為什麼沒有對遺傳演算法的參數進行調優，因為遺傳演算法的參數過於簡單，對結果的影響的可解釋性較強，意義明顯，實驗的意義不大。

遺傳演算法由於是模仿了生物的進化過程，因此我感覺它的求解速度非常的慢，而且進化出來的結果不一定是最適應環境的，就像人的闌尾、視網膜結構等，雖然不是最佳的選擇但是也被保留到了今天。生物的進化的隨機性較大，要不是恐龍的滅絕，也不會有人類的統治，要不是人類有兩只手，每隻手有5根手指，也不會產生10進制。
以下指標純屬個人yy,僅供參考

目錄
上一篇 優化演算法筆記（五）粒子群演算法（3）
下一篇 優化演算法筆記（七）差分進化演算法

優化演算法matlab實現（六）遺傳演算法matlab實現

❸ 演算法筆記之博弈問題——貓和老鼠

博弈問題，需要注意，對於每個玩家，都會爭取：

LeetCode913. 貓和老鼠

兩位玩家分別扮演貓和老鼠，在一張 無向 圖上進行游戲，兩人輪流行動。

圖的形式是：graph[a] 是一個列表，由滿足 ab 是圖中的一條邊的所有節點 b 組成。

老鼠從節點 1 開始，第一個出發；貓從節點 2 開始，第二個出發。在節點 0 處有一個洞。

在每個玩家的行動中，他們 必須 沿著圖中與所在當前位置連通的一條邊移動。例如，如果老鼠在節點 1 ，那麼它必須移動到 graph[1] 中的任一節點。

此外，貓無法移動到洞中（節點 0）。

然後，游戲在出現以下三種情形之一時結束：

如果貓和老鼠出現在同一個節點，貓獲勝。
如果老鼠到達洞中，老鼠獲勝。
如果某一位置重復出現（即，玩家的位置和移動順序都與上一次行動相同），游戲平局。
給你一張圖 graph ，並假設兩位玩家都都以最佳狀態參與游戲：

如果老鼠獲勝，則返回 1；
如果貓獲勝，則返回 2；
如果平局，則返回 0 。

題目描述比較長，但其實還是很好理解的。需要注意，每個玩家都會爭取自己獲勝。本題就是簡單的深度優先搜素+記憶化問題了。

這里考慮的是怎麼才能算平局，我們採取的方法是，如果有n個節點，到2n輪如果還沒出結果，就認為可以平局了。

需要注意的是記憶化，memo[i][j][k] 代表貓在i，老鼠在j，在第k輪的結果。

❹ 【演算法筆記】演算法的平均時間復雜度A(n)的公式及示例

演算法平均時間復雜度計算公式

其中:

舉例：檢索問題，數組 有 個元素，每個元素為從1到n的整數。若待檢索元素在 中（例如1,2,3,4,5），則比較次數為其本身。若待檢索元素位於 的空隙中（例如0.5,1.5,2.5），則比較次數為 ，也就是從頭到尾比較一遍。若位於 和位於 的空隙的待檢索元素數量各佔一半，檢索的平均時間復雜度是多少？

位於 的情況：假設 在 的概率為 ，則 在每個位置的概率為 ，若 的值為 ，則需要比較 次。平均時間復雜度為

位於 的空隙的情況： 不在 的概率為 ，每種情況都要比較 次，則該情況的平均時間復雜度為

綜上，結合等差數列求和公式有：

當 ，

❺ 老喻人生演算法筆記-05 三段-內控：跑好大腦的四人接力賽

上一講，我們講了二段，切換，你要在大腦的兩種思維模式之間自如切換。這一講，我們進一步加大解析度，來拆解我們人類的認知行為。

在三段內控這個階段，你需要知道，一次完整地認知行為，實際上是由 4 個最為關鍵的控制點組成的。

我先問你一個問題，超級富豪有什麼區別於常人的地方？

德國作家齊特爾曼博士做了一個調查，發現了成功的公司創始人有 8 種人格特質，其中一條是「內部控制點」：人們的行為由自己控制。因為成功者堅信：「我的命運掌握在我自己的手中。」

《高效能人士的 7 個習慣》這本書在全球賣了一億冊，他的作者柯維，講過一段話，一段讓他永生難忘的話：

在外界刺激和回應之間，存在著一個空間， 我們的回應就存在於這個空間之中， 我們的成長和幸福蘊含在我們的回應中輪滑。

你可以想像一下，這就像一個夾心餅干，外部世界的刺激是上面那層餅干，你的內部感覺和回應是下面那層，中間還有空出來一塊放夾心的地方。

這個地方就是柯維說的空間，是外部世界和你內心世界之間的空間。這個空間讓你可以對外部世界作出反應，也能讓你的內心世界成長和感受幸福。

有些人會主動把握這個中間夾層，有些人就放棄掉了。我們平時乾的傻事兒， 要麼是一時沖動 ， 要麼是條件反射式地作出回應 。這就很像上一講里我們講的自動駕駛系統，這其實是一種動物式的本能反應，如果你停留在這個系統里，你就放棄了夾心餅干中間那塊甜美的地帶。

但要想啟動中間這個空間，做到主動控制並不容易，

原因有三個：

一是，我們的世界變得越來越自動化了，智能手機和網路讓人們變得沒那麼敏銳了。

二是，人的專注力帶寬是非常有限的。《決策的力量》這本書研究發現，人腦每秒鍾能夠接收 1000 萬比特的信息量，但其中只有 50 比特是思維在有意識的狀態下加以處理的。

三是，信息泛濫讓人的持續專注力下降，微軟有個調查，2000 年人們的持續專注力還有 12 秒，2015 年只有 8 秒。

大腦認知行為的四個內控點

那怎麼才能做到主動控制呢？

最好的辦法是，像飛行員，大多時候靠飛機自動駕駛，起飛和降落等關鍵控制點，人工介入。

其實，我們上節課說到的，巨星碧昂斯的復盤秘密是在酒店看錄像，到關鍵地方，「啪」地按下暫停鍵。這個動作就是一個「內控點」，它幫助我們形成一種暫停能力，讓自動模式暫停，啟動主動模式。

那麼，該在什麼時候按下暫停鍵呢？

要回答這個問題，我們先引入一個概念：認知飛輪。

科學研究需要找到基本的顆粒。物理學找到了原子，生物學找到了細胞和基因，信息學找到了比特，那麼

「認知」的基本顆粒呢，我就把雹悔它叫做「認知飛輪」。

[圖片上傳失敗...(image-24860e-1566890500778)]

「認知飛輪」由感知 、認知、決策以及行動這 四個節點 構成：

 在感知環節，你像個情報員，獲取外部信息，所以你需要 很敏感 ；

在認知環節，你像個分析師，你需要 特別理性 ，考慮各種變數，並且給予公平的估值；

 在決策環節，你像個指揮官，你必須根據分析師的評估計算，作出一個決定，而且這個決定必然是有取捨的，你需要十分 果斷 ；

 在行動環節，你像個戰士，需要 不畏艱險，勇往直前 ，執行任務。

我把這四個環節的要求總結為 16 個字：

好奇感知、灰度認知、黑白決策、瘋子行動 。

難題來了，敏感、理性、決斷、野蠻，看起來都是有點兒沖突的性格。一個人怎麼做到呢？

其實啊，一個完整的認知飛輪，就像一場 4 乘 100 米的接力賽，是由 4 個人共同來完成的，他們分別叫感知、認知、決策和行動。

「感知」跑完了把接力棒交給「認知」，「認知」跑完了交給「決策」，最後由「行動」來跑最後一棒。

這四個人彼此交棒的那一刻，就是「內控點」要介入的時候。

我們的認知出現問題，也經常發生在這些點上。

例如，「感知」作為偵察兵獲取了某個信息，結果到了內控點他不交棒，拖到認知環節。你知道一個人如果太敏感，就會有些情緒化，也很難客觀地評價各種可能的情況。

又比方說「認知」這個人，更像一名軍師臘肆臘，優點是特別智慧，考慮問題周到，但讓他拍板，可能就會因為想法太多而優柔寡斷。所以到了「決策」這個內控點，他必須把接力棒交給一名將軍氣質的人。

以上是用生動的人格打比喻，來描述我們在認知基本單元上的四個「內控點」，這個過程都發生在大腦當中。

提升思考率

但想做到讓這四個人格，在大腦里完美交棒並不容易。

現實生活中經常會有兩類人容易在這件事上犯錯誤：

第一類人，有點懶，他壓根沒有停下來，去思考。正如科學家卡拉漢的研究：人們做不出聰明行為，並不是因為他們缺乏動機或能力有限，而是他們缺乏對思考時機的敏感性。這種敏感性，其實就體現為我們在「內控點」的暫停能力。

就好像在一條路上走，明明有個岔路口，如果你停下來想一想多半都能得出正確答案，但大部分人壓根沒有停下來。

那怎麼提升我們思考的敏感性呢？

我給你一個指標，來評判你思考的覆蓋范圍： 思考率 。

這是我創造的一個詞。思考率，等於主動思考的次數，占你內控點的數量的比例。我有個很厲害的朋友，看起來也不那麼聰明，遇到問題想得很慢，但他就是能在每個內控點停下來，慢慢想，死磕，然後再走向下一個內控點。這類人，我就稱之為「思考率」很高。反過來，有的人就像一個聰明學生，最厲害的題都答出來了，簡單的題卻漏答了。這其實是缺乏對思考機會的敏感性。

設立大腦立項決策者

第二類人，是看起來很聰明的人，他們總是愛自圓其說。

人們不能忍受不完整和不確定性，所以總想把認知飛輪這個圓圈快點兒畫完。認知神經科學之父加扎尼加博士就發現了一個秘密：大腦會編造理由。

聰明人很擅長找到一個解釋，然後就覺得自己想明白了，想趕緊矇混過關。這種人贏了就覺得是自己實力強大，輸了就說是運氣不好。這樣其實會堵死自己成長的路途。

那怎麼避免小聰明呢？

你的腦子要給自己設立一個角色，叫 「立項決策者」。

立項決策者是四人接力賽的總教練，他要指揮「感知、認知、決策、行動」這四個角色完成接棒和賽跑。

放到我們的生活語境來理解，「立項決策者」是一個揮舞小皮鞭的狠人，他催促我們完成每個角色的任務，還要在每個內控點順利交棒。我們常說，「一個人要對自己狠一點」，說的就是你在心裡住一個「立項決策者」，遇到困難不能跳過、逃避。

說完 單個認知飛輪裡面的四個「內控點 」，我們再說一下 不同的認知飛輪之間的「內控點」。

這就像羽毛球比賽打的每個球，從一個來回結束，到開始准備打下一個球，這中間也是一個重要的「內控點」。

在這個內控點，我們需要正確的 復盤 。我們要充分利用上一個認知飛輪的經歷和反饋，從錯誤中吸取教訓，從經驗中提升能力。

要做到這一點，關鍵在於你能把下一個認知飛輪的決策過程，和上一個認知飛輪的結果分開。

為什麼呢？因為好的決策未必帶來好的結果。好的結果，也可能是由錯誤的決策撞來的。

所以，別後悔，別找借口，不要怕犯錯，有時候還要主動犯錯，因為隨機突變可能帶來意想不到的好處。

把握內控點，說起來簡單，做起來不容易。最後，我送給你一個有用的操作方法，叫：巴菲特內控法。巴菲特說自己如果不在一張紙上寫下自己的理由，就絕不交易。這個交易可能是錯的，但自己必須有一個「交易答案」。

比方說，在紙上寫：「我今天要花 500 億美金來買蘋果公司，因為……」

如果你不能回答這個問題，你就不要買。

寫在紙上能有什麼用呢？其實，就是建立了一個節點，人為製造了一個「內控點」，防止愛欺騙自己的大腦過於沖動。

本講小結

總結一下，這一講我們講了三段：內控。

我希望你記住，不管人生多麼緊迫，你都有權利按下自己的暫停鍵。在那些關鍵時刻，你只用說：慢，讓我想想看！然後激活腦袋裡的那位「立項決策者」，開始計算你的答案。

思考題

我們說，感知環節，你要像個情報員，敏感地獲取外部信息；認知環節，你要像個分析師，理性評估；決策環節，你要像個指揮官，果斷取捨；行動環節，你要像個戰士，勇往直前。

但能把這四個角色都做好，其實非常難，你在哪個角色完成得比較好？又在哪個角色上是短板呢？

劃重點

「認知飛輪」有四個環節：

1. 感知環節，你要像個情報員，獲取外部信息，所以你需要很敏感；

2. 認知環節，你要像個分析師，考慮評估各種變數，你需要特別理性；

3. 決策環節，你要像個指揮官，作出決定和取捨，你需要十分果斷；

4. 行動環節，你要像個戰士，勇往直前執行任務，需要不畏艱險。

❻ 優化演算法筆記（一）優化演算法的介紹

（以下描述，均不是學術用語，僅供大家快樂的閱讀）

        我們常見常用的演算法有排序演算法,字元串遍歷演算法,尋路演算法等。這些演算法都是為了解決特定的問題而被提出。

        演算法本質是一種按照固定步驟執行的過程。

        優化演算法也是這樣一種過程，是一種根據概率按照固定步驟尋求問題的最優解的過程。與常見的排序演算法、尋路演算法不同的是，優化演算法不具備等冪性，是一種 概率演算法 。演算法不斷的 迭代 執行同一步驟直到結束，其流程如下圖。

        等冪性即 對於同樣的輸入，輸出是相同的 。

        比如圖1，對於給定的魚和給定的熊掌，我們在相同的條件下一定可以知道它們誰更重，當然，相同的條件是指魚和熊掌處於相同的重力作用下，且不用考慮水分流失的影響。在這些給定的條件下，我們（無論是誰）都將得出相同的結論，魚更重或者熊掌更重。我們可以認為，秤是一個等冪性的演算法（工具）。

        現在把問題變一變，問魚與熊掌你更愛哪個，那麼現在，這個問題，每個人的答案可能不會一樣，魚與熊掌各有所愛。說明喜愛這個演算法不是一個等冪性演算法。當然你可能會問，哪個更重，和更喜歡哪個這兩個問題一個是客觀問題，一個是主觀問題，主觀問題沒有確切的答案的。當我們處理主觀問題時，也會將其轉換成客觀問題，比如給喜歡魚和喜歡熊掌的程度打個分，再去尋求答案，畢竟計算機沒有感情，只認0和1（量子計算機我不認識你）。

        說完了等冪性，再來說什麼是概率演算法。簡單來說就是看臉、看人品、看運氣的演算法。

        有一場考試，考試的內容全部取自課本，同時老師根據自己的經驗給同學們劃了重點，但是因為試卷並不是該老師所出，也會有考試內容不在重點之內，老師估計試卷中至少80%內容都在重點中。學霸和學渣參加了考試，學霸為了考滿分所以無視重點，學渣為了pass，因此只看了重點。這樣做的結果一定是score(學霸)>=score(學渣)。

        當重點跟上圖一樣的時候，所有的內容都是重點的時候，學霸和學渣的學習策略變成了相同的策略，則score(學霸)=score(學渣)。但同時，學渣也要付出跟學霸相同的努力去學習這些內容，學渣心裡苦啊。

        當課本如下圖時

        學霸？學霸人呢，哪去了快來學習啊，不是說學習一時爽，一直學習一直爽嗎，快來啊，還等什麼。

        這時，如果重點內容遠少於書本內容時，學渣的學習策略有了優勢——花費的時間和精力較少。但是同時，學渣的分數也是一個未知數，可能得到80分也可能拿到100分，分數完全取決於重點內容與題目的契合度，契合度越高，分數越高。對學渣來說，自己具體能考多少分無法由自己決定，但是好在能夠知道大概的分數范圍。

        學霸的學習策略是一種遍歷性演算法，他會遍歷、通讀全部內容，以保證滿分。

        學渣的學習策略則是一種概率演算法，他只會遍歷、學習重點內容，但至於這些重點是不是真重點他也不知道。

        與遍歷演算法相比，概率演算法的結果具有不確定性，可能很好，也可能很差，但是會消耗更少的資源，比如時間（人生），空間（記憶）。概率演算法的最大優點就是 花費較少的代價來獲取最高的收益 ，在現實中體現於節省時間，使用很少的時間得到一個不與最優解相差較多的結果。

        「莊子：吾生也有涯，而知也無涯；以有涯隨無涯，殆矣。」的意思是：人生是有限的，但知識是無限的（沒有邊界的），用有限的人生追求無限的知識，是必然失敗的。

        生活中概率演算法（思想）的應用其實比較廣泛，只是我們很少去注意罷了。關於概率演算法還衍生出了一些有趣的理論，比如墨菲定律和倖存者偏差，此處不再詳述。

        上面說到，優化演算法就是不停的執行同樣的策略、步驟直到結束。為什麼要這樣呢？因為優化演算法是一種概率演算法，執行一次操作就得到最優結果幾乎是不可能的，重復多次取得最優的概率也會增大。

        栗子又來了，要從1-10這10個數中取出一個大於9的數，只取1次，達到要求的概率為10%，取2次，達到要求的概率為19%。

        可以看出取到第10次時，達到要求的概率幾乎65%，取到100次時，達到要求的概率能接近100%。優化演算法就是這樣簡單粗暴的來求解問題的嗎？非也，這並不是一個恰當的例子，因為每次取數的操作之間是相互獨立的，第2次取數的結果不受第1次取數結果的影響，假設前99次都沒達到要求，那麼再取一次達到要求的概率跟取一次達到要求的概率相同。

        優化演算法中，後一次的計算會依賴前一次的結果，以保證後一次的結果不會差於前一次的結果。這就不得不談到馬爾可夫鏈了。

        由鐵組成的鏈叫做鐵鏈，同理可得，馬爾可夫鏈就是馬爾可夫組成的鏈。

        言歸正傳, 馬爾可夫鏈（Markov Chain, MC） ,描述的是 狀態轉移的過程中,當前狀態轉移的概率只取決於上一步的狀態,與其他步的狀態無關 。簡單來說就是當前的結果只受上一步的結果的影響。每當我看到馬爾可夫鏈時，我都會陷入沉思，生活中、或者歷史中有太多太多與馬爾可夫鏈相似的東西。西歐封建等級制度中「附庸的附庸不是我的附庸」與「昨天的努力決定今天的生活，今天的努力決定明天的生活」，你的下一份工作的工資大多由你當前的工資決定，這些都與馬爾可夫鏈有異曲同工之處。

        還是從1-10這10個數中取出一個大於9的數的這個例子。基於馬爾可夫鏈的概率演算法在取數時需要使當前取的數不小於上一次取的數。比如上次取到了3，那麼下次只能在3-10這幾個數中取，這樣一來，達到目標的概率應該會顯著提升。還是用數據說話。

        取1次達到要求的概率仍然是

        取2次內達到要求的概率為

        取3次內達到要求的概率為

        取4次內……太麻煩了算了不算了

        可以看出基於馬爾可夫鏈來取數時，3次內能達到要求的概率與不用馬爾可夫鏈時取6次的概率相當。說明基於馬爾可夫鏈的概率演算法求解效率明顯高於隨機概率演算法。那為什麼不將所有的演算法都基於馬爾可夫鏈呢？原因一，其實現方式不是那麼簡單，例子中我們規定了取數的規則是復合馬爾可夫鏈的，而在其他問題中我們需要建立適當的復合馬爾科夫鏈的模型才能使用。原因二，並不是所有的問題都符合馬爾科夫鏈條件，比如原子內電子出現的位置，女朋友為什麼會生（lou）氣，彩票號碼的規律等，建立模型必須與問題有相似之處才能較好的解決問題。

        介紹完了優化演算法，再來討論討論優化演算法的使用場景。

        前面說了優化演算法是一種概率演算法，無法保證一定能得到最優解，故如果要求結果必須是確定、穩定的值，則無法使用優化演算法求解。

        例1，求城市a與城市b間的最短路線。如果結果用來修建高速、高鐵，那麼其結果必定是唯一確定的值，因為修路寸土寸金，必須選取最優解使花費最少。但如果結果是用來趕路，那麼即使沒有選到最優的路線，我們可能也不會有太大的損失。

        例2，求城市a與城市b間的最短路線，即使有兩條路徑，路徑1和路徑2，它們從a到b的距離相同，我們也可以得出這兩條路徑均為滿足條件的解。現在將問題改一下，求城市a到城市b耗時最少的線路。現在我們無法馬上得出確切的答案，因為最短的線路可能並不是最快的路線，還需要考慮到天氣，交通路況等因素，該問題的結果是一個動態的結果，不同的時間不同的天氣我們很可能得出不同的結果。

        現實生產、生活中，也有不少的場景使用的優化演算法。例如我們的使用的美圖軟體，停車場車牌識別，人臉識別等，其底層參數可能使用了優化演算法來加速參數計算，其參數的細微差別對結果的影響不太大，需要較快的得出誤差范圍內的參數即可；電商的推薦系統等也使用了優化演算法來加速參數的訓練和收斂，我們會發現每次刷新時，推給我們的商品都有幾個會發生變化，而且隨著我們對商品的瀏覽，系統推給我們的商品也會發生變化，其結果是動態變化的；打車軟體的訂單系統，會根據司機和客人的位置，區域等來派發司機給客人，不同的區域，不同的路況，派發的司機也是動態變化的。

        綜上我們可以大致總結一下推薦、不推薦使用優化演算法的場景的特點。

        前面說過，優化演算法處理的問題都是客觀的問題，如果遇到主觀的問題，比如「我孰與城北徐公美」，我們需要將這個問題進行量化而轉換成客觀的問題，如身高——「修八尺有餘」，「外貌——形貌昳麗」，自信度——「明日徐公來，孰視之，自以為不如；窺鏡而自視，又弗如遠甚」，轉化成客觀問題後我們可以得到各個解的分數，通過比較分數，我們就能知道如何取捨如何優化。這個轉化過程叫做問題的建模過程，建立的問題模型實際上是一個函數，這個函數對優化演算法來說是一個黑盒函數，即不需要知道其內部實現只需要給出輸入，得到輸出。

        在優化演算法中這個黑盒函數叫做 適應度函數 ， 優化演算法的求解過程就是尋找適應度函數最優解的過程 ，使用優化演算法時我們最大的挑戰就是如何將抽象的問題建立成具體的模型，一旦合適的模型建立完成，我們就可以愉快的使用優化演算法來求解問題啦。（「合適」二字談何容易）

        優化演算法的大致介紹到此結束，後面我們會依次介紹常見、經典的優化演算法，並探究其參數對演算法性能的影響。

——2019.06.20

[目錄]

[下一篇 優化演算法筆記（二）優化演算法的分類]

❼ 優化演算法筆記（十七）萬有引力演算法

（以下描述，均不是學術用語，僅供大家快樂的閱讀）
萬有引力演算法（Gravitational Search Algorithm）是受物體之間的萬有引力啟發而提出的演算法。演算法提出於2008（2009）年，時間不長，不過相關的文章和應用已經相對較多，也有不少的優化改進方案。
萬有引力演算法中，每一個物體的位置代表了一個可行解，而物體的質量則反映了該位置的好壞，位置越好的物體的質量越大，反之物體的質量越小（質量由適應度值計算出，不是直接相等）。物體在解空間中的運動方式由其他物體的引力決定，質量越大的物體，在同等引力作用下的加速度較小，所以單位時間內的速度也相對較小，位移距離較短，反之加速度和速度都較大，位移距離較長。故可以簡單的認為， 位置越優的個體的移動速度越慢，位置越差的個體的移動速度越快 。

萬物之間皆有萬有引力，不過在我們談到萬有引力之時，對象大多是天體，否則萬有引力太小可以忽略不計。所有這次我們的主角就是天體了。（總不可能是蘋果吧）。

每一個天體都有個屬性：位置X，質量M，加速度A，以及速度V，還有適應度值F。
在D維空間內有N個天體，其位置為

，加速度

，速度

，其適應度值為

。

第i個天體的質量則是根據其適應度值計算得出：

其中M為天體的質量在群體重質量中的佔比， 分別表示全局最差天體的適應度值和全局最優個體的適應度值。
可以看出，處於最優位置的天體的質量m為1，最差位置的天體的質量m為0。當最優天體和最差天體重合時，所有的天體的質量m都為1。

由萬有引力計算公式和加速度公式可以計算出當前天體收到另一個天體萬有引力而產生的加速度：

其中R表示第i個天體和第j個天體之間的歐式距離，aij為天體i在第d維上受到天體j的萬有引力而產生的加速度,ai為第i個天體受到的其他所有天體萬有引力的合力產生的加速度。G為萬有引力常量，可以根據一下公式計算：

其中G0為初始值，T為最大迭代次數。

計算出了天體的加速度，則可以根據當前速度計算出下一步天體的運行速度以及天體下一步的位置。

這一步比較簡單與粒子群、蝙蝠等有速度的演算法一致。

可以看出萬有引力演算法的流程異常的簡單，與經典的粒子群差不多。萬有引力演算法也可以看做是一個優化改進版的粒子群，不過設計比較巧妙，引入的質量、加速度等概念，但實現仍然很簡單。萬有引力演算法的效果如何，在下一節將會進行實驗測試。

適應度函數 。
實驗一：

從圖像中可以看出，各個天體都在不停的運動，由於沒有貪心演算法（優於當前值才改變位置）的加入，所以個天體有可能運動到比原先位置更差的地方，而且其收斂速度也比較快。
從結果上看，似乎還不錯，受到最差值的影響均值也相對較大，演算法結果的穩定性不是太好。
直覺上感覺演算法有點問題。根據物理得來的直覺告訴我，這些天體會相互靠近，所以，它們不會集中到它們所構成的凸包之外， 凸實心物體的質心不會跑到該物體的外部 。做個試驗驗證一下，將測試函數的最優解設置到一個極端的位置。
實驗二 ： 適應度函數

這次最優解位置在（90,90）處，該點有很大概率出現在初始天體所圍成的凸多邊形外。

從圖像中可以看出，在天體們還沒有到達最優位置附近（右下角的紅點）時，它們已經收斂於一個點，之後則很難再次向最優解靠經。看結果可以發現幾乎每一次實驗的結果都不太好，演算法果然有點問題，不過問題不大。
萬有引力出現這種現象可能有兩個原因： 1.演算法收斂的太快 ，還未對全局進行充分搜索之時就收斂到了一點，收斂到一點後無法再運到。 2.演算法沒有跳出局部最優的策略 ，萬有引力作用下的天體慢慢聚集到奇點，形成黑洞，無法從中逃離。
那接下來，對萬有引力演算法的改進方向也比較明確了：1.減緩其收斂速度，2增加跳出局部最優操作，使之逃離黑洞。
看看萬有引力常量G的函數圖像

將萬有引力常量的值修改為隨著迭代次數線性下降，從圖像中可以看出，效果還是比較明顯的，天體在不斷的運動，最後才收斂、聚集於一起。從實驗結果也可以看出，演算法相對穩定。結合圖像可以知道，改進後，演算法的收斂性下降，但全局搜索能力有較大的提升，演算法的結果不會很差但是精度較低。

將萬有引力常量的下降趨勢放緩為原來的1/4，從圖像中可以看出，演算法的收斂速度非常快，也得到了較好的結果，相比線性下降，演算法有著更好的精度，不足之處則是沒有跳出局部最優的操作，收斂過快也容易陷入局部最優。
不知道原文為什麼讓萬有引力常量G的如此快的降到0，明明降的更慢能有更好的全局搜索能力，但精度可能較差。猜測如果精度較差則在測試函數結果和曲線上比不贏對比的其他演算法，論文沒法發了。其使用的測試函數的最優解大多處於解空間的中心位置附近，即很少出現最優解在天體所圍成的凸多面體之外的情況，而實際問題中我們是無法預知最優解在個位置的。
接下來，將試著為萬有引力演算法加入一點跳出局部最優的操作。

實驗四 ：改進,新增以下規則及操作
在實驗二的條件下
1 . 處於最優位置的天體保持自己的位置不動.
2 . 如果某一個天體的運動後的位置優於當前全局最優個體的位置則將當前的最優個體初始化到解空間的隨機位置.(將被自己幹掉的大哥流放)。
3 . 如果觸發了規則2，將所有的個體的以迭代次數重置為0，即計算G=G0*e^(-20t/T)中的t置為0，重新計算萬有引力常量，若未觸發條件2則t=t+1。

從圖像上看，演算法的全局搜索能力有大幅的增強，並且已經集中到了最優解的附近，而且由於加入了「流放」這一跳出局部最優的操作，可以看出，不斷的有新的個體出現在距最優位置較遠的位置。不過收斂速度有所下降，因此局部搜索能力有一定減弱。
看結果，好像沒有實驗三那麼好，但與實驗二相比，已經有了很大的提升，而且有了跳出局部最優的操作，結果也相對穩定。
上述的實驗僅僅是對直觀猜想的實現，如果想以此為改進點，還要對其進行大量的調優，相信會有不錯的結果。

萬有引力演算法根據萬有引力提出，結合了牛頓第二定律，可以說其操作步驟與真實的物理規律非常的貼切。不過就像前文說過，受物理現象啟發而來的優化演算法其性能是未知的，因為它們不具備智能，只有著規律，有規律就會存在弱點，就會有搜索盲區。宇宙那麼大，肯定存在沒有任何天體到達過的空間。
不過由於萬有引力演算法流程簡單，理解方便，其優化方案和能改進的地方相對較多。萬有引力演算法的收斂速度過快，導致其全局搜索能力較弱而局部搜索能力很強，容易陷入局部最優。根據其特點，我們可以降低其收斂速度或者增加跳出局部最優操作，來平衡演算法的各個性能。

參考文獻
Rashedi E , Nezamabadi-Pour H , Saryazdi S . GSA: A Gravitational Search Algorithm[J]. Information Sciences, 2009, 179(13):2232-2248. 提取碼：xhpa

以下指標純屬個人yy,僅供參考

目錄
上一篇 優化演算法筆記（十六）混合蛙跳演算法
下一篇 優化演算法筆記（十八）灰狼演算法

優化演算法matlab實現（十七）萬有引力演算法matlab實現

❽ 優化演算法筆記（二十六）和聲搜索演算法

（以下描述，均不是學術用語，僅供大家快樂的閱讀）
和聲搜索演算法（Harmony Search）是受音樂中的和聲啟發而提出的啟發式演算法，其提出（發表）年份為2001年，算是一個比較老的演算法了。和聲搜索演算法放在現在，其性能非常一般，不過它提出了一種領域搜索的具體實現方式，可以和不同的演算法融合，提高其他演算法的性能。

單獨看一個和聲意義不大，一個和聲的一個維度會根據群體中該維度的所以取值來確定其領域范圍，然後再進行領域搜索。

原演算法受音樂啟發，所以它所解決的目標問題也是離散的問題。
和聲搜索演算法中的一個個體被稱為和聲記憶（Harmony Memory,HM），群體中和聲記憶的數量為N,每個和聲記憶中的音數（維度）為D。每一維的取值范圍為 。

原演算法中每個維度的取值范圍L是一組有序的離散的值，即在指定的變數值中選取一個作為和聲記憶的值。
每個和聲記憶每次迭代只能變為其領域的值。
和聲演算法中有兩種操作：1.移動到領域，2.變異到領域
其概率分別為Harmony Memory Considering Rate(HMCR)和Pitch Adjusting Rate(PAR)。
其中HMCR取值約為0.95，PAR取值約為0.10。
可以看出該演算法的步驟和數值參考了遺傳演算法，而且兩者都是為了處理離散問題。

例子如下：
和聲記憶的數量為3，維度為2，其中第1維的取值范圍為{A,B,C,D,E,F,G},第2維的取值為{3,4,5,6}。
第1代，三個個體的取值如下

在計算第2代時，每個個體的每一維只能去到該維度的鄰域的值。
個體1_2能取到的值為(A,3) (A,4) (B,3) (B,4)
個體2_2能取到的值為(F,4)(F,5)(F,6)(G,4)(G,5)(G,6)
個體3_2能取到的值為(C,3)(C,4)(C,5)(D,3)(D,4)(D,5)(E,3)(E,4)(E,5),

圖中標出了這三個個體能夠到達的鄰域。

變異到鄰域到操作也很簡單，該操作是對標了遺傳演算法中的變異操作。
變異到鄰域操作時，該維度不會變異到當前已有的值。
如個體1_1變異第1維，由於群體中第1維的取值為{A,D,G}故該維度只能取到{B,C,E,F}。
下圖中標有顏色的塊出了變異操作無法到達的位置，空白位置為變異操作能夠到達的位置。（如果沒有空白位置呢？概率非常小，畢竟個體位置遠少於解空間位置，如果出現了，不變異或者隨機一個位置都行）

迭代過後，如果新的位置更好，則保留該和聲記憶，並去除最差的和聲記憶。
最後文章給出了判斷找到的解是否是最優解的判斷函數

其中Hr=HMCR,Hi會在該維度找到更好值時隨著迭代次數遞增。該公式的作用主要是為了判斷何時去結束演算法程序，不過在之前我們都是使用的最大迭代次數來結束演算法程序，所有好像沒多大用處。
演算法的流程也挺簡單的：

和聲搜索的原演算法是根據音樂中和聲概念提出的，音符是離散的，所有演算法也是離散的，對標遺傳演算法用於處理離散解空間問題，那麼如何修改和聲搜索演算法使其能處理連續數值問題呢？
最關鍵的點是如何處理「鄰域」，在連續解空間上，很難定義出一個點的領域，而且每個維度上的取值數量也是無窮的。
為和聲搜索演算法定義鄰域也有幾種思路：
1 . 將所有的個體定義為該個體的鄰域，即每次隨機從群體中選擇一個個體，該維度移動到所選中的個體處。

其中D,E,F分別為AB,AC,BC的中點，A,B,C三個和聲記憶的鄰域將由DEF這三個點及解空間邊界決定，此時的鄰域比思路2中的更小，也不會出現重疊部分。
當某一維度的兩個領域值相等時，上述（二維）的鄰域（面）將會退化成鄰域（線），可能會導致該維度快速收斂到該值，故此時需要忽略重復值，將鄰域重新展開（成為面）。
在連續演算法中，當滿足HCMR條件時，演算法將根據上面的色塊在鄰域中隨機選擇一個值；當滿足PAR條件時，由於無法剔除指定值，簡單起見，直接移動到隨機的和聲記憶的該維度。
後續的實驗由於是求解連續函數最值，故會選擇上述連續演算法中的三種思路來進行。

適應度函數 。
實驗一 ： 思路一

從圖像可以看出，思路一的策略與遺傳演算法非常的相似，移動路線類似於十字架，最終也收斂到了正解附近。前期搜索主要靠鄰域移動，後期移動則是靠變異。

從結果也可以看出與遺傳演算法的差距不大，演算法不是很穩定，其策略是飛到相鄰的和聲記憶上，所以跨越度比較大，精度全靠變異。

實驗二 ： 思路二

從圖像中可以看出，種群的搜索路徑不在像實驗一中那樣直來直去的十字路徑，收斂的速度也慢了不少，但是仍能在正解附近收斂。

從結果中可以看出，思路二的結果好了不少，同時也更加穩定（誤，運氣好，之前實驗出現過不好的結果，沒能重現）。該思路的鄰域搜索麵積會更大，且個體之間的鄰域存在重疊部分，故會有可能收斂於不好的位置，不過概率也較小。

實驗三 ： 思路三

圖像逐漸貪吃蛇化！前期的圖像與思路一相似，後期的圖像有點類似遺傳演算法，可能是鄰域的面積逐漸縮小成了長條狀所致，不過最終「貪吃蛇」還是吃到了食物。

結果可以看出，思路三的穩定性不太行，當全部個體收斂到了一點後會開始進行思路一的替換操作，但無論如何替換都是相同的值，難以找到更優的位置，於是會出現一個較差的結果。這里也可以增加范圍隨機來跳出局部最優。

和聲搜索演算法是根據和聲樂理知識提出的演算法。由於音符是離散的值，演算法也對標了遺傳演算法，故原演算法也是針對離散問題提出的。在解決連續性問題時，需要對其鄰域概念進行擴展和修改，最終的效果與遺傳演算法相差不大。
在現在看來，和聲搜索演算法的效果屬實一般，對於其的針對性研究也不太多，該演算法主要提出了其不同於遺傳演算法的遍歷解空間的方式。所以在很多論文中都能看到用和聲搜索演算法與其他演算法融合來進行改進的例子。
與遺傳演算法相比，和聲搜索演算法的鄰域概念，將遺傳演算法的基因由線擴展到了面上。這一點有點類似於SVM和卷積神經網路的關系，不過，遺傳演算法和和聲搜索演算法的差別並沒有那麼大，只是搜索方式不同罷了。
參考文獻
Geem Z W , Kim J H , Loganathan G V . A New Heuristic Optimization Algorithm: Harmony Search[J]. Simulation, 2001, 2(2):60-68. 提取碼：4udl
Omran M , Mahdavi M . Global-best harmony search[J]. Applied Mathematics and Computation, 2008, 198(2):643-656. 提取碼：pk3s

以下指標純屬個人yy,僅供參考

目錄
上一篇 優化演算法筆記（二十五）飛蛾撲火演算法
下一篇 優化演算法筆記（二十七）蜉蝣演算法

❾ 優化演算法筆記（七）差分進化演算法

（以下描述，均不是學術用語，僅供大家快樂的閱讀）
差分進化演算法（Differential Evolution Algorithm，DE）是一種基於群體的進化演算法，它模擬了群體中的個體的合作與競爭的過程。演算法原理簡單，控制參數少，只有交叉概率和縮放比例因子，魯棒性強，易於實現。
差分進化演算法中，每一個個體的基因表示待求問題的一個候選解。每次迭代將先進行變異操作，選擇一個或多個個體的基因作為基，然後選擇不同的個體的差分來構成差分基因，最後將作為基的基因與差分基因相加來得出新的個體。交叉操作將新的個體將於父代的對應個體交叉，然後進行選擇操作，比較交叉後的個體與父代的對應個體，選擇較優的個體保留至下一代。在迭代完成之後將選擇種群中最優個體的基因作為解。
差分進化演算法可以算是我所使用過的優化演算法中大魔王級別的演算法，雖然它每個方面都沒有強到離譜，但是綜合起來的效果好於大多數演算法。它就像一個每個科目都能考到90分（百分制）的學生，雖然沒門課都不是最優秀的，但是論綜合，論總分，它有極大的概率是第一名。

在我研究優化演算法的小路上，我的目標就是找到一個能打敗大魔王或是能在大多數方面壓制魔王的演算法。

這次的主角就選魔王軍吧（或者蟻王軍，為了與蟻群演算法區別還是叫魔王軍吧），個體則稱之為魔王兵。
魔王兵的能力取決於它們的基因，它們可以根據環境或者需要改變自己的基因使得自己更加強大，更方便的處理問題，問題的維度與基因維度相同。

表示第i個魔王兵在進化了第t次後的基因，該個體有D位基因。
與遺傳演算法同為進化演算法的差分進化演算法，它們的操作（運算元）也都非常相似的，都是交叉，變異和選擇，流程也幾乎一樣（遺傳演算法先交叉後變異，差分進化演算法先變異後交叉）。

說到差分進化演算法中的變異，我就想到一句論語 「三人行，必有我師焉。擇其善者而從之，其不善者而改之。」 ，其實這句論語已經向我們說明了差分進化演算法的整個流程：
「三人行，必有我師焉」——變異，交叉。
「擇其善者而從之，其不善者而改之」——選擇。
差分進化演算法中，當一個魔王兵變異時，它會先找來3個小夥伴，當然是隨機找來3個小夥伴，避免同化。在一個小夥伴的基因上加上另外兩個小夥伴基因之差作為自己的目標基因。其變異公式如下：

表示第i個魔王兵找到了編號為r1、r2和r3的三個魔王兵，當然了i、r1、r2、r3為互不相同的整數，F為縮放比例因子，通常 ，一般取F=0.5。 為第i個魔王兵交叉後的目標基因圖紙，不過這是個半成品，再經過交叉後，目標基因圖紙才算完成。
其實現在我們已經有了5個基因圖紙了 ，接下來將進行交叉操作。由於變異操作，差分進化演算法的種群中個體數至少為4，即魔王軍中至少有4個小兵。

交叉操作中，魔王兵i會將目標基因圖紙 進行加工得到 ，加工過程如下：

其中 。 為交叉概率，其值越大，發生交叉的概率越大，一般取 。 為{1,2,…,D}中的隨機整數，其作用是保證交叉操作中至少有一維基因來自變異操作產生的基因，不能讓交叉操作的努力白費。
從公式上可以看出交叉操作實際上是從變異操作得出的基因圖紙上選擇至少一位基因來替換自己的等位基因，得到最終的基因圖紙。

選擇操作相對簡單，魔王兵i拿到了最終的基因圖紙 ，大喊一聲，進化吧，魔王兵i的基因改變了。它拿出了能力測量器fitness function,如果發現自己變強了，那麼就將基因 保留到下一代，否則它選擇放棄進化，讓自己還原成 。

實驗又來啦，還是那個實驗 ，簡單、易算、好畫圖。
實驗1 ：參數如下

圖中可以看出在第20代時，群體已經非常集中了，在來看看最終得出的結果。

這結果真是好到令人發指，惡魔在心中低語「把其他的優化演算法都丟掉吧」。不過別往心裡去，任何演算法都有優缺點，天下沒有免費的午餐，要想獲得某種能力必須付出至少相應的代價。
實驗2：
將交叉率CR設為0,即每次交叉只選擇保留一位變異基因。

看看了看圖，感覺跟實驗1中相比沒有什麼變化，那我們再來看看結果。

結果總體來說比實驗1好了一個數量級。為什麼呢？個人感覺應該是每次只改變一位基因的局部搜索能力比改變多位基因更強。下面我們將交叉率CR設為1來看看是否是這樣。
實驗3：
將交叉率CR設為1,即每次交叉只選擇保留一位原有基因。

實驗3的圖與實驗1和實驗2相比好像也沒什麼差別,只是收斂速度好像快了那麼一點點。再來看看結果。

發現結果比實驗2的結果還要好？那說明了實驗2我得出的結論是可能是錯誤的，交叉率在該問題上對差分進化演算法的影響不大，它們結果的差異可能只是運氣的差異，畢竟是概率演算法。
實驗4：
將變異放縮因子設為0，即變異只與一個個體有關。

收斂速度依然很快，不過怎麼感覺結果不對，而且個體收斂的路徑好像遺傳演算法，當F=0，時，差分進化演算法退化為了沒有變異、選擇操作的遺傳演算法，結果一定不會太好。

果然如此。下面我們再看看F=2時的實驗。
實驗5：
將變異放縮因子設為2。

實驗5的圖可以明顯看出，群體的收斂速度要慢了許多，到第50代時，種群還未完全收斂於一點，那麼在50代時其結果也不會很好，畢竟演算法還未收斂就停止進化了。

結果不算很好但也算相對穩定。

通過上面5個實驗，我們大致了解了差分進化演算法的兩個參數的作用。
交叉率CR，影響基因取自變異基因的比例，由於至少要保留一位自己的基因和變異的基因導致CR在該問題上對演算法性能的影響不大（這個問題比較簡單，維度較低，影響不大）。
變異放縮因子F，影響群體的收斂速度，F越大收斂速度越慢，F絕對值越小收斂速度越快，當F=0是群體之間只會交換基因，不會變異基因。

差分進化演算法大魔王已經如此強大了，那麼還有什麼可以改進的呢？當然有下面一一道來。
方案1 .將3人行修改為5人行，以及推廣到2n+1人行。
實驗6：
將3人行修改為5人行，變異公式如下：

五人行的實驗圖看起來好像與之前並沒有太大的變化，我們再來看看結果。

結果沒有明顯提升，反而感覺比之前的結果差了。反思一下五人行的優缺點，優點，取值范圍更大，缺點，情況太多，減慢搜索速度。

可以看出演算法的收斂速度比之前的變慢了一點，再看看結果。

比之前差。

差分進化演算法的學習在此也告一段落。差分進化演算法很強大，也很簡單、簡潔，演算法的描述都充滿了美感，不愧是大魔王。不過這里並不是結束，這只是個開始，終將找到打敗大魔王的方法，讓新的魔王誕生。
由於差分進化演算法足夠強，而文中實驗的問題較為簡單導致演算法的改進甚至越改越差（其實我也不知道改的如何，需要大量實驗驗證）。在遙遠的將來，也會有更加復雜的問題來檢驗魔王的能力，總之，後會無期。
以下指標純屬個人yy,僅供參考

目錄
上一篇 優化演算法筆記（六）遺傳演算法
下一篇 優化演算法筆記（八）人工蜂群演算法

優化演算法matlab實現（七）差分進化演算法matlab實現

❿ 老喻人生演算法筆記20 猶豫：灰度認知，黑白決策

上一講，我給你講了，考慮問題要把理性思維和直覺思維綜合起來。但在作決策的時候，我們還是容易猶豫不決。這一講我們展開來聊聊，在認知和決策環節，我們應該遵循什麼原則。

我要給你講八個字：灰度認知，黑白決策。

我們在 A 計劃內控點那一講里，就說過一個完整的決策過程有四個重要的點，感知-認知-決策-行動。 理性思維和感性思維的區別 ，往往就是跳過了中間兩個步驟， 直接從感知跑到了行動 。所以， 想要培養自己的理性思維，認知和決策兩個環節至關重要 。

這一講，我要帶你用概率的底層思維，來重新理解應該怎麼去認知，如何作決策。有了概率思維，你就能從「理解這件事很並激重要」，進化成「我知道該怎麼做」。

我們先來回顧一下認知和決策。

認知，你對收集到的信息進行處理，你像分析官一樣思考，評估各種選項。

決策，是指在各種選項面前，你像個指揮官一樣，作出最終選擇。

我說認知要保持灰度，那什麼叫灰度呢？

灰色是處於白色和黑色之間的中間地帶，有深灰、有淺灰。所以當我們想要准確描述它時，需要給它加上一個百分比。

灰度認知，是指你在分析選項的階段，先不急於作非黑即白的判斷，保持一定灰度，這個灰度最好有一個數值。絕畝襪

黑白決策，是說我們在形成最終決定時，必須有一個黑白分明的選擇，不能模稜兩可。但現實中，我們恰恰容易把兩者弄混，在認知環節非黑即白，在決策環節猶豫不決。

認知階段要保持灰度

要想深入理解這兩個概念，我要帶你來看一個有趣的案例。

上世紀 90 年代耐仿中期，銅價下跌厲害，加拿大因邁特礦業公司，在美國一個銅礦經營困難。所以，總公司想關閉這個礦，但也面臨了很多阻力。這個礦有超過1000 名礦工，幾乎是當地唯一的生意，要是關了，會給當地經濟造成很負面的影響。而且關礦就等於承認決策失誤，管理團隊為了保全名聲也不願意關。

除了關閉銅礦，還有另外兩個選擇：

第一，是不在本地煉礦，把礦石運到加拿大，用新式熔爐提煉。

第二，是繼續向北挖礦。因為這個銅礦的北部，可能還有很多礦藏。高管偏向於關掉，礦區經理偏向於繼續經營，各方吵得不可開交，都想說服對方，會議開了幾個小時，毫無進展，大家都很沮喪。

你看，是不是和我們的現實生活很像？一個難題出現，各種因素交織在一起，每個選擇都各有利弊，很難一下子理清。

這時候，咨詢公司有一個叫馬丁的小夥子突然產生了一個想法。他提了一個問題：「這個選擇必須具備怎樣的條件，才能成為正確的答案？」

這就有意思了，小夥子一下子點中了關鍵。為什麼這么說呢？大家在討論選項的時候，都犯了一個錯誤，每個人都急於證明自己的選項是最好的，然後試圖說服對方。

討論是一個認知過程。我們剛才說了，認知要保持灰度，就是要全面評估各種選項的可能性。

如果每個人都固守自己的觀點，就變成「黑白認知」了，大家死守自己的認知，反對別人的認知，而沒有人真正去思考，每個方案的可行性、成本和收益。這個會議當然就沒法進展下去了。

提出了這個問題的馬丁，後來做了羅特曼商學院的院長，成為全球最有影響力的思想家之一。

馬丁的辦法高明在哪兒呢？他提倡對每一種可能性進行分析，我們把不確定的部

分盡可能確定下來，羅列出來。這樣就能理性地評估，每個選項的優劣之處。一旦你開始這樣想問題，你的思考方式就會轉變。他把我們從 立場之爭、非黑即白的對錯之爭 ， 拉到了對事實的判定。認知階段不要非黑即白，別把討論方案變成了堅守立場。

當人們從「黑白認知」轉為「灰度認知」，局面立即發生了轉變，三個選項的問題也暴露出來了：

把礦石從海上運往加拿大這個選項，聽起來不錯，但一算賬，費用太高了，遠超預期，所以只能放棄。另外一個選擇是擴大礦區，看起來也很有吸引力，但從技術上一研究，發現新舊礦脈之間有一個巨大的岩壁，打穿的成本太高了，所以也不可行。到最後大家發現，盡管「關掉銅礦」很艱難，卻是唯一可行的選擇。經過「灰度認知」這個過程，連反對者也不得不接受了這個黑白決策。

灰度認知的秘密是什麼？

在 認知階段 ， 別把時間和資源浪費在非黑即白的爭吵上 ， 而是對每個選項進行灰度數值的確認。

當我們擁有一個觀點時，不管多麼自信，不管自己多麼喜歡這個觀點，都要意識到，這個觀點不可能是百分之百正確的。既然如此，我們就要冷靜地思考一下，這個觀點的可能性到底是多大呢？這個數值，是介於0 和 100%之間的，這就是灰度認知。

灰度認知的底層是概率思維。不管你的某個信念多麼堅定，都要在前面加上一個概率數值。

可信度加權

我們總有一個錯覺，認為厲害的人做什麼都能成功，其實並非如此。

達利歐的公司，是世界上最大的對沖基金，其實他犯過很多慘重的錯誤。這使得他重新制定了公司作決策的方法，也就是後來被很多人提及的可信度加權。用了這個方法，橋水基金的投資決策質量大大提高了，而且非常穩定。這個方法非常有價值，雖然《原則》這本書很火，但真正理解這個概念的人很少。我覺得很有必要好好解

釋一下，這就是一個典型的「對灰度估值」的決策方式。

具體他們是怎麼做的呢？

「加權」的意思就是「乘以權重」，舉個例子，你要開一個家庭會議，就要不要買洗碗機表態，但是每個人的意見權重不一樣，比方說太太的權重是 50%，老公的權重是 25%，小孩的權重占 25%。最後統計的時候，太太的一票，就相當於老公的兩票。

聽起來很簡單吧，其實達利歐在橋水基金採用的工作方法就是這樣：

這群專家都有表達意見的權利，但根據每個人過往的表現不一樣，給每個人的意見權重也不一樣， 對於那些 能力更強的決策者的觀點，賦予更大的權重 。最後經過簡單的計算，得出一個群體意見。2012 年，橋水基金公司內部討論關於歐債危機的決策難題，結果意見形成分歧，一半兒的人認為歐洲央行會印更多鈔票來購買債券，另外一半兒人則反對。怎麼辦呢？運用可信度加權的分析系統來打破僵局。這不是無差別的民主，也不是獨裁，而是把每個人的可信度納入考量。

具體辦法是 ，他們先用自己發明的集點器工具， 收集大家對一個問題的不同想法，可能會收集好幾十種。

然後其他人就可以對你的想法打分 ， 再給打分的人賦予一定的權重。 比如達利歐就說，一個實習生對他的想法打了 3 分，而滿分是 10 分，也就是很差的意思。

但是因為這個實習生的資歷比較淺，他打出來的分數權重不會太高。可能另一個權重高的人，贊同達利歐的這個想法，這個想法的得分依舊會比較高。就這樣，經過一系列的計算，再算出來這些想法的得分，最後得到一個群體決策的結果。這就是一次可信度加權決策程序。

後來，橋水基金果然正確預測出歐洲央行會印更多鈔票。

獨立思考是很重要，一個聰明人的思考是很有價值的。 但更好的辦法是有一群獨立思考者，對他們的判斷進行加權。你就會長期得出比任何一個人，質量更高、更穩定的判斷。

我們再來看看什麼叫黑白決策。

黑白決策就是要敢拍板，作出非黑即白的決定，不要模稜兩可、猶豫不決。決策者是要為其他人負責的。就像在戰場上打仗， 指令必須清晰，黑白分明，不能含糊。這就是領導的意義和價值 。所以，對於決策者來說，所承擔的責任就是，告訴夥伴們，這件事做還是不做。

本講小結

事實上，這個世界上所有的知識都具有不確定性，包括這句話本身。

面對不確定性，我們只有容忍不確定性的存在，用灰度的方法去認知，去盡量測量它的灰度數值，才可能向真理逼近一步。

灰度認知，就是開放地考慮各個維度的選項，並賦予權重。

黑白決策，就是根據計算結果，給出清晰果斷的選擇。

其實，做好了灰度認知，黑白決策也不是什麼難題了。

從達利歐公司的決策方法中，我們可以得到啟發，一群專業人士的意見加權，遠遠比一個人更可靠。所以，我們可以為自己打造出一個專家意見團，在不確定的復雜決策面前，提高我們的勝率。

在現實中，我們要敢於決策，不要猶豫不決。只有作出決策，人生才會在你的面前展開。

思考題

如果你有個朋友被醫院檢查出了重病，但是去另一家醫院復查，醫生卻說沒病。用今天講到的可信度加權的辦法，你可以建議他怎麼做？

劃重點

灰度認知就是分析各種選項的權重，給它們的可能性估值。黑白決策是決策環節，要清晰果斷地給出結論。

認知環節不要為了立場，非黑即白地搞辯論，而是要去分析每種可能性的灰度。

你可以用可信度加權的工具，避免個人決策的偏差，提高正確率。