GA_TSP/Individual.java at main · son3102k/GA_TSP · GitHub

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
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Random;

public class Individual implements Comparable<Individual>{
    public static int[][] COST;
    private int len_genes;
    public int[] genes;
    public int fitness = 0;
    public void caculate_fitness() {
        int fitness = 0;
        for (int i = 1 ; i<len_genes ; i++) {
            fitness -= COST[genes[i]][genes[i+1]];
        }
        fitness -= COST[genes[len_genes]][genes[1]];
        this.fitness = fitness;
    }
    public Individual(int n, int[] a) throws FileNotFoundException{
        this.len_genes = n;
        genes = new int[n+1];
        for (int i = 1 ; i<n ; i++) {
            genes[i] = a[i];
            fitness -= COST[a[i]][a[i+1]];
        }
        genes[n] = a[n];
        fitness -= COST[a[n]][a[1]];
    }

    public void mutation(Random rd) {
        int idx1, idx2;
        idx1 = rd.nextInt(len_genes)+1;
        while ((idx2=rd.nextInt(len_genes)+1) == idx1);
        int tmp = genes[idx1];
        genes[idx1] = genes[idx2];
        genes[idx2] = tmp;
        caculate_fitness();
    }

    public ArrayList<Individual> PMX_crossOver(Individual other,Random rd) throws FileNotFoundException {
        ArrayList<Individual> l = new ArrayList<Individual>();
        int[] offSpring1 = new int[len_genes+1];
        int[] offSpring2 = new int[len_genes+1];

        int idx1 = rd.nextInt(len_genes/3)+1;
        int idx2 = rd.nextInt((len_genes/3))+ (2*len_genes/3)+1;
        HashMap<Integer,Integer> o1_map_o2 = new HashMap<Integer,Integer>();
        HashMap<Integer,Integer> o2_map_o1 = new HashMap<Integer,Integer>();

        for (int i = idx1 ; i<=idx2 ; i++) {
            offSpring1[i] = other.genes[i];

            offSpring2[i] = this.genes[i];

            o1_map_o2.put(offSpring1[i], offSpring2[i]);
            o2_map_o1.put(offSpring2[i], offSpring1[i]);
        }

        // mapping non-collision

        for (int i = 1 ; i<=len_genes ; i++) {
            if (i==idx1) {
                i=idx2;
                continue;
            }
            if (!o1_map_o2.containsKey(this.genes[i])) {
                offSpring1[i] = this.genes[i];

            }
            if (!o2_map_o1.containsKey(other.genes[i])) {
                offSpring2[i] = other.genes[i];
            }

            if (offSpring1[i]!=0) {
                o1_map_o2.put(offSpring1[i], offSpring2[i]);
            }
            if (offSpring2[i]!=0) {
                o2_map_o1.put(offSpring2[i], offSpring1[i]);
            }
        }

        // mapping collision

        for (int i = 1 ; i<=len_genes ; i++) {
            if (i==idx1) {
                i=idx2;
                continue;
            }
            if (offSpring1[i]==0) {
                Integer key = this.genes[i];
                while (o1_map_o2.containsKey(key)) {
                    key = o1_map_o2.get(key);
                }
                offSpring1[i] = key;
            }

            if (offSpring2[i]==0) {
                Integer key = other.genes[i];
                while (o2_map_o1.containsKey(key)) {
                    key = o2_map_o1.get(key);
                }
                offSpring2[i] = key;
            }
        }

        l.add(new Individual(len_genes, offSpring1));
        l.add(new Individual(len_genes, offSpring2));

        return l;
    }

    @Override
    public int compareTo(Individual o) {

        Integer t = this.fitness;
        Integer q = o.fitness;
        return  t.compareTo(q);
    }

}