1  #region License Information


2  /* HeuristicLab


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


23  using HeuristicLab.Core;


24  using HeuristicLab.Data;


25  using HeuristicLab.Optimization;


26  using HeuristicLab.Parameters;


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


28  using HeuristicLab.Problems.VehicleRouting.Encodings.General;


29  using HeuristicLab.Problems.VehicleRouting.Interfaces;


30 


31  namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {


32  [Item("PotvinManipulator", "A VRP manipulation operation.")]


33  [StorableClass]


34  public abstract class PotvinManipulator : VRPManipulator, IStochasticOperator, IPotvinOperator {


35  public ILookupParameter<IRandom> RandomParameter {


36  get { return (LookupParameter<IRandom>)Parameters["Random"]; }


37  }


38 


39  public IValueParameter<BoolValue> AllowInfeasibleSolutions {


40  get { return (IValueParameter<BoolValue>)Parameters["AllowInfeasibleSolutions"]; }


41  }


42 


43  [StorableConstructor]


44  protected PotvinManipulator(bool deserializing) : base(deserializing) { }


45 


46  public PotvinManipulator() {


47  Parameters.Add(new LookupParameter<IRandom>("Random", "The pseudo random number generator which should be used for stochastic manipulation operators."));


48  Parameters.Add(new ValueParameter<BoolValue>("AllowInfeasibleSolutions", "Indicates if infeasible solutions should be allowed.", new BoolValue(false)));


49  }


50 


51  protected PotvinManipulator(PotvinManipulator original, Cloner cloner)


52  : base(original, cloner) {


53  }


54 


55  protected abstract void Manipulate(IRandom random, PotvinEncoding individual);


56 


57  protected static int SelectRandomTourBiasedByLength(IRandom random, PotvinEncoding individual, IVRPProblemInstance instance) {


58  int tourIndex = 1;


59 


60  double sum = 0.0;


61  double[] probabilities = new double[individual.Tours.Count];


62  for (int i = 0; i < individual.Tours.Count; i++) {


63  probabilities[i] = 1.0 / ((double)individual.Tours[i].Stops.Count / (double)instance.Cities.Value);


64  sum += probabilities[i];


65  }


66 


67  for (int i = 0; i < probabilities.Length; i++)


68  probabilities[i] = probabilities[i] / sum;


69 


70  double rand = random.NextDouble();


71  double cumulatedProbabilities = 0.0;


72  int index = 0;


73  while (tourIndex == 1 && index < probabilities.Length) {


74  if (cumulatedProbabilities <= rand && rand <= cumulatedProbabilities + probabilities[index])


75  tourIndex = index;


76 


77  cumulatedProbabilities += probabilities[index];


78  index++;


79  }


80 


81  return tourIndex;


82  }


83 


84  protected static bool FindInsertionPlace(PotvinEncoding individual, int city, int routeToAvoid, bool allowInfeasible, out int route, out int place) {


85  return individual.FindInsertionPlace(


86  city, routeToAvoid, allowInfeasible, out route, out place);


87  }


88 


89  public override IOperation InstrumentedApply() {


90  IVRPEncoding solution = VRPToursParameter.ActualValue;


91  if (!(solution is PotvinEncoding)) {


92  VRPToursParameter.ActualValue = PotvinEncoding.ConvertFrom(solution, ProblemInstance);


93  }


94 


95  Manipulate(RandomParameter.ActualValue, VRPToursParameter.ActualValue as PotvinEncoding);


96  (VRPToursParameter.ActualValue as PotvinEncoding).Repair();


97 


98  return base.InstrumentedApply();


99  }


100  }


101  }

