operategenome.cpp

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

						child2[i] = diff2[diffindex2];
						flag2[j] = true;
						diffindex2--;
						break;
					}
				}
				if (diffindex2 <0 )
					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;
	}
//	int x2[10],x3[10];
//	for(i=0; i<10; i++)
//		x2[i] = x3[i] = 0;
//	for(i=0; i<100; i++)
//	{
//		x2[child1[i]-1]++;
//		x3[child2[i]-1]++;
//	}
//	for(i=0; i<10; i++)
//		cout << x2[i] << "\t";
//	cout << endl;
//	for(i=0; i<10; i++)
//		cout << x3[i] << "\t";
	delete []part1;
	delete []part2;
	delete []diff1;
	delete []diff2;
	delete []flag1;
	delete []flag2;
	return nCross;
}


//第六种交叉：改进Cheng-Gen-Tsujimura方法
int OperateGenome::OperateCrossover6(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;
	}
	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];
	}

	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;
	}

	diffindex1 = diffindex2 = 0;

	//随机化删除位置
	int *eachdiffnum1 = new int[diffnum];	//diff1中每一个diff元素的个数
	int *eachdiffnum2 = new int[diffnum];	//diff1中每一个diff元素的个数
	int *DeletePosition1 = new int[diffnum]; //diff1的删除位置
	int *DeletePosition2 = new int[diffnum]; //diff2的删除位置
	for (i=0; i<diffnum; i++) 
	{
		eachdiffnum1[i] = 0;
		eachdiffnum2[i] = 0;
	}
	//统计diff1和diff2中每个元素的个数
	for (i=0; i<diffnum; i++) 
	{
		for (j=0; j<p1; j++) 
		{
			if (child1[j] == diff2[i]) 
			{
				eachdiffnum1[i]++;
			}
			if (child2[j] == diff1[i]) 
			{
				eachdiffnum2[i]++;
			}
		}
		for (j=p2+1; j<parent1.length; j++) 
		{
			if (child1[j] == diff2[i]) 
			{
				eachdiffnum1[i]++;
			}
			if (child2[j] == diff1[i]) 
			{
				eachdiffnum2[i]++;
			}
		}
	}
	for (i=1; i<diffnum; i++) 
	{
		for (j=0; j<i; j++) 
		{
			if (diff2[j] == diff2[i]) 
			{
				eachdiffnum1[i]--;
			}
		}
	}
	for (i=1; i<diffnum; i++) 
	{
		for (j=0; j<i; j++) 
		{
			if (diff1[j] == diff1[i]) 
			{
				eachdiffnum2[i]--;
			}
		}
	}
	//随机化删除位置
	for (i=0; i<diffnum; i++) 
	{
		DeletePosition1[i] = rand() % eachdiffnum1[i];
		DeletePosition2[i] = rand() % eachdiffnum2[i];
	}

	for (i=0; i<diffnum; i++) 
	{
		diffindex1 = 0;
		for (j=0; j<parent1.length; j++) 
		{
			if (!(j>=p1 && j<=p2))
			{
				if (child1[j] == diff2[i]) 
				{
					if (diffindex1 == DeletePosition1[i]) 
					{
						child1[j] = -1;
						break;
					}
					diffindex1++;
				}
			}
		}
	}
	for (i=0; i<diffnum; i++) 
	{
		diffindex2 = 0;
		for (j=0; j<parent1.length; j++) 
		{
			if (!(j>=p1 && j<=p2)) 
			{
				if (child2[j] == diff1[i]) 
				{
					if (diffindex2 == DeletePosition2[i]) 
					{
						child2[j] = -1;
						break;
					}
					diffindex2++;
				}
			}
		}
	}

	//随机化插入位置(不能插入到p1与p2之间)
	int *InsertPostion1 = new int[diffnum];
	int *InsertPostion2 = new int[diffnum];
	for (i=0; i<diffnum; i++) 
	{
		InsertPostion1[i] = rand() % (parent1.length-partnum);
		if (InsertPostion1[i] >= p1) 
		{
			InsertPostion1[i] += partnum;
		}
		InsertPostion2[i] = rand() % (parent1.length-partnum);
		if (InsertPostion2[i] >= p1) 
		{
			InsertPostion2[i] += partnum;
		}
	}

	//插入数据
	for(i=0; i<diffnum; i++)
	{
		flag1[i] = false;
		flag2[i] = false;
	}
	diffindex1 = diffindex2 = 0;
	//临时存贮数据
	int *tmpstring1 = new int[parent1.length];
	int *tmpstring2 = new int[parent1.length];
	int tmpstringindex1 = 0;
	int tmpstringindex2 = 0;
	for (i=0; i<parent1.length; i++) 
	{
		for (j=0; j<diffnum; j++) 
		{
			if (InsertPostion1[j]==i) 
			{
				tmpstring1[tmpstringindex1++] = diff1[j];
			}
		}
		if (child1[i] != -1) 
		{
			tmpstring1[tmpstringindex1++] = child1[i];
		}
	}
	
	for (i=0; i<parent1.length; i++) 
	{
		for (j=0; j<diffnum; j++) 
		{
			if (InsertPostion2[j]==i) 
			{
				tmpstring2[tmpstringindex2++] = diff2[j];
			}
		}
		if (child2[i] != -1) 
		{
			tmpstring2[tmpstringindex2++] = child2[i];
		}
	}
	for (i=0; i<parent1.length; i++) 
	{
		child1[i] = tmpstring1[i];
		child2[i] = tmpstring2[i];
	}

	delete []DeletePosition1;
	delete []DeletePosition2;
	delete []eachdiffnum1;
	delete []eachdiffnum2;
	delete []InsertPostion1;
	delete []InsertPostion2;
	delete []tmpstring1;
	delete []tmpstring2;
	delete []part1;
	delete []part2;
	delete []diff1;
	delete []diff2;
	delete []flag1;
	delete []flag2;
	return nCross;
}
//第七种交叉A hybrid genetic algorithm for the job shop scheduling problems
//中的第四种交叉
int OperateGenome::OperateCrossover7(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, k, partnum;
	int *index1 = new int[parent1.length];
	int *index2 = new int[parent2.length];
	bool *flag1 = new bool[parent1.length];
	bool *flag2 = new bool[parent2.length];
	int *temp1 = new int[parent1.length];
	int *temp2 = new int[parent2.length];
	nCross++;
	for (i=0; i<parent1.length; i++) 
	{
		flag1[i] = false;
	}
	for (i=0; i<parent2.length; i++) 
	{
		flag2[i] = false;
	}
	for (i=0; i<parent1.jobnum; i++) 
	{
		k = 0;
		for (j=0; j<parent1.length; j++) 
		{
			if (mom[j] == (i+1)) 
			{
				k++;
				index1[j] = k;
			}
		}
	}
	for (i=0; i<parent2.jobnum; i++) 
	{
		k = 0;
		for (j=0; j<parent2.length; j++) 
		{
			if (dad[j] == (i+1)) 
			{
				k++;
				index2[j] = k;
			}
		}
	}
//	cout << "index1:\t" << endl;
//	for (i=0; i<parent1.length; i++) 
//		cout << index1[i] << "\t";
//	cout << endl << "index2:\t" << endl;
//	for (i=0; i<parent2.length; i++) 
//		cout << index2[i] << "\t";
//	cout << endl;
	do 
	{
		p1 = rand() % parent1.length;
		p2 = rand() % parent1.length;
	} while(p1==p2);
	if (p1 > p2) 
	{
		int t = p1;
		p1 = p2;
		p2 = t;
	}
	partnum = p2-p1+1;
//	cout << "position 1:\t" << p1 << "\tposition 2\t" << p2 << endl;
	
	for (i=p1; i<=p2; i++) 
	{
		for (j=0; j<parent2.length; j++) 
		{
			if ((dad[j]==mom[i]) && (index2[j]==index1[i])) 
			{
				flag2[j] = true;
				break;
			}
		}
	}
	for (i=p1; i<=p2; i++) 
	{
		for (j=0; j<parent1.length; j++) 
		{
			if ((mom[j]==dad[i]) && (index1[j]==index2[i])) 
			{
				flag1[j] = true;
				break;
			}
		}
	}
	k = 0;
	for (i=0; i<parent1.length; i++) 
	{
		if (i==p1) 
		{
			for (j=p1; j<=p2; j++) 
			{
				temp1[k++] = dad[j];
			}
			
		}
		
		if (!flag1[i]) 
		{
			temp1[k++] = mom[i];
		}
	}
	k = 0;
	for (i=0; i<parent2.length; i++) 
	{
		if (i==p1) 
		{
			for (j=p1; j<=p2; j++) 
			{
				temp2[k++] = mom[j];
			}
			
		}

		if (!flag2[i]) 
		{
			temp2[k++] = dad[i];
		}
	}
	for (i=0; i<parent1.length; i++) 
	{
		child1[i] = temp1[i];
	}
	for (i=0; i<parent2.length; i++) 
	{
		child2[i] = temp2[i];
	}
	delete []temp1;
	delete []temp2;
	delete []flag1;
	delete []flag2;
	delete []index1;
	delete []index2;
	return nCross;
}

