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

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

報(bào)告人:張成芬

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

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

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

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

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

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

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

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

固體退火概念與優(yōu)化問題的對(duì)應(yīng)關(guān)系213.模擬退火算法

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

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

否則，從當(dāng)前解Xi的鄰域中產(chǎn)生一個(gè)新解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)化算法意大利學(xué)者M(jìn).Dorigo于1991年，在他的博士論文中首次系統(tǒng)地提出了一種基于螞蟻種群的新型優(yōu)化算法—螞蟻算法（antcolonyalgorithms）。人工蟻群和自然界蟻群的區(qū)別在于，人工蟻群有一定的記憶能力。另外，人工蟻群在選擇下一條路徑的時(shí)候，是按一定的算法規(guī)律有意識(shí)地尋找最短路徑。每個(gè)連接上的信息素痕跡的濃度會(huì)自動(dòng)逐漸揮發(fā)，信息素痕跡的揮發(fā)過程主要用于避免算法太快地向局部最優(yōu)區(qū)域集中。264.蟻群優(yōu)化算法軌跡更新:預(yù)見度:

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

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

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

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

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

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

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

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

交叉前：

00000|0111000000001000011100|00000111111000101

交叉后：

00000|0000011111100010111100|011100