遗传算法解决背包问题（C++版本）

遗传算法解决背包问题(C++版本)【源代码+实验报告+可执行文件】 人工智能实验，绝对可以运行，理由详细的注释，方便新手学习。

#include
#include
#include
#include
#include

using namespace std;
//定义问题的最大规模
#define max 100
//为题规模，即共有多少个包
int packageNum;
//每个包的重量
int packageWeight[max] = {53111579136814}; 
//每个包的价值
int packageValue[max] ={100520100604090405080};
//约束，背包的最大容量
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	{
		//保证找到一个符合约束的染色体
		w = limitWeight +1;
		while（w > limitWeight）
		{
			w = 0;
			for（j=0; 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	{
		indivdualMsg[i].index = i;
		indivdualMsg[i].value = 0;
		for（j=0; 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	{
		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	{
		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

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2013-06-02 20:46  遗传算法解决背包问题\
     文件      615424  2013-05-22 16:58  遗传算法解决背包问题\bag.exe
     目录           0  2013-06-02 20:45  遗传算法解决背包问题\bag_code\
     目录           0  2013-06-02 20:45  遗传算法解决背包问题\bag_code\Debug\
     文件        6786  2013-05-22 21:47  遗传算法解决背包问题\bag_code\Debug\BuildLog.htm
     文件      615424  2013-05-22 21:47  遗传算法解决背包问题\bag_code\Debug\bag.exe
     文件         406  2013-05-22 16:58  遗传算法解决背包问题\bag_code\Debug\bag.exe.embed.manifest
     文件         472  2013-05-22 16:58  遗传算法解决背包问题\bag_code\Debug\bag.exe.embed.manifest.res
     文件         381  2013-05-22 21:47  遗传算法解决背包问题\bag_code\Debug\bag.exe.intermediate.manifest
     文件     1470088  2013-05-22 21:47  遗传算法解决背包问题\bag_code\Debug\bag.ilk
     文件      273583  2013-05-22 21:47  遗传算法解决背包问题\bag_code\Debug\bag.obj
     文件     3107840  2013-05-22 21:47  遗传算法解决背包问题\bag_code\Debug\bag.pdb
     文件          67  2013-05-22 21:47  遗传算法解决背包问题\bag_code\Debug\mt.dep
     文件       74752  2010-04-05 19:15  遗传算法解决背包问题\bag_code\Debug\vc60.idb
     文件      110592  2010-04-05 19:15  遗传算法解决背包问题\bag_code\Debug\vc60.pdb
     文件      248832  2013-05-22 21:47  遗传算法解决背包问题\bag_code\Debug\vc90.idb
     文件      184320  2013-05-22 21:47  遗传算法解决背包问题\bag_code\Debug\vc90.pdb
     文件       18944  2013-05-22 13:34  遗传算法解决背包问题\bag_code\Project1.exe
     文件      262144  2013-05-22 13:34  遗传算法解决背包问题\bag_code\Project1.tds
     文件        6930  2013-05-22 21:47  遗传算法解决背包问题\bag_code\bag.cpp
     文件        4248  2010-04-05 16:46  遗传算法解决背包问题\bag_code\bag.dsp
     文件         531  2010-04-05 13:21  遗传算法解决背包问题\bag_code\bag.dsw
     文件     1231872  2013-05-26 21:12  遗传算法解决背包问题\bag_code\bag.ncb
     文件      118175  2013-05-22 13:34  遗传算法解决背包问题\bag_code\bag.obj
     文件       53760  2010-04-06 00:19  遗传算法解决背包问题\bag_code\bag.opt
     文件        1248  2010-04-05 19:15  遗传算法解决背包问题\bag_code\bag.plg
     文件         876  2013-05-26 21:12  遗传算法解决背包问题\bag_code\bag.sln
     文件       14848  2013-05-26 21:12  遗传算法解决背包问题\bag_code\bag.suo
     文件        5129  2013-05-22 15:11  遗传算法解决背包问题\bag_code\bag.vcproj
     文件        1413  2013-05-26 21:12  遗传算法解决背包问题\bag_code\bag.vcproj.saniu-PC.saniu.user
     文件           0  2003-07-23 17:52  遗传算法解决背包问题\bag_code\bagItem.cpp
............此处省略1个文件信息