啟發(fā)式優(yōu)化算法介紹

啟發(fā)式優(yōu)化算法介紹

報告人:張成芬

1報告內(nèi)容一啟發(fā)式優(yōu)化算法研究背景二啟發(fā)式優(yōu)化算法簡介4三應用實例2一.啟發(fā)式優(yōu)化算法研究背景1.概念2.應用領域3.研究意義31.概念啟發(fā)式算法（heuristicalgorithm）定義1

一種基于直觀或經(jīng)驗構(gòu)造的算法，在可接受的耗費（指計算時間、占用空間等）下給出待解決優(yōu)化問題每一實例的一個可行解，該可行解與最優(yōu)解的偏離程度未必可事先估計。啟發(fā)式算法定義2

啟發(fā)式算法是一種技術，該技術使得能在可接受的計算費用內(nèi)去尋找盡可能好的解，但不一定能保證所得解的可行性和最優(yōu)性，甚至在多數(shù)情況下，無法描述所得解與最優(yōu)解的近似程度。42.應用領域52.應用領域工程領域1998年，Mason等采用MINSGA算法，實現(xiàn)了星座的優(yōu)化設計。目標：最小化衛(wèi)星個數(shù)最大化不間斷全球覆蓋百分比并與公開發(fā)表的結(jié)果對比驗證算法的優(yōu)化性能62.應用領域科學領域物理、化學、生態(tài)學醫(yī)學、計算機科學等1993年，Jones等用多目標遺傳算法進行分子結(jié)構(gòu)分析73.研究意義漢諾塔問題：和尚搬盤子天神梵天的三條規(guī)則：每次只能移動一個盤子；盤子只能在三根柱子上來回移動，不能放在他處；在移動過程中，三根柱子上的盤子必須始終保持大盤在下，小盤在上。83.研究意義當n=64時，移動次數(shù)=？花費時間=？

h(n)=2h(n-1)+1=2(2h(n-2)+1)+1=22h(n-2)+2+1=23h(n-3)+22+2+1……=2nh(0)+2n-1+…+22+2+1=2n-1+…+22+2+1=2n-1

需要移動盤子的次數(shù)為：

264-1=1844674407370955161593.研究意義假定每秒移動一次，一年有31536000秒，則僧侶們一刻不停地來回搬動，也需要花費大約5849億年的時間。假定計算機以每秒1000萬個盤子的速度進行搬遷，則需要花費大約58490年的時間。理論上可以計算的問題，實際上并不一定能行，這屬于算法復雜性方面的研究內(nèi)容。103.研究意義P（polynominal）所有可以在多項式時間內(nèi)用確定算法求解的優(yōu)化問題的集合，簡稱多項式問題。判定問題（decisionproblem）如果一個問題的每一個實例只有“是”或“否”兩種答案。NP（nondeterministicpolynominal）是指可以在多項式時間里驗證一個解的判定問題的集合。113.研究意義千禧年數(shù)學難題（2000-5-24，美國的克雷(Clay)數(shù)學研究所，在巴黎法蘭西學院宣布每一個懸賞一百萬美元）

/millennium之一：P(多項式算法)問題對NP(非多項式算法)問題，即P=NP？之二：霍奇(Hodge)猜想之三：龐加萊(Poincare)猜想之四：黎曼(Riemann)假設之五：楊-米爾斯(Yang-Mills)存在性和質(zhì)量缺口之六：納維葉-斯托克斯(Navier-Stokes)方程的存在性與光滑性之七：貝赫(Birch)和斯維訥通-戴爾(Swinnerton-Dyer)猜想123.研究意義現(xiàn)在的估計如果

，則指數(shù)災難無法避免。P=?NP（P-NP問題）P=NPPNP現(xiàn)在的估計13報告內(nèi)容1啟發(fā)式優(yōu)化算法研究背景2啟發(fā)式優(yōu)化算法簡介43應用實例14二.啟發(fā)式優(yōu)化算法簡介1.貪婪算法2.禁忌搜索算法3.模擬退火算法4.蟻群優(yōu)化算法5.粒子群優(yōu)化算法6.遺傳算法7.非支配排序遺傳算法151.貪婪算法有一個顧客拿一張面值100元的鈔票在超市買了5元錢的商品，收銀員需找給他95元零錢，售貨員在找零錢時可有多種選擇。為使找的零錢數(shù)目最少。收銀員通常憑直覺采用的方法，就是一種典型的貪婪算法（greedymethod）。161.貪婪算法在算法的每個階段，都作出在當時看上去最好的決策，以獲得最大的“好處”，換言之，就是在每一個決策過程中都要盡可能的“貪”，直到算法中的某一步不能繼續(xù)前進時，算法才停止。在算法的過程中，“貪”的決策一旦作出，就不可再更改，作出“貪”的決策的依據(jù)稱為貪婪準則。局部搜索的缺點就是太貪婪地對某一個局部區(qū)域以及其鄰域搜索，導致一葉障目，不見泰山。172.禁忌搜索算法一群兔子去尋找世界上最高的山峰兔子們找到了泰山，它們之中的一只就會留守在這里，其他的會有意識地避開泰山。這就是禁忌搜索中“禁忌表（tabulist）”的含義。那只留在泰山的兔子一定時間后重新回到找最高峰的大軍，這個歸隊時間，在禁忌搜索里面叫做“禁忌長度（tabulength）”；如果在搜索的過程中，兔子們找到的地方全是華北平原等比較低的地方，就可以不顧及有沒有兔子留守，都把泰山重新考慮進來，這就叫“特赦準則（aspirationcriterion）”。

