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

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