最優(yōu)化方法課程大作業(yè)實驗課件

1、最優(yōu)化方法登山搜索算法1、產(chǎn)生一個初始點2、向臨域最高的方向移動偽代碼問題: 依賴于初始狀態(tài), 容易陷入局部最優(yōu)改進(jìn)：1、局部束搜索：隨機(jī)產(chǎn)生多個初始點，并行搜索（多幾個人從不同位置開始爬山，能到達(dá)最高點的概率就大大增大）2、隨機(jī)重啟：在指定步以后，簡單地隨機(jī)選取一個狀態(tài)重新開始登山搜索.模擬退火算法模擬退火算法是對登山算法的一種改進(jìn)，以一定的概率接受更差的解，從而跳出局部最優(yōu)的限制采用傳統(tǒng)的登山搜索策略，但是 不時朝產(chǎn)生改進(jìn)解的方向移動，即下山移動(downhill moves). 隨著時間的推移, 采取下山移動的概率逐漸降低，并且下山移動的步長逐漸減小1、產(chǎn)生初始點2、隨機(jī)向周邊移動3、移

2、動后結(jié)果更優(yōu)則接受4、移動后結(jié)果更差，則以一定的概率接受模擬退火模擬的是高溫物體自然降溫的過程，當(dāng)溫度較高的時候，分子運動速度快，接受更差解的概率更大時間增加溫度隨時間變化的函數(shù)如果溫度降為零，則跳出循環(huán)隨機(jī)選擇當(dāng)前點周圍的一個點群智能鳥群算法 Separationavoid crowding local flockmates Alignmentmove towards the average heading of local flockmates Cohesionmove toward the average position of local flockmates 模擬鳥群的三個性質(zhì)：鳥群

3、的個體之間不會相撞鳥群有一個共同的目標(biāo)方向個體會向團(tuán)體中心聚攏產(chǎn)生初始點陣，每個點都有自己的運動方向與速度，這些點總體向著歷史最優(yōu)解方向移動，并且向當(dāng)前所有點中的最優(yōu)點聚攏x* = PSO()P = Particle_Initialization();For i=1 to it_max For each particle p in P do fp = f(p); If fp is better than f(pBest) pBest = p; end end gBest = best p in P; For each particle p in P do v = v + c1*rand*(pB

4、est p) + c2*rand*(gBest p); p = p + v; endend偽代碼初始化一粒子群時間對與每一個粒子計算該粒子所在位置的權(quán)值找出此時所有粒子中最優(yōu)的pbest維護(hù)歷史（全局）最優(yōu)的粒子gbest對于每個粒子，速度（矢量）變化，并朝速度方向移動蟻群算法模擬蟻群尋最短路的算法1、螞蟻在行進(jìn)的過程會留下信息素，當(dāng)碰到分叉的時候，螞蟻會傾向于走信息素濃度更大的路徑（傾向于表示有更大的概率而非一定）2、信息素會隨著時間的延長而稀釋（某些算法不會考慮）3、螞蟻行進(jìn)的速度是一樣的，因此在單位時間內(nèi)，短路徑上的螞蟻數(shù)量比長路徑上的螞蟻數(shù)量要多，從而螞蟻留下的信息素濃度也就越高偽代碼

5、遺傳算法DNA鏈上記載有信息模擬自然界生物的遺傳基因會發(fā)生變異自然（人工）選擇，適者生存0123456789初始化基因夏娃D(zhuǎn)NA鏈復(fù)制并發(fā)生變異0123456789父代012745389S1代0123456789父代012745389S1代0123546789S2代017245389P1代總量小于容量，指數(shù)繁殖依據(jù)規(guī)則進(jìn)行選擇0123456789012745389017245389繼續(xù)繁殖與選擇幸存者Init();For icapability) kill();初始化夏娃D(zhuǎn)NA在規(guī)定的時間內(nèi)活的基因進(jìn)行繁殖DNA鏈的復(fù)制DNA鏈的突變與重組選擇并殺死劣質(zhì)基因偽代碼元啟發(fā)式算法（metaheur

6、istic）元啟發(fā)式算法是一種尋優(yōu)能力很強(qiáng)的啟發(fā)式算法。元啟發(fā)式算法一種智能搜索算法，它的搜索空間由問題實例的解構(gòu)成，通常涵蓋完整的問題解空間。如果問題有n個解，一個啟發(fā)式規(guī)則只能對應(yīng)于n個解中的一個。啟發(fā)式規(guī)則既可能產(chǎn)生很好的解，也可能產(chǎn)生很差的解。元啟發(fā)式算法原理1. 從一個或多個候選解開始作為初始值(pop(t)；2. 根據(jù)初始值計算目標(biāo)函數(shù)值；3. 基于已獲得的信息，通過個體變異、組合等方法不斷更新候選解域；4. 新的候選解域進(jìn)入下一輪迭代(pop(t+1)。元啟發(fā)算法相當(dāng)于在整個解空間內(nèi)搜索最優(yōu)解，當(dāng)運行時間無限大時，理論上可以得到全局最優(yōu)解。但是當(dāng)問題規(guī)模不斷擴(kuò)大，使用元啟發(fā)算法的效率也會降低。超啟發(fā)算法通過制定高層控制策略來操縱底層貪心策略，從而壓縮解空間，達(dá)到剪枝的目的（最優(yōu)解所在的空間有可能被剪掉）?？梢赃@樣理解：元啟發(fā)算法是隨機(jī)交換，而超啟發(fā)算法交換的時候要