文章目錄

• 前言
• • 編碼
  • 解碼
  • 補充

前言

遺傳算法的編碼方法各種各樣，但二進制串編碼方式是最經(jīng)典的一種，那么它的編碼和解碼該如何進行呢？或許本博客能給你一個具有參考價值的答案。

---

編碼

經(jīng)典遺傳算法中使用“染色體”來代指個體，它由二進制串組成，如下圖所示：

它的每一維稱為一個基因，取值為0或1。



下面用一個具體的優(yōu)化問題來解釋個體（染色體）的編碼和解碼:

$$maxmizef(x)=?x^2+10\cos (2\pi x)+30,?5\le x\le 5$$

對于上述待優(yōu)化函數(shù)，我們的編碼應(yīng)該設(shè)置多長的二進制串呢？

我們首先明確，編碼長度取決于自變量的范圍（更準確點應(yīng)該是決策變量的范圍）和搜索精度，所以圍繞它們來考慮如何編碼。

在本例，我們假設(shè)精度是0.01，記清楚了，是 0.01。

首先，我們可以確定自變量的范圍（更準確點應(yīng)該是決策變量的范圍）是5-（-5）= 10.

另外，我們需要的精度是0.01，也就是說我們要能用我們的編碼把自變量范圍10以10.00表示，但二進制串只能表示整數(shù)沒法表示小數(shù)（其實可以表示小數(shù)的，但我們不討論這種情況），所以我們換個思路，我們用1000來表示10.00，但請注意，二進制串轉(zhuǎn)化為十進制時不能剛好得到1000，而是得到 $2^n$，所以我們得找到一個最大值大于1000的二進制串。

根據(jù)上圖，我們發(fā)現(xiàn)可以用長度為10的二進制串來“容納”上述的1000,為什么我用“容納”來表述呢？因為長度為10的二進制串可以表示 $0～(2^{10}?1)$，也就是 $0～1023$，有 $1023>1000$；而 $0～(2^9?1)$是 $0～511$， 有 $511<1000$ ，所以用1023來表示10.00，編碼時二進制串長度為10，而不是9。

由上圖公式，我們把初始群體的每個個體用一個長度為10的二進制串來表示，記為：
$$A_{10}{A}_9{A}_8...A_3{A}_2{A}_1$$

解碼

在上一小節(jié)我們用1023來表示10.00，那解碼的時候表示1023的二進制串如何表示回10.00呢？

想想，我們編碼時把10.00放大成1023，那么解碼時縮小1023倍就行了！

這樣，我們解碼的時候做如下處理：

10.00 /1023 ≈ 0.009775，我們把解碼出來的十進制數(shù)都乘以0.009775，就得到了最終結(jié)果。

于是有：

其中 $L_x=?5$。

$x$ 就是解碼所得十進制數(shù)。

補充

這里要稍微注意下，實際搜索精度與期望搜索精度之間是存在誤差的：

我們本想用1000來表示10.00的，但由于二進制串只能表示 $2^n$，所以只好用1023來表示10.00，之后在

這里沒法除盡產(chǎn)生了誤差。

參考資料：
《人工智能及其應(yīng)用第五版》- 蔡自興

總結(jié)

以上是生活随笔為你收集整理的如何理解遗传算法中的编码与解码？以二进制编码为例的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。