• MostafaSalehi
    了解作者
  • C/C++
    开发工具
  • 65KB
    文件大小
  • rar
    文件格式
  • 0
    收藏次数
  • 1 积分
    下载积分
  • 5
    下载次数
  • 2017-06-20 21:51
    上传日期
Travelling Salesman Problem (TSP) with PSO in C++
TSP with PSO.rar
  • TSP with PSO
  • __history
  • global_var.c.~1~
    2.5KB
  • particle_tools.c
    46.9KB
  • graph_tools.c
    9.9KB
  • display.c
    1.7KB
  • param.c
    6.5KB
  • br17.atsp
    1.6KB
  • graph6.2
    266B
  • swarm_tools.h
    591B
  • global_var.c
    2.5KB
  • particle_tools.h
    1.7KB
  • math_add.c
    4.7KB
  • display.h
    299B
  • graph_Godf_x50.1
    55.3KB
  • display_position_TSP.c
    946B
  • swarm_tools.c
    5.7KB
  • graph_br17
    1.6KB
  • f_TSP.c
    5.2KB
  • math_add.h
    399B
  • main.c
    25.1KB
  • def_and_struc.h
    724B
  • path_tools.c
    5.4KB
  • TSP.c
    44.9KB
  • graph_tools.h
    451B
  • graph_6.2
    263B
  • graph_4
    196B
  • f_Sort.c
    2.5KB
  • display_position_Sort.c
    296B
