自用备份

#include<iostream>
#include<iomanip>
#include<cstdlib>
#include<cmath>
#include<ctime>

using namespace std;
//定义问题的最大规模
#define max 100
//为题规模，即共有多少个包
int packageNum;
//每个包的重量
int packageWeight[max] = {5,3,11,15,7,9,13,6,8,14}; 
//每个包的价值
int packageValue[max] ={100,5,20,100,60,40,90,40,50,80};
//约束，背包的最大容量
int limitWeight;
//群体的规模
int colonySize;
//colonyState[i][k] 表示一个染色体
//colonyState[1...conlonySize][0|1] 表示一个群体
int colonyState[max][2][max];
// currAge 表示当前代的编号
// (currAge+1)%2 表示下一代的编号
int currAge = 0;
// 个体评价信息表

typedef struct tagIndivdualMsg
{
	int index;
	int value;
}IndivdualMsg;
IndivdualMsg indivdualMsg[max];
/
//函数声明
void printColonyState(int nextAge);
/
//初始化群体
void colonyInit()
{
	int i, j;
	int w;

	for(i=0; i<colonySize; i++)
	{
		//保证找到一个符合约束的染色体
		w = limitWeight +1;
		while(w > limitWeight)
		{
			w = 0;
			for(j=0; j<packageNum&&w<=limitWeight; j++)
			{
				colonyState[i][currAge][j] = rand()%2;
				w += packageWeight[j] * colonyState[i][currAge][j];
			}
			
		}
	}
}

//对个体进行评价
int cmp(const void *a, const void *b)
{
	IndivdualMsg *x = (IndivdualMsg *)a;
	IndivdualMsg *y = (IndivdualMsg *)b;
	return y->value - x->value;
}
//适应度函数
void indivdualEstimate()
{
	int i, j;
	for(i=0; i<colonySize; i++)
	{
		indivdualMsg[i].index = i;
		indivdualMsg[i].value = 0;
		for(j=0; j<packageNum; j++)
			indivdualMsg[i].value += packageValue[j]*colonyState[i][currAge][j];
	}
	qsort(indivdualMsg, colonySize, sizeof(IndivdualMsg), cmp);
}
//终止循环的条件
bool stopFlag()
{
	//进行n代进行后停止
	static int n = 50;
	if(n-- <= 0)
		return false;
	else
		return true;
}
//赌轮选择
int gambleChoose()
{
	int wheel[max] = {0};
	int i = colonySize-1;
	int choose;
	wheel[i] = indivdualMsg[i].value;
	for(i--; i>=0; i--)
		wheel[i] = (indivdualMsg[i].value + wheel[i+1]) + colonySize*(colonySize-i);
	int seed = abs(wheel[0]-(rand()%(2*wheel[0]+1)));
	choose = colonySize-1;
	while(seed > wheel[choose])
		choose--;
	return choose;
}
//交叉
void across(int male, int female, int index)
{
	int nextAge = (currAge+1) %2;
	int i, j, t;
	int acrossBit = rand() % (packageNum-1) + 1;
	for(j=0; j<packageNum; j++)
	{
		colonyState[index][nextAge][j] = colonyState[indivdualMsg[male].index][currAge][j];
		colonyState[index+1][nextAge][j] = colonyState[indivdualMsg[female].index][currAge][j];
	}

	for(i=0; i<acrossBit; i++)
	{
		t = colonyState[index][nextAge][i];
		colonyState[index][nextAge][i] = colonyState[index+1][nextAge][i];
		colonyState[index+1][nextAge][j] = t;
	}
}
//变异
void aberrance(int index)
{
	int seed, nextAge;
	nextAge = (currAge+1) %2;
	//只有1/3的概率发生异变
	seed = rand() %(packageNum*3);
	if(seed < packageNum)
		colonyState[index][nextAge][seed] = (colonyState[index][nextAge][seed] + 1) %2;
}
//处理死亡个体
void dealDeath()
{
	int i, j;
	int weight, w;
	int nextAge = (currAge+1) %2;
	for(i=0; i<colonySize; i++)
	{
		weight = 0;
		for(j=0; j<packageNum; j++)
			weight += packageWeight[j] * colonyState[i][nextAge][j];
		if(weight > limitWeight)
		{
			w = limitWeight +1;
			while(w > limitWeight)
			{
				w = 0;
				for(j=0; j<packageNum&&w<=limitWeight; j++)
				{
					colonyState[i][nextAge][j] = rand() %2;
					w += packageWeight[j] * colonyState[i][nextAge][j];
				}
			}
		}
	}
	//printColonyState(nextAge);
}
//最优个体保护
void saveBest()
{
	int i, j;
	int min, minp, value;
	int nextAge = (currAge+1) %2;
	min = indivdualMsg[0].value;
	minp = -1;
	for(i=0; i<colonySize; i++)
	{
		value = 0;
		for(j=0; j<packageNum; j++)
			value += packageValue[j] *colonyState[i][nextAge][j];
		if(value <= min)
		{
			min = value;
			minp = i;
		}
	}
	if(minp >= 0)
	{
		for(j=0; j<packageNum; j++)
		{
			colonyState[minp][nextAge][j] = colonyState[indivdualMsg[0].index][currAge][j];
		}
	}
}


