第四講 軟計(jì)算方法

第四講軟計(jì)算方法第1頁，共40頁，2023年，2月20日，星期三第2頁，共40頁，2023年，2月20日，星期三第3頁，共40頁，2023年，2月20日，星期三第4頁，共40頁，2023年，2月20日，星期三第5頁，共40頁，2023年，2月20日，星期三第6頁，共40頁，2023年，2月20日，星期三第7頁，共40頁，2023年，2月20日，星期三第8頁，共40頁，2023年，2月20日，星期三4.1編碼方法編碼是應(yīng)用遺傳算法要解決的首要問題,也是設(shè)計(jì)遺傳算法的關(guān)鍵.編碼方法除了決定個體的染色體排列形式以外,它還決定了個體從搜索空間的基因型轉(zhuǎn)換到解空間的表現(xiàn)型時(shí)的解碼方法.編碼方法也影響到交叉算子、變異算子等遺傳算子的運(yùn)算方法因此，編碼方法在很大程度上決定了如何進(jìn)行群體的遺傳進(jìn)化運(yùn)算以及遺傳進(jìn)化運(yùn)算效率。第9頁，共40頁，2023年，2月20日，星期三迄今為止，人們已經(jīng)提出了很多種不同的編碼方法，這些編碼方法可以分為三大類：

二進(jìn)制編碼方法浮點(diǎn)數(shù)編碼方法符號編碼方法第10頁，共40頁，2023年，2月20日，星期三二進(jìn)制編碼方法二進(jìn)制編碼方法是遺傳算法中最常用的一種編碼方法，它使用的編碼符號集為{0，1}，它所構(gòu)成的個體基因型是一個二進(jìn)制編碼符號串。二進(jìn)制編碼符號串的長度與問題要求的求解精度有關(guān)。假設(shè)一參數(shù)的取值范圍是我們用長度為的二進(jìn)制表示該參數(shù)

第11頁，共40頁，2023年，2月20日，星期三二進(jìn)制編碼的精度為第12頁，共40頁，2023年，2月20日，星期三第13頁，共40頁，2023年，2月20日，星期三二進(jìn)制編碼方法的優(yōu)點(diǎn)：編碼、解碼操作簡單可行交叉、變異等遺傳操作便于實(shí)現(xiàn)符合最小字符集編碼原則便于利用模式定理對算法進(jìn)行理論分析第14頁，共40頁，2023年，2月20日，星期三浮點(diǎn)數(shù)編碼方法

對于一些多維、高精度要求的連續(xù)函數(shù)優(yōu)化問題，使用二進(jìn)制編碼來表示個體時(shí)會有一些不利之處：

(1)使用二進(jìn)制編碼存在著連續(xù)函數(shù)離散化時(shí)的映射誤差

(2)個體編碼串較短時(shí)，可能達(dá)不到精度要求；而個體編碼串的長度較長時(shí)，雖然能提高編碼精度，但卻會使遺傳算法的搜索空間急劇擴(kuò)大

第15頁，共40頁，2023年，2月20日，星期三例:使用二進(jìn)制方法來處理一個含有100個決策變量的優(yōu)化，每個決策變量的取值范圍是[-250,250],要求精度是小數(shù)點(diǎn)后面五位，即為0.00001,則為26這樣每個個體必須用2600位長的二進(jìn)制編碼符號串來表示。相應(yīng)的搜索空間大約是２２６００第16頁，共40頁，2023年，2月20日，星期三為改變二進(jìn)制編碼方法的缺點(diǎn)，人們提出了浮點(diǎn)數(shù)編碼方法．浮點(diǎn)數(shù)編碼方法指個體的每個基因值用某一范圍內(nèi)的一個浮點(diǎn)數(shù)來表示。個體的編碼長度等于其決策變量的個數(shù)浮點(diǎn)數(shù)編碼方法使用的是決策變量的真實(shí)值，所以該方法也稱為真值編碼方法。例設(shè)一個優(yōu)化問題含有五個變量，每個變量都有其對應(yīng)的上下限就表示一個個體的基因型，對應(yīng)的表現(xiàn)型為

