ls.c

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

            if (pos_c1 > 0)
                p_c1 = tour[pos_c1-1];
            else
                p_c1 = tour[n-1];

            h = 0;    /* Search for one of the h-nearest neighbours */
            while ( h < nn_ls )
            {

                c2   = instance.nn_list[c1][h];  /* second city, determine its position */
                pos_c2 = pos[c2];
                s_c2 = tour[pos_c2+1];
                if (pos_c2 > 0)
                    p_c2 = tour[pos_c2-1];
                else
                    p_c2 = tour[n-1];

                diffs = 0;
                diffp = 0;

                radius = instance.distance[c1][s_c1];
                add1   = instance.distance[c1][c2];

                /* Here a fixed radius neighbour search is performed */
                if ( radius > add1 )
                {
                    decrease_breaks = - radius - instance.distance[c2][s_c2];
                    diffs =  decrease_breaks + add1 + instance.distance[s_c1][s_c2];
                    diffp =  - radius - instance.distance[c2][p_c2] +
                             instance.distance[c1][p_c2] + instance.distance[s_c1][c2];
                }
                else
                    break;
                if ( p_c2 == c1 )  /* in case p_c2 == c1 no exchange is possible */
                    diffp = 0;
                if ( (diffs < move_value) || (diffp < move_value) )
                {
                    improvement_flag = TRUE;
                    if (diffs <= diffp)
                    {
                        h1 = c1;
                        h2 = s_c1;
                        h3 = c2;
                        h4 = s_c2;
                        move_value = diffs;
                        opt2_flag = TRUE;
                        move_flag = 0;
                        /*     	    goto exchange; */
                    }
                    else
                    {
                        h1 = c1;
                        h2 = s_c1;
                        h3 = p_c2;
                        h4 = c2;
                        move_value = diffp;
                        opt2_flag = TRUE;
                        move_flag = 0;
                        /*     	    goto exchange; */
                    }
                }
                /* Now perform the innermost search */
                g = 0;
                while (g < nn_ls)
                {

                    c3   = instance.nn_list[s_c1][g];
                    pos_c3 = pos[c3];
                    s_c3 = tour[pos_c3+1];
                    if (pos_c3 > 0)
                        p_c3 = tour[pos_c3-1];
                    else
                        p_c3 = tour[n-1];

                    if ( c3 == c1 )
                    {
                        g++;
                        continue;
                    }
                    else
                    {
                        add2 = instance.distance[s_c1][c3];
                        /* Perform fixed radius neighbour search for innermost search */
                        if ( decrease_breaks + add1 < add2 )
                        {

                            if ( pos_c2 > pos_c1 )
                            {
                                if ( pos_c3 <= pos_c2 && pos_c3 > pos_c1 )
                                    between = TRUE;
                                else
                                    between = FALSE;
                            }
                            else if ( pos_c2 < pos_c1 )
                                if ( pos_c3 > pos_c1 || pos_c3 < pos_c2 )
                                    between = TRUE;
                                else
                                    between = FALSE;
                            else
                            {
                                printf(" Strange !!, pos_1 %ld == pos_2 %ld, \n",pos_c1,pos_c2);
                            }

                            if ( between )
                            {
                                /* We have to add edges (c1,c2), (c3,s_c1), (p_c3,s_c2) to get
                                   valid tour; it's the only possibility */

                                gain = decrease_breaks - instance.distance[c3][p_c3] +
                                       add1 + add2 +
                                       instance.distance[p_c3][s_c2];

                                /* check for improvement by move */
                                if ( gain < move_value )
                                {
                                    improvement_flag = TRUE; /* g = neigh_ls + 1; */
                                    move_value = gain;
                                    opt2_flag = FALSE;
                                    move_flag = 1;
                                    /* store nodes involved in move */
                                    h1 = c1;
                                    h2 = s_c1;
                                    h3 = c2;
                                    h4 = s_c2;
                                    h5 = p_c3;
                                    h6 = c3;
                                    goto exchange;
                                }
                            }
                            else     /* not between(pos_c1,pos_c2,pos_c3) */
                            {

                                /* We have to add edges (c1,c2), (s_c1,c3), (s_c2,s_c3) */

                                gain = decrease_breaks - instance.distance[c3][s_c3] +
                                       add1 + add2 +
                                       instance.distance[s_c2][s_c3];

                                if ( pos_c2 == pos_c3 )
                                {
                                    gain = 20000;
                                }

                                /* check for improvement by move */
                                if ( gain < move_value )
                                {
                                    improvement_flag = TRUE; /* g = neigh_ls + 1; */
                                    move_value = gain;
                                    opt2_flag = FALSE;
                                    move_flag = 2;
                                    /* store nodes involved in move */
                                    h1 = c1;
                                    h2 = s_c1;
                                    h3 = c2;
                                    h4 = s_c2;
                                    h5 = c3;
                                    h6 = s_c3;
                                    goto exchange;
                                }

                                /* or add edges (c1,c2), (s_c1,c3), (p_c2,p_c3) */
                                gain = - radius - instance.distance[p_c2][c2]
                                       - instance.distance[p_c3][c3] +
                                       add1 + add2 +
                                       instance.distance[p_c2][p_c3];

                                if ( c3 == c2 || c2 == c1 || c1 == c3 || p_c2 == c1 )
                                {
                                    gain = 2000000;
                                }

                                if ( gain < move_value )
                                {
                                    improvement_flag = TRUE;
                                    move_value = gain;
                                    opt2_flag = FALSE;
                                    move_flag = 3;
                                    h1 = c1;
                                    h2 = s_c1;
                                    h3 = p_c2;
                                    h4 = c2;
                                    h5 = p_c3;
                                    h6 = c3;
                                    goto exchange;
                                }

                                /* Or perform the 3-opt move where no subtour inversion is necessary
                                   i.e. delete edges (c1,s_c1), (c2,p_c2), (c3,s_c3) and
                                   add edges (c1,c2), (c3,s_c1), (p_c2,s_c3) */

                                gain = - radius - instance.distance[p_c2][c2] -
                                       instance.distance[c3][s_c3]
                                       + add1 + add2 + instance.distance[p_c2][s_c3];

                                /* check for improvement */
                                if ( gain < move_value )
                                {
                                    improvement_flag = TRUE;
                                    move_value = gain;
                                    opt2_flag = FALSE;
                                    move_flag = 4;
                                    improvement_flag = TRUE;
                                    /* store nodes involved in move */
                                    h1 = c1;
                                    h2 = s_c1;
                                    h3 = p_c2;
                                    h4 = c2;
                                    h5 = c3;
                                    h6 = s_c3;
                                    goto exchange;
                                }
                            }
                        }
                        else
                            g = nn_ls + 1;
                    }
                    g++;
                }
                h++;
            }
            if ( move_flag || opt2_flag )
            {
exchange:
                move_value = 0;

                /* Now make the exchange */
                if ( move_flag )
                {
                    dlb[h1] = FALSE;
                    dlb[h2] = FALSE;
                    dlb[h3] = FALSE;
                    dlb[h4] = FALSE;
                    dlb[h5] = FALSE;
                    dlb[h6] = FALSE;
                    pos_c1 = pos[h1];
                    pos_c2 = pos[h3];
                    pos_c3 = pos[h5];

                    if ( move_flag == 4 )
                    {

                        if ( pos_c2 > pos_c1 )
                            n1 = pos_c2 - pos_c1;
                        else
                            n1 = n - (pos_c1 - pos_c2);
                        if ( pos_c3 > pos_c2 )
                            n2 = pos_c3 - pos_c2;
                        else
                            n2 = n - (pos_c2 - pos_c3);
                        if ( pos_c1 > pos_c3 )
                            n3 = pos_c1 - pos_c3;
                        else
                            n3 = n - (pos_c3 - pos_c1);

                        /* n1: length h2 - h3, n2: length h4 - h5, n3: length h6 - h1 */
                        val[0] = n1;
                        val[1] = n2;
                        val[2] = n3;
                        /* Now order the partial tours */
                        h = 0;
                        help = LONG_MIN;
                        for ( g = 0; g <= 2; g++)
                        {
                            if ( help < val[g] )
                            {
                                help = val[g];
                                h = g;
                            }
                        }

                        /* order partial tours according length */
                        if ( h == 0 )
                        {
                            /* copy part from pos[h4] to pos[h5]
                               direkt kopiert: Teil von pos[h6] to pos[h1], it
                               remains the part from pos[h2] to pos[h3] */
                            j = pos[h4];
                            h = pos[h5];
                            i = 0;
                            h_tour[i] = tour[j];
                            n1 = 1;
                            while ( j != h)
                            {
                                i++;
                                j++;
                                if ( j  >= n )
                                    j = 0;
                                h_tour[i] = tour[j];
                                n1++;
                            }

                            /* First copy partial tour 3 in new position */
                            j = pos[h4];
                            i = pos[h6];
                            tour[j] = tour[i];
                            pos[tour[i]] = j;
                            while ( i != pos_c1)
                            {
                                i++;
                                if ( i >= n )
                                    i = 0;
                                j++;
                                if ( j >= n )
                                    j = 0;
                                tour[j] = tour[i];
                                pos[tour[i]] = j;
                            }

                            /* Now copy stored part from h_tour */
                            j++;
                            if ( j >= n )
                                j = 0;
                            for ( i = 0; i<n1 ; i++ )
                            {
                                tour[j] = h_tour[i];
                                pos[h_tour[i]] = j;
                                j++;
                                if ( j >= n )
                                    j = 0;
                            }
                            tour[n] = tour[0];
                        }
                        else if ( h == 1 )
                        {

                            /* copy part from pos[h6] to pos[h1]
                               direkt kopiert: Teil von pos[h2] to pos[h3], it
                               remains the part from pos[h4] to pos[h5] */
                            j = pos[h6];
                            h = pos[h1];
                            i = 0;
                            h_tour[i] = tour[j];
                            n1 = 1;
                            while ( j != h)
                            {
                                i++;
                                j++;
                                if ( j  >= n )