Changeset 6046 for branches/histogram/HeuristicLab.Algorithms.LocalSearch/3.3/LocalSearchImprovementOperator.cs

Timestamp:

04/23/11 10:00:31 (13 years ago)

Author:

abeham

Message:

#1465

• updated branch with trunk changes

Location:

branches/histogram

Files:

• . (modified) (2 props)
• HeuristicLab.Algorithms.LocalSearch/3.3/LocalSearchImprovementOperator.cs (modified) (8 diffs)

branches/histogram

@@ -10 +10 @@
 protoc.exe
 HeuristicLab 3.3.5.1.ReSharper.user
+*.psess
+*.vsp

@@ -10 +10 @@
 protoc.exe
 HeuristicLab 3.3.5.1.ReSharper.user
+*.psess
+*.vsp

branches/histogram/HeuristicLab.Algorithms.LocalSearch/3.3/LocalSearchImprovementOperator.cs

@@ -21 +21 @@
 
 using System;
-using System.Collections.Generic;
 using System.Linq;
 using HeuristicLab.Analysis;
@@ -39 +38 @@
   [Item("LocalSearchImprovementOperator", "A local search improvement operator.")]
   [StorableClass]
-  public class LocalSearchImprovementOperator : SingleSuccessorOperator, ILocalImprovementOperator {
+  public sealed class LocalSearchImprovementOperator : SingleSuccessorOperator, ILocalImprovementOperator, IStochasticOperator {
+    #region IGenericLocalImprovementOperator Properties
+    public Type ProblemType { get { return typeof(ISingleObjectiveHeuristicOptimizationProblem); } }
+    public IProblem Problem {
+      get { return problem; }
+      set {
+        if (problem != value) {
+          if (value != null && !(value is ISingleObjectiveHeuristicOptimizationProblem))
+            throw new ArgumentException("Only problems of type " + ProblemType.ToString() + " can be assigned.");
+          if (problem != null) DeregisterProblemEventHandlers();
+          problem = (ISingleObjectiveHeuristicOptimizationProblem)value;
+          if (problem != null) RegisterProblemEventHandlers();
+          UpdateProblem();
+        }
+      }
+    }
+    #endregion
+
+    [Storable]
+    private ISingleObjectiveHeuristicOptimizationProblem problem;
     [Storable]
     private LocalSearchMainLoop loop;
-
     [Storable]
     private BestAverageWorstQualityAnalyzer qualityAnalyzer;
 
-    private ConstrainedValueParameter<IMoveGenerator> MoveGeneratorParameter {
+    #region Parameter Properties
+    public ConstrainedValueParameter<IMoveGenerator> MoveGeneratorParameter {
       get { return (ConstrainedValueParameter<IMoveGenerator>)Parameters["MoveGenerator"]; }
     }
-    private ConstrainedValueParameter<IMoveMaker> MoveMakerParameter {
+    public ConstrainedValueParameter<IMoveMaker> MoveMakerParameter {
       get { return (ConstrainedValueParameter<IMoveMaker>)Parameters["MoveMaker"]; }
     }
-    private ConstrainedValueParameter<ISingleObjectiveMoveEvaluator> MoveEvaluatorParameter {
+    public ConstrainedValueParameter<ISingleObjectiveMoveEvaluator> MoveEvaluatorParameter {
       get { return (ConstrainedValueParameter<ISingleObjectiveMoveEvaluator>)Parameters["MoveEvaluator"]; }
     }
-    private ValueParameter<IntValue> MaximumIterationsParameter {
-      get { return (ValueParameter<IntValue>)Parameters["MaximumIterations"]; }
-    }
-    private ValueParameter<IntValue> SampleSizeParameter {
-      get { return (ValueParameter<IntValue>)Parameters["SampleSize"]; }
-    }
-    public LookupParameter<IntValue> EvaluatedSolutionsParameter {
-      get { return (LookupParameter<IntValue>)Parameters["EvaluatedSolutions"]; }
+    public IValueLookupParameter<IntValue> SampleSizeParameter {
+      get { return (IValueLookupParameter<IntValue>)Parameters["SampleSize"]; }
     }
     public ValueParameter<MultiAnalyzer> AnalyzerParameter {
       get { return (ValueParameter<MultiAnalyzer>)Parameters["Analyzer"]; }
     }
-
+    public ScopeTreeLookupParameter<DoubleValue> QualityParameter {
+      get { return (ScopeTreeLookupParameter<DoubleValue>)Parameters["Quality"]; }
+    }
+    public ILookupParameter<IRandom> RandomParameter {
+      get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
+    }
+    #region ILocalImprovementOperator Parameters
+    public IValueLookupParameter<IntValue> MaximumIterationsParameter {
+      get { return (IValueLookupParameter<IntValue>)Parameters["MaximumIterations"]; }
+    }
+    public ILookupParameter<IntValue> EvaluatedSolutionsParameter {
+      get { return (ILookupParameter<IntValue>)Parameters["EvaluatedSolutions"]; }
+    }
+    public ILookupParameter<ResultCollection> ResultsParameter {
+      get { return (ILookupParameter<ResultCollection>)Parameters["Results"]; }
+    }
+    #endregion
+    #endregion
+
+    #region Properties
     public IMoveGenerator MoveGenerator {
       get { return MoveGeneratorParameter.Value; }
@@ -84 +115 @@
       set { AnalyzerParameter.Value = value; }
     }
+    #endregion
 
     [StorableConstructor]
-    protected LocalSearchImprovementOperator(bool deserializing) : base(deserializing) { }
-    [StorableHook(HookType.AfterDeserialization)]
-    private void AfterDeserialization() {
-      Initialize();
-    }
-    protected LocalSearchImprovementOperator(LocalSearchImprovementOperator original, Cloner cloner)
+    private LocalSearchImprovementOperator(bool deserializing) : base(deserializing) { }
+    private LocalSearchImprovementOperator(LocalSearchImprovementOperator original, Cloner cloner)
       : base(original, cloner) {
       this.loop = cloner.Clone(original.loop);
       this.qualityAnalyzer = cloner.Clone(original.qualityAnalyzer);
-      Initialize();
-    }
-    public override IDeepCloneable Clone(Cloner cloner) {
-      return new LocalSearchImprovementOperator(this, cloner);
+      this.problem = cloner.Clone(original.problem);
+      RegisterEventHandlers();
     }
     public LocalSearchImprovementOperator()
       : base() {
-      loop = new LocalSearchMainLoop();
-
-      ResultsCollector rc = (loop.OperatorGraph.InitialOperator as SingleSuccessorOperator).Successor as ResultsCollector;
-      rc.CollectedValues.Remove("BestLocalQuality");
-
-      qualityAnalyzer = new BestAverageWorstQualityAnalyzer();
-
       Parameters.Add(new ConstrainedValueParameter<IMoveGenerator>("MoveGenerator", "The operator used to generate moves to the neighborhood of the current solution."));
       Parameters.Add(new ConstrainedValueParameter<IMoveMaker>("MoveMaker", "The operator used to perform a move."));
       Parameters.Add(new ConstrainedValueParameter<ISingleObjectiveMoveEvaluator>("MoveEvaluator", "The operator used to evaluate a move."));
-      Parameters.Add(new ValueParameter<IntValue>("MaximumIterations", "The maximum number of generations which should be processed.", new IntValue(150)));
-      Parameters.Add(new ValueParameter<IntValue>("SampleSize", "Number of moves that MultiMoveGenerators should create. This is ignored for Exhaustive- and SingleMoveGenerators.", new IntValue(1500)));
+      Parameters.Add(new ValueLookupParameter<IntValue>("MaximumIterations", "The maximum number of generations which should be processed.", new IntValue(150)));
+      Parameters.Add(new ValueLookupParameter<IntValue>("SampleSize", "Number of moves that MultiMoveGenerators should create. This is ignored for Exhaustive- and SingleMoveGenerators.", new IntValue(300)));
       Parameters.Add(new LookupParameter<IntValue>("EvaluatedSolutions", "The number of evaluated moves."));
       Parameters.Add(new ValueParameter<MultiAnalyzer>("Analyzer", "The operator used to analyze the solution.", new MultiAnalyzer()));
-
-      Initialize();
-    }
-
-    private void Initialize() {
+      Parameters.Add(new LookupParameter<ResultCollection>("Results", "The name of the collection where the results are stored."));
+      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("Quality", "The quality/fitness value of a solution."));
+      Parameters.Add(new LookupParameter<IRandom>("Random", "The random number generator to use."));
+
+      loop = new LocalSearchMainLoop();
+      ((ResultsCollector)((SingleSuccessorOperator)loop.OperatorGraph.InitialOperator).Successor).CollectedValues.Remove(loop.BestLocalQualityParameter.Name);
+      ParameterizeLSMainLoop();
+
+      qualityAnalyzer = new BestAverageWorstQualityAnalyzer();
+      Analyzer.Operators.Add(qualityAnalyzer);
+
+      RegisterEventHandlers();
+    }
+
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new LocalSearchImprovementOperator(this, cloner);
+    }
+
+    [StorableHook(HookType.AfterDeserialization)]
+    private void AfterDeserialization() {
+      RegisterEventHandlers();
+    }
+
+    #region Event Handler Registration
+    private void RegisterEventHandlers() {
       MoveGeneratorParameter.ValueChanged += new EventHandler(MoveGeneratorParameter_ValueChanged);
-    }
-
-    public void OnProblemChanged(IProblem problem) {
-      UpdateMoveOperators(problem);
+      if (problem != null)
+        RegisterProblemEventHandlers();
+    }
+
+    private void RegisterProblemEventHandlers() {
+      problem.Reset += new EventHandler(problem_Reset);
+      problem.OperatorsChanged += new EventHandler(problem_OperatorsChanged);
+    }
+
+    private void DeregisterProblemEventHandlers() {
+      problem.Reset -= new EventHandler(problem_Reset);
+      problem.OperatorsChanged -= new EventHandler(problem_OperatorsChanged);
+    }
+    #endregion
+
+    #region Event Handlers
+    private void MoveGeneratorParameter_ValueChanged(object sender, EventArgs e) {
       ChooseMoveOperators();
-
-      ParameterizeMoveGenerators(problem as ISingleObjectiveHeuristicOptimizationProblem);
-      ParameterizeMoveEvaluators(problem as ISingleObjectiveHeuristicOptimizationProblem);
-      ParameterizeMoveMakers(problem as ISingleObjectiveHeuristicOptimizationProblem);
-
-      ParameterizeAnalyzers(problem as ISingleObjectiveHeuristicOptimizationProblem);
-      UpdateAnalyzers(problem as ISingleObjectiveHeuristicOptimizationProblem);
-    }
-
-    void ParameterizeAnalyzers(ISingleObjectiveHeuristicOptimizationProblem problem) {
-      qualityAnalyzer.ResultsParameter.ActualName = "Results";
+      ParameterizeLSMainLoop();
+    }
+
+    private void problem_Reset(object sender, EventArgs e) {
+      UpdateProblem();
+    }
+
+    private void problem_OperatorsChanged(object sender, EventArgs e) {
+      UpdateProblem();
+    }
+    #endregion
+
+    #region Parameterize and Update Methods
+    private void UpdateProblem() {
+      UpdateMoveOperators();
+      ChooseMoveOperators();
+
+      ParameterizeMoveGenerators();
+
+      ParameterizeLSMainLoop();
+      ParameterizeAnalyzers();
+    }
+
+    private void ParameterizeLSMainLoop() {
+      loop.AnalyzerParameter.ActualName = AnalyzerParameter.Name;
+      loop.BestLocalQualityParameter.ActualName = QualityParameter.Name;
+      loop.EvaluatedMovesParameter.ActualName = EvaluatedSolutionsParameter.Name;
+      loop.IterationsParameter.ActualName = "LocalIterations";
+      loop.MaximumIterationsParameter.ActualName = MaximumIterationsParameter.Name;
+      loop.MoveEvaluatorParameter.ActualName = MoveEvaluatorParameter.Name;
+      loop.MoveGeneratorParameter.ActualName = MoveGeneratorParameter.Name;
+      loop.MoveMakerParameter.ActualName = MoveMakerParameter.Name;
+      loop.QualityParameter.ActualName = QualityParameter.Name;
+      loop.RandomParameter.ActualName = RandomParameter.Name;
+      loop.ResultsParameter.ActualName = ResultsParameter.Name;
+
+      if (problem != null) {
+        loop.BestKnownQualityParameter.ActualName = problem.BestKnownQualityParameter.Name;
+        loop.MaximizationParameter.ActualName = problem.MaximizationParameter.Name;
+      }
+      if (MoveEvaluator != null) {
+        loop.MoveQualityParameter.ActualName = MoveEvaluator.MoveQualityParameter.ActualName;
+      }
+    }
+
+    private void ParameterizeAnalyzers() {
+      qualityAnalyzer.ResultsParameter.ActualName = ResultsParameter.Name;
       if (problem != null) {
         qualityAnalyzer.MaximizationParameter.ActualName = problem.MaximizationParameter.Name;
@@ -146 +234 @@
     }
 
-    void UpdateAnalyzers(ISingleObjectiveHeuristicOptimizationProblem problem) {
-      Analyzer.Operators.Clear();
-      if (problem != null) {
-        foreach (IAnalyzer analyzer in problem.Operators.OfType<IAnalyzer>()) {
-          IAnalyzer clone = analyzer.Clone() as IAnalyzer;
-          foreach (IScopeTreeLookupParameter param in clone.Parameters.OfType<IScopeTreeLookupParameter>())
-            param.Depth = 0;
-          Analyzer.Operators.Add(clone);
-        }
-      }
-      Analyzer.Operators.Add(qualityAnalyzer);
-    }
-
-    void MoveGeneratorParameter_ValueChanged(object sender, EventArgs e) {
-      ChooseMoveOperators();
-    }
-
-    private void UpdateMoveOperators(IProblem problem) {
+    private void UpdateMoveOperators() {
       IMoveGenerator oldMoveGenerator = MoveGenerator;
       IMoveMaker oldMoveMaker = MoveMaker;
@@ -171 +242 @@
 
       if (problem != null) {
-        foreach (IMoveGenerator generator in problem.Operators.OfType<IMoveGenerator>().OrderBy(x => x.Name))
+        foreach (IMultiMoveGenerator generator in problem.Operators.OfType<IMultiMoveGenerator>().OrderBy(x => x.Name))
           MoveGeneratorParameter.ValidValues.Add(generator);
-
-        foreach (IMoveMaker maker in problem.Operators.OfType<IMoveMaker>().OrderBy(x => x.Name))
-          MoveMakerParameter.ValidValues.Add(maker);
-
-        foreach (ISingleObjectiveMoveEvaluator evaluator in problem.Operators.OfType<ISingleObjectiveMoveEvaluator>().OrderBy(x => x.Name))
-          MoveEvaluatorParameter.ValidValues.Add(evaluator);
-      }
-
-      if (oldMoveGenerator != null) {
-        IMoveGenerator newMoveGenerator = MoveGeneratorParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldMoveGenerator.GetType());
-        if (newMoveGenerator != null) MoveGenerator = newMoveGenerator;
-      }
-      if (MoveGenerator == null) {
-        ClearMoveParameters();
-      }
-
-      if (oldMoveMaker != null) {
-        IMoveMaker mm = MoveMakerParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldMoveMaker.GetType());
-        if (mm != null) MoveMaker = mm;
-      }
-
-      if (oldMoveEvaluator != null) {
-        ISingleObjectiveMoveEvaluator me = MoveEvaluatorParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldMoveEvaluator.GetType());
-        if (me != null) MoveEvaluator = me;
-      }
-    }
-
-    private void ChooseMoveOperators() {
-      IMoveMaker oldMoveMaker = MoveMaker;
-      ISingleObjectiveMoveEvaluator oldMoveEvaluator = MoveEvaluator;
-
-      if (MoveGenerator != null) {
-        List<Type> moveTypes = MoveGenerator.GetType().GetInterfaces().Where(x => typeof(IMoveOperator).IsAssignableFrom(x)).ToList();
-        foreach (Type type in moveTypes.ToList()) {
-          if (moveTypes.Any(t => t != type && type.IsAssignableFrom(t)))
-            moveTypes.Remove(type);
-        }
-        List<IMoveMaker> validMoveMakers = new List<IMoveMaker>();
-        List<ISingleObjectiveMoveEvaluator> validMoveEvaluators = new List<ISingleObjectiveMoveEvaluator>();
-
-        foreach (Type type in moveTypes) {
-          var moveMakers = MoveMakerParameter.ValidValues.Where(x => type.IsAssignableFrom(x.GetType())).OrderBy(x => x.Name);
-          foreach (IMoveMaker moveMaker in moveMakers)
-            validMoveMakers.Add(moveMaker);
-
-          var moveEvaluators = MoveEvaluatorParameter.ValidValues.Where(x => type.IsAssignableFrom(x.GetType())).OrderBy(x => x.Name);
-          foreach (ISingleObjectiveMoveEvaluator moveEvaluator in moveEvaluators)
-            validMoveEvaluators.Add(moveEvaluator);
-        }
+        foreach (IExhaustiveMoveGenerator generator in problem.Operators.OfType<IExhaustiveMoveGenerator>().OrderBy(x => x.Name))
+          MoveGeneratorParameter.ValidValues.Add(generator);
+
+        if (oldMoveGenerator != null) {
+          IMoveGenerator newMoveGenerator = MoveGeneratorParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldMoveGenerator.GetType());
+          if (newMoveGenerator != null) MoveGenerator = newMoveGenerator;
+        }
+
+        ChooseMoveOperators(oldMoveMaker, oldMoveEvaluator);
+      }
+    }
+
+    private void ChooseMoveOperators(IMoveMaker oldMoveMaker = null, ISingleObjectiveMoveEvaluator oldMoveEvaluator = null) {
+      if (oldMoveMaker == null) oldMoveMaker = MoveMaker;
+      if (oldMoveEvaluator == null) oldMoveEvaluator = MoveEvaluator;
+      MoveMakerParameter.ValidValues.Clear();
+      MoveEvaluatorParameter.ValidValues.Clear();
+
+      if (MoveGenerator != null && Problem != null) {
+        IMoveGenerator generator = MoveGeneratorParameter.Value;
+        foreach (IMoveMaker moveMaker in MoveHelper.GetCompatibleMoveMakers(generator, Problem.Operators).OrderBy(x => x.Name))
+          MoveMakerParameter.ValidValues.Add(moveMaker);
+        foreach (ISingleObjectiveMoveEvaluator moveEvaluator in MoveHelper.GetCompatibleSingleObjectiveMoveEvaluators(generator, Problem.Operators).OrderBy(x => x.Name))
+          MoveEvaluatorParameter.ValidValues.Add(moveEvaluator);
+
         if (oldMoveMaker != null) {
-          IMoveMaker mm = validMoveMakers.FirstOrDefault(x => x.GetType() == oldMoveMaker.GetType());
+          IMoveMaker mm = MoveMakerParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldMoveMaker.GetType());
           if (mm != null) MoveMaker = mm;
-          else MoveMaker = validMoveMakers.FirstOrDefault();
-        }
-
+        }
         if (oldMoveEvaluator != null) {
-          ISingleObjectiveMoveEvaluator me = validMoveEvaluators.FirstOrDefault(x => x.GetType() == oldMoveEvaluator.GetType());
+          ISingleObjectiveMoveEvaluator me = MoveEvaluatorParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldMoveEvaluator.GetType());
           if (me != null) MoveEvaluator = me;
-          else MoveEvaluator = validMoveEvaluators.FirstOrDefault();
         }
       }
