1    package geneticalgorithm;
2    import java.util.*;
3    public class GeneticAlgorithm {
4        /** Static Constants **/
5        public final static int ORDER = 0;
6        public final static int DISTANCE = 1;
7        public final static int N = 20;
8        public final static int X = 0;
9        public final static int Y = 1;
10       /** Internal Constants **/
11       
12       private final int MAX_ITERATIONS = 10000;
13       private double [][] nodes;
14       private double [][] distances;
15       private ArrayList<Tour> population;
16       private Random rand;
17   
18   
19       public GeneticAlgorithm() {
20           rand = new Random();
21           initNodes();
22           initDistances();
23       }
24   
25       // Initialize the nodes with random (x,y) values
26       private void initNodes() {
27           nodes = new double[N][2];
28           for(int i = 0; i < N; i++) {
29               nodes[i][X] = rand.nextDouble();
30               nodes[i][Y] = rand.nextDouble();
31           }
32   
33       }
34   
35       // Create an NxN distance matrix
36       private void initDistances() {
37           distances = new double[N][N];
38           for(int i = 0; i < N; i++) {
39               for(int j = 0; j < N; j++) {
40                   distances[i][j] = getDistance(i,j);
41               }
42           }
43       }
44   
45       // Algorithm inspired by the Knuth Shuffle: http://en.wikipedia.org/wiki/Knuth_shuffle
46       private void initPopulation() {
47           population = new ArrayList<Tour>(N);
48           int k;
49           int [] tour;
50           int [] identityPermutation = new int[N];
51           for(int i = 0; i < N; i++) identityPermutation[i] = i;
52           for(int i = 0; i < N; i++) {
53               tour = identityPermutation.clone();
54               for(int j = 0; j < N; j++) {
55                   k = rand.nextInt(N);
56                   swap(j,k,tour);
57               }
58               population.add(i,new Tour(tour.clone(), fitness(tour)));
59           }
60       }
61   
62       // Used for debugging purposes
63       public void printPopulation() {
64           int [] a;
65           for(Tour pop : population) {
66               a = pop.getTour();
67               for(int i = 0; i < N; i++) {
68                   System.out.print(a[i] + " ");
69               }
70               System.out.println(" : " + pop.getDistance());
71           }
72       }
73   
74       public void run(double mutationRate, int recombinationMethod) {
75           initPopulation();
76           int iteration = 0;
77           int [] child;
78           Tour temp;
79           while(iteration++ < MAX_ITERATIONS) {
80               child = selection(recombinationMethod);
81               // Remove last child
82               population.remove(N - 1);
83               population.add(N - 1, new Tour(child, fitness(child)));
84               for(int i = 0; i < N; i++) {
85                   if(rand.nextDouble() <= mutationRate) {
86                       temp = population.get(i);
87                       population.remove(i);
88                       population.add(i, mutate(temp.getTour()));
89                   }
90               }
91           }
92       }
93   
94       // Since the list is sorted, the first element should be the best tour
95       public Tour getBestTour() {
96           return population.get(0);
97       }
98       // Returns a JPanel that displays the vertices and edges for the optimal tour
99       public TourDisplay getPanel() {
100              return new TourDisplay(nodes, getBestTour().getTour());
101      }
102      // Returns the Euclidean distance between two nodes
103      private double getDistance(int i, int j) {
104          double x = (nodes[j][X] - nodes[i][X]) * (nodes[j][X] - nodes[i][X]);
105          double y = (nodes[j][Y] - nodes[i][Y]) * (nodes[j][Y] - nodes[i][Y]);
106          return Math.sqrt(x + y);
107      }
108      
109      // Finds a mother and father tour.  It will use one of the recombination methods to
110      // return a child tour
111      private int [] selection(int recombinationMethod) {
112          Collections.sort(population);
113          int [] mom = population.get(rand.nextInt(N/2)).getTour();
114          int [] dad = population.get(rand.nextInt(N)).getTour();
115          return (recombinationMethod == ORDER) ?
116                  orderRecombination(mom, dad) : distanceRecombination(mom, dad);
117      }
118      
119      // Apply the mutation on a given tour and return it as a new Tour object
120      private Tour mutate(int [] a)  {
121          int i = rand.nextInt(N);
122          int j = rand.nextInt(N);
123          swap(i, j, a);
124          return new Tour(a, fitness(a));
125      }
126  
127      // Returns the length of the given tour
128      private double fitness(int [] tour) {
129          int j,k;
130          double length = 0;
131          for(int i = 0; i < N; i++) {
132              j = tour[i];
133              k = tour[(i + 1) % N];
134              length += distances[j][k];
135          }
136          return length;
137      }
138      // Order recombination method 
139      private int[] orderRecombination(int [] mom, int [] dad) {
140          int [] child = new int[N];
141          boolean flag;
142          int nextIndex;
143          int crossover1 = rand.nextInt(N);
144          int crossover2 = rand.nextInt(N);
145          if(crossover2 < crossover1) {
146              int temp = crossover1;
147              crossover1 = crossover2;
148              crossover2 = temp;
149          }
150  
151          for(int i = crossover1; i <= crossover2; i++) {
152              child[i] = mom[i];
153          }
154          nextIndex = 0;
155          for(int i = 0; i < N; i++) {
156              flag = false;
157              // Check to see if dad[i] is already in child
158              for(int j = crossover1; j <= crossover2 && !flag; j++) {
159                  if(dad[i] == child[j]) flag = true;
160              }
161              if(!flag) {
162                  while(nextIndex >= crossover1 && nextIndex <= crossover2 && nextIndex < N) nextIndex++;
163                  child[nextIndex] = dad[i];
164                  nextIndex++;
165              }
166          }
167          return child;
168      }
169      
170      // Distance recombination method
171      private int[] distanceRecombination(int [] mom, int [] dad) {
172          int currentCity = rand.nextInt(N);
173          int nextFromMom, nextFromDad;
174          double momDistance = 0, dadDistance = 0;
175          boolean momAvail, dadAvail;
176          int [] child = new int[N];
177          for(int i=0;i<N;i++)child[i]=-1;
178          child[0] = currentCity;
179          for(int i = 1; i < N; i++) {
180              momAvail = false;
181              dadAvail = false;
182              nextFromMom = mom[(getNextIndex(currentCity,mom) + 1) % N];
183              nextFromDad = dad[(getNextIndex(currentCity,dad) + 1) % N];
184              if(!inArray(nextFromMom, child)) {
185                  momAvail = true;
186                  momDistance = distances[currentCity][nextFromMom];
187              }
188              if(!inArray(nextFromDad, child)) {
189                  dadAvail = true;
190                  dadDistance = distances[currentCity][nextFromDad];
191              }
192              if(momAvail && dadAvail) {
193                  currentCity = (momDistance < dadDistance) ? nextFromMom : nextFromDad;
194              } else if(momAvail && !dadAvail) {
195                  currentCity = nextFromMom;
196              } else if(!momAvail && dadAvail) {
197                  currentCity = nextFromDad;
198              } else {
199                  currentCity = rand.nextInt(N);
200                  while(inArray(currentCity, child)) {
201                      currentCity = rand.nextInt(N);
202                  }
203              }
204              child[i] = currentCity;
205          }
206          return child;
207      }
208  
209      // Fetches the index of the next city for the distance recombination method
210      private int getNextIndex(int city, int[] tour) {
211          for(int i = 0; i < tour.length; i++) {
212              if(tour[i] == city) return i;
213          }
214          return -1;
215      }
216      // Determines whether or not a city is already in the tour
217      private boolean inArray(int city, int[] tour) {
218          for(int i = 0; i < tour.length; i++) {
219              if(tour[i] == city) return true;
220          }
221          return false;
222      }
223      // Swap two nodes in a tour
224      private void swap(int i, int j, int [] a) {
225          int temp = a[i];
226          a[i] = a[j];
227          a[j] = temp;
228      }
229  }
230