遺傳算法的編碼與適應(yīng)度函數(shù)課件

遺傳算法的編碼與適應(yīng)度函數(shù)姓名：趙文娟學(xué)號(hào)：30808120304遺傳算法的編碼與適應(yīng)度函數(shù)姓名：趙文娟1遺傳算法的特點(diǎn)：（1）遺傳算法不是直接作用在參變量集上，而是利用參變量集的某種編碼；（2）遺傳算法不是從單個(gè)點(diǎn)，而是從一個(gè)點(diǎn)的群體開(kāi)始搜索；（3）遺傳算法利用適應(yīng)值信息，無(wú)需導(dǎo)數(shù)或其它輔助信息；（4）遺傳算法利用概率轉(zhuǎn)移規(guī)則，而非確定性規(guī)則。遺傳算法的特點(diǎn)：（1）遺傳算法不是直接作用在參變量集上，而是2遺傳算法的編碼和適應(yīng)度函數(shù)的重要性遺傳編碼是整個(gè)遺傳算法執(zhí)行的基礎(chǔ)遺傳算法的適應(yīng)度函數(shù)(FitnessFunction)的選取直接影響到遺傳算法的收斂速度以及能否找到最優(yōu)解,因?yàn)檫z傳算法在進(jìn)化搜索中基本不利用外部信息,僅以適應(yīng)度函數(shù)為依據(jù),利用種群每個(gè)個(gè)體的適應(yīng)度來(lái)進(jìn)行搜索。

遺傳算法的編碼和適應(yīng)度函數(shù)的重要性遺傳編碼是整個(gè)遺傳算法執(zhí)行3遺傳算法的基本定理模式就是一個(gè)相同的構(gòu)形，它描述的是一個(gè)串的子集，這個(gè)集合中的串之間在某些位上是相同的。一個(gè)模式H的階就是出現(xiàn)在模式中確定位置的數(shù)目，記為o（H）。一個(gè)模式的定義長(zhǎng)度是模式中第一個(gè)確定位置和最后一個(gè)確定位置之間的距離，記為（H)。遺傳算法的基本定理模式就是一個(gè)相同的構(gòu)形，它描述的是一個(gè)串的4模式的概念說(shuō)明

V+={0，1，*}—模式，*代表不確定字母.串長(zhǎng)為L(zhǎng)的二進(jìn)制串上的模式共有3l個(gè).一般的，對(duì)于基數(shù)為k的字母表，共有(k+1)l個(gè)模式例如：串長(zhǎng)為7的模式H=*11*0**，A=0111000是模式H的一個(gè)表示。

所有模式并不是以同等機(jī)會(huì)產(chǎn)生的，有些模式比起其它的更加確定，例如：與0******相比，模式011*1**在相似性方面是更明確的表示。模式的概念說(shuō)明V+={0，1，*}—模式，*代表不確5一個(gè)模式H的階——出現(xiàn)在模式中確定位置的數(shù)目。例如：模式011*1**的階為4可記為，o（011*1**）=4；模式0******的階為1。一個(gè)模式的定義長(zhǎng)度——模式中第一個(gè)確定位置和最后一個(gè)確定位置之間的距離。例如：模式011*1**的定義長(zhǎng)度為4，可記為=4；0******的定義長(zhǎng)度為=0。

注：串的階和定義長(zhǎng)度是用于討論串的相似性的符號(hào)。

一個(gè)模式H的階——出現(xiàn)在模式中確定位置的數(shù)目。6在復(fù)制階段，每個(gè)串根據(jù)它的適應(yīng)度值進(jìn)行復(fù)制，更確切的說(shuō)，一個(gè)串Ai的復(fù)制概率為：

m（H，t+1）=m（H，t）·n·f(H)/

其中f(H)是在第t代中模式H的串的平均適應(yīng)值。整個(gè)群體的平均適應(yīng)值可記為/n故模式的復(fù)制生長(zhǎng)方程可以表示為:m（H，t+1）=m（H，t）·/

一個(gè)特定的模式按照其平均適應(yīng)值與群體的平均適應(yīng)值之間的比率生長(zhǎng)

