ls.c

ACO解决TSP问题(蚁群优化)源码!!!

    while ( improvement_flag )
    {

        improvement_flag = FALSE;
        two_move = FALSE;
        node_move = FALSE;

        for (l = 0 ; l < n; l++)
        {

            c1 = random_vector[l];
            DEBUG ( assert ( c1 < n && c1 >= 0); )
            if ( dlb_flag && dlb[c1] )
                continue;
            improve_node = FALSE;
            pos_c1 = pos[c1];
            s_c1 = tour[pos_c1+1];
            radius = instance.distance[c1][s_c1];

            /* First search for c1's nearest neighbours, use successor of c1 */
            for ( h = 0 ; h < nn_ls ; h++ )
            {
                c2 = instance.nn_list[c1][h]; /* exchange partner, determine its position */
                if ( radius > instance.distance[c1][c2] )
                {
                    pos_c2 = pos[c2];
                    s_c2 = tour[pos_c2+1];
                    gain =  - radius + instance.distance[c1][c2] +
                            instance.distance[s_c1][s_c2] - instance.distance[c2][s_c2];
                    if ( gain < 0 )
                    {
                        h1 = c1;
                        h2 = s_c1;
                        h3 = c2;
                        h4 = s_c2;
                        improve_node = TRUE;
                        two_move = TRUE;
                        node_move = FALSE;
                        goto exchange;
                    }
                    if (pos_c2 > 0)
                        p_c2 = tour[pos_c2-1];
                    else
                        p_c2 = tour[n-1];
                    gain = - radius + instance.distance[c1][c2] + instance.distance[c2][s_c1]
                           + instance.distance[p_c2][s_c2] - instance.distance[c2][s_c2]
                           - instance.distance[p_c2][c2];
                    if ( c2 == s_c1 )
                        gain = 0;
                    if ( p_c2 == s_c1 )
                        gain = 0;

                    gain = 0;

                    if ( gain < 0 )
                    {
                        h1 = c1;
                        h2 = s_c1;
                        h3 = c2;
                        h4 = p_c2;
                        h5 = s_c2;
                        improve_node = TRUE;
                        node_move = TRUE;
                        two_move = FALSE;
                        goto exchange;
                    }
                }
                else
                    break;
            }
            /* Second search for c1's nearest neighbours, use predecessor c1 */
            if (pos_c1 > 0)
                p_c1 = tour[pos_c1-1];
            else
                p_c1 = tour[n-1];
            radius = instance.distance[p_c1][c1];
            for ( h = 0 ; h < nn_ls ; h++ )
            {
                c2 = instance.nn_list[c1][h];  /* exchange partner, determine its position */
                if ( radius > instance.distance[c1][c2] )
                {
                    pos_c2 = pos[c2];
                    if (pos_c2 > 0)
                        p_c2 = tour[pos_c2-1];
                    else
                        p_c2 = tour[n-1];
                    if ( p_c2 == c1 )
                        continue;
                    if ( p_c1 == c2 )
                        continue;
                    gain =  - radius + instance.distance[c1][c2] +
                            instance.distance[p_c1][p_c2] - instance.distance[p_c2][c2];
                    if ( gain < 0 )
                    {
                        h1 = p_c1;
                        h2 = c1;
                        h3 = p_c2;
                        h4 = c2;
                        improve_node = TRUE;
                        two_move = TRUE;
                        node_move = FALSE;
                        goto exchange;
                    }
                    s_c2 = tour[pos[c2]+1];
                    gain = - radius + instance.distance[c2][c1] + instance.distance[p_c1][c2]
                           + instance.distance[p_c2][s_c2] - instance.distance[c2][s_c2]
                           - instance.distance[p_c2][c2];
                    if ( p_c1 == c2 )
                        gain = 0;
                    if ( p_c1 == s_c2 )
                        gain = 0;

                    if ( gain < 0 )
                    {
                        h1 = p_c1;
                        h2 = c1;
                        h3 = c2;
                        h4 = p_c2;
                        h5 = s_c2;
                        improve_node = TRUE;
                        node_move = TRUE;
                        two_move = FALSE;
                        goto exchange;
                    }
                }
                else
                    break;
            }
exchange:
            if (improve_node)
            {
                if ( two_move )
                {
                    improvement_flag = TRUE;
                    dlb[h1] = FALSE;
                    dlb[h2] = FALSE;
                    dlb[h3] = FALSE;
                    dlb[h4] = FALSE;
                    /* Now perform move */
                    if ( pos[h3] < pos[h1] )
                    {
                        help = h1;
                        h1 = h3;
                        h3 = help;
                        help = h2;
                        h2 = h4;
                        h4 = help;
                    }
                    if ( pos[h3] - pos[h2] < n / 2 + 1)
                    {
                        /* reverse inner part from pos[h2] to pos[h3] */
                        i = pos[h2];
                        j = pos[h3];
                        while (i < j)
                        {
                            c1 = tour[i];
                            c2 = tour[j];
                            tour[i] = c2;
                            tour[j] = c1;
                            pos[c1] = j;
                            pos[c2] = i;
                            i++;
                            j--;
                        }
                    }
                    else
                    {
                        /* reverse outer part from pos[h4] to pos[h1] */
                        i = pos[h1];
                        j = pos[h4];
                        if ( j > i )
                            help = n - (j - i) + 1;
                        else
                            help = (i - j) + 1;
                        help = help / 2;
                        for ( h = 0 ; h < help ; h++ )
                        {
                            c1 = tour[i];
                            c2 = tour[j];
                            tour[i] = c2;
                            tour[j] = c1;
                            pos[c1] = j;
                            pos[c2] = i;
                            i--;
                            j++;
                            if ( i < 0 )
                                i = n-1;
                            if ( j >= n )
                                j = 0;
                        }
                        tour[n] = tour[0];
                    }
                }
                else if ( node_move )
                {
                    improvement_flag = TRUE;
                    dlb[h1] = FALSE;
                    dlb[h2] = FALSE;
                    dlb[h3] = FALSE;
                    dlb[h4] = FALSE;
                    dlb[h5] = FALSE;
                    /* Now perform move */
                    if ( pos[h3] < pos[h1] )
                    {
                        help = pos[h1] - pos[h3];
                        i = pos[h3];
                        for ( h = 0 ; h < help ; h++ )
                        {
                            c1 = tour[i+1];
                            tour[i] = c1;
                            pos[c1] = i;
                            i++;
                        }
                        tour[i] = h3;
                        pos[h3] = i;
                        tour[n] = tour[0];
                    }
                    else
                    {
                        /* pos[h3] > pos[h1] */
                        help = pos[h3] - pos[h1];
                        /*  	    if ( help < n / 2 + 1) { */
                        i = pos[h3];
                        for ( h = 0 ; h < help - 1 ; h++ )
                        {
                            c1 = tour[i-1];
                            tour[i] = c1;
                            pos[c1] = i;
                            i--;
                        }
                        tour[i] = h3;
                        pos[h3] = i;
                        tour[n] = tour[0];
                        /*  	  } */
                    }
                }
                else
                {
                    fprintf(stderr,"this should never occur, 2-h-opt!!\n");
                    exit(0);
                }
                two_move = FALSE;
                node_move = FALSE;
            }
            else
            {
                dlb[c1] = TRUE;
            }

        }
    }
    free( random_vector );
    free( dlb );
    free( pos );
}

