I'm trying to launch the program code for Travelling Salesman Problem (TSP) with Genetic algorithm. Couldn't figure out in a code as it's not mine. Can anyone understand how to fix it?
I need to define the global object in the code and place it in a right place How can I define it in the code? I am confused(
Graph Map_City;//Define the global object graph and place it after the Graph class
GA zq; //Population category, placed after GA category
#include <iostream>
#include <fstream>
#include <string>
#include <time.h>
#include <stdlib.h>
#include <random>
using namespace std;
default_random_engine random((unsigned int)time(NULL));
uniform_real_distribution<double> u0(0, 1); //Random number distribution object
const int citycount = 29; //The number of cities is used as a global constant and needs to be assigned in the code in advance
Graph Map_City; //Define the global object graph and place it after the Graph class
GA zq; //Population category, placed after GA category
class City
{
public:
string name;//city name
double x, y;//The two-dimensional coordinates of the city point
void shuchu()
{
std::cout << name + ":" << "(" << x << "," << y << ")" << endl;
}
};
class Graph
{
public:
City city[citycount];//City array
double distance[citycount][citycount];//Distance matrix between cities
void Readcoordinatetxt(string txtfilename = "tsp.txt")//Read the function of the city coordinate file
{
ifstream myfile(txtfilename, ios::in);
double x = 0, y = 0;
int z = 0;
if (!myfile.fail())
{
int i = 0;
while (!myfile.eof() && (myfile >> z >> x >> y))
{
city[i].name = to_string(long(z));//City name is converted to string
city[i].x = x; city[i].y = y;
i++;
}
}
else
cout << "file does not exist";
myfile.close();//Calculate the city distance matrix
for (int i = 0; i < citycount; i++)
for (int j = 0; j < citycount; j++)
{
distance[i][j] = sqrt((pow((city[i].x - city[j].x), 2) + pow((city[i].y - city[j].y), 2)) / 10.0);//Calculate the pseudo Euclidean distance between cities ij
if (round(distance[i][j] < distance[i][j]))distance[i][j] = round(distance[i][j]) + 1;
else distance[i][j] = round(distance[i][j]);
}
}
void shuchu()
{
cout << "city name " << "Coordinate x" << " " << "Coordinate y" << endl;
for (int i = 0; i < citycount; i++)
city[i].shuchu();
cout << "Distance matrix:" << endl;
for (int i = 0; i < citycount; i++)
{
for (int j = 0; j < citycount; j++)
{
if (j == citycount - 1)
std::cout << distance[i][j] << endl;
else
std::cout << distance[i][j] << " ";
}
}
}
};
double round(double r) { return (r > 0.0) ? floor(r + 0.5) : ceil(r - 0.5); }
int* Random_N(int n)
{
int* geti;
geti = new int[n];
int j = 0;
while (j < n)
{
while (true)
{
int flag = -1;
int temp = rand() % n + 1;
if (j > 0)
{
int k = 0;
for (; k < j; k++)
{
if (temp == *(geti + k))break;
}
if (k == j)
{
*(geti + j) = temp;
flag = 1;
}
}
else
{
*(geti + j) = temp;
flag = 1;
}
if (flag == 1)break;
}
j++;
}
return geti;
}
class Ranseti
{
public:
int* X;
double fitness;
void Init()
{
X = new int[citycount];
int* M = Random_N(citycount);
for (int j = 0; j < citycount; j++)
X[j] = *(M + j);
fitness = 0;
}
void shuchu()
{
for (int j = 0; j < citycount; j++)
{
if (j == citycount - 1) std::cout << X[j] << " " << fitness << endl;
else std::cout << X[j] << "->";
}
}
};
class GA
{
public:
Ranseti* oldranseti;//Last generation population
Ranseti* ranseti;//Next generation population
int Pop_Size;//Population size
int Itetime;//Number of iterations
double Cross_Prob;//Crossover probability
double Bianyi_Prob;//Probability of mutation
Ranseti Bestranseti;//Best chromosomal individual
double Bestlength;//The length of the shortest path
double* Leiji_Prob;//Cumulative selection probability
void Init(int popsize, int itetime, double crossprob, double bianyiprob, string filename)
{
Map_City.Readcoordinatetxt(filename);
Map_City.shuchu();
Pop_Size = popsize;
Itetime = itetime;
Cross_Prob = crossprob;
Bianyi_Prob = bianyiprob;
oldranseti = new Ranseti[Pop_Size];
ranseti = new Ranseti[Pop_Size];
Leiji_Prob = new double[Pop_Size];
for (int i = 0; i < Pop_Size; i++)
{
oldranseti[i].Init();
oldranseti[i].fitness = Evaluate(i);//Initial fitness
}
int bestid = -1;
for (int i = 0; i < Pop_Size; i++)
{
int j = 0;
for (; j < Pop_Size; j++)
{
if (oldranseti[i].fitness > oldranseti[j].fitness)break;
}
if (j == Pop_Size)
{
bestid = i;
break;
}
}
Bestranseti.Init();
Bestranseti.fitness = 0;
for (int j = 0; j < citycount; j++)
Bestranseti.X[j] = oldranseti[bestid].X[j];
for (int j = 0; j < citycount - 1; j++)
Bestranseti.fitness += Map_City.distance[Bestranseti.X[j]][Bestranseti.X[j + 1]];
Bestranseti.fitness += Map_City.distance[Bestranseti.X[citycount - 1]][Bestranseti.X[0]];
Bestlength = Bestranseti.fitness;
}
void shuchu()
{
for (int i = 0; i < Pop_Size; i++)
oldranseti[i].shuchu();
}
double Evaluate(int k)//Calculate the function of chromosome fitness, calculate the path distance
{
double distancer = 0;
for (int j = 0; j < citycount - 1; j++)
distancer += Map_City.distance[oldranseti[k].X[j]][oldranseti[k].X[j + 1]];
distancer += Map_City.distance[oldranseti[k].X[citycount - 1]][oldranseti[k].X[0]];
oldranseti[k].fitness = distancer;
return distancer;
}
void CalculateLeijiProb()
{
double Sumfitness = -0;
for (int i = 0; i < Pop_Size; i++)
oldranseti[i].fitness = Evaluate(i);
for (int i = 0; i < Pop_Size; i++)
Sumfitness += oldranseti[i].fitness;//Calculate the sum of fitness values of all chromosomes in the population
double* SelectProb;
SelectProb = new double[Pop_Size];
for (int i = 0; i < Pop_Size; i++)
SelectProb[i] = oldranseti[i].fitness / Sumfitness;//Calculate the selection probability of each chromosome
for (int i = 0; i < Pop_Size; i++)
{
Leiji_Prob[i] = 0;
for (int j = 0; j <= i; j++)
Leiji_Prob[i] += SelectProb[j];//Calculate the cumulative probability of each chromosome
}
}
void Roulette()
{
for (int i = 0; i < Pop_Size; i++)//Roulette selection generates a new population
{
double suijishu = u0(random);//Generate a random number between 0-1
int j = 0;
for (; j < Pop_Size; j++)
{
if (suijishu <= Leiji_Prob[j])break;
}
ranseti[i].Init();
for (int k = 0; k < citycount; k++)
ranseti[i].X[k] = oldranseti[j].X[k];
}
for (int i = 0; i < Pop_Size; i++)
{
ranseti[i].fitness = 0;
for (int j = 0; j < citycount - 1; j++)
ranseti[i].fitness += Map_City.distance[ranseti[i].X[j]][ranseti[i].X[j + 1]];
ranseti[i].fitness += Map_City.distance[ranseti[i].X[citycount - 1]][ranseti[i].X[0]];
}
}
void Cross(double Pc)//Cross function adopts partial matching cross strategy
{
for (int k = 0; k + 1 < Pop_Size; k = k + 2)
{
int k1 = k;
int k2 = k1 + 1;
double suijishu = u0(random);
if (Pc > suijishu)
{
int pos1 = rand() % citycount, pos2 = rand() % citycount;
if (pos1 > pos2)//Ensure that pos1 is less than pos2
{
pos1 += pos2;
pos2 = pos1 - pos2;
pos1 = pos1 - pos2;
}
for (int j = 0; j < citycount; j++)
{
if (j >= pos1 && j <= pos2)
{
ranseti[k1].X[j] = ranseti[k1].X[j] + ranseti[k2].X[j];
ranseti[k2].X[j] = ranseti[k1].X[j] - ranseti[k2].X[j];
ranseti[k1].X[j] = ranseti[k1].X[j] - ranseti[k2].X[j];
}
}
int cishu = pos2 - pos1 + 1;
for (int j = 0; j < citycount; j++)
{
if ((j < pos1) || (j > pos2))
{
for (int jishu = 1; jishu <= cishu; jishu++)
{
for (int m = pos1; m <= pos2; m++)
{
if (ranseti[k1].X[j] == ranseti[k1].X[m])
{
ranseti[k1].X[j] = ranseti[k2].X[m];
}
}
}
}
}
for (int j = 0; j < citycount; j++)
{
if ((j < pos1) || (j > pos2))
{
for (int jishu = 1; jishu <= cishu; jishu++)
{
for (int m = pos1; m <= pos2; m++)
{
if (ranseti[k2].X[j] == ranseti[k2].X[m])
{
ranseti[k2].X[j] = ranseti[k1].X[m];
}
}
}
}
}
}
}
for (int i = 0; i < Pop_Size; i++)
{
ranseti[i].fitness = 0;
for (int j = 0; j < citycount - 1; j++)
ranseti[i].fitness += Map_City.distance[ranseti[i].X[j]][ranseti[i].X[j + 1]];
ranseti[i].fitness += Map_City.distance[ranseti[i].X[citycount - 1]][ranseti[i].X[0]];
}
}
void Bianyi(double Pm)//Variation function
{
for (int k = 0; k < Pop_Size; k++)
{
double suijishu = u0(random);
if (Pm > suijishu)
{
int pos1 = rand() % citycount, pos2 = rand() % citycount;//Randomly select two mutation locations, and then exchange the city numbers in the two locations
while (pos2 == pos1)
pos2 = rand() % citycount;
ranseti[k].X[pos1] += ranseti[k].X[pos2];
ranseti[k].X[pos2] = ranseti[k].X[pos1] - ranseti[k].X[pos2];
ranseti[k].X[pos1] = ranseti[k].X[pos1] - ranseti[k].X[pos2];
}
ranseti[k].fitness = 0;
for (int j = 0; j < citycount - 1; j++)
ranseti[k].fitness += Map_City.distance[ranseti[k].X[j]][ranseti[k].X[j + 1]];
ranseti[k].fitness += Map_City.distance[ranseti[k].X[citycount - 1]][ranseti[k].X[0]];
}
}
void SelectBestRanseti()
{
for (int i = 0; i < Pop_Size; i++)
{
if (ranseti[i].fitness < Bestranseti.fitness)
{
for (int j = 0; j < citycount; j++)
Bestranseti.X[j] = ranseti[i].X[j];
}
}
Bestranseti.fitness = 0;
for (int j = 0; j < citycount - 1; j++)
Bestranseti.fitness += Map_City.distance[Bestranseti.X[j]][Bestranseti.X[j + 1]];
Bestranseti.fitness += Map_City.distance[Bestranseti.X[citycount - 1]][Bestranseti.X[0]];
}
void GA_TSP()
{
ofstream outfile;
outfile.open("result.txt", ios::trunc);
for (int k = 0; k < Itetime; k++)
{
outfile << " " << k + 1 << "Generation population:" << endl;
CalculateLeijiProb();//Calculate the cumulative probability of the chromosomes of the previous generation population
Roulette();//The roulette method selects the next generation population
SelectBestRanseti();//Get the best individual
outfile << "The new population after roulette selection:" << endl;
for (int i = 0; i < Pop_Size; i++)
for (int j = 0; j < citycount; j++)
{
if (j == citycount - 1)outfile << ranseti[i].X[j] << " " << ranseti[i].fitness << " " << endl;
else outfile << ranseti[i].X[j] << "->";
}
Cross(Cross_Prob);
SelectBestRanseti();//Get the best individual
outfile << "New population after crossover:" << endl;
for (int i = 0; i < Pop_Size; i++)
for (int j = 0; j < citycount; j++)
{
if (j == citycount - 1)outfile << ranseti[i].X[j] << " " << ranseti[i].fitness << " " << endl;
else outfile << ranseti[i].X[j] << "->";
}
Bianyi(Bianyi_Prob);
SelectBestRanseti();//Get the best individual
outfile << "The new population after mutation:" << "\n";
for (int i = 0; i < Pop_Size; i++)
for (int j = 0; j < citycount; j++)
{
if (j == citycount - 1)outfile << ranseti[i].X[j] << " " << ranseti[i].fitness << " " << endl;
else outfile << ranseti[i].X[j] << "->";
}
SelectBestRanseti();//Get the best individual
std::cout << " " << k + 1 << "The optimal path length for the second iteration is:" << Bestranseti.fitness << endl;
outfile << " " << k + 1 << "The optimal path length for the second iteration is:" << Bestranseti.fitness << endl;
for (int i = 0; i < Pop_Size; i++)
{
for (int j = 0; j < citycount; j++)
{
oldranseti[i].X[j] = ranseti[i].X[j];
}
oldranseti[i].fitness = ranseti[i].fitness;
}
}
std::cout << "****************Iteration is over!****************" << endl;
std::cout << Itetime << "The optimal path length after the second iteration is:" << Bestranseti.fitness << endl;
std::cout << Itetime << "The optimal individual after the second iteration is as follows:" << endl;
outfile << Itetime << "The optimal path length after the second iteration is:" << Bestranseti.fitness << endl;
outfile << Itetime << "The optimal individual after the second iteration is as follows:" << endl;
for (int j = 0; j < citycount; j++)
{
if (j == citycount - 1)
{
std::cout << Bestranseti.X[j] << endl;
outfile << Bestranseti.X[j] << endl;
}
else
{
std::cout << Bestranseti.X[j] << "->";
outfile << Bestranseti.X[j] << "->";
}
}
outfile.close();
}
};
int main()
{
std::cout << "**************** Genetic algorithm to solve traveling salesman problem!****************" << endl;
std::cout << "**************** Number of cities:" << citycount << "****************" << endl;
zq.Init(50, 100, 0.8, 0.9, "C:\\Users\\Behzod\\Source\\Repos\\Gen_TSP\\tsp.txt");
std::cout << "**************** The population after initialization is as follows: ******************" << endl;
zq.shuchu();
zq.GA_TSP();
system("pause");
return 0;
}
enter image description here The program output the next error
Error C2065 'Map_City': undeclared identifier 148 Error C2065 'Map_City': undeclared identifier
Error C2065 'zq': undeclared identifier Gen_TSP
Aucun commentaire:
Enregistrer un commentaire