Changeset 15562 for branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment

Timestamp:

12/29/17 23:56:43 (7 years ago)

Author:

abeham

Message:

#1614: added additional algorithms

Location:

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3

Files:

• HeuristicLab.Problems.GeneralizedQuadraticAssignment-3.3.csproj (modified) (1 diff)
• Interfaces/Operator/IGQAPLocalImprovementOperator.cs (modified) (2 diffs)
• Moves/ExhaustiveOneMoveGenerator.cs (copied) (copied from branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Moves/StochasticNMoveMultiMoveGenerator.cs) (1 diff)
• Operators/LocalImprovers/OneOptLocalSearch.cs (copied) (copied from branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/LocalImprovers/ApproximateLocalSearch.cs) (8 diffs)

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

@@ -104 +104 @@
     <Compile Include="GQAPInstance.cs" />
     <Compile Include="Interfaces\Parameter\IAssignmentAwareGQAPOperator.cs" />
+    <Compile Include="Moves\ExhaustiveOneMoveGenerator.cs" />
     <Compile Include="Operators\Crossovers\CordeauCrossover.cs" />
+    <Compile Include="Operators\LocalImprovers\OneOptLocalSearch.cs" />
     <Compile Include="SolutionCreators\SlackMinimizationSolutionCreator.cs" />
     <Compile Include="SolutionCreators\RandomButFeasibleSolutionCreator.cs" />

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Interfaces/Operator/IGQAPLocalImprovementOperator.cs

@@ -21 +21 @@
 
 using HeuristicLab.Core;
-using HeuristicLab.Data;
 using HeuristicLab.Encodings.IntegerVectorEncoding;
 using HeuristicLab.Optimization;
