|
一、問題描述
一個(gè)旅行者有一個(gè)最多能用m公斤的背包，現(xiàn)在有n件物品，它們的重量分別是W1，W2，..., Wn,它們的價(jià)值分別為V1,V2,...,Vn.若每種物品只有一件求旅行者能獲得最大總價(jià)值。
二、蟻群算法描述
蟻群算法是對(duì)自然界螞蟻的覓食尋路方式進(jìn)行模擬而得出的一種仿生算法。這種算法有別于傳統(tǒng)編程模式，其優(yōu)勢(shì)在于，避免了冗長的編程和籌劃，程序本身是基于一定規(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ī)制：路徑上面的信息素會(huì)隨螞蟻的經(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、針對(duì)于01背包問題，所要求的是一個(gè)物品的排列問題，但是在蟻群算法的實(shí)現(xiàn)過程中要求有一個(gè)相同的起點(diǎn)，因此我們?cè)黾恿艘粋�(gè)共同的虛擬起點(diǎn)，設(shè)為第0個(gè)物品。
2、對(duì)物品的選擇是整個(gè)算法的重點(diǎn)，這個(gè)主要體現(xiàn)在對(duì)物品的選擇概率上。我們?nèi)缦露xANT數(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、 對(duì)于測試集test1.txt，最優(yōu)值為295，程序的運(yùn)行記過如下：
2、 對(duì)于測試集test2.txt，論文中通過遺傳算法所得的最優(yōu)值為1870，程序的運(yùn)行記過如下：
3、 對(duì)于測試集test3.txt，最優(yōu)值為1024，程序的運(yùn)行記過如下：
七、實(shí)驗(yàn)總結(jié)
為了防止算法過早的收斂，可以通過減慢信息素的揮發(fā)過程，并且增加螞蟻覓食的次數(shù)。在實(shí)驗(yàn)的過程中螞蟻的只數(shù)對(duì)于整個(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];//對(duì)應(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("請(qǐng)輸入文件名\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;
} | 
