機(jī)械故障診斷學(xué)鐘秉林第8章模擬退火與演化算法原理課件

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

模擬退火算法原理

演化算法原理

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

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

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

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

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

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

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

最大化 滿足一、概述2022/10/1813在應(yīng)用問題中，設(shè)S的元素是n項(xiàng)經(jīng)營活動各自所需的資源消耗，C是所能提供的資源總量，P的元素是人們從每項(xiàng)經(jīng)營活動中得到的利潤或收益，則背包問題就是在資源有限的條件下，追求總的最大收益的資源有效分配問題。背包問題屬于NP-難問題一、概述2022/10/1814多選擇背包問題：有一個容積有限的背包。要放入背包的物品被分為不重疊的若干類，每類中有若干不同的物品，從每類中選擇一個物品，使得物品總體積在滿足背包容積約束的前提下最大化收益。屬于NP－難問題一、概述2022/10/1815i為類下標(biāo)；j為類中物品的下標(biāo)；ni是第i類中物品的數(shù)量；cij是第i類中第j個物品的收益；m是類的數(shù)量；wij為第i類中第j個項(xiàng)目的體積，W是背包的容積。最大化所選物品的總價值所選物品的總體積不得超過背包容積每一類中只能選一個物品一、概述2022/10/1816旅行商問題（TravelingSalesmanProblem）尋找一條最短的遍歷n個城市的路徑，或者說搜索整數(shù)子集X＝{1，2，…，n}（X的元素表示對n個城市的編號）的一個排列π(X)={v1，v2，…，vn}，使下式取最小值。式中的d(vi,vi+1)表示城市vi到城市vi+1的距離。對稱旅行商問題是NP－難問題一、概述2022/10/1817影片遞送問題（FilmDeliveryProblem）一盤影片拷貝要在n個電影院放映。每個電影院放映的次數(shù)已定，記為一個非負(fù)的整數(shù)di(i＝1，2，…，n)。兩個影院間的距離記為wij，若影院i和j不能直接相連，則令wij＝+。問題是要為影片遞送員找一個巡回，從主影院1開始，將影片拷貝送到第i家影院di(i＝1，2，…，n)次，最后回到主影院1，并極小化總的路線長度。當(dāng)所有的di(i＝l，2，…，n)為1時，F(xiàn)DP變?yōu)榻?jīng)典的TSP。FDP是TSP的新擴(kuò)展，它可以推廣到一大類路徑與排序問題中。一、概述2022/10/1818圖的二劃分問題：對于一無向圖G，設(shè)其頂點(diǎn)集合為V，將頂點(diǎn)集合V劃分為兩個子集V1和V2，VlV2＝，求使V1和V2兩頂點(diǎn)子集之間聯(lián)結(jié)最少的一種劃分。圖的劃分問題在電子線路設(shè)計中非常重要。例如，在多層印刷電路板的布局設(shè)計中，使層間聯(lián)線數(shù)目最少的器件布局等。由于圖的劃分問題的計算復(fù)雜度極高(3000個節(jié)點(diǎn)的二劃分問題的搜索空間可達(dá)10900)，因此，在實(shí)用規(guī)模上精確求出最優(yōu)解是不可能的。一、概述2022/10/1819廣義地講，調(diào)度問題考慮的是隨著時間的變化，如何調(diào)度有限的資源在執(zhí)行任務(wù)的同時滿足特定約束。資源：人力、金錢、機(jī)器、工具、材料、能源、等等。任務(wù)：制造系統(tǒng)的加工工序；計算機(jī)系統(tǒng)的信息處理。任務(wù)的表征：完成時間、預(yù)期時間、相對緊急權(quán)重、處理時間和資源消耗。一、概述2022/10/1820經(jīng)典作業(yè)車間調(diào)度問題（Job-shopScheduling）：有m臺不同的機(jī)器和n個不同的工件，每個工件包含一個由多道工序組成的工序集合，工件的工序順序是預(yù)先給定的。每道工序用它所要求的機(jī)器和固定的加工時間來表示。此外對工件和機(jī)器有一些約束，例如： (1)一個工件不能兩次訪問同一機(jī)器； (2)不同工件的工序之間沒有先后約束； (3)工序一旦進(jìn)行不能中斷；· (4)每臺機(jī)器一次只能加工一個工件； (5)下達(dá)時間和交貨期都不是給定的。 問題：確定機(jī)器上工序的順序，以最小化完成所有工件所需的最小加工持續(xù)時間。一、概述2022/10/1821局部搜索算法是基于貪婪思想利用鄰域函數(shù)進(jìn)行搜索的，容易實(shí)現(xiàn)，但其搜索性能完全依賴于鄰域函數(shù)和初始解的選取，領(lǐng)域函數(shù)設(shè)計不當(dāng)或初始解選擇不合適，算法的最終性能將會很差；同時貪婪思想也導(dǎo)致其最終解只具有局部最優(yōu)性；此外，局部搜索算法的時間復(fù)雜性取決于問題的性質(zhì)與鄰域結(jié)構(gòu)的復(fù)雜程度。鑒于局部搜索算法的上述缺點(diǎn)，許多學(xué)者提出了各種各樣的方法來改善算法的性能。模擬退火算法和演化算法從不同的角度，利用不同的搜索機(jī)制和實(shí)現(xiàn)策略實(shí)現(xiàn)了對局部搜索算法的改進(jìn)，具有了全局最優(yōu)的性能，成為兩種較為成功的全局優(yōu)化算法。一、概述2.組合優(yōu)化問題的局部搜索算法2022/10/1822算法的提出

