《MATLAB遺傳算法工具箱及應(yīng)用》課件第3章

第三章遺傳算法的理論基礎(chǔ) 3.1模式定理

不失一般性，本節(jié)以二進(jìn)制串作為編碼方式來討論模式定理(PatternTheorem)。

定義3.1基于三值字符集{0，1，*}所產(chǎn)生的能描述具有某些結(jié)構(gòu)相似性的0、1字符串集的字符串稱做模式。

以長(zhǎng)度為5的串為例，模式*0001描述了在位置2、3、4、5具有形式“0001”的所有字符串，即(00001，10001)。由此可以看出，模式的概念為我們提供了一種簡(jiǎn)潔的用于描述在某些位置上具有結(jié)構(gòu)相似性的0、1字符串集合的方法。引入模式后，我們看到一個(gè)串實(shí)際上隱含著多個(gè)模式(長(zhǎng)度為n的串隱含著2n個(gè)模式)，一個(gè)模式可以隱含在多個(gè)串中，不同的串之間通過模式而相互聯(lián)系。遺傳算法中串的運(yùn)算實(shí)質(zhì)上是模式的運(yùn)算。因此，通過分析模式在遺傳操作下的變化，就可以了解什么性質(zhì)被延續(xù)，什么性質(zhì)被丟棄，從而把握遺傳算法的實(shí)質(zhì)，這正是模式定理所揭示的內(nèi)容。

定義3.2模式H中確定位置的個(gè)數(shù)稱做該模式的階數(shù)，記作o(H)。比如，模式011*1*的階數(shù)為4，而模式0*****的階數(shù)為1。

顯然，一個(gè)模式的階數(shù)越高，其樣本數(shù)就越少，因而確定性越高。定義3.3模式H中第一個(gè)確定位置和最后一個(gè)確定位置之間的距離稱做該模式的定義距，記作δ(H)。比如,模式011*1*的定義距為4，而模式0*****的定義距為0。

模式的階數(shù)和定義距描述了模式的基本性質(zhì)。

下面通過分析遺傳算法的三種基本遺傳操作對(duì)模式的作用來討論模式定理。令A(yù)(t)表示第t代中串的群體，以A

j(t)(j=1,2,…,n)表示第t代中第j個(gè)個(gè)體串。

1.選擇算子

在選擇算子作用下，與某一模式所匹配的樣本數(shù)的增減依賴于模式的平均適應(yīng)度。與群體平均適應(yīng)度之比，平均適應(yīng)度高于群體平均適應(yīng)度的將呈指數(shù)級(jí)增長(zhǎng)，而平均適應(yīng)度低于群體平均適應(yīng)度的模式將呈指數(shù)級(jí)減少。其推導(dǎo)如下:

設(shè)在第t代種群A(t)中模式所能匹配的樣本數(shù)為m，記為m(H,t)。在選擇中，一個(gè)位串Aj以概率被選中并進(jìn)行復(fù)制，其中fj是個(gè)體Aj(t)的適應(yīng)度。假設(shè)一代中群體大小為n，且個(gè)體兩兩互不相同，則模式H在第t+1代中的樣本數(shù)為(3.1)式中，f(H)是在t時(shí)刻對(duì)應(yīng)于模式的位串的平均適應(yīng)度。令群體平均適應(yīng)度為,則有(3.2)現(xiàn)在，假定模式H的平均適應(yīng)度高于群體平均適應(yīng)度，且設(shè)高出部分為cf,

c為常數(shù)，則有(3.3)假設(shè)從t=0開始，c保持為常值，則有(3.1)

2.交叉算子

然而僅有選擇操作，并不能產(chǎn)生新的個(gè)體，即不能對(duì)搜索空間中新的區(qū)域進(jìn)行搜索，因此引入了交叉操作。下面討論模式在交叉算子作用下所發(fā)生的變化，這里我們只考慮單點(diǎn)交叉的情況。

