Free cookie consent management tool by TermsFeed Policy Generator

source: branches/FitnessLandscapeAnalysis/HeuristicLab.Analysis.FitnessLandscape.VRP/Manipulators/TwoOptStarManipulator.cs @ 14330

Last change on this file since 14330 was 9836, checked in by epitzer, 11 years ago

Fix VRP FLA manipulators and adapt to VRP-3.4 (#1703)

File size: 4.0 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2011 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.Persistence.Default.CompositeSerializers.Storable;
26using HeuristicLab.Data;
27using HeuristicLab.Parameters;
28using HeuristicLab.Problems.VehicleRouting.Encodings.Potvin;
29using HeuristicLab.Problems.VehicleRouting.Encodings;
30using HeuristicLab.Problems.VehicleRouting;
31using HeuristicLab.Problems.VehicleRouting.Interfaces;
32
33namespace HeuristicLab.Analysis.FitnessLandscape.VRP {
34  [Item("TwoOptStarManipulator", "Two opt star manipulation")]
35  [StorableClass]
36  public sealed class TwoOptStarManipulator : PotvinManipulator {
37    [StorableConstructor]
38    private TwoOptStarManipulator(bool deserializing) : base(deserializing) { }
39    private TwoOptStarManipulator(TwoOptStarManipulator original, Cloner cloner)
40      : base(original, cloner) {
41    }
42    public override IDeepCloneable Clone(Cloner cloner) {
43      return new TwoOptStarManipulator(this, cloner);
44    }
45    public TwoOptStarManipulator()
46      : base() {
47    }
48
49    public static void Apply(IRandom random, PotvinEncoding individual, IVRPProblemInstance problemInstance, bool allowInfeasible) {
50      bool feasible;
51      int count = 0;
52
53      //consider creating new tour
54      individual.Tours.Add(new Tour());
55
56      do {
57        feasible = true;
58
59        int route1Idx = random.Next(individual.Tours.Count);
60        int route2Idx = random.Next(individual.Tours.Count - 1);
61        if (route2Idx >= route1Idx)
62          route2Idx++;
63
64        Tour route1 = individual.Tours[route1Idx];
65        Tour route2 = individual.Tours[route2Idx];
66
67        int x1 = random.Next(route1.Stops.Count + 1);
68        int x2 = random.Next(route2.Stops.Count + 1);
69
70        var originalFeasible =
71          problemInstance.TourFeasible(route1, individual) &&
72          problemInstance.TourFeasible(route2, individual);
73
74       SwapSegments(x1, route1, x2, route2);
75
76       if (!allowInfeasible && originalFeasible) {
77         feasible = problemInstance.TourFeasible(route1, individual) &&
78                    problemInstance.TourFeasible(route2, individual);
79         if (!feasible) SwapSegments(x1, route1, x2, route2);
80       }
81      } while (!feasible && count++ < 100);
82
83      individual.Tours.RemoveAll(t => t.Stops.Count == 0);
84    }
85
86    private static void SwapSegments(int x1, Tour route1, int x2, Tour route2) {
87      int count = route1.Stops.Count - x1;
88      List<int> segmentX1 = new List<int>();
89      if (count > 0) {
90        segmentX1 = route1.Stops.GetRange(x1, count);
91        route1.Stops.RemoveRange(x1, count);
92      }
93      count = route2.Stops.Count - x2;
94      List<int> segmentX2 = new List<int>();
95      if (count > 0) {
96        segmentX2 = route2.Stops.GetRange(x2, count);
97        route2.Stops.RemoveRange(x2, count);
98      }
99      route1.Stops.AddRange(segmentX2);
100      route2.Stops.AddRange(segmentX1);
101    }
102
103    protected override void Manipulate(IRandom random, PotvinEncoding individual) {
104      bool allowInfeasible = AllowInfeasibleSolutions.Value.Value;
105      Apply(random, individual, ProblemInstance, allowInfeasible);
106    }
107  }
108}
Note: See TracBrowser for help on using the repository browser.