//if (c1.val <= P[p1].val)	//这里c1和p1还是和p2比较，待定！

#include <iostream>	
#include<time.h>
#define Pop 50					//初始种群中的个体数

#define Times 500			//循环次数
#define Job 50				//工件数 
#define Stg 2					//阶段数
#define Tim 2					//重入次数
#define Machine 5			//机器数
int stage_m[Stg] = { 2,3 };		//表示一次完整过程中，各个阶段的机器数

#define Crop    0.60            //交叉概率
#define Mutp    0.10			//变异概率	
#define random(X) (rand()%X)
double job_time[Job][Stg];					//表示工件各个阶段的加工时间,注意！是各个阶段，因为每个阶段的机器加工时间相等

int summ = 0;		//统计新个体的产生个数
double value[10] = { 0 };  //记录值
double total_time[10] = { 0 };	//记录时间
double best_value;
double worst_value;
double average_value;
double average_time;

time_t start, finish;		//统计运行时间

using namespace std;

struct individual
{
	double seq[Job];	//染色体
	double val;			//最大加工时间
};

individual elite;	//全局最优解

					//储存染色体中每一个基因（每一个工件）的信息
struct Gene
{
	int job;		//工件号
	int machine;   //机器号
	double frac;		//小数部分
};

//存储每一个工件的信息
struct Job_inform
{
	int job;		//工件号
	double pretime;   //上一阶段的加工完成时间
};

individual P[Pop];    //由所有个体组成的种群
individual PP[Pop];    //由所有个体组成的种群


					   //填上工件在每个阶段的时间信息
void set_job_time()
{
	for (int i = 0; i < Job; i++)
	{
		for (int j = 0; j < Stg; j++)
		{
			job_time[i][j] = 1 + random(20);
		}
	}
}

//初始化种群 小数部分取值为[0,0.999],表示机器的整数部分是从 0 开始的！
void Creat_Pop()
{
	int number = stage_m[0];		//第一阶段的机器数
	double integer, frac;
	/*srand((int)time(NULL));*/
	for (int i = 0; i < Pop; i++)
	{
		int flag[1000] = { 0 };
		for (int m = 0; m < Job; m++)
		{
			integer = random(number);
			frac = random(1000);
			while (flag[(int)frac] == 1)
				frac = random(1000);
			flag[(int)frac] = 1;
			P[i].seq[m] = integer + frac / 1000;
		}
	}
}

//工件在第一阶段的加工
void Process(double *time, individual &chrom2, Job_inform *job_infm1)
{
	Gene gene[Job], tmp;
	for (int i = 0; i < Job; i++)
	{
		gene[i].job = i;
		gene[i].machine = (int)chrom2.seq[i];
		gene[i].frac = chrom2.seq[i] - (int)chrom2.seq[i];
		job_infm1[i].job = i;			//用工件序号赋值，是从 0 开始的！
	}
	for (int i = 0; i < Job - 1; i++)
	{
		for (int j = i + 1; j < Job; j++)
		{
			if (gene[j].frac < gene[i].frac)
			{
				tmp = gene[i];
				gene[i] = gene[j];
				gene[j] = tmp;
			}
		}
	}
	for (int i = 0; i < Job; i++)
	{
		int job = gene[i].job;
		int mac = gene[i].machine;
		double time1 = job_time[job][0];
		time[mac] += time1;
		job_infm1[job].pretime = time[mac];			//记录每一个工件上一个加工阶段的完成时间
	}
}

//根据各个工件在上个阶段的加工完成时间对工件升序排列
void Sort_job_pretime(Job_inform *arr)
{
	Job_inform tmp;
	for (int i = 0; i < Job - 1; i++)
	{
		for (int j = i + 1; j < Job; j++)
		{
			if (arr[j].pretime < arr[i].pretime)
			{
				tmp = arr[i];
				arr[i] = arr[j];
				arr[j] = tmp;
			}
		}
	}
}

