// Written by Microsoft Visual C++
// Copyright by UTLab @ Tsinghua University
// http://orsc.edu.cn/UTLab

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "UTLab.h"

static void  initialization(void);
static void  evaluation(int gen);
static void  selection(void);
static void  crossover(void);
static void  mutation(void);
static void  objective_function(void);
static int   constraint_check(int x[]);

#define N 5  
#define M 1  
#define TYPE 1 
#define GEN 1000 
#define POP_SIZE 30
#define P_MUTATION 0.2
#define P_CROSSOVER 0.3

int     CHROMOSOME[POP_SIZE+1][N+1];
double  OBJECTIVE[POP_SIZE+1][M+1];
double  q[POP_SIZE+1];

static void objective_function(void)
{
	int    x1,x2,x3,x4,x5;
    double y,y2;
	int    i,j,k;
	double T0=30;
    double a1,a2,a3,a4,a5;
    double b1,b2,b3,b4,b5;
	for(k = 1; k <= POP_SIZE; k++) {
		x1 = CHROMOSOME[k][1];
		x2 = CHROMOSOME[k][2];
		x3 = CHROMOSOME[k][3];
		x4 = CHROMOSOME[k][4];
		x5 = CHROMOSOME[k][5];
		y=0;
		for(j=1; j<=10000; j++) {
		
			a1=0;
			for(i=1;i<=x1;i++)a1 += myexp(20); 
			a2=0;
			for(i=1;i<=x2;i++)a2 += myexp(30);
			a3=0;
			for(i=1;i<=x3;i++){y2=myexp(40);if(a3<y2)a3=y2;}
			a4=0;
			for(i=1;i<=x4;i++){y2=myexp(50);if(a4<y2)a4=y2;}
			a5=0;
			for(i=1;i<=x5;i++){y2=myexp(60);if(a5<y2)a5=y2;}

			b1=a1;if(b1>a4)b1=a4;
			b2=a1;if(b2>a3)b2=a3;if(b2>a5)b2=a5;
			b3=a2;if(b3>a5)b3=a5;
			b4=a2;if(b4>a3)b4=a3;if(b4>a4)b4=a4;
			b5=b1;if(b5<b2)b5=b2;if(b5<b3)b5=b3;if(b5<b4)b5=b4;
			if(b5>T0) y +=1;
		};
		OBJECTIVE[k][1] = y/10000;
	}
	for(i=1;i<=POP_SIZE;i++)
	  OBJECTIVE[i][0]= OBJECTIVE[i][1];
}

static int constraint_check(int x[])
{
    if((50*x[1]+60*x[2]+70*x[3]+80*x[4]+90*x[5])>600) return 0;
	return 1;
}

static void initialization(void)
{
  int x[N+1]; 
  int i,j,jj;
  for(i=1; i<=POP_SIZE; i++){
	  mark:
  for(j=1; j<=N; j++)x[j]=1;
	  while(constraint_check(x) == 1){
 		  jj = (int)myu(1,6);
		  x[jj]=x[jj]+1;}
	  x[jj]=x[jj]-1;
	  for(j=1; j<=N; j++) CHROMOSOME[i][j]=x[j]; 
  }
}

static void evaluation(int gen)
{
  double a;
  int   i, j, k, a1, label;
  objective_function();
  if(gen==0){
	 for(k=0; k<=M; k++)     OBJECTIVE[0][k]=OBJECTIVE[1][k];
	 for(j = 1; j <= N; j++) CHROMOSOME[0][j]=CHROMOSOME[1][j];
  }
  for(i=0; i<POP_SIZE; i++){
	  label=0;  a=OBJECTIVE[i][0];
	  for(j=i+1; j<=POP_SIZE; j++)
		 if((TYPE*a)<(TYPE*OBJECTIVE[j][0])) {
			 a=OBJECTIVE[j][0];
			 label=j;
		 }
	  if(label!=0) {
		 for(k=0; k<=M; k++) {
			 a=OBJECTIVE[i][k];
			 OBJECTIVE[i][k]=OBJECTIVE[label][k];
			 OBJECTIVE[label][k]=a;
		 }
		 for(j=1; j<=N; j++) {
			 a1=CHROMOSOME[i][j];
			 CHROMOSOME[i][j]=CHROMOSOME[label][j];
			 CHROMOSOME[label][j]=a1;
		 }
	  }
  }
}

