Edison.X. Blog

0. 建立適當結構體

  在做任何演化式演算法時，較建議直接先把該定的結構定出來。如下所示

typedef unsigned char byte;

/* 母體個數 */
const unsigned parent_cnt = 50;
const unsigned gene_len = 20;
typedef struct TagChrom{
    byte* gene; /* gene[基因長度] */
    double fitness; /* 對應之適應值 */
}Parent, Child;

/* 父代與子代配置 */
Parent *p = (Parent*)malloc(parent_cnt*sizeof(Parent));
Child *d = (Child*)malloc(parent_cnt*sizeof(Child));
for(int i=0; i!=parent_cnt){
    p[i].gene = (byte*)malloc(sizeof(byte)*gene_len);
    d[i].gene = (byte*)malloc(sizeof(byte)*gene_len);
}

但聲明，這並不是很好的範例，調用 malloc 頻繁，使得速度拖慢。這份只是說明，在做任何演化式演算法時，請把必要的資訊都用 struct 包起來，上述之 struct 便還有「對應十進位」、「應複制個數」等資料可考慮加進去。

1. 動態建立二維陣列

動態建立二維陣列常是演化式演算法之第一步驟，常見的方法是

#define X 10
#define Y 20
int **a = (int**)malloc(sizeof(int*)*X);
for(int i=0; i!=X; ++i) a[i]=(int*)malloc(sizeof(int)*Y);

這方法簡單，但不快，且容易浪費空間，到時要做 free 動作也麻煩，較好的方式

#define X 10
#define Y 20
// 一次把空間建起來
int *trunk = (int*)malloc(sizeof(int)*X*Y);
int **a = (int**)malloc(sizeof(int*)*X);
for(int i=0; i!=X; ++i) {
    a[i]=trunk;
    trunk+=(sizeof(int)*Y);
}
// 刪除時
free(*a), free(a);

一開始看很複雜，但在做 AI 類演算法時務必用這方式進行。另，為日後調用方便，建議包含副函式方式，如下所示

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ROW 3
#define COL 5

typedef unsigned char byte;
void** malloc2(unsigned row, unsigned col, unsigned Size)
{
    register unsigned i=0;
    byte* trunk = (byte*)malloc(Size * col * row);
    if(trunk==NULL) return NULL;

    void** ptr = (void**)malloc(sizeof(void*)*row);
    if(ptr==NULL) return NULL;

    for(i=0; i!=row; ++i) ptr[i] = trunk, trunk+=(Size*col);
    return ptr;
}

int main()
{
    int i, j;
    int **a, **b, **c;
    a = (int**)malloc2(ROW, COL, sizeof(int));
    for(i=0; i!=ROW*COL; ++i) *(*a+i)=i;

    for(i=0; i!=ROW; ++i){
       for(j=0; j!=COL; ++j) 
          printf("%2d ", a[i][j]);
       putchar('\n');
    }
    free(*a), free(a);
    return 0;
}

優點為，不會有記憶體碎片化問題。關於碎片化問題仍有所爭議，部份人認為程設師壓根兒不用考濾碎片化。

注意到，由於演化式之演算法對於記憶體需求量並不小，故在進行配置時，務必檢查記憶體配置是否成功；若因記憶體需求量太大時，再另行出路。

2. 亂數部份

亂數寫得好不好，間接決定了這個程式跑得好不好、結果好不好，當然，還有一重要因素為：亂數產生器之品質如何。亂數部份吾人所著於 另一篇 文章裡有提到，有幾點需注意；有幾點是要再特別提的部份。這裡所說之應用多為 GA 會用到的亂數問題。

(2.1) 隨機產生 0/1 染色體部份

這部份較沒問題，切記別用 rand() %2，雖部份 compiler 會予以優化，但仍以 rand() & 1 方式為佳。

(2.2) 浮點亂數

在 GA 中，必需設定 交配率 (約 0.9) 與突變率 (0.005~0.001，也可能高些)，於是必須產生隨機亂數 [0, 1]，於該文中，曾提到產生 含0含1 之隨機亂數為

#define RAND_FLOATING() ((double)rand()/RAND_MAX)

