[回目錄]

 

轉載啟示

 這篇文章是我轉自另一篇 blog 之 ga code,原標題為  基因演算法(Genetic Algorithm, GA) - Introduction and C code ,想不到大獲好評,該網誌 10% 以上人氣源自於此文,

原文裡其實有不少與其他網友討論之處,是可苳後續版友參考。但由於該文述敘筆者認為還不夠詳盡,故將該文關閉,並將網址導入為此 blog,願能予以稍為詳盡之敘述。在第一次撰寫完該文後,實際發現,對於 ga 而言,一篇 blog 很多東西都講不到。

若只是要一份 sample code,這篇可予以一點參考,但這篇所提供的例子實在是簡單到不行,換到實際上之問題有可能不知該如何對照,故建議再參考筆者 另一份文章 為佳。 

以下,為轉載 blog 之內容,關於說明部份自覺寫得很不好,日後有空做為補充。

 

筆者前言

 

文章看得很 lag,就換瀏覽器。

我很意外這篇 blog 人氣會暴漲,也由於這篇文章,使得我不敢關這帳號。

希望在看 code 前,讀者能耐心先看完筆者一席前言,這點很重要。

 

(1)  This is for beginner.

初版的 code 約是在二年前發出,當時我初學 ga。而初版 code 出來之後,我陸續又閱了其他文獻,部份予以加上實作,故手邊的 ga code 不只一版,有些思慮並不縝密,其中二年前發出的 code,便屬不縝密之一。直到這陣子網友們經由 search 至此篇文章,我才發現原來這篇文章之 code 並不相當縝密,為避免誤導學子,一方面也給予 beginner 一些參考,目前我能做的便是利用閒暇時加以改善。若發現 code 中有誤,請不吝留言回覆。

 

(2) This is not really absolute correct.

GA、pso... etc ,這類型 algorithm ,所有重要運算子的詳細步驟,在一般書本上記載的大多是「原本提出時」、「一般大多這麼做」的詳細步驟,但它們重的是精神,只重其義不重其招,且對於運算子給予不同之解法,得到的效果也未必相同。對於這問題,有一類型之文獻是在探討,在什麼情況下,參數怎麼設;若改變其運算子模式、再加入其他法則,得到的效果如何等。故對於 code 裡詳細之步驟若有所不同,筆者必須說聲抱歉,我沒為那些 paper 留參。

我直接先提出一個備受質疑之處 (質疑的網友們,請體諒我沒任何責怪之意)。我第一次看文獻講到選擇裡的輪盤法時,說的是用隨機式輪盤法;而後陸續看到的是分配式輪盤法。文獻裡只有說「輪盤法」,而不會說那是「隨機式」還是「分配式」,但當我上台 present 這份報告時 (沒放 code, 只用 powerpoint),教授是較偏向「分配式輪盤法」的。以前在找文獻時,印象中較常出現的是分配式,但最近在找時,卻又完全找不到那些分配式的輪盤法跑哪去了,怪哉!一些工作關係,陸續接洽幾個其他研究生,發現不少老師指定要的是「分配式輪盤法」,而非「隨機式輪盤法」。

下面這份 demo code,這二個輪盤法都有寫上去,在這例子裡,從結果也可看出,分配式輪盤法在收斂速度上較隨機式輪盤法速度為快,理由並不難理解,了解之後也可明白為何一般教授指導的部份,會要求用分配式輪盤法。

至於其他的議題,我很不願讓這篇文章看起來長到不行,讓人完全沒心思想繼續讀下去,若還有爭議,一方面可留言給我,我非常歡迎。但請先看過這份內容與其他網友之留言、回應紀錄。若我的答案沒辦法滿足或信服您,那請以手邊資料、或教授所述為主,我相信我對於文獻閱讀量 (關於 ga 我只閱了約 50 篇左右文獻),一定沒教授閱讀量來得多。

 

(3)  This is not for everyone.

 

註解我已盡可能清楚,幾乎是一行一行逐一註解。架構已配合 ga 整體流程做結構化設計。若程式碼真的看不懂,有三個選擇:try those another year、search another code、learning C language again。

