operategenome.cpp

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

		}
	}
	for(j=0; j<partnum; j++)
	{
		int temp = part2[p1+j];
		part2[p1+j] = part2[j];
		part2[j] = temp;
	}
	for (j=0; j<parent1.length; j++)
	{
		child1[j] = part1[j];
		child2[j] = part2[j];
	}
	delete []part1;
	delete []fpart1;
	delete []part2;
	delete []fpart2;
	return nCross;
}

//第二种交叉先产生含有所有工件的样本，将此样本分成两个部分，依次
//选取前一部分和父代1中相同的工件和后一部分和父代2中相同的工件作为
//子代的工件。
int OperateGenome::OperateCrossover2(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 nCross = 0;
	int *job = new int[parent1.jobnum];
	int *job1 = new int[parent1.jobnum];
	int *job2 = new int[parent1.jobnum];
	int *part1 = new int[parent1.length];
	int *part2 = new int[parent1.length];
	
	int i, j, k, num;
	nCross++;
	for(i=0; i<parent1.jobnum; i++)
		job[i] = i+1;
	for(k=0; k<parent1.jobnum*2; k++)
	{
		int temp1 = rand() % parent1.jobnum;
		int temp2 = rand() % parent1.jobnum;
		int temp3 = job[temp1];
		job[temp1] = job[temp2];
		job[temp2] = temp3;
	}
	do 
	{
		num = (rand() % (parent1.jobnum-1)) + 1;
	} while(num==0 || num==parent1.jobnum);
	
	for(i=0; i<num; i++)
	{
		job1[i] = job[i];
	}
	for(i=num; i<parent1.jobnum; i++)
	{
		job2[i-num] = job[i];
	}
	j = 0;
	for(i=0; i<parent1.length; i++)
	{
		k = 0;
		while ((mom[i]!=job1[k]) && (k<num))
		{
			k++;
		}
		if (k != num)
		{
			part1[j] = mom[i];
			j++;
		}
		k = 0;
		while ((dad[i]!=job2[k]) && (k<(parent1.jobnum-num)))
		{
			k++;
		}
		if (k!=(parent1.jobnum-num))
		{
			part1[j] = dad[i];
			j++;
		}
	}
	j = 0;
	for(i=0; i<parent1.length; i++)
	{
		k = 0;
		while ((mom[i]!=job2[k]) && (k<(parent1.jobnum-num)))
		{
			k++;
		}
		if (k != (parent1.jobnum-num))
		{
			part2[j] = mom[i];
			j++;
		}
		k = 0;
		while ((dad[i]!=job1[k]) && (k<num))
		{
			k++;
		}
		if (k!=num)
		{
			part2[j] = dad[i];
			j++;
		}
	}
	for(i=0; i<parent1.length; i++)
	{
		child1[i] = part1[i];
		child2[i] = part2[i];
	}
	delete []job;
	delete []job1;
	delete []job2;
	delete []part1;
	delete []part2;
	return nCross;
}

//第三种交叉：POX( Precedence Operation Crossover)
//随机划分工作集{1,2,3……n}为两个非空的子集J1和J2。
//复制Parent1包含在J1的工件到Children1，Parent2包含在J1的工件到Children2，保留他们的位置。
//复制Parent2包含在J2的工件到Children1，Parent1包含在J2的工件到Children2，保留他们的顺序。

int OperateGenome::OperateCrossover3(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 nCross = 0;
	int *job = new int[parent1.jobnum];
	int *part1 = new int[parent1.length];
	int *part2 = new int[parent1.length];
	bool *flag1 = new bool[parent1.length];
	bool *flag2 = new bool[parent1.length];

	int i, j, k, num;
	nCross++;
	for(i=0; i<parent1.jobnum; i++)
		job[i] = i+1;
	for(k=0; k<parent1.jobnum*2; k++)
	{
		int temp1 = rand() % parent1.jobnum;
		int temp2 = rand() % parent1.jobnum;
		int temp3 = job[temp1];
		job[temp1] = job[temp2];
		job[temp2] = temp3;
	}
	num = (rand() % (parent1.jobnum-2)) + 1;	
	for(i=0; i<parent1.length; i++)
	{
		flag1[i] = false;
		flag2[i] = false;
	}
	for(i=0; i< parent1.length; i++)
	{
		for(j=0; j<num; j++)
		{
			if (mom[i]==job[j]) 
			{
				part1[i] = mom[i];
				flag1[i] = true;
				break;
			}
		}
		for(j=0; j<num; j++)
		{
			if (dad[i]==job[j]) 
			{
				part2[i] = dad[i];
				flag2[i] = true;
				break;
			}
		}
	}
	int k1 = 0;
	int k2 = 0;
	for(i=0; i<parent1.length; i++)
	{
		if (!flag2[i])
		{
			while (flag1[k1]) 
			{
				k1++;
			}
			part1[k1++] = dad[i];
		}
		if (!flag1[i]) 
		{
			while (flag2[k2]) 
			{
				k2++;
			}
			part2[k2++] = mom[i];
		}
			
	}
	
	for(i=0; i<parent1.length; i++)
	{
		child1[i] = part1[i];
		child2[i] = part2[i];
	}
	delete []job;
	delete []part1;
	delete []part2;
	delete []flag1;
	delete []flag2;
	return nCross;
}