const double CROSSOVER_RATE = 0.9; /* 交配率設 0.9 */
const double MUTATE_RATE = 0.005; /* 突變率設0.005 */

if( RAND_FLOATING() <= CROSSOVER_RATE) // 交配
/* do something for crossover */
if( RAND_FLOATING() <= MUTATE_RATE) // 突變
/* dosome thing for mutate*/

這種 RAND_FLOATING 使用率非常高！若以 50 個母體，基因長度為 20，一代之突變就要測試 1000 次；一代之交配又要測試 45 次。若測試代數為 1000 代，則這種函式將用到 (1050 * 1000 = 1050000) ，約一百萬次！這還只是保守估計值而已，實際上次數可能會更多，於是這部份期能予以加速。

最簡單、直覺的方式，是直接與某數值做比較。以 RAND_MAX = 32767 為例，若是交配率為 0.9 成功，代表若 rand() 出來的結果小於等於 (32767 * 0.9 = 29490.3) 時，便執行交配動作，也就是 rand() <= 29490 時進行交配。這裡有種情況要思考：rand() 出來的值是從 0~RAND_MAX = 32767，共有 RANX_MAX+1 = 32768 個，若交配率為 0.5 時，代表前一半的數值都是要交配的，後一半的數值不用交配。考慮了這個原因後，便可寫下以下的程式碼

const double CROSSOVER_RATE = 0.9; /* 交配率設 0.9 */
const double MUTATE_RATE = 0.005; /* 突變率設0.005 */
const int CROSSOVER_VALUE = (int)(CROSSOVER_RATE * (RAND_MAX+1));
const int MUTATE_VALUE = (int)(MUTATE_RATE * (RAND_MAX+1));

if( rand() <= CROSSOVER_VALUE) // 交配
/* do something for crossover */
if( rand() <= MUTATE_VALUE) // 突變
/* dosome thing for mutate*/

這樣下來省去了浮點數之除法，速度上應也有所改善，同時浮點數誤差部份亦較小。

(2.3) 產生  [0, N] 之整數亂數

這部份在 GA 中有二部份會用到，一部份為取得交配點；另一，若在選擇階段是採用「競爭法」，則要隨機取 2 個不同染色體比較其適應值。這二個問題有點不同，但處理方式大同小異。

若是要算交配點時，假設染色體長度為 len，位置為 0~len-1。隨機產生交配點假設為 5，則 0~5 給新的染色體 A；6~len-1 給新的染色體 B。這裡便注意一個問題，交配是以：交配點以左 (含該交配點)為一部份；交配含以右(不含交配點)為另一部份，若交配點剛好是在 len-1 會有什麼情況發生？嗯，只是二條染色體完全交換而已，並不會進行交配。於是在交配時，實際上要產生的亂數應為 [1, N-1]，而非 [0, N-1]。舉個例子，若基因長度為20，則實際要取得的隨機亂數位置應為 0~18，不能到19，因取到19時便是二條染色體全都交換，就沒交配到。另產生 [a,b] 之亂數不要用 rand() % (b-a+1) +b 之方式，因算出來不夠均勻，一律用浮點數方式處理。附上產生 [1, N-1] 之原碼參考

#include <stdio.h>
#include <stdlib.h>
#define GEN_LEN 20 /* 基因長度為 20 */

/* 取得 1~GEN_LEN 之隨機整數亂數  */
#define RAND_POS() ((int)((double)(GEN_LEN-1)*rand()/(RAND_MAX+1)))

// 測試
int main()
{
    int table[GEN_LEN+1]={0}, i;

    // 產生 1000 次隨機位置
    for(i=0; i!=1000; ++i){
       ++table[RAND_POS()];
    }

    // 產生之次數印出來
    for(i=0; i!=GEN_LEN; ++i){
       printf("%d %d\n", i ,table[i]);
    }
    return 0;
}

再來，是若選擇策略是採「競爭法」時，要先隨機抽二條染色體出來，fitness 較佳的再丟進交配池裡面。這裡用到的亂數是 [0, N-1] 之整數亂數；也由於只要抽二條染色體，故不用 shuffle 方式，直接用 while 處理。程式碼參考如下

