Free cookie consent management tool by TermsFeed Policy Generator

Changeset 3066


Ignore:
Timestamp:
03/16/10 16:04:54 (14 years ago)
Author:
swagner
Message:

Implemented first version of distance matrix-based evaluation for the TSP (#912)

Location:
trunk/sources/HeuristicLab.Problems.TSP/3.3
Files:
2 deleted
4 edited

Legend:

Unmodified
Added
Removed
  • trunk/sources/HeuristicLab.Problems.TSP/3.3/Evaluators/TSPCoordinatesPathEvaluator.cs

    r3053 r3066  
    3939      get { return (ILookupParameter<DoubleMatrix>)Parameters["Coordinates"]; }
    4040    }
     41    public ILookupParameter<DoubleMatrix> DistanceMatrixParameter {
     42      get { return (ILookupParameter<DoubleMatrix>)Parameters["DistanceMatrix"]; }
     43    }
     44    public ILookupParameter<BoolValue> UseDistanceMatrixParameter {
     45      get { return (ILookupParameter<BoolValue>)Parameters["UseDistanceMatrix"]; }
     46    }
    4147
    4248    protected TSPCoordinatesPathEvaluator()
     
    4450      Parameters.Add(new LookupParameter<Permutation>("Permutation", "The TSP solution given in path representation which should be evaluated."));
    4551      Parameters.Add(new LookupParameter<DoubleMatrix>("Coordinates", "The x- and y-Coordinates of the cities."));
     52      Parameters.Add(new LookupParameter<DoubleMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
     53      Parameters.Add(new LookupParameter<BoolValue>("UseDistanceMatrix", "True if a distance matrix should be calculated and used for evaluation, otherwise false."));
    4654    }
    4755
    4856    public sealed override IOperation Apply() {
    49       Permutation p = PermutationParameter.ActualValue;
    50       DoubleMatrix c = CoordinatesParameter.ActualValue;
     57      if (UseDistanceMatrixParameter.ActualValue.Value) {
     58        Permutation p = PermutationParameter.ActualValue;
     59        DoubleMatrix dm = DistanceMatrixParameter.ActualValue;
    5160
    52       double length = 0;
    53       for (int i = 0; i < p.Length - 1; i++)
    54         length += CalculateDistance(c[p[i], 0], c[p[i], 1], c[p[i + 1], 0], c[p[i + 1], 1]);
    55       length += CalculateDistance(c[p[p.Length - 1], 0], c[p[p.Length - 1], 1], c[p[0], 0], c[p[0], 1]);
    56       QualityParameter.ActualValue = new DoubleValue(length);
     61        if (dm == null) {  // calculate distance matrix
     62          DoubleMatrix c = CoordinatesParameter.ActualValue;
    5763
     64          dm = new DoubleMatrix(c.Rows, c.Rows);
     65          for (int i = 0; i < dm.Rows; i++) {
     66            for (int j = 0; j < dm.Columns; j++)
     67              dm[i, j] = CalculateDistance(c[i, 0], c[i, 1], c[j, 0], c[j, 1]);
     68          }
     69          DistanceMatrixParameter.ActualValue = dm;
     70        }
     71
     72        double length = 0;
     73        for (int i = 0; i < p.Length - 1; i++)
     74          length += dm[p[i], p[i + 1]];
     75        length += dm[p[p.Length - 1], p[0]];
     76        QualityParameter.ActualValue = new DoubleValue(length);
     77      } else {
     78        Permutation p = PermutationParameter.ActualValue;
     79        DoubleMatrix c = CoordinatesParameter.ActualValue;
     80
     81        double length = 0;
     82        for (int i = 0; i < p.Length - 1; i++)
     83          length += CalculateDistance(c[p[i], 0], c[p[i], 1], c[p[i + 1], 0], c[p[i + 1], 1]);
     84        length += CalculateDistance(c[p[p.Length - 1], 0], c[p[p.Length - 1], 1], c[p[0], 0], c[p[0], 1]);
     85        QualityParameter.ActualValue = new DoubleValue(length);
     86      }
    5887      return base.Apply();
    5988    }
  • trunk/sources/HeuristicLab.Problems.TSP/3.3/HeuristicLab.Problems.TSP-3.3.csproj

    r3053 r3066  
    8585  <ItemGroup>
    8686    <Compile Include="Evaluators\TSPCoordinatesPathEvaluator.cs" />
    87     <Compile Include="Evaluators\TSPDistanceMatrixPathEvaluator.cs" />
    8887    <Compile Include="Evaluators\TSPEvaluator.cs" />
    8988    <Compile Include="Evaluators\TSPRoundedEuclideanPathEvaluator.cs" />
    9089    <Compile Include="Interfaces\ITSPCoordinatesPathEvaluator.cs" />
    91     <Compile Include="Interfaces\ITSPDistanceMatrixPathEvaluator.cs" />
    9290    <Compile Include="Interfaces\ITSPEvaluator.cs" />
    9391    <Compile Include="Interfaces\ITSPPathEvaluator.cs" />
  • trunk/sources/HeuristicLab.Problems.TSP/3.3/Interfaces/ITSPCoordinatesPathEvaluator.cs

    r3048 r3066  
    2929  public interface ITSPCoordinatesPathEvaluator : ITSPPathEvaluator {
    3030    ILookupParameter<DoubleMatrix> CoordinatesParameter { get; }
     31    ILookupParameter<DoubleMatrix> DistanceMatrixParameter { get; }
     32    ILookupParameter<BoolValue> UseDistanceMatrixParameter { get; }
    3133  }
    3234}
  • trunk/sources/HeuristicLab.Problems.TSP/3.3/TSP.cs

    r3053 r3066  
    5252      get { return (ValueParameter<DoubleMatrix>)Parameters["Coordinates"]; }
    5353    }
     54    public OptionalValueParameter<DoubleMatrix> DistanceMatrixParameter {
     55      get { return (OptionalValueParameter<DoubleMatrix>)Parameters["DistanceMatrix"]; }
     56    }
     57    public ValueParameter<BoolValue> UseDistanceMatrixParameter {
     58      get { return (ValueParameter<BoolValue>)Parameters["UseDistanceMatrix"]; }
     59    }
    5460    public ValueParameter<IPermutationCreator> SolutionCreatorParameter {
    5561      get { return (ValueParameter<IPermutationCreator>)Parameters["SolutionCreator"]; }
     
    7480      set { CoordinatesParameter.Value = value; }
    7581    }
     82    public DoubleMatrix DistanceMatrix {
     83      get { return DistanceMatrixParameter.Value; }
     84      set { DistanceMatrixParameter.Value = value; }
     85    }
     86    public BoolValue UseDistanceMatrix {
     87      get { return UseDistanceMatrixParameter.Value; }
     88      set { UseDistanceMatrixParameter.Value = value; }
     89    }
    7690    public IPermutationCreator SolutionCreator {
    7791      get { return SolutionCreatorParameter.Value; }
     
    108122      Parameters.Add(new ValueParameter<BoolValue>("Maximization", "Set to false as the Traveling Salesman Problem is a minimization problem.", new BoolValue(false)));
    109123      Parameters.Add(new ValueParameter<DoubleMatrix>("Coordinates", "The x- and y-Coordinates of the cities.", new DoubleMatrix(0, 0)));
     124      Parameters.Add(new OptionalValueParameter<DoubleMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
     125      Parameters.Add(new ValueParameter<BoolValue>("UseDistanceMatrix", "True if a distance matrix should be calculated and used for evaluation, otherwise false.", new BoolValue(true)));
    110126      Parameters.Add(new ValueParameter<IPermutationCreator>("SolutionCreator", "The operator which should be used to create new TSP solutions.", creator));
    111127      Parameters.Add(new ValueParameter<ITSPEvaluator>("Evaluator", "The operator which should be used to evaluate TSP solutions.", evaluator));
     
    155171      Coordinates.Reset += new EventHandler(Coordinates_Reset);
    156172      ParameterizeSolutionCreator();
     173      ClearDistanceMatrix();
    157174    }
    158175    private void Coordinates_ItemChanged(object sender, EventArgs<int, int> e) {
     176      ClearDistanceMatrix();
    159177    }
    160178    private void Coordinates_Reset(object sender, EventArgs e) {
    161179      ParameterizeSolutionCreator();
     180      ClearDistanceMatrix();
    162181    }
    163182    private void SolutionCreatorParameter_ValueChanged(object sender, EventArgs e) {
     
    174193    private void EvaluatorParameter_ValueChanged(object sender, EventArgs e) {
    175194      ParameterizeEvaluator();
     195      ClearDistanceMatrix();
    176196      OnEvaluatorChanged();
    177197    }
     
    195215      if (Evaluator is ITSPPathEvaluator)
    196216        ((ITSPPathEvaluator)Evaluator).PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
    197       if (Evaluator is ITSPCoordinatesPathEvaluator)
    198         ((ITSPCoordinatesPathEvaluator)Evaluator).CoordinatesParameter.ActualName = CoordinatesParameter.Name;
     217      if (Evaluator is ITSPCoordinatesPathEvaluator) {
     218        ITSPCoordinatesPathEvaluator evaluator = (ITSPCoordinatesPathEvaluator)Evaluator;
     219        evaluator.CoordinatesParameter.ActualName = CoordinatesParameter.Name;
     220        evaluator.DistanceMatrixParameter.ActualName = DistanceMatrixParameter.Name;
     221        evaluator.UseDistanceMatrixParameter.ActualName = UseDistanceMatrixParameter.Name;
     222      }
    199223    }
    200224    private void InitializeOperators() {
     
    214238      }
    215239    }
     240    private void ClearDistanceMatrix() {
     241      DistanceMatrixParameter.Value = null;
     242    }
    216243    #endregion
    217244  }
Note: See TracChangeset for help on using the changeset viewer.