void Encode(individual &C)
{
	summ++;

	/*if (summ == Times)
	{
	cout << "\n" << Times << ":" << endl;;
	for (int i = 0; i < 1; i++)
	{
	cout << " value--" << i << "-- :" << P[i].val << endl;
	for (int m = 0; m < Job; m++)
	cout << P[i].seq[m] << " ";
	cout << "\n";
	}

	finish = clock();
	cout << "\n the runing time is:" << (double)(finish - start) / CLOCKS_PER_SEC << endl;
	exit(0);
	}*/


	individual chrom = C;							//对该染色体解码
	double m_time[Machine] = { 0 };					//所有机器上时间标志

	int j = 0, index, job, max_m, min_m, now_m;		//index：该阶段的第一台机器号；job：当前加工的工件号
	double min, max, min2, last, now;				//last：工件在上一阶段的完成时间；now：当前阶段的开始时间；
													//min：当前阶段的最早开始时间 max：当前阶段的最晚开始时间

	Job_inform job_infm[Job];						//结构体中记录每一个工件的序号（从 0 开始的！！！） 
													//      也记录了上一个加工阶段完成时间

	for (int i = 0; i < Stg*Tim; i++)
	{
		int stage = i%Stg;
		if (stage == 0)
			index = 0;

		if (i == 0)
		{
			Process(m_time, chrom, job_infm);			//在第一阶段加工
			index += stage_m[stage];
			continue;
		}
		Sort_job_pretime(job_infm);					//根据各个工件在上个阶段的加工完成时间对工件升序排列

		for (int h = 0; h < Job; h++)
		{

			min = 1000, max = -1, min2 = 10000;
			for (int z = index; z < (index + stage_m[stage]); z++)
			{
				if (m_time[z] < min)
				{
					min = m_time[z];
					min_m = z;
				}
				if (m_time[z] > max)
				{
					max = m_time[z];
					max_m = z;
				}
			}

			job = job_infm[h].job;
			last = job_infm[h].pretime;
			if (last <= min)
			{
				now = min;
				now_m = min_m;
			}
			else if (last >= max)
			{
				now = last;
				now_m = max_m;
			}
			else
			{
				for (int i = index; i < (index + stage_m[stage]); i++)
				{
					if (m_time[i] <= last && (last - m_time[i]) < min2)
					{
						now_m = i;
						min2 = (last - m_time[i]);
					}
				}
				now = last;
			}

			job_infm[h].pretime = now + job_time[job][stage];
			m_time[now_m] = now + job_time[job][stage];
		}

		index += stage_m[stage];
	}

	C.val = 0;
	for (int i = 0; i < Machine; i++)
	{
		if (C.val < m_time[i])
			C.val = m_time[i];
	}
}

//交叉操作，随机产生a,b两点（a<b），子代继承p1中a到b的部分，其他部分从p2中传过来
void Crossover(const individual &p1, const individual &p2, individual &c)
{
	int a, b, count = 0;
	/*srand((int)time(NULL));*/
	a = random(Job);
	b = random(Job);
	while (a == b)
		b = random(Job);
	if (a > b)
	{
		int tmp = a;
		a = b;
		b = tmp;
	}
	while (count < a)
	{
		c.seq[count] = p2.seq[count];
		count++;
	}
	while (count <= b)
	{
		c.seq[count] = p1.seq[count];
		count++;
	}
	while (count < Job)
	{
		c.seq[count] = p2.seq[count];
		count++;
	}
}

//计算种群中所有的个体的值
void Cal_value()
{
	for (int i = 0; i < Pop; i++)
		Encode(P[i]);
}

//变异操作
void Mutation(individual &c)
{
	/*srand((int)time(NULL));*/
	int m_mac = stage_m[0];
	int integer = random(m_mac);
	double frac = (random(1000)) / 1000;
	int pick = random(Job);
	c.seq[pick] = integer + frac;
}