在復(fù)制階段，每個(gè)串根據(jù)它的適應(yīng)度值進(jìn)行復(fù)制，更確切的說(shuō)，一個(gè)7遺傳算法的編碼與適應(yīng)度函數(shù)課件8下面推出一個(gè)定量表達(dá)式，假設(shè)某一特定模式下的適應(yīng)值高出群體平均適應(yīng)值以上一個(gè)c，c為一常數(shù)，則模式的復(fù)制生長(zhǎng)方程可變?yōu)椋簃（H，t+1）=m（H，t）=（1+c）·m（H，t）從t=0開(kāi)始，假設(shè)c是一個(gè)固定值，可以推得：m（H，t）=m（H，0）·（1+c）t上式表明，在群體平均適應(yīng)度以上（以下）的模式將會(huì)以指數(shù)增長(zhǎng)（衰減）的方式被復(fù)制。下面推出一個(gè)定量表達(dá)式，假設(shè)某一特定模式下的適應(yīng)值高出群體平9模式定理模式的階和定義長(zhǎng)度兩個(gè)概念提供了一個(gè)分析遺傳算法中遺傳算子對(duì)包含在群體中基因塊的作用效果的基本的方法。m=m（H，t），第t代中模式H有m個(gè)代表串包含在群體中A（t）中的樣本。t不同，m也不同。模式定理：遺傳算法中，在選擇、交叉、編譯算子的作用下，具有低階、短的定義長(zhǎng)度，且平均適應(yīng)度高于群體平均適應(yīng)度的模式將按指數(shù)級(jí)增長(zhǎng)。模式定理模式的階和定義長(zhǎng)度兩個(gè)概念提供了一個(gè)分析遺傳算法中遺10遺傳算法的編碼原則編碼原則一（有意義積木塊編碼原則）：應(yīng)使用能易于產(chǎn)生與所求問(wèn)題相關(guān)的且具有低階、短定義長(zhǎng)度模式的編碼方案。編碼原則二(最小字符集編碼原則)：應(yīng)使用能使問(wèn)題得到自然表示或描述的最小編碼字符集的編碼方案遺傳算法的編碼原則編碼原則一（有意義積木塊編碼原則）：應(yīng)使用11常用的編碼方法二進(jìn)制編碼格雷編碼浮點(diǎn)數(shù)編碼符號(hào)編碼混合編碼常用的編碼方法二進(jìn)制編碼12二進(jìn)制編碼簡(jiǎn)單易行符合最小字符集編碼規(guī)則便于用模式定理進(jìn)行分析,因?yàn)槟Ｊ蕉ɡ砭褪且远M(jìn)制編碼為基礎(chǔ)提出的。二進(jìn)制編碼簡(jiǎn)單易行13格雷編碼格雷編碼有這樣一個(gè)特點(diǎn)：任意兩個(gè)整數(shù)的差是這兩個(gè)整數(shù)所對(duì)應(yīng)的格雷碼之間的漢明距離。這個(gè)特點(diǎn)是遺傳算法使用格雷來(lái)進(jìn)行個(gè)體編碼的主要原因。由二進(jìn)制碼到格雷碼的轉(zhuǎn)換公式為：由格雷碼到二進(jìn)制碼的轉(zhuǎn)換公式為：

