第9章進化計算信息處理方法與應(yīng)用9?1標準遺傳算法遺傳算法是具有“生成+測試”(generateandtest)的迭代過程的搜索算法。它的基本處理流程如圖9-1所示。遺傳算法是一種群體型操作，該操作以群體中的所有個體為對象。圖9-1遺傳算法的基本流程復制(reproduction)，交叉(crossover)和變異(mutation)是遺傳算法的3個主要操作算子，它們構(gòu)成了所謂的遺傳操作(geneticoperation)，使遺傳算法具有了其它傳統(tǒng)搜索算法所沒有的特征。遺傳算法中包含了5個基本要素：參數(shù)編碼；初始群體的設(shè)定；適應(yīng)度(fitness)函數(shù)的設(shè)計；遺傳操作設(shè)計；控制參數(shù)設(shè)定(主要是指群體大小和使用遺傳操作的概率等)。這5個要素構(gòu)成了遺傳算法的核心內(nèi)容。下面以函數(shù)優(yōu)化為例來闡述遺傳算法的基本概念和運行過程。函數(shù)優(yōu)化問題表述如下：有n維映射fx):Rn—R，求mafx)，無函數(shù)連續(xù)性的任何信息。遺傳算法把函數(shù)優(yōu)化問題中的自變量x當作生物體，將其轉(zhuǎn)化為由基因構(gòu)成的染色體(以下稱串)，相應(yīng)的函數(shù)值定義為適應(yīng)度。生物體的目標是進化成有最佳適應(yīng)度的基因型。用遺傳算法求解函數(shù)優(yōu)化問題的步驟如下：選擇編碼策略，把參數(shù)轉(zhuǎn)換成串；編碼策略有二進制編碼和實數(shù)編碼等，若采用二進制碼表示實數(shù)，每個二進制位即為一基因，若一維參數(shù)xe[?,b]，則院g21x=a+"^1(b一a).(9-1)其中l(wèi)是串的長度，g,是第i個基因。定義串的適應(yīng)度函數(shù)；適應(yīng)度函數(shù)是目標函數(shù)的映射，它包含了對優(yōu)化問題所需的

