main.c

用遗传算法实现简单的组合逻辑电路（四输入

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <process.h>
#include <math.h>
#include <string.h>
/*******************************************************************
X1、X0、Y1、Y0四输入
********************************************************************/
unsigned SHURU[16][4]=
{
	{0,0,0,0},{0,0,0,1},{0,0,1,0},{0,0,1,1},
	{0,1,0,0},{0,1,0,1},{0,1,1,0},{0,1,1,1},
	{1,0,0,0},{1,0,0,1},{1,0,1,0},{1,0,1,1},
	{1,1,0,0},{1,1,0,1},{1,1,1,0},{1,1,1,1}
};

unsigned ZZB[16][10]={0};

/********************************************************************
 全局变量 
********************************************************************/
struct individual                       /* 个体*/
{
    char *chrom;						/* 染色体 */
    double   fitness;                   /* 个体适应度 */
    int      xsite;                     /* 交叉位置 */
    int      parent[2];                 /* 父个体  */
	unsigned ZZ[16];                    /* 存储编码对应的真值表，以计算适应度 */
};
struct bestever                         /* 最佳个体*/
{
    char *chrom;						/* 最佳个体染色体*/
    double   fitness;                   /* 最佳个体适应度 */
    int      generation;                /* 最佳个体生成代 */
};
 struct individual *oldpop;             /* 当前代种群 */
 struct individual *newpop;             /* 新一代种群 */
 struct bestever *bestfit;              /* 最佳个体 */
 double sumfitness;                     /* 种群中个体适应度累计 */
 double max;                            /* 种群中个体最大适应度 */
 double avg;                            /* 种群中个体平均适应度 */
 double min;                            /* 种群中个体最小适应度 */
 float  pcross;                         /* 交叉概率 */
 float  pmutation;                      /* 变异概率 */
 unsigned    popsize;                   /* 种群大小  */
 unsigned    lchrom;                    /* 染色体长度*/
 unsigned    chromsize;                 /* 存储一染色体所需字节数 */
 unsigned    gen;                       /* 当前世代数 */
 unsigned    maxgen;                    /* 最大世代数   */
 unsigned    run;                       /* 当前运行次数 */
 unsigned    maxruns;                   /* 总运行次数   */
 unsigned    printstrings;              /* 输出染色体编码的判断，0 -- 不输出, 1 -- 输出 */
 unsigned    nmutation;                 /* 当前代变异发生次数 */
 unsigned    ncross;					/* 当前代交叉发生次数 */

/* 输出文件指针 */
FILE *outfp,*outfp2,*infp ;
/********************************************************************
 函数定义 
*********************************************************************/
int flip(float);					/* 以一定概率产生0或1 */
int rnd(int, int);					/* 在整数low和high之间产生一个随机整数 */
float randomperc();					/* 与库函数random()作用相同, 产生[0,1]之间一个随机数 */	
void initialize();					/* 遗传算法初始化 */
void initdata();					/* 遗传算法参数输入 */
void initpop();						/* 随机初始化种群 */
void initreport();					/* 初始参数输出 */
void generation();                  /* 遗传产生下一代 */
void initmalloc();					/* 为全局数据变量分配空间 */
void freeall();						/* 释放内存空间 */
void nomemory(char *);				/* 内存不足，退出 */
void report();						/* 输出种群统计结果 */
void writechrom(FILE *,char *);		/* 输出染色体编码 */
void preselect();                   /* 统计总的适应度，制作转盘 */
void statistics(struct individual *);/* 计算种群统计数据 */
void repchar (FILE *,char *,int);    /* 在文件中输出int个字符 */
void skip(FILE *,int);              /* 在输出文件中换行 */
int  select();						/* 轮盘赌选择 */
void calculateZZB(struct individual *);  /* 计算个体对应的真值表 */
void objfunc(struct individual *);	/* 计算适应度函数值 */
int  crossover (char *, char *, char *, char *);	/* 交叉操作 */
void mutation(char *);				/* 变异操作*/
void selectbest1(struct bestever *);/* 对适应度高的个体编码进行简化  */
void selectbest2();   /* 对适应度相同的个体编码进行比较，存取最简的 */

 /*******************************************************************
 遗传算法初始化 
*********************************************************************/
void initialize()     
{
    /* 确定染色体的字节长度 */
    chromsize = (lchrom/(8*sizeof(char)));
    if(lchrom%(8*sizeof(char))) chromsize++;
    /*分配给全局数据结构空间 */
    initmalloc();
    /* 初始化全局计数变量和一些数值*/
    nmutation = 0;
    ncross = 0;
    bestfit[run].fitness = 0.0;
    bestfit[run].generation = 0;
    /* 初始化种群，并统计计算结果 */
    initpop();
    statistics(oldpop);
    initreport();
} 

/********************************************************************
 遗传算法参数输入 
*********************************************************************/
void initdata()           
{
	char  answer[2];
	printf("Enter the species size(20-2000):");
	scanf("%d", &popsize);
	if((popsize%2) != 0)
	{
		fprintf(outfp, "种群大小已设置为偶数\n");
		popsize++;
	}
	printf("Enter the chromosome length(9,18,27,36,54,63,72):");
	scanf("%d", &lchrom);
	printf("Whether output the whole chromosome encodings ?(y/n):");
	printstrings=1;
	scanf("%s", answer);
	if(strncmp(answer,"n",1) == 0) printstrings = 0;
	printf("Enter the largest number of generations(100-10000):");
	scanf("%d", &maxgen);
	printf("Enter the cross-rate(0.3-0.9):");   
	scanf("%f", &pcross);
	printf("Enter the mutation-rate(0.0001-0.1):");
	scanf("%f", &pmutation);
	printf("****** wait for the end ******");      
}

