ACO蚁群算法解01背包问题

ACO实现0-1背包问题，算法简单易懂且有实验报告。

#include “iostream“
#include 
#include 
#include 

using namespace std;

#define M 8//蚂蚁数
#define P 0.2//信息素挥发率
#define MAX 70
int BRoute[MAX];//最优解
int BValue=0;//最优解的总价值
int BWeight;//最优解的总重量
int max_circle=500;//外循环最大次数
int antRoute[9][MAX];
int antValue[9];
void main（）{
	int n;//物品个数
	int w_limit;//背包重量限制
	int value[MAX];//各物品价值
	int weight[MAX];//各物品重量
    float inf[MAX][MAX];//信息素矩阵
	int ij;



	// ************** 读数据 *************************//
	string filestring;
	cout<<“请输入测试文件名: “;
	cin>>filestring;
	
	ifstream inFile（filestring.c_str（））;
	//报告错误
	if（!inFile）
	{
		cerr<<“不能打开测试文件：“<		exit（-1）;
	}
    
	inFile>>n;
	inFile>>w_limit;

	value[0]=0;
    weight[0]=0;
	for （i=1; i<=n; i++）
	{
		inFile >> weight[i];  
	}	
	for （i=1; i<=n; i++）
	{
		inFile >> value[i]; 

	}

	//************************* 信息素矩阵初始化 ********************//
	
	for（i=0;i<=n;i++）
		inf[i][0]=0;
	for（i=0;i<=n;i++）{
		for（j=1;j<=n;j++）{
			inf[i][j]=1;
		}
	}
	

	//************************ 数据输出 ****************************//
	cout<<“物品总数为：“<	cout<<“背包重量限制为：“<
	cout<<“各物品重量分别为：“<   	for（i=0;i<=n;i++）
		cout<< weight[i]<<“ “;
	cout<
	cout<<“各物品价值分别为：“<    for（i=0;i<=n;i++）
		cout<< value[i]<<“ “;
	cout</*
	cout<<“信息素矩阵初始化为：“<    for（i=0;i<=n;i++）{
		for（j=0;j<=n;j++）{
			cout<		}
		cout<	}
*/


	srand（（int）time（0））; //初始化随机种子
	bool mark[MAX];
	int no_modify=0;
	for（int k=1;k<=max_circle && no_modify<100 ;k++）{//外循环
//	for（int k=1;k<=max_circle  ;k++）{//外循环
		for（i=1;i<=M;i++）{
			antRoute[i][0]=0;
			int Cur_n=0; //已选取物品个数
			int Cur_w=0; //已选取物品总重量
			int Cur_v=0; //已选取物品总价值
			int Cur_ps=0; //记录当前选取物品的标号
		    for（j=1;j<=n;j++）
				mark[j]=false; //作为物品是否选取的标志
			bool finish=false; 
		   	int ok[MAX]; 
			while（finish==false）{
				if（Cur_n==n）{
					antRoute[i][++Cur_n]=0;
					antValue[i]=Cur_v;
					finish=true;
					
				}
				else{
					int ok_n=0;
					for（j=1;j<=n;j++）{
						if（mark[j]==false &&（Cur_w+weight[j]）<=w_limit）{
							ok[ok_n++]=j; //该数组用于存储满足条件的物品的标号
						}
					}
					if（ok_n==0）{ //无满足条件的物品
						antRoute[i][++Cur_n]=0;
						antValue[i]=Cur_v;
						finish=true;
					}
					else{
						//有满足条件的物品：按信息素来进行随机选取
						float total=0;
						float rate[MAX];						
					
						for（j=0;j							float total=total+inf[Cur_ps][ok[j]];							
						}
						for（j=0;j							rate[j]=（inf[Cur_ps][ok[j]]/total）;
							
						bool choose=false;
						while（choose==false）{
							double r=（double）（rand（） % 1001） * 0.001f;
							int u=（int）（rand（）%ok_n）;
							if（rate[u]>r）{
									antRoute[i][++Cur_n]=ok[u];
									Cur_ps=ok[u];
									Cur_w+=weight[ok[u]];
									Cur_v+=value[ok[u]];
									mark[ok[u]]=true;
									choose=true;
									break;		
			

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       4381  2008-07-10 16:12  ACO解01背包问题\ACO解01背包问题.dsp

     文件        555  2008-07-10 15:32  ACO解01背包问题\ACO解01背包问题.dsw

     文件      50176  2008-07-11 18:59  ACO解01背包问题\ACO解01背包问题.ncb

     文件      48640  2008-07-11 18:59  ACO解01背包问题\ACO解01背包问题.opt

     文件        923  2008-07-11 18:43  ACO解01背包问题\ACO解01背包问题.plg

     文件     553044  2008-07-11 18:43  ACO解01背包问题\Debug\ACO解01背包问题.exe

     文件     817036  2008-07-11 18:43  ACO解01背包问题\Debug\ACO解01背包问题.ilk

     文件    1147904  2008-07-11 18:43  ACO解01背包问题\Debug\ACO解01背包问题.pdb

     文件     352329  2008-07-11 18:43  ACO解01背包问题\Debug\main.obj

     文件     123904  2008-07-11 18:47  ACO解01背包问题\Debug\vc60.idb

     文件     110592  2008-07-11 18:43  ACO解01背包问题\Debug\vc60.pdb

     文件       4612  2008-07-11 18:43  ACO解01背包问题\main.cpp

     文件        122  2008-07-11 14:35  ACO解01背包问题\readme.txt

     文件         65  2008-07-09 21:10  ACO解01背包问题\test1.txt

     文件        126  2008-07-09 21:10  ACO解01背包问题\test2.txt

     文件         18  2008-07-11 14:29  ACO解01背包问题\test3.txt

     文件         27  2008-07-11 14:30  ACO解01背包问题\test4.txt

     文件         27  2008-07-11 14:34  ACO解01背包问题\test5.txt

     文件     157696  2011-01-19 20:29  ACO解01背包问题\蚁群算法实现0.doc

     目录          0  2011-01-19 20:27  ACO解01背包问题\Debug

     目录          0  2011-01-19 20:29  ACO解01背包问题

----------- ---------  ---------- -----  ----

              3372177                    21