//Project Scheduling Problem
//Compiled by Microsoft Visual C++6.0
//Written by Xin Gao in 2009
//Copyright by Uncertainty Theory Laboratory
#include<iostream>
#include <iomanip> 
#include<cmath>
#include "UTLab.h"

using namespace std;

const int TYPE=-1; // 1=max;-1=min
const int GEN=6000; // maximum generation number
const int POP_SIZE=30; // population size 
const double P_MUTATION=0.3; // probability of mutation 
const double P_CROSSOVER=0.8; // probability of crossover
const double alpha=0.85;
const int N=7;

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

int Nodes[9][100];
int T0=53;//due date of the project
int Note[12]={0,12,13,14,25,35,36,37,47,58,68,78};
double cost[100];
double arcs[12][100];
void arcsTable() // table of arcs by 99 method
{
	int a,b;
	for(int i=1;i<=11;i++){
		a=Note[i]/10;
		b=Note[i]%10;
		for(int j=1;j<=99;j++){
			arcs[i][j]=(1-(double)j/100)*a+(double)j/100*b;
			arcs[i][j]=3*arcs[i][j];
		}
	}
}

void nodesTable(int*x)
{
	int i,j;
	double x1[8];
	for(i=1; i<8; i++)
		x1[i]=(double)x[i];

	for(i=1;i<=99;i++){
		Nodes[1][i]=x1[1];
	}
	for(i=1;i<=99;i++){
		Nodes[2][i]=(x1[2]<(x1[1]+arcs[1][i]))?(x1[1]+arcs[1][i]):x1[2];	
	}
    for(i=1;i<=99;i++){
		Nodes[3][i]=(x1[3]<(x1[1]+arcs[2][i]))?(x1[1]+arcs[2][i]):x1[3];	
	}
	for(i=1;i<=99;i++){
		Nodes[4][i]=(x1[4]<(x1[1]+arcs[3][i]))?(x1[1]+arcs[3][i]):x1[4];	
	}
	for(i=1;i<=99;i++){
		if (Nodes[2][i]+arcs[4][i]>Nodes[3][i]+arcs[5][i])
			Nodes[5][i]=Nodes[2][i]+arcs[4][i];
		else Nodes[5][i]=Nodes[3][i]+arcs[5][i];
		if (Nodes[5][i]<x1[5])
			Nodes[5][i]=x1[5];
	}
	for(i=1;i<=99;i++){
		Nodes[6][i]=(x1[6]<(Nodes[3][i]+arcs[6][i]))?(Nodes[3][i]+arcs[6][i]):x1[6];	
	}
	for(i=1;i<=99;i++){
		if (Nodes[3][i]+arcs[7][i]>Nodes[4][i]+arcs[8][i])
			Nodes[7][i]=Nodes[3][i]+arcs[7][i];
		else Nodes[7][i]=Nodes[4][i]+arcs[8][i];
		if (Nodes[7][i]<x1[7])
			Nodes[7][i]=x1[7];
	}
	for(i=1;i<=99;i++){
		if (Nodes[5][i]+arcs[9][i]>Nodes[6][i]+arcs[10][i])
			Nodes[8][i]=Nodes[5][i]+arcs[9][i];
		else Nodes[8][i]=Nodes[6][i]+arcs[10][i];
		if (Nodes[8][i]<Nodes[7][i]+arcs[11][i])
			Nodes[8][i]=Nodes[7][i]+arcs[11][i];
	}
}

void costTable(int*x) 
{
	int a,b;
	double sum;
	for(int j=1;j<=99;j++){
		sum=0;
		for(int i=1;i<=11;i++){
			a=Note[i]/10;
			b=Note[i]%10;
			sum+=(a+b)*pow(1.02,ceil(Nodes[8][j]-x[a]));
		}
		cost[j]=sum;
	}
}


