粒子群(PSO)解決TSP問題

粒子群算法也稱粒子群優化算法，簡稱PSO(Partical Swarm Optimization)。

以下是求解TSP問題的源碼：

#include <vector>
#include <time.h>
#include <stdlib.h>
#include <iostream>
#include <math.h>
#include <fstream>
using namespace std;
#define MAX_DIS 10000000
#define MAX_ARR 500
class PSO
{
public:
    PSO(int c, int pop,int g) :popsize(pop),cities(c),genMax(g) {}

    void InitialSwarm(int** a);
    void Move(int** a);
    void print();

    ~PSO();
private:
    typedef struct{
        int ei;
        int ej;
    }exchangeSeq;
    typedef struct{
        vector<int> sbest;
        int length;
    }seqlen;
    typedef struct{
        vector<int> idl;
        vector<exchangeSeq> velocity;
        seqlen pbest;
    }particle;
    int popsize;
    int cities;
    int genMax;
    seqlen gbest;
    vector<particle> particleSwarm;

    vector<int> BuildRandomSequence(int);
    int getPathLen(int** a,const vector<int>&);
    void computeNexPos(vector<int>&,vector<exchangeSeq>);
    void computeNewVelocity(particle&);
    vector<exchangeSeq> computeEquivalentSet(vector<exchangeSeq>, vector<exchangeSeq>);
    vector<exchangeSeq> BuildBasicExchangeSeq(vector<int>, vector<int>);
    void Movement(int** a);
};

PSO::~PSO()
{
}

//計算一條路徑長度
int PSO::getPathLen(int** a,const vector<int>& seq)
{
    int path = ;
    for (size_t pos = ; pos < cities; pos++)
    {
        path += a[seq[pos - ]][seq[pos]];
    }
    path += a[seq[]][seq[cities - ]];
    return path;
}


//生成等價集
vector<PSO::exchangeSeq> PSO::computeEquivalentSet(vector<PSO::exchangeSeq> sq1, vector<PSO::exchangeSeq> sq2)
{
    vector<int> seq1, seq2;
    for (size_t i = ; i < cities; i++) seq1.push_back(i);
    seq2 = seq1;
    computeNexPos(seq1, sq1);
    computeNexPos(seq1, sq2);
    return BuildBasicExchangeSeq(seq2, seq1);
}


//生成基本交換序
vector<PSO::exchangeSeq> PSO::BuildBasicExchangeSeq(vector<int> seq1, vector<int> seq2)
{
    vector<exchangeSeq> Seq;
    vector<int> sq = seq2;
    int tp;
    exchangeSeq q;
    size_t i, j;
    for (i = ; i < seq1.size()-; i++)
    {
        for (j = i; j < seq1.size() && sq[j] != seq1[i]; j++);
        q.ei = i;
        q.ej = j;

        if (i == j) continue;
        tp = sq[i];
        sq[i] = sq[j];
        sq[j] = tp;
        Seq.push_back(q);
    }
    return Seq;
}

//根據目前解計算下一個解，也即下一個位置
void PSO::computeNexPos(vector<int>& idl, vector<exchangeSeq> v)
{
     int tp;
     for (size_t i = ; i < v.size(); i++)
    {
        tp = idl[v[i].ei];
        idl[v[i].ei] = idl[v[i].ej];
        idl[v[i].ej] = tp;
    }
}

void PSO::computeNewVelocity(particle& pl)
{
    vector<exchangeSeq> Pid = BuildBasicExchangeSeq(pl.pbest.sbest, pl.idl);
    vector<exchangeSeq> Pgd = BuildBasicExchangeSeq(gbest.sbest, pl.idl);

    vector<exchangeSeq> tp = pl.velocity;
    tp = computeEquivalentSet(tp, Pid);
    pl.velocity = computeEquivalentSet(tp, Pgd);
}

//産生随機序列
vector<int> PSO::BuildRandomSequence(int len)
{
    vector<int> vc;
    int i;
    for (i = ; i < len; i++)  vc.push_back(i);
    int x = , tmp = ;
    for (i = len - ; i > ; i--) {
        x = rand() % (i + );
        tmp = vc[i];
        vc[i] = vc[x];
        vc[x] = tmp;
    }
    return vc;
}


//初始化粒子群
void PSO::InitialSwarm(int** a)
{
    int i, j,tp=;
    particle pt;
    exchangeSeq exSeq;
    int shortlen = MAX_DIS;
    srand((unsigned)time(NULL));
    for (i = ; i < popsize; i++)
    {
        pt.idl = BuildRandomSequence(cities);
        pt.pbest.sbest = pt.idl;
        pt.pbest.length = getPathLen(a, pt.pbest.sbest);

        for (j = ; j<cities; j++)
        {
            exSeq.ei = rand() % cities;
            exSeq.ej = rand() % cities;
            pt.velocity.push_back(exSeq);
        }

        particleSwarm.push_back(pt);
        if (shortlen>pt.pbest.length)
        {
            shortlen = pt.pbest.length;
            tp = i;
        }
    }
    gbest = particleSwarm[tp].pbest;
}

void PSO::Movement(int** a)
{
    int tp=;
    for (size_t i = ; i < particleSwarm.size(); i++)
    {
        computeNexPos(particleSwarm[i].idl, particleSwarm[i].velocity);
        computeNewVelocity(particleSwarm[i]);
        if (particleSwarm[i].pbest.length > getPathLen(a, particleSwarm[i].idl))
        {
            particleSwarm[i].pbest.length = getPathLen(a, particleSwarm[i].idl);
            particleSwarm[i].pbest.sbest = particleSwarm[i].idl;
        }
        if (particleSwarm[i].pbest.length < gbest.length)
        {
            gbest.length = particleSwarm[i].pbest.length;
                tp = i;
        }
    }
    gbest.sbest = particleSwarm[tp].idl;
}

void PSO::Move(int** a)
{
    for (int i = ; i < genMax; i++) Movement(a);
}
//列印結果，即最短距離和路徑
void PSO::print()
{
    cout << "最短距離： " << gbest.length << endl;
    cout << "最短路徑：";
    for (size_t i = ; i < gbest.sbest.size(); i++) cout << gbest.sbest[i] << " ";
    cout << gbest.sbest[]<<endl;
}
//created by chithon
           

以上給出了用粒子群優化算法解決TSP問題的基本代碼，難點主要是粒子的速度如何表示，其變化過程怎樣展現，這是難點，在此代碼中涉及的處理方法主要參考：

黃 岚.粒子群優化算法求解旅行商問題.吉林大學學報.2003