Changeset 3195

Timestamp:

03/23/10 01:48:44 (15 years ago)

Author:

abeham

Message:

fixed algorithm when neighborhood contains only tabu moves. It will now terminate correctly. #840

Location:

trunk/sources/HeuristicLab.Algorithms.TabuSearch/3.3

Files:

• TabuSearchMainLoop.cs (modified) (7 diffs)
• TabuSelector.cs (modified) (3 diffs)

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

@@ -131 +131 @@
       BestAverageWorstQualityCalculator bestAverageWorstMoveQualityCalculator = new BestAverageWorstQualityCalculator();
       TabuSelector tabuSelector = new TabuSelector();
+      ConditionalBranch emptyNeighborhoodBranch1 = new ConditionalBranch();
       RightReducer rightReducer = new RightReducer();
       UniformSubScopesProcessor moveMakingProcessor = new UniformSubScopesProcessor();
@@ -136 +137 @@
       Placeholder moveMaker = new Placeholder();
       DataTableValuesCollector valuesCollector = new DataTableValuesCollector();
-      SubScopesRemover subScopesRemover = new SubScopesRemover();
+      SubScopesRemover subScopesRemover1 = new SubScopesRemover();
+      ConditionalBranch emptyNeighborhoodBranch2 = new ConditionalBranch();
+      UniformSubScopesProcessor removeMoves = new UniformSubScopesProcessor();
+      SubScopesRemover subScopesRemover2 = new SubScopesRemover();
       IntCounter iterationsCounter = new IntCounter();
       Comparator iterationsComparator = new Comparator();
@@ -150 +154 @@
       variableCreator.CollectedValues.Add(new ValueParameter<DoubleValue>("Worst Move Quality", new DoubleValue(0)));
       variableCreator.CollectedValues.Add(new ValueParameter<DataTable>("MoveQualities", new DataTable("MoveQualities")));
+      variableCreator.CollectedValues.Add(new ValueParameter<BoolValue>("EmptyNeighborhood", new BoolValue(false)));
 
       bestQualityMemorizer1.BestQualityParameter.ActualName = "BestQuality";
@@ -206 +211 @@
       moveMakingProcessor.Name = "MoveMaking processor (UniformSubScopesProcessor)";
 
+      emptyNeighborhoodBranch1.Name = "Neighborhood empty?";
+      emptyNeighborhoodBranch1.ConditionParameter.ActualName = "EmptyNeighborhood";
+
       tabuMoveMaker.Name = "TabuMoveMaker (placeholder)";
       tabuMoveMaker.OperatorParameter.ActualName = TabuMoveMakerParameter.Name;
@@ -212 +220 @@
       moveMaker.OperatorParameter.ActualName = MoveMakerParameter.Name;
 
-      subScopesRemover.RemoveAllSubScopes = true;
+      subScopesRemover1.RemoveAllSubScopes = true;
+
+      emptyNeighborhoodBranch2.Name = "Neighborhood empty?";
+      emptyNeighborhoodBranch2.ConditionParameter.ActualName = "EmptyNeighborhood";
+
+      subScopesRemover2.RemoveAllSubScopes = true;
 
       iterationsCounter.Name = "Iterations Counter";
@@ -254 +267 @@
       resultsCollector.Successor = mainProcessor;
       mainProcessor.Operator = moveGenerator;
-      mainProcessor.Successor = iterationsCounter;
+      mainProcessor.Successor = emptyNeighborhoodBranch2;
       moveGenerator.Successor = moveEvaluationProcessor;
       moveEvaluationProcessor.Operator = moveEvaluator;
@@ -263 +276 @@
       bestAverageWorstMoveQualityCalculator.Successor = valuesCollector;
       valuesCollector.Successor = tabuSelector;
-      tabuSelector.Successor = rightReducer;
+      tabuSelector.Successor = emptyNeighborhoodBranch1;
+      emptyNeighborhoodBranch1.FalseBranch = rightReducer;
+      emptyNeighborhoodBranch1.TrueBranch = null;
+      emptyNeighborhoodBranch1.Successor = null;
       rightReducer.Successor = moveMakingProcessor;
       moveMakingProcessor.Operator = tabuMoveMaker;
-      moveMakingProcessor.Successor = subScopesRemover;
+      moveMakingProcessor.Successor = subScopesRemover1;
       tabuMoveMaker.Successor = moveMaker;
       moveMaker.Successor = null;
-      subScopesRemover.Successor = null;
+      subScopesRemover1.Successor = null;
+      emptyNeighborhoodBranch2.FalseBranch = iterationsCounter;
+      emptyNeighborhoodBranch2.TrueBranch = removeMoves;
+      emptyNeighborhoodBranch2.Successor = null;
+      removeMoves.Operator = subScopesRemover2;
+      removeMoves.Successor = null;
+      subScopesRemover2.Successor = null;
       iterationsCounter.Successor = iterationsComparator;
       iterationsComparator.Successor = bestQualityMemorizer3;

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

@@ -72 +72 @@
       get { return (IValueLookupParameter<BoolValue>)Parameters["CopySelected"]; }
     }
+    public ILookupParameter<BoolValue> EmptyNeighborhoodParameter {
+      get { return (ILookupParameter<BoolValue>)Parameters["EmptyNeighborhood"]; }
+    }
 
     public BoolValue CopySelected {
@@ -90 +93 @@
       Parameters.Add(new SubScopesLookupParameter<BoolValue>("MoveTabu", "The tabu status of the move."));
       Parameters.Add(new ValueLookupParameter<BoolValue>("CopySelected", "True if the selected move should be copied.", new BoolValue(false)));
+      Parameters.Add(new LookupParameter<BoolValue>("EmptyNeighborhood", "Will be set to true if the neighborhood didn't contain any non-tabu moves. It is not set to false."));
     }
 
@@ -120 +124 @@
       }
 
-      if (selected[0] == null) throw new InvalidOperationException("TabuSelector: The neighborhood contained no or too little moves that are not tabu.");
+      if (selected[0] == null) {
+        EmptyNeighborhoodParameter.ActualValue = new BoolValue(true);
+        selected[0] = new Scope("All moves are tabu.");
+      }
 
       // remove from last to first so that the stored indices remain the same