本章概要

本章介紹了優(yōu)化問題的基本概念，以及常見的優(yōu)化算法（隨機(jī)搜索，爬山，模擬退火，遺傳算法）。讀完本章后，感覺茅塞頓開，之前一直認(rèn)為遺傳算法高深莫測，原來這些算法都是根據(jù)生物，物理的啟發(fā)而來的，頓時親切了許多。

?

什么是優(yōu)化（Optimization）

一個問題的解有一系列組合，在這些組合中找出最優(yōu)的解的過程就是優(yōu)化。最笨的方法，枚舉出所有可能的結(jié)果，找出最優(yōu)的解。但是，往往可能性太多，計算機(jī)根本上無法枚舉出所有的解決方案。

?

成本函數(shù)（Cost Function）

最優(yōu)的解決方案在成本函數(shù)中得到最大或最小值。成本函數(shù)是指導(dǎo)優(yōu)化繼續(xù)進(jìn)行的根本。

?

優(yōu)化算法

• 隨機(jī)搜索：計算一組隨機(jī)的組合方案，在這個方案中找到最優(yōu)秀解，比較盲目，有可能最優(yōu)解并不在這個隨機(jī)的解決方案中。
• 爬山：個人理解就是貪心算法，找到相比于當(dāng)前解決方案而言最優(yōu)的相鄰方案，如此往復(fù)，直到找不到更優(yōu)的方案為止。顯著的問題就是只能找到局部最優(yōu)解，無法找到全局最優(yōu)解。改進(jìn)算法是當(dāng)找到一個最優(yōu)解后，隨機(jī)開始另一組探尋，多嘗試幾次。這樣，雖然可以找到全局最優(yōu)解，但是不能保證每次都可以。
• 模擬退火（Simulated Annealling）:此方法受物理中鍛造合金的啟發(fā)，首先將合金加熱到一個高的溫度，然后慢慢冷卻，在冷卻過程中，可以找到low energy configuration。算法大體思想與爬山有點類似，首先隨機(jī)選取一個相鄰的解決方案，如果更優(yōu)，那么選取，否則，不拒絕，也不選取，會通過一個概率計算到底是拒絕還是選取，開始時，此概率會比較大，溫度比較高，但是每一次選舉后，溫度會降低，選擇較差方案的概率會降低。當(dāng)溫度降到一定程度，過程結(jié)束。這個方法可以使得優(yōu)化在開始時，允許出現(xiàn)非最優(yōu)解，這樣可以加大找到全局最優(yōu)解的機(jī)會。
• 遺傳算法（Genetic Algorithm）:遺傳算法受到生物遺傳的啟發(fā)，主要思路是首先隨機(jī)組合第一代解決方案，根據(jù)目標(biāo)函數(shù)的結(jié)果排序，取出最優(yōu)的一部分作為第二代（稱之為精英），其他的全部淘汰掉（是不是很殘忍），然后在在精英中通過突變或者雜交的方式，創(chuàng)建出第其他的方案，稱之為第二代，然后對第二待排序，任然取出精英，如此往復(fù)，直到精英基本不變或者代數(shù)到達(dá)一定上限時結(jié)束。

?

優(yōu)化算法的不足

上面提到的優(yōu)化算法依賴一個事實，最優(yōu)解通常與次優(yōu)解較近，但是如果較遠(yuǎn)，如下圖所示：

全局最優(yōu)點在比較靠右的地方，但是由于最優(yōu)點的兩邊是一些不好的點，所以根據(jù)上面的優(yōu)化算法，找到全局最游解的概率不高。如果解空間無規(guī)律，那么可能隨機(jī)搜索會比其他優(yōu)化方案更好。

總結(jié)

以上是生活随笔為你收集整理的读书笔记《集体智慧编程》Chapter 5 : Optimization的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。