1    // ============================================================================
2    //   Copyright 2006, 2007, 2008 Daniel W. Dyer
3    //
4    //   Licensed under the Apache License, Version 2.0 (the "License");
5    //   you may not use this file except in compliance with the License.
6    //   You may obtain a copy of the License at
7    //
8    //       http://www.apache.org/licenses/LICENSE-2.0
9    //
10   //   Unless required by applicable law or agreed to in writing, software
11   //   distributed under the License is distributed on an "AS IS" BASIS,
12   //   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   //   See the License for the specific language governing permissions and
14   //   limitations under the License.
15   // ============================================================================
16   package org.uncommons.watchmaker.examples.travellingsalesman;
17   
18   import java.util.List;
19   import org.uncommons.watchmaker.framework.FitnessEvaluator;
20   
21   /**
22    * Fitness evalator that measures the total distance of a route in the travelling salesman
23    * problem.  The fitness score of a route is the total distance (in km).  A route
24    * is represented as a list of cities in the order that they will be visited.
25    * The last leg of the journey is from the last city in the list back to the
26    * first.
27    * @author Daniel Dyer
28    */
29   public class RouteEvaluator implements FitnessEvaluator<List<String>>
30   {
31       private final DistanceLookup distances;
32   
33   
34       /**
35        * @param distances Provides distances between a set of cities.
36        */
37       public RouteEvaluator(DistanceLookup distances)
38       {
39           this.distances = distances;
40       }
41   
42   
43       /**
44        * Calculates the length of an evolved route. 
45        * @param candidate The route to evaluate.
46        * @param population {@inheritDoc}
47        * @return The total distance (in kilometres) of a journey that visits
48        * each city in order and returns to the starting point.
49        */
50       public double getFitness(List<String> candidate,
51                                List<? extends List<String>> population)
52       {
53           int totalDistance = 0;
54           int cityCount = candidate.size();
55           for (int i = 0; i < cityCount; i++)
56           {
57               int nextIndex = i < cityCount - 1 ? i + 1 : 0;
58               totalDistance += distances.getDistance(candidate.get(i),
59                                                      candidate.get(nextIndex));
60           }
61           return totalDistance;
62       }
63   
64   
65       /**
66        * {@inheritDoc}
67        * Returns false since shorter distances represent fitter candidates.
68        * @return false
69        */
70       public boolean isNatural()
71       {
72           return false;
73       }
74   }
75