package_ga.cpp

来自「本程序利用遗传算法解决背包文件问题。本程序利用遗传算法解决背包文件问题。」· C++ 代码 · 共 499 行

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
using namespace std;

#define POPSIZE 50					//种群大小
#define MAXGENS 1000				// 叠带次数　
#define NVARS 50					// 基因数目
#define PXOVER 1					// 交配概率
#define PMUTATION 0.2				// 变异概率
#define TRUE 1
#define FALSE 0
#define  MAXVOLUME 1000
int generation;						// 代数记录 
int cur_best;						// 目前最优记录 
vector<pair<int,int> > items;		//first 表示重量 second表示总体积
struct genotype						//种群个体数据结构
{

	bool gene[NVARS];
	double fitness;				// 适应值 
	double weight;				//总重量
	double volume;				//体积
	double rfitness;           // 概率
	double cfitness;           // 累计概率
	genotype(){
		weight = 0;
		for (int i = 0;i < NVARS;i++)
		{
			gene[i] = 0;
		}
		rfitness = 0;
		cfitness = 0;
		fitness = 0;
		volume = 0;
	}
};
//重量
//int c[]={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};
//体积
//int v[]={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};
int *c;
int *v;
genotype population[POPSIZE+1];    //　种群 
genotype newpopulation[POPSIZE+1]; // 新种群 

/******************函数原形声明************************************/

void initialize(void);
void evaluate(void);
void keep_the_best(void);
void elitist(void);
void select(void);
void crossover(void);
void Xover(int,int);
void swap(double *, double *);
void mutate(void);

bool judge(pair<int,int> p1,pair<int,int> p2){

	return p1.first / p1.second > p2.first > p2.second;

}
/***************************************************************/
/* Initialization：随即初始化背包基因
输入参数：无
返回值：无
注：贪心策略　无非法解产生
/***************************************************************/

void initialize(void)
{

	for (int i = 0;i < POPSIZE;i++)
	{
		int pos = rand()%NVARS;
		while(items[pos].second + population[i].volume < MAXVOLUME)
		{
			population[i].volume += items[pos].second;
			population[i].weight += items[pos].first;
			population[i].gene[pos] = 1;
			pos = (pos + 1) % NVARS;
		}
	}
	population[POPSIZE].fitness = 0;
}

/*************************************************************/
/* Evaluation ：评价函数
输入参数：无
返回值：无
注：评价标准为　背包重量/体积 * 背包重量
/*************************************************************/

void evaluate()
{

// 	double tmp = 0;
// 	for (int i = 0; i < POPSIZE;i++)
// 	{
// 		tmp += population[i].weight;
// 	}
	for (int i = 0;i < POPSIZE;i++)
	{
		//population[i].fitness = population[i].weight / tmp;
		population[i].fitness = population[i].weight / population[i].volume * population[i].weight;
	}
}

/***************************************************************/
/* Keep_the_best :保存最优个体
输入参数：　无
返回值：　无
/***************************************************************/

void keep_the_best()
{
	int mem;
	int i;
	cur_best = 0; 
	//标记最优个体
	for (mem = 0; mem < POPSIZE; mem++)
	{
		if (population[mem].fitness > population[POPSIZE].fitness)
		{
			cur_best = mem;
			population[POPSIZE].fitness = population[mem].fitness;
		}
	}
	//将最优值复制给POPSIZE个体
	for (i = 0; i < NVARS; i++)
		population[POPSIZE].gene[i] = population[cur_best].gene[i];
	population[POPSIZE].weight = population[cur_best].weight;
	population[POPSIZE].volume = population[cur_best].volume;
}

/****************************************************************/
/* Elitist function:调整种群，保存最优
输入参数：无
返回值：无
注：最优解保存在population最后一项，如果当前子代无更优解，则替代
子代中最差解，否则更新最优解
/****************************************************************/

