浮點數編碼遺傳演算法

Ⅰ 浮點數編碼介紹

（1）浮點數：
小數點位置可移動的數據稱為浮點數，可用下式表示：N=M*RE
其中，M—尾數，
R—階的基數（也就是指數部分的底）。R 一般取2、8或16，為約定的常數，大多數機器 R 取定為2。
E—階的階碼。

當基數約定後，對浮點數的編碼就只需對尾數和階碼部分進行編碼。浮點數在機器中的形式如下：

尾數M用定點小數表示，階碼E是整數。 M乘以RE後小數點的位置改變，改變指數部分RE的值，小數點的位置隨之變動，故稱上述表示法表示的數據為浮點數。

（2）浮點數的編碼
階碼E一般用移碼或補碼表示，尾數用原碼或補碼表示。
機器零當浮點數的尾數部分M=0時，不論階碼為何值，都看作是零值，稱為機器零。
上溢浮點數的絕對值太大而機器不能表示的情況，此時浮點數的階碼大於機器所能表示的最大階碼。
下溢浮點數的絕對值太小（階碼小於機器所能表示的最小階碼）的情況稱為下溢。當浮點數下溢時，通常將尾數各位強置為零 ，按機器零處理。


（3）規格化浮點數
為了便於浮點數之間的運算與比較，也為了提高浮點數的精度，規定計算機中的浮點數尾數部分必須滿足1/R≤|M|<1，也即，小數點後的第一位必須是有效數字。當尾數用補碼表示，且R=2時，其規格化形式一般為：

上式表明，當尾數的最高數值位與符號位相反時，即為規格化形式。但對於M<0 有兩種特殊情況需考慮。
＊M=-1/2，按規定是規格化數，但[-0.5]補=1.10…0，與一般情況相悖，為便於硬體判斷，特規定-0.5不是規格化的數（對補碼而言）。
＊M=-1，因小數補碼允許表示-1，且［-1]補=1.00…0.故將-1作為規格化數（對補碼而言 ）

（4）IEE754標准
現代計算機中，浮點數一般採用IEEE制定的國際標准，形式如下；
符號位s 階碼e 尾數 總位數
短實數（單精度數） 1 8 23 32
長實數（雙精度數） 1 11 52 64
臨時實數 1 15 64 80

在IEEE754浮點數標准中，符號位也是「0」表示正數，「1」表示負數。階碼也用移碼表示，尾數也是規格化表示，但為如下形式：1.ff---f.在實際表示中，整數位的1省略，稱隱藏位 （臨時實數不採用隱藏位方案）。由於尾數形式的變化，階碼部分也與一般移碼不同，對短實數而言，[X]移=27+x-1=127+x,也就是說此種移碼比一般移碼的值小1，如.[810]移為13310 而不是13410。所以，短實數.長實數和臨時實數的階碼偏移量分別為7FH、3FFH和3FFFH。單精度數所表示的數值為：（-1）5 1.ff---f*2e-127。
注意：浮點數的編碼有多種方法，在實際應用時，首先一定要明確是哪種編碼方法，分清各種編碼方法的不同之處，這樣才能不出差錯。