格雷編碼格雷編碼有這樣一個(gè)特點(diǎn)：任意兩個(gè)整數(shù)的差是這兩個(gè)整數(shù)14浮點(diǎn)數(shù)編碼首先，二進(jìn)制編碼存在著連續(xù)函數(shù)離散化時(shí)的映射誤差。個(gè)體編碼長(zhǎng)度較短時(shí)達(dá)不到精度要求；個(gè)體編碼較長(zhǎng)時(shí)會(huì)使搜索空間急劇擴(kuò)大。另外，二進(jìn)制編碼不便于反映所求問(wèn)題的特定知識(shí)，這樣就不便于開(kāi)發(fā)針對(duì)專門(mén)知識(shí)的遺傳算子。浮點(diǎn)數(shù)編碼首先，二進(jìn)制編碼存在著連續(xù)函數(shù)離散化時(shí)的映射誤差。15浮點(diǎn)數(shù)編碼的優(yōu)點(diǎn)主要有：（1）適合用在遺傳算法中表示范圍較大的數(shù)；（2）適合于精度要求較高的遺傳算法；（3）便于較大空間的遺傳搜索；（4）改善了遺傳算法的計(jì)算復(fù)雜性，提高了運(yùn)算效率。浮點(diǎn)數(shù)編碼的優(yōu)點(diǎn)主要有：16符號(hào)編碼符號(hào)編碼是指?jìng)€(gè)體染色體編碼串中的基因值取自一個(gè)無(wú)數(shù)值含義、而只有代碼含義的符號(hào)集。這個(gè)符號(hào)集是一個(gè)字母表，如：{A,B,C,D,…};也可以是一個(gè)數(shù)字序號(hào)表，如{1，2，3，…};也可以是一個(gè)代碼表，如：{A1,A2,A3,…}等等。優(yōu)點(diǎn)：（1）符合有意義積木塊編碼原則；（2）便于在遺傳算法中利用所求解問(wèn)題的專門(mén)知識(shí)；（3）便于遺傳算法于相關(guān)近似算法之間的混合使用。符號(hào)編碼符號(hào)編碼是指?jìng)€(gè)體染色體編碼串中的基因值取自一個(gè)無(wú)數(shù)值17多參數(shù)交叉編碼假設(shè)有n個(gè)參數(shù)，每個(gè)參數(shù)都采用碼長(zhǎng)m的二進(jìn)制編碼，取各參數(shù)編碼串中的最高位聯(lián)在一起，作為個(gè)體編碼的前n位編碼、再取次高位聯(lián)在一起作為個(gè)體第二組n位編碼，….,再取最后一位聯(lián)在一起作為編碼的最后n位。這種編碼方式中，各個(gè)參數(shù)的局部編碼結(jié)構(gòu)就不易被遺傳算子破壞掉，它適合于各參數(shù)之間的相互關(guān)系較弱，特別是某一各或少數(shù)幾個(gè)參數(shù)其主要作用時(shí)的優(yōu)化問(wèn)題。

