粒子群算法(C++版).doc

/#pragma warning (disable: 4786)/#pragma comment (linker, /STACK:16777216)/HEAD#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long LL;const double MAX_VAL = (double)1e18;const int MAX_GEN = 30;/最大迭代次数const int MAX_SCALE = 3000;/最大种群规模const int MAX_CITY = 20 + 2;/最大城市数const double W_VAL = 0.729;/struct SO int x, y; SO() SO(int x, int y): x(x), y(y);struct Point double x, y; Point() Point(int x, int y):x(x), y(y); void read() scanf(%lf%lf, &x, &y); ;inline int randomI(int x) return rand()%x; inline double randomD() return (double)rand()/RAND_MAX; inline double getDist(Point a, Point b) return sqrt(a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);struct PSO double w; int scale; int cityNum; int nowGen;/当前代数 int maxGen;/迭代次数 int bestNum; int bestGen;/最佳出现代数 double distMAX_CITYMAX_CITY; int oPopMAX_SCALEMAX_CITY;/粒子群 double fitnessMAX_SCALE;/种群适应度，表示种群中各个个体的适应度 vector listVMAX_SCALE;/ 每科粒子的初始交换序列 int PdMAX_SCALEMAX_CITY;/一颗粒子历代中出现最好的解， double vPdMAX_SCALE;/解的评价值 int PgdMAX_CITY;/ 整个粒子群经历过的的最好的解，每个粒子都能记住自己搜索到的最好解 double vPgd;/ 最好的解的评价值 PSO() PSO(int s, int c, int mG, double ww, double dMAX_CITYMAX_CITY) scale = s; cityNum = c; maxGen = mG; w = ww; for (int i = 0; i cityNum; i+) for (int j = 0; j cityNum; j+) distij = dij; void copyArray(double a, double b, int n) for (int i = 0; i n; i+) ai = bi; void copyArray(int a, int b, int n) for (int i = 0; i n; i+) ai = bi; void init() nowGen = 0; for (int i = 0; i scale; i+) for (int j = 0; j cityNum; ) int x = randomI(cityNum); int r; for (r = 0; r j; r+) if (x = oPopir) break; if (r = j) oPopij = x;/ cout oPopij ; j+; / cout endl; for (int i = 0; i scale; i+) / cout i : endl; int vn = randomI(cityNum) + 1; for (int j = 0; j vn; j+) int x = randomI(cityNum); int y = randomI(cityNum); while (x = y) y = randomI(cityNum); SO so(x, y); listVi.push_back(so);/ cout so.x * so.y ; / cout endl; getFitness(); for (int i = 0; i scale; i+) vPdi = fitnessi; copyArray(Pdi, oPopi, cityNum); bestNum = 0; vPgd = fitness0; bestGen = 0; for (int i = 0; i fitnessi) vPgd = fitnessi; bestNum = i; copyArray(Pgd, oPopbestNum, cityNum); double getVal(int x) double ret = 0; for (int i = 0; i cityNum; i+) int xx = oPopxi % cityNum; int yy = oPopx(i + 1) % cityNum; ret += distxxyy; return ret; void getFitness() for (int i = 0; i scale; i+) fitnessi = getVal(i); void UpdateVal() int j = 0; double vj = fitness0; for (int i = 0; i fitnessi) vPdi = fitnessi; copyArray(Pdi, oPopi, cityNum);/? if (vj fitnessi) vj = fitnessi; j = i; if (vj vPgd) bestGen = nowGen;/ bestNum = j;/ vPgd = vj; copyArray(Pgd, oPopj, cityNum); void changeTo(int a, vector v)/ int vn = v.size(); for (int i = 0; i vn; i+) int x = vi.x, y = vi.y; swap(ax, ay); vector minus(int a, int b)/ int cMAX_CITY, dMAX_CITY; for (int i = 0; i cityNum; i+) di = bi; for (int i = 0; i cityNum; i+) cai = i; vector v; SO s; for (int i = 0; i cityNum; i+) if (di != ai) s.x = i, s.y = cai; swap(ds.x, ds.y); v.push_back(s); return v;void addTo(vector &v, vector a, int vn) for (int i = 0; i vn; i+) v.push_back(ai); / Vii=wVi+ra(Pid-Xid)+rb(Pgd-Xid) void evolution() for (int ig = 0; ig maxGen; ig+) nowGen = ig + 1;/nowGen for (int is = 0; is scale; is+) if (is = bestNum) continue; vector v; v.clear(); int lvn = w * listVis.size(); addTo(v, listVis, lvn); vector a = minus(Pdis, oPopis); int an = randomD() * a.size(); addTo(v, a, an); vector b = minus(Pgd, oPopis); int bn = randomD() * b.size(); addTo(v, b, bn); listVis = v; changeTo(oPopis, listVis);/ cout listVis.size() endl; getFitness(); UpdateVal(); void solve() init(); evolution(); printf(answer %lf:n, vPgd); printf(solution n); for (int i = 0; i cityNum; i+) if (i) printf( ); printf(%dn, Pgdi); cout bestGen bestNum endl; puts(); ;int cn;vector pv;double dMAX_CITYMAX_CITY;void pre(vector pv) int cn = pv.size(); for (int i = 0; i cn; i+) for (int j = i + 1; j cn) pv.clear(); for (int i = 0; i cn; i+) Point p; p.read(); pv.push_back(p); pre(pv); PSO solver(MAX_SCALE, cn, MAX_GEN, W_VAL, d); cout * endl; solver.solve(); cout * endl; return 0;/ cout nowGen -: endl;/ for (int i = 0; i scale; i+)/ / cout vPdi fitnessi endl;/ for (int j = 0; j cityNum; j+)/ cout Pdij ;/ cout endl;/ / for (int i = 0; i scale; i+)/ / for (int j = 0; j listVi.size