// GATest.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
//#include <GATest.h>
#include <stdio.h>
#include <iostream.h>
#include <math.h>
 #include <stdlib.h> 
#include <time.h> 


/*工件加工時間數組*/
int t[5][4]={{3,4,5,3},{9,5,8,3},{5,7,9,2},{2,5,9,1},{7,8,2,3}};
/*總體適應度值*/
float sumfit=0;  
int sumtime=0;   //種群總加工時間
/*染色體編碼*/
int vold[10][5];
int totaltime[10]; /*各染色體加工總時間*/
int waittime[10]={0,0,4,0,5,0,6,0,0,0};/*各染色體加工等待時間*/
float voldfitness[10]={0,0,0,0,0,0,0,0,0,0};   /*記錄染色體適應度*/
int comp;   /*記錄歷次迭代最優染色體的加工時間*/

struct chromnode    /*設計結構體使染色體和其適應度函數相關聯*/
{	
	int chrom[5]; 
	float fitness;
}bestchrom,wrostchrom;

chromnode chrompop[10];   /*種群數組*/
chromnode newchrompop[10];    /*新種群數組*/
chromnode midchrompop[7];/*迭代中間優等種群*/


int temp[5][4];  /*按染色體工件序列加工時間矩陣*/
int tstart[5][4];  /*按染色體工件序列開始加工時間矩陣*/
int tover[5][4];   /*按染色體工件序列結束加工時間矩陣*/
int mupos[4][2];   /*記錄染色體變異基因位位置*/

/*函數聲明部分*/
int rndom(); /*在整數low和high之間產生一個隨機整數*/
void randomsel(float* array,int num);     /*生成0－1之間的浮點數*/
void murandom(int posarray[1][2]);  /*產生二維隨機數組記錄染色體變異位置*/

void initialpop(int &v);    /*種群初始化*/
bool retreat(int i,int j);    /*查看染色體中是否有重復*/
int calcutime(int array[5][4]);    /*計算各染色體排列樹的相關加工時間*/

void copychrom(chromnode &chromx,chromnode &chromy);    /*將chromy復制到chromx*/
void dispchrom(chromnode node,FILE *fp);       /*輸出染色體的值*/
void dispchrompop(chromnode structarray[10],FILE *fp);       /*輸出各染色體種群中的所有染色體的值*/
void reversechrom(int array[5],int posx,int posy);   /*將兩個位置之間的染色體順序倒置*/
void chromsort(chromnode pop[10]);    /*對染色體種群進行排序*/
void relatearray(int testchr[5]);  /*按照染色體序列將加工時間數組重新排列*/
void calfitness(int array[10][5]);      /*以數組為參數計算種群適應度的值并排序*/
void calchromfit(chromnode pop[10]);    /*以種群為參數計算種群適應度值——calfitness，并排序*/
int fittotime(chromnode para);   /*求出染色體適應度的加工時間*/
void caloptchrompt(chromnode pop[10]);     /*求出種群中最優染色體*/

void preselect(double pmsum[10],double randarray[10],int sortarray[10]);   /*確定選擇染色體位置*/
void select(chromnode pop[10],chromnode subpop[10]);    /*選擇算子*/
void mutation(chromnode pop[1]);    /*變異算子*/
void generate(chromnode pop[10],chromnode subpop[10]);     /*迭代產生新一代種群*/



int max(int a,int b)
{
	if(a>=b)
		return a;
	else
		return b;
}

int min(int a,int b)
{
	if(a<=b)
		return a;
	else
		return b;
}


int rndom() /*在整數low和high之間產生一個隨機整數*/
{
     
     
     return (rand()%5+1) ;
	 
 
}

void randomsel(double* array,int num)
{
	for(int i = 0; i < num; i++) 
	{ 
	double fRand = (double)(rand()%1000)/1000 ;   //將隨機數映射到0 -- 1區間內
		array[i] = fRand; 

	} 


}

void murandom(int posarray[4][2])   /*產生二維隨機數組記錄染色體變異位置*/
{
	for(int i=0;i<4;i++)
	{
		int posx=0;
		int posy=0;
		while(posx==posy)
		{
			posx=rand()%5;
			posy=rand()%5;
		}
		posarray[i][0]=min(posx,posy);
		posarray[i][1]=max(posx,posy);
		
	}

}

bool retreat(int i,int j)    /*查看染色體中是否有重復*/
{
	for(int t = 0;t < j;t++)
		{
			int seek = vold[i][t];
			
			if(seek == vold[i][j])
			{
				return true;
			}
			 
         }
	return false;
}