@@ -242 +286 @@
     }
 
-    private void ParameterizeMoveGenerators(ISingleObjectiveHeuristicOptimizationProblem problem) {
+    private void ParameterizeMoveGenerators() {
       if (problem != null) {
         foreach (IMultiMoveGenerator generator in problem.Operators.OfType<IMultiMoveGenerator>())
@@ -248 +292 @@
       }
     }
-    private void ParameterizeMoveEvaluators(ISingleObjectiveHeuristicOptimizationProblem problem) {
-      foreach (ISingleObjectiveMoveEvaluator op in problem.Operators.OfType<ISingleObjectiveMoveEvaluator>()) {
-        op.QualityParameter.ActualName = problem.Evaluator.QualityParameter.ActualName;
-      }
-    }
-    private void ParameterizeMoveMakers(ISingleObjectiveHeuristicOptimizationProblem problem) {
-      foreach (IMoveMaker op in problem.Operators.OfType<IMoveMaker>()) {
-        op.QualityParameter.ActualName = problem.Evaluator.QualityParameter.ActualName;
-        if (MoveEvaluator != null)
-          op.MoveQualityParameter.ActualName = MoveEvaluator.MoveQualityParameter.ActualName;
-      }
-    }
+    #endregion
 
     public override IOperation Apply() {
-      Scope subScope = new Scope();
+      IScope currentScope = ExecutionContext.Scope;
+
+      Scope localScope = new Scope();
       Scope individual = new Scope();
 
-      foreach (Variable var in ExecutionContext.Scope.Variables) {
-        individual.Variables.Add(var);
-      }
-      subScope.SubScopes.Add(individual);
-
-      ExecutionContext.Scope.SubScopes.Add(subScope);
-      int index = subScope.Parent.SubScopes.IndexOf(subScope);
+      foreach (IVariable var in currentScope.Variables)
+        individual.Variables.Add(var); // add reference to variable otherwise the analyzer fails (it's looking down the tree)
+
+      localScope.SubScopes.Add(individual);
+      currentScope.SubScopes.Add(localScope);
+      int index = currentScope.SubScopes.Count - 1;
 
       SubScopesProcessor processor = new SubScopesProcessor();
@@ -279 +313 @@
       remover.SubScopeIndexParameter.Value = new IntValue(index);
 
-      for (int i = 0; i < index; i++) {
-        processor.Operators.Add(new EmptyOperator());
+      if (index > 0) {
+        EmptyOperator eo = new EmptyOperator();
+        for (int i = 0; i < index - 1; i++) {
+          processor.Operators.Add(eo);
+        }
       }
 
       VariableCreator variableCreator = new VariableCreator();
-      variableCreator.CollectedValues.Add(new ValueParameter<IntValue>("LocalIterations", new IntValue(0)));
-      variableCreator.CollectedValues.Add(new ValueParameter<DoubleValue>("BestLocalQuality", new DoubleValue(0)));
+      variableCreator.CollectedValues.Add(new ValueParameter<IntValue>(loop.IterationsParameter.ActualName, new IntValue(0)));
+      variableCreator.CollectedValues.Add(new ValueParameter<DoubleValue>(loop.BestLocalQualityParameter.ActualName, new DoubleValue(0)));
 
       variableCreator.Successor = loop;
-
-      loop.EvaluatedMovesParameter.ActualName = EvaluatedSolutionsParameter.ActualName;
 
       processor.Operators.Add(variableCreator);
       processor.Successor = remover;
 
-      IOperation next = base.Apply();
-      if (next as ExecutionContext != null) {
-        remover.Successor = (next as ExecutionContext).Operator;
-      }
-
-      return ExecutionContext.CreateChildOperation(processor);
+      OperationCollection next = new OperationCollection(base.Apply());
+      next.Insert(0, ExecutionContext.CreateChildOperation(processor));
+
+      return next;
     }
   }

@@ -10 +10 @@
 protoc.exe
 HeuristicLab 3.3.5.1.ReSharper.user
+*.psess
+*.vsp