1、工程優化幾種常用的算法 1. 神經網絡神經網絡 1. 神經網絡的簡單原理神經網絡的簡單原理人工神經網絡（ Artificial Neural Networks， 簡寫為ANNs）也簡稱為神經網絡（NNs）或 稱作連接模型（Connectionist Model） ，是對人腦或自 然神經網絡（Natural Neural Network）若干基本特性的 抽象和模擬。是由人工建立的以有向圖為拓撲結構的動態 系統，它通過對連續或斷續的輸入作出狀態相應而進行信 息處理。它是根據人的認識過程而開發出的一種算法。 2. 神經元和神經網絡的結構神經元和神經網絡的結構 如上所述，神經網絡的基本結構如圖5.35

2、所示： 神經網絡一般分為輸入層，輸出層和隱含層，層數越多，計 算結果越精確，但所需的時間也就越長，所以實際應用中要 根據要求設計網絡層數。 神經網絡中每一個節點叫做一個人 工神經元，他對應于人腦中的神經元。 由人腦神經元的工作機理，人們構造了人工神經元的數學模 型，如圖5.36所示。 圖5.36 McCulloch-Pitts網絡 在圖中， 是表示神經元對信息 的感知能力， 稱為關聯權，稱為輸出函數或激活函數，采用激活函數的神經 網絡也稱閾網絡。McCulloch-Pitts輸出函數定義為 其中， 為符號函數， 稱為閾值。 1 sgn(), n ii i yfzw x sgn() i w i

3、x f z sgn() 一般來說，一個人工神經元有多個輸入和一個輸出，另外 有一個激活函數，不同的激發函數對應了不同的網絡，也 決定了網絡的用途。從方程可以看出，當 確定時，任給 一組輸入 ，也就很容易得到輸出。而現 在我們的想法是：對給定的輸入，確定權數，使得通過方 程計算出來的輸出盡可能與實際值吻合，這即是學習的過 程。人工神經網絡的主要工作就是通過學習，建立模型和 確定的值。 i w 1, i xin ， 神經網絡按照網絡結構和激發函數的不同可分為許多種，感 知機、BP網絡及Hopfield神經網絡。 首先介紹單層前向神經網絡。單層前向神經網絡的模型結 構如圖5.37所示。 或用矩陣表示

4、為 其中， 為權系數矩陣， 分別為輸入 向量、輸出向量及閾值向量。感知機學習規則算法步驟為： 用t表示學習步驟的序號，t=0表示學習前的神經網絡的初 始狀態。 第1步：賦初值。給網絡上權數和閾值賦初值，如； 第2步：計算樣本實際輸出。 選擇一個樣本作為網絡輸入，計算樣本在目前神經網絡中 的實際輸出。如，對于第個樣本，感知機輸出為： () T Yf W X () ijm n Ww XY， ， 00 iji w， 其中， 第3步：計算誤差。 計算感知機輸出的實際結果與期望輸出之差： 第4步：權數修正。 如果 ，則轉第2步，否則調整權值： 第5步：若訓練樣本已完全輸入或輸出誤差小于預設值，則 學習結