信息。3）設(shè)置遺傳算法的控制參數(shù)（群體規(guī)模N,交叉概率Pc，變異概率Pm等），隨機產(chǎn)生N個串構(gòu)成群體；’“4）計算群體中每個串的適應(yīng)度，串解碼所得的解越好，則適應(yīng)度值越高；5）從群體中復制兩個串，串適應(yīng)度越高，則被復制的概率越大；6）在串上隨機選擇一個位置，以交叉概率Pc對兩個串進行交叉操作；7）對兩個串中的基因位以變異概率Pm進行翻轉(zhuǎn)；8）轉(zhuǎn)至5）直至復制N個串；9）轉(zhuǎn)至4）重復進行，直到解滿足性能指標或規(guī)定的進化代數(shù)。以上遺傳操作過程描述了最簡單的進化模型。步驟1）和步驟2）是實際應(yīng)用中的關(guān)鍵。步驟5）至步驟7）進行三種基本遺傳操作，復制實施了適者生存的原則，交叉的作用是組合父代中有價值的信息，產(chǎn)生新的后代，以實現(xiàn)高效搜索，變異的作用是保持群體中基因的多樣性。假定用遺傳算法求f（x）=x2函數(shù)的最大值，XG[0,31]。表2.1給出了用遺傳算法求解此問題的計算過程和結(jié)果。編碼由于遺傳算法不能直接處理解空間的解數(shù)據(jù)，因此必須通過編碼將它們表示成遺傳空間的基因型中結(jié)構(gòu)數(shù)據(jù)。在表9-1中，變量x編碼為5位長的二進制無符號整數(shù)表示形式。如x=13可以表示成01101。初始群體的生成由于遺傳算法的群體型操作需要，所以必須為遺傳操作準備一個由若干個初始解組成的初始群體。為了簡化說明，在表2.1中取群體大小仁4，即群體由4個個體組成。在表2.1左端給出了這一初始群體的成員。需要說明的是，初始群體的每個個體都是通過隨機方法產(chǎn)生的。初始群體也稱為進化的初始代，即第一代（firstgeneration）。適應(yīng)度評估檢測遺傳算法在搜索進化過程中一般不需要其它外部信息，僅用評估函數(shù)值來評估個體或解的優(yōu)劣，并作為以后遺傳操作的依據(jù)。評估函數(shù)值又稱作適應(yīng)度（fitness）。這里，根據(jù)f（x）=x2來評估群體中各個體。顯然，為了利用f（x）=x2這一評估函數(shù)，即適應(yīng)度函數(shù)，要把基因個體譯碼成表現(xiàn)型個體，即搜索空間中的解，比如11000要譯碼成24。復制復制操作的目的是為了從當前群體中選出優(yōu)良的個體，使它們有機會作為父代為下一代繁殖子孫。判斷個體優(yōu)良與否的準則就是各自的適應(yīng)度值。顯然這一操作是借用了達爾文適者生存的進化原則，即個體適應(yīng)度越高，其被選擇的機會就越多。選擇操作實現(xiàn)方式很多，這里采用和適應(yīng)度值成比例的概率方法來進行選擇的方法。表9-1遺傳算法求f（x）=x2極值（中處理）中號初始群體（隨機生成n=4）適應(yīng)度選擇概率中號初始群體（隨機生成n=4）適應(yīng)度選擇概率期望個數(shù)f(x)=x2Pff&f101101131690.140.58211000245760.491.973010008640.060.22410011193610.311.23總和11701.04.0平均2930.251.0最大5760.492.0表9-1（續(xù)）實際選擇個數(shù)交叉（豎線表配偶新群體（比例選擇）示交叉處）xf(x)=x210110|12011001214421100|011100125625011|00041101127729110|01131000016256總和1754平均439最大729注：表中平均適應(yīng)度f=￡f「n。I具體地說，就是首先計算群體中所有個體適應(yīng)度的總和（If）,再計算每個個體的適應(yīng)度所占的比例f./Sf）,并以此作為相應(yīng)的選擇概率（P,）。表2.1給出了選擇4個個體的概率，由此概率計算出每個個體被選擇的次數(shù)。表2.1給出了相應(yīng)的結(jié)果：個體1和個體4各復制一份，個體2復制2份，個體3不復制而被淘汰。這是所期待的結(jié)果，即最優(yōu)秀的個體（個體2，適應(yīng)度為576）獲得了最多的生存繁殖機會（2份復制），最差的個體（個體3,適應(yīng)度為64）被淘汰。由此得到的4份復制送到配對庫（matingpool），以備配對繁殖。交叉操作簡單的交叉（即一點交叉）可分兩步進行：首先對配對庫中的個體進行隨機配對；其次，在配對個體中隨機設(shè)定交叉處（表2.1中的配對庫中的豎線表示交叉處），配對個體彼此交換部分信息。由表2.1可見，配對庫中的個體2與個體1配對，交叉處為4,通過交叉得到了兩個新的個體：01100和11001。同樣，配對庫中的個體3和個體4的配對交叉（交叉處為2）得到另外兩個新個體11011和10000。這4個新個體形成了新的群體，即新一代。需要指出的是，交叉操作是遺傳算法中最主要的遺傳操作。由于交叉操作得到了新一代個體。仔細觀察比較表2.1中的新舊個體，不難發(fā)現(xiàn)新群體中個體適應(yīng)度的平均值和最大值都有了明顯提高。由于這個例子的適應(yīng)度函數(shù)也就是函數(shù)本身f（x）=x2，所以函數(shù)值也變大了。由此可見，新群體中的個體（即解）的確朝著期望的方向進化了。變異變異操作是按位進行的，即把某一位的內(nèi)容進行變異。對于二進制編碼的個體來說，若某位原為0,則通過變異操作就變成了1,反之亦然。變異操作同樣也是隨機進行的。一般而言，變異概率Pm都取得很小。在這個例子中，取Pm=0.001，由于群體中共有20X0.001=0.02位可以變異，這就意味群體中沒有一位可變異。變異操作是十分微妙的遺傳操作，它需要和交叉操作妥善配合使用，目的是挖掘群體中個體的多樣性，克服有可能限于局部解的弊病。在本例的模擬計算中，僅通過一代進化就使問題的解得到了優(yōu)化，如果按表2.1那樣進行多次迭代處理，或者說群體繼續(xù)不斷地一代代進化下去，那么，最終一定可以得到最優(yōu)解或近似最優(yōu)解。上述的遺傳算法操作過程構(gòu)成了標準的遺傳算法(StandardGA,SGA)，有時也叫簡單遺傳算法，簡稱也是SGA(SimpleGA)。通過上述的簡單例子的討論，不難發(fā)現(xiàn)，遺傳算法所依賴的兩個必不可少而又最重要的操作(即復制和交叉)，是出乎意料的簡單可行。除了隨機數(shù)產(chǎn)生、串結(jié)構(gòu)數(shù)據(jù)復制以及部分串結(jié)構(gòu)數(shù)據(jù)互換外，似乎沒有更多更復雜行為。在這種簡單而似乎有些盲目的結(jié)構(gòu)數(shù)據(jù)復制和重組的操作中，遺傳算法究竟做了些什么？其中是否存在某種規(guī)律或帶有指導性的結(jié)論？以下將對這些問題進行深入的討論。7.遺傳算法算例為了更清楚的地說明上述過程的細節(jié)，我們舉一實例。設(shè)休要解決的問題是：尋找f(x)=-x2+31x+10這一函數(shù)，當自變量X在0-31之間取整數(shù)時函數(shù)值的最大值。若要用枚舉法來求解，則要比較x從0至31的所有值，盡管此法是可靠的，但是這是一種效率低的方法。而若要做到小數(shù)點后若干位，枚舉法甚至由于計算工作量大而成為不可能。下面我們用遺傳來求解這個問題。編碼(coding)(解決初始化種群)其目的是將尋求優(yōu)化解的參數(shù)用若干代碼串來表示。這種代碼就稱為染色體，這一個過程稱為編碼。編碼的方法很多，最簡單的辦法是用二進制來編碼。編碼的基本要求是要為染色體的基因型(代碼串)和表現(xiàn)型(參數(shù)值)建立對應(yīng)關(guān)系。采用二進制代碼時，這種對應(yīng)關(guān)系就是二進制數(shù)與十進制數(shù)的轉(zhuǎn)化關(guān)系。在本例中，x值在0-31之間變化，所以有5位二進制代碼串就可以組成所有染色體的基因型。即所有的染色體基因型在00000-11111之間。接下來是要選擇初始染色體種群的個體數(shù)及個體的具體基因型。一般種群的個體數(shù)要適中，太少了可能迭代次數(shù)要增加，甚至得不到結(jié)果，太大了會增加計算量，降低效率。在本例中我們設(shè)種群的大小為4,即有4個個體。基因型的選擇是隨機的，一般在x值的定義域中較均勻地隨機分布，例如在本例中，我們隨機取4個x值：1，28，8，19。相對應(yīng)的4個基因型為：00001，11100，01000，10011。這樣便完成了遺傳算法的準備工作，產(chǎn)生了初始染色體種群的基因型。.計算適應(yīng)度f(fitness)決定適應(yīng)度f的計算公式，是一個技巧性很高的、而理論上的研究又很不充分的復雜問題。一般要根據(jù)優(yōu)化的目標函數(shù)來決定。在本例中，選擇求解最大值的函數(shù)f(x)=-x2+31x+10來作適應(yīng)度f的計算公式。對應(yīng)所選的4個個體，計算出的適

