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

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

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

3、明,V+={0，1，*} —模式，*代表不確定字母. 串長為L的二進(jìn)制串上的模式共有3l個.一般的，對于基數(shù)為k的字母表，共有(k+1)l個模式 例如：串長為7的模式H=*11*0** ，A=0111000是模式H的一個表示。 所有模式并不是以同等機會產(chǎn)生的，有些模式比起其它的更加確定，例如：與0******相比，模式011*1**在相似性方面是更明確的表示。,一個模式H的階——出現(xiàn)在模式中確定位置的數(shù)目 。 例如：模

4、式011*1**的階為4可記為，o（011*1**）=4 ；模式0******的階為1 。一個模式的定義長度——模式中第一個確定位置和最后一個確定位置之間的距離 。 例如：模式011*1**的定義長度為4，可記為=4；0******的定義長度為=0。 注：串的階和定義長度是用于討論串的相似性的符號。,在復(fù)制階段，每個串根據(jù)它的適應(yīng)度值進(jìn)行復(fù)制，更確切的說，一個串Ai的復(fù)制概率為： m（H，t+1）= m（H，t）·

5、;n·f(H)/ 其中f(H)是在第t代中模式H的串的平均適應(yīng)值。整個群體的平均適應(yīng)值可記為 /n故模式的復(fù)制生長方程可以表示為:m（H，t+1）= m（H，t）·/ 一個特定的模式按照其平均適應(yīng)值與群體的平均適應(yīng)值之間的比率生長,,,,,,,,下面推出一個定量表達(dá)式，假設(shè)某一特定模式下的適應(yīng)值高出群體平均適應(yīng)值以上一個c，c為一常數(shù)，則模式的復(fù)制生長方程可變?yōu)椋簃（H，t+1）= m（

6、H，t）=（1+c）·m（H，t） 從t=0開始，假設(shè)c是一個固定值，可以推得： m（H，t）= m（H，0）·（1+c）t 上式表明，在群體平均適應(yīng)度以上（以下）的模式將會以指數(shù)增長（衰減）的方式被復(fù)制。,模式定理,模式的階和定義長度兩個概念提供了一個分析遺傳算法中遺傳算子對包含在群體中基因塊的作用效果的基本的方法。m=m（H，t），第t代中模式H有m個代表串包含在群體中A（t）中的樣本。t不同，m

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

8、編碼,簡單易行符合最小字符集編碼規(guī)則便于用模式定理進(jìn)行分析, 因為模式定理就是以二進(jìn)制編碼為基礎(chǔ)提出的。,格雷編碼,格雷編碼有這樣一個特點：任意兩個整數(shù)的差是這兩個整數(shù)所對應(yīng)的格雷碼之間的漢明距離。這個特點是遺傳算法使用格雷來進(jìn)行個體編碼的主要原因。由二進(jìn)制碼到格雷碼的轉(zhuǎn)換公式為：由格雷碼到二進(jìn)制碼的轉(zhuǎn)換公式為：,,,,,浮點數(shù)編碼,首先，二進(jìn)制編碼存在著連續(xù)函數(shù)離散化時的映射誤差。個體編碼長度較短時達(dá)不到精度要求；個體編碼

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

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

11、一位聯(lián)在一起作為編碼的最后n位。這種編碼方式中，各個參數(shù)的局部編碼結(jié)構(gòu)就不易被遺傳算子破壞掉，它適合于各參數(shù)之間的相互關(guān)系較弱，特別是某一各或少數(shù)幾個參數(shù)其主要作用時的優(yōu)化問題。,適應(yīng)度函數(shù),傳算法中使用適應(yīng)度這個概念來度量群體中各個個體在優(yōu)化計算中有可能達(dá)到或接近于或有助于找到最有解的優(yōu)良程度。適應(yīng)度高的個體遺傳到下一代的可能性比較大，而適應(yīng)度比較低的個體遺傳到下一代的概率相對小一些。度量個體適應(yīng)度的函數(shù)稱為適應(yīng)度函數(shù)。,目標(biāo)函