/********************************************************************
 随机初始化种群 
*********************************************************************/
void initpop()           
{
    unsigned j, j1, k, stop;
    unsigned mask = 1;
    for(j = 0; j < popsize; j++)
    {
        stop =4*sizeof(char);
        for(k = 0; k < chromsize-1; k++)
        {
            oldpop[j].chrom[k] = 0;            
            for(j1 = 1; j1 <= stop; j1++)
            {
				if(flip(0.5))
				{
					oldpop[j].chrom[k] = oldpop[j].chrom[k]|mask;
					oldpop[j].chrom[k] = oldpop[j].chrom[k]<<2;
				}
				else
				{
					oldpop[j].chrom[k] = oldpop[j].chrom[k]<<1;
					oldpop[j].chrom[k] = oldpop[j].chrom[k]|mask;
					oldpop[j].chrom[k] = oldpop[j].chrom[k]<<1;
				}
            }
        }
		stop = lchrom - (k*(8*sizeof(char)));
		for(j1 = 0; 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;
		calculateZZB(&(oldpop[j]));
        objfunc(&(oldpop[j]));       /* 计算初始适应度*/
    }
}

/********************************************************************
 初始参数输出 
*********************************************************************/
void initreport()               
{
    void   skip();
    skip(outfp,1);
    fprintf(outfp,"             基本遗传算法参数\n");
    fprintf(outfp," -------------------------------------------------\n");
    fprintf(outfp,"    种群大小(popsize)     =   %d\n",popsize);
    fprintf(outfp,"    染色体长度(lchrom)    =   %d\n",lchrom);
    fprintf(outfp,"    最大进化代数(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()
{
	unsigned mate1, mate2, jcross, j = 0;
	/*  每代运算前进行预选 */
	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);
      /* 解码, 计算适应度 */
	  calculateZZB(&(newpop[j]));
      objfunc(&(newpop[j]));
      /*记录亲子关系和交叉位置 */
      newpop[j].parent[0] = mate1+1;
      newpop[j].xsite = jcross;
      newpop[j].parent[1] = mate2+1;
	  calculateZZB(&(newpop[j+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()              
{
	unsigned nbytes;
	unsigned 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(char);
	for(j = 0; j < popsize; j++)
    {
		if((oldpop[j].chrom = (char *) malloc(nbytes)) == NULL)
			nomemory("oldpop chromosomes");
		if((newpop[j].chrom = (char *) malloc(nbytes)) == NULL)
			nomemory("newpop chromosomes");
	}
	for(j = 0; j < maxruns+1; j++)
	{
		if((bestfit[j].chrom = (char *) malloc(nbytes)) == NULL)
			nomemory("bestfit chromosome");
	}
}

/********************************************************************
 释放内存空间 
*********************************************************************/
void freeall()               
{
	unsigned i;
	for(i = 0; i < popsize; i++)
	{
		free(oldpop[i].chrom);
		free(newpop[i].chrom);
	}
	free(oldpop);
	free(newpop);
	free(bestfit[run].chrom);
}

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

/********************************************************************
 输出种群统计结果 
*********************************************************************/
void report()                
{
    void  repchar(), skip();
    void  writepop();
    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-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 代统计: \n",gen+1);
    fprintf(outfp,"总交叉操作次数 = %d, 总变异操作数 = %d\n",ncross,nmutation);
    fprintf(outfp," 最小适应度：%f 最大适应度：%f  平均适应度 %f\n", min,max,avg);
    fprintf(outfp," 迄今发现最佳个体 =>  所在代数： %d  ", bestfit[run].generation);
    fprintf(outfp," 适应度：%f  染色体：", bestfit[run].fitness);
    writechrom(outfp,(&bestfit[run])->chrom);
    skip(outfp,1);
    repchar(outfp,"-",80);
    skip(outfp,1);
	fflush(outfp);
}

/********************************************************************
输出种群所有个体的染色体编码
*********************************************************************/
void writepop()
{
	struct individual *pind;
    unsigned j;
    for(j=0; j<popsize; j++)
    {
        fprintf(outfp,"%3d)  ",j+1);
        /* 当前代个体 */
        pind = &(oldpop[j]);
        writechrom(outfp,pind->chrom);
        fprintf(outfp,"  %8f | ", pind->fitness);
        /* 新一代个体 */
        pind = &(newpop[j]);
        fprintf(outfp,"(%2d,%2d)   %2d   ",
        pind->parent[0], pind->parent[1], pind->xsite);
        writechrom(outfp,pind->chrom);
        fprintf(outfp,"  %8f\n", pind->fitness);
    }
	fflush(outfp);
}

/********************************************************************
 输出染色体编码 
*********************************************************************/
void writechrom(FILE *fp,char *chrom)           
{
	unsigned j, k, stop;
    unsigned mask = 0x80, tmp;
    for(k = 0; k < chromsize; k++)
    {
        tmp = chrom[k];
        if(k == (chromsize-1))
		{
            stop = lchrom - (k*(8*sizeof(char)));
			mask = mask >>((8*sizeof(char))-stop);
		}
		else
            stop =8*sizeof(char);
        for(j = 0; j < stop; j++)
        {
            if(tmp&mask)
                fprintf(fp,"1");
            else
                fprintf(fp,"0");
            tmp = tmp<<1;
      }
      fprintf(fp," ");
    }
}

/********************************************************************
统计总的适应度，制作转盘
*********************************************************************/
void preselect()