/******************************************************************/ 
/* 基于基本遺傳算法的函數(shù)最優(yōu)化 SGA.C */ 
/* A Function Optimizer using Simple Genetic Algorithm */ 
/* developed from the Pascal SGA code presented by David E.Goldberg */ 
//******************************************************************/ 
#include 
#include 
#include 
#include "graph.c" 
/* 全局變量 */ 
struct individual /* 個體*/ 
{ 
unsigned *chrom; /* 染色體 */ 
double fitness; /* 個體適應(yīng)度*/ 
double varible; /* 個體對應(yīng)的變量值*/ 
int xsite; /* 交叉位置 */ 
int parent[2]; /* 父個體 */ 
int *utility; /* 特定數(shù)據(jù)指針變量 */ 
}; 
struct bestever /* 最佳個體*/ 
{ 
unsigned *chrom; /* 最佳個體染色體*/ 
double fitness; /* 最佳個體適應(yīng)度 */ 
double varible; /* 最佳個體對應(yīng)的變量值 */ 
int generation; /* 最佳個體生成代 */ 
}; 
struct individual *oldpop; /* 當(dāng)前代種群 */ 
struct individual *newpop; /* 新一代種群 */ 
struct bestever bestfit; /* 最佳個體 */ 
double sumfitness; /* 種群中個體適應(yīng)度累計 */ 
double max; /* 種群中個體最大適應(yīng)度 */ 
double avg; /* 種群中個體平均適應(yīng)度 */ 
double min; /* 種群中個體最小適應(yīng)度 */ 
float pcross; /* 交叉概率 */ 
float pmutation; /* 變異概率 */ 
int popsize; /* 種群大小 */ 
int lchrom; /* 染色體長度*/ 
int chromsize; /* 存儲一染色體所需字節(jié)數(shù) */ 
int gen; /* 當(dāng)前世代數(shù) */ 
int maxgen; /* 最大世代數(shù) */ 
int run; /* 當(dāng)前運行次數(shù) */ 
int maxruns; /* 總運行次數(shù) */ 
int printstrings; /* 輸出染色體編碼的判斷，0 -- 不輸出, 1 -- 輸出 */ 
int nmutation; /* 當(dāng)前代變異發(fā)生次數(shù) */ 
int ncross; /* 當(dāng)前代交叉發(fā)生次數(shù) */ 

/* 隨機數(shù)發(fā)生器使用的靜態(tài)變量 */ 
static double oldrand[55]; 
static int jrand; 
static double rndx2; 
static int rndcalcflag; 
/* 輸出文件指針 */ 
FILE *outfp ; 
/* 函數(shù)定義 */ 
void advance_random(); 
int flip(float);rnd(int, int); 
void randomize(); 
double randomnormaldeviate(); 
float randomperc(),rndreal(float,float); 
void warmup_random(float); 
void initialize(),initdata(),initpop(); 
void initreport(),generation(),initmalloc(); 
void freeall(),nomemory(char *),report(); 
void writepop(),writechrom(unsigned *); 
void preselect(); 
void statistics(struct individual *); 
void title(),repchar (FILE *,char *,int); 
void skip(FILE *,int); 
int select(); 
void objfunc(struct individual *); 
int crossover (unsigned *, unsigned *, unsigned *, unsigned *); 
void mutation(unsigned *); 


void initialize() /* 遺傳算法初始化 */ 
{ 
/* 鍵盤輸入遺傳算法參數(shù) */ 
initdata(); 
/* 確定染色體的字節(jié)長度 */ 
chromsize = (lchrom/(8*sizeof(unsigned))); 
if(lchrom%(8*sizeof(unsigned))) chromsize++; 
/*分配給全局數(shù)據(jù)結(jié)構(gòu)空間 */ 
initmalloc(); 
/* 初始化隨機數(shù)發(fā)生器 */ 
randomize(); 
/* 初始化全局計數(shù)變量和一些數(shù)值*/ 
nmutation = 0; 
ncross = 0; 
bestfit.fitness = 0.0; 
bestfit.generation = 0; 
/* 初始化種群，并統(tǒng)計計算結(jié)果 */ 
initpop(); 
statistics(oldpop); 
initreport(); 
} 

