第6章遺傳算法

1、2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院1第六章 遺傳算法 6.1遺傳算法概述 6.2基本遺傳算法 6.3遺傳算法數(shù)學(xué)基礎(chǔ) 6.4遺傳算法的改進(jìn)2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院26.1 遺傳算法概述一、簡(jiǎn)介 遺傳算法(Genetic Algorithms, GA)是模擬生物在自然環(huán)境中的遺傳和進(jìn)化過(guò)程而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法. 遺傳算法吸取了自然生物系統(tǒng)“適者生存”的進(jìn)化理論，將達(dá)爾文的進(jìn)化理論引入人工系統(tǒng)串結(jié)構(gòu)的改造中，使得串結(jié)構(gòu)及其攜帶的信息發(fā)生有組織的而又是隨機(jī)的變換和組合，并使該過(guò)程按物種進(jìn)化規(guī)律來(lái)操作運(yùn)行，設(shè)法使物種的優(yōu)良品質(zhì)在組合中加以保留，從而不斷產(chǎn)

2、生出更佳的個(gè)體后代。2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院36.1 遺傳算法概述二、發(fā)展簡(jiǎn)史 n20世紀(jì)50年代，生物學(xué)家Fraser試圖通過(guò)計(jì)算的方法來(lái)模擬生物界“遺傳與選擇”的進(jìn)化過(guò)程 。n20世紀(jì)60年代，1975年Holland教授出版了遺傳算法歷史上的經(jīng)典著作Adaptation in Natural and Artificial Systems，首次提出遺傳算法的概念 。n20世紀(jì)80年代，迅速發(fā)展 ，1989年，Holland的學(xué)生Goldberg出版了Genetic Algorithms in Search ,Optimization and Machine Learni

3、ng 一書，為這一領(lǐng)域奠定了堅(jiān)實(shí)的科學(xué)基礎(chǔ)。n20世紀(jì)90年代，隨著計(jì)算機(jī)技術(shù)的發(fā)展，遺傳算法在各個(gè)領(lǐng)域得到了廣泛的應(yīng)用。不同領(lǐng)域的專家、學(xué)者根據(jù)各自的實(shí)際問(wèn)題，構(gòu)造出了多種能很好地解決行業(yè)問(wèn)題新的遺傳算法。 2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院46.1 遺傳算法概述三、遺傳算法的特點(diǎn) v全局性v并行性和高效性v魯棒性 v普適性和易擴(kuò)性 v簡(jiǎn)明性 2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院56.2 基本遺傳算法一、基本原理1、基本術(shù)語(yǔ)n染色體：遺傳物質(zhì)的主要載體，指多個(gè)遺傳因子的集合。n個(gè)體：指染色體帶有特征的實(shí)體稱個(gè)體n種群：染色體帶有特征個(gè)體的集合稱為群體，該集合內(nèi)的個(gè)體書稱為群

4、體的大小。n編碼：從表現(xiàn)型到遺傳子型的映射稱為編碼n適應(yīng)度：各個(gè)個(gè)體對(duì)各自適應(yīng)環(huán)境的程度稱為適應(yīng)度。n選擇：指決定以一定的概率從群體中選擇若干對(duì)個(gè)體的操作稱為選擇。n交叉：把兩個(gè)染色體換組的操作稱為交叉，又稱重組。n變異：讓遺傳因子以一定的概率變化的操作稱為變異n解碼：從遺傳子型到表現(xiàn)型的映射稱為解碼2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院66.2 基本遺傳算法2、基本原理與流程 2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院76.2 基本遺傳算法YN簡(jiǎn)單遺傳算法基本流程圖 2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院83、遺傳算法的基本操作n設(shè)有函數(shù) ,用遺傳算法求其自變量x在區(qū)間0，31

5、取整數(shù)時(shí)最大值2( )f xx6.2 基本遺傳算法2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院9（1）初始種群6.2 基本遺傳算法2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院10（2）復(fù)制 根據(jù)目標(biāo)函數(shù)適應(yīng)度的計(jì)算，從初始種群中挑選適應(yīng)度高的個(gè)體進(jìn)行復(fù)制。通常可把目標(biāo)函數(shù)制定成獲得的利益、利潤(rùn)、功效等指標(biāo)的量度函數(shù)。這里，可把目標(biāo)函數(shù)值確定為適應(yīng)值。 適應(yīng)值相當(dāng)于自然界中的一個(gè)生物為了生存所具備的各項(xiàng)能力的大小，決定了該染色體被復(fù)制還是被淘汰。6.2 基本遺傳算法2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院116.2 基本遺傳算法2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院126.2 基本遺傳

