?? sga.c
字號:
/********************************************************************/
/* 基于基本遺傳算法的分層遺傳改進算法函數(shù)最優(yōu)化 SHGA.C */
/* A Function Optimizer using Simple Genetic Algorithm */
/* developed from the Pascal SGA code presented by David E.Goldberg */
/* 華南理工大學電子與信息學院 蘇勇 2004年4月*/
/********************************************************************/
#include <stdio.h>
#include <math.h>
/* 全局變量 */
struct individual /* 個體*/
{
unsigned *chrom; /* 染色體 */
double fitness; /* 個體適應度*/
double varible; /* 個體對應的變量值*/
int xsite; /* 低層交叉位置 */
int xsiteA; /* 高層交叉位置 */
int parent[2]; /* 父個體 */
int parentA[2]; /* 高層父個體(父代子群) */
int *utility; /* 特定數(shù)據(jù)指針變量 */
};
struct bestever /* 最佳個體*/
{
unsigned *chrom; /* 低層遺傳運算所得最佳個體染色體*/
unsigned *chromA; /* 全局最佳個體染色體 */
double fitness; /* 最佳個體適應度 */
double varible; /* 最佳個體對應的變量值 */
int generation; /* 最佳個體生成代 */
int subpopulation; /* 最佳個體所在子種群 */
};
struct individual **oldpop; /* 當前代種群 */
struct individual **newpop; /* 新一代種群 */
struct bestever bestfit; /* 最佳個體 */
double sumfitness; /* 種群中個體適應度累計 */
double sumA; /* 所有子群平均適應度累計 */
double max; /* 種群中個體最大適應度 */
double maxA; /* 全局最佳適應度值 */
double avg; /* 種群中個體平均適應度 */
double min; /* 種群中個體最小適應度 */
double minA; /* 全局最小適應度值 */
double *A; /* 子群平均適應度值數(shù)組 */
float pcross; /* 低層交叉概率 */
float pcrossA; /* 高層交叉概率 */
float pmutation; /* 低層變異概率 */
float pmutationA; /* 高層變異概率 */
int popsize; /* 種群大小 */
int lchrom; /* 染色體長度*/
int chromsize; /* 存儲一染色體所需字節(jié)數(shù) */
int gen; /* 當前世代數(shù) */
int maxgen; /* 最大世代數(shù) */
int run; /* 低層遺傳當前運行次數(shù) */
int runA; /* 高層遺傳當前運行次數(shù) */
int maxruns; /* 總運行次數(shù) */
int printstrings; /* 輸出染色體編碼的判斷，0 -- 不輸出, 1 -- 輸出 */
int nmutation; /* 低層當前代變異發(fā)生次數(shù) */
int nmutationA; /* 高層當前代變異發(fā)生次數(shù) */
int ncross; /* 低層當前代交叉發(fā)生次數(shù) */
int ncrossA; /* 高層當前代交叉發(fā)生次數(shù) */
int subpopnum; /* 子種群個數(shù) */
int subpop; /* 當前子種群 */
float randomseed; /* 隨機數(shù)種子 */
int shu; /* 當前子群 */
double varibleA; /* 全局最佳染色體對應變量值 */
int genA; /* 全局最佳染色體所在代數(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 reportA();
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 *);
/* 低層交叉變異函數(shù) */
int crossover (unsigned *, unsigned *, unsigned *, unsigned *);
void mutation(unsigned *);
/* 高層交叉變異函數(shù) */
void CMTransA();
int selectA();
void preselectA();
void initialize() /* 遺傳算法初始化 */
{
/* 鍵盤輸入遺傳算法參數(shù) */
initdata();
/* 確定染色體的字節(jié)長度 */
chromsize = (lchrom/(8*sizeof(unsigned)));
if(lchrom%(8*sizeof(unsigned))) chromsize++;
/*分配給全局數(shù)據(jù)結構空間 */
initmalloc();
initreport();
}
void initdata() /* 遺傳算法參數(shù)輸入 */
{
char answer[2];
popsize=30;
if((popsize%2) != 0)
{
fprintf(outfp, "種群大小已設置為偶數(shù)\n");
popsize++;
}
lchrom=22; /* 染色體長度定義為22 */
printstrings=1;
maxgen=100; /* 低層運算100代 */
pcross=0.8; /* 低層交叉概率0.8 */
pcrossA=0.2; /* 高層交叉概率0.6 */
pmutation=0.05; /* 低層變異概率0.05 */
pmutationA=0.05; /* 高層變異概率0.05 */
genA=maxgen;
}
void initpop() /* 隨機初始化種群 */
{
int j, j1, k, stop;
unsigned mask = 1;
for(j = 0; j < popsize; j++)
{
for(k = 0; k < chromsize; k++)
{
oldpop[subpop][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[subpop][j].chrom[k] = oldpop[subpop][j].chrom[k]<<1;
if(flip(randomseed))
oldpop[subpop][j].chrom[k] = oldpop[subpop][j].chrom[k]|mask;
}
}
oldpop[subpop][j].parent[0] = 0; /* 初始父個體信息 */
oldpop[subpop][j].parent[1] = 0;
oldpop[subpop][0].parentA[0]= 0;
oldpop[subpop][0].parentA[1]= 0;
oldpop[subpop][j].xsite = 0;
oldpop[subpop][0].xsiteA= 0;
objfunc(&(oldpop[subpop][j])); /* 計算初始適應度*/
}
if(subpop==0)
{
maxA = oldpop[0][0].fitness;
minA = oldpop[0][0].fitness;
}
}
void initreport() /* 初始參數(shù)輸出 */
{
void skip();
skip(outfp,1);
fprintf(outfp," 基本遺傳算法參數(shù)\n");
fprintf(outfp," -------------------------------------------------\n");
fprintf(outfp," 子種群數(shù)(subpopnum) = %d\n",subpopnum);
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;
/* 每代運算前進行預選 */
preselect();
/* 選擇, 交叉, 變異 */
do
{
/* 挑選交叉配對 */
mate1 = select();
mate2 = select();
/* 交叉和變異 */
jcross = crossover(oldpop[subpop][mate1].chrom, oldpop[subpop][mate2].chrom, newpop[subpop][j].chrom, newpop[subpop][j+1].chrom);
mutation(newpop[subpop][j].chrom);
mutation(newpop[subpop][j+1].chrom);
/* 解碼, 計算適應度 */
objfunc(&(newpop[subpop][j]));
/*記錄親子關系和交叉位置 */
newpop[subpop][j].parent[0] = mate1+1;
newpop[subpop][j].xsite = jcross;
newpop[subpop][j].parent[1] = mate2+1;
objfunc(&(newpop[subpop][j+1]));
newpop[subpop][j+1].parent[0] = mate1+1;
newpop[subpop][j+1].xsite = jcross;
newpop[subpop][j+1].parent[1] = mate2+1;
j = j + 2;
}
while(j < (popsize-1));
}
void CMTransA() /* 高層交叉變異 */
{
int mateA1, mateA2, jcrossA = 0, k, h, m, j1, j=0;
unsigned mask = 1;
int stop;
preselectA();
do
{
/*//////////// 高層交叉 ///////////////*/
mateA1 = selectA();
mateA2 = selectA();
if(flip(pcrossA))
{
jcrossA = (int)rnd(1 ,(popsize - 1));
ncrossA++;
for(m = jcrossA; m < popsize; m++)
{
for(k=0;k< chromsize; k++)
{
oldpop[mateA1][m].chrom[k] = newpop[j+1][m].chrom[k];
oldpop[mateA2][m].chrom[k] = newpop[j][m].chrom[k];
}
}
{
for(k=0;k< chromsize; k++)
{
oldpop[mateA1][m].chrom[k] = newpop[j][m].chrom[k];
oldpop[mateA2][m].chrom[k] = newpop[j+1][m].chrom[k];
}
}
}
else
{
for(m = 0; m< popsize; m++)
{
for(k=0;k<chromsize;k++)
{
oldpop[mateA1][m].chrom[k] = newpop[j][m].chrom[k];
oldpop[mateA2][m].chrom[k] = newpop[j+1][m].chrom[k];
}
}
jcrossA=0;
}
/*//////////// 高層變異 ////////////////*/
if(flip(pmutationA))
{
nmutationA++;
for(h = 0; h < chromsize; h++)
{
newpop[j][m].chrom[h] = 0;
if(h == (chromsize-1))
stop = lchrom - (h*(8*sizeof(unsigned)));
else
stop =8*sizeof(unsigned);
for(j1 = 1; j1 <= stop; j1++)
{
newpop[j][m].chrom[h] = newpop[j][m].chrom[h]<<1;
if(flip(0.5))
newpop[j][m].chrom[h] = newpop[j][m].chrom[h]|mask;
}
}
}
if(flip(pmutation))
{
nmutationA++;
for(h = 0; h < chromsize; h++)
{
newpop[j+1][m].chrom[h] = 0;
if(h == (chromsize-1))
stop = lchrom - (h*(8*sizeof(unsigned)));
else
stop =8*sizeof(unsigned);
for(j1 = 1; j1 <= stop; j1++)
{
newpop[j+1][m].chrom[h] = newpop[j+1][m].chrom[h]<<1;
if(flip(0.5))
newpop[j+1][m].chrom[h] = newpop[j+1][m].chrom[h]|mask;
}
}
}
/* 解碼, 計算適應度 */
for(k = 0; k < popsize; k++)
objfunc(&(newpop[j][k]));
for(k = 0; k < popsize; k++)
objfunc(&(newpop[j+1][k]));
newpop[j+1][0].parentA[0] = mateA1+1;
newpop[j+1][0].xsiteA = jcrossA;
newpop[j+1][0].parentA[1] = mateA2+1;
j = j + 2;
}
while(j<(subpopnum-1));
}
void initmalloc() /*為全局數(shù)據(jù)變量分配空間 */
{
unsigned nbytes;
char *malloc();
int i,j;
/* 分配給當前代和新一代種群內存空間 */
if((A = (double *) malloc(subpopnum*sizeof(double))) == NULL)
nomemory("A");
nbytes = popsize*sizeof(struct individual);
if((oldpop = (struct individual **) malloc(subpopnum*4)) == NULL)
nomemory("oldpop");
for(j=0; j<subpopnum;j++)
{
if((oldpop[j] = (struct individual *) malloc(nbytes)) == NULL)
nomemory("oldpop[j]");
}
if((newpop = (struct individual **) malloc(subpopnum*4)) == NULL)
nomemory("newpop");
for(j=0; j<subpopnum;j++)
{
if((newpop[j] = (struct individual *) malloc(nbytes)) == NULL)
nomemory("newpop[j]");
}
/* 分配給染色體內存空間 */
nbytes = chromsize*sizeof(unsigned);
for(j = 0; j < popsize; j++)
{
for(i=0;i<subpopnum;i++)
{
if((oldpop[i][j].chrom = (unsigned *) malloc(nbytes)) == NULL)
nomemory("oldpop[i] chromosomes");
if((newpop[i][j].chrom = (unsigned *) malloc(nbytes)) == NULL)
nomemory("newpop[i] chromosomes");
}
}
if((bestfit.chrom = (unsigned *) malloc(nbytes)) == NULL)
nomemory("bestfit chromosome");
if((bestfit.chromA = (unsigned *) malloc(nbytes)) == NULL)
nomemory("bestfit chromosomeA");
}
void freeall() /* 釋放內存空間 */
{
int i,j;
for(i = 0; i < popsize; i++)
{
for(j=0;j<subpopnum;j++)
{
free(oldpop[j][i].chrom);
free(newpop[j][i].chrom);
}
}
free(A);
for(j=0;j<subpopnum;j++)
free(oldpop[j]);
free(oldpop);
for(j=0;j<subpopnum;j++)
free(newpop[j]);
free(newpop);
free(bestfit.chrom);
free(bestfit.chromA);
}
void nomemory(string) /* 內存不足，退出*/
char *string;
{
fprintf(outfp,"malloc: out of memory making %s!!\n",string);
exit(-1);
}
void reportA()
{
void skip();
int i,j,s;
fprintf(outfp,"第1次高層交叉變異統(tǒng)計報告\n");
repchar(outfp,"-",80);
skip(outfp,1);
for(s=0;s<subpopnum-1;s+=2)
{
fprintf(outfp, " 第%d子種群 ", s+1);
repchar(outfp, " ",lchrom-10);
fprintf(outfp, " 適應度值 ");
repchar(outfp, " ",2);
fprintf(outfp, " 第%d子種群 ", s+2);
repchar(outfp, " ",lchrom-6);
fprintf(outfp, " 適應度值 ");
fprintf(outfp, " 父代子群:");
fprintf(outfp, "(%2d,%2d)", newpop[s+1][0].parentA[0],newpop[s+1][0].parentA[1]);
skip(outfp,1);
for(i=0;i<popsize-1;i++)
{
fprintf(outfp, "%2d) ",i+1);
writechrom((&newpop[s][i])->chrom);
repchar(outfp, " ",2);
fprintf(outfp, " %f " ,newpop[s][i].fitness);
repchar(outfp, " ",5);
fprintf(outfp, "%2d) ",i+1);
writechrom((&newpop[s][i+1])->chrom);
repchar(outfp, " ",2);
fprintf(outfp, " %f " ,newpop[s][i+1].fitness);
skip(outfp,1);
}
repchar(outfp,"-",80);
skip(outfp,1);
fprintf(outfp, "高層交叉次數(shù): %d , 高層變異次數(shù): %d ",ncrossA,nmutationA);
skip(outfp,1);
}
fprintf(outfp," 迄今發(fā)現(xiàn)最佳個體 => 所在分層: %d 所在子群: %d 所在代數(shù): %d ", runA,bestfit.subpopulation , genA);
fprintf(outfp," 適應度：%f 染色體: ", maxA);
writechrom((&bestfit)->chromA);
fprintf(outfp," 對應的變量值: %f", varibleA);
skip(outfp,1);
fprintf(outfp," 迄今發(fā)現(xiàn)最小適應度 => %f ",minA);
skip(outfp,1);
repchar(outfp,"-",80);
skip(outfp,1);
}
void report() /* 輸出種群統(tǒng)計結果 */
{
void repchar(), skip();
void writepop(), writestats();
repchar(outfp,"-",80);
skip(outfp,1);
if(printstrings == 1)
{
repchar(outfp," ",((80-17)/2));
fprintf(outfp,"第%d子種群模擬計算統(tǒng)計報告 \n",(subpop+1));
fprintf(outfp, "世代數(shù) %3d", gen);
repchar(outfp," ",(80-28));
fprintf(outfp, "世代數(shù) %3d\n", (gen+1));
fprintf(outfp,"個體 染色體編碼");
repchar(outfp," ",lchrom-5);
fprintf(outfp,"適應度 父個體 交叉位置 ");
fprintf(outfp,"染色體編碼 ");
repchar(outfp," ",lchrom-5);
fprintf(outfp,"適應度\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);
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -