一、問題描述

一個(gè)旅行者有一個(gè)最多能用m公斤的背包，現(xiàn)在有n件物品，它們的重量分別是W1，W2，..., Wn,它們的價(jià)值分別為V1,V2,...,Vn.若每種物品只有一件求旅行者能獲得最大總價(jià)值。

二、蟻群算法描述

       蟻群算法是對自然界螞蟻的覓食尋路方式進(jìn)行模擬而得出的一種仿生算法。這種算法有別于傳統(tǒng)編程模式，其優(yōu)勢在于，避免了冗長的編程和籌劃，程序本身是基于一定規(guī)則的隨機(jī)運(yùn)行來尋找最佳配置。也就是說，當(dāng)程序最開始找到目標(biāo)的時(shí)候，路徑幾乎不可能是最優(yōu)的，甚至可能是包含了無數(shù)錯(cuò)誤的選擇而極度冗長的。但是，程序可以通過螞蟻尋找食物的時(shí)候的信息素原理，不斷地去修正原來的路線，使整個(gè)路線越來越短，也就是說，程序執(zhí)行的時(shí)間越長，所獲得的路徑就越可能接近最優(yōu)路徑。這看起來很類似與我們所見的由無數(shù)例子進(jìn)行歸納概括形成最佳路徑的過程。實(shí)際上好似是程序的一個(gè)自我學(xué)習(xí)的過程。

這種優(yōu)化過程的本質(zhì)在于：

選擇機(jī)制：信息素越多的路徑，被選擇的概率越大。

更新機(jī)制：路徑上面的信息素會隨螞蟻的經(jīng)過而增長，而且同時(shí)也隨時(shí)間的推移逐漸揮發(fā)消失。

協(xié)調(diào)機(jī)制：螞蟻間實(shí)際上是通過分泌物來互相通信、協(xié)同工作的。

蟻群算法正是充分利用了選擇、更新和協(xié)調(diào)的優(yōu)化機(jī)制，即通過個(gè)體之間的信息交流與相互協(xié)作最終找到最優(yōu)解，使它具有很強(qiáng)的發(fā)現(xiàn)較優(yōu)解的能力。

三、問題實(shí)現(xiàn)分析

1、針對于01背包問題，所要求的是一個(gè)物品的排列問題，但是在蟻群算法的實(shí)現(xiàn)過程中要求有一個(gè)相同的起點(diǎn)，因此我們增加了一個(gè)共同的虛擬起點(diǎn)，設(shè)為第0個(gè)物品。

2、對物品的選擇是整個(gè)算法的重點(diǎn)，這個(gè)主要體現(xiàn)在對物品的選擇概率上。我們?nèi)缦露�義ANT數(shù)據(jù)結(jié)構(gòu)：

struct{

    int path[nMAX];

    int v,c;

    bool pathTag[nMAX+1];

    int num;

}

其中，pathTag標(biāo)記了蟻群所訪問過的物品，c表示當(dāng)前螞蟻已經(jīng)占有的物品的重量。如果某個(gè)物品已經(jīng)被訪問過了，或者是該物品的重量加上已經(jīng)占有的物品的重量超過了背包的總負(fù)重量，則將其的被選擇的概率設(shè)為0。由于在c語言的實(shí)現(xiàn)過程中，涉及到一個(gè)浮點(diǎn)數(shù)的誤差問題，所以進(jìn)行比較的過程中都是通過DML_MIN進(jìn)行比較的。

四、實(shí)驗(yàn)環(huán)境

       Windows sp3 + vs2005命令行編譯器。

五、使用方法

       直接雙擊運(yùn)行aco.exe；

六、實(shí)驗(yàn)結(jié)果

       實(shí)驗(yàn)數(shù)據(jù)文件的格式為：物品數(shù)量、背包容量、各物品重量、各物品價(jià)值

1、  對于測試集test1.txt，最優(yōu)值為295，程序的運(yùn)行記過如下：

2、  對于測試集test2.txt，論文中通過遺傳算法所得的最優(yōu)值為1870，程序的運(yùn)行記過如下：

3、  對于測試集test3.txt，最優(yōu)值為1024，程序的運(yùn)行記過如下：

七、實(shí)驗(yàn)總結(jié)

       為了防止算法過早的收斂，可以通過減慢信息素的揮發(fā)過程，并且增加螞蟻覓食的次數(shù)。在實(shí)驗(yàn)的過程中螞蟻的只數(shù)對于整個(gè)的算法的影響并不是很大。

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

代碼

/**
*作者：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;//物品的最大個(gè)數(shù)
const int t = 1000;//覓食的次數(shù)
const int m = 50;//螞蟻個(gè)數(shù)
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;//物品數(shù)量
int w[nMAX];//單個(gè)物品的重量
int v[nMAX];//對應(yīng)物品的價(jià)值
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;//已經(jīng)沒有可以選擇的物品
 
 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("輸入的數(shù)據(jù)有誤\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物體總價(jià)值為%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("物品數(shù)量過多\n");
  system("pause");
  exit(0);
  }
 printf("物體數(shù)量為：%d\n",n);
 fscanf(fp,"%d",&c);
 printf("背包總?cè)萘繛椋?d\n",c);
 printf("物品重量分別為：\n");
 int i = 0;
 for(; i < n; i++){
  fscanf(fp,"%d",&w[i]);
  printf("%4d",w[i]);
 }
 printf("\n物品價(jià)值分別為：\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個(gè)物品：<%3d,%3d>\n",j+1,bestAnt.path[j],w[bestAnt.path[j]-1],v[bestAnt.path[j]-1]);
 printf("物體總價(jià)值為%d\n",bestAnt.v);
 printf("物體總重量為%d\n",bestAnt.c);
 system("pause");
 return 0;
 }