#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()