模式H只有當(dāng)交叉點(diǎn)落在定義距之外時(shí)才能生存。在簡(jiǎn)單交叉(單點(diǎn)交叉)下H的生存概率Ps=1-δ(H)/(t-1)。例如,一個(gè)長(zhǎng)度為5的串以及隱含其中的兩個(gè)模式為A=010110H1=*1***0H2=***11*

我們注意到模式H1的定義長(zhǎng)度為4，那么交叉點(diǎn)在6-1=5個(gè)位置隨機(jī)產(chǎn)生時(shí)，H1遭破壞的概率Pd=δ(H2)/(m-1)=1/5，即生存概率為4/5。

而交叉本身也是以一定的概率Pc發(fā)生的，所以模式H的生存概率為(3.5)現(xiàn)在我們考慮交叉發(fā)生在定義距內(nèi)，模式H不被破壞的可能性。在前面的例子中，若與A交叉的串在位置2、6上有一位與A相同，則H1將被保留?？紤]到這一點(diǎn)，式(3.5)給出的生存概率只是一個(gè)下界，即有(3.5)

3.變異算子

假定串的某一位置發(fā)生改變的概率為Pm，則該位置不變的概率為1-Pm，而模式H在變異算子作用下若要不受破壞，則其中所有的確定位置(“0”或“1”的位)必須保持不變。因此模式H保持不變的概率為(1-Pm)o(H)，其中o(H)為模式H的階數(shù)。當(dāng)Pm<<1時(shí)，模式H在變異算子作用下的生存概率為Ps=(1-Pm)o(H)≈1-o(H)Pm

(3.7)

綜上所述，模式H在遺傳算子選擇、交叉和變異的共同作用下，其子代的樣本數(shù)為(3.8)

定理3.1(模式定理)在遺傳算子選擇、交叉和變異的作用下，具有階數(shù)低、長(zhǎng)度短、平均適應(yīng)度高于群體平均適應(yīng)度的模式在子代中將以指數(shù)級(jí)增長(zhǎng)。

統(tǒng)計(jì)學(xué)的研究表明：在隨機(jī)搜索中，要獲得最優(yōu)的可行解，則必須保證較優(yōu)解的樣本呈指數(shù)級(jí)增長(zhǎng)，而模式定理保證了較優(yōu)的模式(遺傳算法的較優(yōu)解)的樣本呈指數(shù)級(jí)增長(zhǎng)，從而給出了遺傳算法的理論基礎(chǔ)。另外，由于遺傳算法總能以一定的概率遍歷到解空間的每一個(gè)部分，因此在選擇算子的條件下總能得到問題的最優(yōu)解。 3.2積木塊假設(shè)

定義3.4階數(shù)低、長(zhǎng)度短和適應(yīng)度高的模式稱為積木塊。

假設(shè)3.1積木塊假設(shè)(BuildingBlockHypothesis)階數(shù)低、長(zhǎng)度短、適應(yīng)度高的模式(積木塊)在遺傳算子作用下，相互結(jié)合，能生成階數(shù)高、長(zhǎng)度長(zhǎng)、適應(yīng)度高的模式，可最終生成全局最優(yōu)解。

