jspga.cpp

这是一个柔性加工车间的优化调度的遗传算法

#include "stdafx.h"
#include "jspga.h"

//作者林献坤，[e-mail]
//作者有大量的智能算法，欢迎交流

extern SYSPARA gasp;

//0:不指定新的种子，1：指定新的种子
int bgenrnd = 1;

//返回为0-1之间的随机数
double genrnd()
{
	if(bgenrnd == 1)
	{
		SYSTEMTIME st;	GetLocalTime(&st);
		unsigned tm = (unsigned) st.wMilliseconds;	//通过获得毫秒的时间数
		srand(tm); //获取随机的种子
		bgenrnd = 0;						
	}

	double p = (rand()%1000)/1000.0;				//在随机种子的引导下获取随机数
	return p;
}

//获得1-ninput的整数
int ngrnd(int ninput)
{
	int m = int(genrnd() * ninput);
	m = m + 1;
	return m;
}

//实现约束条件下，填充所有rowno对应行的染色体 
BOOL SGA::bFitRowCon(int rowno,PERSN *persn)
{
	BOOL bretn = TRUE;

	int worknum = 0;	//总生产量
	
	int lstdayno = 0;	//最后一天微调

	//总生产量的约束
	while( worknum < gasp.ncont3[rowno])
	{
		//获得加工的某个日期,实现了交工期的约束
		int ngetday = ngrnd(gasp.ncont2[rowno]);  
		
		//获得日夹具范围内的一个值，实现日可能使用的夹具的约束
		int ngetnum = ngrnd(gasp.ncont1[rowno]);	
		
		//对应的工件在ngetday那天加工ngetnum个
		persn->chrom.abc[rowno][ngetday-1] = ngetnum;
		
		int sumnum = 0;

		//实现总加工夹具的统计
		for(int j = 0; j < gasp.ncont2[rowno]; j++)
		{
			sumnum = sumnum + persn->chrom.abc[rowno][j];
		}
		worknum = sumnum;
		lstdayno = ngetday;
	}

	//开始进入微调节，最后分配的进行微调
	while( worknum != gasp.ncont3[rowno])
	{
		int ntemp = persn->chrom.abc[rowno][lstdayno-1];
		ntemp--;
		persn->chrom.abc[rowno][lstdayno-1] = ntemp;
		
		int sumnum = 0;
		for(int j = 0; j < gasp.ncont2[rowno]; j++)
		{
			sumnum = sumnum + persn->chrom.abc[rowno][j];
		}
		worknum = sumnum;
	}
	return bretn;
}

//对列进行判定  FALSE 不满足  selcol选种的列
BOOL SGA::isfitVerCon(int selcol,PERSN *persn)
{
	//条件1的判定
	double bcolsum = 0;
	for(int j = 0; j < gasp.genenum; j++)
	{
		bcolsum = bcolsum + persn->chrom.abc[j][selcol] * gasp.bcont1[j];
	}
	if (bcolsum > 11.0)
		return FALSE;

	//条件2的判定
	int npoint = 0;
	for(j = 0; j < gasp.genenum; j++)
	{
		//gasp.nconts[][0]中取计算的指针
		if(persn->chrom.abc[gasp.nconts[j][0]][selcol] > 0)
		{
			npoint = j + 1;	//获得读取参数数组的指针
			break;
		}
	}

	int ncolsum = 0;
	for(j = 0; j < gasp.genenum; j++)
	{
		if(persn->chrom.abc[j][selcol] > 0)
			ncolsum	= ncolsum + gasp.nconts[npoint][j];	//有加工的工件的刀具相加
	}

	if (ncolsum > 99)
		return FALSE;	//不符

	return TRUE;
}

//开始对行进行微调满足列
BOOL SGA::bmFitVerCon(int fitcol,PERSN *persn)
{
	if(fitcol >= gasp.chromnum)
		return FALSE;

	int selrow = ngrnd(gasp.genenum) - 1;

	//选择有加工件的行
	while(persn->chrom.abc[selrow][fitcol] <= 0)
	{
		selrow = ngrnd(gasp.genenum) - 1;
	}
	
	TRACE("%d行%d列开始微调\n",selrow,fitcol);

	BOOL bcontinue = TRUE;
	
	int seltedcol[MAXCHROMNUM]; memset(seltedcol,0,MAXCHROMNUM * sizeof(int));
	while (bcontinue)
	{
		
		bcontinue = FALSE;
		for(int k = 0; k < gasp.chromnum; k++)
		{
			if(seltedcol[k] != 0xffff)
			{
				bcontinue = TRUE;	//遍历是否还有可行的位置
				break;
			}
		}
		if(!bcontinue) return FALSE;		//如果都已经选上了，就终止

		int getcol = ngrnd(gasp.chromnum) - 1;
		int ntemp = persn->chrom.abc[selrow][getcol];

		if(seltedcol[getcol] == 0xffff) continue;	//已经为非可行方案就继续

		//不能超过单天的约束
		if (getcol == fitcol || ntemp >= gasp.ncont1[selrow])
		{
			TRACE("can not find fittable,selrow = %d,getcol = %d\n",selrow,getcol);
			seltedcol[getcol] = 0xffff;		//给不能选择的列做上标志
			continue;
		}
		
		//选择符合条件的列给予多一个1
		persn->chrom.abc[selrow][getcol] = ntemp + 1;	
		
		if(isfitVerCon(getcol,persn))
		{
			//如果可以则移动一个工件
			persn->chrom.abc[selrow][fitcol] = persn->chrom.abc[selrow][fitcol] - 1;
			if(!isfitVerCon(fitcol,persn))
			{
				TRACE("减少一个还不行则，继续减少\n");
				continue;
			}
			else 
			    bcontinue = FALSE;
		}
		else
		{	
			//这种欲选定的列不满足，则
			persn->chrom.abc[selrow][getcol] = ntemp;	//返回原来的值
			seltedcol[getcol] = 0xffff;
		}
		
	}

	TRACE("%d列微调结束\n",fitcol);
	return TRUE;
}


