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。則希望之解碼方式如下

基因位置 0 1 2 3 4 5 6 7 8 9 對應十進位 對應實數 實數
編碼最小值 0 0 0 0 0 0 0 0 0 0 0(Xmin) -2(Ymin) 最小實數
編碼最大值 1 1 1 1 1 1 1 1 1 1 1023(XMax) 2(YMax) 最大實數

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

X-Xmin   Y-Ymin
Xmax-Xmin = Ymax-Ymin
 

 故求出來之 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 #

 

edisonx 發表在 痞客邦 PIXNET 留言(0) 人氣()