operategenome.cpp

车间调度问题的基于工序的编码源程序

//基于工序的表达法

#include "OperateGenome.h"
#include "GA.H"
extern int mat[24][4];
//Construct function
OperateGenome::OperateGenome(char *filename, Evaluator f, Initializer i, 
							 Crossover c, Mutator m):
Genome(filename, f, i, c, m)
{
	if (macnum>0 && jobnum>0) 
	{
		length = macnum * jobnum;
		chrom = new int[length];
		for(int j=0; j<length; j++)
			chrom[j] = 0;
	}
}
OperateGenome::OperateGenome(const OperateGenome & orig)
{
	OperateGenome::copy(orig);
}
//Destuct function
OperateGenome::~OperateGenome()
{
}
void OperateGenome::copy(const Genome & orig)
{
	if (&orig == this) 
		return;
	const OperateGenome *c = dynamic_cast<const OperateGenome*>(&orig);
	if (c) 
	{
		Genome::copy(*c);
	}
	
}
Genome *OperateGenome::clone() const
{
	OperateGenome *cpy = new OperateGenome;
	cpy->copy(*this);
	return cpy;
}
//初始化
void OperateGenome::OperateInitializer(Genome & child)
{
	int i, j;
	OperateGenome &c = dynamic_cast<OperateGenome &>(child);
	for(i=0; i<c.macnum; i++)
	{
		for (j=0; j<c.jobnum; j++)
			c[i*c.jobnum+j] = j+1;
	}
	int p1, p2;
	for(i=0; i<c.length*c.length; i++)
	{
		p1 = rand() % c.length;
		p2 = rand() % c.length;
		int tmp = c[p1];
		c[p1] = c[p2];
		c[p2] = tmp;
	}
}