6、算法2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院13 根據(jù)上表數(shù)據(jù)，對(duì)應(yīng)輪盤賭轉(zhuǎn)盤的隨機(jī)方法，繪制出輪盤賭轉(zhuǎn)盤。6.2 基本遺傳算法2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院14 旋轉(zhuǎn)4次輪盤，就產(chǎn)生4個(gè)染色體，這4個(gè)染色體是上一代種群中有選擇的復(fù)制，有的可能被復(fù)制一次或多次，有的則可能被淘汰。6.2 基本遺傳算法2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院15（3）交叉 不但復(fù)制出優(yōu)秀的染色體，而且還要?jiǎng)?chuàng)造出新的染色體。交叉操作模擬生物進(jìn)化過(guò)程的繁殖現(xiàn)象，通過(guò)兩個(gè)染色體的交換組合，從而產(chǎn)生新的優(yōu)良品種。 交叉步驟：（1）將復(fù)制產(chǎn)生的染色體隨機(jī)兩兩匹配，稱之為雙親的染色體；（2）將雙親的染色

7、體進(jìn)行交叉繁殖。6.2 基本遺傳算法2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院166.2 基本遺傳算法2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院176.2 基本遺傳算法2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院186.2 基本遺傳算法2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院19（4）變異 以很小的概率隨機(jī)地改變遺傳基因的值，模擬生物在自然環(huán)境中，由于某種偶然因素引起的基因突變。假設(shè)只有復(fù)制和交叉，沒有變異操作，就無(wú)法在初始基因族組以外的空間進(jìn)行搜索，可能使進(jìn)化過(guò)程較早陷入局部解而失去某種特殊的進(jìn)化途徑。 對(duì)于二進(jìn)制編碼表示的染色體數(shù)字符串中，隨機(jī)地將染色體的某一個(gè)基因，即染色體的數(shù)字

8、符串的某一位的數(shù)值由1變成0，或由0變成1。6.2 基本遺傳算法2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院20 變異的概率比較小，通常取千分之一二，但變異操作增加了基因類型的多樣性，使搜索能在盡可能大的空間進(jìn)行，得到更優(yōu)化的解。 假設(shè)變異概率為0.001，則對(duì)于種群總共有20個(gè)基因位，期望的變異串位數(shù)為20X0.001=0.02位，所以這里沒有基因位數(shù)值的改變。6.2 基本遺傳算法2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院216.2 基本遺傳算法二、遺傳算法的設(shè)計(jì)與實(shí)現(xiàn) 1、編碼 利用遺傳算法進(jìn)行問(wèn)題求解時(shí),首先確定問(wèn)題的目標(biāo)函數(shù)和變量,然后對(duì)其進(jìn)行編碼。這樣做主要是因?yàn)樵谶z傳算法中,問(wèn)題

9、的解是用數(shù)字串來(lái)表示的，而遺傳操作算子也是直接對(duì)串進(jìn)行操作的。編碼方式常用的有二進(jìn)制編碼和浮點(diǎn)數(shù)編碼 。2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院226.2 基本遺傳算法2、適應(yīng)度函數(shù) 在生物的遺傳和進(jìn)化過(guò)程中，對(duì)生物環(huán)境適應(yīng)程度較高的物種將有更多的繁殖機(jī)會(huì)。遺傳算法中也使用這個(gè)概念來(lái)度量群體中各個(gè)個(gè)體在優(yōu)化計(jì)算中有可能達(dá)到或有助于找到最佳解的尋優(yōu)過(guò)程。適應(yīng)度較高的個(gè)體遺傳到下一代的概率就較大，而適應(yīng)度較低的個(gè)體遺傳到下一代的概率就相對(duì)小一些。度量個(gè)體適應(yīng)度的函數(shù)稱為適應(yīng)度函數(shù)（Fitness Function）。 2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院236.2 基本遺傳算法適應(yīng)度函

