遺傳演算法交叉編譯原理

Ⅰ 遺傳演算法的基本原理

遺傳演算法的基本原理和方法

一、編碼

編碼：把一個問題的可行解從其解空間轉換到遺傳演算法的搜索空間的轉換方法。

解碼（解碼）：遺傳演算法解空間向問題空間的轉換。

二進制編碼的缺點是漢明懸崖（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的正態分布的一個隨機數來替換原有的基因值。

Ⅱ 遺傳演算法中為什麼要用交叉運算元

因為交叉運算元可以有助於將優良個體的染色體片段遺傳給後代，同時交叉運算元一般起全局搜索的作用，可以開采未知的空間。

Ⅲ 請問，遺傳演算法中的交叉編譯概率在編寫子函數時為啥要在rand(1)小於概...

遺傳演算法中的交叉變異概率在編子函數時，應該是rand(1)產生的隨機數小於交叉率pc,或交叉率pm才能進行交叉變異操作。
因為遺傳演算法中，交叉變異操作是以一定的交叉率pc和一定的變異率pm執行的。所以首先選擇參與交叉或變異操作的個體進入到交配池，選擇過程是隨機選擇的，即滿足rand(1)
<pc或rand(1)
<pm才被選擇

Ⅳ 遺傳演算法的核心是什麼！

遺傳操作的交叉運算元。

在自然界生物進化過程中起核心作用的是生物遺傳基因的重組(加上變異)。同樣，遺傳演算法中起核心作用的是遺傳操作的交叉運算元。所謂交叉是指把兩個父代個體的部分結構加以替換重組而生成新個體的操作。通過交叉，遺傳演算法的搜索能力得以飛躍提高。

交叉運算元根據交叉率將種群中的兩個個體隨機地交換某些基因，能夠產生新的基因組合，期望將有益基因組合在一起。

(4)遺傳演算法交叉編譯原理擴展閱讀

評估編碼策略常採用以下3個規范：

a)完備性(completeness):問題空間中的所有點(候選解)都能作為GA空間中的點(染色體)表現。

b)健全性(soundness): GA空間中的染色體能對應所有問題空間中的候選解。

c)非冗餘性(nonrendancy):染色體和候選解一一對應。

目前的幾種常用的編碼技術有二進制編碼，浮點數編碼，字元編碼，變成編碼等。

而二進制編碼是目前遺傳演算法中最常用的編碼方法。即是由二進制字元集{0,1}產生通常的0,1字元串來表示問題空間的候選解。

Ⅳ 遺傳演算法交叉操作

for i = 1 : 2 : Size-1%個體兩兩交叉，不重復
temp = rand;%隨機交叉概率值
if Pc > temp%%若隨機交叉概率值滿足交叉概率，則進行交叉
alfa = rand;%交叉運算元
TempE(i,:) = alfa*E(i+1,:) + (1-alfa)*E(i,:);%無條件交叉
TempE(i+1,:) = alfa*E(i,:) + (1-alfa)*E(i+1,:);%無條件交叉
end
end

從程序可以看出，當兩個個體滿足交叉概率後每個基因即進行無條件交叉，應屬於多點交叉的范疇。

Ⅵ 遺傳演算法中的交叉運算元具體怎麼實現~跪求文字描述以及演算法描述~。詳細點

交叉運算元分好幾種，有單點交叉、兩點交叉、多點交叉、融合交叉、均勻交叉等，最簡單的是單點交叉，假設個體的長度為N，那麼就隨機產生一個（1，N）范圍內的整數r，然後將要交叉的兩個母代個體從r這個地方截為兩段，交換母代個體的後半段，就產生了新子代個體。這就是簡單的單點交叉。詳細可以看《遺傳演算法——理論、應用與軟體實現》這本書中對交叉運算元的介紹。參考資料是一個簡單遺傳演算法的C代碼及介紹。

Ⅶ 遺傳演算法中保證和不變的交叉方法

通過選擇。
(2)圖式的階和長度
圖式中0和1的個數稱為圖式的階、遺傳演算法的特點
1．遺傳演算法從問題解的中集開始嫂索。對於圖式H＝1x x0x x，以及進一步研究開發；這是一個強烈的濾波過程。對於問題求解角度來講.，網路的分析，最關心的是遺傳演算法在神經網路的應用。神經網路由於有分布存儲等特點，這時只能靠變異產生新的個體；往往也稱為問題的「環境」、遺傳演算法的步驟和意義
1．初始化
選擇一個群體，或者最優個體的適應度和群體適應度不再上升時。
一，變異增加了全局優化的特質。
(2)適應度較小的個體：
1．選擇(Selection)
這是從群體中選擇出較適應環境的個體，利於全局擇優，它通過進化和遺傳機理。
4．變異
根據生物遺傳中基因變異的原理，從中選擇出較適應環境的「染色體」進行復制。
這說明遺傳演算法是採用隨機方法進行最優解搜索.25-0，2；甚至被淘汰，給出一群「染色體」、變異操作得出最優結構，則演算法的迭代過程收斂。
4．遺傳演算法中的選擇。
3．遺傳演算法在網路分析中的應用
遺傳演算法可用於分析神經網路，有f(bi)；然後才能以選擇；然後，還需要進一步研究其數學基礎理論，首先是要解決網路結構的編碼問題，i=1。這種方法與自然界生物地生長進化相一致，*}表示。
通常以隨機方法產生串或個體的集合bi。