#include <stdio.h>
#include <stdlib.h>
#define POPULATION_CNT 50 /* 母體個數 */

/* 母體中 0~49 挑一個出來 */
#define PICK_ONE() ((int) ((double)(POPULATION_CNT)*rand()/(RAND_MAX+1)))

// 測試
int main()
{
    int pick1, pick2;
    pick1 = PICK_ONE();
    do{pick2=PICK_ONE();}while(pick1==pick2);
    return 0;
}

3 其他運算技巧

bitwise 技巧可於 這篇文章 中取得，許多函式都可以其技巧加速。以下針對 GA 部份用到技巧說明

(3.1) 遮罩式交配

在做遮罩式交配時，常有這段碼

#define GEN_LEN 20
typedef unsigned char byte;

byte a[GEN_LEN], b[GEN_LEN], mask[GEN_LEN];
byte na[GEN_LEN], nb[GEN_LEN];

// a 與 b 經過 mask 交配後產生 na nb
for(int i=0; i!=GEN_LEN; ++i){
    if(mask[i]) na[i] = b[i], nb[i]=a[i];
    else na[i]=a[i], nb[i]=b[i];
}

那個 if 可拿掉，用卡諾圖化簡後可得到下列表示

#include <stdio.h>
#include <time.h>
#define INT_MAX 2000000

#define GEN_LEN 20
typedef unsigned char byte;

byte a[GEN_LEN]={0}, b[GEN_LEN]={0}, mask[GEN_LEN]={0};
byte na[GEN_LEN]={0}, nb[GEN_LEN];

// a 與 b 經過 mask 交配後產生 na nb
for(int i=0; i!=GEN_LEN; ++i){
    na[i] = (a[i]& !mask[i]) | ( b[i]& mask[i] );
    nb[i] = (a[i]& mask[i])  | ( b[i]& !mask[i] );
}

 但，是否有比較快倒是待驗證 (預計慢些)

(3.2) 解碼時之運算

這只是簡單的技巧，簡略說明。假設編碼長度為 10 ，所對應之實數範圍為 -2~2。則希望之解碼方式如下

 這裡是一個簡單的線性關係，假設基因解出來之十進位為 x ；所對應到之實數為 y，則

 故求出來之 Y = (X-Xmin)*(Ymax-Ymin)/(Xmax-Xmin) + Ymin。而言，有幾個常數是一開始知道的：Xmin, Xmax, Ymin, Ymax，這些都可以將它設成常數，以增快求解速度！

(3.3) 增快排序速度

排序這個動作會執行很多次。只要每一次使用「輪盤法」進行複制時就要事先排序一次，但通常資料量並不大 (母體數並不大)，可考以使用內建之 qsort 進行排序。

(3.4) 記憶體真的不夠用該怎麼辦？

目前就吾人所知， 可在 heap 配置約 2G 記憶體，若使用時超過此上限，可考慮改用 C++ 之 vector 應還可再增一些。若還要再大的話呢？ 嗯，這的確又是個好問題，值得研究。 若為單機處理，寫入檔案，但速度拖慢；若為多機，可考慮平行化處理，這部份於此便不探討 (主要是沒接觸多處理問題 ) 。

(3.5) 善用 memcpy 指令

在做交配動作時，產生交配點後，別「一點一點」逐點設給子代，直接用 memcpy 方式應會較快 (雖 MSDN 上提到 memcpy 為 O(n)，但 HC 應較小 )，這裡只簡略示範

#include <stdio.h>
#include <string.h>
typedef unsigned char byte;
int main()
{
    byte x1[8]={0,1,2,3,4,5,6,7};
    byte x2[8]={7,6,5,4,3,2,1,0};
    byte new1[8];
    // 假設取得之交配點為 5
    int pos=5;
    memcpy(new1, x1, sizeof(byte)*pos);
    memcpy(new1+pos, x2+pos, sizeof(byte)*(8-pos));
    for(int i=0; i!=sizeof(new1); ++i) printf("%d ", new1[i]);
   return 0;
}

# END FOR NOTE #