1

嗨，我正在尝试编写一些简单的代码来使用随机突变爬山来解决旅行商问题。我已经创建了一个 Tour 类：-

import java.util.ArrayList;
import java.util.Collections;

public class Tour 
{
    private ArrayList<Integer> tour;

    // Specified tour
    public Tour(ArrayList<Integer> tour) { this.tour = tour; }

    // Random tour
    public Tour(int size) 
    {
        // Initalize tour with size
        tour = new ArrayList<Integer>(size);
        // Add integers up to size into ArrayList
        for (int i=0; i<size; ++i) {tour.add(i);}
        // Shuffle ArrayList
        Collections.shuffle(tour);
    }

    ArrayList<Integer> getTour() {return tour;}

    void printTour()
    {
        for (int i=0; i<tour.size(); ++i)
        {
            System.out.print(tour.get(i) + ", ");
        }
    }

    // Get the distance between all tour stops using a set of distances
    double getFitness (double[][] distances)
    {
        double s = 0;
        for (int i=0; i<tour.size()-1; ++i)
        {
            int a = tour.get(i);
            int b = tour.get(i+1);
            s += distances[a][b];
        }
        int start_city = tour.get(0);
        int end_city = tour.get(tour.size()-1);
        s += distances[end_city][start_city];
        return s;
    }

    // Makes a small change to the tour
    void smallChange()
    {
        // Change random index values to swap
        int indexfirst = CS2004.UI(0, tour.size()-1);
        int indexsecond = CS2004.UI(0, tour.size()-1);

        // Checks to make sure index values are not the same
        while (indexsecond == indexfirst)
        {
            indexsecond = CS2004.UI(0, tour.size()-1);
        }

        // Store city value in temp variable
        int indexTemp = tour.get(indexfirst);

        // Swap values
        tour.set(indexfirst, tour.get(indexsecond));
        tour.set(indexsecond, indexTemp);
    }

}

我的 RMHC 方法如下所示：-

public static Tour RMHC(double[][] distances, int iter)
{
    Tour sol = new Tour(distances.length);
    double oldFitness;
    double fitness = 0;
    Tour oldSol=null;

    for (int i=0;i<iter;i++)
    {
        oldSol = null;
        // Make old solution equal to solution before change
        oldSol = new Tour(sol.getTour());

        System.out.println(oldSol.getTour());
        // Calculate old fitness for comparison
        oldFitness = sol.getFitness(distances); 

        // Change solution slightly
        sol.smallChange();

        // Calculate new fitness
        fitness = sol.getFitness(distances);

        /* Compare new fitness to old fitness 
         * set solution back to old solution and fitness to old fitness if 
         * new solution is not better */
        System.out.println(oldFitness + " " + fitness);
        if (fitness > oldFitness) {System.out.println(oldSol.getTour()); System.out.println(sol.getTour()); sol = null; sol = new Tour(oldSol.getTour()); fitness = oldFitness;}

        // Print iteration number and new fitness
        System.out.println("Iteration " + (i+1) + ", fitness: " + sol.getFitness(distances));
    }
    return(sol);
}

我遇到的问题是，当我在 RMHC 中调用我的 smallChange 方法时，它似乎改变了旧解决方案和新解决方案的 Tour。我在一个 48 大小的数据集上运行了几次迭代，得到了以下输出：-

[11, 6, 13, 37, 23, 45, 34, 25, 16, 39, 5, 35, 31, 9, 27, 0, 10, 42, 30, 28, 4, 12, 33, 36, 2, 21, 17, 29, 18, 20, 32, 3, 15, 47, 26, 19, 46, 8, 22, 44, 7, 24, 43, 14, 41, 1, 38, 40]
155843.9387676824 159088.1701641078
[31, 6, 13, 37, 23, 45, 34, 25, 16, 39, 5, 35, 11, 9, 27, 0, 10, 42, 30, 28, 4, 12, 33, 36, 2, 21, 17, 29, 18, 20, 32, 3, 15, 47, 26, 19, 46, 8, 22, 44, 7, 24, 43, 14, 41, 1, 38, 40]
[31, 6, 13, 37, 23, 45, 34, 25, 16, 39, 5, 35, 11, 9, 27, 0, 10, 42, 30, 28, 4, 12, 33, 36, 2, 21, 17, 29, 18, 20, 32, 3, 15, 47, 26, 19, 46, 8, 22, 44, 7, 24, 43, 14, 41, 1, 38, 40]
Iteration 1, fitness: 159088.1701641078
[31, 6, 13, 37, 23, 45, 34, 25, 16, 39, 5, 35, 11, 9, 27, 0, 10, 42, 30, 28, 4, 12, 33, 36, 2, 21, 17, 29, 18, 20, 32, 3, 15, 47, 26, 19, 46, 8, 22, 44, 7, 24, 43, 14, 41, 1, 38, 40]
159088.1701641078 144709.1336957683
Iteration 2, fitness: 144709.1336957683
[31, 6, 13, 37, 7, 45, 34, 25, 16, 39, 5, 35, 11, 9, 27, 0, 10, 42, 30, 28, 4, 12, 33, 36, 2, 21, 17, 29, 18, 20, 32, 3, 15, 47, 26, 19, 46, 8, 22, 44, 23, 24, 43, 14, 41, 1, 38, 40]
144709.1336957683 143387.5110957744
Iteration 3, fitness: 143387.5110957744
[31, 6, 13, 37, 7, 45, 22, 25, 16, 39, 5, 35, 11, 9, 27, 0, 10, 42, 30, 28, 4, 12, 33, 36, 2, 21, 17, 29, 18, 20, 32, 3, 15, 47, 26, 19, 46, 8, 34, 44, 23, 24, 43, 14, 41, 1, 38, 40]
143387.5110957744 143565.3842060348
[31, 6, 13, 37, 7, 45, 22, 25, 16, 39, 5, 35, 14, 9, 27, 0, 10, 42, 30, 28, 4, 12, 33, 36, 2, 21, 17, 29, 18, 20, 32, 3, 15, 47, 26, 19, 46, 8, 34, 44, 23, 24, 43, 11, 41, 1, 38, 40]
[31, 6, 13, 37, 7, 45, 22, 25, 16, 39, 5, 35, 14, 9, 27, 0, 10, 42, 30, 28, 4, 12, 33, 36, 2, 21, 17, 29, 18, 20, 32, 3, 15, 47, 26, 19, 46, 8, 34, 44, 23, 24, 43, 11, 41, 1, 38, 40]
4

0 回答 0