[13861]  1  #region License Information


 2  /* HeuristicLab


 3  * Copyright (C) 20022016 Heuristic and Evolutionary Algorithms Laboratory (HEAL)


 4  *


 5  * This file is part of HeuristicLab.


 6  *


 7  * HeuristicLab is free software: you can redistribute it and/or modify


 8  * it under the terms of the GNU General Public License as published by


 9  * the Free Software Foundation, either version 3 of the License, or


 10  * (at your option) any later version.


 11  *


 12  * HeuristicLab is distributed in the hope that it will be useful,


 13  * but WITHOUT ANY WARRANTY; without even the implied warranty of


 14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the


 15  * GNU General Public License for more details.


 16  *


 17  * You should have received a copy of the GNU General Public License


 18  * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.


 19  */


 20  #endregion


 21 


[15713]  22  using System;


 23  using System.Collections.Generic;


 24  using System.Linq;


[13861]  25  using HeuristicLab.Common;


 26  using HeuristicLab.Core;


 27  using HeuristicLab.Data;


[15713]  28  using HeuristicLab.Encodings.IntegerVectorEncoding;


[13861]  29  using HeuristicLab.Optimization;


 30  using HeuristicLab.Parameters;


 31  using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;


[15713]  32  using HeuristicLab.Problems.GeneralizedQuadraticAssignment;


[13861]  33  using HeuristicLab.Random;


 34 


[14678]  35  namespace HeuristicLab.Analysis.FitnessLandscape {


[15713]  36  [Item("Directed Walk (GQAPspecific)", "")]


[13861]  37  [StorableClass]


[15713]  38  public class GQAPDirectedWalk : CharacteristicCalculator {


[13861]  39 


 40  public IFixedValueParameter<IntValue> PathsParameter {


 41  get { return (IFixedValueParameter<IntValue>)Parameters["Paths"]; }


 42  }


 43 


 44  public IFixedValueParameter<BoolValue> BestImprovementParameter {


 45  get { return (IFixedValueParameter<BoolValue>)Parameters["BestImprovement"]; }


 46  }


 47 


 48  public IValueParameter<IntValue> SeedParameter {


 49  get { return (IValueParameter<IntValue>)Parameters["Seed"]; }


 50  }


 51 


[14690]  52  public IFixedValueParameter<BoolValue> LocalOptimaParameter {


 53  get { return (IFixedValueParameter<BoolValue>)Parameters["LocalOptima"]; }


 54  }


 55 


[13861]  56  public int Paths {


 57  get { return PathsParameter.Value.Value; }


 58  set { PathsParameter.Value.Value = value; }


 59  }


 60 


 61  public bool BestImprovement {


 62  get { return BestImprovementParameter.Value.Value; }


 63  set { BestImprovementParameter.Value.Value = value; }


 64  }


 65 


 66  public int? Seed {


 67  get { return SeedParameter.Value != null ? SeedParameter.Value.Value : (int?)null; }


 68  set { SeedParameter.Value = value.HasValue ? new IntValue(value.Value) : null; }


 69  }


 70 


[14690]  71  public bool LocalOptima {


 72  get { return LocalOptimaParameter.Value.Value; }


 73  set { LocalOptimaParameter.Value.Value = value; }


 74  }


 75 


[13861]  76  [StorableConstructor]


[15713]  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" }


[13861]  81  .Select(x => new StringValue(x)).ToList());


 82  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)));


 83  Parameters.Add(new FixedValueParameter<BoolValue>("BestImprovement", "Whether the best of all alternatives should be chosen for each step in the path or just the first improving (least degrading) move should be made.", new BoolValue(true)));


 84  Parameters.Add(new OptionalValueParameter<IntValue>("Seed", "The seed for the random number generator."));


[14690]  85  Parameters.Add(new FixedValueParameter<BoolValue>("LocalOptima", "Whether to perform walks between local optima.", new BoolValue(false)));


[13861]  86  }


 87 


 88  public override IDeepCloneable Clone(Cloner cloner) {


[15713]  89  return new GQAPDirectedWalk(this, cloner);


[13861]  90  }


 91 


 92  public override bool CanCalculate() {


[15713]  93  return Problem is GQAP;


[13861]  94  }


 95 


 96  public override IEnumerable<IResult> Calculate() {


[14429]  97  IRandom random = Seed.HasValue ? new MersenneTwister((uint)Seed.Value) : new MersenneTwister();


[15713]  98  var gqap = (GQAP)Problem;


 99  List<IntegerVector> assignments = CalculateRelinkingPoints(random, gqap, Paths, LocalOptima);


[13861]  100 


[15713]  101  var trajectories = Run(random, (GQAP)Problem, assignments, BestImprovement).ToList();


 102  var result = IntegerVectorPathAnalysis.GetCharacteristics(trajectories);


[15031]  103 


 104  foreach (var chara in characteristics.CheckedItems.Select(x => x.Value.Value)) {


[15713]  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));


