智能優(yōu)化理論-第3章遺傳算法

遺傳算法目錄contents遺傳算法尋優(yōu)的基本思路遺傳算法的理論基礎遺傳算法的實現(xiàn)及改進算法遺傳算法尋優(yōu)的基本思路01遺傳算法是一種基于自然選擇和基因遺傳學原理的搜索算法，將“適者生存”這一基本的達爾文進化原理引入串結(jié)構(gòu)，并且在串之間進行有組織但又隨機的信息交換。伴隨著算法的運行，優(yōu)良的品質(zhì)被逐漸保留并加以組合，從而不斷產(chǎn)生出更佳的個體。好的特征被不斷地繼承下來，壞的特性被逐漸淘汰。新一代個體中包含著上一代個體的大量信息，新一代的個體不斷地在總體特性上勝過舊的一代，從而使整個群體向前進化發(fā)展。遺傳算法尋優(yōu)的基本思路研究遺傳算法的目的主要有兩個：一是通過它的研究來進一步解釋自然界的適應過程；二是為了將自然生物系統(tǒng)的重要機理運用到人工系統(tǒng)的設計中。遺傳算法的中心問題是魯棒性，它能在許多不同的環(huán)境中通過效率及功能之間的協(xié)調(diào)平衡以求生存。人工系統(tǒng)很難達到如生物系統(tǒng)那樣的魯棒性。遺傳算法正是吸取了自然生物系統(tǒng)“適者生存”的進化原理，使它能夠提供一個在復雜空間中進行魯棒搜索的方法。遺傳算法尋優(yōu)的基本思路輸入標題02010403遺傳算法尋優(yōu)的基本思路遺傳算法具有計算簡單及功能強的特點，它對于搜索空間基本上不需要什么限制性的假設（如連續(xù)、導數(shù)存在及單峰等）。枚舉法最大缺點是計算效率太低，對于一個實際問題，常常由于太大的搜索空間而不可能將所有的情況都搜索到。枚舉法可以克服上述解析法的兩個缺點，即它可以尋找到全局的極值，而且也不需要目標函數(shù)是連續(xù)光滑的。常規(guī)的尋優(yōu)方法主要有3種類型：解析法、枚舉法和隨機法。解析法尋優(yōu)通過讓目標函數(shù)的梯度為零，進而求解一組非線性方程來尋求局部極值。遺傳算法的理論基礎0203表現(xiàn)型生物個體表現(xiàn)出來的性狀，即具有特定基因型的個體在一定環(huán)境條件下表現(xiàn)出來的性狀特征的總和。01基因是DNA分子片段，含有大量遺傳信息，是控制生物體性狀的基本遺傳單位。02染色體包含一定數(shù)目的基因，是基因的物質(zhì)載體，也是細胞中遺傳信息的物質(zhì)載體。遺傳算法的基本概念遺傳算法的基本概念01種群：每個物種由一定數(shù)量的個體組成，所有個體的總和稱為種群。02適應度：用于衡量種群中每個個體的優(yōu)劣程度，是度量每個個體對其生存環(huán)境的適應能力的標準。03遺傳算法中，適應度函數(shù)根據(jù)目標函數(shù)設定，它的大小直接影響到種群中每個個體的生存概率。04一種群為遺傳算法提供了搜索解的遺傳進化搜索空間。010203通過一個簡單的例子詳細描述遺傳算法的基本操作過程，目的在于清晰地展現(xiàn)遺傳算法的理論基礎。設需要求解的優(yōu)化問題為尋找當自變量x在0-31之間取整數(shù)值時函數(shù)的最大值。枚舉的方法是將x取盡所有可能值，觀察是否得到最高的目標函數(shù)值。盡管對如此簡單的問題該法是可靠的．但這是一種效率很低的方法。下面運用遺傳算法來求解這個問題。遺傳算法的基本操作針對本例中自變量的定義域，可以考慮采用二進制數(shù)來對其編碼，這里恰好可用5位數(shù)來表示，如01010對應11111對應。許多其他的優(yōu)化方法是從定義域空間的某個單個點出發(fā)來求解問題，并且根據(jù)某些規(guī)則，它相當于按照一定的路線，進行點到點的順序搜索。遺傳算法的第一步是將x編碼為有限長度的串。編碼的方法很多，這里僅舉一種簡單易行的方法。遺傳算法的基本操作對于多峰值問題的求解很容易陷入局部極值。而遺傳算法則是從一個種群（由若干個串組成，每個串對應一個自變量值）開始，不斷地產(chǎn)生和測試新一代的種群。這種方法一開始便擴大了搜索的范圍，因而可期望較快地完成問題的求解。初始種群的生成往往是隨機產(chǎn)生的。對于本例，若設種群大小為4，即含有4個個體，則需按位隨機生成4個5位二進制串，如可以通過擲硬幣的方法來生成隨機的串。遺傳算法的基本操作若用計算機，可考慮首先產(chǎn)生0-l之間均勻分布的隨機數(shù)．然后規(guī)定產(chǎn)生的隨機數(shù)在0-0.5之間代表0，0.5-1之間的隨機數(shù)代表1。若用上述方法，隨機生成以下4個位串：01101，11000，01000，10011。位串1-4可分別解碼為如下十進制的數(shù)遺傳算法的基本操作位串1位串3位串2遺傳算法的基本操作這樣便完成了遺傳算法的準備工作。位串4選擇、交叉和變異。下面來介紹遺傳算法的3個基本操作步驟遺傳算法的基本操作01適應度越大，被選中的概率就越大．從而遺傳到下一代的概率越大。優(yōu)良個體在種群中具有較強的繁殖能力，而適應度較差的個體會受到排擠，甚至被淘汰。在選擇算子的作用下，種群的整體質(zhì)量得到逐步提高。在遺傳算法中，以適應度為指標，把當前種群中適應度較高的個體選擇出來，為下一步遺傳操作做準備。020304遺傳算法的基本操作123遺傳算法的特點之一是它不對實際決策變量直接進行操作，而是對表示解的個體編碼進行選擇、交叉、變異等遺傳運算。編碼是應用遺傳算法時要解決的首要問題，也是設計遺傳算法時的一個關鍵步驟。好的編碼方法可以使得交叉運算、變異運算等遺傳操作簡單易行，而差的編碼方法則可能使得這些操作難以實現(xiàn)。遺傳個體編碼遺傳個體編碼假設某一個體的編碼是則對應的解碼公式為進制編碼方法有下述一些優(yōu)點：編碼、解碼操作簡單易行。遺傳個體編碼03便于利用模式定理對算法進行理論分析。01交叉、變異等遺傳操作便于實現(xiàn)。02符合最小字符集編碼原則。遺傳個體編碼遺傳算法在進化搜索中基本不利用外部信息，僅以適應度函數(shù)(fitnessfunction)為依據(jù)，利用種群中每個個體的適應度值來進行搜索。適應度函數(shù)的選取至關重要，直接影響到遺傳算法的收斂速度以及能否找到最優(yōu)解。一般而言，適應度函數(shù)是由目標函數(shù)轉(zhuǎn)換而成的。對目標函數(shù)值域的某種映射變換稱為適應度的尺度變換。幾種常見的適應度函數(shù)：直接以待求解的目標函數(shù)轉(zhuǎn)化為適應度函數(shù)，改進的“界限構(gòu)造法”和保守估計法。適應度函數(shù)的作用：在選擇操作時會出現(xiàn)一些問題，如超常個體和種群中個體適應度差異較小的情況。適應度函數(shù)的設計：通常，適應度函數(shù)設計主要滿足以下條件：單值、連續(xù)、非負和最大化；合理性和一致性；計算量??；通用性強。適應度函數(shù)及其尺度變換遺傳算法的實現(xiàn)及改進算法03遺傳算法需要提前設定控制參數(shù)，包括種群大小、交叉概率、變異概率和終止條件。種群大小影響算法效率，太小會降低多樣性，太大則會影響收斂速度。交叉概率一般為0.400～0.990，變異概率在0.001～0.100范圍內(nèi)。遺傳算法的實現(xiàn)終止條件分為兩類：一類是預先設定的最大函數(shù)評價次數(shù)NFE，另一類是未找到最優(yōu)解則終止算法。交叉操作借鑒生物進化中兩性繁殖的作用方式，對兩個個體進行基因?qū)Q操作產(chǎn)生新個體。變異操作通過對染色體的某些基因位點進行突變來產(chǎn)生新的個體，變異的主要作用在于保持種群的多樣性。010203遺傳算法的實現(xiàn)遺傳算法的實現(xiàn)在種群中多數(shù)個體趨同的情況下，交叉操作能夠產(chǎn)生的不同于父代個體的數(shù)量非常有限，甚至重復產(chǎn)生相同的解，而變異操作可以較為有效地異化種群中的個體，增加多樣性，從而在一定程度上避免算法陷入早熟收斂。遺傳算法的改進研究編碼策略是遺傳算法的基礎工作之一，在問題求解中扮演著重要的角色。實際工程優(yōu)化問題中的變量往往不能直接被遺傳算法作用，需要采用編碼策略將實際變量轉(zhuǎn)化為可以被遺傳算法直接操作的對象。編碼過程實質(zhì)上是一種“映射”過程，即在優(yōu)化問題與算法涉及的操作對象之間建立一個一一對應法則。遺傳算法的改進研究針對不同的問題，人們提出了不同的編碼方式，包括二進制編碼、格雷編碼和實數(shù)編碼等。格雷碼克服了二進制碼的不足，連續(xù)兩個整數(shù)對應的編碼之間僅有一個碼位不同，其余完全相同。二進制編碼具有最小字符編碼原理和模式定理，但存在局部搜索能力不強、連續(xù)函數(shù)離散化誤差大、不能反映問題固有結(jié)構(gòu)等缺點。實數(shù)編碼則針對多維、高精度要求的連續(xù)變量優(yōu)化問題，將每個基因值用實數(shù)表示，提高了編碼的精度和運行效率。自適應遺傳算法中，交叉概率和變異概率的選擇是影響算法行為和性能的關鍵所在。交叉概率越大，新個體產(chǎn)生的速度就越快。然而，當交叉概率過大時，遺傳模式被破壞的可能性也會變大。如果交叉概率過小，會使搜索過程變得緩慢，甚至停滯不前。遺傳算法的經(jīng)典變體遺傳算法的經(jīng)典變體變異概率太小，不易產(chǎn)生新的個體結(jié)構(gòu)；太大則變成隨機搜索算法。02Srinivas等首次提出一種自適應遺傳算法(AdaptiveGeneticAlgorithm，AGA)，其中交叉概率與變異概率能夠隨著適應度的大小而改變。03當群體中各個個體的適應度值趨于一致或者趨于局部最優(yōu)時，增加交叉和變異概率；而當群體適應度值比較分散時，減小交叉和變異概率。01遺傳算法的經(jīng)典變體種群中具有最大適應值的個體的交叉概率和變異概率為零，這增大了進化趨向局部最優(yōu)解的可能性。對適應度值高于群體平均適應度值的個體，給予較低的交叉和變異概率，使該個體得以保護進入下一代；而低于平均適應度值的個體，基于較高的交叉和變異概率，使該個體被淘汰。改進的自適應遺傳算法使種群中具有最大適應值的個體的交叉概率和變異概率不為零。VS一個刻畫種群多樣性的函數(shù)，在此基礎上提出交叉和變異算子的點數(shù)隨種群多樣性而變化?；旌线z傳算法的實質(zhì)是將不同算法的優(yōu)點有機結(jié)合，改善單純遺傳算法的性能。遺傳算法的經(jīng)典變體改進的遺傳算法舉例01改進的遺傳算法在一個高低不同的層次上都使用了遺傳算法。02生物模型中，遺傳算法是對一個群體進行操作，該群體相當于自然界中的一群人。第一步的選擇是以現(xiàn)實世界中的優(yōu)勝劣汰現(xiàn)象為背景的。03010203第二步的交叉則相當于人類的結(jié)婚和生育。第三步的變異則與自然界中偶然發(fā)生的變異是一致的。包含著對模式的操作，遺傳算法不斷地產(chǎn)生