static void selection()
{
  double r;
  int    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, kk, pop, x[N+1], y[N+1];
  pop=POP_SIZE/2;
  for(i=1; i<=pop; i++) {
	 if(myu(0,1)>P_CROSSOVER) continue;
mark:
	 j=(int)myu(1,POP_SIZE);
	 jj=(int)myu(1,POP_SIZE);
	 for(k=1; k<=N; k++) {
		 x[k]=CHROMOSOME[j][k];y[k]=CHROMOSOME[jj][k];
	 }
	 j=(int)myu(1,6);jj=(int)myu(1,6);
     if(k>kk){pop=j;j=jj;jj=pop;}
     for(k=j;k<=jj;k++){pop=x[k];x[k]=y[k];y[k]=pop;}
     if(constraint_check(x)==0 && constraint_check(y)==0)goto mark;

	 if(constraint_check(x) == 1){
	 while(constraint_check(x) == 1){
 		  kk = (int)myu(1,6);
		  x[kk]=x[kk]+1;}
     x[kk]=x[kk]-1;
	 }
	 
	 if(constraint_check(y) == 1){
	 while(constraint_check(y) == 1){
		  kk = (int)myu(1,6);
		  y[kk]=y[kk]+1;
	  }
     y[kk]=y[kk]-1;
	 }
	 
	 while(constraint_check(x) == 0){
		  kk = (int)myu(1,6);
		  if(x[kk]>1)x[kk]=x[kk]-1;
	  };
	 
	 while(constraint_check(y) == 0){
		  kk = (int)myu(1,6);
		  if(y[kk]>1)y[kk]=y[kk]-1;
	  }
	 
	 for(k=1; k<=N; k++) {
		 CHROMOSOME[j][k] = x[k] ;CHROMOSOME[jj][k] = y[k];
	 }
  }
}

static void mutation(void)
{
  int i, j, jj, k, kk;
  int x[N+1];
  for(i=1; i<=POP_SIZE; i++) {
	  if(myu(0,1)>P_MUTATION) continue;
      j = (int)myu(1,POP_SIZE);
      for(k=1; k<=N; k++)x[k]=CHROMOSOME[j][k]; 
	  kk = (int)myu(1,7);
	  jj = (int)myu(1,6);
	  x[jj] = kk;
	  if(constraint_check(x) == 1){
	  while(constraint_check(x) == 1){
 		  jj = (int)myu(1,6);
		  x[jj]=x[jj]+1;}
	  x[jj]=x[jj]-1;
	  }
	  while(constraint_check(x) == 0){
		  jj = (int)myu(1,6);
		  if(x[jj]>1)x[jj]=x[jj]-1;
	  }
	  for(k=1; k<=N; k++)CHROMOSOME[j][k]=x[k];
  }
}

main()
{
  int i, j, 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;}
  initialization();
  evaluation(0);
  for(i=1; i<=GEN; i++) {
	  selection();
	  crossover();
	  mutation();
	  evaluation(i);
	  printf("\nGeneration NO.%d\n", i);
	  printf("x=(");
	  k=0;
	  for(j=1; j<=N; j++) {
		  if(j<N) printf("%d,",CHROMOSOME[0][j]);
		  else printf("%d",CHROMOSOME[0][j]);
		  k +=CHROMOSOME[0][j]*(40+10*j);
	  }
	  if(M==1) printf(")\ncost = %d\nf=%3.4f\n", k, OBJECTIVE[0][1]);
	  else {
	      printf(")\nf=(");
	      for(j=1; j<=M; j++) {
		     if(j<M) printf("%3.4f,", OBJECTIVE[0][j]);
		     else printf("%3.4f", OBJECTIVE[0][j]);
		  }
          printf(")  Aggregating Value=%3.4f\n",OBJECTIVE[0][0]);
	  }
  }
  printf("\n");
  return 1;
}