#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "UTLab.h"
#define N 32//每个染色体的基因数
//#define W 100//试卷总分值 
#define TYPE -1//题型数量
//#define M 2 //目标数目
//#define TYPE -1//求最大还是求最小
#define GEN 100//迭代次数
#define POP_SIZE 30//种群大小
#define SELECTQUE_SIZE 250 //选择题题库总量
#define TKQUE_SIZE 200 //填空题题库总量
#define ZHGQUE_SIZE 50  //主观题题库总量
#define NUM 4//题目特征数目
#define NUMCH 6//章节数目
#define NUMD 3//难度数目
#define DRATE1 0.2 //难度系数为1的预定义比率
#define DRATE2 0.6
#define DRATE3 0.2
#define CHRATE1 0.1//预定义每章的分值比率
#define CHRATE2 0.2
#define CHRATE3 0.2
#define CHRATE4 0.2
#define CHRATE5 0.2
#define CHRATE6 0.1
#define RCH 0.5
#define RD 0.5
#define P_MUTATION 0.008//变异系数
#define P_CROSSOVER 0.8//交叉系




double OBJECTIVE[POP_SIZE+1];
double DRATE[NUMD+1]={0,DRATE1,DRATE2,DRATE3};	//预定义难度系数比例
double CHRATE[NUMCH+1]={0,CHRATE1,CHRATE2,CHRATE3,CHRATE4,CHRATE5,CHRATE6};//预定义章节比
double  CHROMOSOME[POP_SIZE+1][N+1];//染色体数组
double  q[POP_SIZE+1];//存储选题到的题号的数组
int  SELECTQUESTION[SELECTQUE_SIZE+1][NUM];//选择题题库;1/分值；2、章节；3、难度；
int  TKQUESTION[TKQUE_SIZE+1][NUM];//填空题题库;1/分值；2、章节；3、难度；
int  ZHGQUESTION[ZHGQUE_SIZE+1][NUM];//主观题题库;1/分值；2、章节；3、难度；




static double caucal(double x[]); //计算新染色体的章节和难度比
static void  initialquestion(void);//初始化题库
static void  initialrate(void);//初始化各比例
static void  initialization(void);//初始化
static void  evaluation(int gen);
static void objective_function(void);
static void  selection(void);
static void  crossover(void);
static void  mutation(void);
static int   constraint_check(double x[]);


static double caucal(double x[])
{int i,j,t,s,m;
	double chrate[NUMCH+1],drate[NUMD+1];//定义各章节分值比和难度比
	double da=0;
	double ba=0;
  for (j=0;j<=NUMCH;j++)
	  {chrate[j]=0;}
  
  for (j=0;j<=NUMD;j++)
	  {drate[j]=0;}
	
	   for(j=1;j<=30;j++)
	   {t=int(x[j]);
	    if(j<=15)
		{
		  s=SELECTQUESTION[t][2];
		  chrate[s]+=2;
          m=SELECTQUESTION[t][3];
		  drate[m]+=2;
		}
		  else if(j>15&&j<=25)
           {
			   s=TKQUESTION[t][2];
		       chrate[s]+=2;
                m=TKQUESTION[t][3];
		        drate[m]+=2;
		  }
		    else
				{s=ZHGQUESTION[t][2];
		         chrate[s]+=10;
                 m=ZHGQUESTION[t][3];
		         drate[m]+=10;
			    }
	   }  
       for(j=1;j<=NUMCH;j++)
	   {chrate[j]=chrate[j]/100;
	    //printf("第%d个染色体第%d章的分值比是%f\n",i,j,chrate[i][j]);
	    ba+=fabs(double(chrate[j]-CHRATE[j]));
		}
	    //printf("第个染色体章的分值比平均值%f\n",ba/NUMCH);
        x[31]=ba/NUMCH;
       for(j=1;j<=NUMD;j++)
       {drate[j]=drate[j]/100;
	    //printf("第%d个染色体第%d难度的分值比是%f\n",i,j,drate[i][j]);
	    da+=fabs(double(drate[j]-DRATE[j]));
	   }
       //printf("第染色体难度差的平均值是%f\n",da/NUMD);
       x[32]=da/NUMD;
	   return RCH*x[31]+RD*x[32];
	   
   
 }
