粒子群算法(C++版)

1、-作者xxxx-日期xxxx粒子群算法(C+版)【精品文檔】/#pragma warning (disable: 4786)/#pragma comment (linker, "/STACK:16777216")/HEAD#include <cstdio>#include <ctime>#include <cstdlib>#include <cstring>#include <queue>#include <string>#include <set>#include <stack>

2、;#include <map>#include <cmath>#include <vector>#include <iostream>#include <algorithm>#include <time.h>#include <cstdlib>using namespace std;typedef long long LL;const double MAX_VAL = (double)1e18;const int MAX_GEN = 30;/最大迭代次數(shù)const int MAX_SCALE = 3000;/最

3、大種群規(guī)模const int MAX_CITY = 20 + 2;/最大城市數(shù)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

4、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;/當(dāng)前代數(shù) int maxGen;/迭代次數(shù) int bestNum; int bestGen;/最佳出現(xiàn)代數(shù) double distMAX_CITYMAX_CITY; int oPopMAX_

5、SCALEMAX_CITY;/粒子群 double fitnessMAX_SCALE;/種群適應(yīng)度，表示種群中各個(gè)個(gè)體的適應(yīng)度 vector<SO> listVMAX_SCALE;/ 每科粒子的初始交換序列 int PdMAX_SCALEMAX_CITY;/一顆粒子歷代中出現(xiàn)最好的解， double vPdMAX_SCALE;/解的評(píng)價(jià)值 int PgdMAX_CITY;/ 整個(gè)粒子群經(jīng)歷過(guò)的的最好的解，每個(gè)粒子都能記住自己搜索到的最好解 double vPgd;/ 最好的解的評(píng)價(jià)值 PSO() PSO(int s, int c, int mG, double ww, double

6、 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

7、 = 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 < scal

8、e; 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 << "*" <<

9、 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 < scale; i+) if (vPgd > fitnessi) vPgd = fitnessi; bestNum = i; copyArray(Pgd, oPopbestN

10、um, 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;

11、for (int i = 0; i < scale; i+) if (vPdi > 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<SO> v)/ int vn = v.

12、size(); for (int i = 0; i < vn; i+) int x = vi.x, y = vi.y; swap(ax, ay); vector<SO> 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<SO> v; SO s; for (int i = 0; i < cityNum; i+) if (di

13、!= ai) s.x = i, s.y = cai; swap(ds.x, ds.y); v.push_back(s); return v;void addTo(vector<SO> &v, vector<SO> 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 (

14、int is = 0; is < scale; is+) if (is = bestNum) continue; vector<SO> v; v.clear(); int lvn = w * listVis.size(); addTo(v, listVis, lvn); vector<SO> a = minus(Pdis, oPopis); int an = randomD() * a.size(); addTo(v, a, an); vector<SO> b = minus(Pgd, oPopis); int bn = randomD() * b.s

15、ize(); 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(" &

16、quot;); printf("%dn", Pgdi); cout << bestGen << ' ' << bestNum << endl; puts(""); ;int cn;vector<Point> pv;double dMAX_CITYMAX_CITY;void pre(vector<Point> pv) int cn = pv.size(); for (int i = 0; i < cn; i+) for (int j = i + 1; j <

17、 cn; j+) dij = dji = getDist(pvi, pvj); int main () srand(unsigned long)time(0); /設(shè)置時(shí)間種子 while (cin >> 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.sol

18、ve(); 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(); j+)/ cout << listVij.x << "*" << listVij.y << ' '/ cout << endl;/ / cout << vPgd << ' ' << bestGen << '