12、數(shù)與適應(yīng)度函數(shù),遺傳算法的一個特點就是它僅使用所求問題的目標(biāo)函數(shù)值就可得到下一步的有關(guān)搜索信息。而對目標(biāo)函數(shù)值的使用是通過評價個體的適應(yīng)度來體現(xiàn)的。評價個體適應(yīng)度的過程一般是： （1）對個體編碼串進(jìn)行解碼處理后，可得到個體的表現(xiàn)型； （2）有個體表現(xiàn)型可計算出對應(yīng)個體的目標(biāo)函數(shù)值； （3）根據(jù)最優(yōu)化問題的類型，有目標(biāo)函數(shù)值按一定轉(zhuǎn)換規(guī)則求出個體的適應(yīng)度。,最優(yōu)化問題,最優(yōu)化問題可以分為兩大類，一類為求目標(biāo)函數(shù)的全局最大值，另一類

13、為求目標(biāo)函數(shù)的全局最小值。對于目標(biāo)函數(shù)最小值的優(yōu)化問題可轉(zhuǎn)化為： min f(X)=max (-f(X)) 當(dāng)優(yōu)化目標(biāo)是函數(shù)的最大值，并且目標(biāo)函數(shù)總?cè)≌龝r，可以直接設(shè)定個體適應(yīng)度F（x）為：F（x）=f（x）,,注：Cmax和Cmin最好與種群無關(guān),我們希望在遺傳算法運行的初期，算法能對一些適應(yīng)度較高的個體進(jìn)行控制，降低其適應(yīng)度與其他個體適應(yīng)度之間的差異程度，從而限制復(fù)制數(shù)量，以維護群體的多樣性。 在遺傳運算后期，算法能對個體

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

15、數(shù)量被遺傳到下一代種群中。F’max=C· Favg，C為最佳個體的期望復(fù)制數(shù)量。這條要求是為了保證群體中做好的個體能夠期望復(fù)制C倍到新一代群體中。,使用線性變換時，群體中有少數(shù)幾個優(yōu)良個體的適應(yīng)度按比例縮小，同時幾個較差的個體適應(yīng)度也按比例擴大。在搜索的后期階段，隨著個體適應(yīng)度從總體上的不斷改進(jìn)，群體中個體的最大適應(yīng)度和全部個體的平均適應(yīng)度較接近，而少數(shù)幾個較差的個體的適應(yīng)度卻遠(yuǎn)遠(yuǎn)小于最大適應(yīng)度，這時若想維持F’max和

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

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

18、件下越簡單越好。,適應(yīng)度函數(shù)的設(shè)計,(3)通用性 一個適應(yīng)度函數(shù)的好壞,還應(yīng)滿足盡可能廣泛的通用性,使用戶在求解種種問題時,最好無需改變適應(yīng)度函數(shù)中的參數(shù)。它能使用戶在對所求解函數(shù)的全局最優(yōu)解的性質(zhì)完全“無知”的情況下,由算法在運行過程中自動修正其中的參數(shù)值,從而一步一步接近最優(yōu)解。從另一種意義上說,這樣的適應(yīng)度函數(shù)具有自適應(yīng)性。,適應(yīng)度函數(shù)的設(shè)計,理想情況下 :b的值是minf(x)= y*,當(dāng)適應(yīng)度值為0.5時,α是f(

19、x)到minf(x)的距離?？紤]到適應(yīng)度函數(shù)的不同應(yīng)用場合, 將β值取為2,將α值分別取為1,1.5,0.5.即可在b,a取定的情況下得到3種適應(yīng)度函數(shù)。,,當(dāng)取α=1時,適應(yīng)度值在[0.5～1]之間是線性的;對于在全局最優(yōu)解y*附近變化比較緩慢的函數(shù),用α=0.5可以使適應(yīng)度函數(shù)較靈敏地反映出y值的變化情況.在算法的后期,則可以有效地拉開最優(yōu)解附近點的適應(yīng)度值,便于做出敏感選擇,從而有利于以后的選擇;當(dāng)α=1.5時的適應(yīng)度函數(shù)則有

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