vendredi 3 décembre 2021

Genetic Algorithm for TSP in C++ errors [closed]

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