應(yīng)度「的值分別是：40,94,194,238如表9-1所示。表9-1復制操作之前的各項數(shù)據(jù)中號初始種群（基因型）x值（表現(xiàn)型）適應(yīng)度fif=-x2+31x+10復制概率f期望復制數(shù)f復制數(shù)R1000011400.0710.284021110028940.1660.664130100081940.3431.3721410011192380.4201.6802總計5661.004.004平均141.50.251.001最大值2380.421.6802(3).復制(reproduction)按照達爾文的適者生存理論，愈能適應(yīng)環(huán)境的生物品種，愈能繁衍（復制）其后代，而不適應(yīng)環(huán)境的生物，其生存和繁衍的能力比較低，甚至被淘汰。在本例中，初始種群的適應(yīng)度f已計算出來。復制的原則是：適應(yīng)度f愈高的染色體，其復制的可能及復制的數(shù)愈多。具體的計算是利用隨機方法來實現(xiàn)的。首先按下式來計算復制概率Pi(9—2)再用下式來計算期望的復制個數(shù)Ri(9-3)式中，f是f的期望值（平均值）。根據(jù)四舍五入的規(guī)則，將R圓整為整數(shù)R。1被淘汰掉，串2被復制一次，串3被復制一次，而串4則被復制了兩次。復制后的新種群的4個染色體基因型如表9-2所示。（4）.交換（Crossover，又稱交叉、雜交）交換分兩個步驟。第一步是選擇兩兩匹配的對象。通常是隨機選取的。在本例中，選擇新串號1與4匹配，新串號2與3匹配，這樣選取是為了避免讓新串號3與4匹配（因為兩者的基因相同，這對交換操作沒有實際意義）。第二步是決定交換點及交換規(guī)則。在遺傳算法中，對此步驟的研究也不多，現(xiàn)在一般還是隨機選取。例如在本例中，新串1與4的交換點選在左起第3位，交換規(guī)則是第3位以后的2位代碼交換；新串2與3的交換點選在左起第2位，交換規(guī)則是第2位以后的3位代碼交換，具體過程如下:[新串1：111500]1*11111新串4:10051110000

