非对称TSP问题的禁忌搜索算法求解的Java实现一. 非对称TSP问题：二. 禁忌搜索算法：三. 编程实现 四. 后记

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
public class Ts {
    private int A, f;                       //历史最优A，当前目标函数值f
    private int gen, T_size, cnum;          // 迭代次数gen，禁忌表长度T_size，城市数量cnum
    private ArrayList<MoveNeigbor> tab = new ArrayList<>();             // tab是邻域表，用顺序表实现
    private LimitedQueue<MoveNeigbor> T;     // T是禁忌表，用固定长度队列实现
    private Route s_;                        //最优路径s_
    private Route s;                         //当前路径s
    private String csvPath = "/Users/Henry/Desktop/task/data/data.csv";
    private int[][] dis= new int[this.cnum][this.cnum];
    // 迭代求解
    public void iterate(){
        initial();
        // 获取所有可行的邻域移动方式
        getTab();
        for (int i = 0; i < this.gen; i++) {
            // 第一步先排序
            this.tab.sort(new Comparator<MoveNeigbor>() {
                // 重写比较器的比较方法
                @Override
                public int compare(MoveNeigbor o1, MoveNeigbor o2) {
                    return get_f(o1) - get_f(o2);
                }
            });
            // 第二步循环，从头到尾看tab中的邻域移动方式是否在禁忌表中，
            // 若该移动方式在禁忌表中，则判断该方式是否能打破禁忌（f > A）,
            // 若能打破禁忌，则取该种方式；若无法打破禁忌，则继续搜索，直到
            // 搜索到不在禁忌表中的移动方式或是能够打破禁忌的移动方式,采取
            // 该方式，break停止循环，并更新T（禁忌表）以及f（当前最优）。
            for (MoveNeigbor moveNeigbor : this.tab) {
                if (this.T.contains(moveNeigbor)) {
                    if (get_f(moveNeigbor) < this.A) {               
                        this.s.makeAMove(moveNeigbor);
                        // this.T.add(moveNeigbor);
                        this.f = get_f(moveNeigbor);
                        break;
                    }
                } else {
                    this.s.makeAMove(moveNeigbor);
                    this.T.add(moveNeigbor);
                    this.f = get_f(moveNeigbor);
                    break;
                }
            }
            // 第三步，更新s_（最优路径）、更新A（历史最优）
            if (this.f < this.A) {
                this.A = this.f;
                s_ = new Route(this.s.getRt());
            }
            // 打印日志
            if(i % 10 == 0){
                System.out.println("第" + i + "代————" + "历史最优A：" + this.A + " 当前优化f：" + this.f);
            }
        }
    }
    // 构造方法
    public Ts(int t_size, int gen,int cnum) {
        this.gen = gen;
        this.T_size = t_size;
        this.cnum = cnum;
        this.T = new LimitedQueue<>(T_size);
    }
    // 初始化解集状态
    public void initial(){
        ReadCsv cr = new ReadCsv(this.csvPath);
        this.dis = cr.getArray(this.cnum);
        this.s = setRandS();
        this.s_ = new Route(this.s.getRt());
        this.f = getF(this.s.getRt());
        this.A = this.f;
    }
    // setS方法用于生成随机顺序的初始解
    public Route setRandS(){
        ArrayList<Double> arr1 = new ArrayList<>();
        ArrayList<Double> arr2 = new ArrayList<>();
        ArrayList<Integer> arr = new ArrayList<>();
        // 初始化arr
        for (int i = 0; i < this.cnum; i++) {
            arr.add(i);
        }
        // 随机初始化arr1
        for (int i = 0; i < this.cnum; i++) {
            arr1.add(Math.random());
        }
        // copy arr1给arr2
        for (int i = 0; i < this.cnum; i++) {
            arr2.add(arr1.get(i));
        }
        arr2.sort(Comparator.naturalOrder());
        for (int i = 0; i < this.cnum; i++) {
            int idx = arr2.indexOf(arr1.get(i));
            arr.set(idx, i);
        }
        return new Route(arr);
    }
    // 创建方法获取某一状态的目标函数值
    public int getF(ArrayList<Integer> rt_){
        int sum = 0;
        for (int i = 0; i < this.cnum; i++) {
            sum = sum + this.dis[rt_.get(i)][rt_.get((i + 1) % this.cnum)];
        }
        return sum;
    }
    // 定义评估当前路径进行进行某种路径移动后的目标函数值的方法
    public int get_f(MoveNeigbor m){
        ArrayList<Integer> rt_ = (ArrayList<Integer>) this.s.getRt().clone();
        ArrayList<Integer> loc = m.getLoc();
        int idx1 = rt_.indexOf(loc.get(0));
        int idx2 = rt_.indexOf(loc.get(1));
        Integer tempVar = rt_.get(idx1);
        rt_.set(idx1, rt_.get(idx2));
        rt_.set(idx2, tempVar);
        return getF(rt_);
    }
    // 得到当前解的所有邻域
    public void getTab(){
        for (int i = 0; i < this.cnum; i++) {
            for (int j = i + 1; j < this.cnum; j++) {
                this.tab.add(new MoveNeigbor(i, j));
            }
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class MoveNeigbor {
    // movm代表交换i和j的动作
    public HashSet<Integer> movm = new HashSet<>();
    // 通过构造方法设置movm属性
    public MoveNeigbor(Integer i, Integer j) {
        this.movm.add(i);
        this.movm.add(j);
    }
    // 重写equals方法
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        MoveNeigbor that = (MoveNeigbor) o;
        return that.movm.equals(this.movm);
    }

    // 定义方法将movm转为顺序表并返回
    public ArrayList<Integer> getLoc() {
        Iterator it = this.movm.iterator();
        Integer loc1 = (Integer) it.next();
        Integer loc2 = (Integer) it.next();
        ArrayList<Integer> loc = new ArrayList<>();
        loc.add(loc1);
        loc.add(loc2);
        return loc;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Route {
    // 属性rt描述当前路径
    private ArrayList<Integer> rt = new ArrayList<>();

    public ArrayList<Integer> getRt() {
        return (ArrayList<Integer>) rt.clone();
    }
    // 构造方法
    public Route(ArrayList<Integer> rt) {
        this.rt = (ArrayList<Integer>) rt.clone();
    }
    // 定义对当前路径进行邻域移动的方法
    public void makeAMove(MoveNeigbor m){
        ArrayList<Integer> loc = m.getLoc();
        int idx1 = rt.indexOf(loc.get(0));
        int idx2 = rt.indexOf(loc.get(1));
        Integer tempVar = this.rt.get(idx1);
        this.rt.set(idx1, this.rt.get(idx2));
        this.rt.set(idx2, tempVar);
    }
    // 定义获取指定索引值的方法
    public Integer get(int i){
        return this.rt.get(i);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class LimitedQueue<E> extends LinkedList<E> {
    private static final long serialVersionUID = 1L;
    private final int size;

    public LimitedQueue(int size) {
        this.size = size;
    }
    @Override
    public boolean add(E o) {
        super.add(o);
        while (size() > size) {
            super.remove();
        }
        return true;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class ReadCsv {
    // 定义构造方法，传入文件路径
    private String path;
    public ReadCsv(String path) {
        this.path = path;
    }
    // 定义方法得到文件解析后的数组
    public int[][] getArray(int y){
        int[][] arr = new int[y][y];
        CSVReader reader = null;
        int x = 0;
        try {
            reader = new CSVReader(new FileReader(path));
            String[] line;
            while ((line = reader.readNext()) != null) {
                for (int i = 0; i < y; i++) {
                    arr[x][i] = Integer.parseInt(line[i]);
                }
                x++;
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
        return arr;
    }
}