void elitist()
{
	int i;
	double best, worst;             /* best and worst fitness values */
	int best_mem, worst_mem; /* indexes of the best and worst member */

	best = population[0].fitness;
	worst = population[0].fitness;
	for (i = 0; i < POPSIZE - 1; ++i)
	{
		if(population[i].fitness > population[i+1].fitness)
		{      
			if (population[i].fitness >= best)
			{
				best = population[i].fitness;
				best_mem = i;
			}
			if (population[i+1].fitness <= worst)
			{
				worst = population[i+1].fitness;
				worst_mem = i + 1;
			}
		}
		else
		{
			if (population[i].fitness <= worst)
			{
				worst = population[i].fitness;
				worst_mem = i;
			}
			if (population[i+1].fitness >= best)
			{
				best = population[i+1].fitness;
				best_mem = i + 1;
			}
		}
	}
	//根据情况更新最优解或者替代最差解

	if (best >= population[POPSIZE].fitness)
	{
		for (i = 0; i < NVARS; i++)
			population[POPSIZE].gene[i] = population[best_mem].gene[i];

		population[POPSIZE].fitness = population[best_mem].fitness;
		population[POPSIZE].volume = population[best_mem].volume;
		population[POPSIZE].weight = population[best_mem].weight;
	}
	else
	{
		for (i = 0; i < NVARS; i++)
			population[worst_mem].gene[i] = population[POPSIZE].gene[i];

		population[worst_mem].fitness = population[POPSIZE].fitness;
		population[worst_mem].weight = population[POPSIZE].weight;
		population[worst_mem].volume = population[POPSIZE].volume;
	} 
}
/**************************************************************/
/* Selection ：根据轮盘赌的算法选取个体
输入参数：无
返回值：无
/**************************************************************/

void select()
{
	int mem, i, j, k;
	double sum = 0;
	double p;

	//计算总的适应度
	for (mem = 0; mem < POPSIZE; mem++)
	{
		sum += population[mem].fitness;
	}

	//计算概率
	for (mem = 0; mem < POPSIZE; mem++)
	{
		population[mem].rfitness =  population[mem].fitness / sum ;
	}
	population[0].cfitness = population[0].rfitness;

	//计算累计概率
	for (mem = 1; mem < POPSIZE; mem++)
	{
		population[mem].cfitness =  population[mem-1].cfitness +       
			population[mem].rfitness;
	}


	//轮盘赌选择
	for (i = 0; i < POPSIZE; i++)
	{ 
		p = rand()%1000/1000.0;
		if (p < population[0].cfitness)
			newpopulation[i] = population[0];      
		else
		{
			for (j = 0; j < POPSIZE;j++)      
				if (p >= population[j].cfitness && 
					p<population[j+1].cfitness)
					newpopulation[i] = population[j+1];
		}
	}
	//复制
	for (i = 0; i < POPSIZE; i++)
		population[i] = newpopulation[i];      
}

/***************************************************************/
/* Crossover：交配操作函数
输入参数：无
输出参数：无
注：对于交配产生的非法解采用变异的方法进行处理。
/***************************************************************/

void crossover()
{
	int i, mem, one;
	int first  =  0; /* count of the number of members chosen */
	double x;

	for (mem = 0; mem < POPSIZE; ++mem)
	{
		x = rand()%1000/1000.0;
		if (x < PXOVER)
		{
			++first;
			if (first % 2 == 0)
				Xover(one, mem);
			else
				one = mem;
		}
	}
}
/***************************************************************/
/*cal：计算基因总重量
输入参数：基因
返回值：对应背包的重量
*/
/***************************************************************/
pair<double,double> cal(bool gene[]){
	pair<double,double> tmp;
	tmp.first = 0;//重量
	tmp.second = 0;//体积
	for (int i = 0;i < NVARS; i++)
	{
		if (gene[i])
		{
			tmp.first += items[i].first;
			tmp.second += items[i].second;
		}
	}
	return tmp;
}
/***************************************************************/
/*modify:随即选择一位，进行0/1 -> 1/0的操作并修改　相应的参数
输入参数：基因位置
返回值：无
*/
/***************************************************************/
void modify(int num){
	int r;
	r= rand() % NVARS;
	if (population[num].gene[r])
	{
		population[num].volume -= items[r].second;
		population[num].weight -= items[r].first;
		population[num].gene[r] = 0;
	}else{
		population[num].volume += items[r].second;
		population[num].weight += items[r].first;
		population[num].gene[r] = 1;
	}
	return;
}
/**************************************************************/
/* Xover;交配过程
输入参数：两个基因位置
返回值：无
/**************************************************************/

