遗传算法解决0-1背包问题

遗传算法解决0-1背包问题,C++,VS2013

#include “Genetic_Algorithm.h“

int calculate_total_volume（）//计算物品的总容量
{
	int t_volume = 0;
	for （int i = 0; i < NUM; i++）
		t_volume += volume[i];
	return t_volume;
}

int calculate_total_value（）//计算物品的总价值
{
	int t_value = 0;
	for （int i = 0; i < NUM; i++）
		t_value += value[i];
	return t_value;
}

void output_volume（）//输出每一件物品的体积
{
	cout << “每一件物品的体积：“ << endl;
	for （int i = 0; i < NUM; i++）
		cout << volume[i] << “   “;
	cout << endl;
}

void output_value（）//输出每一件物品的价值
{
	cout << “每一件物品的价值：“ << endl;
	for （int i = 0; i < NUM; i++）
		cout << value[i] << “   “;
	cout << endl;
}

GA::GA（）
{
	for （int i = 0; i < NP; i++）
	{
		for （int j = 0; j < NUM; j++）
		{
			individual[i].chromosome[j] = 0;
			best_individual.chromosome[j] = 0;
		}
		individual[i].total_volume = 0;
		individual[i].total_value = 0;
		best_individual.total_volume = 0;
		best_individual.total_value = 0;
	}
	for （int j = 0; j < NUM; j++）
		chr[j] = false;
	max_value = 0;
	max_volume = 0;
}

void GA::initial_population（）//产生初始种群
{
	for （int i = 0; i < NP; i++）
	{
		for （int j = 0; j < NUM; j++）
		{
			bool k = （rand（） % 10 < 5） ? 0 : 1;//随机产生0或1
			individual[i].chromosome[j] = k;//初始化染色体编码		
			individual[i].total_volume += k*volume[j];//计算初始种群中每一个个体的体积
			individual[i].total_value += k*value[j];//计算初始种群中每一个个体的价值
		}
		if （individual[i].total_volume > PACK_MAX_V）//如果个体体积超过最大的承受值，重新选择
		{
			individual[i].total_volume = 0;
			individual[i].total_value = 0;
			i--;
		}
	}
	for （int i = 0; i < NP; i++）//比较，选出初始最优解，即装入背包物品的价值最大
	{
		if （individual[i].total_value >= max_value）
		{
			max_volume = individual[i].total_volume;
			max_value = individual[i].total_value;
			best_individual = individual[i];
		}
	}
}

void GA::calculate_fitness_value（）//计算适应值
{
	for （int i = 0; i < NP; i++）
	{
		individual[i].total_volume = 0;
		individual[i].total_value = 0;
		for （int j = 0; j < NUM; j++）
		{
			individual[i].total_volume += individual[i].chromosome[j] * volume[j];
			individual[i].total_value += individual[i].chromosome[j] * value[j];
		}
		if （individual[i].total_volume > PACK_MAX_V）//如果个体体积超过最大的承受值，用初始最优解取代
		{
			individual[i] = best_individual;
		}
	}
	for （int i = 0; i < NP; i++）
	{
		for （int j = 0; j < NUM; j++）
		{
			if （individual[i].total_value >= max_value）//更新最优解
			{
				max_volume = individual[i].total_volume;
				max_value = individual[i].total_value;
				best_individual = individual[i];//保存当前最优解
				chr[j] = individual[i].chromosome[j];//记录当前最优解的初始01序列
			}
		}
	}
	return;
}

void GA::select_operator（）//选择
{
	int sum_of_fitness = 0;
	double selected[NP];
	double r;
	Individual new_[NP];//新种群
	for （int i = 0; i < NP; i++）//计算种群中所有个体的适应值的和
		sum_of_fitness += individual[i].total_volume;
	for （int i = 0; i < NP; i++）//染色体i被选中的概率
	{
		selected[i] = （double）individual[i].total_volume / （double）sum_of_fitness;
	}
	for （int i = 1; i < NP; i++）//概率的累积
	{

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2018-04-19 20:16  遗传算法解决0-1背包问题\
     目录           0  2018-04-15 18:36  遗传算法解决0-1背包问题\Debug\
     文件       73728  2018-04-19 17:22  遗传算法解决0-1背包问题\Debug\遗传算法解决0-1背包问题.exe
     文件     1101520  2018-04-19 17:22  遗传算法解决0-1背包问题\Debug\遗传算法解决0-1背包问题.ilk
     文件     1575936  2018-04-19 17:22  遗传算法解决0-1背包问题\Debug\遗传算法解决0-1背包问题.pdb
     目录           0  2018-04-19 17:21  遗传算法解决0-1背包问题\遗传算法解决0-1背包问题\
     文件     7471104  2018-04-19 20:16  遗传算法解决0-1背包问题\遗传算法解决0-1背包问题.sdf
     文件        1045  2018-04-14 16:07  遗传算法解决0-1背包问题\遗传算法解决0-1背包问题.sln
     文件       31744  2018-04-19 20:16  遗传算法解决0-1背包问题\遗传算法解决0-1背包问题.v12.suo
     目录           0  2018-04-15 18:06  遗传算法解决0-1背包问题\遗传算法解决0-1背包问题txt\
     文件        6423  2018-04-15 14:50  遗传算法解决0-1背包问题\遗传算法解决0-1背包问题txt\Genetic_Algorithm_cpp.txt
     文件        1194  2018-04-15 14:50  遗传算法解决0-1背包问题\遗传算法解决0-1背包问题txt\Genetic_Algorithm_h.txt
     文件         527  2018-04-15 14:50  遗传算法解决0-1背包问题\遗传算法解决0-1背包问题txt\main.txt
     文件       10724  2018-04-15 18:06  遗传算法解决0-1背包问题\遗传算法解决0-1背包问题txt\参考代码.txt
     目录           0  2018-04-19 17:22  遗传算法解决0-1背包问题\遗传算法解决0-1背包问题\Debug\
     文件      166382  2018-04-19 17:22  遗传算法解决0-1背包问题\遗传算法解决0-1背包问题\Debug\Genetic_Algorithm.obj
     文件      155560  2018-04-19 17:04  遗传算法解决0-1背包问题\遗传算法解决0-1背包问题\Debug\main.obj
     文件      363520  2018-04-19 17:22  遗传算法解决0-1背包问题\遗传算法解决0-1背包问题\Debug\vc120.idb
     文件      356352  2018-04-19 17:22  遗传算法解决0-1背包问题\遗传算法解决0-1背包问题\Debug\vc120.pdb
     文件        1720  2018-04-19 17:22  遗传算法解决0-1背包问题\遗传算法解决0-1背包问题\Debug\遗传算法解决0-1背包问题.log
     目录           0  2018-04-19 17:22  遗传算法解决0-1背包问题\遗传算法解决0-1背包问题\Debug\遗传算法解决0-1背包问题.tlog\
     文件        1158  2018-04-19 17:22  遗传算法解决0-1背包问题\遗传算法解决0-1背包问题\Debug\遗传算法解决0-1背包问题.tlog\cl.command.1.tlog
     文件       25230  2018-04-19 17:22  遗传算法解决0-1背包问题\遗传算法解决0-1背包问题\Debug\遗传算法解决0-1背包问题.tlog\CL.read.1.tlog
     文件        1642  2018-04-19 17:22  遗传算法解决0-1背包问题\遗传算法解决0-1背包问题\Debug\遗传算法解决0-1背包问题.tlog\CL.write.1.tlog
     文件        1266  2018-04-19 17:22  遗传算法解决0-1背包问题\遗传算法解决0-1背包问题\Debug\遗传算法解决0-1背包问题.tlog\link.command.1.tlog
     文件        2822  2018-04-19 17:22  遗传算法解决0-1背包问题\遗传算法解决0-1背包问题\Debug\遗传算法解决0-1背包问题.tlog\link.read.1.tlog
     文件         558  2018-04-19 17:22  遗传算法解决0-1背包问题\遗传算法解决0-1背包问题\Debug\遗传算法解决0-1背包问题.tlog\link.write.1.tlog
     文件         183  2018-04-19 17:22  遗传算法解决0-1背包问题\遗传算法解决0-1背包问题\Debug\遗传算法解决0-1背包问题.tlog\遗传算法解决0-1背包问题.lastbuildstate
     文件        5103  2018-04-19 17:21  遗传算法解决0-1背包问题\遗传算法解决0-1背包问题\Genetic_Algorithm.cpp
     文件        1901  2018-04-19 17:04  遗传算法解决0-1背包问题\遗传算法解决0-1背包问题\Genetic_Algorithm.h
     文件         689  2018-04-15 17:04  遗传算法解决0-1背包问题\遗传算法解决0-1背包问题\main.cpp
............此处省略2个文件信息