最後,不要直接伸手跟我要 code,特別是許多 coder 反感看到只留一個 mail 就要寄過去的人,這行為很糟。既已 public 出來,就自己實際去 coding 一遍,對 ga 整體流程概念、程式語言熟悉度都是加分作用。

 

 

(4) I want to appreciate ..

 

 我深信,這世上沒有任何一個人有義務去幫助另一個人。在此感謝李老師吳老師對於我在演化式演算法之啟蒙;感謝網路上曾給我建議的各位先進、網友。由於要感謝的人真的太多,我也不知該如何向他們表達感謝之意,最後我選擇的是繼承他們的精神,有空時幫忙學子、網友,給予以些意見,也希望這份精神能繼續擴散開來。

 

EdisonX / Edison.Shih

 

修改日期

 

初版日期:2010. 02. 14

   (1) 第一版 ga algorithm 示例碼

一修日期:2011. 11. 21

   (1) 修正未重算 fitness 之筆誤

二修日期:2011. 11. 30 

   (1) 更改struct 內容 ,去除 copy_cnt 贅項 ( dev_value 也可以去,只是懶得去)

   (2) 新增隨機式輪盤法 (收斂速度比分配式還慢)

   (3) 將 code 改為 .c 亦可編譯 (原本 code 只能 c++ compiler, 這份 code 都可以)

* (4) 新增 global best gene 概念 (這是重要的,相信許多文獻沒提但有用)

三修日期:2012.06.15

   (1) 修正輪盤法判別式累計機率問題。

   (2) 修正交配過程個數不配對問題。

   < 補註:此份原始碼並沒特別考慮個體數為奇數之情況,主要是筆者貪懶,認為一般個體數多設為偶數。 >

四修日期:2012.09.17

   (1) 修正 global best gene 於突變更新之錯誤。

跳過的簡介

 

關於演算法的簡介就不說了, GA 主要也是用來解決 NP 問題,下列將用簡單的 f(x) =x*x | 0≦x≦15 , 用 GA 找出最大值,以下說明資料是摘錄自網路加以整理, code 是我自己編寫,但我實在忘了資料出處是哪  如有侵權  請立即告知。

最後, 若對 code 有問題, 歡迎回覆討論。

 

GA 流程

選擇初始生命種群

循環

a. 複製.選擇(reproduction)-評價種群中的個體適應度,並以比例原則(分數高的挑中機率也較高)選擇產生下一個種群(輪盤法 en:roulette wheel selection、競爭法 en:tournament selection 及等級輪盤法 Rank Based Wheel Selection)。不僅僅挑分數最高的的原因是這麼做可能收斂到 local 的最佳點,而非 global 的。

b. 交配 - crossover

c. 突變 - mutation

      直到停止循環的條件滿足

 

變數說明

最簡單的遺傳演算法將染色體表示為一個數位串,數值變數也可以表示成整數,或者實數(浮點數)。演算法中的雜交和突變都是在位元組串上進行的,所以所謂的整數或者實數表示也一定要轉化為數位形式。例如一個變數的形式是實數,其範圍是0~1,而要求的精度是0.001,那麼可以用10個數位表示:0000000000表示0,1111111111表示1。那麼0110001110就代表0.389。

 

適用問題

遺傳演算法擅長解決的問題是全局最優化問題,例如,解決時間表安排問題就是它的一個特長,很多安排時間表的軟體都使用遺傳演算法,遺傳演算法還經常被用於解決實際工程問題。

 

運算子說明

 

一. 複製(reproduction):

1.複製是依據每一物種的適應程度來決定下一代中應被淘汰或複製且保留的個數多寡的一種運算過程。

2.複製過程有兩種形式:

(a)輪盤式選擇(roulette wheel selection)

在每一代的演化過程中,首先依每個物種(字串)的適應函數值的大小來分割輪盤的位置,適應函數值越大的話,則在輪盤上佔有的面積比例也越大,每個物種在輪盤上佔有的面積比例越大代表被挑選到交配池中的機率越大,然後隨機選取輪盤的一點,其所對應的物種即被選入到交配池中。

(b)競爭式選擇(tournament selection)

    在每一代的演化過程中首先隨機地選取兩個或更多的物種(字串),具有最大適應函數值的物種即被選中送至交配池中。  