int calcutime(int array[5][4])    /*計算各染色體排列樹的相關加工時間*/
{
	
	for(int m=0;m<5;m++)     /*計算機器加工工件的開始時間和結束時間*/
	{
		for(int n=0;n<4;n++)
			{
				   /*對每條染色體中的第一個工件的加工時間的計算*/
				
					if(m==0&&n==0)tstart[m][n]=0;      //機器最先開始時間為0
					
					if(m==0&&n>0)
					{
						tover[m][n-1] = tstart[m][n-1] + array[m][n-1];
						tstart[m][n] = tover[m][n-1];
						if(n==3)tover[m][n]=tstart[m][n]+array[m][n];

					}
					
					if(m>0&&n==0)
					{
						tstart[m][n]=tover[m-1][n];
						tover[m][n]=tstart[m][n]+array[m][n];   
					
					}
					
					
					if(m>0&&n>0)
					{
						tstart[m][n]=max(tover[m][n-1],tover[m-1][n]);    /*只有當此刻機器加工結束并且此刻需要加工的工件在前一個機器上已經加工完畢時才可以繼續加工*/
						tover[m][n]=tstart[m][n]+array[m][n];
					}

			}
			
		}

		int totaltime=tover[4][3];
		return totaltime;
		
}

int calwaittime(int array[5][4])
{
	int wtime=0;
	for(int i=0;i<5;i++)
	{
		for(int j=0;j<4;j++)
		{
			if(i>=1)
			{
				if(array[i-1][j+1] > array[i][j])
				wtime = wtime + array[i-1][j+1]-array[i][j];
			}
		}
	}

	return wtime;

}

void copychrom(chromnode &chromx,chromnode &chromy)    /*將chromy復制到chromx*/
{
	for(int w=0;w<5;w++)
	{
		chromx.chrom[w]=chromy.chrom[w];
	}
	chromx.fitness=chromy.fitness;
}


void reversechrom(int array[5],int posx,int posy)   /*將兩個位置之間的染色體順序倒置*/
{
	int temp;
	while(posx<=posy)
	{
		temp=array[posx];
		array[posx]=array[posy];
		posx++;
		array[posy]=temp;
		posy--;
	}
}


void chromsort(chromnode pop[10])    /*對染色體種群進行排序*/
{
	chromnode tpsn;    /*染色體交換中轉站*/
	for(int i=0;i<9; i++)
	{
		tpsn.fitness = pop[i].fitness ;
	
		for(int j=i+1;j<10;j++)
		{
			if(pop[i].fitness <= pop[j].fitness  )
			{	
				copychrom(tpsn,pop[j]);
				copychrom(pop[j],pop[i]);
				copychrom(pop[i],tpsn);
			}
		}
		
	}

}


void relatearray(int testchr[5])  /*按照染色體序列將加工時間數組重新排列*/
{
	for(int m=0;m<5;m++)
		{
			
			int tpos=testchr[m]-1;

			for(int n=0;n<4;n++)
			{					
				temp[m][n]=t[tpos][n];
				
			}

		}
     
}


void calfitness(int array[10][5])      /*以數組為參數計算種群適應度的值并排序*/
{
		int testchrom[5]={0,0,0,0,0};  /*存儲群體中的染色體序列*/
	

	for(int i=0;i<10;i++)
	{
		for(int j=0;j<5;j++)
		{
			testchrom[j]=array[i][j];
			relatearray(testchrom);   /*重組加工時間數組*/
			chrompop[i].chrom[j]=array[i][j];							/*將當前染色體序列復制到種群結構體*/
		}
			totaltime[i] = calcutime(temp);      /*計算當前染色體適應度（加工總時間）*/
			//waittime[i] = calwaittime(tover);
			voldfitness[i]=1/(float)totaltime[i];
			
	}
	chromsort(chrompop);

	
}


void calchromfit(chromnode pop[10])    /*以種群為參數計算種群適應度值——calfitness，并排序*/
{
	int dupli[10][5];
	for(int i=0;i<10;i++)
	{
		for(int j=0;j<5;j++)
		{
			dupli[i][j]=pop[i].chrom[j];
		}
	}
	calfitness(dupli);
	
	for(int k=0;k<10;k++)
	pop[k].fitness = voldfitness[k];
	/*for(int k=0;k<10;k++)
	{
		pop[k].fitness = float(100-voldfitness[k]*100);
		if(pop[k].fitness>80)pop[k].fitness-=10;
		else if(pop[k].fitness <50)pop[k].fitness+=10;

	}*/
	
}

int  fittotime(chromnode para)   /*求出染色體適應度的加工時間*/
{
	int stake[5];
	int time;
	for(int i=0;i<5;i++)