static void objective_function(void)
{
	
	int i;
	for(i = 1; i <= POP_SIZE; i++) {
		
		OBJECTIVE[i] =RCH*CHROMOSOME[i][31]+RD*CHROMOSOME[i][32];
		
}
}

static void  initialquestion(void)
{ int i,j;
  for(i=1;i<=SELECTQUE_SIZE+1;i++)//将选择题输入题库
	  for(j=1;j<=NUM;j++)
	  {
	   if(j==1)SELECTQUESTION[i][j]=2;
	   if(j==2)SELECTQUESTION[i][j]=int(myu(1,7));
	   if(j==3)SELECTQUESTION[i][j]=int(myu(1,4));
	  }
  for(i=1;i<=TKQUE_SIZE+1;i++)//将填空题输入题库
	  for(j=1;j<=NUM;j++)
	   {
	   if(j==1)TKQUESTION[i][j]=2;
	   if(j==2)TKQUESTION[i][j]=int(myu(1,7));
	   if(j==3)TKQUESTION[i][j]=int(myu(1,4));
	  }
		  
  for(i=1;i<=ZHGQUE_SIZE+1;i++)//将填空题输入题库
	  for(j=1;j<=NUM;j++)
	 {
	   if(j==1)ZHGQUESTION[i][j]=10;
	   if(j==2)ZHGQUESTION[i][j]=int(myu(1,7));
	   if(j==3)ZHGQUESTION[i][j]=int(myu(1,4));
	  }
}


static void  initialrate(void)//初始化章节和难度比例
{   int i,j,t,s,x;
	double chrate[POP_SIZE+1][NUMCH+1],drate[POP_SIZE+1][NUMD+1];//定义各章节分值比和难度比
	double da=0;
	double ba=0;


	for (i=1;i<=POP_SIZE;i++)
  {for (j=1;j<=NUMCH;j++)
	  {chrate[i][j]=0;}
  }
    for (i=1;i<=POP_SIZE;i++)
  {for (j=1;j<=NUMD;j++)
	  {drate[i][j]=0;}
  }


	for(i=1; i<=POP_SIZE; i++)
   {
	   for(j=1;j<=30;j++)
	   {t=CHROMOSOME[i][j];
	    if(j<=15)
		{
		  s=SELECTQUESTION[t][2];
		  chrate[i][s]+=2;
          x=SELECTQUESTION[t][3];
		  drate[i][x]+=2;
		}
		  else if(j>15&&j<=25)
           {
			   s=TKQUESTION[t][2];
		       chrate[i][s]+=2;
                x=TKQUESTION[t][3];
		        drate[i][x]+=2;
		  }
		    else
				{s=ZHGQUESTION[t][2];
		         chrate[i][s]+=10;
                 x=ZHGQUESTION[t][3];
		         drate[i][x]+=10;
			    }
	   }  
       for(j=1;j<=NUMCH;j++)
	   {chrate[i][j]=chrate[i][j]/100;
	    //printf("第%d个染色体第%d章的分值比是%f\n",i,j,chrate[i][j]);
	    ba+=fabs(double(chrate[i][j]-CHRATE[j]));
		}
	    //printf("第%d个染色体章的分值比平均值%f\n",i,ba/NUMCH);
        CHROMOSOME[i][31]=ba/NUMCH;
		ba=0;
       for(j=1;j<=NUMD;j++)
       {drate[i][j]=drate[i][j]/100;
	    //printf("第%d个染色体第%d难度的分值比是%f\n",i,j,drate[i][j]);
	    da+=fabs(double(drate[i][j]-DRATE[j]));
	   }
       //printf("第%d个染色体难度差的平均值是%f\n",i,da/NUMD);
       CHROMOSOME[i][32]=da/NUMD;
	   da=0;
   
 }
}


