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

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

報告人:張成芬

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

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

啟發(fā)式算法是一種技術，該技術使得能在可接受的計算費用內去尋找盡可能好的解，但不一定能保證所得解的可行性和最優(yōu)性，甚至在多數(shù)情況下，無法描述所得解與最優(yōu)解的近似程度。42.應用領域52.應用領域工程領域1998年，Mason等采用MINSGA算法，實現(xiàn)了星座的優(yōu)化設計。目標：最小化衛(wèi)星個數(shù)最大化不間斷全球覆蓋百分比并與公開發(fā)表的結果對比驗證算法的優(yōu)化性能62.應用領域科學領域物理、化學、生態(tài)學醫(yī)學、計算機科學等1993年，Jones等用多目標遺傳算法進行分子結構分析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年的時間。理論上可以計算的問題，實際上并不一定能行，這屬于算法復雜性方面的研究內容。103.研究意義P（polynominal）所有可以在多項式時間內用確定算法求解的優(yōu)化問題的集合，簡稱多項式問題。判定問題（decisionproblem）如果一個問題的每一個實例只有“是”或“否”兩種答案。NP（nondeterministicpolynominal）是指可以在多項式時間里驗證一個解的判定問題的集合。113.研究意義千禧年數(shù)學難題（2000-5-24，美國的克雷(Clay)數(shù)學研究所，在巴黎法蘭西學院宣布每一個懸賞一百萬美元）

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

，則指數(shù)災難無法避免。P=?NP（P-NP問題）P=NPPNP現(xiàn)在的估計13報告內容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）若在該溫度下達到內循環(huán)終止條件，則轉到步驟（3）

否則，從當前解Xi的鄰域中產(chǎn)生一個新解Xj，若F(Xj)≤F(Xi),則F(Xi)=F(Xj)；否則，以概率接收新解。（3）降溫，Tk+1=dTk；k=k+1，若滿足終止條件，算法結束否則，轉步驟（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)勢是決定性的，遠大于對食物的競爭帶來的劣勢?！?85.粒子群優(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í)行，直到獲得一個令人滿意的結果或符合終止條件為止。316.遺傳算法進化過程優(yōu)化過程生物進化過程是一個自然，并行，穩(wěn)健的優(yōu)化過程，這一優(yōu)化過程的目的在于使生命體達到適應環(huán)境的最佳結構與效果，而生物種群通過“優(yōu)勝劣汰”及遺傳變異來達到進化（優(yōu)化）目的的。326.遺傳算法遺傳算法(GeneticAlgorithm)是由美國的J.Holland教授于1975年在他的專著《AdaptationinNaturalandArtificialSystems》中首先提出的?；具z傳算法的構成要素

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

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

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

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

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

交叉前：

00000|0111000000001000011100|00000111111000101

交叉后：

00000|0000011111100010111100|01110000000010000交叉點366.遺傳算法

變異前：

000001110000000010000

變異后：

000001110001000010000變異點376.遺傳算法產(chǎn)生初始群體基本位變異新一代群體最佳個體計算個體適應度是否滿足停止準則比例選擇單點交叉SGA流程圖NY387.非支配排序遺傳算法快速非支配遺傳算法（NSGA-II）具有計算復雜度低、全局搜索能力強等優(yōu)點，已經(jīng)成為多目標進化算法的基準算法之一，并成功應用于求解各種復雜的工程優(yōu)化問題。39數(shù)學模型n個決策變量，r個目標函數(shù)(相互沖突)

其中為決策變量尋求,使?jié)M足約束的同時達到最優(yōu)。40概念Pareto最優(yōu)解支配關系Pareto最優(yōu)解對于一些解，不可能進一步優(yōu)化某一個或某幾個目標而其他目標不至于劣化，因此也稱非劣最優(yōu)解。數(shù)學描述給定一個多目標優(yōu)化問題min

f(X),設X*∈Ω，若不存在X∈Ω使其滿足f(X)≤f(X*)，則稱X*∈Ω為Pareto最優(yōu)解。

41概念Pareto最優(yōu)解支配關系支配關系設p和q是進化群體pop中任意兩個不同的個體，稱p支配q，當滿足下面兩個條件：①對所有的子目標，p不比q差即fk(p)≤fk(q),(k=1,2,…,r)②至少存在一個子目標，使p比q好即存在l∈{k=1,2,…,r}，使fl(p)<fl(q)

