格雷碼演算法

Ⅰ 遺傳演算法的基本原理

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

一、編碼

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

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

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

Ⅱ 遺傳演算法的編碼方法有幾種

常用的編碼介紹
1、二進制編碼：
（1）定義：二進制編碼方法是使用二值符號集{0,1}，它所構成的個體基因型是一個二進制編碼符號串。二進制編碼符號串的長度與問題所要求的求解精度有關。
（2）舉例：0≤x≤1023,精度為1,m表示二進制編碼的長度。則有建議性說法：使
2m-1≤1000（跟精度有關）≤2m-1。取m=10
則X:0010101111就可以表示一個個體，它所對應的問題空間的值是x=175。
（3）優缺點
優點：符合最小字元集原則，便於用模式定理分析；
缺點：連續函數離散化時的映射誤差。
2、格雷碼編碼
（1）定義：格雷碼編碼是其連續的兩個整數所對應的編碼之間只有一個碼位是不同的，其餘碼位完全相同。它是二進制編碼方法的一種變形。
十進制數0—15之間的二進制碼和相應的格雷碼分別編碼如下。
二進制編碼為：0000，0001，0010，001
1，0100。0101，0110，0111，
1000，1001，1010，1011，1100，1101，1110，1111；
格雷碼編碼為：0000，0001，0011，0010，0110，0111，0101，0100，
1100，1101，1111，1110，1010，1011，1001，1000。
（2）舉例：對於區間[0。1023]中兩個鄰近的整數X1=175和X2=176，若用長度為10位的二進制編碼，可表示為X11：0010101111和X12
0010110000，而使用同樣長度的格雷碼，它們可分別表示為X21：0010101111和X22：0010101000。
（3）優點：增強了遺傳演算法的局部搜索能力，便於連續函數的局部控制項搜索。
3、浮點數(實數)編碼
（1）定義：浮點數編碼是指個體的每個基因值用某一范圍內的一個浮點數來表示，而個體的編碼長度等於其決策變數的個數。因為這種編碼方法使用的決策變數的真實值，也稱之為真值編碼方法。
（2）舉例：
（3）優點：實數編碼是遺傳演算法中在解決連續參數優化問題時普遍使用的一種編碼方式，具有較高的精度，在表示連續漸變問題方面具有優勢。
4、排列編碼
排列編碼也叫序列編碼，是針對一些特殊問題的特定編碼方式。排序編碼使問題簡潔，易於理解。該編碼方式將有限集合內的元素進行排列。若集合內包含m個元素，則存在m!種排列方法，當m不大時，m!也不會太大，窮舉法就可以解決問題。當m比較大時，m!就會變得非常大，窮舉法失效，遺傳演算法在解決這類問題上具有優勢。如解決TSP問題時，用排列編碼自然、合理。
5、其它編碼方式
多參數級聯編碼等

Ⅲ c語言實現格雷碼轉換為二進制

把十進制小數乘以2，取其積的整數部分作對應二進制小數的最高位系數k -1 再取積的純小數部分乘以2，新得積的整數部分又作下一位的系數k -2 ，再取其積的純小數部分繼續乘2，…，直到乘積小數部分為0時停止，這時乘積的整數部分是二進制數最低位系數，每次乘積得到的整數序列就是所求的二進制小數。這種方法每次乘以基數取其整數作系數。所以叫乘基取整法。需要指出的是並不是所有十進制小數都能轉換成有限位的二進制小數並出現乘積的小數部分0的情況，有時整個換算過程無限進行下去。此時可以根據要求並考慮計算機字長，取定長度的位數後四捨五入這時得到的二進制數是原十進制數的近似值。

Ⅳ 急求FIFO資料 越基礎越好

剛好也是做FIFO的新手，前段時間從網上找的

FIFO
一、先入先出隊列(First Input First Output，FIFO)這是一種傳統的按序執行方法，先進入的指令先完成並引退，跟著才執行第二條指令。
1．什麼是FIFO？
FIFO是英文First In First Out 的縮寫，是一種先進先出的數據緩存器，他與普通存儲器的區別是沒有外部讀寫地址線，這樣使用起來非常簡單，但缺點就是只能順序寫入數據，順序的讀出數據，其數據地址由內部讀寫指針自動加1完成，不能像普通存儲器那樣可以由地址線決定讀取或寫入某個指定的地址。
2．什麼情況下用FIFO？
FIFO一般用於不同時鍾域之間的數據傳輸，比如FIFO的一端時AD數據採集，另一端時計算機的PCI匯流排，假設其AD採集的速率為16位 100K SPS，那麼每秒的數據量為100K×16bit=1.6Mbps,而PCI匯流排的速度為33MHz，匯流排寬度32bit,其最大傳輸速率為1056Mbps,在兩個不同的時鍾域間就可以採用FIFO來作為數據緩沖。另外對於不同寬度的數據介面也可以用FIFO，例如單片機位8位數據輸出，而DSP可能是16位數據輸入，在單片機與DSP連接時就可以使用FIFO來達到數據匹配的目的。
3．FIFO的一些重要參數
FIFO的寬度：也就是英文資料里常看到的THE WIDTH，它只的是FIFO一次讀寫操作的數據位，就像MCU有8位和16位，ARM 32位等等，FIFO的寬度在單片成品IC中是固定的，也有可選擇的，如果用FPGA自己實現一個FIFO，其數據位，也就是寬度是可以自己定義的。
FIFO的深度：THE DEEPTH，它指的是FIFO可以存儲多少個N位的數據（如果寬度為N）。如一個8位的FIFO，若深度為8，它可以存儲8個8位的數據，深度為12 ，就可以存儲12個8位的數據，FIFO的深度可大可小，個人認為FIFO深度的計算並無一個固定的公式。在FIFO實際工作中，其數據的滿/空標志可以控制數據的繼續寫入或讀出。在一個具體的應用中也不可能由一些參數算數精確的所需FIFO深度為多少，這在寫速度大於讀速度的理想狀態下是可行的，但在實際中用到的FIFO深度往往要大於計算值。一般來說根據電路的具體情況，在兼顧系統性能和FIFO成本的情況下估算一個大概的寬度和深度就可以了。而對於寫速度慢於讀速度的應用，FIFO的深度要根據讀出的數據結構和讀出數據的由那些具體的要求來確定。
滿標志：FIFO已滿或將要滿時由FIFO的狀態電路送出的一個信號，以阻止FIFO的寫操作繼續向FIFO中寫數據而造成溢出（overflow）。
空標志：FIFO已空或將要空時由FIFO的狀態電路送出的一個信號，以阻止FIFO的讀操作繼續從FIFO中讀出數據而造成無效數據的讀出（underflow）。
讀時鍾：讀操作所遵循的時鍾，在每個時鍾沿來臨時讀數據。
寫時鍾：寫操作所遵循的時鍾，在每個時鍾沿來臨時寫數據。
讀指針：指向下一個讀出地址。讀完後自動加1。
寫指針：指向下一個要寫入的地址的，寫完自動加1。
讀寫指針其實就是讀寫的地址，只不過這個地址不能任意選擇，而是連續的。
4．FIFO的分類
根均FIFO工作的時鍾域，可以將FIFO分為同步FIFO和非同步FIFO。同步FIFO是指讀時鍾和寫時鍾為同一個時鍾。在時鍾沿來臨時同時發生讀寫操作。非同步FIFO是指讀寫時鍾不一致，讀寫時鍾是互相獨立的。
5．FIFO設計的難點
FIFO設計的難點在於怎樣判斷FIFO的空/滿狀態。為了保證數據正確的寫入或讀出，而不發生益處或讀空的狀態出現，必須保證FIFO在滿的情況下，不能進行寫操作。在空的狀態下不能進行讀操作。怎樣判斷FIFO的滿/空就成了FIFO設計的核心問題。由於同步FIFO幾乎很少用到，這里只描述非同步FIFO的空/滿標志產生問題。
在用到觸發器的設計中，不可避免的會遇到亞穩態的問題（關於亞穩態這里不作介紹，可查看相關資料）。在涉及到觸發器的電路中，亞穩態無法徹底消除，只能想辦法將其發生的概率將到最低。其中的一個方法就是使用格雷碼。格雷碼在相鄰的兩個碼元之間只由一位變換(二進制碼在很多情況下是很多碼元在同時變化)。這就會避免計數器與時鍾同步的時候發生亞穩態現象。但是格雷碼有個缺點就是只能定義2^n的深度，而不能像二進制碼那樣隨意的定義FIFO的深度，因為格雷碼必須循環一個2^n，否則就不能保證兩個相鄰碼元之間相差一位的條件，因此也就不是真正的各雷碼了。第二就是使用冗餘的觸發器，假設一個觸發器發生亞穩態的概率為P，那麼兩個及聯的觸發器發生亞穩態的概率就為P的平方。但這回導致延時的增加。亞穩態的發生會使得FIFO出現錯誤，讀/寫時鍾采樣的地址指針會與真實的值之間不同，這就導致寫入或讀出的地址錯誤。由於考慮延時的作用，空/滿標志的產生並不一定出現在FIFO真的空/滿時才出現。可能FIFO還未空/滿時就出現了空/滿標志。這並沒有什麼不好，只要保證FIFO不出現overflow or underflow 就OK了。
很多關於FIFO的文章其實討論的都是空/滿標志的不同演算法問題。
在Vijay A. Nebhrajani的《非同步FIFO結構》一文中，作者提出了兩個關於FIFO空/滿標志的演算法。
第一個演算法：構造一個指針寬度為N+1，深度為2^N位元組的FIFO（為便方比較將格雷碼指針轉換為二進制指針）。當指針的二進制碼中最高位不一致而其它N位都相等時，FIFO為滿（在Clifford E. Cummings的文章中以格雷碼表示是前兩位均不相同，而後兩位LSB相同為滿，這與換成二進製表示的MSB不同其他相同為滿是一樣的）。當指針完全相等時，FIFO為空。這也許不容易看出，舉個例子說明一下：一個深度為8位元組的FIFO怎樣工作（使用已轉換為二進制的指針）。FIFO_WIDTH=8，FIFO_DEPTH= 2^N = 8，N = 3，指針寬度為N+1=4。起初rd_ptr_bin和wr_ptr_bin均為「0000」。此時FIFO中寫入8個位元組的數據。wr_ptr_bin =「1000」，rd_ptr_bin=「0000」。當然，這就是滿條件。現在，假設執行了8次的讀操作，使得rd_ptr_bin =「1000」，這就是空條件。另外的8次寫操作將使wr_ptr_bin 等於「0000」，但rd_ptr_bin 仍然等於「1000」，因此FIFO為滿條件。
顯然起始指針無需為「0000」。假設它為「0100」，並且FIFO為空，那麼8個位元組會使wr_ptr_bin =「1100」，, rd_ptr_bin 仍然為「0100」。這又說明FIFO為滿。
在Vijay A. Nebhrajani的這篇《非同步FIFO結構》文章中說明了怎樣運用格雷碼來設置空滿的條件，但沒有說清為什麼深度為8的FIFO其讀寫指針要用3+1位的格雷碼來實現，而3+1位的格雷碼可以表示16位的深度，而真實的FIFO只有8位，這是怎麼回事？而這個問題在Clifford E. Cummings的文章中得以解釋。三位格雷碼可表示8位的深度，若在加一位最為MSB，則這一位加其他三位組成的格雷碼並不代表新的地址，也就是說格雷碼的0100表示表示7，而1100仍然表示7，只不過格雷碼在經過一個以0位MSB的循環後進入一個以1為MSB的循環，然後又進入一個以0位MSB的循環，其他的三位碼仍然是格雷碼，但這就帶來一個問題，在0100的循環完成後，進入1000，他們之間有兩位發生了變換，而不是1位，所以增加一位MSB的做法使得該碼在兩處：0100~1000，1100~0000有兩位碼元發生變化，故該碼以不是真正的格雷碼。增加的MSB是為了實現空滿標志的計算。Vijay A. Nebhrajani的文章用格雷碼轉二進制，再轉格雷碼的情況下提出空滿條件，僅過兩次轉換，而Clifford E. Cummings的文章中直接在格雷碼條件下得出空滿條件。其實二者是一樣的，只是實現方式不同罷了。
第二種演算法：Clifford E. Cummings的文章中提到的STYLE #2。它將FIFO地址分成了4部分，每部分分別用高兩位的MSB 00 、01、 11、 10決定FIFO是否為going full 或going empty (即將滿或空)。如果寫指針的高兩位MSB小於讀指針的高兩位MSB則FIFO為「幾乎滿」，
若寫指針的高兩位MSB大於讀指針的高兩位MSB則FIFO為「幾乎空」。
在Vijay A. Nebhrajani的《非同步FIFO結構》第三部分的文章中也提到了一種方法，那就是方向標志與門限。設定了FIFO容量的75%作為上限，設定FIFO容量的25%為下限。當方向標志超過門限便輸出滿/空標志，這與Clifford E. Cummings的文章中提到的STYLE #2可謂是異曲同工。他們都屬於保守的空滿判斷。其實這時輸出空滿標志FIFO並不一定真的空/滿。
說到此，我們已經清楚地看到，FIFO設計最關鍵的就是產生空/滿標志的演算法的不同產生了不同的FIFO。但無論是精確的空滿還是保守的空滿都是為了保證FIFO工作的可靠。

另外，我空間有另一篇
http://hi..com/bbgzy168/blog/item/f11ee0164ccd744221a4e9b9.html

樓主要是還有什麼好的也發給我吧，發到我空間或者郵箱[email protected]，共同學習啊

Ⅳ 九連環全套解法圖解

沒有圖
九連環是中國民間玩具。規定環在桿上用1表示，環在下面用0表示。規定最左邊的環是可以任意上下的那一環，輸出數據中最右邊必須是1，也就是說，010100要寫成0101。
現在是X連環，由於「輸出數據中最右邊必須是1」，所以X可以理解為無限大，右邊多餘的0在輸出時都省略。初始化各環都是0，以下是前9步的情況：
1．1
2．11
3．01
4．011
5．111
6．101
7．001
8．0011
9．1011
問在X連環裝上過程中，第n步完成後，具體情況是怎麼樣的。
答案：將n轉化為二進制，求其格雷碼。將二進制的格雷碼逆序輸出，即得具體情況。
注意：這個演算法揭示了傳統的九連環與現代的格雷碼的重要關系！

Ⅵ 請教：關於用格雷碼定位的問題

根據公式,自己寫一個
格雷碼
轉換二進制
的FC塊就行了.格雷碼的最高位賦值給二進制的最高位,然後格格雷碼的第x位與x-1位
異或
,賦值給二進制的第x-1位,依次類推.......給你貼一段在網上找的:(遇到這種問題先google或者,可能會有很大收獲啊,呵呵)

