Changeset 3636 for trunk/sources/HeuristicLab.Algorithms.LocalSearch

Timestamp:

05/05/10 14:52:19 (14 years ago)

Author:

abeham

Message:

#999

• changes in LS
  • counting evaluated moves
  • tracking best quality which is needed by the algorithm
• changes in TS
  • adapted to analyzer
  • added a neighborhood analyzer that shows what percentage of the neighborhood is tabu

Location:

trunk/sources/HeuristicLab.Algorithms.LocalSearch/3.3

Files:

• LocalSearch.cs (modified) (2 diffs)
• LocalSearchMainLoop.cs (modified) (8 diffs)

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

@@ -140 +140 @@
       Parameters.Add(new ValueParameter<IntValue>("MaximumIterations", "The maximum number of generations which should be processed.", new IntValue(1000)));
       Parameters.Add(new ValueParameter<IntValue>("SampleSize", "Number of moves that MultiMoveGenerators should create. This is ignored for Exhaustive- and SingleMoveGenerators.", new IntValue(100)));
-      Parameters.Add(new ValueParameter<MultiAnalyzer<IPopulationAnalyzer>>("MoveAnalyzer", "The operator used to analyze the moves in each iteration.", new MultiAnalyzer<IPopulationAnalyzer>()));
-      Parameters.Add(new ValueParameter<MultiAnalyzer<ISolutionAnalyzer>>("Analyzer", "The operator used to analyze each iteration.", new MultiAnalyzer<ISolutionAnalyzer>()));
+      Parameters.Add(new ValueParameter<MultiAnalyzer<IPopulationAnalyzer>>("MoveAnalyzer", "The operator used to analyze the moves.", new MultiAnalyzer<IPopulationAnalyzer>()));
+      Parameters.Add(new ValueParameter<MultiAnalyzer<ISolutionAnalyzer>>("Analyzer", "The operator used to analyze the solution.", new MultiAnalyzer<ISolutionAnalyzer>()));
       
       RandomCreator randomCreator = new RandomCreator();
@@ -229 +229 @@
       ParameterizeMoveEvaluators();
       ParameterizeMoveMakers();
+      ParameterizeAnalyzers();
       base.Problem_OperatorsChanged(sender, e);
     }

trunk/sources/HeuristicLab.Algorithms.LocalSearch/3.3/LocalSearchMainLoop.cs

@@ -104 +104 @@
       Parameters.Add(new ValueLookupParameter<IOperator>("MoveEvaluator", "The operator that evaluates a move."));
 
-      Parameters.Add(new ValueLookupParameter<IOperator>("MoveAnalyzer", "The operator used to analyze the moves in each iteration."));
-      Parameters.Add(new ValueLookupParameter<IOperator>("Analyzer", "The operator used to analyze each iteration."));
+      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 ScopeParameter("CurrentScope", "The current scope which represents a population of solutions on which the TS should be applied."));
       #endregion
@@ -111 +111 @@
       #region Create operators
       VariableCreator variableCreator = new VariableCreator();
+      SubScopesProcessor subScopesProcessor0 = new SubScopesProcessor();
+      Assigner bestQualityInitializer = new Assigner();
+      Placeholder analyzer1 = new Placeholder();
       ResultsCollector resultsCollector1 = new ResultsCollector();
-      UniformSubScopesProcessor uniformSubScopesProcessor0 = new UniformSubScopesProcessor();
-      Placeholder analyzer1 = new Placeholder();
-      UniformSubScopesProcessor mainProcessor = new UniformSubScopesProcessor();
+      SubScopesProcessor mainProcessor = new SubScopesProcessor();
       Placeholder moveGenerator = new Placeholder();
       UniformSubScopesProcessor moveEvaluationProcessor = new UniformSubScopesProcessor();
       Placeholder moveEvaluator = new Placeholder();
