?? actsp.cpp
字號:
#include <iostream>
#include <fstream>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
#include "MapClass.h"
//#include "AntClass.h"
using namespace std;
const int iMaxLoop=2000;
int iCount=0;
const int iAntNumber=30;
const double dAlpha=1;
const double dBeta=5;
const double Q=100.0;
double P_0;
class Ant{
private:
double PathLength;
int iA_Tabu[iCityNumber];
//MapInfo * Map;
public:
int iCityCount;
Ant();
int iA_Allowed[iCityNumber];
void NextCity(MapInfo * Map);
void NextCity_opt2(MapInfo * Map);
void AddCity(int CityIndex);
double GetOneDirectProbility(MapInfo * Map,int i,int j);
double GetPathLength(void);
void SetPathLength(MapInfo * Map);
void UpDateDeltaPheromone(MapInfo * Map);
void LocalUpdating(MapInfo * Map,int from,int to);
void GlobeUpdating(MapInfo * Map);
int getTabu(int index);
void clear();
void Reset();
void operator=( Ant & srcAnt )
{
PathLength=srcAnt.GetPathLength();
for(int i=0;i<iCityNumber;i++ )
{
iA_Tabu[i]=srcAnt.getTabu(i);
iA_Allowed[i]=srcAnt.iA_Allowed[i];
}
}
};
Ant::Ant(){
for(int i=0;i<iCityNumber;i++){
iA_Tabu[i]=0;
iA_Allowed[i]=1;
}
PathLength=0.0;
iCityCount=0;
}
void Ant::AddCity(int CityIndex)
{
iA_Tabu[iCityCount]=CityIndex;
iCityCount++;
iA_Allowed[CityIndex]=0;
}
double Ant::GetOneDirectProbility(MapInfo * Map,int i,int j){
double p=0.0;
p=pow((1.0/ Map->GetDistance(i,j) ),dBeta)*pow((Map->GetPheromone(i,j)),dAlpha);
if( p<=0)p=rnd(0,1)*pow( (1.0 / Map->GetDistance(i,j)), dBeta);
return p;
}
void Ant::NextCity_opt2(MapInfo * Map)
{
int curCity=iA_Tabu[iCityCount-1];
double maxPathInfo=0.0;
double p=rnd(0,1);
double temp;
int index;
if(p<=P_0)
{
for (int i=0;i<iCityNumber;i++) {
if((iA_Allowed[i]==1)) {
temp=GetOneDirectProbility(Map,curCity,i);
if( maxPathInfo<temp ){
maxPathInfo=temp;
index=i;
//cout<<" "<<index;
}
}
}
AddCity(index);
LocalUpdating(Map,curCity,index);
}
else NextCity(Map);
}
void Ant::NextCity(MapInfo * Map){
int i,to=-1;
double TotalP=0.0;
int curCity=iA_Tabu[iCityCount-1];
//if(iCount<6)
// {
for (i=0;i<iCityNumber;i++) {
if((iA_Allowed[i]==1)) {
TotalP += GetOneDirectProbility(Map,curCity,i);
}
}
if(TotalP==0.0)
{
to=rand()%iCityNumber;
}
else
{
for(to=0;to<iCityNumber;to++)
{
double p;
if(iA_Allowed[to]==1)
{
p=GetOneDirectProbility(Map,curCity,to)/TotalP;
if(rnd(0,1)<p)
break;
}
}
}
if(to==iCityNumber)
{
TotalP=-1;
for(i=0;i<iCityNumber;i++)
if(iA_Allowed[i]==1)
{
if (TotalP<GetOneDirectProbility(Map,curCity,i)) {
TotalP=GetOneDirectProbility(Map,curCity,i);
to=i;
}
}
}
// }
// if(iCount>=6) //當連續6代都沒有產生更短的路徑，則
// {
// for ( i=0;i<iCityCount;i++) {
// if((iA_Allowed[i]==1)) {
// to=i;
// iCount=0;
// dRou=0.5;
// if(rnd(0.0,1.0)>0.5) //隨機選擇一個還沒訪問的城市
// {
// break;
// }
// }
// }
// }
AddCity(to);
LocalUpdating(Map,curCity,to);
}
double Ant::GetPathLength(){
return PathLength;
}
void Ant::SetPathLength(MapInfo * Map){
for(int i=0;i<iCityNumber-1;i++)
{
PathLength+=Map->GetDistance(iA_Tabu[i],iA_Tabu[i+1]);
}
PathLength+=Map->GetDistance(iA_Tabu[iCityNumber-1],iA_Tabu[0]);
}
void Ant::UpDateDeltaPheromone(MapInfo * Map){
int from,to;
for (int j=0;j<iCityNumber-1;j++) {
from=iA_Tabu[j];
to=iA_Tabu[j+1];
Map->AddDeltaPheromone(from,to,Q/PathLength);
Map->AddDeltaPheromone(to,from,Q/PathLength);
//Map->w_dDeltaPheromone[from][to]+=Q/PathLength;
//Map->w_dDeltaPheromone[to][from]=Map->w_dDeltaPheromone[from][to]; //兩個方向的信息量相等
}
from=iA_Tabu[iCityNumber-1];
to=iA_Tabu[0];
Map->w_dDeltaPheromone[from][to]+=Q/PathLength ; //加上起點和終點之間的信息量
Map->w_dDeltaPheromone[to][from]=Map->w_dDeltaPheromone[from][to]; //兩個方向的信息量相等
}
void Ant::LocalUpdating(MapInfo * Map,int from,int to){//not finished
double DeltaPheromone;
DeltaPheromone=100.0/(52*8000);/////////not finished
Map->LocalUpdating(from,to,DeltaPheromone);
}
void Ant::GlobeUpdating(MapInfo * Map){
int from,to;
for(int i=0;i<iCityNumber-1;i++){
from=iA_Tabu[i];
to=iA_Tabu[i+1];
Map->LocalUpdating(from,to,Q/PathLength);
//Map->LocalUpdating(to,from,Q/PathLength);
}
from=iA_Tabu[iCityNumber-1];
to=iA_Tabu[0];
Map->LocalUpdating(from,to,Q/PathLength);
//Map->LocalUpdating(to,from,Q/PathLength);
}
int Ant::getTabu(int index)
{
return iA_Tabu[index];
}
void Ant::clear(){
iCityCount=0;
for(int i=0;i<iCityNumber;i++){
iA_Allowed[i]=1;
}
PathLength=0.0;
}
void Ant::Reset(){
iCityCount=0;
for(int i=0;i<iCityNumber;i++){
iA_Allowed[i]=1;
}
PathLength=0.0;
AddCity(iA_Tabu[iCityNumber-1]);
}
void main()
{
srand( (unsigned)time( NULL ));
MapInfo *Map=new MapInfo();
Map->ReadCityInfo();
Ant ants[iAntNumber],bestsofar;
int i,j,k,minant,last,loop=0;
double minLength;
double temp;
int tempant;
FILE * outresult=fopen("result.txt","w+");
for(int v=0;v<100;v++)
{
Map->clear();
for(i=0;i<iAntNumber;i++)
{
ants[i].clear();
k=rand()%iCityNumber;
ants[i].AddCity(k);
}
minLength=10000000.0;
loop=0;
P_0=0.9;
iCount=0;
while(loop<iMaxLoop)
{
temp=10000000.0;
for(i=0;i<iCityNumber-1;i++)
{
for(j=0;j<iAntNumber;j++){
ants[j].NextCity_opt2(Map);
}
}
for(j=0;j<iAntNumber;j++){
ants[j].SetPathLength(Map);
if(temp>ants[j].GetPathLength()){
temp=ants[j].GetPathLength();
tempant=j;
}
}
if(temp<minLength){
iCount=0;
P_0=P_0+0.1;
if(P_0>0.9)P_0=0.9;
minLength=temp;
minant=tempant;
last=loop;
ants[minant].GlobeUpdating(Map);
bestsofar=ants[minant];
}
else{
iCount++;
bestsofar.GlobeUpdating(Map);
}
if(iCount>3)
{
P_0=P_0-0.1;
if(P_0<0.5)P_0=0.5;
}
for(j=0;j<iAntNumber;j++){
ants[j].Reset();
}
// printf("\n%d\t%.9f",loop,minLength);
loop++;
}
fprintf(outresult,"\n%d\t%.9f",v,minLength);
printf("\n%d\t%d\t%.9f",v,last,minLength);
//cout<<endl<<"the best route is :"<<endl;
// for(j=0;j<iAntNumber;j++){
// cout<<" "<<bestsofar.getTabu(j);
//}
}
fclose(outresult);
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -