www.pudn.com > JSP.zip > JSP.cpp, change:2009-11-09,size:5586b


// JSP.cpp : Defines the entry point for the console application. 
// 
 
 
#include<iostream> 
#include<vector> 
#include<ctime> 
using namespace std; 
const int INFINITY=60000; 
const int size=20;  /*群体或种群的大小*/ 
const double mateRate=0.9;/*交配概率*/ 
const double changeRate=0.01;/*变异概率*/ 
 
vector< vector<int> > jobArray; 
int jobNum; 
int proNum; 
int calTime(vector<int> &result);/*计算一个作业序列完成所需要的时间*/ 
void randomResult(vector<int> &result);/*随机产生一个作业序列*/ 
double evaluate(vector<int> &result,double curMax);/*适应函数*/ 
void genSpecies(vector< vector<int> > &oldgroup,vector< vector<int> > &newgroup,double curMax);/*产生种群*/ 
void mate(vector<int> &left,vector<int> &right);/*交配*/ 
bool existBeforePos(vector<int> &array,int pos,int data); 
void change(vector<int> &result);/*变异*/ 
void solve(vector<int> &result); 
int main() 
{ 
	freopen("in.txt","r",stdin); 
	freopen("out.txt","w",stdout); 
 
	srand((unsigned)time(NULL)); 
 
	int i,j; 
 
	cin>>jobNum>>proNum; 
	jobArray.resize(jobNum); 
	for(i=0;i<jobNum;i++) 
		jobArray[i].resize(proNum); 
 
	for(i=0;i<jobNum;i++) 
	{ 
		for(j=0;j<proNum;j++) 
			cin>>jobArray[i][j]; 
	} 
	vector<int> result; 
	result.resize(jobNum); 
 
	 
	solve(result); 
	 
	for(i=0;i<jobNum;i++) 
		cout<<result[i]; 
	cout<<endl; 
	cout<<calTime(result)<<endl; 
	 
	 
	 
 
	fclose(stdin); 
	fclose(stdout); 
 
	return 0; 
} 
int calTime(vector<int> &result)/*计算一个作业序列完成所需要的时间*/ 
{ 
	int i,k,j; 
	vector<int> beginTime(jobNum); 
	vector<int> endTime(jobNum); 
 
	vector<int> tempTime(jobNum); 
 
	beginTime[0]=0; 
	k=0; 
	for(i=1;i<jobNum;i++) 
	{ 
		beginTime[i]=beginTime[i-1]+jobArray[ result[k] ][0]; 
		endTime[i-1]=beginTime[i]; 
		k++; 
	} 
	endTime[jobNum-1]=beginTime[jobNum-1]+jobArray[ result[jobNum-1] ][0]; 
 
	for(i=1;i<proNum;i++) 
	{ 
		tempTime[0]=endTime[0]; 
		for(j=1;j<jobNum;j++) 
		{ 
			tempTime[j]=endTime[j]>tempTime[j-1]+jobArray[ result[j-1] ][i]?endTime[j]:tempTime[j-1]+jobArray[ result[j-1] ][i]; 
		} 
 
		for(k=0;k<jobNum;k++) 
		{ 
			beginTime[k]=tempTime[k]; 
			endTime[k]=beginTime[k]+jobArray[ result[k] ][i]; 
		} 
	} 
 
	return endTime[jobNum-1]; 
	 
} 
/*适应函数,由于是要求最短时间,而适应值是较大者为优,故令适应函数值=无穷值-所需时间。同时为了增加 
适应函数值间的差距,利用于下面的算法。*/ 
double evaluate(vector<int> &result,double curMax)  
{ 
	if(INFINITY-calTime(result)<curMax) 
		return 1/(curMax-INFINITY+calTime(result)); 
	else 
		return INFINITY; 
} 
void randomResult(vector<int> &result)/*随机产生一个作业序列*/ 
{ 
	int i; 
	vector<bool> visited(jobNum); 
	for(i=0;i<jobNum;i++) 
		visited[i]=false; 
	int s=jobNum; 
	int temp; 
	while(s>0) 
	{ 
		temp=rand()%jobNum; 
		if(visited[temp]==false) 
		{ 
			visited[temp]=true; 
			result.push_back(temp); 
			s--; 
		} 
 
	} 
} 
void solve(vector<int> &result) 
{ 
	int i,g; 
	vector< vector<int> > oldgroup(size); 
	vector< vector<int> > newgroup(size); 
	for(i=0;i<size;i++) 
	{ 
		oldgroup[i].reserve(jobNum); 
		newgroup[i].resize(jobNum); 
	} 
	for(i=0;i<size;i++) 
	{ 
		randomResult(oldgroup[i]);/*随机产生一个群体*/ 
 
		newgroup[i].resize(jobNum); 
	} 
	int maxGen=150; /*最大代数*/ 
	double maxvalue=0;/*当前所得到最优适应函数值*/ 
	int pos;/*存储最大适应值所对应的作业序列在群体中的下标*/ 
	double temp; 
	for(g=0;g<maxGen;g++) 
	{ 
		genSpecies(oldgroup,newgroup,maxvalue);/*产生种群*/ 
		for(i=0;i<size;i+=2) 
		{ 
			if((double)rand()/RAND_MAX<=mateRate) 
			{ 
				mate(newgroup[i],newgroup[i+1]);/*交配*/ 
			} 
		} 
		for(i=0;i<size;i++) 
		{ 
			if((double)rand()/RAND_MAX<=changeRate) 
			{ 
				change(newgroup[i]);/*变异*/ 
			} 
		} 
		for(i=0;i<size;i++) 
			oldgroup[i]=newgroup[i];/*令群体为当前种群*/ 
 
 
		/*求解当前最优适应值及所对应的作业序列*/ 
		temp=maxvalue; 
		for(i=0;i<size;i++) 
		{ 
			if(evaluate(oldgroup[i],maxvalue)>temp) 
			{ 
				temp=evaluate(oldgroup[i],maxvalue); 
				pos=i; 
			} 
		} 
		maxvalue=temp; 
 
	} 
	 
 
	result=oldgroup[pos];/*得出解*/ 
} 
void genSpecies(vector< vector<int> > &oldgroup,vector< vector<int> > &newgroup,double curMax) 
{ 
	int i,k,j; 
	double sum=0,s=0; 
	vector<double> value(size); 
	for(i=0;i<size;i++) 
	{ 
		value[i]=evaluate(oldgroup[i],curMax); 
		sum+=value[i]; 
	} 
 
	/*用轮盘赌算法产生一个种群*/ 
	k=0; 
	while(k<size) 
	{ 
		double temp=(double)rand()/RAND_MAX; 
		j=0; 
		s=0; 
		while((double)s/sum<temp) 
		{ 
			s+=value[j]; 
			j++; 
		} 
		if(j==0) 
			newgroup[k]=oldgroup[0]; 
		else 
			newgroup[k]=oldgroup[j-1]; 
		k++; 
	} 
} 
void mate(vector<int> &left,vector<int> &right)/*交配*/ 
{ 
	vector<int> templeft(jobNum); 
	vector<int> tempright(jobNum); 
	templeft=left; 
	tempright=right; 
 
	int pos=rand()%jobNum; 
	int i,j; 
	for(i=pos;i<jobNum;i++) 
	{ 
		for(j=0;j<jobNum;j++) 
		{ 
			if(!existBeforePos(left,i,tempright[j])) 
			{ 
				left[i]=tempright[j]; 
				break; 
			} 
		} 
 
	} 
 
	 
	for(i=pos;i<jobNum;i++) 
	{ 
		for(j=0;j<jobNum;j++) 
		{ 
			if(!existBeforePos(right,i,templeft[j])) 
			{ 
				right[i]=templeft[j]; 
				break; 
			} 
		} 
	} 
} 
bool existBeforePos(vector<int> &array,int pos,int data)/*若data在位置pos之前存在,则返回真,否则返回假*/ 
{ 
	if(pos>=array.size() || pos<0) 
		return false; 
	int i; 
	for(i=0;i<pos;i++) 
	{ 
		if(array[i]==data) 
			return true; 
	} 
	return false; 
} 
void change(vector<int> &result)  /*变异*/ 
{ 
	int pos1=rand()%jobNum; 
	int pos2=rand()%jobNum; 
	while(pos1==pos2) 
	{ 
		pos1=rand()%jobNum; 
		pos2=rand()%jobNum; 
	} 
	int temp=result[pos2]; 
	result[pos2]=result[pos1]; 
	result[pos1]=temp; 
 
}