5、束；否則，轉第2步繼續學習。 1 ( )( ( )( ) n Y pY pYp ， ， ( )()1, iijji Y pfw xin ， t D pY p 0 t (1)( )( ),( ) iiiiti W pW pW pW px 5.4.2 遺傳算法遺傳算法 遺傳算法(Genetic Algorithm，GA)是一種基于自然群體遺 傳演化機制的高度并行、隨機、自適應高效探索算法。它 根據預定的目標適應度函數對每個個體進行評價，依據適 者生存，優勝劣汰的進化規則，不斷得到更優的群體，同 時以全局并行搜索方式來搜索優化群體中的最優個體，求 得滿足要求的最優解。 2. 基本遺傳算法的步驟基本遺

6、傳算法的步驟 從上面的例子中，我們便能得到遺傳算法的一般步驟， 第1步： 編碼。選擇問題的一個編碼，給出一個有N個染 色體的初始群體 ，t=1； 第2步： 對群體 中的每個染色體 ，計算它的適應 函數 ; (1)pop ( )pop t ( ) i pop t ( )( ) i f ifitness pop t 第3步：若停止規則滿足，則算法停止；否則，計算概率 （5-143） 并以概率(5-143)從 中隨機選一些染色體構成一個 種群 第4步：通過交叉，交叉概率為 ，得到有N個染色體 的 ； 第5步：以一個較小的概率 ，使得一個染色體的基因發 生變異，形成一個新的群體 返回第2步。 一般流程

7、如圖圖5.40所示 1 ( ) ,1, ( ) iN i f i piN f i ( )pop t (1)( )|1, j newpop tpop tjN c P (1)crosspop t m p ( )( );pop tmutpop t 圖5.40 基本遺傳算法的步驟 與傳統的搜索方法相比，遺傳算法是采用概率的變遷規則來指導搜索方 向，對搜索空間沒有任何特殊要求只利用適應性信息，不需要導數等其 它輔助信息。搜索過程是從一組解迭代到另一組解，采用同時處理群體中 多個個體的方法，降低了陷入局部最優解的可能性，易于并行化。 4. 遺傳算法的應用遺傳算法的應用 最短路徑問題可以用圖論描述，現求解如

8、圖最短路徑問題可以用圖論描述，現求解如圖5.41所示的圖所示的圖15 點加權有向圖從頂點點加權有向圖從頂點1到頂點到頂點15的最短路徑。的最短路徑。 圖圖5.41 15點加權有向圖點加權有向圖 第第1步：染色體編碼。對于給定的圖，將圖中各頂點按頂點步：染色體編碼。對于給定的圖，將圖中各頂點按頂點 號自然排序，然后按此順序將每個待選頂點作為染色體的一號自然排序，然后按此順序將每個待選頂點作為染色體的一 個基因，當基因值為個基因，當基因值為1時，表示相應的頂點被選入該條路徑時，表示相應的頂點被選入該條路徑 中，否則反之。此染色體中的基因排列順序即為各頂點在此中，否則反之。此染色體中的基因排列順序即

9、為各頂點在此 通路中出現的先后順序，染色體的長度應等于該圖中頂點的通路中出現的先后順序，染色體的長度應等于該圖中頂點的 個數。個數。 ( ,) ij v v ( ,) ij d v v 1 1 1 ( )(,) n iin r f id vv m x () m f x 第2步：計算每個個體適應度。 對具有個n頂點的圖，已知各頂點 的邊長度 ，把 到 間一條通路長 度定義為適應函數 ，求該優化問題就是要尋找 解 ，使 最小。 第3步：選擇操作。 選擇作為交叉的雙親，是根據前代染色體的適應函數所確定 的，質量好的個體，即從起點到終點路徑長度最短的個體被 選中的概率最大。 第4步：交叉與變異操作。

10、將被選中的兩個染色體進行交叉操作的過程是先產生一個隨 機數，確定交叉點位于染色體的第幾位基因上，然后在此位 置進行部分基因互換。變異操作是將染色體中某位基因逆換， 即由1變為0，或反之。變異的意義為在某條路徑上去掉或增 加某頂點，但這樣做的結果不一定能使路徑長度減少，也就 是說有可能使各代中產生的比較好的方案在遺傳過程中丟失， 遲緩了獲得最優解的速度。 經使用遺傳算法，本例的最短路徑解集為： 最短路徑等于14。 ( ,) ij v v ( ,) ij d v v 1 i v in v 1 1 1 ( )(,) n iin r f id vv m x() m f x 變異的意義為在某條路徑上去掉

11、或增加某頂點，但這樣做的 結果不一定能使路徑長度減少，也就是說有可能使各代中產 生的比較好的方案在遺傳過程中丟失，遲緩了獲得最優解的 速度。 經使用遺傳算法，本例的最短路徑解集為： 最短路徑等于14。 13461215 12111315 1211131415 1341315 134131415 5.4.3 模擬退火算法模擬退火算法 1. 模擬退火算法原理模擬退火算法原理 模擬退火算法主要用于解決組合優化問題，它是模擬物理中 金屬物質的退火過程而開發的一種優化算法 金屬物體在加熱到一定的溫度后，它的所有的分子在狀態空 間中自由運動，在溫度，分子停留在狀態滿足波茲曼 （Boltzmann）概率分布： 表5.6 組合優化問題與金屬物體退火類比 組合優化問題 金屬物體 解空間 狀態空間 最優解 能量最低的狀態 目標函數 能量函數 ( )( ) ( )exp()exp() s V BB E rE s P EE r k Tk T 2. 簡單模擬退火算法的步驟簡單模擬退火算法的步驟 第1步：任選一個初始解 ； ； ；設定初始溫度 ， 終止溫度 ，概率閾值 。 第2步：若在該溫度達到內循環停止條件（是否符合收斂條件），則 到第3步；否則，從鄰域 中隨機選一 ，計算 ； 若 ，則 ，否則計算 ，