10、數(shù)設(shè)計(jì)方法（1）目標(biāo)函數(shù)映射成適應(yīng)度函數(shù)2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院246.2 基本遺傳算法（2）適應(yīng)度函數(shù)調(diào)整 應(yīng)用遺傳算法時(shí)(尤其用它處理小規(guī)模群體時(shí))常常會(huì)出現(xiàn)一些不利于優(yōu)化的現(xiàn)象或結(jié)果。在進(jìn)化的初期，通常會(huì)出現(xiàn)一些異常的個(gè)體，若按照輪盤選擇策略，這些異常個(gè)體有可能在群體中占據(jù)很大的比例，這是我們所不期望出現(xiàn)的現(xiàn)象。因?yàn)檫@樣可能導(dǎo)致未成熟收斂現(xiàn)象。這些異常個(gè)體競(jìng)爭(zhēng)力太突出，它們會(huì)控制選擇過(guò)程，影響算法的全局優(yōu)化性能。調(diào)整方式主要有:2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院256.2 基本遺傳算法1)線性調(diào)整 2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院266.2 基本

11、遺傳算法2)冪調(diào)整2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院276.2 基本遺傳算法3. 遺傳算子(1) 選擇運(yùn)算(selection) 選擇是從群體中挑選優(yōu)良個(gè)體并淘汰劣質(zhì)個(gè)體的操作過(guò)程。它建立在適應(yīng)度評(píng)估的基礎(chǔ)上，個(gè)體適應(yīng)度越大，被選中的可能性就越大，它的子代保留到配對(duì)庫(kù)(mating pool)中的個(gè)數(shù)就越多。常用選擇方法:輪盤賭方法 、 排序選擇法 、最佳個(gè)體保存法 。 2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院286.2 基本遺傳算法輪盤賭方法 (roulette wheel model) 2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院296.2 基本遺傳算法2022-5-1上海工

12、程技術(shù)大學(xué)機(jī)械工程學(xué)院306.2 基本遺傳算法(2) 交叉運(yùn)算(crossover) 在遺傳操作中的，交叉操作因其全局搜索能力而成為主要算子，其作用在于它不僅使原種群中優(yōu)良個(gè)體的特性能夠在一定程度上保持，而且其探索新的基因空間的能力使得種群中的個(gè)體具有多樣性。它是GA獲取新優(yōu)良個(gè)體的最重要手段。交叉是指把兩個(gè)父串個(gè)體的部分結(jié)構(gòu)加以替換重組而生成新個(gè)體的操作。交叉運(yùn)算分為兩類，一類為二進(jìn)制交叉，另一類為浮點(diǎn)數(shù)交叉。 2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院316.2 基本遺傳算法（a）二進(jìn)制交叉運(yùn)算 交叉操作是按一定概率Pc在配對(duì)庫(kù)中隨機(jī)地選取兩個(gè)個(gè)體進(jìn)行的。交叉的位置也是隨機(jī)確定的。其二進(jìn)

13、制編碼操作又可分為單點(diǎn)交叉、兩點(diǎn)交叉和多點(diǎn)交叉等。n一點(diǎn)交叉：是在個(gè)體中隨機(jī)地選定一個(gè)交叉點(diǎn)，兩個(gè)個(gè)體在該點(diǎn)前后進(jìn)行部分互換，以產(chǎn)生新的個(gè)體。父輩個(gè)體1 A A A A A A |A A A A A A B B B B B B | A A A A A A父輩個(gè)體2 B B B B B B | B B B B B B A A A A A A | B B B B B Bn兩點(diǎn)交叉：該交叉操作與單點(diǎn)交叉類似，只是隨機(jī)設(shè)置兩個(gè)交叉點(diǎn)進(jìn)行部分互換，以產(chǎn)生新的個(gè)體。父輩個(gè)體1 A A A A | A A A A |A A A A A A A A | B B B B | A A A A父輩個(gè)體2 B B B

14、 B | B B B B | B B B B B B B B | A A A A | B B B B n多點(diǎn)交叉：該交叉操作即前述兩中交叉方法的推廣，多點(diǎn)交叉有時(shí)又被叫做廣義交叉。若用參數(shù)c表示交叉數(shù)，則當(dāng)c1或c2時(shí)即為單點(diǎn)交叉和兩點(diǎn)交叉。 2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院326.2 基本遺傳算法（b）浮點(diǎn)數(shù)編碼的交叉運(yùn)算2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院336.2 基本遺傳算法(3) 變異運(yùn)算(mutation) 遺傳算法中使用變異算子使得遺傳算法具有局部的隨機(jī)搜索能力,能找到更精確的值.并配合交叉操作以維持種群的多樣性，防止出現(xiàn)過(guò)早收斂。兩類變異運(yùn)算：二進(jìn)制變異運(yùn)算

