機(jī)械故障診斷學(xué) 鐘秉林 第8章模擬退火與演化算法的原理及應(yīng)用

第8章模擬退火與演化算法的原理及應(yīng)用

模擬退火算法原理

演化算法原理

模擬退火和演化算法在知識(shí)獲取中的應(yīng)用機(jī)械故障診斷理論與方法第2篇基于人工智能的故障診斷技術(shù)2023/11/191內(nèi)容安排一、概述

故障的分類(lèi)和診斷本質(zhì)上可以理解為一種優(yōu)化過(guò)程，即在所有可能的分類(lèi)或診斷結(jié)論中尋找一個(gè)最佳的結(jié)果來(lái)解釋所獲得的故障樣本。因此，分類(lèi)和診斷問(wèn)題可以通過(guò)選擇合適的目標(biāo)函數(shù)轉(zhuǎn)換為函數(shù)優(yōu)化或組合優(yōu)化問(wèn)題。2023/11/192

模擬退火算法和演化算法是兩種具有全局最優(yōu)性能優(yōu)化方法，前者模擬物理學(xué)中固體物質(zhì)的高溫退火過(guò)程，后者則借鑒生物界自然選擇和進(jìn)化機(jī)制以獲取函數(shù)的最優(yōu)解。本章主要介紹著兩種算法的基本原理及其應(yīng)用。

定義：組合優(yōu)化問(wèn)題π是一個(gè)最小化問(wèn)題，或是一個(gè)最大化問(wèn)題，它由下面三部分組成：(1)

實(shí)例集合；(2)

對(duì)每一個(gè)實(shí)例I，有一個(gè)有窮的可行解集合S(I)；(3)目標(biāo)函數(shù)f，它對(duì)每一個(gè)實(shí)例I和每一個(gè)可行解，賦以一個(gè)有理數(shù)。一、概述1.組合優(yōu)化問(wèn)題2023/11/193一個(gè)通俗的定義：所謂組合優(yōu)化，是指在離散的、有限的數(shù)學(xué)結(jié)構(gòu)上，尋找一個(gè)（或一組）滿(mǎn)足給定約束條件并使其目標(biāo)函數(shù)值達(dá)到最大或最小的解。一般來(lái)說(shuō)，組合優(yōu)化問(wèn)題通常帶有大量的局部極值點(diǎn)，往往是不可微的、不連續(xù)的、多維的、有約束條件的、高度非線(xiàn)性的NP完全（難）問(wèn)題，因此，精確地求解組合優(yōu)化問(wèn)題的全局最優(yōu)解的“有效”算法一般是不存在的。一、概述2023/11/194典型的組合優(yōu)化問(wèn)題主要有如下幾種：集覆蓋問(wèn)題（set-coveringproblem）裝箱問(wèn)題（bin-packingproblem）0-1背包問(wèn)題（knapsackproblem）指派問(wèn)題（assignmentproblem）旅行商問(wèn)題（travelingsalesmanproblem）[TSP、貨郎擔(dān)問(wèn)題]影片遞送問(wèn)題（filmdeliveryproblem）圖劃分問(wèn)題（graphpartitioningproblem）作業(yè)調(diào)度問(wèn)題（job-shopschedulingproblem）一、概述2023/11/195集覆蓋問(wèn)題（set-coveringproblem）對(duì)于一個(gè)m行n列的0－1矩陣A，每行代表一種任務(wù)，每列代表一個(gè)人，aij=1表示第j個(gè)人能完成第i個(gè)任務(wù)。每個(gè)人都有一個(gè)雇傭代價(jià)。問(wèn)題的目標(biāo)是：用最小的代價(jià)選擇一些人（矩陣的列），使得每一個(gè)任務(wù)都至少有一個(gè)人能完成。設(shè)向量x的元素xj=1表示列j被選中（費(fèi)用是cj>0），xj=0則表示其未被選中（j=1,2,…,n）。已經(jīng)證明集覆蓋問(wèn)題是NP完全問(wèn)題。一、概述2023/11/196如果所有費(fèi)用cj都相同，則問(wèn)題稱(chēng)為單一費(fèi)用問(wèn)題（unicostset-coveringproblem）。如果為等式約束，則稱(chēng)為集劃分問(wèn)題（setpartitioningproblem）一、概述2023/11/197Cost=29101010一、概述2023/11/1982023/11/199裝箱問(wèn)題（binpackingproblem）所裝物品不得超過(guò)箱子的容積一個(gè)物品只能放入一個(gè)箱子用最少的箱子將所有物品都裝下一、概述2023/11/1910貨運(yùn)裝箱問(wèn)題截銅棒問(wèn)題布匹套裁問(wèn)題。。。裝箱問(wèn)題屬于NP－難問(wèn)題一、概述2023/11/19110/1背包問(wèn)題：給出幾個(gè)體積為S1，S2，…，Sn的物體和容量為C的背包；要求找出n個(gè)物件的一個(gè)子集使其盡可能多地填滿(mǎn)容量為C的背包。 數(shù)學(xué)形式：