與積木塊一樣，一些好的模式在遺傳算法操作下相互拼搭、結(jié)合，產(chǎn)生適應(yīng)度更高的串，從而找到更優(yōu)的可行解，這正是積木塊假設(shè)所揭示的內(nèi)容。下面用圖來說明遺傳算法中積木塊生成最優(yōu)解的過程。假設(shè)每代種群規(guī)模為8，Si表示每代群體中第i個(gè)個(gè)體，問題的最優(yōu)解由積木塊AA、BB、CC組成。圖3.1所示為初始種群，個(gè)體S1、S7含有AA，個(gè)體S4、S8含有BB，個(gè)體S3含有CC。當(dāng)種群進(jìn)化一代后，第二代種群如圖3.2所示，個(gè)體S1、S3、S7含有AA，個(gè)體S2、S7含有BB，個(gè)體S3、S6含有CC。個(gè)體S3含有AA、CC，個(gè)體S7含有AA、BB。當(dāng)種群進(jìn)化到第二代后，第三代種群如圖3.3所示，在群體中，出現(xiàn)了含有積木塊AA、BB、CC的個(gè)體S3，個(gè)體S3就是問題的最優(yōu)解。圖3.1初始種群當(dāng)種群進(jìn)化一代后，第二代種群如圖3.2所示，個(gè)體S1、S3、S7含有AA，個(gè)體S2、S7含有BB，個(gè)體S3、S6含有CC。個(gè)體S3含有AA、CC，個(gè)體S7含有AA、BB。當(dāng)種群進(jìn)化到第二代后，第三代種群如圖3.3所示，在群體中，出現(xiàn)了含有積木塊AA、BB、CC的個(gè)體S3，個(gè)體S3就是問

題的最優(yōu)解。圖3.2第二代種群圖3.3第三代種群模式定理保證了較優(yōu)的模式(遺傳算法的較優(yōu)解)樣本數(shù)呈指數(shù)級(jí)增長(zhǎng)，從而滿足了尋找最優(yōu)解的必要條件，即遺傳算法存在著尋找到全局最優(yōu)解的可能性。而這里的積木塊假設(shè)則指出，遺傳算法具備找到全局最優(yōu)解的能力，即積木塊在遺傳算子作用下，能生成階數(shù)高、長(zhǎng)度長(zhǎng)、適應(yīng)度高的模式，最終生成全局最優(yōu)解。 3.3欺騙問題

在遺傳算法中，將所有妨礙適應(yīng)度高的個(gè)體的生成從而影響遺傳算法正常工作的問題統(tǒng)稱為欺騙問題(DeceptiveProblem)。遺傳算法運(yùn)行過程具有將階數(shù)低、長(zhǎng)度短、平均適應(yīng)度高于群體平均適應(yīng)度的模式重組成高階模式的趨勢(shì)。如果在低階模式中包含了最優(yōu)解，則遺傳算法就可能找出這個(gè)最優(yōu)解來。但是低階、高適應(yīng)度的模式可能沒有包含最優(yōu)串的具體取值，于是遺傳算法就會(huì)收斂到一個(gè)次優(yōu)的結(jié)果。下面給出有關(guān)欺騙性的概念。

定義3.5(競(jìng)爭(zhēng)模式)

若模式H和H′中*的位置完全一致，但任一確定位的編碼均不同，則稱H和H′互為競(jìng)爭(zhēng)模式。

定義3.6(欺騙性)假設(shè)f(X)的最大值對(duì)應(yīng)的X的集合為X*，H為一包含X*的m階模式，H的競(jìng)爭(zhēng)模式為H′，而且f(H)＞f(H′)，則f為m階欺騙。

定義3.7(最小欺騙性)在欺騙問題中，為了造成騙局所需設(shè)置的最小的問題規(guī)模(即階

數(shù))稱為最小欺騙性。其主要思想是在最大程度上違背積木塊假設(shè)，是優(yōu)于由平均的短積木塊生成局部最優(yōu)點(diǎn)的方法。

這里的“最小”是指問題規(guī)模采用兩位。

下面是一個(gè)由4個(gè)階數(shù)為2、有2個(gè)確定位置的模式集：

***0*****0*

f(00)

***0*****1*

f(01)

***1*****0*

f(10)

***1*****1*

f(11)為簡(jiǎn)單(達(dá)到最小)起見，我們不考慮*位，令f(11)為全局最優(yōu)解，為了欺騙遺傳算法，Goldberg設(shè)計(jì)了兩種情況：

Type1：f(01)＞f(00)

Type2：f(00)＞f(01)

滿足f(0*)＞f(1*)或者f(*0)＞f(*1)。

