⑴ 遺傳演算法
根據問題的目標函數構造一個適值函數,對一個由多個解(每個解對應一個染色體)構成的種群進行評估、遺傳、選擇,經多代繁殖,獲得適應值最好的個體作為問題的最優解。
1,產生一個初始種群
2,根據問題的目標函數構造適值函數
3,根據適應值的好壞不斷選擇和繁殖
4,若干代後得到適應值最好的個體即為最優解
1.種群和種群大小
一般越大越好,但是規模越大運算時間越大,一般設為100~1000
2. 編碼方法 (基因表達方法
3. 遺傳運算元
包括交叉和變異,模擬了每一代中創造後代的繁殖過程。是遺傳演算法的精髓
交叉:性能在很大程度上取決於交叉運算的性能,交叉率Pc:各代中交叉產生的後與代數與種群中的個體數的比。Pc越高,解空間就越大,越耗時/
變異:Pm:種群中變異基因數在總基因數中的百分比。它控制著新基因導入種群的比例。太低,一些有用的基因就難以進入選擇;太高,後代就可能失去從雙親繼承下來的良好特性,也就失去了從過去中搜索的能力。
4.選擇策略
適者生存,優勝劣汰
5.停止准則
最大迭代數
初始種群的產生:隨機產生,具體依賴於編碼方法
編碼方法 :二進制編碼法、浮點編碼法、符號編碼法。順序編碼,實數編碼,整數編碼。
適值函數 :根據目標函數設計
遺傳運算 : 交叉 :單切點交叉,雙切點交叉,均勻交叉,算術交叉
變異 :基本位變異(Simple Mutation):對個體編碼串中以變異概率、隨機指定的某一位或某幾位僅因座上的值做變異運算。
均勻變異(Uniform Mutation):分別用符合某一范圍內均勻分布的隨機數,以某一較小的概率來替換個體編碼串中各個基因座上的原有基因值。(特別適用於在演算法的初級運行階段)
邊界變異(Boundary Mutation):隨機的取基因座上的兩個對應邊界基因值之一去替代原有基因值。特別適用於最優點位於或接近於可行解的邊界時的一類問題。
非均勻變異:對原有的基因值做一隨機擾動,以擾動後的結果作為變異後的新基因值。對每個基因座都以相同的概率進行變異運算之後,相當於整個解向量在解空間中作了一次輕微的變動。
高斯近似變異:進行變異操作時用符號均值為P的平均值,方差為P**2的正態分布的一個隨機數來替換原有的基因值。
選擇策略 :1.輪盤賭選擇(Roulette Wheel Selection):是一種回放式隨機采樣方法。每個個體進入下一代的概率等於它的適應度值與整個種群中個體適應度值和的比例。選擇誤差較大。
2.隨機競爭選擇(Stochastic Tournament):每次按輪盤賭選擇一對個體,然後讓這兩個個體進行競爭,適應度高的被選中,如此反復,直到選滿為止。
3.最佳保留選擇:首先按輪盤賭選擇方法執行遺傳演算法的選擇操作,然後將當前群體中適應度最高的個體結構完整地復制到下一代群體中。
4.無回放隨機選擇(也叫期望值選擇Excepted Value Selection):根據每個個體在下一代群體中的生存期望來進行隨機選擇運算。方法如下:
(1) 計算群體中每個個體在下一代群體中的生存期望數目N。
(2) 若某一個體被選中參與交叉運算,則它在下一代中的生存期望數目減去0.5,若某一個體未 被選中參與交叉運算,則它在下一代中的生存期望數目減去1.0。
(3) 隨著選擇過程的進行,若某一個體的生存期望數目小於0時,則該個體就不再有機會被選中。
5.確定式選擇:按照一種確定的方式來進行選擇操作。具體操作過程如下:
(1) 計算群體中各個個體在下一代群體中的期望生存數目N。
(2) 用N的整數部分確定各個對應個體在下一代群體中的生存數目。
(3) 用N的小數部分對個體進行降序排列,順序取前M個個體加入到下一代群體中。至此可完全確定出下一代群體中M個個體。
6.無回放余數隨機選擇:可確保適應度比平均適應度大的一些個體能夠被遺傳到下一代群體中,因而選擇誤差比較小。
7.均勻排序:對群體中的所有個體按期適應度大小進行排序,基於這個排序來分配各個個體被選中的概率。
8.最佳保存策略:當前群體中適應度最高的個體不參與交叉運算和變異運算,而是用它來代替掉本代群體中經過交叉、變異等操作後所產生的適應度最低的個體。
9.隨機聯賽選擇:每次選取幾個個體中適應度最高的一個個體遺傳到下一代群體中。
10.排擠選擇:新生成的子代將代替或排擠相似的舊父代個體,提高群體的多樣性。
之前在網上看到的一個比方,覺得很有趣:
{
既然我們把函數曲線理解成一個一個山峰和山谷組成的山脈。那麼我們可以設想所得到的每一個解就是一隻袋鼠,我們希望它們不斷的向著更高處跳去,直到跳到最高的山峰。所以求最大值的過程就轉化成一個「袋鼠跳」的過程。
下面介紹介紹「袋鼠跳」的幾種方式。
爬山演算法:一隻袋鼠朝著比現在高的地方跳去。它找到了不遠處的最高的山峰。但是這座山不一定是最高峰。這就是爬山演算法,它不能保證局部最優值就是全局最優值。
模擬退火:袋鼠喝醉了。它隨機地跳了很長時間。這期間,它可能走向高處,也可能踏入平地。但是,它漸漸清醒了並朝最高峰跳去。這就是模擬退火演算法。
遺傳演算法:有很多袋鼠,它們降落到喜瑪拉雅山脈的任意地方。這些袋鼠並不知道它們的任務是尋找珠穆朗瑪峰。但每過幾年,就在一些海拔高度較低的地方射殺一些袋鼠。於是,不斷有袋鼠死於海拔較低的地方,而越是在海拔高的袋鼠越是能活得更久,也越有機會生兒育女。就這樣經過許多年,這些袋鼠們竟然都不自覺地聚攏到了一個個的山峰上,可是在所有的袋鼠中,只有聚攏到珠穆朗瑪峰的袋鼠被帶回了美麗的澳洲。
}
(把那些總是愛走下坡路的袋鼠射殺,這就是遺傳演算法的精粹!)
遺傳演算法並不保證你能獲得問題的最優解,但是使用遺傳演算法的最大優點在於你不必去了解和操心如何去「找」最優解。(你不必去指導袋鼠向那邊跳,跳多遠。)而只要簡單的「否定」一些表現不好的個體就行了。(把那些總是愛走下坡路的袋鼠射殺,這就是遺傳演算法的精粹!)
改進與變形
編碼方法:
⑵ 遺傳演算法的主要步驟
為了使用遺傳演算法來解決優化問題,准備工作分為以下四步[56,57,61]。
7.4.1 確定問題的潛在解的遺傳表示方案
在基本的遺傳演算法中,表示方案是把問題的搜索空間中每個可能的點表示為確定長度的特徵串(通常是二進制串)。表示方案的確定需要選擇串長l和字母表規模k。在染色體串和問題的搜索空間中的點之間選擇映射有時容易實現,有時又非常困難。選擇一個便於遺傳演算法求解問題的表示方案經常需要對問題有深入的了解。
7.4.2 確定適應值的度量
適應值度量為群體中每個可能的確定長度的特徵串指定一個適應值,它經常是問題本身所具有的。適應值度量必須有能力計算搜索空間中每個確定長度的特徵串的適應值。
7.4.3 確定控制該演算法的參數和變數
控制遺傳演算法的主要參數有群體規模Pop-Size、演算法執行的最大代數N-Gen、交叉概率Pc、變異概率Pm和選擇策略R等參數。
(1)群體規模Pop-Size。群體規模影響到遺傳演算法的最終性能和效率。當規模太小時,由於群體對大部分超平面只給出了不充分的樣本量,所以得到的結果一般不佳。大的群體更有希望包含出自大量超平面的代表,從而可以阻止過早收斂到局部最優解;然而群體越大,每一代需要的計算量也就越多,這有可能導致一個無法接受的慢收斂率。
(2)交叉率Pc。交叉率控制交叉運算元應用的頻率,在每代新的群體中,有Pc·Pop-Size個串實行交叉。交叉率越高,群體中串的更新就越快。如果交叉率過高,相對選擇能夠產生的改進而言,高性能的串被破壞得更快。如果交叉率過低,搜索會由於太小的探查率而可能停滯不前。
(3)變異率Pm。變異是增加群體多樣性的搜索運算元,每次選擇之後,新的群體中的每個串的每一位以相等的變異率進行隨機改變。對於M進制串,就是相應的位從1變為0或0變為1。從而每代大約發生Pm·Pop-Size·L次變異,其中L為串長。一個低水平的變異率足以防止整個群體中任一給定位保持永遠收斂到單一的值。高水平的變異率產生的實質是隨機搜索。
比起選擇和交叉,變異在遺傳演算法中是次要的,它在恢復群體中失去的多樣性方面具有潛在的作用。例如,在遺傳演算法執行的開始階段,串中一個特定位上的值1可能與好的性能緊密聯系,也就是說從搜索空間中某些初始隨機點開始,在那個位上的值1可能一致地產生適應性度量好的值。因為越好的適應值與串中那個位上的值1相聯系,復製作用就越會使群體的遺傳多樣性損失。當達到一定程度時,值0會從整個群體中的那個位上消失,然而全局最優解可能在串中那個位上是0。一旦搜索范圍縮小到實際包含全局最優解的那部分搜索空間,在那個位上的值0就可能正好是達到全局最優解所需的。這僅僅是一種說明搜索空間是非線性的方式,這種情形不是假定的,因為實際上所有我們感興趣的問題都是非線性的。變異作用提供了一個恢復遺傳多樣性的損失的方法。
(4)選擇策略R。有兩種選擇策略。一是利用純選擇,即當前群體中每個點復制的次數比與點的性能值成比例。二是利用最優選擇,即首先執行純選擇,且具有最好性能的點總是保留到下一代。在缺少最優選擇的情況下,由於采樣誤差、交叉和變異,最好性能的點可能會丟失。
通過指定各個參數Pop-Size、Pc、Pm和R的值,可以表示一個特定的遺傳演算法。
7.4.4 確定指定結果的方法和停止運行的准則
當遺傳的代數達到最大允許代數時,就可以停止演算法的執行,並指定執行中得到的最好結果作為演算法的結果。
基本的遺傳演算法
1)隨機產生一個由固定長度字元串組成的初始群體。
2)對於字元串群體,迭代地執行下述步驟,直到選擇標准被滿足為止。
①計算群體中的每個個體字元串的適應值;
②實施下列三種操作(至少前兩種)來產生新的群體,操作對象的選取基於與適應度成比例的概率。
選擇:把現有的個體串按適應值復制到新的群體中。
交叉:通過遺傳重組隨機選擇兩個現有的子串進行遺傳重組,產生兩個新的串。
變異:將現有串中某一位的字元隨機變異產生一個新串。
3)把在後代中出現的最好適應值的個體串指定為遺傳演算法運行的結果。這一結果可以是問題的解(或近似解)。
基本的遺傳演算法流程圖如圖7-1所示。
⑶ 遺傳演算法的運算過程
遺傳操作是模擬生物基因遺傳的做法。在遺傳演算法中,通過編碼組成初始群體後,遺傳操作的任務就是對群體的個體按照它們對環境適應度(適應度評估)施加一定的操作,從而實現優勝劣汰的進化過程。從優化搜索的角度而言,遺傳操作可使問題的解,一代又一代地優化,並逼近最優解。
遺傳操作包括以下三個基本遺傳運算元(genetic operator):選擇(selection);交叉(crossover);變異(mutation)。這三個遺傳運算元有如下特點:
個體遺傳運算元的操作都是在隨機擾動情況下進行的。因此,群體中個體向最優解遷移的規則是隨機的。需要強調的是,這種隨機化操作和傳統的隨機搜索方法是有區別的。遺傳操作進行的高效有向的搜索而不是如一般隨機搜索方法所進行的無向搜索。
遺傳操作的效果和上述三個遺傳運算元所取的操作概率,編碼方法,群體大小,初始群體以及適應度函數的設定密切相關。 從群體中選擇優勝的個體,淘汰劣質個體的操作叫選擇。選擇運算元有時又稱為再生運算元(reproction operator)。選擇的目的是把優化的個體(或解)直接遺傳到下一代或通過配對交叉產生新的個體再遺傳到下一代。選擇操作是建立在群體中個體的適應度評估基礎上的,目前常用的選擇運算元有以下幾種:適應度比例方法、隨機遍歷抽樣法、局部選擇法。
其中輪盤賭選擇法 (roulette wheel selection)是最簡單也是最常用的選擇方法。在該方法中,各個個體的選擇概率和其適應度值成比例。設群體大小為n,其中個體i的適應度為,則i 被選擇的概率,為遺傳演算法
顯然,概率反映了個體i的適應度在整個群體的個體適應度總和中所佔的比例。個體適應度越大。其被選擇的概率就越高、反之亦然。計算出群體中各個個體的選擇概率後,為了選擇交配個體,需要進行多輪選擇。每一輪產生一個[0,1]之間均勻隨機數,將該隨機數作為選擇指針來確定被選個體。個體被選後,可隨機地組成交配對,以供後面的交叉操作。 在自然界生物進化過程中起核心作用的是生物遺傳基因的重組(加上變異)。同樣,遺傳演算法中起核心作用的是遺傳操作的交叉運算元。所謂交叉是指把兩個父代個體的部分結構加以替換重組而生成新個體的操作。通過交叉,遺傳演算法的搜索能力得以飛躍提高。
交叉運算元根據交叉率將種群中的兩個個體隨機地交換某些基因,能夠產生新的基因組合,期望將有益基因組合在一起。根據編碼表示方法的不同,可以有以下的演算法:
a)實值重組(real valued recombination)
1)離散重組(discrete recombination)
2)中間重組(intermediate recombination)
3)線性重組(linear recombination)
4)擴展線性重組(extended linear recombination)。
b)二進制交叉(binary valued crossover)
1)單點交叉(single-point crossover)
2)多點交叉(multiple-point crossover)
3)均勻交叉(uniform crossover)
4)洗牌交叉(shuffle crossover)
5)縮小代理交叉(crossover with reced surrogate)。
最常用的交叉運算元為單點交叉(one-point crossover)。具體操作是:在個體串中隨機設定一個交叉點,實行交叉時,該點前或後的兩個個體的部分結構進行互換,並生成兩個新個體。下面給出了單點交叉的一個例子:
個體A:1 0 0 1 ↑1 1 1 → 1 0 0 1 0 0 0 新個體
個體B:0 0 1 1 ↑0 0 0 → 0 0 1 1 1 1 1 新個體 變異運算元的基本內容是對群體中的個體串的某些基因座上的基因值作變動。依據個體編碼表示方法的不同,可以有以下的演算法:
a)實值變異
b)二進制變異。
一般來說,變異運算元操作的基本步驟如下:
a)對群中所有個體以事先設定的變異概率判斷是否進行變異
b)對進行變異的個體隨機選擇變異位進行變異。
遺傳演算法引入變異的目的有兩個:一是使遺傳演算法具有局部的隨機搜索能力。當遺傳演算法通過交叉運算元已接近最優解鄰域時,利用變異運算元的這種局部隨機搜索能力可以加速向最優解收斂。顯然,此種情況下的變異概率應取較小值,否則接近最優解的積木塊會因變異而遭到破壞。二是使遺傳演算法可維持群體多樣性,以防止出現未成熟收斂現象。此時收斂概率應取較大值。
遺傳演算法中,交叉運算元因其全局搜索能力而作為主要運算元,變異運算元因其局部搜索能力而作為輔助運算元。遺傳演算法通過交叉和變異這對相互配合又相互競爭的操作而使其具備兼顧全局和局部的均衡搜索能力。所謂相互配合.是指當群體在進化中陷於搜索空間中某個超平面而僅靠交叉不能擺脫時,通過變異操作可有助於這種擺脫。所謂相互競爭,是指當通過交叉已形成所期望的積木塊時,變異操作有可能破壞這些積木塊。如何有效地配合使用交叉和變異操作,是目前遺傳演算法的一個重要研究內容。
基本變異運算元是指對群體中的個體碼串隨機挑選一個或多個基因座並對這些基因座的基因值做變動(以變異概率P.做變動),(0,1)二值碼串中的基本變異操作如下:
基因位下方標有*號的基因發生變異。
變異率的選取一般受種群大小、染色體長度等因素的影響,通常選取很小的值,一般取0.001-0.1。 當最優個體的適應度達到給定的閾值,或者最優個體的適應度和群體適應度不再上升時,或者迭代次數達到預設的代數時,演算法終止。預設的代數一般設置為100-500代。
⑷ 遺傳演算法的選擇,交叉和變異概率的和是1嗎
這幾個操作的概率是相互獨立的,並不要求和為1。
選擇操作中的概率,以輪賭法為例,概率只反映了個體被選擇到的可能性,與個體的適應度大小有關,一般是適應度越大,對應輪賭法中的概率值越大。
交叉操作中的概率是用於判定兩個個體是否進行交叉操作,一般都會大於0.9。
變異操作的概率是允許少數個體存在變異情況,以避免限入局部最優解,其值一般都在0.1以下。
⑸ 遺傳演算法的基本原理
遺傳演算法的基本原理和方法
一、編碼
編碼:把一個問題的可行解從其解空間轉換到遺傳演算法的搜索空間的轉換方法。
解碼(解碼):遺傳演算法解空間向問題空間的轉換。
二進制編碼的缺點是漢明懸崖(Hamming Cliff),就是在某些相鄰整數的二進制代碼之間有很大的漢明距離,使得遺傳演算法的交叉和突變都難以跨越。
格雷碼(Gray Code):在相鄰整數之間漢明距離都為1。
(較好)有意義的積木塊編碼規則:所定編碼應當易於生成與所求問題相關的短距和低階的積木塊;最小字元集編碼規則,所定編碼應採用最小字元集以使問題得到自然的表示或描述。
二進制編碼比十進制編碼搜索能力強,但不能保持群體穩定性。
動態參數編碼(Dynamic Paremeter Coding):為了得到很高的精度,讓遺傳演算法從很粗糙的精度開始收斂,當遺傳演算法找到一個區域後,就將搜索現在在這個區域,重新編碼,重新啟動,重復這一過程,直到達到要求的精度為止。
編碼方法:
1、 二進制編碼方法
缺點:存在著連續函數離散化時的映射誤差。不能直接反映出所求問題的本身結構特徵,不便於開發針對問題的專門知識的遺傳運算運算元,很難滿足積木塊編碼原則
2、 格雷碼編碼滾如:連續的兩個整數所對應的編碼之間僅僅只有一個碼位是不同的,其餘碼位都相同。
3、 浮點數編碼方法:個體的每個基因值用某一范圍內的某個浮點數來表示,個體的編碼長度等於其決策變數的位數。
4、 各參數級聯編碼:對含有多個變數的個體進行編碼的方法。通常將各個參數分別以某種編碼方法進行編碼,然後再將他們的編碼按照一定順序連接在一起就組成了表示全部參數的個體編碼。
5、 多參數交叉編碼:將各個參數中起主要作用的碼位集中在一起,這樣它們就不易於被遺傳運算元破壞掉。
評估編碼的三個規范:完備性、健全性、非冗餘性。
二、選擇
遺傳演算法中的選擇操作就是用來確定如何從父代群體中按某種方法選取那些個體遺傳到下一代群體中的一種遺傳運算,用來確定重組或交叉個體,以及被選個體將產生多少個子代個體。
常用的選擇運算元:
1、 輪盤賭選擇(Roulette Wheel Selection):是一種回放式隨機采樣方法。每個個體進入下一代的概率等於它的適應度值與整個種群中個體適應度值和的比例。選擇誤差較大。
2、 隨機競爭選擇(Stochastic Tournament):每次按輪盤賭選擇一對個體,然後讓這兩個個體進行競爭,適應度高的被選中,如此反復,直到選滿為止。
3、 最佳保留選擇:首先按輪盤賭選擇方法執行遺傳演算法的選擇操作,然後將當前群體中適應度最高的大宏啟個體結構完整地復制到下一代群體中。
4、 無回放隨機選擇(也叫期望值選擇Excepted Value Selection):根據每個個體在下一代群體中的生存期望來進行隨機選擇運算。方法如下
(1) 計算群體中每個個體在下一代群體中的生存期望數目N。
(2) 若某一個體被選中參與交叉運算,則它在下一代中的生存期望數目減去0.5,若某一個體未被選中參與交叉運算,則它絕配在下一代中的生存期望數目減去1.0。
(3) 隨著選擇過程的進行,若某一個體的生存期望數目小於0時,則該個體就不再有機會被選中。
5、 確定式選擇:按照一種確定的方式來進行選擇操作。具體操作過程如下:
(1) 計算群體中各個個體在下一代群體中的期望生存數目N。
(2) 用N的整數部分確定各個對應個體在下一代群體中的生存數目。
(3) 用N的小數部分對個體進行降序排列,順序取前M個個體加入到下一代群體中。至此可完全確定出下一代群體中M個個體。
6、無回放余數隨機選擇:可確保適應度比平均適應度大的一些個體能夠被遺傳到下一代群體中,因而選擇誤差比較小。
7、均勻排序:對群體中的所有個體按期適應度大小進行排序,基於這個排序來分配各個個體被選中的概率。
8、最佳保存策略:當前群體中適應度最高的個體不參與交叉運算和變異運算,而是用它來代替掉本代群體中經過交叉、變異等操作後所產生的適應度最低的個體。
9、隨機聯賽選擇:每次選取幾個個體中適應度最高的一個個體遺傳到下一代群體中。
10、排擠選擇:新生成的子代將代替或排擠相似的舊父代個體,提高群體的多樣性。
三、交叉
遺傳演算法的交叉操作,是指對兩個相互配對的染色體按某種方式相互交換其部分基因,從而形成兩個新的個體。
適用於二進制編碼個體或浮點數編碼個體的交叉運算元:
1、單點交叉(One-pointCrossover):指在個體編碼串中只隨機設置一個交叉點,然後再該點相互交換兩個配對個體的部分染色體。
2、兩點交叉與多點交叉:
(1) 兩點交叉(Two-pointCrossover):在個體編碼串中隨機設置了兩個交叉點,然後再進行部分基因交換。
(2) 多點交叉(Multi-pointCrossover)
3、均勻交叉(也稱一致交叉,UniformCrossover):兩個配對個體的每個基因座上的基因都以相同的交叉概率進行交換,從而形成兩個新個體。
4、算術交叉(ArithmeticCrossover):由兩個個體的線性組合而產生出兩個新的個體。該操作對象一般是由浮點數編碼表示的個體。
四、變異
遺傳演算法中的變異運算,是指將個體染色體編碼串中的某些基因座上的基因值用該基因座上的其它等位基因來替換,從而形成以給新的個體。
以下變異運算元適用於二進制編碼和浮點數編碼的個體:
1、基本位變異(SimpleMutation):對個體編碼串中以變異概率、隨機指定的某一位或某幾位僅因座上的值做變異運算。
2、均勻變異(UniformMutation):分別用符合某一范圍內均勻分布的隨機數,以某一較小的概率來替換個體編碼串中各個基因座上的原有基因值。(特別適用於在演算法的初級運行階段)
3、邊界變異(BoundaryMutation):隨機的取基因座上的兩個對應邊界基因值之一去替代原有基因值。特別適用於最優點位於或接近於可行解的邊界時的一類問題。
4、非均勻變異:對原有的基因值做一隨機擾動,以擾動後的結果作為變異後的新基因值。對每個基因座都以相同的概率進行變異運算之後,相當於整個解向量在解空間中作了一次輕微的變動。
5、高斯近似變異:進行變異操作時用符號均值為P的平均值,方差為P2的正態分布的一個隨機數來替換原有的基因值。
⑹ 遺傳演算法
優化的演算法有很多種,從最基本的梯度下降法到現在的一些啟發式演算法,如遺傳演算法(GA),差分演化演算法(DE),粒子群演算法(PSO)和人工蜂群演算法(ABC)。
舉一個例子,遺傳演算法和梯度下降:
梯度下降和遺傳演算法都是優化演算法,而梯度下降只是其中最基礎的那一個,它依靠梯度與方向導數的關系計算出最優值。遺傳演算法則是優化演算法中的啟發式演算法中的一種,啟發式演算法的意思就是先需要提供至少一個初始可行解,然後在預定義的搜索空間高效搜索用以迭代地改進解,最後得到一個次優解或者滿意解。遺傳演算法則是基於群體的啟發式演算法。
遺傳演算法和梯度下降的區別是:
1.梯度下降使用誤差函數決定梯度下降的方向,遺傳演算法使用目標函數評估個體的適應度
2.梯度下降是有每一步都是基於學習率下降的並且大部分情況下都是朝著優化方向迭代更新,容易達到局部最優解出不來;而遺傳演算法是使用選擇、交叉和變異因子迭代更新的,可以有效跳出局部最優解
3.遺傳演算法的值可以用二進制編碼表示,也可以直接實數表示
遺傳演算法如何使用它的內在構造來算出 α 和 β :
主要講一下選擇、交叉和變異這一部分:
1.選擇運算:將選擇運算元作用於群體。選擇的目的是把優秀(適應值高)的個體直接遺傳到下一代。選擇操作是建立在群體中個體的適應度評估基礎上的。
2.交叉運算:將交叉運算元作用於群體。遺傳演算法中起核心作用的就是交叉運算元。交叉運算元是將種群中的個體兩兩分組,按一定概率和方式交換部分基因的操作。將交叉運算元作用於群體。遺傳演算法中起核心作用的就是交叉運算元。例如:(根據概率選取50個個體,兩兩配對,交換x,y,比如之前兩個是(x1,y1),(x2,y2),之後變成了(x1,y2),(x2,y1))
3.變異運算:將變異運算元作用於群體。即是對群體中的個體串的某些基因座上的基因值作變動。(x2可能變為x2+δ,y1變為y1+δ)
種群P(t)經過選擇、交叉、變異運算之後得到下一代種群P(t+1)。
遺傳演算法就是通過對大量的數據個體使用選擇、交叉和變異方式來進化,尋找適合問題的最優解或者滿意解。
遺傳演算法參數的用處和設置:
1.編碼選擇:通常使用二進制編碼和浮點數編碼,二進制適合精度要求不高、特徵較少的情況。浮點數適合精度高、特徵多的情況
2.種群:種群由個體組成,個體中的每個數字都代表一個特徵,種群個體數量通常設置在40-60之間;迭代次數通常看情況定若計算時間較長可以在100內,否則1000以內都可以。
3.選擇因子:通常有輪盤賭選擇和錦標賽選擇,輪盤賭博的特點是收斂速度較快,但優勢個體會迅速繁殖,導致種群缺乏多樣性。錦標賽選擇的特點是群多樣性較為豐富,同時保證了被選個體較優。
4.交叉因子:交叉方法有單點交叉和兩點交叉等等,通常用兩點交叉。交叉概率則選擇在0.7-0.9。概率越低收斂越慢時間越長。交叉操作能夠組合出新的個體,在串空間進行有效搜索,同時降低對種群有效模式的破壞概率。
5.變異因子:變異也有變異的方法和概率。方法有均勻變異和高斯變異等等;概率也可以設置成0.1。變異操作可以改善遺傳演算法的局部搜索能力,豐富種群多樣性。
6.終止條件:1、完成了預先給定的進化代數;2、種群中的最優個體在連續若干代沒有改進或平均適應度在連續若干代基本沒有改進;3、所求問題最優值小於給定的閾值.
⑺ 遺傳演算法中的錦標賽選擇演算法的思想是什麼
我理解的是,在50個人中,隨機選擇兩組人,每組10個人,對於每組的10個人按適應度進行排列,選擇兩組中適應度最好的兩個個體作為母代進行兩兩交叉;
然後再從剩下來的48個人中,隨機選擇兩組人,每組10個人,對於每組的10個人按適應度進行排列,選擇兩組中適應度最好的兩個個體作為母代進行兩兩交叉;
依此類推,知道你選出的母代個數滿足你的要求,這里母代個數肯定是少於50的。
⑻ 遺傳演算法的基本原理
遺傳演算法的基本原理是:
遺傳演算法是一種基於自然選擇和群體遺傳機理的搜索演算法,它模擬了自然選擇和自然遺傳過程中的繁殖、雜交和突變現象,在利用遺傳演算法求解問題時,問題的每一個可能解都被編碼成一個"染色體",即個體,若干個個體構成了群體(所有可能解)。在遺傳演算法開始時總是隨機的產生一些個體(即初始解),根據預定的目標函數對每一個個體進行評估,給出一個適應度值,基於此適應度值,選擇一些個體用來產生下一代,選擇操作體現了適者生存的原理,」好「的個體被用來產生下代,「壞」的個體則被淘汰,然後選擇出來的個體經過交叉和變異,運算元進行再組合生成新的一代,這一代的個體由於繼承了上代的一些優良性狀,因而在性能上上要優於上一代,這樣逐步朝著最優解的方向進化,因此,遺傳演算法可以看成是一個由可行解組成的群體初步進化的過程。