多參數(shù)交叉編碼假設(shè)有n個(gè)參數(shù)，每個(gè)參數(shù)都采用碼長(zhǎng)m的二進(jìn)制編18適應(yīng)度函數(shù)傳算法中使用適應(yīng)度這個(gè)概念來(lái)度量群體中各個(gè)個(gè)體在優(yōu)化計(jì)算中有可能達(dá)到或接近于或有助于找到最有解的優(yōu)良程度。適應(yīng)度高的個(gè)體遺傳到下一代的可能性比較大，而適應(yīng)度比較低的個(gè)體遺傳到下一代的概率相對(duì)小一些。度量個(gè)體適應(yīng)度的函數(shù)稱為適應(yīng)度函數(shù)。適應(yīng)度函數(shù)傳算法中使用適應(yīng)度這個(gè)概念來(lái)度量群體中各個(gè)個(gè)體在優(yōu)19目標(biāo)函數(shù)與適應(yīng)度函數(shù)遺傳算法的一個(gè)特點(diǎn)就是它僅使用所求問(wèn)題的目標(biāo)函數(shù)值就可得到下一步的有關(guān)搜索信息。而對(duì)目標(biāo)函數(shù)值的使用是通過(guò)評(píng)價(jià)個(gè)體的適應(yīng)度來(lái)體現(xiàn)的。評(píng)價(jià)個(gè)體適應(yīng)度的過(guò)程一般是：（1）對(duì)個(gè)體編碼串進(jìn)行解碼處理后，可得到個(gè)體的表現(xiàn)型；（2）有個(gè)體表現(xiàn)型可計(jì)算出對(duì)應(yīng)個(gè)體的目標(biāo)函數(shù)值；（3）根據(jù)最優(yōu)化問(wèn)題的類型，有目標(biāo)函數(shù)值按一定轉(zhuǎn)換規(guī)則求出個(gè)體的適應(yīng)度。目標(biāo)函數(shù)與適應(yīng)度函數(shù)遺傳算法的一個(gè)特點(diǎn)就是它僅使用所求問(wèn)題的20最優(yōu)化問(wèn)題最優(yōu)化問(wèn)題可以分為兩大類，一類為求目標(biāo)函數(shù)的全局最大值，另一類為求目標(biāo)函數(shù)的全局最小值。對(duì)于目標(biāo)函數(shù)最小值的優(yōu)化問(wèn)題可轉(zhuǎn)化為：minf(X)=max(-f(X))當(dāng)優(yōu)化目標(biāo)是函數(shù)的最大值，并且目標(biāo)函數(shù)總?cè)≌龝r(shí)，可以直接設(shè)定個(gè)體適應(yīng)度F（x）為：F（x）=f（x）最優(yōu)化問(wèn)題最優(yōu)化問(wèn)題可以分為兩大類，一類為求目標(biāo)函數(shù)的全局最21遺傳算法的編碼與適應(yīng)度函數(shù)課件22注：Cmax和Cmin最好與種群無(wú)關(guān)注：Cmax和Cmin最好與種群無(wú)關(guān)23遺傳算法的編碼與適應(yīng)度函數(shù)課件24我們希望在遺傳算法運(yùn)行的初期，算法能對(duì)一些適應(yīng)度較高的個(gè)體進(jìn)行控制，降低其適應(yīng)度與其他個(gè)體適應(yīng)度之間的差異程度，從而限制復(fù)制數(shù)量，以維護(hù)群體的多樣性。在遺傳運(yùn)算后期，算法能對(duì)個(gè)體適應(yīng)度進(jìn)行適當(dāng)放大，擴(kuò)大最佳個(gè)體適應(yīng)度與其它適應(yīng)度之間的差異程度，以提高個(gè)體之間的競(jìng)爭(zhēng)性。目前常用的個(gè)體適應(yīng)度尺度變換方法主要有三種：線性尺度變換、乘冪尺度變換、指數(shù)尺度變換。我們希望在遺傳算法運(yùn)行的初期，算法能對(duì)一些適應(yīng)度較高的個(gè)體進(jìn)25線性尺度變換F’=aF+b，F(xiàn)為原適應(yīng)度；F’為變換后的新適應(yīng)度，a和b位系數(shù)。系數(shù)a和b直接影響到這個(gè)尺度變換的大小，所以對(duì)其選擇有一定的要求，一般要滿足以下條件：F’avg=Favg，這條要求是為了保證群體中適應(yīng)度接近于平均適應(yīng)度的個(gè)體能夠有期待的數(shù)量被遺傳到下一代種群中。F’max=C·Favg，C為最佳個(gè)體的期望復(fù)制數(shù)量。這條要求是為了保證群體中做好的個(gè)體能夠期望復(fù)制C倍到新一代群體中。

線性尺度變換F’=aF+b，F(xiàn)為原適應(yīng)度；F’為變換后的新適26使用線性變換時(shí)，群體中有少數(shù)幾個(gè)優(yōu)良個(gè)體的適應(yīng)度按比例縮小，同時(shí)幾個(gè)較差的個(gè)體適應(yīng)度也按比例擴(kuò)大。在搜索的后期階段，隨著個(gè)體適應(yīng)度從總體上的不斷改進(jìn)，群體中個(gè)體的最大適應(yīng)度和全部個(gè)體的平均適應(yīng)度較接近，而少數(shù)幾個(gè)較差的個(gè)體的適應(yīng)度卻遠(yuǎn)遠(yuǎn)小于最大適應(yīng)度，這時(shí)若想維持F’max和Favg的指定倍數(shù)關(guān)系，將有可能會(huì)使較差的個(gè)體適應(yīng)度變換為負(fù)值。解決上述問(wèn)題的方法是：把原最小適應(yīng)度Fmin映射為F’min=0，并且保持原平均適應(yīng)度Favg與新的平均適應(yīng)度F’avg相等。使用線性變換時(shí)，群體中有少數(shù)幾個(gè)優(yōu)良個(gè)體的適應(yīng)度按比例縮小，27乘冪尺度變換F’=Fk新的適應(yīng)度是原有適應(yīng)度的某個(gè)指定乘冪。冪指數(shù)k與所求解的問(wèn)題有關(guān)，并且在算法的執(zhí)行過(guò)程中需要不斷對(duì)其進(jìn)行修正才能使尺度變換滿足一定的伸縮要求。機(jī)器視覺(jué)中k的最佳取值為1.005。

