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

1、遺傳算法的編碼與適應(yīng)度函數(shù),姓名：趙文娟學(xué)號(hào)：30808120304,遺傳算法的特點(diǎn)：,（1）遺傳算法不是直接作用在參變量集上，而是利用參變量集的某種編碼；（2）遺傳算法不是從單個(gè)點(diǎn)，而是從一個(gè)點(diǎn)的群體開(kāi)始搜索；（3）遺傳算法利用適應(yīng)值信息，無(wú)需導(dǎo)數(shù)或其它輔助信息；（4）遺傳算法利用概率轉(zhuǎn)移規(guī)則，而非確定性規(guī)則。,遺傳算法的編碼和適應(yīng)度函數(shù)的重要性,遺傳編碼是整個(gè)遺傳算法執(zhí)行的基礎(chǔ)遺傳算法的適應(yīng)度函數(shù) (Fitness Fun

2、ction)的選取直接影響到遺傳算法的收斂速度以及能否找到最優(yōu)解,因?yàn)檫z傳算法在進(jìn)化搜索中基本不利用外部信息,僅以適應(yīng)度函數(shù)為依據(jù),利用種群每個(gè)個(gè)體的適應(yīng)度來(lái)進(jìn)行搜索。,遺傳算法的基本定理,模式就是一個(gè)相同的構(gòu)形，它描述的是一個(gè)串的子集，這個(gè)集合中的串之間在某些位上是相同的。 一個(gè)模式H的階就是出現(xiàn)在模式中確定位置的數(shù)目，記為o（H） 。一個(gè)模式的定義長(zhǎng)度是模式中第一個(gè)確定位置和最后一個(gè)確定位置之間的距離，記為（H)。,模式的概念說(shuō)

3、明,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**在相似性方面是更明確的表示。,一個(gè)模式H的階——出現(xiàn)在模式中確定位置的數(shù)目 。 例如：模

4、式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)。,在復(fù)制階段，每個(gè)串根據(jù)它的適應(yīng)度值進(jìn)行復(fù)制，更確切的說(shuō)，一個(gè)串Ai的復(fù)制概率為： m（H，t+1）= m（H，t）·

5、;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),,,,,,,,下面推出一個(gè)定量表達(dá)式，假設(shè)某一特定模式下的適應(yīng)值高出群體平均適應(yīng)值以上一個(gè)c，c為一常數(shù)，則模式的復(fù)制生長(zhǎng)方程可變?yōu)椋簃（H，t+1）= m（

6、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ù)制。,模式定理,模式的階和定義長(zhǎng)度兩個(gè)概念提供了一個(gè)分析遺傳算法中遺傳算子對(duì)包含在群體中基因塊的作用效果的基本的方法。m=m（H，t），第t代中模式H有m個(gè)代表串包含在群體中A（t）中的樣本。t不同，m

7、也不同。模式定理：遺傳算法中，在選擇、交叉、編譯算子的作用下，具有低階、短的定義長(zhǎng)度，且平均適應(yīng)度高于群體平均適應(yīng)度的模式將按指數(shù)級(jí)增長(zhǎng)。,遺傳算法的編碼原則,編碼原則一（有意義積木塊編碼原則）：應(yīng)使用能易于產(chǎn)生與所求問(wèn)題相關(guān)的且具有低階、短定義長(zhǎng)度模式的編碼方案。編碼原則二(最小字符集編碼原則)：應(yīng)使用能使問(wèn)題得到自然表示或描述的最小編碼字符集的編碼方案,常用的編碼方法,二進(jìn)制編碼格雷編碼浮點(diǎn)數(shù)編碼符號(hào)編碼混合編碼,二進(jìn)制

8、編碼,簡(jiǎn)單易行符合最小字符集編碼規(guī)則便于用模式定理進(jìn)行分析, 因?yàn)槟Ｊ蕉ɡ砭褪且远M(jìn)制編碼為基礎(chǔ)提出的。,格雷編碼,格雷編碼有這樣一個(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)換公式為：,,,,,浮點(diǎn)數(shù)編碼,首先，二進(jìn)制編碼存在著連續(xù)函數(shù)離散化時(shí)的映射誤差。個(gè)體編碼長(zhǎng)度較短時(shí)達(dá)不到精度要求；個(gè)體編碼