//第四种交叉：POX2( Precedence Operation Crossover)
//随机划分工作集{1,2,3……n}为两个非空的子集J1和J2。
//复制Parent1包含在J1的工件到Children1，Parent2包含在J2的工件到Children2，保留他们的位置。
//复制Parent2包含在J1的工件到Children1，Parent1包含在J2的工件到Children2，保留他们的顺序。

int OperateGenome::OperateCrossover4(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 nCross = 0;
	int *job = new int[parent1.jobnum];
	int *part1 = new int[parent1.length];
	int *part2 = new int[parent1.length];
	bool *flag1 = new bool[parent1.length];
	bool *flag2 = new bool[parent1.length];

	int i, j, k, num;
	nCross++;
	for(i=0; i<parent1.jobnum; i++)
		job[i] = i+1;
	for(k=0; k<parent1.jobnum*2; k++)
	{
		int temp1 = rand() % parent1.jobnum;
		int temp2 = rand() % parent1.jobnum;
		int temp3 = job[temp1];
		job[temp1] = job[temp2];
		job[temp2] = temp3;
	}
	num = (rand() % (parent1.jobnum-1)) + 1;	
//	cout << "job1:" << endl;
//	for (i=0; i<num; i++) 
//	{
//		cout << job[i] << "\t";
//	}
//	cout << endl << "job2:" << endl;
//	for (i=num; i<parent1.jobnum; i++) 
//	{
//		cout << job[i] << "\t";
//	}
//	cout << endl;
	for(i=0; i<parent1.length; i++)
	{
		flag1[i] = false;
		flag2[i] = false;
	}
	for(i=0; i< parent1.length; i++)
	{
		for(j=0; j<num; j++)
		{
			if (mom[i]==job[j]) 
			{
				part1[i] = mom[i];
				flag1[i] = true;
				break;
			}
		}
		for (j=num; j<parent1.jobnum; j++) 
		{
			if (dad[i]==job[j]) 
			{
				part2[i] = dad[i];
				flag2[i] = true;
			}
		}
	}
	int k1 = 0;
	int k2 = 0;
	for(i=0; i<parent1.length; i++)
	{
		if (flag2[i])
		{
			while (flag1[k1]) 
			{
				k1++;
			}
			part1[k1++] = dad[i];
		}
		if (flag1[i]) 
		{
			while (flag2[k2]) 
			{
				k2++;
			}
			part2[k2++] = mom[i];
		}
			
	}
	
	for(i=0; i<parent1.length; i++)
	{
		child1[i] = part1[i];
		child2[i] = part2[i];
	}
	delete []job;
	delete []part1;
	delete []part2;
	delete []flag1;
	delete []flag2;
	return nCross;
}

//第五种交叉：改进Cheng-Gen-Tsujimura方法
//按照双点交叉的原则，找到截取片断的不同部分，在父染色体中删除多余的基因，
//立即用丢失的基因补充，这样可以保证片断的内部的相对顺序，也可保证片断的
//绝对顺序。同时在扫描父染色体时，可从前往后扫描，也可从后往前扫描，从后
//往前扫描可以保证前面工序的在父染色体中的顺序，从前往后扫描可以保证后面
//工序在父染色体中的顺序

