遗传算法旅行推销员C++

Question

因此，我正在处理旅行推销员问题，其中我需要使用遗传算法来解决。该程序最终需要从输入文件中读取城市值，但现在我已经对它们进行了硬编码。当我编译时，我得到一些我不明白的错误和/或知道如何解决。有人可以帮我获得这个程序的工作吗？

以下是编译错误：

tsp.cpp:75:22: error: ISO C++ forbids initialization of member ‘fitness’ [-fpermissive] 
tsp.cpp:75:22: error: making ‘fitness’ static [-fpermissive] 
tsp.cpp:75:22: error: ISO C++ forbids in-class initialization of non-const static member ‘fitness’ 
tsp.cpp:76:20: error: ISO C++ forbids initialization of member ‘distance’ [-fpermissive] 
... more of these ... 

In file included from /usr/include/c++/4.6/algorithm:63:0, 
       from tsp.cpp:6: 
/usr/include/c++/4.6/bits/stl_algo.h: In function ‘void std::random_shuffle(_RAIter, _RAIter, _Generator&) [with _RAIter = __gnu_cxx::__normal_iterator<City*, std::vector<City> >, _Generator = std::vector<City>]’:  
tsp.cpp:104:54: instantiated from here 
/usr/include/c++/4.6/bits/stl_algo.h:5185:2: error: no match for call to ‘(std::vector<City>) (__gnu_cxx::__normal_iterator<City*, std::vector<City> >::difference_type)’ 

还有我不知道如果我甚至将这个问题的正确方法。这个程序在概念上是否正确？

#include <iostream> 
#include <ctime> 
#include <cstdlib> 
#include <cmath> 
#include <vector> 
#include <algorithm> 

using namespace std; 

class City 
{ 
private: 
    int x; 
    int y; 

public: 
    //constructs a city at chosen x,y location 
    City(int x, int y) 
    { 
     this->x = x; 
     this->y = y; 
    } 

    int getX() 
    { 
     return this->x; 
    } 

    int getY() 
    { 
     return this->y; 
    } 

    double distanceTo(City city) 
    { 
     int xDistance = abs(getX() - city.getX()); 
     int yDistance = abs(getY() - city.getY()); 
     double distance = sqrt((xDistance*xDistance) + (yDistance*yDistance)); 

     return distance; 
    } 
}; 

class TourManager 
{ 
private: 
    //holds the cities 
    vector<City> destinationCities; 

public: 
    //adds a destination city 
    void addCity(City city) 
    { 
     destinationCities.push_back(city); 
    } 

    //get a city 
    City getCity(int index) 
    { 
     return (City)destinationCities.at(index); 
    } 

    //get the number of destination city 
    int numberOfCities() 
    { 
     return (int)destinationCities.size(); 
    } 
}; 

class Tour 
{ 
private: 
    //holds our tour of cities 
    vector<City> tour; 
    double fitness = 0; 
    int distance = 0; 
    TourManager tourManager; 

public: 
    //constructs a blank tour 
    Tour() 
    { 
     City *city = new City(0, 0); 
     for (int i = 0; i < tourManager.numberOfCities(); ++i) 
     { 
      tour.push_back(*city); 
     } 
    } 

    Tour(vector<City> tour) 
    { 
     this->tour = tour; 
    } 

    //generates a random individual 
    void generateIndividual() 
    { 
     //loop through all our destinations cities and add them to our tour 
     for (int cityIndex = 0; cityIndex < tourManager.numberOfCities(); ++cityIndex) 
     { 
      setCity(cityIndex, tourManager.getCity(cityIndex)); 
     } 
     //randomly reorder the tour 
     random_shuffle(tour.begin(), tour.end(), tour); 
    } 

    City getCity(int tourPosition) 
    { 
     return (City)tour.at(tourPosition); 
    } 

    void setCity(int tourPosition, City city) 
    { 
     //CAUTION: not sure if the line below will work! 
     tour.insert(tour.begin()+tourPosition, city); 

     //if the tour has been altered we need to reset fitness and distance 
     fitness = 0; 
     distance = 0; 
    } 

    //gets the tours fitness (fitness = cost?) 
    double getFitness() 
    { 
     if (fitness == 0) 
     { 
      fitness = 1/(double)getDistance(); 
     } 

     return fitness; 
    } 