最大化 滿(mǎn)足一、概述2023/11/1912廣義背包問(wèn)題：輸入由背包容積C和兩個(gè)向量：物品體積S＝(S1，S2，…，Sn)和物品價(jià)值P＝(P1，P2，…，Pn)組成。設(shè)X為一整數(shù)集合（物品的標(biāo)識(shí)），X＝1，2，3，…，n，T為X的子集，則問(wèn)題就是找出滿(mǎn)足約束條件，并使總價(jià)值最大的子集T。 數(shù)學(xué)形式：

最大化 滿(mǎn)足一、概述2023/11/1913在應(yīng)用問(wèn)題中，設(shè)S的元素是n項(xiàng)經(jīng)營(yíng)活動(dòng)各自所需的資源消耗，C是所能提供的資源總量，P的元素是人們從每項(xiàng)經(jīng)營(yíng)活動(dòng)中得到的利潤(rùn)或收益，則背包問(wèn)題就是在資源有限的條件下，追求總的最大收益的資源有效分配問(wèn)題。背包問(wèn)題屬于NP-難問(wèn)題一、概述2023/11/1914多選擇背包問(wèn)題：有一個(gè)容積有限的背包。要放入背包的物品被分為不重疊的若干類(lèi)，每類(lèi)中有若干不同的物品，從每類(lèi)中選擇一個(gè)物品，使得物品總體積在滿(mǎn)足背包容積約束的前提下最大化收益。屬于NP－難問(wèn)題一、概述2023/11/1915i為類(lèi)下標(biāo)；j為類(lèi)中物品的下標(biāo)；ni是第i類(lèi)中物品的數(shù)量；cij是第i類(lèi)中第j個(gè)物品的收益；m是類(lèi)的數(shù)量；wij為第i類(lèi)中第j個(gè)項(xiàng)目的體積，W是背包的容積。最大化所選物品的總價(jià)值所選物品的總體積不得超過(guò)背包容積每一類(lèi)中只能選一個(gè)物品一、概述2023/11/1916旅行商問(wèn)題（TravelingSalesmanProblem）尋找一條最短的遍歷n個(gè)城市的路徑，或者說(shuō)搜索整數(shù)子集X＝{1，2，…，n}（X的元素表示對(duì)n個(gè)城市的編號(hào)）的一個(gè)排列π(X)={v1，v2，…，vn}，使下式取最小值。式中的d(vi,vi+1)表示城市vi到城市vi+1的距離。對(duì)稱(chēng)旅行商問(wèn)題是NP－難問(wèn)題一、概述2023/11/1917影片遞送問(wèn)題（FilmDeliveryProblem）一盤(pán)影片拷貝要在n個(gè)電影院放映。每個(gè)電影院放映的次數(shù)已定，記為一個(gè)非負(fù)的整數(shù)di(i＝1，2，…，n)。兩個(gè)影院間的距離記為wij，若影院i和j不能直接相連，則令wij＝+

。問(wèn)題是要為影片遞送員找一個(gè)巡回，從主影院1開(kāi)始，將影片拷貝送到第i家影院di(i＝1，2，…，n)次，最后回到主影院1，并極小化總的路線(xiàn)長(zhǎng)度。當(dāng)所有的di(i＝l，2，…，n)為1時(shí)，F(xiàn)DP變?yōu)榻?jīng)典的TSP。FDP是TSP的新擴(kuò)展，它可以推廣到一大類(lèi)路徑與排序問(wèn)題中。一、概述2023/11/1918圖的二劃分問(wèn)題：對(duì)于一無(wú)向圖G，設(shè)其頂點(diǎn)集合為V，將頂點(diǎn)集合V劃分為兩個(gè)子集V1和V2，Vl

V2＝

，求使V1和V2兩頂點(diǎn)子集之間聯(lián)結(jié)最少的一種劃分。圖的劃分問(wèn)題在電子線(xiàn)路設(shè)計(jì)中非常重要。例如，在多層印刷電路板的布局設(shè)計(jì)中，使層間聯(lián)線(xiàn)數(shù)目最少的器件布局等。由于圖的劃分問(wèn)題的計(jì)算復(fù)雜度極高(3000個(gè)節(jié)點(diǎn)的二劃分問(wèn)題的搜索空間可達(dá)10900)，因此，在實(shí)用規(guī)模上精確求出最優(yōu)解是不可能的。一、概述2023/11/1919廣義地講，調(diào)度問(wèn)題考慮的是隨著時(shí)間的變化，如何調(diào)度有限的資源在執(zhí)行任務(wù)的同時(shí)滿(mǎn)足特定約束。資源：人力、金錢(qián)、機(jī)器、工具、材料、能源、等等。任務(wù)：制造系統(tǒng)的加工工序；計(jì)算機(jī)系統(tǒng)的信息處理。任務(wù)的表征：完成時(shí)間、預(yù)期時(shí)間、相對(duì)緊急權(quán)重、處理時(shí)間和資源消耗。一、概述2023/11/1920經(jīng)典作業(yè)車(chē)間調(diào)度問(wèn)題（Job-shopScheduling）：有m臺(tái)不同的機(jī)器和n個(gè)不同的工件，每個(gè)工件包含一個(gè)由多道工序組成的工序集合，工件的工序順序是預(yù)先給定的。每道工序用它所要求的機(jī)器和固定的加工時(shí)間來(lái)表示。此外對(duì)工件和機(jī)器有一些約束，例如： (1)一個(gè)工件不能兩次訪(fǎng)問(wèn)同一機(jī)器； (2)不同工件的工序之間沒(méi)有先后約束； (3)工序一旦進(jìn)行不能中斷；· (4)每臺(tái)機(jī)器一次只能加工一個(gè)工件； (5)下達(dá)時(shí)間和交貨期都不是給定的。 問(wèn)題：確定機(jī)器上工序的順序，以最小化完成所有工件所需的最小加工持續(xù)時(shí)間。一、概述2023/11/1921局部搜索算法是基于貪婪思想利用鄰域函數(shù)進(jìn)行搜索的，容易實(shí)現(xiàn)，但其搜索性能完全依賴(lài)于鄰域函數(shù)和初始解的選取，領(lǐng)域函數(shù)設(shè)計(jì)不當(dāng)或初始解選擇不合適，算法的最終性能將會(huì)很差；同時(shí)貪婪思想也導(dǎo)致其最終解只具有局部最優(yōu)性；此外，局部搜索算法的時(shí)間復(fù)雜性取決于問(wèn)題的性質(zhì)與鄰域結(jié)構(gòu)的復(fù)雜程度。鑒于局部搜索算法的上述缺點(diǎn)，許多學(xué)者提出了各種各樣的方法來(lái)改善算法的性能。模擬退火算法和演化算法從不同的角度，利用不同的搜索機(jī)制和實(shí)現(xiàn)策略實(shí)現(xiàn)了對(duì)局部搜索算法的改進(jìn)，具有了全局最優(yōu)的性能，成為兩種較為成功的全局優(yōu)化算法。一、概述2.組合優(yōu)化問(wèn)題的局部搜索算法2023/11/1922算法的提出

