Changeset 7786 for branches/ScatterSearch/HeuristicLab.Algorithms.ScatterSearch/3.3/ScatterSearch.cs

Timestamp:

05/09/12 12:22:33 (12 years ago)

Author:

jkarder

Message:

#1331:

• fixed bug in path relinking selection
• fixed bug in ScatterSearch.Prepare()
• added custom interface (IImprovementOperator) for Scatter Search specific improvement operators
• switched from diversity calculation to similarity calculation
• separated IPathRelinker from ICrossover
• changed TestFunctionsImprovementOperator to use reflection for evaluating functions
• changed SolutionPoolUpdateMethod to use similarity calculation for solution comparison
• improved TravelingSalesmanImprovementOperator
• improved operator graph
• removed specific operators used to evaluate TestFunctions problems
• removed custom crossover operator (NChildCrossover)
• added parameters and adjusted types
• adjusted event handling
• changed access levels
• minor code improvements

File:

• branches/ScatterSearch/HeuristicLab.Algorithms.ScatterSearch/3.3/ScatterSearch.cs (modified) (18 diffs)

branches/ScatterSearch/HeuristicLab.Algorithms.ScatterSearch/3.3/ScatterSearch.cs

@@ -31 +31 @@
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.PluginInfrastructure;
 using HeuristicLab.Random;
 using HeuristicLab.Selection;
@@ -61 +62 @@
       get { return (ConstrainedValueParameter<ICrossover>)Parameters["Crossover"]; }
     }
