智能優(yōu)化概述課件

4.1智能優(yōu)化概述4.1智能優(yōu)化概述1傳統(tǒng)優(yōu)化理論與方法的局限性函數(shù)優(yōu)化問(wèn)題定義增廣目標(biāo)函數(shù)，轉(zhuǎn)化約束優(yōu)化問(wèn)題為無(wú)約束優(yōu)化問(wèn)題；基于梯度類方法求解無(wú)約束優(yōu)化問(wèn)題的局部最優(yōu)解。傳統(tǒng)理論方法面向的問(wèn)題傳統(tǒng)方法思路與步驟（1）選取初始點(diǎn)（2）構(gòu)造下降搜索方向（3）確定搜索方向上的步長(zhǎng)（4）（5）滿足終止條件，停止迭代，當(dāng)前解；否則，k=k+1,轉(zhuǎn)第2步傳統(tǒng)優(yōu)化理論與方法的局限性函數(shù)優(yōu)化問(wèn)題定義增廣目標(biāo)函數(shù)，轉(zhuǎn)化2傳統(tǒng)方法的局限性經(jīng)典優(yōu)化算法是局部搜索算法。在其迭代過(guò)程中，不斷以當(dāng)前解鄰域下降方向上的解替換當(dāng)前解，即總是以鄰域的較好解更新當(dāng)前解。這是一種基于貪婪思想的做法，無(wú)疑會(huì)喪失全局優(yōu)化的能力，從而在搜索過(guò)程中不可避免地陷入局部最小。其迭代過(guò)程是從初始解開(kāi)始的確定性的過(guò)程，是一個(gè)確定性算法。不適用于組合優(yōu)化問(wèn)題涉及排序、分類、篩選等的一類問(wèn)題旅行商問(wèn)題（Travelingsalesmanproblem，TSP)加工調(diào)度問(wèn)題(Shedulingproblem,如Flow-shop,Job-Shop)0-1背包問(wèn)題(KnapsackProblem);裝箱問(wèn)題（Binpackingproblem)圖著色問(wèn)題（Graphcoloringproblem)聚類問(wèn)題（clusteringproblem)傳統(tǒng)方法的局限性經(jīng)典優(yōu)化算法是局部搜索算法。在其迭代過(guò)程中，3TSP:共去n個(gè)城市再回到原點(diǎn)，每個(gè)城市當(dāng)且僅當(dāng)去一次，求最短路徑。n!個(gè)排列。已知城市的位置圖。加工調(diào)度問(wèn)題：n個(gè)工件，m臺(tái)機(jī)器；每個(gè)工件在m臺(tái)機(jī)器加工的順序和操作時(shí)間已知，要求安排所有工件的加工次序，使某指標(biāo)最優(yōu)。0－1背包問(wèn)題：有n個(gè)物品（可能不同），1個(gè)背包；已知各物品的體積和價(jià)值；該背包如何盛放物品，可以使包中物品的價(jià)值最大。裝箱問(wèn)題：有已知數(shù)量的很多小物品，如何用最少的箱子數(shù)去裝入。圖著色問(wèn)題：對(duì)于n個(gè)頂點(diǎn)的無(wú)環(huán)圖，對(duì)每個(gè)頂點(diǎn)著色，要求相鄰的頂點(diǎn)著不同的顏色，怎樣著色使顏色種類最少。聚類問(wèn)題：M維空間上的n個(gè)模式聚成k類，使類內(nèi)距最小。劃分方式工程代表性TSP:共去n個(gè)城市再回到原點(diǎn)，每個(gè)城市當(dāng)且僅當(dāng)去一次，求4智能優(yōu)化方法模擬退火算法(SimulatedAnnealingAlgorithm)模擬進(jìn)化算法(Simulatedevolutionaryalgorithm)集群優(yōu)化方法（Swarmoptimization)蟻群優(yōu)化（AntColonyOptimization)粒子群優(yōu)化算法（ParticleSwarmOpt.)克隆選擇算法(ColonalSelectionAlgorithm,CSA)是隨機(jī)性的或貌似隨機(jī)性的搜索算法，可適用于多種問(wèn)題，魯棒性好。往往是一些物理或生物優(yōu)化過(guò)程的模擬算法，或混沌搜索算法。有些智能優(yōu)化算法，還能根據(jù)優(yōu)化過(guò)程的進(jìn)展情況，對(duì)算法自身的參數(shù)作出自適應(yīng)的調(diào)整，智能化程度更高。人工免疫系統(tǒng)(ArtificialImmuneSystem,AIS)BiologicalInspiredComputaitonBIC混沌搜索算法禁忌搜索(TabuSearch,或TabooSearch)智能優(yōu)化方法模擬退火算法(SimulatedAnneali5模擬退火算法(SimulatedAnnealing)1。隨機(jī)產(chǎn)生一個(gè)點(diǎn)，作為初始最優(yōu)點(diǎn)，計(jì)算函數(shù)值，T=T0;t=12。當(dāng)前最優(yōu)點(diǎn)處作一隨機(jī)擾動(dòng)，計(jì)算函數(shù)值增量⊿3。若⊿<0,則以概率1轉(zhuǎn)移（替換當(dāng)前點(diǎn)）；否則以概率p=exp(-⊿/T)轉(zhuǎn)移。4。若t小于終止步數(shù)，則t=t+1,T=T(t)（冷卻進(jìn)度表）,轉(zhuǎn)步驟25。輸出最優(yōu)點(diǎn)模擬退火算法以概率1收斂于目標(biāo)函數(shù)的全局最小點(diǎn)物理退火：包括加熱、保溫、冷卻三個(gè)子過(guò)程，旨在消除內(nèi)應(yīng)力,使固（晶）體的結(jié)構(gòu)狀態(tài)處于最低自由能狀態(tài)。Metropolis準(zhǔn)則（1953）

：某一溫度下，晶體接收一新的較低能量結(jié)構(gòu)狀態(tài)的概率為1，而接收一較高能量結(jié)構(gòu)狀態(tài)的概率為p=exp(-⊿/T)，⊿為函數(shù)增量；或者說(shuō)，某一溫度下變到能量較高狀態(tài)的概率總是低于變到較低能量狀態(tài)的概率，當(dāng)溫度較低時(shí)，變到能量較高狀態(tài)的概率會(huì)更小。因此，總的趨勢(shì)是，在保溫和冷卻過(guò)程中，晶體的結(jié)構(gòu)狀態(tài)朝著能量較低的方向變化；最后隨著冷卻過(guò)程的結(jié)束，晶體結(jié)構(gòu)狀態(tài)以概率1收斂于晶體的最低能量結(jié)構(gòu)。算法步驟：模擬退火算法(SimulatedAnnealing)1。隨61。在目標(biāo)函數(shù)的定義（基本）空間隨機(jī)給出一些點(diǎn)（或個(gè)體）作為初始的父代群體2。評(píng)價(jià)初始父代群體，若滿足要求則結(jié)束，否則繼續(xù)。3。通過(guò)對(duì)父代群體的交叉（crossover）、突變（mutation）、選擇(selection)等遺傳操作產(chǎn)生新一代群體4。評(píng)價(jià)新一代群體，若有滿足要求的優(yōu)化解或迭代次數(shù)足夠多則過(guò)程結(jié)束，否則將新一代群體置為父代群體又回到步驟三。

模擬進(jìn)化算法（SimulatedEA,EA)自然界中生物進(jìn)化是一個(gè)規(guī)律。如何進(jìn)化的？孟德?tīng)柕摹斑z傳變異”理論和達(dá)爾文的“自然選擇”學(xué)說(shuō)回答了這個(gè)問(wèn)題。模擬進(jìn)化算法就是一類模擬自然界生物進(jìn)化過(guò)程的優(yōu)化方法,具有并行、隨機(jī)、自適應(yīng)的特點(diǎn)。其中最有名進(jìn)化算法——遺傳算法(GA）由Holland于1975年提出。優(yōu)化步驟：1。在目標(biāo)函數(shù)的定義（基本）空間隨機(jī)給出一些點(diǎn)（或個(gè)體）作為7集群優(yōu)化方法（Swarmoptimization)蟻群優(yōu)化（AntColonyOptimization,ACO)螞蟻覓食過(guò)程蟻群覓食現(xiàn)象：蟻群從蟻巢出發(fā)四處覓食，假設(shè)兩只螞蟻找到食物后選擇不同路線返回蟻巢，其他螞蟻將更傾向于（更大概率地）選擇實(shí)際較短的路線前往食物，結(jié)果蟻群會(huì)找到一條最短的去食物的路徑。物理解釋：螞蟻在其經(jīng)過(guò)的路途上留下了一種信息素（pheromone）作為標(biāo)記，信息素濃度與路徑的質(zhì)量成正比，即越短濃度越大，越吸引后面螞蟻；另外，一條路線上走過(guò)的螞蟻越多，信息素濃度就越高，也越能吸引蟻群；最終，蟻群將找到距離食物最近的路線。ACO算法就是模擬蟻群覓食路徑優(yōu)化過(guò)程的算法。已被成功地用于解決旅行商問(wèn)題、圖著色問(wèn)題等大搜索空間的離散優(yōu)化問(wèn)題，特別是在電信路由選擇方面取得了很好的實(shí)際應(yīng)用效果。方法具有健壯性、靈活性、并行性等特點(diǎn)。集群優(yōu)化方法（Swarmoptimization)蟻群優(yōu)化8初始化：所有邊上的信息素量設(shè)為相同值τ0。多只人工蟻從頂點(diǎn)c1開(kāi)始隨機(jī)行走，選擇下一頂點(diǎn)的概率和連接兩頂點(diǎn)的邊上的信息素量成正比，行走一直繼續(xù)，直至構(gòu)造成功一個(gè)候選解，或沒(méi)有合法頂點(diǎn)可選擇。所有人工蟻完成行走后，計(jì)算候選解的適應(yīng)度值，并分兩步進(jìn)行信息素更新：①模擬信息素?fù)]發(fā)，按固定比例減少所有邊上的信息素量；②增加人工蟻經(jīng)過(guò)的邊上的信息素量，增加量與候選解的適應(yīng)度值成正比。若達(dá)到最大循環(huán)次數(shù)或取得滿意解則結(jié)束流程，否則轉(zhuǎn)<2>。ACO算法步驟如下：初始化：所有邊上的信息素量設(shè)為相同值τ0。ACO算法步驟9粒子群優(yōu)化算法（ParticleSwarmOpt.，PSO)鳥(niǎo)群覓食現(xiàn)象：鳥(niǎo)群在一片只有一塊食物的區(qū)域內(nèi)隨機(jī)覓食，所有的鳥(niǎo)都不知道食物的位置，它們能在不斷往復(fù)的搜索中發(fā)現(xiàn)食物，并得知與食物間的距離，然后跟隨目前離食物最近的鳥(niǎo)飛行過(guò)去。PSO算法正是從鳥(niǎo)群覓食的行為中得到啟示而產(chǎn)生的優(yōu)化算法。在PSO算法中，候選解稱為粒子，被看作是解空間中的一只“鳥(niǎo)”，編碼為粒子在D維解空間中所處的位置。粒子被賦以適應(yīng)度值和速度，通過(guò)在解空間中的移動(dòng)實(shí)現(xiàn)解的優(yōu)化，移動(dòng)前需要獲取兩個(gè)參數(shù)，一個(gè)是自身截至目前的最優(yōu)解pbest，另一個(gè)則是所有鄰近粒子當(dāng)前的最優(yōu)解nbest。根據(jù)對(duì)鄰近粒子定義的不同，PSO算法可分為全局模式PSO算法和局部模式PSO算法，前者將整個(gè)種群看作鄰近粒子，而后者粒子只將拓?fù)浠蚩臻g相鄰的粒子視作鄰近粒子。在獲取了兩個(gè)參數(shù)之后，更新粒子的速度和位置，實(shí)現(xiàn)移動(dòng)：其中，v=(v1,v2,…,vD)是粒子的速度，x=(x1,x2,…,xD)是粒子當(dāng)前的位置，rand是[0,1]之間的隨機(jī)數(shù)，c1、c2是學(xué)習(xí)因子，通常取c1=c2=2。

