Changeset 8319 for branches/ScatterSearch (trunk integration)/HeuristicLab.Algorithms.ScatterSearch

Timestamp:

07/24/12 15:04:37 (12 years ago)

Author:

jkarder

Message:

#1331:

• applied some of the changes suggested by ascheibe in comment:32:ticket:1331
• restructured path relinking and improvement operators and similarity calculators
• fixed bug in TSPMultipleGuidesPathRelinker

Location:

branches/ScatterSearch (trunk integration)/HeuristicLab.Algorithms.ScatterSearch/3.3

Files:

• HeuristicLab.Algorithms.ScatterSearch-3.3.csproj (modified) (1 diff)
• IScatterSearchOperator.cs (deleted)
• OffspringProcessor.cs (modified) (4 diffs)
• PopulationRebuildMethod.cs (modified) (1 diff)
• ReferenceSetUpdateMethod.cs (modified) (2 diffs)
• ScatterSearch.cs (modified) (6 diffs)
• ScatterSearchMainLoop.cs (modified) (5 diffs)
• SolutionPoolUpdateMethod.cs (modified) (4 diffs)

branches/ScatterSearch (trunk integration)/HeuristicLab.Algorithms.ScatterSearch/3.3/HeuristicLab.Algorithms.ScatterSearch-3.3.csproj

@@ -85 +85 @@
   </ItemGroup>
   <ItemGroup>
-    <Compile Include="IScatterSearchOperator.cs" />
     <Compile Include="OffspringProcessor.cs" />
     <None Include="HeuristicLab.snk" />

branches/ScatterSearch (trunk integration)/HeuristicLab.Algorithms.ScatterSearch/3.3/OffspringProcessor.cs

@@ -32 +32 @@
   [Item("OffspringProcessor", "An operator that creates a subscope with subscopes for every variable in the current scope.")]
   [StorableClass]