内容介绍
//------------------------------------------------------------------- ALEA_VELOCITY struct velocity alea_velocity(int N) { int i; struct velocity vt; vt.size=alea(1,N); for (i=0;i<vt.size;i++) { vt.comp[i][0]=alea(0,G.N-1); vt.comp[i][1]=alea_diff(0,G.N-1,vt.comp[i][0]); } //display_velocity(vt); return vt; } // ------------------------------------------------------------------- AUTO_MOVE struct particle auto_move(struct particle p,int type, int monotony, int levelling,int trace) /* The particle moves slowly, looking for a better position */ { int b,d,g; int dd,gg; //double best_before; double delta1,delta2,delta_min; double eval_f0; int i,j,k; int improv; //int levelling0; int loop,loop_max; int node; struct particle pt,pt1,pt2; struct velocity v; if (trace>1) printf("\n Auto-move type %i for particle %i. Size %i \n",type,p.rank+1,p.x.size); pt=p; if (pt.x.s[0]!=0) pt.x=rotate(pt.x,0); if (pt.best_x.s[0]!=0) pt.best_x=rotate(pt.best_x,0); // loop_max=G.N; loop_max=1; if (type==0) // Lazy Descent Method (random) { for(loop=0;loop<loop_max;loop++) { for (i=0;i<G.N;i++) // Move at random. { pt.v=alea_velocity(1); pt=pos_plus_vel(pt,pt.v,monotony,1,levelling); if(pt.best_f<p.best_f) // Stop as soon as a better position is found { goto return_pt; } } } if (trace>1) {printf("\n auto move => no move ");display_position(p,1);} return p; } if (type==1) // Energetic { next_step1: for (i=0;i<G.N;i++) // Move at random { pt.v=alea_velocity(1); // Just one transposition (switch) pt1=pos_plus_vel(pt,pt.v,monotony,1,levelling); if(pt1.best_f<pt.best_f) // Move as long as a better position is found { pt=pt1; goto next_step1; } } goto return_pt; } // type=2, 3, 5, 6, 7 if (trace>1) printf("\n transpositions"); /* Check all immediate physical neighbours. If one is better, choose the best, and move if (type=3, 5, 6, 7 ) check again */ v.size=1; next_step2: improv=0; delta_min=pt.best_f-target; for (j=0;j<G.N-1;j++) // For each neighbour { v.comp[0][0]=j; for (k=j+1;k<G.N;k++) { v.comp[0][1]=k; pt1=pos_plus_vel(pt,v,monotony,1,levelling); delta1=pt1.best_f-target; if( delta1<delta_min) { if (trace>1) {printf("\n auto move => ");display_position(pt1,1);} delta_min=delta1; pt=pt1; // Memorize the best new position improv=1; if (delta_min<=0) goto end_type2; // By any chance ... } } } if (improv==1 &&(type==3 || type==5 || type==6 || type==7)) // Move as long as a better position is found { goto next_step2; } if (type==6) goto three_opt; if (type==7) goto three_opt_weak; end_type2: goto return_pt; //---------------------------------------------------------------------------------------------------------------- three_opt: if(pt. best_time<splice_time ) goto return_pt; if (trace>1) printf("\n auto_move, 3-opt"); three_opt_loop: // b=>g => d=> b, so (b,d,g) => (g,d,b) // or // b=> d=>g=>b, so (b,d,g) => (d,g,b) delta_min=pt.best_f-target; // Maximum possible improvement // for (b=0;b<G.N;b++) for (b=0;b<G.N-2;b++) { //for (d=b+1;d<b+G.N;d++) for (d=b+1;d<G.N-1;d++) { //dd=d%G.N; //if (dd==b) continue; //for (g=dd+1;g<dd+G.N;g++) //for (g=dd+1;g<dd+G.N;g++) for (g=d+1;g<G.N;g++) { //gg=g%G.N; // if (gg==b) continue; //if (gg==dd) continue; pt1=pt; pt1.x=pt.best_x; // Try to directly modify the best previous position pt2=pt1; node= pt1.x.s[b]; pt1.x.s[b]=pt1.x.s[g]; pt1.x.s[g]=pt1.x.s[d]; pt1.x.s[d]=node; eval_f0=eval_f; pt1.f=f(pt1,-1,-1); eval_f=eval_f0+6.0/G.N; // This move could be done by just two transpositions // so it wouldn't be fair to count a complete evaluation node= pt2.x.s[b]; pt2.x.s[b]=pt2.x.s[d]; pt2.x.s[d]=pt2.x.s[g]; pt2.x.s[g]=node ; eval_f0=eval_f; pt2.f=f(pt2,-1,-1); eval_f=eval_f0+6.0/G.N; delta1= pt1.f-target; delta2= pt2.f-target; if (MIN(delta1,delta2)>=delta_min) goto next_g; // No improvement if (delta1<delta2) { p1: pt=pt1; delta_min=delta1; goto end_improve; } if (delta2<delta1) { p2: pt=pt2; delta_min=delta2; goto end_improve; } if (delta1==delta2) { if (alea(0,1)==0) goto p1; else goto p2; } end_improve: next_g:; } // g } // d } // b if(pt.f<pt.best_f) { pt.best_x=pt.x; pt.best_f=pt.f; pt.best_time=time; if (move[4]>=3) BB_update(pt); goto three_opt_loop; // Try again } goto return_pt; //----------------------------------------------------------------------------------------------------- three_opt_weak: // Only three _consecutive_ nodes if(pt. best_time<splice_time ) goto return_pt; if (trace>1) printf("\n auto_move, 3-opt_weak"); // three_opt_weak_loop: delta_min=pt.best_f-target; // Maximum possible improvement // (b,b+1,b+2) => (b+2,b,b+1) // or // (b,b+1,b+2) => (b+1,b+2,b) for (b=0;b<G.N;b++) { dd=(b+1)%G.N; gg=(dd+1)%G.N; pt1=pt; pt1.x=pt.best_x; // Try to directly modify the best previous position pt2=pt1; node= pt1.x.s[b]; pt1.x.s[b]=pt1.x.s[gg]; pt1.x.s[gg]=pt1.x.s[dd]; pt1.x.s[dd]=node; eval_f0=eval_f; pt1.f=f(pt1,-1,-1); eval_f=eval_f0+6.0/G.N; // This move could be done by just two transpositions // so it wouldn't be fair to count a complete evaluation node= pt2.x.s[b]; pt2.x.s[b]=pt2.x.s[dd]; pt2.x.s[dd]=pt2.x.s[gg]; pt2.x.s[gg]=node ; eval_f0=eval_f; pt2.f=f(pt2,-1,-1); eval_f=eval_f0+6.0/G.N; delta1= pt1.f-target; delta2= pt2.f-target; if (MIN(delta1,delta2)>=delta_min) goto next_b_2; // No improvement if (delta1<delta2) { pt_1: pt=pt1; delta_min=delta1; goto end_improve_2; } if (delta2<delta1) { pt_2: pt=pt2; delta_min=delta2; goto end_improve_2; } if (delta1==delta2) { if (alea(0,1)==0) goto pt_1; else goto pt_2; } end_improve_2: if (trace>1) printf("\n3-opt_weak =>%f",pt.f); next_b_2:; } // next b if (pt.x.s[0]!=0) pt.x=rotate(pt.x,0); if(pt.f<pt.best_f) { pt.best_x=pt.x; pt.best_f=pt.f; pt.best_time=time; if (move[4]>=3) BB_update(pt); //
评论
    相关推荐
    • pso_C++.rar
      有关粒子群算法的求解tspc++程序。
    • PSO-TSP.rar
      在分析粒子群优化的搜索原理的基础上,通过引入交换子和交换序的概念,构造 一种特殊的粒子群优化算法,并用于求解旅行商问题。
    • pso_tsp_ansi_c.zip
      Particle Swarm Optimization (PSO) for the TSP
    • pso-tsp-parallel-by-tedade-tekrar.rar
      mpi.net sample of tsp problem using pso algorithm
    • tsp.rar
      tsp问题求解 基于蚁群算法 粒子群算法 结果收敛稳定
    • pso.zip
      this is a implementation for PSO Algorithm!
    • PSO_TSP-master C++.zip
      This code is written in C++, and this PSO method is written for solving TSP.
    • pso-tsp.zip
      采用PSO解决TSP问题,代码可以直接运行,无需其它数据输入。
    • vc.net TSP粒子群算法修正版(VS2008)
      内容索引:VC/C++源码,算法相关,粒子,算法 tsp 粒子群算法修正源码, 参考:大连理工大学 谷超 2009年硕士学位论文 “改进的ACO和PSO算法在TSP中的应用”  *郭文忠1,陈国龙1,洪玉玲2 .求解TSP问题的动态邻域粒子...
    • libiconv-1.1.tar.gz
      字符集转换程序