附录：代码
/****************************************/ /*********TSP write by LJ ******************/ /****************************************/ #include
#define maxpop 100 #define maxstring 29
struct individual {
unsigned int chrom[maxstring]; float x,fitness; int parent[2]; int xsite; };
struct individual *oldpop; /* 当前代种群 */ struct individual *newpop; /* 新一代种群 */ struct individual *temp,*p1;
unsigned int co_min,jrand;
unsigned int nmutation,ncross,jcross,maxpp,minpp,maxxy; float sumfitness,avg,max,min,seed,maxold,oldrand[maxstring]; unsigned char x[maxstring],y[maxstring]; float *dd,ff,maxdd,refpd,fm[201]; //以下为29个城市的边权值 /*
0 107 241 190 124 80 316 76 152 157 283 133 113 297 228 129 348 276 188 150 65 341 184 67 221 169 108 45 167
107 0 148 137 88 127 336 183 134 95 254 180 101 234 175 176 265 199 182 67 42 278 271 146 251 105 191 139 79 241 148 0 374 171 259 509 317 217 232 491 312 280 391 412 349 422 356 355 204 182 435 417 292 424 116 337 273 77 190 137 374 0 202 234 222 192 248 42 117 287 79 107 38 121 152 86 68 70 137 151 239 135 137 242 165 228 205 124 88 171 202 0 61 392 202 46 160 319 112 163 322 240 232 314 287 238 155 65 366 300 175 307 57 220 121 97 80 127 259 234 61 0 386 141 72 167 351 55 157 331 272 226 362 296 232 164 85 375 249 147 301 118 188 60 185 316 336 509 222 392 386 0 233 438 254 202 439 235 254 210 187 313 266 154 282 321 298 168 249 95 437 190 314 435 76 183 317 192 202 141 233 0 213 188 272 193 131 302 233 98 344 289 177 216 141 346 108 57 190 245 43 81 243 152 134 217 248 46 72 438 213 0 206 365 89 209 368 286 278 360 333 284 201 111 412 321 221 353 72 266 132 111
157 95 232 42 160 167 254 188 206 0 159 220 57 149 80 132 193 127 100 28 95 193 241 131 169 200 161 189 163 283 254 491 117 319 351 202 272 365 159 0 404 176 106 79 161 165 141 95 187 254 103 279 215 117 359 216 308 322 133 180 312 287 112 55 439 193 89 220 404 0 210 384 325 279 415 349 285 217 138 428 310 200 354 169 241 112 238 113 101 280 79 163 157 235 131 209 57 176 210 0 186 117 75 231 165 81 85 92 230 184 74 150 208 104 158 206 297 234 391 107 322 331 254 302 368 149 106 384 186 0 69 191 59 35 125 167 255 44 309 245 169 327 246 335 288 228 175 412 38 240 272 210 233 286 80 79 325 117 69 0 122 122 56 56 108 175 113 240 176 125 280 177 266 243 129 176 349 121 232 226 187 98 278 132 161 279 75 191 122 0 244 178 66 160 161 235 118 62 92 277 55 155 275 348 265 422 152 314 362 313 344 360 193 165 415 231 59 122 244 0 66 178 198 286 77 362 287 228 358 299 380 319 276 199 356 86 287 296 266 289 333 127 141 349 165 35 56 178 66 0 112 132 220 79 296 232 181 292 233 314 253 188 182 355 68 238 232 154 177 284 100 95 285 81 125 56 66 178 112 0 128 167 169 179 120 69 283 121 213 281 150 67 204 70 155 164 282 216 201 28 187 217 85 167 108 160 198 132 128 0 88 211 269 159 197 172 189 182 135 65 42 182 137 65 85 321 141 111 95 254 138 92 255 175 161 286 220 167 88 0 299 229 104 236 110 149 97 108 341 278 435 151 366 375 298 346 412 193 103 428 230 44 113 235 77 79 169 211 299 0 353 289 213 371 290 379 332 184 271 417 239 300 249 168 108 321 241 279 310 184 309 240 118 362 296 179 269 229 353 0 121 162 345 80 189 342 67 146 292 135 175 147 249 57 221 131 215 200 74 245 176 62 287 232 120 159 104 289 121 0 154 220 41 93 218 221 251 424 137 307 301 95 190 353 169 117 354 150 169 125 92 228 181 69 197 236 213 162 154 0 352 147 247 350 169 105 116 242 57 118 437 245 72 200 359 169 208 327 280 277 358 292 283 172 110 371 345 220 352 0 265 178 39 108 191 337 165 220 188 190 43 266 161 216 241 104 246 177 55 299 233 121 189 149 290 80 41 147 265 0 124 263 45 139 273 228 121 60 314 81 132 189 308 112 158 335 266 155 380 314 213 182 97 379 189 93 247 178 124 0 199 167 79 77 205 97 185 435 243 111 163 322 238 206 288 243 275 319 253 281 135 108 332 342 218 350 39 263 199 0
*/
static int matrix[maxstring][maxstring]={
{0,107,241,190,124,80,316,76,152,157,283,133,113,297,228,129,348,276,188,150,65,341,184,67,221,169,108,45,167} ,{107,0,148,137,88,127,336,183,134,95,254,180,101,234,175,176,265,199,182,67,42,278,271,146,251,105,191,139,79} ,{241,148,0,374,171,259,509,317,217,232,491,312,280,391,412,349,422,356,355,204,182,435,417,292,424,116,337,273,77} ,{190,137,374,0,202,234,222,192,248,42,117,287,79,107,38,121,152,86,68,70,137,151,239,135,137,242,165,228,205} ,{124,88,171,202,0,61,392,202,46,160,319,112,163,322,240,232,314,287,238,155,65,366,300,175,307,57,220,121,97} ,{80,127,259,234,61,0,386,141,72,167,351,55,157,331,272,226,362,296,232,164,85,375,249,147,301,118,188,60,185} ,{316,336,509,222,392,386,0,233,438,254,202,439,235,254,210,187,313,266,154,282,321,298,168,249,95,437,190,314,435} ,{76,183,317,192,202,141,233,0,213,188,272,193,131,302,233,98,344,289,177,216,141,346,108,57,190,245,43,81,243} ,{152,134,217,248,46,72,438,213,0,206,365,89,209,368,286,278,360,333,284,201,111,412,321,221,353,72,266,132,111} ,{157,95,232,42,160,167,254,188,206,0,159,220,57,149,80,132,193,127,100,28,95,193,241,131,169,200,161,189,163} ,{283,254,491,117,319,351,202,272,365,159,0,404,176,106,79,161,165,141,95,187,254,103,279,215,117,359,216,308,322} ,{133,180,312,287,112,55,439,193,89,220,404,0,210,384,325,279,415,349,285,217,138,428,310,200,354,169,241,112,238} ,{113,101,280,79,163,157,235,131,209,57,176,210,0,186,117,75,231,165,81,85,92,230,184,74,150,208,104,158,206} ,{297,234,391,107,322,331,254,302,368,149,106,384,186,0,69,191,59,35,125,167,255,44,309,245,169,327,246,335,288} ,{228,175,412,38,240,272,210,233,286,80,79,325,117,69,0,122,122,56,56,108,175,113,240,176,125,280,177,266,243} ,{129,176,349,121,232,226,187,98,278,132,161,279,75,191,122,0,244,178,66,160,161,235,118,62,92,277,55,155,275} ,{348,265,422,152,314,362,313,344,360,193,165,415,231,59,122,244,0,66,178,198,286,77,362,287,228,358,299,380,319} ,{276,199,356,86,287,296,266,289,333,127,141,349,165,35,56,178,66,0,112,132,220,79,296,232,181,292,233,314,253} ,{188,182,355,68,238,232,154,177,284,100,95,285,81,125,56,66,178,112,0,128,167,169,179,120,69,283,121,213,281} ,{150,67,204,70,155,164,282,216,201,28,187,217,85,167,108,160,198,132,128,0,88,211,269,159,197,172,189,182,135} ,{65,42,182,137,65,85,321,141,111,95,254,138,92,255,175,161,286,220,167,88,0,299,229,104,236,110,149,97,108}
,{341,278,435,151,366,375,298,346,412,193,103,428,230,44,113,235,77,79,169,211,299,0,353,289,213,371,290,379,332} ,{184,271,417,239,300,249,168,108,321,241,279,310,184,309,240,118,362,296,179,269,229,353,0,121,162,345,80,189,342} ,{67,146,292,135,175,147,249,57,221,131,215,200,74,245,176,62,287,232,120,159,104,289,121,0,154,220,41,93,218} ,{221,251,424,137,307,301,95,190,353,169,117,354,150,169,125,92,228,181,69,197,236,213,162,154,0,352,147,247,350} ,{169,105,116,242,57,118,437,245,72,200,359,169,208,327,280,277,358,292,283,172,110,371,345,220,352,0,265,178,39} ,{108,191,337,165,220,188,190,43,266,161,216,241,104,246,177,55,299,233,121,189,149,290,80,41,147,265,0,124,263} ,{45,139,273,228,121,60,314,81,132,189,308,112,158,335,266,155,380,314,213,182,97,379,189,93,247,178,124,0,199} ,{167,79,77,205,97,185,435,243,111,163,322,238,206,288,243,275,319,253,281,135,108,332,342,218,350,39,263,199,0}
};
float pcross; /* 交叉概率 */ float pmutation; /* 变异概率 */ int popsize; /* 种群大小 */ int lchrom; /* 染色体长度*/ int gen; /* 当前世代数 */ int maxgen; /* 最大世代数 */ int var_num; /*变量数目*/ int func_num; /*函数数目*/
struct individual *spop; int compare_count;
FILE *outfp,*outfp1,*outfp2; void init();
void initmalloc(); void initpop();
void initparameters();
void inversion(unsigned int,unsigned int, unsigned int *); float decode(unsigned int *); float objfunc(float); void generation(); int select();
void statistics(struct individual *);
int crossover(unsigned int [],unsigned int[],unsigned int[],unsigned int[]); void mutation(unsigned int [],float ); void report(int ,struct individual *);
void main() {
double start=clock(),end,time; init();
statistics(oldpop); gen=1;
outfp=fopen(\ outfp1=fopen(\
outfp2=fopen(\
for (gen=1;gen<=maxgen;gen++) { printf(\ compare_count=%d\\n\ generation(); statistics(oldpop); report(gen,oldpop); }
fprintf(outfp2,\ end=clock();
time=(end-start)/CLOCKS_PER_SEC; fprintf(outfp1,\}
void climb(unsigned int a[]) {
int i1,i2,j,k,j2;
j2=rand()%(2*lchrom/3); float x,y;
for(j=j2;j
inversion(i1,i2,a); //i1,i2为前后的两个逆转点 y=decode(a);
if(y>x) inversion(i1,i2,a); //如果逆转后路经长度增长，则再次逆转
//一次恢复到以前的状态。
}
}
void init() {
initparameters(); initmalloc(); initpop(); }
void initparameters() {
maxgen=200; popsize=100;
lchrom=maxstring; pcross=0.9;
pmutation=1.0/(lchrom); nmutation=0; ncross=0; }
void initmalloc() {
oldpop=new individual[popsize]; newpop=new individual[popsize]; temp=new individual[popsize]; }
void initpop() {
srand((unsigned)time(NULL)); //初始化随机数 unsigned int temp;
unsigned int j,i,k,j2,j3,j4;
unsigned int p5[maxstring]; //临时待排列数组 float f1,f2; j=0;
for(k=0;k