void Xover(int one, int two)
{
	genotype tmpgene;
	tmpgene = population[one];
	int r = rand() % NVARS;
	for (int i = r; i < NVARS ; i++)
	{
		population[one].gene[i] = population[two].gene[i];
	}
	pair<double,double> tmp;
	tmp = cal(population[one].gene);
	
	population[one].weight = tmp.first;
	population[one].volume = tmp.second;

	for (int i = r; i < NVARS; i++ )
	{
		population[two].gene[i] = tmpgene.gene[i];
	}
	tmp = cal(population[two].gene);

	population[two].weight = tmp.first;
	population[two].volume = tmp.second;
	while (population[one].volume > MAXVOLUME)
	{
		modify(one);
	}
	while (population[two].volume > MAXVOLUME)
	{
		modify(two);
	}
	return ;
}



/**************************************************************/
/* Mutation: 变异操作
输入参数：无
返回值：无
/**************************************************************/

void mutate(void)
{
	int i;
	double x;

	for (i = 0; i < POPSIZE; i++){

		x = rand()%1000/1000.0;

		if (x < PMUTATION)
		{
			do 
			{
				modify(i);
			} while (population[i].volume > MAXVOLUME);
			
		}
	}
}


/**************************************************************/
/* Main ：程序主体
输入参数:无
返回值:无
/**************************************************************/

void main(int argc,char * argv[])
{
	int i;
	srand(time(0));
	//数据预处理
	if (argc != 2)
	{
		cout <<"Usage: Package_GA sourcefile"<<endl;
		return ;
	}
	ifstream input;
	input.open(argv[1]);
	if (!input)
	{
		cout << "Open source file "<<argv[1]<<"failed"<<endl;
		return ;
	}
	pair<int,int> tmp;
	c = new int[NVARS] ;
	v = new int [NVARS];

	for (int i = 0;i < NVARS; i++)
	{
		input >> c[i];
	}
	for (int i = 0;i < NVARS; i++)
	{
		input >> v[i];
	}
	for (int i = 0;i < NVARS; i++)
	{
		tmp.first = c[i];
		tmp.second = v[i];
		items.push_back(tmp);
	}
	sort(items.begin(),items.end(),judge);

	while (1)
	{
		generation = 0;
		for (int i = 0; i < POPSIZE;i ++)
		{
			population[i].volume = 0;
			population[i].weight = 0;
			population[i].fitness = 0;
			for (int j = 0;j < NVARS;j ++)
			{
				population[i].gene[j] = 0;
			}
		}
		cout << "利用遗传算法求解背包问题"<<endl;
		cout <<"相关数据如下: "<<endl;
		cout << "变异概率:"<<PMUTATION <<endl;
		cout << "交配概率:"<< PXOVER <<endl;
		cout << "种群数量:"<<POPSIZE <<endl;
		cout << "叠带次数:"<< MAXGENS <<endl;
		initialize();
		evaluate();
		keep_the_best();
		while(generation < MAXGENS)
		{
			generation++;
			select();
			crossover();
			mutate();

			evaluate();
			elitist();
		}
		cout << "计算结束!"<<endl;
		cout << "利用遗传算法求解背包问题"<<endl;
		cout<<"最优解背包重量为:"<< population[POPSIZE].weight<<endl;
		cout<<"最优解背包体积为:"<<population[POPSIZE].volume<<endl;
		int counts = 0;
		cout <<"具体背包内物品重量如下"<<endl;
		for (int i = 0; i< NVARS;i++)
		{
			if (population[POPSIZE].gene[i])
			{
				counts++;
				cout << items[i].first<< " ";
			}
		}
		cout<<endl;
		cout<<"总共的物品数目为： "<< counts<<endl;

		cout << "输入0,结束操作,其他键继续"<<endl;
		int a;
		cin >> a;
		if (a == 0)
		{
			break;
		}
	}

}