java人工蜂群算法求解TSP問題

壹、人工蜂群算法的介紹

人工蜂群算法(Artificial Bee Colony, ABC)是由Karaboga於2005年提出的壹種新穎的基於群智能的全局優化算法，其直觀背景來源於蜂群的采蜜行為，蜜蜂根據各自的分工進行不同的活動，並實現蜂群信息的***享和交流，從而找到問題的最優解。人工蜂群算法屬於群智能算法的壹種。

二、人工蜂群算法的原理

1、原理

標準的ABC算法通過模擬實際蜜蜂的采蜜機制將人工蜂群分為3類: 采蜜蜂、觀察蜂和偵察蜂。整個蜂群的目標是尋找花蜜量最大的蜜源。在標準的ABC算法中，采蜜蜂利用先前的蜜源信息尋找新的蜜源並與觀察蜂分享蜜源信息；觀察蜂在蜂房中等待並依據采蜜蜂分享的信息尋找新的蜜源；偵查蜂的任務是尋找壹個新的有價值的蜜源，它們在蜂房附近隨機地尋找蜜源。

假設問題的解空間是維的，采蜜蜂與觀察蜂的個數都是，采蜜蜂的個數或觀察蜂的個數與蜜源的數量相等。則標準的ABC算法將優化問題的求解過程看成是在維搜索空間中進行搜索。每個蜜源的位置代表問題的壹個可能解，蜜源的花蜜量對應於相應的解的適應度。壹個采蜜蜂與壹個蜜源是相對應的。與第個蜜源相對應的采蜜蜂依據如下公式尋找新的蜜源：

其中，，，是區間上的隨機數，。標準的ABC算法將新生成的可能解與原來的解作比較，並采用貪婪選擇策略保留較好的解。每壹個觀察蜂依據概率選擇壹個蜜源，概率公式為

其中，是可能解的適應值。對於被選擇的蜜源，觀察蜂根據上面概率公式搜尋新的可能解。當所有的采蜜蜂和觀察蜂都搜索完整個搜索空間時，如果壹個蜜源的適應值在給定的步驟內(定義為控制參數“limit”) 沒有被提高, 則丟棄該蜜源，而與該蜜源相對應的采蜜蜂變成偵查蜂，偵查蜂通過已下公式搜索新的可能解。

其中，是區間上的隨機數，和是第維的下界和上界。

2、流程

初始化；

重復以下過程：

將采蜜蜂與蜜源壹壹對應，根據上面第壹個公式更新蜜源信息，同時確定蜜源的花蜜量；

觀察蜂根據采蜜蜂所提供的信息采用壹定的選擇策略選擇蜜源，根據第壹個公式更新蜜源信息，同時確定蜜源的花蜜量；

確定偵查蜂，並根據第三個公式尋找新的蜜源；

記憶迄今為止最好的蜜源；

判斷終止條件是否成立；

三、人工蜂群算法用於求解函數優化問題

對於函數

其中。

代碼：

[cpp]?view plain?copy

#include<iostream>?

#include<time.h>?

#include<stdlib.h>?

#include<cmath>?

#include<fstream>?

#include<iomanip>?

using?namespace?std;?

const?int?NP=40;//種群的規模，采蜜蜂+觀察蜂?

const?int?FoodNumber=NP/2;//食物的數量，為采蜜蜂的數量?

const?int?limit=20;//限度，超過這個限度沒有更新采蜜蜂變成偵查蜂?

const?int?maxCycle=10000;//停止條件?

/*****函數的特定參數*****/?

const?int?D=2;//函數的參數個數?

const?double?lb=-100;//函數的下界

const?double?ub=100;//函數的上界?

double?result[maxCycle]={0};?

/*****種群的定義****/?

struct?BeeGroup?

{?

double?code[D];//函數的維數?

double?trueFit;//記錄真實的最小值?

double?fitness;?

double?rfitness;//相對適應值比例?

int?trail;//表示實驗的次數，用於與limit作比較?

}Bee[FoodNumber];?

BeeGroup?NectarSource[FoodNumber];//蜜源，註意：壹切的修改都是針對蜜源而言的?

BeeGroup?EmployedBee[FoodNumber];//采蜜蜂?