這時，p稱非支配的，q稱被支配的

42概念Pareto最優(yōu)解支配關系...........ABFCDEKJGIH437.非支配排序遺傳算法產(chǎn)生初始群體P快速非支配排序虛擬適應度計算錦標賽選擇交叉和變異得到子種群QR=P∪Q計算各目標函數(shù)值計算各目標函數(shù)值快速非支配排序選前N個個體作為父代個體P達到最大代數(shù)?結束開始代數(shù)加1精英策略

否是NSGAⅡ流程圖447.非支配排序遺傳算法產(chǎn)生初始群體P快速非支配排序虛擬適應度計算錦標賽選擇交叉和變異得到子種群QR=P∪Q計算各目標函數(shù)值計算各目標函數(shù)值快速非支配排序選前N個個體作為父代個體P達到最大代數(shù)?結束開始代數(shù)加1精英策略

否是NSGAⅡ流程圖457.非支配排序遺傳算法快速非支配排序P’=find-nondominated-front(P)P’={1}將第一個個體放入P’中foreachp∈P∧p∈P’每次取一個個體P’=P’∪{p}將個體p臨時放入P’中foreachq∈P’∧q≠p比較p與P’中其它個體q之間的支配關系ifp＞q,thenP’=P’\{q}若p支配q，則刪除qelseifq＞p,thenP’=P’\{p}若q支配p，則刪除p復雜度：最壞的情況下，N個個體均為非支配個體時比較操作的總次數(shù)為1+2+3+…+(N-1)=N2/2若有r個目標，則總的時間復雜度為O(rN2)467.非支配排序遺傳算法虛擬適應度計算首先要對每個目標升序排序擁擠距離：個體與其相鄰的兩個個體在每個目標上的距離差之和對于兩個目標，個體i的擁擠距離為四邊形的長寬之和.i+1..i-1.i.。。。。。。477.非支配排序遺傳算法錦標賽選擇

經(jīng)過排序和擁擠距離的計算，每個個體擁有兩個屬性：非支配序irank和擁擠距離id。選擇的規(guī)則如下：若兩個個體非支配排序不同,取序號低的個體；若兩個個體在同一級,取周圍較不擁擠的個體。交叉和變異實數(shù)編碼時，采用SBX交叉和正態(tài)變異SBX(simulatedbinarycrossover)交叉，模擬二進制交叉過程，對給定的隨機交叉點，交換位于交叉點一側的部分48報告內容一啟發(fā)式優(yōu)化算法研究背景二啟發(fā)式優(yōu)化算法簡介4三應用實例49函數(shù)的優(yōu)化結果三.應用實例——遺傳算法圖3.函數(shù)優(yōu)化結果50三.應用實例——粒子群優(yōu)化算法函數(shù)的優(yōu)化結果圖4.函數(shù)優(yōu)化結果三.應用實例——粒子群優(yōu)化算法

函數(shù)驗證51三.應用實例——粒子群優(yōu)化算法

函數(shù)驗證參數(shù)：M=20MaxGe=2000RunN=5052三.應用實例——干式空心電抗器的優(yōu)化設計53干式空心電抗器的結構：54三.應用實例——干式空心電抗器的優(yōu)化設計目標函數(shù)設計變量約束附加等式約束和層電流密度約束三.應用實例——干式空心電抗器的優(yōu)化設計55三相平放電抗器組設計結果如下：1.額定電參數(shù)：容量Sn=50.00KVar電壓Un=317.50V電流In=157.50A頻率fn=50.00Hz電感Ln=6.42mH絕緣等級：B

2.單相線圈數(shù)據(jù)：電感為：6.42mH

序號中徑(mm)線圈高(mm)匝數(shù)并繞根數(shù)裸線直徑(mm)電阻(ohm)電流(A)電密(A/mm2)1859.00298.1093.8712.851.1248.3601.312865.20292.0091.9512.851.1098.4531.333871.40286.9090.3512.851.0978.4941.334877.50282.7089.0412.851.0898.4891.33第1包封：線徑=2.85mm溫升=55.48℃_________________________________________________________________________________________________5940.20297.1080.5013.350.76310.8661.236947.40293.2079.4313.350.75910.8241.237954.60290.2078.6413.350.75710.7791.22第2包封：線徑=3.35mm溫升=63.21℃_________________________________________________________________________________________________81018.00287.6073.8113.550.67511.7201.1891025.50285.5073.28