Free cookie consent management tool by TermsFeed Policy Generator

Changeset 14454 for branches


Ignore:
Timestamp:
12/05/16 16:06:18 (7 years ago)
Author:
abeham
Message:

#2701:

  • Worked on MemPR algorithm for permutations
  • Refactored TSP
Location:
branches/MemPRAlgorithm
Files:
1 added
9 deleted
12 edited
1 copied

Legend:

Unmodified
Added
Removed
  • branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/MemPRAlgorithm.cs

    r14453 r14454  
    557557        || Context.Population.Any(p => IsBetter(offspring, p))) return offspring;
    558558
    559       if (HillclimbingSuited(offspring))
     559      if (IsBetter(offspring.Fitness, Context.BestQuality))
     560        HillClimb(offspring, token); // perform hillclimb in full solution space
     561      else if (HillclimbingSuited(offspring))
    560562        HillClimb(offspring, token, subspace); // perform hillclimb in the solution sub-space
    561563      return offspring;
     
    587589      if (dist1 > 0 && dist2 > 0) {
    588590        var subspace = CalculateSubspace(new[] { a.Solution, b.Solution }, inverse: true);
    589         if (HillclimbingSuited(child)) {
    590           HillClimb(child, token, subspace);
     591        if (IsBetter(child.Fitness, Context.BestQuality))
     592          HillClimb(child, token); // perform hillclimb in full solution space
     593        else if (HillclimbingSuited(child)) {
     594          HillClimb(child, token, subspace); // perform hillclimb in solution sub-space
    591595        }
    592596      }
  • branches/MemPRAlgorithm/HeuristicLab.Problems.TravelingSalesman.Views/3.3/HeuristicLab.Problems.TravelingSalesman.Views-3.3.csproj

    r11623 r14454  
    230230    </ProjectReference>
    231231  </ItemGroup>
     232  <ItemGroup>
     233    <EmbeddedResource Include="TravelingSalesmanProblemView.resx">
     234      <DependentUpon>TravelingSalesmanProblemView.cs</DependentUpon>
     235    </EmbeddedResource>
     236  </ItemGroup>
    232237  <Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" />
    233238  <!-- To modify your build process, add your task inside one of the targets below and uncomment it.
  • branches/MemPRAlgorithm/HeuristicLab.Problems.TravelingSalesman.Views/3.3/TravelingSalesmanProblemView.Designer.cs

    r14185 r14454  
    4545      this.visualizationTabPage = new System.Windows.Forms.TabPage();
    4646      this.pathTSPTourView = new HeuristicLab.Problems.TravelingSalesman.Views.PathTSPTourView();
     47      this.updateDistanceMatrixButton = new System.Windows.Forms.Button();
    4748      ((System.ComponentModel.ISupportInitialize)(this.problemInstanceSplitContainer)).BeginInit();
    4849      this.problemInstanceSplitContainer.Panel1.SuspendLayout();
     
    6061      // problemInstanceSplitContainer.Panel2
    6162      //
     63      this.problemInstanceSplitContainer.Panel2.Controls.Add(this.updateDistanceMatrixButton);
    6264      this.problemInstanceSplitContainer.Panel2.Controls.Add(this.tabControl);
    6365      //
     
    6769      this.parameterCollectionView.Dock = System.Windows.Forms.DockStyle.Fill;
    6870      this.parameterCollectionView.Location = new System.Drawing.Point(3, 3);
    69       this.parameterCollectionView.Size = new System.Drawing.Size(497, 274);
     71      this.parameterCollectionView.Size = new System.Drawing.Size(497, 245);
    7072      //
    7173      // nameTextBox
     
    7779      //
    7880      this.tabControl.AllowDrop = true;
    79       this.tabControl.Anchor = ((System.Windows.Forms.AnchorStyles)((((System.Windows.Forms.AnchorStyles.Top | System.Windows.Forms.AnchorStyles.Bottom)
    80                   | System.Windows.Forms.AnchorStyles.Left)
    81                   | System.Windows.Forms.AnchorStyles.Right)));
     81      this.tabControl.Anchor = ((System.Windows.Forms.AnchorStyles)((((System.Windows.Forms.AnchorStyles.Top | System.Windows.Forms.AnchorStyles.Bottom) 
     82            | System.Windows.Forms.AnchorStyles.Left)
     83            | System.Windows.Forms.AnchorStyles.Right)));
    8284      this.tabControl.Controls.Add(this.parametersTabPage);
    8385      this.tabControl.Controls.Add(this.visualizationTabPage);
    84       this.tabControl.Location = new System.Drawing.Point(0, 27);
     86      this.tabControl.Location = new System.Drawing.Point(0, 56);
    8587      this.tabControl.Name = "tabControl";
    8688      this.tabControl.SelectedIndex = 0;
    87       this.tabControl.Size = new System.Drawing.Size(511, 306);
     89      this.tabControl.Size = new System.Drawing.Size(511, 277);
    8890      this.tabControl.TabIndex = 4;
    8991      //
     
    9496      this.parametersTabPage.Name = "parametersTabPage";
    9597      this.parametersTabPage.Padding = new System.Windows.Forms.Padding(3);
    96       this.parametersTabPage.Size = new System.Drawing.Size(503, 280);
     98      this.parametersTabPage.Size = new System.Drawing.Size(503, 251);
    9799      this.parametersTabPage.TabIndex = 0;
    98100      this.parametersTabPage.Text = "Parameters";
     
    112114      // pathTSPTourView
    113115      //
    114       this.pathTSPTourView.Anchor = ((System.Windows.Forms.AnchorStyles)((((System.Windows.Forms.AnchorStyles.Top | System.Windows.Forms.AnchorStyles.Bottom)
    115                   | System.Windows.Forms.AnchorStyles.Left)
    116                   | System.Windows.Forms.AnchorStyles.Right)));
     116      this.pathTSPTourView.Anchor = ((System.Windows.Forms.AnchorStyles)((((System.Windows.Forms.AnchorStyles.Top | System.Windows.Forms.AnchorStyles.Bottom) 
     117            | System.Windows.Forms.AnchorStyles.Left)
     118            | System.Windows.Forms.AnchorStyles.Right)));
    117119      this.pathTSPTourView.Caption = "PathTSPTour View";
    118120      this.pathTSPTourView.Content = null;
     
    123125      this.pathTSPTourView.TabIndex = 0;
    124126      //
     127      // updateDistanceMatrixButton
     128      //
     129      this.updateDistanceMatrixButton.Location = new System.Drawing.Point(3, 27);
     130      this.updateDistanceMatrixButton.Name = "updateDistanceMatrixButton";
     131      this.updateDistanceMatrixButton.Size = new System.Drawing.Size(133, 23);
     132      this.updateDistanceMatrixButton.TabIndex = 5;
     133      this.updateDistanceMatrixButton.Text = "Update Distance Matrix";
     134      this.updateDistanceMatrixButton.UseVisualStyleBackColor = true;
     135      this.updateDistanceMatrixButton.Click += new System.EventHandler(this.updateDistanceMatrixButton_Click);
     136      //
    125137      // TravelingSalesmanProblemView
    126138      //
    127       this.AutoScaleDimensions = new System.Drawing.SizeF(6F, 13F);
    128139      this.AutoScaleMode = System.Windows.Forms.AutoScaleMode.Inherit;
    129140      this.Name = "TravelingSalesmanProblemView";
     
    148159    private System.Windows.Forms.TabPage visualizationTabPage;
    149160    private PathTSPTourView pathTSPTourView;
     161    private System.Windows.Forms.Button updateDistanceMatrixButton;
    150162  }
    151163}
  • branches/MemPRAlgorithm/HeuristicLab.Problems.TravelingSalesman.Views/3.3/TravelingSalesmanProblemView.cs

    r14185 r14454  
    2222using System;
    2323using System.Windows.Forms;
     24using HeuristicLab.Data;
    2425using HeuristicLab.MainForm;
    2526using HeuristicLab.Optimization.Views;
     
    4647    protected override void DeregisterContentEvents() {
    4748      Content.CoordinatesParameter.ValueChanged -= new EventHandler(CoordinatesParameter_ValueChanged);
    48       Content.BestKnownQualityParameter.ValueChanged -= new EventHandler(BestKnownQualityParameter_ValueChanged);
     49      //Content.BestKnownQualityParameter.ValueChanged -= new EventHandler(BestKnownQualityParameter_ValueChanged);
    4950      Content.BestKnownSolutionParameter.ValueChanged -= new EventHandler(BestKnownSolutionParameter_ValueChanged);
    5051      base.DeregisterContentEvents();
     
    5354      base.RegisterContentEvents();
    5455      Content.CoordinatesParameter.ValueChanged += new EventHandler(CoordinatesParameter_ValueChanged);
    55       Content.BestKnownQualityParameter.ValueChanged += new EventHandler(BestKnownQualityParameter_ValueChanged);
     56      //Content.BestKnownQualityParameter.ValueChanged += new EventHandler(BestKnownQualityParameter_ValueChanged);
    5657      Content.BestKnownSolutionParameter.ValueChanged += new EventHandler(BestKnownSolutionParameter_ValueChanged);
    5758    }
     
    6263        pathTSPTourView.Content = null;
    6364      } else {
    64         pathTSPTourView.Content = new PathTSPTour(Content.Coordinates, Content.BestKnownSolution, Content.BestKnownQuality);
     65        pathTSPTourView.Content = new PathTSPTour(Content.Coordinates, Content.BestKnownSolution, new DoubleValue(Content.BestKnownQuality));
    6566      }
    6667    }
     
    6970      base.SetEnabledStateOfControls();
    7071      pathTSPTourView.Enabled = Content != null;
     72      updateDistanceMatrixButton.Enabled = Content != null && !ReadOnly && !Locked;
    7173    }
    7274
     
    7577    }
    7678    private void BestKnownQualityParameter_ValueChanged(object sender, EventArgs e) {
    77       pathTSPTourView.Content.Quality = Content.BestKnownQuality;
     79      pathTSPTourView.Content.Quality = new DoubleValue(Content.BestKnownQuality);
    7880    }
    7981    private void BestKnownSolutionParameter_ValueChanged(object sender, EventArgs e) {
    8082      pathTSPTourView.Content.Permutation = Content.BestKnownSolution;
    8183    }
     84
     85    private void updateDistanceMatrixButton_Click(object sender, EventArgs e) {
     86      Content.UpdateDistanceMatrix();
     87    }
    8288  }
    8389}
  • branches/MemPRAlgorithm/HeuristicLab.Problems.TravelingSalesman/3.3/DistanceMatrix.cs

    r14185 r14454  
    4444    public DistanceMatrix(int rows, int columns, IEnumerable<string> columnNames, IEnumerable<string> rowNames) : base(rows, columns, columnNames, rowNames) { }
    4545    public DistanceMatrix(double[,] elements) : base(elements) { }
     46    public DistanceMatrix(double[,] elements, bool readOnly) : base(elements) {
     47      this.readOnly = readOnly;
     48    }
    4649    public DistanceMatrix(double[,] elements, IEnumerable<string> columnNames) : base(elements, columnNames) { }
    4750    public DistanceMatrix(double[,] elements, IEnumerable<string> columnNames, IEnumerable<string> rowNames) : base(elements, columnNames, rowNames) { }
  • branches/MemPRAlgorithm/HeuristicLab.Problems.TravelingSalesman/3.3/HeuristicLab.Problems.TravelingSalesman-3.3.csproj

    r12978 r14454  
    122122    <Compile Include="Analyzers\TSPAlleleFrequencyAnalyzer.cs" />
    123123    <Compile Include="DistanceMatrix.cs" />
    124     <Compile Include="Evaluators\TSPDistanceMatrixEvaluator.cs" />
    125     <Compile Include="Evaluators\TSPEuclideanPathEvaluator.cs" />
    126     <Compile Include="Evaluators\TSPGeoPathEvaluator.cs" />
    127     <Compile Include="Evaluators\TSPUpperEuclideanPathEvaluator.cs" />
    128124    <Compile Include="Improvers\TSPImprovementOperator.cs" />
    129125    <Compile Include="Interfaces\ITSPDistanceMatrixEvaluator.cs" />
    130     <Compile Include="MoveEvaluators\ThreeOpt\TSPTranslocationMoveDistanceMatrixEvaluator.cs" />
    131     <Compile Include="MoveEvaluators\ThreeOpt\TSPTranslocationMoveEuclideanPathEvaluator.cs" />
    132     <Compile Include="MoveEvaluators\ThreeOpt\TSPTranslocationMoveGeoPathEvaluator.cs" />
    133126    <Compile Include="MoveEvaluators\ThreeOpt\TSPTranslocationMovePathEvaluator.cs" />
    134     <Compile Include="MoveEvaluators\ThreeOpt\TSPTranslocationMoveRoundedEuclideanPathEvaluator.cs" />
    135     <Compile Include="MoveEvaluators\TwoOpt\TSPInversionMoveEuclideanPathEvaluator.cs" />
    136     <Compile Include="MoveEvaluators\TwoOpt\TSPInversionMoveGeoPathEvaluator.cs" />
    137     <Compile Include="MoveEvaluators\TwoOpt\TSPInversionMoveDistanceMatrixEvaluator.cs" />
    138127    <Compile Include="MoveEvaluators\TwoOpt\TSPInversionMovePathEvaluator.cs" />
    139     <Compile Include="MoveEvaluators\TwoOpt\TSPInversionMoveRoundedEuclideanPathEvaluator.cs" />
    140128    <Compile Include="PathRelinkers\TSPMultipleGuidesPathRelinker.cs" />
    141129    <Compile Include="PathRelinkers\TSPPathRelinker.cs" />
     
    145133    <Compile Include="TravelingSalesmanProblem.cs" />
    146134    <Compile Include="PathTSPTour.cs" />
    147     <Compile Include="Evaluators\TSPCoordinatesPathEvaluator.cs" />
    148     <Compile Include="Evaluators\TSPEvaluator.cs" />
    149     <Compile Include="Evaluators\TSPRoundedEuclideanPathEvaluator.cs" />
    150135    <Compile Include="Interfaces\ITSPCoordinatesPathEvaluator.cs" />
    151136    <Compile Include="Interfaces\ITSPEvaluator.cs" />
  • branches/MemPRAlgorithm/HeuristicLab.Problems.TravelingSalesman/3.3/Interfaces/ITSPMoveEvaluator.cs

    r14185 r14454  
    2424
    2525namespace HeuristicLab.Problems.TravelingSalesman {
    26   public interface ITSPMoveEvaluator : ISingleObjectiveMoveEvaluator, IMoveOperator {
    27     Type EvaluatorType { get; }
    28   }
     26  public interface ITSPMoveEvaluator : ISingleObjectiveMoveEvaluator, IMoveOperator { }
    2927}
  • branches/MemPRAlgorithm/HeuristicLab.Problems.TravelingSalesman/3.3/Interfaces/ITSPPathMoveEvaluator.cs

    r14185 r14454  
    2626namespace HeuristicLab.Problems.TravelingSalesman {
    2727  public interface ITSPPathMoveEvaluator : ITSPMoveEvaluator, IPermutationMoveOperator {
     28    ILookupParameter<EnumValue<TSPDistanceFunction>> DistanceFunctionParameter { get; }
    2829    ILookupParameter<DoubleMatrix> CoordinatesParameter { get; }
    2930    ILookupParameter<DistanceMatrix> DistanceMatrixParameter { get; }
  • branches/MemPRAlgorithm/HeuristicLab.Problems.TravelingSalesman/3.3/MoveEvaluators/TSPMoveEvaluator.cs

    r14185 r14454  
    3636  [StorableClass]
    3737  public abstract class TSPMoveEvaluator : SingleSuccessorOperator, ITSPMoveEvaluator, IMoveOperator {
    38 
    39     public abstract Type EvaluatorType { get; }
     38   
    4039    public override bool CanChangeName {
    4140      get { return false; }
  • branches/MemPRAlgorithm/HeuristicLab.Problems.TravelingSalesman/3.3/MoveEvaluators/TSPPathMoveEvaluator.cs

    r14185 r14454  
    4747      get { return (ILookupParameter<BoolValue>)Parameters["UseDistanceMatrix"]; }
    4848    }
     49    public ILookupParameter<EnumValue<TSPDistanceFunction>> DistanceFunctionParameter {
     50      get { return (ILookupParameter<EnumValue<TSPDistanceFunction>>)Parameters["DistanceFunction"]; }
     51    }
    4952
    5053    [StorableConstructor]
     
    5760      Parameters.Add(new LookupParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
    5861      Parameters.Add(new LookupParameter<BoolValue>("UseDistanceMatrix", "True if a distance matrix should be calculated (if it does not exist already) and used for evaluation, otherwise false."));
    59     }
    60 
    61     [StorableHook(HookType.AfterDeserialization)]
    62     private void AfterDeserialization() {
    63       // BackwardsCompatibility3.3
    64       #region Backwards compatible code (remove with 3.4)
    65       LookupParameter<DoubleMatrix> oldDistanceMatrixParameter = Parameters["DistanceMatrix"] as LookupParameter<DoubleMatrix>;
    66       if (oldDistanceMatrixParameter != null) {
    67         Parameters.Remove(oldDistanceMatrixParameter);
    68         Parameters.Add(new LookupParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
    69         DistanceMatrixParameter.ActualName = oldDistanceMatrixParameter.ActualName;
    70       }
    71       #endregion
     62      Parameters.Add(new LookupParameter<EnumValue<TSPDistanceFunction>>("DistanceFunction", "The distance function to use when the distance matrix is not being used."));
    7263    }
    7364
    7465    public override IOperation Apply() {
    75       Permutation permutation = PermutationParameter.ActualValue;
    76       DoubleMatrix coordinates = CoordinatesParameter.ActualValue;
     66      var permutation = PermutationParameter.ActualValue;
     67      var coordinates = CoordinatesParameter.ActualValue;
     68      var distanceFunction = DistanceFunctionParameter.ActualValue.Value;
    7769      double relativeQualityDifference = 0;
    7870      if (UseDistanceMatrixParameter.ActualValue.Value) {
    7971        DistanceMatrix distanceMatrix = DistanceMatrixParameter.ActualValue;
    8072        if (distanceMatrix == null) {
    81           if (coordinates == null) throw new InvalidOperationException("Neither a distance matrix nor coordinates were given.");
    82           distanceMatrix = CalculateDistanceMatrix(coordinates);
    83           DistanceMatrixParameter.ActualValue = distanceMatrix;
     73          throw new InvalidOperationException("Distance matrix is not given.");
    8474        }
    8575        relativeQualityDifference = EvaluateByDistanceMatrix(permutation, distanceMatrix);
    8676      } else {
    8777        if (coordinates == null) throw new InvalidOperationException("No coordinates were given.");
    88         relativeQualityDifference = EvaluateByCoordinates(permutation, coordinates);
     78        relativeQualityDifference = EvaluateByCoordinates(permutation, coordinates, distanceFunction);
    8979      }
    9080      DoubleValue moveQuality = MoveQualityParameter.ActualValue;
     
    9383      return base.Apply();
    9484    }
    95 
    96     protected abstract double CalculateDistance(double x1, double y1, double x2, double y2);
    9785    protected abstract double EvaluateByDistanceMatrix(Permutation permutation, DistanceMatrix distanceMatrix);
    98     protected abstract double EvaluateByCoordinates(Permutation permutation, DoubleMatrix coordinates);
    99 
    100     private DistanceMatrix CalculateDistanceMatrix(DoubleMatrix c) {
    101       DistanceMatrix distanceMatrix = new DistanceMatrix(c.Rows, c.Rows);
    102       for (int i = 0; i < distanceMatrix.Rows; i++) {
    103         for (int j = 0; j < distanceMatrix.Columns; j++)
    104           distanceMatrix[i, j] = CalculateDistance(c[i, 0], c[i, 1], c[j, 0], c[j, 1]);
    105       }
    106       return (DistanceMatrix)distanceMatrix.AsReadOnly();
    107     }
     86    protected abstract double EvaluateByCoordinates(Permutation permutation, DoubleMatrix coordinates, TSPDistanceFunction distanceFunction);
    10887  }
    10988}
  • branches/MemPRAlgorithm/HeuristicLab.Problems.TravelingSalesman/3.3/MoveEvaluators/ThreeOpt/TSPTranslocationMovePathEvaluator.cs

    r14185 r14454  
    4646    }
    4747
    48     public static double EvaluateByCoordinates(Permutation permutation, TranslocationMove move, DoubleMatrix coordinates, TSPTranslocationMovePathEvaluator evaluator) {
     48    public static double EvaluateByCoordinates(Permutation permutation, TranslocationMove move, DoubleMatrix coordinates, TSPDistanceFunction distanceFunction) {
    4949      if (move.Index1 == move.Index3
    5050        || move.Index2 == permutation.Length - 1 && move.Index3 == 0
     
    6565      double moveQuality = 0;
    6666      // remove three edges
    67       moveQuality -= evaluator.CalculateDistance(coordinates[edge1source, 0], coordinates[edge1source, 1],
     67      moveQuality -= TravelingSalesmanProblem.CalculateDistance(distanceFunction, coordinates[edge1source, 0], coordinates[edge1source, 1],
    6868        coordinates[edge1target, 0], coordinates[edge1target, 1]);
    69       moveQuality -= evaluator.CalculateDistance(coordinates[edge2source, 0], coordinates[edge2source, 1],
     69      moveQuality -= TravelingSalesmanProblem.CalculateDistance(distanceFunction, coordinates[edge2source, 0], coordinates[edge2source, 1],
    7070        coordinates[edge2target, 0], coordinates[edge2target, 1]);
    71       moveQuality -= evaluator.CalculateDistance(coordinates[edge3source, 0], coordinates[edge3source, 1],
     71      moveQuality -= TravelingSalesmanProblem.CalculateDistance(distanceFunction, coordinates[edge3source, 0], coordinates[edge3source, 1],
    7272        coordinates[edge3target, 0], coordinates[edge3target, 1]);
    7373      // add three edges
    74       moveQuality += evaluator.CalculateDistance(coordinates[edge3source, 0], coordinates[edge3source, 1],
     74      moveQuality += TravelingSalesmanProblem.CalculateDistance(distanceFunction, coordinates[edge3source, 0], coordinates[edge3source, 1],
    7575        coordinates[edge1target, 0], coordinates[edge1target, 1]);
    76       moveQuality += evaluator.CalculateDistance(coordinates[edge2source, 0], coordinates[edge2source, 1],
     76      moveQuality += TravelingSalesmanProblem.CalculateDistance(distanceFunction, coordinates[edge2source, 0], coordinates[edge2source, 1],
    7777        coordinates[edge3target, 0], coordinates[edge3target, 1]);
    78       moveQuality += evaluator.CalculateDistance(coordinates[edge1source, 0], coordinates[edge1source, 1],
     78      moveQuality += TravelingSalesmanProblem.CalculateDistance(distanceFunction, coordinates[edge1source, 0], coordinates[edge1source, 1],
    7979        coordinates[edge2target, 0], coordinates[edge2target, 1]);
    8080      return moveQuality;
     
    110110    }
    111111
    112     protected override double EvaluateByCoordinates(Permutation permutation, DoubleMatrix coordinates) {
    113       return EvaluateByCoordinates(permutation, TranslocationMoveParameter.ActualValue, coordinates, this);
     112    protected override double EvaluateByCoordinates(Permutation permutation, DoubleMatrix coordinates, TSPDistanceFunction distanceFunction) {
     113      return EvaluateByCoordinates(permutation, TranslocationMoveParameter.ActualValue, coordinates, distanceFunction);
    114114    }
    115115
  • branches/MemPRAlgorithm/HeuristicLab.Problems.TravelingSalesman/3.3/MoveEvaluators/TwoOpt/TSPInversionMovePathEvaluator.cs

    r14185 r14454  
    3333  [Item("TSPInversionMovePathEvaluator", "Evaluates an inversion move (2-opt) by summing up the length of all added edges and subtracting the length of all deleted edges.")]
    3434  [StorableClass]
    35   public abstract class TSPInversionMovePathEvaluator : TSPPathMoveEvaluator, IPermutationInversionMoveOperator {
     35  public class TSPInversionMovePathEvaluator : TSPPathMoveEvaluator, IPermutationInversionMoveOperator {
    3636    public ILookupParameter<InversionMove> InversionMoveParameter {
    3737      get { return (ILookupParameter<InversionMove>)Parameters["InversionMove"]; }
     
    4646    }
    4747
    48     public static double EvaluateByCoordinates(Permutation permutation, InversionMove move, DoubleMatrix coordinates, TSPInversionMovePathEvaluator evaluator) {
     48    public override IDeepCloneable Clone(Cloner cloner) {
     49      return new TSPInversionMovePathEvaluator(this, cloner);
     50    }
     51
     52    public static double EvaluateByCoordinates(Permutation permutation, InversionMove move, DoubleMatrix coordinates, TSPDistanceFunction distanceFunction) {
    4953      int edge1source = permutation.GetCircular(move.Index1 - 1);
    5054      int edge1target = permutation[move.Index1];
     
    5458      double moveQuality = 0;
    5559      // remove two edges
    56       moveQuality -= evaluator.CalculateDistance(coordinates[edge1source, 0], coordinates[edge1source, 1],
     60      moveQuality -= TravelingSalesmanProblem.CalculateDistance(distanceFunction, coordinates[edge1source, 0], coordinates[edge1source, 1],
    5761            coordinates[edge1target, 0], coordinates[edge1target, 1]);
    58       moveQuality -= evaluator.CalculateDistance(coordinates[edge2source, 0], coordinates[edge2source, 1],
     62      moveQuality -= TravelingSalesmanProblem.CalculateDistance(distanceFunction, coordinates[edge2source, 0], coordinates[edge2source, 1],
    5963        coordinates[edge2target, 0], coordinates[edge2target, 1]);
    6064      // add two edges
    61       moveQuality += evaluator.CalculateDistance(coordinates[edge1source, 0], coordinates[edge1source, 1],
     65      moveQuality += TravelingSalesmanProblem.CalculateDistance(distanceFunction, coordinates[edge1source, 0], coordinates[edge1source, 1],
    6266        coordinates[edge2source, 0], coordinates[edge2source, 1]);
    63       moveQuality += evaluator.CalculateDistance(coordinates[edge1target, 0], coordinates[edge1target, 1],
     67      moveQuality += TravelingSalesmanProblem.CalculateDistance(distanceFunction, coordinates[edge1target, 0], coordinates[edge1target, 1],
    6468        coordinates[edge2target, 0], coordinates[edge2target, 1]);
    6569      return moveQuality;
     
    8286    }
    8387
    84     protected override double EvaluateByCoordinates(Permutation permutation, DoubleMatrix coordinates) {
    85       return EvaluateByCoordinates(permutation, InversionMoveParameter.ActualValue, coordinates, this);
     88    protected override double EvaluateByCoordinates(Permutation permutation, DoubleMatrix coordinates, TSPDistanceFunction distanceFunction) {
     89      return EvaluateByCoordinates(permutation, InversionMoveParameter.ActualValue, coordinates, distanceFunction);
    8690    }
    8791
  • branches/MemPRAlgorithm/HeuristicLab.Problems.TravelingSalesman/3.3/TravelingSalesmanProblem.cs

    r14453 r14454  
    2121
    2222using System;
    23 using System.Collections.Generic;
    2423using System.IO;
    2524using System.Linq;
     
    3736
    3837namespace HeuristicLab.Problems.TravelingSalesman {
     38  public enum TSPDistanceFunction { Euclidean, RoundedEuclidean, UpperEuclidean, Geo, DistanceMatrix };
     39
    3940  [Item("Traveling Salesman Problem (TSP)", "Represents a symmetric Traveling Salesman Problem.")]
    40   [Creatable(CreatableAttribute.Categories.CombinatorialProblems, Priority = 100)]
     41  [Creatable(CreatableAttribute.Categories.CombinatorialProblems, Priority = 999)]
    4142  [StorableClass]
    42   public sealed class TravelingSalesmanProblem : SingleObjectiveHeuristicOptimizationProblem<ITSPEvaluator, IPermutationCreator>, IStorableContent,
    43     IProblemInstanceConsumer<TSPData> {
     43  public sealed class TravelingSalesmanProblem : SingleObjectiveBasicProblem<PermutationEncoding>, IStorableContent, IProblemInstanceConsumer<TSPData> {
     44    public const double PI = 3.141592;
     45    public const double RADIUS = 6378.388;
    4446    private static readonly int DistanceMatrixSizeLimit = 1000;
    45     public string Filename { get; set; }
     47
     48    public override bool Maximization {
     49      get { return false; }
     50    }
    4651
    4752    #region Parameter Properties
     53    [Storable]
     54    private IFixedValueParameter<EnumValue<TSPDistanceFunction>> distanceFunctionParameter;
     55    public IFixedValueParameter<EnumValue<TSPDistanceFunction>> DistanceFunctionParameter {
     56      get { return distanceFunctionParameter; }
     57    }
     58    [Storable]
     59    private OptionalValueParameter<DoubleMatrix> coordinatesParameter;
    4860    public OptionalValueParameter<DoubleMatrix> CoordinatesParameter {
    49       get { return (OptionalValueParameter<DoubleMatrix>)Parameters["Coordinates"]; }
    50     }
     61      get { return coordinatesParameter; }
     62    }
     63    [Storable]
     64    private OptionalValueParameter<DistanceMatrix> distanceMatrixParameter;
    5165    public OptionalValueParameter<DistanceMatrix> DistanceMatrixParameter {
    52       get { return (OptionalValueParameter<DistanceMatrix>)Parameters["DistanceMatrix"]; }
    53     }
    54     public ValueParameter<BoolValue> UseDistanceMatrixParameter {
    55       get { return (ValueParameter<BoolValue>)Parameters["UseDistanceMatrix"]; }
    56     }
     66      get { return distanceMatrixParameter; }
     67    }
     68    [Storable]
     69    private IFixedValueParameter<BoolValue> useDistanceMatrixParameter;
     70    public IFixedValueParameter<BoolValue> UseDistanceMatrixParameter {
     71      get { return useDistanceMatrixParameter; }
     72    }
     73    [Storable]
     74    private OptionalValueParameter<Permutation> bestKnownSolutionParameter;
    5775    public OptionalValueParameter<Permutation> BestKnownSolutionParameter {
    58       get { return (OptionalValueParameter<Permutation>)Parameters["BestKnownSolution"]; }
     76      get { return bestKnownSolutionParameter; }
    5977    }
    6078    #endregion
    6179
    6280    #region Properties
     81    public TSPDistanceFunction DistanceFunction {
     82      get { return distanceFunctionParameter.Value.Value; }
     83      set { distanceFunctionParameter.Value.Value = value; }
     84    }
    6385    public DoubleMatrix Coordinates {
    64       get { return CoordinatesParameter.Value; }
    65       set { CoordinatesParameter.Value = value; }
     86      get { return coordinatesParameter.Value; }
     87      set { coordinatesParameter.Value = value; }
    6688    }
    6789    public DistanceMatrix DistanceMatrix {
    68       get { return DistanceMatrixParameter.Value; }
    69       set { DistanceMatrixParameter.Value = value; }
    70     }
    71     public BoolValue UseDistanceMatrix {
    72       get { return UseDistanceMatrixParameter.Value; }
    73       set { UseDistanceMatrixParameter.Value = value; }
     90      get { return distanceMatrixParameter.Value; }
     91      set { distanceMatrixParameter.Value = value; }
     92    }
     93    public bool UseDistanceMatrix {
     94      get { return useDistanceMatrixParameter.Value.Value; }
     95      set { useDistanceMatrixParameter.Value.Value = value; }
    7496    }
    7597    public Permutation BestKnownSolution {
    76       get { return BestKnownSolutionParameter.Value; }
    77       set { BestKnownSolutionParameter.Value = value; }
     98      get { return bestKnownSolutionParameter.Value; }
     99      set { bestKnownSolutionParameter.Value = value; }
    78100    }
    79101    private BestTSPSolutionAnalyzer BestTSPSolutionAnalyzer {
     
    82104    private TSPAlleleFrequencyAnalyzer TSPAlleleFrequencyAnalyzer {
    83105      get { return Operators.OfType<TSPAlleleFrequencyAnalyzer>().FirstOrDefault(); }
    84     }
    85     #endregion
    86 
    87     // BackwardsCompatibility3.3
    88     #region Backwards compatible code, remove with 3.4
    89     [Obsolete]
    90     [Storable(Name = "operators")]
    91     private IEnumerable<IOperator> oldOperators {
    92       get { return null; }
    93       set {
    94         if (value != null && value.Any())
    95           Operators.AddRange(value);
    96       }
    97106    }
    98107    #endregion
     
    102111    private TravelingSalesmanProblem(TravelingSalesmanProblem original, Cloner cloner)
    103112      : base(original, cloner) {
     113      distanceFunctionParameter = cloner.Clone(original.distanceFunctionParameter);
     114      coordinatesParameter = cloner.Clone(original.coordinatesParameter);
     115      distanceMatrixParameter = cloner.Clone(original.distanceMatrixParameter);
     116      useDistanceMatrixParameter = cloner.Clone(original.useDistanceMatrixParameter);
     117      bestKnownSolutionParameter = cloner.Clone(original.bestKnownSolutionParameter);
    104118      RegisterEventHandlers();
    105119    }
     
    107121      return new TravelingSalesmanProblem(this, cloner);
    108122    }
    109     public TravelingSalesmanProblem()
    110       : base(new TSPRoundedEuclideanPathEvaluator(), new RandomPermutationCreator()) {
    111       Parameters.Add(new OptionalValueParameter<DoubleMatrix>("Coordinates", "The x- and y-Coordinates of the cities."));
    112       Parameters.Add(new OptionalValueParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
    113       Parameters.Add(new ValueParameter<BoolValue>("UseDistanceMatrix", "True if the coordinates based evaluators should calculate the distance matrix from the coordinates and use it for evaluation similar to the distance matrix evaluator, otherwise false.", new BoolValue(true)));
    114       Parameters.Add(new OptionalValueParameter<Permutation>("BestKnownSolution", "The best known solution of this TSP instance."));
    115 
    116       Maximization.Value = false;
    117       MaximizationParameter.Hidden = true;
    118       UseDistanceMatrixParameter.Hidden = true;
    119       DistanceMatrixParameter.ReactOnValueToStringChangedAndValueItemImageChanged = false;
     123    public TravelingSalesmanProblem() : base() {
     124      Encoding = new PermutationEncoding("TSPTour") { Length = 16 };
     125
     126      Parameters.Add(distanceFunctionParameter = new FixedValueParameter<EnumValue<TSPDistanceFunction>>("DistanceFunction", "The distance function that is used to calculate distance among the coordinates.", new EnumValue<TSPDistanceFunction>(TSPDistanceFunction.RoundedEuclidean)));
     127      Parameters.Add(coordinatesParameter = new OptionalValueParameter<DoubleMatrix>("Coordinates", "The x- and y-Coordinates of the cities."));
     128      Parameters.Add(distanceMatrixParameter = new OptionalValueParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
     129      Parameters.Add(useDistanceMatrixParameter = new FixedValueParameter<BoolValue>("UseDistanceMatrix", "True if the coordinates based evaluators should calculate the distance matrix from the coordinates and use it for evaluation similar to the distance matrix evaluator, otherwise false.", new BoolValue(true)));
     130      Parameters.Add(bestKnownSolutionParameter = new OptionalValueParameter<Permutation>("BestKnownSolution", "The best known solution of this TSP instance."));
     131     
     132      useDistanceMatrixParameter.Hidden = true;
     133      distanceMatrixParameter.ReactOnValueToStringChangedAndValueItemImageChanged = false;
    120134
    121135      Coordinates = new DoubleMatrix(new double[,] {
     
    125139        { 400, 100 }, { 400, 200 }, { 400, 300 }, { 400, 400 }
    126140      });
    127 
    128       SolutionCreator.PermutationParameter.ActualName = "TSPTour";
     141     
    129142      Evaluator.QualityParameter.ActualName = "TSPTourLength";
    130       ParameterizeSolutionCreator();
    131       ParameterizeEvaluator();
    132143
    133144      InitializeOperators();
    134145      RegisterEventHandlers();
    135146    }
    136 
    137     #region Events
    138     protected override void OnSolutionCreatorChanged() {
    139       base.OnSolutionCreatorChanged();
    140       SolutionCreator.PermutationParameter.ActualNameChanged += new EventHandler(SolutionCreator_PermutationParameter_ActualNameChanged);
    141       ParameterizeSolutionCreator();
    142       ParameterizeEvaluator();
     147   
     148    #region Helpers
     149    [StorableHook(HookType.AfterDeserialization)]
     150    private void AfterDeserialization() {
     151      RegisterEventHandlers();
     152    }
     153
     154    public override double Evaluate(Individual individual, IRandom random) {
     155      var tour = individual.Permutation(Encoding.Name);
     156      return Evaluate(tour);
     157    }
     158
     159    public double Evaluate(Permutation tour) {
     160      if (UseDistanceMatrix) return EvaluateWithDistanceMatrix(tour);
     161
     162      switch (DistanceFunction) {
     163        case TSPDistanceFunction.DistanceMatrix:
     164          return EvaluateWithDistanceMatrix(tour);
     165        case TSPDistanceFunction.Euclidean:
     166        case TSPDistanceFunction.RoundedEuclidean:
     167        case TSPDistanceFunction.UpperEuclidean:
     168        case TSPDistanceFunction.Geo:
     169          return EvaluateWithDistanceCalculation(tour);
     170        default: throw new InvalidOperationException(string.Format("Unknown distance function: {0}", DistanceFunction));
     171      }
     172    }
     173
     174    private double EvaluateWithDistanceMatrix(Permutation tour) {
     175      var distances = DistanceMatrix;
     176      double length = 0;
     177      for (var i = 0; i < tour.Length - 1; i++)
     178        length += distances[tour[i], tour[i + 1]];
     179      length += distances[tour[tour.Length - 1], tour[0]];
     180      return length;
     181    }
     182
     183    private double EvaluateWithDistanceCalculation(Permutation tour) {
     184      var coordinates = Coordinates;
     185      var distanceFunction = DistanceFunction;
     186      double length = 0;
     187      for (var i = 0; i < tour.Length - 1; i++)
     188        length += CalculateDistance(distanceFunction, coordinates[tour[i], 0], coordinates[tour[i], 1], coordinates[tour[i + 1], 0], coordinates[tour[i + 1], 1]);
     189      length += CalculateDistance(distanceFunction, coordinates[tour[tour.Length - 1], 0], coordinates[tour[tour.Length - 1], 1], coordinates[tour[0], 0], coordinates[tour[0], 1]);
     190      return length;
     191    }
     192
     193    private void RegisterEventHandlers() {
     194      coordinatesParameter.ValueChanged += coordinatesParameter_ValueChanged;
     195      if (Coordinates != null) {
     196        Coordinates.ItemChanged += Coordinates_ItemChanged;
     197        Coordinates.Reset += Coordinates_Reset;
     198      }
     199      Evaluator.QualityParameter.ActualNameChanged += Evaluator_QualityParameter_ActualNameChanged;
     200    }
     201
     202    private void Evaluator_QualityParameter_ActualNameChanged(object sender, EventArgs e) {
    143203      ParameterizeAnalyzers();
    144204      ParameterizeOperators();
    145205    }
    146     protected override void OnEvaluatorChanged() {
    147       base.OnEvaluatorChanged();
    148       Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
    149       ParameterizeEvaluator();
    150       ParameterizeSolutionCreator();
    151       UpdateMoveEvaluators();
    152       ParameterizeAnalyzers();
    153       if (Evaluator is ITSPCoordinatesPathEvaluator && Coordinates != null)
    154         ClearDistanceMatrix();
    155     }
    156     private void CoordinatesParameter_ValueChanged(object sender, EventArgs e) {
     206
     207    private void Coordinates_Reset(object sender, EventArgs e) {
     208      DistanceMatrix = null;
     209    }
     210
     211    private void Coordinates_ItemChanged(object sender, EventArgs<int, int> e) {
     212      DistanceMatrix = null;
     213    }
     214
     215    private void coordinatesParameter_ValueChanged(object sender, EventArgs e) {
    157216      if (Coordinates != null) {
    158217        Coordinates.ItemChanged += new EventHandler<EventArgs<int, int>>(Coordinates_ItemChanged);
    159218        Coordinates.Reset += new EventHandler(Coordinates_Reset);
    160       }
    161       if (Evaluator is ITSPCoordinatesPathEvaluator) {
    162         ParameterizeSolutionCreator();
    163         ClearDistanceMatrix();
    164       }
    165     }
    166     private void Coordinates_ItemChanged(object sender, EventArgs<int, int> e) {
    167       if (Evaluator is ITSPCoordinatesPathEvaluator) {
    168         ClearDistanceMatrix();
    169       }
    170     }
    171     private void Coordinates_Reset(object sender, EventArgs e) {
    172       if (Evaluator is ITSPCoordinatesPathEvaluator) {
    173         ParameterizeSolutionCreator();
    174         ClearDistanceMatrix();
    175       }
    176     }
    177     private void SolutionCreator_PermutationParameter_ActualNameChanged(object sender, EventArgs e) {
    178       ParameterizeEvaluator();
    179       ParameterizeAnalyzers();
    180       ParameterizeOperators();
    181     }
    182     private void Evaluator_QualityParameter_ActualNameChanged(object sender, EventArgs e) {
    183       ParameterizeAnalyzers();
    184     }
    185     #endregion
    186 
    187     #region Helpers
    188     [StorableHook(HookType.AfterDeserialization)]
    189     private void AfterDeserialization() {
    190       // BackwardsCompatibility3.3
    191       #region Backwards compatible code (remove with 3.4)
    192       OptionalValueParameter<DoubleMatrix> oldDistanceMatrixParameter = Parameters["DistanceMatrix"] as OptionalValueParameter<DoubleMatrix>;
    193       if (oldDistanceMatrixParameter != null) {
    194         Parameters.Remove(oldDistanceMatrixParameter);
    195         Parameters.Add(new OptionalValueParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
    196         DistanceMatrixParameter.GetsCollected = oldDistanceMatrixParameter.GetsCollected;
    197         DistanceMatrixParameter.ReactOnValueToStringChangedAndValueItemImageChanged = false;
    198         if (oldDistanceMatrixParameter.Value != null) {
    199           DoubleMatrix oldDM = oldDistanceMatrixParameter.Value;
    200           DistanceMatrix newDM = new DistanceMatrix(oldDM.Rows, oldDM.Columns, oldDM.ColumnNames, oldDM.RowNames);
    201           newDM.SortableView = oldDM.SortableView;
    202           for (int i = 0; i < newDM.Rows; i++)
    203             for (int j = 0; j < newDM.Columns; j++)
    204               newDM[i, j] = oldDM[i, j];
    205           DistanceMatrixParameter.Value = (DistanceMatrix)newDM.AsReadOnly();
    206         }
    207       }
    208 
    209       ValueParameter<DoubleMatrix> oldCoordinates = (Parameters["Coordinates"] as ValueParameter<DoubleMatrix>);
    210       if (oldCoordinates != null) {
    211         Parameters.Remove(oldCoordinates);
    212         Parameters.Add(new OptionalValueParameter<DoubleMatrix>("Coordinates", "The x- and y-Coordinates of the cities.", oldCoordinates.Value, oldCoordinates.GetsCollected));
    213       }
    214 
    215       if (Operators.Count == 0) InitializeOperators();
    216       #endregion
    217       RegisterEventHandlers();
    218     }
    219 
    220     private void RegisterEventHandlers() {
    221       CoordinatesParameter.ValueChanged += new EventHandler(CoordinatesParameter_ValueChanged);
    222       if (Coordinates != null) {
    223         Coordinates.ItemChanged += new EventHandler<EventArgs<int, int>>(Coordinates_ItemChanged);
    224         Coordinates.Reset += new EventHandler(Coordinates_Reset);
    225       }
    226       SolutionCreator.PermutationParameter.ActualNameChanged += new EventHandler(SolutionCreator_PermutationParameter_ActualNameChanged);
    227       Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
     219        DistanceMatrix = null;
     220      }
    228221    }
    229222
     
    239232      Operators.Add(new TSPAlleleFrequencyAnalyzer());
    240233      Operators.Add(new PopulationSimilarityAnalyzer(Operators.OfType<ISolutionSimilarityCalculator>()));
     234      Operators.AddRange(ApplicationManager.Manager.GetInstances<ITSPMoveEvaluator>());
     235
    241236      ParameterizeAnalyzers();
    242       var operators = new HashSet<IPermutationOperator>(new IPermutationOperator[] {
    243         new OrderCrossover2(),
    244         new InversionManipulator(),
    245         new StochasticInversionMultiMoveGenerator()
    246       }, new TypeEqualityComparer<IPermutationOperator>());
    247       foreach (var op in ApplicationManager.Manager.GetInstances<IPermutationOperator>())
    248         operators.Add(op);
    249       Operators.AddRange(operators);
    250237      ParameterizeOperators();
    251238      UpdateMoveEvaluators();
    252239    }
    253240    private void UpdateMoveEvaluators() {
    254       Operators.RemoveAll(x => x is ISingleObjectiveMoveEvaluator);
    255       foreach (var op in ApplicationManager.Manager.GetInstances<ITSPMoveEvaluator>())
    256         if (op.EvaluatorType == Evaluator.GetType()) {
    257           Operators.Add(op);
    258         }
    259241      ParameterizeOperators();
    260242      OnOperatorsChanged();
    261     }
    262     private void ParameterizeSolutionCreator() {
    263       if (Evaluator is ITSPDistanceMatrixEvaluator && DistanceMatrix != null)
    264         SolutionCreator.LengthParameter.Value = new IntValue(DistanceMatrix.Rows);
    265       else if (Evaluator is ITSPCoordinatesPathEvaluator && Coordinates != null)
    266         SolutionCreator.LengthParameter.Value = new IntValue(Coordinates.Rows);
    267       else {
    268         SolutionCreator.LengthParameter.Value = null;
    269         string error = "The given problem does not support the selected evaluator.";
    270         if (Evaluator is ITSPDistanceMatrixEvaluator)
    271           error += Environment.NewLine + "Please review that the " + DistanceMatrixParameter.Name + " parameter is defined or choose another evaluator.";
    272         else error += Environment.NewLine + "Please review that the " + CoordinatesParameter.Name + " parameter is defined or choose another evaluator.";
    273         PluginInfrastructure.ErrorHandling.ShowErrorDialog(error, null);
    274       }
    275       SolutionCreator.LengthParameter.Hidden = SolutionCreator.LengthParameter.Value != null;
    276       SolutionCreator.PermutationTypeParameter.Value = new PermutationType(PermutationTypes.RelativeUndirected);
    277       SolutionCreator.PermutationTypeParameter.Hidden = true;
    278     }
    279     private void ParameterizeEvaluator() {
    280       if (Evaluator is ITSPPathEvaluator) {
    281         ITSPPathEvaluator evaluator = (ITSPPathEvaluator)Evaluator;
    282         evaluator.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
    283         evaluator.PermutationParameter.Hidden = true;
    284       }
    285       if (Evaluator is ITSPCoordinatesPathEvaluator) {
    286         ITSPCoordinatesPathEvaluator evaluator = (ITSPCoordinatesPathEvaluator)Evaluator;
    287         evaluator.CoordinatesParameter.ActualName = CoordinatesParameter.Name;
    288         evaluator.CoordinatesParameter.Hidden = true;
    289         evaluator.DistanceMatrixParameter.ActualName = DistanceMatrixParameter.Name;
    290         evaluator.DistanceMatrixParameter.Hidden = true;
    291         evaluator.UseDistanceMatrixParameter.ActualName = UseDistanceMatrixParameter.Name;
    292         evaluator.UseDistanceMatrixParameter.Hidden = true;
    293       }
    294       if (Evaluator is ITSPDistanceMatrixEvaluator) {
    295         var evaluator = (ITSPDistanceMatrixEvaluator)Evaluator;
    296         evaluator.DistanceMatrixParameter.ActualName = DistanceMatrixParameter.Name;
    297         evaluator.DistanceMatrixParameter.Hidden = true;
    298       }
    299243    }
    300244    private void ParameterizeAnalyzers() {
    301245      if (BestTSPSolutionAnalyzer != null) {
    302246        BestTSPSolutionAnalyzer.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
    303         BestTSPSolutionAnalyzer.CoordinatesParameter.ActualName = CoordinatesParameter.Name;
    304         BestTSPSolutionAnalyzer.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
     247        BestTSPSolutionAnalyzer.CoordinatesParameter.ActualName = coordinatesParameter.Name;
     248        BestTSPSolutionAnalyzer.PermutationParameter.ActualName = Encoding.SolutionCreator.PermutationParameter.ActualName;
    305249        BestTSPSolutionAnalyzer.ResultsParameter.ActualName = "Results";
    306250        BestTSPSolutionAnalyzer.BestKnownQualityParameter.ActualName = BestKnownQualityParameter.Name;
    307         BestTSPSolutionAnalyzer.BestKnownSolutionParameter.ActualName = BestKnownSolutionParameter.Name;
    308         BestTSPSolutionAnalyzer.MaximizationParameter.ActualName = MaximizationParameter.Name;
     251        BestTSPSolutionAnalyzer.BestKnownSolutionParameter.ActualName = bestKnownSolutionParameter.Name;
     252        BestTSPSolutionAnalyzer.MaximizationParameter.ActualName = ((ISingleObjectiveHeuristicOptimizationProblem)this).MaximizationParameter.Name;
    309253      }
    310254
    311255      if (TSPAlleleFrequencyAnalyzer != null) {
    312         TSPAlleleFrequencyAnalyzer.MaximizationParameter.ActualName = MaximizationParameter.Name;
    313         TSPAlleleFrequencyAnalyzer.CoordinatesParameter.ActualName = CoordinatesParameter.Name;
    314         TSPAlleleFrequencyAnalyzer.DistanceMatrixParameter.ActualName = DistanceMatrixParameter.Name;
    315         TSPAlleleFrequencyAnalyzer.SolutionParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
     256        TSPAlleleFrequencyAnalyzer.MaximizationParameter.ActualName = ((ISingleObjectiveHeuristicOptimizationProblem)this).MaximizationParameter.Name;
     257        TSPAlleleFrequencyAnalyzer.CoordinatesParameter.ActualName = coordinatesParameter.Name;
     258        TSPAlleleFrequencyAnalyzer.DistanceMatrixParameter.ActualName = distanceMatrixParameter.Name;
     259        TSPAlleleFrequencyAnalyzer.SolutionParameter.ActualName = Encoding.SolutionCreator.PermutationParameter.ActualName;
    316260        TSPAlleleFrequencyAnalyzer.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
    317         TSPAlleleFrequencyAnalyzer.BestKnownSolutionParameter.ActualName = BestKnownSolutionParameter.Name;
     261        TSPAlleleFrequencyAnalyzer.BestKnownSolutionParameter.ActualName = bestKnownSolutionParameter.Name;
    318262        TSPAlleleFrequencyAnalyzer.ResultsParameter.ActualName = "Results";
    319263      }
    320264    }
    321265    private void ParameterizeOperators() {
    322       foreach (IPermutationCrossover op in Operators.OfType<IPermutationCrossover>()) {
    323         op.ParentsParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
    324         op.ParentsParameter.Hidden = true;
    325         op.ChildParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
    326         op.ChildParameter.Hidden = true;
    327       }
    328       foreach (IPermutationManipulator op in Operators.OfType<IPermutationManipulator>()) {
    329         op.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
    330         op.PermutationParameter.Hidden = true;
    331       }
    332       foreach (IPermutationMoveOperator op in Operators.OfType<IPermutationMoveOperator>()) {
    333         op.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
    334         op.PermutationParameter.Hidden = true;
    335       }
    336266      foreach (ITSPPathMoveEvaluator op in Operators.OfType<ITSPPathMoveEvaluator>()) {
    337         op.CoordinatesParameter.ActualName = CoordinatesParameter.Name;
     267        op.DistanceFunctionParameter.ActualName = distanceFunctionParameter.Name;
     268        op.DistanceFunctionParameter.Hidden = true;
     269        op.CoordinatesParameter.ActualName = coordinatesParameter.Name;
    338270        op.CoordinatesParameter.Hidden = true;
    339         op.DistanceMatrixParameter.ActualName = DistanceMatrixParameter.Name;
     271        op.DistanceMatrixParameter.ActualName = distanceMatrixParameter.Name;
    340272        op.DistanceMatrixParameter.Hidden = true;
    341         op.UseDistanceMatrixParameter.ActualName = UseDistanceMatrixParameter.Name;
     273        op.UseDistanceMatrixParameter.ActualName = useDistanceMatrixParameter.Name;
    342274        op.UseDistanceMatrixParameter.Hidden = true;
    343275        op.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
    344276        op.QualityParameter.Hidden = true;
    345         op.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
     277        op.PermutationParameter.ActualName = Encoding.SolutionCreator.PermutationParameter.ActualName;
    346278        op.PermutationParameter.Hidden = true;
    347279      }
    348       foreach (IPermutationMultiNeighborhoodShakingOperator op in Operators.OfType<IPermutationMultiNeighborhoodShakingOperator>()) {
    349         op.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
    350         op.PermutationParameter.Hidden = true;
    351       }
    352280      foreach (ISingleObjectiveImprovementOperator op in Operators.OfType<ISingleObjectiveImprovementOperator>()) {
    353         op.SolutionParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
     281        op.SolutionParameter.ActualName = Encoding.SolutionCreator.PermutationParameter.ActualName;
    354282        op.SolutionParameter.Hidden = true;
    355283      }
    356284      foreach (ISingleObjectivePathRelinker op in Operators.OfType<ISingleObjectivePathRelinker>()) {
    357         op.ParentsParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
     285        op.ParentsParameter.ActualName = Encoding.SolutionCreator.PermutationParameter.ActualName;
    358286        op.ParentsParameter.Hidden = true;
    359287      }
    360288      foreach (ISolutionSimilarityCalculator op in Operators.OfType<ISolutionSimilarityCalculator>()) {
    361         op.SolutionVariableName = SolutionCreator.PermutationParameter.ActualName;
     289        op.SolutionVariableName = Encoding.SolutionCreator.PermutationParameter.ActualName;
    362290        op.QualityVariableName = Evaluator.QualityParameter.ActualName;
    363291      }
    364292    }
    365293
    366     private void ClearDistanceMatrix() {
    367       DistanceMatrixParameter.Value = null;
     294    public void UpdateDistanceMatrix() {
     295      var df = DistanceFunction;
     296      var c = Coordinates;
     297      if (c == null) throw new InvalidOperationException("No coordinates are given to calculate distance matrix.");
     298      DistanceMatrix = CalculateDistanceMatrix(df, c);
     299    }
     300
     301    public static DistanceMatrix CalculateDistanceMatrix(TSPDistanceFunction distance, DoubleMatrix coordinates) {
     302      var dm = new double[coordinates.Rows, coordinates.Rows];
     303      for (var i = 0; i < dm.GetLength(0); i++) {
     304        for (var j = 0; j < dm.GetLength(1); j++)
     305          dm[i, j] = CalculateDistance(distance, coordinates[i, 0], coordinates[i, 1], coordinates[j, 0], coordinates[j, 1]);
     306      }
     307      return new DistanceMatrix(dm, readOnly: true);
    368308    }
    369309    #endregion
     
    381321      Name = data.Name;
    382322      Description = data.Description;
    383 
    384       bool clearCoordinates = false, clearDistanceMatrix = false;
     323     
    385324      if (data.Coordinates != null && data.Coordinates.GetLength(0) > 0)
    386325        Coordinates = new DoubleMatrix(data.Coordinates);
    387       else clearCoordinates = true;
    388 
    389       TSPEvaluator evaluator;
     326      else Coordinates = null;
     327     
    390328      if (data.DistanceMeasure == DistanceMeasure.Att
    391329        || data.DistanceMeasure == DistanceMeasure.Manhattan
    392330        || data.DistanceMeasure == DistanceMeasure.Maximum) {
    393         evaluator = new TSPDistanceMatrixEvaluator();
    394         UseDistanceMatrix = new BoolValue(true);
     331        UseDistanceMatrix = true;
    395332        DistanceMatrix = new DistanceMatrix(data.GetDistanceMatrix());
     333        DistanceFunction = TSPDistanceFunction.DistanceMatrix;
    396334      } else if (data.DistanceMeasure == DistanceMeasure.Direct && data.Distances != null) {
    397         evaluator = new TSPDistanceMatrixEvaluator();
    398         UseDistanceMatrix = new BoolValue(true);
     335        UseDistanceMatrix = true;
    399336        DistanceMatrix = new DistanceMatrix(data.Distances);
     337        DistanceFunction = TSPDistanceFunction.DistanceMatrix;
    400338      } else {
    401         clearDistanceMatrix = true;
    402         UseDistanceMatrix = new BoolValue(data.Dimension <= DistanceMatrixSizeLimit);
     339        UseDistanceMatrix = data.Dimension <= DistanceMatrixSizeLimit;
    403340        switch (data.DistanceMeasure) {
    404341          case DistanceMeasure.Euclidean:
    405             evaluator = new TSPEuclideanPathEvaluator();
     342            DistanceFunction = TSPDistanceFunction.Euclidean;
    406343            break;
    407344          case DistanceMeasure.RoundedEuclidean:
    408             evaluator = new TSPRoundedEuclideanPathEvaluator();
     345            DistanceFunction = TSPDistanceFunction.RoundedEuclidean;
    409346            break;
    410347          case DistanceMeasure.UpperEuclidean:
    411             evaluator = new TSPUpperEuclideanPathEvaluator();
     348            DistanceFunction = TSPDistanceFunction.UpperEuclidean;
    412349            break;
    413350          case DistanceMeasure.Geo:
    414             evaluator = new TSPGeoPathEvaluator();
     351            DistanceFunction = TSPDistanceFunction.Geo;
    415352            break;
    416353          default:
    417354            throw new InvalidDataException("An unknown distance measure is given in the instance!");
    418355        }
    419       }
    420       evaluator.QualityParameter.ActualName = "TSPTourLength";
    421       Evaluator = evaluator;
    422 
    423       // reset them after assigning the evaluator
    424       if (clearCoordinates) Coordinates = null;
    425       if (clearDistanceMatrix) DistanceMatrix = null;
    426 
     356        if (UseDistanceMatrix) UpdateDistanceMatrix();
     357        else DistanceMatrix = null;
     358      }
     359      Evaluator.QualityParameter.ActualName = "TSPTourLength";
     360     
    427361      BestKnownSolution = null;
    428       BestKnownQuality = null;
     362      BestKnownQualityParameter.Value = null;
    429363
    430364      if (data.BestKnownTour != null) {
     
    433367        } catch (InvalidOperationException) {
    434368          if (data.BestKnownQuality.HasValue)
    435             BestKnownQuality = new DoubleValue(data.BestKnownQuality.Value);
     369            BestKnownQuality = data.BestKnownQuality.Value;
    436370        }
    437371      } else if (data.BestKnownQuality.HasValue) {
    438         BestKnownQuality = new DoubleValue(data.BestKnownQuality.Value);
     372        BestKnownQuality = data.BestKnownQuality.Value;
    439373      }
    440374      OnReset();
     
    444378      var route = new Permutation(PermutationTypes.RelativeUndirected, tour);
    445379      BestKnownSolution = route;
    446 
    447       double quality;
    448       if (Evaluator is ITSPDistanceMatrixEvaluator) {
    449         quality = TSPDistanceMatrixEvaluator.Apply(DistanceMatrix, route);
    450       } else if (Evaluator is ITSPCoordinatesPathEvaluator) {
    451         quality = TSPCoordinatesPathEvaluator.Apply((TSPCoordinatesPathEvaluator)Evaluator, Coordinates, route);
    452       } else {
    453         throw new InvalidOperationException("Cannot calculate solution quality, evaluator type is unknown.");
    454       }
    455       BestKnownQuality = new DoubleValue(quality);
     380      BestKnownQuality = Evaluate(route);
     381    }
     382
     383    public static double CalculateDistance(TSPDistanceFunction distanceFunction, double x1, double y1, double x2, double y2) {
     384      switch (distanceFunction) {
     385        case TSPDistanceFunction.Euclidean:
     386          return CalculateEuclideanDistance(x1, y1, x2, y2);
     387        case TSPDistanceFunction.RoundedEuclidean:
     388          return CalculateRoundedEuclideanDistance(x1, y1, x2, y2);
     389        case TSPDistanceFunction.UpperEuclidean:
     390          return CalculateUpperEuclideanDistance(x1, y1, x2, y2);
     391        case TSPDistanceFunction.Geo:
     392          return CalculateGeoDistance(x1, y1, x2, y2);
     393        default: throw new ArgumentException(string.Format("Distance calculation not available for {0}", distanceFunction));
     394      }
     395    }
     396
     397    public static double CalculateEuclideanDistance(double x1, double y1, double x2, double y2) {
     398      return Math.Sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
     399    }
     400
     401    public static double CalculateRoundedEuclideanDistance(double x1, double y1, double x2, double y2) {
     402      return Math.Round(Math.Sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)));
     403    }
     404
     405    public static double CalculateUpperEuclideanDistance(double x1, double y1, double x2, double y2) {
     406      return Math.Ceiling(Math.Sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)));
     407    }
     408
     409    public static double CalculateGeoDistance(double x1, double y1, double x2, double y2) {
     410      double latitude1, longitude1, latitude2, longitude2;
     411      double q1, q2, q3;
     412      double length;
     413
     414      latitude1 = ConvertToRadian(x1);
     415      longitude1 = ConvertToRadian(y1);
     416      latitude2 = ConvertToRadian(x2);
     417      longitude2 = ConvertToRadian(y2);
     418
     419      q1 = Math.Cos(longitude1 - longitude2);
     420      q2 = Math.Cos(latitude1 - latitude2);
     421      q3 = Math.Cos(latitude1 + latitude2);
     422
     423      length = (int)(RADIUS * Math.Acos(0.5 * ((1.0 + q1) * q2 - (1.0 - q1) * q3)) + 1.0);
     424      return (length);
     425    }
     426
     427    private static double ConvertToRadian(double x) {
     428      return PI * (Math.Truncate(x) + 5.0 * (x - Math.Truncate(x)) / 3.0) / 180.0;
    456429    }
    457430  }
Note: See TracChangeset for help on using the changeset viewer.