遺傳算法（GA）的C語言實現 · 計算機數學模型

## 問題：在下面的程序中將要運用遺傳算法對一個多項式求最小值要求在(-8,8)間尋找使表達式達到最小的x，誤差為0.001 ## 問題分析：編碼：采用常規碼，即二進制碼編碼。構造簡單，交叉、變異的實現非常容易，同時解的表達也很簡潔、直觀。可以每0.001取一個點，這樣理論誤差講小于0.0005，可以滿足題目中的誤差要求。此事總的求解空間為： N = (8 - (-8)) * 1000 = 160000 可以用n = 14位二進制來表示。群體規模m：群體規模m可以選擇 n ~ 2n 的一個確定的數，這里選擇 m = 20 初始種群的選取：在這里初始種群將在值域范圍內隨機選取終止規則： ①最優解在連續的20次循環中改變量小于0.01，此事認為這個最優解為滿足題目要求的最優解，求解成功，退出程序 ②總的循環次數大于1200次時，循環也將結束，這種情況按照求解失敗處理交叉規則：采用最常用的雙親雙子法選擇：在進行交叉、變異后，種群中的個體個數達到2m個，將這2m個染色體按其適應度進行排序，保留最優的m個淘汰其他的，使種群在整體上得到進化 ~~~ #include <stdio.h> #include <math.h> #include <stdlib.h> #include <time.h> #define SUM 20 //總共的染色體數量 #define MAXloop 1200 //最大循環次數 #define error 0.01 //若兩次最優值之差小于此數則認為結果沒有改變 #define crossp 0.7 //交叉概率 #define mp 0.04 //變異概率 //用于求解函數y=x^6-10x^5-26x^4+344x^3+193x^2-1846x-1680在（-8，8）之間的最小值 struct gen //定義染色體結構 { int info; //染色體結構，用一整型數的后14位作為染色體編碼 float suitability; //次染色體所對應的適應度函數值，在本題中為表達式的值 }; struct gen gen_group[SUM];//定義一個含有20個染色體的組 struct gen gen_new[SUM]; struct gen gen_result; //記錄最優的染色體 int result_unchange_time; //記錄在error前提下最優值為改變的循環次數 struct log //形成鏈表，記錄每次循環所產生的最優的適應度 { float suitability; struct log *next; }llog,*head,*end; int log_num; //鏈表長度 /**************函數聲明******************/ void initiate(); //初始化函數，主要負責產生初始化種群 void evaluation(int flag); //評估種群中各染色體的適應度，并據此進行排序 void cross(); //交叉函數 void selection(); //選擇函數 int record(); //記錄每次循環產生的最優解并判斷是否終止循環 void mutation(); //變異函數 void showresult(int); //顯示結果 //-----------------------以上函數由主函數直接調用 int randsign(float p); //按照概率p產生隨機數0、1，其值為1的概率為p int randbit(int i,int j); //產生一個在i，j兩個數之間的隨機整數 int randnum(); //隨機產生一個由14個基因組成的染色體 int convertionD2B(float x);//對現實解空間的可能解x進行二進制編碼（染色體形式） float convertionB2D(int x); //將二進制編碼x轉化為現實解空間的值 int createmask(int a); //用于交叉操作 void main() { int i,flag; flag=0; initiate(); //產生初始化種群 evaluation( 0 ); //對初始化種群進行評估、排序 for( i = 0 ; i < MAXloop ; i++ ) { cross(); //進行交叉操作 evaluation( 1 ); //對子種群進行評估、排序 selection(); //對父子種群中選擇最優的NUM個作為新的父種群 if( record() == 1 ) //滿足終止規則1，則flag=1并停止循環 { flag = 1; break; } mutation(); //變異操作 } showresult( flag ); //按照flag顯示尋優結果 } void initiate() { int i , stime; long ltime; ltime=time(NULL); stime=(unsigned)ltime/2; srand(stime); for( i = 0 ; i < SUM ; i++ ) { gen_group[i].info = randnum(); //調用randnum()函數建立初始種群 } gen_result.suitability=1000; result_unchange_time=0; head=end=(struct log *)malloc(sizeof(llog));//初始化鏈表 if(head==NULL) { printf("\n內存不夠！\n"); exit(0); } end->next = NULL; log_num = 1; } void evaluation(int flag) { int i,j; struct gen *genp; int gentinfo; float gentsuitability; float x; if( flag == 0 ) // flag=0的時候對父種群進行操作 genp = gen_group; else genp = gen_new; for(i = 0 ; i < SUM ; i++)//計算各染色體對應的表達式值 { x = convertionB2D( genp[i].info ); genp[i].suitability = x*(x*(x*(x*(x*(x-10)-26)+344)+193)-1846)-1680; //提取公因式比原式更快 } for(i = 0 ; i < SUM - 1 ; i++)//按表達式的值進行排序， { for(j = i + 1 ; j < SUM ; j++) { if( genp[i].suitability > genp[j].suitability ) { gentinfo = genp[i].info; genp[i].info = genp[j].info; genp[j].info = gentinfo; gentsuitability = genp[i].suitability; genp[i].suitability = genp[j].suitability; genp[j].suitability = gentsuitability; } } } } void cross() { int i , j , k ; int mask1 , mask2; int a[SUM]; for(i = 0 ; i < SUM ; i++) a[i] = 0; k = 0; for(i = 0 ; i < SUM ; i++) { if( a[i] == 0) { for( ; ; )//隨機找到一組未進行過交叉的染色體與a[i]交叉 { j = randbit(i + 1 , SUM - 1); if( a[j] == 0) break; } if(randsign(crossp) == 1) //按照crossp的概率對選擇的染色體進行交叉操作 { mask1 = createmask(randbit(0 , 14)); //由ranbit選擇交叉位 mask2 = ~mask1; //形成一個類似 111000 000111之類的二進制碼編碼 gen_new[k].info = (gen_group[i].info) & mask1 + (gen_group[j].info) & mask2; gen_new[k+1].info=(gen_group[i].info) & mask2 + (gen_group[j].info) & mask1; k = k + 2; } else //不進行交叉 { gen_new[k].info=gen_group[i].info; gen_new[k+1].info=gen_group[j].info; k=k+2; } a[i] = a[j] = 1; } } } void selection() { int i , j , k; j = 0; i = SUM/2-1; if(gen_group[i].suitability < gen_new[i].suitability) { for(j = 1 ; j < SUM / 2 ; j++) { if(gen_group[i+j].suitability > gen_new[i-j].suitability) break; } } else if(gen_group[i].suitability>gen_new[i].suitability) { for(j=-1;j>-SUM/2;j--) { if(gen_group[i+j].suitability<=gen_new[i-j].suitability) break; } } for(k=j;k<SUM/2+1;k++) { gen_group[i+k].info = gen_new[i-k].info; gen_group[i+k].suitability = gen_new[i-k].suitability; } } int record() //記錄最優解和判斷是否滿足條件 { float x; struct log *r; r=(struct log *)malloc(sizeof(llog)); if(r==NULL) { printf("\n內存不夠！\n"); exit(0); } r->next = NULL; end->suitability = gen_group[0].suitability; end->next = r; end = r; log_num++; x = gen_result.suitability - gen_group[0].suitability; if(x < 0)x = -x; if(x < error) { result_unchange_time++; if(result_unchange_time >= 20)return 1; } else { gen_result.info = gen_group[0].info; gen_result.suitability = gen_group[0].suitability; result_unchange_time=0; } return 0; } void mutation() { int i , j , m; float x; float gmp; int gentinfo; float gentsuitability; gmp = 1 - pow(1 - mp , 11);//在基因變異概率為mp時整條染色體的變異概率 for(i = 0 ; i < SUM ; i++) { if(randsign(gmp) == 1) { j = randbit(0 , 14); m = 1 << j; gen_group[i].info = gen_group[i].info^m; x = convertionB2D(gen_group[i].info); gen_group[i].suitability = x*(x*(x*(x*(x*(x-10)-26)+344)+193)-1846)-1680; } } for(i = 0 ; i < SUM - 1 ; i++) { for(j = i + 1 ; j < SUM ; j++) { if(gen_group[i].suitability > gen_group[j].suitability) { gentinfo = gen_group[i].info; gen_group[i].info = gen_group[j].info; gen_group[j].info = gentinfo; gentsuitability = gen_group[i].suitability; gen_group[i].suitability = gen_group[j].suitability; gen_group[j].suitability = gentsuitability; } } } /* *為了提高執行速度，在進行變異操作的時候并沒有直接確定需要進行變異的位 *而是先以cmp概率確定將要發生變異的染色體，再從染色體中隨進選擇一個基因進行變異 *由于進行選擇和變異后父代種群的次序已被打亂，因此，在變異前后對種群進行一次排序 */ } void showresult(int flag)//顯示搜索結果并釋放內存 { int i , j; struct log *logprint,*logfree; FILE *logf; if(flag == 0) printf("已到最大搜索次數，搜索失敗！"); else { printf("當取值%f時表達式達到最小值為%f\n",convertionB2D(gen_result.info),gen_result.suitability); printf("收斂過程記錄于文件log.txt"); if((logf = fopen("log.txt" , "w+")) == NULL) { printf("Cannot create/open file"); exit(1); } logprint=head; for(i = 0 ; i < log_num ; i = i + 5)//對收斂過程進行顯示 { for(j = 0 ; (j < 5) & ((i + j) < log_num-1) ; j++) { fprintf(logf , "%20f" , logprint->suitability); logprint=logprint->next; } fprintf(logf,"\n\n"); } } for(i = 0 ; i< log_num ; i++)//釋放內存 { logfree=head; head=head->next; free(logfree); fclose(logf); } getchar(); } int randsign(float p)//按概率p返回1 { if(rand() > (p * 32768)) return 0; else return 1; } int randbit(int i, int j)//產生在i與j之間的一個隨機數 { int a , l; l = j - i + 1; a = i + rand() * l / 32768; return a; } int randnum() { int x; x = rand() / 2; return x; } float convertionB2D(int x) { float y; y = x; y = (y - 8192) / 1000; return y; } int convertionD2B(float x) { int g; g = (x * 1000) + 8192; return g; } int createmask(int a) { int mask; mask=(1 << (a + 1)) - 1; return mask; } ~~~ 本例中所實現的是最基本的遺傳算法，在實際應用中，往往要事先建立問題的數學模型，選擇適合的適應度函數，并且根據問題的特點確定求解空間及染色體形式。本例事先用mathmatica繪出函數的曲線圖，確認函數的最小值位于±8之間，然后在此區間內求解。交叉、變異、選擇的實現方法常常由選定的適應度函數以及染色體形式決定，可供選擇的方式有很多。讀者可以自行查閱資料