模擬退火算法(SimulatedAnnealing,簡(jiǎn)稱(chēng)SA)的思想最早是由Metropolis等(1953)提出的，1983年Kirkpatrick等將其用于組合優(yōu)化。SA算法是基于MonteCarlo迭代求解策略的一種隨機(jī)尋優(yōu)算法，其出發(fā)點(diǎn)是基于物理中固體物質(zhì)的退火過(guò)程與一般組合優(yōu)化問(wèn)題之間的相似性。算法的目的解決NP復(fù)雜性問(wèn)題；克服優(yōu)化過(guò)程陷入局部極?。豢朔踔狄蕾?lài)性。二、模擬退火算法2023/11/1923

模擬退火算法在某一初溫下，伴隨溫度參數(shù)的不斷下降，結(jié)合概率突跳特性在解空間中隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解，即在局部?jī)?yōu)解能概率性地跳出并最終趨于全局最優(yōu)解。模擬退火算法是一種通用的優(yōu)化算法，目前已在工程中得到了廣泛應(yīng)用。二、模擬退火算法2023/11/1924局部?jī)?yōu)解全局最優(yōu)解概率突跳特性什么是退火：退火是指將固體加熱到足夠高的溫度（不能加熱到熔解溫度，得保持形狀和尺寸），使分子呈隨機(jī)排列狀態(tài)，然后逐步降溫使之冷卻，最后分子以低能狀態(tài)排列，固體達(dá)到某種穩(wěn)定狀態(tài)。退火目的：使金屬的顯微結(jié)構(gòu)更加規(guī)則化，并消除前道工序所產(chǎn)生的內(nèi)應(yīng)力。簡(jiǎn)單而言，物理退火過(guò)程由以下三部分組成：1.物理退火過(guò)程和Metropolis準(zhǔn)則二、模擬退火算法2023/11/1925

退火過(guò)程⑴加溫過(guò)程：其目的是增強(qiáng)粒子的熱運(yùn)動(dòng)，使其偏離平衡位置。當(dāng)溫度足夠高時(shí)，固體將熔解為液體，從而消除系統(tǒng)原先可能存在的非均勻態(tài)，使隨后進(jìn)行的冷卻過(guò)程以某一平衡態(tài)為起點(diǎn)。熔解過(guò)程與系統(tǒng)的熵增過(guò)程聯(lián)系，系統(tǒng)能量也隨溫度的升高而增大。⑵等溫過(guò)程：物理學(xué)的知識(shí)告訴我們，對(duì)于與周?chē)h(huán)境交換熱量而溫度不變的封閉系統(tǒng)，系統(tǒng)狀態(tài)的自發(fā)變化總是朝自由能減少的方向進(jìn)行，當(dāng)自由能達(dá)到最小時(shí)，系統(tǒng)達(dá)到平衡態(tài)。⑶冷卻過(guò)程：目的是使粒子的熱運(yùn)動(dòng)減弱并漸趨有序，系統(tǒng)能量逐漸下降，從而得到低能的晶體結(jié)構(gòu)。二、模擬退火算法2023/11/1926Metropolis等在1953年提出了重要性采樣法，即以概率接受新?tīng)顟B(tài)。具體而言：首先，在溫度T，給定固體初始狀態(tài)i

作為當(dāng)前狀態(tài)，由當(dāng)前狀態(tài)i隨機(jī)產(chǎn)生新?tīng)顟B(tài)j，兩者的能量分別為Ei和Ej。然后判斷：若Ej＜Ei，則接受新?tīng)顟B(tài)j為當(dāng)前“重要”狀態(tài)，否則，若Ej＞Ei，則該狀態(tài)是否“重要”要依據(jù)固體處于該狀態(tài)的概率進(jìn)行判斷，其方法如下：

