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

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

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

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

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