I'm solving the Traveling Salesman Problem via an ACO implementation in C++. However, I found out that the program I've built so far gives a segmentation fault. (Note: I've limited the algorithm to only do one iteration of the colony for debugging purposes).
First off, I have a total of 52 cities taken from a file, and I distribute the ants so that every city has the same number of ants starting from it.
To store the distances between every pair of cities, I'm using a vector of vectors of doubles called Map (a square matrix). However, half-way during the execution it looks like these vectors are deleted. In this instance, it happens when calculating the path for the ant number 55. I've added a section of code just to highlight exactly where it crashes:
//DEBUGGING SECTION
cout << "Size Roulette: " << Roulette.size() << endl;
cout << "Size Remain: " << RemainingCities.size() << endl;
cout << "Size Map: " << Map.size() << " x " << Map[0].size() << endl;
int k = 0;
cout << "Test: Map access: " << endl;
for(int i = 0; i < Map.size(); ++i) // HERE IT CRASHES AT ANT NUMBER 55
cout << Map[0][i] << " ";
cout << endl;
cout << "Test: Operation: " << Map[Colony[ant_i][city_i-1]][RemainingCities[k]] << endl;
Roulette[k] = pow((MAX_DIST - Map[Colony[ant_i][city_i-1]][RemainingCities[k]]), heur_coef) + pow((pheromones[Colony[ant_i][city_i-1]][RemainingCities[k]]), pher_coef);
//END OF DEBUGGING SECTION
There, the function Map[0].size() normally returns 52 (just like Map.size(), as it's supposed to be a square matrix), but at the crashing iteration it returns what looks like a memory address, and the moment I try to access any element, a segmentation fault occurs.
I have checked that the memory access is always correct, and I can access any other variable without issue except Map until that 55th ant. I've tried different seeds for the roulette method, but it always crashes at the same place.
I have also varied the number of ants of the colony. If it's just one ant per city, the program executes without issue, but for any higher amount the program always crashes at the 55th ant.
You can download the full cpp file and the reading .tsp file from github:
https://github.com/yitosmash/ACO
In any case, I'll leave the full function here:
void ACO(const vector<City>& cities, const vector<vector<double>>& Map, int max_it, int num_ants, double decay, double heur_coef, double pher_coef, double pher_coef_elit)
{
srand(30);
//Initialise colony of ants (each ant is a vector of city indices)
vector<vector<int>> Colony(num_ants, vector<int>(cities.size(), 0));
//Initialise pheromone matrix
vector<vector<double>> pheromones(cities.size(), vector<double>(cities.size(), 0));
//Initialise costs vector(for etilist expansion)
vector<double> costs(cities.size(), 0);
//Auxiliar vector of indices
vector<int> cityIndices(cities.size());
for (int i = 0; i < cities.size(); ++i)
cityIndices[i] = i;
//Longest distance from Map, used for heuristic values.
vector<double> longests(cities.size(), 0);
for(int i = 0; i < cities.size(); ++i)
longests[i] = *(max_element(Map[i].begin(), Map[i].end()));
const double MAX_DIST = *(max_element(longests.begin(), longests.end()));
longests.clear();
int i=0;
while(i<max_it)
{
for(int ant_i = 0; ant_i < num_ants; ++ant_i)
{
cout << "Ant: " << ant_i << endl;
//City for ant_i to start at; each ant is assigned a determined starting city
int starting_city = (int) ((float)ant_i/num_ants*cities.size());
//cout << starting_city << endl;
Colony[ant_i][0] = starting_city;
//Get a vector with the cities left to visit
vector<int> RemainingCities = cityIndices;
//Remove starting city from remaining cities
RemainingCities.erase(RemainingCities.begin() + starting_city);
//Create path for ant_i
for(int city_i = 1; city_i < Colony[ant_i].size(); ++city_i)
{
cout << "Calculating city number: " << city_i << endl;
//Create roulette for next city selection
vector<double> Roulette(RemainingCities.size(), 0);
double total = 0;
//DEBUGGING SECTION
cout << "Size Roulette: " << Roulette.size() << endl;
cout << "Size Remain: " << RemainingCities.size() << endl;
cout << "Size Map: " << Map.size() << " x " << Map[0].size() << endl;
int k = 0;
cout << "Test: Map access: " << endl;
for(int i = 0; i < Map.size(); ++i) // HERE IT CRASHES AT ANT NUMBER 55
cout << Map[0][i] << " ";
cout << endl;
cout << "Test: Operation: " << Map[Colony[ant_i][city_i-1]][RemainingCities[k]] << endl;
Roulette[k] = pow((MAX_DIST - Map[Colony[ant_i][city_i-1]][RemainingCities[k]]), heur_coef) + pow((pheromones[Colony[ant_i][city_i-1]][RemainingCities[k]]), pher_coef);
//END OF DEBUGGING SECTION
for(int j = 0; j < RemainingCities.size(); ++j)
{
//Heuristic value is MAX_DIST - current edge.
Roulette[j] = pow((MAX_DIST - Map[Colony[ant_i][city_i-1]][RemainingCities[j]]), heur_coef) + pow((pheromones[Colony[ant_i][city_i-1]][RemainingCities[j]]), pher_coef);
total += Roulette[j];
}
cout << endl;
//Transform roulette into stacked probabilities
Roulette[0] = Roulette[0]/total;
for(int j = 1; j < Roulette.size(); ++j)
Roulette[j] = Roulette[j-1] + Roulette[j] / total;
//Select a city from Roulette
int chosen = 0;
double r = (double) rand()/RAND_MAX;
while(Roulette[chosen] < r)
chosen++;
//Add chosen city to
Colony[ant_i][city_i] = RemainingCities[chosen];
RemainingCities.erase(RemainingCities.begin() + chosen);
}
cout << endl;
//Save cost of ant_i, for elitist expansion
costs[ant_i] = pathCost(Colony[ant_i], Map);
}
i++;
}
}
That part is very suspicious :
for(int i = 0; i < Map.size(); ++i) // HERE IT CRASHES AT ANT NUMBER 55
cout << Map[0][i] << " ";
because i is the size of the map but you use it as an index in a probable string / vector, so you probably go out of the string/vector with an undefined behavior
probably you want
for(int i = 0; i < Map.size(); ++i)
cout << Map[i] << " ";
or
for(int i = 0; i < Map[0].size(); ++i)
cout << Map[0][i] << " ";
As I said in a remark at a moment RemainingCities[0] values -163172699 first in
cout << "Test: Operation: " << Map.at(Colony.at(ant_i).at(city_i-1)).at(RemainingCities.at(k)) << endl;
so is not a valid index in Map, but there is visible reason to have that looking at the code, so the reason is a probable write out of a vector destructing your memory elements.
To detect where I replaced all the [...] by .at(...) and the first error I have is in ACO at the line
costs.at(ant_i) = pathCost(Colony.at(ant_i), Map);
where ant_i values 52 while costs has 52 entries and Colony 260, so the error concerns costs
note that ant_i is set by the loop
for(int ant_i = 0; ant_i < num_ants; ++ant_i)
and in that case num_ants value 260 so much more than the size of costs which is defined as
vector<double> costs(cities.size(), 0);
but cost is just allocated and set but never read, so its goal is just to destruct the memory.
If I remove the two lines concerning it I do not have anymore an error and the program ends normally, there is no exception in a .at(...) and valgrind detect no error too.