遺傳算法二進制編碼負整數

-1

我想實現最大化n個整數變量x1..xn函數的遺傳算法，其中每個變量屬於範圍[-n，n]。我正在考慮使用二進制編碼來表示染色體，但我不確定如何編碼負整數。我已經搜索了相當長的一段時間，但我還沒有遇到二進制編碼的通用公式。對遺傳算法的範圍[-n，n]中的整數進行編碼的最常用方法是什麼？我希望交叉和變異的複雜度較低（條件檢查較少）。如果對於初始羣體，它會起作用，而不是生成-n和n之間的數字，我生成0到2n的數字並將它們編碼爲二進制，然後在解碼時每次（每隔一代）減去n？遺傳算法二進制編碼負整數

來源

2013-04-22 vjain27

不知道這會有所幫助，但你可以存儲編碼時真的很有幫助二進制補碼形式的數字 – jg943 2013-04-22 22:45:39

編碼[-n，n]和[0,2n]之間的區別是什麼？我想這不應該是...... – sashkello 2013-04-22 22:53:00

C會爲你做字節編碼，我期望。 – flup 2013-04-22 23:11:38

user1765444的回答很有意義......我剛剛讀了sashkello的建議（使用偏移二進制將消除與GA內簽名的int進行綁定）。做交叉和變異等等會很容易 - 使用shashkello's和user1765444的答案組合。問題是如果你的數據類型的寬度大於你的範圍，那麼交叉會產生無效的孩子。

假設一個int32具有您需要的寬度。然後int32數組[n]。你知道有32n位，所以你可以隨機取一個交叉點m，其中m> = 0和m爲32n。你知道位m在數組[m/n]中出現，位置m％n從msb開始（想象數組只是一個長二進制串）。

然後說你有2個父母int32 parent1 [n]和int32 parent2 [n]。像下面的僞代碼一樣？在這個交叉的字符串只是一個二進制字符串爲交叉（即符號位被視爲只是另一位）...

免責聲明：對不起，以下代碼是粗略的準備，未編譯，所以可能包含錯誤... 只是一個想法！

int child1[n]; 
uint32 m = rand_like_func(); // random cross over point, a bit position 
          // in the binary string of length n*32; 
uint32 arraySlotForCrossOvr = (uint32)(m/n); 
uint32 bitInSlotForCrossOvr = 31 - m % n; 
uint32 maskForCrossOvrP2 = (1 << bitInSlotForCrossOvr) - 1; 
uint32 maskForCrossOvrP1 = ~maskForCrossOvrP2; 

// crossover to create child 1 
memcpy(child1, parent1, arraySlotForCrossOvr); 
child1[arraySlotForCrossOvr] = 
    (int32)(((uint32)parent1[arraySlotForCrossOvr] & maskForCrossOverP1) | 
      ((uint32)parent2[arraySlotForCrossOvr] & maskForCrossOvrP2)) 
memcpy(
    child1, 
    parent2 + arraySlotForCrossOvr + 1, 
    total_num_slots - arraySlotForCrossOvr);

那麼你可能檢測到超出範兒，還是讓範兒了剛剛進球零下一輪。也許你可以用一些智能來增加交叉，比如將無效值加上最近的有效值等等。

希望有幫助嗎？

另外，我發現「如何解決這個問題：由Z. Michalewicz和d福格爾現代啓發式」試圖瞭解的問題等等:)

來源

2013-04-22 23:25:37 Jimbo

感謝您的解釋。但就編碼而言，我應該生成從0到2n的數字，然後在解碼時從它們中減去n？ – vjain27 2013-04-23 01:08:21

我可能會去2n實施。然後你在處理未簽名的同時進行稍微更友好的位操作。例如。如果您右移一個簽名數量的結果可能不會很好定義（http://stackoverflow.com/questions/7622/shift-operator-in-c） – Jimbo 2013-04-23 06:23:11

遺傳算法二進制編碼負整數

回答

相關問題