X=[5.80,6.90,3.50,3.80,5.00]第17頁，共40頁，2023年，2月20日，星期三在浮點(diǎn)數(shù)編碼的ＧＡ算法中的注意要點(diǎn)(1)必須保證給定的基因值在給定的范圍內(nèi)(2)GA算法中所使用的交叉和變異算子必須使運(yùn)算結(jié)果在所給范圍(3)當(dāng)用多個字節(jié)來表示一個基因時(shí)，交叉運(yùn)算必須在兩個基因的分界字節(jié)處進(jìn)行，而不能在某個基因的中間字節(jié)分隔處進(jìn)行。浮點(diǎn)數(shù)編碼方法的優(yōu)點(diǎn)：(1)適合于在ＧＡ中表示范圍較大的數(shù)(2)適合于精度要求較高的ＧＡ(3)便于較大空間的遺傳搜索(4)改善了ＧＡ的計(jì)算的復(fù)雜性，提高了運(yùn)算效率(5)便于ＧＡ與經(jīng)典的優(yōu)化算法的使用第18頁，共40頁，2023年，2月20日，星期三符號編碼方法指個體染色體編碼串中基因值取自一個無數(shù)值含義，而只有代碼含義的符號集?？梢允且粋€字母表{A,B,C,…}也可以是一個數(shù)字序號集{1,2,3,…}還可以是一個代碼表{A1,A2,A3,…}如ＴＳＰ問題，假設(shè)有n個城市C1C2…Cn，將各個城市的代碼按其被訪問的順序連接起來，可以構(gòu)成一條旅行路線的個體Ｘ＝［Ｃ１，Ｃ２，…，Ｃn]第19頁，共40頁，2023年，2月20日，星期三4.2適應(yīng)度函數(shù)生物學(xué)家使用適應(yīng)度這個術(shù)語來度量某個物種對于其生存環(huán)境的適應(yīng)程度，適應(yīng)度高的物種有更多的繁殖機(jī)會，而對環(huán)境適應(yīng)程度較低的物種，其繁殖機(jī)會就較低，甚至回逐步滅絕。ＧＡ使用這個概念來度量群體中各個個體在優(yōu)化計(jì)算中有可能達(dá)到或接近于或有助于找到最優(yōu)解的優(yōu)良程度。度量個體適應(yīng)度的函數(shù)稱為適應(yīng)度函數(shù)第20頁，共40頁，2023年，2月20日，星期三目標(biāo)函數(shù)與適應(yīng)度函數(shù)轉(zhuǎn)換關(guān)系

解空間目標(biāo)函數(shù)學(xué)值f(x)搜索空間適應(yīng)度F(x)第21頁，共40頁，2023年，2月20日，星期三適應(yīng)度尺度變換

實(shí)踐表明，使用上面的轉(zhuǎn)化關(guān)系來計(jì)算個體的適應(yīng)度時(shí)，有些GA會收斂得很快，也有些收斂得很慢。所以，如何確定適應(yīng)度對ＧＡ的性能有較大影響。

在ＧＡ運(yùn)行初期群體中可能會有少數(shù)幾個各個的適應(yīng)度相對于其他個體來說非常高。如果按照常用的比例選擇算子來確定個體的遺傳數(shù)量，則這幾個相對較好的個體將在下一代群體中占有較高比例，在極端情況下或群體規(guī)模較小時(shí)，新的群體甚至完全由這少數(shù)幾個個體組成。這時(shí)產(chǎn)生新個體作用較大的交叉算子不起作用。這樣就會使群體的多樣性降低。容易導(dǎo)致GA過早收斂。使GA所得到的解停留在某一局部最優(yōu)點(diǎn)上。第22頁，共40頁，2023年，2月20日，星期三結(jié)論：我們希望在遺傳算法運(yùn)行的初期階段，算法能對一些適應(yīng)度較高的個體進(jìn)行控制，降低其適應(yīng)度與其他個體適應(yīng)度之間的差異程度，從而限制其復(fù)制的數(shù)量，以維護(hù)群體的多樣性。第23頁，共40頁，2023年，2月20日，星期三在ＧＡ運(yùn)行后期群體中所有個體的平均適應(yīng)度可能會接近群體中最佳個體的適應(yīng)度。即大部分個體的適應(yīng)度和最佳個體的適應(yīng)度差異不大。它們之間無競爭力，都會以相接近的概率被遺傳到下一代。從而使進(jìn)化過程無競爭可言。只是一種隨機(jī)的選擇過程。這就導(dǎo)致無法對某些重點(diǎn)區(qū)域進(jìn)行重點(diǎn)搜索。從而影響GA的效率。結(jié)論：我們希望在后期能夠?qū)€體的適應(yīng)度進(jìn)行適當(dāng)?shù)姆糯?，擴(kuò)大最佳個體適應(yīng)度與其他個體適應(yīng)度之間的差異程度，以提高個體之間的競爭性。第24頁，共40頁，2023年，2月20日，星期三適應(yīng)度尺度變換(fitnessScaling)方法在GA運(yùn)行的不同階段，需要對個體的適應(yīng)度進(jìn)行適當(dāng)?shù)臄U(kuò)大和縮小。這種對個體適應(yīng)度所做的擴(kuò)大和縮小變換稱為適應(yīng)度尺度變換。目前變換有三種：

(1)線性尺度變換

(2)冪尺度變換

(3)指數(shù)尺度變換第25頁，共40頁，2023年，2月20日，星期三線性尺度變換第26頁，共40頁，2023年，2月20日，星期三系數(shù)a,b直接影響到這個尺度變換的大小，對其選取有一定的要求，一般希望他們滿足如下條件：

(1)尺度變換后全部個體的新適應(yīng)度的平均值要等于其原適應(yīng)度的平均值

(2)尺度變換后群體中新的適應(yīng)度最大值要等于原平均適應(yīng)度的指定倍數(shù)

