1、/#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>#include <map>#include

2、<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;/最大迭代次數const int MAX_SCALE = 3000;/最大種群規模const int MAX_CITY = 20 +

3、 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(

4、)/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 fitn

5、essMAX_SCALE;/種群適應度，表示種群中各個個體的適應度 vector<SO> 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;

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

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

8、lt; " :" << 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 << ' ' / c

9、out <<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, oPopbestNum, cityNum); double getVal(in

10、t 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 < scale;

11、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.size(); for (int i = 0; i <

12、 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 != ai) s.x = i, s.y = cai; swa

13、p(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 (int is = 0; is < scale; is+

14、) 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.size(); addTo(v, b, bn); listVi

15、s = 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"

16、, 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 < cn; j+) dij = dji = getDist(p

17、vi, pvj); int main () srand(unsigned long)time(0); /設置時間種子 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.solve(); cout << "*&qu

18、ot; << 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 << &