//选择操作，先把P[]中的个体保存到PP[]中，然后再从PP[]中选择个体放进P[]中
//void  Select()
//{
//	srand((int)time(NULL));
//	individual tmp;
//	int count = Best;
//	int a, b;
//	for (int i = 0; i < Best; i++)
//	{
//		for (int j = i + 1; j < Pop; j++)
//		{
//			if (P[j].val < P[i].val)
//			{
//				tmp = P[i];
//				P[i] = P[j];
//				P[j] = tmp;
//			}
//		}
//	}
//	for (int i = 0; i < Pop; i++)
//		PP[i] = P[i];
//	while (count < Pop)
//	{
//		a = random(Pop);
//		b = random(Pop);
//		while (a == b)
//			b = random(Pop);
//		a = (PP[a].val < PP[b].val) ? a : b;
//		P[count++] = PP[a];
//	}
//
//}


//种群所有个体进行交叉
void Cross_operator()
{
	/*srand((int)time(NULL));*/
	int Pair[(Pop / 2)][2];
	int flag[Pop] = { 0 };
	for (int i = 0; i < Pop / 2; i++)
	{
		int x, y;
		x = random(Pop);
		while (flag[x] == 1)
			x = random(Pop);
		flag[x] = 1;
		y = random(Pop);
		while (flag[y] == 1)
			y = random(Pop);
		flag[y] = 1;
		Pair[i][0] = x;
		Pair[i][1] = y;
	}
	for (int i = 0; i < Pop / 2; i++)
	{
		individual c1, c2;
		int p1, p2;
		p1 = Pair[i][0], p2 = Pair[i][1];
		int posibility = random(100);
		if (posibility <= Crop * 100)
		{
			Crossover(P[p1], P[p2], c1);
			Crossover(P[p2], P[p1], c2);
			P[p1] = c1;
			P[p2] = c2;
		}
	}
}

//变异操作
void Mutation_operator()
{
	int posibility;
	/*srand((int)time(NULL));*/
	for (int i = 0; i < Pop; i++)
	{
		posibility = random(100);
		if (posibility < Mutp * 100)
			Mutation(P[i]);
	}
}

//精英保留策略
void Copy_operator(individual &best)
{
	individual tmp;
	for (int i = 0; i < 1; i++)
	{
		for (int j = i + 1; j < Pop; j++)
		{
			if (P[j].val < P[i].val)
			{
				tmp = P[i];
				P[i] = P[j];
				P[j] = tmp;
			}
		}
	}
	if (best.val>P[0].val)
		best = P[0];
}


int main()
{

	srand(0);
	set_job_time();

	cout << "GA" << endl;
	cout << "\nrepeat_times is: " << Times << "    ;Job is: " << Job << "    ;Stage is:  "
		<< Stg << endl;
	for (int circle = 0; circle < 10; circle++)
	{
		rand();
		summ = 0;
		start = clock();
		Creat_Pop();
		Cal_value();
		elite = P[0];

		while (1)
		{
			Copy_operator(elite);
			Cross_operator();
			Mutation_operator();
			Cal_value();

			if (summ >= Times)
			{
				value[circle] = elite.val;
				/*for (int z = 0; z < Job*Tim; z++)
				cout << elite.seq[z] << " ";
				cout << "\n";*/
				finish = clock();
				total_time[circle] = (double)(finish - start) / CLOCKS_PER_SEC;

				//cout << "value:" << value[circle] << "\ntime:" << total_time[circle] << endl;

				break;
			}
		}
	}

	double maxx = -1, minn = 10000;
	for (int i = 0; i < 10; i++)
	{
		if (value[i] > maxx)
		{
			maxx = value[i];
			worst_value = maxx;
		}
		if (value[i] < minn)
		{
			minn = value[i];
			best_value = minn;
		}
		average_value += value[i];
		average_time += total_time[i];
	}
	cout << "\n the best value of every round is:" << endl;
	for (int i = 0; i < 10; i++)
		cout << value[i] << " ";

	cout << "\n the best value is:" << best_value;
	cout << "\n the worst value is:" << worst_value;
	cout << "\n the average value is:" << average_value / 10;
	cout << "\n the average  program's runing time:" << average_time / 10;
	return 0;

}