Changeset 15507 for branches/GeneralizedQAP

Timestamp:

12/11/17 15:42:12 (7 years ago)

Author:

abeham

Message:

#1614:

• fixed some bugs introduced in last commit (project file, tests)
• fixed ApproximateLocalSearch due to change in move evaluator that outputs an absolute quality of the move and not a delta
• added evaluated solution counting to approximate local search
• GRASP+PR: restructured main loop and combined iteration initialization with variable creator outside

Location:

branches/GeneralizedQAP

Files:

• HeuristicLab.Algorithms.GRASP/3.3/GRASPWithPathRelinking.cs (modified) (4 diffs)
• HeuristicLab.Algorithms.GRASP/3.3/GRASPWithPathRelinkingMainLoop.cs (modified) (7 diffs)
• HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Evaluation/GQAPNMoveEvaluator.cs (modified) (1 diff)
• HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/HeuristicLab.Problems.GeneralizedQuadraticAssignment-3.3.csproj (modified) (1 diff)
• HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/LocalImprovers/ApproximateLocalSearch.cs (modified) (5 diffs)
• UnitTests/CordeauCrossoverTest.cs (modified) (1 diff)

branches/GeneralizedQAP/HeuristicLab.Algorithms.GRASP/3.3/GRASPWithPathRelinking.cs

@@ -26 +26 @@
 using HeuristicLab.Core;
 using HeuristicLab.Data;
+using HeuristicLab.Operators;
 using HeuristicLab.Optimization;
 using HeuristicLab.Optimization.Operators;
@@ -111 +112 @@
       get { return (RandomCreator)OperatorGraph.InitialOperator; }
     }
+    private VariableCreator VariableCreator {
+      get { return (VariableCreator)RandomCreator.Successor; }
+    }
     private SolutionsCreator SolutionsCreator {
-      get { return (SolutionsCreator)RandomCreator.Successor; }
+      get { return (SolutionsCreator)VariableCreator.Successor; }
+    }
+    private SubScopesCounter SubScopesCounter {
+      get { return (SubScopesCounter)SolutionsCreator.Successor; }
+    }
+    private ResultsCollector ResultsCollector {
+      get { return (ResultsCollector)SubScopesCounter.Successor; }
     }
     private GRASPWithPathRelinkingMainLoop MainLoop {
-      get { return SolutionsCreator.Successor as GRASPWithPathRelinkingMainLoop; }
+      get { return (GRASPWithPathRelinkingMainLoop)ResultsCollector.Successor; }
     }
     #endregion
@@ -153 +163 @@
       randomCreator.SetSeedRandomlyParameter.ActualName = SetSeedRandomlyParameter.Name;
       randomCreator.SetSeedRandomlyParameter.Value = null;
-
+      
+      var variableCreator = new VariableCreator();
+      variableCreator.CollectedValues.Add(new ValueParameter<IntValue>("EvaluatedSolutions", new IntValue(0)));
+      variableCreator.CollectedValues.Add(new ValueParameter<IntValue>("Iterations", new IntValue(0)));
+      randomCreator.Successor = variableCreator;
+      
       var solutionsCreator = new SolutionsCreator();
       solutionsCreator.NumberOfSolutionsParameter.ActualName = MinimumEliteSetSizeParameter.Name;
       solutionsCreator.ParallelParameter.Value = new BoolValue(true);
-      randomCreator.Successor = solutionsCreator;
+      variableCreator.Successor = solutionsCreator;
+
+      var subscopesCounter = new SubScopesCounter();
+      subscopesCounter.Name = "EvaluatedSolutions++";
+      subscopesCounter.AccumulateParameter.Value.Value = true;
+      subscopesCounter.ValueParameter.ActualName = "EvaluatedSolutions";
+      solutionsCreator.Successor = subscopesCounter;
+
+      var resultsCollector = new ResultsCollector();
+      resultsCollector.CopyValue.Value = false;
+      resultsCollector.CollectedValues.Add(new LookupParameter<IntValue>("EvaluatedSolutions", "Counter for the number of times the evaluation function is called."));
+      resultsCollector.CollectedValues.Add(new LookupParameter<IntValue>("Iterations", "The algorithm's current iteration"));
+      subscopesCounter.Successor = resultsCollector;
 
       var mainLoop = new GRASPWithPathRelinkingMainLoop();
@@ -168 +195 @@
       mainLoop.PathRelinkingParameter.ActualName = PathRelinkingParameter.Name;
       mainLoop.ResultsParameter.ActualName = "Results";
-      solutionsCreator.Successor = mainLoop;
+      resultsCollector.Successor = mainLoop;
 
       InitializeOperators();

branches/GeneralizedQAP/HeuristicLab.Algorithms.GRASP/3.3/GRASPWithPathRelinkingMainLoop.cs