［新串2：01:000'1r01011［新串3：10:011.一10000這樣就得到了新種群的4個染色體基因型，如表9-2所示。新串4:10051110000表9-2復制操作之后的各項數(shù)據(jù)新串號復制種群（基因型）匹配對象（隨機選?。┙粨Q點（隨機選?。┬路N群（基因型）x值（表現(xiàn)型）適應(yīng)度匕⑴11110043111113110201000320101111230310011221000016250410011131000016250總計740平均185最大值250（5）.變異（mutation，又稱突變）變異是生物體中某一個或某幾個基因位變化，這種概率是很小的，在自然選擇中，通常是千分之幾或百分之幾。在人工選擇中，為了得到某個新品種，有時人工改變某幾個基因，而造成轉(zhuǎn)基因新物種。在遺傳算法中，變異就是隨機選取的串位的代碼由1變成0或由0變成1.變異操作可以防止染色體中丟失一些有用的遺傳因子，保證物種基因型的多樣型。在本例中，若變異概率設(shè)取為0.001，則對于種群的總共20個基因位（4個個體，每個個體有5位，所以總共有20位），期望的變異位數(shù)為20x0.001=0.02（位），所以本例無變異位。（6）.迭代經(jīng)過復制、變換、變異操作后得到新一代群種的基因型，對此群種再進行適應(yīng)度計算，這一過程稱為迭代。根據(jù)新一代個體的適應(yīng)度值，按照預先確定的評判規(guī)則來估計是否已得到最優(yōu)解？通常使用的評判規(guī)則如下：E（f（S1）,f（k））=Ma（f'+旦二Ma（f））＜e?（9-4），，Max（f（k））式中，E（fk+,fk）兩次迭代的相對誤差；Max（f（k）），Max（f（k+）分別為iiii第k次迭代和第k+1次迭代時各染色體的最大適應(yīng)度（從k=0開始），8——給定的評判標準（一般取百分之一到千分之一）。若相對誤差小于給定的標準，則遺傳算法便結(jié)束，輸出最優(yōu)解，否則繼續(xù)進行復制、變換和變異。在本例中，第一次迭代的最大適應(yīng)度Max（f⑴）=250，初始種群的最大適應(yīng)度Max（f（。））=238，由此計算出兩代種群最大適應(yīng)度的相對誤差為:250-250-238238=0.05若選擇8若選擇8=0.01，計算結(jié)果如表9-3所示。由表可知，這一次得到的新種群中，已有兩個染色體基因型保持未變，其適應(yīng)度仍為250.這就是說，本次計算的最大適應(yīng)度與上次相同，相對誤差為0，遺傳算法史結(jié)束，所得的最優(yōu)解是：x=16，f(x)=250。由此例可見，僅一次迭代便得到結(jié)果，遺傳算法的效率史很高的。表9-3第一次迭代以后的各項數(shù)據(jù)新串號復制概率fj￡f期望復制數(shù)f17ii復制Ri數(shù)復制種群(基因型)匹配對象交換點八、、新種群(基因型)x值適應(yīng)f度10.0130.0520010112301000819420.3111.24411000013100111923830.3381.35211000042100001625040.3381.352210000321000016250總計932平均233最大值250從數(shù)學分析可知，函數(shù)f(x)=-x2+31x+10勺極值點為x=15.5，最大函數(shù)值為Max(f(x))=250.?？梢娪眠z傳算法計算的結(jié)果也是很精確的。9?2模式定理在前節(jié)求f(x)=x2最大值的實例中，得到了一個深刻的印象：群體中個體的適應(yīng)度越高，其生存的機會就越多，而通過交叉操作，在下一代中產(chǎn)生了適應(yīng)度更高或者說性能更好的個體。在這一過程中，雖然隨機處理有助于這種優(yōu)化過程，但真正的原因或機制尚不清楚。從表2.1所描述的兩代進化過程中，可以發(fā)現(xiàn)第一代個體(11000)和次優(yōu)個體(10011)的隨機配對并在位置2互相交叉時，產(chǎn)生了新的更優(yōu)的個體(11011)。若再進一步觀察就會發(fā)現(xiàn)，新的個體的結(jié)構(gòu)模式(11011)與其父代個體(11***和***11)的結(jié)構(gòu)模式之間似乎有著一種十分有趣的聯(lián)系：1)它們的模式結(jié)構(gòu)有某種相似性；2)這些相似模板(similaritytemplates)都對應(yīng)高適應(yīng)值(高于群體的平均適應(yīng)度)。由此得到這樣直觀感覺：遺傳算法在搜索過程中一直在搜索群體中個體的某個重要的結(jié)構(gòu)相似性。于是，得到一個新的概念——相似模板，又稱模式(schema)。由此將導出遺傳算法中關(guān)鍵的基本理論模式定理。9.2.1模式模式是一個描述字符串集的模板，該字符串集中的串的某些位置上存在相似性。不失一般性，考慮二值字符集｛0,1｝，由此可產(chǎn)生通常的0，1字符串。現(xiàn)在增加一個符號“*”，稱作無關(guān)符或通配符，即“*”既可以當作“0”，又可以當作“1”。這樣，二值字符集就擴展為三值字符集｛0,1,*｝，由此可以產(chǎn)生如0110、0*11**、**01*0等字符串。定義2.1基于三值字符集｛0,1,*｝所產(chǎn)生的能描述具有某些結(jié)構(gòu)相似性的0、1字符串集的字符串稱為模式。以長度為5的串為例，模式*0001描述了在位置2、3、4、5具有形式“0001”的所有字符串，即｛00001,10001｝；又比如模式*1**0描述了在位置2為“1”和位置5為“0”的所有字符串，即｛01000，01010，01100，01110,11000，11010，11100，11110｝；而模式01010描述了只有一個串的集合，即｛01010｝。由此可以看出，模式的概念提供了一種簡潔的用于描述在某些位置上具有結(jié)構(gòu)相似性的0、1字符串集合的方法。這里需要強調(diào)的是，“*”只是一個描述符，而并非遺傳算法中實際的運算符號，它僅僅是為了描述上的方便而引入的符號而已。然而，模式概念的引入并不是僅僅為了描述上的方便。在引入模式概念前，我們所看到的遺傳算法是：在某一代中，N個互不相同的串在選擇、交叉、變異等遺傳算子作用下產(chǎn)生下一代的N個新的互不相同的串。那么，在兩代之間究竟保留了什么性質(zhì)，我們無從得知，因為我們所看到的串都是相互獨立的，互不聯(lián)系的。而引入模式概念后，我們看到一個串實際上隱含著多個模式(長度為l的串隱含著21個模式)，一個模式可以隱含在多個串中，不同的串之間通過模式而相互聯(lián)系。遺傳算法中串的運算實質(zhì)上是模式的運算。因此，通過分析模式在遺傳操作下的變化，就可以了解什么性質(zhì)被延續(xù)，什么性質(zhì)被丟棄，從而把握遺傳算法的實質(zhì)，這正是模式定理所要揭示的內(nèi)容。9.2.2模式定理如前所述，遺傳算法中串的運算實質(zhì)上是模式的運算。這一小節(jié)討論模式在選擇、交叉以及變異算子作用下的變化，進而導出模式定理。首先，我們給出模式的兩個重要概念：模式階(schemaorder)和定義距(definelength)0我們知道，一個串中隱含著多個不同的模式。確切地說，長度為l的串，隱含著2i個不同的模式，而不同的模式所匹配的串(稱作模式的樣本)的個數(shù)是不同的。比如模式011*1*與模式0*****相比，前者所匹配的串(樣本)的個數(shù)比后者少，即前者的確定性高。為了反映這種確定性的差異，我們引入模式階的概念。定義2.2模式H中確定位置的個數(shù)稱作該模式的模式階，記作0(H)。比如模式011*1*的階數(shù)為4，而模式0*****的階數(shù)為1。顯然，一個模式的階數(shù)越高，其樣本數(shù)就越少，因而確定性越高。但是，模式階并不是反映模式的所有性質(zhì)。以后將看到，即使具有同階的模式，在遺傳操作下，也會有著不同的性質(zhì)。為此，我們再引入定義距概念。定義2.3模式H中第一個確定位置和最后一個確定位置之間的距離稱作該模式的定義距，記作(H)o比如模式011*1*的定義距為4，而模式0*****為0o模式階和定義距描述了模式的基本性質(zhì)。有了這兩個概念，就可以開始討論模式在遺傳操作下的變化。令A(t)表示第t代中串的群體，以A.(j=1,2,??n)表示一代中第j個個體串。首先，我們探討選擇操作對模式的作用。假設(shè)在第t代，群體A。）中模式H所能匹配的樣本數(shù)為m,記作m（H,t）。在選擇中，一個串是根據(jù)其適應(yīng)度進行復制的。更確切地說，一個串是以概率Pi=f/lfj進行選擇的，其中f是個體A^（t）的適應(yīng)度。假設(shè)一代中群體大?。ㄈ后w中個體的總數(shù)）為〃，且個體兩兩互不相同，則模式H在第t+1代中的樣本數(shù)m（H,t+1）為m（H,t+1）=m（H,t）?n-f（H）/Xfj（9-2）其中f（H）是模式H所有樣本的平均適應(yīng)度。令群體平均適應(yīng)度為f=Xf「n，則有m（H,t+1）=m（H,t）?f（H）；f（9-3）可見，模式的增長（減少），即樣本數(shù)的增加（減少），依賴于模式的平均適應(yīng)度與群體適應(yīng)度之比，那些適應(yīng)度高于群體平均適應(yīng)度的模式將在下一代中得以增長；而那些適應(yīng)度低于群體平均適應(yīng)度的模式將在下一代中減少?，F(xiàn)在，假設(shè)模式H的適應(yīng)度一直高于群體平均適應(yīng)度，且設(shè)高出部分為cf,c為常數(shù)，則有m（H,t+1）=m（H,t）?[+cf）f=m（H,t）?G+c）（9-4）假設(shè)從t=0開始，c保持為常值，則有m（H,t+1）=m（H,0）?G+c）+1（9-5）可見，在選擇算子作用下，適應(yīng)度高于群體平均適應(yīng)度的模式將呈指數(shù)級增長，而適應(yīng)度低于群體適應(yīng)度的模式將呈指數(shù)級減少。以上，我們討論了模式在選擇中的變化。然而僅僅有選擇操作，并不能產(chǎn)生新的個體，即不能對搜索空間中新的區(qū)域進行搜索，因此引入了交叉操作。下面討論模式在交叉算子作用下所發(fā)生的變化，這里只考慮單點交叉的情況。為了討論方便，不妨考慮一個長度為6的串以及隱含其中的兩個模式：A=010110其=*1***0H=***11*假定A被選中進行交叉，而交叉點等概率產(chǎn)生，即交叉點落在1、2、3、4、5的概率相同。這里不妨假設(shè)交叉點為3,即交叉發(fā)生在位置3和位置4之間，并以分隔符“I”表示交叉位置，即有A=010I110其=*1*I**0h2=***I11*在這種情況下，除了與A進行交叉的串（稱之為配偶）在確定位（比如位置2、6）相同（這種可能性我們暫且不考慮）外，模式H]將遭到破壞，因為位置2的“1”和位置6的“0”在交叉產(chǎn)生的子代個體中將被替代為不同的值。比如A的配偶為A=101001，則產(chǎn)生的后代為A1=010001,A2=101110,都不是H1的樣本，即發(fā)生交叉后，模式H1丟失了。而相同的情況下，H2卻依然存在，因為不論A的配偶為任何串，H2中確定位4的“1”和確定位5的“1”都將一塊傳入子代。假若交叉點在位置4,H2不也會遭到破壞嗎？不錯！但有一點可以看出，由于交叉點等概率產(chǎn)生，模式H1遭破壞的概率(在位置2、3、4、5交叉都遭到破壞)大大超過模式H2(只在位置4交叉遭破壞)，即H2的生命力要強于H］。現(xiàn)在定量地討論一下。我們注意到模式H1的定義距為4,那么交叉點在6-1=5個位置隨機產(chǎn)生時，H1遭破壞的概率為Pd=5(H1)/(Z-1)=4/5，換句話說，其生存概率為1/5；而模式H2的定義距為1，則H2遭破壞的概率為Pd=8(H2)/(l-1)=1/5，即生存概率為4/5。更一般地講，模式H只有當交叉點落在定義距之外才能生存。在簡單交叉(單點交叉)下的H的生存概率P==1-8(H)/(l-1)。而交叉本身也是以一定概率Pc發(fā)生的，所以模式H的生存概率為TOC\o"1-5"\h\zP=1-P..(H).(/-1)(9-6)現(xiàn)在考慮先前暫且忽略的可能性，即交叉發(fā)生在定義距內(nèi)，模式H不被破壞的可能性。在前面的例子中，若A的匹偶在位置2、6上有一位與A相同，則弓將被保留。考慮到這一點，式(2.6)給出的生存概率只是一個下界，即有P>1-P-8(H)/0-1)(9-7)式(2.7)描述了模式在交叉算子作用下的生存概率?，F(xiàn)在考慮模式H在選擇和交叉算子的共同作用下的變化。參照式(9-3)和(9-7)，則有\(zhòng)o"CurrentDocument"m(H,t+1)=m(H,t).l(HVf)G-P-5(H)/(/-1))(9-8)由式(2.8)可以看出，在選擇和交叉算子的共同作用下，模式的增長(減少)取決于兩個因素：1)模式的適應(yīng)度是否高于群體平均適應(yīng)度，2)模式是否具有較短的定義距。顯然，那些適應(yīng)度高于群體平均適應(yīng)度、具有短定義距的模式將呈指數(shù)級增長。最后考慮變異操作。假定串的某一位置發(fā)生改變的概率為Pm，則該位置不變的概率為1-Pm，而模式H在變異算子作用下若要不受破壞，則其中所有的確定位置(為“0”或“1”的位)必須保持不變。因此模式H保持不變的概率為1-PmO(H)，其中0(H)為模式H的階數(shù)。模式H在變異算子作用下的生存概率為P=1-O(H)?P(9-9)綜上所述，模式H在遺傳算子選擇、交叉和變異的共同作用下，其子代的樣本數(shù)為m(H,t+1)=m(H,t).(f(H)/f)G—P-5(H)/(/-1)-O(H)?P)(9-10)式(9-10)忽略了極小項(P-8(H)/。-1)?O(H)?P)。通過式(9-10)，就可以給出以下模式定理。定理2.1(模式定理)在遺傳算子選擇、交叉和變異的作用下，具有低階、短定義距以及適應(yīng)度高于群體平均適應(yīng)度的模式在子代中將以指數(shù)級增長。模式定理是遺傳算法的理論基礎(chǔ)，其意義是深遠的。為了很好地理解該定理，下面通過一個實例來觀察遺傳算法對模式的處理情況。采用2.1節(jié)中的求f(x)=x2最大值的實例。假定x的取值范圍為［0,31］，則x可編碼為5位二進制數(shù)。給定4個初始串，然后施加選擇、交叉、變異操作，有關(guān)的串處理過程由表2.1表示，模式處理由表2.2表示?？疾?個模式：氣=1****、h2=*10**和h3t***°的運行情況。首先來看H在遺傳操作下的變化。在選擇階段，各串按照其適應(yīng)度在群體適應(yīng)度中所占的比例進行復制(比例復制法)。觀察表9-1和表9-2,可以看出，由于串2的適應(yīng)度大，其復制概率高，經(jīng)過選擇被復制成2份，而串3則丟失了。注意到串2、4都是H1的樣本，這樣通過選擇后，H1的樣本增至為3。由模式定理，理論上應(yīng)有m-f(H)/f個樣本，其中f(H)=(576+361)/2=468.5，而f為293，則H在選擇算子作用下應(yīng)有2X468.5/293=3.2*3個樣本，與實際相符。進一步可以看到，由于H1的定義距為0，交叉操作對H1的樣本沒有任可影響。而對于變異操作，在變異概率為Pm=0.001的情況下，H1的3個樣本遭破壞的概率為3X0.001=0.003，可以認為不發(fā)生變異。事實上，我們看到子代中有3個H的樣本11001、11011、10000，H的樣本數(shù)的確如模式定理所預計的呈指數(shù)級增長。那么模式H2、H3呢？H2的初始樣本數(shù)為2,在選擇算子作用下，樣本數(shù)仍為2。這與模式定理所預計的2X320/293=2.18q一致。而模式H3的初始樣本數(shù)為1，預表9-2遺傳算法對模式的處理模式表示串代表(見表2.1)選擇前選擇后下一代模式平均適應(yīng)度f(H)期望個數(shù)實際個數(shù)串代表期望個數(shù)實際個數(shù)串代表H11****2,44693.2032,3,43.2032,3,4H2*10**2,33202.1822,31.6422,3H31***025761.9722,3014期值為1X576/293=1.97以與實際值相符。下面來看交叉操作。盡管H2和弓的階數(shù)相同，選擇后的樣本數(shù)也相同，但由于兩個模式的定義距不同，在交叉算子作用下的結(jié)果也不同。對于H2，由模式定理，其預期值應(yīng)為m(H2,t+1)=2.18X(1-1/4)=2.18X0.75=1.64*2，實際上，最終％的兩個樣本都得以保留。而對于H3，其預期值為m(H3,t+1)=1.97?(1-4/4)=0，但事實上，H3有一個樣本得以保留(10000)。這似乎與模式定理不相符，但應(yīng)該強調(diào)的是，模式定理給出的只是一個下界，H3之所以有一個樣本能生存，是因為H3的樣本11000的配偶10011在H3的確定位(位置1、5)并不互補。盡管如此，我們也可以看出，由于H2具有較短的定義距，其生命力強于H3。以上通過一個實例證實了模式定理的正確性。在遺傳算子的作用下，低階、短距、高平均適應(yīng)度的模式以指數(shù)級數(shù)增長。但為什么這樣一種性質(zhì)就有利于找到全局最優(yōu)解呢?第三章將從遺傳算法的收斂性方面來討論這個問題。9.3進化規(guī)劃60年代中期，L.J.Fogel等人為有限狀態(tài)機的演化提出了進化規(guī)劃來求解預測問題a,這些機器的狀態(tài)變換表是通過在對應(yīng)的離散、有界集上進行均勻隨機變異來修改。進化規(guī)劃根據(jù)被正確預測的符號數(shù)來度量適應(yīng)值。通過變異，父代群體中的每個機器產(chǎn)生一個子代，父代和子代中最好的那一半被選擇生存下來。基于正態(tài)分布變異，D.B.Fogel將進化規(guī)劃也擴展到解實值問題。表示法和適應(yīng)值度量進化規(guī)劃首先假設(shè)目標變量向量X(即個體)存在于一個有界子空間HU,y]uRn，i=1其中u<v，，Rn為n維實數(shù)空間，然后將目標變量向量X的搜索區(qū)域擴展到Rn，即XWRn。進化規(guī)劃把個體的函數(shù)值/(X)通過比例變換到正值，同時加入某個隨機變量。來得到個體的適應(yīng)值?(x)=6(f(x),6)，其中0是比例函數(shù)。變異標準進化規(guī)劃采用的是高斯變異算子，它對個體X的每個分量X.作用一個標準偏差，標準偏差值是個體適應(yīng)值?(X)的一個線性變換的平方根。個體x的變異操作表示為m(x)=x，其中X，為變異后的子代個體，X=X+C-N(0,1),i=1,2,…，n,(9-11)iiiib.=七B..①(x)+r,i=1,2,...,n。(9-12)式中N(0,1)表示對每個下標i都重新采樣且具有期望值為0、標準偏差為1的正態(tài)分布隨機變量，系數(shù)乃.，r,是特定參數(shù)，一般將乃.和r,分別置為1和0。IIII選擇在"個父代個體每經(jīng)過一次變異產(chǎn)生"個子代后，進化規(guī)劃利用一種隨機q競爭選擇方法從父代和子代的集合中選擇"個個體，其中q31是選擇算法的參數(shù)。具體選擇過程如下：對每個個體X.EP(t)UP’(t)，其中P(t)與P’(t)分別是父代集合和子代集合，從P(t)UP’(t)k中隨機選擇q個個體，把它們按適應(yīng)值與Xk的適應(yīng)值進行比較，計算出其中比七差的個體數(shù)目*，并把*作為Xk的得分，*￡{0,...,q}；在所有2"個個體都經(jīng)過了這個比較過程后，按得分嗎(沱{1,2,...,2"})的高低順序?qū)€體排序；選擇前"個得分高的個體作為新一代群體，這樣最好的個體就能夠保證生存下來。綜上所述，進化規(guī)劃可描述為：t=0初始化P(0)={x1(0),...,X"(0)}度量P(0){?(x1(0)),.,?(X"(0))},其中?(Xk(0))=5(f(Xk(0)),3k)while(a(P(t))^T)do變異：x'(t)=m(x(t))，k=1,2,...,"kk度量：p。)具卜),...,普)}：Wq))...,從仲))}其中^^x'kg))=5qq。))氣)選擇：P(t+1)=S{}G(t)uP(t))t=t+1end9.4進化策略進化策略(ES)的研究始于1964年，當初主要是用于試驗處理流體動力學問題，如彎管形態(tài)優(yōu)化。在ES的發(fā)展中，Rechenberg和Schwefel做出了重要貢獻[44]:Rechenberg對稱為(1+1)-ES的進化策略發(fā)展了收斂速度理論，(1+1)-ES是一個簡單變異選擇機制，它每代通過高斯變異作用在一個個體上來產(chǎn)生一個子代。Rechenberg還首先提出了(^+1)-ES，這個策略是將MN>1)個個體經(jīng)過選擇形成的一個子代替換掉變異后最差的父代個體。Schwefel在此基礎(chǔ)上提出(N+入)-ES和(此入)-ES，前者是針對多父體和子體的，在算法過程中，|^個父體產(chǎn)生入個子體，這N+入個候選解同時參加竟爭并適者生存(一般生存數(shù)目為^)；后者也是針對多父體和子體的，在算法過程中，|^個父體產(chǎn)生入個子體，但只有這入個候選解竟爭，然后父體被完全取代，也即每個候選解的生命期只限在當前一代。這兩種策略(尤其是后者)在進化策略中占據(jù)著重要地位。表示法和適應(yīng)值度量在進化策略中，搜索點是n維向量x￡加，個體的適應(yīng)度值等于其目標函數(shù)值，即?(a)=f(x)，其中x是個體a的目標變量部分。此外，每個個體可以包括至多n個不同的方差C=b2(i=1,2,...,n)和至多n(n-1)/2個協(xié)方差C^(z=1,2,_,n,j=i+1,...,n)，從而有至多w=n(n+1)/2個策略參數(shù)可以和目標變量組合在一起構(gòu)成一個個體ad=Rn+w。不過，一般只考慮方差，從而aeI=R2n，有時甚至對所有目標變量只用一個共同的方差，這時ad=Rn+1。變異在進化策略中，全體a=｛x,b｝在變異算子的作用下變?yōu)閍7=(x\b’｝，其中b，=b-expC-N(0,1)+t?N(0,1))i=1,2,...,n(9-13)x'=x+N。0,b),i=1,2,...,n(9-14)iii式中N(0,1)表示具有期望值為0、標準偏差為1的正態(tài)分布隨機變量，t和t’是算子集參數(shù)，分別定義整體和個體步長。交叉在進化策略中，交叉算子己山一I可以按下列方式產(chǎn)生一個個體：尤s”x'=\xorxiS,i(T,ixx+oj-x)vS,iT,iS,i下標S和T指從P(t)中隨機選取的兩個父代個體，6e[0,1]為均勻隨機變量。選擇在進化策略中，選擇是按完全確定的方式進行。(莊入)-ES是從入個子代個體集中選擇貝1W^W入)個最好的個體；S+入)-ES是從父代和子代個體的并集中選擇|^個最好的個體。雖然S+入)-ES保留最優(yōu)的個體能保證性能單調(diào)提高，但這種策略不能處理變化的環(huán)境，因此，目前選用最多的還是(此入)-ES。從上面的討論，可以得到S+入)-ES和(此入)-ES的形式描述：t=0初始化R0)={%(0),…，匕(0)}￡川度量尸(0){0(ai(0)),…，0風(0))},其中?(氣(0))=f(xk(0))while(a(P(t))^T)do交叉：a(t)=r'(P(t))，k=1,2,…，入k變異：a(t)=m(a(t))，k=1,2,...,入kk度量：P(t)=1；(t),...,a人(t)}：0(a；(t))...,0。人(t)》其中0(r(t))=fCr(t))選擇：if(莊入)-ESthenP(t+1)=XG())lu，入}elseP(+1)=SG(t)uP”(t)){u+A)t=t+1end在進化策略中，候選解的各個組成部分不像在GA中被認為是基因信息，而被看作是染色體行為的特性；其連接的性態(tài)是不確定的，不管遺傳變換發(fā)生了什么，特性的改變(即候選解的各個組成部分的變化)只依賴于高斯變量。綜合前幾節(jié)所述，比較遺傳算法、進化規(guī)劃和進化策略，可以發(fā)現(xiàn)這三種算法既有許多相似之處，同時也有很大的不同。進化規(guī)劃和進化策略都把變異作為主要的操作算子，而在標準遺傳算法中，變異只處于次要地位；另一方面，交叉在標準遺傳算法中起著重要作用，而在進化規(guī)劃中則被完全省去，在進化策略中有三種方式。另外，標準遺傳算法和進化規(guī)劃都強調(diào)隨機選擇機制的重要性，而進化策略的選擇是完全確定的，沒有合理的根據(jù)表明隨機選擇原則的重要性。進化規(guī)劃和進化策略確定地把某個體排除在被選擇復制之外，而標準遺傳算法一般對每個個體都指定一個非零選擇概率。再者，進化策略與進化規(guī)劃相比，主要區(qū)別在于：進化策略著重于確定性的選擇，而進化規(guī)劃著重于群體中的競爭選擇。9?5遺傳規(guī)劃遺傳規(guī)劃(GeneticProgramming,GP)首先是J.R.Koza在設(shè)計最優(yōu)計算機程序(即最優(yōu)控制策略)時提出的⑸。GP采用的是一種樹編碼結(jié)構(gòu)，它已成功地用于進化非線性時間序列的預測模型。例如，Oakey擬合了Mackey-Glass方程產(chǎn)生的混沌時間序列㈣，Iba等提出用GP進行系統(tǒng)識別和預測［46］，Kargupta等提出了利用進化多項式得到預測函數(shù)網(wǎng)。本節(jié)從建立時間序列的一步預測模型的例子來介紹GP［48］。一步預測是在過去的時間序列值的基礎(chǔ)上進行的，把由(％,%，???，、)漲成的滯后空間中的點映射成將來值孔的估計，即~=f(x,x,,x)(9-15)此處t表示當前時間，，表示用于預測的時間跨度。一般地，f(?)是(xt-1,xt-2，...,、)的一個復雜的非齊次的函數(shù)。假設(shè)f(?)能被初等函數(shù)和算術(shù)算子近似地表示，f(?)就可以被描述成一棵“樹”，如圖2.2,樹的根部是一模型函數(shù)，樹的內(nèi)部節(jié)點(分支點)相應(yīng)于選擇函數(shù)(如+,-,*,/,sin,cos等初等函數(shù))，而樹的葉子是輸入變量(xt-i,%,...,%)。圖9-2的樹表示函數(shù)f(%,x2,x)=a*a*x*x+a*sin(a*x+a)，此處aaaaa是構(gòu)造個體模型期間自動插入的參數(shù)?！?I。。。IJ通過最優(yōu)地定義函數(shù)的形式和調(diào)節(jié)參數(shù)可以建立一個適合的預測算子，而GP用于時間序列預測就是搜索最優(yōu)的函數(shù)形式和最佳的調(diào)節(jié)參數(shù)。GP通過“產(chǎn)生和測試”過程產(chǎn)生和選擇候選模型。GP在每一代中執(zhí)行下面五個步驟。圖9-2函數(shù)的樹表示

