Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
02/02/18 16:31:42 (6 years ago)
Author:
abeham
Message:

#1614:

  • added additional constraint to benchmark data generator and updated one instance that was affected by this
  • added fitness landscape characteristics for the GQAP
  • fixed RLD analysis view to compensate for empty convergence graphs
  • fixed CPLEX solvers not using the obj value when the solver terminates (callback is not called if proven optimal solution is found)
  • added code for local solver to also check on final quality
Location:
branches/1614_GeneralizedQAP/HeuristicLab.Analysis.FitnessLandscape/3.3/ProblemCharacteristicAnalysis/GQAP
Files:
1 added
2 copied

Legend:

Unmodified
Added
Removed
  • branches/1614_GeneralizedQAP/HeuristicLab.Analysis.FitnessLandscape/3.3/ProblemCharacteristicAnalysis/GQAP/GQAPCharacteristicCalculator.cs

    r15702 r15713  
    2020#endregion
    2121
     22using System;
     23using System.Collections.Generic;
     24using System.Linq;
    2225using HeuristicLab.Common;
    2326using HeuristicLab.Core;
     
    2528using HeuristicLab.Optimization;
    2629using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    27 using HeuristicLab.Problems.QuadraticAssignment;
    28 using System;
    29 using System.Collections.Generic;
    30 using System.Linq;
     30using HeuristicLab.Problems.GeneralizedQuadraticAssignment;
    3131
    3232namespace HeuristicLab.Analysis.FitnessLandscape {
    33   [Item("QAP Characteristic Calculator", "")]
     33  [Item("GQAP Characteristic Calculator", "")]
    3434  [StorableClass]
    35   public sealed class QAPCharacteristicCalculator : CharacteristicCalculator {
     35  public sealed class GQAPCharacteristicCalculator : CharacteristicCalculator {
    3636
    3737    [StorableConstructor]
    38     private QAPCharacteristicCalculator(bool deserializing) : base(deserializing) { }
    39     private QAPCharacteristicCalculator(QAPCharacteristicCalculator original, Cloner cloner) : base(original, cloner) { }
    40     public QAPCharacteristicCalculator() {
    41       characteristics.AddRange(new[] { "Dimension",
     38    private GQAPCharacteristicCalculator(bool deserializing) : base(deserializing) { }
     39    private GQAPCharacteristicCalculator(GQAPCharacteristicCalculator original, Cloner cloner) : base(original, cloner) { }
     40    public GQAPCharacteristicCalculator() {
     41      characteristics.AddRange(new[] {
     42        "Dimension", "MNRatio",
    4243        "FlowDominance", "DistanceDominance",
    43         "FlowAsymmetry", "DistanceAsymmetry",
    4444        "FlowSparsity", "DistanceSparsity",
    45         "FlowSkewness", "DistanceSkewness",
    46         "FlowDisparity", "DistanceDisparity" }.Select(x => new StringValue(x)).ToList());
     45        "DemandDominance", "CapacityDominance",
     46        "Utilization", "BasicFeasibility",
     47      }.Select(x => new StringValue(x)).ToList());
    4748    }
    4849
    4950    public override IDeepCloneable Clone(Cloner cloner) {
    50       return new QAPCharacteristicCalculator(this, cloner);
     51      return new GQAPCharacteristicCalculator(this, cloner);
    5152    }
    5253
    5354    public override bool CanCalculate() {
    54       return Problem is QuadraticAssignmentProblem;
     55      return Problem is GQAP;
    5556    }
    5657
    5758    public override IEnumerable<IResult> Calculate() {
    58       var qap = Problem as QuadraticAssignmentProblem;
    59       if (qap == null) throw new ArgumentException("Instance is not of type QuadraticAssignmentProblem");
     59      var gqap = Problem as GQAP;
     60      if (gqap == null) throw new ArgumentException("Instance is not of type GQAP");
     61      var inst = gqap.ProblemInstance;
    6062      foreach (var chara in characteristics.CheckedItems.Select(x => x.Value.Value)) {
    6163        if (chara == "Dimension")
    62           yield return new Result(chara, new IntValue(qap.Weights.Rows));
     64          yield return new Result(chara, new IntValue(inst.Demands.Length));
     65        if (chara == "MNRatio")
     66          yield return new Result(chara, new DoubleValue(inst.Capacities.Length / (double)inst.Demands.Length));
    6367        if (chara == "FlowDominance")
    64           yield return new Result(chara, new DoubleValue(DoubleMatrixCharacteristicCalculator.CoeffVariation(qap.Weights)));
     68          yield return new Result(chara, new DoubleValue(DoubleMatrixCharacteristicCalculator.CoeffVariation(inst.Weights)));
    6569        if (chara == "DistanceDominance")
    66           yield return new Result(chara, new DoubleValue(DoubleMatrixCharacteristicCalculator.CoeffVariation(qap.Distances)));
    67         if (chara == "FlowAsymmetry")
    68           yield return new Result(chara, new DoubleValue(DoubleMatrixCharacteristicCalculator.Asymmetry(qap.Weights)));
    69         if (chara == "DistanceAsymmetry")
    70           yield return new Result(chara, new DoubleValue(DoubleMatrixCharacteristicCalculator.Asymmetry(qap.Distances)));
     70          yield return new Result(chara, new DoubleValue(DoubleMatrixCharacteristicCalculator.CoeffVariation(inst.Distances)));
    7171        if (chara == "FlowSparsity")
    72           yield return new Result(chara, new DoubleValue(DoubleMatrixCharacteristicCalculator.Sparsity(qap.Weights)));
     72          yield return new Result(chara, new DoubleValue(DoubleMatrixCharacteristicCalculator.Sparsity(inst.Weights)));
    7373        if (chara == "DistanceSparsity")
    74           yield return new Result(chara, new DoubleValue(DoubleMatrixCharacteristicCalculator.Sparsity(qap.Distances)));
    75         if (chara == "FlowSkewness")
    76           yield return new Result(chara, new DoubleValue(DoubleMatrixCharacteristicCalculator.Skewness(qap.Weights)));
    77         if (chara == "DistanceSkewness")
    78           yield return new Result(chara, new DoubleValue(DoubleMatrixCharacteristicCalculator.Skewness(qap.Distances)));
    79         if (chara == "FlowDisparity")
    80           yield return new Result(chara, new DoubleValue(DoubleMatrixCharacteristicCalculator.Disparity(qap.Weights)));
    81         if (chara == "DistanceDisparity")
    82           yield return new Result(chara, new DoubleValue(DoubleMatrixCharacteristicCalculator.Disparity(qap.Distances)));
     74          yield return new Result(chara, new DoubleValue(DoubleMatrixCharacteristicCalculator.Sparsity(inst.Distances)));
     75        if (chara == "DemandDominance")
     76          yield return new Result(chara, new DoubleValue(inst.Demands.StandardDeviation() / inst.Demands.Average()));
     77        if (chara == "CapacityDominance")
     78          yield return new Result(chara, new DoubleValue(inst.Capacities.StandardDeviation() / inst.Capacities.Average()));
     79        if (chara == "Utilization")
     80          yield return new Result(chara, new DoubleValue(inst.Demands.Sum() / inst.Capacities.Sum()));
     81        if (chara == "BasicFeasibility")
     82          yield return new Result(chara, new DoubleValue(inst.Demands.Select(d => inst.Capacities.Count(c => d <= c)).Average() / inst.Capacities.Length));
    8383      }
    8484    }
  • branches/1614_GeneralizedQAP/HeuristicLab.Analysis.FitnessLandscape/3.3/ProblemCharacteristicAnalysis/GQAP/GQAPDirectedWalk.cs

    r15702 r15713  
    2020#endregion
    2121
     22using System;
     23using System.Collections.Generic;
     24using System.Linq;
    2225using HeuristicLab.Common;
    2326using HeuristicLab.Core;
    2427using HeuristicLab.Data;
    25 using HeuristicLab.Encodings.PermutationEncoding;
     28using HeuristicLab.Encodings.IntegerVectorEncoding;
    2629using HeuristicLab.Optimization;
    2730using HeuristicLab.Parameters;
    2831using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    29 using HeuristicLab.Problems.QuadraticAssignment;
     32using HeuristicLab.Problems.GeneralizedQuadraticAssignment;
    3033using HeuristicLab.Random;
    31 using System;
    32 using System.Collections.Generic;
    33 using System.Linq;
    34 using System.Threading;
    3534
    3635namespace HeuristicLab.Analysis.FitnessLandscape {
    37   [Item("Directed Walk (QAP-specific)", "")]
     36  [Item("Directed Walk (GQAP-specific)", "")]
    3837  [StorableClass]
    39   public class QAPDirectedWalk : CharacteristicCalculator {
     38  public class GQAPDirectedWalk : CharacteristicCalculator {
    4039   
    4140    public IFixedValueParameter<IntValue> PathsParameter {
     
    7675
    7776    [StorableConstructor]
    78     private QAPDirectedWalk(bool deserializing) : base(deserializing) { }
    79     private QAPDirectedWalk(QAPDirectedWalk original, Cloner cloner) : base(original, cloner) { }
    80     public QAPDirectedWalk() {
    81       characteristics.AddRange(new[] { "Swap2.Sharpness", "Swap2.Bumpiness", "Swap2.Flatness" }
     77    private GQAPDirectedWalk(bool deserializing) : base(deserializing) { }
     78    private GQAPDirectedWalk(GQAPDirectedWalk original, Cloner cloner) : base(original, cloner) { }
     79    public GQAPDirectedWalk() {
     80      characteristics.AddRange(new[] { "1Shift.Sharpness", "1Shift.Bumpiness", "1Shift.Flatness" }
    8281        .Select(x => new StringValue(x)).ToList());
    8382      Parameters.Add(new FixedValueParameter<IntValue>("Paths", "The number of paths to explore (a path is a set of solutions that connect two randomly chosen solutions).", new IntValue(50)));
     
    8887
    8988    public override IDeepCloneable Clone(Cloner cloner) {
    90       return new QAPDirectedWalk(this, cloner);
     89      return new GQAPDirectedWalk(this, cloner);
    9190    }
    9291
    9392    public override bool CanCalculate() {
    94       return Problem is QuadraticAssignmentProblem;
     93      return Problem is GQAP;
    9594    }
    9695
    9796    public override IEnumerable<IResult> Calculate() {
    9897      IRandom random = Seed.HasValue ? new MersenneTwister((uint)Seed.Value) : new MersenneTwister();
    99       var qap = (QuadraticAssignmentProblem)Problem;
    100       List<Permutation> permutations = CalculateRelinkingPoints(random, qap, Paths, LocalOptima);
    101 
    102       var trajectories = Run(random, (QuadraticAssignmentProblem)Problem, permutations, BestImprovement).ToList();
    103       var result = PermutationPathAnalysis.GetCharacteristics(trajectories);
     98      var gqap = (GQAP)Problem;
     99      List<IntegerVector> assignments = CalculateRelinkingPoints(random, gqap, Paths, LocalOptima);
     100
     101      var trajectories = Run(random, (GQAP)Problem, assignments, BestImprovement).ToList();
     102      var result = IntegerVectorPathAnalysis.GetCharacteristics(trajectories);
    104103
    105104      foreach (var chara in characteristics.CheckedItems.Select(x => x.Value.Value)) {
    106         if (chara == "Swap2.Sharpness") yield return new Result("Swap2.Sharpness", new DoubleValue(result.Sharpness));
    107         if (chara == "Swap2.Bumpiness") yield return new Result("Swap2.Bumpiness", new DoubleValue(result.Bumpiness));
    108         if (chara == "Swap2.Flatness") yield return new Result("Swap2.Flatness", new DoubleValue(result.Flatness));
    109       }
    110     }
    111 
    112     public static List<Permutation> CalculateRelinkingPoints(IRandom random, QuadraticAssignmentProblem qap, int pathCount, bool localOptima) {
    113       var perm = new Permutation(PermutationTypes.Absolute, qap.Weights.Rows, random);
     105        if (chara == "1Shift.Sharpness") yield return new Result("1Shift.Sharpness", new DoubleValue(result.Sharpness));
     106        if (chara == "1Shift.Bumpiness") yield return new Result("1Shift.Bumpiness", new DoubleValue(result.Bumpiness));
     107        if (chara == "1Shift.Flatness") yield return new Result("1Shift.Flatness", new DoubleValue(result.Flatness));
     108      }
     109    }
     110
     111    public static List<IntegerVector> CalculateRelinkingPoints(IRandom random, GQAP gqap, int pathCount, bool localOptima) {
     112      var assign = new IntegerVector(gqap.ProblemInstance.Demands.Length, random, 0, gqap.ProblemInstance.Capacities.Length);
    114113      if (localOptima) {
    115         var fit = new DoubleValue(QAPEvaluator.Apply(perm, qap.Weights, qap.Distances));
    116         QAPExhaustiveSwap2LocalImprovement.ImproveFast(perm, qap.Weights, qap.Distances, fit, new IntValue(0), new IntValue(0), qap.Maximization.Value, int.MaxValue, CancellationToken.None);
    117       }
    118       var permutations = new List<Permutation> { perm };
    119       while (permutations.Count < pathCount + 1) {
    120         perm = (Permutation)permutations.Last().Clone();
    121         BiasedShuffle(perm, random);
     114        var eval = gqap.ProblemInstance.Evaluate(assign);
     115        var fit = gqap.ProblemInstance.ToSingleObjective(eval);
     116        OneOptLocalSearch.Apply(random, assign, ref fit, ref eval, gqap.ProblemInstance, out var evals);
     117      }
     118      var points = new List<IntegerVector> { assign };
     119      while (points.Count < pathCount + 1) {
     120        assign = (IntegerVector)points.Last().Clone();
     121        RelocateEquipmentManipluator.Apply(random, assign, gqap.ProblemInstance.Capacities.Length, 0);
    122122        if (localOptima) {
    123           var fit = new DoubleValue(QAPEvaluator.Apply(perm, qap.Weights, qap.Distances));
    124           QAPExhaustiveSwap2LocalImprovement.ImproveFast(perm, qap.Weights, qap.Distances, fit, new IntValue(0), new IntValue(0), qap.Maximization.Value, int.MaxValue, CancellationToken.None);
     123          var eval = gqap.ProblemInstance.Evaluate(assign);
     124          var fit = gqap.ProblemInstance.ToSingleObjective(eval);
     125          OneOptLocalSearch.Apply(random, assign, ref fit, ref eval, gqap.ProblemInstance, out var evals);
    125126        }
    126         if (HammingSimilarityCalculator.CalculateSimilarity(permutations.Last(), perm) < 0.75)
    127           permutations.Add(perm);
    128       }
    129 
    130       return permutations;
    131     }
    132 
    133     public static IEnumerable<List<Tuple<Permutation, double>>> Run(IRandom random, QuadraticAssignmentProblem qap, IEnumerable<Permutation> permutations, bool bestImprovement = true) {
    134       var iter = permutations.GetEnumerator();
     127        if (HammingSimilarityCalculator.CalculateSimilarity(points.Last(), assign) < 0.75)
     128          points.Add(assign);
     129      }
     130
     131      return points;
     132    }
     133
     134    public static IEnumerable<List<Tuple<IntegerVector, double>>> Run(IRandom random, GQAP gqap, IEnumerable<IntegerVector> points, bool bestImprovement = true) {
     135      var iter = points.GetEnumerator();
    135136      if (!iter.MoveNext()) yield break;
    136 
    137       var min = qap.LowerBound.Value;
    138       var max = qap.AverageQuality.Value;
    139137
    140138      var start = iter.Current;
     
    142140        var end = iter.Current;
    143141
    144         var walk = (bestImprovement ? BestDirectedWalk(qap, start, end) : FirstDirectedWalk(random, qap, start, end)).ToList();
    145         yield return walk.Select(x => Tuple.Create(x.Item1, (x.Item2 - min) / (max - min))).ToList();
     142        var walk = (bestImprovement ? BestDirectedWalk(gqap, start, end) : FirstDirectedWalk(random, gqap, start, end)).ToList();
     143        yield return walk.ToList();
    146144        start = end;
    147145      } // end paths
    148146    }
    149147
    150     private static IEnumerable<Tuple<Permutation, double>> BestDirectedWalk(QuadraticAssignmentProblem qap, Permutation start, Permutation end) {
    151       var N = qap.Weights.Rows;
     148    private static IEnumerable<Tuple<IntegerVector, double>> BestDirectedWalk(GQAP gqap, IntegerVector start, IntegerVector end) {
     149      var N = gqap.ProblemInstance.Demands.Length;
    152150      var sol = start;
    153       var fitness = QAPEvaluator.Apply(sol, qap.Weights, qap.Distances);
     151      var evaluation = gqap.ProblemInstance.Evaluate(start);
     152      var fitness = gqap.ProblemInstance.ToSingleObjective(evaluation);
    154153      yield return Tuple.Create(sol, fitness);
    155 
    156       var invSol = GetInverse(sol);
    157       // we require at most N-1 steps to move from one permutation to another
    158       for (var step = 0; step < N - 1; step++) {
     154     
     155      var reassignments = Enumerable.Range(0, N).Select(x => {
     156        if (start[x] == end[x]) return null;
     157        var r = new int[N];
     158        r[x] = end[x] + 1;
     159        return r;
     160      }).ToArray();
     161      var indices = Enumerable.Range(0, N).Select(x => start[x] == end[x] ? null : new List<int>(1) { x }).ToArray();
     162
     163      for (var step = 0; step < N; step++) {
    159164        var bestFitness = double.MaxValue;
     165        Evaluation bestEvaluation = null;
    160166        var bestIndex = -1;
    161         sol = (Permutation)sol.Clone();
     167        sol = (IntegerVector)sol.Clone();
     168       
    162169        for (var index = 0; index < N; index++) {
    163170          if (sol[index] == end[index]) continue;
    164           var fit = QAPSwap2MoveEvaluator.Apply(sol, new Swap2Move(index, invSol[end[index]]), qap.Weights, qap.Distances);
     171
     172          var oneMove = new NMove(reassignments[index], indices[index]);
     173          var eval = GQAPNMoveEvaluator.Evaluate(oneMove, sol, evaluation, gqap.ProblemInstance);
     174          var fit = gqap.ProblemInstance.ToSingleObjective(eval);
    165175          if (fit < bestFitness) { // QAP is minimization
    166176            bestFitness = fit;
     177            bestEvaluation = eval;
    167178            bestIndex = index;
    168179          }
    169180        }
    170181        if (bestIndex >= 0) {
    171           var prev = sol[bestIndex];
    172           Swap2Manipulator.Apply(sol, bestIndex, invSol[end[bestIndex]]);
    173           fitness += bestFitness;
     182          sol[bestIndex] = end[bestIndex];
     183          fitness = bestFitness;
     184          evaluation = bestEvaluation;
    174185          yield return Tuple.Create(sol, fitness);
    175           invSol[prev] = invSol[end[bestIndex]];
    176           invSol[sol[bestIndex]] = bestIndex;
    177186        } else break;
    178187      }
    179188    }
    180189
    181     private static IEnumerable<Tuple<Permutation, double>> FirstDirectedWalk(IRandom random, QuadraticAssignmentProblem qap, Permutation start, Permutation end) {
    182       var N = qap.Weights.Rows;
     190    private static IEnumerable<Tuple<IntegerVector, double>> FirstDirectedWalk(IRandom random, GQAP gqap, IntegerVector start, IntegerVector end) {
     191      var N = gqap.ProblemInstance.Demands.Length;
    183192      var sol = start;
    184       var fitness = QAPEvaluator.Apply(sol, qap.Weights, qap.Distances);
     193      var evaluation = gqap.ProblemInstance.Evaluate(start);
     194      var fitness = gqap.ProblemInstance.ToSingleObjective(evaluation);
    185195      yield return Tuple.Create(sol, fitness);
    186196
    187       var invSol = GetInverse(sol);
     197      var reassignments = Enumerable.Range(0, N).Select(x => {
     198        if (start[x] == end[x]) return null;
     199        var r = new int[N];
     200        r[x] = end[x] + 1;
     201        return r;
     202      }).ToArray();
     203      var indices = Enumerable.Range(0, N).Select(x => start[x] == end[x] ? null : new List<int>(1) { x }).ToArray();
     204
    188205      // randomize the order in which improvements are tried
    189206      var order = Enumerable.Range(0, N).Shuffle(random).ToArray();
    190       // we require at most N-1 steps to move from one permutation to another
    191       for (var step = 0; step < N - 1; step++) {
     207
     208      for (var step = 0; step < N; step++) {
    192209        var bestFitness = double.MaxValue;
     210        Evaluation bestEvaluation = null;
    193211        var bestIndex = -1;
    194         sol = (Permutation)sol.Clone();
     212        sol = (IntegerVector)sol.Clone();
    195213        for (var i = 0; i < N; i++) {
    196214          var index = order[i];
    197215          if (sol[index] == end[index]) continue;
    198           var fit = QAPSwap2MoveEvaluator.Apply(sol, new Swap2Move(index, invSol[end[index]]), qap.Weights, qap.Distances);
    199           if (fit < bestFitness) { // QAP is minimization
     216
     217          var oneMove = new NMove(reassignments[index], indices[index]);
     218          var eval = GQAPNMoveEvaluator.Evaluate(oneMove, sol, evaluation, gqap.ProblemInstance);
     219          var fit = gqap.ProblemInstance.ToSingleObjective(eval);
     220
     221          if (fit < bestFitness) { // GQAP is minimization
    200222            bestFitness = fit;
     223            bestEvaluation = evaluation;
    201224            bestIndex = index;
    202             if (bestFitness < 0) break;
     225            if (fit < fitness) break;
    203226          }
    204227        }
    205228        if (bestIndex >= 0) {
    206           var prev = sol[bestIndex];
    207           Swap2Manipulator.Apply(sol, bestIndex, invSol[end[bestIndex]]);
    208           fitness += bestFitness;
     229          sol[bestIndex] = end[bestIndex];
     230          fitness = bestFitness;
     231          evaluation = bestEvaluation;
    209232          yield return Tuple.Create(sol, fitness);
    210           invSol[prev] = invSol[end[bestIndex]];
    211           invSol[sol[bestIndex]] = bestIndex;
    212233        } else break;
    213       }
    214     }
    215 
    216     private static int[] GetInverse(Permutation p) {
    217       var inv = new int[p.Length];
    218       for (var i = 0; i < p.Length; i++) {
    219         inv[p[i]] = i;
    220       }
    221       return inv;
    222     }
    223 
    224     // permutation must be strictly different in every position
    225     private static void BiasedShuffle(Permutation p, IRandom random) {
    226       for (var i = p.Length - 1; i > 0; i--) {
    227         // Swap element "i" with a random earlier element (excluding itself)
    228         var swapIndex = random.Next(i);
    229         var h = p[swapIndex];
    230         p[swapIndex] = p[i];
    231         p[i] = h;
    232234      }
    233235    }
Note: See TracChangeset for help on using the changeset viewer.