目標規劃——遺傳演算法

突變頻率怎麼計算

1.

遺傳演算法簡介

遺傳演算法是用於解決最最佳化問題的一種搜尋演算法，演算法的整體思路是建立在達爾文生物進化論“優勝劣汰”規律的基礎上。它將生物學中的基因編碼、染色體交叉、基因變異以及自然選擇等概念引入最最佳化問題的求解過程中，透過不斷的“種群進化”，最終得到問題的最優解。

2.

遺傳演算法實現步驟

在講下面幾個基於生物學提出的概念之前，首先我們需要理解為什麼需要在最最佳化問題的求解中引入生物學中的各種概念。

假設我們需要求一個函式的最大值，但這個函式異常複雜以至於無法套用一般化的公式，那麼就會想到：如果可以將所有可能的解代入方程，那麼函式最大值所對應的那個解就是問題的最優解。但是，對於較複雜的函式來說，其可能的解的個數的數量級是我們所無法想象的。因此，我們只好退而求其次，只代入部分解並在其中找到最優解。那麼這樣做的核心就在於

如何設定演算法確定部分解並去逼近函式的最優解或者較好的區域性最優解

。

遺傳演算法就是為了解決上述問題而誕生的。假設函式值所對應的所有解是一個容量超級大的種群，而種群中的個體就是一個個解，接下去遺傳演算法的工作就是讓這個種群中的部分個體去不斷繁衍，在繁衍的過程中一方面會發生染色體交叉而產生新的個體。另一方面，基因變異也會有機率會發生併產生新的個體。接下去，只需要透過自然選擇的方式，淘汰質量差的個體，保留質量好的個體，並且讓這個繁衍的過程持續下去，那麼最後就有可能進化出最優或者較優的個體。這麼看來原來最最佳化問題居然和遺傳變異是相通的，而且大自然早已掌握了這樣的機制，這著實令人興奮。為了將這種機制引入最最佳化問題並利用計算機求解，我們需要將上述提到的生物學概念轉化為計算機能夠理解的演算法機制。

下面介紹在計算機中這種遺傳變異的機制是如何實現的：

基因編碼與解碼：

在生物學中，交叉與變異能夠實現是得益於染色體上的基因，可以想象每個個體都是一串超級長的基因編碼，當兩個個體發生交叉時，兩條基因編碼就會發生交換，產生的新基因同時包含父親和母親的基因編碼。在交叉過程中或者完成後，某些基因點位又會因為各種因素髮生突變，由此產生新的基因編碼。當然，發生交叉和變異之後的個體並不一定優於原個體，但這給了進化（產生更加優秀的個體）發生的可能。

因此，為了在計算機裡實現交叉和變異，就需要對十進位制的解進行編碼。對於計算機來說其最底層的語言是由二進位制0、1構成的，而0、1就能夠被用來表示每個基因點位，大量的0、1就能夠表示一串基因編碼，因此我們可以用二進位制對十進位制數進行編碼，即將十進位制的數對映到二進位制上。但是我們並不關心如何將十進位制轉換為二進位制的數，因為計算機可以隨機生成大量的二進位制串，我們只需要將辦法將二進位制轉化為十進位制就可以了。

二進位制轉換為十進位制實現方式：

假設，我們需要將二進位制對映到以下範圍：

首先，將二進位制串展開並透過計算式轉化為［0，1］範圍內的數字：

將［0，1］範圍內的數字對映到我們所需要的區間內：

交叉與變異：

在能夠用二進位制串表示十進位制數的基礎上，我們需要將交叉與變異引入演算法中。假設我們已經獲得兩條二進位制串（基因編碼），一條作為父親，一條作為母親，那麼交叉指的就是用父方一半的二進位制編碼與母方一半的二進位制編碼組合成為一條新的二進位制串（即新的基因）。變異則指的是在交叉完成產生子代的過程中，二進位制串上某個數字發生了變異，由此產生新的二進位制串。當然，交叉與變異並不是必然發生的，其需要滿足一定的機率條件。一般來說，交叉發生的機率較大，變異發生的機率較小。交叉是為了讓演算法朝著收斂的方向發展，而變異則是為了讓演算法有機率跳出某種區域性最優解。

自然選擇：

在成功將基因編碼和解碼以及交叉與變異引入演算法後，我們已經實現了讓演算法自動產生部分解並最佳化的機制。接下去，我們需要解決如何在演算法中實現自然選擇並將優秀的個體保留下來進而進化出更優秀的個體。

首先我們需要確定個體是否優秀，考慮先將其二進位制串轉化為十進位制數並代入最初定義的目標函式中，將函式值定義為適應度。在這裡，假設我們要求的是最大值，則定義函式值越大，則其適應度越大。那是否在每一輪迭代過程中只需要按照適應度對個體進行排序並選出更加優秀的個體就可以了呢？事實上，自然選擇的過程中存在一個現象，並沒有說優秀的個體一定會被保留，而差勁的個體就一定被會被淘汰。自然選擇是一個機率事件，越適應環境則生存下去的機率越高，反之越低。為了遵循這樣的思想，我們可以根據之前定義的適應度的大小給定每個個體一定的生存機率，其適應度越高，則在篩選時被保留下來的機率也越高，反之越低。

那麼問題就來了，如何定義這種生存機率，一般來說，我們可以將

個體適應度與全部個體適應度之和的比率作為生存機率

。但我們在定義適應度時使用函式值進行定義的，但函式值是有可能為負的，但機率不能為負。因此，我們需要對

函式值進行正數化處理

，其處理方式如下：

定義適應度函式：

定義生存機率函式：

注：最後一項之所以加上0。0001是因為不能讓某個個體的生存機率變為0，這不符合自然選擇中包含的機率思想。

3.

遺傳算例

在這裡以一個比較簡單的函式為例，可以直接判斷出函式的最小值為0，最優解為（0，0）

若利用遺傳演算法進行求解，設定交叉機率為0。8，變異機率為0。005，種群內個體數為2000，十進位制數基因編碼長度為24，迭代次數為500次。

從遺傳演算法收斂的動態圖中可以發現，遺傳演算法現實生成了大量的解，並對這些解進行試錯，最終收斂到最大值，可以發現遺傳演算法的結果大致上與最優解無異，結果圖如下：

4.

遺傳演算法優缺點

優點：

1、 透過變異機制避免演算法陷入區域性最優，搜尋能力強

2、 引入自然選擇中的機率思想，個體的選擇具有隨機性

3、 可拓展性強，易於與其他演算法進行結合使用

缺點：

1、 遺傳演算法程式設計較為複雜，涉及到基因編碼與解碼

2、 演算法內包含的交叉率、變異率等引數的設定需要依靠經驗確定

3、 對於初始種群的優劣依賴性較強

下一節分享內容：Python和Matlab遺傳演算法實現展示

若對以上內容有疑問可關注微信公眾號“TES工作室”進行諮詢。

出品/TES工作室