第1页 / 共10页
第2页 / 共10页
第3页 / 共10页
第4页 / 共10页
第5页 / 共10页
第6页 / 共10页
第7页 / 共10页
第8页 / 共10页
基于遗传算法的函数最优化程序.doc
/************************************/
*/
/*基于遗传算法的函数最优化 SGA.C
/*同济大学 王小平
*/
/************************************/
#include "stdio.h"
#include "math.h"
#include "stdlib.h"
#include "string.h"
/*全局变量 */
struct individual
{
unsigned *chrom;
fitness;
double
varible;
double
xsite;
int
int
parent[2];
*utility;
int
};
struct bestever
{
unsigned *chrom;
fitness;
double
varible;
double
int
generation;
};
struct individual *oldpop;
struct individual *newpop;
struct bestever bestfit;
double sumfitness;
double max;
double avg;
double min;
float
float
int
int
int
int
int
int
int
pcross;
pmutation;
popsize;
lchrom;
chromsize;
gen;
maxgen;
run;
maxruns;
/* 个体*/
/* 染色体 */
/* 个体适应度*/
/* 个体对应的变量值*/
/* 交叉位置 */
/* 父个体 */
/* 特定数据指针变量 */
/* 最佳个体*/
/* 最佳个体染色体*/
/* 最佳个体适应度 */
/* 最佳个体对应的变量值 */
/* 最佳个体生成代 */
/* 当前代种群 */
/* 新一代种群 */
/* 最佳个体 */
/* 种群中个体适应度累计 */
/* 种群中个体最大适应度 */
/* 种群中个体平均适应度 */
/* 种群中个体最小适应度 */
/* 交叉概率 */
/* 变异概率 */
/* 种群大小 */
/* 染色体长度*/
/* 存储一染色体所需字节数 */
/* 当前世代数 */
/* 最大世代数 */
/* 当前运行次数 */
/* 总运行次数 */
/* 输出染色体编码的判断，0 -- 不输出, 1 -- 输出 */
/* 当前代变异发生次数 */
/* 当前代交叉发生次数 */
printstrings;
nmutation;
ncross;
int
int
int
/* 随机数发生器使用的静态变量 */
static double oldrand[55];
static int jrand;
static double rndx2;
static int rndcalcflag;
/* 输出文件指针 */
FILE *outfp ;
/* 函数定义 */
void advance_random();
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();
flip(float);rnd(int, int);
select();
void statistics(struct individual *);
void title(),repchar(FILE *,char *,int);
void skip(FILE *,int);
int
void objfunc(struct individual *);
int
void mutation(unsigned *);
void skip();
crossover (unsigned *, unsigned *, unsigned *, unsigned *);
void initialize()
{
/* 遗传算法初始化 */
/* 键盘输入遗传算法参数 */
initdata();
/* 确定染色体的字节长度 */
chromsize = (lchrom/(8*sizeof(unsigned)));
if(lchrom%(8*sizeof(unsigned))) chromsize++;
/*分配给全局数据结构空间 */
initmalloc();
/* 初始化随机数发生器 */
randomize();
/* 初始化全局计数变量和一些数值*/
nmutation = 0;
ncross = 0;
bestfit.fitness = 0.0;
bestfit.generation = 0;
/* 初始化种群，并统计计算结果 */
initpop();
statistics(oldpop);
initreport();
/* 遗传算法参数输入 */
}
void initdata()
{
answer[2];
char
printf("\n 种群大小(20-100)：");
scanf("%d", &popsize);
getchar();
if((popsize%2) != 0)
{
printf("种群大小已设置为偶数\n");
popsize++;
};
printf("染色体长度(8-40)：");
scanf("%d", &lchrom);
printf("是否输出染色体编码(y/n)：") ;
printstrings=1;
scanf("%s", answer);
if(strcmp(answer,"n") == 0) printstrings = 0;
printf("最大世代数(100-300)：");
scanf("%d", &maxgen);
printf("交叉率(0.2-0.9)：");
scanf("%f", &pcross);
printf("变异率(0.01-0.1)：");
scanf("%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]));
}
}
void initreport()
{
/* 初始父个体信息 */
/* 计算初始适应度*/
/* 初始参数输出 */
基本遗传算法参数\n");
skip(outfp,1);
fprintf(outfp,"
fprintf(outfp," -------------------------------------------------\n");
fprintf(outfp,"
fprintf(outfp,"
fprintf(outfp,"
fprintf(outfp,"
fprintf(outfp,"
fprintf(outfp," -------------------------------------------------\n");
skip(outfp,1);
fflush(outfp);
种群大小(popsize)
染色体长度(lchrom)
最大进化代数(maxgen)
交叉概率(pcross)
变异概率(pmutation)
= %d\n",popsize);
= %d\n",lchrom);
= %d\n",maxgen);
= %f\n", pcross);
= %f\n", pmutation);
}
void generation()
{
int mate1, mate2, jcross, j = 0;
/* 每代运算前进行预选 */
preselect();
/* 选择, 交叉, 变异 */
do
{
/* 挑选交叉配对 */
mate1 = select();
mate2 = select();
/* 交叉和变异 */
jcross
=
newpop[j+1].chrom);
mutation(newpop[j].chrom);
mutation(newpop[j+1].chrom);
/* 解码, 计算适应度 */
objfunc(&(newpop[j]));
/*记录亲子关系和交叉位置 */
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;
}
crossover(oldpop[mate1].chrom,
oldpop[mate2].chrom,
newpop[j].chrom,
while(j < (popsize-1));
}
void initmalloc()
{
/*为全局数据变量分配空间 */
unsigned nbytes;
int j;
/* 分配给当前代和新一代种群内存空间 */
nbytes = popsize*sizeof(struct individual);
if((oldpop = (struct individual *) malloc(nbytes)) == NULL)
nomemory("oldpop");
if((newpop = (struct individual *) malloc(nbytes)) == NULL)
nomemory("newpop");
/* 分配给染色体内存空间 */
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()
{
/* 释放内存空间 */
void nomemory(char *str)
{
/* 内存不足，退出*/
fprintf(outfp,"malloc: out of memory making %s!!\n",str);
exit(-1);
void report()
{
/* 输出种群统计结果 */
repchar(FILE *,char *,int);
skip(FILE *,int);
void
void
void writestats();
repchar(outfp,"-",80);
skip(outfp,1);
if(printstrings == 1)
{
repchar(outfp," ",((80-17)/2));
fprintf(outfp,"模拟计算统计报告 \n");
fprintf(outfp, "世代数 %3d", gen);
repchar(outfp," ",(80-28));
fprintf(outfp, "世代数 %3d\n", (gen+1));
fprintf(outfp,"个体 染色体编码");
repchar(outfp," ",lchrom-8);
fprintf(outfp,"适应度
fprintf(outfp,"染色体编码 ");
repchar(outfp," ",lchrom-10);
fprintf(outfp,"适应度\n");
父个体 交叉位置 ");
int i;
for(i = 0; i < popsize; i++)
{
free(oldpop[i].chrom);
free(newpop[i].chrom);
}
free(oldpop);
free(newpop);
free(bestfit.chrom);
}
}
}
repchar(outfp,"-",88);
skip(outfp,1);
writepop();
repchar(outfp,"-",88);
skip(outfp,1);
}
fprintf(outfp,"第 %d 代统计: \n",gen);
fprintf(outfp,"总交叉操作次数 = %d, 总变异操作数 = %d\n",ncross,nmutation);
fprintf(outfp," 最小适应度：%f 最大适应度：%f 平均适应度 %f\n", min,max,avg);
fprintf(outfp," 迄今发现最佳个体 => 所在代数： %d
fprintf(outfp," 适应度：%f 染色体：", bestfit.fitness);
writechrom((&bestfit)->chrom);
fprintf(outfp," 对应的变量值: %f", bestfit.varible);
skip(outfp,1);
repchar(outfp,"-",80);
skip(outfp,1);
", bestfit.generation);
}
", pind->parent[0], pind->parent[1], pind->xsite);
/* 输出染色体编码 */
/* 输出染色体编码 */
void writepop()
{
struct individual *pind;
int j;
for(j=0; jchrom);
fprintf(outfp," %8f | ", pind->fitness);
/* 新一代个体 */
pind = &(newpop[j]);
fprintf(outfp,"(%2d,%2d) %2d
writechrom(pind->chrom);
fprintf(outfp," %8f\n", pind->fitness);
}
}
void writechrom(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()
{
int j;
sumfitness = 0;
for(j = 0; j < popsize; j++)
sumfitness += oldpop[j].fitness;
int select()
{
/* 轮盘赌选择*/
extern float randomperc();
float sum, pick;
int i;
pick = randomperc();
sum = 0;
if(sumfitness != 0)
{
}
else
i = rnd(1,popsize);
return(i-1);
for(i = 0; (sum < pick) && (i < popsize); i++)
sum += oldpop[i].fitness/sumfitness;
}
}
}
}
}
}
void statistics(struct individual *pop)
{
/* 计算种群统计数据 */
int i, j;
sumfitness = 0.0;
min = pop[0].fitness;
max = pop[0].fitness;
/* 计算最大、最小和累计适应度 */
for(j = 0; j < popsize; j++)
{
sumfitness = sumfitness + pop[j].fitness;
if(pop[j].fitness > max) max = pop[j].fitness;
if(pop[j].fitness < min) min = pop[j].fitness;
/* new global best-fit individual */
if(pop[j].fitness > bestfit.fitness)
{
for(i = 0; i < chromsize; i++)
bestfit.chrom[i]
= pop[j].chrom[i];
bestfit.fitness
bestfit.varible
bestfit.generation = gen;
= pop[j].fitness;
= pop[j].varible;
}
}
/* 计算平均适应度 */
avg = sumfitness/popsize;
void title()
{
printf("SGA Optimizer 基本遗传算法\n");
void repchar(FILE *outfp,char *ch,int repcount)
{
int j;
for (j = 1; j <= repcount; j++) fprintf(outfp,"%s", ch);
void skip(FILE *outfp,int skipcount)
{
int j;
for (j = 1; j <= skipcount; j++)
fprintf(outfp,"\n");
void objfunc(struct individual *critter)
{
/* 计算适应度函数值 */
unsigned mask=1;
unsigned bitpos;
unsigned tp;
double bitpow ;
int j, k, stop;
critter->varible = 0.0;
for(k = 0; k < chromsize; k++)
{
if(k == (chromsize-1))
stop = lchrom-(k*(8*sizeof(unsigned)));
else
stop =8*sizeof(unsigned);
tp = critter->chrom[k];
for(j = 0; j < stop; j++)
{
bitpos = j + (8*sizeof(unsigned))*k;
if((tp&mask) == 1)
{
bitpow = pow(2.0,(double) bitpos);
critter->varible = critter->varible + bitpow;
}
tp = tp>>1;
}
}
critter->varible =-1+critter->varible*3/(pow(2.0,(double)lchrom)-1);
critter->fitness =critter->varible*sin(critter->varible*10*atan(1)*4)+2.0;
}
void mutation(unsigned *child)
{
/*变异操作*/
int j, k, stop;
unsigned mask, temp = 1;
for(k = 0; k < chromsize; k++)
{
mask = 0;
if(k == (chromsize-1))
stop = lchrom - (k*(8*sizeof(unsigned)));
else
stop = 8*sizeof(unsigned);
for(j = 0; j < stop; j++)
{
if(flip(pmutation))
{
mask = mask|(temp<= (k*(8*sizeof(unsigned))))
{
child1[k-1] = parent1[k-1];
child2[k-1] = parent2[k-1];
}
else if((jcross < (k*(8*sizeof(unsigned)))) && (jcross > ((k-1)*(8*sizeof(unsigned)))))
{
mask = 1;
for(j = 1; j <= (jcross-1-((k-1)*(8*sizeof(unsigned)))); j++)
{
temp = 1;
mask = mask<<1;
mask = mask|temp;
}
child1[k-1] = (parent1[k-1]&mask)|(parent2[k-1]&(~mask));
child2[k-1] = (parent1[k-1]&(~mask))|(parent2[k-1]&mask);
child1[k-1] = parent2[k-1];
child2[k-1] = parent1[k-1];
for(k = 0; k < chromsize; k++)
{
child1[k] = parent1[k];
child2[k] = parent2[k];
}
else
{
}
}
}
else
{
}
jcross = 0;
}
return(jcross);
}
void advance_random()
{
int j1;
double new_random;
for(j1 = 0; j1 < 24; j1++)
{
}
for(j1 = 24; j1 < 55; j1++)
{
}
}
/* 产生 55 个随机数 */
new_random = oldrand[j1] - oldrand[j1+31];
if(new_random < 0.0) new_random = new_random + 1.0;
oldrand[j1] = new_random;
new_random = oldrand [j1] - oldrand [j1-24];
if(new_random < 0.0) new_random = new_random + 1.0;
oldrand[j1] = new_random;
/* 以一定概率产生 0 或 1 */
int flip(float prob)
{
float randomperc();
if(randomperc() <= prob)
return(1);
return(0);
else
}
/* 设定随机数种子并初始化随机数发生器 */
void randomize()
{
float randomseed;
int j1;
for(j1=0; j1<=54; j1++)
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
