【文章內(nèi)容簡介】 點數(shù)編碼方法是指個體的每個染色體用某一范圍內(nèi)的一個浮點數(shù)來表示，個體的編碼長度等于其問題變量的個數(shù)。因為這種編碼方法使用的是變量的真實值，所以浮點數(shù)編碼方法也叫做真值編碼方法。對于一些多維、高精度要求的連續(xù)函數(shù)優(yōu)化問題，用浮點數(shù)編碼來表示個體時將會有一些益處。格雷碼是其連續(xù)的兩個整數(shù)所對應(yīng)的編碼值之間只有一個碼位是不相同的，其余碼位都完全相同。例如十進(jìn)制數(shù)7和8的格雷碼分別為0100和1100，而二進(jìn)制編碼分別為0111和1000。符號編碼方法是指個體染色體編碼串的基因值取自一個無數(shù)值含義而只有代碼含義的符號集。這個符號集可以是一個字母表，如{A,B,C,D,……}；也可以是一個數(shù)字序號表，如{1,2,3,4,5,……}；還可以是一個代碼表，如{x1, x2, x3, x4, ……}，等等。第三節(jié) 群體設(shè)定遺傳算法中初始群體中的個體是隨機產(chǎn)生的。不失一般性，初始群體的設(shè)定可以采取下面的策略：l 根據(jù)問題固有知識，設(shè)法把握最優(yōu)解所占空間在整個問題空間的分布范圍，然后，在此分布范圍內(nèi)設(shè)定初始群體。 l 先隨機生成一定數(shù)目的個體，然后從中挑出最好的個體加到初始群體中。這種過程不斷迭代，直到初始群體中個體數(shù)目達(dá)到了預(yù)先確定的規(guī)模。 通過定理證明，在二進(jìn)制編碼的前提下，為了滿足隱含的并行性，群體個體數(shù)只要設(shè)定為即可，其中 n 為個體長度的一半。所以在實際應(yīng)用中，群體個數(shù)的取值范圍一般在幾十到幾百。另外，群體規(guī)模的確定受遺傳操作中選擇操作的影響很大。群體規(guī)模越大，群體中個體的多樣性越高，算法陷入局部解的危險就小。但是，群體過大，其適應(yīng)度評估次數(shù)增加，所以計算量也增加，從而影響算法效率。另一方面，如果群體規(guī)模太小，會使遺傳算法的搜索空間分布范圍有限，因此搜索有可能停止在未成熟階段，導(dǎo)致未成熟收斂。第四節(jié) 適應(yīng)度函數(shù)遺傳算法在進(jìn)化搜索中基本上不用外部信息，僅僅使用目標(biāo)函數(shù)即適應(yīng)度函數(shù)為依據(jù)。遺傳算法的目標(biāo)函數(shù)不受連續(xù)可微的約束且定義域可以為任意集合。對目標(biāo)函數(shù)的唯一要求是，針對輸入可計算出能加以比較的結(jié)果，而且結(jié)果為非負(fù)。一、 目標(biāo)函數(shù)到適應(yīng)度函數(shù)的映射在許多問題中，目標(biāo)是求費用函數(shù)g(x)的最小值。即使某一問題可自然的表示成求最大值形式，也不能保證對于所有的 x,使 f(x)取非負(fù)值。但是遺傳算法中，適應(yīng)度函數(shù)要進(jìn)行比較排序并且在此基礎(chǔ)上計算選擇概率，所以適應(yīng)度函數(shù)的值要取正值。因此必須將目標(biāo)函數(shù)映射成求最大值形式且適應(yīng)度函數(shù)值非負(fù)。 在通常情況下，為了把一個最小化問題轉(zhuǎn)化為最大化問題，只需要簡單的把原函數(shù)乘以1 即可，但對遺傳算法而言，這種方法還不足以保證在各種情況下的非負(fù)值。對此，可以采用以下的方法進(jìn)行轉(zhuǎn)換： 當(dāng) 其他情況 ()有多種方法來選擇系數(shù)?？梢允且粋€合適的輸入值，也可以采用迄今為止進(jìn)化過程中g(shù)(x)的最大值或當(dāng)前群體中g(shù)(x)的最大值。最好與群體無關(guān)。二、適應(yīng)度尺度變換（適應(yīng)度函數(shù)定標(biāo)）應(yīng)用遺傳算法時，常常會出現(xiàn)一些不利于優(yōu)化的現(xiàn)象或結(jié)果。在遺傳進(jìn)化的初期，通常出現(xiàn)一些超常的個體，這些異常個體有可能在群體中占據(jù)很大的比例，因而可能導(dǎo)致未成熟收斂現(xiàn)象。這是因為這些異常個體競爭力太突出控制了整個選擇過程，從而影響了算法的全局優(yōu)化性能。針對上述情況，可以通過放大或縮小相應(yīng)的適應(yīng)度函數(shù)值來進(jìn)行改進(jìn)。這種對適應(yīng)度的縮放調(diào)整稱作適應(yīng)度定標(biāo)。通常采用的定標(biāo)方式為：① 線性定標(biāo)：； ()② σ 截斷： ()③ 乘冪定標(biāo)： ； ()第五節(jié) 遺傳操作一、選擇算子從群體中選擇優(yōu)勝的個體，淘汰劣質(zhì)個體的操作叫做選擇。選擇算子又 叫再生算子（Reproduction Operator）。選擇的目的是把優(yōu)化的解直接遺傳到下一代或者通過配對交叉產(chǎn)生新的個體再遺傳到下一代。選擇操作是建立在群體中個體的適應(yīng)度評估基礎(chǔ)上的，目前常用的選擇算子有：1． 適應(yīng)度比例方法（Fitness proportional model）適應(yīng)度比例方法是目前遺傳算法中最基本最常用的選擇方法。它也叫賭輪（roulette wheel）或蒙特卡羅（Monte Carlo）選擇[1]。 設(shè)群體大小為n,其中個體i的適應(yīng)度值為,則i被選擇的概率為: ()可見反映了個體i的適應(yīng)度在整個群體的個體適應(yīng)度總和中所占的比例。個體適應(yīng)度越大，被選擇的概率就越高。2． 最佳個體保存方法（Elitist model）此方法的思想是把群體中適應(yīng)度最高的個體不進(jìn)行配對交叉而直接復(fù)制到下一代中。采用這種選擇方法的優(yōu)點是：進(jìn)化過程中某一代的最優(yōu)解可以不被交叉和變異操作所破壞。但是，這是這樣可能隱含了一種危機——導(dǎo)致早熟，即局部最優(yōu)個體的遺傳基因會急速增加而使進(jìn)化有可能限于局部解。也就是說，該方法的全局搜索能力不強，它更加適合于單峰性質(zhì)的搜索空間搜索。一般將這種方法與其它一些選擇操作配合起來使用，才能有良好的效果。 另外，最佳個體保存方法還可加以推廣，即在每一代的進(jìn)化過程中保留多個最優(yōu)個體不參加交叉、變異等遺傳操作，而直接將它們復(fù)制到下一代群體中。這種選擇方法也稱為穩(wěn)態(tài)復(fù)制。3． 排序選擇方法（Rankbased）排序選擇方法是指在計算每個個體的適應(yīng)度后，根據(jù)適應(yīng)度大小順序?qū)θ后w中個體排序，然后把事先設(shè)計好的概率表按順序分配給個體，作為各自的選擇概率。這種方法的不足之處在于選擇概率和序號的關(guān)系必須事先確定。此外，它和適應(yīng)度比例方法一樣都是一種基于概率的選擇，所以仍然有統(tǒng)計誤差。此外還有一些比較常用的選擇方法如期望值方法（Expected value model）、聯(lián)賽選擇方法（Tournament selection model）等。二、交叉算子1．交叉算子的設(shè)計 實現(xiàn)個體結(jié)構(gòu)重組的交叉算子設(shè)計一般與所求解的具體問題有關(guān)，一般包括以下一些要點： ① 任何交叉算子需要滿足交叉算子的評估準(zhǔn)則，就是說交叉算子需要保證前一代中優(yōu)秀個體的性狀能在后一代的新個體中盡可能得到遺傳和繼承。 ② 交叉設(shè)計和編碼設(shè)計是相互聯(lián)系的。也就是說，交叉算子設(shè)計和編碼設(shè)計需協(xié)調(diào)操作。這也就是所謂的編碼——交叉設(shè)計。2．基本的交叉算子① 一點交叉（One point crossover） 一點交叉又叫做簡單交叉。具體的操作是：在個體串中隨機設(shè)定一個交叉點，實行交叉的時候，該點前或后的兩個個體的部分結(jié)構(gòu)進(jìn)行互換，并生成兩個新的個體。② 二點交叉（Two point crossover） 二點交叉與一點交叉類似，只是設(shè)值2個交叉點（隨機設(shè)定）。③ 一致交叉（Uniform crossover） 一致交叉是指通過設(shè)定屏蔽字（mask）來決定新個體的基因繼承兩個舊個體中哪個個體的對應(yīng)基因。④ 算術(shù)交叉（Arithmetic Crossover） 算術(shù)交叉是指由兩個個體的線性組合而產(chǎn)生出兩個新的個體。為了能夠進(jìn)行線性組合運算，算術(shù)交叉的操作對象一般是由浮點數(shù)編碼所表示的個體。3．交叉算子與遺傳算法的收斂型 遺傳算法的收斂性不僅取決于編碼，初始化群體，適應(yīng)度函數(shù)，選擇算子的設(shè)計，而且還取決于交叉算子和下面要提到的變異算子。但是，遺傳算法的收斂性主要決定于作為其核心操作的交叉算子。交叉算子收斂性是遺傳算法研究中最重要的課題之一。需要指出的是，交叉算子并未提供收斂性保證。三、變異算子變異操作的基本內(nèi)容是對群體中的個體串的某些基因座上的基因值作變動。例如，基于字符集{0,1}的二值碼串，變異操作就是把 1 變成 0 或者把 0 變成1。變異操作的步驟為：在群體中所有個體的碼串范圍內(nèi)隨機的確定基因座，然后以事先設(shè)定的變異概率對這些基因座的基因值進(jìn)行變異。遺傳算法引入變異的目的有兩個：一個是使遺傳算法具有局部的隨機搜索能力。當(dāng)遺傳算法通過交叉算子已接近最優(yōu)解臨近值時，利用變異算子的這種局部隨機搜索能力可以加速向最優(yōu)解收斂。這種情況下變異概率應(yīng)取較小值，否則已經(jīng)接近最優(yōu)解的值會因為變異而遭到破壞。二是使遺傳算法可以維持群體多樣性，以防止出現(xiàn)早熟現(xiàn)象。 遺傳算法中，交叉算子因為其全局搜索能力作為主要算子，變異算子因其局部搜索能力作為輔助算子。遺傳算法通過交叉和變異這一對相互配合又相互競爭的操作而使其具備兼顧全局和局部的均衡搜索能力。第六節(jié) 遺傳算法的性能分析目前，遺傳算法的評估指標(biāo)大多采用適應(yīng)度值。特別在沒有具體要求的情況下，一般采用各代中最優(yōu)個體的適應(yīng)度值和群體的平均適應(yīng)度值。普遍使用的兩個定量分析指標(biāo)是遺傳算法的離線性能（offline performance）和在線性能（online performance）[11]。前者測量收斂性，后者測量動態(tài)性能。一般來說，在離線應(yīng)用時，優(yōu)化問題的求解可以得到模擬，在一定的優(yōu)化進(jìn)程停止準(zhǔn)則下，當(dāng)前最好的解可以被保存和利用；在在線應(yīng)用中，優(yōu)化問題的求解必須通過真實的實驗在線實現(xiàn)，其好處在于可以迅速的得到較好的優(yōu)化結(jié)果。一、在線性性能評估 設(shè)為環(huán)境e下策略s的在線性能，為時刻t 或第t代相應(yīng)于環(huán)境e的目標(biāo)函數(shù)或平均適應(yīng)度函數(shù)，則可以表示為 ()上式表明，在線性能可以用從第一代到當(dāng)前代的優(yōu)化進(jìn)程的平均值來表示。例如，若在線性能用平均適應(yīng)度表示，那么通過簡單計算從第一帶到當(dāng)前代的各代平均適應(yīng)度值對代數(shù)的平均值即可獲得在線性能。二、離線性能評估 設(shè)為環(huán)境e下策略s的離線性能，則可表示為： ()其中，上式表明，離線性能是特定時刻最佳性能的累計平均。具體地說，在進(jìn)化過程中每進(jìn)化一代就統(tǒng)計目前為止的各代中的最佳適應(yīng)度或最佳平均適應(yīng)度，并計算對進(jìn)化代數(shù)的平均值。第三章 遺傳算法的求解構(gòu)造步驟及應(yīng)用舉例第一節(jié) 遺傳算法的求解步驟一、遺傳算法的偽碼描述和形式化定義基本遺傳算法可定義為一個8元組： 式中: C——個體的編碼方法； E——個體適應(yīng)度評價函數(shù)； P0——初始群體； M——群體大??；——選擇算子：——交叉算子：——變異算子：T——遺傳運算終止條件：Procedure SGA begin initialize P(0)； t=0： while(t≤T) do for i=l to M do Evaluate fitness of P(t)； endfor for i=l to M do Select operation to P(t)； endfor for i=1 to M／2 do Crossover operation toP(t)； endfor for i=1 to M do Mutation operation t0 P(t)； endfor for i=1 to M do P(t+1)=P(t) endfor t=t+1：end whileend二、遺傳算法的求解步驟及其框圖基本遺傳算法遵循以下求解步驟：1. 初始化種群；2. 計算種群上每個個體的適應(yīng)度值；3. 按由個體適應(yīng)度值所決定的某個規(guī)則選擇進(jìn)入下一代的個體；4. 按概率Pc進(jìn)行交叉操作；5. 按概率Pm進(jìn)行變異操作；6. 若沒有滿足某種停止條件，則轉(zhuǎn)步驟（2），否則進(jìn)入下一步；7. 輸出種群中適應(yīng)度最優(yōu)的染色體作為問題的滿意解或最優(yōu)解?；镜倪z傳算法框圖如圖31所示，其中GEN是當(dāng)前代數(shù)。 圖31 基本遺傳算法框圖第二節(jié) 遺傳算法的構(gòu)造步驟 遺傳算法提供一種求解復(fù)雜系統(tǒng)優(yōu)化問題的通用框架．它不依賴于問題的領(lǐng)域和種類。對一個需要進(jìn)行優(yōu)化計算的實際應(yīng)用問題，一般可按下述步驟來構(gòu)造求解該問題的遺傳算法。 第一步：確定決策變量及其各種約束條件，即確定出個體的表現(xiàn)型X和問題的解空間。 第二步：建立優(yōu)化模型，即確定出目標(biāo)函數(shù)的類型(是求目標(biāo)函數(shù)的最大值還是求目標(biāo)函數(shù)的最小值?)及其數(shù)學(xué)描述形式或量化方法。 第三步：確定表示可行解的染色體編碼方法，也即確定出個體的基因型X及遺傳算法的搜索空問。 第四步：確定解碼方法，即確定出由個體基因型X到個體表現(xiàn)型X的對應(yīng)關(guān)系或轉(zhuǎn)換方法。 第五步：確定個體適應(yīng)度的量化評價方法，即確定出由目標(biāo)函數(shù)值f(x)到個體適應(yīng)度F(x)的轉(zhuǎn)換規(guī)則。 第六步：設(shè)計遺傳算子，即確定出選擇運算、交叉運算、變異運算等遺傳算子的具體操作方法。 第七步：確定遺傳算法的有關(guān)運行參數(shù)，即確定出遺傳算法的M、T、pc、pm等參數(shù)。由上述構(gòu)造步驟可以看出，可行解的編碼方法、遺傳算子的設(shè)計是構(gòu)造遺傳算法時需要考慮的兩個主要問題，也是設(shè)計遺傳算法時的兩個關(guān)鍵步驟。對不同的優(yōu)化問題需要使用不同的編碼方法和不同操作的遺傳算子．它們與所求解的具體問題密切相關(guān)．因而對所求解問題的理解程度是遺傳算法應(yīng)用成功與否的關(guān)鍵。 圖32遺傳算法主要構(gòu)造過程示意圖第三節(jié) 基本遺傳算法在函數(shù)優(yōu)化中的應(yīng)用舉例例：Rosenbrock函數(shù)的全局最大值計算。 Max () . ( i=1，2) ()如圖33所示，該函數(shù)有兩個局部極大點，分別是f(，－)=(－，－)=，其中后者為全局最大點。 圖33 Rosenbr