generational.cpp

用遗传算法解0/1背包问题

//用遗传算法解0/1背包问题
#define NUM 100//总的物体的个数
#define SCH 500//每一代总的方案个数
#include<iostream>
#include<time.h>
using namespace std;

int Random(int number){
	return (int)(number/(double)RAND_MAX*rand());
}

class Generation{
	public:
		int  Scheme[SCH][NUM];
		int  Temp[SCH][NUM];
		float W[NUM];//权值数组
 		float	P[NUM];//价值数组
 		float C;//背包重量的上限值
		Generation(float* ww,float* pp,float cc);
		float EvaluateProS(int plan);//评价第plan个方案的利润
		float EvaluateWeight(int *a);
		void TwoCross(int n1,int n2,int pos,int* a,int* b);//两个方案进行单点交叉，pos为交叉点的位置
		void Copy(int num);//直接复制到下一代中的个体,num表示直接复制的个体的数目
		void Cross(int num);//交叉产生下一代个体，num表示产生的下一代个体的数目
		void Mutation(float rate);//变异，rate表示变异率
		void Generate(int copy,int cross,float rate);//产生下一代;
		float GetBestPro(int& num);//计算出最好方案的利润，num返回方案的序号
	};

Generation::Generation(float* ww,float* pp,float cc){
	C=cc;
	for(int j=0;j<NUM;j++){
		W[j]=ww[j];
		P[j]=pp[j];
	}
	int temp=0;
	int i=0;
	while(i<SCH){
		int weight=0;
		for(int j=0;j<NUM;j++){
				temp=Random(11);
				if(temp>5) temp=1;
					else temp=0;
				Scheme[i][j]=temp;
				weight=weight+temp*W[j];
		}
		if(weight<=C){
			i++;
			}
	 }
	 for(i=0;i<SCH;i++)
	 		for(int j=0;j<NUM;j++)
	 				Temp[i][j]=0;
}

float Generation::EvaluateProS(int plan){
	float profit=0;
	for(int i=0;i<NUM;i++){
		profit=profit+Scheme[plan][i]*P[i];
	}
	return profit;
}

float Generation::EvaluateWeight(int *a){
	float weight=0;
	for(int i=0;i<NUM;i++){
		weight=weight+W[i]*a[i];
	}
	return weight;
}
void Generation::Copy(int num){
	int i=1;
	while(i<=num){
		int MAXP=0;
		int MAXS=0;
		int temp=0;
		for(int j=0;j<7;j++){
			temp=Random(SCH);
			float t=EvaluateProS(temp);
			if(MAXP<t){
				MAXP=t;
				MAXS=temp;
			}
		}
		for(j=0;j<NUM;j++){
				Temp[MAXS][j]=Scheme[MAXS][j];
			}
			i++;
	}
}

void Generation::TwoCross(int n1,int n2,int pos,int* array1,int* array2){
	for(int i=0;i<pos;i++){
	array1[i]=Scheme[n2][i];
	array2[i]=Scheme[n1][i];
	}
	for(i=pos;i<NUM;i++){
		array1[i]=Scheme[n1][i];
		array2[i]=Scheme[n2][i];
	}
}

void Generation::Cross(int num){
	int nn=1;
	while(nn<num){
		
		int MAXP=0;
		int MAXS=0;
		int temp=0;
		for(int j=0;j<7;j++){
			temp=Random(SCH);
			float t=EvaluateProS(temp);
			if(MAXP<t){
				MAXP=t;
				MAXS=temp;
			}
		}
		int Par1=MAXS;
		int array1[NUM];
		 MAXP=0;
		 MAXS=0;
		 temp=0;
		for(j=0;j<7;j++){
			temp=Random(SCH);
			float t=EvaluateProS(temp);
			if(MAXP<t){
				MAXP=t;
				MAXS=temp;
			}
		}
		int Par2=MAXS;
		int array2[NUM];
		for(int i=0;i<NUM;i++){
			array1[i]=0;
			array2[i]=0;
		}
		int flag=0;
			for(j=0;j<NUM;j++){
				TwoCross(Par1,Par2,j,array1,array2);
				if(EvaluateWeight(array1)<=C&&EvaluateWeight(array2)<=C){
					flag=1;
					break;
				}
			}
			if(flag==1) {
				for(int k=0;k<NUM;k++){
				Temp[Par1][k]=array1[k];
				Temp[Par2][k]=array2[k];
				}
				nn++;
			}
	}
}
		

		
void Generation::Mutation(float rate){
	int num=rate*SCH;
	int i=1;
	while(i<=num){
		int plan=Random(SCH);
		int pos=Random(NUM);
		int array[NUM];
		for(int k=0;k<NUM;k++){
			array[k]=Temp[plan][k];
		}
		if(array[pos]==1)
			array[pos]=0;
			else if(array[pos]==0) 
				array[pos]=0;
		if(EvaluateWeight(array)<=C){
			Temp[plan][pos]=array[pos];
			i++;
		}
			
	}
}

void Generation::Generate(int copy,int cross,float rate){
	Copy(copy);
	Cross(cross);
	Mutation(rate);
	for(int i=0;i<SCH;i++)
		for(int j=0;j<NUM;j++){
			Scheme[i][j]=Temp[i][j];
			Temp[i][j]=0;
		}
	}

float Generation::GetBestPro(int& num){
	float best=0;
	int i=0;
	for(i=0;i<SCH;i++){
		float temp=0;
		temp=EvaluateProS(i);
		if(best<temp){
			best=temp;
			num=i;
		}
	}
	return best;
}
						
void main(){
		srand(time(0));
		float W[NUM]={253,245,243,239,239,239,238,238,237,232,
   					  231,231,230,229,228,227,224,217,213,207,
   					  203,201,195,194,191,187,187,177,175,171,
   					  169,168,166,164,161,160,158,150,149,147,
   					  141,140,139,136,135,132,128,126,122,120,
   					  119,116,116,114,111,110,105,105,104,103,
   					  93,92,90,79,78,77,76,76,75,73,
   					  62,62,61,60,60,59,57,56,53,53,
   					  51,50,44,44,42,42,38,36,34,28,
   					  27,24,22,18,12,10,7,4,4,1};
		float	P[NUM]={253,245,243,239,239,239,238,238,237,232,
   					  231,231,230,229,228,227,224,217,213,207,
   					  203,201,195,194,191,187,187,177,175,171,
   					  169,168,166,164,161,160,158,150,149,147,
   					  141,140,139,136,135,132,128,126,122,120,
   					  119,116,116,114,111,110,105,105,104,103,
   					  93,92,90,79,78,77,76,76,75,73,
   					  62,62,61,60,60,59,57,56,53,53,
   					  51,50,44,44,42,42,38,36,34,28,
   					  27,24,22,18,12,10,7,4,4,1};//价值数组
		float C=6666;//背包的重量
		int num=0;
		float best;
		float weight=0;
		Generation	GM(W,P,C);
		for(int i=1;i<=20;i++){
			GM.Generate(50,450,0.02);
		}
		best=GM.GetBestPro(num);
		cout<<"The best profit is:"<<best<<endl;
		cout<<"The Scheme vector is:"<<endl;
		for(i=0;i<NUM;i++){
			cout<<GM.Scheme[num][i]<<" ";
			weight=weight+GM.Scheme[num][i]*W[i];
		}	
		cout<<endl<<"The weight is:"<<weight<<endl;
	}