#include <iostream>
#include "UTLab.h"

using namespace std;

void  initialization(void);
void  evaluation(void);
void  selection(void);
void  crossover(void);
void  mutation(void);
void  objective_function(int);

#define N 8                  // 工件数量 
#define M 3                   // 机器数量 
#define O 2                   // 目标值数量 
#define GEN 200               // 繁殖代数 
#define POP_SIZE 500          // 种群规模 
#define P_MUTATION 0.3        // 变异概率 
#define P_CROSSOVER 0.1       // 交叉概率 
#define SIM 10000              // 模拟次数 
#define A 0.05                // 评价函数参数 
#define B1 0                  // 目标值参数
#define B2 45                 // 目标值参数
#define ALPHA1 0.95           // 目标值参数
#define ALPHA2 0.90           // 目标值参数 

static int  CHROMOSOMEX[POP_SIZE][N+1];               //工件 
static int  CHROMOSOMEY[POP_SIZE][M+1];             //机器
static double  OBJECTIVE[POP_SIZE][O];              //目标值  
static double  q[POP_SIZE];                         //计算选择的参数 
static double  TIME[N][M][4]= {{{10,11,14,16},{11,12,14,15},{12,13,15,17}},{{10,13,16,18},{10,11,15,16},{12,13,14,18}},{{12,14,15,16},{11,13,14,16},{12,15,16,18}},{{18,21,22,24},{20,21,22,23},{20,23,24,25}},{{10,12,13,15},{12,14,15,17},{10,12,13,15}},{{10,14,15,18},{12,13,16,17},{12,16,17,20}},{{10,11,12,16},{10,11,12,14},{10,11,12,13}},{{15,17,18,20},{14,15,16,20},{12,14,15,16}}};
//static double  TIME[N][M][4]= {{{10,11,14,16},{11,12,14,15},{12,13,15,17}},{{10,13,16,18},{10,11,15,16},{12,13,14,18}},{{12,14,15,16},{11,13,14,16},{12,15,16,18}},{{18,21,22,24},{20,21,22,23},{20,23,24,25}},{{10,12,13,15},{12,14,15,17},{10,12,13,15}},{{10,14,15,18},{12,13,16,17},{12,16,17,20}},{{10,11,12,16},{10,11,12,14},{10,11,12,13}},{{15,17,18,20},{14,15,16,20},{12,14,15,16}},{{10,12,13,17},{10,16,17,20},{10,11,12,13}},{{10,11,12,13},{15,17,18,19},{10,11,13,15}}};
//加工时间矩阵 
static double  DUE[N]={30,150,105,130,60,30,75,50};
//static double  DUE[N]={30,150,105,130,60,30,75,50,60,25};
//计划完成时间 