粒子群優(yōu)化算法（ParticleSwarmOpt.，P10初始化，在解空間隨機(jī)選取粒子組成群體；計(jì)算每個(gè)粒子的適應(yīng)度值，若優(yōu)于其pbest，則設(shè)當(dāng)前粒子取得的解為pbest；根據(jù)公式更新每個(gè)粒子的速度和位置；若達(dá)到最大循環(huán)次數(shù)或取得滿意解則結(jié)束流程，否則轉(zhuǎn)<2>。PSO算法的一般流程如下：PSO算法同GA類似，都是以隨機(jī)的初始種群開(kāi)始，以適應(yīng)度值評(píng)價(jià)個(gè)體，用隨機(jī)技術(shù)進(jìn)化種群并尋優(yōu)；但PSO算法并不使用交叉、變異等遺傳算子，粒子通過(guò)在解空間的移動(dòng)實(shí)現(xiàn)進(jìn)化。同GA比較，PSO算法的優(yōu)勢(shì)在于簡(jiǎn)單、容易實(shí)現(xiàn)、需調(diào)整的參數(shù)少，目前已廣泛應(yīng)用于函數(shù)優(yōu)化，神經(jīng)網(wǎng)絡(luò)訓(xùn)練，模糊系統(tǒng)控制等領(lǐng)域。初始化，在解空間隨機(jī)選取粒子組成群體；PSO算法的一般流程如11克隆選擇算法(ColonalSelectionAlgorithm,CSA)人工免疫系統(tǒng)(ArtificialImmuneSystem,AIS)克隆選擇學(xué)說(shuō)：當(dāng)機(jī)體受到外來(lái)抗原(antigen)刺激時(shí)，B淋巴細(xì)胞產(chǎn)生附著于細(xì)胞表面的抗體(antibody,亦稱受體）來(lái)作出免疫應(yīng)答，與抗原具有較高親合度（affinity）的抗體能夠識(shí)別抗原并與其結(jié)合，并分裂增殖、成長(zhǎng)為能夠產(chǎn)生更高親合度抗體的成熟細(xì)胞克隆，最后分化為漿細(xì)胞（plasmacell）和記憶細(xì)胞(memorycell)。漿細(xì)胞是一種不能分裂的細(xì)胞，是最活躍的抗體分泌者；而記憶細(xì)胞則具有較長(zhǎng)的壽命，在血液、淋巴和組織中擴(kuò)散，在下一次受到近似抗原刺激時(shí)迅速轉(zhuǎn)變?yōu)槟軌蚍置诟哂H合度抗體的漿細(xì)胞。在這一過(guò)程中，抗原被看作是細(xì)胞克隆的選擇因子，因此該理論被命名為克隆選擇學(xué)說(shuō)?？寺∵x擇算法(ColonalSelectionAlgor12克隆選擇的最初靈感來(lái)自于自然選擇理論，但它和達(dá)爾文進(jìn)化論之間的聯(lián)系并不僅限于此，它所具有的種群多樣性、遺傳變化和自然選擇三大特征都說(shuō)明，克隆選擇實(shí)質(zhì)上是一個(gè)“迷你的”進(jìn)化過(guò)程。首先，在免疫應(yīng)答中，不同的B細(xì)胞產(chǎn)生了大量特異性抗體，但只有極少數(shù)能夠成功地識(shí)別入侵抗原，并與抗原結(jié)合。絕大多數(shù)抗體的親合度都過(guò)低，無(wú)法被選中增殖，只能在免疫應(yīng)答過(guò)程中充當(dāng)被動(dòng)的背景式角色。這體現(xiàn)了克隆選擇中的抗體種群多樣性。其次，被選中的抗體除增殖外，還將經(jīng)歷親合度成熟化（affinitymaturation）過(guò)程，這既是提高抗體質(zhì)量的重要步驟，同時(shí)也是維持抗體種群多樣性的有效手段。這一過(guò)程通過(guò)超變異（hypermutation）和受體編輯（receptorediting）兩種類似于遺傳變化的機(jī)制實(shí)現(xiàn)：①超變異類似于小范圍變異，在負(fù)責(zé)抗體-抗原結(jié)合的基因上引入隨機(jī)變化，可能偶然地導(dǎo)致親合度的提高，這些改善抗體質(zhì)量的基因變化將被引入記憶細(xì)胞，這一機(jī)制和選擇一道提供了一個(gè)局部調(diào)優(yōu)的策略；②受體編輯類似于交叉重組，B細(xì)胞刪除自身的低親合度受體，并通過(guò)基因重組來(lái)發(fā)展出新受體，和遺傳學(xué)相比，免疫系統(tǒng)中的基因重組更加自由，核苷酸可以被隨機(jī)插入或刪除，這一機(jī)制在效果上更接近大范圍變異，提供了逃出局部最優(yōu)、找到全局最優(yōu)的可能性。最后，只有識(shí)別抗原并與其結(jié)合的抗體才能增殖和保存于記憶細(xì)胞中，低質(zhì)量抗體則被排除在進(jìn)一步的免疫應(yīng)答過(guò)程之外，這體現(xiàn)了克隆選擇的自然選擇特性。與進(jìn)化的關(guān)系克隆選擇的最初靈感來(lái)自于自然選擇理論，但它和達(dá)爾文進(jìn)化論之間134.對(duì)克隆種群中的所有個(gè)體施以超變異，產(chǎn)生成熟克隆種群C*，實(shí)現(xiàn)克隆種群的親合度成熟化；5.計(jì)算成熟克隆種群中各個(gè)體的親合度，選擇每組克隆中親合度最高的個(gè)體，共n個(gè)個(gè)體組成新的Ab{n}；6.隨機(jī)產(chǎn)生d個(gè)新的抗體，取代Ab中親合度最低的d個(gè)抗體，以模擬受體編輯機(jī)制。至此完成一個(gè)循環(huán)，若達(dá)到事先設(shè)定的終止條件（如達(dá)到最大代數(shù)、取到滿意解等）終止算法，否則轉(zhuǎn)<2>繼續(xù)。隨機(jī)產(chǎn)生規(guī)模為N的初始抗體種群Ab對(duì)于種群中的每個(gè)抗體Abi，計(jì)算其親合度，并選擇n個(gè)親合度最高的抗體組成Ab{n}為Ab{n}中的每個(gè)抗體產(chǎn)生與其親合度成比例的數(shù)目的克隆，組成克隆種群C克隆選擇算法步驟4.對(duì)克隆種群中的所有個(gè)體施以超變異，產(chǎn)生成熟克隆種群14禁忌搜索(TabuSearch,或TabooSearch，TS)禁忌搜索是鄰域搜索的一種擴(kuò)展，其最重要的思想是：標(biāo)記已搜索過(guò)的若干歷史最優(yōu)點(diǎn)，并在進(jìn)一步的迭代搜索中盡量避開(kāi)這些對(duì)象，即采用禁忌策略（但不是絕對(duì)禁止），從而保證對(duì)不同的有效搜索途徑的搜索。禁忌搜索涉及到鄰域(Neighborhood)，禁忌表(Tabulist)，禁忌長(zhǎng)度(Tabulength),候選解（Candidate），藐視準(zhǔn)則(Aspirationcriterion)等概念。通過(guò)禁忌表禁忌一些已經(jīng)歷的操作；并用藐視準(zhǔn)則來(lái)獎(jiǎng)勵(lì)一些優(yōu)良狀態(tài)。禁忌搜索(TabuSearch,或TabooSearc15禁忌搜索算法步驟：給出初始解x,令最優(yōu)解xg=x，令迭代步數(shù)i=0,禁忌表T={};從x的鄰域中選擇一定數(shù)量的解構(gòu)成候選解集合N(x);如果N(x)為非空集,從N(x)中找出最優(yōu)解x’；否則，轉(zhuǎn)到步驟2。如果x’不屬于T，或?qū)儆赥但滿足激活條件，則令x=x’；如果x’屬于T且x’不滿足激活條件，則令N(x)=N(x)-{x’},轉(zhuǎn)到步驟3。如果x的性能比xg的性能好，則xg=x;令T=TU{x}；如果禁忌表長(zhǎng)度等于規(guī)定長(zhǎng)度，則去掉最早進(jìn)入表中的解，即FIFO。如果滿足條件，則算法結(jié)束，xg為最終解；否則，令i=i+1,轉(zhuǎn)步驟2禁忌搜索算法步驟：給出初始解x,令最優(yōu)解xg=x，令迭代步16混沌搜索算法混沌搜索是一種確定性的搜索算法，但混沌具有遍歷性，能夠不重復(fù)地歷經(jīng)一定范圍內(nèi)的所有狀態(tài)，因此它可以作為搜索過(guò)程中避免局部最小的一種優(yōu)化機(jī)制。給出一個(gè)xn的初值，換算到定義區(qū)間，計(jì)算其函數(shù)f0，fmin=f0,i=1;迭代第i次產(chǎn)生xn+1，