/*******************************************
*             畢設遺傳算法程序             *
*          programmed by 朱健華            *
*******************************************/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
/*******************************************
*    the defination of constant            *
*******************************************/
#define POPSIZE 200//種群數量
#define pi 3.14
/*******************************************
*                用戶數據定義              *
*******************************************/
#define CHROMLENGTH 120
int PopSize =200;//種群規模
int MaxGeneration =50000;//終止進化代數
double Pc =0.60;//交叉概率
double Pm =0.03;//變異概率
/*******************************************
*                數據類型定義              *
*******************************************/
struct individual //個體數據定義
{
char chrom[CHROMLENGTH+1];//個體字符串編碼
double f1,f2,a1,a2,k1,k2;
double value;//個體表現型值
double fitness;//個體適應度值
};
/*******************************************
*                 定義全局變量             *
*******************************************/
int generation;//進化代數
int best_index;//最佳個體索引
int worst_index;//最差個體索引
struct individual bestindividual;//當前代最佳個體
struct individual worstindividual;//當前代最差個體
struct individual currentbest;//迄今為止的最好個體
struct individual population[POPSIZE];//種群
FILE *galog;
/*******************************************
*            函數原型聲明                  *
*******************************************/
void GenerateInitialPopulation(void);//產生初始種群
void GenerateNextPopulation(void);//產生下一代群體
void EvaluatePopulation(void);//評價函數
double DecodeChromosome1(char *,int,int);//電阻值對應染色體解碼
double DecodeChromosome2(char *,int,int);//電容值對應染色體解碼
void CaculateObjectValue(void);//計算個體表現型值
void CaculateFitnessValue(void);//計算適應度
void FindBestAndWorstIndividual(void);//尋找最佳和最差個體
void PerformEvolution(void);//進行評價操作
void SelectionOperator(void);//選擇操作
void CrossoverOperator(void);//交叉操作
void MutationOperator(void);//變異操作
void OutputTextReport(void);
/********************************************
*            主程序                         *
********************************************/
void main(void)
{
generation=0;
GenerateInitialPopulation();
EvaluatePopulation();
while(generation<MaxGeneration)
  {
  generation++;
  GenerateNextPopulation();
  EvaluatePopulation();
  PerformEvolution();
  OutputTextReport();
	}
}    
/********************************************
*            產生初始群體                   *
********************************************/
void GenerateInitialPopulation(void)
{
 int i,j;
 //randomize();
 for(i=0;i<PopSize;i++)
 {
	for(j=0;j<CHROMLENGTH;j++)
	{population[i].chrom[j]=(rand()%10<5)?'0':'1';}
 	population[i].chrom[CHROMLENGTH]='\0';
 }	
}
/*********************************************
*              產生下一代                    *
*********************************************/
void GenerateNextPopulation(void)
{
  SelectionOperator();//選擇操作
  CrossoverOperator();//交叉操作
  MutationOperator();//變異操作
}
/*********************************************
*         依據一定的規則評價種群             *
*********************************************/
void EvaluatePopulation(void)
{
  CaculateObjectValue();//計算個體函數值
  CaculateFitnessValue();//計算適應度
  FindBestAndWorstIndividual();
}
/*********************************************
*將二進制染色體碼解碼成十進制數 電阻值解碼   *
*********************************************/
double DecodeChromosome1(char *string,int point,int length)
{
	int i;
	double r=0.0;
	char *pointer;
	for(i=0,pointer=string+point;i<length;i++,pointer++)
	{
		if(i<7)
		{r+=(*pointer-'0')<<(length-1-i);}
        else if(i>=7)
		{r+=(*pointer-'0')<<(length-1-i)/8;}
	}
	return(r);
}
/*********************************************
*將二進制染色體碼解碼成十進制數 電容值解碼   *
*********************************************/
double DecodeChromosome2(char *string,int point,int length)
{
	int i;
	double c=0.0;
	char *pointer;
	for(i=0,pointer=string+point;i<length;i++,pointer++)
	{c+=(*pointer-'0')<<(length-1-i);}
	c=c/(1024*40);
	return(c);
}
/*********************************************
*           計算個體函數值                   *
*********************************************/
void CaculateObjectValue(void)
{
	int i,j;
	double x[12];
	for(i=0;i<PopSize;i++)
	{
		for(j=0;j<12;j++)
		{
			if(j<8)
			{
				x[j]=DecodeChromosome1(population[i].chrom,10*j,10);
			}
			else if(j>=8)
			{
				x[j]=DecodeChromosome2(population[i].chrom,10*j,10);
			}
		}
		population[i].f1=1/(2*pi*sqrt(x[0]*x[1]*x[8]*x[9]));
        population[i].f2=1/(2*pi*sqrt(x[4]*x[5]*x[10]*x[11]));
		population[i].k1=1+x[3]/x[2];
		population[i].k2=1+x[7]/x[6];
        population[i].a1=(sqrt(x[1]*x[9]/(x[0]*x[8]))+sqrt(x[0]*x[9]/(x[1]*x[8]))-(population[i].k1-1)*sqrt(x[0]*x[8]/(x[1]*x[9])))/2;
		population[i].a2=(sqrt(x[5]*x[11]/(x[4]*x[10]))+sqrt(x[4]*x[11]/(x[5]*x[10]))-(population[i].k2-1)*sqrt(x[4]*x[10]/(x[5]*x[11])))/2;
		population[i].value=0.05*fabs(population[i].f1-11940.04)+0.05*fabs(population[i].f2-20625.4)+fabs(population[i].k1*population[i].k2-36)+10*fabs(population[i].a1-0.17)+10*fabs(population[i].a2-0.709)+1;
	}
}
/***********************************************
*          計算適應度值                        *
***********************************************/
void CaculateFitnessValue(void)
{
	int i;
	for(i=0;i<PopSize;i++)
	{
		if(population[i].value==0.00)
		  population[i].fitness=population[i].value;
		else
		  population[i].fitness=1/population[i].value;
	}
}
/***********************************************
*       尋找當前代最佳個體                     *
***********************************************/
void FindBestAndWorstIndividual(void)
{
	int i;
	double sum=0.0;
	//尋找當前代最佳和最差個體
	bestindividual=population[0];
	worstindividual=population[0];
	for(i=1;i<PopSize;i++)
	{
		if(population[i].fitness>bestindividual.fitness)
		 {
		 	bestindividual=population[i];
		 	best_index=i;
		 }
		else if(population[i].fitness<worstindividual.fitness)
		 {
		 	worstindividual=population[i];
		 	worst_index=i;
		 }	
		sum+=population[i].fitness;
	//尋找迄今為止最佳個體
  if(generation==0)
     {currentbest=bestindividual;}
  else
     {if(bestindividual.fitness>currentbest.fitness)
 	      {currentbest=bestindividual;}
     } 	
	}
}
/***********************************************
*          用最優保存策略進行評價操作          *
***********************************************/
void PerformEvolution(void)
{
	if(bestindividual.fitness>currentbest.fitness)
		{currentbest=population[best_index];}
	else 
		{population[worst_index]=currentbest;}
}
/***********************************************
*         用比例選擇的方法復制染色體           *
***********************************************/
void SelectionOperator(void)
{
	int i,index;
	double p,sum=0.0;
	double cfitness[POPSIZE];
	struct individual newpopulation[POPSIZE];
	//計算相對適應度
	for(i=0;i<PopSize;i++)
	{sum+=population[i].fitness;}
	for(i=0;i<PopSize;i++)
	{cfitness[i]=population[i].fitness/sum;}
	//計算
	for(i=1;i<PopSize;i++)
	{cfitness[i]=cfitness[i-1]+cfitness[i];}
	//選擇操作
  for(i=0;i<PopSize;i++)
  {
	 p=rand()%1000/1000.0;
	 index=0;
	 while(p>cfitness[index])
	 {index++;}
	 newpopulation[i]=population[index];
  }
  for(i=0;i<PopSize;i++)
  {population[i]=newpopulation[i];}
}
/***********************************************
*        用單點交叉方法進行交叉操作            *
***********************************************/
void CrossoverOperator(void)
{
	int i,j;
	int index[POPSIZE];
	int point,temp;
	double p;
	char ch;
	//隨機配對兩個個體
	for(i=0;i<PopSize;i++)
	{index[i]=i;}
	for(i=0;i<PopSize;i++)
	{
		point=rand()%(PopSize-i);
		temp=index[i];
		index[i]=index[point+i];
		index[point+i]=temp;
	}
	//單點交叉操作
	for(i=0;i<PopSize-1;i+=2)
	{
		p=rand()%1000/1000.0;
		if(p<Pc)
			{
				point=rand()%(CHROMLENGTH-1)+1;
				for(j=point;j<CHROMLENGTH;j++)
				{
					ch=population[index[i]].chrom[j];
					population[index[i]].chrom[j]=population[index[i+1]].chrom[j];
					population[index[i+1]].chrom[j]=ch;
				}
			}
	}
}
/***********************************************
*                     變異操作                 *
***********************************************/
void MutationOperator(void)
{
	int i,j;
	double p;
	//位變異
	for(i=0;i<PopSize;i++)
	{
		for(j=0;j<CHROMLENGTH;j++)
		{
			p=rand()%1000/1000.0;
			if(p<Pm)
			{population[i].chrom[j]=(population[i].chrom[j]=='0')?'1':'0';}
		}
	}
}
/***********************************************
*                     輸出結果                 *
***********************************************/
void OutputTextReport(void)
{
	//輸出
	printf(galog,"\n\nSimulation Completed\n");
    printf("success!\n");
}