15、，浮點(diǎn)數(shù)的變異運(yùn)算。（a）二進(jìn)制變異運(yùn)算 以很小的概率Pm隨機(jī)地改變?nèi)后w中染色體某些基因的值。變異操作的基本過(guò)程是，變異算子隨機(jī)地將某個(gè)基因值取反，即“0”變成“1”或“1”變?yōu)椤?”。 01000101000101011010 01010101000101001010 2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院346.2 基本遺傳算法（b）浮點(diǎn)數(shù)變異運(yùn)算2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院356.2 基本遺傳算法三、遺傳算法運(yùn)行參數(shù)的選擇 1、種群規(guī)模 種群規(guī)模過(guò)小，容易使算法陷入局部最優(yōu)解；種群規(guī)模過(guò)大，增加了算法的計(jì)算量，從而減緩了算法的進(jìn)化速度。一般來(lái)說(shuō)對(duì)種群的大小是針對(duì)一個(gè)

16、具體的問(wèn)題而言的，種群的規(guī)模與以下影響因素有關(guān)：(1) 問(wèn)題的內(nèi)在規(guī)律。如果在問(wèn)題空間內(nèi)目標(biāo)函數(shù)的極值點(diǎn)越多，所要求的種群規(guī)模越大；如果問(wèn)題空間內(nèi)目標(biāo)函數(shù)的變化越平滑，所要求的種群規(guī)模越小。(2) 問(wèn)題空間的范圍。問(wèn)題空問(wèn)的取值范圍越大，要求的種群規(guī)模也越大。(3) 交叉率、變異率的選擇。交叉率和變異率較大時(shí)，要求的種群規(guī)模較小；反之，較大。 2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院366.2 基本遺傳算法2、交叉率 交叉率是最主要的遺傳運(yùn)算，遺傳算法的性能在很大程度上取決于所采用的交叉算子的性能和交叉率的大小。交叉率是指各代中交叉產(chǎn)生的后代數(shù)與種群規(guī)模之比。交叉運(yùn)算產(chǎn)生新個(gè)體，不斷拓展搜

17、索空間，較高的交叉率可以搜索更大的解空間，從而降低停在非優(yōu)解的機(jī)會(huì)；但是交叉率太高，會(huì)因搜索不必要的解空間而耗費(fèi)大量的計(jì)算時(shí)間。常用的交叉率的取值范圍為0.40.6。2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院376.2 基本遺傳算法3、 變異率 變異率也是遺傳操作中的重要參數(shù)，它直接影響到算法的收斂性和最終解的性能。變異率是指種群中變異的基因數(shù)占總基因數(shù)的百分比。變異率控制了新基因引入的比例。在實(shí)際操作的過(guò)程中，算法常用變異率的數(shù)量級(jí)范圍為0.10.001?；蛘咴谶M(jìn)化初期選擇一個(gè)較大的值，而在進(jìn)化后期變異概率隨之減小。 2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院386.2 基本遺傳算法4.

18、 進(jìn)化終止條件 化計(jì)算的終止可以從兩方面進(jìn)行控制：預(yù)先設(shè)定進(jìn)化代數(shù)或者以種群的進(jìn)化程度進(jìn)行控制。種群的進(jìn)化程度是指種群的當(dāng)前代最大適應(yīng)值與種群的平均適應(yīng)值的比例關(guān)系。 2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院396.2 基本遺傳算法四、函數(shù)尋優(yōu)實(shí)例 2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院406.2 基本遺傳算法1、染色體編碼2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院416.2 基本遺傳算法2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院426.2 基本遺傳算法2、適應(yīng)度計(jì)算2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院436.2 基本遺傳算法3、染色體的選擇 2022-5-1上海工程技術(shù)

19、大學(xué)機(jī)械工程學(xué)院446.2 基本遺傳算法2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院456.2 基本遺傳算法2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院466.2 基本遺傳算法4、交叉運(yùn)算 2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院476.2 基本遺傳算法2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院486.2 基本遺傳算法5、變異運(yùn)算 2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院496.2 基本遺傳算法2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院506.2 基本遺傳算法6、循環(huán) 2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院516.3遺傳算法的數(shù)學(xué)基礎(chǔ) 一、模式定理 1、模式的定義 由編碼串的

20、結(jié)構(gòu)形式變化表明，模式是一個(gè)字符串集在某些位置上的相似性。對(duì)于二進(jìn)制編碼方式，個(gè)體是由二值編碼串集0,1所組成，由此產(chǎn)生了常見的0,1編碼串，再加入一個(gè)通配符“*”，其含義即可表示為0也可表示為1。這樣就將二值字符串?dāng)U展成了三值字符串0,1,*，由此可以產(chǎn)生00110、01*11、*01*等編碼串。n模式 ：描述基因串集中相似類基因串的模板，該類基因串中某些特征位結(jié)構(gòu)相同，稱為“模式”。 通俗地講，基于三值字符集0,1,*所產(chǎn)生的一類能夠描述在某些位置上具有結(jié)構(gòu)相似性的0，1編碼串集的編碼，稱為模式。2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院526.3遺傳算法的數(shù)學(xué)基礎(chǔ)n模式階(schema

21、 order)：模式H中確定位置的個(gè)數(shù),稱為該模式的階，記作O(H)。 例如，在二進(jìn)制編碼中，一個(gè)模式的階就是所有0和1的數(shù)目。模式H=*1*0*的階數(shù)為2，記為O(H)2；，模式H=1*10*的階數(shù)為3，記為O(H)3；顯然一個(gè)模式的階越高，其樣本數(shù)就越少，其確定性也越高。n定義長(zhǎng)度(Defining Length)：模式H中第一個(gè)確定位和最后一個(gè)確定位置的距離稱作該模式的定義長(zhǎng)度，記作。 例如：模式H=*1*0*的定義長(zhǎng)度為2，記為(H)=2，這是因?yàn)榈谝粋€(gè)確定位置為3，最后一個(gè)確定位置為5，他們之間的距離(H)=5-3=2。若模式H=1*僅有一個(gè)確定位置，根據(jù)概念該模式的定義長(zhǎng)度為0。2

22、022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院536.3遺傳算法的數(shù)學(xué)基礎(chǔ)2、選擇對(duì)模式的影響 選擇操作能使模式的數(shù)量以指數(shù)形式增減，但由于選擇操作只能將某些高適應(yīng)度的個(gè)體復(fù)制，低適應(yīng)度的個(gè)體淘汰，它并不能產(chǎn)生新的模式結(jié)構(gòu)，因而選擇操作對(duì)性能的改進(jìn)是有限的。 2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院546.3遺傳算法的數(shù)學(xué)基礎(chǔ)3、交叉對(duì)模式的影響 交叉操作是基因串之間的有組織而又是隨機(jī)的信息交換，它在創(chuàng)造新結(jié)構(gòu)的同時(shí)，應(yīng)盡可能少的破壞復(fù)制過(guò)程所選擇的高適應(yīng)度模式。 在選擇和交叉操作共同作用下，模式數(shù)量的增長(zhǎng)或減少，取決于其模式的平均適應(yīng)度的高低和定義長(zhǎng)度的長(zhǎng)短，平均適應(yīng)度越大，定義長(zhǎng)度越小，則

23、H的數(shù)量就越多。 2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院556.3遺傳算法的數(shù)學(xué)基礎(chǔ)4、變異對(duì)模式的影響 2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院566.3遺傳算法的數(shù)學(xué)基礎(chǔ)5、模式定理 在遺傳算子選擇、交叉和變異的作用下，具有低階、短定義長(zhǎng)度以及平均適應(yīng)度高于群體平均適應(yīng)度的模式，將在子代中呈指數(shù)級(jí)地增長(zhǎng)。 模式定理是遺傳算法的理論基礎(chǔ)，適用于二進(jìn)制編碼，對(duì)其他編碼方式未必成立。 2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院576.3遺傳算法的數(shù)學(xué)基礎(chǔ)二、積木塊假設(shè) 由模式定理可知，具有低階、短定義長(zhǎng)度以及平均適應(yīng)度高于群體平均適應(yīng)度的模式，在子代中將呈指數(shù)級(jí)增長(zhǎng)。這類模式在遺傳算

