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

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

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

3、明,V+={0，1，*} —模式，*代表不確定字母. 串長為L的二進制串上的模式共有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。 注：串的階和定義長度是用于討論串的相似性的符號。,在復制階段，每個串根據(jù)它的適應度值進行復制，更確切的說，一個串Ai的復制概率為： m（H，t+1）= m（H，t）·

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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