遺傳算法模式定理課件

遺傳算法的模式理論遺傳算法的模式理論1從簡單遺傳算法的操作中，我們可以看到尋優(yōu)問題的性能是朝著不斷改進(jìn)的方向發(fā)展的。但是我們怎么能知道對某一特定問題使用遺傳算法會得到優(yōu)化或接近優(yōu)化的解呢？分析遺傳算法中的模式理論：模式；復(fù)制對模式的影響；交叉對模式的影響；變異對模式的影響；遺傳算法有效處理的模式數(shù)量。從簡單遺傳算法的操作中，我們可以看到尋優(yōu)問題的性能是朝著不斷2模式一個模式(Schemata)就是一個描述種群中在位串的某些確定位置上具有相似性的位串子集的相似性模板(SimilarityTemplate)

。例如：求maxf(x)=x2x

{0,31}遺傳算法的第0代

在上列種群里的各位串之間，我們能發(fā)現(xiàn)具有某種相似性和這種相似性與高適配值之間具有某種因果關(guān)系。位串Xi適配值x=0110113f(x)=x2＝132＝16911000 2457601000 8641001119361模式一個模式(Schemata)就是一個描述種群中在位串的某3

這種因果關(guān)系例如：凡是以“1”開始的位串，其適配值就高；以“0”開始的位串的適配值就低。這種相似性正是遺傳算法有效工作的因素。根據(jù)對種群中高適配置位串之間的相似性的分析，Holland提出了遺傳算法的模式理論.這種因果關(guān)系例如：凡是以“1”開始的位串，其適配值就高；以4模式為了描述一個模式，在用以表示位串的兩個字符的字母{0,1}中加入一個通配符“*”，就構(gòu)成了一個表示模式用的三個字符的字母表{0，1，*}。因此用三元素字母表{0，1，*}可以構(gòu)造出任意一種模式。一個模式與一個特定位串相匹配是指：該模式中的1與位串中的1相匹配，模式中的0與位串的0相匹配，模式中的“*”可以匹配位串中的0或1。模式為了描述一個模式，在用以表示位串的兩個字符的字母{0,15模式模式00*00匹配了兩個位{00100,00000}模式*111*可以和{01110,01111,11110,11111}中的任何一個位串匹配，即與長度為5中間三位為“1”的四個位串匹配；模式0*1**則匹配了長度為5、第一位為0、第三位為1的8個位串{00100,00101,00110,00111,01100,01101,01110,01111}模式6模式的思路為我們提供了一種簡單而有效的方法，使能夠在有限字母表的基礎(chǔ)上討論有限長位串的嚴(yán)謹(jǐn)定義的相似性。應(yīng)強(qiáng)調(diào)的是，“*”只是一個元符號，既是代表其他符號的一個符號。它不能被遺傳算法直接處理，只不過是允許來描述特定長度和特定字母表的位串的所有可能相似性的符號件。模式的思路為我們提供了一種簡單而有效的方法，使能夠在有限字母7

8

9

10

?

個體是由二值字符集V={0,1}中的元素所組成的一個編碼串;

?而模式卻是由三值字符集V={0,1,*}中的元素所組成的一個編碼串。模式階(SchemaOrder)——指模式中已有明確含意(二進(jìn)制字符時指0或1)的字符個數(shù)，記做o(s)，式中s代表模式。例如，模式(011*1**)含有4個明確含意的字符，其階次是4，記作o(011*1**)=4;模式(0******)的階次是1，記作o(0******)=1。?階次越低，模式的概括性越強(qiáng)，所代表的編碼串個體數(shù)也越多，反之亦然；?當(dāng)模式階次為零時，它沒有明確含義的字符，其概括性最強(qiáng)。

?個體是由二值字符集V={0,1}中的元素所組成11模式的定義長度(SchemaDefiningLength)——指模式中第一個和最后一個具有明確含意的字符之間的距離，記作

(s)。例如，模式H(011*l**)的第一個字符為0，最后一個字符為，中間有3個字符，其定義長度為5-1=4，記作

(011*1**)=4；模式H(0******)的長度是0，記作

(0******)=0；模式的定義長度(SchemaDefiningLeng12復(fù)制對模式的影響設(shè)在給定時間(代)t有N個個體，種群A(t)包含有m個特定模式H，記為

m=m(H,t)在復(fù)制過程中，A(t)中的任何一個位串Ai以概率Pi＝fi/∑fi被選中并進(jìn)行復(fù)制。復(fù)制對模式的影響設(shè)在給定時間(代)t有N個個體，種群A(t13因此復(fù)制后在下一代群體A(t+1)中，群體內(nèi)屬于模式H（或稱與模式H匹配）的個體數(shù)目m(H,t+1)可用平均適應(yīng)度按下式近似計算：式中——第t代屬于模式H的所有個體之平均適應(yīng)度；N——群體中擁有的個體數(shù)目。因此復(fù)制后在下一代群體A(t+1)中，群體內(nèi)屬于模式H（或14式(2-1)式(2-1)15可見，經(jīng)過復(fù)制操作后，下一代中特定模式的數(shù)量H正比于所在位串的平均值與種群平均適配值的比值。時，H的數(shù)量將增加；時，H的數(shù)量將減少。 種群A(t)中的任一模式H在復(fù)制中都將按照式(2-1)的規(guī)律變化，即適配值高于種群平均值的模式在下一代中的數(shù)量增加；而適配值低于種群平均值的模式在下一代的數(shù)量將減少。

這種所有模式的增減在復(fù)制中是并行進(jìn)行的,遺傳算法中隱含的并行機(jī)制就在于此?？梢姡?jīng)過復(fù)制操作后，下一代中特定模式的數(shù)量H正比于所在位串16為了進(jìn)一步分析高于平均適配值的模式數(shù)量的增長，假設(shè)(c是一個大于零的常數(shù))，則式（2-1）可重寫為為了進(jìn)一步分析高于平均適配值的模式數(shù)量的增長，假設(shè)17從原始種群開始（t＝0），并假定是一個穩(wěn)定的值，則有

可見，對于高于平均適配值的模式的數(shù)量將呈指數(shù)形