4.文字的編碼
(1) 西文字元的編碼目前常用的編碼系統是ASCII碼（American Standard Code for Information Interchange）。
ASCII碼特點：
＊每個字元用7位二進制代碼表示。在計算機中每個符號實際用8位表示，最高位置「0」或作為奇偶校驗位。
＊共有128個符號。其中95個可印刷字元（包括空格），其餘為控制字元。
＊字元0——9的高3位編碼為011，低4位為0000——1001（正好為二進制形式的0—9），滿足正常的排序關系，且大、小寫英文一位字母編碼的對應關系簡單，大寫字母的高2位編碼10，低5位為00001-11010（為二進制形式的1—26），小寫字母高2位為11，低5位也為0000—11010。
（2）中文編碼
漢字編碼分輸入碼、機內碼和字形碼等三大類。
漢字輸入碼 主要有數字編碼、拼音編碼和字形編碼等。這幾種編碼方式都是利用相應的編碼規則，用字母數字串代
替漢字，從西文標准鍵盤上輸入漢字。
漢字機內碼用於漢字信息存儲、交換、檢索等的機內代碼，一般用兩個或三個位元組表示一個漢字。為了區別於ASCII
碼，漢字機內代碼中位元組的最高位均為「1」。
漢字字形碼根據漢字字形信息進行編碼，存儲在字形庫中，用於漢字的輸出，常用點陣表示漢字字形。
（3）十進制數的編碼
＊字元串形式一個位元組存放一個十進制的數位或符號，用連續的多個位元組表示一個完整的十進制數據。
十進制數據的機內表示常用ASCII碼。有前分隔字元串和串兩種方式。
＃前分隔字元串 符號位在數字位之前單獨佔用一個位元組。字元「+」（2B）16表示正號，「-」（2D）16表 示負號。
＃後嵌入字元串 將符號位嵌入最低一位數字里。規則：將「-」號變成（40）16與最低位數相加。「+」號省略。
上述兩種表示方法主要用於非數值計算的應用領域，算術運算不方便。
＊壓縮十進制數串形式一個位元組存放兩個十進制數位，用連續的多個位元組表示一個完整的十進制數據。比前一種形式節省存儲空間並且便於數據處理，應用廣泛。
在壓縮十進制數串形式中，可以用ASCII碼的低4位或BCD碼表示十進制數。符號位也用4位二進制代碼表示，並放在最低數位之後（C）16=(1100)2代表正號，（D）16=(1101)2表示負號。
用十進制數串表示十進制數據的特點是位長可變，但需給出首地址和串長。

Ⅱ 遺傳演算法的基本框架

遺傳演算法不能直接處理問題空間的參數，必須把它們轉換成遺傳空間的由基因按一定結構組成的染色體或個體。這一轉換操作就叫做編碼，也可以稱作(問題的)表示(representation)。
評估編碼策略常採用以下3個規范:
a)完備性(completeness):問題空間中的所有點(候選解)都能作為GA空間中的點(染色體)表現。
b)健全性(soundness): GA空間中的染色體能對應所有問題空間中的候選解。
c)非冗餘性(nonrendancy):染色體和候選解一一對應。
目前的幾種常用的編碼技術有二進制編碼，浮點數編碼，字元編碼，變成編碼等。
而二進制編碼是目前遺傳演算法中最常用的編碼方法。即是由二進制字元集{0,1}產生通常的0,1字元串來表示問題空間的候選解。它具有以下特點：
a)簡單易行
b)符合最小字元集編碼原則
c)便於用模式定理進行分析，因為模式定理就是以基礎的。 進化論中的適應度，是表示某一個體對環境的適應能力，也表示該個體繁殖後代的能力。遺傳演算法的適應度函數也叫評價函數，是用來判斷群體中的個體的優劣程度的指標，它是根據所求問題的目標函數來進行評估的。
遺傳演算法在搜索進化過程中一般不需要其他外部信息，僅用評估函數來評估個體或解的優劣，並作為以後遺傳操作的依據。由於遺傳演算法中，適應度函數要比較排序並在此基礎上計算選擇概率，所以適應度函數的值要取正值。由此可見，在不少場合，將目標函數映射成求最大值形式且函數值非負的適應度函數是必要的。
適應度函數的設計主要滿足以下條件：
a）單值、連續、非負、最大化
b) 合理、一致性
c）計算量小
d）通用性強。
在具體應用中，適應度函數的設計要結合求解問題本身的要求而定。適應度函數設計直接影響到遺傳演算法的性能。 遺傳演算法中初始群體中的個體是隨機產生的。一般來講，初始群體的設定可採取如下的策略:
a)根據問題固有知識，設法把握最優解所佔空間在整個問題空間中的分布范圍，然後，在此分布范圍內設定初始群體。
b)先隨機生成一定數目的個體，然後從中挑出最好的個體加到初始群體中。這種過程不斷迭代，直到初始群體中個體數達到了預先確定的規模。

Ⅲ 遺傳演算法

優化的演算法有很多種，從最基本的梯度下降法到現在的一些啟發式演算法，如遺傳演算法(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、所求問題最優值小於給定的閾值.

Ⅳ 你好，請問matlab中使用遺傳演算法編程，變數既有0-1整數，又有0~1之間的實數，該怎麼編碼處理啊謝謝

可以用二進制編碼，對於0-1整數，顯然可以解決；對於0~1之間的實數，可以用解碼的方式，將其映射到0~1范圍內。比如：二進制01101轉換成十進制是15，那麼你可以將其乘以0.01，變為0.15。其他類似。