knapsack.cpp

用GAlib库实现的解决0/1背包问题的遗传算法程序源代码。

/* ----------------------------------------------------------------------------
  gaknapsack.cpp by yweiqin in Wuhan University, 2004-05.
  It uses genetic algorithm to solve 0/1knapsack problem on the basis of GAlib.  
---------------------------------------------------------------------------- */
#include <stdio.h>
#include <iostream.h>
#include <fstream.h>
#include <ga/ga.h>
//定义编译开关
#define GREEDREPAIR               //使用贪婪修复
#define MIXGREEDGENOME            //初始种群带贪心解
//定义常量
#define POPULATION_SIZE 80        //种群大小
#define NUM_GENERATIONS 500       //进化最大代数
#define PROBABILITY_MUTATION 0.01 //变异概率
#define PROBABILITY_CROSSOVER 0.6 //杂交概率
#define NUM_GOODS 50              //物品总共数量
//定义全局变量
static float WeightList[NUM_GOODS]=   //各物品的重量 
{80,82,85,70,72,70,66,50,55,25,50,55,40,48,50,32,22,60,30,32,40,38,35,32,25,28,30,22,50,30,45,30,60,50,20,65,20,25,30,10,20,25,15,10,10,10,4,4,2,1}
;
static float ValueList[NUM_GOODS]=    //各物品的价值
{220,208,198,192,180,180,165,162,160,158,155,130,125,122,120,118,115,110,105,101,100,100,98,96,95,90,88,82,80,77,75,73,72,70,69,66,65,63,60,58,56,50,30,20,15,10,8,5,3,1}
;
static float KnapsackMaxContent=1015; //背包的极限容量
static int DensityQueue[NUM_GOODS];   //各物品按密度的降序队列
//函数声明
float objective(GAGenome & c);        //目标值函数
float WeightSum(GAGenome & c);        //计算个体对应解的物品总重量
void InitDensityQueue();              //把物品按密度从大到小排序，把下标队列写入数组DensityQueue
void RandomRepair(GAGenome & c);      //不可行解的随机修复算子
int SelectRandomBit(GAGenome & c);     //为随机修复选择一个清除物品
void GreedRepair(GAGenome & c);       //不可行解的贪心修复算子
void repair(GAGenome & c);            //总的修复算子
void KnapsackGenomeInitialize(GAGenome & c);            //个体初始化算子
int KnapsackGenomeOnePointCrossover(const GAGenome& p1, const GAGenome& p2,
				GAGenome* c1, GAGenome* c2);            //杂交算子
