1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 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.Collections.Generic;


23  using HeuristicLab.Common;


24  using HeuristicLab.Core;


25  using HeuristicLab.Data;


26  using HeuristicLab.Optimization;


27  using HeuristicLab.Parameters;


28  using HEAL.Attic;


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


30  using HeuristicLab.Problems.VehicleRouting.Interfaces;


31 


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


33  [Item("PotvinCrossover", "A VRP crossover operation.")]


34  [StorableType("B2E9AC24C68945ADBEDE2F226E044BDE")]


35  public abstract class PotvinCrossover : VRPCrossover, IStochasticOperator, IPotvinOperator {


36  public ILookupParameter<IRandom> RandomParameter {


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


38  }


39 


40  public IValueParameter<BoolValue> AllowInfeasibleSolutions {


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


42  }


43 


44  [StorableConstructor]


45  protected PotvinCrossover(StorableConstructorFlag _) : base(_) { }


46 


47  public PotvinCrossover() {


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


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


50  }


51 


52  protected PotvinCrossover(PotvinCrossover original, Cloner cloner)


53  : base(original, cloner) {


54  }


55 


56  protected abstract PotvinEncodedSolution Crossover(IRandom random, PotvinEncodedSolution parent1, PotvinEncodedSolution parent2);


57 


58  protected static bool FindInsertionPlace(PotvinEncodedSolution individual, int city, bool allowInfeasible,


59  out int route, out int place) {


60  return individual.FindInsertionPlace(


61  city, 1, allowInfeasible,


62  out route, out place);


63  }


64 


65  protected static Tour FindRoute(PotvinEncodedSolution solution, int city) {


66  Tour found = null;


67 


68  foreach (Tour tour in solution.Tours) {


69  if (tour.Stops.Contains(city)) {


70  found = tour;


71  break;


72  }


73  }


74 


75  return found;


76  }


77 


78  protected static bool RouteUnrouted(PotvinEncodedSolution solution, bool allowInfeasible) {


79  bool success = true;


80  int index = 0;


81  while (index < solution.Unrouted.Count && success) {


82  int unrouted = solution.Unrouted[index];


83 


84  int route, place;


85  if (FindInsertionPlace(solution, unrouted, allowInfeasible,


86  out route, out place)) {


87  solution.Tours[route].Stops.Insert(place, unrouted);


88  } else {


89  success = false;


90  }


91 


92  index++;


93  }


94 


95  for (int i = 0; i < index; i++)


96  solution.Unrouted.RemoveAt(0);


97 


98  return success;


99  }


100 


101  protected static bool Repair(IRandom random, PotvinEncodedSolution solution, Tour newTour, IVRPProblemInstance instance, bool allowInfeasible) {


102  bool success = true;


103 


104  //remove duplicates from new tour


105  for (int i = 0; i < newTour.Stops.Count; i++) {


106  for (int j = 0; j < newTour.Stops.Count; j++) {


107  if (newTour.Stops[i] == newTour.Stops[j] && i != j) {


108  if (random.NextDouble() < 0.5)


109  newTour.Stops[i] = 0;


110  else


111  newTour.Stops[j] = 0;


112  }


113  }


114  }


115  while (newTour.Stops.Contains(0))


116  newTour.Stops.Remove(0);


117 


118  //remove duplicates from old tours


119  for (int i = 0; i < newTour.Stops.Count; i++) {


120  foreach (Tour tour in solution.Tours) {


121  if (tour != newTour && tour.Stops.Contains(newTour.Stops[i])) {


122  tour.Stops.Remove(newTour.Stops[i]);


123  }


124  }


125  }


126 


127  //remove empty tours


128  List<Tour> toBeDeleted = new List<Tour>();


129  foreach (Tour tour in solution.Tours) {


130  if (tour.Stops.Count == 0)


131  toBeDeleted.Add(tour);


132  }


133  foreach (Tour tour in toBeDeleted) {


134  solution.Tours.Remove(tour);


135  }


136 


137  if (newTour.Stops.Count > 0 && !allowInfeasible && !instance.TourFeasible(newTour, solution))


138  return false;


139 


140  //route unrouted vehicles


141  success = RouteUnrouted(solution, allowInfeasible);


142 


143  return success;


144  }


145 


146  public override IOperation InstrumentedApply() {


147  ItemArray<IVRPEncodedSolution> parents = new ItemArray<IVRPEncodedSolution>(ParentsParameter.ActualValue.Length);


148  for (int i = 0; i < ParentsParameter.ActualValue.Length; i++) {


149  IVRPEncodedSolution solution = ParentsParameter.ActualValue[i];


150 


151  if (!(solution is PotvinEncodedSolution)) {


152  parents[i] = PotvinEncodedSolution.ConvertFrom(solution, ProblemInstance);


153  } else {


154  parents[i] = solution;


155  }


156  }


157  ParentsParameter.ActualValue = parents;


158 


159  ChildParameter.ActualValue = Crossover(RandomParameter.ActualValue, parents[0] as PotvinEncodedSolution, parents[1] as PotvinEncodedSolution);


160  (ChildParameter.ActualValue as PotvinEncodedSolution).Repair();


161 


162  return base.InstrumentedApply();


163  }


164  }


165  }