static void initialization(void)//初始化染色体操作
{
   int i,j;
  
  for(i=1; i<=POP_SIZE; i++)//初始化染色体，待讨论!
  {
	  for(j=1;j<=15;j++)//选择选择题
          CHROMOSOME[i][j]=int(myu(1,SELECTQUE_SIZE+1));
	  for(j=16;j<=25;j++)//选择填空题
          CHROMOSOME[i][j]=int(myu(1,TKQUE_SIZE+1));
	  for(;j<=30;j++)//select postive question
		  CHROMOSOME[i][j]=int(myu(1,ZHGQUE_SIZE+1));
  }
   
}

  static int constraint_check(double x[])
{
	int n; 
	for(n=1;n<=30;n++) if(x[n]<=0) return 0;
	return 1;
  }
  
	    



 void main()
 {
   int i, j,t,k;
   double a;
   q[0]=0.05; a=0.05;//定义的比率
  for(i=1; i<=POP_SIZE; i++) {a=a*0.95; q[i]=q[i-1]+a;}
   initialquestion();
   initialization();
   initialrate();
   evaluation(0);
	
    for(i=1; i<=GEN; i++) {
	  selection();
	  crossover();
	  mutation();
	  evaluation(i);
	  t=1; k=1;
	  for(j=1;j<=POP_SIZE;j++)
		  if(t>RCH*CHROMOSOME[j][31]+RD*CHROMOSOME[j][32])
		  {
			  t=RCH*CHROMOSOME[j][31]+RD*CHROMOSOME[j][32];
			  k=j;

		  }
		  printf("第%d代的最佳章节比是%f,最佳难度比是%f\n",i,CHROMOSOME[k][31],CHROMOSOME[k][32]);

  }


	 printf("题号	分值	章节	难度\n");
	  for(i=1; i<=1; i++)//输出生成的试卷
		  for(j=1;j<=30;j++)
		  {t=CHROMOSOME[i][j];
		   
		    if(j<=15)
			{   printf("%d\t",t);
				for(k=1;k<NUM;k++)
			   printf("%d\t",SELECTQUESTION[t][k]);
			   printf("\n");
			}
			  else if(j>15&&j<=25)
			  {   printf("%d\t",t);
				for(k=1;k<NUM;k++)
			  printf("%d\t",TKQUESTION[t][k]);
			   printf("\n");
			  }
			  else
				  {   printf("%d\t",t);
				for(k=1;k<NUM;k++)
			   printf("%d\t",ZHGQUESTION[t][k]);
			   printf("\n");
			}
		  }
		  a=0;
		  for(i=1;i<=POP_SIZE;i++)
			  a+=(1-RCH*CHROMOSOME[i][31]+RD*CHROMOSOME[i][32]);
		  printf("最佳适应度为%f\n",a/0.3);
 }
static void evaluation(int gen)
{
  double a;
  int   i, j, label;
  objective_function();//计算目标函数值
  if(gen==0){
	  OBJECTIVE[0]=OBJECTIVE[1];
	 for(j = 1; j <= N; j++) CHROMOSOME[0][j]=CHROMOSOME[1][j];
  }
  for(i=0; i<POP_SIZE; i++){
	  label=0;  a=OBJECTIVE[i];
	  for(j=i+1; j<=POP_SIZE; j++)
		 if((TYPE*a)<(TYPE*OBJECTIVE[j])) {
			 a=OBJECTIVE[j];
			 label=j;
		 }
	  if(label!=0) {
		 {
			 a=OBJECTIVE[i];
			 OBJECTIVE[i]=OBJECTIVE[label];
			 OBJECTIVE[label]=a;
		 }
		 for(j=1; j<=N; j++) {
			 a=CHROMOSOME[i][j];
			 CHROMOSOME[i][j]=CHROMOSOME[label][j];
			 CHROMOSOME[label][j]=a;
		 }
	  }
  }
}



