遺傳演算法設置
⑴ 遺傳演算法可以給優化結果設置范圍嗎
你可以設置停止迭代的條件之一是y在區間內。
如戚鎮果一定在【10,20】內,就應該在適應度函數中做這個條件的添加,例如比較簡單高升粗的在這個外圍外加上一個很大笑或的罰值,但是容易你求不到最優解,所以你要在前面編碼的時候把范圍給好。
⑵ 如何在遺傳演算法中設置變數約束條件
1、一般有兩種方法,一種是在生成初始種群時只生成滿足約束的個體;另一種是隨機產生個體,並且在隨後的操作中判斷個體是否滿足約束條件。
2、這是遺傳演算法的特點決定的;遺傳演算法是一種隨機搜索演算法,每次都因種群規模的不同、參數的不同而得到不同的結果。即便參數都相同,每次運算得到的近似最優解也不一定相同。一般取n次運算中的最好結果來作為最終的最優解。當然,如果你的約束條件設置不妥,或者參數設置不適當,那麼也會造成每次運算的近似最優解相差過大,且質量不高。這些都要注意。
3、我用MATLAB自己編寫遺傳演算法來解決問題,因為其自帶的工具箱比較固定,只能解決簡單、典型的問題。但你的問題稍加復雜時,工具箱的作用就發揮不出來。
⑶ 遺傳演算法的交叉概率設置為1會有什麼不好的地方,一般
交神銀慧叉概率最搏族好不要設置為1,一般情況是0.5~0.95。
如果設置為1,那麼每一個個體都要參與交叉,游答就很有可能會破壞優秀個體的結構,
從而失去某些優秀基因。
⑷ 遺傳演算法
優化的演算法有很多種,從最基本的梯度下降法到現在的一些啟發式演算法,如遺傳演算法(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、所求問題最優值小於給定的閾值.
⑸ 遺傳演算法<sup>[1,]</sup>
遺傳演算法,又稱基因演算法(Genetic Algorithm,簡稱GA),也是一種啟發式蒙特卡洛優化演算法。遺傳演算法最早是由Holland(1975)提出,它模擬了生物適者生存、優勝劣汰的進化過程,具有不依賴於初始模型的選擇、不容易陷入局部極小、在反演過程中不用計算偏導數矩陣等優點。遺傳演算法最早由Stoffa和Sen(1991)用於地震波的一維反演,之後在地球物理資料的非線性反演中得到廣泛的應用。GA演算法對模型群體進行追蹤、搜索,即模型狀態通過模型群體傳送,具有比模擬退火法更大、更復雜的「記憶」,潛力更大。
遺傳演算法在反演中的基本思路和過程是:
(1)將生物體看成模型,模型參數看成染色體,有多少個模型的參數就有多少個染色體。對每個模型的參數(染色體)用二進制進行編碼,這個編碼就是基因。
(2)隨機生成一個模型群體(相當於生物的種群),然後在模型群體中進行繁殖,通過母本的選擇、交換和變異等遺傳操作產生下一代,然後保留較好基因,淘汰較差基因。
(3)通過一代一代的繁殖優勝劣汰的進化過程,最後所剩下的種群基本上都是最優的基因,種群趨於一致。所謂群體「一致」,即群體目標函數的方差或標准差很小,或者群體目標函數的均值接近於極值(可能是極大值或極小值),從而獲得非線性反演問題所對應的最優解或近似最優解。
下面以一個實例來簡述遺傳演算法的基本過程。
[例1]設m是正整數,且0≤m≤127,求方程φ(m)=m2的極大值。
這個例子極為簡單,只有一個模型參數,因此只有一條染色體,目標函數的極值是極大值(此例子來自阮百堯課件)。遺傳演算法通過以下7個步驟來實現:
(1)模型參數二進制編碼。
每個模型參數就是一條染色體,把十進制的模型參數表示為二進制,這就是基因。首先確定二進制碼的長度(基因的長度):
2N=[mmax(i)-mmin(i)]/Δm(i) (8.20)
其中:N為第i條染色體基因的長度(也就是第i個模型參數的二進制碼位數);[mmin(i),mmax(i)]為第i個模型參數的取值范圍;Δm(i)為第i個模型參數的解析度。這樣就把模型參數離散化了,它只能按Δm(i)的整數倍變化。基因的長度按下式計算:
地球物理反演教程
其中:c為實數;N為基因長度,是整數;int[ ]為取整函數。上式表示如果c不是整數,那麼基因長度N就是對c取整後加1,這樣保證最小解析度。
基因的編碼按下式進行:
地球物理反演教程
其中:式(8.22)是編碼公式;k為基因編碼的十進制數,是整數;int[ ]為取整函數。把k轉化為二進制就是基因的編碼。解碼是按照式(8.23)進行的。首先把一個基因的二進制編碼轉化為十進制數k,然後按式(8.23)可以計算出第i個模型參數m(i)的十進制值。
例如:電阻率參數ρ(1),它的變化范圍為10~5000Ω·m,解析度為2Ω·m,設當前參數ρ(1)=133Ω·m,按式(8.21)計算得
c=11.28482,N=12
所以二進制基因長度為13位。
利用式(8.22)計算基因編碼k的十進制數:
k=int[(133-10)/2]=61
把它轉化為二進制數為:000000111101。所以ρ(1)=133 的二進制基因編碼為:000000111101。
解碼過程就是把二進制基因編碼變為十進制數k後用式(8.23)計算:
ρ(1)=10+61×2=132(Ω·m)
注意:基因編碼並不是直接把電阻率值變為二進制。此外,133這個值在基因里不會出現,因為解析度是2,所以表示為最接近的132。
對於[例1]問題來說,選解析度為1,0~127用二進制編碼需7位。
(2)產生初始模型種群。
生物繁殖進化需要一定數量的生物體種群,因此遺傳演算法開始時需要一定數量的初始模型。為保證基因的多樣性,隨機產生大量的初始模型作為初始種群,按照上面的編碼方式進行編碼。個體在模型空間中應分布均勻,最好是模型空間各代表區域均有成員。初始模型群體大,有利於搜索,但太大會增加計算量。
為保證演算法收斂,在初始模型群體中,有時候應增加各位都為0和都為1的成員。遺傳演算法就是在這個初始模型種群的基礎上進行繁殖,進化求解的。
對於[例1]問題來說,模型空間是0~127個數字,這樣初始種群最多具有128個個體。為了簡單,隨機選擇4個個體作為初始種群。初始種群的編碼、目標函數值見表8.1。
表8.1 初始種群編碼表
(3)模型選擇。
為了生成新一代模型,需要選擇較優的個體進行配對。生物進化按照自然選擇、優勝劣汰的准則進行。對應地,遺傳演算法按照一定的准則來選擇母本(兩個),然後進行配對繁殖下一代模型,這個選擇稱為模型選擇。模型配對最基本的方法是隨機采樣,用各模型的目標函數值對所有模型目標函數的平均值的比值定義繁殖概率,即
地球物理反演教程
其中:p(mi)為繁殖概率;φ(mi)為第i個模型的目標函數;φAVG為目標函數的平均值。對於極小化問題來說,規定目標函數值高於平均值的不傳代;對於極大化問題來說,反之即可。
就[例1]來說,要求目標函數取極大值,所以規定目標函數小於平均值的模型不傳代,大於它的可以傳代。對第一代,為了防止基因丟失,可先不捨去繁殖概率小的模型,讓它與概率大的模型配對。如:本例中70與56配對,101與15配對產生子代,見表8.2。
表8.2 基因交換表
(4)基因交換。
將配對的兩個親本模型的部分染色體相互交換,其中交換點可隨機選擇,形成兩個新的子代(見表8.2)。兩個染色體遺傳基因的交換過程是遺傳演算法的「繁殖」過程,是母本的重組過程。
為了使染色體的基因交換比較徹底,Stoffa等人提出了一個交換概率px來控制選擇操作的效果。如果px的值較小,那麼交換點的位置就比較靠低位,這時的交換操作基本是低位交換,交換前後模型的染色體變化不是太大。如果px的值較大,那麼交換點的位置就比較靠高位,此時的交換操作可以在較大的染色體空間進行,交換前後模型數值變化可以很大。
在[例1]中:15、101和56、70作為母本通過交換繁殖出子代5、6、111、120。所選擇的基因交換位置見表8.2。有下劃線的,是要交換的基因位置。
(5)更新。
母本模型和子本模型如何選擇保留一定數量作為新的母本,就是模型更新。不同的策略會導致不同的結果。一般而言,若產生的新一代模型較好,則選擇新一代模型而淘汰上一代模型。否則,則必須根據一定的更新概率pu來選擇上一代模型來取代新一代中某些較劣的模型。
經過更新以後,繁殖時對子代再進行優勝劣汰的選擇。對於極大值問題,大於目標函數平均值的子代可以繁殖,小於目標函數平均值的子代不能繁殖。由於新的種群能繁殖的個體數量減小了,所以要多繁殖幾次,維持種群個體的數量保持平衡。
在[例1]中,子代較好,所以完全淘汰上一代模型,完全用子代作為新的母本。選擇子代目標函數最大的兩個模型進行繁殖,分別是111、120。
(6)基因變異。
在新的配對好的母本中,按一定比例隨機選擇模型進行變異,變異操作就是模擬自然界中的環境因素,就是按比較小的變異概率pm將染色體某位或某幾位的基因發生突變(即將0變為1或將1變為0)。
變異操作的作用是使原來的模型發生某些變化,從而成為新的個體。這樣可使群體增加多樣性。變異操作在遺傳演算法中也起著至關重要的作用。實際上,由於搜索空間的性質和初始模型群體的優劣,遺傳演算法搜索過程中往往會出現所謂的「早熟收斂」現象,即在進化過程中早期陷入局部解而中止進化。採用合適的變異策略可提高群體中個體的多樣性,從而防止這種現象的出現,有助於模型跳出局部極值。表8.3為[例1]的基因變異繁殖表。
表8.3 基因變異繁殖表
在[例1]中,用111、120分別繁殖兩次,形成4個子代,維持種群數量平衡。隨機選擇120進行變異,變異的位數也是隨機的。這里把它的第2位進行變異,即從1變為0,繁殖後形成子代為:70、110、121、127。可以看出新的子代比初始種群要好得多,其中甚至已經出現了最優解。如果對於地球物理的極小值問題,我們可以預先設置一個擬合精度,只要在種群中出現一個達到擬合精度的模型就可以終止反演了。
(7)收斂。
重復(3)~(6)的步驟,模型群體經多次選擇、交換、更新、變異後,種群個體數量大小不變,模型目標函數平均值趨於穩定,最後聚集在模型空間中一個小范圍內,則找到了全局極值對應的解,使目標函數最大或最小的模型就是全局最優模型。
對於具有多解性的地球物理反演問題來說,通過這一步有可能找到滿足擬合精度的多個模型,對於實際反演解釋、推斷具有較高的指導意義。
遺傳演算法中的各種概率包括交換概率px、變異概率pm以及更新概率pu,這些參數的選擇與設定目前尚無統一的理論指導,多數都視具體問題而定。Stoffa等(1991)的研究表明,適中的交換概率(px≈0.6)、較小的變異概率(pm≈0.01)和較大的更新概率(pu≈0.9),遺傳演算法的性能較優。
與模擬退火反演演算法相同,遺傳演算法與傳統的線性反演方法相比,該方法具有:不依賴初始模型的選擇、能尋找全局最小點而不陷入局部極小、在反演過程中不用計算雅克比偏導數矩陣等優點。另外,遺傳演算法具有並行性,隨著並行計算和集群式計算機技術的發展,該演算法將會得到越來越廣泛的研究與應用。
但是遺傳演算法作為類蒙特卡洛演算法同樣需要進行大量的正演計算,種群個體數量越大,繁衍代數越多,則計算量越大。所以和前面的最小二乘法相比,速度不是它的優勢。
⑹ matlab遺傳演算法工具箱的缺陷
Matlab遺傳演算法工具箱是一種常用的工具箱,可以用於遺傳演算法的建模和優化。但是,該工具箱也存在一些缺陷,主要包括以下幾個方面:
1. 效率問題:在數據量如脊特別大的情況下,Matlab遺傳演算法工具箱的效率相對較低,求解時間較長。
2. 可靠性問題:遺傳演算法依賴於初始種群和隨機交叉操作,因此產生的結果會有一定的隨機性,不一定達到最優解或者無法找到解。
3. 參數設置問題:使用遺傳演算法需要進纖橡蘆行參數設置,如種群大小、交叉率、變異率等。這些參數的設置對結果產生重要影響,但並沒有一個統一的標准,需要根據實際問題進行調整。
4. 局部最優解問題:遺傳演算法容易陷入毀帶局部最優解,無法搜索到全局最優解,解決方法一般採用增加交叉次數和變異次數等策略。
總之,Matlab遺傳演算法工具箱作為一種優化工具,其在應用時需要根據具體情況進行選擇,並且需要針對實際情況進行參數設置和進一步優化。
⑺ 遺傳演算法理解
遺傳演算法是一種進化演算法,進化是什麼哪?就是種群逐漸適應生存環境,種群中個體不斷得到改良的過程。
遺傳演算法是一種對生物遺傳的模擬、在演算法中,初始化一個種群,種群中的每個染色體個體都是一種解決方案,我們通過適應性fitness來衡量這個解決方案的好壞。並對它們進行選擇、變異、交叉的操作,找到最優的解決方案。
總結一下遺傳演算法的基本的步驟:
1.初始化一個種群,並評估每條染色體所對應個體的適應度。
2.選擇、交叉、變異,產生新的種群
3.再評估每個個體的適應值,如果適應值達到要求或者達到最大循環次數,否則重復2,不斷產生新種群。
知道了GA的大致流程之後、來具體分析一下細節,怎麼實現吧
我們知道遺傳演算法起源於生物遺傳,因此在種群中每個個體就是一個染色體,那如何對染色體進行編碼,讓它表示我們的解決方案那(就是把現實要優化的參數用編碼表示成一個染色體)。這里就遇到了一個編碼、解碼的問題,我們將需要優化的目標編碼成染色體,然後再解碼為我們可以用來計算fitness的解;
一般在進行參數優化時,一般有兩種方式:實數編碼、二進制編碼
實數編碼:基因直接用實數進行表示,這樣的表示方法比較簡單,不用特意解碼了,但是在交叉和變異時,容易過早收斂,陷入局部最優。
二進制編碼:將基因用二進制的形式表示,將參數的值轉化為二進制形式,這樣交叉、變異時更好操作,多樣性好,但是佔用的存儲空間大,需要解碼。
染色體就稱為個體。對於一次實驗,個體就是需要優化參數的一種解、許多這樣的個體就構成了種群。
在面對群體中那麼多個體時,如何判斷個體的好壞呢,就是通過適應值函數了,將解帶入適應值函數,適應值越大、解越好。
在遺傳演算法中,我們怎麼使得裡面的個體變得越來越優秀呢?
核心思想就是:選擇優秀的、淘汰不好的,並且為了生成更好的解,我們要嘗試交叉、變異,帶來新的解。
選擇就是從當前的種群中選擇出比較好的個體、淘汰不好的個體
常見的選擇方法有:輪盤賭選擇、錦標賽選擇、最佳保留選擇等等
輪盤賭選擇就是根據每個個體fitness和種群所有fitness之和比較,確定每個個體被選中的概率,然後進行n次選擇,選擇n個個體構成新種群,是一種放回抽樣的方式。
錦標賽就是每次從種群中選擇m個個體,選擇最優的,放入新種群,重復選擇,直到新種群中個體數目達到n。
最佳保留選擇就是在輪盤賭的基礎上,將fitness個體先加進新種群,因為輪盤賭是一種概率模型,可能存在最優個體沒有進入新種群的情況。
在選擇之後,就要考慮產生新的、更優秀的解,為種群帶來新的血液。遺傳演算法的思路是交叉兩個優秀的解,往往get好的解。
交叉通過在經過選擇的種群中,隨機選擇一對父母,將它們的染色體進行交叉,生成新的個體,替代原來的解。
常用的交叉方法有:單點交叉、多點交叉等等。
交叉就像生物裡面,染色體交換基因一樣的~但是並不是種群中所有個體都進行交叉的,實現時可以,設置一個交叉率和交叉概率,隨機選擇種群中兩個體、隨機一個數,小於交叉率就進行交叉操作,並根據交叉概率判斷交叉的程度,從而生成新個體,反之就保留這兩個體。
變異也是一種產生新個體的方式,通過改變個體上基因,期望產生更好的解。比如在以二進制編碼的個體上,將裡面的0、1進行等位變化啥的,就是0變1、1變0這樣。同樣也要考慮變異率、變異產生的新解是不可控的,可能很好,也可能很壞,不能像交叉一樣,確保一定的效果,所以往往變異率設置的比較小。
⑻ 優化演算法筆記(六)遺傳演算法
遺傳演算法(Genetic Algorithms,GA)是一種粗衡模擬自然中生物的遺傳、進化以適應環境的智能演算法。由於其演算法流程簡單,參數較少優化速度較快,效果較好,在圖像處理、函數優化、信號處理、模式識別等領域有著廣泛的應用。
在遺傳演算法(GA)中,每一個待求問題的候選解被抽象成為種群中一個個體的基因。種群中個體基因的好壞由表示個體基因的候選解在待求問題中的所的得值來評判。種群中的個體通過與其他個體交叉產生下一代,每一代中個體均只進行一次交叉。兩個進行交叉的個體有一定幾率交換一個或者多個對應位的基因來產生新的後代。每個後代都有一定的概率發生變異。發生變異的個體的某一位或某幾位基因會變異成其他值。最終將以個體的適應度值為概率選取個體保留至下一代。
遺傳演算法啟發於生物的繁殖與dna的重組,本次的主角選什麼呢?還是根據大家熟悉的孟德爾遺傳規律選豌豆吧,選動物的話又會有人疑車,還是植物比較好,本次的主角就是它了。
遺傳演算法包含三個操作(運算元):交叉,變異和選擇操作。下面我們將詳細介紹這三個操作。
大多數生物的遺傳信息都儲存在DNA,一種雙螺旋結構的復雜有機化合物。其含氮鹼基為腺嘌呤、鳥嘌呤、胞嘧啶及胸腺嘧啶。
表格中表示了一個有10個基因的個體,它們每一個基因的值為0或者1。
生物的有性生殖一般伴隨著基因的重組。遺傳演算法中父輩和母輩個體產生子代個體的過程稱為交叉。
表中給出了兩個豌豆的基因,它們均有10個等位基因(即編號相同的基因)。
遺傳演算法的交叉過程會在兩個個體中隨機選擇1位或者n位基因進行交叉,即這兩個個體交換等位基因。
如,A豌豆和B豌豆在第6位基因上進行交叉,則其結果如下
當兩個個體交叉的等位基因相同時,交叉過程也有可能沒有產生新慧衡的個體,如交叉A豌豆和B豌豆的第2位基因時,交叉操作並沒有產生新的基因。
一般的會給群體設定一個交叉率,crossRate,表示會在群體中選取一定比例的個體進行交叉,交叉率相對較大,一般取值為0.8。
基因的變異是生物進化的一個主要因素。
遺傳演算法中變異操作相對簡單,只需要將一個隨機位基因的值修改就行了,因為其值只為0或1,那麼當基因為0時,變異操作會將其值設為1,當基因值為1時,變異操作會將其值設為0。
上圖表示了A豌豆第3位基因變異後的基因編碼。
與交叉率相似,變異操作也有變異率,alterRate,但是變異率會遠低於交叉率,否則會產生大量的隨機基因。一般變異率為0.05。
選擇操作是遺傳演算法中的一個關鍵操作,它的主要作用就是根據一定的策略隨機選擇個體保留至下一代。適應度越優的岩碧做個體被保留至下一代的概率越大。
實現上,我們經常使用「輪盤賭」來隨機選擇保留下哪個個體。
假設有4個豌豆A、B、C、D,它們的適應度值如下:
適應度值越大越好,則它們組成的輪盤如下圖:
但由於輪盤賭選擇是一個隨機選擇過程,A、B、C、D進行輪盤賭選擇後產生的下一代也有可能出現A、A、A、A的情況,即雖然有些個體的適應度值不好,但是運氣不錯,也被選擇留到了下一代。
遺產演算法的三個主要操作介紹完了,下面我們來看看遺傳演算法的總體流程:
前面我們說了遺傳演算法的流程及各個操作,那麼對於實際的問題我們應該如何將其編碼為基因呢?
對於計算機來所所有的數據都使用二進制數據進行存放,如float類型和double類型的數據。
float類型的數據將保存為32位的二進制數據:1bit(符號位) 8bits(指數位) 23bits(尾數位)
如-1.234567f,表示為二進制位
Double類型的數據將保存為64位的二進制數據:1bit(符號位) 11bits(指數位) 53bits(尾數位)
如-1.234567d,表示為二進制為
可以看出同樣的數值不同的精度在計算機中存儲的內容也不相同。之前的適應度函數 ,由於有兩個double類型的參數,故其進行遺傳演算法基因編碼時,將有128位基因。
雖然基因數較多,但好在每個基因都是0或者1,交叉及變異操作非常簡單。
相比二進制編碼,十進制編碼的基因長度更短,適應度函數 有兩個輸入參數,那麼一個個體就有2個基因,但其交叉、變異操作相對復雜。
交叉操作
方案1:將一個基因作為一個整體,交換兩個個體的等位基因。
交換前
交換第1位基因後
方案2:將兩個個體的等位基因作為一個整體,使其和不變,但是值隨機
交換前
交換第1位基因後
假設A、B豌豆的第一位基因的和為40,即 ,第一位基因的取值范圍為0-30,那麼A、B豌豆的第一位基因的取值范圍為[10,30],即 為[0,30]的隨機數, 。
變異操作,將隨機的一位基因設置為該基因取值范圍內的隨機數即可。
這個過程說起來簡單但其實現並不容易。
我們要將它們的值映射到一個軸上才能進行隨機選擇,畢竟我們無法去繪制一個輪盤來模擬這個過程
如圖,將ABCD根據其值按順序排列,取[0,10]內的隨機數r,若r在[0,1]內則選擇A,在(1,3]內則選擇B,在(3,6]內則選擇C,在(6,10]則選擇D。
當然這仍然會有問題,即當D>>A、B、C時,假如它們的值分布如下
那麼顯然,選D的概率明顯大於其他,根據輪盤賭的選擇,下一代極有可能全是D的後代有沒有辦法均衡一下呢?
首先我想到了一個函數,
不要問我為什麼我不知道什麼是神經什麼網路的,什麼softmax、cnn統統沒聽說過。
這樣一來,它們之間的差距沒有之前那麼大了,只要個體適應度值在均值以上那麼它被保留至下一代的概率會相對較大,當然這樣縮小了個體之間的差距,對真正優秀的個體來說不太公平,相對應,我們可以在每次選擇過程中保留當前的最優個體到下一代,不用參與輪盤賭這個殘酷的淘汰過程。
最令人高興的環節到了,又可以愉快的湊字數了。
由於遺傳演算法的收斂速度實在是太慢,區區50代,幾乎得不到好的結果,so我們把它的最大迭代次數放寬到200代。
使用二進制編碼來進行求解
參數如下:
求解過程如上圖,可以看出基因收斂的很快,在接近20代時就圖中就只剩一個點了,之後的點大概是根據變異操作產生。看一下最後的結果。
可以看出最好的結果已經得到了最優解,但是10次實驗的最差值和平均值都差的令人發指。為什麼會這樣呢?
問題出在二進制編碼上,由於double類型的編碼有11位指數位和52位小數位,這會導致交叉、變異操作選到指數位和小數位的概率不均衡,在小數位上的修改對結果的影響太小而對指數為的修改對結果的影響太大,
如-1.234567d,表示為二進制為
對指數為第5位進行變異操作後的結果為-2.8744502924382686E-10,而對小數位第5為進行變異操作後的結果為-1.218942。可以看出這兩部分對數值結果的影響太不均衡,得出較好的結果時大概率是指數位與解非常相近,否則很難得出好的結果,就像上面的最差值和均值一樣。
所以使用上面的二進制編碼不是一個好的基因編碼方式,因此在下面的實驗中,將使用十進制來進行試驗。
使用:十進制編碼來進行求解
參數如下:
我們可以看到直到40代時,所有的個體才收束到一點,但隨後仍不斷的新的個體出現。我們發現再後面的新粒子總是在同一水平線或者豎直線上,因為交叉操作直接交換了兩個個體的基因,那麼他們會相互交換x坐標或者y坐標,導致新個體看起來像在一條直線上。
我們來看看這次的結果。
這次最優值沒有得到最優解,但是最差值沒有二進制那麼差,雖然也不容樂觀。使用交換基因的方式來進行交叉操作的搜索能力不足,加之輪盤賭的選擇會有很大概率選擇最優個體,個體總出現在矩形的邊上。
下面我們先改變輪盤賭的選擇策略,使用上面的sigmod函數方案,並且保留最優個體至下一代。
使用:十進制編碼來進行求解
參數如下:
看圖好像跟之前的沒什麼區別,讓我們們看看最終的結果:
可以看出,最優值沒有什麼變化,但是最差值和平均值有了較大的提升,說明該輪盤賭方案使演算法的魯棒性有了較大的提升。在每次保留最優個體的情況下,對於其他的個體的選擇概率相對平均,sigmod函數使得即使適應度函數值相差不太大的個體被選到的概率相近,增加了基因的多樣性。
使用:十進制編碼來進行求解,改變交叉方案,保持兩個個體等位基因和不變的情況下隨機賦值。
參數如下:
上圖可以看出該方案與之前有明顯的不同,在整個過程中,個體始終遍布整個搜索空間,雖然新產生的個體大多還是集中在一個十字架型的位置上,但其他位置的個體比之前的方案要多。
看看結果,
這次的結果明顯好於之前的所有方案,但仍可以看出,十進制的遺傳演算法的精度不高,只能找到最優解的附近,也有可能是演算法的收斂速度實在太慢,還沒有收斂到最優解。
遺傳演算法的探究到此也告一段落,在研究遺傳演算法時總有一種力不從心的感覺,問題可能在於遺傳演算法只提出了一個大致的核心思想,其他的實現細節都需要自己去思考,而每個人的思維都不一樣,一萬個人能寫出一萬種遺傳演算法,其實不僅是遺傳演算法,後面的很多演算法都是如此。
為什麼沒有對遺傳演算法的參數進行調優,因為遺傳演算法的參數過於簡單,對結果的影響的可解釋性較強,意義明顯,實驗的意義不大。
遺傳演算法由於是模仿了生物的進化過程,因此我感覺它的求解速度非常的慢,而且進化出來的結果不一定是最適應環境的,就像人的闌尾、視網膜結構等,雖然不是最佳的選擇但是也被保留到了今天。生物的進化的隨機性較大,要不是恐龍的滅絕,也不會有人類的統治,要不是人類有兩只手,每隻手有5根手指,也不會產生10進制。
以下指標純屬個人yy,僅供參考
目錄
上一篇 優化演算法筆記(五)粒子群演算法(3)
下一篇 優化演算法筆記(七)差分進化演算法
優化演算法matlab實現(六)遺傳演算法matlab實現
⑼ 遺傳演算法種群規模是怎麼得到的
種群規模是指任意一代中的個體總數,這個是人為設定的,種群規模越大越可能找到全局解,但運行時間也相對較長,一般在40-100之間取值,像我就習慣選60.
至於你所處理的問題,可以對比不同的種群規模下最優解和運行時間,然後折衷取。
拓展資料:
遺傳演算法(Genetic Algorithm,GA)最早是由美國的 John holland於20世紀70年代提出,該演算法是根據大自然中生物體進化規律而設計提出的。是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型,是一種通過模擬自然進化過程搜索最優解的方法。該演算法通過數學的方式,利用計算機模擬運算,將問題的求解過程轉換成類似生物進化中的染色體基因的交叉、變異等過程。在求解較為復雜的組合優化問題時,相對一些常規的優化演算法,通常能夠較快地獲得較好的優化結果。遺傳演算法已被人們廣泛地應用於組合優化、機器學習、信號處理、自適應控制和人工生命等領域。
運算過程
遺傳演算法的基本運算過程如下:
(1)初始化:設置進化代數計數器t=0,設置最大進化代數T,隨機生成M個個體作為初始群體P(0)。
(2)個體評價:計算群體P(t)中各個個體的適應度。
(3)選擇運算:將選擇運算元作用於群體。選擇的目的是把優化的個體直接遺傳到下一代或通過配對交叉產生新的個體再遺傳到下一代。選擇操作是建立在群體中個體的適應度評估基礎上的。
(4)交叉運算:將交叉運算元作用於群體。遺傳演算法中起核心作用的就是交叉運算元。[2]
(5)變異運算:將變異運算元作用於群體。即是對群體中的個體串的某些基因座上的基因值作變動。群體P(t)經過選擇、交叉、變異運算之後得到下一代群體P(t+1)。
(6)終止條件判斷:若t=T,則以進化過程中所得到的具有最大適應度個體作為最優解輸出,終止計算。
遺傳操作包括以下三個基本遺傳運算元(genetic operator):選擇(selection);交叉(crossover);變異(mutation)。
⑽ 遺傳演算法中字元串長度如何設置
遺傳演算法中字元串長度直接調用類似於strlen之類的函數就可以。遺嫌飢傳演算法中字元串長度直接嫌隱調用芹者廳類似於strlen之類的函數就可以,調用strlen之類的函數可設置字元串的長度。遺傳演算法是根據大自然中生物體進化規律而設計提出的。