按Holland的模式定理，最小欺騙問題將給遺傳算法造成很大困難，遺傳算法甚至找不到最優(yōu)解。但Goldberg實(shí)驗(yàn)的結(jié)果卻是：Type1問題基本上都能很快找到最優(yōu)解，Type2問題找到和找不到兩種情況都可能出現(xiàn)。遺傳算法中欺騙性的產(chǎn)生往往與適應(yīng)度函數(shù)確定和調(diào)整、基因編碼方式選取相關(guān)。采用合適的編碼方式或調(diào)整適應(yīng)度函數(shù)，就可能化解和避免欺騙問題。下面以合適的編碼方式為例來說明。

一個(gè)2位編碼的適應(yīng)度函數(shù)為采用二進(jìn)制編碼，計(jì)算個(gè)體的函數(shù)值(見表3.1)，則存在第二類欺騙問題。采用格雷編碼，計(jì)算個(gè)體的函數(shù)值(見表3.2)，則第二類欺騙問題化解為第一類欺騙問題。表3.1二進(jìn)制編碼及函數(shù)值

編碼對(duì)應(yīng)整數(shù)解函數(shù)值0004011310211135表3.2格雷編碼及函數(shù)值

編碼對(duì)應(yīng)整數(shù)解函數(shù)值0004011311211035采用適當(dāng)?shù)倪m應(yīng)度函數(shù)調(diào)整方法，設(shè)g(x)∶g(00)=128,g(01)=1,g(10)=g(11)=32如果適應(yīng)度函數(shù)f(x)=g(x)，則故存在欺騙問題。如果用適應(yīng)度函數(shù)的調(diào)整方法，f(x)=lbg(x)，則f(00)=7,f(01)=0,f(11)=f(10)=5得f(0*)=3.5，f(1*)=5，故不會(huì)產(chǎn)生欺騙問題。3.4遺傳算法的未成熟收斂問題及其防止

3.4.1遺傳算法的未成熟收斂問題

1.未成熟收斂現(xiàn)象未成熟收斂現(xiàn)象主要表現(xiàn)在兩個(gè)方面：

(1)群體中所有的個(gè)體都陷于同一極值而停止進(jìn)化。

(2)接近最優(yōu)解的個(gè)體總是被淘汰，進(jìn)化過程不收斂。未成熟收斂現(xiàn)象是遺傳算法中的特有現(xiàn)象，且十分常見。它指的是，當(dāng)還未達(dá)到全局最優(yōu)解或滿意解時(shí)，群體中不能再產(chǎn)生性能超過父代的后代，群體中的各個(gè)個(gè)體非常相似。未成熟收斂的重要特征是群體中個(gè)體結(jié)構(gòu)的多樣性急劇減少，這將導(dǎo)致遺傳算法的交叉算子和選擇算子不能再產(chǎn)生更有生命力的新個(gè)體。遺傳算法希望找到最優(yōu)解或滿意解，而不是在找到最優(yōu)解或滿意解之前，整個(gè)群體就收斂到一個(gè)非優(yōu)個(gè)體，它希望能夠保持群體中個(gè)體結(jié)構(gòu)的多樣性，從而使搜索能夠進(jìn)行下去。未成熟收斂問題就像其他算法中的局部極小值(極大值)問題，但它和局部極小值問題有著本質(zhì)上的不同，未成熟收斂問題并不一定出現(xiàn)在局部極小點(diǎn)。同時(shí)，它的產(chǎn)生是帶有隨機(jī)性的，人們很難預(yù)見是否會(huì)出現(xiàn)未成熟收斂問題。

2.未成熟收斂產(chǎn)生的主要原因

未成熟收斂產(chǎn)生的主要原因有以下幾點(diǎn)：

(1)理論上考慮的選擇、交叉、變異操作都是絕對(duì)精確的，它們之間相互協(xié)調(diào)，能搜索到整個(gè)解空間，但在具體實(shí)現(xiàn)時(shí)很難達(dá)到這個(gè)要求。