-    public ConstrainedValueParameter<ILocalImprovementOperator> ImproverParameter {
-      get { return (ConstrainedValueParameter<ILocalImprovementOperator>)Parameters["Improver"]; }
-    }
-    public ConstrainedValueParameter<DiversityCalculator> DiversityCalculatorParameter {
-      get { return (ConstrainedValueParameter<DiversityCalculator>)Parameters["DiversityCalculator"]; }
+    public IValueParameter<BoolValue> ExecutePathRelinkingParameter {
+      get { return (IValueLookupParameter<BoolValue>)Parameters["ExecutePathRelinking"]; }
+    }
+    public ConstrainedValueParameter<IImprovementOperator> ImproverParameter {
+      get { return (ConstrainedValueParameter<IImprovementOperator>)Parameters["Improver"]; }
     }
     public IValueParameter<IntValue> MaximumIterationsParameter {
@@ -73 +74 @@
       get { return (IValueParameter<IntValue>)Parameters["NumberOfHighQualitySolutions"]; }
     }
+    public ConstrainedValueParameter<IPathRelinker> PathRelinkerParameter {
+      get { return (ConstrainedValueParameter<IPathRelinker>)Parameters["PathRelinker"]; }
+    }
     public IValueParameter<IntValue> PopulationSizeParameter {
       get { return (IValueParameter<IntValue>)Parameters["PopulationSize"]; }
@@ -84 +88 @@
     public IValueParameter<BoolValue> SetSeedRandomlyParameter {
       get { return (IValueParameter<BoolValue>)Parameters["SetSeedRandomly"]; }
+    }
+    public ConstrainedValueParameter<SimilarityCalculator> SimilarityCalculatorParameter {
+      get { return (ConstrainedValueParameter<SimilarityCalculator>)Parameters["SimilarityCalculator"]; }
     }
     #endregion
@@ -96 +103 @@
       set { CrossoverParameter.Value = value; }
     }
-    private ILocalImprovementOperator Improver {
+    private BoolValue ExecutePathRelinking {
+      get { return ExecutePathRelinkingParameter.Value; }
+      set { ExecutePathRelinkingParameter.Value = value; }
+    }
+    private IImprovementOperator Improver {
       get { return ImproverParameter.Value; }
       set { ImproverParameter.Value = value; }
-    }
-    private DiversityCalculator DiversityCalculator {
-      get { return DiversityCalculatorParameter.Value; }
-      set { DiversityCalculatorParameter.Value = value; }
     }
     private IntValue MaximumIterations {
@@ -112 +119 @@
       set { NumberOfHighQualitySolutionsParameter.Value = value; }
     }
+    private IPathRelinker PathRelinker {
+      get { return PathRelinkerParameter.Value; }
+      set { PathRelinkerParameter.Value = value; }
+    }
     private IntValue PopulationSize {
       get { return PopulationSizeParameter.Value; }
@@ -128 +139 @@
       set { SetSeedRandomlyParameter.Value = value; }
     }
-    public RandomCreator RandomCreator {
+    private SimilarityCalculator SimilarityCalculator {
+      get { return SimilarityCalculatorParameter.Value; }
+      set { SimilarityCalculatorParameter.Value = value; }
+    }
+    private RandomCreator RandomCreator {
       get { return (RandomCreator)OperatorGraph.InitialOperator; }
     }
-    public SolutionsCreator SolutionsCreator {
+    private SolutionsCreator SolutionsCreator {
       get { return (SolutionsCreator)RandomCreator.Successor; }
     }
-    public ScatterSearchMainLoop MainLoop {
+    private ScatterSearchMainLoop MainLoop {
       get { return FindMainLoop(SolutionsCreator.Successor); }
     }
@@ -159 +174 @@
       : base() {
       #region Create parameters
-      Parameters.Add(new ValueParameter<MultiAnalyzer>("Analyzer", "The operator used to analyze the solution and moves.", new MultiAnalyzer()));
-      Parameters.Add(new ConstrainedValueParameter<ICrossover>("Crossover", "The operator used to combine solutions."));
-      Parameters.Add(new ConstrainedValueParameter<ILocalImprovementOperator>("Improver", "The operator used to improve solutions."));
-      Parameters.Add(new ConstrainedValueParameter<DiversityCalculator>("DiversityCalculator", "The operator used to calculate the diversity of two solutions."));
-      Parameters.Add(new ValueParameter<IntValue>("MaximumIterations", "The maximum number of generations which should be processed.", new IntValue(100)));
-      Parameters.Add(new ValueParameter<IntValue>("NumberOfHighQualitySolutions", "The number of high quality solutions that should be added to the reference set.", new IntValue(10)));
-      Parameters.Add(new ValueParameter<IntValue>("PopulationSize", "The size of the population.", new IntValue(300)));
-      Parameters.Add(new ValueParameter<IntValue>("ReferenceSetSize", "The size of the reference set.", new IntValue(100)));
-      Parameters.Add(new ValueParameter<IntValue>("Seed", "The random seed used to initialize the new pseudo random number generator.", new IntValue(0)));
-      Parameters.Add(new ValueParameter<BoolValue>("SetSeedRandomly", "True if the random seed should be set to a random value, otherwise false.", new BoolValue(true)));
+      Parameters.Add(new ValueParameter<MultiAnalyzer>("Analyzer", new MultiAnalyzer()));
+      Parameters.Add(new ConstrainedValueParameter<ICrossover>("Crossover"));
+      Parameters.Add(new ValueParameter<BoolValue>("ExecutePathRelinking", new BoolValue(true)));
+      Parameters.Add(new ConstrainedValueParameter<IImprovementOperator>("Improver"));
+      Parameters.Add(new ValueParameter<IntValue>("MaximumIterations", new IntValue(100)));
+      Parameters.Add(new ValueParameter<IntValue>("NumberOfHighQualitySolutions", new IntValue(10)));
+      Parameters.Add(new ConstrainedValueParameter<IPathRelinker>("PathRelinker"));
+      Parameters.Add(new ValueParameter<IntValue>("PopulationSize", new IntValue(300)));
+      Parameters.Add(new ValueParameter<IntValue>("ReferenceSetSize", new IntValue(100)));
+      Parameters.Add(new ValueParameter<IntValue>("Seed", new IntValue(0)));
+      Parameters.Add(new ValueParameter<BoolValue>("SetSeedRandomly", new BoolValue(true)));
+      Parameters.Add(new ConstrainedValueParameter<SimilarityCalculator>("SimilarityCalculator"));
       #endregion
 
@@ -178 +195 @@
       Placeholder solutionImprover = new Placeholder();
       BestSelector bestSelector = new BestSelector();
-      VariableCreator variableCreator = new VariableCreator();
-      ResultsCollector resultsCollector = new ResultsCollector();
       ScatterSearchMainLoop mainLoop = new ScatterSearchMainLoop();
       #endregion
@@ -207 +222 @@
       bestSelector.NumberOfSelectedSubScopesParameter.ActualName = NumberOfHighQualitySolutionsParameter.Name;
       bestSelector.CopySelected = new BoolValue(false);
-      bestSelector.Successor = variableCreator;
-
-      variableCreator.CollectedValues.Add(new ValueParameter<IntValue>("Iterations", new IntValue(0)));
-      variableCreator.CollectedValues.Add(new ValueParameter<BoolValue>("NewSolutions", new BoolValue(false)));
-      variableCreator.Successor = resultsCollector;
-
-      resultsCollector.CollectedValues.Add(new LookupParameter<IntValue>("Iterations"));
-      resultsCollector.ResultsParameter.ActualName = "Results";
-      resultsCollector.Successor = mainLoop;
+      bestSelector.Successor = mainLoop;
 
       mainLoop.MaximumIterationsParameter.ActualName = MaximumIterationsParameter.Name;
@@ -236 +243 @@
 
     public override void Prepare() {
-      base.Prepare();
+      if (Problem != null) base.Prepare();
     }
 
@@ -249 +256 @@
       UpdateAnalyzers();
       UpdateCrossovers();
-      UpdateDiversityCalculators();
+      UpdatePathRelinkers();
+      UpdateSimilarityCalculators();
       UpdateImprovers();
-      UpdateDiversityCalculators();
+      UpdateSimilarityCalculators();
       Problem.Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
       base.OnProblemChanged();
@@ -272 +280 @@
       UpdateAnalyzers();
       UpdateCrossovers();
-      UpdateDiversityCalculators();
+      UpdatePathRelinkers();
+      UpdateSimilarityCalculators();
       UpdateImprovers();
       ParameterizeMainLoop();
@@ -306 +315 @@
       ICrossover defaultCrossover = Problem.Operators.OfType<ICrossover>().FirstOrDefault();
 
-      CrossoverParameter.ValidValues.Add(new Knapsack.KnapsackPathRelinker());
-      CrossoverParameter.ValidValues.Add(new Knapsack.KnapsackSimultaneousPathRelinker());
-      CrossoverParameter.ValidValues.Add(new TestFunctions.TestFunctionsPathRelinker());
-      CrossoverParameter.ValidValues.Add(new TravelingSalesman.TravelingSalesmanPathRelinker());
-      CrossoverParameter.ValidValues.Add(new TravelingSalesman.TravelingSalesmanSimultaneousPathRelinker());
-      CrossoverParameter.ValidValues.Add(new TravelingSalesman.TravelingSalesmanMultipleGuidesPathRelinker());
-
       foreach (ICrossover crossover in Problem.Operators.OfType<ICrossover>().OrderBy(x => x.Name))
         CrossoverParameter.ValidValues.Add(crossover);
-
-      foreach (var crossover in CrossoverParameter.ValidValues.OfType<Knapsack.INBinaryVectorCrossover>())
-        crossover.ParentsParameter.ActualName = "KnapsackSolution"; // temporary solution for the knapsack problem
 
       if (oldCrossover != null) {
@@ -327 +326 @@
         CrossoverParameter.Value = defaultCrossover;
     }
-    private void UpdateDiversityCalculators() {
-      DiversityCalculator oldDiversityCalculator = DiversityCalculatorParameter.Value;
-      DiversityCalculatorParameter.ValidValues.Clear();
-      DiversityCalculator defaultDiversityCalculator = Problem.Operators.OfType<DiversityCalculator>().FirstOrDefault();
-
-      DiversityCalculatorParameter.ValidValues.Add(new Knapsack.BinaryVectorDiversityCalculator());
-      DiversityCalculatorParameter.ValidValues.Add(new TestFunctions.RealVectorDiversityCalculator());
-      DiversityCalculatorParameter.ValidValues.Add(new TravelingSalesman.PermutationDiversityCalculator());
-
-      foreach (DiversityCalculator diversityCalculator in Problem.Operators.OfType<DiversityCalculator>().OrderBy(x => x.Name))
-        DiversityCalculatorParameter.ValidValues.Add(diversityCalculator);
-
-      if (oldDiversityCalculator != null) {
-        DiversityCalculator diversityCalculator = DiversityCalculatorParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldDiversityCalculator.GetType());
-        if (diversityCalculator != null) DiversityCalculatorParameter.Value = diversityCalculator;
-        else oldDiversityCalculator = null;
-      }
-      if (oldDiversityCalculator == null && defaultDiversityCalculator != null)
-        DiversityCalculatorParameter.Value = defaultDiversityCalculator;
-    }
     private void UpdateImprovers() {
-      ILocalImprovementOperator oldImprover = ImproverParameter.Value;
+      IImprovementOperator oldImprover = ImproverParameter.Value;
       ImproverParameter.ValidValues.Clear();
-      ILocalImprovementOperator defaultImprover = Problem.Operators.OfType<ILocalImprovementOperator>().FirstOrDefault();
-
-      ImproverParameter.ValidValues.Add(new Knapsack.KnapsackImprovementOperator());
-      ImproverParameter.ValidValues.Add(new TestFunctions.TestFunctionsAckleyImprovementOperator());
-      ImproverParameter.ValidValues.Add(new TestFunctions.TestFunctionsBealeImprovementOperator());
-      ImproverParameter.ValidValues.Add(new TestFunctions.TestFunctionsBoothImprovementOperator());
-      ImproverParameter.ValidValues.Add(new TestFunctions.TestFunctionsGriewankImprovementOperator());
-      ImproverParameter.ValidValues.Add(new TestFunctions.TestFunctionsLevyImprovementOperator());
-      ImproverParameter.ValidValues.Add(new TestFunctions.TestFunctionsMatyasImprovementOperator());
-      ImproverParameter.ValidValues.Add(new TestFunctions.TestFunctionsRosenbrockImprovementOperator());
-      ImproverParameter.ValidValues.Add(new TestFunctions.TestFunctionsSchwefelImprovementOperator());
-      ImproverParameter.ValidValues.Add(new TestFunctions.TestFunctionsSumSquaresImprovementOperator());
-      ImproverParameter.ValidValues.Add(new TestFunctions.TestFunctionsZakharovImprovementOperator());
-      ImproverParameter.ValidValues.Add(new TravelingSalesman.TravelingSalesmanImprovementOperator());
-
-      foreach (ILocalImprovementOperator improver in Problem.Operators.OfType<ILocalImprovementOperator>().OrderBy(x => x.Name))
+      IImprovementOperator defaultImprover = Problem.Operators.OfType<IImprovementOperator>().FirstOrDefault();
+
+      foreach (IImprovementOperator improver in ApplicationManager.Manager.GetInstances<IImprovementOperator>().OrderBy(x => x.Name))
         ImproverParameter.ValidValues.Add(improver);
 
-      foreach (var improver in ImproverParameter.ValidValues.OfType<IScatterSearchTargetProcessor>())
-        improver.TargetParameter.ActualName = "KnapsackSolution"; // temporary solution for the knapsack problem
+      foreach (IImprovementOperator improver in Problem.Operators.OfType<IImprovementOperator>().OrderBy(x => x.Name))
+        ImproverParameter.ValidValues.Add(improver);
 
       if (oldImprover != null) {
-        ILocalImprovementOperator improver = ImproverParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldImprover.GetType());
+        IImprovementOperator improver = ImproverParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldImprover.GetType());
         if (improver != null) ImproverParameter.Value = improver;
         else oldImprover = null;
@@ -378 +344 @@
       if (oldImprover == null && defaultImprover != null)
         ImproverParameter.Value = defaultImprover;
+    }
+    private void UpdatePathRelinkers() {
+      IPathRelinker oldPathRelinker = PathRelinkerParameter.Value;
+      PathRelinkerParameter.ValidValues.Clear();
+      IPathRelinker defaultPathRelinker = Problem.Operators.OfType<IPathRelinker>().FirstOrDefault();
+
+      foreach (IPathRelinker pathRelinker in ApplicationManager.Manager.GetInstances<IPathRelinker>().OrderBy(x => x.Name))
+        PathRelinkerParameter.ValidValues.Add(pathRelinker);
+
+      foreach (IPathRelinker pathRelinker in Problem.Operators.OfType<IPathRelinker>().OrderBy(x => x.Name))
+        PathRelinkerParameter.ValidValues.Add(pathRelinker);
+
+      if (oldPathRelinker != null) {
+        IPathRelinker pathRelinker = PathRelinkerParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldPathRelinker.GetType());
+        if (pathRelinker != null) PathRelinkerParameter.Value = pathRelinker;
+        else oldPathRelinker = null;
+      }
+      if (oldPathRelinker == null && defaultPathRelinker != null)
+        PathRelinkerParameter.Value = defaultPathRelinker;
+    }
+    private void UpdateSimilarityCalculators() {
+      SimilarityCalculator oldDiversityCalculator = SimilarityCalculatorParameter.Value;
+      SimilarityCalculatorParameter.ValidValues.Clear();
+      SimilarityCalculator defaultDiversityCalculator = Problem.Operators.OfType<SimilarityCalculator>().FirstOrDefault();
+
+      foreach (SimilarityCalculator diversityCalculator in ApplicationManager.Manager.GetInstances<SimilarityCalculator>().OrderBy(x => x.Name))
+        SimilarityCalculatorParameter.ValidValues.Add(diversityCalculator);
+
+      foreach (SimilarityCalculator diversityCalculator in Problem.Operators.OfType<SimilarityCalculator>().OrderBy(x => x.Name))
+        SimilarityCalculatorParameter.ValidValues.Add(diversityCalculator);
+
+      if (oldDiversityCalculator != null) {
+        SimilarityCalculator diversityCalculator = SimilarityCalculatorParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldDiversityCalculator.GetType());
+        if (diversityCalculator != null) SimilarityCalculatorParameter.Value = diversityCalculator;
+        else oldDiversityCalculator = null;
+      }
+      if (oldDiversityCalculator == null && defaultDiversityCalculator != null)
+        SimilarityCalculatorParameter.Value = defaultDiversityCalculator;
     }
     private void ParameterizeSolutionsCreator() {
@@ -397 +401 @@
       }
     }
-    //private void ParameterizeScatterSearchTargetProcessor(IOperator op) {
-    //  if (op is IScatterSearchTargetProcessor) {
-    //    IScatterSearchTargetProcessor ssOp = (IScatterSearchTargetProcessor)op;
-    //    ssOp.TargetParameter.ActualName = "KnapsackSolution"; // temporary solution for the knapsack problem
-    //    ssOp.TargetParameter.Hidden = true;
-    //  }
-    //}
     private void ParameterizeAnalyzers() {
       qualityAnalyzer.ResultsParameter.ActualName = "Results";
@@ -422 +419 @@
       while (mainLoop != null && !(mainLoop is ScatterSearchMainLoop))
         mainLoop = ((SingleSuccessorOperator)mainLoop).Successor;
-      if (mainLoop == null) return null;
-      else return (ScatterSearchMainLoop)mainLoop;
+      return mainLoop as ScatterSearchMainLoop;
     }
     #endregion