二. 交配(crossover):

交配運算式,依據交配率從一族群中隨機地任意兩個字元串,經彼此交換字元串的某些位元資訊而產生兩個新位元字串的一種過程,一般而言交配運算可以用三種方式進行交配:(a)單點交配(b)雙點交配(c)均勻交配。

三. 突變(mutation):

突變的過程是隨機的選取一物種的字串,並隨機選取突變點,並改變物種字串裡的位元資訊突變過程發生機率由突變機率所控制。

突變過程可以針對單一位元或對整個字串進行突變演算或以字罩突變方式為之,對於二進制的位元字串就是將字串的 0變1 , 1變成0

 

範例碼

 

GA.h

 

/*******************************************************************/
/*                                                                 */
/*     filename : GA.h                                             */
/*     author   : edison.shih/edisonx                              */
/*     compiler : Visual C++ 2008                                  */
/*     date     : 2010.02.14                                       */
/*     maintain : 2011.11.21                                       */
/*     maintain : 2012.06.15                                       */
/*                                                                 */
/*         A.L.L.      R.I.G.H.T.S.     R.E.S.E.R.V.E.             */
/*                                                                 */
/*******************************************************************/

#ifndef __GA__
#define __GA__

#define GENETIC_LENGTH     4                     //
基因長度
#define POPULATION_CNT     10                    //
母群數量
#define ITERA_CNT          100                   //
迭代次數
#define CROSSOVER_RATE     0.5                   //
交配率
#define MUTATION_RATE      0.1                   //
突變率

// =====================================================
//
定義母體結構
typedef struct tag_parent_t{
     int genes[GENETIC_LENGTH];
     double fitness;
     double dec_value;
}parent_t;

// GAPosRand():
隨機取得突變位置
#define GAPosRand()            (rand()%GENETIC_LENGTH)
// BinaryRand():
隨機產生/1 整數
#define BinaryRand()           (rand()%2)
// SRand():
隨機產生~1 的亂數
#define SRand()                ((double)rand()/(double)RAND_MAX)
// =====================================================

//
進行初始化
void initialize();          
//
複製, 輪盤式選擇(分配式), 決定每個母體複製到交配池的個數
void reproduction();    
//
複製, 輪盤式選擇(隨機式)
void reproduction_rnd();  
//
交配, 交配池中的個體進行交配, [單點交配, 雙點交配, mask]
void crossover();          
//
突變, 逐一bit 慢慢確認突變
void mutation();
//
計算基因所對應之適應值
void cal_fitness(parent_t *x);    
//
計算基因對應之進制值
void cal_xvalue(parent_t *x);    

// =====================================================

parent_t population[POPULATION_CNT];      //
母體數量
parent_t pool[POPULATION_CNT];            //
交配池
parent_t best_gene;                       //
從以前到現在最好的基因

// =====================================================
// binary 2 dec
,將染色體中的二進位(genes) ,轉為實際可用之十進位(dec_value)
void cal_xvalue(parent_t *x)
{
     int i, dec=0;
     for(i=0; i<GENETIC_LENGTH; i++){
         if(x->genes[i] ==1) dec = dec + (0x01 << i);
     }
     x->dec_value = (double)dec;
}

// =====================================================
//
適應函式,此設為f(x) = x*x,其中x 為染色體中之十進位,即dec_value
void cal_fitness(parent_t *x)
{   
     double i = x->dec_value;
     x->fitness =i*i;
}