void printResult()
{
    cout<<"-----------------------------------------------------------"<<endl;
	cout<<"结果:"<<endl;
	int j, w = 0;

	cout<<setw(10)<<"物品I ";
	for(j=0; j<packageNum; j++)
	{
		cout<<setw(5)<<j+1;
	}
	cout<<endl;
    cout<<setw(10)<<"重量W ";
	for(j=0; j<packageNum; j++)
	{
		w += packageWeight[j] *colonyState[indivdualMsg[0].index][currAge][j];
		cout<<setw(5)<<packageWeight[j];
	}
	cout<<endl;
	cout<<setw(10)<<"价值V ";
	for(j=0; j<packageNum; j++)
		cout<<setw(5)<<packageValue[j];
	cout<<endl;

	cout<<setw(10)<<"Choose: ";
	for(j=0; j<packageNum; j++)
		cout<<setw(5)<<colonyState[indivdualMsg[0].index][currAge][j];
	cout<<endl;

	cout<<"总重量: "<<w<<endl;
	cout<<"总价值: "<<indivdualMsg[0].value<<endl;

}
///
void setProblem()
{
	int i;

	cout<<"              遗传算法求解下面的背包问题"<<endl;
	cout<<"-------------------------------------------------------"<<endl;
	cout<<"物品I   1    2    3    4    5    6    7    8    9   10 "<<endl;
	cout<<"重量W   5    3   11    15   7    9   13    6    8   14 "<<endl;
	cout<<"价值V 100    5   20   100  60   40   90   40   50   80 "<<endl;
	cout<<"-------------------------------------------------------"<<endl;
	
    packageNum=10;  //物品的个数	
	limitWeight=25; //背包容量
	colonySize = 100;//克隆次数

	cout<<"物品个数= "<<packageNum<<endl;
	cout<<"背包容量= "<<limitWeight<<endl;
	cout<<"克隆次数= "<<colonySize<<endl;

}

void printColonyState(int k)
{
	cout<<"----------------------------------------------------"<<endl;
	cout<<"colonyState-->";
	if(k == currAge)
		cout<<"currAge:"<<endl;
	else
		cout<<"next age:"<<endl;
	int i, j;
	for(i=0; i<colonySize; i++)
	{
		for(j=0; j<packageNum; j++)
			cout<<setw(2)<<colonyState[i][k][j];
		cout<<endl;
	}
}
void printIndividualMsg()
{
	int i;
	cout<<"---------------------------------------------------"<<endl;
	cout<<"Individual Msg:"<<endl;
	for(i=0; i<colonySize; i++)
		cout<<indivdualMsg[i].index<<"\t"<<indivdualMsg[i].value<<endl;
}

void main()
{
	srand((unsigned int)time(NULL));
	setProblem();

	//初始化群体
	colonyInit();
	printColonyState(currAge);
	while(! stopFlag())
	{
		//评价当前群体
		indivdualEstimate();
		//生成下一代
		for(int i=0; i<colonySize; i+=2)
		{
			int male = gambleChoose();
			int female = gambleChoose();
			across(male, female, i);
			aberrance(i);
			aberrance(i+1);
		}
		//处理死亡个体
		dealDeath();
		//保护最优个体
		saveBest();
		//现在的下一代变成下一轮的当前代
		currAge = (currAge+1) %2;
	}
	//输出问题解
	
	indivdualEstimate();
	printResult();
	system("Pause");
}