1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022017 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 


22  using System;


23  using System.Linq;


24  using HeuristicLab.Common;


25  using HeuristicLab.Core;


26  using HeuristicLab.Data;


27  using HeuristicLab.Encodings.IntegerVectorEncoding;


28  using HeuristicLab.Parameters;


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


30  using HeuristicLab.Random;


31 


32  namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment {


33  [Item("CordeauCrossover", "The merge procedure that is described in Cordeau, J.F., Gaudioso, M., Laporte, G., Moccia, L. 2006. A memetic heuristic for the generalized quadratic assignment problem. INFORMS Journal on Computing, 18, pp. 433–443.")]


34  [StorableClass]


35  public class CordeauCrossover : GQAPCrossover,


36  IQualitiesAwareGQAPOperator, IProblemInstanceAwareGQAPOperator {


37 


38  public ILookupParameter<BoolValue> MaximizationParameter {


39  get { return (ILookupParameter<BoolValue>)Parameters["Maximization"]; }


40  }


41  public IScopeTreeLookupParameter<DoubleValue> QualityParameter {


42  get { return (IScopeTreeLookupParameter<DoubleValue>)Parameters["Quality"]; }


43  }


44  public IScopeTreeLookupParameter<Evaluation> EvaluationParameter {


45  get { return (IScopeTreeLookupParameter<Evaluation>)Parameters["Evaluation"]; }


46  }


47  public ILookupParameter<IntValue> EvaluatedSolutionsParameter {


48  get { return (ILookupParameter<IntValue>)Parameters["EvaluatedSolutions"]; }


49  }


50 


51  [StorableConstructor]


52  protected CordeauCrossover(bool deserializing) : base(deserializing) { }


53  protected CordeauCrossover(CordeauCrossover original, Cloner cloner)


54  : base(original, cloner) {


55  }


56  public CordeauCrossover()


57  : base() {


58  Parameters.Add(new LookupParameter<BoolValue>("Maximization", ""));


59  Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("Quality", "The quality of the parents", 1));


60  Parameters.Add(new ScopeTreeLookupParameter<Evaluation>("Evaluation", GQAP.EvaluationDescription, 1));


61  Parameters.Add(new LookupParameter<IntValue>("EvaluatedSolutions", "The number of evaluated solutions."));


62  }


63 


64  public override IDeepCloneable Clone(Cloner cloner) {


65  return new CordeauCrossover(this, cloner);


66  }


67 


68  public static IntegerVector Apply(IRandom random, bool maximization,


69  IntegerVector parent1, DoubleValue quality1,


70  IntegerVector parent2, DoubleValue quality2,


71  GQAPInstance problemInstance, IntValue evaluatedSolutions) {


72  var distances = problemInstance.Distances;


73  var capacities = problemInstance.Capacities;


74  var demands = problemInstance.Demands;


75 


76  var medianDistances = Enumerable.Range(0, distances.Rows).Select(x => distances.GetRow(x).Median()).ToArray();


77 


78  int m = capacities.Length;


79  int n = demands.Length;


80 


81  bool onefound = false;


82  double fbest, fbestAttempt = maximization ? double.MinValue : double.MaxValue;


83  IntegerVector bestAttempt = null;


84  IntegerVector result = null;


85 


86  fbest = quality1.Value;


87  if (maximization && quality1.Value < quality2.Value


88   !maximization && quality1.Value > quality2.Value) {


89  var temp = parent1;


90  parent1 = parent2;


91  parent2 = temp;


92  fbest = quality2.Value;


93  }


94  var cap = new double[m];


95  for (var i = 0; i < m; i++) {


96  int unassigned;


97  Array.Clear(cap, 0, m);


98  var child = Merge(parent1, parent2, distances, demands, medianDistances, m, n, i, cap, out unassigned);


99  if (unassigned > 0)


100  TryRandomAssignment(random, demands, capacities, m, n, cap, child, ref unassigned);


101  if (unassigned == 0) {


102  var childFit = problemInstance.ToSingleObjective(problemInstance.Evaluate(child));


103  evaluatedSolutions.Value++;


104  if (maximization && childFit >= fbest


105   !maximization && childFit <= fbest) {


106  fbest = childFit;


107  result = child;


108  onefound = true;


109  }


110  if (!onefound && (maximization && fbestAttempt < childFit  !maximization && fbestAttempt > childFit)) {


111  bestAttempt = child;


112  fbestAttempt = childFit;


113  }


114  }


115  }


116 


117  if (!onefound) {


118  var i = random.Next(m);


119  int unassigned;


120  Array.Clear(cap, 0, m);


121  var child = Merge(parent1, parent2, distances, demands, medianDistances, m, n, i, cap, out unassigned);


122  RandomAssignment(random, demands, capacities, m, n, cap, child, ref unassigned);


123 


124  var childFit = problemInstance.ToSingleObjective(problemInstance.Evaluate(child));


125  evaluatedSolutions.Value++;


126  if (childFit < fbest) {


127  fbest = childFit;


128  result = child;


129  onefound = true;


130  }


131 


132  if (!onefound && (maximization && fbestAttempt < childFit  !maximization && fbestAttempt > childFit)) {


133  bestAttempt = child;


134  fbestAttempt = childFit;


135  }


136  }


137  /*if (tabufix(&son, 0.5 * sqrt(n * m), round(n * m * log10(n)), &tabufix_it)) {


138  solution_cost(&son);


139  if (son.cost < fbest) {


140  fbest = son.cost;


141  *sptr = son;


142  onefound = TRUE;


143  merge_fixed++;


144  }*/


145  return result ?? bestAttempt;


146  }


147 


148  private static IntegerVector Merge(IntegerVector p1, IntegerVector p2,


149  DoubleMatrix distances, DoubleArray demands, double[] mediana,


150  int m, int n, int i, double[] cap, out int unassigned) {


151  unassigned = n;


152  var child = new IntegerVector(n);


153  for (var k = 0; k < n; k++) {


154  child[k] = 1;


155  var ik1 = p1[k];


156  var ik2 = p2[k];


157  if (distances[i, ik1] < mediana[i]) {


158  child[k] = ik1;


159  cap[ik1] += demands[k];


160  unassigned;


161  } else if (distances[i, ik2] > mediana[i]) {


162  child[k] = ik2;


163  cap[ik2] += demands[k];


164  unassigned;


165  };


166  }


167  return child;


168  }


169 


170  private static bool TryRandomAssignment(IRandom random, DoubleArray demands, DoubleArray capacities, int m, int n, double[] cap, IntegerVector child, ref int unassigned) {


171  var unbiasedOrder = Enumerable.Range(0, n).Shuffle(random).ToList();


172  for (var idx = 0; idx < n; idx++) {


173  var k = unbiasedOrder[idx];


174  if (child[k] < 0) {


175  var feasibleInserts = Enumerable.Range(0, m)


176  .Select((v, i) => new { Pos = i, Slack = capacities[i]  cap[i] })


177  .Where(x => x.Slack >= demands[k]).ToList();


178  if (feasibleInserts.Count == 0) return false;


179  var j = feasibleInserts.SampleRandom(random).Pos;


180  child[k] = j;


181  cap[j] += demands[k];


182  unassigned;


183  }


184  }


185  return true;


186  }


187 


188  private static void RandomAssignment(IRandom random, DoubleArray demands, DoubleArray capacities, int m, int n, double[] cap, IntegerVector child, ref int unassigned) {


189  for (var k = 0; k < n; k++) {


190  if (child[k] < 0) {


191  var j = random.Next(m);


192  child[k] = j;


193  cap[j] += demands[k];


194  unassigned;


195  }


196  }


197  }


198 


199  protected override IntegerVector Cross(IRandom random, ItemArray<IntegerVector> parents,


200  GQAPInstance problemInstance) {


201  if (parents == null) throw new ArgumentNullException("parents");


202  if (parents.Length != 2) throw new ArgumentException(Name + " works only with exactly two parents.");


203 


204  var qualities = QualityParameter.ActualValue;


205  return Apply(random, MaximizationParameter.ActualValue.Value,


206  parents[0], qualities[0],


207  parents[1], qualities[1],


208  problemInstance,


209  EvaluatedSolutionsParameter.ActualValue);


210  }


211  }


212  }