(2)所求解的問題是遺傳算法欺騙問題。當(dāng)解決的問題對(duì)于標(biāo)準(zhǔn)遺傳算法來說比較困難時(shí)，遺傳算法就會(huì)偏離尋優(yōu)方向，這種問題被稱為遺傳算法欺騙問題。

(3)遺傳算法處理的群體是有限的，因而存在隨機(jī)誤差，它主要包括取樣誤差和選擇誤差。取樣誤差是指所選擇的有限群體不能代表整個(gè)群體所產(chǎn)生的誤差。當(dāng)表示有效模板串的數(shù)量不充分或所選的串不是相似子集的代表時(shí)，遺傳算法就會(huì)發(fā)生上述類似的情況。小群體中的取樣誤差妨礙模板的正確傳播，因而阻礙模板原理所預(yù)測(cè)的期望性能產(chǎn)生。選擇誤差是指不能按期望的概率進(jìn)行個(gè)體選擇。對(duì)一個(gè)染色體來說，在遺傳操作中只能產(chǎn)生整數(shù)個(gè)后代。在有限群體中，模板的樣本不可能以任意精度反映所要求的比例，這是產(chǎn)生取樣誤差的根本原因，加上隨機(jī)選擇的誤差，就可以導(dǎo)致模板樣品數(shù)量與理論預(yù)測(cè)值有很大差別。隨著這種偏差的積累，一些有用的模板將會(huì)從群體中消失。遺傳學(xué)家認(rèn)為當(dāng)群體很小時(shí)，選擇就不會(huì)起作用，這時(shí)有利的基因可能被淘汰，有害的基因可能被保留。引起群體結(jié)構(gòu)發(fā)生變化的主要因素是隨機(jī)波動(dòng)的——遺傳漂移，它也是產(chǎn)生未成熟收斂的一個(gè)主要原因。對(duì)此可以采用增大群體容量的方法來減緩遺傳漂移，但這樣做可能導(dǎo)致算法效率的降低。上述三個(gè)方面都有可能產(chǎn)生未成熟收斂現(xiàn)象，即群體中個(gè)體的多樣性過早地丟失，從而使算法陷入局部最優(yōu)點(diǎn)。

在遺傳算法處理過程的每個(gè)環(huán)節(jié)都有可能導(dǎo)入未成熟收斂的因素。遺傳算法未成熟收斂產(chǎn)生的主要原因是，在迭代過程中，未得到最優(yōu)解或滿意解以前，群體就失去了多樣性。

具體表現(xiàn)在以下幾個(gè)方面：

(1)在進(jìn)化初始階段，生成了具有很高適應(yīng)度的個(gè)體X。

(2)在基于適應(yīng)度比例的選擇下，其他個(gè)體被淘汰，大部分個(gè)體與X一致。

(3)相同的兩個(gè)個(gè)體進(jìn)行交叉，從而未能生成新個(gè)體。

(4)通過變異所生成的個(gè)體適應(yīng)度高但數(shù)量少，所以被淘汰的概率很大。

(5)群體中的大部分個(gè)體都處于與X一致的狀態(tài)。3.4.2未成熟收斂的防止

在分析了未成熟收斂產(chǎn)生的原因后，下面要解決的是如何防止該現(xiàn)象的發(fā)生，即如何維持群體多樣性以保證在尋找到最優(yōu)解或滿意解以前，不會(huì)發(fā)生未成熟收斂現(xiàn)象。解決的方法有以下幾種。

1.重新啟動(dòng)法