-  public sealed class OffspringProcessor : SingleSuccessorOperator, IScatterSearchOperator {
+  public sealed class OffspringProcessor : SingleSuccessorOperator {
     #region Parameter properties
     public ScopeParameter CurrentScopeParameter {
       get { return (ScopeParameter)Parameters["CurrentScope"]; }
-    }
-    public IValueLookupParameter<IItem> TargetParameter {
-      get { return (IValueLookupParameter<IItem>)Parameters["Target"]; }
     }
     #endregion
@@ -45 +42 @@
     private IScope CurrentScope {
       get { return CurrentScopeParameter.ActualValue; }
-    }
-    private IItem Target {
-      get { return TargetParameter.ActualValue; }
     }
     #endregion
@@ -58 +52 @@
       #region Create parameters
       Parameters.Add(new ScopeParameter("CurrentScope", "The current scope that contains the offspring as variables."));
-      Parameters.Add(new ValueLookupParameter<IItem>("Target", "This parameter is used for name translation only."));
       #endregion
     }
@@ -67 +60 @@
 
     public override IOperation Apply() {
-      VariableCollection offspringSolutions = CurrentScope.Variables;
-      IScope offspringScope = new Scope("Offspring");
-      foreach (var solution in offspringSolutions) {
-        IScope scope = new Scope();
-        scope.Variables.Add(new Variable(TargetParameter.ActualName, solution.Value));
-        offspringScope.SubScopes.Add(scope);
-      }
+      var child = new Scope();
+      child.Variables.AddRange(CurrentScope.Variables);
+      var offspringScope = new Scope();
+      offspringScope.SubScopes.Add(child);
+      var parents = CurrentScope.SubScopes.ToArray();
+      CurrentScope.Variables.Clear();
+      CurrentScope.SubScopes.Clear();
+      CurrentScope.SubScopes.AddRange(parents);
       CurrentScope.SubScopes.Add(offspringScope);
-      CurrentScope.Variables.Clear();
       return base.Apply();
     }

branches/ScatterSearch (trunk integration)/HeuristicLab.Algorithms.ScatterSearch/3.3/PopulationRebuildMethod.cs

@@ -34 +34 @@
   [Item("PopulationRebuildMethod", "An operator that updates the reference set and rebuilds the population.")]
   [StorableClass]
-  public sealed class PopulationRebuildMethod : SingleSuccessorOperator, IScatterSearchOperator {
+  public sealed class PopulationRebuildMethod : SingleSuccessorOperator {
     #region Parameter properties
     public ScopeParameter CurrentScopeParameter {

branches/ScatterSearch (trunk integration)/HeuristicLab.Algorithms.ScatterSearch/3.3/ReferenceSetUpdateMethod.cs

@@ -39 +39 @@
   public sealed class ReferenceSetUpdateMethod : SingleSuccessorOperator, ISimilarityBasedOperator {
     #region ISimilarityBasedOperator Members
-    public ISimilarityCalculator SimilarityCalculator { get; set; }
+    public ISolutionSimilarityCalculator SimilarityCalculator { get; set; }
     #endregion
 
@@ -76 +76 @@
 
     public override IOperation Apply() {
-      IDictionary<IScope, double> population = new Dictionary<IScope, double>();
-      foreach (var pScope in CurrentScope.SubScopes[0].SubScopes) {
-        double similarity = 0;
-        foreach (var rScope in CurrentScope.SubScopes[1].SubScopes) {
-          similarity += SimilarityCalculator.CalculateIndividualSimilarity(pScope, rScope);
-        }
-        population[pScope] = similarity;
+      var populationSimilarity = new Dictionary<IScope, double>();
+      var populationScope = CurrentScope.SubScopes[0];
+      var refSetScope = CurrentScope.SubScopes[1];
+      var similarityMatrix = SimilarityCalculator.CalculateSolutionCrowdSimilarity(populationScope, refSetScope);
+      for (int i = 0; i < populationScope.SubScopes.Count; i++) {
+        populationSimilarity[populationScope.SubScopes[i]] = similarityMatrix[i].Sum();
       }
       int numberOfHighQualitySolutions = CurrentScope.SubScopes[1].SubScopes.Count;
-      foreach (var entry in population.OrderBy(x => x.Value).Take(ReferenceSetSize.Value - numberOfHighQualitySolutions)) {
+      foreach (var entry in populationSimilarity.OrderBy(x => x.Value).Take(ReferenceSetSize.Value - numberOfHighQualitySolutions)) {
         CurrentScope.SubScopes[1].SubScopes.Add(entry.Key);
         CurrentScope.SubScopes[0].SubScopes.Remove(entry.Key);

branches/ScatterSearch (trunk integration)/HeuristicLab.Algorithms.ScatterSearch/3.3/ScatterSearch.cs

@@ -22 +22 @@
 using System;
 using System.Linq;
-using System.Reflection;
 using HeuristicLab.Analysis;
 using HeuristicLab.Common;
@@ -89 +88 @@
       get { return (IValueParameter<BoolValue>)Parameters["SetSeedRandomly"]; }
     }
-    public ConstrainedValueParameter<ISimilarityCalculator> SimilarityCalculatorParameter {
-      get { return (ConstrainedValueParameter<ISimilarityCalculator>)Parameters["SimilarityCalculator"]; }
+    public ConstrainedValueParameter<ISolutionSimilarityCalculator> SimilarityCalculatorParameter {
+      get { return (ConstrainedValueParameter<ISolutionSimilarityCalculator>)Parameters["SimilarityCalculator"]; }
     }
     #endregion
@@ -139 +138 @@
       set { SetSeedRandomlyParameter.Value = value; }
     }
-    private ISimilarityCalculator SimilarityCalculator {
+    private ISolutionSimilarityCalculator SimilarityCalculator {
       get { return SimilarityCalculatorParameter.Value; }
       set { SimilarityCalculatorParameter.Value = value; }
@@ -185 +184 @@
       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 ConstrainedValueParameter<ISimilarityCalculator>("SimilarityCalculator", "The operator used to calculate the similarity between two solutions."));
+      Parameters.Add(new ConstrainedValueParameter<ISolutionSimilarityCalculator>("SimilarityCalculator", "The operator used to calculate the similarity between two solutions."));
       #endregion
 
@@ -382 +381 @@
     }
     private void UpdateSimilarityCalculators() {
-      ISimilarityCalculator oldDiversityCalculator = SimilarityCalculatorParameter.Value;
+      ISolutionSimilarityCalculator oldSimilarityCalculator = SimilarityCalculatorParameter.Value;
       SimilarityCalculatorParameter.ValidValues.Clear();
-      ISimilarityCalculator defaultDiversityCalculator = Problem.Operators.OfType<ISimilarityCalculator>().FirstOrDefault();
-
-      foreach (ISimilarityCalculator diversityCalculator in Problem.Operators.OfType<ISimilarityCalculator>())
-        SimilarityCalculatorParameter.ValidValues.Add(diversityCalculator);
-
-      if (oldDiversityCalculator != null) {
-        ISimilarityCalculator 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;
+      ISolutionSimilarityCalculator defaultSimilarityCalculator = Problem.Operators.OfType<ISolutionSimilarityCalculator>().FirstOrDefault();
+
+      foreach (ISolutionSimilarityCalculator similarityCalculator in Problem.Operators.OfType<ISolutionSimilarityCalculator>())
+        SimilarityCalculatorParameter.ValidValues.Add(similarityCalculator);
+
+      if (oldSimilarityCalculator != null) {
+        ISolutionSimilarityCalculator similarityCalculator = SimilarityCalculatorParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldSimilarityCalculator.GetType());
+        if (similarityCalculator != null) SimilarityCalculatorParameter.Value = similarityCalculator;
+        else oldSimilarityCalculator = null;
+      }
+      if (oldSimilarityCalculator == null && defaultSimilarityCalculator != null)
+        SimilarityCalculatorParameter.Value = defaultSimilarityCalculator;
     }
     private void ParameterizeBestSelector() {
@@ -410 +409 @@
         MainLoop.MaximizationParameter.ActualName = Problem.MaximizationParameter.Name;
         MainLoop.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName;
-        MainLoop.TargetParameter.ActualName = Improver.TargetParameter.ActualName;
-        foreach (var op in MainLoop.OperatorGraph.Operators.OfType<IScatterSearchOperator>()) {
-          // parameter should be accessed direclty (using an interface definition)
-          PropertyInfo propInfo = op.GetType().GetProperty(MainLoop.TargetParameter.Name + "Parameter");
-          if (propInfo != null && propInfo.CanRead)
-            (propInfo.GetValue(op, null) as IValueLookupParameter<IItem>).ActualName = MainLoop.TargetParameter.ActualName;
-          propInfo = op.GetType().GetProperty(MainLoop.QualityParameter.Name + "Parameter");
-          if (propInfo != null && propInfo.CanRead)
-            (propInfo.GetValue(op, null) as IValueLookupParameter<IItem>).ActualName = MainLoop.QualityParameter.ActualName;
-        }
+        MainLoop.OperatorGraph.Operators.OfType<PopulationRebuildMethod>().Single().QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName;
+        MainLoop.OperatorGraph.Operators.OfType<SolutionPoolUpdateMethod>().Single().QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName;
         foreach (ISimilarityBasedOperator op in MainLoop.OperatorGraph.Operators.OfType<ISimilarityBasedOperator>())
           op.SimilarityCalculator = SimilarityCalculator;

branches/ScatterSearch (trunk integration)/HeuristicLab.Algorithms.ScatterSearch/3.3/ScatterSearchMainLoop.cs

@@ -89 +89 @@
       get { return (IValueLookupParameter<VariableCollection>)Parameters["Results"]; }
     }
-    public IValueLookupParameter<ISimilarityCalculator> SimilarityCalculatorParameter {
-      get { return (IValueLookupParameter<ISimilarityCalculator>)Parameters["SimilarityCalculator"]; }
-    }
-    public IValueLookupParameter<IItem> TargetParameter {
-      get { return (IValueLookupParameter<IItem>)Parameters["Target"]; }
+    public IValueLookupParameter<ISolutionSimilarityCalculator> SimilarityCalculatorParameter {
+      get { return (IValueLookupParameter<ISolutionSimilarityCalculator>)Parameters["SimilarityCalculator"]; }
     }
     #endregion
@@ -166 +163 @@
       set { ResultsParameter.ActualValue = value; }
     }
-    private ISimilarityCalculator SimilarityCalculator {
+    private ISolutionSimilarityCalculator SimilarityCalculator {
       get { return SimilarityCalculatorParameter.ActualValue; }
       set { SimilarityCalculatorParameter.ActualValue = value; }
-    }
-    private IItem Target {
-      get { return TargetParameter.ActualValue; }
-      set { TargetParameter.ActualValue = value; }
     }
     #endregion
@@ -204 +197 @@
       Parameters.Add(new ValueLookupParameter<IRandom>("Random", "A pseudo random number generator."));
       Parameters.Add(new ValueLookupParameter<VariableCollection>("Results", "The variable collection where results should be stored."));
-      Parameters.Add(new ValueLookupParameter<ISimilarityCalculator>("SimilarityCalculator", "The operator used to calculate the similarity between two solutions."));
-      Parameters.Add(new ValueLookupParameter<IItem>("Target", "This parameter is used for name translation only."));
+      Parameters.Add(new ValueLookupParameter<ISolutionSimilarityCalculator>("SimilarityCalculator", "The operator used to calculate the similarity between two solutions."));
       #endregion
 
@@ -298 +290 @@
       pathRelinker.Name = "PathRelinker";
       pathRelinker.OperatorParameter.ActualName = PathRelinkerParameter.Name;
-      pathRelinker.Successor = offspringProcessor;
+      pathRelinker.Successor = rightSelector;
 
       crossover.Name = "Crossover";
@@ -304 +296 @@
       crossover.Successor = offspringProcessor;
 
-      offspringProcessor.TargetParameter.ActualName = TargetParameter.ActualName;
       offspringProcessor.Successor = rightSelector;
 

branches/ScatterSearch (trunk integration)/HeuristicLab.Algorithms.ScatterSearch/3.3/SolutionPoolUpdateMethod.cs

@@ -28 +28 @@
 using HeuristicLab.Operators;
 using HeuristicLab.Optimization;
-using HeuristicLab.Optimization.Operators;
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
@@ -38 +37 @@
   [Item("SolutionPoolUpdateMethod", "An operator that updates the solution pool.")]
   [StorableClass]
-  public sealed class SolutionPoolUpdateMethod : SingleSuccessorOperator, IScatterSearchOperator, ISimilarityBasedOperator {
+  public sealed class SolutionPoolUpdateMethod : SingleSuccessorOperator, ISimilarityBasedOperator {
     #region ISimilarityBasedOperator Members
-    public ISimilarityCalculator SimilarityCalculator { get; set; }
+    public ISolutionSimilarityCalculator SimilarityCalculator { get; set; }
     #endregion
 
@@ -130 +129 @@
       if (orderedOffspring.Any(hasBetterQuality)) {
         // produce the set union
-        var union = orderedParents.Union(orderedOffspring.Where(hasBetterQuality), new SolutionEqualityComparer<IScope>(SimilarityCalculator.CalculateIndividualSimilarity));
+        var union = orderedParents.Union(orderedOffspring.Where(hasBetterQuality), new SolutionEqualityComparer<IScope>(SimilarityCalculator.CalculateSolutionSimilarity));
         if (union.Count() > orderedParents.Count()) {
           var orderedUnion = Maximization.Value ? union.OrderByDescending(x => x.Variables[QualityParameter.ActualName].Value) :
@@ -142 +141 @@
     }
 
+    // derive SingleObjectiveSolutionSimilarityCalculator from EqualityComparer
+    // delete this ...
     public class SolutionEqualityComparer<T> : EqualityComparer<T> {
       private readonly Func<T, T, double> similarityCalculator;