乘冪尺度變換F’=Fk新的適應(yīng)度是原有適應(yīng)度的某個(gè)指定乘冪。28指數(shù)尺度變換F’=exp（-F）新的適應(yīng)度使原有適應(yīng)度的某個(gè)指數(shù)。式中系數(shù)決定了選擇的強(qiáng)制性，越小，原有的是適應(yīng)度較高的個(gè)體的新適應(yīng)度就越與其它個(gè)體的新適應(yīng)度相差較大，亦即越增加了選擇該個(gè)體的強(qiáng)制性。指數(shù)尺度變換F’=exp（-F）29遺傳算法的編碼與適應(yīng)度函數(shù)課件30適應(yīng)度函數(shù)的設(shè)計(jì)

(1)單值、連續(xù)、非負(fù)、最大化適應(yīng)度函數(shù)F(X)應(yīng)該是實(shí)函數(shù),并且單值、連續(xù),但不要求可導(dǎo)。不過(guò),F(X)的曲線在重要部位,特別在最優(yōu)解附近一般不宜太陡也不宜過(guò)于平緩。適應(yīng)度函數(shù)的設(shè)計(jì)(1)單值、連續(xù)、非負(fù)、最大化31(2)計(jì)算量小F(X)不應(yīng)設(shè)計(jì)得過(guò)于繁復(fù),應(yīng)在上述條件下越簡(jiǎn)單越好。適應(yīng)度函數(shù)的設(shè)計(jì)

(2)計(jì)算量小適應(yīng)度函數(shù)的設(shè)計(jì)32(3)通用性一個(gè)適應(yīng)度函數(shù)的好壞,還應(yīng)滿足盡可能廣泛的通用性,使用戶在求解種種問(wèn)題時(shí),最好無(wú)需改變適應(yīng)度函數(shù)中的參數(shù)。它能使用戶在對(duì)所求解函數(shù)的全局最優(yōu)解的性質(zhì)完全“無(wú)知”的情況下,由算法在運(yùn)行過(guò)程中自動(dòng)修正其中的參數(shù)值,從而一步一步接近最優(yōu)解。從另一種意義上說(shuō),這樣的適應(yīng)度函數(shù)具有自適應(yīng)性。適應(yīng)度函數(shù)的設(shè)計(jì)

(3)通用性適應(yīng)度函數(shù)的設(shè)計(jì)33理想情況下:b的值是minf(x)=y*,當(dāng)適應(yīng)度值為0.5時(shí),α是f(x)到minf(x)的距離?？紤]到適應(yīng)度函數(shù)的不同應(yīng)用場(chǎng)合,將β值取為2,將α值分別取為1,1.5,0.5.即可在b,a取定的情況下得到3種適應(yīng)度函數(shù)。理想情況下:b的值是minf(x)=y*,當(dāng)適應(yīng)度值為034當(dāng)取α=1時(shí),適應(yīng)度值在[0.5～1]之間是線性的;對(duì)于在全局最優(yōu)解y*附近變化比較緩慢的函數(shù),用α=0.5可以使適應(yīng)度函數(shù)較靈敏地反映出y值的變化情況.在算法的后期,則可以有效地拉開(kāi)最優(yōu)解附近點(diǎn)的適應(yīng)度值,便于做出敏感選擇,從而有利于以后的選擇;當(dāng)α=1.5時(shí)的適應(yīng)度函數(shù)則有相反的適應(yīng)情況.本文建議公式里的b和a隨遺傳算法的下一代進(jìn)化而不斷地修正.當(dāng)取α=1時(shí),適應(yīng)度值在[0.5～1]之間是線性的;35b