旅行商問題演算法

#include<iostream>

#include<time.h>

#include<stdlib.h>

#include<cmath>

#include<fstream>

#include<iomanip>

usingnamespacestd;

constintNP=40;//種群的規模，采蜜蜂+觀察蜂

constintFoodNumber=NP/2;//食物的數量，為采蜜蜂的數量

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

constintmaxCycle=10000;//停止條件

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

constintD=2;//函數的參數個數

constdoublelb=-100;//函數的下界

constdoubleub=100;//函數的上界

doubleresult[maxCycle]={0};

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

structBeeGroup

{

doublecode[D];//函數的維數

doubletrueFit;//記錄真實的最小值

doublefitness;

doublerfitness;//相對適應值比例

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

}Bee[FoodNumber];

BeeGroupNectarSource[FoodNumber];//蜜源，注意：一切的修改都是針對蜜源而言的

BeeGroupEmployedBee[FoodNumber];//采蜜蜂

BeeGroupOnLooker[FoodNumber];//觀察蜂

BeeGroupBestSource;//記錄最好蜜源

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

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

voidinitilize();//初始化參數

doublecalculationTruefit(BeeGroup);//計算真實的函數值

doublecalculationFitness(double);//計算適應值

voidCalculateProbabilities();//計算輪盤賭的概率

voidevalueSource();//評價蜜源

voidsendEmployedBees();

voidsendOnlookerBees();

voidsendScoutBees();

voidMemorizeBestSource();

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

intmain()

{

ofstreamoutput;

output.open("dataABC.txt");

srand((unsigned)time(NULL));

initilize();//初始化

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

//主要的循環

intgen=0;

while(gen<maxCycle)

{

sendEmployedBees();

CalculateProbabilities();

sendOnlookerBees();

MemorizeBestSource();

sendScoutBees();

MemorizeBestSource();

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

gen++;

}

output.close();

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

return0;

}

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

doublerandom(doublestart,doubleend)//隨機產生區間內的隨機數

{

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

}

voidinitilize()//初始化參數

{

inti,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;

}

doublecalculationTruefit(BeeGroupbee)//計算真實的函數值

{

doubletruefit=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])));

returntruefit;

}

doublecalculationFitness(doubletruefit)//計算適應值

{

doublefitnessResult=0;

if(truefit>=0)

{

fitnessResult=1/(truefit+1);

}else

{

fitnessResult=1+abs(truefit);

}

returnfitnessResult;

}

voidsendEmployedBees()//修改采蜜蜂的函數

{

inti,j,k;

intparam2change;//需要改變的維數

doubleRij;//[-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++;

}

}

}

voidCalculateProbabilities()//計算輪盤賭的選擇概率

{

inti;

doublemaxfit;

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;

}

}

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

{

inti,j,t,k;

doubleR_choosed;//被選中的概率

intparam2change;//需要被改變的維數

doubleRij;//[-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;

}

}

}