int KnapsackGenomeFlipMutator(GAGenome & c, float pmut);//变异算子
void CreatKnapsackGreedGenome(GAGenome & c);            //生成贪心解个体
void ShowGenome(GAGenome & c);                          //输出个体的基因编码
//定义解0-1背包问题的遗传算法类
class MyKnapsackGA : public GASimpleGA{ 
public:
	MyKnapsackGA(const GAGenome& c): GASimpleGA(c){};   //构造函数
#ifdef MIXGREEDGENOME                                   
    void initialize(unsigned int seed)                  //重载算法初始化函数
	{	//调用基类的初始化函数
		GASimpleGA::initialize(seed);
		//初始化时种群中最差个体替换为贪心解个体
		GAGenome& genome = pop->worst();
		CreatKnapsackGreedGenome(genome);
		//重新评估种群中的个体
		pop->evaluate(gaTrue);	
		stats.reset(*pop);
		if(!scross) GAErr(GA_LOC, className(), "initialize", gaErrNoSexualMating);
	};
#endif
};
//主函数
int main(int argc, char **argv)
{
	cout << "应用遗传算法求解0-1背包问题\n";
    cout.flush();
    //把物品按密度从大到小排序
    InitDensityQueue();
    //创建基因组对象，并为其指定编码长度、适应值函数
    GA1DBinaryStringGenome genome(NUM_GOODS, (GAGenome::Evaluator) objective);
	//为基因组指定自定义的初始化函数、杂交算子、变异算子
	genome.initializer((GAGenome::Initializer) KnapsackGenomeInitialize);
    genome.crossover((GAGenome::SexualCrossover) KnapsackGenomeOnePointCrossover);
    genome.mutator((GAGenome::Mutator) KnapsackGenomeFlipMutator);
    //创建遗传算法对象，并为其指定基因组对象
    MyKnapsackGA ga(genome);
    //为遗传算法类指定各控制参数
    ga.populationSize(POPULATION_SIZE);         //种群大小 
    ga.nGenerations(NUM_GENERATIONS);           //进化代数
	ga.pCrossover(PROBABILITY_CROSSOVER);       //变异概率
    ga.pMutation(PROBABILITY_MUTATION);         //杂交概率
    ga.scoreFilename("score.dat");              //记录跟踪信息的文件
    ga.scoreFrequency(50);                      //记录跟踪信息的频率
    ga.flushFrequency(100);                     //输出跟踪信息到文件的频率
	//开始进化 
    ga.evolve();
    //输出求解结果 
    genome = ga.statistics().bestIndividual();
    cout << "the best individual: "; ShowGenome(genome);  
    cout << "\nthe total value: "<<objective(genome)<< "\n";
    cout << "the total weight: "<<WeightSum(genome) << "\n";
    cout << "best of each generation data are in '" << ga.scoreFilename() << "'\n";
    return 0;
}
float objective(GAGenome & c)          //目标值函数
{
    int i, genomelength;
	float sum=0;
    GA1DBinaryStringGenome & genome = (GA1DBinaryStringGenome &)c;
	genomelength=genome.length();
    for(i=0;i<genomelength;i++)
		if(genome.gene(i)!=0) sum += ValueList[i];
    return sum;
}
float WeightSum(GAGenome & c)          //个体对应解的包中物品总重量
{
    int i, genomelength;
	float sum=0;
    GA1DBinaryStringGenome & genome = (GA1DBinaryStringGenome &)c;
    genomelength=genome.length();
    for(i=0;i<genomelength;i++)
		if(genome.gene(i)!=0) sum += WeightList[i];
    return sum;
}
void InitDensityQueue()                //把物品按密度从大到小排序，把下标队列写入数组DensityQueue
{
	int i,j,no;
	float FixDensity,CursorDensity;
	for(i=0;i<NUM_GOODS;i++)
	{
		FixDensity = ValueList[i] / WeightList[i];
		no=0;
		for(j=0;j<NUM_GOODS;j++)
			if(i!=j){
				CursorDensity = ValueList[j] / WeightList[j];
				if((CursorDensity > FixDensity)||((CursorDensity == FixDensity)&&(j < i)))
					   no++;
			}
		DensityQueue[no]=i;
	}
}
void repair(GAGenome & c)              //总的修复算子
{
#ifdef GREEDREPAIR
		GreedRepair(c);
#else
		RandomRepair(c);
#endif
}
int SelectRandomBit(GAGenome & c)      //为随机修复选择一个清除物品
{
	bool foundflag=false;
	int index,rand;
	GA1DBinaryStringGenome & genome = (GA1DBinaryStringGenome &)c;
	rand = GARandomInt(0, NUM_GOODS-1);
	for(index=0; !foundflag && index<NUM_GOODS; index++)
		if(genome.gene(rand)!=0) foundflag=true;
		else rand = (rand+1)%NUM_GOODS;
	return rand;
}
void RandomRepair(GAGenome & c)        //随机修复算子
{
    bool knapsack_overfilled=false;
	float wsum;
	int index;
	GA1DBinaryStringGenome & genome = (GA1DBinaryStringGenome &)c;
	
	wsum = WeightSum(c);
	if(wsum > KnapsackMaxContent) knapsack_overfilled=true;
	while(knapsack_overfilled)
	{
        index=SelectRandomBit(c);
	    genome.gene(index, 0);
        wsum -= WeightList[index];
		if(wsum <= KnapsackMaxContent) knapsack_overfilled=false;
	}
}
void GreedRepair(GAGenome & c)         //贪心修复算子
{
	float wsum,tempwsum;
	int no,index;
	GA1DBinaryStringGenome & genome = (GA1DBinaryStringGenome &)c;
	
	wsum = 0;
	for(no=0;no<NUM_GOODS;no++)
	{
		index = DensityQueue[no];
		if(genome.gene(index)==1)
		{
			tempwsum = wsum + WeightList[index];
			if(tempwsum > KnapsackMaxContent) genome.gene(index, 0);
			else wsum = tempwsum;
		}
	}
}
int KnapsackGenomeOnePointCrossover(const GAGenome& p1,	const GAGenome& p2,
		GAGenome* c1, GAGenome* c2)                     //杂交算子
{
	GAGenome &rc1=*c1, &rc2=*c2;
	int n;
	n = GA1DBinaryStringGenome::OnePointCrossover(p1, p2, c1, c2);
	repair(rc1); repair(rc2);	
	return n;
}
int KnapsackGenomeFlipMutator(GAGenome & c, float pmut) //变异算子
{
	int nMut;
	nMut = GA1DBinaryStringGenome::FlipMutator(c, pmut);
	repair(c);
    return nMut;
}
void KnapsackGenomeInitialize(GAGenome & c)             //个体初始化算子
{
	GA1DBinaryStringGenome::UniformInitializer( c );
	repair(c);
}
void CreatKnapsackGreedGenome(GAGenome & c)             //生成贪心解个体
{
	int index;
	GA1DBinaryStringGenome & genome = (GA1DBinaryStringGenome &)c;
	for(index=0;index<NUM_GOODS;index++) genome.gene(index, 1);
	GreedRepair(genome);
}
void ShowGenome(GAGenome & c)                           //输出个体的基因编码
{
	int i;
	float wsum=0;
	GA1DBinaryStringGenome & genome = (GA1DBinaryStringGenome &)c;
	for(i=0;i<NUM_GOODS;i++) cout<<genome.gene(i);
}




//debug code
/*
//int popsize  = POPULATION_SIZE;
    //int ngen     = NUM_GENERATIONS;
    //float pmut   = PROBABILITY_MUTATION;
    //float pcross = PROBABILITY_CROSSOVER;
class MyKnapsackGA : public GASimpleGA{ 
public:
	MyKnapsackGA(const GAGenome& c): GASimpleGA(c){};
#ifdef MIXGREEDGENOME//need fix
    void initialize(unsigned int seed)
	{
    pop->initialize();
	GASimpleGA::initialize(seed);

	GAGenome& genome = pop->worst();
	CreatKnapsackGreedGenome(genome);
	//float x = WeightSum(genome);
	//cout << "    CreatKnapsackGreedGenome = "<<x<<"\n";
	//cout << objective(genome)<<"\n";
	//ShowGenome(genome);

    pop->evaluate(gaTrue);	
    stats.reset(*pop);
    if(!scross) 
      GAErr(GA_LOC, className(), "initialize", gaErrNoSexualMating);
	};
#endif
};
  
void writeBestGenome(GAGenome & c)
{
	ofstream ostrm;
	ostrm.open("bogbest.dat");
	ostrm.seekp(0,ios::end);

	int i;
	GA1DBinaryStringGenome & genome = (GA1DBinaryStringGenome &)c;

	for(i=0;i<NUM_GOODS;i++)
	{
		ostrm<<genome.gene(i);
	}
	ostrm<<"\n";
	
	ostrm.close();
}*/