二、模擬退火算法2023/11/1927Metropolis準(zhǔn)則①計(jì)算r=P(Ej)/P(Ei)=exp[(Ei-Ej)/kT]，顯然r＜1，其中P(E)為系統(tǒng)處于能量E的概率、T為系統(tǒng)絕對(duì)溫度、k為Boltzmann常數(shù)。②產(chǎn)生一個(gè)[0,1]區(qū)間的隨機(jī)數(shù)ζ，若r＞ζ

，則新?tīng)顟B(tài)作為重要狀態(tài)，否則舍去。若新?tīng)顟B(tài)為重要狀態(tài)，則以新?tīng)顟B(tài)為當(dāng)前狀態(tài)（否則仍以原狀態(tài)i為當(dāng)前狀態(tài)）。重復(fù)以上新?tīng)顟B(tài)產(chǎn)生過(guò)程。二、模擬退火算法2023/11/1928

在大量固體狀態(tài)的變換（也稱(chēng)遷移）后，固體趨于能量較低的平衡狀態(tài)，固體狀態(tài)的概率分布趨于Gibbs正則分布：

P(E)

∝exp(-E/kT)

上述以一定的概率接受新?tīng)顟B(tài)的準(zhǔn)則稱(chēng)為Metropolis準(zhǔn)則，相應(yīng)算法稱(chēng)為Metropolis算法。由r=exp[(Ei-Ej)/kT]可知，高溫下可接受與當(dāng)前狀態(tài)能差較大的新?tīng)顟B(tài)為重要狀態(tài)，而在低溫下只能接受與當(dāng)前狀態(tài)能差較小的新?tīng)顟B(tài)為重要狀態(tài)，這與不同溫度下熱運(yùn)動(dòng)的影響完全一致。在溫度趨于0時(shí)，不能接受任一Ej＞Ei的新?tīng)顟B(tài)。二、模擬退火算法2023/11/1929Metropolis準(zhǔn)則：利用重要性采樣過(guò)程，在高溫下可接受與當(dāng)前狀態(tài)能量差較大的新?tīng)顟B(tài)；在低溫下基本只接受與當(dāng)前狀態(tài)能量差較小的新?tīng)顟B(tài)；當(dāng)溫度趨于零時(shí)，就不能接受比當(dāng)前狀態(tài)能量高的新?tīng)顟B(tài)。二、模擬退火算法2023/11/19301983年Kirkpatrick等意識(shí)到組合優(yōu)化與物理退火的相似性，并受到Metropolis準(zhǔn)則的啟迪，提出了模擬退火算法。模擬退火算法是基于MonteCarlo

迭代求解策略的一種隨機(jī)尋優(yōu)算法。其出發(fā)點(diǎn)是基于物理退火過(guò)程與組合優(yōu)化之間的相似性，SA由某一較高初溫開(kāi)始，利用具有概率突跳特性的Metropolis抽樣策略在解空間中進(jìn)行隨機(jī)搜索，伴隨溫度的不斷下降重復(fù)抽樣過(guò)程，最終得到問(wèn)題的全局最優(yōu)解。

2.模擬退火算法的基本思想和步驟二、模擬退火算法2023/11/1931基本思想標(biāo)準(zhǔn)模擬退火算法的一般步驟可描述如下：⑴給定初溫，隨機(jī)產(chǎn)生初始狀態(tài)，令；⑵重復(fù)過(guò)程:①Repeat

產(chǎn)生新?tīng)顟B(tài)；二、模擬退火算法2023/11/1932算法步驟（標(biāo)準(zhǔn)）Until抽樣穩(wěn)定準(zhǔn)則滿(mǎn)足；②退溫，并令；

Until算法終止準(zhǔn)則滿(mǎn)足；

⑶輸出算法搜索結(jié)果。二、模擬退火算法2023/11/1933

二、模擬退火算法2023/11/1934算法步驟（組合優(yōu)化問(wèn)題）模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)定

從算法流程上看，模擬退火算法包括:三函數(shù)兩準(zhǔn)則，即狀態(tài)產(chǎn)生函數(shù)、狀態(tài)接受函數(shù)、溫度更新函數(shù)、內(nèi)循環(huán)終止準(zhǔn)則和外循環(huán)終止準(zhǔn)則，這些環(huán)節(jié)的設(shè)計(jì)將決定SA算法的優(yōu)化性能。此外，初溫的選擇對(duì)SA算法性能也有很大影響。二、模擬退火算法2023/11/1935⑴狀態(tài)產(chǎn)生函數(shù)設(shè)計(jì)狀態(tài)產(chǎn)生函數(shù)（鄰域函數(shù)）的出發(fā)點(diǎn)應(yīng)該是盡可能保證產(chǎn)生的候選解遍布全部的解空間。通常，狀態(tài)產(chǎn)生函數(shù)由兩部分組成，即產(chǎn)生候選解的方式和候選解產(chǎn)生的概率分布。二、模擬退火算法2023/11/1936⑵狀態(tài)接受函數(shù)狀態(tài)接受函數(shù)一般以概率的方式給出，不同接受函數(shù)的差別主要在于接受概率的形式不同。設(shè)計(jì)狀態(tài)接受概率，應(yīng)該遵循以下原則：①在固定溫度下，接受使目標(biāo)函數(shù)值下降的候選解的概率要大于使目標(biāo)值上升的候選解的概率；二、模擬退火算法2023/11/1937②隨溫度的下降，接受使目標(biāo)函數(shù)值上升的解的概率要逐漸減?。虎郛?dāng)溫度趨于零時(shí)，只能接受目標(biāo)函數(shù)值下降的解。狀態(tài)接受函數(shù)的引入是SA算法實(shí)現(xiàn)全局搜索的最關(guān)鍵的因素，SA算法中通常采用min[1,exp(-△C/t)]作為狀態(tài)接受函數(shù)。二、模擬退火算法2023/11/1938⑶初溫

