粒子群算法求解tsp问题 c++代码

以下是用C++实现的粒子群算法求解TSP问题的代码：

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

using namespace std;

// 定义城市类
class City {
public:
    City(double x = 0, double y = 0) : x(x), y(y) {}
    double getX() const { return x; }
    double getY() const { return y; }
    double distanceTo(const City& city) const {
        double dx = x - city.getX();
        double dy = y - city.getY();
        return sqrt(dx * dx + dy * dy);
    }
private:
    double x;
    double y;
};

// 定义粒子类
class Particle {
public:
    Particle(int numCities) : position(numCities), velocity(numCities) {
        for (int i = 0; i < numCities; ++i) {
            position[i] = i;
            velocity[i] = rand() % 100 / 100.0;
        }
        random_shuffle(position.begin(), position.end());
        bestPosition = position;
        bestFitness = fitness();
    }
    void update(const vector<int>& globalBestPosition) {
        updateVelocity(globalBestPosition);
        updatePosition();
        double fitnessValue = fitness();
        if (fitnessValue < bestFitness) {
            bestPosition = position;
            bestFitness = fitnessValue;
        }
    }
    vector<int> getPosition() const { return position; }
    vector<int> getBestPosition() const { return bestPosition; }
    double getBestFitness() const { return bestFitness; }
private:
    vector<int> position;
    vector<int> bestPosition;
    vector<double> velocity;
    double bestFitness;
    double fitness() const {
        double sum = 0;
        for (int i = 0; i < position.size() - 1; ++i) {
            sum += cities[position[i]].distanceTo(cities[position[i+1]]);
        }
        sum += cities[position[position.size()-1]].distanceTo(cities[position[0]]);
        return sum;
    }
    void updateVelocity(const vector<int>& globalBestPosition) {
        const double w = 0.5;
        const double c1 = 1;
        const double c2 = 2;
        for (int i = 0; i < velocity.size(); ++i) {
            double r1 = rand() % 100 / 100.0;
            double r2 = rand() % 100 / 100.0;
            velocity[i] = w * velocity[i] + c1 * r1 * (bestPosition[i] - position[i]) +
                          c2 * r2 * (globalBestPosition[i] - position[i]);
        }
    }
    void updatePosition() {
        for (int i = 0; i < position.size(); ++i) {
            position[i] += round(velocity[i]);
            if (position[i] < 0) {
                position[i] += position.size();
            }
            if (position[i] >= position.size()) {
                position[i] -= position.size();
            }
        }
    }
    static vector<City> cities;
};

vector<City> Particle::cities;

// 定义粒子群算法类
class PSO {
public:
    PSO(int numParticles, int numCities, int maxIterations) :
        numParticles(numParticles), numCities(numCities), maxIterations(maxIterations) {
        for (int i = 0; i < numParticles; ++i) {
            particles.push_back(Particle(numCities));
        }
        globalBestPosition = particles[0].getPosition();
        globalBestFitness = particles[0].getBestFitness();
        for (int i = 1; i < numParticles; ++i) {
            double fitnessValue = particles[i].getBestFitness();
            if (fitnessValue < globalBestFitness) {
                globalBestPosition = particles[i].getBestPosition();
                globalBestFitness = fitnessValue;
            }
        }
    }
    void run() {
        for (int i = 0; i < maxIterations; ++i) {
            for (int j = 0; j < numParticles; ++j) {
                particles[j].update(globalBestPosition);
            }
            for (int j = 0; j < numParticles; ++j) {
                double fitnessValue = particles[j].getBestFitness();
                if (fitnessValue < globalBestFitness) {
                    globalBestPosition = particles[j].getBestPosition();
                    globalBestFitness = fitnessValue;
                }
            }
        }
        cout << "最短路径长度为：" << globalBestFitness << endl;
        cout << "最短路径为：";
        for (int i = 0; i < globalBestPosition.size(); ++i) {
            cout << globalBestPosition[i] << " ";
        }
        cout << endl;
    }
private:
    int numParticles;
    int numCities;
    int maxIterations;
    vector<Particle> particles;
    vector<int> globalBestPosition;
    double globalBestFitness;
};

// 测试
int main() {
    srand((unsigned)time(NULL));
    const int numParticles = 50;
    const int numCities = 10;
    const int maxIterations = 1000;
    for (int i = 0; i < numCities; ++i) {
        double x = rand() % 1000 / 10.0;
        double y = rand() % 1000 / 10.0;
        Particle::cities.push_back(City(x, y));
    }
    PSO pso(numParticles, numCities, maxIterations);
    pso.run();
    return 0;
}

其中，City类表示一个城市，Particle类表示一个粒子，PSO类表示粒子群算法。在main函数中，首先生成一些随机的城市，然后创建一个PSO对象并运行，最后输出最优路径的长度和路径。