static double pt[N]; //序列中的工件完工时间 
static double obj1[SIM+1]; //目标值1模拟循环向量 
static double obj2[SIM+1]; //目标值2模拟循环向量 
static double m[SIM+1]; //计算模拟的隶属度向量 
static double mm[N];   //计算单个染色体的每个工序完成时间的隶属度向量
static  int tempx[POP_SIZE][N], tempy[POP_SIZE][M+1]; //选择过程中用以复制 
static  double tempo[POP_SIZE][O]; //选择过程中用以复制  
 
 
void objective_function(int i)//计算第i个染色体的目标值 
{
        int j; //一般循环参数
        int l; //模拟循环参数 
        /*
        double * pt= new double[N]; //序列中的工件完工时间 
        double * obj1=new double[SIM+1]; //目标值1模拟循环向量 
        double * obj2=new double[SIM+1]; //目标值2模拟循环向量 
        double * m=new double[SIM+1]; //计算模拟的隶属度向量 
        double * mm=new double[N];   //计算单个染色体的每个工序完成时间的隶属度向量
        */ 
		for(l=1; l<=SIM; l++)//模拟循环 
        {
                 for(j=1; j<M+1; j++) //便利机器序列 
                 {
                          int k;
                          double ptm=0;
                          for(k=CHROMOSOMEY[i][j-1]; k<CHROMOSOMEY[i][j]; k++) //确定在第j个机器上运行的任务序号 
                          {
                                  double temp=myu(TIME[CHROMOSOMEX[i][k]-1][j-1][0],TIME[CHROMOSOMEX[i][k]-1][j-1][3]);
                                  //随机产生第k个工件在第j个机器上的运行时间 
				                  mm[k]=trapezoidal(temp, TIME[CHROMOSOMEX[i][k]-1][j-1][0],TIME[CHROMOSOMEX[i][k]-1][j-1][1],TIME[CHROMOSOMEX[i][k]-1][j-1][2],TIME[CHROMOSOMEX[i][k]-1][j-1][3]);
                                  //计算上述运行时间的隶属度 
                                  ptm=ptm+temp;
                                  //整个机器的加工时间 
                                  pt[k]=ptm;
                                  //x序列中第k个工件的完工时间 
                           }   
                 }
                 obj1[l]=0;
                 obj2[l]=0;
                 for(j=0; j<N; j++)
                 {
                          if(pt[j]-DUE[CHROMOSOMEX[i][j]-1]>obj1[l])  //CHROMOSOMEX[i][j]是第i个染色体x序列中第k个工件对应的工件编号 
                                  obj1[l]=pt[j]-DUE[CHROMOSOMEX[i][j]-1];
                          if(pt[j]>obj2[l])
                                  obj2[l]=pt[j];
                 }
		         m[l]=mm[0];
		         for(j=1; j<N; j++) //计算单个染色体一次模拟中的隶属度 
		                 if(mm[j]<m[l]) m[l]=mm[j];
        }
	    OBJECTIVE[i][0]=fuzzypessimistic(obj1,m,SIM,ALPHA1)-B1;
	    if(OBJECTIVE[i][0]<0) OBJECTIVE[i][0]=0;
	    OBJECTIVE[i][1]=fuzzypessimistic(obj2,m,SIM,ALPHA2)-B2;
	    if(OBJECTIVE[i][0]<0) OBJECTIVE[i][0]=0;
/*
		delete[]pt;
		delete[]obj1;
		delete[]obj2;
		delete[]m;
		delete[]mm;
*/
}

	
void initialization(void)                     //初始化 
{
    double * a=new double[POP_SIZE];
    double b=0;
    int i;
    for(i=0; i<POP_SIZE; i++)
    { 
        a[i]=A*pow((1-A),i);                  //计算选择矩阵 
        b=b+a[i];
        q[i]=b;
         
        int j;
        for(j=0; j<N; j++)                    //初始化x部分 
            CHROMOSOMEX[i][j]=j+1;
        random_shuffle(&CHROMOSOMEX[i][0],&CHROMOSOMEX[i][N]);
        
        CHROMOSOMEY[i][0]=0;                   //初始化y部分 
        CHROMOSOMEY[i][M]=N;
        for(int j=1; j<M; j++)                 
            CHROMOSOMEY[i][j] = int(myu(0,N+0.99));
        sort(CHROMOSOMEY[i], CHROMOSOMEY[i]+M);

        objective_function(i);                  //计算 目标函数值 
    }
    delete[]a;
}


void evaluation(void)                           //种群排序 
{
  double a,b;
  int   i, j, k, label,c;

  for(i=0; i<POP_SIZE; i++)
  {
	  label=0;  a=OBJECTIVE[i][0];  b=OBJECTIVE[i][1];
	  for(j=i+1; j<POP_SIZE; j++)                //排泡法确定位置 
	  {
		 if(a>OBJECTIVE[j][0]) 
         {
			 a=OBJECTIVE[j][0];
			 label=j;
		 }
		 if(a==OBJECTIVE[j][0])
		 {
		     if(b>OBJECTIVE[j][1])
		     {
		         b=OBJECTIVE[j][1];
		         label=j;
		     }
         }        
	  }
    		 
	  if(label!=0)                               //交换位置 
      {
		 for(k=0; k<O; k++)
         {
			 a=OBJECTIVE[i][k];
			 OBJECTIVE[i][k]=OBJECTIVE[label][k];
			 OBJECTIVE[label][k]=a;
		 }
		 for(j=0; j<N; j++)
         {
			 c=CHROMOSOMEX[i][j];
			 CHROMOSOMEX[i][j]=CHROMOSOMEX[label][j];
			 CHROMOSOMEX[label][j]=c;
		 }
		 for(j=1; j<M; j++)
		 {
		     c=CHROMOSOMEY[i][j];
			 CHROMOSOMEY[i][j]=CHROMOSOMEY[label][j];
			 CHROMOSOMEY[label][j]=c;
		 }    
	  }
  }
}


