【路徑規(guī)劃】基于遺傳算法實(shí)現(xiàn)物流中心配送方案matlab源碼
定義
遺傳算法（Genetic Algorithm, GA）起源于對(duì)生物系統(tǒng)所進(jìn)行的計(jì)算機(jī)模擬研究。它是模仿自然界生物進(jìn)化機(jī)制發(fā)展起來(lái)的隨機(jī)全局搜索和優(yōu)化方法，借鑒了達(dá)爾文的進(jìn)化論和孟德爾的遺傳學(xué)說(shuō)。其本質(zhì)是一種高效、并行、全局搜索的方法，能在搜索過(guò)程中自動(dòng)獲取和積累有關(guān)搜索空間的知識(shí)，并自適應(yīng)地控制搜索過(guò)程以求得最佳解。
相關(guān)術(shù)語(yǔ)
基因型(genotype)：性狀染色體的內(nèi)部表現(xiàn)。
表現(xiàn)型(phenotype)：染色體決定的性狀的外部表現(xiàn)，或者說(shuō)，根據(jù)基因型形成的個(gè)體的外部表現(xiàn)。
進(jìn)化(evolution)：種群逐漸適應(yīng)生存環(huán)境，品質(zhì)不斷得到改良。生物的進(jìn)化是以種群的形式進(jìn)行的。
適應(yīng)度(fitness)：度量某個(gè)物種對(duì)于生存環(huán)境的適應(yīng)程度。
選擇(selection)：以一定的概率從種群中選擇若干個(gè)個(gè)體。一般，選擇過(guò)程是一種基于適應(yīng)度的優(yōu)勝劣汰的過(guò)程。
復(fù)制(reproduction)：細(xì)胞分裂時(shí)，遺傳物質(zhì)DNA通過(guò)復(fù)制而轉(zhuǎn)移到新產(chǎn)生的細(xì)胞中，新細(xì)胞就繼承了舊細(xì)胞的基因。
交叉(crossover)：兩個(gè)染色體的某一相同位置處DNA被切斷，前后兩串分別交叉組合形成兩個(gè)新的染色體。也稱基因重組或雜交。
變異(mutation)：復(fù)制時(shí)可能（很小的概率）產(chǎn)生某些復(fù)制差錯(cuò)，變異產(chǎn)生新的染色體，表現(xiàn)出新的性狀。
編碼(coding)：DNA中遺傳信息在一個(gè)長(zhǎng)鏈上按一定的模式排列。遺傳編碼可看作從表現(xiàn)型到基因型的映射。
解碼(decoding)：基因型到表現(xiàn)型的映射。
個(gè)體（individual）：指染色體帶有特征的實(shí)體。
種群（population）：個(gè)體的集合，該集合內(nèi)個(gè)體數(shù)稱為種群的大小。
交叉
變異
產(chǎn)生子代完整過(guò)程
遺傳算法應(yīng)用
遺傳算法的有趣應(yīng)用很多，諸如尋路問(wèn)題，8數(shù)碼問(wèn)題，囚犯困境，動(dòng)作控制，找圓心問(wèn)題（在一個(gè)不規(guī)則的多邊形中，尋找一個(gè)包含在該多邊形內(nèi)的最大圓圈的圓心），TSP問(wèn)題，生產(chǎn)調(diào)度問(wèn)題，人工生命模擬等。下面以袋鼠為例子講講遺傳算法。
遺傳算法中每一條染色體，對(duì)應(yīng)著遺傳算法的一個(gè)解決方案，一般我們用適應(yīng)性函數(shù)（fitness function）來(lái)衡量這個(gè)解決方案的優(yōu)劣。所以從一個(gè)基因組到其解的適應(yīng)度形成一個(gè)映射?？梢园堰z傳算法的過(guò)程看作是一個(gè)在多元函數(shù)里面求最優(yōu)解的過(guò)程?？梢赃@樣想象，這個(gè)多維曲面里面有數(shù)不清的“山峰”，而這些山峰所對(duì)應(yīng)的就是局部最優(yōu)解。而其中也會(huì)有一個(gè)“山峰”的海拔最高的，那么這個(gè)就是全局最優(yōu)解。而遺傳算法的任務(wù)就是盡量爬到最高峰，而不是陷落在一些小山峰。（另外，值得注意的是遺傳算法不一定要找“最高的山峰”，如果問(wèn)題的適應(yīng)度評(píng)價(jià)越小越好的話，那么全局最優(yōu)解就是函數(shù)的最小值，對(duì)應(yīng)的，遺傳算法所要找的就是“最深的谷底”）
問(wèn)題的提出與解決方案
先來(lái)考慮如何求出下面的一元函數(shù)在既定區(qū)間的最優(yōu)解。
“袋鼠跳”問(wèn)題
既然我們把函數(shù)曲線理解成一個(gè)一個(gè)山峰和山谷組成的山脈。那么我們可以設(shè)想所得到的每一個(gè)解就是一只袋鼠，我們希望它們不斷的向著更高處跳去，直到跳到最高的山峰（盡管袋鼠本身不見得愿意那么做）。所以求最大值的過(guò)程就轉(zhuǎn)化成一個(gè)“袋鼠跳”的過(guò)程。
作為對(duì)比下面簡(jiǎn)單介紹“袋鼠跳”的幾種方式。
爬山法（最速上升爬山法）
從搜索空間中隨機(jī)產(chǎn)生鄰近的點(diǎn)，從中選擇對(duì)應(yīng)解最優(yōu)的個(gè)體，替換原來(lái)的個(gè)體，不斷重復(fù)上述過(guò)程。因?yàn)榕郎椒ㄖ粚?duì)“鄰近”的點(diǎn)作比較，所以目光比較“短淺”，常常只能收斂到離開初始位置比較近的局部最優(yōu)解上面。對(duì)于存在很多局部最優(yōu)點(diǎn)的問(wèn)題，通過(guò)一個(gè)簡(jiǎn)單的迭代找出全局最優(yōu)解的機(jī)會(huì)非常渺茫。（在爬山法中，袋鼠最有希望到達(dá)最靠近它出發(fā)點(diǎn)的山頂，但不能保證該山頂是珠穆朗瑪峰，或者是一個(gè)非常高的山峰。因?yàn)橐宦飞纤活櫳掀?，沒(méi)有下坡。）
模擬退火
這個(gè)方法來(lái)自金屬熱加工過(guò)程的啟發(fā)。在金屬熱加工過(guò)程中，當(dāng)金屬的溫度超過(guò)它的熔點(diǎn)（Melting Point）時(shí)，原子就會(huì)激烈地隨機(jī)運(yùn)動(dòng)。與所有的其它的物理系統(tǒng)相類似，原子的這種運(yùn)動(dòng)趨向于尋找其能量的極小狀態(tài)。在這個(gè)能量的變遷過(guò)程中，開始時(shí)，溫度非常高， 使得原子具有很高的能量。隨著溫度不斷降低，金屬逐漸冷卻，金屬中的原子的能量就越來(lái)越小，最后達(dá)到所有可能的最低點(diǎn)。利用模擬退火的時(shí)候，讓算法從較大的跳躍開始，使到它有足夠的“能量”逃離可能“路過(guò)”的局部最優(yōu)解而不至于限制在其中，當(dāng)它停在全局最優(yōu)解附近的時(shí)候，逐漸的減小跳躍量，以便使其“落腳 ”到全局最優(yōu)解上。（在模擬退火中，袋鼠喝醉了，而且隨機(jī)地大跳躍了很長(zhǎng)時(shí)間。運(yùn)氣好的話，它從一個(gè)山峰跳過(guò)山谷，到了另外一個(gè)更高的山峰上。但最后，它漸漸清醒了并朝著它所在的峰頂跳去。）
遺傳算法
模擬物競(jìng)天擇的生物進(jìn)化過(guò)程，通過(guò)維護(hù)一個(gè)潛在解的群體執(zhí)行了多方向的搜索，并支持這些方向上的信息構(gòu)成和交換。是以面為單位的搜索，比以點(diǎn)為單位的搜索，更能發(fā)現(xiàn)全局最優(yōu)解。（在遺傳算法中，有很多袋鼠，它們降落到喜瑪拉雅山脈的任意地方。這些袋鼠并不知道它們的任務(wù)是尋找珠穆朗瑪峰。但每過(guò)幾年，就在一些海拔高度較低的地方射殺一些袋鼠，并希望存活下來(lái)的袋鼠是多產(chǎn)的，在它們所處的地方生兒育女。）（或者換個(gè)說(shuō)法。從前，有一大群袋鼠，它們被莫名其妙的零散地遺棄于喜馬拉雅山脈。于是只好在那里艱苦的生活。海拔低的地方彌漫著一種無(wú)色無(wú)味的毒氣，海拔越高毒氣越稀薄?？墒强蓱z的袋鼠們對(duì)此全然不覺(jué)，還是習(xí)慣于活蹦亂跳。于是，不斷有袋鼠死于海拔較低的地方，而越是在海拔高的袋鼠越是能活得更久，也越有機(jī)會(huì)生兒育女。就這樣經(jīng)過(guò)許多年，這些袋鼠們竟然都不自覺(jué)地聚攏到了一個(gè)個(gè)的山峰上，可是在所有的袋鼠中，只有聚攏到珠穆朗瑪峰的袋鼠被帶回了美麗的澳洲。）
遺傳算法的實(shí)現(xiàn)過(guò)程
遺傳算法實(shí)現(xiàn)過(guò)程
遺傳算法的實(shí)現(xiàn)過(guò)程實(shí)際上就像自然界的進(jìn)化過(guò)程那樣。首先尋找一種對(duì)問(wèn)題潛在解進(jìn)行“數(shù)字化”編碼的方案。（建立表現(xiàn)型和基因型的映射關(guān)系）然后用隨機(jī)數(shù)初始化一個(gè)種群（那么第一批袋鼠就被隨意地分散在山脈上），種群里面的個(gè)體就是這些數(shù)字化的編碼。接下來(lái)，通過(guò)適當(dāng)?shù)慕獯a過(guò)程之后（得到袋鼠的位置坐標(biāo)），用適應(yīng)性函數(shù)對(duì)每一個(gè)基因個(gè)體作一次適應(yīng)度評(píng)估（袋鼠爬得越高，越是受我們的喜愛，所以適應(yīng)度相應(yīng)越高）。用選擇函數(shù)按照某種規(guī)定擇優(yōu)選擇（我們要每隔一段時(shí)間，在山上射殺一些所在海拔較低的袋鼠，以保證袋鼠總體數(shù)目持平。）。讓個(gè)體基因變異（讓袋鼠隨機(jī)地跳一跳）。然后產(chǎn)生子代（希望存活下來(lái)的袋鼠是多產(chǎn)的，并在那里生兒育女）。遺傳算法并不保證你能獲得問(wèn)題的最優(yōu)解，但是使用遺傳算法的最大優(yōu)點(diǎn)在于你不必去了解和操心如何去“找”最優(yōu)解。（你不必去指導(dǎo)袋鼠向那邊跳，跳多遠(yuǎn)。）而只要簡(jiǎn)單的“否定”一些表現(xiàn)不好的個(gè)體就行了。（把那些總是愛走下坡路的袋鼠射殺，這就是遺傳算法的精粹?。?/p>
遺傳算法的一般步驟
遺傳算法中每一條染色體，對(duì)應(yīng)著遺傳算法的一個(gè)解決方案，一般我們用適應(yīng)性函數(shù)（fitness function）來(lái)衡量這個(gè)解決方案的優(yōu)劣。所以從一個(gè)基因組到其解的適應(yīng)度形成一個(gè)映射。遺傳算法的實(shí)現(xiàn)過(guò)程實(shí)際上就像自然界的進(jìn)化過(guò)程那樣。
下面我們用袋鼠跳中的步驟一一對(duì)應(yīng)解釋，以方便大家理解：
1.首先尋找一種對(duì)問(wèn)題潛在解進(jìn)行“數(shù)字化”編碼的方案。（建立表現(xiàn)型和基因型的映射關(guān)系）
2.隨機(jī)初始化一個(gè)種群（那么第一批袋鼠就被隨意地分散在山脈上），種群里面的個(gè)體就是這些數(shù)字化的編碼
3.接下來(lái)，通過(guò)適當(dāng)?shù)慕獯a過(guò)程之后（得到袋鼠的位置坐標(biāo)）
4.用適應(yīng)性函數(shù)對(duì)每一個(gè)基因個(gè)體作一次適應(yīng)度評(píng)估（袋鼠爬得越高當(dāng)然就越好，所以適應(yīng)度相應(yīng)越高）
5.用選擇函數(shù)按照某種規(guī)定擇優(yōu)選擇（每隔一段時(shí)間，射殺一些所在海拔較低的袋鼠，以保證袋鼠總體數(shù)目持平）
讓個(gè)體基因變異（讓袋鼠隨機(jī)地跳一跳）
6.然后產(chǎn)生子代（希望存活下來(lái)的袋鼠是多產(chǎn)的，并在那里生兒育女）
由此我們可以得出遺傳算法的一般步驟：
1.隨機(jī)產(chǎn)生種群
2.根據(jù)策略判斷個(gè)體的適應(yīng)度，是否符合優(yōu)化準(zhǔn)則，若符合，輸出最佳個(gè)體及其最優(yōu)解，結(jié)束。否則，進(jìn)行下一步
3.依據(jù)適應(yīng)度選擇父母，適應(yīng)度高的個(gè)體被選中的概率高，適應(yīng)度低的個(gè)體被淘汰
4.用父母的染色體按照一定的方法進(jìn)行交叉，生成子代
5.對(duì)子代染色體進(jìn)行變異
由交叉和變異產(chǎn)生新一代種群，返回步驟2，直到最優(yōu)解產(chǎn)生
遺傳算法圖解
進(jìn)化細(xì)節(jié)
種群和個(gè)體
遺傳算法啟發(fā)自進(jìn)化理論，而我們知道進(jìn)化是由種群為單位的，種群是什么呢？維基百科上解釋為：在生物學(xué)上，是在一定空間范圍內(nèi)同時(shí)生活著的同種生物的全部個(gè)體。顯然要想理解種群的概念，又先得理解個(gè)體的概念，在遺傳算法里，個(gè)體通常為某個(gè)問(wèn)題的一個(gè)解，并且該解在計(jì)算機(jī)中被編碼為一個(gè)向量表示！ 我們的例子中要求最大值，所以該問(wèn)題的解為一組可能的(x,y) (x, y)(x,y)的取值。比如(x=2.1,y=0.8),(x=?1.5,y=2.3)… 就是求最大值問(wèn)題的一個(gè)可能解，也就是遺傳算法里的個(gè)體，把這樣的一組一組的可能解的集合就叫做種群?，比如在這個(gè)問(wèn)題中設(shè)置100個(gè)這樣的x,y 的可能的取值對(duì)，這100個(gè)個(gè)體就構(gòu)成了種群。
編碼方法
在上面?zhèn)€體概念里提到個(gè)體（也就是一組可能解）在計(jì)算機(jī)程序中被編碼為一個(gè)向量表示，而在我們這個(gè)問(wèn)題中，個(gè)體是x,y 的取值，是兩個(gè)實(shí)數(shù)，所以問(wèn)題就可以轉(zhuǎn)化為如何將實(shí)數(shù)編碼為一個(gè)向量表示，可能有些朋友有疑惑，實(shí)數(shù)在計(jì)算機(jī)里不是可以直接存儲(chǔ)嗎，為什么需要編碼呢？這里編碼是為了后續(xù)操作（交叉和變異）的方便。
生物的DNA有四種堿基對(duì)，分別是ACGT，DNA的編碼可以看作是DNA上堿基對(duì)的不同排列，不同的排列使得基因的表現(xiàn)出來(lái)的性狀也不同（如單眼皮雙眼皮）。在計(jì)算機(jī)中，我們可以模仿這種編碼，但是堿基對(duì)的種類只有兩種，分別是0，1。只要我們能夠?qū)⒉煌膶?shí)數(shù)表示成不同的0，1二進(jìn)制串表示就完成了編碼，也就是說(shuō)其實(shí)我們并不需要去了解一個(gè)實(shí)數(shù)對(duì)應(yīng)的二進(jìn)制具體是多少，我們只需要保證有一個(gè)映射
1
能夠?qū)⑹M(jìn)制的數(shù)編碼為二進(jìn)制即可，至于這個(gè)映射是什么，其實(shí)可以不必關(guān)心。將個(gè)體（可能解）編碼后的二進(jìn)制串叫做染色體，染色體（或者有人叫DNA）就是個(gè)體（可能解）的二進(jìn)制編碼表示。為什么可以不必關(guān)心映射f(x)呢？因?yàn)槠鋵?shí)我們?cè)诔绦蛑胁倏v的都是二進(jìn)制串，而二進(jìn)制串生成時(shí)可以隨機(jī)生成。
編碼是應(yīng)用遺傳算法時(shí)要解決的首要問(wèn)題，也是設(shè)計(jì)遺傳算法時(shí)的一個(gè)關(guān)鍵步驟。編碼方法影響到交叉算子、變異算子等遺傳算子的運(yùn)算方法，大很大程度上決定了遺傳進(jìn)化的效率。
迄今為止人們已經(jīng)提出了許多種不同的編碼方法?？偟膩?lái)說(shuō)，這些編碼方法可以分為三大類：二進(jìn)制編碼法、浮點(diǎn)編碼法、符號(hào)編碼法。下面分別進(jìn)行介紹：
二進(jìn)制編碼
就像人類的基因有AGCT 4種堿基序列一樣。不過(guò)在這里我們只用了0和1兩種堿基,然后將他們串成一條鏈形成染色體。一個(gè)位能表示出2種狀態(tài)的信息量，因此足夠長(zhǎng)的二進(jìn)制染色體便能表示所有的特征。這便是二進(jìn)制編碼。如下：
1110001010111
它由二進(jìn)制符號(hào)0和1所組成的二值符號(hào)集。有以下一些優(yōu)點(diǎn)：
1.編碼、解碼操作簡(jiǎn)單易行
2.交叉、變異等遺傳操作便于實(shí)現(xiàn)
3.符合最小字符集編碼原則
4.利用模式定理對(duì)算法進(jìn)行理論分析
缺點(diǎn)：對(duì)于一些連續(xù)函數(shù)的優(yōu)化問(wèn)題，由于其隨機(jī)性使得其局部搜索能力較差，如對(duì)于一些高精度的問(wèn)題，當(dāng)解迫近于最優(yōu)解后，由于其變異后表現(xiàn)型變化很大（比如00000變異成10000等），不連續(xù)，所以會(huì)遠(yuǎn)離最優(yōu)解，達(dá)不到穩(wěn)定。
浮點(diǎn)編碼法
二進(jìn)制編碼雖然簡(jiǎn)單直觀，但明顯地存在著連續(xù)函數(shù)離散化時(shí)的映射誤差。個(gè)體長(zhǎng)度較短時(shí)，可能達(dá)不到精度要求，而個(gè)體編碼長(zhǎng)度較長(zhǎng)時(shí)，雖然能提高精度，但增加了解碼的難度，使遺傳算法的搜索空間急劇擴(kuò)大。
所謂浮點(diǎn)法，是指?jìng)€(gè)體的每個(gè)基因值用某一范圍內(nèi)的一個(gè)浮點(diǎn)數(shù)來(lái)表示。在浮點(diǎn)數(shù)編碼方法中，必須保證基因值在給定的區(qū)間限制范圍內(nèi)，遺傳算法中所使用的交叉、變異等遺傳算子也必須保證其運(yùn)算結(jié)果所產(chǎn)生的新個(gè)體的基因值也在這個(gè)區(qū)間限制范圍內(nèi)。如下所示：
1.2-3.2-5.3-7.2-1.4-9.7
浮點(diǎn)數(shù)編碼方法有下面幾個(gè)優(yōu)點(diǎn)：
1.適用于在遺傳算法中表示范圍較大的數(shù)
2.適用于精度要求較高的遺傳算法
3.便于較大空間的遺傳搜索
4.改善了遺傳算法的計(jì)算復(fù)雜性，提高了運(yùn)算交率
5.便于遺傳算法與經(jīng)典優(yōu)化方法的混合使用
6.便于設(shè)計(jì)針對(duì)問(wèn)題的專門知識(shí)的知識(shí)型遺傳算子
7.便于處理復(fù)雜的決策變量約束條件
符號(hào)編碼法
符號(hào)編碼法是指?jìng)€(gè)體染色體編碼串中的基因值取自一個(gè)無(wú)數(shù)值含義、而只有代碼含義的符號(hào)集如｛A,B,C…｝。
符號(hào)編碼的主要優(yōu)點(diǎn)是：
1.符合有意義積術(shù)塊編碼原則
2.便于在遺傳算法中利用所求解問(wèn)題的專門知識(shí)
3.便于遺傳算法與相關(guān)近似算法之間的混合使用。
袋鼠染色體編碼
在上面介紹了一系列編碼方式以后，那么，如何利用上面的編碼來(lái)為我們的袋鼠染色體編碼呢？首先我們要明確一點(diǎn)：編碼無(wú)非就是建立從基因型到表現(xiàn)型的映射關(guān)系。這里的表現(xiàn)型可以理解為個(gè)體特征（比如身高、體重、毛色等等）。那么，在此問(wèn)題下，我們關(guān)心的個(gè)體特征就是：袋鼠的位置坐標(biāo)（因?yàn)槲覀円押０蔚偷拇蠼o殺掉）。無(wú)論袋鼠長(zhǎng)什么樣，愛吃什么。我們關(guān)心的始終是袋鼠在哪里，并且只要知道了袋鼠的位置坐標(biāo)（位置坐標(biāo)就是相應(yīng)的染色體編碼，可以通過(guò)解碼得出），我們就可以：
1.在喜馬拉雅山脈的地圖上找到相應(yīng)的位置坐標(biāo)，算出海拔高度。（相當(dāng)于通過(guò)自變量求得適應(yīng)函數(shù)的值）然后判讀該不該射殺該袋鼠。
2.可以知道染色體交叉和變異后袋鼠新的位置坐標(biāo)。
上文所提的求一元函數(shù)最大值的問(wèn)題。在上面我們把極大值比喻為山峰，那么，袋鼠的位置坐標(biāo)可以比喻為區(qū)間[-1, 2]的某一個(gè)x坐標(biāo)（有了x坐標(biāo)，再通過(guò)函數(shù)表達(dá)式可以算出函數(shù)值 <==> 得到了袋鼠染色體編碼，解碼得到位置坐標(biāo)，在喜馬拉雅山脈地圖查詢位置坐標(biāo)算出海拔高度）。這個(gè)x坐標(biāo)是一個(gè)實(shí)數(shù)，現(xiàn)在，說(shuō)白了就是怎么對(duì)這個(gè)x坐標(biāo)進(jìn)行編碼。下面以二進(jìn)制編碼為例，不過(guò)這種情況下以二進(jìn)制編碼比較復(fù)雜。
一定長(zhǎng)度的二進(jìn)制編碼序列，只能表示一定精度的浮點(diǎn)數(shù)。在這里假如我們要求解精確到六位小數(shù)，由于區(qū)間為[-1,2]，所以長(zhǎng)度為3 ,為了保證精度要求，至少把區(qū)間[-1,2]分為3 × 10^6等份。又因?yàn)?/p>
所以編碼的二進(jìn)制串至少需要22位。
把一個(gè)二進(jìn)制串（b0,b1,…bn)轉(zhuǎn)化位區(qū)間里面對(duì)應(yīng)的實(shí)數(shù)值通過(guò)下面兩個(gè)步驟。
1.將一個(gè)二進(jìn)制串代表的二進(jìn)制數(shù)轉(zhuǎn)化為10進(jìn)制數(shù)：
2.對(duì)應(yīng)區(qū)間內(nèi)的實(shí)數(shù)：
例如一個(gè)二進(jìn)制串<1000101110110101000111>表示實(shí)數(shù)值0.637197
以上編碼方式只是舉個(gè)例子便于理解，編碼的方式千奇百怪，層出不窮，每個(gè)問(wèn)題可能采用的編碼方式都不一樣。在這一點(diǎn)上大家要注意。
評(píng)價(jià)個(gè)體的適應(yīng)度–適應(yīng)度函數(shù)（fitness function）
適應(yīng)度函數(shù)主要是通過(guò)個(gè)體特征從而判斷個(gè)體的適應(yīng)度。在本例的袋鼠跳中，我們只關(guān)心袋鼠的海拔高度，以此來(lái)判斷是否該射殺該袋鼠。這樣一來(lái)，該函數(shù)就非常簡(jiǎn)單了。只要輸入袋鼠的位置坐標(biāo)，在通過(guò)相應(yīng)查找運(yùn)算，返回袋鼠當(dāng)前位置的海拔高度就行。
適應(yīng)度函數(shù)也稱評(píng)價(jià)函數(shù)，是根據(jù)目標(biāo)函數(shù)確定的用于區(qū)分群體中個(gè)體好壞的標(biāo)準(zhǔn)。適應(yīng)度函數(shù)總是非負(fù)的，而目標(biāo)函數(shù)可能有正有負(fù)，故需要在目標(biāo)函數(shù)與適應(yīng)度函數(shù)之間進(jìn)行變換。
評(píng)價(jià)個(gè)體適應(yīng)度的一般過(guò)程為：
1.對(duì)個(gè)體編碼串進(jìn)行解碼處理后，可得到個(gè)體的表現(xiàn)型。
2.由個(gè)體的表現(xiàn)型可計(jì)算出對(duì)應(yīng)個(gè)體的目標(biāo)函數(shù)值
根據(jù)最優(yōu)化問(wèn)題的類型，由目標(biāo)函數(shù)值按一定的轉(zhuǎn)換規(guī)則求出個(gè)體的適應(yīng)度
射殺一些袋鼠–選擇函數(shù)（selection）
遺傳算法中的選擇操作就是用來(lái)確定如何從父代群體中按某種方法選取那些個(gè)體，以便遺傳到下一代群體。選擇操作用來(lái)確定重組或交叉?zhèn)€體，以及被選個(gè)體將產(chǎn)生多少個(gè)子代個(gè)體。前面說(shuō)了，我們希望海拔高的袋鼠存活下來(lái)，并盡可能繁衍更多的后代。但我們都知道，在自然界中，適應(yīng)度高的袋鼠越能繁衍后代，但這也是從概率上說(shuō)的而已。畢竟有些適應(yīng)度低的袋鼠也可能逃過(guò)我們的眼睛。
那么，怎么建立這種概率關(guān)系呢？
下面介紹幾種常用的選擇算子：
輪盤賭選擇（Roulette Wheel Selection）：是一種回放式隨機(jī)采樣方法。每個(gè)個(gè)體進(jìn)入下一代的概率等于它的適應(yīng)度值與整個(gè)種群中個(gè)體適應(yīng)度值和的比例。選擇誤差較大。
隨機(jī)競(jìng)爭(zhēng)選擇（Stochastic Tournament）：每次按輪盤賭選擇一對(duì)個(gè)體，然后讓這兩個(gè)個(gè)體進(jìn)行競(jìng)爭(zhēng)，適應(yīng)度高的被選中，如此反復(fù)，直到選滿為止。
最佳保留選擇：首先按輪盤賭選擇方法執(zhí)行遺傳算法的選擇操作，然后將當(dāng)前群體中適應(yīng)度最高的個(gè)體結(jié)構(gòu)完整地復(fù)制到下一代群體中。
無(wú)回放隨機(jī)選擇（也叫期望值選擇Excepted Value Selection）：根據(jù)每個(gè)個(gè)體在下一代群體中的生存期望來(lái)進(jìn)行隨機(jī)選擇運(yùn)算。方法如下:
（1） 計(jì)算群體中每個(gè)個(gè)體在下一代群體中的生存期望數(shù)目N。
（2） 若某一個(gè)體被選中參與交叉運(yùn)算，則它在下一代中的生存期望數(shù)目減去0.5，若某一個(gè)體未 被選中參與交叉運(yùn)算，則它在下一代中的生存期望數(shù)目減去1.0。
（3） 隨著選擇過(guò)程的進(jìn)行，若某一個(gè)體的生存期望數(shù)目小于0時(shí)，則該個(gè)體就不再有機(jī)會(huì)被選中。
確定式選擇：按照一種確定的方式來(lái)進(jìn)行選擇操作。具體操作過(guò)程如下：
（1） 計(jì)算群體中各個(gè)個(gè)體在下一代群體中的期望生存數(shù)目N。
（2） 用N的整數(shù)部分確定各個(gè)對(duì)應(yīng)個(gè)體在下一代群體中的生存數(shù)目。
（3） 用N的小數(shù)部分對(duì)個(gè)體進(jìn)行降序排列，順序取前M個(gè)個(gè)體加入到下一代群體中。至此可完全確定出下一代群體中Ｍ個(gè)個(gè)體。
無(wú)回放余數(shù)隨機(jī)選擇：可確保適應(yīng)度比平均適應(yīng)度大的一些個(gè)體能夠被遺傳到下一代群體中，因而選擇誤差比較小。
均勻排序：對(duì)群體中的所有個(gè)體按期適應(yīng)度大小進(jìn)行排序，基于這個(gè)排序來(lái)分配各個(gè)個(gè)體被選中的概率。
最佳保存策略：當(dāng)前群體中適應(yīng)度最高的個(gè)體不參與交叉運(yùn)算和變異運(yùn)算，而是用它來(lái)代替掉本代群體中經(jīng)過(guò)交叉、變異等操作后所產(chǎn)生的適應(yīng)度最低的個(gè)體。
隨機(jī)聯(lián)賽選擇：每次選取幾個(gè)個(gè)體中適應(yīng)度最高的一個(gè)個(gè)體遺傳到下一代群體中。
排擠選擇：新生成的子代將代替或排擠相似的舊父代個(gè)體，提高群體的多樣性。
以輪盤賭選擇為例：
假如有５條染色體，他們的適應(yīng)度分別為５、８、３、７、２。
那么總的適應(yīng)度為：F = 5 + 8 + 3 + 7 + 2 = 25。
那么各個(gè)個(gè)體的被選中的概率為：
α1 = ( 5 / 25 ) * 100% = 20%
α2 = ( 8 / 25 ) * 100% = 32%
α3 = ( 3 / 25 ) * 100% = 12%
α4 = ( 7 / 25 ) * 100% = 28%
α5 = ( 2 / 25 ) * 100% = 8%
當(dāng)指針在這個(gè)轉(zhuǎn)盤上轉(zhuǎn)動(dòng)，停止下來(lái)時(shí)指向的個(gè)體就是天選之人啦?？梢钥闯?，適應(yīng)性越高的個(gè)體被選中的概率就越大。
遺傳–染色體交叉(crossover)
遺傳算法的交叉操作，是指對(duì)兩個(gè)相互配對(duì)的染色體按某種方式相互交換其部分基因，從而形成兩個(gè)新的個(gè)體。
適用于二進(jìn)制編碼個(gè)體或浮點(diǎn)數(shù)編碼個(gè)體的交叉算子：
1.單點(diǎn)交叉（One-point Crossover）：指在個(gè)體編碼串中只隨機(jī)設(shè)置一個(gè)交叉點(diǎn)，然后再該點(diǎn)相互交換兩個(gè)配對(duì)個(gè)體的部分染色體。
2.兩點(diǎn)交叉與多點(diǎn)交叉：
(1) 兩點(diǎn)交叉（Two-point Crossover）：在個(gè)體編碼串中隨機(jī)設(shè)置了兩個(gè)交叉點(diǎn)，然后再進(jìn)行部分基因交換。
(2) 多點(diǎn)交叉（Multi-point Crossover）
3.均勻交叉（也稱一致交叉，Uniform Crossover）：兩個(gè)配對(duì)個(gè)體的每個(gè)基因座上的基因都以相同的交叉概率進(jìn)行交換，從而形成兩個(gè)新個(gè)體。
4.算術(shù)交叉（Arithmetic Crossover）：由兩個(gè)個(gè)體的線性組合而產(chǎn)生出兩個(gè)新的個(gè)體。該操作對(duì)象一般是由浮點(diǎn)數(shù)編碼表示的個(gè)體。
變異–基因突變(Mutation)
遺傳算法中的變異運(yùn)算，是指將個(gè)體染色體編碼串中的某些基因座上的基因值用該基因座上的其它等位基因來(lái)替換，從而形成新的個(gè)體。
例如下面這串二進(jìn)制編碼：
101101001011001
經(jīng)過(guò)基因突變后，可能變成以下這串新的編碼：
001101011011001
以下變異算子適用于二進(jìn)制編碼和浮點(diǎn)數(shù)編碼的個(gè)體：
基本位變異（Simple Mutation）：對(duì)個(gè)體編碼串中以變異概率、隨機(jī)指定的某一位或某幾位僅因座上的值做變異運(yùn)算。
均勻變異（Uniform Mutation）：分別用符合某一范圍內(nèi)均勻分布的隨機(jī)數(shù)，以某一較小的概率來(lái)替換個(gè)體編碼串中各個(gè)基因座上的原有基因值。（特別適用于在算法的初級(jí)運(yùn)行階段）
邊界變異（Boundary Mutation）：隨機(jī)的取基因座上的兩個(gè)對(duì)應(yīng)邊界基因值之一去替代原有基因值。特別適用于最優(yōu)點(diǎn)位于或接近于可行解的邊界時(shí)的一類問(wèn)題。
非均勻變異：對(duì)原有的基因值做一隨機(jī)擾動(dòng)，以擾動(dòng)后的結(jié)果作為變異后的新基因值。對(duì)每個(gè)基因座都以相同的概率進(jìn)行變異運(yùn)算之后，相當(dāng)于整個(gè)解向量在解空間中作了一次輕微的變動(dòng)。
高斯近似變異：進(jìn)行變異操作時(shí)用符號(hào)均值為Ｐ的平均值，方差為P**2的正態(tài)分布的一個(gè)隨機(jī)數(shù)來(lái)替換原有的基因值
?
