一、問題描述

一個旅行者有一個最多能用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;
 }