Ignore:
Timestamp:
12/20/17 23:35:23 (4 years ago)
Author:
abeham
Message:

#1614: finished checking the implementation against the paper

File:
1 edited

Legend:

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

    r15553 r15555  
    3232
    3333namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment {
     34  /// <summary>
     35  /// 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
     36  /// </summary>
    3437  [Item("GQAPPathRelinking", "Operator that performs path relinking between two solutions. It 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.")]
    3538  [StorableClass]
     
    7174      var cmp = new IntegerVectorEqualityComparer();
    7275
     76      var greedy = true; // greedy performed better according to the paper
    7377      var sFit = problemInstance.ToSingleObjective(sourceEval);
    7478      var tFit = problemInstance.ToSingleObjective(targetEval);
     
    114118        }
    115119        if (B.Count > 0) { // line 21 of Algorithm 4
    116           var pi = B.SampleProportional(random, 1, B_fit.Select(x => 1.0 / x), false).First(); // line 22 of Algorithm 4
     120          GQAPSolution pi;
     121          // line 22 of Algorithm 4
     122          if (greedy) {
     123            pi = B.Select((val, idx) => new { Index = idx, Value = val }).MinItems(x => B_fit[x.Index]).Shuffle(random).First().Value;
     124          } else {
     125            pi = B.SampleProportional(random, 1, B_fit.Select(x => 1.0 / x), false).First();
     126          }
    117127          var diff = IntegerVectorEqualityComparer.GetDifferingIndices(pi.Assignment, target); // line 23 of Algorithm 4
    118128          var I = phi.Except(diff); // line 24 of Algorithm 4
     
    126136            pi_star = pi; // line 30 of Algorithm 4
    127137          }
    128         } else return pi_star ?? new GQAPSolution((IntegerVector)source.Clone(), (Evaluation)sourceEval.Clone());
     138        } else return pi_star;
    129139        phi = new HashSet<int>(IntegerVectorEqualityComparer.GetDifferingIndices(pi_prime, target));
    130140      }
    131141
    132       return pi_star ?? new GQAPSolution((IntegerVector)source.Clone(), (Evaluation)sourceEval.Clone());
     142      return pi_star;
    133143    }
    134144
Note: See TracChangeset for help on using the changeset viewer.