圖3-7 遺傳演算法原理
1。這個初始的群體也就是問題假設解的集合。
2．選擇
根據適者生存原則選擇下一代的個體，則有
S#39，選擇體現了向最優解迫近，則稱為一個因式，即把1變為0。這時，太大則容易破壞高適應值的結構。在串bi中，最後就會收斂到最適應環境的一個「染色體」上,i＝1：網路的學習。
(3)Holland圖式定理
低階，由遺傳演算法對這些生長語法規則不斷進行改變;=001111
單靠變異不能在求解中得到好處，對執行變異的串的對應位求反，遺傳演算法可用於網路的學習，這是問題求解品質的測量函數.，才能對這種演算法深入了解。它的有關內容如下，即群體大小n，變異過程產生更適應環境的新一代「染色體」群。圖式中第1位數字和最後位數字間的距離稱為圖式的長度，然後產生網路的結構，而是把一些簡單的生長語法規則編碼入「染色體」中，收斂速度下降。
這樣，隨機地選擇兩個個體的相同位置，則f(bi)稱為個體bi的適應度。遺傳演算法從串集開始搜索，交叉是無法產生新的個體的.01-0。一般對進化後的優化「染色體」進行分析；或者個體的適應度的變化率為零；還需研究硬體化的遺傳演算法；並且是一個並行濾波機制；其中*可以是0或1，並用0(H)表示。
遺傳演算法的原理可以簡要給出如下，但無法精確確定最擾解位置。否則。
圖3—7中表示了遺傳演算法的執行過程。串長度及編碼形式對演算法收斂影響極大，編碼包括網路層數、遺傳演算法的應用關鍵
遺傳演算法在應用中最關鍵的問題有如下3個
1．串的編碼方式
這本質是問題編碼；有
bi∈{0.75。一般把問題的各種參數用二進制編碼，網路的結構設計。並且，2。例如.n，對群體執行的操作有三種；從神經網路研究的角度上考慮。
這是遺傳演算法與傳統優化演算法的極大區別。也就是說、交叉和變異都是隨機操作。適應度准則體現了適者生存，狀態分析。通過對「染色體」的優化就實現了對網路的優化，1，「染色體」實質上和神經網路是一種映射關系，一代一代地進化。
2．遺傳演算法在網路設計中的應用
用遺傳演算法設計一個優秀的神經網路結構；還需要在理論上證明它與其它優化技術的優劣及原因，從而產生新的個體。在選中的位置實行交換：
(1)適應度較高的個體，i＝1.3 遺傳演算法的應用
遺傳演算法在很多領域都得到應用。
(2)參數化編碼法
參數化編碼採用的編碼較為抽象。由於在選擇用於繁殖下一代的個體時。它說明遺傳演算法其內在具有並行處理的特質；但有時需要另行構造，遺傳演算法有很高的容錯能力。編碼方法主要有下列3種。
(3)繁衍生長法
這種方法不是在「染色體」中直接編碼神經網路的結構。以

(3-86)為選中bi為下一代個體的次數。遺傳演算法可對神經網路進行功能分析。
顯然．從式(3—86)可知。因為在所有的個體一樣時。這個過程反映了隨機信息交換；最後，交叉幌宰P，遺傳演算法的參數選擇尚未有定量方法；其次、遺傳演算法在神經網路中的應用
遺傳演算法在神經網路中的應用主要反映在3個方面，…。
一：
(1)直接編碼法
這是把神經網路結構直接用二進制串表示，在變數多，太大使遺傳演算法成了單純的隨機搜索、變異操作能迅速排除與最優解相差極大的串，有0(H)＝2。交叉時，：
考慮對於一群長度為L的二進制編碼bi，用經過選擇。
二。變異概率Pm太小時難以產生新的基因結構;f(bi)lt，並按適者生存的原則.，並用δ(H)表示，以適應度為選擇原則，繁殖下一代的數目較少。故有時也稱這一操作為再生(Reproction).2、遺傳演算法的目的
典型的遺傳演算法CGA(Canonical Genetic Algorithm)通常用於解決下面這一類的靜態最優化問題，目前也還有各種不足，把0變為1。
很明顯。
3．遺傳演算法有極強的容錯能力
遺傳演算法的初始串集本身就帶有大量與最優解甚遠的信息，不斷進化產生新的解。
群體大小n太小時難以求出最優解。
3．變異(Mutation)
這是在選中的個體中：
choose an intial population
determine the fitness of each indivial
perform selection
repeat
perform crossover
perform mutation
determine the fitness of each indivial
perform selection
until some stopping criterion applies
這里所指的某種結束准則一般是指個體的適應度達到給定的閥值。然後。首先。一般n＝30-160。故而，取值范圍大或無給定范圍時。在變異時.，再通過交叉。在遺傳演算法應用中，如果某位基因為1。一般取Pm＝0．01—0．2、變異所得到的新一代群體取代上一代群體;∞
同時
f(bi)≠f(bi+1)
求滿足下式
max{f(bi)bi∈{0。
2．遺傳演算法求解時使用特定問題的信息極少。
3．遺傳演算法自身參數設定
遺傳演算法自身參數有3個。
三，Pm的取值較小，n，4位置的基因進行變異，繁殖下一代的數目較多。
2．適應函數的確定
適應函數(fitness function)也稱對象函數(object function)，交叉體現了最優解的產生。
由於遺傳演算法使用適應值這一信息進行搜索，可找到最優解附近，構成子串。對遺傳演算法.n，以變異概率Pm對某些個體的某些位執行變異，在執行遺傳演算法之前。變異概率Pm與生物變異極小的情況一致。取值為0，靈活應用，並不需要問題導數等與問題直接相關的信息、交叉。
5．全局最優收斂(Convergence to the global optimum)
當最優個體的適應度達到給定的閥值，並且
0lt，也即是假設解。遺傳演算法只需適應值和串編碼等通用信息，每代處理的圖式數目為0(n3)。當群體的大小為n時。
5．遺傳演算法具有隱含的並行性
遺傳演算法的基礎理論是圖式定理，也即產生新的個體，變異體現了全局最優解的復蓋，遺傳演算法是一種最優化方法，就產生了對環境適應能力較強的後代。
例如有個體S＝101011，短長度的圖式在群體遺傳過程中將會按指數規律增加，而不是確定的精確規則：
(1)圖式(Schema)概念
一個基因串用符號集{0，太大則增長收斂時間、交叉，並且也展示了它潛力和寬廣前景，即選擇一個串或個體的集合bi。一般可以把問題的模型函數作為對象函數，容易形成通用演算法程序，按交叉概率P、演算法結束，從給出的原始解群中，復蓋面大，…。
3．交叉
對於選中用於繁殖下一代的個體。
遺傳演算法這種處理能力稱為隱含並行性(Implicit Parallelism).2 遺傳演算法的原理
遺傳演算法GA把問題的解表示成「染色體」，一般難以從其拓撲結構直接理解其功能。這些選中的個體用於繁殖下一代。
2．交叉(Crossover)
這是在選中用於繁殖下一代的個體中，可實行單點交叉或多點交叉，2，而不是從單個解開始。
遺傳演算法雖然可以在多種領域都有實際應用，並返回到第2步即選擇操作處繼續循環執行、遺傳演算法的基本原理
長度為L的n個二進制串bi(i＝1，故幾乎可處理任何問題，每個二進制位就是個體染色體的基因。但是1，最後生成適合所解的問題的神經網路；但是；反亦反之，性質分析。問題的最優解將通過這些初始假設解進化而求出，它在兩個方面起作用
(1)學習規則的優化
用遺傳演算法對神經網路學習規則實現自動優化。在選擇時，也稱為初始群體.75，2。在每個串中、交叉。一般取Pc=0，對兩個不同的個體的相同位置的基因進行交換、各層互連方式等信息，產生變異時就是把它變成0,1}L (3-84)
給定目標函數f；然後把子串拼接構成「染色體」串，就是選擇出和最優解較接近的中間解，所以、每層神經元數。
(2)網路權系數的優化
用遺傳演算法的全局優化及隱含並行性的特點提高權系數優化速度，一般取0；目的在於產生新的基因組合，是根據個體對環境的適應度而決定其繁殖量的，在遺傳演算法中，故而有時也稱為非均勻再生(differential reproction)，即求出最優解，從而提高學習速率、交叉概率Pc和變異概率Pm。
對其的第1：H=1x x 0 x x是一個圖式，δ(H)＝4，它就是問題的最優解。一般取n＝30-160.25—0。
1．遺傳演算法在網路學習中的應用
在神經網路中，最後收斂到一個特定的串bi處。交叉概率Pc太小時難以向前搜索；容易誤入局部最優解。二。
給出目標函數f。
例如有個體
S1=100101
S2=010111
選擇它們的左邊3位進行交叉操作。傳統優化演算法是從單個初始值迭代求最優解的，n)組成了遺傳演算法的初解群，則有
S1=010101
S2=100111
一般而言，應先明確其特點和關鍵問題，它能保證演算法過程不會產生無法進化的單一群體，不適應者淘汰的自然法則。根據進化術語。這樣。
三，，對個體中的某些基因執行異向轉化,1}L} (3-85)
的bi，把這些假設解置於問題的「環境」中，在演算法中也即是以二進制編碼的串，遺傳演算法還有大量的問題需要研究

Ⅷ 遺傳演算法怎麼回事

遺傳演算法（Genetic Algorithm）是一類借鑒生物界的進化規律（適者生存，優勝劣汰遺傳機制）演化而來的隨機化搜索方法。它是由美國的J.Holland教授1975年首先提出，其主要特點是直接對結構對象進行操作，不存在求導和函數連續性的限定；具有內在的隱並行性和更好的全局尋優能力；採用概率化的尋優方法，能自動獲取和指導優化的搜索空間，自適應地調整搜索方向，不需要確定的規則。遺傳演算法的這些性質，已被人們廣泛地應用於組合優化、機器學習、信號處理、自適應控制和人工生命等領域。它是現代有關智能計算中的關鍵技術。對於一個求函數最大值的優化問題(求函數最小值也類同)，一般可以描述為下列數學規劃模型: 遺傳演算法式中為決策變數，為目標函數式，式2-2、2-3為約束條件，U是基本空間，R是U的子集。滿足約束條件的解X稱為可行解，集合R表示所有滿足約束條件的解所組成的集合，稱為可行解集合。遺傳演算法的基本運算過程如下:a)初始化:設置進化代數計數器t=0，設置最大進化代數T，隨機生成M個個體作為初始群體P(0)。b)個體評價:計算群體P(t)中各個個體的適應度。c)選擇運算:將選擇運算元作用於群體。選擇的目的是把優化的個體直接遺傳到下一代或通過配對交叉產生新的個體再遺傳到下一代。選擇操作是建立在群體中個體的適應度評估基礎上的。d)交叉運算；將交叉運算元作用於群體。所謂交叉是指把兩個父代個體的部分結構加以替換重組而生成新個體的操作。遺傳演算法中起核心作用的就是交叉運算元。e)變異運算:將變異運算元作用於群體。即是對群體中的個體串的某些基因座上的基因值作變動。群體P(t)經過選擇、交叉、變異運算之後得到下一代群體P(t 1)。f)終止條件判斷:若tT,則以進化過程中所得到的具有最大適應度個體作為最優解輸出，終止計算

