本文即將關閉，後續欲討論請至另一篇 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;
}
留言列表
C/C++ 程式設計 (8)