24、法中非常重要，稱之為積木塊(Building Block)。 積木塊假設(shè)(Building Block Hypothesis)：低階、短定義長(zhǎng)度、高平均適應(yīng)度的模式在遺傳算子作用下，相互結(jié)合，能生成高階、長(zhǎng)定義長(zhǎng)度、高平均適應(yīng)度的模式，可最終生成全局最優(yōu)解。 2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院586.4 遺傳算法的改進(jìn)一、早熟現(xiàn)象 在遺傳算法進(jìn)化的過(guò)程中，在某些時(shí)候會(huì)出現(xiàn)以下情況:(1）當(dāng)群體中出現(xiàn)個(gè)別或極少數(shù)適應(yīng)度值相當(dāng)高的個(gè)體時(shí),由于選擇機(jī)制就有可能導(dǎo)致這些個(gè)體在群體中迅速繁殖，經(jīng)過(guò)少數(shù)幾次迭代后就占滿了群體的位置, 這樣GA的求解過(guò)程就結(jié)束了，但這樣很有可能是收斂到局部最優(yōu)解，

25、即遺傳算法的不成熟收斂；（2）當(dāng)群體中個(gè)體適應(yīng)度彼此非常接近時(shí)，便失去了種群的多樣性，這些個(gè)體進(jìn)行交配的機(jī)會(huì)相等，而且交叉后得到的新個(gè)體也不會(huì)有多大變化，這樣搜索過(guò)程也不能有效地進(jìn)行，從而使進(jìn)化過(guò)程陷于停頓的狀態(tài),。這兩種情況統(tǒng)稱“早熟”現(xiàn)象。2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院596.4 遺傳算法的改進(jìn)二、自適應(yīng)遺傳算法 自適應(yīng)遺傳算法是指?jìng)€(gè)體的交叉和變異率由個(gè)體在當(dāng)前種群中的優(yōu)良程度來(lái)自適應(yīng)決定，并隨遺傳代數(shù)的變化而變化。動(dòng)態(tài)自適應(yīng)技術(shù)在進(jìn)化過(guò)程中通過(guò)調(diào)整遺傳控制參數(shù)可以克服早熟現(xiàn)象，在進(jìn)化早期，群體中個(gè)體的差異較大，所以選擇操作和交叉操作的作用比較明顯，進(jìn)化速度也較快；但在進(jìn)化的

26、后期，由于選擇問(wèn)題和固定交叉、變異的問(wèn)題使得種群中個(gè)體的近親繁殖而造成的種群失去了多樣性，其適應(yīng)度值也比較接近，產(chǎn)生早熟現(xiàn)象。 2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院606.4 遺傳算法的改進(jìn)1指數(shù)形式實(shí)現(xiàn)交叉和變異 指數(shù)形式的交叉和變異是指在進(jìn)化過(guò)程中，交叉率和變異率隨指數(shù)形式變化。 交叉率對(duì)遺傳代數(shù)影響較大，這是因?yàn)樵诘跗冢粨Q率選擇得大一些可以造成足夠的擾動(dòng)，從而增強(qiáng)遺傳算法的搜索能力，而在迭代后期，交換率選得小一些可以避免破壞優(yōu)良基因，從而加快收斂速度?？紤]到交換率隨遺傳代數(shù)變化下降的關(guān)系，可將算式可表示為 2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院616.4 遺傳算法的改

27、進(jìn)2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院626.4 遺傳算法的改進(jìn)2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院636.4 遺傳算法的改進(jìn)2平均適應(yīng)度形式實(shí)現(xiàn)交叉和變異 以平均適應(yīng)度形式的交叉和變異是指在進(jìn)化過(guò)程中，交叉率和變異率隨該帶的平均適應(yīng)度變化而變化。 平均適應(yīng)度在一定意義上反映整個(gè)種群的變化趨勢(shì)，因此可以平均適應(yīng)度形式判定種群中的交叉和變異率，即系統(tǒng)自適應(yīng)產(chǎn)生的交叉和變異率必須同這一代的平均適應(yīng)度相關(guān)聯(lián)，如下式所示2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院646.4 遺傳算法的改進(jìn)2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院656.4 遺傳算法的改進(jìn)2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院666.4 遺傳算法的改進(jìn)2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院676.4 遺傳算法的改進(jìn)三、小生境技術(shù) 在遺傳進(jìn)化過(guò)程中，尤其是對(duì)于一些多峰值函數(shù)的優(yōu)化計(jì)算時(shí)，在尋優(yōu)過(guò)程中往往都會(huì)找一些局部最優(yōu)解并徘徊其中，很難跳出。使得進(jìn)化后期大量個(gè)體收斂于該局部?jī)?yōu)化解從而陷入早熟的現(xiàn)象。為此，小生境技術(shù)的引入也是為了實(shí)現(xiàn)尋優(yōu)過(guò)程的全局最優(yōu)。幾種小生境策略： 2022-5-1上海工程技術(shù)大學(xué)機(jī)械工程學(xué)院