#include <afxwin.h>
#include <iostream.h>
#include<windows.h>
#include <stdio.h>
#include<stdlib.h>
#include<time.h>
#include<math.h>
#include<fstream.h> 
#define POPSIZE 500
#define MAX 300

#define C 1   //目標函數界限保守估計
#define length1 10
#define length2 10
#define chromlength length1+length2  //染色體長度
#define d length1/4
#define R 0.35
#define L length1

int generation;      //世代數
int best_index;
int worst_index;
int popsize;        //種群大小
int cksize;
int maxgeneration;  //最大世代數
struct individual
 {
      char  chrom[chromlength+1];
      double value;         
      double fitness;      //適應度
 };
struct individual bestindividual;  //最佳個體
struct individual worstindividual; //最差個體
struct individual currentbest;
struct individual population[MAX][POPSIZE];
struct individual copyone[MAX][POPSIZE];
struct individual mixedone;
struct individual p[MAX][POPSIZE];
//函數聲明                                       
void generateinitialpopulation();                 
void generatenextpopulation();
void evaluatepopulation();
long decodechromosome(char *,int,int);
void calculateobjectvalue();
void calculatefitnessvalue();
void findbestandworstindividual();
void performevolution();
void select();
void crossover();
void partinitial();
void input();
void output();
//種群初始化
void generateinitialpopulation()
{
	int i,j;
	for(i=0;i<popsize;i++)
	{
		for(j=0;j<chromlength;j++)
		{
			population[generation][i].chrom[j]=(rand()%10<5)?'0':'1';
		}
		population[generation][i].chrom[chromlength]='\0';
	}
	cksize=popsize;
}
//復制混合種群
void copy()
{   int i;
    for(i=0;i<popsize;i++)
   {
	  copyone[generation][i]=population[generation][i];
	  copyone[generation][popsize+i]=population[generation-1][i]; //產生混合種群C(K)
   }
}
//交叉
void crossover()
{
	int i,j,point,m,hm;
	struct individual temp;
	int mm=2*popsize;
    int index[2*POPSIZE];
	char ch;

	for(i=0;i<mm;i++)   //隨機配對
	{
		point=rand()%(2*popsize-i);
		temp=index[i];
		index[i]=index[point+i];
		index[point+i]=temp;
	}
	for(i=0;i<mm-1;i+=2)
	{    
		 hm=0;
	     for(j=0;j<chromlength;j++)//計算配對個體間海明距離
		 {
		     if(copyone[generation][index[i]].chrom[j]!=copyone[generation][index[i+1]].chrom[j])
			 {  hm++;}
		 }
		 if(hm>2*d)  //執行改進均勻交叉--->c(k)'
		 {    
			 m=(hm/2);
			 ch=copyone[generation][index[i]].chrom[m];
			 copyone[generation][index[i]].chrom[m]=copyone[generation][index[i+1]].chrom[m];
			 copyone[generation][index[i+1]].chrom[m]=ch;
		 }
		 else
		 {
			 if(i=popsize-1)
			 {
                copyone[generation][index[i]].value=NULL;
			    copyone[generation][index[i+1]].value=NULL;
			 }
             else
			 {  
				copyone[generation][index[i]]=copyone[generation][index[i+2]];
			    copyone[generation][index[i+1]]=copyone[generation][index[i+3]];
				i=i-2;
				mm=mm-2;
			 }
		 }
	}
	cksize=mm-1;
	for(i=0;i<cksize;i++)
	{
      population[generation][i]=copyone[generation][i];
	}
}
//選擇
void select()
{
    int i,index,j;
	double p,sum=0.0;
	int cP=cksize+POPSIZE;
	double cfitness[2*POPSIZE];
	struct individual newpopulation[2*POPSIZE];
	struct individual t;

	//c(k)'與p(k-1)混合起來
	for(i=0;i<cksize;i++)
	{
	     copyone[generation][popsize+i]=population[generation-1][i];
	}
	//c(k)'與p(k-1)混合種群按適應度從大到小排序
	for(i=0;i<cP;i++)
	{
		for(j=i+1;j<popsize;j++)
		{
			if(copyone[generation][i].fitness<copyone[generation][j].fitness)
			{
				t=copyone[generation][i];
				copyone[generation][i]=copyone[generation][j];
		        copyone[generation][j]=t;
			}
		}
	}

  //計算選擇概率
	for(i=0;i<cP;i++)
	{
		sum+=copyone[generation][i].fitness;
	}

    for(i=0;i<cP; i++)
	{
		cfitness[i]=copyone[generation][i].fitness/sum;
	}

	for(i=1;i<cP; i++)
	{
		cfitness[i]=cfitness[i-1]+cfitness[i];
	}

   //輪盤賭選取popsize個較優的個體組成p(k)
	for (i=0;i<popsize;i++)
	{
		p=rand()%1000/1000.0;
		index=0;
	   while (p>cfitness[index])
		{
			index++;
		}
		newpopulation[i]=copyone[generation][index];
	}
	for(i=0;i<popsize; i++)
	{
		population[generation][i]=newpopulation[i];
	}
	cksize=popsize;
}
//部分個體初始化
void partinitial()
{
	int i,j;
	double p;
	int RL=4;
	for (i=0;i<popsize-1;i++)
	{
		for(j=0;j<RL;j++)
		{
			p=rand()%chromlength;
		    population[generation-1][i].chrom[j]=(rand()%10<5)?'0':'1';
		}
  		population[generation][i]=population[generation-1][i];
	}

		population[generation][popsize-1]=population[generation-1][popsize-1];
		cksize=popsize;
}
//評價個體，求最佳個體
void evaluatepopulation()  
{
	calculateobjectvalue();   //計算目標值
	calculatefitnessvalue();   //計算適應度
	findbestandworstindividual();  //找到最好和最差個體
}
//給染色體解碼
long decodechromosome(char *string ,int point,int length) 
{
	int i;
	long decimal=0;
	char *pointer;
     for(i=0,pointer=string+point;i<length;i++,pointer++)
	    if(*pointer-'0')
		{
			decimal+=(long)pow(2,i);
		}
	return (decimal);
}
//計算函數值
void calculateobjectvalue()  
{
	int i;
	long temp1,temp2;
    double x,y,tt; 
	for (i=0; i<cksize; i++)
	{
		 temp1=decodechromosome(population[generation][i].chrom,0,length1);
         temp2=decodechromosome(population[generation][i].chrom,length1,length2);
         x=20.0*temp1/1023.0-10.0;    
         y=20.0*temp2/1023.0-10.0;  
		 tt=pow(x,2)+pow(y,2);
		 population[generation][i].value=0.5-(pow(sin(sqrt(tt)),2)-0.5)/pow((1+0.001*pow(tt,2)),2);
	}
}
//計算適應度
void calculatefitnessvalue()
{
	int  i;
    double temp;
    for(i=0;i<cksize;i++)
    {
		  if((C-population[generation][i].value)>0.0)
		  {
			  temp=1/(1+C-population[generation][i].value);
		  }
          else
		  {
			  temp=0.0;
		  }
     population[generation][i].fitness=temp;
   }
}
//求最佳個體和最差個體
void findbestandworstindividual( ) 
{
	int i;
	
	bestindividual=population[generation][0];
	worstindividual=population[generation][0];

	for (i=1;i<cksize; i++)
	{
		if (population[generation][i].fitness>bestindividual.fitness)
		{
			bestindividual=population[generation][i];
			best_index=i;
		}
		else if (population[generation][i].fitness<worstindividual.fitness)
		{
			worstindividual=population[generation][i];
			worst_index=i;
			
		}
	}

    if (generation==0)
	{
		currentbest=bestindividual;
	}
	else
	{
		if(bestindividual.fitness>=currentbest.fitness)
		{
			currentbest=bestindividual;
		}
	}
  
}
//演示評價結果
void performevolution() 
{
	if (bestindividual.fitness>currentbest.fitness)
	{
		currentbest=population[generation][best_index];
	}
	else
	{
		population[generation][worst_index]=currentbest;
	}
}
//數據輸入
void input() 
{   
	printf("初始化全局變量:\n");
	printf("    種群大小(50-500)：");  /**/
    scanf("%d", &popsize);
    if((popsize%2) != 0)
	{ 
    	printf( "   種群大小已設置為偶數\n");
	    popsize++;
	}
        printf("     最大世代數(100-300)：");
        scanf("%d", &maxgeneration);
}
//數據輸出
void output()
{

	int i;
    double sum;
    double average;
    sum=0.0;
    for(i=0;i<popsize;i++)
	{
		sum+=population[generation][i].value;
	}
    average=sum/popsize;
    printf("當前世代=%d\n當前世代平均函數值=%f\n當前世代最高函數值=%f\n",generation,average,currentbest.value);
}
void main()
{
	int i;
    printf("本程序為求shaffer's F6函數的最大值\n");
    printf("其中-10.0<x,y<10.0\n");   /**/
	input();
    generation=0;
    generateinitialpopulation();
	evaluatepopulation();
	while(generation<maxgeneration)
	{
		generation++;
        copy();
		crossover();
		evaluatepopulation();
		for(i=0;i<cksize;i++)
		{
            copyone[generation][i]=population[generation][i];
		}
		select();
		performevolution();
		output();
		if(population[generation]==population[generation-1])
		{
			d==d-1;
		   if(d<0)
		   {
			   partinitial();
			   d==(R*(1-R)*L);
		   }
		}
		else
		{
			 generateinitialpopulation();
			 evaluatepopulation();
		}
	}
	printf("\n");
	printf("統計結果:\n");
    printf("最大函數值等于：%f\n",currentbest.value);
}