182.禁忌搜索算法Glover在1986年提出禁忌搜索的概念，進而形成一套完整的算法。為了找到“全局最優(yōu)解”，就不應該執(zhí)著于某一個特定的區(qū)域。禁忌搜索就是對于找到的一部分局部最優(yōu)解，有意識地避開它（但不是完全隔絕），從而獲得更多的搜索區(qū)間。193.模擬退火算法模擬退火（simulatedannealing）算法的思想最早是由Metropolis等人在1953年提出。1982年，Kirkpatrick等人將其運用在求組合最優(yōu)化的問題上。金屬物體在加熱到一定的溫度后，再徐徐冷卻使之凝固成規(guī)整晶體的熱力學過程。在溫度最低時，系統(tǒng)能量趨于最小值。根據(jù)熱力學定律，在溫度為T的情況下，能量改變所表現(xiàn)的幾率如下：k是Boltzmann’sConstant。203.模擬退火算法固體退火模擬退火算法金屬物體狀態(tài)能量溫度T能量最低的狀態(tài)某一溫度下趨于熱平衡的過程優(yōu)化問題解目標函數(shù)控制參數(shù)t最優(yōu)解產(chǎn)生新解-判斷-接受/舍棄接收概率：

固體退火概念與優(yōu)化問題的對應關系213.模擬退火算法

算法的實現(xiàn)步驟

（1）隨機產(chǎn)生一個初始解X0，給定初始溫度Tmax。（2）若在該溫度下達到內(nèi)循環(huán)終止條件，則轉(zhuǎn)到步驟（3）

否則，從當前解Xi的鄰域中產(chǎn)生一個新解Xj，若F(Xj)≤F(Xi),則F(Xi)=F(Xj)；否則，以概率接收新解。（3）降溫，Tk+1=dTk；k=k+1，若滿足終止條件，算法結(jié)束否則，轉(zhuǎn)步驟（2）。224.蟻群優(yōu)化算法AC234.蟻群優(yōu)化算法AC244.蟻群優(yōu)化算法AC254.蟻群優(yōu)化算法意大利學者M.Dorigo于1991年，在他的博士論文中首次系統(tǒng)地提出了一種基于螞蟻種群的新型優(yōu)化算法—螞蟻算法（antcolonyalgorithms）。人工蟻群和自然界蟻群的區(qū)別在于，人工蟻群有一定的記憶能力。另外，人工蟻群在選擇下一條路徑的時候，是按一定的算法規(guī)律有意識地尋找最短路徑。每個連接上的信息素痕跡的濃度會自動逐漸揮發(fā)，信息素痕跡的揮發(fā)過程主要用于避免算法太快地向局部最優(yōu)區(qū)域集中。264.蟻群優(yōu)化算法軌跡更新:預見度:

ij=1/dij表示殘留信息的相對重要程度表示預見度的相對重要程度信息素的揮發(fā)因子表示第K只螞蟻在本次循環(huán)中留在路徑ij上的信息量275.粒子群優(yōu)化算法生物社會學家E.O.Wilson指出：“至少從理論上，在搜索食物過程中群體中個體成員可以得益于所有其他成員的發(fā)現(xiàn)和先前的經(jīng)歷。當食物源不可預測地零星分布時，這種協(xié)作帶來的優(yōu)勢是決定性的，遠大于對食物的競爭帶來的劣勢。”285.粒子群優(yōu)化算法每個尋優(yōu)的問題解都被想像成一條魚，也稱為“Particle”。所有的Particle都有一個fitnessfunction以判斷目前的位置之好壞，每一個Particle具有記憶性，能記得所搜尋到最佳位置。每一個Particle還有一個速度以決定飛行的距離與方向。29局部最優(yōu)解全局最優(yōu)解運動向量速度向量StudyFactorHereIam!Thebest

positionofteamMybestpositionx(t)pgpivPBestgBestx(t+1)速度與位置更新30

5.粒子群優(yōu)化算法（1）將群族做初始化，以隨機的方式求出每一Particle之初始位置與速度。（2）依據(jù)fitnessfunction計算出其fitnessvalue以作為判斷每一個Particle之好壞。（3）找出每一個Particle到目前為止的搜尋過程中最佳解，這個最佳解稱之為Pbest。（4）找出所有群體中的最佳解，此最佳解稱之為Gbest。（5）根據(jù)速度與位置公式更新每一Particle的速度與位置。（6）返回步驟2繼續(xù)執(zhí)行，直到獲得一個令人滿意的結(jié)果或符合終止條件為止。316.遺傳算法進化過程優(yōu)化過程生物進化過程是一個自然，并行，穩(wěn)健的優(yōu)化過程，這一優(yōu)化過程的目的在于使生命體達到適應環(huán)境的最佳結(jié)構(gòu)與效果，而生物種群通過“優(yōu)勝劣汰”及遺傳變異來達到進化（優(yōu)化）目的的。326.遺傳算法遺傳算法(GeneticAlgorithm)是由美國的J.Holland教授于1975年在他的專著《AdaptationinNaturalandArtificialSystems》中首先提出的?；具z傳算法的構(gòu)成要素

（1）染色體的編碼（產(chǎn)生初始群體）（2）適應度函數(shù)（3）遺傳算子（選擇、交叉、變異)（4）運行參數(shù)336.遺傳算法生物的進化機制自然選擇

適應環(huán)境的個體具有更高的生存能力，同時染色體特征被保留下來。雜交

隨機組合來自父代的染色體上的遺傳物質(zhì)，產(chǎn)生不同于它們父代的染色體。突變

隨機改變父代的染色體基因結(jié)構(gòu)，產(chǎn)生新染色體。346.遺傳算法幾個術語基因型：

1000101110110101000111表現(xiàn)型：0.637197編碼解碼個體（染色體）基因356.遺傳算法

交叉前：

00000|0111000000001000011100|00000111111000101

交叉后：

00000|0000011111100010111100|011100