BeeGroup?OnLooker[FoodNumber];//觀察蜂?

BeeGroup?BestSource;//記錄最好蜜源?

/*****函數的聲明*****/?

double?random(double,?double);//產生區間上的隨機數?

void?initilize();//初始化參數?

double?calculationTruefit(BeeGroup);//計算真實的函數值?

double?calculationFitness(double);//計算適應值?

void?CalculateProbabilities();//計算輪盤賭的概率?

void?evalueSource();//評價蜜源?

void?sendEmployedBees();?

void?sendOnlookerBees();?

void?sendScoutBees();?

void?MemorizeBestSource();?

/*******主函數*******/?

int?main()?

{?

ofstream?output;?

output.open("dataABC.txt");?

srand((unsigned)time(NULL));?

initilize();//初始化?

MemorizeBestSource();//保存最好的蜜源?

//主要的循環?

int?gen=0;?

while(gen<maxCycle)?

{?

sendEmployedBees();?

CalculateProbabilities();?

sendOnlookerBees();?

MemorizeBestSource();?

sendScoutBees();?

MemorizeBestSource();?

output<<setprecision(30)<<BestSource.trueFit<<endl;?

gen++;?

}?

output.close();?

cout<<"運行結束!!"<<endl;?

return?0;?

}?

/*****函數的實現****/?

double?random(double?start,?double?end)//隨機產生區間內的隨機數?

{?

return?start+(end-start)*rand()/(RAND_MAX?+?1.0);?

}?

void?initilize()//初始化參數?

{?

int?i,j;?

for?(i=0;i<FoodNumber;i++)?

{?

for?(j=0;j<D;j++)?

{?

NectarSource[i].code[j]=random(lb,ub);?

EmployedBee[i].code[j]=NectarSource[i].code[j];?

OnLooker[i].code[j]=NectarSource[i].code[j];?

BestSource.code[j]=NectarSource[0].code[j];?

}?

/****蜜源的初始化*****/?

NectarSource[i].trueFit=calculationTruefit(NectarSource[i]);?

NectarSource[i].fitness=calculationFitness(NectarSource[i].trueFit);?

NectarSource[i].rfitness=0;?

NectarSource[i].trail=0;?

/****采蜜蜂的初始化*****/?

EmployedBee[i].trueFit=NectarSource[i].trueFit;?

EmployedBee[i].fitness=NectarSource[i].fitness;?

EmployedBee[i].rfitness=NectarSource[i].rfitness;?

EmployedBee[i].trail=NectarSource[i].trail;?

/****觀察蜂的初始化****/?

OnLooker[i].trueFit=NectarSource[i].trueFit;?

OnLooker[i].fitness=NectarSource[i].fitness;?

OnLooker[i].rfitness=NectarSource[i].rfitness;?

OnLooker[i].trail=NectarSource[i].trail;?

}?

/*****最優蜜源的初始化*****/?

BestSource.trueFit=NectarSource[0].trueFit;?

BestSource.fitness=NectarSource[0].fitness;?

BestSource.rfitness=NectarSource[0].rfitness;?

BestSource.trail=NectarSource[0].trail;?

}?

double?calculationTruefit(BeeGroup?bee)//計算真實的函數值?

{?

double?truefit=0;?

/******測試函數1******/?

truefit=0.5+(sin(sqrt(bee.code[0]*bee.code[0]+bee.code[1]*bee.code[1]))*sin(sqrt(bee.code[0]*bee.code[0]+bee.code[1]*bee.code[1]))-0.5)?

/((1+0.001*(bee.code[0]*bee.code[0]+bee.code[1]*bee.code[1]))*(1+0.001*(bee.code[0]*bee.code[0]+bee.code[1]*bee.code[1])));?

return?truefit;?

}?

double?calculationFitness(double?truefit)//計算適應值?

{?

double?fitnessResult=0;?

if?(truefit>=0)?

{?

fitnessResult=1/(truefit+1);?

}else?

{?

fitnessResult=1+abs(truefit);?

}?

return?fitnessResult;?

}?

void?sendEmployedBees()//修改采蜜蜂的函數?

