第8章 智能優(yōu)化

第8章智能優(yōu)化1VisualFoxPro8.1模擬退火算法模擬退火算法概述8.2遺傳算法

遺傳算法概述遺傳算法關(guān)鍵參數(shù)8.3粒子群優(yōu)化算法粒子群算法的基本結(jié)構(gòu)

粒子群算法的關(guān)鍵參數(shù)8.4人工神經(jīng)網(wǎng)絡(luò)神經(jīng)網(wǎng)絡(luò)模型神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)規(guī)則

主要內(nèi)容2VisualFoxPro8.1.1物理退火過程和Metropolis準(zhǔn)則

通過對固體退火過程的研究可知，高溫狀態(tài)下的物質(zhì)降溫時其內(nèi)能隨之下降，如果降溫過程充分緩慢，則在降溫過程中物質(zhì)體系始終處于平衡狀態(tài)。從而降到某一低溫時其內(nèi)能可達(dá)最小，稱這種降溫為退火過程，模擬退火過程的尋優(yōu)方法稱為模擬退火（simulatedannealing,SA）算法。3VisualFoxPro8.1.2模擬退火算法概述

1.模擬退火的基本思想模擬退火算法可以分解為解空間、目標(biāo)函數(shù)和初始解三部分。4VisualFoxPro模擬退火算法簡單步驟描述如下：(1)初始化：初始溫度T(充分大)，初始解狀態(tài)S(是算法迭代的起點(diǎn))，每個T值的迭代次數(shù)L；(2)對k=1，……，L做第(3)至第6步；(3)產(chǎn)生新解S′；(4)計算增量Δt′=C(S′)-C(S)，其中C(S)為評價函數(shù)；(5)若Δt′<0則接受S′作為新的當(dāng)前解，否則以概率exp(-Δt′/T)接受S′作為新的當(dāng)前解。(6)如果滿足終止條件則輸出當(dāng)前解作為最優(yōu)解，結(jié)束程序。終止條件通常取為連續(xù)若干個新解都沒有被接受時終止算法。(7)T逐漸減少，且T->0，然后轉(zhuǎn)第2步。5VisualFoxPro應(yīng)用舉例

論貨郎擔(dān)問題(TravellingSalesmanProblem，簡記為TSP問題)：設(shè)有n個城市，用數(shù)碼1,…,n代表。城市i和城市j之間的距離為d(i，j)i,j=1,…,n．TSP問題是要找遍訪每個域市恰好一次的一條回路，且其路徑總長度為最短。求解TSP的模擬退火算法模型可描述如下：

6VisualFoxPro解空間解空間S是遍訪每個城市恰好一次的所有回路，是{1，……，n}的所有循環(huán)排列的集合，S中的成員記為(w1,w2,……，wn)，并記wn+1=w1。初始解可選為(1，……，n)；目標(biāo)函數(shù)此時的目標(biāo)函數(shù)即為訪問所有城市的路徑總長度或稱為代價函數(shù)：并要求此代價函數(shù)的最小值。7VisualFoxPro新解的產(chǎn)生隨機(jī)產(chǎn)生1和n之間的兩相異數(shù)k和m，若k<m，則將(w1,w2,…，wk,wk+1,…，wm,…，wn)變?yōu)椋?w1,w2,…，wm,wm-1,…，wk+1,wk,…，wn)如果是k>m，則將(w1,w2,…，wk,wk+1,…，wm,…，wn)變?yōu)椋?wm,wm-1,…，w1,wm+1,…，wk-1,wn,wn-1,…，wk)上述變換方法可簡單說成是“逆轉(zhuǎn)中間或者逆轉(zhuǎn)兩端”。也可以采用其他的變換方法，有些變換有獨(dú)特的優(yōu)越性，有時也將它們交替使用，得到一種更好方法。代價函數(shù)差設(shè)將(w1,w2,……，wn)變換為(u1,u2,……，un),則代價函數(shù)差為：8VisualFoxProProcedureTSPSA:begininit-of-T;{T為初始溫度}S={1，……，n};{S為初始值}termination=false;whiletermination=false