模擬退火算法(SimulatedAnnealing,簡稱SA)的思想最早是由Metropolis等(1953)提出的，1983年Kirkpatrick等將其用于組合優(yōu)化。SA算法是基于MonteCarlo迭代求解策略的一種隨機(jī)尋優(yōu)算法，其出發(fā)點(diǎn)是基于物理中固體物質(zhì)的退火過程與一般組合優(yōu)化問題之間的相似性。算法的目的解決NP復(fù)雜性問題；克服優(yōu)化過程陷入局部極小；克服初值依賴性。二、模擬退火算法2022/10/1823

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

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

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

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

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

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

P(E)

∝exp(-E/kT)

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

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

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

產(chǎn)生新狀態(tài)；二、模擬退火算法2022/10/1832算法步驟（標(biāo)準(zhǔn)）Until抽樣穩(wěn)定準(zhǔn)則滿足；②退溫，并令；

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

⑶輸出算法搜索結(jié)果。二、模擬退火算法2022/10/1833

二、模擬退火算法2022/10/1834算法步驟（組合優(yōu)化問題）模擬退火算法關(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è)計將決定SA算法的優(yōu)化性能。此外，初溫的選擇對SA算法性能也有很大影響。二、模擬退火算法2022/10/1835⑴狀態(tài)產(chǎn)生函數(shù)設(shè)計狀態(tài)產(chǎn)生函數(shù)（鄰域函數(shù)）的出發(fā)點(diǎn)應(yīng)該是盡可能保證產(chǎn)生的候選解遍布全部的解空間。通常，狀態(tài)產(chǎn)生函數(shù)由兩部分組成，即產(chǎn)生候選解的方式和候選解產(chǎn)生的概率分布。二、模擬退火算法2022/10/1836⑵狀態(tài)接受函數(shù)狀態(tài)接受函數(shù)一般以概率的方式給出，不同接受函數(shù)的差別主要在于接受概率的形式不同。設(shè)計狀態(tài)接受概率，應(yīng)該遵循以下原則：①在固定溫度下，接受使目標(biāo)函數(shù)值下降的候選解的概率要大于使目標(biāo)值上升的候選解的概率；二、模擬退火算法2022/10/1837②隨溫度的下降，接受使目標(biāo)函數(shù)值上升的解的概率要逐漸減小；③當(dāng)溫度趨于零時，只能接受目標(biāo)函數(shù)值下降的解。狀態(tài)接受函數(shù)的引入是SA算法實(shí)現(xiàn)全局搜索的最關(guān)鍵的因素，SA算法中通常采用min[1,exp(-△C/t)]作為狀態(tài)接受函數(shù)。二、模擬退火算法2022/10/1838⑶初溫

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

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

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

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

●

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

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

●

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

三、演化算法原理2022/10/18514.3.染色體與基因

染色體（chromosome）就是問題中個體的某種字符串形式的編碼表示。字符串中的字符也就稱為基因（gene）。例如：個體染色體

9----

1001

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

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

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

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

例如,設(shè)染色體

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

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

s=11001101→11101101=s′。

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

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

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

種群規(guī)?！?/p>

最大代數(shù)■

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

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

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

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

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

步7按變異率Pm所決定的變異次數(shù)m，從S2中隨機(jī)確定m個染色體，分別進(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三、演化算法原理2022/10/1861

分析

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

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

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

三、演化算法原理2022/10/1863

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

三、演化算法原理2022/10/1864

首先計算種群S1中各個體

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

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

容易求得

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

由此可求得

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

賭輪選擇示意s40.31s20.49s10.14s30.06●賭輪選擇法三、演化算法原理2022/10/1866在算法中賭輪選擇法可用下面的子過程來模擬:

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

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

設(shè)從區(qū)間［0,1］中產(chǎn)生4個隨機(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三、演化算法原理2022/10/1868于是，經(jīng)復(fù)制得群體：s1’=11000（24）,s2’=01101（13）s3’=11000（24）,s4’=10011（19）三、演化算法原理2022/10/1869交叉

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

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

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

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

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

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

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

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

s3=11011（27）,s4=10000（16）三、演化算法原理2022/10/1872

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

染色體

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

估計的選中次數(shù)s1=110016250.360.361s2=011001440.080.440s3=110117290.410.852s4=100002560.151.001三、演化算法原理2022/10/1873假設(shè)這一輪選擇-復(fù)制操作中，種群S2中的4個染色體都被選中，則得到群體：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）這一輪仍然不會發(fā)生變異。三、演化算法原理2022/10/1874于是，得第三代種群S3：

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

s3=11000（24）,s4=10011（19）2022/10/1875

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

染色體

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

估計的選中次數(shù)s1=111007840.440.442s2=01001810.040.480s3=110005760.320.801s4=100113610.201.001三、演化算法原理2022/10/1876

設(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）

這一輪仍然不會發(fā)生變異。三、演化算法原理2022/10/1877

于是，得第四代種群S4：

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

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

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

8131924

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

12162527

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

9192428

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

16242831

X第四代種群及其適應(yīng)度2022/10/1880

例4.2

用遺傳算法求解TSP。

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