初始溫度、溫度更新函數(shù)、內(nèi)循環(huán)終止準(zhǔn)則和外循環(huán)終止準(zhǔn)則通常被稱(chēng)為退火歷程(annealingschedule)。實(shí)驗(yàn)表明，初溫越大，獲得高質(zhì)量解的幾率越大，但花費(fèi)的計(jì)算時(shí)間將增加。因此，初溫的確定應(yīng)折衷考慮優(yōu)化質(zhì)量和優(yōu)化效率，常用方法包括：

二、模擬退火算法2023/11/1939①均勻抽樣一組狀態(tài)，以各狀態(tài)目標(biāo)值的方差為初溫；②隨機(jī)產(chǎn)生一組狀態(tài)，確定兩兩狀態(tài)間的最大目標(biāo)值差，然后依據(jù)差值，利用一定的函數(shù)確定初溫。譬如，其中為初始接受概率；③利用經(jīng)驗(yàn)公式給出。二、模擬退火算法2023/11/1940⑷溫度更新函數(shù)溫度更新函數(shù)，即溫度的下降方式，用于在外循環(huán)中修改溫度值。目前，最常用的溫度更新函數(shù)為指數(shù)退溫函數(shù)，即其大小可以不斷變化。二、模擬退火算法2023/11/1941⑸內(nèi)循環(huán)終止準(zhǔn)則內(nèi)循環(huán)終止準(zhǔn)則，或稱(chēng)Metropolis抽樣穩(wěn)定準(zhǔn)則，用于決定在各溫度下產(chǎn)生候選解的數(shù)目。在非時(shí)齊SA算法理論中，由于在每個(gè)溫度下只產(chǎn)生一個(gè)或少量候選解，所以不存在選擇內(nèi)循環(huán)終止準(zhǔn)則的問(wèn)題。二、模擬退火算法2023/11/1942

而在時(shí)齊SA算法理論中，收斂條件要求在每個(gè)溫度下產(chǎn)生候選解的數(shù)目趨于無(wú)窮大，以使相應(yīng)的馬氏鏈（Markov鏈）達(dá)到平穩(wěn)概率分布，顯然在實(shí)際應(yīng)用算法時(shí)這是無(wú)法實(shí)現(xiàn)的。常用的抽樣準(zhǔn)則包括：①檢驗(yàn)?zāi)繕?biāo)函數(shù)的均值是否穩(wěn)定；②連續(xù)若干步的目標(biāo)值變化較??；③按一定的步數(shù)抽樣。