void three_opt_first( long int *tour )

/*
      FUNCTION:       3-opt the tour
      INPUT:          pointer to the tour that is to optimize
      OUTPUT:         none
      (SIDE)EFFECTS:  tour is 3-opt
      COMMENT:        this is certainly not the best possible implementation of a 3-opt
                      local search algorithm. In addition, it is very lengthy; the main
		      reason herefore is that awkward way of making an exchange, where
		      it is tried to copy only the shortest possible part of a tour.
		      Whoever improves the code regarding speed or solution quality, please
		      drop me the code at stuetzle no@spam informatik.tu-darmstadt.de
		      The neighbourhood is scanned in random order (this need
                      not be the best possible choice). Concerning the speed-ups used
		      here consult, for example, Chapter 8 of
		      Holger H. Hoos and Thomas Stuetzle,
		      Stochastic Local Search---Foundations and Applications,
		      Morgan Kaufmann Publishers, 2004.
		      or some of the papers online available from David S. Johnson.
*/
{
    /* In case a 2-opt move should be performed, we only need to store opt2_move = TRUE,
       as h1, .. h4 are used in such a way that they store the indices of the correct move */

    long int   c1, c2, c3;           /* cities considered for an exchange */
    long int   s_c1, s_c2, s_c3;     /* successors of these cities        */
    long int   p_c1, p_c2, p_c3;     /* predecessors of these cities      */
    long int   pos_c1, pos_c2, pos_c3;     /* positions of cities c1, c2, c3    */
    long int   i, j, h, g, l;
    long int   improvement_flag, help;
    long int   h1=0, h2=0, h3=0, h4=0, h5=0, h6=0; /* memorize cities involved in a move */
    long int   diffs, diffp;
    long int   between = FALSE;
    long int   opt2_flag;  /* = TRUE: perform 2-opt move, otherwise none or 3-opt move */
    long int   move_flag;  /*
			      move_flag = 0 --> no 3-opt move
			      move_flag = 1 --> between_move (c3 between c1 and c2)
			      move_flag = 2 --> not_between with successors of c2 and c3
			      move_flag = 3 --> not_between with predecessors of c2 and c3
			      move_flag = 4 --> cyclic move
			   */
    long int gain, move_value, radius, add1, add2;
    long int decrease_breaks;    /* Stores decrease by breaking two edges (a,b) (c,d) */
    long int val[3];
    long int n1, n2, n3;
    long int *pos;               /* positions of cities in tour */
    long int *dlb;               /* vector containing don't look bits */
    long int *h_tour;            /* help vector for performing exchange move */
    long int *hh_tour;           /* help vector for performing exchange move */
    long int *random_vector;

    pos = malloc(n * sizeof(long int));
    dlb = malloc(n * sizeof(long int));
    h_tour = malloc(n * sizeof(long int));
    hh_tour = malloc(n * sizeof(long int));

    for ( i = 0 ; i < n ; i++ )
    {
        pos[tour[i]] = i;
        dlb[i] = FALSE;
    }
    improvement_flag = TRUE;
    random_vector = generate_random_permutation( n );

    while ( improvement_flag )
    {
        move_value = 0;
        improvement_flag = FALSE;

        for ( l = 0 ; l < n ; l++ )
        {

            c1 = random_vector[l];
            if ( dlb_flag && dlb[c1] )
                continue;
            opt2_flag = FALSE;

            move_flag = 0;
            pos_c1 = pos[c1];
            s_c1 = tour[pos_c1+1];