+      IntCounter evaluatedMovesCounter = new IntCounter();
       Placeholder moveAnalyzer = new Placeholder();
       BestSelector bestSelector = new BestSelector();
       RightReducer rightReducer = new RightReducer();
-      UniformSubScopesProcessor moveMakingProcessor = new UniformSubScopesProcessor();
+      SubScopesProcessor moveMakingProcessor = new SubScopesProcessor();
       QualityComparator qualityComparator = new QualityComparator();
       ConditionalBranch improvesQualityBranch = new ConditionalBranch();
       Placeholder moveMaker = new Placeholder();
+      Assigner bestQualityUpdater = new Assigner();
       SubScopesRemover subScopesRemover = new SubScopesRemover();
       IntCounter iterationsCounter = new IntCounter();
       Comparator iterationsComparator = new Comparator();
+      SubScopesProcessor subScopesProcessor1 = new SubScopesProcessor();
+      Placeholder analyzer2 = new Placeholder();
       ResultsCollector resultsCollector2 = new ResultsCollector();
-      UniformSubScopesProcessor uniformSubScopesProcessor1 = new UniformSubScopesProcessor();
-      Placeholder analyzer2 = new Placeholder();
       ConditionalBranch iterationsTermination = new ConditionalBranch();
 
       variableCreator.CollectedValues.Add(new ValueParameter<IntValue>("Iterations", new IntValue(0)));
-
-      resultsCollector1.CollectedValues.Add(new LookupParameter<IntValue>("Iterations"));
-      resultsCollector1.ResultsParameter.ActualName = ResultsParameter.Name;
+      variableCreator.CollectedValues.Add(new ValueParameter<DoubleValue>("BestQuality", new DoubleValue(0)));
+      variableCreator.CollectedValues.Add(new ValueParameter<IntValue>("EvaluatedMoves", new IntValue(0)));
+
+      bestQualityInitializer.Name = "Initialize BestQuality";
+      bestQualityInitializer.LeftSideParameter.ActualName = "BestQuality";
+      bestQualityInitializer.RightSideParameter.ActualName = QualityParameter.Name;
 
       analyzer1.Name = "Analyzer (placeholder)";
       analyzer1.OperatorParameter.ActualName = AnalyzerParameter.Name;
 
-      mainProcessor.Name = "Solution processor (UniformSubScopesProcessor)";
+      resultsCollector1.CollectedValues.Add(new LookupParameter<IntValue>("Iterations"));
+      resultsCollector1.CollectedValues.Add(new LookupParameter<DoubleValue>("Best Quality", null, "BestQuality"));
+      resultsCollector1.CollectedValues.Add(new LookupParameter<IntValue>("Evaluated Moves", null, "EvaluatedMoves"));
+      resultsCollector1.ResultsParameter.ActualName = ResultsParameter.Name;
 
       moveGenerator.Name = "MoveGenerator (placeholder)";
@@ -148 +157 @@
       moveEvaluator.Name = "MoveEvaluator (placeholder)";
       moveEvaluator.OperatorParameter.ActualName = MoveEvaluatorParameter.Name;
+
+      evaluatedMovesCounter.Name = "EvaluatedMoves + 1";
+      evaluatedMovesCounter.ValueParameter.ActualName = "EvaluatedMoves";
+      evaluatedMovesCounter.Increment = new IntValue(1);
 
       moveAnalyzer.Name = "MoveAnalyzer (placeholder)";
@@ -157 +170 @@
       bestSelector.QualityParameter.ActualName = MoveQualityParameter.Name;
 
-      moveMakingProcessor.Name = "MoveMaking processor (UniformSubScopesProcessor)";
-
       qualityComparator.LeftSideParameter.ActualName = MoveQualityParameter.Name;
       qualityComparator.RightSideParameter.ActualName = QualityParameter.Name;
@@ -167 +178 @@
       moveMaker.Name = "MoveMaker (placeholder)";
       moveMaker.OperatorParameter.ActualName = MoveMakerParameter.Name;