void initdata() /* 遺傳算法參數(shù)輸入 */ 
{ 
char answer[2]; 
setcolor(9); 
disp_hz16("種群大小(20-100)：",100,150,20); 
gscanf(320,150,9,15,4,"%d", &popsize); 
if((popsize%2) != 0) 
{ 
fprintf(outfp, "種群大小已設(shè)置為偶數(shù)\n"); 
popsize++; 
}; 
setcolor(9); 
disp_hz16("染色體長度(8-40)：",100,180,20); 
gscanf(320,180,9,15,4,"%d", &lchrom); 
setcolor(9); 
disp_hz16("是否輸出染色體編碼(y/n)：",100,210,20); 
printstrings=1; 
gscanf(320,210,9,15,4,"%s", answer); 
if(strncmp(answer,"n",1) == 0) printstrings = 0; 
setcolor(9); 
disp_hz16("最大世代數(shù)(100-300)：",100,240,20); 
gscanf(320,240,9,15,4,"%d", &maxgen); 
setcolor(9); 
disp_hz16("交叉率(0.2-0.9)：",100,270,20); 
gscanf(320,270,9,15,5,"%f", &pcross); 
setcolor(9); 
disp_hz16("變異率(0.01-0.1)：",100,300,20); 
gscanf(320,300,9,15,5,"%f", &pmutation); 
} 

void initpop() /* 隨機初始化種群 */ 
{ 
int j, j1, k, stop; 
unsigned mask = 1; 
for(j = 0; j < popsize; j++) 
{ 
for(k = 0; k < chromsize; k++) 
{ 
oldpop[j].chrom[k] = 0; 
if(k == (chromsize-1)) 
stop = lchrom - (k*(8*sizeof(unsigned))); 
else 
stop =8*sizeof(unsigned); 
for(j1 = 1; j1 <= stop; j1++) 
{ 
oldpop[j].chrom[k] = oldpop[j].chrom[k]<<1; 
if(flip(0.5)) 
oldpop[j].chrom[k] = oldpop[j].chrom[k]|mask; 
} 
} 
oldpop[j].parent[0] = 0; /* 初始父個體信息 */ 
oldpop[j].parent[1] = 0; 
oldpop[j].xsite = 0; 
objfunc(&(oldpop[j])); /* 計算初始適應(yīng)度*/ 
} 
} 

void initreport() /* 初始參數(shù)輸出 */ 
{ 
void skip(); 
skip(outfp,1); 
fprintf(outfp," 基本遺傳算法參數(shù)\n"); 
fprintf(outfp," -------------------------------------------------\n"); 
fprintf(outfp," 種群大小(popsize) = %d\n",popsize); 
fprintf(outfp," 染色體長度(lchrom) = %d\n",lchrom); 
fprintf(outfp," 最大進化代數(shù)(maxgen) = %d\n",maxgen); 
fprintf(outfp," 交叉概率(pcross) = %f\n", pcross); 
fprintf(outfp," 變異概率(pmutation) = %f\n", pmutation); 
fprintf(outfp," -------------------------------------------------\n"); 
skip(outfp,1); 
fflush(outfp); 
} 

void generation() 
{ 
int mate1, mate2, jcross, j = 0; 
/* 每代運算前進行預(yù)選 */ 
preselect(); 
/* 選擇, 交叉, 變異 */ 
do 
{ 
/* 挑選交叉配對 */ 
mate1 = select(); 
mate2 = select(); 
/* 交叉和變異 */ 
jcross = crossover(oldpop[mate1].chrom, oldpop[mate2].chrom, newpop[j].chrom, newpop[j+1].chrom); 
mutation(newpop[j].chrom); 
mutation(newpop[j+1].chrom); 
/* 解碼, 計算適應(yīng)度 */ 
objfunc(&(newpop[j])); 
/*記錄親子關(guān)系和交叉位置 */ 
newpop[j].parent[0] = mate1+1; 
newpop[j].xsite = jcross; 
newpop[j].parent[1] = mate2+1; 
objfunc(&(newpop[j+1])); 
newpop[j+1].parent[0] = mate1+1; 
newpop[j+1].xsite = jcross; 
newpop[j+1].parent[1] = mate2+1; 
j = j + 2; 
} 
while(j < (popsize-1)); 

} 

