Skip to content

Instantly share code, notes, and snippets.

@macroxela

macroxela/ACO.cpp

Created April 24, 2014 00:33
Show Gist options
  • Save macroxela/11237368 to your computer and use it in GitHub Desktop.
Save macroxela/11237368 to your computer and use it in GitHub Desktop.
Download ZIP
Ant Colony Optimization implementation for finding the shortest path between 2 cities given in the input file. The input file also contains the map data (city names and distances).
Raw
ACO.cpp
/*
Alex Marroquin
CSCI 4350 Artificial Intelligence
Homework 2: Ant Colony Optimization Implementation
main.cpp
*/
#include<iostream>
#include<string>
#include<fstream>
#include<time.h>
#include<math.h>
using namespace std;
class GoneThrough
{
public:
GoneThrough * nxt, * prev;
string name;
GoneThrough(){nxt = NULL; prev = NULL; name = "";};
void print();
};
void GoneThrough::print()
{
GoneThrough *n = nxt;
cout<<"\n**********\nVisited so far:\n";
cout<<name<<endl;
while(n != NULL)
{
cout<<n->name<<endl;
n = n->nxt;
}
cout<<"**********\n";
}
class Child
{
public:
string name;
Child *parent,*next;
double distance;
double path;
double risk;
double pher;
double heuristic;
double probability;
Child(const Child&);
Child(){name = "NULL";distance = 0;path = 0; risk = 0; pher = 0;parent = NULL;};
Child(string nm, double d, double p, double r, double std){name = nm;distance = d;path = p; risk = r;pher = std;parent = NULL;};
void print(){cout<<name<<"\n Path: "<<path<<" Dist.: "<<distance<<" Risk: "<<risk<<" Straight Dist.: "<<pher<<endl;};
};
Child::Child(const Child &s)
{
name = s.name;
parent = s.parent;
distance = s.distance;
path = s.path;
risk = s.risk;
pher = s.pher;
}
class Table
{
public:
Child *neigh[25];
double pher;
string name;
void printData();
void printChildren();
Table();
};
Table::Table()
{
for(int i = 0; i < 25; i++)
neigh[i] = NULL;
}
void Table::printData()
{
cout<<name<<", "<<pher<<endl;
}
void Table::printChildren()
{
Child *trav = neigh[0];
int cnt = 0;
while(trav != NULL)
{
trav->print();
cnt++;
trav = neigh[cnt];
}
}
class Ant
{
public:
GoneThrough *list;
Ant(){list = NULL;};
};
void cutstring(string &input, int pos)
{
string dummy = "";
for(int i = pos; i < input.length(); i++)
{
dummy += input[i];
}
input = dummy;
}
string concatenate(string &input)
{
string ls = "";
if(input == "")
{
return "";
}
int size = input.length();
int cnt = 0;
int i = 0;
while(isspace(input[cnt]))
{
cnt ++;
if(cnt == size)
return "";
}
if(cnt == size)
{
return "";
}
while(cnt < size)
{
if(isspace(input[cnt]))
break;
ls += input[cnt];
cnt++;
}
cutstring(input,cnt);
return ls;
}
//To look up city data on the table
Table* Find(Table *look[], string item, int size)
{
for(int i = 0; i < size; i++)
{
if(look[i]->name == item)
{
return look[i];
}
}
cout<<"Item not found"<<endl;
Table *tabs = NULL;
return tabs;
}
//Checks through entire list to see if nm is present
bool traveled(GoneThrough *list, string nm)
{
GoneThrough *s = list;
while(s != NULL)
{
if(s->name == nm)
return true;
s = s->nxt;
}
return false;
}
//Goes through all neighbors to see they have been visited
bool allTraveled(GoneThrough *list, Table *tab, Child *test)
{
bool all = true;
int count = 0;
while(test != NULL)
{
if(!traveled(list,test->name))
{
all = false;
break;
}
count++;
test = tab->neigh[count];
}
return all;
}
void retrace(Table *data[], Table *current, Ant *a)
{
//Retrace back until node with unvisited neighbors is reached
GoneThrough *list = a->list;
while(list->nxt != NULL && list->nxt->name != "")
list = list->nxt;
GoneThrough *end = list->nxt;
list = list->prev;
Table *prev = Find(data,list->name,25);
bool all = allTraveled(a->list, prev, prev->neigh[0]);
while(all)
{
end->name = prev->name;
end->nxt = new GoneThrough;
end->nxt->prev = end;
end = end->nxt;
list = list->prev;
prev = Find(data,list->name,25);
all = allTraveled(a->list, prev, prev->neigh[0]);
}
end->name = prev->name;
end->nxt = new GoneThrough;
end->nxt->prev = end;
}
int main()
{
Table *data[25]; //Table used to store city data including neighbors
ifstream inFile("dats.txt");
srand (time(NULL));
rand();
if(inFile.is_open())
{
string s, s1, s2, s3, s4, s5, s6;
string goal, start;
getline(inFile,s);
start = s;
getline(inFile,s);
goal = s;
//This entire for loop is to fill the table with city data. This data can then be searched
//for using the Find function
for(int i = 0; i < 25; i++)
{
string s, s1, s2, s3, s4, s5, s6;
getline(inFile,s);
s1 = concatenate(s);
s2 = concatenate(s);
s3 = concatenate(s);
if(s1 == "# ")
{
data[i]->name = "Null";
}
else
{
data[i] = new Table;
if(!isdigit(s2[0]))
{
data[i]->name = s1 + " " + s2;
data[i]->pher = atof(s3.c_str());
}
else
{
data[i]->name = s1;
data[i]->pher = atof(s2.c_str());
s = s3 + s;
}
int cnt = 0;
while(!s.empty())
{
s1 = concatenate(s);
s2 = concatenate(s);
s3 = concatenate(s);
s4 = concatenate(s);
s5 = concatenate(s);
s6 = concatenate(s);
if(s1 == "@")
break;
data[i]->neigh[cnt] = new Child;
if(!isdigit(s2[0]))
{
data[i]->neigh[cnt]->name = s1 + " " + s2;
data[i]->neigh[cnt]->distance = atof(s3.c_str());
data[i]->neigh[cnt]->path = 1/atof(s4.c_str());
data[i]->neigh[cnt]->risk = atof(s5.c_str());
data[i]->neigh[cnt]->pher = atof(s6.c_str());
}
else
{
data[i]->neigh[cnt]->name = s1;
data[i]->neigh[cnt]->distance = atof(s2.c_str());
data[i]->neigh[cnt]->path = 1/atof(s3.c_str());
data[i]->neigh[cnt]->risk = atof(s4.c_str());
data[i]->neigh[cnt]->pher = atof(s5.c_str());
s = s6 + s;
}
cnt++;
}
}
}
/*for(int i = 0; i < 25; i++)
{
data[i]->printData();
data[i]->printChildren();
cout<<endl;
}*/
cout<<"Start: "<<start<<", Goal: "<<goal<<endl<<endl;
clock_t clock_start = clock();
//Start Ant algorithm
double alpha = 0.5;
double beta = 1.0;
double rho = 0.75;
double Q = 1000;
Table *found, *dummy;
bool FD = false;
if(start == goal)
{
cout<<"Already there"<<endl;
FD = true;
}
found = Find(data,start,25);
//Initialize ants
Ant *ant[10];
for(int i = 0; i < 10; i++)
ant[i] = new Ant;
for(int b = 0; b < 5; b++)
{
for(int j = 0; j < 35; j++)
{
dummy = found;
//Tour through all ants
for(int k = 0; k < 10; k++)
{
dummy = found;
ant[k]->list = new GoneThrough;
ant[k]->list->name = start;
ant[k]->list->nxt = new GoneThrough;
ant[k]->list->nxt->prev = ant[k]->list;
Table *previous = new Table;
////////////////////////////////////////////////////
//Loop until target is reached
while(!FD)
{
//Calculate heuristic for all neighbors
Child *c = dummy->neigh[0];
int cnt = 0;
double sum = 0;
double neigh_cnt = 0;
while(c != NULL)
{
c->heuristic = c->distance*c->path*exp(c->risk);
sum += pow(c->heuristic,beta)*pow(c->pher,alpha);
neigh_cnt++;
cnt++;
c = dummy->neigh[cnt];
}
//Calculate probability of all neighbors
cnt = 0;
c = dummy->neigh[cnt];
while(c != NULL)
{
if(sum != 0)
c->probability = (pow(c->heuristic,beta)*pow(c->pher,alpha))/sum;
else
c->probability = 1/neigh_cnt;
cnt++;
c = dummy->neigh[cnt];
}
//Choose desired path
cnt = 0;
double p = 0;
bool t = true;
double ran = (double)rand()/RAND_MAX;
GoneThrough *dum = ant[k]->list;
c = dummy->neigh[cnt];
//Loop until city not traveled is picked
while(t)
{
if(c != NULL && ran > p && ran <= p + c->probability) //if chosen
{
if(!traveled(ant[k]->list, c->name)) //if not visited
{
t = false;
while(dum->nxt != NULL)
dum = dum->nxt;
dum->name = c->name;
dum->nxt = new GoneThrough;
dum->nxt->prev = dum;
}
else //if visited
{
//To check if any unvisited neighbors are left
bool has_visited_neigh = allTraveled(ant[k]->list, dummy, dummy->neigh[0]);
if(!has_visited_neigh) //there are unvisited neighbors
{
ran = (double)rand()/RAND_MAX;
c = dummy->neigh[0];
cnt = 0;
p = 0;
}
else //there are no unvisited neighbors
{
//Retrace back until node with unvisited neighbors is reached
retrace(data,dummy,ant[k]);
t = false;
while(dum->nxt != NULL && dum->nxt->name != "") //**
dum = dum->nxt;
}
}
}
else //if visited
{
if(c != NULL)
{
cnt++;
p += c->probability;
c = dummy->neigh[cnt];
}
else
{
ran = (double)rand()/RAND_MAX;
c = dummy->neigh[0];
cnt = 0;
p = 0;
}
}
}
previous = dummy;
dummy = Find(data,dum->name,25);
if(dummy->name == goal) //Goal reached, move to next ant
FD = true;
} //End Loop FD
FD = false;
////////////////////////////////////////////////////
} //End ant tours
//cout<<"Finished ant tour "<<j<<endl;
//Update Pheremones
for(int i = 0; i < 10; i++)
{
//cout<<"Ant "<<i<<endl;
GoneThrough *list = ant[i]->list;
GoneThrough *nxt = ant[i]->list->nxt;
while(nxt->nxt != NULL)
{
//Find appropriate pointers for data in adjacency list
Table *x = Find(data,list->name,25);
Table *y = Find(data,nxt->name,25);
Child *xx = x->neigh[0];
Child *yy = y->neigh[0];
int cnt = 1;
while(xx != NULL)
{
if(xx->name == y->name)
break;
xx = x->neigh[cnt];
cnt++;
}
cnt = 1;
while(yy != NULL)
{
if(yy->name == x->name)
break;
yy = y->neigh[cnt];
cnt++;
}
//Update Pheremones
xx->pher = xx->pher*(1-rho);
xx->pher += Q;
yy->pher = yy->pher*(1-rho);
yy->pher += Q;
list = list->nxt;
nxt = nxt->nxt;
if(j == 24)
cout<<"Updated "<<yy->name<<" and "<<xx->name<<endl;
}
if(j == 24)
cout<<endl;
}
if(j == 24)
{
cout<<"Iteration "<<b<<" over\n";
cout<<"Alpha: "<<alpha;
cout<<"\nBeta: "<<beta;
cout<<"\nRho: "<<rho<<endl;
system("pause");
system("CLS");
}
}// End iteration
if(b == 0)
{
alpha = 1.0;
beta = 0.5;
rho = 0.75;
}
if(b == 1)
{
alpha = 1.0;
beta = 1.0;
rho = 0.75;
}
if(b == 2)
{
alpha = 1.0;
beta = 1.0;
rho = 0.3;
}
if(b == 3)
{
alpha = 1.0;
beta = 1.0;
rho = 0.95;
}
} // End run
}
system("pause");
return 0;
}
Raw
input.txt
Blue Mountains
Iron Hills
Blue Mountains 0 Lake Evendim 250 2 4 0 Michel Delving 270 5 2 0 White Towers 225 5 2 0 Grey Havens 240 5 2 0 @
Lake Evendim 0 Blue Mountains 250 2 4 0 Fornost 85 2 6 0 Michel Delving 110 2 5 0 @
Grey Havens 0 Blue Mountains 240 5 2 0 White Towers 100 5 1 0 Sarn Ford 270 2 3 0 @
White Towers 0 Blue Mountains 225 5 2 0 Michel Delving 40 5 1 0 Hobbiton 70 5 1 0 Grey Havens 100 5 1 0 @
Michel Delving 0 Blue Mountains 270 5 2 0 Hobbiton 35 5 0.5 0 Brandy Hall 80 5 0.5 0 White Towers 40 5 1 0 Lake Evendim 110 2 5 0 @
Hobbiton 0 Brandy Hall 50 5 0.5 0 Bree 100 5 1.5 0 Sarn Ford 130 5 3 0 Michel Delving 35 5 0.5 0 White Towers 70 5 1 0 @
Brandy Hall 0 Bree 50 5 1.5 0 Hobbiton 50 5 0.5 0 Michel Delving 80 5 0.5 0 @
Bree 0 Brandy Hall 50 5 1.5 0 Hobbiton 100 5 1.5 0 Fornost 115 5 3 0 Weathertop 100 5 4 0 Sarn Ford 105 5 3 0 @
Fornost 0 Lake Evendim 85 2 6 0 Bree 115 5 3 0 Weathertop 160 2 3 0 Rivendell 375 2 5 0 @
Sarn Ford 0 Grey Havens 270 2 3 0 Hobbiton 130 5 3 0 Bree 105 5 3 0 Weathertop 180 2 5.5 0 Rivendell 400 2 5.5 0 Isengard 500 2 6 0 @
Weathertop 0 Fornost 160 2 3 0 Bree 100 5 4 0 Sarn Ford 180 2 5.5 0 Rivendell 230 5 4.5 0 @
Rivendell 0 Fornost 375 2 5 0 Sarn Ford 400 2 5.5 0 Weathertop 230 5 4.5 0 North Pass 100 2 6.5 0 Caradhras 60 5 6.5 0 Moria 180 2 9 0 Isengard 500 2 8.5 0 @
North Pass 0 Rivendell 100 2 6.5 0 Carrock 80 2 7 0 @
Caradhras 0 Rivendell 60 5 6.5 0 Carrock 70 2 7 0 Gladden Fields 150 2 6 0 Lothlorien 300 2 5.5 0 @
Moria 0 Rivendell 180 2 9 0 Gladden Fields 140 2 9.5 0 Lothlorien 20 2 9.5 0 @
Gladden Fields 0 Caradhras 150 2 6 0 Moria 140 2 9.5 0 Esgaroth 400 2 6 0 Dol Guldur 175 2 8 0 Lothlorien 190 2 7 0 @
Lothlorien 0 Caradhras 300 2 5.5 0 Moria 20 2 9.5 0 Gladden Fields 190 2 7 0 Dol Guldur 180 2 8.5 0 Isengard 240 2 8 0 @
Carrock 0 North Pass 80 2 7 0 Caradhras 70 2 7 0 Wood Elves 175 2 8 0 Erebor 250 2 8 0 Esgaroth 240 2 8 0 Dol Guldur 300 2 8.5 0 @
Dol Guldur 0 Lothlorien 180 2 8.5 0 Carrock 300 2 8.5 0 Gladden Fields 175 2 8 0 Isengard 390 2 8.5 0 @
Isengard 0 Sarn Ford 500 2 6 0 Rivendell 500 2 8.5 0 Lothlorien 240 2 8 0 Dol Guldur 390 2 8.5 0 @
Wood Elves 0 Carrock 175 2 8 0 Dale 90 5 3 0 Erebor 100 5 3 0 @
Esgaroth 0 Carrock 240 2 8 0 Gladden Fields 400 2 6 0 Dale 40 5 1.5 0 Erebor 50 5 1.5 0 Iron Hills 175 5 3 0 @
Dale 0 Wood Elves 90 5 3 0 Esgaroth 40 5 1.5 0 Erebor 10 5 1 0 Iron Hills 180 5 3 0 @
Erebor 0 Carrock 250 2 8 0 Wood Elves 100 5 3 0 Esgaroth 50 5 1.5 0 Dale 10 5 1 0 Iron Hills 200 5 3 0 @
Iron Hills 0 Erebor 200 5 3 0 Dale 180 5 3 0 Esgaroth 175 5 3 0 @
#
Start 1 dist. p r std 2 dist. p r std 3 dist. p r std 4 dist. p r std 5 dist. p r std 6 dist. p r std 7 dist. p r std
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment