source: branches/ScatterSearch/HeuristicLab.Algorithms.ScatterSearch/3.3/TravelingSalesman/TravelingSalesmanImprovementOperator.cs @ 7786

Last change on this file since 7786 was 7786, checked in by jkarder, 9 years ago

#1331:

  • fixed bug in path relinking selection
  • fixed bug in ScatterSearch.Prepare()
  • added custom interface (IImprovementOperator) for Scatter Search specific improvement operators
  • switched from diversity calculation to similarity calculation
  • separated IPathRelinker from ICrossover
  • changed TestFunctionsImprovementOperator to use reflection for evaluating functions
  • changed SolutionPoolUpdateMethod to use similarity calculation for solution comparison
  • improved TravelingSalesmanImprovementOperator
  • improved operator graph
  • removed specific operators used to evaluate TestFunctions problems
  • removed custom crossover operator (NChildCrossover)
  • added parameters and adjusted types
  • adjusted event handling
  • changed access levels
  • minor code improvements
File size: 6.0 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2012 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;
23using HeuristicLab.Common;
24using HeuristicLab.Core;
25using HeuristicLab.Data;
26using HeuristicLab.Encodings.PermutationEncoding;
27using HeuristicLab.Operators;
28using HeuristicLab.Optimization;
29using HeuristicLab.Parameters;
30using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
31using HeuristicLab.Problems.TravelingSalesman;
32
33namespace HeuristicLab.Algorithms.ScatterSearch.TravelingSalesman {
34  /// <summary>
35  /// An operator that improves traveling salesman solutions.
36  /// </summary>
37  [Item("TravelingSalesmanImprovementOperator", "An operator that improves traveling salesman solutions.")]
38  [StorableClass]
39  public sealed class TravelingSalesmanImprovementOperator : SingleSuccessorOperator, IImprovementOperator {
40    #region Parameter properties
41    public ScopeParameter CurrentScopeParameter {
42      get { return (ScopeParameter)Parameters["CurrentScope"]; }
43    }
44    public ILookupParameter<DistanceMatrix> DistanceMatrixParameter {
45      get { return (ILookupParameter<DistanceMatrix>)Parameters["DistanceMatrix"]; }
46    }
47    public ILookupParameter<IEvaluator> EvaluatorParameter {
48      get { return (ILookupParameter<IEvaluator>)Parameters["Evaluator"]; }
49    }
50    public IValueParameter<IntValue> ImprovementAttemptsParameter {
51      get { return (IValueParameter<IntValue>)Parameters["ImprovementAttempts"]; }
52    }
53    public ILookupParameter<IRandom> RandomParameter {
54      get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
55    }
56    public IValueLookupParameter<IItem> TargetParameter {
57      get { return (IValueLookupParameter<IItem>)Parameters["Target"]; }
58    }
59    #endregion
60
61    #region Properties
62    public IScope CurrentScope {
63      get { return CurrentScopeParameter.ActualValue; }
64    }
65    public DistanceMatrix DistanceMatrix {
66      get { return DistanceMatrixParameter.ActualValue; }
67      set { DistanceMatrixParameter.ActualValue = value; }
68    }
69    public IEvaluator Evaluator {
70      get { return EvaluatorParameter.ActualValue; }
71      set { EvaluatorParameter.ActualValue = value; }
72    }
73    public IntValue ImprovementAttempts {
74      get { return ImprovementAttemptsParameter.Value; }
75      set { ImprovementAttemptsParameter.Value = value; }
76    }
77    public IRandom Random {
78      get { return RandomParameter.ActualValue; }
79      set { RandomParameter.ActualValue = value; }
80    }
81    private IItem Target {
82      get { return TargetParameter.ActualValue; }
83    }
84    #endregion
85
86    [StorableConstructor]
87    private TravelingSalesmanImprovementOperator(bool deserializing) : base(deserializing) { }
88    private TravelingSalesmanImprovementOperator(TravelingSalesmanImprovementOperator original, Cloner cloner) : base(original, cloner) { }
89    public TravelingSalesmanImprovementOperator()
90      : base() {
91      #region Create parameters
92      Parameters.Add(new ScopeParameter("CurrentScope"));
93      Parameters.Add(new LookupParameter<DistanceMatrix>("DistanceMatrix"));
94      Parameters.Add(new LookupParameter<IEvaluator>("Evaluator"));
95      Parameters.Add(new ValueParameter<IntValue>("ImprovementAttempts", new IntValue(100)));
96      Parameters.Add(new LookupParameter<IRandom>("Random"));
97      Parameters.Add(new ValueLookupParameter<IItem>("Target"));
98      #endregion
99      TargetParameter.ActualName = "TSPTour"; // temporary solution for the traveling salesman problem
100    }
101
102    public override IDeepCloneable Clone(Cloner cloner) {
103      return new TravelingSalesmanImprovementOperator(this, cloner);
104    }
105
106    public override IOperation Apply() {
107      Permutation currSol = CurrentScope.Variables[TargetParameter.ActualName].Value as Permutation;
108      if (currSol.PermutationType != PermutationTypes.RelativeUndirected)
109        throw new ArgumentException("Cannot improve solution because the permutation type is not supported.");
110
111      for (int i = 0; i < ImprovementAttempts.Value; i++) {
112        int a = Random.Next(currSol.Length);
113        int b = Random.Next(currSol.Length);
114        double oldFirstEdgeLength = DistanceMatrix[currSol[a], currSol[(a - 1 + currSol.Length) % currSol.Length]];
115        double oldSecondEdgeLength = DistanceMatrix[currSol[b], currSol[(b + 1) % currSol.Length]];
116        double newFirstEdgeLength = DistanceMatrix[currSol[b], currSol[(a - 1 + currSol.Length) % currSol.Length]];
117        double newSecondEdgeLength = DistanceMatrix[currSol[a], currSol[(b + 1 + currSol.Length) % currSol.Length]];
118        if (newFirstEdgeLength + newSecondEdgeLength < oldFirstEdgeLength + oldSecondEdgeLength)
119          Invert(currSol, a, b);
120      }
121
122      return base.Apply();
123    }
124
125    private void Invert(Permutation sol, int i, int j) {
126      if (i != j)
127        for (int a = 0; a < Math.Abs(i - j) / 2; a++)
128          if (sol[(i + a) % sol.Length] != sol[(j - a + sol.Length) % sol.Length]) {
129            // XOR swap
130            sol[(i + a) % sol.Length] ^= sol[(j - a + sol.Length) % sol.Length];
131            sol[(j - a + sol.Length) % sol.Length] ^= sol[(i + a) % sol.Length];
132            sol[(i + a) % sol.Length] ^= sol[(j - a + sol.Length) % sol.Length];
133          }
134    }
135  }
136}
Note: See TracBrowser for help on using the repository browser.