9、較長(zhǎng)時(shí)會(huì)使搜索空間急劇擴(kuò)大。另外，二進(jìn)制編碼不便于反映所求問(wèn)題的特定知識(shí)，這樣就不便于開(kāi)發(fā)針對(duì)專(zhuān)門(mén)知識(shí)的遺傳算子。,浮點(diǎn)數(shù)編碼的優(yōu)點(diǎn)主要有：（1）適合用在遺傳算法中表示范圍較大的數(shù)；（2）適合于精度要求較高的遺傳算法；（3）便于較大空間的遺傳搜索；（4）改善了遺傳算法的計(jì)算復(fù)雜性，提高了運(yùn)算效率。,符號(hào)編碼,符號(hào)編碼是指?jìng)€(gè)體染色體編碼串中的基因值取自一個(gè)無(wú)數(shù)值含義、而只有代碼含義的符號(hào)集。這個(gè)符號(hào)集是一個(gè)字母表，如：{A,B,

10、C,D,…};也可以是一個(gè)數(shù)字序號(hào)表，如{1，2，3，…};也可以是一個(gè)代碼表，如：{A1,A2,A3,…}等等。優(yōu)點(diǎn)：（1）符合有意義積木塊編碼原則；（2）便于在遺傳算法中利用所求解問(wèn)題的專(zhuān)門(mén)知識(shí)；（3）便于遺傳算法于相關(guān)近似算法之間的混合使用。,多參數(shù)交叉編碼,假設(shè)有n個(gè)參數(shù)，每個(gè)參數(shù)都采用碼長(zhǎng)m的二進(jìn)制編碼，取各參數(shù)編碼串中的最高位聯(lián)在一起，作為個(gè)體編碼的前n位編碼、再取次高位聯(lián)在一起作為個(gè)體第二組n位編碼，….,再取最后

11、一位聯(lián)在一起作為編碼的最后n位。這種編碼方式中，各個(gè)參數(shù)的局部編碼結(jié)構(gòu)就不易被遺傳算子破壞掉，它適合于各參數(shù)之間的相互關(guān)系較弱，特別是某一各或少數(shù)幾個(gè)參數(shù)其主要作用時(shí)的優(yōu)化問(wèn)題。,適應(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ù)稱(chēng)為適應(yīng)度函數(shù)。,目標(biāo)函

12、數(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)題的類(lèi)型，有目標(biāo)函數(shù)值按一定轉(zhuǎn)換規(guī)則求出個(gè)體的適應(yīng)度。,最優(yōu)化問(wèn)題,最優(yōu)化問(wèn)題可以分為兩大類(lèi)，一類(lèi)為求目標(biāo)函數(shù)的全局最大值，另一類(lèi)