int OperateGenome::OperateCrossover5(const Genome &parent1, const Genome &parent2,
							Genome &child1, Genome &child2)
{
	const OperateGenome &mom = dynamic_cast<const OperateGenome &>(parent1);
	const OperateGenome &dad = dynamic_cast<const OperateGenome &>(parent2);
	child1 = parent1;
	child2 = parent2;
	int nCross = 0;
	int p1, p2;									//交叉位置

	int i, j, partnum, diffnum;
	nCross++;
	do 
	{
		p1 = rand() % parent1.length;
		p2 = rand() % parent1.length;
	} while(p1==p2);
	if (p1 > p2) 
	{
		int t = p1;
		p1 = p2;
		p2 = t;
	}
	cout << "crossover position:\t" << p1 << "\t" << p2 << endl;
	partnum = p2-p1+1;
	int *part1 = new int[partnum];		//片断1
	int *part2 = new int[partnum];		//片断2
	int *diff1 = new int[partnum];		//片断1中有而片断2中没有的基因
	int *diff2 = new int[partnum];		//片断2中有而片断1中没有的基因
	bool *flag1 = new bool[partnum];
	bool *flag2 = new bool[partnum];
	int diffindex1 = 0;
	int diffindex2 = 0;
	for(i=p1; i<=p2; i++)
	{
		part1[i-p1] = mom[i];
		child2[i] = mom[i];
		part2[i-p1] = dad[i];
		child1[i] = dad[i];
	}
	cout << "part1:\t";
	for(i=0; i<partnum; i++)
		cout << part1[i] << "\t";
	cout << endl << "part2:\t";
	for(i=0; i<partnum; i++)
		cout << part2[i] << "\t";
	cout << endl;
	for(i=0; i<partnum; i++)
		flag1[i] = flag2[i] = false;
	
	for(i=0; i<partnum; i++)
	{
		for(j=0; j<partnum; j++)
		{
			if (!flag2[j] && part1[i]==part2[j]) 
			{
				flag2[j] = true;
				break;
			}
		}
		if (j==partnum) 
		{
			diff1[diffindex1++] = part1[i];
		}
	}
	for(i=0; i<partnum; i++)
	{
		for(j=0; j<partnum; j++)
		{
			if (!flag1[j] && part2[i]==part1[j]) 
			{
				flag1[j] = true;
				break;
			}
		}
		if (j==partnum) 
		{
			diff2[diffindex2++] = part2[i];
		}
	}
	assert(diffindex1==diffindex1);
	diffnum = diffindex1;
	delete []flag1;
	delete []flag2;
	flag1 = new bool[diffnum];
	flag2 = new bool[diffnum];
	for(i=0; i<diffnum; i++)
	{
		flag1[i] = false;
		flag2[i] = false;
	}
	cout << "diff1:\t";
	for(i=0; i<diffnum; i++)
		cout << diff1[i] << "\t";
	cout << endl << "diff2:\t";
	for(i=0; i<diffnum; i++)
		cout << diff2[i] << "\t";
	cout << endl;
	diffindex1 = diffindex2 = 0;
	if (Random::RandomInt(0.999)) 
	{
		diffindex1 = diffindex2 = 0;
		cout << "from forward to backward:" << endl;
		for(i=0; i<p1; i++)
		{
			for(j=0; j<diffnum; j++)
			{
				if (!flag1[j] && mom[i]==diff2[j]) 
				{
					child1[i] = diff1[diffindex1];
					flag1[j] = true;
					diffindex1++;
					break;
				}
			}
			if (diffindex1 >= diffnum)
				break;
		}
		if (diffindex1 < diffnum) 
		{
			for(i=p2+1; i<parent1.length; i++)
			{
				for(j=0; j<diffnum; j++)
				{
					if (!flag1[j] && mom[i]==diff2[j]) 
					{
						child1[i] = diff1[diffindex1];
						flag1[j] = true;
						diffindex1++;
						break;
					}
				}
				if (diffindex1 >= diffnum)
					break;
			}	
		}
		for(i=0; i<p1; i++)
		{
			for(j=0; j<diffnum; j++)
			{
				if (!flag2[j] && dad[i]==diff1[j]) 
				{
					child2[i] = diff2[diffindex2];
					flag2[j] = true;
					diffindex2++;
					break;
				}
			}
			if (diffindex2 >= diffnum)
				break;
		}
		if (diffindex2 < diffnum) 
		{
			for(i=p2+1; i<parent1.length; i++)
			{
				for(j=0; j<diffnum; j++)
				{
					if (!flag2[j] && dad[i]==diff1[j]) 
					{
						child2[i] = diff2[diffindex2];
						flag2[j] = true;
						diffindex2++;
						break;
					}
				}
				if (diffindex2 >= diffnum)
					break;
			}
		}
		cout << "child1:" << endl;
		for(i=0; i<parent1.length; i++)
			cout << child1[i] << "\t";
		cout << endl << "child2:" << endl;
		for(i=0; i<parent1.length; i++)
			cout << child2[i] << "\t";
		cout << endl;
	}
	else
	{
		diffindex1 = diffindex2 = diffnum-1;
		//cout << "from backward to forward:" << endl;
		for(i=parent1.length-1; i>=p2+1; i--)
		{
			for(j=0; j<diffnum; j++)
			{
				if (!flag1[j] && mom[i]==diff2[j]) 
				{
					child1[i] = diff1[diffindex1];
					flag1[j] = true;
					diffindex1--;
					break;
				}
			}
			if (diffindex1 <0 )
				break;
		}
		if (diffindex1 >= 0) 
		{
			for(i=p1-1; i>=0; i--)
			{
				for(j=0; j<diffnum; j++)
				{
					if (!flag1[j] && mom[i]==diff2[j])
					{
						child1[i] = diff1[diffindex1];
						flag1[j] = true;
						diffindex1--;
						break;
					}
				}
				if (diffindex1 <0 )
					break;
			}
		}
		for(i=parent1.length-1; i>=p2+1; i--)
		{
			for(j=0; j<diffnum; j++)
			{
				if (!flag2[j] && dad[i]==diff1[j]) 
				{
					child2[i] = diff2[diffindex2];
					flag2[j] = true;
					diffindex2--;
					break;
				}
			}
			if (diffindex2 < 0)
				break;
		}
		if (diffindex2 >= 0) 
		{
			for(i=p1-1; i>=0; i--)
			{
				for(j=0; j<diffnum; j++)
				{
					if (!flag2[j] && dad[i]==diff1[j])
					{