Changeset 3809 for trunk/sources/HeuristicLab.Algorithms.TabuSearch

Timestamp:

05/14/10 17:47:49 (15 years ago)

Author:

abeham

Message:

#893

• fixed BestKnownQuality tracking in tabu search and local search

Location:

trunk/sources/HeuristicLab.Algorithms.TabuSearch/3.3

Files:

• TabuNeighborhoodAnalyzer.cs (modified) (1 diff)
• TabuSearch.cs (modified) (6 diffs)
• TabuSearchMainLoop.cs (modified) (9 diffs)

trunk/sources/HeuristicLab.Algorithms.TabuSearch/3.3/TabuNeighborhoodAnalyzer.cs

@@ -48 +48 @@
     public override IOperation Apply() {
       ItemArray<BoolValue> tabu = IsTabuParameter.ActualValue;
-      PercentValue value = PercentTabuParameter.ActualValue;
-      if (value == null) {
-        value = new PercentValue();
-        PercentTabuParameter.ActualValue = value;
-      }
-      value.Value = tabu.Where(x => x.Value).Count() / (double)tabu.Length;
-      ResultCollection results = ResultsParameter.ActualValue;
-      if (results != null) {
-        IResult result = null;
-        results.TryGetValue(PercentTabuParameter.ActualName, out result);
-        if (result != null)
-          result.Value = value;
-        else
-          results.Add(new Result(PercentTabuParameter.ActualName, "Indicates how much of the neighborhood is tabu.", (IItem)value.Clone()));
+      if (tabu.Length > 0) {
+        PercentValue value = PercentTabuParameter.ActualValue;
+        if (value == null) {
+          value = new PercentValue();
+          PercentTabuParameter.ActualValue = value;
+        }
+        value.Value = tabu.Where(x => x.Value).Count() / (double)tabu.Length;
+        ResultCollection results = ResultsParameter.ActualValue;
+        if (results != null) {
+          IResult result = null;
+          results.TryGetValue(PercentTabuParameter.ActualName, out result);
+          if (result != null)
+            result.Value = value;
+          else
+            results.Add(new Result(PercentTabuParameter.ActualName, "Indicates how much of the neighborhood is tabu.", (IItem)value.Clone()));
+        }
       }
       return base.Apply();

trunk/sources/HeuristicLab.Algorithms.TabuSearch/3.3/TabuSearch.cs

@@ -81 +81 @@
       get { return (ValueParameter<IntValue>)Parameters["SampleSize"]; }
     }
-    private ValueParameter<MultiAnalyzer> MoveAnalyzerParameter {
-      get { return (ValueParameter<MultiAnalyzer>)Parameters["MoveAnalyzer"]; }
-    }
     private ValueParameter<MultiAnalyzer> AnalyzerParameter {
       get { return (ValueParameter<MultiAnalyzer>)Parameters["Analyzer"]; }
@@ -125 +122 @@
       get { return MaximumIterationsParameter.Value; }
       set { MaximumIterationsParameter.Value = value; }
-    }
-    public MultiAnalyzer MoveAnalyzer {
-      get { return MoveAnalyzerParameter.Value; }
-      set { MoveAnalyzerParameter.Value = value; }
     }
     public MultiAnalyzer Analyzer {
@@ -161 +154 @@
       Parameters.Add(new ValueParameter<IntValue>("MaximumIterations", "The maximum number of generations which should be processed.", new IntValue(1000)));
       Parameters.Add(new ValueParameter<IntValue>("SampleSize", "The neighborhood size for stochastic sampling move generators", new IntValue(100)));
-      Parameters.Add(new ValueParameter<MultiAnalyzer>("MoveAnalyzer", "The operator used to analyze the moves.", new MultiAnalyzer()));
       Parameters.Add(new ValueParameter<MultiAnalyzer>("Analyzer", "The operator used to analyze the solution.", new MultiAnalyzer()));
       
@@ -187 +179 @@
       tsMainLoop.RandomParameter.ActualName = RandomCreator.RandomParameter.ActualName;
       tsMainLoop.ResultsParameter.ActualName = "Results";
-      tsMainLoop.MoveAnalyzerParameter.ActualName = MoveAnalyzerParameter.Name;
       tsMainLoop.AnalyzerParameter.ActualName = AnalyzerParameter.Name;
 
@@ -392 +383 @@
     private void UpdateAnalyzers() {
       Analyzer.Operators.Clear();
-      MoveAnalyzer.Operators.Clear();
-      MoveAnalyzer.Operators.Add(moveQualityAnalyzer);
-      MoveAnalyzer.Operators.Add(tabuNeighborhoodAnalyzer);
       if (Problem != null) {
         foreach (IAnalyzer analyzer in Problem.Operators.OfType<IAnalyzer>().OrderBy(x => x.Name)) {
@@ -402 +390 @@
         }
       }
+      Analyzer.Operators.Add(moveQualityAnalyzer);
+      Analyzer.Operators.Add(tabuNeighborhoodAnalyzer);
     }
     private void ClearMoveParameters() {

trunk/sources/HeuristicLab.Algorithms.TabuSearch/3.3/TabuSearchMainLoop.cs

@@ -77 +77 @@
       get { return (ValueLookupParameter<IOperator>)Parameters["TabuMaker"]; }
     }
-    public ValueLookupParameter<IOperator> MoveAnalyzerParameter {
-      get { return (ValueLookupParameter<IOperator>)Parameters["MoveAnalyzer"]; }
-    }
     public ValueLookupParameter<IOperator> AnalyzerParameter {
       get { return (ValueLookupParameter<IOperator>)Parameters["Analyzer"]; }
@@ -112 +109 @@
       Parameters.Add(new ValueLookupParameter<IOperator>("TabuMaker", "The operator that declares a move tabu."));
 
-      Parameters.Add(new ValueLookupParameter<IOperator>("MoveAnalyzer", "The operator used to analyze the moves."));
-      Parameters.Add(new ValueLookupParameter<IOperator>("Analyzer", "The operator used to analyze the solution."));
+      Parameters.Add(new ValueLookupParameter<IOperator>("Analyzer", "The operator used to analyze the solution and moves."));
       Parameters.Add(new ValueLookupParameter<VariableCollection>("Results", "The variable collection where results should be stored."));
       #endregion
@@ -130 +126 @@
       IntCounter evaluatedMovesCounter = new IntCounter();
       Placeholder tabuChecker = new Placeholder();
-      Placeholder moveAnalyzer = new Placeholder();
       SubScopesSorter moveQualitySorter = new SubScopesSorter();
       TabuSelector tabuSelector = new TabuSelector();
       ConditionalBranch emptyNeighborhoodBranch1 = new ConditionalBranch();
-      RightReducer rightReducer = new RightReducer();
       SubScopesProcessor moveMakingProcessor = new SubScopesProcessor();
+      UniformSubScopesProcessor selectedMoveMakingProcesor = new UniformSubScopesProcessor();
       Placeholder tabuMaker = new Placeholder();
       Placeholder moveMaker = new Placeholder();
+      MergingReducer mergingReducer = new MergingReducer();
+      Placeholder analyzer2 = new Placeholder();
       SubScopesRemover subScopesRemover = new SubScopesRemover();
       ConditionalBranch emptyNeighborhoodBranch2 = new ConditionalBranch();
@@ -143 +140 @@
       IntCounter iterationsCounter = new IntCounter();
       Comparator iterationsComparator = new Comparator();
-      SubScopesProcessor subScopesProcessor1 = new SubScopesProcessor();
-      Placeholder analyzer2 = new Placeholder();
       ResultsCollector resultsCollector3 = new ResultsCollector();
       ConditionalBranch iterationsTermination = new ConditionalBranch();
@@ -182 +177 @@
       tabuChecker.Name = "TabuChecker (placeholder)";
       tabuChecker.OperatorParameter.ActualName = TabuCheckerParameter.Name;
-
-      moveAnalyzer.Name = "MoveAnalyzer (placeholder)";
-      moveAnalyzer.OperatorParameter.ActualName = MoveAnalyzerParameter.Name;
 
       moveQualitySorter.DescendingParameter.ActualName = MaximizationParameter.Name;
@@ -208 +200 @@
       moveMaker.OperatorParameter.ActualName = MoveMakerParameter.Name;
 
+      analyzer2.Name = "Analyzer (placeholder)";
+      analyzer2.OperatorParameter.ActualName = AnalyzerParameter.Name;
+
       subScopesRemover.RemoveAllSubScopes = true;
 
@@ -225 +220 @@
       iterationsComparator.ResultParameter.ActualName = "Terminate";
 
-      analyzer2.Name = "Analyzer (placeholder)";
-      analyzer2.OperatorParameter.ActualName = AnalyzerParameter.Name;
-
       resultsCollector3.CopyValue = new BoolValue(true);
       resultsCollector3.CollectedValues.Add(new LookupParameter<IntValue>("Evaluated Moves", null, "EvaluatedMoves"));
@@ -244 +236 @@
       subScopesProcessor0.Operators.Add(bestQualityInitializer);
       subScopesProcessor0.Successor = resultsCollector1;
+      bestQualityInitializer.Successor = analyzer1;
+      analyzer1.Successor = null;
       resultsCollector1.Successor = resultsCollector2;
       resultsCollector2.Successor = solutionProcessor;
@@ -250 +244 @@
       moveGenerator.Successor = moveEvaluationProcessor;
       moveEvaluationProcessor.Operator = moveEvaluator;
-      moveEvaluationProcessor.Successor = moveAnalyzer;
+      moveEvaluationProcessor.Successor = moveQualitySorter;
       moveEvaluator.Successor = evaluatedMovesCounter;
       evaluatedMovesCounter.Successor = tabuChecker;
       tabuChecker.Successor = null;
-      moveAnalyzer.Successor = moveQualitySorter;
       moveQualitySorter.Successor = tabuSelector;
       tabuSelector.Successor = emptyNeighborhoodBranch1;
-      emptyNeighborhoodBranch1.FalseBranch = rightReducer;
+      emptyNeighborhoodBranch1.FalseBranch = moveMakingProcessor;
       emptyNeighborhoodBranch1.TrueBranch = null;
       emptyNeighborhoodBranch1.Successor = subScopesRemover;
-      rightReducer.Successor = moveMakingProcessor;
-      moveMakingProcessor.Operators.Add(tabuMaker);
-      moveMakingProcessor.Successor = null;
+      moveMakingProcessor.Operators.Add(new EmptyOperator());
+      moveMakingProcessor.Operators.Add(selectedMoveMakingProcesor);
+      moveMakingProcessor.Successor = mergingReducer;
+      selectedMoveMakingProcesor.Operator = tabuMaker;
+      selectedMoveMakingProcesor.Successor = null;
       tabuMaker.Successor = moveMaker;
       moveMaker.Successor = null;
+      mergingReducer.Successor = analyzer2;
+      analyzer2.Successor = null;
       subScopesRemover.Successor = null;
       iterationsCounter.Successor = iterationsComparator;
-      iterationsComparator.Successor = subScopesProcessor1;
-      subScopesProcessor1.Operators.Add(analyzer2);
-      subScopesProcessor1.Successor = resultsCollector3;
+      iterationsComparator.Successor = resultsCollector3;
       resultsCollector3.Successor = emptyNeighborhoodBranch2;
       emptyNeighborhoodBranch2.TrueBranch = null;