//解码，求适应度值
int OperateGenome::OperateEvaluator(Genome &genome)
{
	OperateGenome &g = dynamic_cast<OperateGenome &>(genome);
	int i, j, k;
	int makespan;				//调度长度
	int Current;				//记录当前的时间
	int JobCurrentIndex;		//当前正在处理的工件在机器上的序号
	int *ChromMachine = new int[g.length];	//机器编码方式
	int *ChromTime = new int[g.length];		//机器编码方式对应的时间表
	int *JobCurrent = new int[g.jobnum];	//记录工件i的当前时间
	int *JobProcessed = new int[g.macnum];	//记录第i台机器上已经处理的工件数目
	int ***Time;							//记录第i台机器处理第j个工件之前(后)的时间
	int **JobId;							//记录第i台机器上处理的第j个工件的工件编号
	int *JobIndex = new int[g.jobnum];		//工件序号
	JobId = new int * [g.macnum];	//int **JobId; //记录第i台机器上处理的第j个工件的工件编号
	for(i=0; i<g.macnum; i++)
		JobId[i] = new int[g.jobnum];

	Time = new int ** [g.macnum];//int ***Time;	//记录第i台机器处理第j个工件之前(后)的时间
	for(i=0; i<g.macnum; i++)
		Time[i] = new int * [g.jobnum];
	for(i=0; i<g.macnum; i++)
	{
		for(j=0; j<g.jobnum; j++)
			Time[i][j] = new int[2];
	}
		
	for(i=0; i<g.jobnum; i++)//初始化工件序号
		JobIndex[i] = 0;
	for(k=0; k<g.length; k++)//获得机器编码
	{    
		int job = g[k]-1;
		ChromMachine[k] = g.machine[job][JobIndex[job]++];
		ChromTime[k] = g.time[job][JobIndex[job]-1];
	}

	for(i=0; i<g.jobnum; i++)	//int *JobCurrent = new int[g.jobnum];	//记录工件i的当前时间
		JobCurrent[i] = 0;
	for(i=0; i<g.macnum; i++)	//int *JobProcessed = new int[g.macnum];	//记录第i台机器上已经处理的工件数目
		JobProcessed[i] = 0;
	for(k=0; k<g.length; k++)
	{
		int mac, job;
		mac = ChromMachine[k]-1;
		job = g[k]-1;
		Current = JobCurrent[job];
		JobCurrentIndex = 0;
		if (JobProcessed[mac]==0)
		{
			Time[mac][0][0] = Current;
			Time[mac][0][1] = Current + ChromTime[k];
			JobId[mac][0] = g[k];
		}
		if (JobProcessed[mac] >0)
		{
			if ((ChromTime[k]+Current <= Time[mac][0][0]))
			{
				for(i=JobProcessed[mac]; i>0; i--)
				{
					Time[mac][i][0] = Time[mac][i-1][0];
					Time[mac][i][1] = Time[mac][i-1][1];
					JobId[mac][i] = JobId[mac][i-1];
				}
				Time[mac][0][0] = Current;
				Time[mac][0][1] = Current + ChromTime[k];
				JobId[mac][0] = g[k];
			}
			else
			{
				i = 0;
				while (((max(Time[mac][i][1],Current)+ChromTime[k])>Time[mac][i+1][0]) && (i<(JobProcessed[mac]-1)))
				{
					i++;
				}
				JobCurrentIndex = i+1;
				if (i != (JobProcessed[mac]-1))
				{
					for(j=JobProcessed[mac]; j>i+1; j--)
					{
						Time[mac][j][0] = Time[mac][j-1][0];
						Time[mac][j][1] = Time[mac][j-1][1];
						JobId[mac][j] = JobId[mac][j-1];
					}
					Time[mac][i+1][0] = max(Time[mac][i][1],Current);
					Time[mac][i+1][1] = max(Time[mac][i][1],Current) + ChromTime[k];
					JobId[mac][i+1] = g[k];
				}
				if (i == (JobProcessed[mac]-1))
				{
					int num = JobProcessed[mac];
					Time[mac][num][0] = max(Time[mac][num-1][1],Current);
					Time[mac][num][1] = max(Time[mac][num-1][1],Current) + ChromTime[k];
					JobId[mac][num] = g[k];
				}
			}
		}
		JobCurrent[job] = Time[mac][JobCurrentIndex][1];
		JobProcessed[mac]++;
	}
	makespan = Time[0][g.jobnum-1][1];
	for(i=1; i<g.macnum; i++)
	{
		if (Time[i][g.jobnum-1][1] > makespan)
			makespan = Time[i][g.jobnum-1][1];
	}
	if (g.lekin) 
	{
		//write job machine and sequence file for leckin software
		ofstream jobfile;
		jobfile.open("pso.job",ios::out);
		jobfile << "Shop:               Job" << endl;
		for(i=0; i<g.jobnum; i++)
		{
			int red = (int)((Random::RandomDouble()) * 255);
			int green = (int)((Random::RandomDouble()) * 255);
			int blue = (int)((Random::RandomDouble()) * 255);
			jobfile << "Job:                Job 0" << i+1 << endl;
			jobfile << "  RGB:                ";
			jobfile << red << ";" << green << ";" << blue << ";" << endl;
			jobfile << "  Release:            0" << endl;
			jobfile << "  Due:                10" << endl;
			jobfile << "  Weight:             1" << endl;
			for(j=0; j<g.macnum; j++)
			{
				jobfile << "  Oper:               W" << g.machine[i][j] << ";" ;
				jobfile << g.time[i][j] <<";A" << endl;
			}
			jobfile << endl;
		}
		jobfile.close();
		ofstream macfile;
		macfile.open("pso.mch",ios::out);
		macfile << "Ordinary:" << endl;
		for(i=0; i<g.macnum; i++)
		{
			int red = (int)((Random::RandomDouble()) * 255);
			int green = (int)((Random::RandomDouble()) * 255);
			int blue = (int)((Random::RandomDouble()) * 255);
			macfile << "Workcenter:         W" << (i+1) << endl;
			macfile << "  RGB:                ";
			macfile << red << ";" << green << ";" << blue << ";" << endl;
			macfile << "  Release:            0" << endl;
			macfile << "  Status:             A" << endl;
			macfile << endl;
		}
		macfile.close();
		
		ofstream seqfile;
		seqfile.open("pso.seq",ios::out);
		seqfile << "Schedule:           PSO" << endl;
		seqfile << "  RGB:                0;0;255" << endl;
		seqfile << "  Time:               1" << endl;
		for(i=0; i<g.macnum; i++)
		{
			seqfile << "  Machine:            W" << (i+1) << endl;
			for(j=0; j<g.jobnum; j++)
			{
				seqfile << "    Oper:               Job 0";
				seqfile << JobId[i][j] << endl;
			}
		}
		seqfile.close();
		//end three file construction
	}
	for(i=0; i<g.macnum; i++)
	{
		for(j=0; j<g.jobnum; j++)
			delete Time[i][j];
	}
	for(i=0; i<g.macnum; i++)
		delete Time[i];
	delete []Time;
	for(i=0; i<g.macnum; i++)
		delete JobId[i];
	delete []JobId;
	delete []ChromMachine;
	delete []ChromTime;
	delete []JobCurrent;
	delete []JobProcessed;
	delete []JobIndex;
	return makespan;
}

