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.Collections.Generic;


24  using System.Linq;


25  using System.Threading;


26  using HeuristicLab.Common;


27  using HeuristicLab.Core;


28  using HeuristicLab.Data;


29  using HeuristicLab.Encodings.IntegerVectorEncoding;


30  using HeuristicLab.Parameters;


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


32  using HeuristicLab.Random;


33 


34  namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment {


35  [Item("RandomButFeasibleSolutionCreator", "Creates a random, but feasible solution to the Generalized Quadratic Assignment Problem.")]


36  [StorableClass]


37  public class RandomFeasibleSolutionCreator : GQAPStochasticSolutionCreator {


38 


39  public IValueLookupParameter<IntValue> MaximumTriesParameter {


40  get { return (IValueLookupParameter<IntValue>)Parameters["MaximumTries"]; }


41  }


42  public IValueLookupParameter<BoolValue> CreateMostFeasibleSolutionParameter {


43  get { return (IValueLookupParameter<BoolValue>)Parameters["CreateMostFeasibleSolution"]; }


44  }


45 


46  [StorableConstructor]


47  protected RandomFeasibleSolutionCreator(bool deserializing) : base(deserializing) { }


48  protected RandomFeasibleSolutionCreator(RandomFeasibleSolutionCreator original, Cloner cloner) : base(original, cloner) { }


49  public RandomFeasibleSolutionCreator()


50  : base() {


51  Parameters.Add(new ValueLookupParameter<IntValue>("MaximumTries", "The maximum number of tries to create a feasible solution after which an exception is thrown. If it is set to 0 or a negative value there will be an infinite number of attempts.", new IntValue(100000)));


52  Parameters.Add(new ValueLookupParameter<BoolValue>("CreateMostFeasibleSolution", "If this is set to true the operator will always succeed, and outputs the solution with the least violation instead of throwing an exception.", new BoolValue(false)));


53  }


54 


55  public override IDeepCloneable Clone(Cloner cloner) {


56  return new RandomFeasibleSolutionCreator(this, cloner);


57  }


58 


59  public static IntegerVector CreateSolution(IRandom random, GQAPInstance problemInstance,


60  int maximumTries, bool createMostFeasibleSolution, CancellationToken cancel) {


61  var capacities = problemInstance.Capacities;


62  var demands = problemInstance.Demands;


63  IntegerVector result = null;


64  bool isFeasible = false;


65  int counter = 0;


66  double minViolation = double.MaxValue;


67  var slack = new double[capacities.Length];


68  var assignment = new int[demands.Length];


69 


70  while (!isFeasible) {


71  cancel.ThrowIfCancellationRequested();


72  if (maximumTries > 0) {


73  counter++;


74  if (counter > maximumTries) {


75  if (createMostFeasibleSolution) break;


76  else throw new InvalidOperationException("A feasible solution could not be obtained after " + maximumTries + " attempts.");


77  }


78  }


79  for (int i = 0; i < capacities.Length; i++) slack[i] = capacities[i];


80  foreach (var equipment in Enumerable.Range(0, demands.Length).Shuffle(random)) {


81  var freeLocations = GetFreeLocations(equipment, demands, slack);


82  assignment[equipment] = freeLocations.SampleRandom(random);


83  slack[assignment[equipment]] = demands[equipment];


84  }


85  double violation = slack.Select(x => x < 0 ? x : 0).Sum();


86  isFeasible = violation == 0;


87  if (isFeasible  violation < minViolation) {


88  result = new IntegerVector(assignment);


89  minViolation = violation;


90  }


91  }


92  return result;


93  }


94 


95  protected override IntegerVector CreateRandomSolution(IRandom random, GQAPInstance problemInstance) {


96  return CreateSolution(random, problemInstance,


97  MaximumTriesParameter.ActualValue.Value,


98  CreateMostFeasibleSolutionParameter.ActualValue.Value,


99  CancellationToken);


100  }


101 


102  private static IEnumerable<int> GetFreeLocations(int equipment, DoubleArray demands, double[] freeCapacities) {


103  var freeLocations = freeCapacities


104  .Select((v, idx) => new KeyValuePair<int, double>(idx, v))


105  .Where(x => x.Value >= demands[equipment]);


106  if (!freeLocations.Any()) {


107  freeLocations = freeCapacities


108  .Select((v, idx) => new KeyValuePair<int, double>(idx, v))


109  .OrderByDescending(x => x.Value)


110  .Take(3); // if there are none, take the three where the free capacity is largest


111  }


112  return freeLocations.Select(x => x.Key);


113  }


114  }


115  }

