📄 gaopt.c
字号:
/**************************************************************/
/* 基于基本遗传算法的函数最优化 */
/* 同济大学计算机系 王小平 2000年5月 */
/**************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<graphics.h>
#include<math.h>
#include<time.h>
#include<string.h>
#include "graph.c"
#include "operator.c"
#define POP_SIZE 25 /* 种群大小 */
#define G_LENGTH 8 /* 染色体长度 */
#define C_RATE 0.2 /* 交叉概率 */
#define M_RATE 0.01 /* 变异概率 */
#define XMAX 255 /* 函数变量最大值 */
#define X1 350 /* 函数图形区窗口左上点X坐标 */
#define Y1 40 /* 函数图形区窗口左上点Y坐标 */
#define XR1 255 /* 函数图形区窗口长度 */
#define YR1 200 /* 函数图形区窗口高度 */
#define X2 360 /* 适应度图形区窗口左上点X坐标 */
#define Y2 280 /* 适应度图形区窗口左上点Y坐标 */
#define XR2 250 /* 适应度图形区窗口长度 */
#define YR2 100 /* 适应度图形区窗口宽度 */
#define STEP 2 /* 适应度图形区X方向步长 */
void initialize_gene(gene,pop_size,g_length)
/* 种群中个体遗传基因型的初始化 */
unsigned char *gene; /* 遗传基因 */
int pop_size; /* 种群大小 */
int g_length; /* 个体染色体长度 */
{
int i,j;
randomize();
for(i=0;i<pop_size;i++)
for(j=0;j<g_length;j++)
*(gene+i*g_length+j)=random(2);
}
int gene_to_pheno(gene,g_length)
/* 基因型到表现型的变换--解码 */
unsigned char *gene; /* 基因型 */
int g_length; /* 染色体长度 */
{
int i,pheno;
pheno=0;
for(i=0;i<g_length;i++)
pheno=pheno*2+*(gene+i);
return(pheno);
}
void calc_fitness(gene,fitness,pop_size,g_length,func, max_fit,avg_fit)
/* 计算种群中个体的适应度 */
unsigned char *gene; /* 个体的遗传基因 */
double *fitness; /* 个体的适应度 */
double *func; /* 评价函数 */
double *max_fit,*avg_fit; /* 最大适应度与平均适应度 */
int pop_size; /* 种群大小 */
int g_length; /* 个体染色体长度 */
{
unsigned char *g; /* 个体的遗传基因指针变量 */
int pheno; /* 个体的表现型 */
int i,j;
double f;
*max_fit=0.0;
*avg_fit=0.0;
f=(double)pop_size;
for(i=0;i<pop_size;i++)
{
g=gene+i*g_length;
pheno=gene_to_pheno(g,g_length);
*(fitness+i)=*(func+pheno);
if(*(fitness+i)>*max_fit)
*max_fit=*(fitness+i);
*avg_fit=*avg_fit+*(fitness+i)/f;
}
}
void sga_reproduction(gene,fitness,new_gene,new_fitness,pop_size,g_length)
/* 基于个体的适应度评价进行新一代个体的选择(轮盘赌方法)，选择后分别将新的基因型和适应度代入到新个体中 */
unsigned char *gene; /* 当前代的个体遗传基因型 */
unsigned char *new_gene; /* 新一代的个体遗传基因型 */
double *fitness; /* 当前代的个体适应度 */
double *new_fitness; /* 新一代的个体适应度 */
int pop_size; /* 种群大小 */
int g_length; /* 染色体长度 */
{
double sum_of_fitness;
double border;
double r; /* 轮盘上的选择位置变量 */
int i,j;
int num;
sum_of_fitness=0.0;
for(i=0;i<pop_size;i++) /* 轮盘赌的选择循环 */
sum_of_fitness=sum_of_fitness+*(fitness+i);
for(i=0;i<pop_size;i++)
{
r=sum_of_fitness*(random(10001)/10000.0);
num=0;
border=*fitness;
while(border<r)
{
num++;
border=border+*(fitness+num);
}
for(j=0;j<g_length;j++)
*(new_gene+i*g_length+j)=*(gene+num*g_length+j);
*(new_fitness+i)=*(fitness+num);
}
}
void sga_crossover(gene,pop_size,g_length,c_rate)
/* 基本遗传算法的交叉操作--单点交叉 */
unsigned char *gene; /* 遗传基因 */
int pop_size; /* 种群大小 */
int g_length; /* 个体染色体长度 */
double c_rate; /* 交叉概率 */
{
unsigned char *gene1; /* 父个体1的遗传基因指针变量 */
unsigned char *gene2; /* 父个体1的遗传基因指针变量 */
unsigned char work; /* 中间变量 */
int i,j;
int c_pos; /* 交叉位置变量 */
double r; /* 随机数变量 */
for(i=0;i<pop_size-1;i=i+2)
{
r=random(10001)/10000.0;
if(r<=c_rate)
{
gene1=gene+g_length*i;
gene2=gene1+g_length;
c_pos=random(g_length-2)+1;
for(j=c_pos;j<g_length;j++) /* 两个父个体之间部分遗传基因的交换 */
{ work=*(gene1+j);
*(gene1+j)=*(gene2+j);
*(gene2+j)=work;
}
}
}
}
void sga_mutation(gene,pop_size,g_length,m_rate)
/* 基本遗传算法的变异操作--个体遗传基因按小概率翻转 */
unsigned char *gene; /* 遗传基因 */
int pop_size; /* 种群大小 */
int g_length; /* 染色体长度 */
double m_rate; /* 变异概率 */
{
int i,j;
double r;
for(i=0;i<pop_size;i++)
{
for(j=0;j<g_length;j++)
r=random(10001)/10000.0;
if(r<=m_rate) /* 变异发生判断 */
{
if ( *(gene+g_length*i+j)==0)
*(gene+g_length*i+j)=1;
else
*(gene+g_length*i+j)=0;
}
}
}
void make_function(func,xmax)
/* 生成一个函数, 用于最优化计算的目标函数(最大化) */
/* f=∑ai*sin(x* bi+ci) 其中 ai∈[0, 0.35]的均匀随机数
bi∈[2*pi, 5*2*pi] /xmax的均匀随机数
ci∈[0, 2*pi]的均匀随机数
x∈[0,xmax]为优化变量
i=1,2,3 */
double *func; /* 函数值 */
int xmax; /* 变量最大值 <XMAX */
{
int x,i;
double a[3],b[3],c[3];
double pi=3.141592;
double fxmax,fx,f_value;
double f_min,f_max,f_mid,f_range;
double dbl;
randomize();
fxmax=(double)xmax;
for(i=0;i<3;i++) /* 优化函数为三个三角函数之和 */
{
a[i]=0.35*(random(10001)/10000.0);
b[i]=(4*(random(10001)/10000.0)+1)*2.0*pi/fxmax;
c[i]=2.0*pi*(random(10001)/10000.0);
}
f_min=1.0;
f_max=0.0;
for(x=0;x<=xmax;x++) /* 将优化函数正规化为[0,1]区间数 */
{
fx=(double)x;
f_value=0.0;
for(i=0;i<3;i++)
{
dbl=b[i]*fx+c[i];
f_value=f_value+a[i]*sin(dbl);
}
f_value=f_value+0.5;
if(f_value>f_max) f_max=f_value;
if(f_value<f_min) f_min=f_value;
*(func+x)=(double)f_value;
}
f_range=f_max-f_min;
f_mid=(f_max+f_min)/2.0;
for(x=0;x<=xmax;x++)
{
f_value=(*(func+x)-f_mid)/f_range+0.5;
if(f_value>1.0) f_value=1.0;
else if(f_value<0.0) f_value=0.0;
*(func+x)=f_value;
}
}
void g_draw_func(func,xmax)
/* 绘制优化函数的图形 */
double *func; /* 函数值 */
int xmax; /* 变量最大值 */
{
int x,y,x_old,y_old,i;
double f;
g_rectangle(X1+1,Y1+1,X1+XR1-1,Y1+YR1-1,0,1);
g_rectangle(X1+1,Y1-12,X1+XR1,Y1-1,8,1);
g_rectangle(X1,Y1,X1+XR1,Y1+YR1,6,0);
x_old=X1;
y_old=Y1+YR1-(int)(*func*YR1);
f=XR1/(double)xmax;
for(i=1;i<=xmax;i++)
{
x=X1+(int)(i*f);
y=Y1+YR1-(int)(*(func+i)*YR1);
g_line(x_old,y_old,x,y,12);
x_old=x;
y_old=y;
}
}
void g_init_grph(func,xmax)
/* 初始化画面的图形 */
double *func; /* 函数值 */
int xmax; /* 变量最大值 */
{
int x,y,x_old,y_old,i;
char c[5];
/*初始化函数图形区*/
g_rectangle(320,0,639,399,8,1);
g_rectangle(321,1,638,16,8,1);
disp_hz16("基于基本遗传算法的函数最优化",370,1,15);
disp_hz16("g(x)",X1-30,Y1-18,15);
disp_hz16("1.0",X1-30,Y1,15);
disp_hz16("0",X1-10,Y1+YR1,15);
disp_hz16("x",X1+XR1+10,Y1+YR1-20,15);
disp_hz16("XMAX",X1+XR1-10,Y1+YR1,15);
g_draw_func(func,xmax);
/* 初始化适应度图形区 */
g_rectangle(X2,Y2,X2+XR2,Y2+YR2,0,1);
g_rectangle(X2,Y2,X2+XR2,Y2+YR2,6,0);
setcolor(15);
disp_hz16("最大适应度",X2+5,Y2-18,15);
g_line(X2+90,Y2-10,X2+110,Y2-10,11);
setcolor(15);
disp_hz16("平均适应度",X2+120,Y2-18,15);
g_line(X2+205,Y2-10,X2+225,Y2-10,9);
setcolor(15);
disp_hz16("世代数",X2+168,Y2+YR2+10,15);
g_text(X2-30,Y2,15,"1.0");
/* g_text(X2-30,Y2+YR2,15,"0.0");*/
}
void g_plot_grph(num,gene,fitness,pop_size,g_length,func, xmax,max_fit,m_f_old,avg_fit,a_f_old,gen_num)
/* 随世代进化更新图形 */
unsigned char *gene; /* 遗传基因 */
double *fitness; /* 适应度 */
double *func; /* 函数值 */
double max_fit,m_f_old; /* 当前代最大适应度，上一代最大适应度 */
double avg_fit,a_f_old; /* 当前代平均适应度，上一代平均适应度 */
int num; /* 当前世代数 */
int pop_size; /* 种群大小 */
int g_length; /* 染色体长度 */
int xmax; /* 变量最大值 */
int gen_num; /* 最大世代数 */
{
int i,j,x,y,x_old,y_old;
double f;
unsigned char *g;
char c[10];
/* 显示当前世代种群中个体的遗传基因 */
if(num==gen_num-1)
{
for(i=0;i<pop_size;i++)
{
printf("Indv.%2d:",i+1);
for(j=0;j<g_length;j++)
printf("%d",*(gene+i*g_length+j));
printf("==>Fitness %.4f\n",*(fitness+i));
}
printf("Max_fit=%f \n",max_fit);
printf("Avg_fit=%f \n",avg_fit);
}
/* 显示个体在函数图形区中的位置 */
g_draw_func(func,xmax);
f=XR1/(double)xmax;
for(i=0;i<pop_size;i++)
{
g=gene+i*g_length;
j=gene_to_pheno(g,g_length);
x=X1+(int)(j*f);
y=Y1+YR1-*(func+j)*YR1;
g_line(x,y-10,x,y,15);
}
/* 适应度曲线的更新 */
if(num!=1 && num<=XR2/STEP)
{
if(num%10==0) /* 每隔10代更新一次 */
{
x=X2+(num-1)*STEP;
g_line(x,Y2+1,x,Y2+YR2-1,1);
sprintf(c,"%d",num);
if(num<100 || num%20==0)
g_text(x-8,Y2+YR2,15,c);
}
x_old=X2+(num-1)*STEP;
x=x_old+STEP;
y_old=Y2+YR2-(int)(m_f_old*YR2);
y=Y2+YR2-(int)(max_fit*YR2);
g_line(x_old,y_old,x,y,11);
y_old=Y2+YR2-(int)(a_f_old*YR2);
y=Y2+YR2-(int)(avg_fit*YR2);
g_line(x_old,y_old,x,y,9);
}
}
void generation(gene,fitness,pop_size,g_length, c_rate,m_rate,new_gene,new_fitness,func,xmax)
/* 世代进化的模拟 */
unsigned char *gene; /* 当前世代的个体遗传基因型 */
unsigned char *new_gene; /* 新一代的个体遗传基因型 */
double *fitness; /* 当前世代的个体适应度 */
double *new_fitness; /* 新一代的个体适应度 */
double *func; /* 优化函数 */
double c_rate,m_rate; /* 交叉概率和变异概率 */
int pop_size, g_length; /* 种群大小与染色体长度 */
{ int gen_max; /* 最大模拟世代数 */
int i,j,k;
double max_fit,avg_fit; /* 当前代最大适应度和平均适应度 */
double m_f_old,a_f_old; /* 新一代最大适应度和平均适应度 */
char choice[3];
setcolor(15);
disp_hz16("输入最大模拟世代数:",10,1,20);
gscanf(170,1,4,0,3,"%s",choice);
gen_max=atoi(choice);
m_f_old=0.0;
a_f_old=0.0;
for(i=0;i<gen_max;i++)
{
if(i==gen_max-1)
{
printf("\n");
printf("************Gen.%d*************\n",i+1);
}
calc_fitness(gene,fitness,pop_size,g_length,func,
&max_fit,&avg_fit);
sga_reproduction(gene,fitness,new_gene,new_fitness,
pop_size,g_length);
for(j=0;j<pop_size;j++)
{
*(fitness+j)=*(new_fitness+j);
for(k=0;k<g_length;k++)
*(gene+g_length*j+k)=*(new_gene+g_length*j+k);
}
sga_crossover(gene,pop_size,g_length,c_rate);
sga_mutation(gene,pop_size,g_length,m_rate);
g_plot_grph(i,gene,fitness,pop_size,g_length,func,
xmax,max_fit,m_f_old,avg_fit,a_f_old,gen_max);
m_f_old=max_fit;
a_f_old=avg_fit;
}
}
main() /* 主程序 */
{
/*当前代的个体遗传基因型与新一代的个体遗传基因型 */
unsigned char gene[POP_SIZE][G_LENGTH], new_gene[POP_SIZE][G_LENGTH];
/*当前代的个体适应度与新一代个体的适应度 */
double fitness[POP_SIZE], new_fitness[POP_SIZE];
/* 优化函数 */
double func[XMAX+1];
/* 初始化图形设置 */
g_init();
/* 生成优化函数 */
make_function(func,XMAX);
/* 初始化显示画面 */
g_init_grph(func,XMAX);
/* 初始化种群 */
initialize_gene(gene,POP_SIZE,G_LENGTH);
/* 世代进化模拟 */
generation(gene,fitness,POP_SIZE,G_LENGTH,
C_RATE,M_RATE,new_gene,new_fitness,func,XMAX);
setcolor(9);
disp_hz16("回车键结束",350,430,20);
getch();
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -