|
一、问题描述
一个旅行者有一个最多能用m公斤的背包，现在有n件物品，它们的重量分别是W1，W2，..., Wn,它们的价值分别为V1,V2,...,Vn.若每种物品只有一件求旅行者能获得最大总价值。
二、蚁群算法描述
蚁群算法是对自然界蚂蚁的觅食寻路方式进行模拟而得出的一种仿生算法。这种算法有别于传统编程模式，其优势在于，避免了冗长的编程和筹划，程序本身是基于一定规则的随机运行来寻找最佳配置。也就是说，当程序最开始找到目标的时候，路径几乎不可能是最优的，甚至可能是包含了无数错误的选择而极度冗长的。但是，程序可以通过蚂蚁寻找食物的时候的信息素原理，不断地去修正原来的路线，使整个路线越来越短，也就是说，程序执行的时间越长，所获得的路径就越可能接近最优路径。这看起来很类似与我们所见的由无数例子进行归纳概括形成最佳路径的过程。实际上好似是程序的一个自我学习的过程。
这种优化过程的本质在于：
选择机制：信息素越多的路径，被选择的概率越大。
更新机制：路径上面的信息素会随蚂蚁的经过而增长，而且同时也随时间的推移逐渐挥发消失。
协调机制：蚂蚁间实际上是通过分泌物来互相通信、协同工作的。
蚁群算法正是充分利用了选择、更新和协调的优化机制，即通过个体之间的信息交流与相互协作最终找到最优解，使它具有很强的发现较优解的能力。
三、问题实现分析
1、针对于01背包问题，所要求的是一个物品的排列问题，但是在蚁群算法的实现过程中要求有一个相同的起点，因此我们增加了一个共同的虚拟起点，设为第0个物品。
2、对物品的选择是整个算法的重点，这个主要体现在对物品的选择概率上。我们如下定义ANT数据结构：
struct{
int path[nMAX];
int v,c;
bool pathTag[nMAX+1];
int num;
}
其中，pathTag标记了蚁群所访问过的物品，c表示当前蚂蚁已经占有的物品的重量。如果某个物品已经被访问过了，或者是该物品的重量加上已经占有的物品的重量超过了背包的总负重量，则将其的被选择的概率设为0。由于在c语言的实现过程中，涉及到一个浮点数的误差问题，所以进行比较的过程中都是通过DML_MIN进行比较的。
四、实验环境
Windows sp3 + vs2005命令行编译器。
五、使用方法
直接双击运行aco.exe；
六、实验结果
实验数据文件的格式为：物品数量、背包容量、各物品重量、各物品价值
1、 对于测试集test1.txt，最优值为295，程序的运行记过如下：
2、 对于测试集test2.txt，论文中通过遗传算法所得的最优值为1870，程序的运行记过如下：
3、 对于测试集test3.txt，最优值为1024，程序的运行记过如下：
七、实验总结
为了防止算法过早的收敛，可以通过减慢信息素的挥发过程，并且增加蚂蚁觅食的次数。在实验的过程中蚂蚁的只数对于整个的算法的影响并不是很大。
------------------------------------------------------------------------------------------------------------------------------------
代码
/**
*作者：fern
*邮箱：yqshen3000@126.com
*xmu-3#221-2
*
**/
#include<stdio.h>
#include<string.h>
#include<time.h>
#include<process.h>
#include<stdlib.h>
#include<float.h>
const int nMAX = 100;//物品的最大个数
const int t = 1000;//觅食的次数
const int m = 50;//蚂蚁个数
const double del = 0.4;
const double minP = 0.0000001;
typedef struct{
int path[nMAX];
int v,c;
bool pathTag[nMAX+1];
int num;
}ANT;
ANT ant ;
ANT bestAnt;
double p[nMAX+1][nMAX+1];
int n;//物品数量
int w[nMAX];//单个物品的重量
int v[nMAX];//对应物品的价值
int c;//背包的容量
void initACO(){
double temp = 1.0 / (n*n);
int i = 0;
for(; i <= n; i++)
for(int j=1; j<=n; j++)
if(i == j)p[i][j]=0.0;
else p[i][j] = temp;
for(i=0; i<=n; i++)
p[i][0]=0.0;
bestAnt.v = 0;
}
bool selectThing(ANT &singleant, int beg){
double total = 0.0;
double select[nMAX+1];
int i=1;
for(; i < n+1; i++)
if(!singleant.pathTag[i]&&(c-singleant.c-w[i-1]>=0)){
total += p[beg][i];
select[i] = p[beg][i];
}
else
select[i] = 0.0;
if(total<DBL_MIN)return false;//已经没有可以选择的物品
select[0]=0.0;
for(i = 1; i< n+1;i++)
select[i] = select[i-1] + select[i]/total;
select[--i] += DBL_MIN;
double randP = rand()%1000*1.0/1000;
if(randP<DBL_MIN)randP=DBL_MIN;
for(i=1;select[i]<randP&&i<n+1;i++);
singleant.path[singleant.num] = i;
singleant.v += v[--i];
singleant.c += w[i];
singleant.pathTag[++i] = true;
singleant.num ++;
return true;
}
int changeP(){
int index = 0, i;
for(i=1;i < m; i++)
if(ant[i].v>ant[index].v)index = i;
for(i = 0;i < n+1; i++)
for(int j=1; j<n+1; j++)
p[i][j] *= 1-del;
if(ant[index].num == 0){
printf("输入的数据有误\n");
exit(0);
}
double add = del/ant[index].num;
int beg = 0;
for(i=0; i < ant[index].num; i++){
p[beg][ant[index].path[i]] += add;
beg = ant[index].path[i];
}
return index;
}
void aco(){
initACO();
srand(time(NULL));
int i;
for(i=0; i< t; i++){
int j = 0;
for(;j < m; j++){
//初始化蚂蚁
memset(ant[j].path,0,n*sizeof(int));
ant[j].v = 0;
ant[j].c = 0;
memset(ant[j].pathTag,false,(n+1)*sizeof(bool));
ant[j].num = 0;
int beg = 0;
while(true){
bool tag = selectThing(ant[j],beg);
if(!tag)break;
beg = ant[j].path[ant[j].num-1];
}
}
//更新信息素
int index = changeP();
/*printf("\n\n第%d次，最好的选择为：\n",i+1);
for(j=0; j<ant[index].num; j++)
printf("%d\t",ant[index].path[j]);
printf("\n物体总价值为%d\n",ant[index].v);*/
if(bestAnt.v < ant[index].v){
bestAnt.c = ant[index].c;
bestAnt.num = ant[index].num;
bestAnt.v = ant[index].v;
memcpy(bestAnt.path,ant[index].path,ant[index].num*sizeof(int));
memcpy(bestAnt.pathTag,ant[index].pathTag,ant[index].num*sizeof(bool));
}
}
}
void init(){
char fileName[512];
printf("请输入文件名\n");
scanf("%s",fileName);
//char *fileName = "test2.txt";
printf("测试的文件为：%s\n",fileName);
FILE *fp = fopen(fileName,"r");
fscanf(fp,"%d",&n);
if(n>nMAX){
printf("物品数量过多\n");
system("pause");
exit(0);
}
printf("物体数量为：%d\n",n);
fscanf(fp,"%d",&c);
printf("背包总容量为：%d\n",c);
printf("物品重量分别为：\n");
int i = 0;
for(; i < n; i++){
fscanf(fp,"%d",&w[i]);
printf("%4d",w[i]);
}
printf("\n物品价值分别为：\n");
for(i = 0; i < n; i++){
fscanf(fp,"%d",&v[i]);
printf("%4d",v[i]);
}
}
int main(){
init();
aco();
printf("\n最好的选择是：\n");
for(int j=0; j<bestAnt.num; j++)
printf("%2d、第%2d个物品：<%3d,%3d>\n",j+1,bestAnt.path[j],w[bestAnt.path[j]-1],v[bestAnt.path[j]-1]);
printf("物体总价值为%d\n",bestAnt.v);
printf("物体总重量为%d\n",bestAnt.c);
system("pause");
return 0;
} | 