[15031]  108  }


 109  }


 110 


[15713]  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);


[15031]  113  if (localOptima) {


[15713]  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);


[14690]  117  }


[15713]  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);


[15031]  122  if (localOptima) {


[15713]  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);


[14690]  126  }


[15713]  127  if (HammingSimilarityCalculator.CalculateSimilarity(points.Last(), assign) < 0.75)


 128  points.Add(assign);


[14429]  129  }


[13861]  130 


[15713]  131  return points;


[14429]  132  }


[13861]  133 


[15713]  134  public static IEnumerable<List<Tuple<IntegerVector, double>>> Run(IRandom random, GQAP gqap, IEnumerable<IntegerVector> points, bool bestImprovement = true) {


 135  var iter = points.GetEnumerator();


[14429]  136  if (!iter.MoveNext()) yield break;


[13861]  137 


[14429]  138  var start = iter.Current;


 139  while (iter.MoveNext()) {


 140  var end = iter.Current;


[13861]  141 


[15713]  142  var walk = (bestImprovement ? BestDirectedWalk(gqap, start, end) : FirstDirectedWalk(random, gqap, start, end)).ToList();


 143  yield return walk.ToList();


[14429]  144  start = end;


 145  } // end paths


 146  }


[13861]  147 


[15713]  148  private static IEnumerable<Tuple<IntegerVector, double>> BestDirectedWalk(GQAP gqap, IntegerVector start, IntegerVector end) {


 149  var N = gqap.ProblemInstance.Demands.Length;


[13861]  150  var sol = start;


[15713]  151  var evaluation = gqap.ProblemInstance.Evaluate(start);


 152  var fitness = gqap.ProblemInstance.ToSingleObjective(evaluation);


[14429]  153  yield return Tuple.Create(sol, fitness);


[15713]  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();


[14429]  162 


[15713]  163  for (var step = 0; step < N; step++) {


[13861]  164  var bestFitness = double.MaxValue;


[15713]  165  Evaluation bestEvaluation = null;


[13861]  166  var bestIndex = 1;


[15713]  167  sol = (IntegerVector)sol.Clone();


 168 


[13861]  169  for (var index = 0; index < N; index++) {


 170  if (sol[index] == end[index]) continue;


[15713]  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);


[13861]  175  if (fit < bestFitness) { // QAP is minimization


 176  bestFitness = fit;


[15713]  177  bestEvaluation = eval;


[13861]  178  bestIndex = index;


 179  }


 180  }


 181  if (bestIndex >= 0) {


[15713]  182  sol[bestIndex] = end[bestIndex];


 183  fitness = bestFitness;


 184  evaluation = bestEvaluation;


[13861]  185  yield return Tuple.Create(sol, fitness);


 186  } else break;


 187  }


 188  }


 189 


[15713]  190  private static IEnumerable<Tuple<IntegerVector, double>> FirstDirectedWalk(IRandom random, GQAP gqap, IntegerVector start, IntegerVector end) {


 191  var N = gqap.ProblemInstance.Demands.Length;


[13861]  192  var sol = start;


[15713]  193  var evaluation = gqap.ProblemInstance.Evaluate(start);


 194  var fitness = gqap.ProblemInstance.ToSingleObjective(evaluation);


[14429]  195  yield return Tuple.Create(sol, fitness);


 196 


[15713]  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 


[13861]  205  // randomize the order in which improvements are tried


 206  var order = Enumerable.Range(0, N).Shuffle(random).ToArray();


[15713]  207 


 208  for (var step = 0; step < N; step++) {


[13861]  209  var bestFitness = double.MaxValue;


[15713]  210  Evaluation bestEvaluation = null;


[13861]  211  var bestIndex = 1;


[15713]  212  sol = (IntegerVector)sol.Clone();


[13861]  213  for (var i = 0; i < N; i++) {


 214  var index = order[i];


 215  if (sol[index] == end[index]) continue;


[15713]  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


[13861]  222  bestFitness = fit;


[15713]  223  bestEvaluation = evaluation;


[13861]  224  bestIndex = index;


[15713]  225  if (fit < fitness) break;


[13861]  226  }


 227  }


 228  if (bestIndex >= 0) {


[15713]  229  sol[bestIndex] = end[bestIndex];


 230  fitness = bestFitness;


 231  evaluation = bestEvaluation;


[13861]  232  yield return Tuple.Create(sol, fitness);


 233  } else break;


 234  }


 235  }


 236  }


 237  }

