1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022018 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 IScopeTreeLookupParameter<DoubleValue> QualityParameter {


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


40  }


41  public IScopeTreeLookupParameter<Evaluation> EvaluationParameter {


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


43  }


44  public ILookupParameter<IntValue> EvaluatedSolutionsParameter {


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


46  }


47 


48  [StorableConstructor]


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


50  protected CordeauCrossover(CordeauCrossover original, Cloner cloner)


51  : base(original, cloner) {


52  }


53  public CordeauCrossover()


54  : base() {


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


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


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


58  }


59 


60  public override IDeepCloneable Clone(Cloner cloner) {


61  return new CordeauCrossover(this, cloner);


62  }


63 


64  public static IntegerVector Apply(IRandom random,


65  IntegerVector parent1, DoubleValue quality1,


66  IntegerVector parent2, DoubleValue quality2,


67  GQAPInstance problemInstance, IntValue evaluatedSolutions) {


68  var distances = problemInstance.Distances;


69  var capacities = problemInstance.Capacities;


70  var demands = problemInstance.Demands;


71 


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


73 


74  int m = capacities.Length;


75  int n = demands.Length;


76 


77  bool onefound = false;


78  double fbest, fbestAttempt = double.MaxValue;


79  IntegerVector bestAttempt = null;


80  IntegerVector result = null;


81 


82  fbest = quality1.Value;


83  if (quality1.Value > quality2.Value) {


84  var temp = parent1;


85  parent1 = parent2;


86  parent2 = temp;


87  fbest = quality2.Value;


88  }


89  var cap = new double[m];


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


91  int unassigned;


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


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


94  if (unassigned > 0)


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


96  if (unassigned == 0) {


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


98  evaluatedSolutions.Value++;


99  if (childFit <= fbest) {


100  fbest = childFit;


101  result = child;


102  onefound = true;


103  }


104  if (!onefound && fbestAttempt > childFit) {


105  bestAttempt = child;


106  fbestAttempt = childFit;


107  }


108  }


109  }


110 


111  if (!onefound) {


112  var i = random.Next(m);


113  int unassigned;


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


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


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


117 


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


119  evaluatedSolutions.Value++;


120  if (childFit < fbest) {


121  fbest = childFit;


122  result = child;


123  onefound = true;


124  }


125 


126  if (!onefound && fbestAttempt > childFit) {


127  bestAttempt = child;


128  fbestAttempt = childFit;


129  }


130  }


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


132  solution_cost(&son);


133  if (son.cost < fbest) {


134  fbest = son.cost;


135  *sptr = son;


136  onefound = TRUE;


137  merge_fixed++;


138  }*/


139  return result ?? bestAttempt;


140  }


141 


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


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


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


145  unassigned = n;


146  var child = new IntegerVector(n);


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


148  child[k] = 1;


149  var ik1 = p1[k];


150  var ik2 = p2[k];


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


152  child[k] = ik1;


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


154  unassigned;


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


156  child[k] = ik2;


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


158  unassigned;


159  };


160  }


161  return child;


162  }


163 


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


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


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


167  var k = unbiasedOrder[idx];


168  if (child[k] < 0) {


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


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


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


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


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


174  child[k] = j;


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


176  unassigned;


177  }


178  }


179  return true;


180  }


181 


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


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


184  if (child[k] < 0) {


185  var j = random.Next(m);


186  child[k] = j;


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


188  unassigned;


189  }


190  }


191  }


192 


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


194  GQAPInstance problemInstance) {


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


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


197 


198  var qualities = QualityParameter.ActualValue;


199  return Apply(random,


200  parents[0], qualities[0],


201  parents[1], qualities[1],


202  problemInstance,


203  EvaluatedSolutionsParameter.ActualValue);


204  }


205  }


206  }