// =====================================================
//
初始化,
void initialize()
{
     int i, j;
     for(i=0; i<POPULATION_CNT; i++){
         for(j=0; j<GENETIC_LENGTH; j++){
              //
每個母體的基因都是隨機給/1
              population[i].genes[j] = BinaryRand();
         }
         //
計算母體基因之進制值
         cal_xvalue(&population[i]);
         //
計算母體對應之適應值
         cal_fitness(&population[i]);

         //
更新best_gene
         if(i==0) {
              memcpy(&best_gene,
                  &population[i],
                  sizeof(parent_t));
         } else if (population[i].fitness > best_gene.fitness){
              memcpy(&best_gene,
                  &population[i],
                  sizeof(parent_t));
         }
     }
}
// =====================================================
//
複製, 輪盤式選擇(分配式)
void reproduction()
{
     int i, j, cnt, has_copy=0;
     int Slack = POPULATION_CNT; //
還剩幾個可複制
     int pos1, pos2;
     double fitness_sum=0.0;

     //
計算所有適應值總合
     for(i=0; i<POPULATION_CNT; i++) {
         fitness_sum += population[i].fitness;
     }

     //
計算每個母體應複製幾個到交配池中,並直接做複製
     for(i=0; i<POPULATION_CNT && Slack!=0; i++) {
         //
計算應複製個數, 四捨五入
         cnt = (int)(population[i].fitness/fitness_sum * POPULATION_CNT + 0.5);
         //
調整可複製個數
         if(cnt > Slack) cnt=Slack;
         //
開始進行複製
         for(j=0; j<cnt; ++j, ++has_copy)
              memcpy(&pool[has_copy],
              &population[i],
              sizeof(parent_t));
         //
調整Slack
         Slack-=cnt;
     }
     //
若還有沒複製完的
     while(has_copy < POPULATION_CNT){
         //
隨機挑二條不同染色體出來
         pos1 = rand() % POPULATION_CNT;
         do{pos2=rand()%POPULATION_CNT;}while(pos1==pos2);
         //
比較好的那條丟到交配池去
         if(population[pos1].fitness > population[pos2].fitness) i = pos1;
         else i=pos2;
         memcpy(&pool[has_copy++],&population[i],sizeof(parent_t));
     }
}

// =====================================================
//
複製, 輪盤式選擇(隨機式)
void reproduction_rnd()
{
     int i, pos;
     double fitness_sum=0.0; //
適應值總合
     double column_prob[POPULATION_CNT];//
累計機率
     double prob; //
随機機率

     //
計算所有適應值總合
     for(i=0; i<POPULATION_CNT; i++) {
         fitness_sum += population[i].fitness;
     }
     //
計算累計機率累計分配
     column_prob[0] = population[0].fitness / fitness_sum;
     for(i=1; i<POPULATION_CNT; ++i){
         column_prob[i] =
              column_prob[i-1] + population[i].fitness / fitness_sum;
     }

     //
開始隨機抽POPULATION_CNT 個染色體到交配池
     for(i=0; i<POPULATION_CNT; ++i){
         //
產生亂數
         prob=SRand();
         //
取得落於哪一區塊
         for(pos=0; pos < POPULATION_CNT-1; ++pos){
              if(prob <= column_prob[pos] )
                  break;
         }
         //
至此,pos 必為 [0, POPULATION_CNT-1]


         //
複製
         memcpy(&pool[i], &population[pos], sizeof(parent_t));
     }
}

// =====================================================
//
交配
//!< attention :
這裡只考慮母體個數為偶數個,
//!<
若母體個數為奇數個需再做額外判斷處理,否則發生記憶體寫入錯誤。

void crossover()
{
     int i, cnt=0;
     int pos=0;
     int p1, p2;
     double crossover_if;

     while(cnt < POPULATION_CNT) { //!< correct 2012.06.15
         //
隨機選二個個體
         p1 = rand() % POPULATION_CNT;    
         do{p2=rand()% POPULATION_CNT;}while(p2==p1);

         crossover_if = SRand();//
決定是否交配
         if(crossover_if > CROSSOVER_RATE) {
              //
不交配, 將交配池中之個體丟回母體
              memcpy( (void *)&population[cnt++],
                  (void *)&pool[p1],
                  sizeof(parent_t));
              memcpy( (void *)&population[cnt++],
                  (void *)&pool[p2],
                  sizeof(parent_t));
         }
         else {
              //
單點交配, 交配完後再丟回母體
              do{ pos = GAPosRand();} while(pos==0);                
              // crossover
              for(i=0; i<pos; i++){
                  population[cnt].genes[i] = pool[p1].genes[i];
                  population[cnt+1].genes[i] = pool[p2].genes[i];
              }
              for(i=pos; i<GENETIC_LENGTH; i++) {
                  population[cnt+1].genes[i] = pool[p1].genes[i];
                  population[cnt].genes[i] = pool[p2].genes[i];
              }
              cnt+=2; //
已複制完二條
         }          
     }
}
// =====================================================
//
突變
void mutation()
{
     int i;
     int pos;
     for(i=0; i<POPULATION_CNT; i++){
         double mutation_if = SRand();
         if(mutation_if <= MUTATION_RATE){
              pos = GAPosRand();      //
突變位置
              population[i].genes[pos] =
                  1 - population[i].genes[pos];
         }
         //
突變完後再算一次母體適應值
         cal_xvalue(&population[i]);  //
先算基因對應之進制x
         cal_fitness(&population[i]); //
再將進制x 值代入適應函式
         //
再更新best_gene
         if (population[i].fitness > best_gene.fitness){
              memcpy(&best_gene,
                  &population[i],
                  sizeof(parent_t));
         }
     }
}
// =====================================================
#endif

 


