[公告] 痞客邦「應用市集」新 App 上架-iFontCloud Professional[公告] 痞客邦後台發表文章提供插入多張圖片新功能[公告]痞客邦新服務上線 部落客商店聚集就在《痞市集》[公告] 部落格「快捷功能BAR」改版介紹[公告] 痞客邦「快捷功能BAR」6月4日改版通知

本文即將關閉,後續欲討論請至另一篇 blog -

[GA] 基因演算法(Genetic Algorithm, GA) - Introduction and C code

 

筆者前言

 

文章看得很 lag,就換 firefox。

我很意外這篇 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 概念 (這是重要的,相信許多文獻沒提但有用)

 

跳過的簡介


關於演算法的簡介就不說了, 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 的最佳點,而非 globe 的。

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                                       */
/*                                                                 */
/*         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 + 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; ++pos){
                if(prob >= column_prob[pos])
                     break;
           }
           //
複製
           memcpy(&pool[i], &population[pos], sizeof(parent_t));
     }
}

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

     for(itera = 0; itera < POPULATION_CNT; itera++){
           //
隨機選二個個體
           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(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));
           }
     }
}
// =====================================================
#endif

 

GaMain.c

/*******************************************************************/
/*                                                                 */
/*     filename : GaMain.c                                         */
/*     author   : edison.shih/edisonx                              */
/*     compiler : Visual C++ 2008                                  */
/*     date     : 2010.02.14                                       */
/*     maintain : 2011.11.21                                       */
/*                                                                 */
/*         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;
}


 

Posted by Edison at 痞客邦 PIXNET 留言(40) 引用(0) 人氣()


open trackbacks list Trackbacks (0)

留言列表 (40)

Disable comments
  • EdisonShih
  • GA 可以補充的資料實在是太多了
    看來一篇還是寫不完的 = =
  • 阿M
  • 不好意思 有些問題請教 假如我要再設定基因那裡要控制1的個數我該怎麼寫,
  • #define GENETIC_LENGTH 4

    上面這行 code 就是定義基因自身長度

    若有問題,歡迎發問

    或以悄悄話留下 msn 一起討論 ^^

    Edison replied in 2010/08/05 08:20

  • Private Comment
  • 魷魚
  • 請問一下
    我改動#define GENETIC_LENGTH 4 這行成5
    應該理論上他範圍會從0~15變成0~31
    但不知為何我跑出來的結果都一樣是未更動前的樣子
    請問是為什麼呢?
  • 正常的確是從0-31,
    有興趣的話請 po 上你 code 的連結..

    Edison replied in 2010/09/14 16:36

  • 魷魚
  • 我CODE就是版主你貼的那段
    純粹只更動基因長度那行的定義而已
    我是想說會不會是你有把長度寫死在哪裡 所以才不能變動@@
  • 我跑過之後,確定會從 0-31 沒錯,
    所以我很納悶你說只有 #define 那段更改
    ( 因我copy - past 自己的東西,更改後是可以正常執行的)
    or, 你可了解其精華後, 自行寫一段 code..

    Edison replied in 2010/09/15 18:17

  • Jenny
  • 請問版主, 如果要用基因演算法去算出移動物件的下一個點出現位置
    現在我們手上有的是發現移動物件時這一個點的速度, 時間與正要去的方向, 與物件前一點的速度時間與方向, 這樣基因演算法的算式要如何算?
  • 你的問題似乎不適用基因演算法唷,就你的東西而言,看起來比較像是粒子移動演算法(PSO)的過程,然而如果這真的是你要解決的部份,你應該是要去找一些數學式,因為基因演算法是屬於 "尋優式問題" 的演算法,找出來的解不保證是最佳解,但會是趨近於最佳解之近似解,至於你的問題聽起來似乎根本還用不到GA.

    Edison replied in 2010/09/29 22:19

  • Jenny
  • 物件移動預測

    版主 您好
    我是剛剛的Jenny, 我教授要我寫的, 就是要利用你所謂的"尋優式"的基因演算法, 去預測物件動向, 也許第一次預測的不是最佳解. 當透過很多次的基因演算法預測, 預測就會越來越準確. 所以你是上面的例子中, F(X)=X*X 的部份, 如果我要放入速度S, 方向D的話, 要變成F(S, D)嗎? 那F(S, D) = 會等於多少? 才可以跑你以上的流程, 基因長度與母體數量要設成多少? 原諒我這個初學者, 基因演算法, 我真的ㄧ竅不通. 我可以留下我的MSN 每天ㄧ些些跟主討論嗎? 不然我畢不了業....(哭), 我的MSN: sow888@hotmail.com
  • 你說到重點了, 的確是 F(S,D),但 F(S,D) 的函數似乎是專業領域的東西,這部份你是否有念過相關之 paper 在探討?或是有相關之書籍有介紹?我想這是你該先去 research 的部份,畢竟基因演算法並沒辦法幫你把算式列好直接下去做..

    Edison replied in 2010/09/30 00:05

  • Jenny
  • 物件移動預測

    版主您好, 如果單純就速度來看, 當物件從a點移到b點時 , 時間會從t1 變成t2, 而位置座標會從(Xa, Ya), 變成(Xb, Yb), 因此只單純討論速度,算式會是
    F(S)=((Xb-Xa)平方 - (Yb-Ya)平方)之後, 開根號 / T2-T1 ,

    有以上算式是否就可以依序討論以上版面的基因演算法流程?
    如果將速度與方向分開的話, 兩者均已經有算式了
  • 這部份可議性很大, 我比較好奇的是:其實作業研究裡面已經有一章節在講 "預測", 你對於那章熟嗎?單純預測的話我想裡面的章節應該也已經夠用了.只是覺得很納悶.. 為什麼一定硬要搞成 GA.. 你可以給我一個這個問題要用到 GA 的理由嗎?( 怎麼看都是預測不是尋優解 )

    Edison replied in 2010/09/30 00:37

  • Jenny
  • 昨天謝謝您的回覆, 怕我一次問太多, 嚇到你, 因為我對GA實在是完全門外漢, 所以版主如果不嫌棄, 我一天按照你以上順序發展, 問你5個問題, 謝謝版主幫我加入MSN,
    這次GA演算法式要用在WSN, 為了省電所以需要利用睡眠模式, 當在設定睡眠時間後醒來, 就要再繼續偵測, 所以會變成需要預測, 其他的研究, 有人也是用單純的速度, 方向平均等去預測, 而我這次論文就是要去比較GA預測與其他的單純預測有何差異, 是否GA預測會比較準, 省比較多電
    你可以參考一下website 的第四項
    http://dblab.csie.ncku.edu.tw/sensor/index.html

  • 在文獻上,GA 的確有用來做過預測,但每個文獻之 GA 必須包含各個專業領域所應用到之知識,且使用類神經網路做預測的文獻更多,也有使用 GA+類神經 之方式,我不是很清楚你的情形是不是一定要用到GA, 如果不用的話, 考慮一下類神經網路, 另外如果你對 GA / 類神經 沒有很熟的話, 你應先找相關文獻, 即使是商科的文獻也可以(做股票預測的不少, 做銷售的文獻似乎可以讓你比較看得懂),另外你必須考慮到一個情形,GA 可以調整的參數多,每個參數做出來的結果都可能不盡相同,大多數人使用(交配率、突變率、群體個數)設多個變數去 try error,每個參數設3個值,每組參數跑3次,就要跑81次,如果你做出來的結果,GA 預測沒有比較準怎麼辦?如果是我的話我會選擇用 類神經 演算法而不是基因演算法。
    在此你必須確定一件事,因為你是要做 預測 ,那你的 sensor 是否可以控制寫入記憶體?記憶體你是否讀得出來?不然你怎麼做歷史資料的分析和預測準確度的分析?

    Edison replied in 2010/09/30 16:52

  • Jenny
  • GA 預測

    有關你最後問的歷史資料問題, 我也曾經問過教授, 他回答說 :"利用os(作業系統),之分頁預測如何記錄歷史,預測未來、或權重或分割,來做ga的運算" ,
    另外, 許多研究, 對於sensor的部份, 大多都是用模擬實驗, 不是實際去布sensor,讓它跑 , 所以我可以先不用擔心sensor是否可以控制寫入記憶體或是記憶體我是否讀的出來
    說的這麼多, 因為我不懂, 所以教授要我先寫再說, 碰到問題再問, 他覺得GA可以做.
    言歸正傳, 我今天要問的問題, 假設 我的演算法是 昨天說的 F(S)=sqrt((xb-xa)平方-(Yb-Ya)/tb-ta , 0≦S≦5, 會在120m * 120m 的面積裡面, 隨機佈滿 95個sensor, 模擬總時間為120秒, 每次偵測時間2秒, 睡覺5秒, 回報1秒,
    1- 請問我基因長度要如何設? 跟你的ㄧ樣是4嗎?
    2- 母群數量10, 我要怎麼設? 會是95嗎? 因為有95個sensor
    3-佚代次數的1000, 可是偵測秒數, 或是偵測次數嗎?
    4- 交配率, 突變率 可以設成跟你ㄧ樣嗎?


  • 針對你的問題,我非常了解一件事:你沒有看過 GA 的相關文獻 = =,coding 而言如果不了解演算法是件非常危險的事情,因為最後不知道初步結果到底對不對,同時也浪費了一堆時間,如果你們學校有圖書館的話,請先借閱相關書籍,或直接在網路上google 基因(遺傳)演算法,將有一狗票的東西在做性質上的介紹。

    在此先說 GA 初步最重要的二個步驟:(1) 設計適應函數 (2)編碼。我舉的例子只是很簡單的 MAX f(x) =x*x | 0≦x≦15,注意到了嗎?是 MAX,極大化。而你所寫的 fitness function: F(S)=sqrt((xb-xa)平方-(Yb-Ya)/tb-ta , 0≦S≦5, 我從頭到尾都不知道你是要 MIN F(s) 還是要 MAX F(S),還是其實你的適應函數是你的 "預測值" 扣除 "模擬值" ? 這個我真的不清楚

    1. 基因長度決定是在於解碼的範圍與精準度,上例由於我是 0<x<15 之 "整數",用2進制表示需要4個bits,所以我才設為4,但如果是 0<X<1 之小數,這時長度就會影響你的精準度,如果氞度只有設1,那結果不是0就是1,很不好,因為不能表示小數,如果長度是度10,則0000000001,代表的是 2^(-10),這裡有一定的公式可以計算你要範圍和精準度去決定你的基因長度,推導不難,要找書可以,上面 "變數說明" 也有說明了,當作是你的 homework。

    2. 母群數量和你的 sensor 個數沒有關係,每一個個體代表的是一個 "可行解",經過演化後,希望能演化成 "趨近最佳解",數量通常是設 50 或 100,但沒一定的規則。

    3. 不行。迭代次數就代表演化代數。
    4. 交配率和突變率事實上是自己要去試的,我的東西我試了不下一百次,當然我連母群數量也試了,能得到最好的結果,可以說是針對這個問題較好的參數。(這也就是為什麼有些論文在探討怎樣的問題要設怎樣的參數,不過這些論文真的不好找,大多人都針對這三個參數進行 try error, 甚至直接用程式一次跑完所有參數。)

    基因演算法概念我直接舉個例子,假設全世界只有 100 個人(母體個數),這100個人都沒有性別(可自由交配),這100個人即為第一代。現在我們依照他們的能力強弱(適應值)去決定要複製幾個同樣的人到交配池裡面(接間地,適應值差的人會被淘汰),再從交配池裡抽2個人出來進行交配,如果他們交配成功(依交配率看有沒有成功),就會有新的第二代子代,如果交配失敗,就直接把這二個人丟到第二個子代去,這個動作進行50次,就會有100個子代。接下來每一個子代有可能會發生突變(依突變率),突變發生的話基因會發生怎樣的改變?(我的例子是反向運算..),突變完後第二代的100個子代,再次進行一次演化,生成第三代,一直下去到1000代,這是迭代次數的意義。至於你說的偵測秒數、次數,我想那些應該是屬於 history data 的部份,是該拿來做參考的。

    就算你要做即時系統,你還是要拿 history data 來做校準的參考依據,等模型發展完後再去做比對才是。不然可以將 history data 的 8 成資料當訓練資料,另外2成資料當驗證資料。

    最後想告知你,我不是理工背景的,如果提到一些比較專業性的東西,我想我的幫助是有限的。

    Edison replied in 2010/10/01 02:14

  • Jerry
  • 請問版主
    我想讓一條染色體轉換成2個十進位的x,y值要怎麼寫?
  • 耶..這問題真的不好說耶.
    何況染色體的編碼當初是由設計者編的,
    要怎麼解編碼成 x, y也是由設計者編的
    只要合理就行

    你有看過上面的解釋和我給你的 ppt 了嗎?
    如果你沒程式底子的話我真的不知該如何教你
    上面的 cal_xvalue 就是從二進位編碼之染色體
    換算為十進制的 x, y 值
    或許你應該先查詢,如何將二進制轉為十進制
    與十進制轉為二進制..

    建議你先集中火力花一個月時間學程式語言比較實際
    如果都慢慢學,你的論文很快就會卡住寫不下去
    考慮一下在當地找個家教或和老師說明你的情況吧
    這樣下去真的不是辦法..

    Edison replied in 2010/10/09 18:49

  • Private Comment
  • arain60124
  • 版主您好~
    我對於程式一點也不熟,不過最近需要用VB寫基因程式,因此想請問一下,我應該如何下手比較好???謝謝~
  • 1. 先練習你的程式語言到"基礎部份"熟練的地步。
    2. 徹底了解 GA 演算法之特性,並看範例之計算過程與整體流程,以確定你會設計整個適應函數、染色體編解碼等,其餘之部份應視該專業領域之專業給予適當之修正。

    Edison replied in 2010/10/12 18:24

  • 留痕
  • 版主

    請問你編譯軟體是哪一套?!
  • vc6.0, vc2008, dev-c++ 均測過無誤

    Edison replied in 2010/10/13 00:00

  • 留痕
  • 請問版主

    您那邊有沒有用實數編碼的相關資料(或是範例程式碼)?!
  • 我都是用二進制編碼後再轉成實數,
    如長度為10,0-1023
    欲表示為 1.2 ~ 2.8
    則染色體若為 10000000 = 512 = x
    假設此染色體對應到之實數為 y, 則
    x / (x_max - x_min) = y / (y_max - y_min)
    => 512 / (1023 - 0) = y / (2.8 - 1.2)
    => y = 512*2.6/1023 = 1.30127

    由上可知,其染色體長度愈長,可表達的精度愈高。
    這些東西在上次寄給你的資料裡面都有了,
    知道原理後就很容易實做了,這部份程式碼請自行編寫。
    或是你可以再找其它的實數編碼方式。

    留言內容如無私密資料, 盡別用私密留言,
    如果上來看沒人留言, 我不會進行登入解答。

    Edison replied in 2010/11/09 02:48

  • shine
  • 版主你好,最近在寫作業要用到,
    你的內容講解對我幫助很大。
    不過初始化那邊 code 好像打錯了,
    應該是 j<GENETIC_LENGTH 才對。
    感謝你的熱心教學。
  • 放了這麼久你是第一個發現,
    謝謝您的指正

    Edison replied in 2010/11/14 15:11

  • 余
  • 抱歉,第一次學ga法
    請問期刊裡有ga法,那該如何應用呢?
  • 有點不懂你要說的意思

    Edison replied in 2010/12/08 15:19

  • 小夫
  • 版主你好~我已經有看過GA的一些相關流程~但對於實際上的做法~有點不懂~可否與你用MSN來做討論呢?
  • 有問題直接po在 blog 上討論即可。

    Edison replied in 2011/01/18 17:00

  • cooler
  • 板主你好:
    不好意思打擾了,我專題也是寫ga演算法,有幾個問題想請教您

    我設定一開始母群體100個,經由複製較好的(by roullete wheel),產生新的200個,再由crossover probability決定是否交配,若A,B可繁殖(because crossover prob)則有子代a,b,若不可繁衍則將A,B直接加進子代中.

    我第一個問題是,如果可以繁衍,那AB還要不要加進子代中呢..?

    如果crossover prob是100%好了,(如果A.B不加進子代中,)這樣會產生200個子代,
    第二個問題是作第二次疊代時是以原始母群體100個再加上200個子代去跑是嗎..?

    謝謝板主回答:)
  • 這裡先講三個名詞:母群、交配池、子代。整個 GA 的流程(1) 選擇:母群(100個)選出較佳的(你是用輪盤式)到交配池,這裡請先確定你複製到交配池是不是真的是 200 個母代(選擇出來的母代);
    (2) 交配:從交配池隨機取二個出來,再依 crossover rate 決定是否交配,如果決定交配,把交配後的染色體丟到子代去;如果決定不交配,直接把那二個染色體丟到子代去。
    (3) 突變:每條染色體每個基因都要經過突變率的測試,如果子代有200條染色體,染色體基因長度為50,意思是你要進行10000次的測試,所以也有可能一條染色體會大於一個基因做突變。

    至於你的方法我覺得很奇怪,通常是 100 個母代抽 100 個到交配池,再產生 100 個子代,生成的 100 個子代到下一迭代就又變成了母代 (子代逐一複製到母代,程式可用 memcpy 進行複製速度較快),到這裡,上一迭代的那 100 個母代就全部都被子代取代掉,不會留下來。

    基因演算法事實上重的是觀念,實做上你也知道有很多細節可以修改,這部份也沒有強制規定過,只要出來的效果好就可以(效果沒跑過程式,用想的是絕對不可能知道效果到底好不好)。

    最後再說的是精英政策,假設母代是 100 個,而我額外再設精英 10 個,這 10 個精英是 "額外" 的,也就是不參與那些選擇、交配、突變等問題,而是把 ga 從一開始到現在,每次最好解答的 10 個都丟到精英群裡面,這精英群裡面的解答是不可以重複的!(ex: y=x^2,精英群可以是 2, -2,對應到的都是 4,但精英群裡面不可以是 2, 2,因為解答有重複了)。如果產生的解答都沒有比精英群還好,那就可以不用複製到精英群。接著可以每100、200 個代數,把母體裡面較差的 10 個染色體,全都淘汰換成精英群裡面的精英。類似的方法很多,你可以再去找找其它資料。

    另先確定你的問題,100個母代確定生成200個子代?那第三代是不是就變400個子代?這樣沒過幾代你的電腦就會因為記憶體不足跑到當機了唷。

    Edison replied in 2011/01/28 22:02

  • cooler
  • 呃我可能對這演算法有點誤解了
    我是想說族群的數量應是會越來越大的(按照常理)@@
    然後終止條件可能是因為族群數量已達飽和所以演算法會停止

    看過你的crossover說明後我比較知道怎麼寫了..
    原來是沒有交配的母代直接丟入下一代..嗯..


    還有你寫的突變跟我的也不一樣,
    你的方法好像是bit-wise mutation(看書上寫的)

    我寫的程式是single-point mutation,如果低於mutation rate的話,
    在隨機產生一個mutationsite(染色體如果長度50,則1<=mutationsite<=50)
    那個site如果是1就變0,如果是0就變1,
    對我而言程式比較簡單寫…^^

    至於精英政策提到的較差的10個染色體,一定是最差的十個嗎?
    這方法倒是沒看過..

    謝謝板主熱心回覆!!你的回覆對我幫助很大!!
  • 可以確定的是目前我看過介紹 GA 的書(>5),族群數量並不會隨迭代次數愈來愈多,一直都是維持一開始你設的母體數量,所以才請教您是不是您的研究有特殊的應用才讓族群成倍數成長。即使是成倍數成長,我想到一定的數量也要有淘汰的動作,一般 PC 的 memory 會不夠存那麼大的資訊,同時這也不符合 GA 的精神,它沒有"不適者淘汰" 的成份在裡面;再加上,若以倍數成本,相對的計算時間也是成倍數成長,這是件很可怕的事(GA 本身就是件非常耗時的工作,可以想辦法在不影響找最佳解之情況下,細節上進行速度上的優化是件重要的事,如排序的動作等)。

    不是很確定我的突變機制名稱為何,可能我曾閱過書籍沒特別提到,只有提到我說的方式。接著討論您的問題,如果問題改成 f(x) = x^2, 0<=x<=15,假設在進行演化時,出現了所謂的超級染色體(超級染色體泛指你的100個母體中,有一半以上,甚至幾乎全部都是同一條染色體),超級染色體編碼若為 1110,這樣對應起來是 14,若依您的突變機制,突變率本身就很小,假設為 1%,100個母體平均有1個母體發生突變,接著突變的位置還要保祐剛好是在那個 0 ,才可以再順利再到最優解;這部份你是可以去 try,畢竟我覺得您說的方法"直覺"上對於尋優助益並不大。

    至於精英政策的十個染色體是要取代哪十個染色體,你也可以再多做測試研究看效果如何(還是如我所說,GA 只是重觀念,實際部份效果如何有太多的細節可做變化),只是在母體中挑十個最差的出來取代原因是,怕目前母體所演化出較好的解也被那十個精英洗掉,怕的是重新的演化。所以本身在實做的時候是挑 10 個最差的表現讓精英去取代。

    也有試過其它方法避免陷入區域解,就是設一個 ITER_LOOP ,假設是500,每500代的演化後,我會將一半 (還是 1/3、2/3,可以自己調) 的染色體再洗掉,重新 rand 出另一半新的染色體,這麼做的目的也是期望避開陷入區域解。

    GA 是個很好玩的演算法,但相對的用演化式的演算法來解決問題時,那些參數的設定顯得重要,目前有不少論文期刊在研究母體數量、突變率、交配率... etc 這些在什麼特定的情況下,設多少會得到較好的結果(當然這些是比較屬於數理推論的部份,這裡不深入探討)。可以確定的是,不論是理論還是解實際問題,事實上參數通常不會跑一組,會多跑幾組去看結果,因為我們要的只是那個最好的解答,其它的都是假的。

    Edison replied in 2011/01/30 13:14

  • xman
  • 板主你好:
    想請問假如我想把x值設為0~20,要怎麼修改程式碼呢?
    抱歉小弟素質比較低,希望你可以解答.
  • #define GENETIC_LENGTH 5
    由 4 改成 5
    可從 0 找到 31

    Edison replied in 2011/03/09 17:52

  • xman
  • 感謝版主的回覆,抱歉我剛才敘述可能讓你誤會了
    我想問的是x的範圍只能0~20 ,至於21~31則不在範圍內
    希望你可以解答. (已看過變數說明那邊)
  • 這裡設定上沒辦法完全符合你的要求,可以確定的是至少長度要5才能繼續算,有二種解決方式
    (1) 一樣設 5 bits, 只要發現算出來之 x>20, 調整它, 調整方式也有二種,一種是重新隨機產生一新解,一種是直接把它設成 20

    (2) 用數值對應法
    假設給 5 bits, 基因解碼出之數值為 x, 故x=0~31 ;
    實際上是要 y=0~20
    於是解出之 x 可對應到 y :
    (x - x_min) / (x_max-x_min )= ( y-y_min ) / ( y_max-y_min )

    (x-0)/31 = (y-0) / 20

    可見 15F 之回答,你們的問題是一樣的。

    Edison replied in 2011/03/09 18:15

  • 波德萊爾
  • 版主,您好:
    感謝版主的分享,不過我自己在dev c++上編譯時顯示了一些錯誤,想請教版主><,如下
    在GA.c中
    #include "GA.h" ---> In file included from GA.c
    main function中出現---->syntax error before "srand"
    最後顯示了
    ---> C:\Dev-Cpp\Examples\GA\Makefile.win [Build Error] [GA.o] Error 1
    在GA.h中
    在initialize()中的
    cal_xvalue(population[i]);
    ---> incompatible type for argument 1 of `cal_xvalue'
    cal_fitness(population[i]);
    ---> incompatible type for argument 1 of `cal_fitness'

    很抱歉,好像問題很多ˊ ˋ".....謝謝版主的不吝指教>"""<~~感謝!!!!
  • >> 在GA.c中
    你從哪看來我有 GA.c 了?估你是分號忘了打,不是的話請別人幫你看

    >> cal_xvalue(population[i]);
    發問前先看清楚原文, &population[i]

    Edison replied in 2011/03/16 08:03

  • Private Comment
  • Private Comment
  • Andy
  • 是不是應該在
    main()之中
    在reproduction();
    crossover();
    mutation();
    後重新計算population的fitness?
  • 皆可,或許做了比較好。這是最陽春版的,通常會再加一些東西進去期望效果會變較好。

    Edison replied in 2011/03/29 23:33

  • 大堯
  • 請問我程式都打完 可是compiler時候出現 Nothing to be done
    這樣有可能是哪個環節錯誤嗎?

    謝謝
  • 先去學怎麼用你的 compiler、debugger 比較實際

    Edison replied in 2011/05/08 18:46

  • Private Comment
  • Private Comment
  • Private Comment
  • 求知者
  • 請問版大
    能否與你討論關於GA應用在單機排程的相關問題呢
    因為小弟有找到使用MATLAB相關的程式碼
    可是要解釋時
    卻不知該從何解釋起
    能否請教版大呢
    謝謝...
  • matlab 部份我完全不熟,另請專業為佳。

    Edison replied in 2011/07/22 23:54

  • 熊掌
  • 版主你好,這裡想請教一下,關於母群數量、
    交配、突變率的設計,是否有什麼資料可以介
    紹?我的架構裡解空間過於龐大,估計有10^30
    以上個解,目前模擬做了幾周,還是找不出較適
    合的參數配置。
  • 我很久沒做這裡了,可能用學術去 Science Direct 找一下。10^30 解空間應該還好,之前我解空間更大,不過我有做一點運算上的加速就是。另解空間大時,我較建議加入精英法則可能會好一點。

    Edison replied in 2011/10/07 13:39

  • 熊掌
  • 感謝指點,我會再朝這方向做些研究
  • MM
  • 請問X->是什麼意思?
    不知道要如何查這個指令><

    在計算適應值函數時
    為何沒有宣告i就可以使用呢?是因為主程式就有宣告了嗎??

    謝謝^^
  • (1) -> :C 語言去翻結構體那章,在講結構體指標時會提到。
    (2)
    void cal_fitness(parent_t *x)
    {
    double i = x->dec_value;
    x->fitness =i*i;
    }

    我 i 有給了。

    Edison replied in 2011/11/10 00:56

  • 您的暱稱 ...
  • 瞭解了:)
    所以x->dec_value=double(dec)等於
    struct dec_value{
    double x=dec};
    是嗎是嗎??
  • 你回去再翻 C 語言的書吧,整個很不熟。

    一開始就定義這個東西了:
    typedef struct{
    int genes[GENETIC_LENGTH];
    double fitness;
    double dec_value;
    int copy_cnt;
    }parent_t;

    再仔細看一下副函式裡面所有有用到的資料型態是什麼

    void cal_fitness(parent_t *x)
    {
    double i = x->dec_value;
    x->fitness =i*i;
    }

    Edison replied in 2011/11/11 01:14

  • Mi
  • // 計算每個母體應複製幾個到交配池中
    for(i=0; i<POPULATION_CNT; i++)
    population[i].copy_cnt =\
    (int)(population[i].fitness * (double)POPULATION_CNT/ fitness_sum);
    這邊我不懂
    輪盤式是將所有母體的適應值加總化成圓盤,根據適應值大小不同占據面積大小不同,隨機選取,適應值高的被選中機會也高,將選中的丟入交配池中,進行交配
    那為何是應複製幾個@@?
  • 輪盤法本身就有二種,這二種在文獻上都有出現、被實際應用過,妙的這二種說法,都有書提,但沒書二個都提。
    你可再翻翻其他文獻或書籍,我翻過的大多是介紹我 coding 的方式。

    Edison replied in 2011/11/18 20:34

  • Mi
  • 可否提供一篇paper有關你撰寫的輪盤法?
  • 這... 我想您注意到這篇文章發佈的日期了吧 ? 文獻部份我並沒留存下來,實感抱歉。

    Edison replied in 2011/11/24 05:58

  • Mi
  • 可通常使用這樣的輪盤法
    為確保次置配池中的染色體數量與母體數量一致
    會有個零選擇的挑選補充不足的母體數量

    程式部分//計算每個母體應該複製幾個~如何確認總共有10個複製呢?
  • 疑,是我這版程式裡面沒考慮到這個嗎?用 counter 計數。
    在 loop 裡,只要 counter 達到 10 的時候,即使還有沒複制完的也強制跳出;而 loop 結束後若 counter 還沒達到 10,做法我所知又有二、三種,一種是剩下的直接從母體裡隨機抽取補足 (我採這個);另一種是全都補最佳染色體;另一種是補fitness較佳之相異染色體,再沒補完才又再用隨機抽取補。

    原始碼已有做更動修改,可參考 reproduction_rnd() 與 reproduction(),相關敘述在 「前言(2)」裡有提出,希望能解決您的疑惑。 :)

    Edison replied in 2011/11/30 02:39

  • 龍
  • 請問大哥是讀哪的? 科系? 會用到全域最適化東西.
    佩服你能寫成C++
  • 某國立大學企業管理學系。強調一下,是老師方向指導的好,所以才懂一些皮毛。

    Edison replied in 2011/12/20 22:57

  • hi5
  • 請問static int first_call;
    first_call從頭到尾只出現一次,就是宣告時
    請問這有什麼特別意義嗎?
  • 看了一下,應是進行其他測試的時候用到的,
    這份 code 可直接拿掉沒關係。

    Edison replied in 2012/01/14 06:53

本文章不能留言