二、模擬退火算法2023/11/1943⑹外循環(huán)終止準(zhǔn)則外循環(huán)終止準(zhǔn)則，即算法終止準(zhǔn)則，用于決定算法何時(shí)結(jié)束。設(shè)置溫度終值是一種簡(jiǎn)單的方法。SA算法的收斂性理論中要求溫度終值趨于零，這顯然不合實(shí)際。通常的做法是：二、模擬退火算法2023/11/1944①設(shè)置終止溫度的閾值；②設(shè)置外循環(huán)迭代次數(shù)；③算法收斂到的最優(yōu)值連續(xù)若干步保持不變；④檢驗(yàn)系統(tǒng)熵是否穩(wěn)定。三、演化算法原理2023/11/1945演化算法是基于生物進(jìn)化思想而發(fā)展起來(lái)的一種問(wèn)題求解方法。采用簡(jiǎn)單的編碼技術(shù)來(lái)表示各種復(fù)雜的結(jié)構(gòu)，并通過(guò)對(duì)一組編碼表示進(jìn)行簡(jiǎn)單的遺傳操作和優(yōu)生劣汰的自然選擇來(lái)指導(dǎo)學(xué)習(xí)和確定搜索的方向。與傳統(tǒng)搜索算法相比具有以下的特點(diǎn)：演化算法從一個(gè)群體開(kāi)始搜索，可以同時(shí)搜索解空間內(nèi)的多個(gè)區(qū)域，效率高，具有本質(zhì)的并行性，能夠以較大的概率找到全局最優(yōu)解；1.引言三、演化算法原理2023/11/1946演化算法解的變換使用隨機(jī)轉(zhuǎn)移規(guī)則，只使用解的適應(yīng)性信息（即適應(yīng)函數(shù)或目標(biāo)函數(shù)），不受目標(biāo)函數(shù)連續(xù)、可謂微條件的限制；演化算法采用適者生存、不適者淘汰的自然選擇策略，利用個(gè)體的適應(yīng)值推動(dòng)群體的演化，算法設(shè)計(jì)過(guò)程中無(wú)需事先描述問(wèn)題的全部特點(diǎn)及其結(jié)構(gòu)特征。演化算法具有內(nèi)在學(xué)習(xí)性，包括宗親學(xué)習(xí)（phylogeneticlearning）：祖先的良好特征通過(guò)遺傳傳遞給后代；社團(tuán)學(xué)習(xí)（sociogeneticlearning）：獨(dú)立群體內(nèi)部知識(shí)或結(jié)構(gòu)共享；個(gè)體學(xué)習(xí)（ontogeneticlearning）：通過(guò)改變個(gè)體的基因結(jié)構(gòu)來(lái)提高自己的適應(yīng)度。三、演化算法原理2023/11/1947演化計(jì)算在機(jī)器學(xué)習(xí)、過(guò)程控制、經(jīng)濟(jì)預(yù)測(cè)、工程優(yōu)化等領(lǐng)域去的巨大的成功，在故障診斷領(lǐng)域也得到了廣泛的關(guān)注。三、演化算法原理2023/11/1948生物進(jìn)化學(xué)說(shuō)[達(dá)爾文（1858年）]包括以下3方面的內(nèi)容：遺傳（Heredity）：它是生物的普遍特征，子代按照從父代獲取的遺傳信息進(jìn)行發(fā)育和分化，保證了子代和父代之間具有相同或相似的形狀，使得物種得以穩(wěn)定存在；變異（Mutation）：它是生命多樣性的源泉，變異的發(fā)生使得子代的性狀不同于父代性狀；生存斗爭(zhēng)和適者生存：自然選擇來(lái)自繁衍過(guò)剩和生存斗爭(zhēng)，自然選擇的原則是“適者生存”，它決定了群體中只有對(duì)其生存環(huán)境具有較強(qiáng)適應(yīng)性的那些個(gè)體才能夠存活并繁殖。2.生物進(jìn)化過(guò)程的一般特性三、演化算法原理2023/11/1949演化計(jì)算一般具有如下幾大分支：遺傳算法（GeneticAlgorithm，GA）；演化策略（EvolutionStrategy，ES）；演化規(guī)劃（EvolutionaryProgramming，EP）；遺傳程序設(shè)計(jì)（GeneticProgramming，GP）：基于遺傳算法發(fā)展起來(lái)的一個(gè)分支。這幾個(gè)分支在算法實(shí)現(xiàn)方面具有一些細(xì)微的差別，但它們具有一個(gè)共同的特點(diǎn)，即都是借助生物演化的思想和原理來(lái)解決實(shí)際問(wèn)題。3.演化計(jì)算的主要分支4.1個(gè)體與種群

●個(gè)體就是模擬生物個(gè)體而對(duì)問(wèn)題中的對(duì)象一般就是問(wèn)題的解）的一種稱(chēng)呼，一個(gè)個(gè)體也就是搜索空間中的一個(gè)點(diǎn)。

●

種群(population)就是模擬生物種群而由若干個(gè)體組成的群體,它一般是整個(gè)搜索空間的一個(gè)很小的子集。三、演化算法原理4.遺傳算法的基本概念2023/11/19504.2適應(yīng)度與適應(yīng)度函數(shù)●

適應(yīng)度(fitness)就是借鑒生物個(gè)體對(duì)環(huán)境的適應(yīng)程度,而對(duì)問(wèn)題中的個(gè)體對(duì)象所設(shè)計(jì)的表征其優(yōu)劣的一種測(cè)度。

●

適應(yīng)度函數(shù)(fitnessfunction)就是問(wèn)題中的全體個(gè)體與其適應(yīng)度之間的一個(gè)對(duì)應(yīng)關(guān)系。它一般是一個(gè)實(shí)值函數(shù)。該函數(shù)就是遺傳算法中指導(dǎo)搜索的評(píng)價(jià)函數(shù)。

三、演化算法原理2023/11/19514.3.染色體與基因

染色體（chromosome）就是問(wèn)題中個(gè)體的某種字符串形式的編碼表示。字符串中的字符也就稱(chēng)為基因（gene）。例如：個(gè)體染色體

9----

1001

（2，5，6）----010101110三、演化算法原理2023/11/19524.4.遺傳操作亦稱(chēng)遺傳算子(geneticoperator)，就是關(guān)于染色體的運(yùn)算。遺傳算法中有三種遺傳操作:●選擇-復(fù)制(selection-reproduction)●交叉(crossover，亦稱(chēng)交換、交配或雜交)●變異(mutation，亦稱(chēng)突變)

三、演化算法原理2023/11/1953選擇-復(fù)制通常做法是：對(duì)于一個(gè)規(guī)模為N的種群S,按每個(gè)染色體xi∈S的選擇概率P(xi)所決定的選中機(jī)會(huì),分N次從S中隨機(jī)選定N個(gè)染色體,并進(jìn)行復(fù)制。

這里的選擇概率P(xi)的計(jì)算公式為三、演化算法原理2023/11/1954交叉就是互換兩個(gè)染色體某些位上的基因。

s1′=01000101,s2′=10011011，可以看做是原染色體s1和s2的子代染色體。

例如,設(shè)染色體

s1=01001011,s2=10010101,交換其后4位基因,即三、演化算法原理2023/11/1955

