1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022012 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 HeuristicLab.Common;


26  using HeuristicLab.Core;


27  using HeuristicLab.Data;


28  using HeuristicLab.Encodings.IntegerVectorEncoding;


29  using HeuristicLab.Parameters;


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


31  using HeuristicLab.Problems.GeneralizedQuadraticAssignment.Common;


32 


33  namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment {


34 


35  [Item("RelocateEquipmentManipluator", "Relocates a random equipment from an overstuffed location to a random one with space or a random equipment if constraints are satisfied.")]


36  [StorableClass]


37  public class RelocateEquipmentManipluator : GQAPManipulator, IDemandsAwareGQAPOperator, ICapacitiesAwareGQAPOperator {


38 


39  public ILookupParameter<DoubleArray> CapacitiesParameter {


40  get { return (ILookupParameter<DoubleArray>)Parameters["Capacities"]; }


41  }


42  public ILookupParameter<DoubleArray> DemandsParameter {


43  get { return (ILookupParameter<DoubleArray>)Parameters["Demands"]; }


44  }


45 


46  [StorableConstructor]


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


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


49  public RelocateEquipmentManipluator()


50  : base() {


51  Parameters.Add(new LookupParameter<DoubleArray>("Demands", GeneralizedQuadraticAssignmentProblem.DemandsDescription));


52  Parameters.Add(new LookupParameter<DoubleArray>("Capacities", GeneralizedQuadraticAssignmentProblem.CapacitiesDescription));


53  }


54 


55  public override IDeepCloneable Clone(Cloner cloner) {


56  return new RelocateEquipmentManipluator(this, cloner);


57  }


58 


59  public static void Apply(IRandom random, IntegerVector assignment, DoubleArray capacities, DoubleArray demands) {


60  int locations = capacities.Length;


61  if (locations < 2) throw new InvalidOperationException("There are not enough locations for relocation operations.");


62 


63  Dictionary<int, double> usedCapacities = new Dictionary<int, double>();


64  Dictionary<int, List<int>> groupedLocations = new Dictionary<int, List<int>>();


65  for (int i = 0; i < locations; i++) {


66  usedCapacities[i] = 0.0;


67  groupedLocations.Add(i, new List<int>());


68  }


69  for (int i = 0; i < assignment.Length; i++) {


70  usedCapacities[assignment[i]] += demands[i];


71  groupedLocations[assignment[i]].Add(i);


72  }


73 


74  var overbookedLocations = usedCapacities.Where(x => capacities[x.Key] < x.Value);


75  var freeLocations = usedCapacities.Where(x => capacities[x.Key] > x.Value);


76  if (!overbookedLocations.Any()  !freeLocations.Any()) { // perform a random relocation


77  assignment[random.Next(assignment.Length)] = random.Next(locations);


78  return;


79  }


80 


81  var sourceLocation = overbookedLocations.ChooseUniformRandom(random);


82  int equipmentToRelocate = groupedLocations[sourceLocation.Key].ChooseUniformRandom(random);


83  var bestFreeLocations = freeLocations.Where(x => capacities[x.Key] > x.Value + demands[equipmentToRelocate]);


84 


85  if (bestFreeLocations.Any()) { // a feasible solution will still be feasible, an infeasible solution might become feasible


86  var selected = bestFreeLocations.ChooseUniformRandom(random);


87  assignment[equipmentToRelocate] = sourceLocation.Key;


88  } else { // the solution will become infeasible


89  sourceLocation = freeLocations.ChooseUniformRandom(random);


90  assignment[equipmentToRelocate] = sourceLocation.Key;


91  }


92  }


93 


94  protected override void Manipulate(IRandom random, IntegerVector vector) {


95  Apply(random, vector, CapacitiesParameter.ActualValue, DemandsParameter.ActualValue);


96  }


97  }


98  }