父體A父體B子體A子體B圖9-3GP的交叉操作父體A父體B子體A子體B初始化隨機產(chǎn)生初始群體。步驟1交叉隨機地選擇一對個體作為父代，隨機選擇某一節(jié)點，將與該節(jié)點連接的部分染色體從父體上切割下來，切割的染色體片斷相互交換生成兩個新個體，即為子代，如圖9-3所示。子體模型繼承了它們父代的的函數(shù)形式。步驟2適應(yīng)度評估個體的適應(yīng)度一般定義為模型的輸出和訓練樣本序列氣之間誤差平方和的倒數(shù)，F(xiàn)itness=1(9-16)矣(f(x)一x)2+c-m<Fitness=1(9-16)式中xk=（xki，xk-2，，"Xk-T），kA，c是一常數(shù)，m是節(jié)點數(shù)步驟3選擇父代和子代個體根據(jù)適應(yīng)度排列，自然地選擇，具有高適應(yīng)度的個體生存下來，適應(yīng)度差的個體被剔除出去。排列選擇自動地保證了精華部分。步驟4變異隨機選擇樹內(nèi)部的一個節(jié)，節(jié)點的選擇函數(shù)被強迫改變，如圖9-4,個體C一節(jié)點的選擇函數(shù)“+”變異為“*”。

