Free cookie consent management tool by TermsFeed Policy Generator

Changeset 15558


Ignore:
Timestamp:
12/22/17 01:32:13 (7 years ago)
Author:
abeham
Message:

#1614: fixed bugs

Location:
branches/GeneralizedQAP
Files:
6 edited

Legend:

Unmodified
Added
Removed

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/GRASP.cs

    r15553 r15558  
    108108    }
    109109    [Storable]
    110     private FixedValueParameter<PercentValue> minimumDifferenceParameter;
    111     public IFixedValueParameter<PercentValue> MinimumDifferenceParameter {
     110    private FixedValueParameter<IntValue> minimumDifferenceParameter;
     111    public IFixedValueParameter<IntValue> MinimumDifferenceParameter {
    112112      get { return minimumDifferenceParameter; }
    113113    }
    … …  
    121121      set { seedParameter.Value.Value = value; }
    122122    }
     123    public int EliteSetSize {
     124      get { return eliteSetSizeParameter.Value.Value; }
     125      set { eliteSetSizeParameter.Value.Value = value; }
     126    }
    123127    public int MinimumEliteSetSize {
    124128      get { return minimiumEliteSetSizeParameter.Value.Value; }
    125129      set { minimiumEliteSetSizeParameter.Value.Value = value; }
    126130    }
    127     public int EliteSetSize {
    128       get { return eliteSetSizeParameter.Value.Value; }
    129       set { eliteSetSizeParameter.Value.Value = value; }
     131    public int MaximumIterations {
     132      get { return maximumIterationsParameter.Value.Value; }
     133      set { maximumIterationsParameter.Value.Value = value; }
     134    }
     135    public int MaximumLocalSearchIterations {
     136      get { return maximumLocalSearchIterationsParameter.Value.Value; }
     137      set { maximumLocalSearchIterationsParameter.Value.Value = value; }
    130138    }
    131139    public double CandidateSizeFactor {
    … …  
    141149      set { oneMoveProbabilityParameter.Value.Value = value; }
    142150    }
    143     public double MinimumDifference {
     151    public int MinimumDifference {
    144152      get { return minimumDifferenceParameter.Value.Value; }
    145153      set { minimumDifferenceParameter.Value.Value = value; }
    … …  
    174182      Parameters.Add(maximumCandidateListSizeParameter = new FixedValueParameter<IntValue>("MaximumCandidateListSize", "The maximum number of candidates that should be found in each step.", new IntValue(10)));
    175183      Parameters.Add(oneMoveProbabilityParameter = new FixedValueParameter<PercentValue>("OneMoveProbability", "The probability for performing a 1-move, which is the opposite of performing a 2-move.", new PercentValue(.5)));
    176       Parameters.Add(minimumDifferenceParameter = new FixedValueParameter<PercentValue>("MinimumDifference", "The minimum amount of difference between two solutions so that they are both accepted in the elite set.", new PercentValue(1e-7)));
     184      Parameters.Add(minimumDifferenceParameter = new FixedValueParameter<IntValue>("MinimumDifference", "The minimum amount of difference between two solutions so that they are both accepted in the elite set.", new IntValue(4)));
    177185      Problem = new GQAP();
    178186    }
    … …  
    252260            var fit = Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation);
    253261            double[] similarities = context.Population.Select(x => HammingSimilarityCalculator.CalculateSimilarity(x.Solution.Assignment, pi_prime.Assignment)).ToArray();
    254             if (similarities.Max() <= 1.0 - MinimumDifference) { // cond. 2 of line 13 in Algorithm 1
     262            if (similarities.Max() <= 1.0 - (MinimumDifference / (double)pi_prime.Assignment.Length)) { // cond. 2 of line 13 in Algorithm 1
    255263              var replacement = context.Population.Select((v, i) => new { V = v, Index = i })
    256264                                          .Where(x => x.V.Fitness >= fit).ToArray();
    … …  
    277285        }
    278286
    279         context.Iterations++;
    280 
    281287        IResult result;
    282288        if (Results.TryGetValue("Iterations", out result))
    … …  
    294300
    295301        context.RunOperator(analyzerParameter.Value, context.Scope, cancellationToken);
     302
     303        context.Iterations++;
    296304      }
    297305    }
    … …  
    299307    private bool IsSufficientlyDifferent(IntegerVector vec) {
    300308      return context.Population.All(x =>
    301         HammingSimilarityCalculator.CalculateSimilarity(x.Solution.Assignment, vec) <= 1.0 - MinimumDifference
     309        HammingSimilarityCalculator.CalculateSimilarity(vec, x.Solution.Assignment) <= 1.0 - (MinimumDifference / (double)vec.Length)
    302310      );
    303311    }
    … …  
    329337      var localSearchEvaluations = 0;
    330338      ApproximateLocalSearch.Apply(context.Random, pi_prime, MaximumCandidateListSize,
    331         OneMoveProbability, 1000, Problem.ProblemInstance, out localSearchEvaluations);
     339        OneMoveProbability, MaximumLocalSearchIterations, Problem.ProblemInstance, out localSearchEvaluations);
    332340      context.EvaluatedSolutions += localSearchEvaluations;
    333341    }
    334342
    335343    private bool StoppingCriterion() {
    336       return context.Iterations > MaximumIterationsParameter.Value.Value;
     344      return context.Iterations > MaximumIterations;
    337345    }
    338346  }

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/GRASPContext.cs

    r15553 r15558  
    174174      scope.Variables.Add(new Variable("Evaluation", code.Evaluation));
    175175      return scope;
    176     }
    177 
    178     public double Evaluate(GQAPSolution solution, CancellationToken token) {
    179       var solScope = ToScope(solution);
    180       Evaluate(solScope, token);
    181       return solScope.Fitness;
    182     }
    183 
    184     public void Evaluate(ISingleObjectiveSolutionScope<GQAPSolution> solScope, CancellationToken token) {
    185       var pdef = Problem as ISingleObjectiveProblemDefinition;
    186       if (pdef != null) {
    187         var ind = new SingleEncodingIndividual(pdef.Encoding, solScope);
    188         solScope.Fitness = pdef.Evaluate(ind, Random);
    189       } else {
    190         RunOperator(Problem.Evaluator, solScope, token);
    191       }
    192     }
    193 
    194     public GRASPSolutionContext CreateSingleSolutionContext(ISingleObjectiveSolutionScope<GQAPSolution> solution) {
    195       return new GRASPSolutionContext(this, solution);
    196176    }
    197177
    … …  
    274254    #endregion
    275255  }
    276 
    277   [Item("GRASP+PR (GQAP) SolutionContext", "SolutionContext for GRASP+PR (GQAP).")]
    278   [StorableClass]
    279   public sealed class GRASPSolutionContext : ParameterizedNamedItem, IExecutionContext {
    280 
    281     private GRASPContext parent;
    282     public IExecutionContext Parent {
    283       get { return parent; }
    284       set { throw new InvalidOperationException("Cannot set the parent of a single-solution context."); }
    285     }
    286 
    287     [Storable]
    288     private ISingleObjectiveSolutionScope<GQAPSolution> scope;
    289     public IScope Scope {
    290       get { return scope; }
    291     }
    292 
    293     IKeyedItemCollection<string, IParameter> IExecutionContext.Parameters {
    294       get { return Parameters; }
    295     }
    296 
    297     public GQAP Problem {
    298       get { return parent.Problem; }
    299     }
    300     public bool Maximization {
    301       get { return parent.Maximization; }
    302     }
    303 
    304     public double BestQuality {
    305       get { return parent.BestQuality; }
    306       set { parent.BestQuality = value; }
    307     }
    308 
    309     public GQAPSolution BestSolution {
    310       get { return parent.BestSolution; }
    311       set { parent.BestSolution = value; }
    312     }
    313 
    314     public IRandom Random {
    315       get { return parent.Random; }
    316     }
    317 
    318     [Storable]
    319     private IValueParameter<IntValue> evaluatedSolutions;
    320     public int EvaluatedSolutions {
    321       get { return evaluatedSolutions.Value.Value; }
    322       set { evaluatedSolutions.Value.Value = value; }
    323     }
    324 
    325     [Storable]
    326     private IValueParameter<IntValue> iterations;
    327     public int Iterations {
    328       get { return iterations.Value.Value; }
    329       set { iterations.Value.Value = value; }
    330     }
    331 
    332     [StorableConstructor]
    333     private GRASPSolutionContext(bool deserializing) : base(deserializing) { }
    334     private GRASPSolutionContext(GRASPSolutionContext original, Cloner cloner)
    335       : base(original, cloner) {
    336       scope = cloner.Clone(original.scope);
    337       evaluatedSolutions = cloner.Clone(original.evaluatedSolutions);
    338       iterations = cloner.Clone(original.iterations);
    339     }
    340     public GRASPSolutionContext(GRASPContext baseContext, ISingleObjectiveSolutionScope<GQAPSolution> solution) {
    341       parent = baseContext;
    342       scope = solution;
    343 
    344       Parameters.Add(evaluatedSolutions = new ValueParameter<IntValue>("EvaluatedSolutions", new IntValue(0)));
    345       Parameters.Add(iterations = new ValueParameter<IntValue>("Iterations", new IntValue(0)));
    346     }
    347 
    348     public override IDeepCloneable Clone(Cloner cloner) {
    349       return new GRASPSolutionContext(this, cloner);
    350     }
    351 
    352     public void IncrementEvaluatedSolutions(int byEvaluations) {
    353       if (byEvaluations < 0) throw new ArgumentException("Can only increment and not decrement evaluated solutions.");
    354       EvaluatedSolutions += byEvaluations;
    355     }
    356     public double Evaluate(GQAPSolution solution, CancellationToken token) {
    357       return parent.Evaluate(solution, token);
    358     }
    359 
    360     public void Evaluate(ISingleObjectiveSolutionScope<GQAPSolution> solScope, CancellationToken token) {
    361       parent.Evaluate(solScope, token);
    362     }
    363 
    364     #region IExecutionContext members
    365     public IAtomicOperation CreateOperation(IOperator op) {
    366       return new Core.ExecutionContext(this, op, Scope);
    367     }
    368 
    369     public IAtomicOperation CreateOperation(IOperator op, IScope s) {
    370       return new Core.ExecutionContext(this, op, s);
    371     }
    372 
    373     public IAtomicOperation CreateChildOperation(IOperator op) {
    374       return new Core.ExecutionContext(this, op, Scope);
    375     }
    376 
    377     public IAtomicOperation CreateChildOperation(IOperator op, IScope s) {
    378       return new Core.ExecutionContext(this, op, s);
    379     }
    380     #endregion
    381   }
    382256}

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/Crossovers/GQAPPathRelinking.cs

    r15555 r15558  
    4545      get { return (IScopeTreeLookupParameter<Evaluation>)Parameters["Evaluation"]; }
    4646    }
    47 
    4847    public IValueParameter<PercentValue> CandidateSizeFactorParameter {
    4948      get { return (IValueParameter<PercentValue>)Parameters["CandidateSizeFactor"]; }
     49    }
     50    public IValueLookupParameter<BoolValue> GreedyParameter {
     51      get { return (IValueLookupParameter<BoolValue>)Parameters["Greedy"]; }
    5052    }
    5153
    … …  
    5860      Parameters.Add(new ScopeTreeLookupParameter<Evaluation>("Evaluation", GQAP.EvaluationDescription));
    5961      Parameters.Add(new ValueParameter<PercentValue>("CandidateSizeFactor", "(η) Determines the size of the set of feasible moves in each path-relinking step relative to the maximum size. A value of 50% means that only half of all possible moves are considered each step.", new PercentValue(0.5)));
     62      Parameters.Add(new ValueLookupParameter<BoolValue>("Greedy", "Whether to use a greedy selection strategy or a probabilistic one.", new BoolValue(true)));
    6063    }
    6164
    … …  
    6871      IntegerVector target, Evaluation targetEval,
    6972      GQAPInstance problemInstance, double candidateSizeFactor,
    70       out int evaluatedSolutions) {
     73      out int evaluatedSolutions, bool greedy = true) {
    7174      evaluatedSolutions = 0;
    7275      var demands = problemInstance.Demands;
    7376      var capacities = problemInstance.Capacities;
    7477      var cmp = new IntegerVectorEqualityComparer();
    75 
    76       var greedy = true; // greedy performed better according to the paper
     78     
    7779      var sFit = problemInstance.ToSingleObjective(sourceEval);
    7880      var tFit = problemInstance.ToSingleObjective(targetEval);
    … …  
    8385      //var fix = new bool[demands.Length]; // line 3 of Algorithm 4, note that according to the description it is not necessary to track the fixed equipments
    8486      var nonFix = Enumerable.Range(0, demands.Length).ToList(); // line 3 of Algorithm 4
    85       var phi = new HashSet<int>(IntegerVectorEqualityComparer.GetDifferingIndices(pi_prime, target)); // line 4 of Algorithm 4
    86 
     87      var phi = new List<int>(IntegerVectorEqualityComparer.GetDifferingIndices(pi_prime, target)); // line 4 of Algorithm 4
     88
     89      var B = new List<GQAPSolution>((int)Math.Ceiling(phi.Count * candidateSizeFactor));
     90      var B_fit = new List<double>(B.Capacity);
    8791      while (phi.Count > 0) { // line 5 of Algorithm 4
    88         var B = new List<GQAPSolution>((int)Math.Ceiling(phi.Count * candidateSizeFactor)); // line 6 of Algorithm 4
    89         var B_fit = new List<double>(B.Capacity); // line 6 of Algorithm 4 (B is split into two synchronized lists)
     92        B.Clear(); // line 6 of Algorithm 4
     93        B_fit.Clear(); // line 6 of Algorithm 4 (B is split into two synchronized lists)
    9094        foreach (var v in phi) { // line 7 of Algorithm 4
    9195          int oldLocation = pi_prime[v];
    … …  
    9397          var pi_dash = MakeFeasible(random, pi_prime, v, nonFix, demands, capacities); // line 9 of Algorithm 4
    9498          pi_prime[v] = oldLocation; // not mentioned in Algorithm 4, but seems reasonable
    95           var pi_dash_eval = problemInstance.Evaluate(pi_dash);
    96           evaluatedSolutions++;
    97           var pi_dash_fit = problemInstance.ToSingleObjective(pi_dash_eval);
    9899
    99100          if (problemInstance.IsFeasible(pi_dash)) { // line 10 of Algorithm 4
     101            var pi_dash_eval = problemInstance.Evaluate(pi_dash);
     102            evaluatedSolutions++;
     103            var pi_dash_fit = problemInstance.ToSingleObjective(pi_dash_eval);
     104
    100105            if (B.Any(x => cmp.Equals(x.Assignment, pi_dash))) continue; // cond. 2 of line 12 and cond. 1 of line 16 in Algorithm 4
    101106
    … …  
    103108              var replacement = B_fit.Select((val, idx) => new { Index = idx, Fitness = val })
    104109                                            .Where(x => x.Fitness >= pi_dash_fit) // cond. 1 in line 12 of Algorithm 4
    105                                             .Select(x => new { Index = x.Index, Fitness = x.Fitness, Similarity = HammingSimilarityCalculator.CalculateSimilarity(B[x.Index].Assignment, pi_dash) })
     110                                            .Select(x => new { x.Index, x.Fitness, Similarity = HammingSimilarityCalculator.CalculateSimilarity(B[x.Index].Assignment, pi_dash) })
    106111                                            .ToArray();
    107112              if (replacement.Length > 0) {
    108                 var mostSimilar = replacement.MaxItems(x => x.Similarity).First().Index;
     113                var mostSimilar = replacement.MaxItems(x => x.Similarity).SampleRandom(random).Index;
    109114                B[mostSimilar].Assignment = pi_dash; // line 13 of Algorithm 4
    110115                B[mostSimilar].Evaluation = pi_dash_eval; // line 13 of Algorithm 4
    … …  
    121126          // line 22 of Algorithm 4
    122127          if (greedy) {
    123             pi = B.Select((val, idx) => new { Index = idx, Value = val }).MinItems(x => B_fit[x.Index]).Shuffle(random).First().Value;
     128            pi = B.Select((val, idx) => new { Index = idx, Value = val }).MinItems(x => B_fit[x.Index]).SampleRandom(random).Value;
    124129          } else {
    125130            pi = B.SampleProportional(random, 1, B_fit.Select(x => 1.0 / x), false).First();
    … …  
    137142          }
    138143        } else return pi_star;
    139         phi = new HashSet<int>(IntegerVectorEqualityComparer.GetDifferingIndices(pi_prime, target));
     144        phi = new List<int>(IntegerVectorEqualityComparer.GetDifferingIndices(pi_prime, target));
    140145      }
    141146
    … …  
    156161      return Apply(random, source, evaluations[betterParent],
    157162        target, evaluations[worseParent], problemInstance,
    158         CandidateSizeFactorParameter.Value.Value, out evaluatedSolution).Assignment;
    159     }
    160 
     163        CandidateSizeFactorParameter.Value.Value, out evaluatedSolution,
     164        GreedyParameter.ActualValue.Value).Assignment;
     165    }
     166
     167    /// <summary>
     168    /// Relocates equipments in the same location as <paramref name="equipment"/> to other locations in case the location
     169    /// is overutilized.
     170    /// </summary>
     171    /// <remarks>
     172    /// This method is performance critical, called very often and should run as fast as possible.
     173    /// </remarks>
     174    /// <param name="random">The random number generator.</param>
     175    /// <param name="pi">The current solution.</param>
     176    /// <param name="equipment">The equipment that was just assigned to a new location.</param>
     177    /// <param name="nonFix">The equipments that have not yet been fixed.</param>
     178    /// <param name="demands">The demands for all equipments.</param>
     179    /// <param name="capacities">The capacities of all locations.</param>
     180    /// <param name="maximumTries">The number of tries that should be done in relocating the equipments.</param>
     181    /// <returns>A feasible or infeasible solution</returns>
    161182    private static IntegerVector MakeFeasible(IRandom random, IntegerVector pi, int equipment, List<int> nonFix, DoubleArray demands, DoubleArray capacities, int maximumTries = 1000) {
    162183      int l = pi[equipment];
    163184      var slack = ComputeSlack(pi, demands, capacities);
    164185      if (slack[l] >= 0) // line 1 of Algorithm 5
    165         return new IntegerVector(pi); // line 2 of Algorithm 5
     186        return (IntegerVector)pi.Clone(); // line 2 of Algorithm 5
    166187
    167188      IntegerVector pi_prime = null;
    168189      int k = 0; // line 4 of Algorithm 5
    169       while (k < maximumTries && slack[l] < 0) {  // line 5 of Algorithm 5
    170         pi_prime = new IntegerVector(pi); // line 6 of Algorithm 5
     190      var maxSlack = slack.Max(); // line 8-9 of Algorithm 5
     191      var slack_prime = (double[])slack.Clone();
     192      var maxSlack_prime = maxSlack;
     193      // note that FTL can be computed only once for all tries as all tries restart with the same solution
     194      var FTL = nonFix.Where(x => x != equipment && pi[x] == l && demands[x] <= maxSlack).ToList(); // line 8-9 of Algorithm 5
     195      var FTLweight = FTL.Select(x => demands[x]).ToList();
     196      while (k < maximumTries && slack_prime[l] < 0) {  // line 5 of Algorithm 5
     197        pi_prime = (IntegerVector)pi.Clone(); // line 6 of Algorithm 5
     198        // set T can only shrink and not grow, thus it is created outside the loop and only updated inside
     199        var T = new List<int>(FTL); // line 8-9 of Algorithm 5
     200        var weightT = new List<double>(FTLweight);
    171201        do {  // line 7 of Algorithm 5
    172           var maxSlack = slack.Max(); // line 8-9 of Algorithm 5
    173           var T = nonFix.Where(x => pi[x] == l && demands[x] <= maxSlack).ToList(); // line 8-9 of Algorithm 5
    174202          if (T.Count > 0) { // line 10 of Algorithm 5
    175             int i = T.SampleProportional(random, 1, T.Select(x => demands[x]), false).First(); // line 11 of Algorithm 5
     203            var idx = Enumerable.Range(0, T.Count).SampleProportional(random, 1, weightT, false, false).First(); // line 11 of Algorithm 5
     204            int i = T[idx]; // line 11 of Algorithm 5
    176205            var j = Enumerable.Range(0, capacities.Length)
    177               .Where(x => slack[x] >= demands[i]) // line 12 of Algorithm 5
     206              .Where(x => slack_prime[x] >= demands[i]) // line 12 of Algorithm 5
    178207              .SampleRandom(random);  // line 13 of Algorithm 5
    179208            pi_prime[i] = j; // line 14 of Algorithm 5
    180             slack[j] -= demands[i]; // line 14 of Algorithm 5
    181             slack[l] += demands[i]; // line 14 of Algorithm 5
     209            T.RemoveAt(idx);
     210            weightT.RemoveAt(idx);
     211            var recomputeMaxSlack = slack_prime[j] == maxSlack_prime; // efficiency improvement: recompute max slack only if we assign to a location whose slack equals maxSlack
     212            slack_prime[j] -= demands[i]; // line 14 of Algorithm 5
     213            slack_prime[l] += demands[i]; // line 14 of Algorithm 5
     214            if (recomputeMaxSlack) {
     215              maxSlack_prime = slack_prime.Max();
     216              // T needs to be removed of equipments whose demand is higher than maxSlack only if maxSlack changes
     217              for (var h = 0; h < T.Count; h++) {
     218                var f = T[h];
     219                if (demands[f] > maxSlack_prime) {
     220                  T.RemoveAt(h);
     221                  weightT.RemoveAt(h);
     222                  h--;
     223                }
     224              }
     225            }
    182226          } else break; // cond. 1 in line 16 of Algorithm 5
    183         } while (slack[l] < 0); // cond. 2 in line 16 of Algorithm 5
     227        } while (slack_prime[l] < 0); // cond. 2 in line 16 of Algorithm 5
    184228        k++; // line 17 of Algorithm 5
     229        if (slack_prime[l] < 0) {
     230          // reset
     231          Array.Copy(slack, slack_prime, slack.Length);
     232          maxSlack_prime = maxSlack;
     233        }
    185234      }
    186235      return pi_prime; // line 19-23 of Algorithm 5
    … …  
    188237
    189238    private static double[] ComputeSlack(IntegerVector assignment, DoubleArray demands, DoubleArray capacities) {
    190       var slack = new double[capacities.Length];
     239      var slack = capacities.ToArray();
    191240      for (int i = 0; i < assignment.Length; i++) {
    192241        slack[assignment[i]] -= demands[i];

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

    r15555 r15558  
    7676      get { return (ILookupParameter<ResultCollection>)Parameters["Results"]; }
    7777    }
     78    public IValueLookupParameter<BoolValue> GreedyParameter {
     79      get { return (IValueLookupParameter<BoolValue>)Parameters["Greedy"]; }
     80    }
    7881
    7982    [StorableConstructor]
    … …  
    9295      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)));
    9396      Parameters.Add(new LookupParameter<ResultCollection>("Results", "The result collection that stores the results."));
     97      Parameters.Add(new ValueLookupParameter<BoolValue>("Greedy", "Whether to use a greedy selection strategy or a probabilistic one.", new BoolValue(true)));
    9498    }
    9599
    … …  
    100104    public static void Apply(IRandom random, GQAPSolution sol, int maxCLS,
    101105      double oneMoveProbability, int maximumIterations,
    102       GQAPInstance problemInstance, out int evaluatedSolutions) {
     106      GQAPInstance problemInstance, out int evaluatedSolutions, bool greedy = true) {
    103107      var fit = problemInstance.ToSingleObjective(sol.Evaluation);
    104108      var eval = sol.Evaluation;
    105109      Apply(random, sol.Assignment, ref fit, ref eval, maxCLS, oneMoveProbability, maximumIterations, problemInstance,
    106         out evaluatedSolutions);
     110        out evaluatedSolutions, greedy);
    107111      sol.Evaluation = eval;
    108112    }
    109113
    110       /// <summary>
    111       /// </summary>
    112       /// <param name="random">The random number generator to use.</param>
    113       /// <param name="assignment">The equipment-location assignment vector.</param>
    114       /// <param name="quality">The solution quality.</param>
    115       /// <param name="evaluation">The evaluation result of the solution.</param>
    116       /// <param name="maxCLS">The maximum number of candidates that should be found in each step.</param>
    117       /// <param name="oneMoveProbability">The probability for performing a 1-move, which is the opposite of performing a 2-move.</param>
    118       /// <param name="maximumIterations">The maximum number of iterations that should be performed each time the candidate list is generated.</param>
    119       /// <param name="problemInstance">The problem instance that contains the data.</param>
    120       /// <param name="evaluatedSolutions">The number of evaluated solutions.</param>
    121       public static void Apply(IRandom random, IntegerVector assignment,
     114    /// <summary>
     115    /// </summary>
     116    /// <param name="random">The random number generator to use.</param>
     117    /// <param name="assignment">The equipment-location assignment vector.</param>
     118    /// <param name="quality">The solution quality.</param>
     119    /// <param name="evaluation">The evaluation result of the solution.</param>
     120    /// <param name="maxCLS">The maximum number of candidates that should be found in each step.</param>
     121    /// <param name="oneMoveProbability">The probability for performing a 1-move, which is the opposite of performing a 2-move.</param>
     122    /// <param name="maximumIterations">The maximum number of iterations that should be performed each time the candidate list is generated.</param>
     123    /// <param name="problemInstance">The problem instance that contains the data.</param>
     124    /// <param name="evaluatedSolutions">The number of evaluated solutions.</param>
     125    /// <param name="greedy">Greedy selection performed better in 5 of 8 instances according to the paper</param>
     126    public static void Apply(IRandom random, IntegerVector assignment,
    122127      ref double quality, ref Evaluation evaluation, int maxCLS,
    123128      double oneMoveProbability, int maximumIterations,
    124       GQAPInstance problemInstance, out int evaluatedSolutions) {
     129      GQAPInstance problemInstance, out int evaluatedSolutions, bool greedy = true) {
    125130      evaluatedSolutions = 0;
    126131      var capacities = problemInstance.Capacities;
    … …  
    128133      var evaluations = 0.0;
    129134      var deltaEvaluationFactor = 1.0 / assignment.Length;
    130       var greedy = true; // greedy selection performed better in 5 of 8 instances according to the paper
    131135      while (true) { // line 1 of Algorithm 3
    132136        var count = 0; // line 2 of Algorithm 3
    … …  
    183187        MaximumIterationsParameter.ActualValue.Value,
    184188        ProblemInstanceParameter.ActualValue,
    185         out evaluatedSolutions);
     189        out evaluatedSolutions,
     190        GreedyParameter.ActualValue.Value);
    186191
    187192      EvaluationParameter.ActualValue = evaluation;

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/SolutionCreators/GreedyRandomizedSolutionCreator.cs

    r15555 r15558  
    6565      var weights = problemInstance.Weights;
    6666      var distances = problemInstance.Distances;
     67      var installCosts = problemInstance.InstallationCosts;
    6768      var demands = problemInstance.Demands;
    6869      var capacities = problemInstance.Capacities.ToArray();
    … …  
    7172      var locations = capacities.Length;
    7273      int tries = 0;
    73       var assignment = new int[equipments];
    7474      var slack = new double[locations];
    7575      double minViolation = double.MaxValue;
     76      int[] assignment = null;
    7677      int[] bestAssignment = null;
    7778      var F = new List<int>(equipments); // set of (initially) all facilities / equipments
    … …  
    8485      var W = new double[equipments]; // proportions for choosing facilities in stage 2
    8586      var Z = new double[locations]; // proportions for choosing locations in stage 2
     87     
     88      for (var k = 0; k < equipments; k++) {
     89        for (var h = 0; h < equipments; h++) {
     90          if (k == h) continue;
     91          W[k] += weights[k, h];
     92        }
     93        W[k] *= demands[k];
     94      }
    8695
    8796      while (maximumTries <= 0 || tries < maximumTries) {
    8897        cancelToken.ThrowIfCancellationRequested();
     98
     99        assignment = new int[equipments];
    89100
    90101        Array.Copy(capacities, slack, locations); // line 2 of Algorihm 2
    … …  
    96107        F.Clear(); F.AddRange(Enumerable.Range(0, equipments)); // line 2 of Algorihm 2
    97108        L.Clear(); L.AddRange(Enumerable.Range(0, locations)); // line 2 of Algorihm 2
     109
     110        Array.Clear(H, 0, H.Length);
    98111
    99112        double threshold = 1.0; // line 3 of Algorithm 2
    … …  
    104117            // does not contain an element in which case according to the formula
    105118            // all H_k elements would be 0 which would be equal to random selection
    106             var HH = H.Select((v, i) => new { Index = i, Value = v })
    107               .Where(x => !CL_selected[x.Index])
    108               .Select(x => x.Value);
     119            var HH = L.Select(x => H[x]);
    109120            int l = L.SampleProportional(random, 1, HH, false, false).Single(); // line 6 of Algorithm 2
    110121            L.Remove(l); // line 7 of Algorithm 2
    111122            CL_list.Add(l); // line 7 of Algorithm 2
    112123            CL_selected[l] = true; // line 7 of Algorithm 2
    113             for (var k = 0; k < locations; k++)
    114               if (!CL_selected[k])
    115                 H[k] += capacities[k] * capacities[l] / distances[k, l];
     124            // incrementally updating location weights
     125            foreach (var k in L)
     126              H[k] += capacities[k] * capacities[l] / distances[k, l];
     127
    116128            T = new List<int>(WhereDemandEqualOrLess(F, GetMaximumSlack(slack, CL_selected), demands)); // line 8 of Algorithm 2
    117129          }
    118130          if (T.Count > 0) { // line 10 of Algorithm 2
    119131            // W is the proportion that an equipment is chosen
    120             Array.Clear(W, 0, W.Length);
    121             var wk = 0;
    122             foreach (var k in T) {
    123               for (var h = 0; h < equipments; h++) {
    124                 if (k == h) continue;
    125                 W[wk] += weights[k, h];
    126               }
    127               W[wk] *= demands[k];
    128               wk++;
    129             }
    130             var f = T.SampleProportional(random, 1, W.Take(T.Count), false, false) // line 11 of Algorithm 2
     132            var WW = T.Select(x => W[x]);
     133            var f = T.SampleProportional(random, 1, WW, false, false) // line 11 of Algorithm 2
    131134              .Single();
    132135            T.Remove(f); // line 12 of Algorithm 2
    … …  
    135138            var R = WhereSlackGreaterOrEqual(CL_list, demands[f], slack).ToList(); // line 13 of Algorithm 2
    136139            // Z is the proportion that a location is chosen in stage 2
    137             Array.Clear(Z, 0, Z.Length);
    138             var zk = 0;
    139             foreach (var k in R) {
    140               // d is an increase in fitness if f would be assigned to location k
    141               var d = problemInstance.InstallationCosts[f, k];
    142               foreach (var i in CF) {
    143                 if (assignment[i] == 0) continue; // i is unassigned
    144                 var j = assignment[i] - 1;
    145                 d += transportCosts * weights[f, i] * distances[k, j];
     140            var l = R[0];
     141            if (R.Count > 1) { // optimization, calculate probabilistic weights only in case |R| > 1
     142              Array.Clear(Z, 0, R.Count);
     143              var zk = 0;
     144              foreach (var k in R) {
     145                // d is an increase in fitness if f would be assigned to location k
     146                var d = installCosts[f, k];
     147                foreach (var i in CF) {
     148                  if (assignment[i] == 0) continue; // i is unassigned
     149                  var j = assignment[i] - 1;
     150                  d += transportCosts * weights[f, i] * distances[k, j];
     151                }
     152                foreach (var h in CL_list) {
     153                  if (k == h) continue;
     154                  Z[zk] += slack[k] * capacities[h] / (d * distances[k, h]);
     155                }
     156                zk++;
    146157              }
    147               foreach (var h in CL_list) {
    148                 if (k == h) continue;
    149                 Z[zk] += slack[k] * capacities[h] / (d * distances[k, h]);
    150               }
    151               zk++;
     158              l = R.SampleProportional(random, 1, Z.Take(R.Count), false, false).Single(); // line 14 of Algorithm 2
    152159            }
    153             int l = R.SampleProportional(random, 1, Z.Take(R.Count), false, false).Single(); // line 14 of Algorithm 2
    154160            assignment[f] = l + 1; // line 15 of Algorithm 2
    155161            slack[l] -= demands[f];
    … …  
    183189            minViolation = violation;
    184190          }
    185           assignment = new int[equipments];
    186191        }
    187192      }

  • branches/GeneralizedQAP/UnitTests/ApproximateLocalSearchTest.cs

    r15553 r15558  
    1313    [TestMethod]
    1414    public void ApproximateLocalSearchApplyTest() {
    15       CollectionAssert.AreEqual(new [] { 3, 2, 2, 0, 0, 0, 2, 3, 0, 2 }, assignment.ToArray());
     15      CollectionAssert.AreEqual(new [] { 3, 2, 1, 1, 3, 0, 1, 0, 3, 0 }, assignment.ToArray());
    1616
    1717      var evaluation = instance.Evaluate(assignment);
    18       Assert.AreEqual(3764492, evaluation.FlowCosts);
    19       Assert.AreEqual(46, evaluation.InstallationCosts);
     18      Assert.AreEqual(4091776, evaluation.FlowCosts);
     19      Assert.AreEqual(42, evaluation.InstallationCosts);
    2020      Assert.AreEqual(0, evaluation.ExcessDemand);
    2121
    2222      var quality = instance.ToSingleObjective(evaluation);
    23       Assert.AreEqual(14631771.476177376, quality, 1e-9);
     23      Assert.AreEqual(15903846.056964701, quality, 1e-9);
    2424
    2525      var evaluatedSolutions = 0;
    … …  
    2727        ref evaluation, 10, 0.5, 1000, instance,
    2828        out evaluatedSolutions);
    29       Assert.AreEqual(300, evaluatedSolutions);
    30       CollectionAssert.AreEqual(new[] { 3, 2, 2, 0, 0, 2, 2, 3, 0, 0 }, assignment.ToArray());
    31       Assert.AreEqual(14271146.913257681, quality, 1e-9);
     29      Assert.AreEqual(680, evaluatedSolutions);
     30      CollectionAssert.AreEqual(new[] { 3, 1, 0, 3, 0, 0, 1, 2, 3, 0 }, assignment.ToArray());
     31      Assert.AreEqual(12440163.936988469, quality, 1e-9);
    3232    }
    3333
Note: See TracChangeset for help on using the changeset viewer.