+
+      bestQualityUpdater.Name = "Update BestQuality";
+      bestQualityUpdater.LeftSideParameter.ActualName = "BestQuality";
+      bestQualityUpdater.RightSideParameter.ActualName = QualityParameter.Name;
 
       subScopesRemover.RemoveAllSubScopes = true;
@@ -180 +195 @@
       iterationsComparator.ResultParameter.ActualName = "Terminate";
 
-      resultsCollector2.CollectedValues.Add(new LookupParameter<IntValue>("Iterations"));
-      resultsCollector2.ResultsParameter.ActualName = ResultsParameter.Name;
-
       analyzer2.Name = "Analyzer (placeholder)";
       analyzer2.OperatorParameter.ActualName = AnalyzerParameter.Name;
+
+      resultsCollector2.CollectedValues.Add(new LookupParameter<IntValue>("Iterations"));
+      resultsCollector2.CollectedValues.Add(new LookupParameter<DoubleValue>("Best Quality", null, "BestQuality"));
+      resultsCollector2.CollectedValues.Add(new LookupParameter<IntValue>("Evaluated Moves", null, "EvaluatedMoves"));
+      resultsCollector2.ResultsParameter.ActualName = ResultsParameter.Name;
 
       iterationsTermination.Name = "Iterations Termination Condition";
@@ -192 +209 @@
       #region Create operator graph
       OperatorGraph.InitialOperator = variableCreator;
-      variableCreator.Successor = resultsCollector1;
-      resultsCollector1.Successor = uniformSubScopesProcessor0;
-      uniformSubScopesProcessor0.Operator = analyzer1;
-      uniformSubScopesProcessor0.Successor = mainProcessor;
+      variableCreator.Successor = subScopesProcessor0;
+      subScopesProcessor0.Operators.Add(bestQualityInitializer);
+      subScopesProcessor0.Successor = resultsCollector1;
+      bestQualityInitializer.Successor = analyzer1;
       analyzer1.Successor = null;
-      mainProcessor.Operator = moveGenerator;
+      resultsCollector1.Successor = mainProcessor;
+      mainProcessor.Operators.Add(moveGenerator);
       mainProcessor.Successor = iterationsCounter;
       moveGenerator.Successor = moveEvaluationProcessor;
       moveEvaluationProcessor.Operator = moveEvaluator;
       moveEvaluationProcessor.Successor = moveAnalyzer;
+      moveEvaluator.Successor = evaluatedMovesCounter;
+      evaluatedMovesCounter.Successor = null;
       moveAnalyzer.Successor = bestSelector;
       bestSelector.Successor = rightReducer;
       rightReducer.Successor = moveMakingProcessor;
-      moveMakingProcessor.Operator = qualityComparator;
+      moveMakingProcessor.Operators.Add(qualityComparator);
       moveMakingProcessor.Successor = subScopesRemover;
       subScopesRemover.Successor = null;
@@ -212 +232 @@
       improvesQualityBranch.FalseBranch = null;
       improvesQualityBranch.Successor = null;
-      moveMaker.Successor = null;
+      moveMaker.Successor = bestQualityUpdater;
+      bestQualityUpdater.Successor = null;
       iterationsCounter.Successor = iterationsComparator;
-      iterationsComparator.Successor = resultsCollector2;
-      resultsCollector2.Successor = uniformSubScopesProcessor1;
-      uniformSubScopesProcessor1.Operator = analyzer2;
-      uniformSubScopesProcessor1.Successor = iterationsTermination;
+      iterationsComparator.Successor = subScopesProcessor1;
+      subScopesProcessor1.Operators.Add(analyzer2);
+      subScopesProcessor1.Successor = resultsCollector2;
       analyzer2.Successor = null;
+      resultsCollector2.Successor = iterationsTermination;
       iterationsTermination.TrueBranch = null;
       iterationsTermination.FalseBranch = mainProcessor;