{?

int?i,j,k;?

int?param2change;//需要改變的維數?

double?Rij;//[-1,1]之間的隨機數?

for?(i=0;i<FoodNumber;i++)?

{?

param2change=(int)random(0,D);//隨機選取需要改變的維數?

/******選取不等於i的k********/?

while?(1)?

{?

k=(int)random(0,FoodNumber);?

if?(k!=i)?

{?

break;?

}?

}?

for?(j=0;j<D;j++)?

{?

EmployedBee[i].code[j]=NectarSource[i].code[j];?

}?

/*******采蜜蜂去更新信息*******/?

Rij=random(-1,1);?

EmployedBee[i].code[param2change]=NectarSource[i].code[param2change]+Rij*(NectarSource[i].code[param2change]-NectarSource[k].code[param2change]);?

/*******判斷是否越界********/?

if?(EmployedBee[i].code[param2change]>ub)?

{?

EmployedBee[i].code[param2change]=ub;?

}?

if?(EmployedBee[i].code[param2change]<lb)?

{?

EmployedBee[i].code[param2change]=lb;?

}?

EmployedBee[i].trueFit=calculationTruefit(EmployedBee[i]);?

EmployedBee[i].fitness=calculationFitness(EmployedBee[i].trueFit);?

/******貪婪選擇策略*******/?

if?(EmployedBee[i].trueFit<NectarSource[i].trueFit)?

{?

for?(j=0;j<D;j++)?

{?

NectarSource[i].code[j]=EmployedBee[i].code[j];?

}?

NectarSource[i].trail=0;?

NectarSource[i].trueFit=EmployedBee[i].trueFit;?

NectarSource[i].fitness=EmployedBee[i].fitness;?

}else?

{?

NectarSource[i].trail++;?

}?

}?

}?

void?CalculateProbabilities()//計算輪盤賭的選擇概率?

{?

int?i;?

double?maxfit;?

maxfit=NectarSource[0].fitness;?

for?(i=1;i<FoodNumber;i++)?

{?

if?(NectarSource[i].fitness>maxfit)?

maxfit=NectarSource[i].fitness;?

}?

for?(i=0;i<FoodNumber;i++)?

{?

NectarSource[i].rfitness=(0.9*(NectarSource[i].fitness/maxfit))+0.1;?

}?

}?

void?sendOnlookerBees()//采蜜蜂與觀察蜂交流信息，觀察蜂更改信息?

{?

int?i,j,t,k;?

double?R_choosed;//被選中的概率?

int?param2change;//需要被改變的維數?

double?Rij;//[-1,1]之間的隨機數?

i=0;?

t=0;?

while(t<FoodNumber)?

{?

R_choosed=random(0,1);?

if(R_choosed<NectarSource[i].rfitness)//根據被選擇的概率選擇?

{?

t++;?

param2change=(int)random(0,D);?

/******選取不等於i的k********/?

while?(1)?

{?

k=(int)random(0,FoodNumber);?

if?(k!=i)?

{?

break;?

}?

}?

for(j=0;j<D;j++)?

{?

OnLooker[i].code[j]=NectarSource[i].code[j];?

}?

/****更新******/?

Rij=random(-1,1);?

OnLooker[i].code[param2change]=NectarSource[i].code[param2change]+Rij*(NectarSource[i].code[param2change]-NectarSource[k].code[param2change]);?

/*******判斷是否越界*******/?

if?(OnLooker[i].code[param2change]<lb)?

{?

OnLooker[i].code[param2change]=lb;?

}?

if?(OnLooker[i].code[param2change]>ub)?

{?

OnLooker[i].code[param2change]=ub;?

}?

OnLooker[i].trueFit=calculationTruefit(OnLooker[i]);?

OnLooker[i].fitness=calculationFitness(OnLooker[i].trueFit);?

/****貪婪選擇策略******/?

if?(OnLooker[i].trueFit<NectarSource[i].trueFit)?

{?

for?(j=0;j<D;j++)?

{?

NectarSource[i].code[j]=OnLooker[i].code[j];?

}?

NectarSource[i].trail=0;?

NectarSource[i].trueFit=OnLooker[i].trueFit;?

NectarSource[i].fitness=OnLooker[i].fitness;?

}else?

{?

NectarSource[i].trail++;?

}?

}

i++;?

if?(i==FoodNumber)?

{?

i=0;?

}?

}?

}?