    // Gets the total distance of the tour 
    int getDistance() 
    { 
     if (distance == 0) 
     { 
      int tourDistance = 0; 

      // Loop through our tour's cities 
      for (int cityIndex=0; cityIndex < tourSize(); cityIndex++) 
      { 
       // Get city we're travelling from 
       City fromCity = getCity(cityIndex); 

       // City we're travelling to 
       City *destinationCity = new City(0,0); 

       // Check we're not on our tour's last city, if we are set our 
       // tour's final destination city to our starting city 
       if(cityIndex+1 < tourSize()) 
       { 
        *destinationCity = getCity(cityIndex+1); 
       } 
       else 
       { 
        *destinationCity = getCity(0); 
       } 

       // Get the distance between the two cities 
       tourDistance += fromCity.distanceTo(*destinationCity); 
      } 
      distance = tourDistance; 
     } 
     return distance; 
    } 

    //get the number of cities on our tour 
    int tourSize() 
    { 
     return (int)tour.size(); 
    } 

    // Check if the tour contains a city 
    bool containsCity(City city) 
    { 
     for (int i = 0; i < tourSize(); ++i) 
     { 
      if((tour[i].getX() == city.getX()) && (tour[i].getY() == city.getY())) 
       return true; 
     } 

     return false; 
    } 
}; 

class Population 
{ 
private: 
    //hold population of tours 
    vector<Tour> tours; 

public: 
    //contructs a population 
    Population(int populationSize, bool initialize) 
    { 
     tours.resize(populationSize); 

     //if we need to initialize a population then do so 
     if (initialize) 
     { 
      for (int i = 0; i < populationSize; ++i) 
      { 
       Tour *newTour = new Tour(); 
       newTour->generateIndividual(); 
       saveTour(i, *newTour); 
      } 
     } 
    } 

    // Saves a tour 
    void saveTour(int index, Tour tour) 
    { 
     tours[index] = tour; 
    } 

    // Gets a tour from population 
    Tour getTour(int index) 
    { 
     return tours[index]; 
    } 

    // Gets the best tour in the population 
    Tour getFittest() 
    { 
     Tour fittest = tours[0]; 

     // Loop through individuals to find fittest 
     for (int i = 1; i < populationSize(); i++) 
     { 
      if (fittest.getFitness() <= getTour(i).getFitness()) 
      { 
       fittest = getTour(i); 
      } 
     } 
     return fittest; 
    } 

    // Gets population size 
    int populationSize() 
    { 
     return (int)tours.size(); 
    } 
}; 

class GA 
{ 
private: 

    /* GA parameters */ 
    double mutationRate = 0.015; 
    int tournamentSize = 5; 
    bool elitism = true; 

public: 

    //Evolves a population over one generation 
    Population evolvePopulation(Population pop) 
    { 
     Population* newPopulation = new Population(pop.populationSize(), false); 

     //keep our best individual if elitism is enabled 
     int elitismOffset = 0; 
     if (elitism) 
     { 
      newPopulation->saveTour(0, pop.getFittest()); 
      elitismOffset = 1; 
     } 

     // Crossover population 
     // Loop over the new population's size and create individuals from 
     // Current population 
     for (int i = 0; i < newPopulation->populationSize(); ++i) 
     { 
      //select parents 
      Tour parent1 = tournamentSelection(pop); 
      Tour parent2 = tournamentSelection(pop); 

      //crossover parents 
      Tour child = crossover(parent1, parent2); 

      //add child to new population 
      newPopulation->saveTour(i, child); 
     } 

     //mutate the new population a bit to add some new genetic material 
     for (int i = elitismOffset; i < newPopulation->populationSize(); ++i) 
     { 
      mutate(newPopulation->getTour(i)); 
     } 

     return *newPopulation; 
    } 

    //applies crossover to a set of parents and creates offspring 