void initmalloc() /*為全局數(shù)據(jù)變量分配空間 */ 
{ 
unsigned nbytes; 
char *malloc(); 
int j; 
/* 分配給當(dāng)前代和新一代種群內(nèi)存空間 */ 
nbytes = popsize*sizeof(struct individual); 
if((oldpop = (struct individual *) malloc(nbytes)) == NULL) 
nomemory("oldpop"); 
if((newpop = (struct individual *) malloc(nbytes)) == NULL) 
nomemory("newpop"); 
/* 分配給染色體內(nèi)存空間 */ 
nbytes = chromsize*sizeof(unsigned); 
for(j = 0; j < popsize; j++) 
{ 
if((oldpop[j].chrom = (unsigned *) malloc(nbytes)) == NULL) 
nomemory("oldpop chromosomes"); 
if((newpop[j].chrom = (unsigned *) malloc(nbytes)) == NULL) 
nomemory("newpop chromosomes"); 
} 
if((bestfit.chrom = (unsigned *) malloc(nbytes)) == NULL) 
nomemory("bestfit chromosome"); 

} 

void freeall() /* 釋放內(nèi)存空間 */ 
{ 
int i; 
for(i = 0; i < popsize; i++) 
{ 
free(oldpop[i].chrom); 
free(newpop[i].chrom); 
} 
free(oldpop); 
free(newpop); 
free(bestfit.chrom); 
} 

void nomemory(string) /* 內(nèi)存不足，退出*/ 
char *string; 
{ 
fprintf(outfp,"malloc: out of memory making %s!!\n",string); 
exit(-1); 
} 

void report() /* 輸出種群統(tǒng)計結(jié)果 */ 
{ 
void repchar(), skip(); 
void writepop(), writestats(); 
repchar(outfp,"-",80); 
skip(outfp,1); 
if(printstrings == 1) 
{ 
repchar(outfp," ",((80-17)/2)); 
fprintf(outfp,"模擬計算統(tǒng)計報告 \n"); 
fprintf(outfp, "世代數(shù) %3d", gen); 
repchar(outfp," ",(80-28)); 
fprintf(outfp, "世代數(shù) %3d\n", (gen+1)); 
fprintf(outfp,"個體 染色體編碼"); 
repchar(outfp," ",lchrom-5); 
fprintf(outfp,"適應(yīng)度 父個體 交叉位置 "); 
fprintf(outfp,"染色體編碼 "); 
repchar(outfp," ",lchrom-5); 
fprintf(outfp,"適應(yīng)度\n"); 
repchar(outfp,"-",80); 
skip(outfp,1); 
writepop(outfp); 
repchar(outfp,"-",80); 
skip(outfp,1); 
} 
fprintf(outfp,"第 %d 代統(tǒng)計: \n",gen); 
fprintf(outfp,"總交叉操作次數(shù) = %d, 總變異操作數(shù) = %d\n",ncross,nmutation); 
fprintf(outfp," 最小適應(yīng)度：%f 最大適應(yīng)度：%f 平均適應(yīng)度 %f\n", min,max,avg); 
fprintf(outfp," 迄今發(fā)現(xiàn)最佳個體 => 所在代數(shù)： %d ", bestfit.generation); 
fprintf(outfp," 適應(yīng)度：%f 染色體：", bestfit.fitness); 
writechrom((&bestfit)->chrom); 
fprintf(outfp," 對應(yīng)的變量值: %f", bestfit.varible); 
skip(outfp,1); 
repchar(outfp,"-",80); 
skip(outfp,1); 
} 

void writepop() 
{ 
struct individual *pind; 
int j; 
for(j=0; j { 
fprintf(outfp,"%3d) ",j+1); 
/* 當(dāng)前代個體 */ 
pind = &(oldpop[j]); 
writechrom(pind->chrom); 
fprintf(outfp," %8f | ", pind->fitness); 
/* 新一代個體 */ 
pind = &(newpop[j]); 
fprintf(outfp,"(%2d,%2d) %2d ", 
pind->parent[0], pind->parent[1], pind->xsite); 
writechrom(pind->chrom); 
fprintf(outfp," %8f\n", pind->fitness); 
} 
} 

void writechrom(chrom) /* 輸出染色體編碼 */ 
unsigned *chrom; 
{ 
int j, k, stop; 
unsigned mask = 1, tmp; 
for(k = 0; k < chromsize; k++) 
{ 
tmp = chrom[k]; 
if(k == (chromsize-1)) 
stop = lchrom - (k*(8*sizeof(unsigned))); 
else 
stop =8*sizeof(unsigned); 
for(j = 0; j < stop; j++) 
{ 
if(tmp&mask) 
fprintf(outfp,"1"); 
else 
fprintf(outfp,"0"); 
tmp = tmp>>1; 
} 
} 
} 

void preselect()