beginfori=1toLdobegingenerate(S′formS);{從當(dāng)前回路S產(chǎn)生新回路S′}Δt:=f(S′))-f(S);{f(S)為路徑總長}IF(Δt<0)OR(EXP(-Δt/T)>Random-of-[0,1])S=S′;IFthe-halt-condition-is-TRUETHENtermination=true;End;T_lower;End;End9VisualFoxPro8.2遺傳算法

遺傳算法是一類模擬生物進(jìn)化的智能優(yōu)化算法，它是由J.H.Holland于六十年代提出的。目前，遺傳算法已成為進(jìn)化計算研究的一個重要分支。與傳統(tǒng)優(yōu)化方法相比，遺傳算法的優(yōu)點(diǎn)是：群體搜索，不需要目標(biāo)函數(shù)的導(dǎo)數(shù)，概率轉(zhuǎn)移準(zhǔn)則。10VisualFoxPro8.2.1生物的進(jìn)化與遺傳

生物進(jìn)化的基本過程群體子群變異競爭婚配淘汰的群體種群11VisualFoxPro早在20世紀(jì)60年代初期就由美國大學(xué)的教授提出，并且在1975年教授發(fā)表了系統(tǒng)論述遺傳算法的專著自然與人工系統(tǒng)中的自適應(yīng)，其主要特點(diǎn)是群體搜索策略和群體中個體之間的信息交換，搜索不依賴于梯度信息。所以它的應(yīng)用范圍非常廣泛，尤其適合于處理傳統(tǒng)搜索方法難于解決的復(fù)雜和非線性問題，可廣泛用于組合優(yōu)化，機(jī)器學(xué)習(xí)，自適應(yīng)控制，規(guī)劃設(shè)計和人工生命等領(lǐng)域，從而確立了它在21世紀(jì)的智能計算技術(shù)中的關(guān)鍵地位。12VisualFoxPro8.2.2遺傳算法概述

遺傳算法已有了許多發(fā)展，但一般來說，其基本過程是：首先采用某種編碼方式將解空間映射到編碼空間（可以是位串、實(shí)數(shù)、有序串、樹或圖，Holland最初的遺傳算法是基于二進(jìn)制串的，類似于生物染色體結(jié)構(gòu)，易于用生物遺傳理論解釋，各種遺傳操作也易于實(shí)現(xiàn)。

13VisualFoxPro遺傳算法具有許多獨(dú)特的優(yōu)點(diǎn)：不必非常明確描述問題的全部特征，通用性和魯棒性強(qiáng)，能很快適應(yīng)問題和環(huán)境的變化；對領(lǐng)域知識依賴程度低，不受搜索空間限制性假設(shè)的約束，不必要求連續(xù)性、可導(dǎo)或單峰等。從多點(diǎn)進(jìn)行搜索，如同在搜索空間上覆蓋的一張網(wǎng)，搜索的全局性強(qiáng)，不易陷入局部最優(yōu)；具有隱并行性，非常適合于并行計算。在遺傳算法的研究中，可以看到主要有三類研究方向：(1)研究遺傳算法本身的理論基礎(chǔ)。(2)用遺傳算法作為工具解決工程問題，主要是進(jìn)行優(yōu)化，關(guān)心的是是否能在傳統(tǒng)方法上有所提高。(3)用遺傳算法研究演化現(xiàn)象，一般涉及到人工生命和復(fù)雜性科學(xué)領(lǐng)域。14VisualFoxPro遺傳算法包括以下的主要處理步驟：(1)對優(yōu)化問題的解進(jìn)行編碼，稱一個解的編碼為一個染色體，組成編碼的元素稱為基因。編碼的目的主要是用于優(yōu)化問題解的表現(xiàn)形式和利于之后遺傳算法中的計算。(2)適應(yīng)函數(shù)的構(gòu)造和應(yīng)用。適應(yīng)函數(shù)基本上依據(jù)優(yōu)化問題的目標(biāo)函數(shù)而定。當(dāng)函數(shù)確定之后，自然選擇規(guī)律是以適應(yīng)函數(shù)值的大小決定的概率分布來確定哪些染色體適應(yīng)生存，哪些被淘汰。生存下來的染色體組成種群，形成一個可以繁衍下一代的群體。染色體的結(jié)合。雙親的遺傳基因結(jié)合是通過編碼之間的交配（crossover）達(dá)到下一代的產(chǎn)生。新一代的產(chǎn)生是一個生殖過程，它產(chǎn)生了一個新解。(3)變異。新解產(chǎn)生過程中是可能發(fā)生基因變異，變異使某些解的編碼發(fā)生變化，使解有更大的遍歷性。15VisualFoxPro

以貨郎擔(dān)問題(TravellingSalesmanProblem，簡記為TSP)問題為例：設(shè)有n個城市，城市i和城市j之間的距離為d(i，j)i,j=1,...,n．TSP問題是要找遍訪每個域市恰好一次的一條回路，且其路徑總長度為最短。

許多應(yīng)用問題結(jié)構(gòu)很復(fù)雜，但可以化為簡單的位串形式編碼表示，我們將問題結(jié)構(gòu)變換為位串形式編碼表示的過程叫編碼；而相反將位串形式編碼表示變換為原問題結(jié)構(gòu)的過程叫譯碼。我們把位串形式編碼表示叫染色體，有時也叫個體。對TSP可以按一條回路城市的次序進(jìn)行編碼，比如碼串134567829表示從城市1開始，依次是城市3,4,5,6,7,8,2,9，最后回到城市1。一般情況是從城市w1開始，依次經(jīng)過城市w2,……，wn，最后回到城市w1，我們就有如下編碼表示：w1w2……wn16VisualFoxPro(2)適應(yīng)度函數(shù)為了體現(xiàn)染色體的適應(yīng)能力，引入了對問題中的每一個染色體都能進(jìn)行度量的函數(shù)，叫適應(yīng)度函數(shù)。通過適應(yīng)度函數(shù)來決定染色體的優(yōu)、劣程度，它體現(xiàn)了自然進(jìn)化中的優(yōu)利劣汰原則。對優(yōu)化問題，適應(yīng)度函數(shù)就是目標(biāo)函數(shù)。TSP的目標(biāo)是路徑總長度為最短，路徑總長度的倒數(shù)就可以為TSP的適應(yīng)度函數(shù)：

17VisualFoxPro

請注意其中wn+1=w1。適應(yīng)度函數(shù)要有效反映每一個染色體與問題的最優(yōu)解染色體之間的差距，一個染色體與問題的最優(yōu)解染色體之間的差距小，則對應(yīng)的適應(yīng)度函數(shù)值之差就小，否則就大。適應(yīng)度函數(shù)的取值大小與求解問題對象的意義有很大的關(guān)系。18VisualFoxPro(3)遺傳算法基本步驟下面是遺傳算法基本步驟的簡單描述：初始化群體；計算群體上每個個體的適應(yīng)度值；按由個體適應(yīng)度值所決定的某個規(guī)則選擇將進(jìn)入下一代的個體；按概率Pc進(jìn)行交叉操作；按概率Pc進(jìn)行突變操作；沒有滿足某種停止條件，則轉(zhuǎn)第(2)步，否則進(jìn)入(7)。輸出種群中適應(yīng)度值最優(yōu)的染色體作為問題的滿意解或最優(yōu)解。程序的停止條件最簡單的有如下二種：完成了預(yù)先給定的進(jìn)化代數(shù)則停止；種群中的最優(yōu)個體在連續(xù)若干代沒有改進(jìn)或平均適應(yīng)度在連續(xù)若干代基本沒有改進(jìn)時停止。19VisualFoxPro8.2.3遺傳算法關(guān)鍵參數(shù)

遺傳算法中需要選擇的運(yùn)行參數(shù)主要有個體編碼串長度l、群體大小M，交叉概率pc、變異概率pm、終止代數(shù)T等。這些參數(shù)對遺傳算法的運(yùn)行性能影響較大，需要認(rèn)真選取。20VisualFoxPro8.3粒子群優(yōu)化算法