    Tour crossover(Tour parent1, Tour parent2) 
    { 
     //create the new child 
     Tour* child = new Tour(); 
     City* cityBlank = new City(0, 0); 

     //get start and end sub tour positions for parents1's tour 
     int startPos = (int) (rand() * parent1.tourSize()); 
     int endPos = (int) (rand() * parent1.tourSize()); 

     // Loop and add the sub tour from parent1 to our child 
     for (int i = 0; i < child->tourSize(); i++) 
     { 
      // if our start position is less than the end position 
      if (startPos < endPos && i > startPos && i < endPos) 
      { 
       child->setCity(i, parent1.getCity(i)); 
      } // If our start position is larger 
      else if (startPos > endPos) 
      { 
       if (!(i < startPos && i > endPos)) 
       { 
        child->setCity(i, parent1.getCity(i)); 
       } 
      } 
     } 

     // Loop through parent2's city tour 
     for (int i = 0; i < parent2.tourSize(); i++) 
     { 
      // If child doesn't have the city add it 
      if (!child->containsCity(parent2.getCity(i))) 
      { 
       // Loop to find a spare position in the child's tour 
       for (int ii = 0; ii < child->tourSize(); ii++) 
       { 
        // Spare position found, add city 
        // CHECK HERE! 
        if (child->getCity(ii).getX() == cityBlank->getX() && child->getCity(ii).getY() == cityBlank->getY()) 
        { 
         child->setCity(ii, parent2.getCity(i)); 
         break; 
        } 
       } 
      } 
     } 
     return *child; 
    } 

    // Mutate a tour using swap mutation 
    void mutate(Tour tour) 
    { 
     // Loop through tour cities 
     for(int tourPos1=0; tourPos1 < tour.tourSize(); tourPos1++) 
     { 
      // Apply mutation rate 
      if(rand() < mutationRate) 
      { 
       // Get a second random position in the tour 
       int tourPos2 = (int) (tour.tourSize() * rand()); 

       // Get the cities at target position in tour 
       City city1 = tour.getCity(tourPos1); 
       City city2 = tour.getCity(tourPos2); 

       // Swap them around 
       tour.setCity(tourPos2, city1); 
       tour.setCity(tourPos1, city2); 
      } 
     } 
    } 

    // Selects candidate tour for crossover 
    Tour tournamentSelection(Population pop) 
    { 
     // Create a tournament population 
     Population* tournament = new Population(tournamentSize, false); 

     // For each place in the tournament get a random candidate tour and 
     // add it 
     for (int i = 0; i < tournamentSize; i++) 
     { 
      int randomId = (int) (rand() * pop.populationSize()); 
      tournament->saveTour(i, pop.getTour(randomId)); 
     } 

     // Get the fittest tour 
     Tour fittest = tournament->getFittest(); 

     return fittest; 
    } 
}; 

int main() 
{ 
    TourManager tourmanager; 
    GA ga; 

    City *city1 = new City(60, 200); 
    tourmanager.addCity(*city1); 

    City *city2 = new City(180, 200); 
    tourmanager.addCity(*city2); 

    City *city3 = new City(80, 180); 
    tourmanager.addCity(*city3); 

    City *city4 = new City(140, 180); 
    tourmanager.addCity(*city4); 

    City *city5 = new City(20, 160); 
    tourmanager.addCity(*city5); 

    //initialize population 
    Population *pop = new Population(50, true); 
    cout << "Initial distance: " << pop->getFittest().getDistance() << endl; 

    // Evolve population for 50 generations 
    *pop = ga.evolvePopulation(*pop); 
    for (int i = 0; i < 100; i++) 
    { 
     *pop = ga.evolvePopulation(*pop); 
    } 

    // Print final results 
    cout << "Finished" << endl; 
    cout << "Final distance: " << pop->getFittest().getDistance() << endl; 
    cout << "Solution: " << pop->getFittest() << endl; 

} 

Answer 1

关于你的错误ISO C++ forbids initialization of member ...，那是因为你使用c++11语法但没有指定编译C++ 11。尝试使用编译器选项，如-std=c++11（GCC）。您还有没有定义std:ostream& operator<<(std::ostream&, const Tour&)，你有吗？

cout << "Solution: " << pop->getFittest() << endl; 

-> prog.cpp:424:26: error: no match for ‘operator<<’ (operand types are ‘std::basic_ostream<char>’ and ‘Tour’) 

不知道我是否抓住了所有的编译错误，但修复这些会减少它们很多。