You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@mahout.apache.org by gs...@apache.org on 2008/07/31 12:33:50 UTC
svn commit: r681327 [3/6] - in /lucene/mahout/trunk/core: ./ lib/
src/main/examples/org/apache/mahout/ga/
src/main/examples/org/apache/mahout/ga/watchmaker/
src/main/examples/org/apache/mahout/ga/watchmaker/cd/
src/main/examples/org/apache/mahout/ga/wa...
Added: lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/EuropeanDistanceLookup.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/EuropeanDistanceLookup.java?rev=681327&view=auto
==============================================================================
--- lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/EuropeanDistanceLookup.java (added)
+++ lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/EuropeanDistanceLookup.java Thu Jul 31 03:33:45 2008
@@ -0,0 +1,330 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.mahout.ga.watchmaker.travellingsalesman;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
+/**
+ * This class contains data about cities in Europe and the distances
+ * between them.
+ *
+ * <br>
+ * The original code is from <b>the Watchmaker project</b>
+ * (https://watchmaker.dev.java.net/).
+ */
+public final class EuropeanDistanceLookup implements DistanceLookup
+{
+ private static final Map<String, Map<String, Integer>> DISTANCES = new HashMap<String, Map<String, Integer>>(15);
+ static
+ {
+ // Distances are in km as the crow flies (from http://www.indo.com/distance/)
+
+ Map<String, Integer> amsterdam = new HashMap<String, Integer>(20);
+ amsterdam.put("Amsterdam", 0);
+ amsterdam.put("Athens", 2162);
+ amsterdam.put("Berlin", 576);
+ amsterdam.put("Brussels", 171);
+ amsterdam.put("Copenhagen", 622);
+ amsterdam.put("Dublin", 757);
+ amsterdam.put("Helsinki", 1506);
+ amsterdam.put("Lisbon", 1861);
+ amsterdam.put("London", 356);
+ amsterdam.put("Luxembourg", 318);
+ amsterdam.put("Madrid", 1477);
+ amsterdam.put("Paris", 429);
+ amsterdam.put("Rome", 1304);
+ amsterdam.put("Stockholm", 1132);
+ amsterdam.put("Vienna", 938);
+ DISTANCES.put("Amsterdam", amsterdam);
+
+ Map<String, Integer> athens = new HashMap<String, Integer>(20);
+ athens.put("Amsterdam", 2162);
+ athens.put("Athens", 0);
+ athens.put("Berlin", 1801);
+ athens.put("Brussels", 2089);
+ athens.put("Copenhagen", 2140);
+ athens.put("Dublin", 2860);
+ athens.put("Helsinki", 2464);
+ athens.put("Lisbon", 2854);
+ athens.put("London", 2391);
+ athens.put("Luxembourg", 1901);
+ athens.put("Madrid", 2374);
+ athens.put("Paris", 2097);
+ athens.put("Rome", 1040);
+ athens.put("Stockholm", 2410);
+ athens.put("Vienna", 1280);
+ DISTANCES.put("Athens", athens);
+
+ Map<String, Integer> berlin = new HashMap<String, Integer>(20);
+ berlin.put("Amsterdam", 576);
+ berlin.put("Athens", 1801);
+ berlin.put("Berlin", 0);
+ berlin.put("Brussels", 648);
+ berlin.put("Copenhagen", 361);
+ berlin.put("Dublin", 1315);
+ berlin.put("Helsinki", 1108);
+ berlin.put("Lisbon", 2310);
+ berlin.put("London", 929);
+ berlin.put("Luxembourg", 595);
+ berlin.put("Madrid", 1866);
+ berlin.put("Paris", 877);
+ berlin.put("Rome", 1185);
+ berlin.put("Stockholm", 818);
+ berlin.put("Vienna", 525);
+ DISTANCES.put("Berlin", berlin);
+
+ Map<String, Integer> brussels = new HashMap<String, Integer>(20);
+ brussels.put("Amsterdam", 171);
+ brussels.put("Athens", 2089);
+ brussels.put("Berlin", 648);
+ brussels.put("Brussels", 0);
+ brussels.put("Copenhagen", 764);
+ brussels.put("Dublin", 780);
+ brussels.put("Helsinki", 1649);
+ brussels.put("Lisbon", 1713);
+ brussels.put("London", 321);
+ brussels.put("Luxembourg", 190);
+ brussels.put("Madrid", 1315);
+ brussels.put("Paris", 266);
+ brussels.put("Rome", 1182);
+ brussels.put("Stockholm", 1284);
+ brussels.put("Vienna", 917);
+ DISTANCES.put("Brussels", brussels);
+
+ Map<String, Integer> copenhagen = new HashMap<String, Integer>(20);
+ copenhagen.put("Amsterdam", 622);
+ copenhagen.put("Athens", 2140);
+ copenhagen.put("Berlin", 361);
+ copenhagen.put("Brussels", 764);
+ copenhagen.put("Copenhagen", 0);
+ copenhagen.put("Dublin", 1232);
+ copenhagen.put("Helsinki", 885);
+ copenhagen.put("Lisbon", 2477);
+ copenhagen.put("London", 953);
+ copenhagen.put("Luxembourg", 799);
+ copenhagen.put("Madrid", 2071);
+ copenhagen.put("Paris", 1028);
+ copenhagen.put("Rome", 1540);
+ copenhagen.put("Stockholm", 526);
+ copenhagen.put("Vienna", 876);
+ DISTANCES.put("Copenhagen", copenhagen);
+
+ Map<String, Integer> dublin = new HashMap<String, Integer>(20);
+ dublin.put("Amsterdam", 757);
+ dublin.put("Athens", 2860);
+ dublin.put("Berlin", 1315);
+ dublin.put("Brussels", 780);
+ dublin.put("Copenhagen", 1232);
+ dublin.put("Dublin", 0);
+ dublin.put("Helsinki", 2021);
+ dublin.put("Lisbon", 1652);
+ dublin.put("London", 469);
+ dublin.put("Luxembourg", 961);
+ dublin.put("Madrid", 1458);
+ dublin.put("Paris", 787);
+ dublin.put("Rome", 1903);
+ dublin.put("Stockholm", 1625);
+ dublin.put("Vienna", 1687);
+ DISTANCES.put("Dublin", dublin);
+
+ Map<String, Integer> helsinki = new HashMap<String, Integer>(20);
+ helsinki.put("Amsterdam", 1506);
+ helsinki.put("Athens", 2464);
+ helsinki.put("Berlin", 1108);
+ helsinki.put("Brussels", 1649);
+ helsinki.put("Copenhagen", 885);
+ helsinki.put("Dublin", 2021);
+ helsinki.put("Helsinki", 0);
+ helsinki.put("Lisbon", 3362);
+ helsinki.put("London", 1823);
+ helsinki.put("Luxembourg", 1667);
+ helsinki.put("Madrid", 2949);
+ helsinki.put("Paris", 1912);
+ helsinki.put("Rome", 2202);
+ helsinki.put("Stockholm", 396);
+ helsinki.put("Vienna", 1439);
+ DISTANCES.put("Helsinki", helsinki);
+
+ Map<String, Integer> lisbon = new HashMap<String, Integer>(20);
+ lisbon.put("Amsterdam", 1861);
+ lisbon.put("Athens", 2854);
+ lisbon.put("Berlin", 2310);
+ lisbon.put("Brussels", 1713);
+ lisbon.put("Copenhagen", 2477);
+ lisbon.put("Dublin", 1652);
+ lisbon.put("Helsinki", 3362);
+ lisbon.put("Lisbon", 0);
+ lisbon.put("London", 1585);
+ lisbon.put("Luxembourg", 1716);
+ lisbon.put("Madrid", 501);
+ lisbon.put("Paris", 1452);
+ lisbon.put("Rome", 1873);
+ lisbon.put("Stockholm", 2993);
+ lisbon.put("Vienna", 2300);
+ DISTANCES.put("Lisbon", lisbon);
+
+ Map<String, Integer> london = new HashMap<String, Integer>(20);
+ london.put("Amsterdam", 356);
+ london.put("Athens", 2391);
+ london.put("Berlin", 929);
+ london.put("Brussels", 321);
+ london.put("Copenhagen", 953);
+ london.put("Dublin", 469);
+ london.put("Helsinki", 1823);
+ london.put("Lisbon", 1585);
+ london.put("London", 0);
+ london.put("Luxembourg", 494);
+ london.put("Madrid", 1261);
+ london.put("Paris", 343);
+ london.put("Rome", 1444);
+ london.put("Stockholm", 1436);
+ london.put("Vienna", 1237);
+ DISTANCES.put("London", london);
+
+ Map<String, Integer> luxembourg = new HashMap<String, Integer>(20);
+ luxembourg.put("Amsterdam", 318);
+ luxembourg.put("Athens", 1901);
+ luxembourg.put("Berlin", 595);
+ luxembourg.put("Brussels", 190);
+ luxembourg.put("Copenhagen", 799);
+ luxembourg.put("Dublin", 961);
+ luxembourg.put("Helsinki", 1667);
+ luxembourg.put("Lisbon", 1716);
+ luxembourg.put("London", 494);
+ luxembourg.put("Luxembourg", 0);
+ luxembourg.put("Madrid", 1282);
+ luxembourg.put("Paris", 294);
+ luxembourg.put("Rome", 995);
+ luxembourg.put("Stockholm", 1325);
+ luxembourg.put("Vienna", 761);
+ DISTANCES.put("Luxembourg", luxembourg);
+
+ Map<String, Integer> madrid = new HashMap<String, Integer>(20);
+ madrid.put("Amsterdam", 1477);
+ madrid.put("Athens", 2374);
+ madrid.put("Berlin", 1866);
+ madrid.put("Brussels", 1315);
+ madrid.put("Copenhagen", 2071);
+ madrid.put("Dublin", 1458);
+ madrid.put("Helsinki", 2949);
+ madrid.put("Lisbon", 501);
+ madrid.put("London", 1261);
+ madrid.put("Luxembourg", 1282);
+ madrid.put("Madrid", 0);
+ madrid.put("Paris", 1050);
+ madrid.put("Rome", 1377);
+ madrid.put("Stockholm", 2596);
+ madrid.put("Vienna", 1812);
+ DISTANCES.put("Madrid", madrid);
+
+ Map<String, Integer> paris = new HashMap<String, Integer>(20);
+ paris.put("Amsterdam", 429);
+ paris.put("Athens", 2097);
+ paris.put("Berlin", 877);
+ paris.put("Brussels", 266);
+ paris.put("Copenhagen", 1028);
+ paris.put("Dublin", 787);
+ paris.put("Helsinki", 1912);
+ paris.put("Lisbon", 1452);
+ paris.put("London", 343);
+ paris.put("Luxembourg", 294);
+ paris.put("Madrid", 1050);
+ paris.put("Paris", 0);
+ paris.put("Rome", 1117);
+ paris.put("Stockholm", 1549);
+ paris.put("Vienna", 1037);
+ DISTANCES.put("Paris", paris);
+
+ Map<String, Integer> rome = new HashMap<String, Integer>(20);
+ rome.put("Amsterdam", 1304);
+ rome.put("Athens", 1040);
+ rome.put("Berlin", 1185);
+ rome.put("Brussels", 1182);
+ rome.put("Copenhagen", 1540);
+ rome.put("Dublin", 1903);
+ rome.put("Helsinki", 2202);
+ rome.put("Lisbon", 1873);
+ rome.put("London", 1444);
+ rome.put("Luxembourg", 995);
+ rome.put("Madrid", 1377);
+ rome.put("Paris", 1117);
+ rome.put("Rome", 0);
+ rome.put("Stockholm", 1984);
+ rome.put("Vienna", 765);
+ DISTANCES.put("Rome", rome);
+
+ Map<String, Integer> stockholm = new HashMap<String, Integer>(20);
+ stockholm.put("Amsterdam", 1132);
+ stockholm.put("Athens", 2410);
+ stockholm.put("Berlin", 818);
+ stockholm.put("Brussels", 1284);
+ stockholm.put("Copenhagen", 526);
+ stockholm.put("Dublin", 1625);
+ stockholm.put("Helsinki", 396);
+ stockholm.put("Lisbon", 2993);
+ stockholm.put("London", 1436);
+ stockholm.put("Luxembourg", 1325);
+ stockholm.put("Madrid", 2596);
+ stockholm.put("Paris", 1549);
+ stockholm.put("Rome", 1984);
+ stockholm.put("Stockholm", 0);
+ stockholm.put("Vienna", 1247);
+ DISTANCES.put("Stockholm", stockholm);
+
+ Map<String, Integer> vienna = new HashMap<String, Integer>(20);
+ vienna.put("Amsterdam", 938);
+ vienna.put("Athens", 1280);
+ vienna.put("Berlin", 525);
+ vienna.put("Brussels", 917);
+ vienna.put("Copenhagen", 876);
+ vienna.put("Dublin", 1687);
+ vienna.put("Helsinki", 1439);
+ vienna.put("Lisbon", 2300);
+ vienna.put("London", 1237);
+ vienna.put("Luxembourg", 761);
+ vienna.put("Madrid", 1812);
+ vienna.put("Paris", 1037);
+ vienna.put("Rome", 765);
+ vienna.put("Stockholm", 1247);
+ vienna.put("Vienna", 0);
+ DISTANCES.put("Vienna", vienna);
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public List<String> getKnownCities()
+ {
+ List<String> cities = new ArrayList<String>(DISTANCES.keySet());
+ Collections.sort(cities);
+ return cities;
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public int getDistance(String startingCity, String destinationCity)
+ {
+ return DISTANCES.get(startingCity).get(destinationCity);
+ }
+}
Propchange: lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/EuropeanDistanceLookup.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/EvolutionaryTravellingSalesman.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/EvolutionaryTravellingSalesman.java?rev=681327&view=auto
==============================================================================
--- lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/EvolutionaryTravellingSalesman.java (added)
+++ lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/EvolutionaryTravellingSalesman.java Thu Jul 31 03:33:45 2008
@@ -0,0 +1,182 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.mahout.ga.watchmaker.travellingsalesman;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Random;
+
+import org.apache.mahout.ga.watchmaker.MahoutFitnessEvaluator;
+import org.apache.mahout.ga.watchmaker.STEvolutionEngine;
+import org.apache.mahout.ga.watchmaker.STFitnessEvaluator;
+import org.uncommons.maths.random.MersenneTwisterRNG;
+import org.uncommons.maths.random.PoissonGenerator;
+import org.uncommons.watchmaker.framework.CandidateFactory;
+import org.uncommons.watchmaker.framework.EvolutionEngine;
+import org.uncommons.watchmaker.framework.EvolutionObserver;
+import org.uncommons.watchmaker.framework.EvolutionaryOperator;
+import org.uncommons.watchmaker.framework.PopulationData;
+import org.uncommons.watchmaker.framework.SelectionStrategy;
+import org.uncommons.watchmaker.framework.StandaloneEvolutionEngine;
+import org.uncommons.watchmaker.framework.factories.ListPermutationFactory;
+import org.uncommons.watchmaker.framework.operators.EvolutionPipeline;
+import org.uncommons.watchmaker.framework.operators.ListOrderCrossover;
+import org.uncommons.watchmaker.framework.operators.ListOrderMutation;
+import org.uncommons.watchmaker.framework.termination.GenerationCount;
+
+/**
+ * Evolutionary algorithm for finding (approximate) solutions to the travelling
+ * salesman problem.
+ *
+ *
+ * <br>
+ * The original code is from <b>the Watchmaker project</b>
+ * (https://watchmaker.dev.java.net/).<br>
+ * Modified to use Mahout whenever requested.
+ */
+public class EvolutionaryTravellingSalesman implements
+ TravellingSalesmanStrategy {
+ private final DistanceLookup distances;
+
+ private final SelectionStrategy<? super List<String>> selectionStrategy;
+
+ private final int populationSize;
+
+ private final int eliteCount;
+
+ private final int generationCount;
+
+ private final boolean crossover;
+
+ private final boolean mutation;
+
+ private final boolean mahout;
+
+ /**
+ * Creates an evolutionary Travelling Salesman solver with the specified
+ * configuration.
+ *
+ * @param distances Information about the distances between cities.
+ * @param selectionStrategy The selection implementation to use for the
+ * evolutionary algorithm.
+ * @param populationSize The number of candidates in the population of evolved
+ * routes.
+ * @param eliteCount The number of candidates to preserve via elitism at each
+ * generation.
+ * @param generationCount The number of iterations of evolution to perform.
+ * @param crossover Whether or not to use a cross-over operator in the
+ * evolution.
+ * @param mutation Whether or not to use a mutation operator in the evolution.
+ * @param mahout Whether or not to use Mahout for evaluation.
+ */
+ public EvolutionaryTravellingSalesman(DistanceLookup distances,
+ SelectionStrategy<? super List<String>> selectionStrategy,
+ int populationSize, int eliteCount, int generationCount,
+ boolean crossover, boolean mutation, boolean mahout) {
+ if (eliteCount < 0 || eliteCount >= populationSize) {
+ throw new IllegalArgumentException(
+ "Elite count must be non-zero and less than population size.");
+ }
+ if (!crossover && !mutation) {
+ throw new IllegalArgumentException(
+ "At least one of cross-over or mutation must be selected.");
+ }
+ this.distances = distances;
+ this.selectionStrategy = selectionStrategy;
+ this.populationSize = populationSize;
+ this.eliteCount = eliteCount;
+ this.generationCount = generationCount;
+ this.crossover = crossover;
+ this.mutation = mutation;
+ this.mahout = mahout;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public String getDescription() {
+ String selectionName = selectionStrategy.getClass().getSimpleName();
+ return (mahout ? "Mahout " : "") + "Evolution (pop: " + populationSize
+ + ", gen: " + generationCount + ", elite: " + eliteCount + ", "
+ + selectionName + ")";
+ }
+
+ /**
+ * Calculates the shortest route using a generational evolutionary algorithm
+ * with a single ordered mutation operator and truncation selection.
+ *
+ * @param cities The list of destinations, each of which must be visited once.
+ * @param progressListener Call-back for receiving the status of the algorithm
+ * as it progresses.
+ * @return The (approximate) shortest route that visits each of the specified
+ * cities once.
+ */
+ public List<String> calculateShortestRoute(Collection<String> cities,
+ final ProgressListener progressListener) {
+ Random rng = new MersenneTwisterRNG();
+
+ // Set-up evolution pipeline (cross-over followed by mutation).
+ List<EvolutionaryOperator<? super List<?>>> operators = new ArrayList<EvolutionaryOperator<? super List<?>>>(
+ 2);
+ if (crossover) {
+ operators.add(new ListOrderCrossover());
+ }
+ if (mutation) {
+ operators.add(new ListOrderMutation(new PoissonGenerator(1.5, rng),
+ new PoissonGenerator(1.5, rng)));
+ }
+
+ EvolutionaryOperator<List<?>> pipeline = new EvolutionPipeline<List<?>>(
+ operators);
+
+ CandidateFactory<List<String>> candidateFactory = new ListPermutationFactory<String>(
+ new LinkedList<String>(cities));
+ EvolutionEngine<List<String>> engine = getEngine(candidateFactory,
+ pipeline, rng);
+ engine.addEvolutionObserver(new EvolutionObserver<List<String>>() {
+ public void populationUpdate(PopulationData<List<String>> data) {
+ if (progressListener != null) {
+ progressListener
+ .updateProgress(((double) data.getGenerationNumber() + 1)
+ / generationCount * 100);
+ }
+ }
+ });
+ return engine.evolve(populationSize, eliteCount, new GenerationCount(
+ generationCount));
+ }
+
+ private EvolutionEngine<List<String>> getEngine(
+ CandidateFactory<List<String>> candidateFactory,
+ EvolutionaryOperator<List<?>> pipeline, Random rng) {
+ if (mahout) {
+ // This is what we need to do to distribute the fitness evaluation.
+ // First create a STFitnessEvaluator that wraps our FitnessEvaluator
+ STFitnessEvaluator<List<String>> evaluator = new MahoutFitnessEvaluator<List<String>>(
+ new RouteEvaluator(distances));
+ // Then use a STEvolutionEngine instead of a StandaloneEvolutionEngine.
+ // Its parameters remain the same.
+ return new STEvolutionEngine<List<String>>(candidateFactory, pipeline,
+ evaluator, selectionStrategy, rng);
+ } else {
+ return new StandaloneEvolutionEngine<List<String>>(candidateFactory,
+ pipeline, new RouteEvaluator(distances), selectionStrategy, rng);
+ }
+ }
+}
Propchange: lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/EvolutionaryTravellingSalesman.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/ExecutionPanel.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/ExecutionPanel.java?rev=681327&view=auto
==============================================================================
--- lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/ExecutionPanel.java (added)
+++ lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/ExecutionPanel.java Thu Jul 31 03:33:45 2008
@@ -0,0 +1,112 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.mahout.ga.watchmaker.travellingsalesman;
+
+import java.awt.BorderLayout;
+import java.awt.Font;
+import java.awt.event.ActionListener;
+import javax.swing.BorderFactory;
+import javax.swing.JButton;
+import javax.swing.JPanel;
+import javax.swing.JProgressBar;
+import javax.swing.JScrollPane;
+import javax.swing.JTextArea;
+import javax.swing.SwingUtilities;
+
+/**
+ * Panel for controlling the execution of the Travelling Salesman applet.
+ * Contains controls for starting and stopping the route-finding algorithms
+ * and for displaying progress and results.
+ *
+ * <br>
+ * The original code is from <b>the Watchmaker project</b>
+ * (https://watchmaker.dev.java.net/).
+ */
+@SuppressWarnings("serial")
+final class ExecutionPanel extends JPanel implements ProgressListener
+{
+ private final JButton startButton;
+ private final JTextArea output;
+ private final JScrollPane scroller;
+ private final JProgressBar progressBar;
+
+
+ public ExecutionPanel()
+ {
+ super(new BorderLayout());
+ JPanel controlPanel = new JPanel(new BorderLayout());
+ startButton = new JButton("Start");
+ controlPanel.add(startButton, BorderLayout.WEST);
+ progressBar = new JProgressBar(0, 100);
+ controlPanel.add(progressBar, BorderLayout.CENTER);
+ add(controlPanel, BorderLayout.NORTH);
+ output = new JTextArea();
+ output.setEditable(false);
+ output.setLineWrap(true);
+ output.setWrapStyleWord(true);
+ output.setFont(new Font("Monospaced", Font.PLAIN, 12));
+ scroller = new JScrollPane(output);
+ scroller.setBorder(BorderFactory.createTitledBorder("Results"));
+ add(scroller, BorderLayout.CENTER);
+ }
+
+
+ /**
+ * Adds logic to the start button so that something happens when
+ * it is clicked.
+ * @param actionListener The action to perform when the button is
+ * clicked.
+ */
+ public void addActionListener(ActionListener actionListener)
+ {
+ startButton.addActionListener(actionListener);
+ }
+
+
+ /**
+ * Updates the position of the progress bar.
+ */
+ public void updateProgress(final double percentComplete)
+ {
+ SwingUtilities.invokeLater(new Runnable()
+ {
+ public void run()
+ {
+ progressBar.setValue((int) percentComplete);
+ }
+ });
+ }
+
+
+ /**
+ * Appends the specified text to this panel's text area.
+ * @param text The text to append.
+ */
+ public void appendOutput(String text)
+ {
+ output.append(text);
+ }
+
+
+ @Override
+ public void setEnabled(boolean b)
+ {
+ startButton.setEnabled(b);
+ scroller.setEnabled(b);
+ super.setEnabled(b);
+ }
+}
Propchange: lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/ExecutionPanel.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/ItineraryPanel.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/ItineraryPanel.java?rev=681327&view=auto
==============================================================================
--- lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/ItineraryPanel.java (added)
+++ lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/ItineraryPanel.java Thu Jul 31 03:33:45 2008
@@ -0,0 +1,115 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.mahout.ga.watchmaker.travellingsalesman;
+
+import java.awt.BorderLayout;
+import java.awt.GridLayout;
+import java.awt.event.ActionEvent;
+import java.awt.event.ActionListener;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.List;
+import java.util.Set;
+import java.util.TreeSet;
+import javax.swing.BorderFactory;
+import javax.swing.JButton;
+import javax.swing.JCheckBox;
+import javax.swing.JPanel;
+
+/**
+ * Component for selecting which cities are to be visited by the
+ * travelling salesman.
+ *
+ * <br>
+ * The original code is from <b>the Watchmaker project</b>
+ * (https://watchmaker.dev.java.net/).
+ */
+@SuppressWarnings("serial")
+final class ItineraryPanel extends JPanel
+{
+ private final Collection<JCheckBox> checkBoxes;
+ private JButton selectAllButton;
+ private JButton clearButton;
+
+ public ItineraryPanel(List<String> cities)
+ {
+ super(new BorderLayout());
+
+ JPanel checkBoxPanel = new JPanel(new GridLayout(0, 1));
+ checkBoxes = new ArrayList<JCheckBox>(cities.size());
+ for (String city : cities)
+ {
+ JCheckBox checkBox = new JCheckBox(city, false);
+ checkBoxes.add(checkBox);
+ checkBoxPanel.add(checkBox);
+ }
+ add(checkBoxPanel, BorderLayout.CENTER);
+
+ JPanel buttonPanel = new JPanel(new GridLayout(2, 1));
+ selectAllButton = new JButton("Select All");
+ buttonPanel.add(selectAllButton);
+ clearButton = new JButton("Clear Selection");
+ buttonPanel.add(clearButton);
+ ActionListener buttonListener = new ActionListener()
+ {
+
+ public void actionPerformed(ActionEvent actionEvent)
+ {
+ boolean select = actionEvent.getSource() == selectAllButton;
+ for (JCheckBox checkBox : checkBoxes)
+ {
+ checkBox.setSelected(select);
+ }
+ }
+ };
+ selectAllButton.addActionListener(buttonListener);
+ clearButton.addActionListener(buttonListener);
+ add(buttonPanel, BorderLayout.SOUTH);
+
+ setBorder(BorderFactory.createTitledBorder("Itinerary"));
+ }
+
+
+ /**
+ * Returns the cities that have been selected as part of the itinerary.
+ */
+ public Collection<String> getSelectedCities()
+ {
+ Set<String> cities = new TreeSet<String>();
+ for (JCheckBox checkBox : checkBoxes)
+ {
+ if (checkBox.isSelected())
+ {
+ cities.add(checkBox.getText());
+ }
+ }
+ return cities;
+ }
+
+
+ @Override
+ public void setEnabled(boolean b)
+ {
+ for (JCheckBox checkBox : checkBoxes)
+ {
+ checkBox.setEnabled(b);
+ }
+ selectAllButton.setEnabled(b);
+ clearButton.setEnabled(b);
+ super.setEnabled(b);
+ }
+}
Propchange: lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/ItineraryPanel.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/ProgressListener.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/ProgressListener.java?rev=681327&view=auto
==============================================================================
--- lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/ProgressListener.java (added)
+++ lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/ProgressListener.java Thu Jul 31 03:33:45 2008
@@ -0,0 +1,35 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.mahout.ga.watchmaker.travellingsalesman;
+
+/**
+ * Call-back interface for keeping track of the progress of a
+ * {@link TravellingSalesmanStrategy} implementation.
+ *
+ * <br>
+ * The original code is from <b>the Watchmaker project</b>
+ * (https://watchmaker.dev.java.net/).
+ */
+public interface ProgressListener
+{
+ /**
+ * Call-back method that informs the implementing object
+ * of the current completion percentage.
+ * @param percentComplete A percentage between 0 and 100.
+ */
+ void updateProgress(double percentComplete);
+}
Propchange: lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/ProgressListener.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/RouteEvaluator.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/RouteEvaluator.java?rev=681327&view=auto
==============================================================================
--- lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/RouteEvaluator.java (added)
+++ lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/RouteEvaluator.java Thu Jul 31 03:33:45 2008
@@ -0,0 +1,78 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.mahout.ga.watchmaker.travellingsalesman;
+
+import java.util.List;
+import org.uncommons.watchmaker.framework.FitnessEvaluator;
+
+/**
+ * Fitness evalator that measures the total distance of a route in the travelling salesman
+ * problem. The fitness score of a route is the total distance (in km). A route
+ * is represented as a list of cities in the order that they will be visited.
+ * The last leg of the journey is from the last city in the list back to the
+ * first.
+ *
+ * <br>
+ * The original code is from <b>the Watchmaker project</b>
+ * (https://watchmaker.dev.java.net/).
+ */
+public class RouteEvaluator implements FitnessEvaluator<List<String>>
+{
+ private final DistanceLookup distances;
+
+
+ /**
+ * @param distances Provides distances between a set of cities.
+ */
+ public RouteEvaluator(DistanceLookup distances)
+ {
+ this.distances = distances;
+ }
+
+
+ /**
+ * Calculates the length of an evolved route.
+ * @param candidate The route to evaluate.
+ * @param population {@inheritDoc}
+ * @return The total distance (in kilometres) of a journey that visits
+ * each city in order and returns to the starting point.
+ */
+ public double getFitness(List<String> candidate,
+ List<? extends List<String>> population)
+ {
+ int totalDistance = 0;
+ int cityCount = candidate.size();
+ for (int i = 0; i < cityCount; i++)
+ {
+ int nextIndex = i < cityCount - 1 ? i + 1 : 0;
+ totalDistance += distances.getDistance(candidate.get(i),
+ candidate.get(nextIndex));
+ }
+ return totalDistance;
+ }
+
+
+ /**
+ * {@inheritDoc}
+ * Returns false since shorter distances represent fitter candidates.
+ * @return false
+ */
+ public boolean isNatural()
+ {
+ return false;
+ }
+}
Propchange: lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/RouteEvaluator.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/StrategyPanel.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/StrategyPanel.java?rev=681327&view=auto
==============================================================================
--- lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/StrategyPanel.java (added)
+++ lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/StrategyPanel.java Thu Jul 31 03:33:45 2008
@@ -0,0 +1,218 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.mahout.ga.watchmaker.travellingsalesman;
+
+import java.awt.BorderLayout;
+import java.awt.Component;
+import java.awt.FlowLayout;
+import java.awt.event.ItemEvent;
+import java.awt.event.ItemListener;
+import java.util.List;
+
+import javax.swing.BorderFactory;
+import javax.swing.ButtonGroup;
+import javax.swing.DefaultListCellRenderer;
+import javax.swing.JCheckBox;
+import javax.swing.JComboBox;
+import javax.swing.JLabel;
+import javax.swing.JList;
+import javax.swing.JPanel;
+import javax.swing.JRadioButton;
+import javax.swing.JSpinner;
+import javax.swing.SpinnerNumberModel;
+import javax.swing.SpringLayout;
+
+import org.uncommons.swing.SpringUtilities;
+import org.uncommons.watchmaker.framework.SelectionStrategy;
+import org.uncommons.watchmaker.framework.selection.RankSelection;
+import org.uncommons.watchmaker.framework.selection.RouletteWheelSelection;
+import org.uncommons.watchmaker.framework.selection.StochasticUniversalSampling;
+import org.uncommons.watchmaker.framework.selection.TournamentSelection;
+import org.uncommons.watchmaker.framework.selection.TruncationSelection;
+
+/**
+ * Panel for configuring a route-finding strategy for the travelling salesman
+ * problem.
+ *
+ * <br>
+ * The original code is from <b>the Watchmaker project</b>
+ * (https://watchmaker.dev.java.net/).<br>
+ * The <code>EvolutionPanel</code> has been modified to add a "distributed
+ * (mahout)" JCheckBox.
+ */
+@SuppressWarnings("serial")
+final class StrategyPanel extends JPanel {
+ private final SelectionStrategy<?>[] selectionStrategies = {
+ new RankSelection(), new RouletteWheelSelection(),
+ new StochasticUniversalSampling(), new TournamentSelection(0.95d),
+ new TruncationSelection(0.5d) };
+
+ private final DistanceLookup distances;
+
+ private final JRadioButton evolutionOption;
+
+ private final JRadioButton bruteForceOption;
+
+ private final EvolutionPanel evolutionPanel;
+
+ /**
+ * Creates a panel with components for controlling the route-finding strategy.
+ *
+ * @param distances Data used by the strategy in order to calculate shortest
+ * routes.
+ */
+ public StrategyPanel(DistanceLookup distances) {
+ super(new BorderLayout());
+ this.distances = distances;
+ evolutionOption = new JRadioButton("Evolution", true);
+ bruteForceOption = new JRadioButton("Brute Force", false);
+ evolutionOption.addItemListener(new ItemListener() {
+ public void itemStateChanged(ItemEvent itemEvent) {
+ evolutionPanel.setEnabled(evolutionOption.isSelected());
+ }
+ });
+ ButtonGroup strategyGroup = new ButtonGroup();
+ strategyGroup.add(evolutionOption);
+ strategyGroup.add(bruteForceOption);
+ evolutionPanel = new EvolutionPanel();
+ add(evolutionOption, BorderLayout.NORTH);
+ add(evolutionPanel, BorderLayout.CENTER);
+ add(bruteForceOption, BorderLayout.SOUTH);
+ setBorder(BorderFactory.createTitledBorder("Route-Finding Strategy"));
+ }
+
+ public TravellingSalesmanStrategy getStrategy() {
+ if (bruteForceOption.isSelected()) {
+ return new BruteForceTravellingSalesman(distances);
+ } else {
+ return evolutionPanel.getStrategy();
+ }
+ }
+
+ @Override
+ public void setEnabled(boolean b) {
+ evolutionOption.setEnabled(b);
+ bruteForceOption.setEnabled(b);
+ evolutionPanel.setEnabled(b && evolutionOption.isSelected());
+ super.setEnabled(b);
+ }
+
+ /**
+ * Panel of evolution controls.
+ */
+ private final class EvolutionPanel extends JPanel {
+ private final JLabel populationLabel;
+
+ private final JSpinner populationSpinner;
+
+ private final JLabel elitismLabel;
+
+ private final JSpinner elitismSpinner;
+
+ private final JLabel generationsLabel;
+
+ private final JSpinner generationsSpinner;
+
+ private final JLabel selectionLabel;
+
+ private final JComboBox selectionCombo;
+
+ private final JCheckBox crossoverCheckbox;
+
+ private final JCheckBox mutationCheckbox;
+
+ private final JCheckBox distributedCheckbox;
+
+ public EvolutionPanel() {
+ super(new FlowLayout(FlowLayout.LEFT, 0, 0));
+ JPanel innerPanel = new JPanel(new SpringLayout());
+
+ populationLabel = new JLabel("Population Size: ");
+ populationSpinner = new JSpinner(new SpinnerNumberModel(300, 2, 10000, 1));
+ populationLabel.setLabelFor(populationSpinner);
+ innerPanel.add(populationLabel);
+ innerPanel.add(populationSpinner);
+
+ elitismLabel = new JLabel("Elitism: ");
+ elitismSpinner = new JSpinner(new SpinnerNumberModel(3, 0, 10000, 1));
+ elitismLabel.setLabelFor(elitismSpinner);
+ innerPanel.add(elitismLabel);
+ innerPanel.add(elitismSpinner);
+
+ generationsLabel = new JLabel("Number of Generations: ");
+ generationsSpinner = new JSpinner(
+ new SpinnerNumberModel(100, 1, 10000, 1));
+ generationsLabel.setLabelFor(generationsSpinner);
+ innerPanel.add(generationsLabel);
+ innerPanel.add(generationsSpinner);
+
+ selectionLabel = new JLabel("Selection Strategy: ");
+ innerPanel.add(selectionLabel);
+ selectionCombo = new JComboBox(selectionStrategies);
+ selectionCombo.setRenderer(new DefaultListCellRenderer() {
+ @Override
+ public Component getListCellRendererComponent(JList list, Object value,
+ int index, boolean isSelected, boolean hasFocus) {
+ SelectionStrategy<?> strategy = (SelectionStrategy<?>) value;
+ String text = strategy.getClass().getSimpleName();
+ return super.getListCellRendererComponent(list, text, index,
+ isSelected, hasFocus);
+ }
+ });
+ selectionCombo.setSelectedIndex(selectionCombo.getItemCount() - 1);
+ innerPanel.add(selectionCombo);
+
+ crossoverCheckbox = new JCheckBox("Cross-over", true);
+ mutationCheckbox = new JCheckBox("Mutation", true);
+ distributedCheckbox = new JCheckBox("Distributed (Mahout)", false);
+
+ innerPanel.add(crossoverCheckbox);
+ innerPanel.add(mutationCheckbox);
+ innerPanel.add(distributedCheckbox);
+ innerPanel.add(new JLabel()); // pour avoir un nombre paire de components
+
+ SpringUtilities.makeCompactGrid(innerPanel, 6, 2, 30, 6, 6, 6);
+ add(innerPanel);
+ }
+
+ @Override
+ public void setEnabled(boolean b) {
+ populationLabel.setEnabled(b);
+ populationSpinner.setEnabled(b);
+ elitismLabel.setEnabled(b);
+ elitismSpinner.setEnabled(b);
+ generationsLabel.setEnabled(b);
+ generationsSpinner.setEnabled(b);
+ selectionLabel.setEnabled(b);
+ selectionCombo.setEnabled(b);
+ crossoverCheckbox.setEnabled(b);
+ mutationCheckbox.setEnabled(b);
+ distributedCheckbox.setEnabled(b);
+ super.setEnabled(b);
+ }
+
+ @SuppressWarnings("unchecked")
+ public TravellingSalesmanStrategy getStrategy() {
+ return new EvolutionaryTravellingSalesman(distances,
+ (SelectionStrategy<? super List<String>>) selectionCombo
+ .getSelectedItem(), (Integer) populationSpinner.getValue(),
+ (Integer) elitismSpinner.getValue(), (Integer) generationsSpinner
+ .getValue(), crossoverCheckbox.isSelected(), mutationCheckbox
+ .isSelected(), distributedCheckbox.isSelected());
+ }
+ }
+}
Propchange: lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/StrategyPanel.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/TravellingSalesman.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/TravellingSalesman.java?rev=681327&view=auto
==============================================================================
--- lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/TravellingSalesman.java (added)
+++ lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/TravellingSalesman.java Thu Jul 31 03:33:45 2008
@@ -0,0 +1,172 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.mahout.ga.watchmaker.travellingsalesman;
+
+import java.awt.BorderLayout;
+import java.awt.Frame;
+import java.awt.event.ActionEvent;
+import java.awt.event.ActionListener;
+import java.util.Collection;
+import java.util.List;
+
+import javax.swing.JApplet;
+import javax.swing.JDialog;
+import javax.swing.JOptionPane;
+import javax.swing.JPanel;
+
+import org.uncommons.swing.SwingBackgroundTask;
+import org.uncommons.watchmaker.framework.FitnessEvaluator;
+
+/**
+ * Applet for comparing evolutionary and brute force approaches to the
+ * Travelling Salesman problem.
+ *
+ * The original code is from <b>the Watchmaker project</b>
+ * (https://watchmaker.dev.java.net/). <br>
+ * This class has been modified to add a main function that runs the JApplet
+ * inside a JDialog.
+ */
+@SuppressWarnings("serial")
+public final class TravellingSalesman extends JApplet {
+ private final ItineraryPanel itineraryPanel;
+
+ private final StrategyPanel strategyPanel;
+
+ private final ExecutionPanel executionPanel;
+
+ private final FitnessEvaluator<List<String>> evaluator;
+
+ /**
+ * Creates the applet and lays out its GUI.
+ */
+ public TravellingSalesman() {
+ DistanceLookup distances = new EuropeanDistanceLookup();
+ evaluator = new RouteEvaluator(distances);
+ itineraryPanel = new ItineraryPanel(distances.getKnownCities());
+ strategyPanel = new StrategyPanel(distances);
+ executionPanel = new ExecutionPanel();
+ add(itineraryPanel, BorderLayout.WEST);
+ JPanel innerPanel = new JPanel(new BorderLayout());
+ innerPanel.add(strategyPanel, BorderLayout.NORTH);
+ innerPanel.add(executionPanel, BorderLayout.CENTER);
+ add(innerPanel, BorderLayout.CENTER);
+
+ executionPanel.addActionListener(new ActionListener() {
+ public void actionPerformed(ActionEvent actionEvent) {
+ Collection<String> cities = itineraryPanel.getSelectedCities();
+ if (cities.size() < 4) {
+ JOptionPane.showMessageDialog(TravellingSalesman.this,
+ "Itinerary must include at least 4 cities.", "Error",
+ JOptionPane.ERROR_MESSAGE);
+ } else {
+ try {
+ setEnabled(false);
+ createTask(cities).execute();
+ } catch (IllegalArgumentException ex) {
+ JOptionPane.showMessageDialog(TravellingSalesman.this, ex
+ .getMessage(), "Error", JOptionPane.ERROR_MESSAGE);
+ setEnabled(true);
+ }
+ }
+ }
+ });
+ validate();
+ }
+
+ /**
+ * Helper method to create a background task for running the travelling
+ * salesman algorithm.
+ *
+ * @param cities The set of cities to generate a route for.
+ * @return A Swing task that will execute on a background thread and update
+ * the GUI when it is done.
+ */
+ private SwingBackgroundTask<List<String>> createTask(
+ final Collection<String> cities) {
+ final TravellingSalesmanStrategy strategy = strategyPanel.getStrategy();
+ return new SwingBackgroundTask<List<String>>() {
+ private long elapsedTime = 0;
+
+ protected List<String> performTask() {
+ long startTime = System.currentTimeMillis();
+ List<String> result = strategy.calculateShortestRoute(cities,
+ executionPanel);
+ elapsedTime = System.currentTimeMillis() - startTime;
+ return result;
+ }
+
+ protected void postProcessing(List<String> result) {
+ executionPanel.appendOutput(createResultString(strategy
+ .getDescription(), result, evaluator.getFitness(result, null),
+ elapsedTime));
+ setEnabled(true);
+ }
+ };
+ }
+
+ /**
+ * Helper method for formatting a result as a string for display.
+ */
+ private String createResultString(String strategyDescription,
+ List<String> shortestRoute, double distance, long elapsedTime) {
+ StringBuilder buffer = new StringBuilder();
+ buffer.append('[');
+ buffer.append(strategyDescription);
+ buffer.append("]\n");
+ buffer.append("ROUTE: ");
+ for (String s : shortestRoute) {
+ buffer.append(s);
+ buffer.append(" -> ");
+ }
+ buffer.append(shortestRoute.get(0));
+ buffer.append('\n');
+ buffer.append("TOTAL DISTANCE: ");
+ buffer.append(String.valueOf(distance));
+ buffer.append("km\n");
+ buffer.append("(Search Time: ");
+ double seconds = (double) elapsedTime / 1000;
+ buffer.append(String.valueOf(seconds));
+ buffer.append(" seconds)\n\n");
+ return buffer.toString();
+ }
+
+ /**
+ * Toggles whether the controls are enabled for input or not.
+ *
+ * @param b Enables the controls if this flag is true, disables them
+ * otherwise.
+ */
+ @Override
+ public void setEnabled(boolean b) {
+ itineraryPanel.setEnabled(b);
+ strategyPanel.setEnabled(b);
+ executionPanel.setEnabled(b);
+ super.setEnabled(b);
+ }
+
+ public static void main(String[] args) {
+ JDialog dialog = new JDialog((Frame) null, "Travelling Salesman Frame",
+ true);
+ dialog.setDefaultCloseOperation(JDialog.DISPOSE_ON_CLOSE);
+
+ dialog.getContentPane().add(new TravellingSalesman());
+ dialog.pack();
+ dialog.setLocationRelativeTo(null);
+
+ dialog.setVisible(true);
+ }
+}
Propchange: lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/TravellingSalesman.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/TravellingSalesmanStrategy.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/TravellingSalesmanStrategy.java?rev=681327&view=auto
==============================================================================
--- lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/TravellingSalesmanStrategy.java (added)
+++ lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/TravellingSalesmanStrategy.java Thu Jul 31 03:33:45 2008
@@ -0,0 +1,48 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.mahout.ga.watchmaker.travellingsalesman;
+
+import java.util.Collection;
+import java.util.List;
+
+/**
+ * Defines methods that must be implemented by classes that provide solutions to
+ * the Travelling Salesman problem.
+ *
+ * <br>
+ * The original code is from <b>the Watchmaker project</b>
+ * (https://watchmaker.dev.java.net/).
+ */
+public interface TravellingSalesmanStrategy {
+ /**
+ * @return A description of the strategy.
+ */
+ String getDescription();
+
+ /**
+ * Calculates the shortest round trip distance that visits each of the
+ * specified cities once and returns to the starting point.
+ *
+ * @param cities The destination that must each be visited for the route to be
+ * valid.
+ * @param progressListener A call-back for keeping track of the route-finding
+ * algorithm's progress.
+ * @return The shortest route found for the given list of destinations.
+ */
+ List<String> calculateShortestRoute(Collection<String> cities,
+ ProgressListener progressListener);
+}
Propchange: lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/TravellingSalesmanStrategy.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/package-info.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/package-info.java?rev=681327&view=auto
==============================================================================
--- lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/package-info.java (added)
+++ lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/package-info.java Thu Jul 31 03:33:45 2008
@@ -0,0 +1,26 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+/**
+ * An evolutionary approach to tackling the well-known Travelling Salesman
+ * problem.
+ *
+ * <br>
+ * The original code is from <b>the Watchmaker project</b>
+ * (https://watchmaker.dev.java.net/).
+ */
+package org.apache.mahout.ga.watchmaker.travellingsalesman;
Propchange: lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/package-info.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/readme.txt
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/readme.txt?rev=681327&view=auto
==============================================================================
--- lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/readme.txt (added)
+++ lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/readme.txt Thu Jul 31 03:33:45 2008
@@ -0,0 +1,15 @@
+This example shows how it's easy to adapt an existing Watchmaker program to use Mahout.
+
+The original code is from the Watchmaker Travelling Salesman example (https://watchmaker.dev.java.net/).
+
+Nearly all the files are the same as in the original code, the only modifications are:
+
+. StrategyPanel.java : EvolutionPanel class has been modified to add a "distributed (mahout)" JCheckBox.
+
+. TravellingSalesman.java : (originally TravellingSalesmanApplet.java) has been modified to add a main
+ method that runs the JApplet inside a modal JDialog, this way Hadoop waits until the Dialog is closed
+ to terminate.
+
+. EvolutionaryTravellingSalesman.java : has been modified to use Mahout whenever requested by the GUI
+ (when the mahout checkbox is checked). To use Mahout we start by wrapping the original FitnessEvaluator
+ inside a STFitnessEvaluator, and the pass it to a STEvolutionEngine, instead of a StandaloneEngine.
Propchange: lucene/mahout/trunk/core/src/main/examples/org/apache/mahout/ga/watchmaker/travellingsalesman/readme.txt
------------------------------------------------------------------------------
svn:eol-style = native
Added: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/ga/watchmaker/EvalMapper.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/ga/watchmaker/EvalMapper.java?rev=681327&view=auto
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/ga/watchmaker/EvalMapper.java (added)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/ga/watchmaker/EvalMapper.java Thu Jul 31 03:33:45 2008
@@ -0,0 +1,72 @@
+package org.apache.mahout.ga.watchmaker;
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+import java.io.IOException;
+
+import org.apache.hadoop.io.FloatWritable;
+import org.apache.hadoop.io.LongWritable;
+import org.apache.hadoop.io.Text;
+import org.apache.hadoop.mapred.JobConf;
+import org.apache.hadoop.mapred.MapReduceBase;
+import org.apache.hadoop.mapred.Mapper;
+import org.apache.hadoop.mapred.OutputCollector;
+import org.apache.hadoop.mapred.Reporter;
+import org.apache.mahout.utils.StringUtils;
+import org.uncommons.watchmaker.framework.FitnessEvaluator;
+
+/**
+ * <p>
+ * Generic Mapper class for fitness evaluation. Works with the following :
+ * <code><key, candidate, key, fitness></code>, where :
+ * </p>
+ * key: position of the current candidate in the input file. <br>
+ * candidate: candidate solution to evaluate. <br>
+ * fitness: evaluated fitness for the given candidate.
+ */
+public class EvalMapper extends MapReduceBase implements
+ Mapper<LongWritable, Text, LongWritable, FloatWritable> {
+
+ /** Parameter used to store the "stringified" evaluator */
+ public static final String MAHOUT_GA_EVALUATOR = "mahout.ga.evaluator";
+
+ private FitnessEvaluator evaluator = null;
+
+ @Override
+ public void configure(JobConf job) {
+ String evlstr = job.get(EvalMapper.MAHOUT_GA_EVALUATOR);
+ if (evlstr == null) {
+ throw new RuntimeException(
+ "'MAHOUT_GA_EVALUATOR' job parameter non found");
+ }
+
+ evaluator = (FitnessEvaluator) StringUtils.fromString(evlstr);
+
+ super.configure(job);
+ }
+
+ public void map(LongWritable key, Text value,
+ OutputCollector<LongWritable, FloatWritable> output, Reporter reporter)
+ throws IOException {
+ Object candidate = StringUtils.fromString(value.toString());
+
+ double fitness = evaluator.getFitness(candidate, null);
+
+ output.collect(key, new FloatWritable((float) fitness));
+ }
+
+}
Propchange: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/ga/watchmaker/EvalMapper.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/ga/watchmaker/MahoutEvaluator.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/ga/watchmaker/MahoutEvaluator.java?rev=681327&view=auto
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/ga/watchmaker/MahoutEvaluator.java (added)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/ga/watchmaker/MahoutEvaluator.java Thu Jul 31 03:33:45 2008
@@ -0,0 +1,143 @@
+package org.apache.mahout.ga.watchmaker;
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+import java.io.BufferedWriter;
+import java.io.IOException;
+import java.io.OutputStreamWriter;
+import java.util.List;
+
+import org.apache.hadoop.fs.FSDataOutputStream;
+import org.apache.hadoop.fs.FileSystem;
+import org.apache.hadoop.fs.Path;
+import org.apache.hadoop.io.FloatWritable;
+import org.apache.hadoop.io.LongWritable;
+import org.apache.hadoop.mapred.JobClient;
+import org.apache.hadoop.mapred.JobConf;
+import org.apache.hadoop.mapred.SequenceFileOutputFormat;
+import org.apache.hadoop.mapred.TextInputFormat;
+import org.apache.mahout.utils.StringUtils;
+import org.uncommons.watchmaker.framework.FitnessEvaluator;
+
+/**
+ * Generic Mahout distributed evaluator. takes an evaluator and a population and
+ * launches a Hadoop job. The job evaluates the fitness of each individual of the
+ * population using the given evaluator. Takes care of storing the population
+ * into an input file, and loading the fitness from job outputs.
+ *
+ */
+public class MahoutEvaluator {
+
+ /**
+ * Uses Mahout to evaluate every candidate from the input population using the
+ * given evaluator.
+ *
+ * @param evaluator FitnessEvaluator to use
+ * @param population input population
+ * @param evaluations <code>List<Float></code> that contains the
+ * evaluated fitness for each candidate from the input population,
+ * sorted in the same order as the candidates.
+ * @throws IOException
+ */
+ public static void evaluate(FitnessEvaluator evaluator, List population,
+ List<Float> evaluations) throws IOException {
+ JobConf conf = new JobConf(MahoutEvaluator.class);
+ FileSystem fs = FileSystem.get(conf);
+
+ Path inpath = prepareInput(fs, population);
+ Path outpath = OutputUtils.prepareOutput(fs);
+
+ configureJob(conf, evaluator, inpath, outpath);
+ JobClient.runJob(conf);
+
+ OutputUtils.importEvaluations(fs, conf, outpath, evaluations);
+ }
+
+ /**
+ * Create the input directory and stores the population in it.
+ *
+ * @param fs <code>FileSystem</code> to use
+ * @param population population to store
+ * @return input <code>Path</code>
+ *
+ * @throws IOException
+ */
+ private static Path prepareInput(FileSystem fs, List population)
+ throws IOException {
+ Path inpath = new Path(fs.getWorkingDirectory(), "input");
+
+ if (!fs.exists(inpath)) {
+ fs.mkdirs(inpath);
+ }
+
+ storePopulation(fs, new Path(inpath, "population"), population);
+
+ return inpath;
+ }
+
+ /**
+ * Configure the job
+ *
+ * @param conf
+ * @param evaluator FitnessEvaluator passed to the mapper
+ * @param inpath input <code>Path</code>
+ * @param outpath output <code>Path</code>
+ */
+ private static void configureJob(JobConf conf, FitnessEvaluator evaluator,
+ Path inpath, Path outpath) {
+ TextInputFormat.setInputPaths(conf, inpath);
+ SequenceFileOutputFormat.setOutputPath(conf, outpath);
+
+ conf.setOutputKeyClass(LongWritable.class);
+ conf.setOutputValueClass(FloatWritable.class);
+
+ conf.setMapperClass(EvalMapper.class);
+ // no combiner
+ // identity reducer
+ // TODO do we really need a reducer at all ?
+
+ conf.setInputFormat(TextInputFormat.class);
+ conf.setOutputFormat(SequenceFileOutputFormat.class);
+
+ // store the stringified evaluator
+ conf.set(EvalMapper.MAHOUT_GA_EVALUATOR, StringUtils.toString(evaluator));
+ }
+
+ /**
+ * Stores a population of candidates in the output file path.
+ *
+ * @param fs FileSystem used to create the output file
+ * @param outFile output file path
+ * @param population population to store
+ * @throws IOException
+ */
+ static void storePopulation(FileSystem fs, Path f, List population)
+ throws IOException {
+ FSDataOutputStream out = fs.create(f);
+ BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(out));
+
+ try {
+ for (Object candidate : population) {
+ writer.write(StringUtils.toString(candidate));
+ writer.newLine();
+ }
+ } finally {
+ writer.close();
+ }
+ }
+
+}
Propchange: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/ga/watchmaker/MahoutEvaluator.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/ga/watchmaker/MahoutFitnessEvaluator.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/ga/watchmaker/MahoutFitnessEvaluator.java?rev=681327&view=auto
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/ga/watchmaker/MahoutFitnessEvaluator.java (added)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/ga/watchmaker/MahoutFitnessEvaluator.java Thu Jul 31 03:33:45 2008
@@ -0,0 +1,51 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.mahout.ga.watchmaker;
+
+import java.io.IOException;
+import java.util.List;
+
+import org.uncommons.watchmaker.framework.FitnessEvaluator;
+
+/**
+ * Watchmaker compatible Fitness Evaluator that delegates the evaluation of the
+ * whole population to Mahout.
+ */
+public class MahoutFitnessEvaluator<T> extends STFitnessEvaluator<T> {
+
+ private final FitnessEvaluator<? super T> evaluator;
+
+ public MahoutFitnessEvaluator(FitnessEvaluator<? super T> evaluator) {
+ this.evaluator = evaluator;
+ }
+
+ @Override
+ protected void evaluate(List<? extends T> population, List<Float> evaluations) {
+ try {
+ MahoutEvaluator.evaluate(evaluator, population, evaluations);
+ } catch (IOException e) {
+ new RuntimeException("Exception while evaluating the population", e);
+ }
+ }
+
+ @Override
+ public boolean isNatural() {
+ return evaluator.isNatural();
+ }
+
+}
Propchange: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/ga/watchmaker/MahoutFitnessEvaluator.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/ga/watchmaker/OutputUtils.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/ga/watchmaker/OutputUtils.java?rev=681327&view=auto
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/ga/watchmaker/OutputUtils.java (added)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/ga/watchmaker/OutputUtils.java Thu Jul 31 03:33:45 2008
@@ -0,0 +1,111 @@
+package org.apache.mahout.ga.watchmaker;
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+
+import org.apache.hadoop.fs.FileStatus;
+import org.apache.hadoop.fs.FileSystem;
+import org.apache.hadoop.fs.FileUtil;
+import org.apache.hadoop.fs.Path;
+import org.apache.hadoop.io.FloatWritable;
+import org.apache.hadoop.io.LongWritable;
+import org.apache.hadoop.io.SequenceFile.Reader;
+import org.apache.hadoop.io.SequenceFile.Sorter;
+import org.apache.hadoop.mapred.JobConf;
+
+/**
+ * Utility Class that deals with the output.
+ */
+public class OutputUtils {
+
+ /**
+ * Removes the output directory if it already exists.
+ *
+ * @param fs <code>FileSystem</code> to use
+ * @return output <code>Path</code>
+ *
+ * @throws IOException
+ */
+ public static Path prepareOutput(FileSystem fs) throws IOException {
+ Path outpath = new Path(fs.getWorkingDirectory(), "output");
+
+ if (fs.exists(outpath)) {
+ FileUtil.fullyDelete(fs, outpath);
+ }
+
+ return outpath;
+ }
+
+ /**
+ * Lists all files in the output <code>Path</code>
+ *
+ * @param fs <code>FileSystem</code> to use
+ * @param outpath output <code>Path</code>
+ * @return <code>Path</code> array
+ * @throws IOException
+ */
+ public static Path[] listOutputFiles(FileSystem fs, Path outpath)
+ throws IOException {
+ FileStatus[] status = fs.listStatus(outpath);
+ List<Path> outpaths = new ArrayList<Path>();
+ for (FileStatus s : status) {
+ if (!s.isDir()) {
+ outpaths.add(s.getPath());
+ }
+ }
+
+ Path[] outfiles = new Path[outpaths.size()];
+ outpaths.toArray(outfiles);
+
+ return outfiles;
+ }
+
+ /**
+ * Reads back the evaluations.
+ *
+ * @param fs
+ * @param conf
+ * @param outpath output <code>Path</code>
+ * @param evaluations List of evaluations
+ * @throws IOException
+ */
+ public static void importEvaluations(FileSystem fs, JobConf conf,
+ Path outpath, List<Float> evaluations) throws IOException {
+ Sorter sorter = new Sorter(fs, LongWritable.class, FloatWritable.class,
+ conf);
+
+ // merge and sort the outputs
+ Path[] outfiles = listOutputFiles(fs, outpath);
+ Path output = new Path(outpath, "output.sorted");
+ sorter.merge(outfiles, output);
+
+ // import the evaluations
+ LongWritable key = new LongWritable();
+ FloatWritable value = new FloatWritable();
+ Reader reader = new Reader(fs, output, conf);
+
+ while (reader.next(key, value)) {
+ evaluations.add(value.get());
+ }
+
+ reader.close();
+ }
+
+}
Propchange: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/ga/watchmaker/OutputUtils.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/ga/watchmaker/STEvolutionEngine.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/ga/watchmaker/STEvolutionEngine.java?rev=681327&view=auto
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/ga/watchmaker/STEvolutionEngine.java (added)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/ga/watchmaker/STEvolutionEngine.java Thu Jul 31 03:33:45 2008
@@ -0,0 +1,74 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.mahout.ga.watchmaker;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.List;
+import java.util.Random;
+
+import org.uncommons.watchmaker.framework.AbstractEvolutionEngine;
+import org.uncommons.watchmaker.framework.CandidateFactory;
+import org.uncommons.watchmaker.framework.EvaluatedCandidate;
+import org.uncommons.watchmaker.framework.EvolutionaryOperator;
+import org.uncommons.watchmaker.framework.SelectionStrategy;
+
+/**
+ * Single Threaded Evolution Engine.
+ */
+public class STEvolutionEngine<T> extends AbstractEvolutionEngine<T> {
+
+ public STEvolutionEngine(CandidateFactory<T> candidateFactory,
+ EvolutionaryOperator<? super T> evolutionScheme,
+ STFitnessEvaluator<? super T> fitnessEvaluator,
+ SelectionStrategy<? super T> selectionStrategy, Random rng) {
+ super(candidateFactory, evolutionScheme, fitnessEvaluator,
+ selectionStrategy, rng);
+ }
+
+ /**
+ *
+ * @see org.uncommons.watchmaker.framework.AbstractEvolutionEngine#evaluatePopulation(java.util.List)
+ */
+ @Override
+ protected List<EvaluatedCandidate<T>> evaluatePopulation(List<T> population) {
+ List<Float> evaluations = new ArrayList<Float>();
+ STFitnessEvaluator<? super T> evaluator = (STFitnessEvaluator<? super T>) getFitnessEvaluator();
+
+ evaluator.evaluate(population, evaluations);
+
+ List<EvaluatedCandidate<T>> evaluatedPopulation = new ArrayList<EvaluatedCandidate<T>>();
+ for (int index = 0; index < population.size(); index++) {
+ evaluatedPopulation.add(new EvaluatedCandidate<T>(population.get(index),
+ evaluations.get(index)));
+ }
+
+ // Sort candidates in descending order according to fitness.
+ if (getFitnessEvaluator().isNatural()) // Descending values for natural fitness.
+ {
+ Collections.sort(evaluatedPopulation, Collections.reverseOrder());
+ }
+ else // Ascending values for non-natural fitness.
+ {
+ Collections.sort(evaluatedPopulation);
+ }
+
+ return evaluatedPopulation;
+ }
+
+}
Propchange: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/ga/watchmaker/STEvolutionEngine.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/ga/watchmaker/STFitnessEvaluator.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/ga/watchmaker/STFitnessEvaluator.java?rev=681327&view=auto
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/ga/watchmaker/STFitnessEvaluator.java (added)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/ga/watchmaker/STFitnessEvaluator.java Thu Jul 31 03:33:45 2008
@@ -0,0 +1,60 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.mahout.ga.watchmaker;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import org.uncommons.watchmaker.framework.FitnessEvaluator;
+
+/**
+ * Special Fitness Evaluator that evaluates all the population ones.
+ */
+public abstract class STFitnessEvaluator<T> implements FitnessEvaluator<T> {
+
+ private List<Float> evaluations = new ArrayList<Float>();
+
+ private List<? extends T> population;
+
+ public double getFitness(T candidate, List<? extends T> population) {
+ // evaluate the population, when needed
+ if (this.population == null || this.population != population) {
+ evaluations.clear();
+ evaluate(population, evaluations);
+ this.population = population;
+ }
+
+ int index = population.indexOf(candidate);
+ if (index == -1)
+ throw new RuntimeException("Candidate is not part of the population");
+
+ return evaluations.get(index);
+ }
+
+ /**
+ *
+ * @param population
+ * @param evaluations
+ * @return
+ */
+ protected abstract void evaluate(List<? extends T> population,
+ List<Float> evaluations);
+
+ public abstract boolean isNatural();
+
+}
Propchange: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/ga/watchmaker/STFitnessEvaluator.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/utils/StringUtils.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/utils/StringUtils.java?rev=681327&view=auto
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/utils/StringUtils.java (added)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/utils/StringUtils.java Thu Jul 31 03:33:45 2008
@@ -0,0 +1,50 @@
+package org.apache.mahout.utils;
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+import com.thoughtworks.xstream.XStream;
+
+/**
+ * offers two methods to convert an object to a string representation and
+ * restore the object given its string representation. Should use Hadoop
+ * Stringifier whenever available.
+ *
+ */
+public class StringUtils {
+
+ private static XStream xstream = new XStream();
+
+ /**
+ * Converts the object to a one-line string representation
+ *
+ * @param obj the object to convert
+ * @return the string representation of the object
+ */
+ public static String toString(Object obj) {
+ return xstream.toXML(obj).replaceAll("\n", "");
+ }
+
+ /**
+ * Restores the object from its string representation.
+ *
+ * @param str the string representation of the object
+ * @return restored object
+ */
+ public static Object fromString(String str) {
+ return xstream.fromXML(str);
+ }
+}
Propchange: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/utils/StringUtils.java
------------------------------------------------------------------------------
svn:eol-style = native