變異就是改變?nèi)旧w某個(gè)(些)位上的基因。例如,設(shè)染色體s=11001101，將其第三位上的0變?yōu)?,即

s=11001101→11101101=s′。

s′也可以看做是原染色體s的子代染色體。三、演化算法原理2023/11/19565基本遺傳算法

遺傳算法基本流程框圖生成初始種群計(jì)算適應(yīng)度選擇-復(fù)制交叉變異生成新一代種群終止?結(jié)束三、演化算法原理2023/11/19571975年J.Holland在研究自然和人工系統(tǒng)自適應(yīng)行為的過(guò)程中提出了遺傳算法，他提出的遺傳算法常被稱(chēng)為簡(jiǎn)單遺傳算法（簡(jiǎn)記SGA），SGA的操作對(duì)象是一群二進(jìn)制串（稱(chēng)為染色體、個(gè)體），即種群（population），每個(gè)染色體都對(duì)應(yīng)于問(wèn)題的一個(gè)解。從初始種群出發(fā)，采用基于適應(yīng)值比例的選擇策略在當(dāng)前種群中選擇個(gè)體，適應(yīng)雜交（crossover）和變異來(lái)產(chǎn)生下一代種群，如此一代代演化下去，指導(dǎo)滿(mǎn)足期望的終止條件。

5.1算法中的一些控制參數(shù)：■

種群規(guī)模■

最大代數(shù)■

交叉率(crossoverrate)就是參加交叉運(yùn)算的染色體個(gè)數(shù)占全體染色體總數(shù)的比例，記為Pc,取值范圍一般為0.4～0.99?！?/p>

變異率(mutationrate)是指發(fā)生變異的基因位數(shù)所占全體染色體的基因總位數(shù)的比例，記為Pm，取值范圍一般為0.0001～0.1。三、演化算法原理2023/11/19585.2基本遺傳算法

步1在搜索空間U上定義一個(gè)適應(yīng)度函數(shù)f(x)，給定種群規(guī)模N、交叉率Pc和變異率Pm、代數(shù)T；步2隨機(jī)產(chǎn)生U中的N個(gè)個(gè)體s1,s2,…,sN，組成初始種群S={s1,s2,…,sN}，置代數(shù)計(jì)數(shù)器t=1；步3計(jì)算S中每個(gè)個(gè)體的適應(yīng)度f(wàn)()

；步4若終止條件滿(mǎn)足，則取S中適應(yīng)度最大的個(gè)體作為所求結(jié)果，算法結(jié)束。三、演化算法原理2023/11/1959

步5按選擇概率P(xi)所決定的選中機(jī)會(huì)，每次從S中隨機(jī)選定1個(gè)個(gè)體并將其染色體復(fù)制，共做N次，然后將復(fù)制所得的N個(gè)染色體組成群體S1；步6按交叉率Pc所決定的參加交叉的染色體數(shù)c，從S1中隨機(jī)確定c個(gè)染色體，配對(duì)進(jìn)行交叉操作，并用產(chǎn)生的新染色體代替原染色體，得群體S2；三、演化算法原理2023/11/1960

步7按變異率Pm所決定的變異次數(shù)m，從S2中隨機(jī)確定m個(gè)染色體，分別進(jìn)行變異操作，并用產(chǎn)生的新染色體代替原染色體，得群體S3；步8將群體S3作為新一代種群，即用S3代替S，t=t+1，轉(zhuǎn)步3；6遺傳算法應(yīng)用舉例例4.1

利用遺傳算法求解區(qū)間［0,31］上的二次函數(shù)y=x2的最大值。y=x2

31

XY三、演化算法原理2023/11/1961

分析

原問(wèn)題可轉(zhuǎn)化為在區(qū)間［0,31］中搜索能使y取最大值的點(diǎn)a的問(wèn)題。那么，［0,31］中的點(diǎn)x就是個(gè)體,函數(shù)值f(x)恰好就可以作為x的適應(yīng)度，區(qū)間［0,31］就是一個(gè)(解)空間。這樣,只要能給出個(gè)體x的適當(dāng)染色體編碼,該問(wèn)題就可以用遺傳算法來(lái)解決。三、演化算法原理2023/11/1962解

(1)設(shè)定種群規(guī)模，編碼染色體，產(chǎn)生初始種群。將種群規(guī)模設(shè)定為4；用5位二進(jìn)制數(shù)編碼染色體；取下列個(gè)體組成初始種群S1:s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)(2)定義適應(yīng)度函數(shù),

取適應(yīng)度函數(shù)：f(x)=x2

三、演化算法原理2023/11/1963

(3)計(jì)算各代種群中的各個(gè)體的適應(yīng)度,并對(duì)其染色體進(jìn)行遺傳操作,直到適應(yīng)度最高的個(gè)體(即31（11111）)出現(xiàn)為止。

三、演化算法原理2023/11/1964

首先計(jì)算種群S1中各個(gè)體

s1=13(01101),s2=24(11000)

s3=8(01000),s4=19(10011)的適應(yīng)度f(wàn)(si)。

容易求得

f(s1)=f(13)=132=169f(s2)=f(24)=242=576f(s3)=f(8)=82=64f(s4)=f(19)=192=361再計(jì)算種群S1中各個(gè)體的選擇概率。選擇概率的計(jì)算公式為