//第一种变异：循环移动
int OperateGenome::OperateMutator1(Genome & child, double pmut)
{
	OperateGenome &c = dynamic_cast<OperateGenome &>(child);
	if (pmut <=0.0 )
		return 0;
	int nMut = 0;
	c.fitness = c.evaluate();
	int min = c.fitness;
	OperateGenome tmpGenome(c);
	if (Random::RandomInt(pmut))
	{
		nMut++;
		int n = c.jobnum ;
		int *j = new int [n];
		int i,iter;
		bool flag;
		for(iter=0; iter<c.length*10; iter++)
		{
			do 
			{
				for (i=0; i<n; i++)
					j[i] = rand() % c.length;
				flag = false;
				for (i=0; i<n-1; i++)
				{
					if (j[i] == j[i+1])
					{
						flag = true;
						break;
					}
				}
			} while(flag);
			int tmp = tmpGenome[j[0]];
			for(i=0; i<n-1; i++)
				tmpGenome[j[i]] = tmpGenome[j[i+1]];
			tmpGenome[j[n-1]] = tmp;
			tmpGenome.fitness = tmpGenome.evaluate();
			if (tmpGenome.fitness < min)
			{
				min = tmpGenome.fitness;
				c = tmpGenome;
			}
		}
		delete []j;
	}
	return (nMut);
}
//第二种变异：将染色体分成数个基因片断，然后依次
//将后面的基因片断前移形成子染色体
int OperateGenome::OperateMutator2(Genome & child, double pmut)
{
	OperateGenome &c = dynamic_cast<OperateGenome &>(child);
	if (pmut <=0.0 )
		return 0;
	int nMut = 0;
	c.fitness = c.evaluate();
	int min = c.fitness;
	OperateGenome tmpGenome(c);
	if (Random::RandomInt(pmut))
	{
		nMut++;
		int i, j, k, iter;
		//int num = c.length/2;
		int num = 4;
		int *p = new int[num];
		for(iter=0; iter<c.length*10; iter++)
		{
			for(i=0; i<num; i++)
				p[i] = rand() % c.length;
			for(i=0; i<num-1; i++)
			{
				for(j=0; j<num-i-1; j++)
				{
					if (p[j] > p[j+1]) 
					{
						int temp = p[j];
						p[j] = p[j+1];
						p[j+1] =temp;
					}
				}
			}
			int **part = new int*[num-1];
			for(i=0; i<num-1; i++)
				part[i] = new int[p[i+1]-p[i]];
			for(i=0; i<num-1; i++)
			{
				for(j=0; j<p[i+1]-p[i]; j++)
				{
					part[i][j] = tmpGenome[p[i]+j];
				}
			}
			k = 0;
			for(i=0; i<num-1; i++)
			{
				for(j=0; j<(p[num-i-1]-p[num-i-2]); j++)
				{
					tmpGenome[p[0]+p[num-1]-p[num-i-1]+j] = part[num-i-2][k];
					k++;
				}
				k = 0;
			}
			tmpGenome.fitness = tmpGenome.evaluate();
			
			if (tmpGenome.fitness < min)
			{
				min = tmpGenome.fitness;
				c = tmpGenome;
			}
			for(i=0; i<num-1; i++)
				delete part[i];
			delete []part;
		}
		delete []p;
	}
	return nMut;
}
//第三种变异：基于邻域搜索的新型变异算子
int OperateGenome::OperateMutator3(Genome & child, double pmut)
{
	OperateGenome &c = dynamic_cast<OperateGenome &>(child);
	if (pmut <=0.0 )
		return 0;
	int nMut = 0;
	OperateGenome tmpGenome(c);
	if (Random::RandomInt(pmut)) 
	{
		nMut++;
		int i, j;
		int min;
		//int lmd = 4;
		int col = 4;
		int row = 24;
		int *p = new int[col];
		bool *flag = new bool[c.length];
		for(i=0; i<c.length; i++)
			flag[i] = false;
		for(i=0; i<col; i++)
		{
			int k = 0;
			p[i] = rand() % (c.length-i*c.macnum);
			for(j=0; j<c.length; j++)
			{
				if (!flag[j]) 
				{
					if (k==p[i]) 
					{
						p[i] = j;
						break;
					}
					else
						k++;
				}
			}
			for(j=0; j<c.length; j++)
			{
				if (!flag[j] && c[j]==c[p[i]]) 
				{
					flag[j] = true;
				}
			}
		}
//		cout << "position:\t";
//		for(i=0; i<lmd; i++)
//			cout << p[i] << "\t";
//		cout << endl << "value:\t";
//		for(i=0; i<lmd; i++)
//			cout << c[p[i]] << "\t";
//		cout << endl;
		int matindex;
		for(j=0; j<col; j++)
		{
			matindex = mat[0][j];
			tmpGenome[p[j]] = c[p[matindex]];
		}
		tmpGenome.fitness = tmpGenome.evaluate();
		min = tmpGenome.fitness;
		//for(int iter=0; iter<c.jobnum*2; iter++)
		{
			for(i=1; i<row; i++)
			{
				for(j=0; j<col; j++)
				{
					matindex = mat[i][j];
					tmpGenome[p[j]] = c[p[matindex]];
				}
				tmpGenome.fitness = tmpGenome.evaluate();
				if (tmpGenome.fitness <= min) 
				{
					min = tmpGenome.fitness;
					c = tmpGenome;
				}
			}
		}
		delete []p;
		delete []flag;
	}
	return nMut;
}
//第四种变异，逆序变异
int OperateGenome::OperateMutator4(Genome & child, double pmut)
{
	OperateGenome &c = dynamic_cast<OperateGenome &>(child);
	if (pmut <=0.0 )
		return 0;
	int nMut = 0;
	c.fitness = c.evaluate();
	int min;
	OperateGenome tmpGenome(c);
	if (Random::RandomInt(pmut)) 
	{
		nMut++;
		int i, iter;
		int p1, p2, num;
		for (iter=0; iter<c.length*10; iter++) 
		{
			tmpGenome = c;
			do 
			{
				p1 = rand() % c.length;
				p2 = rand() % c.length;
			} while(p1==p2);
			if (p1 > p2) 
			{
				int temp = p1;
				p1 = p2;
				p2 = temp;
			}
			num = p2 - p1 +1;
			int *part = new int[num];
			for (i=p1; i<=p2; i++) 
			{
				part[num-i+p1-1] = c[i];
			}
			for (i=p1; i<=p2; i++) 
			{
				tmpGenome[i] = part[i-p1];
			}
			delete []part;
			
			tmpGenome.fitness = tmpGenome.evaluate();
			if (iter==0) 
				min = tmpGenome.fitness;
			if (tmpGenome.fitness < min) 
			{
				min = tmpGenome.fitness;
				c = tmpGenome;
				break;
			}
		}
	}
	return nMut;
}
//第一种交叉从父代1中截取一个片断到子代中，再依次扫描父代2的基因，如果
//该基因在子代中(截取的片断)中出现，则将子代该基因作一标志，如果没有
//出现，则将父代2的该基因拷贝到子代中
int OperateGenome::OperateCrossover1(const Genome &parent1, const Genome &parent2,
							 Genome &child1, Genome &child2)
{
//	const Genome &mom = parent1;
//	const Genome &dad = parent2;
	const OperateGenome &mom = dynamic_cast<const OperateGenome &>(parent1);
	const OperateGenome &dad = dynamic_cast<const OperateGenome &>(parent2);
	if (child1.chrom==0) 
		child1 = parent1;
	if (child2.chrom==0)
		child2 = parent2;
	int p1, p2;
	int nCross = 0;
	int *part1 = new int[parent1.length];
	int *fpart1 = new int[parent1.length];
	int *part2 = new int[parent1.length];
	int *fpart2 = new int[parent1.length];
	
	int j, k;
	do 
	{
		p1 = rand() % (parent1.length-1);
		p2 = rand() % (parent1.length-1);
	} while(p1==p2);
	nCross++;
	if (p1 > p2) 
	{
		int temp = p1;
		p1 = p2;
		p2 = temp;
	}
	k = 0;
	for(j=p1; j<=p2; j++)
	{
		part1[k] = fpart1[k] = mom[j];
		part2[k] = fpart2[k] = dad[j];
		k++;
	}
	int partnum = k;
	
	for(j=0; j<parent1.length; j++)
	{
		int iter = 0;
		while ((dad[j] !=fpart1[iter] && iter<partnum))
		{
			iter++;
		}
		fpart1[iter] = 0;
		if (iter==partnum)
		{
			part1[k] = dad[j];
			k++;
		}
	}
	for(j=0; j<partnum; j++)
	{
		int temp = part1[p1+j];
		part1[p1+j] = part1[j];
		part1[j] = temp;
	}
	k = partnum;
	for(j=0; j<parent1.length; j++)
	{
		int iter = 0;
		while ((mom[j]!=fpart2[iter]) && (iter<partnum))
		{
			iter++;
		}
		fpart2[iter] = 0;
		if (iter==partnum)
		{
			part2[k] = mom[j];
			k++;