第三章 高級搜索
- 局部搜索方法
- 模擬退火方法
- 遺傳算法
高級搜索其實就是求組合優(yōu)化問題的解钞脂，之前的運籌學（還是叫別的什么名字來的）這門課上都學過扒秸，也是美賽的必備技能之一。
優(yōu)化問題的一般描述：
在x的定義域D上埃脏，求f滿足條件g的極值max f 或min f
（簡書什么時候能支持公式啊\怨念）
局部搜索
基本思想：始終向著離目標最近的方向搜索阴孟。
（這里不做特殊說明，則默認是求最小值）
步驟：
- 隨機選擇一個解x_0昼榛，生成鄰域P境肾。
鄰域的生成方法有很多種剔难，比如旅行商問題中胆屿，選擇兩個點交換，將所有可能的交換結(jié)果列出來偶宫，得到的就是原始解的鄰域非迹。 - 如果P為空，則結(jié)束計算纯趋。否則憎兽，從P中任選一個元素x_n。
- 如果f(x_n)<f(x_0)吵冒，則把這個解作為新解纯命，更新鄰域P。
- 否則痹栖，P=P-{x_n}亿汞。
- 轉(zhuǎn)到2
以上步驟的一個明顯問題：容易陷入局部最優(yōu)。只要找到一個極值點揪阿，就會停止計算疗我。有三種改進的思路：
-
改進1：按照f的值隨機選點。
- 課件上模擬退火在用這個隨機的時候南捂，方法是按照Metropolis準則來轉(zhuǎn)換狀態(tài)吴裤。在P中隨機選一個解，f減小則選中溺健，f增大則按照玻爾茲曼分布選中麦牺。
- 改進2：每次選點之后都改變一下步長。
-
改進3：散布不同的初值點進行搜索，在最終結(jié)果中找出最優(yōu)的枕面。
Remark：本章之后的算法都是上述改進的組合愿卒。上述改進1和改進2結(jié)合，就形成了模擬退火算法潮秘。
模擬退火
在上述改進1的基礎上琼开，按照Metropolis準則進行狀態(tài)轉(zhuǎn)化：
當從狀態(tài)i轉(zhuǎn)為狀態(tài)j時，如果E(j)<=E(i)枕荞，則接受轉(zhuǎn)化狀態(tài)柜候；否則，以Boltzman分布接受躏精，即以概率:
$e^{\frac{E(i)-E(j)}{KT}}$
接受渣刷。
其中E是待優(yōu)化的函數(shù)，T是溫度矗烛，K是玻爾茲曼常數(shù)辅柴。
之后的重點基本上就是算法的實現(xiàn)。有以下幾個點：
- 初始溫度的選炔t吃÷掂郑?/li>
- 溫度的衰減函數(shù)；
- 算法的終止準則歪架；
- 每個溫度下的馬爾科夫鏈長度（也就是要算多少次）股冗；
起始溫度的選擇
初始溫度要盡量大，使得$e^{\frac{E(i)-E(j)}{KT}}\approx 1$
可以直接給定和蚪，也可以用升溫的辦法求取止状。先給定一個小的溫度，然后產(chǎn)生一個鄰域攒霹，算一下被接受的概率怯疤。如果符合設想的值（比如0.98），那么就接受催束；否則就升溫集峦。
溫度下降
可以采用等比例下降、等值下降或者平衡分布的方法泣崩。
每一溫度下的馬爾科夫鏈長度
- 固定長度
- 被接受的狀態(tài)數(shù)到達一定值
- 接受率到達一定值
- 兩代之間的指標函數(shù)差值小于一定值
算法的終止
- 當溫度小于一定值（零度法）
- 當溫度下降的次數(shù)達到一定值（循環(huán)總控制法）
- 當溫度下降后少梁，指標函數(shù)沒有變化（無變化控制法）
- 除了當前最優(yōu)之外，其他狀態(tài)的接受概率都很小
- 相對誤差估計法
遺傳算法
遺傳算法就是根據(jù)進化論推出來的一個算法——其實這樣說有種戴個很大的帽子的感覺……遺傳算法就是前面提到的隨機搜索算法的改進1和改進3的組合矫付。每一代通過選擇凯沪、交叉、變異這三個步驟买优，生成子代妨马。最后選擇整個進化過程中最優(yōu)的后代挺举。
選擇過程對應著改進1，用很多隨機初始點進行模擬對應著改進3烘跺。對前面的部分理解了之后這一部分就沒什么難的了湘纵。
比較困難的部分是編碼。不過這一部分屬于工程處理問題滤淳，大概不會考梧喷，期末復習筆記就不寫了。