//第七种变异：用SA代替变异
int OperateGenome::OperateMutatorSA(Genome & child, double pmut)
{
	OperateGenome &c = dynamic_cast<OperateGenome &>(child);
	if (pmut <=0.0 )
		return 0;
	int nMut = 0;
	int L = 4;	//马尔可夫链长L	
	int Iter = 0;					//确定温度下稳定能量时的循环变量
	int GenNum = 0;					//迭代次数
	int MaxNum = 10;				//最大迭代次数
	double Lmd = 0.9;				//退温系数
	double T;						//温度
	double pr = 0.1;				//初温系数
	double df;						//函数值改变量

	c.fitness = c.evaluate();
	OperateGenome CurrentGenome(c);	// 当前解
	OperateGenome tmpGenome(c);		//临时解
	OperateGenome BestGenome(c);	//最优解

	//确定初始温度
	{
		int Cworst = c.ga->worstfitness;
		int Cbest = c.ga->bestfitness;
		//T = -(Cworst - Cbest) / (log(pr));
		T = 10 * (Cworst - Cbest);
	}
	
	int row = 24;
	int col = 4;
	int *p = new int[col];
	bool *flag = new bool[c.length];
	do 
	{
		Iter++;
		if (Iter <= L) 
		{
			int i, j;
		
			for (i=0; i<c.length; i++) 
			{
				tmpGenome[i] = c[i];
			}
			//列举该个体的邻域
			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;
					}
				}
			}
			
			int matindex;
			for(i=0; i<row; i++)
			{
				for(j=0; j<col; j++)
				{
					matindex = mat[i][j];
					tmpGenome[p[j]] = c[p[matindex]];
				}
				
				tmpGenome.fitness = tmpGenome.evaluate();
				df = tmpGenome.fitness - CurrentGenome.fitness;
				if (df <= 0) 
				{
					CurrentGenome = tmpGenome;
					if (CurrentGenome.fitness < BestGenome.fitness) 
					{
						BestGenome = CurrentGenome;
					}
				}
				else if (exp(-df/T) > Random::RandomDouble()) 
				{
					CurrentGenome = tmpGenome;
				}
			}
			
		}
		else
		{
			GenNum++;
			//cout << GenNum << "\t" << BestGenome.fitness << endl;
			if (GenNum >= MaxNum) 
			{
				break;
			}
			Iter = 0;
			T = T * Lmd;
		}
		
	} while(1);
	delete []flag;
	delete []p;
	c = BestGenome;	
	return c.fitness;
}