13、為求目標(biāo)函數(shù)的全局最小值。對(duì)于目標(biāo)函數(shù)最小值的優(yōu)化問(wèn)題可轉(zhuǎn)化為： min f(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）,,注：Cmax和Cmin最好與種群無(wú)關(guān),我們希望在遺傳算法運(yùn)行的初期，算法能對(duì)一些適應(yīng)度較高的個(gè)體進(jìn)行控制，降低其適應(yīng)度與其他個(gè)體適應(yīng)度之間的差異程度，從而限制復(fù)制數(shù)量，以維護(hù)群體的多樣性。 在遺傳運(yùn)算后期，算法能對(duì)個(gè)體

14、適應(yīng)度進(jìn)行適當(dāng)放大，擴(kuò)大最佳個(gè)體適應(yīng)度與其它適應(yīng)度之間的差異程度，以提高個(gè)體之間的競(jìng)爭(zhēng)性。目前常用的個(gè)體適應(yīng)度尺度變換方法主要有三種：線(xiàn)性尺度變換、乘冪尺度變換、指數(shù)尺度變換。,線(xiàn)性尺度變換,F’=aF+b，F(xiàn)為原適應(yīng)度；F’為變換后的新適應(yīng)度，a和b位系數(shù)。系數(shù)a和b直接影響到這個(gè)尺度變換的大小，所以對(duì)其選擇有一定的要求，一般要滿(mǎn)足以下條件：F’avg= Favg，這條要求是為了保證群體中適應(yīng)度接近于平均適應(yīng)度的個(gè)體能夠有期待的

15、數(shù)量被遺傳到下一代種群中。F’max=C· Favg，C為最佳個(gè)體的期望復(fù)制數(shù)量。這條要求是為了保證群體中做好的個(gè)體能夠期望復(fù)制C倍到新一代群體中。,使用線(xiàn)性變換時(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和

16、Favg的指定倍數(shù)關(guān)系，將有可能會(huì)使較差的個(gè)體適應(yīng)度變換為負(fù)值。解決上述問(wèn)題的方法是：把原最小適應(yīng)度Fmin映射為F’min=0，并且保持原平均適應(yīng)度Favg與新的平均適應(yīng)度F’avg相等。,乘冪尺度變換,F’=Fk,新的適應(yīng)度是原有適應(yīng)度的某個(gè)指定乘冪。冪指數(shù)k與所求解的問(wèn)題有關(guān)，并且在算法的執(zhí)行過(guò)程中需要不斷對(duì)其進(jìn)行修正才能使尺度變換滿(mǎn)足一定的伸縮要求。機(jī)器視覺(jué)中k的最佳取值為1.005。,指數(shù)尺度變換,F’=exp（-

17、F）新的適應(yīng)度使原有適應(yīng)度的某個(gè)指數(shù)。式中系數(shù) 決定了選擇的強(qiáng)制性， 越小，原有的是適應(yīng)度較高的個(gè)體的新適應(yīng)度就越與其它個(gè)體的新適應(yīng)度相差較大，亦即越增加了選擇該個(gè)體的強(qiáng)制性。,,,,適應(yīng)度函數(shù)的設(shè)計(jì),(1)單值、連續(xù)、非負(fù)、最大化 適應(yīng)度函數(shù)F(X)應(yīng)該是實(shí)函數(shù),并且單值、連續(xù),但不要求可導(dǎo)。不過(guò),F(X)的曲線(xiàn)在重要部位,特別在最優(yōu)解附近一般不宜太陡也不宜過(guò)于平緩。,(2)計(jì)算量小 F(X)不應(yīng)設(shè)計(jì)得過(guò)于繁復(fù),應(yīng)在上述條

18、件下越簡(jiǎn)單越好。,適應(yīng)度函數(shù)的設(shè)計(jì),(3)通用性 一個(gè)適應(yīng)度函數(shù)的好壞,還應(yīng)滿(mǎn)足盡可能廣泛的通用性,使用戶(hù)在求解種種問(wèn)題時(shí),最好無(wú)需改變適應(yīng)度函數(shù)中的參數(shù)。它能使用戶(hù)在對(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ì),理想情況下 :b的值是minf(x)= y*,當(dāng)適應(yīng)度值為0.5時(shí),α是f(

19、x)到minf(x)的距離?？紤]到適應(yīng)度函數(shù)的不同應(yīng)用場(chǎng)合, 將β值取為2,將α值分別取為1,1.5,0.5.即可在b,a取定的情況下得到3種適應(yīng)度函數(shù)。,,當(dāng)取α=1時(shí),適應(yīng)度值在[0.5～1]之間是線(xiàn)性的;對(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ù)則有

20、相反的適應(yīng)情況.本文建議公式里的b和a隨遺傳算法的下一代進(jìn)化而不斷地修正.,b的值可取當(dāng)前第i代中的最小值,即而則建議用下列公式求取 ： 若要求適應(yīng)度函數(shù)曲線(xiàn)變化得“陡”一些,只需把公式中的相關(guān)系數(shù)調(diào)節(jié)得再小一些即可(例如將分母變大);同樣,若要求適應(yīng)度函數(shù)曲線(xiàn)“緩”一點(diǎn),可以把系數(shù)適當(dāng)調(diào)大一些(例如將分母變小).,,遺傳算法的終止條件,遺傳算法的終止條件常用的判定準(zhǔn)則有下面兩種連續(xù)幾代個(gè)體平均適應(yīng)度的差異小于某一個(gè)極小的閾值。