int check(int*x)
{
	int a;
	
	int test_temp;

	for(int i=1;i<=N;i++)
	{
		if(x[i]<0)
	 		return 0;
		if(x[2]<x[1])
			return 0;
		if(x[3]<x[1])
			return 0;
		if(x[4]<x[1])
			return 0;
		if(x[5]<x[2])
			return 0;
		if(x[5]<x[3])
			return 0;
		if(x[6]<x[3])
			return 0;
		if(x[7]<x[3])
			return 0;
		if(x[7]<x[4])
			return 0;
	}
	nodesTable(x);
	if(Nodes[8][99]<T0)
{           
		return 1;
        }
	for (int j=1;j<=99;j++)
	{
		if(Nodes[8][j]>=T0)
		{
			double temp =(double)j/100;
				if (temp>=alpha){
				return 1;
			}

			else 
				return 0;
		}

	}	

}


static void objective_function()
{
	int i,j;
	double sum=0;
	for(i=1;i<=POP_SIZE;i++) {
		sum=0;
		nodesTable(CHROMOSOME[i]);
		costTable(CHROMOSOME[i]);
		for(j=1;j<=99;j++){
			sum+=cost[j];
		}
		OBJECTIVE[i]=sum/99.;
	}
}


static void  initialization()
{
	int x[N+1]; 
	int i=1,j,a;
	for (i=1;i<=POP_SIZE;i++)
	{
		a=1;
			while(a){	
			for (j=1;j<=N;j++)
			{
            	CHROMOSOME[i][j]=myu(0,70);
			}
        	if(1==check(CHROMOSOME[i]))
				a=0;
		}
	}
}
	
static void evaluation(int gen)
{
	double a,cost0,cost1;
	int i,j,k,label;
	objective_function();
	if(gen==0){
		OBJECTIVE[0]=OBJECTIVE[1];
		for(j=1;j<=N;j++) CHROMOSOME[0][j]=CHROMOSOME[1][j];
	}
	for(i=1;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(k=1;k<=N;k++) {
					a=CHROMOSOME[i][k];
					CHROMOSOME[i][k]=CHROMOSOME[label][k];
					CHROMOSOME[label][k]=a;
				}
			}
		}
	}
	if(TYPE*OBJECTIVE[0]<TYPE*OBJECTIVE[1]){
		OBJECTIVE[0]=OBJECTIVE[1];
		OBJECTIVE[label]=a;
		for(j=1;j<=N;j++)
			CHROMOSOME[0][j]=CHROMOSOME[1][j];
	}
}


static void selection()
{
	double r;
	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,r;
	int 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,POP_SIZE);
		jj=(int)myu(1,POP_SIZE);
		r=(int)myu(1,N+1);
		for(k=1;k<=N;k++){
			if(k<=r){
				x[k]=CHROMOSOME[j][k];
				y[k]=CHROMOSOME[jj][k];
			}
			if(k>r){
				x[k]=CHROMOSOME[jj][k];
				y[k]=CHROMOSOME[j][k];
			}
		}
		if(check(x)==1){
			for(k=1;k<=N;k++) CHROMOSOME[j][k]=x[k];
		}
		if(check(y)==1){
			for(k=1;k<=N;k++) CHROMOSOME[jj][k]=y[k];
		}
	}
}

static void mutation()
{	
	int i,j,k;
	int x[N+1],y[N+1],direction[N+1];
	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<=N;k++){
			if(myu(0,1)<0.5) 
				direction[k]=(int)myu(-2,2);
			else
				direction[k]=0;
		}
		for(j=1;j<=N;j++) y[j]=x[j]+direction[j];
		if(check(y)==1){
			for(k=1;k<=N;k++) CHROMOSOME[i][k]=y[k];
			break;
		}
	}
}




int main()
{
	arcsTable();
	
	int i,j;
	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);
	}
	a=0;
	cout<<"(";
	for(i=1;i<=N;i++)
	{
	cout<<CHROMOSOME[0][i]<<" ";
	}
	cout<<")"<<endl;

	cout<<"The expected total cost is :  "<<OBJECTIVE[0]<<endl;
    nodesTable(CHROMOSOME[0]);
    costTable(CHROMOSOME[0]);
		
	for(i=1;i<=99;i++)
	{
		if(Nodes[8][i]>T0){
			cout<<"M  <=  "<<(i-1)/100.0<<endl;
			break;
		}
	}
  
	
	return 1;
}