MMAS.rar_eil76.tsp_mmas_改进蚁群_最大最小蚁群

/*MAX-MIN Ant System*/ #include <iostream> #include <time.h> #include <math.h> using namespace std; /*number of cities*/ #define n 51 /*number of iterations*/ #define NC 5000 /*number of ants*/ #define m 51 /*times of runs*/ #define times 100 /*parameters*/ double alpha = 1.0; double beta = 3.5; double rho = 0.1; double Q = 1.0; /*length computed by greedy algorithm*/ /*for oliver30: 480 for eil51: 569 for eil76: 693 for eil101: 844*/ #define greedy_length 569 double trail_max = 1.0 / (rho * greedy_length); double trail_min = trail_max / (2.0 * n); double trail0 = trail_max; /*city map*/ int city[n][2]; /*distance between cities*/ int dis[n][n]; /*pheromone level of each edge*/ double trail[n][n]; double dtrail[n][n]; /*tour of each ant*/ int tour[m][n]; /*allowed cities for each ant to visit*/ bool allow_city[m][n]; /*start city of each ant*/ int start_city[m]; /*current city of each ant*/ int r[m]; /*next city of each ant*/ int s[m]; /*city counter of each ant*/ int city_count[m]; /*globally best length*/ long global_best; long restart_best; long ilength[times][NC]; double alength[NC]; int restart, foundbest; /*add a city into a tour*/ void add_city(int k, int t) { tour[k][city_count[k]++] = t; allow_city[k][t] = false; } /*initialization phase*/ void initialize() { int i, j, k; /*set the initial pheromone level of each edge*/ for(i = 0; i < n; i++) { for(j = 0; j < n; j++) { trail[i][j] = trail0; dtrail[i][j] = 0; } } /*set the intitial information of each ant*/ for(k = 0; k < m; k++) { city_count[k] = 0; start_city[k] = 0; r[k] = 0; s[k] = 0; for(i = 0; i < n; i++) { allow_city[k][i] = true; tour[k][i] = 0; } start_city[k] = rand() % n; r[k] = start_city[k]; add_city(k,start_city[k]); } /*set the initial value of the global best tour's length*/ global_best = LONG_MAX; } /*compute the length of tour*/ long compute_length(int k) { int i; long temp = 0; for(i = 0; i < n-1; i++) { temp += dis[tour[k][i]][tour[k][i+1]]; } temp += dis[tour[k][i]][tour[k][0]]; return temp; } /*pheromone update*/ void pheromone_update(int t, int nc) { int i, j, k; int ibest; long ishort = LONG_MAX; double p_x; for(k = 0; k < m; k++) { if(compute_length(k) < ishort) { ishort = compute_length(k); ibest = k; } } if (compute_length(ibest) < global_best) { global_best = compute_length(ibest); restart = nc; p_x = exp(log(0.05)/n); trail_min = 1.0 * (1.0 - p_x) / (p_x * (double)((m + 1) / 2)); trail_max = 1.0 / (rho * global_best); trail_min = trail_max * trail_min; } for(i = 0; i < n-1; i++) { dtrail[tour[ibest][i]][tour[ibest][i+1]] += Q / (double)compute_length(ibest); dtrail[tour[ibest][i+1]][tour[ibest][i]] = dtrail[tour[ibest][i]][tour[ibest][i+1]]; } dtrail[tour[ibest][i]][tour[ibest][0]] += Q / (double)compute_length(ibest); dtrail[tour[ibest][0]][tour[ibest][i]] = dtrail[tour[ibest][i]][tour[ibest][0]]; for(i = 0; i < n; i++) { for(j = 0; j < n; j++) { trail[i][j] = (1 - rho) * trail[i][j] + dtrail[i][j]; dtrail[i][j] = 0; if(trail[i][j] < trail_min) trail[i][j] = trail_min; else if(trail[i][j] > trail_max) trail[i][j] = trail_max; } } if((nc - restart) > 250) { // restart_best = LONG_MAX; restart = nc; for(i = 0; i < n; i++) { for(j = 0; j < n; j++) { trail[i][j] = trail_max; } } } printf("%d %d\n", nc, global_best); ilength[t][nc] = global_best; } /*choose next city to move to*/ void move(int k) { int i, best; double sum = 0; double max = -1; double temp = 0; /*pseudo-random-proportional rule*/ for(i = 0; i < n; i++) { if(allow_city[k][i]) { temp = pow(trail[r[k]][i], alpha) * pow((1.0 / (double)dis[r[k]][i]), beta); sum += temp; if(temp > max) { max = temp; best = i; } } } if(sum <= 0) s[k] = best; else { double p = (double)rand() / (double)RAND_MAX; temp = 0; for(i = 0; i < n; i++) { if(allow_city[k][i]) { temp += pow(trail[r[k]][i], alpha) * pow((1.0 / (double)dis[r[k]][i]), beta); if(p <= (temp / sum)) { s[k] = i; break; } } } } add_city(k,s[k]); } /*each ant builds a tour*/ void build_tour() { int i, k; for(i = 0; i < n; i++) { if(i < n-1) { for(k = 0; k < m; k++) { move(k); } } else { for(k = 0; k < m; k++) { s[k] = start_city[k]; } } for(k = 0; k < m; k++) { r[k] = s[k]; } } } /*clear the information left in the last iteration*/ void clear(int k) { int i; for(i = 0; i < n; i++) { allow_city[k][i] = true; } allow_city[k][start_city[k]] = false; city_count[k] = 1; } int main() { int i, j, k, nc, temp; /*open the file and scan the map of cities*/ freopen("eil51.tsp", "r", stdin); for(i = 0; i < n; i++) scanf ("%d %d %d", &temp, &city[i][0], &city[i][1]); for(i = 0; i < n; i++) { for(j = 0; j < i; j++) { dis[i][j] = dis[j][i] = sqrt(pow((city[i][0] - city[j][0]), 2) + pow((city[i][1] - city[j][1]), 2)) + 0.5; } } for(i = 0; i < times; i++) { for(j = 0; j < NC; j++) { ilength[i][j] = 426; alength[j] = 0; } } FILE * out; out = fopen("MMAS_eil51.txt", "a"); srand((unsigned) time(NULL)); for(i = 0; i < times; i++) { nc = 0; initialize(); /*iterations*/ while(nc < NC) { build_tour(); pheromone_update(i, nc); for(k = 0; k < m; k++) { clear(k); } /*print the number of iteration in which the optimum tour found*/ if(global_best == 426) { printf("%d ", nc); fprintf(out, "%d ", nc); break; } nc++; } printf("%d \n", global_best); fprintf(out, "%d \n", global_best); } for(i = 0; i < NC; i++) { for(j = 0; j < times; j++) { alength[i] += ilength[j][i]; } } for(i = 0; i < NC; i++) { alength[i] = (double) alength[i] / (double) times; // printf("%f \n", alength[i]); fprintf(out, "%f \n", alength[i]); } return 0; }