個體C個體C圖9-4GP的變異操作步驟5中止判斷如果最優(yōu)個體的適應(yīng)度達到預先設(shè)定的要求或重復次數(shù)達到預先設(shè)定值，則結(jié)束算法，這兩種情況下最后一代的最優(yōu)個體被認為是最適當?shù)哪Ｐ?。否則返回至步驟1繼續(xù)。9.6粒子群優(yōu)化算法9.6.1標準粒子群算法：粒子群算法與其他進化類算法相類似，也采用“群體”與“進化”的概念，同樣也是根據(jù)個體(微粒)的適應(yīng)值大小進行操作。所不同的是，粒子群算法不像其他進化算法那樣對于個體使用進化算子，而是將每個個體看作是在N維搜索空間中的一個沒有重量和體積的微粒，并在搜索空間中以一定的速度飛行。該飛行速度由個體的飛行經(jīng)驗和群體的飛行經(jīng)驗進行動態(tài)調(diào)整。設(shè)：X=G,x,...,x)為微粒i的當前位置；TOC\o"1-5"\h\zii1i2iNV=v,v,...,v)為微粒i的當前飛行速度；ii1i2iNP=^,P,...,P)為微粒i所經(jīng)歷的最好位置，稱為個體最好位置。pBest；

ii1i2iNigN設(shè)f(X)為最小化問題的適應(yīng)度函數(shù)，則微粒/的當前最好位置由P=gN設(shè)f(X)為最小化問題的適應(yīng)度函數(shù)，則微粒/的當前最好位置由D。為了討論方便，gBest式(9-15)確定P式(9-15)確定P(t+1)={P(t)X,(t+1)若f(X(t+1)Af(P(t))

若f(X\t+1)>f(P(t))ii(9-15)設(shè)群體中微粒數(shù)為M，則微粒群的全局最好位置由式(9-16)確定P(t)e{P(t),P(t),...，P(t斗f(P(t))=min{f(P(t))f(P(t))...，f(P(t))}(9-16)有了以上定義，標準粒子群算法的進化方程可描述為:v(t有了以上定義，標準粒子群算法的進化方程可描述為:v(t+1)=wVij(t)+cr》(t)—x(tY+cr》(t)—x(t)11aij22gjij(9-17)尤(t+1)=X(t)+V(t+1)(9-18)ijijij其中，下標“i”表示微粒i,“j”表示微粒的第j維，t表示第t代，W稱為慣性權(quán)重，c、c為加速常數(shù)，分別用來調(diào)節(jié)微粒飛向自身最好位置方向和全局最好位置方向的步長，r、r為兩個在［0，1］范圍內(nèi)互相獨立的隨機數(shù)。為了減少在進化過程中，微粒離開搜索空間的可能性，v..通常限定于一定范圍內(nèi)，即Ve〔V,V1ijijjmaxjmax由上式可以看出，公式(9-17)主要通過三部分來計算微粒i更新的速度：微粒i前一時刻的速度V(t)，微粒i當前位置與自己歷史最好位置之間的距離((t)-X(tJ。微粒i通過公式(9-18)計算新位置的坐標。微粒進化原理如圖9-5所示：9.6.2算法參數(shù)說明微粒的個數(shù)M:微粒種群大小的選擇視具體問題而定，但是一般設(shè)置微粒數(shù)為20-50，不過對于比較復雜或者特定類型的問題，微粒數(shù)也可以取到100或200。微粒的長度N:即是問題解空間的維數(shù)。微粒的最大速度u:微粒的速度在空間中的每一維上都有一個最大速度限制值Vmax，用來對微粒的速度進行鉗制使速度控制在LV,V］范圍內(nèi)，該值一般由用戶自己設(shè)定。V是一個非常重要的參數(shù)。如果V值太大，則微粒群也許會飛過最優(yōu)區(qū)域；另一方面如果V值太小，則微粒群可能就無法對局部最優(yōu)區(qū)域以外的區(qū)域進行充分的探測。實max際上，它們可能會陷入局部最優(yōu)，而無法移動足夠遠的距離跳出局部最優(yōu)達到空間中最佳的位置。假設(shè)搜索空間的第j維定義為區(qū)間LX,X］，則通常V=k-Xma，0.1<k<1.0，每一維都用相同的設(shè)置方法。慣性權(quán)重“:慣性權(quán)重“使微粒保持運動慣性，使其有擴展搜索空間的趨勢，有能力探索新的區(qū)域。引入慣性權(quán)重可消除算法對v的需要，因為它們的作用都是維護全局和局部搜索能力的平衡。這樣，當v增加時，可通過減少“來達到平衡搜索的目的。而“的減少可使得所需的迭代次數(shù)變小，從這個意義上看，可以將v.固定為每維變量的變化范圍，只對“進行調(diào)節(jié)。加速常數(shù)c、c:分別調(diào)節(jié)微粒向pBest，和gBest方向飛行的最大步長，決定微粒的個TOC\o"1-5"\h\z121體經(jīng)驗和群體經(jīng)驗對微粒運行軌跡的影響，反映微粒群之間的信息交流。改變這些常數(shù)會改變系統(tǒng)的“張力”，較低的c、c值使得微粒徘徊在遠離目標的區(qū)域，較高的c、c值產(chǎn)生1212陡峭的運動或越過目標區(qū)域。Kennedy在文獻［50］中研究了兩種參數(shù)的具體取值，經(jīng)過大量的實驗結(jié)果對比，指出c與c之和最好接近4.0，通常cwc=2.05。1212r「r2:為兩個在［0，1］范圍內(nèi)相互獨立的隨機數(shù)。迭代終止條件：一般設(shè)為最大迭代次數(shù)Tmax，或是當搜索過程中解的適應(yīng)度滿足精度要求￡時，終止算法。9.6.3算法流程Step1初始化微粒群：設(shè)定群體規(guī)模M，解空間維數(shù)N，隨機產(chǎn)生每個微粒的初始位置和速度；Step2用適應(yīng)度函數(shù)f(X)分別計算每個微粒的當前適應(yīng)值：Step3更新個體極值：對每個微粒的適應(yīng)值進行評價，即將第/個微粒的當前適應(yīng)值f(X,)與該微粒的個體極值pBest的適應(yīng)值進行比較，若前者優(yōu)，貝0更新pBest，否則保持pBest不變；Step4更新全局極值：從所有pBest1中選出最好的，作為全局極值gBest;Step5更新速度和位置：通過公式(9-17)、(9-18)來更新每個微粒的速度和位置；Step6檢查是否滿足中止條件，若滿足，則退出；否則，轉(zhuǎn)至Step2。標準微粒群算法的程序執(zhí)行流程可用下圖表示：

圖9-6標準粒子群算法程序流程圖與其他進化計算方法相比,POS算法的優(yōu)勢在于其計算的快速性和算法本身的易實現(xiàn)性，目前在各類多維搜索空間優(yōu)化問題上均取得了成功的應(yīng)用。9.6.4PSO算法與一些進化算法的比較(1)與遺傳算法的比較這兩種算法