ga_Main.c

 

 

/*******************************************************************/
/*                                                                 */
/*     filename : GaMain.c                                         */
/*     author   : edison.shih/edisonx                              */
/*     compiler : Visual C++ 2008                                  */
/*     date     : 2010.02.14                                       */
/*     maintain : 2011.11.21                                       */
/*     maintain : 2012.06.15                                       */
/*                                                                 */
/*         A.L.L.      R.I.G.H.T.S.     R.E.S.E.R.V.E.             */
/*                                                                 */
/*******************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include "GA.h"

int main(int argc, char **argv)
{
     int i,j;

     srand((unsigned)time(NULL));
     initialize();            //
初始化
     for(i=0; i<ITERA_CNT; i++){
         reproduction();      //
選擇(分配式)
         //  reproduction_rnd();  //
選擇(隨機式), 收斂速度慢
         crossover();         //
交配
         mutation();          //
突變f
     }
     printf("\n =========================\n");
     printf(" %3d times..\n", i);
     for(j=0; j<POPULATION_CNT; j++){
         printf("(%5.2lf, %5.2lf) ", population[j].dec_value, population[j].fitness);
         if(j%4==3) printf("\n");
     }
     printf("\n =========================\n");
     printf(" ever find best gene : ");
     printf("(%5.2lf, %5.2lf)\n", best_gene.dec_value, best_gene.fitness);
     getchar();
     return 0;
}

 

 

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


留言列表 (23)

發表留言
  • 路人
  • 期待大大繼承好的態度,大大寫的文章真的很不錯,每次都蠻期待的。
  • 疾之雁
  • 大大你好
    非常感謝你詳細的說明
    在下有一個疑惑想請教
    在隨機式輪盤法的函數 reproduction_rnd() 中
    既然 column_prob[POPULATION_CNT] 是累積機率的話
    if(prob >= column_prob[pos]) break;
    條件是否應該改成 if(column_prob[pos] >= prob) 才對
    (我測試的結果也是這樣,感謝!!)
  • 你說的沒錯。這部份原始碼確實有誤,原文已修正。

    提醒的是,還必需再加上其他修正,
    假設 column_prob[] = {0.123, 0.456, 0.999}
    正常來講最後的 0.999 應該要等於 1.0,

    但浮點數誤差的關係,可能會是接近1.0但小於1.0,
    所以真正取到 prob = 1.0 ,必須考慮怎麼才不會出包,
    才能正確的取到 pos = 2 之情況,修改之部份如下所述。

    --------
    // 產生亂數
    prob=SRand();
    // 取得落於哪一區塊
    for(pos=0; pos < POPULATION_CNT-1; ++pos){
    if(prob >= column_prob[pos] )
    break;
    }
    // 至此,pos 必為 [0, POPULATION_CNT-1]
    --------

    edisonx 於 2012/05/27 01:02 回覆

  • 疾之雁
  • 大大
    我說的那部份似乎還沒改喔?
    --------
    // 產生亂數
    prob=SRand();
    // 取得落於哪一區塊
    for(pos=0; pos < POPULATION_CNT-1; ++pos){
    if(column_prob[pos] >= prob) // 這行
    break;
    }
    // 至此,pos 必為 [0, POPULATION_CNT-1]
    --------
  • 真的是頭昏眼花,已修正。

    edisonx 於 2012/05/28 00:30 回覆

  • 冷凍貓
  • 提醒一下站主"複製, 輪盤式選擇(分配式)"

    // 計算應複製個數, 四捨五入
    cnt = (int)(population[i].fitness/fitness_sum + 0.5);
    這一段可能是有問題的

    因為(population[i].fitness/fitness_sum + 0.5)值域為
    0.5<(population[i].fitness/fitness_sum + 0.5)<1.5
    四捨五入後,值必定為1

    這樣子的話"複製"的行為
    永遠都是每1個基因丟1個進交配池...
  • 抱歉,我怕你沒看到回覆,所以把悄悄話開起來了,
    如果看到我的回覆,不想讓別人看到這提問的話請再留言,
    我把這留言隱藏。

    耶 ~~ 這部份可能您有誤會了一點點。

    >> 0.5<(population[i].fitness/fitness_sum + 0.5)<1.5
    >> 四捨五入後,值必定為1

    事實上不是的,這是 c / c++ 的特性。
    double x ;
    int y = (int)x;
    如果 x 值域為 [0, 1) ,得到的 y 都是 0 ,
    意思是 (int) 轉型是無條件捨去。

    但我想要的做法是「四捨五入」,
    所以簡單的做法是將 x 加上 0.5,再強制轉型。

    說明有點模糊,但搭配看 C/C++ 的資料型態 - 轉型部份應可較清楚。

    edisonx 於 2012/06/15 02:23 回覆

  • 冷凍貓
  • 原來是C++語法的關系,我了解了...

    PS:不用隱藏也沒關係

  • 冷凍貓
  • 不好意思 想再請教一下站主
    在 // 交配 void crossover()這一段

    每一次處理會產生POPULATION_CNT兩倍的子代 到population[]中
    (也就是說共會寫入20筆基因資料)
    但是"選擇"與"突變"的處理範圍為0~9...
    這樣子population[]中位於 10~19的資料都沒處理到

    是不是還需要再做一些其他處理?
  • crossover 那裡的確是寫錯,應以 cnt < POPULATION_CNT 判斷才準確,其中 cnt 即為已交配至 child 之個數 ( 應以 has_done 變數可能較佳 ),謝謝指正。另提醒,這份 crossover 有些不非常完美 ( 筆者貪懶不改 ),因每次交配/不交配都是一次丟二條染色體到 child,若 POPULATION_CNT 為奇數的話,這機制必須做點修改,否則會造成 crash 。

    edisonx 於 2012/06/15 20:43 回覆

  • 阿昌
  • 神人版主你好,非常感謝你的詳細教學,看到這篇真的受益頗多,但有個關於best_gene的問題想要請教:

    parent_t best_gene; // 從以前到現在最好的基因

    而初始化和突變的函數都有這行:
    if(i==0) {
    memcpy(&best_gene, &population[i], sizeof(parent_t));
    }

    best_gene應該是歷代裡最好的基因吧,「初始化」裡i==0要把它存進去沒疑問。但在「突變」的函數裡,為什麼要i==0時要把當代基因存進去呢?這樣不就把上一代最好的洗掉了,變成每次都只有當代再比了?
  • 突變那裡是我寫錯 < 當時複製、貼上所造成的謬誤 >,謝謝您的指正。

    edisonx 於 2012/09/17 22:22 回覆

  • 麴粿
  • 不好意思,我想請問的是有關分配式輪盤的地方,

    cnt = (int)(population[i].fitness/fitness_sum + 0.5);
    這段我不是很能理解,
    是不是代表說 將(某個母體的適應值/總適應值)四捨五入作為複製個數呢?
    如此一來,
    分配式的流程就是將適應值比率大於0.5的母體直接放入交配池,
    剩下的在隨機競爭,
    不知道我的理解有沒有錯誤,抱歉。
    因為我找不太到說明分配式的原文,
    只有看到隨機式的T_T
    不好意思麻煩你了
  • 你說的完全都沒錯。
    分配式是我在很早很早的中文書裡面看到的,原文也沒翻到過;
    隨機式是做累計機率,一般文獻用的是這種方式。

    哪種方法好說不準,也許需要一些運氣+機率不一定,
    只是目前我測的結果是分配式結果稍好一點,但不代表所有情況皆如此。

    edisonx 於 2012/11/20 19:43 回覆

  • zhouguoguo
  • 赞一下楼主,程序写得浅显易懂,我拿来直接改改就可以用了,谢谢楼主的分享。
  • 很開心這篇有幫助到你,祝好運 :)

    edisonx 於 2012/12/26 18:44 回覆

  • Min
  • 您好,我google一下分配式輪盤,找不到答案,想請教您的這行
    cnt = (int)(population[i].fitness/fitness_sum + 0.5);有代表什麼意義嗎?
    我用printf("%d",cnt)來看,都是0.....謝謝
  • 你可以自行分析每個 population[i].fitness / fitness_sum 。

    edisonx 於 2013/06/07 18:15 回覆

  • Min
  • 感謝回覆,我後來有想到fitness最高的優先被丟入到pool,但是我在crossover那裡卡住了,想請問你的population不是設為10嗎?為何crossover裡的cnt那裡可以用到20?然後在mutation那裡只突變前10個@@?謝謝。
  • Min
  • 阿,我這問題上面好像有問到....謝謝。
  • 訪客
  • 你的文章都很讚
  • 這是最好的讚美,謝謝 :D

    edisonx 於 2014/05/27 09:36 回覆

  • 訪客
  • cnt = (int)(population[i].fitness/fitness_sum + 0.5); //這可能會有問題

    改成
    cnt = (int)(population[i].fitness/fitness_sum * POPULATION_CNT + 0.5);

    會比較符合原本分配的意函

    不然cnt有很大的機會是零,除非是個體的fitness算出來是總數的一半,這機率很少,而且最多只會存在一個個體有這機會,並且它也只能獲得一份的複製。
    大家都是零的情況下只會跑隨機分配的程式區塊
  • 疑!真怪,我原版的 code 有,貼來網頁竟沒有。總之,謝謝指正,已修正,感謝。

    edisonx 於 2015/03/02 17:26 回覆

  • Yun Hsuan Liao
  • 謝謝您的分享,我想請問一下,如果我想要用原本的基因population[i].genes[j]分別表達兩個以上變數的話,程式要怎麼寫
  • 作法很多種,最直接是對 struct parent_t 重新定義,
    裡面的 int genes[GENETIC_LENGTH]; 是一個變數,你要第二個變數可以 "追加"
    int genes2[GENETIC_LENGTH2] ; 當然變數名稱可以自己命名,其他的自己再視問題修改。

    edisonx 於 2015/03/03 23:40 回覆

  • 紋
  • 不好意思,請問如果我是第一次接觸GA什麼都不懂,那我要從哪裡先下手
  • 先找本書下手,已經有些書是用 C 語言做 GA 及類神經算法,也有說明。

    edisonx 於 2015/05/05 10:24 回覆

  • winton
  • 想請問#include "GA.h"的部分 要怎麼撰寫?
    DEV C++編譯會跑出[Error] GA.h: No such file or directory,
    初學 麻煩大大解答
  • Source Code Release 確定可跑,且這份 Code 已包含 GA.h 在裡面,我的 code 註解已經很清楚,請用心看 (這是你出錯的主因 - 拿到 Code Copy-Paste ,不能跑後也不看註解或找其他 solution)。初學的話請先熟悉你的 IDE 、工具、錯誤訊息怎看。

    edisonx 於 2015/10/15 16:26 回覆

  • winton
  • 我有把GA.h和ga_Main.c分開run
    都會跑出()範圍未聲明.
    -
    初學者Copy-Paste才正常吧,
    一來看看會跑出什麼結果&改一些地方看自己觀念是否正確.
  • 我沒說 Copy-Paste 不正常,重點是後面兩句。如果分開檔案一起編譯這個不會的話,我想你該嚐試的是其他的方案或是 solution。這本文章重點是 GA , 我沒把重點放在 C 語言之基礎教學上。

    edisonx 於 2015/10/20 19:27 回覆

  • m5735322
  • 請問一下 依您程式來看 好像不是單點交配,分二個迴圈,pos前copy到cnt cnt+1,後半段交換cppy到cnt+1 cnt,這比較像mask方式?
  • 這不就是單點交配?

    edisonx 於 2015/11/20 16:13 回覆

  • m5735322
  • 我記得單點交配 應該是只交換一個bit, 而不是整段交換?
  • 是整段交換,或是你可以再找其他文獻佐證。

    edisonx 於 2015/11/23 02:13 回覆

  • Wellson
  • 您好 我最近剛學c
    想請問您x的範圍 0≦x≦15是在程式哪邊設定呢?
    初學不是很理解 不好意思
  • 基因長度我設成 4 ,對應到的範圍也就變為了 0~15

    edisonx 於 2016/04/18 02:43 回覆

  • 我很好奇
  • 看了後終於知道什麼是 基因演算法, 3Q

    調整參數的行為好像
    射出一支箭 ==>
    畫一個靶? 然後在慢慢移動靶到 中箭處?

    我很好奇
    有一個疑問是 search 最優解?

    應該不會 事先 知道 哪一個是最優解?
    也就是不知道 射的出箭落在何處?

    那麼? 如何 移動靶到 中箭處?

  • 幾乎每個演化式算法都會經過調參數這關,甚至不同問題也有不同調法。

    另不論 GA , PSO , ... etc , 並沒有保證找到的會是最優解。

    edisonx 於 2016/04/18 02:45 回覆

  • 好奇
  • 這個問題我困惑了很久
    你的意思是?

    比如 求 最大值:
    1: 調整 各項 參數
    2: 然後看看 哪一組 參數 得到的值 最大 [儘管它不是真實上的最大​​值, 但他 已經是 所求得的最大了]
    3: 就使用 這組參數 作為求解這個問題 的參數 是嘛?

    謝謝, 3Q
  • 我認為你沒了解 GA 整體運作及設計流程,或許你該直接 implement 一個小的問題,多改幾次 code 看實驗結果就知道了。

    我不知道確認你第一個問題說的「各參數」是不是源自於編碼,還是突變率、交配率、突變方法、交配方法等。

    你對於基因算法 "編碼" 的概念熟悉嗎?如果不熟的話請先看另一篇文章
    http://edisonx.pixnet.net/blog/post/90563824

    1. 調整各項參數
    這本身是視問題本身會有不同編碼,除了不同編碼,不同的交配方式、選擇方式、適應值計算方式也會有影響,所以要調整的可能不只是 "參數" ,也會搭配 "方法" 下去做測試,所以測試的東西可以很多。

    2. 你的敘述並不正確,一般我們會設「母體個數 (假設 50 個) 」和「最大迭代次數 (假設 100 次) 」,在第一次迭代裡,所有的母體都有自己的適應值,假設問題是望大,最佳適應值是 20;在第二次迭代裡,所有母體也有自己的適應值,最佳適應值反而縮成 10 了,因為我們不能保證每一次的迭代都會使得最佳適應值會 "愈變愈好",所以需要一個變數,去存從以前到現在 ( 這 100 次迭代) 裡,表現最好的染色體。後半段才是如你所說的,就算這 100 次迭代裡拿到一個表現最好的染色體,我們也不能保證它是最佳解,也可能因為編碼的設計導致找到的解和最佳解差很多,這個我給你的另一個連結有講到這問題。當然除了編碼方式之外,也有很多細節可能導致找到的解和最佳解有一段距離。


    3. 即使同一個問題,不同規模大小、不同限制,也可能使得參數、編碼方式不一。

    可能我理解能力不太好,總覺得你問的問題和 GA 的本質有些搭不上。

    edisonx 於 2016/04/21 01:46 回覆

您尚未登入,將以訪客身份留言。亦可以上方服務帳號登入留言

請輸入暱稱 ( 最多顯示 6 個中文字元 )

請輸入標題 ( 最多顯示 9 個中文字元 )

請輸入內容 ( 最多 140 個中文字元 )

請輸入左方認證碼:

看不懂,換張圖

請輸入驗證碼

【 X 關閉 】

【PIXNET 痞客邦】國外旅遊調查
您是我們挑選到的讀者!

填完問卷將有機會獲得心動好禮哦(注意:關閉此視窗將不再出現)

立即填寫取消