Ⅶ C語言 遞歸 輸出格雷碼（Gray碼）

你查網路：
一般的,普通二進制碼與格雷碼可以按以下方法互相轉換:
二進制碼->格雷碼（編碼）：從最右邊一位起，依次將每一位與左邊一位異或(XOR)，作為對應格雷碼該位的值，最左邊一位不變(相當於左邊是0)；
格雷碼-〉二進制碼（解碼）：從左邊第二位起，將每位與左邊一位解碼後的值異或，作為該位解碼後的值（最左邊一位依然不變）

如果非要按遞歸來做，可以這樣，如果要輸出n位格雷碼，那麼遞歸層為N：0層負責第0位，1層負責第1位，2層負責第2位。。。。第n-1層負責第n-1位（也就是gray的最高位）這樣就可以寫出遞歸函數的輪廓了。
void gray(int n)
{
if(0==n)
{……;return;}
……
gray(n-1);//把處理第n-1位的任務交下一層處理

}
對於第0位來說，每4位為一個循環周期——01 10.
對於第1位來說，每8位為一個循環周期——0011 1100.
對於第2位來說，每16位為一個循環周期——00001111 11110000.
……
對於第N位來說，每2^(N+2)為一個循環周期。
看到這里你有什麼啟發？
所以我想你應該設置一個全局變數:int flag=1.
對於gray(i)函數來說，可以通過set=flag%(2^(i+2))來設置該第位（當2^i<set&&set<=3*2^i,就設第i位為1）

Ⅷ 格雷碼編碼4位的怎麼編啊

自然二進制數轉換到格雷碼
－－－－－－－－－－－－
設有 N 位二進制數 B(i)，其中 0 <= i <= N - 1；它可以變換成為同樣位數的格雷碼 G(i)。
二進制數與格雷碼的轉換公式如下：

G(i) = B(i+1) XOR B(i) ; 0 <= i < N - 1
G(i) = B(i) ; i = N - 1

如果是通過編程計算進行變換，就需要使用這個公式逐位的計算；
如果是使用硬體電路進行變換，就可以使用做而論道前面在回答問題時給出的電路。

格雷碼轉換到自然二進制數
－－－－－－－－－－－－
設有 N 位格雷碼 G(i)，把它轉換成自然二進制數的演算法如下。

自然二進制碼的最高位等於雷碼的最高位；
自然二進制碼的次高位為最高位自然二進制碼與次高位格雷碼相異或；
自然二進制碼的其餘各位與次高位自然二進制碼的求法相類似。
轉換公式如下：

B(i) = G(i) ; i = N - 1
B(i) = B(i+1) XOR G(i) ; 0 <= i < N - 1

轉換電路可以參考做而論道以前寫的博文：
http://hi..com/%D7%F6%B6%F8%C2%DB%B5%C0/blog/item/14e95cc24ec8fc58b219a88d.html