gaonkp.cpp

利用遗传算法解决背包问题

#include "GAonKP.h"
#include <time.h>
#include <math.h>
#include <iostream>
#include <stdio.h>
using namespace std;
CGAonKP::CGAonKP()
{
	index=0;
	nindex=1;
	EndValue=0;
	EndWeight=0;
	
}
CGAonKP::~CGAonKP()
{
	delete [] Element;
	Element=0;
	delete[] adaptive_value;
	delete[] Wheel;
	delete[] Endx;
	Endx=0;
	Wheel=0;
	adaptive_value=0;
	

}
long CGAonKP::ReadInt(FILE* in)
{
	char dum, dummy[128];
	for(;;)
	{
		fscanf(in,"%s", dummy);
		if(dummy[0]=='#' && strlen(dummy)>1 && dummy[strlen(dummy)-1]=='#') {}//单行#----#
		else if(dummy[0]=='#') 
		{
			do
			{
				fscanf(in,"%c", &dum);//多行连接#-----
				//-----#                		 　　　　　　　　　　　　　　　　
			} while(dum!='#');
		}
		else                   
		{
			return atoi(dummy); //读到数据将其转化为ｉｎｔ型数存储
		} 
	}

}
double CGAonKP::ReadDouble(FILE* in)
{
	char dum, dummy[128];
	for(;;)
	{
		fscanf(in,"%s", dummy);
		if(dummy[0]=='#' && strlen(dummy)>1 && dummy[strlen(dummy)-1]=='#') {}
		else if(dummy[0]=='#') 
		{
			do
			{
				fscanf(in,"%c", &dum);
			} while(dum!='#');
		}
		else                   
		{
			return atof(dummy); //atof是什么函数/转化为什么型的数是double还是float型数据
			break;
		} 
	}

}
double CGAonKP::GetSum(int *che)
{
	double sum=0;
	for (int i=0;i<chN;i++)
	{
		if (che[i])
		{
			sum+=Element[i][0];
		}
	}
	return sum;
}
double CGAonKP::GetAdaptiveValue(int *che)
{
	double sum=0;
	for (int i=0;i<chN;i++)
	{
		if (che[i])
		{
			sum+=Element[i][1];
		}
	}

	return sum;
}
void CGAonKP::GetAdaVector()
{
	for (int i=0;i<scale;i++)
	{
		adaptive_value[i]=GetAdaptiveValue(x_m[index].pMatrix[i]);
		if (adaptive_value[i]>EndValue)
		{
			EndValue=adaptive_value[i];
			for (int j=0;j<chN;j++)
			{
				Endx[j]=x_m[index].pMatrix[i][j];
				EndWeight=GetSum(x_m[index].pMatrix[i]);
			}
		}
	}
}
void CGAonKP::GetWheel()
{
	double sum=0;
	int i;
	for (i=0;i<scale;i++)
	{
		sum+=adaptive_value[i];
	}
	for (i=0;i<scale;i++)
	{
		Wheel[i]=adaptive_value[i]/sum;
	}
	for (i=1;i<scale;i++)
	{
		Wheel[i]+=Wheel[i-1];
	}
}
void CGAonKP::SelectV()
{
	double temp;
	int i,j;
	int* h_v=new int[scale];
	for (i=0;i<scale;i++)
	{
		temp=RandomDist(0,1);
		if (temp<=Wheel[0])
		{
			h_v[i]=0;
		}
		else
		{
			for (j=1;j<scale;j++)
			{
				if (temp<=Wheel[j]&&temp>Wheel[j-1])
				{
					h_v[i]=j;
					break;
				}
			}
		}
	}
	for (i=0;i<scale;i++)
	{
		for (j=0;j<chN;j++)
		{
			x_m[nindex].pMatrix[i][j]=x_m[index].pMatrix[h_v[i]][j];
		}
	}
	delete[] h_v;
}
void CGAonKP::HybriVariat()
{
	int tempi,tempj;
	int temp;
	int i,j;
	for (i=0;i<scale;i++)
	{
		if (RandomDist(0,1)<pc)
		{
			do
			{
				tempi=rand()%chN;
				tempj=rand()%chN;
				temp=x_m[nindex].pMatrix[i][tempi];
				x_m[nindex].pMatrix[i][tempi]=x_m[nindex].pMatrix[i][tempj];
				x_m[nindex].pMatrix[i][tempj]=temp;
			}while (!JudgeSatis(x_m[nindex].pMatrix[i]));

			if (RandomDist(0,1)<pm)
			{
				do
				{
					tempi=rand()%chN;
					temp=rand()%2;
					x_m[nindex].pMatrix[i][tempi]=temp;
				}while (!JudgeSatis(x_m[nindex].pMatrix[i]));
			}

		}
		
	}

}
bool CGAonKP::JudgeSatis(int* che)
{
	if (MaxWeight<GetSum(che))
	{
		return false;
	}
	return true;
}