重新啟動(dòng)法是實(shí)際應(yīng)用中最早出現(xiàn)的方法之一。在遺傳算法搜索中碰到未成熟收斂問題而不能繼續(xù)時(shí)，隨機(jī)選擇一組初始值重新進(jìn)行遺傳算法操作。假設(shè)每次執(zhí)行遺傳算法后陷入不成熟收斂的概率為Q(0≤Q＜1)，那么做n次獨(dú)立的遺傳算法操作后，可避免未成熟收斂的概率為F(n)=1-Qn，隨著n的增大，F(xiàn)(n)將趨于1。但是，對(duì)于Q較大的情況，如果優(yōu)化對(duì)象很復(fù)雜以及每次執(zhí)行時(shí)間都很長(zhǎng)，采用該辦法顯然是不合適的。

2.配對(duì)策略(MatingStrategies)

為了維持群體的多樣性，可以有目的地選擇配對(duì)個(gè)體。一般情況下，在物種的形成過程中要考慮配對(duì)策略，以防止根本不相似的個(gè)體進(jìn)行配對(duì)。因?yàn)樵谏锝?，不同種族之間一般是不會(huì)雜交的，這是因?yàn)樗鼈兊幕蚪Y(jié)構(gòu)不同，會(huì)發(fā)生互斥作用，同時(shí)雜交后會(huì)使種族失去其優(yōu)良特性。因此，配對(duì)受到限制，即大多數(shù)是同種或近種相配，以使一個(gè)種族的優(yōu)良特性得以保存和發(fā)揚(yáng)。然而，這里所說的匹配策略有不同的目的。其目的是，由不同的父輩產(chǎn)生的個(gè)體試圖比其父輩更具有多樣性，Goldberg的共享函數(shù)(SharingFunction)就是一種間接匹配策略。該策略對(duì)生物種(Species)內(nèi)的相互匹配或至少對(duì)占統(tǒng)治地位的物種內(nèi)的相互匹配有一定限制。Eshelman提出了一種可以更直接地防止相似個(gè)體交配的方法——防止亂倫機(jī)制(IncestPreventionMechanism)。參與交配的個(gè)體是隨機(jī)配對(duì)的，但只有當(dāng)參與配對(duì)的個(gè)體間的海明距離超過一定閾值時(shí)，才允許它們進(jìn)行交配。最初的閾值可采用初始群體海明距離的期望平均值，隨著迭代過程的發(fā)展，閾值可以逐步減小。盡管Eshelman的方法并不能明顯地阻止同輩或相似父輩之間進(jìn)行交配，但只要個(gè)體相似，它就有一定的影響。匹配策略是對(duì)具有一定差異的個(gè)體進(jìn)行配對(duì)，這在某種程度上可以維持群體的多樣性。但它同時(shí)也具有一定的副作用，即交叉操作會(huì)使較多的模板遭到破壞，只有較少的共享模板得以保留。

3.重組策略(RecombinationStrategies)

重組策略就是使用交叉算子。在某種程度上，交叉操作試圖產(chǎn)生與其父輩不同的個(gè)體，從而使產(chǎn)生的群體更具多樣性。能使交叉操作更具有活力的最簡(jiǎn)單的方法是，增加其使用的頻率和使用動(dòng)態(tài)改變適應(yīng)度函數(shù)的方法，如共享函數(shù)方法。另一種方法是把交叉點(diǎn)選在個(gè)體的具有不同值的位上。只要父輩個(gè)體至少有兩位不同，所產(chǎn)生的子代個(gè)體就會(huì)與其父輩不相同。維持群體多樣性的基本方法是，使用更具有破壞性的交叉算子，如均勻交叉算子。

該算子試圖交叉近一半的不同位，因而保留的模板比單點(diǎn)或兩點(diǎn)交叉所保留的模板要少得多?？傊?，重組策略主要是從使用頻率和交叉點(diǎn)兩方面考慮，來維持群體的多樣性。這對(duì)采用隨機(jī)選擇配對(duì)個(gè)體進(jìn)行交叉操作可能有特定的意義，但對(duì)成比例選擇方式，效果則不一定明顯。

4.替代策略(ReplacementStrategies)