@@ -27 +26 @@
 namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment {
   public interface IGQAPLocalImprovementOperator : ILocalImprovementAlgorithmOperator {
-    IValueLookupParameter<IntValue> MaximumCandidateListSizeParameter { get; }
     ILookupParameter<IntegerVector> AssignmentParameter { get; }
   }

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Moves/ExhaustiveOneMoveGenerator.cs

@@ -20 +20 @@
 #endregion
 
+using System;
 using System.Collections.Generic;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
-using HeuristicLab.Data;
 using HeuristicLab.Encodings.IntegerVectorEncoding;
 using HeuristicLab.Optimization;
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Random;
 
 namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment {
-  [Item("Stochastic N-Move MultiMoveGenerator", "Randomly samples a number of N-Moves.")]
+  [Item("Exhaustive 1-Move MoveGenerator", "Exhaustively generates all possible 1-moves.")]
   [StorableClass]
-  public class StochasticNMoveMultiMoveGenerator : GQAPNMoveGenerator, IStochasticOperator, IMultiMoveGenerator {
+  public class ExhaustiveOneMoveGenerator : GQAPNMoveGenerator, IStochasticOperator, IExhaustiveMoveGenerator {
     
     public ILookupParameter<IRandom> RandomParameter {
       get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
     }
-    public IValueLookupParameter<IntValue> SampleSizeParameter {
-      get { return (IValueLookupParameter<IntValue>)Parameters["SampleSize"]; }
-    }
 
     [StorableConstructor]
-    protected StochasticNMoveMultiMoveGenerator(bool deserializing) : base(deserializing) { }
-    protected StochasticNMoveMultiMoveGenerator(StochasticNMoveMultiMoveGenerator original, Cloner cloner) : base(original, cloner) { }
-    public StochasticNMoveMultiMoveGenerator()
+    protected ExhaustiveOneMoveGenerator(bool deserializing) : base(deserializing) { }
+    protected ExhaustiveOneMoveGenerator(ExhaustiveOneMoveGenerator original, Cloner cloner) : base(original, cloner) { }
+    public ExhaustiveOneMoveGenerator()
       : base() {
       Parameters.Add(new LookupParameter<IRandom>("Random", "The random number generator that should be used."));
-      Parameters.Add(new ValueLookupParameter<IntValue>("SampleSize", "The number of moves to generate."));
+      NParameter.Value.Value = 1;
+      NParameter.Hidden = true;
     }
 
     public override IDeepCloneable Clone(Cloner cloner) {
-      return new StochasticNMoveMultiMoveGenerator(this, cloner);
+      return new ExhaustiveOneMoveGenerator(this, cloner);
     }
 
-    public static IEnumerable<NMove> Generate(IRandom random, IntegerVector assignment, int n, GQAPInstance problemInstance, int sampleSize) {
-      for (int i = 0; i < sampleSize; i++)
-        yield return StochasticNMoveSingleMoveGenerator.GenerateUpToN(random, assignment, n, problemInstance.Capacities);
+    public static IEnumerable<NMove> Generate(IntegerVector assignment, GQAPInstance problemInstance) {
+      var equipments = problemInstance.Demands.Length;
+      var locations = problemInstance.Capacities.Length;
+      var tmp = new int[equipments];
+      for (var e = 0; e < equipments; e++) {
+        var indices = new List<int> { e };
+        for (var l = 0; l < locations; l++) {
+          if (assignment[e] == l) continue;
+          var reassign = (int[])tmp.Clone();
+          reassign[e] = l + 1;
+          yield return new NMove(reassign, indices);
+        }
+      }
+    }
+
+    public static IEnumerable<NMove> GenerateAllNxM(GQAPInstance problemInstance) {
+      var equipments = problemInstance.Demands.Length;
+      var locations = problemInstance.Capacities.Length;
+      var tmp = new int[equipments];
+      for (var e = 0; e < equipments; e++) {
+        var indices = new List<int> { e };
+        for (var l = 0; l < locations; l++) {
+          var reassign = (int[])tmp.Clone();
+          reassign[e] = l + 1;
+          yield return new NMove(reassign, indices);
+        }
+      }
     }
 
     public override IEnumerable<NMove> GenerateMoves(IntegerVector assignment, int n, GQAPInstance problemInstance) {
-      return Generate(RandomParameter.ActualValue, assignment, n, problemInstance, SampleSizeParameter.ActualValue.Value);
+      if (n != 1) throw new ArgumentException("N must be equal to 1 for the exhaustive 1-move generator.");
+      var random = RandomParameter.ActualValue;
+      return Generate(assignment, problemInstance).Shuffle(random);
     }
   }

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

@@ -1 @@
-#region License Information
+
+#region License Information
 /* HeuristicLab
  * Copyright (C) 2002-2017 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
@@ -21 +22 @@
 
 using System;
-using System.Collections.Generic;
 using System.Linq;
 using HeuristicLab.Common;
@@ -34 +34 @@
 
 namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment {
-  /// <summary>
-  /// This is an implementation of the algorithm described in Mateus, G.R., Resende, M.G.C. & Silva, R.M.A. J Heuristics (2011) 17: 527. https://doi.org/10.1007/s10732-010-9144-0
-  /// </summary>
-  [Item("ApproximateLocalSearch", "The approximate local search is described in Mateus, G., Resende, M., and Silva, R. 2011. GRASP with path-relinking for the generalized quadratic assignment problem. Journal of Heuristics 17, Springer Netherlands, pp. 527-565.")]
+  [Item("1-opt LocalSearch", "A simple exhaustive 1-change local search.")]
   [StorableClass]
-  public class ApproximateLocalSearch : SingleSuccessorOperator, IProblemInstanceAwareGQAPOperator,
+  public class OneOptLocalSearch : SingleSuccessorOperator, IProblemInstanceAwareGQAPOperator,
     IQualityAwareGQAPOperator, IGQAPLocalImprovementOperator, IAssignmentAwareGQAPOperator, IStochasticOperator {
     public IProblem Problem { get; set; }
@@ -67 +64 @@
       get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
     }
-    public IValueLookupParameter<IntValue> MaximumCandidateListSizeParameter {
-      get { return (IValueLookupParameter<IntValue>)Parameters["MaximumCandidateListSize"]; }
-    }
-    public IValueLookupParameter<PercentValue> OneMoveProbabilityParameter {
-      get { return (IValueLookupParameter<PercentValue>)Parameters["OneMoveProbability"]; }
-    }
     public ILookupParameter<ResultCollection> ResultsParameter {
       get { return (ILookupParameter<ResultCollection>)Parameters["Results"]; }
     }
-    public IValueLookupParameter<BoolValue> GreedyParameter {
-      get { return (IValueLookupParameter<BoolValue>)Parameters["Greedy"]; }
-    }
 
     [StorableConstructor]
-    protected ApproximateLocalSearch(bool deserializing) : base(deserializing) { }
-    protected ApproximateLocalSearch(ApproximateLocalSearch original, Cloner cloner) : base(original, cloner) { }
-    public ApproximateLocalSearch()
+    protected OneOptLocalSearch(bool deserializing) : base(deserializing) { }
+    protected OneOptLocalSearch(OneOptLocalSearch original, Cloner cloner) : base(original, cloner) { }
+    public OneOptLocalSearch()
       : base() {
       Parameters.Add(new LookupParameter<GQAPInstance>("ProblemInstance", GQAP.ProblemInstanceDescription));
@@ -89 +77 @@
       Parameters.Add(new LookupParameter<DoubleValue>("Quality", ""));
       Parameters.Add(new LookupParameter<Evaluation>("Evaluation", GQAP.EvaluationDescription));
-      Parameters.Add(new ValueLookupParameter<IntValue>("MaximumIterations", "The maximum number of iterations that should be performed."));
+      Parameters.Add(new ValueLookupParameter<IntValue>("MaximumIterations", "This parameter is ignored by the operator.") { Hidden = true });
       Parameters.Add(new LookupParameter<IntValue>("EvaluatedSolutions", "The number of evaluated solution equivalents."));
       Parameters.Add(new LookupParameter<IRandom>("Random", "The random number generator to use."));
-      Parameters.Add(new ValueLookupParameter<IntValue>("MaximumCandidateListSize", "The maximum number of candidates that should be found in each step.", new IntValue(10)));
-      Parameters.Add(new ValueLookupParameter<PercentValue>("OneMoveProbability", "The probability for performing a 1-move, which is the opposite of performing a 2-move.", new PercentValue(.5)));
       Parameters.Add(new LookupParameter<ResultCollection>("Results", "The result collection that stores the results."));
-      Parameters.Add(new ValueLookupParameter<BoolValue>("Greedy", "Whether to use a greedy selection strategy or a probabilistic one.", new BoolValue(true)));
     }
 
     public override IDeepCloneable Clone(Cloner cloner) {
-      return new ApproximateLocalSearch(this, cloner);
+      return new OneOptLocalSearch(this, cloner);
     }
 
-    public static void Apply(IRandom random, GQAPSolution sol, int maxCLS,
-      double oneMoveProbability, int maximumIterations,
-      GQAPInstance problemInstance, out int evaluatedSolutions, bool greedy = true) {
+    public static void Apply(IRandom random, GQAPSolution sol,
+      GQAPInstance problemInstance, out int evaluatedSolutions) {
       var fit = problemInstance.ToSingleObjective(sol.Evaluation);
       var eval = sol.Evaluation;
-      Apply(random, sol.Assignment, ref fit, ref eval, maxCLS, oneMoveProbability, maximumIterations, problemInstance,
-        out evaluatedSolutions, greedy);
+      Apply(random, sol.Assignment, ref fit, ref eval, problemInstance, out evaluatedSolutions);
       sol.Evaluation = eval;
     }
@@ -125 +108 @@
     /// <param name="greedy">Greedy selection performed better in 5 of 8 instances according to the paper</param>
     public static void Apply(IRandom random, IntegerVector assignment,
-      ref double quality, ref Evaluation evaluation, int maxCLS,
-      double oneMoveProbability, int maximumIterations,
-      GQAPInstance problemInstance, out int evaluatedSolutions, bool greedy = true) {
+      ref double quality, ref Evaluation evaluation,
+      GQAPInstance problemInstance, out int evaluatedSolutions) {
       evaluatedSolutions = 0;
       var capacities = problemInstance.Capacities;
@@ -133 +115 @@
       var evaluations = 0.0;
       var deltaEvaluationFactor = 1.0 / assignment.Length;
-      while (true) { // line 1 of Algorithm 3
-        var count = 0; // line 2 of Algorithm 3
-        var CLS = new List<Tuple<NMove, double, Evaluation>>(); // line 3 of Algorithm 3
-        do {
-          var move = Move(random, assignment, oneMoveProbability, capacities); // line 4 of Algorithm 3
-
+      var change = true;
+      var moves = ExhaustiveOneMoveGenerator.GenerateAllNxM(problemInstance).ToList();
+      var slack = evaluation.Slack.ToList();
+      while (change) {
+        change = false;
+        var feasible = evaluation.IsFeasible;
+        foreach (var move in moves
+            .Where(x => {
+              var equip = x.Indices[0];
+              var assignTo = x.Reassignments[equip] - 1;
+              if (assignTo == assignment[equip]) return false;
+              var dem = problemInstance.Demands[equip];
+              if (feasible) return slack[assignTo] >= dem;
+              return slack[assignTo] - dem > slack[assignment[equip]];
+            })
+            .Shuffle(random)) {
           var moveEval = GQAPNMoveEvaluator.Evaluate(move, assignment, evaluation, problemInstance);
-          evaluations += move.Indices.Count * deltaEvaluationFactor;
-          double moveQuality = problemInstance.ToSingleObjective(moveEval);
-
-          if (moveEval.ExcessDemand <= 0.0 && moveQuality < quality) { // line 5 of Algorithm 3
-            CLS.Add(Tuple.Create(move, moveQuality, moveEval)); // line 6 of Algorithm 3
+          evaluations += deltaEvaluationFactor;
+          var moveQuality = problemInstance.ToSingleObjective(moveEval);
+          if (moveQuality < quality) {
+            NMoveMaker.Apply(assignment, move);
+            quality = moveQuality;
+            evaluation = moveEval;
+            change = true;
+            break;
           }
-          count++; // line 8 of Algorithm 3
-        } while (CLS.Count < maxCLS && count < maximumIterations); // line 9 of Algorithm 3
-
-        if (CLS.Count == 0) { // line 10 of Algorithm 3
-          evaluatedSolutions += (int)Math.Ceiling(evaluations);
-          return; // END
-        } else {
-          // line 11 of Algorithm 3
-          Tuple<NMove, double, Evaluation> selected;
-          if (greedy) {
-            selected = CLS.MinItems(x => x.Item2).Shuffle(random).First();
-          } else {
-            selected = CLS.SampleProportional(random, 1, CLS.Select(x => 1.0 / x.Item2), false, false).Single();
-          }
-          NMoveMaker.Apply(assignment, selected.Item1);
-          quality = selected.Item2;
-          evaluation = selected.Item3;
         }
       }
+      evaluatedSolutions += (int)Math.Ceiling(evaluations);
     }
 
@@ -183 +162 @@
         ref fit,
         ref evaluation,
-        MaximumCandidateListSizeParameter.ActualValue.Value,
-        OneMoveProbabilityParameter.ActualValue.Value,
-        MaximumIterationsParameter.ActualValue.Value,
         ProblemInstanceParameter.ActualValue,
-        out evaluatedSolutions,
-        GreedyParameter.ActualValue.Value);
+        out evaluatedSolutions);
 
       EvaluationParameter.ActualValue = evaluation;