Ｃ為最佳個體的期望復(fù)制數(shù)量，對于群體規(guī)模為50-100的個體，一般取c=1.2—２.第27頁，共40頁，2023年，2月20日，星期三在搜索過程前期,使用線性尺度變換時(shí)，群體中少數(shù)幾個優(yōu)良個體的適應(yīng)度按比例縮小，同時(shí)幾個較差個體的適應(yīng)度也按比例擴(kuò)大。在搜索過程后期，隨著個體適應(yīng)度從總體上的不斷改進(jìn)，群體中個體的最大適應(yīng)度和全部個體的平均適應(yīng)度較接近，而少數(shù)幾個較差的個體的適應(yīng)度遠(yuǎn)遠(yuǎn)低于最大適應(yīng)度，這時(shí)要維持

第28頁，共40頁，2023年，2月20日，星期三將會使較差個體的適應(yīng)度變換為負(fù)值。將會給后面的處理帶來不變。解決這一問題的辦法是：使變換滿足如下條件第29頁，共40頁，2023年，2月20日，星期三第30頁，共40頁，2023年，2月20日，星期三a,b的計(jì)算方法如下:第31頁，共40頁，2023年，2月20日，星期三4.3選擇算子常用的選擇算子是SGA中的比例選擇算子,但對各種各樣的問題,比例選擇算子并不一定是最合適的.所以人們提出了其他一些選擇算子.下面介紹幾種常用選擇算子的操作方法.(1)比例選擇(proportionalModel)基本思想:各個個體被選中的概率與其適應(yīng)度大小成正比.由于隨機(jī)操作的原因,這種選擇方法的誤差較大,有時(shí)甚至連適應(yīng)度較高的個體選擇不上.第32頁，共40頁，2023年，2月20日，星期三(2)最優(yōu)保存策略（ElitistModel)(e-GA)

在GA的運(yùn)行過程中,通過對個體進(jìn)行交叉、變異等遺傳操作而不斷產(chǎn)生新的個體。雖然隨著群體的進(jìn)化過程而不斷產(chǎn)生出越來越多的優(yōu)良個體，但由于選擇、交叉、變異等遺傳操作的隨機(jī)性，他們也可能破壞掉當(dāng)前群體中適應(yīng)度最好的個體。這樣可能會降低群體的平均適應(yīng)度，對遺傳算法的效率產(chǎn)生不良的影響。

所以我們希望適應(yīng)度最好的個體要盡可能地保留到下一代群體中。

方法：如果下一代群體的最佳個體適應(yīng)值小于當(dāng)前群體最佳個體的適應(yīng)值，則將當(dāng)前群體最佳個體或者適應(yīng)值大于下一代群體中最佳個體適應(yīng)值的多個個體直接復(fù)制到下一代，即替代或替代最差的下一代群體中的相應(yīng)數(shù)量的個體。

第33頁，共40頁，2023年，2月20日，星期三第34頁，共40頁，2023年，2月20日，星期三4.4交叉算子在生物的自然進(jìn)化過程中，兩個同源染色體通過交配而重組，形成新的染色體，從而產(chǎn)生新的個體。GA中的所謂交叉算子是指對兩個相互配對的染色體按某種方式相互交換其部分基因，從而形成新的個體GA中，在交叉運(yùn)算之前還必須對群體中的個體進(jìn)行配對。目前常用的配對策略是隨機(jī)配對。即將群體中的M個個體以隨機(jī)的方式組成對個體組，交叉操作在這些配對個體組中的兩個個體之間進(jìn)行。第35頁，共40頁，2023年，2月20日，星期三第36頁，共40頁，2023年，2月20日，星期三交叉算子的設(shè)計(jì)和實(shí)現(xiàn)與所研究的問題密切相關(guān)。一般要求它既不要太多地破壞個體編碼串表示優(yōu)良性狀的優(yōu)良模式，又要能夠有效地產(chǎn)生出一些較好的新個體模式。交叉算子的設(shè)計(jì)包含以下兩方面的內(nèi)容

(1)如何確定交叉點(diǎn)的位置

(2)如何進(jìn)行部分基因交換幾種適合于二進(jìn)制編碼個體或浮點(diǎn)數(shù)編碼個體的交叉算子單點(diǎn)交叉雙點(diǎn)交叉與多點(diǎn)交叉均勻交叉算術(shù)交叉

第37頁，共40頁，2023年，2月20日，星期三單點(diǎn)交叉(one-pointcrossover)個體編碼串中只隨機(jī)設(shè)置一個交叉點(diǎn)，然后在該點(diǎn)相互交換兩個配對個體的部分染色體。雙點(diǎn)交叉與多點(diǎn)交叉(Two-pointcrossover)(multi-pointcrossover)注意：一般不太使用多點(diǎn)交叉算子，因?yàn)樗赡芷茐囊恍┖玫慕Y(jié)構(gòu)。隨著交叉點(diǎn)的增多，個體結(jié)構(gòu)被破壞的可能性也逐漸增大，這樣可