匹配策略和重組策略分別是在選擇、交叉階段，通過某種策略來維持群體的多樣性。而替代策略是確定在選擇、交叉產(chǎn)生的個(gè)體中，選擇哪一個(gè)個(gè)體進(jìn)入新一代群體。DeJong采用排擠（Crowding）模式，用新產(chǎn)生的個(gè)體去替換父輩中類似的個(gè)體。Syscuda和Whiteley也采用類

似的方法，他們僅把與父輩各個(gè)個(gè)體均不相似的新個(gè)體添加到群體中。這種替換策略僅從維持群體的多樣性出發(fā)，存在一定的負(fù)面影響，即交叉操作會(huì)破壞較多模板，但這種影響比前兩種策略的要小。 3.5性能評(píng)估

1.在線性能評(píng)估準(zhǔn)則

定義3.8設(shè)Xe(s)為環(huán)境e下策略s的在線性能，fe(t)為時(shí)刻t或第t代中相應(yīng)于環(huán)境e的目標(biāo)函數(shù)或平均適應(yīng)度函數(shù)，則Xe(s)可以表示為(3.9)式(3.9)表明，在線性能可以用從第一代到當(dāng)前代的優(yōu)化進(jìn)程的平均值來表示。

2.離線性能評(píng)估準(zhǔn)則

定義3.9

設(shè)X*e(s)為環(huán)境e下策略s的離線性能，則有(3.10)式中，fe*

(t)=best{fe(1),fe(2),…,fe(t)}。式(3.10)表明，離線性能是特定時(shí)刻或特定代的最佳性能的累積平均。具體地說，在進(jìn)化過程中，每進(jìn)化一代就統(tǒng)計(jì)目前為止的各代中的最佳適應(yīng)度或最佳平均適應(yīng)度，并計(jì)算進(jìn)化代數(shù)的平均值。DeJong指出：離線性能用于測(cè)量算法的收斂性，在應(yīng)用時(shí)，優(yōu)化問題的求解可以得到模擬，在一定的優(yōu)化進(jìn)程停止準(zhǔn)則下，當(dāng)前最好的解可以被保存和利用；而在線性能用于測(cè)量算法的動(dòng)態(tài)性能，在應(yīng)用時(shí)，優(yōu)化問題的求解必須通過真實(shí)的實(shí)驗(yàn)在線實(shí)現(xiàn)，可以迅速得到較好的優(yōu)化結(jié)果。但是，從遺傳算法的運(yùn)行機(jī)理可知，在遺傳算子的作用下，群體的平均適應(yīng)度呈現(xiàn)增長(zhǎng)的趨勢(shì)，因此，定義3.8和定義3.9中的fe(t)和f*e(t)相差不大，它們所反映的性質(zhì)也基本一樣。

假設(shè)一算法產(chǎn)生的迭代點(diǎn)列{xi}在某種范數(shù)意義下收斂，即(3.11)式中，xi+1=xi+αi,αi為步長(zhǎng)因子。若存在實(shí)數(shù)α＞0及一個(gè)與迭代次數(shù)無關(guān)的常數(shù)q＞0，使得(3.12)則稱此算法產(chǎn)生的迭代點(diǎn)列{xi}具有q-α階收斂速度（α為迭代步長(zhǎng)因子）。因?yàn)椤瑇i+1-xi‖是‖xi-x*‖的一個(gè)估計(jì)，所以在實(shí)際中，一般用‖xi+1-xi‖代替‖xi-x*‖，作為迭代終止判決條件。(1)當(dāng)α=1，q＞0時(shí)，稱{xi}具有q線性收斂速度。

(2)當(dāng)1＜α＜2,q＞0或α=1,q=0時(shí)，稱{xi}具有q超線性收斂速度。

(3)當(dāng)α=2時(shí)，稱{xi}具有q二階收斂速度。

具有超線性收斂速度和二階收斂速度的迭代算法收斂比較快。

關(guān)于算法的終止準(zhǔn)則