void selection()                                     //选择 
{
  double r;
  /*
  int * tempx=new int[POP_SIZE][N]
  int * tempy=new int[POP_SIZE][M+1];
  double * tempo=new double[POP_SIZE][O];
  */
  int   i, j, k;
  for(i=0; i<POP_SIZE; i++)                          //轮盘赌 
  {
	  r=myu(0, q[POP_SIZE-1]);
	  for(j=0; j<POP_SIZE; j++) 
      {
		  if(r<=q[j]) 
          {
			  for(k=0; k<N; k++) tempx[i][k]=CHROMOSOMEX[j][k];
			  for(k=1; k<M; k++) tempy[i][k]=CHROMOSOMEY[j][k];
			  for(k=0; k<O; k++) tempo[i][k]=OBJECTIVE[j][k];
			  break;
		  }
	  }
  }
  for(i=0; i<POP_SIZE; i++)
  {
	 for(k=0; k<N; k++)
		 CHROMOSOMEX[i][k]=tempx[i][k];
	 for(k=1; k<M; k++)
	     CHROMOSOMEY[i][k]=tempy[i][k];
     for(k=0; k<O; k++)
         OBJECTIVE[i][k]=tempo[i][k];
  }
  /*
  delete[]tempx;
  delete[]tempy;
  delete[]tempo;
  */
}

void crossover()                                             //交叉 
{
  int   i, j, jj, k, pop;
  int * x=new int[N];
  int * y=new int[M+1];
  pop=POP_SIZE/2;
  for(i=0; i<pop; i++) 
  {
	 if(myu(0,1)<=P_CROSSOVER) 
	 {	 
	    j=(int)myu(0,POP_SIZE-1);
	    jj=(int)myu(0,POP_SIZE-1);

	    for(k=1; k<M; k++)                                   //交换y部分 
        {
		         y[k]=CHROMOSOMEY[j][k];
                 CHROMOSOMEY[j][k]=CHROMOSOMEY[jj][k];
                 CHROMOSOMEY[jj][k]=y[k];
        }
	 objective_function(j);
	 objective_function(jj);
	 }
  }
  delete[]x;
  delete[]y;
}


void mutation(void)                                          //变异 
{
  int x1,x2,y1,y2;
  for(int i=0; i<POP_SIZE; i++) 
  {
	  if(myu(0,1)<=P_MUTATION) 
	  {
            x1=(int)myu(0,N-1);                            //x部分部分变异（可选） 
            x2=(int)myu(0,N-1);
            if(x1<x2)
                     random_shuffle(&CHROMOSOMEX[i][x1],&CHROMOSOMEX[i][x2]);
            else     random_shuffle(&CHROMOSOMEX[i][x2],&CHROMOSOMEX[i][x1]);

//            random_shuffle(&CHROMOSOMEX[i][0],&CHROMOSOMEX[i][N]);   //x部分全部变异    
            y1=(int)myu(1,M);                               //y部分变异 
            y2=(int)myu(y1,M);
            for(int k=y1; k<=y2; k++)
                    CHROMOSOMEY[i][k]=(int)myu(0,N+0.99);
            sort(CHROMOSOMEY[i],CHROMOSOMEY[i]+M);

            objective_function(i);                            //计算目标值 
	  }
  }
}


int main(int argc, char *argv[])
{

  initialization();
  evaluation();
  for(int x=1; x<=GEN; x++) {

	  selection();
	  crossover();
	  mutation();
	  evaluation();
	  
	  cout<<endl<<x<<" Generation OK"<<endl;

	  for(int q=0; q<N; q++)                                  //输出本轮最佳染色体及目标值 
	  cout<<CHROMOSOMEX[0][q]<<" ";
	  cout<<endl;
	  for(int q=0; q<M+1; q++)
	  cout<<CHROMOSOMEY[0][q]<<" ";
	  cout<<endl;
	  for(int q=0; q<O; q++)
	  cout<<OBJECTIVE[0][q]<<endl;
	  cout<<endl;
/*	  
	  for(int q=0; q<N; q++)                                  //输出本轮最差染色体及目标值 
	  cout<<CHROMOSOMEX[POP_SIZE-1][q]<<" ";
	  cout<<endl;
	  for(int q=0; q<M+1; q++)
	  cout<<CHROMOSOMEY[POP_SIZE-1][q]<<" ";
	  cout<<endl;
	  for(int q=0; q<O; q++)
	  cout<<OBJECTIVE[POP_SIZE-1][q]<<endl;	  
*/
  }
  
  system("PAUSE");	
  return 1;
}