@@ -37 +37 @@
   [StorableClass]
   public class GRASPWithPathRelinkingMainLoop : AlgorithmOperator {
+    public IValueLookupParameter<IntValue> IterationsParameter {
+      get { return (IValueLookupParameter<IntValue>)Parameters["Iterations"]; }
+    }
     public IValueLookupParameter<IOperator> SolutionCreatorParameter {
       get { return (IValueLookupParameter<IOperator>)Parameters["SolutionCreator"]; }
@@ -74 +77 @@
     public GRASPWithPathRelinkingMainLoop()
       : base() {
+      Parameters.Add(new ValueLookupParameter<IntValue>("Iterations", "The algorithm's current iteration."));
       Parameters.Add(new ValueLookupParameter<IOperator>("SolutionCreator", "The solution creation procedure which ideally should be a greedy initialization heuristic."));
       Parameters.Add(new ValueLookupParameter<IOperator>("Evaluator", "The evaluator which calculates the fitness of a solutions."));
@@ -85 +89 @@
       Parameters.Add(new ValueLookupParameter<IOperator>("Analyzer", "The analyzer that is to be applied."));
 
-      var variableCreator1 = new VariableCreator();
-      variableCreator1.Name = "Iterations = 0";
-      variableCreator1.CollectedValues.Add(new ValueParameter<IntValue>("Iterations", new IntValue(0)));
-
-      var resultsCollector = new ResultsCollector();
-      resultsCollector.CopyValue = new BoolValue(false);
-      resultsCollector.CollectedValues.Add(new LookupParameter<IntValue>("Iterations"));
+      var analyzer1 = new Placeholder() { Name = "(Analyzer)" };
+      analyzer1.OperatorParameter.ActualName = AnalyzerParameter.Name;
 
       var selector1 = new RandomSelector();
@@ -111 +110 @@
       var eo2 = new EmptyOperator();
 
-      var placeholder1 = new Placeholder();
-      placeholder1.Name = "(LocalImprovement)";
+      var placeholder1 = new Placeholder() { Name = "(LocalImprovement)" };
       placeholder1.OperatorParameter.ActualName = LocalImprovementParameter.Name;
 
@@ -120 +118 @@
       var ssp3 = new SubScopesProcessor();
 
-      var placeholder2 = new Placeholder();
-      placeholder2.Name = "(PathRelinking)";
+      var placeholder2 = new Placeholder() { Name = "(PathRelinking)" };
       placeholder2.OperatorParameter.ActualName = PathRelinkingParameter.Name;
 
-      var placeholder3 = new Placeholder();
-      placeholder3.Name = "(Evaluator)";
+      var placeholder3 = new Placeholder() { Name = "(Evaluator)" };
       placeholder3.OperatorParameter.ActualName = EvaluatorParameter.Name;
 
@@ -137 +133 @@
       placeholder4.OperatorParameter.ActualName = LocalImprovementParameter.Name;
 
-      var placeholder5 = new Placeholder();
-      placeholder5.Name = "(EliteSetReplacer)";
+      var placeholder5 = new Placeholder() { Name = "(EliteSetReplacer)" };
       placeholder5.OperatorParameter.ActualName = EliteSetReducerParameter.Name;
 
-      var counter = new IntCounter();
-      counter.Name = "Iterations++";
-      counter.ValueParameter.ActualName = "Iterations";
+      var counter = new IntCounter() { Name = "Iterations++" };
+      counter.ValueParameter.ActualName = IterationsParameter.Name;
       counter.Increment = new IntValue(1);
 
-      var analyzer1 = new Placeholder();
-      analyzer1.Name = "(Analyzer)";
-      analyzer1.OperatorParameter.ActualName = AnalyzerParameter.Name;
-
-      var comparator3 = new Comparator();
-      comparator3.Name = "Iterations >= MaximumIterations";
+      var analyzer2 = new Placeholder() { Name = "(Analyzer)" };
+      analyzer2.OperatorParameter.ActualName = AnalyzerParameter.Name;
+
+      var comparator3 = new Comparator() { Name = "Iterations >= MaximumIterations" };
       comparator3.Comparison.Value = ComparisonType.GreaterOrEqual;
-      comparator3.LeftSideParameter.ActualName = "Iterations";
+      comparator3.LeftSideParameter.ActualName = IterationsParameter.Name;
       comparator3.RightSideParameter.ActualName = MaximumIterationsParameter.Name;
       comparator3.ResultParameter.ActualName = "TerminatedByIteration";
 
-      var conditionalBranch3 = new ConditionalBranch();
-      conditionalBranch3.Name = "Terminate by Iterations?";
+      var conditionalBranch3 = new ConditionalBranch() { Name = "Terminate by Iterations?" };
       conditionalBranch3.ConditionParameter.ActualName = "TerminatedByIteration";
 
-      OperatorGraph.InitialOperator = variableCreator1;
-      variableCreator1.Successor = resultsCollector;
-      resultsCollector.Successor = selector1;
+      OperatorGraph.InitialOperator = analyzer1;
+      analyzer1.Successor = selector1;
       selector1.Successor = ssp1;
       ssp1.Operators.Add(eo1);
@@ -183 +173 @@
       placeholder4.Successor = null;
       placeholder5.Successor = counter;
-      counter.Successor = analyzer1;
-      analyzer1.Successor = comparator3;
+      counter.Successor = analyzer2;
+      analyzer2.Successor = comparator3;
       comparator3.Successor = conditionalBranch3;
       conditionalBranch3.TrueBranch = null;

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Evaluation/GQAPNMoveEvaluator.cs

@@ -130 +130 @@
 
       MoveEvaluationParameter.ActualValue = moveEvaluation;
+      MoveQualityParameter.ActualValue = new DoubleValue(problemInstance.ToSingleObjective(moveEvaluation));
       return base.Apply();
     }

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/HeuristicLab.Problems.GeneralizedQuadraticAssignment-3.3.csproj

@@ -102 +102 @@
     <Compile Include="GQAPAssignment.cs" />
     <Compile Include="GQAPInstance.cs" />
+    <Compile Include="Interfaces\Parameter\IAssignmentAwareGQAPOperator.cs" />
     <Compile Include="Operators\Crossovers\CordeauCrossover.cs" />
     <Compile Include="SolutionCreators\SlackMinimizationSolutionCreator.cs" />

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/LocalImprovers/ApproximateLocalSearch.cs

@@ -106 +106 @@
     /// <param name="maximumIterations">The maximum number of iterations that should be performed each time the candidate list is generated.</param>
     /// <param name="problemInstance">The problem instance that contains the data.</param>
+    /// <param name="evaluatedSolutions">The number of evaluated solutions.</param>
     /// <param name="oneMoveProbability">The probability for performing a 1-move, which is the opposite of performing a 2-move.</param>
     public static void Apply(IRandom random, IntegerVector assignment,
       DoubleValue quality, ref Evaluation evaluation, IntValue maxCLS, IntValue maximumIterations,
-      GQAPInstance problemInstance, PercentValue oneMoveProbability) {
+      GQAPInstance problemInstance, IntValue evaluatedSolutions, PercentValue oneMoveProbability) {
       var capacities = problemInstance.Capacities;
       var demands = problemInstance.Demands;
-      //var weights = problemInstance.Weights;
-      //var distances = problemInstance.Distances;
-      //var installationCosts = problemInstance.InstallationCosts;
+      var evaluations = 0.0;
+      var deltaEvaluationFactor = 1.0 / assignment.Length;
       while (true) {
         int count = 0;
@@ -126 +126 @@
           
           var moveEval = GQAPNMoveEvaluator.Evaluate(move, assignment, evaluation, problemInstance);
+          evaluations += move.NewAssignments.Count * deltaEvaluationFactor;
           double moveQuality = problemInstance.ToSingleObjective(moveEval);
 
-          if (moveEval.ExcessDemand <= 0.0 && moveQuality < 0.0) {
+          if (moveEval.ExcessDemand <= 0.0 && moveQuality < quality.Value) {
             CLS.Add(Tuple.Create(move, moveQuality, moveEval));
             sum += 1.0 / moveQuality;
@@ -135 +136 @@
         } while (CLS.Count < maxCLS.Value && count < maximumIterations.Value);
 
-        if (CLS.Count == 0)
+        if (CLS.Count == 0) {
+          evaluatedSolutions.Value += (int)Math.Ceiling(evaluations);
           return; // END
-        else {
+        } else {
           var ball = random.NextDouble() * sum;
           var selected = CLS.Last();
@@ -148 +150 @@
           }
           NMoveMaker.Apply(assignment, selected.Item1);
-          quality.Value += selected.Item2;
+          quality.Value = selected.Item2;
           evaluation = selected.Item3;
         }
@@ -163 +165 @@
         MaximumIterationsParameter.ActualValue,
         ProblemInstanceParameter.ActualValue,
+        EvaluatedSolutionsParameter.ActualValue,
         OneMoveProbabilityParameter.ActualValue);
       EvaluationParameter.ActualValue = evaluation;

branches/GeneralizedQAP/UnitTests/CordeauCrossoverTest.cs

@@ -45 +45 @@
 
         try {
-          CordeauCrossover.Apply(random, gqap.Maximization,
+          CordeauCrossover.Apply(random,
             parent1,
             new DoubleValue(gqap.Evaluate(parent1)),