由此可求得

P(s1)=P(13)=0.14P(s2)=P(24)=0.49P(s3)=P(8)=0.06P(s4)=P(19)=0.31三、演化算法原理2023/11/1965

賭輪選擇示意s40.31s20.49s10.14s30.06●賭輪選擇法三、演化算法原理2023/11/1966在算法中賭輪選擇法可用下面的子過(guò)程來(lái)模擬:

①在［0,1］區(qū)間內(nèi)產(chǎn)生一個(gè)均勻分布的隨機(jī)數(shù)r。②若r≤q1，則染色體x1被選中。③若qk-1<r≤qk(2≤k≤N),則染色體xk被選中。其中的qi稱(chēng)為染色體xi

(i=1,2,…,n)的積累概率，其計(jì)算公式為三、演化算法原理2023/11/1967選擇-復(fù)制

設(shè)從區(qū)間［0,1］中產(chǎn)生4個(gè)隨機(jī)數(shù)如下:r1=0.450126,r2=0.110347r3=0.572496,r4=0.98503

染色體

適應(yīng)度選擇概率積累概率選中次數(shù)s1=011011690.140.141s2=110005760.490.632s3=01000640.060.690s4=100113610.311.001三、演化算法原理2023/11/1968于是，經(jīng)復(fù)制得群體：s1’=11000（24）,s2’=01101（13）s3’=11000（24）,s4’=10011（19）三、演化算法原理2023/11/1969交叉

設(shè)交叉率pc=100%，即S1中的全體染色體都參加交叉運(yùn)算。設(shè)s1’與s2’配對(duì)，s3’與s4’配對(duì)。分別交換后兩位基因，得新染色體：

s1’’=11001（25）,s2’’=01100（12）

s3’’=11011（27）,s4’’=10000（16）

三、演化算法原理2023/11/1970變異設(shè)變異率pm=0.001。這樣，群體S1中共有

5×4×0.001=0.02位基因可以變異。

0.02位顯然不足1位，所以本輪遺傳操作不做變異。三、演化算法原理2023/11/1971

于是，得到第二代種群S2：

s1=11001（25）,s2=01100（12）

s3=11011（27）,s4=10000（16）三、演化算法原理2023/11/1972

第二代種群S2中各染色體的情況

染色體

適應(yīng)度選擇概率積累概率

估計(jì)的選中次數(shù)s1=110016250.360.361s2=011001440.080.440s3=110117290.410.852s4=100002560.151.001三、演化算法原理2023/11/1973假設(shè)這一輪選擇-復(fù)制操作中，種群S2中的4個(gè)染色體都被選中，則得到群體：s1’=11001（25）,s2’=01100（12）

s3’=11011（27）,s4’=10000（16）

做交叉運(yùn)算，讓s1’與s2’，s3’與s4’

分別交換后三位基因，得s1’’=11100（28）,s2’’=01001（9）

s3’’=11000（24）,s4’’=10011（19）這一輪仍然不會(huì)發(fā)生變異。三、演化算法原理2023/11/1974于是，得第三代種群S3：

s1=11100（28）,s2=01001（9）

s3=11000（24）,s4=10011（19）2023/11/1975

第三代種群S3中各染色體的情況

染色體

適應(yīng)度選擇概率積累概率

估計(jì)的選中次數(shù)s1=111007840.440.442s2=01001810.040.480s3=110005760.320.801s4=100113610.201.001三、演化算法原理2023/11/1976

設(shè)這一輪的選擇-復(fù)制結(jié)果為：

s1’=11100（28）,s2’=11100（28）

s3’=11000（24）,s4’=10011（19）

做交叉運(yùn)算，讓s1’與s4’，s2’與s3’

分別交換后兩位基因，得s1’’=11111（31）,s2’’=11100（28）

s3’’=11000（24）,s4’’=10000（16）

這一輪仍然不會(huì)發(fā)生變異。三、演化算法原理2023/11/1977

于是，得第四代種群S4：

s1=11111（31）,s2=11100（28）

s3=11000（24）,s4=10000（16）三、演化算法原理2023/11/1978顯然，在這一代種群中已經(jīng)出現(xiàn)了適應(yīng)度最高的染色體s1=11111。于是，遺傳操作終止，將染色體“11111”作為最終結(jié)果輸出。

然后，將染色體“11111”解碼為表現(xiàn)型，即得所求的最優(yōu)解：31。將31代入函數(shù)y=x2中，即得原問(wèn)題的解，即函數(shù)y=x2的最大值為961。三、演化算法原理2023/11/1979YYy=x2

8131924

X第一代種群及其適應(yīng)度y=x2

12162527

XY第二代種群及其適應(yīng)度y=x2

9192428

XY第三代種群及其適應(yīng)度y=x2

16242831

X第四代種群及其適應(yīng)度2023/11/1980

例4.2

用遺傳算法求解TSP。

分析由于其任一可能解——一個(gè)合法的城市序列，即n個(gè)城市的一個(gè)排列，都可以事先構(gòu)造出來(lái)。于是，我們就可以直接在解空間（所有合法的城市序列）中搜索最佳解。這正適合用遺傳算法求解。三、演化算法原理（1）定義適應(yīng)度函數(shù)