static void selection()
{
  double r, temp[POP_SIZE+1][N+1];
  int   i, j, k;
  for(i=1; i<=POP_SIZE; i++) {
	  r=myu(0, q[POP_SIZE]);
	  for(j=0; j<=POP_SIZE; j++) {
		  if(r<=q[j]) {
			  for(k=1; k<=N; k++) temp[i][k]=CHROMOSOME[j][k];
			  break;
		  }
	  }
  }
  for(i=1; i<=POP_SIZE; i++)
	 for(k=1; k<=N; k++)
		 CHROMOSOME[i][k]=temp[i][k];
}




static void crossover()
{
  int   i, j, jj, k, pop;
  double a,r;
  double x[N+1], y[N+1];
  pop=POP_SIZE/2;
  for(i=1; i<=pop; i++) {
	 if(myu(0,1)>P_CROSSOVER) continue;
	 j=(int)myu(1,16);
	 jj=(int)myu(1,16);
	 r=myu(0,1);
	 for(k=1; k<=15; k++) {
		 x[k]=int(r*CHROMOSOME[j][k]+(1-r)*CHROMOSOME[jj][k])%(SELECTQUE_SIZE+1);
		 y[k]=int(r*CHROMOSOME[jj][k]+(1-r)*CHROMOSOME[j][k])%(SELECTQUE_SIZE+1);
	 }
	 j=(int)myu(16,26);
	 jj=(int)myu(16,26);
	 r=myu(0,1);
	 for(k=16; k<=26; k++) {
		 x[k]=int(r*CHROMOSOME[j][k]+(1-r)*CHROMOSOME[jj][k])%(TKQUE_SIZE+1);
		 y[k]=int(r*CHROMOSOME[jj][k]+(1-r)*CHROMOSOME[j][k])%(SELECTQUE_SIZE+1);
	 }
	 j=(int)myu(26,31);
	 jj=(int)myu(26,31);
	 r=myu(0,1);
	 for(k=26; k<=30; k++) {
		 x[k]=int(r*CHROMOSOME[j][k]+(1-r)*CHROMOSOME[jj][k])%(ZHGQUE_SIZE+1);
		 y[k]=int(r*CHROMOSOME[jj][k]+(1-r)*CHROMOSOME[j][k])%(ZHGQUE_SIZE+1);
	 }
	  a=caucal(x);
	 if((constraint_check(x)==1)&&a<=(RCH*CHROMOSOME[j][31]+RD*CHROMOSOME[j][32]))
		 for(k=1; k<=N; k++) CHROMOSOME[j][k]=x[k];
	a=caucal(y);
	 if((constraint_check(y)==1)&&a<=(RCH*CHROMOSOME[jj][31]+RD*CHROMOSOME[jj][32]))
		 for(k=1; k<=N; k++) CHROMOSOME[jj][k]=y[k];
  }
}
static void mutation(void)
{
  int i, j, k;
  double x[N+1], y[N+1], infty, direction[N+1],a;
  double INFTY=10, precision=0.0001;
  for(i=1; i<=POP_SIZE; i++) {
	  if(myu(0,1)>P_MUTATION) continue;
	  for(k=1; k<=N; k++) x[k] = CHROMOSOME[i][k];
	  for(k=1; k<=30; k++)
		  if(myu(0,1)<0.5) direction[k]=myu(-1,1);
		  else direction[k]=0;
	  infty=myu(0,INFTY);
	  while(infty>precision) {
		  for(j=1; j<=30; j++) y[j]=int(x[j]+infty*direction[j]);
		  a=caucal(y);
		  if(constraint_check(y)==1&&a<=(RCH*CHROMOSOME[i][31]+RD*CHROMOSOME[i][32])) {
			 for(k=1; k<=N; k++) CHROMOSOME[i][k]=y[k];
			 break;
		  }
		  infty=myu(0,infty);
	  }
  }
}