//实现约束条件下，实现从列方向对persn染色体进行调节
BOOL SGA::bFitVerCon(PERSN *persn)
{
	int fitcont1[MAXCHROMNUM];
	int fitcont2[MAXCHROMNUM];

	memset(fitcont1,0,MAXCHROMNUM * sizeof(int));
	memset(fitcont2,0,MAXCHROMNUM * sizeof(int));

	//条件1：累计加工时间<11天的判定
	for(int i = 0; i < gasp.chromnum; i++)
	{
		double bcolsum = 0;
		for(int j = 0; j < gasp.genenum; j++)
		{
			bcolsum = bcolsum + persn->chrom.abc[j][i] * gasp.bcont1[j];
		}
		if (bcolsum > 11.0)
			fitcont1[i] = 0xff;		//不符
		else
			fitcont1[i] = 0x01;		//符合条件
	}

	//开始进行条件1微调
	for(i = 0; i < gasp.chromnum; i++)
	{
		if(fitcont1[i] == 0xff)
		{
			while (!bmFitVerCon(i,persn)){};		//一直找到可行解
			TRACE("person[%d]条件1微调结束\n",i);
		}
	}

	//条件2：每天使用的刀具数总和<99的判定
	for(i = 0; i < gasp.chromnum; i++)
	{
		int npoint = 0;
		for(int j = 0; j < gasp.genenum; j++)
		{
			//gasp.nconts[][0]中取计算的指针
			if(persn->chrom.abc[gasp.nconts[j][0]][i] > 0)
			{
				npoint = j + 1;	//获得读取参数数组的指针
				break;
			}
		}

		int ncolsum = 0;
		for(j = 0; j < gasp.genenum; j++)
		{
			if(persn->chrom.abc[j][i] > 0)
				ncolsum	= ncolsum + gasp.nconts[npoint][j];	//有加工的工件的刀具相加
		}

		if (ncolsum > 99)
			fitcont2[i] = 0xff;		//不符
		else
			fitcont2[i] = 0x01;		//符合条件
	}

	//开始进行微调条件2
	for(i = 0; i < gasp.chromnum; i++)
	{
		if(fitcont2[i] == 0xff)
		{
			while (!bmFitVerCon(i,persn)){};		//一直找到可行解
			TRACE("person[%d]条件2微调结束\n",i);
		}
	}
	return TRUE;
}


//获得初始的群体
BOOL SGA::InitPops()
{
	/*
	//按加工期的长短排序
	int nNoByJGQ[MAXGENENUM];
	memset(nNoByJGQ,0,MAXGENENUM);

	int ntemp[MAXGENENUM];
	memcpy(ntemp,&gasp.ncont2[0],MAXGENENUM);//从加工期内拷贝数据

	for(int k = 0; k < gasp.genenum; k++)
	{
		int nMax = 0; int nMaxNo = 0;
		for(int i = 0; i < gasp.genenum; i++)
		{
			if(ntemp[i] > nMax)
			{
				nMax = ntemp[i];
				nMaxNo = i;
			}
		}

		ntemp[nMaxNo] = 0;	//找到最大值之后，置成0成最小值
		nNoByJGQ[k] = nMaxNo;
	}
	*/

	for(int j = 0; j < gasp.popsize; j++)
	{
		BOOL bfitRow = 0;
		BOOL bfitcol = 0;
		for(int i = 0; i < gasp.genenum; i++)
		{
			bFitRowCon(i,&persns[j]);	//适合行约束
		}

		bFitVerCon(&persns[j]);	//实现对列微调节
		TRACE("%d个体调节正常\n",j);
	}

	return TRUE;
}

BOOL SGA::Select()
{


	return TRUE;
}

BOOL SGA::Crsover()
{


	return TRUE;
}

BOOL SGA::Mutate()
{


	return TRUE;
}