Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Crossovers/PotvinCrossover.cs @ 10298

Last change on this file since 10298 was 10298, checked in by svonolfe, 10 years ago

Adapted all VRP related operators to subclass InstrumentedOperator (#2119)

File size: 5.8 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2013 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
22using System.Collections.Generic;
23using HeuristicLab.Common;
24using HeuristicLab.Core;
25using HeuristicLab.Data;
26using HeuristicLab.Optimization;
27using HeuristicLab.Parameters;
28using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
29using HeuristicLab.Problems.VehicleRouting.Encodings.General;
30using HeuristicLab.Problems.VehicleRouting.Interfaces;
31
32namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
33  [Item("PotvinCrossover", "A VRP crossover operation.")]
34  [StorableClass]
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(bool deserializing) : base(deserializing) { }
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 PotvinEncoding Crossover(IRandom random, PotvinEncoding parent1, PotvinEncoding parent2);
57
58    protected static bool FindInsertionPlace(PotvinEncoding 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(PotvinEncoding 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(PotvinEncoding 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, PotvinEncoding 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<IVRPEncoding> parents = new ItemArray<IVRPEncoding>(ParentsParameter.ActualValue.Length);
148      for (int i = 0; i < ParentsParameter.ActualValue.Length; i++) {
149        IVRPEncoding solution = ParentsParameter.ActualValue[i];
150
151        if (!(solution is PotvinEncoding)) {
152          parents[i] = PotvinEncoding.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 PotvinEncoding, parents[1] as PotvinEncoding);
160      (ChildParameter.ActualValue as PotvinEncoding).Repair();
161
162      return base.InstrumentedApply();
163    }
164  }
165}
Note: See TracBrowser for help on using the repository browser.