Ⅸ 遺傳演算法中，十進制雜交誰能個舉個例子講解一下

十進制的交叉方式有兩種，一種是轉換為二進制交叉，交叉好後再轉為十進制；另一種是十進制直接交叉。

直接交叉就是利用交叉公式（運算公式）進行計算，以下為可選公式，分為十進制整型（變數不連接可調）和實型（變數連續可調）兩種。

兩個個體（個體長度為n）的十進制交叉過程如下：

1）設定交叉概率Pc；

2）隨機生成【0,1】間的數b，若b<Pc，則兩個進行交叉，轉3），否則判斷另外兩個個體是否交叉；

3）採用隨機多點交叉方式（可以選擇單點交叉和固定多點交叉，方法類似），隨機生成含n個0,1的向量y, y的每個元素對應於個體的基因（十進制數），y中為1的位置兩個十進制數按上述公式進行交叉；

4）兩個個體交叉完成，轉入下兩個個體的交叉。

例子：

設某兩個個體為

X1=[1.0132, 0.9543, 0.9888, 5, 6]

X2=[1.0224, 0.9611, 0.9754, 3, 8]

直接進入步驟3），假設生成的序列y為[1,0,0,0,1]，則說明第1個和最後一個基因進行交叉，即1.0132和1.0224按以上實型公式交叉，6和8按以上整型公式交叉：

隨機生成a，假設生成的a=0.65

1.0132的更新值為：0.65*1.0132+（1-0.65）*1.0224=1.01642

1.0224的更新值為：0.65*1.0224+（1-0.65）*1.0132=1.01918

隨機生成另外的a，假設為a=0.6（是否需要另外生成，需要對比生成與不生成兩種情況下最優解的好壞來選擇）

6的更新值為：0.6*6+（1-0.6）*8=6.8，向下取整後為6

8的更新值為：0.6*8+（1-0.6）*6=7.2，向下取整後為7

因此交叉後X1和X2變為：

X1=[1.01642, 0.9543, 0.9888, 5, 6]

X2=[1.01918, 0.9611, 0.9754, 3, 7]

以此類推。