void CGAonKP::Initial(FILE* fp)
{
	

	int i,j;
	chN=ReadInt(fp);
	Wheel=new double[scale];
	Element=new double[chN][2];
	Endx=new int[chN];
	for (i=0;i<chN;i++)
	{
		Element[i][0]=ReadDouble(fp);
		Element[i][1]=ReadDouble(fp);
	}
	for (i=0;i<chN;i++)
		if (MaxWeight>=Element[i][0]) break;
	if (i==chN)
	{
		cout<<"对不起任何备选物品中质量都大于您输入的背包允许质量！"<<endl;
		exit(0);
	}
	adaptive_value=new double[scale];
	x_m[index].ObtainMemory(scale,chN);
	x_m[nindex].ObtainMemory(scale,chN);
	for (i=0;i<scale;i++)
	{
		do
		{
			for (j=0;j<chN;j++)
			{
				x_m[index].pMatrix[i][j]=rand()%2;
			}
		}while (!JudgeSatis(x_m[index].pMatrix[i]));
	}
	
	
}
double CGAonKP::RandomDist(int a, int b)
{
	if(a==b){cout<<"illegal Argument!"<<endl; exit(0);}
	return ((double)rand()/RAND_MAX * (b-a) + a);
}
/********************************************************************************/
/* 函数名： GetSolute(double max_weight,double PC,double PM,int chn,int max_gen)*/
/*   参数：max_weight 背包允许最大财宝质量                                      */
/*           PC         杂交概率                                                */
/*           PM         变异概率                                                */
/*           SCALE      种群规模                                                */
/*           max_gen    最大进化代数                                            */
/********************************************************************************/
void CGAonKP::GetSolute(double max_weight,double PC,double PM,int SCALE,int max_gen,FILE* fp)
{
	MaxWeight=max_weight;
	pc=PC;
	pm=PM;
	scale=SCALE;
	maxgen=max_gen;
	srand((int)time(0));
	Initial(fp);
	GetAdaVector();
	for (int k=0;k<max_gen;k++)
	{	
	
		GetWheel();
		SelectV();
		HybriVariat();
		if (index)
		{
			index=0;
			nindex=1;	
		}
		else
		{
			index=1;
			nindex=0;
		}
		GetAdaVector();
	}

	int i;
	cout<<endl<<endl<<"输出运算结果："<<endl;
	cout<<"最后结果价值总量："<<EndValue<<endl;
	cout<<"最后结果质量："<<EndWeight<<endl;
	cout<<"最后结果所选个体："<<endl;
	for (i=0;i<chN;i++)
	{
		cout<<Endx[i]<<"  ";
	}
	cout<<endl;
	
	FILE* fpout=fopen("output.txt","w");
	fprintf(fpout,"程序运行结果输出\n");
	fprintf(fpout,"最后结果价值总量：\n");
	fprintf(fpout,"%g\n",EndValue);
	fprintf(fpout,"最后结果质量：\n");
	fprintf(fpout,"%g\n",EndWeight);
	fprintf(fpout,"最后结果所选个体：\n");
	for (i=0;i<chN;i++)
	{
		fprintf(fpout,"%d ",Endx[i]);
	}
	fprintf(fpout,"\n");
	fclose(fpout);

}