Changeset 13412


Ignore:
Timestamp:
11/28/15 23:38:51 (7 years ago)
Author:
abeham
Message:

#2221:

  • Completely refactored PTSP branch
    • Added two sets of problem instances based on TSPLIB: homogeneous and heterogeneous
    • Implemented missing EvaluateByCoordinates for 1-shift moves
    • Made it clear that move evaluators are for estimated PTSP only
    • Changed parameter realization from a rather strange list of list of ints to a list of bool arrays
    • Reusing code of the 2-opt and 1-shift move evaluators in 2.5 move evaluator
    • Introducing distance calculators to properly handle the case when no distance matrix is given (previous code only worked with distance matrix and without only with euclidean distance in some settings)
    • Fixed several smaller code issues: protected, static, method parameters, copy & paste, interfaces, naming, parameters, serialization hooks, license headers, doc comments, data types
Location:
branches/PTSP
Files:
13 added
4 deleted
24 edited
16 copied
3 moved

Legend:

Unmodified
Added
Removed
  • branches/PTSP/HeuristicLab.Problems.Instances.TSPLIB/3.3/HeuristicLab.Problems.Instances.TSPLIB-3.3.csproj

    r11650 r13412  
    1919    <DebugType>full</DebugType>
    2020    <Optimize>false</Optimize>
    21     <OutputPath>..\..\bin\</OutputPath>
     21    <OutputPath>..\..\..\..\trunk\sources\bin\</OutputPath>
    2222    <DefineConstants>DEBUG;TRACE</DefineConstants>
    2323    <ErrorReport>prompt</ErrorReport>
     
    2828    <DebugType>pdbonly</DebugType>
    2929    <Optimize>true</Optimize>
    30     <OutputPath>..\..\bin\</OutputPath>
     30    <OutputPath>..\..\..\..\trunk\sources\bin\</OutputPath>
    3131    <DefineConstants>TRACE</DefineConstants>
    3232    <ErrorReport>prompt</ErrorReport>
     
    4242  <PropertyGroup Condition="'$(Configuration)|$(Platform)' == 'Debug|x64'">
    4343    <DebugSymbols>true</DebugSymbols>
    44     <OutputPath>..\..\bin\</OutputPath>
     44    <OutputPath>..\..\..\..\trunk\sources\bin\</OutputPath>
    4545    <DefineConstants>DEBUG;TRACE</DefineConstants>
    4646    <DebugType>full</DebugType>
     
    5858  </PropertyGroup>
    5959  <PropertyGroup Condition="'$(Configuration)|$(Platform)' == 'Release|x64'">
    60     <OutputPath>..\..\bin\</OutputPath>
     60    <OutputPath>..\..\..\..\trunk\sources\bin\</OutputPath>
    6161    <DefineConstants>TRACE</DefineConstants>
    6262    <Optimize>true</Optimize>
     
    7676  <PropertyGroup Condition="'$(Configuration)|$(Platform)' == 'Debug|x86'">
    7777    <DebugSymbols>true</DebugSymbols>
    78     <OutputPath>..\..\bin\</OutputPath>
     78    <OutputPath>..\..\..\..\trunk\sources\bin\</OutputPath>
    7979    <DefineConstants>DEBUG;TRACE</DefineConstants>
    8080    <DebugType>full</DebugType>
     
    9292  </PropertyGroup>
    9393  <PropertyGroup Condition="'$(Configuration)|$(Platform)' == 'Release|x86'">
    94     <OutputPath>..\..\bin\</OutputPath>
     94    <OutputPath>..\..\..\..\trunk\sources\bin\</OutputPath>
    9595    <DefineConstants>TRACE</DefineConstants>
    9696    <Optimize>true</Optimize>
     
    109109  </PropertyGroup>
    110110  <ItemGroup>
     111    <Reference Include="HeuristicLab.Common-3.3">
     112      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Common-3.3.dll</HintPath>
     113      <Private>False</Private>
     114    </Reference>
     115    <Reference Include="HeuristicLab.PluginInfrastructure-3.3">
     116      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.PluginInfrastructure-3.3.dll</HintPath>
     117      <Private>False</Private>
     118    </Reference>
    111119    <Reference Include="System" />
    112120    <Reference Include="System.Core" />
     
    115123  </ItemGroup>
    116124  <ItemGroup>
     125    <Compile Include="MarsagliaRandom.cs" />
     126    <Compile Include="TSPLIBHeterogeneousPTSPDataDescriptor.cs" />
     127    <Compile Include="TSPLIBHomogeneousPTSPDataDescriptor.cs" />
     128    <Compile Include="TSPLIBHeterogeneousPTSPInstanceProvider.cs" />
    117129    <Compile Include="TSPLIBInstanceProvider.cs" />
    118130    <Compile Include="TSPLIBATSPInstanceProvider.cs" />
    119131    <Compile Include="TSPLIBCVRPInstanceProvider.cs" />
    120132    <Compile Include="TSPLIBDataDescriptor.cs" />
     133    <Compile Include="TSPLIBHomogeneousPTSPInstanceProvider.cs" />
    121134    <Compile Include="TSPLIBTSPInstanceProvider.cs" />
    122135    <Compile Include="TSPLIBParser.cs" />
     
    134147  </ItemGroup>
    135148  <ItemGroup>
    136     <ProjectReference Include="..\..\HeuristicLab.Common\3.3\HeuristicLab.Common-3.3.csproj">
    137       <Project>{A9AD58B9-3EF9-4CC1-97E5-8D909039FF5C}</Project>
    138       <Name>HeuristicLab.Common-3.3</Name>
    139       <Private>False</Private>
    140     </ProjectReference>
    141     <ProjectReference Include="..\..\HeuristicLab.PluginInfrastructure\3.3\HeuristicLab.PluginInfrastructure-3.3.csproj">
    142       <Project>{94186A6A-5176-4402-AE83-886557B53CCA}</Project>
    143       <Name>HeuristicLab.PluginInfrastructure-3.3</Name>
    144       <Private>False</Private>
    145     </ProjectReference>
    146149    <ProjectReference Include="..\..\HeuristicLab.Problems.Instances\3.3\HeuristicLab.Problems.Instances-3.3.csproj">
    147       <Project>{3540E29E-4793-49E7-8EE2-FEA7F61C3994}</Project>
     150      <Project>{3540e29e-4793-49e7-8ee2-fea7f61c3994}</Project>
    148151      <Name>HeuristicLab.Problems.Instances-3.3</Name>
    149152      <Private>False</Private>
    150153    </ProjectReference>
    151154  </ItemGroup>
    152   <ItemGroup />
    153155  <Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" />
    154156  <PropertyGroup>
  • branches/PTSP/HeuristicLab.Problems.Instances.TSPLIB/3.3/TSPLIBATSPInstanceProvider.cs

    r12012 r13412  
    3636    protected override string FileExtension { get { return "atsp"; } }
    3737
    38     protected override ATSPData LoadInstance(TSPLIBParser parser) {
     38    protected override ATSPData LoadInstance(TSPLIBParser parser, IDataDescriptor descriptor = null) {
    3939      var instance = new ATSPData();
    4040
  • branches/PTSP/HeuristicLab.Problems.Instances.TSPLIB/3.3/TSPLIBCVRPInstanceProvider.cs

    r12012 r13412  
    3636    protected override string FileExtension { get { return "vrp"; } }
    3737
    38     protected override CVRPData LoadInstance(TSPLIBParser parser) {
     38    protected override CVRPData LoadInstance(TSPLIBParser parser, IDataDescriptor descriptor = null) {
    3939      parser.Parse();
    4040      var instance = new CVRPData();
  • branches/PTSP/HeuristicLab.Problems.Instances.TSPLIB/3.3/TSPLIBHeterogeneousPTSPDataDescriptor.cs

    r13408 r13412  
    2020#endregion
    2121
     22
    2223namespace HeuristicLab.Problems.Instances.TSPLIB {
    23   internal class TSPLIBDataDescriptor : IDataDescriptor {
    24     public string Name { get; internal set; }
    25     public string Description { get; internal set; }
     24  internal class TSPLIBHeterogeneousPTSPDataDescriptor : TSPLIBDataDescriptor {
     25    public int Seed { get; internal set; }
    2626
    27     internal string InstanceIdentifier { get; set; }
    28     internal string SolutionIdentifier { get; set; }
    29 
    30     internal TSPLIBDataDescriptor(string name, string description, string instanceIdentifier, string solutionIdentifier) {
     27    internal TSPLIBHeterogeneousPTSPDataDescriptor(string name, string description, string instanceIdentifier, string solutionIdentifier, int seed)
     28      : base(name, description, instanceIdentifier, solutionIdentifier) {
    3129      this.Name = name;
    3230      this.Description = description;
    3331      this.InstanceIdentifier = instanceIdentifier;
    3432      this.SolutionIdentifier = solutionIdentifier;
     33      this.Seed = seed;
    3534    }
    3635  }
  • branches/PTSP/HeuristicLab.Problems.Instances.TSPLIB/3.3/TSPLIBHeterogeneousPTSPInstanceProvider.cs

    r13408 r13412  
    2121
    2222using System;
     23using System.Collections.Generic;
    2324using System.IO;
    2425using System.Linq;
    2526
    2627namespace HeuristicLab.Problems.Instances.TSPLIB {
    27   public class TSPLIBTSPInstanceProvider : TSPLIBInstanceProvider<TSPData> {
     28  public class TSPLIBHeterogeneousPTSPInstanceProvider : TSPLIBInstanceProvider<PTSPData> {
    2829
    2930    public override string Name {
    30       get { return "TSPLIB (symmetric TSP)"; }
     31      get { return "TSPLIB (heterogeneous symmetric PTSP)"; }
    3132    }
    3233
     
    3738    protected override string FileExtension { get { return "tsp"; } }
    3839
    39     protected override TSPData LoadInstance(TSPLIBParser parser) {
     40    public override IEnumerable<IDataDescriptor> GetDataDescriptors() {
     41      foreach (var desc in base.GetDataDescriptors().OfType<TSPLIBDataDescriptor>()) {
     42        desc.Name += " [0.1;0.9]";
     43        desc.SolutionIdentifier = null;
     44        yield return desc;
     45      }
     46    }
     47
     48    protected override PTSPData LoadInstance(TSPLIBParser parser, IDataDescriptor descriptor = null) {
    4049      parser.Parse();
    4150      if (parser.FixedEdges != null) throw new InvalidDataException("TSP instance " + parser.Name + " contains fixed edges which are not supported by HeuristicLab.");
    42       var instance = new TSPData();
     51      var instance = new PTSPData();
    4352      instance.Dimension = parser.Dimension;
    4453      instance.Coordinates = parser.Vertices != null ? parser.Vertices : parser.DisplayVertices;
     
    7382        + Environment.NewLine + Environment.NewLine
    7483        + GetInstanceDescription();
     84
     85      var random = new MarsagliaRandom((uint)(descriptor != null ? descriptor.Name : instance.Name).GetHashCode());
     86      instance.Probabilities = Enumerable.Range(0, instance.Dimension).Select(_ => 0.1 + 0.9 * random.NextDouble()).ToArray();
     87
    7588      return instance;
    7689    }
    7790
    78     protected override void LoadSolution(TSPLIBParser parser, TSPData instance) {
     91    protected override void LoadSolution(TSPLIBParser parser, PTSPData instance) {
    7992      parser.Parse();
    8093      instance.BestKnownTour = parser.Tour.FirstOrDefault();
    8194    }
    8295
    83     public TSPData LoadData(string tspFile, string tourFile, double? bestQuality) {
     96    public PTSPData LoadData(string tspFile, string tourFile, double? bestQuality) {
    8497      var data = LoadInstance(new TSPLIBParser(tspFile));
    8598      if (!String.IsNullOrEmpty(tourFile)) {
  • branches/PTSP/HeuristicLab.Problems.Instances.TSPLIB/3.3/TSPLIBHomogeneousPTSPDataDescriptor.cs

    r13408 r13412  
    2121
    2222namespace HeuristicLab.Problems.Instances.TSPLIB {
    23   internal class TSPLIBDataDescriptor : IDataDescriptor {
    24     public string Name { get; internal set; }
    25     public string Description { get; internal set; }
     23  internal class TSPLIBHomogeneousPTSPDataDescriptor : TSPLIBDataDescriptor {
     24    public double Probability { get; internal set; }
    2625
    27     internal string InstanceIdentifier { get; set; }
    28     internal string SolutionIdentifier { get; set; }
    29 
    30     internal TSPLIBDataDescriptor(string name, string description, string instanceIdentifier, string solutionIdentifier) {
     26    internal TSPLIBHomogeneousPTSPDataDescriptor(string name, string description, string instanceIdentifier, string solutionIdentifier, double probability)
     27      : base(name, description, instanceIdentifier, solutionIdentifier) {
    3128      this.Name = name;
    3229      this.Description = description;
    3330      this.InstanceIdentifier = instanceIdentifier;
    3431      this.SolutionIdentifier = solutionIdentifier;
     32      this.Probability = probability;
    3533    }
    3634  }
  • branches/PTSP/HeuristicLab.Problems.Instances.TSPLIB/3.3/TSPLIBHomogeneousPTSPInstanceProvider.cs

    r13408 r13412  
    2121
    2222using System;
     23using System.Collections.Generic;
     24using System.Globalization;
    2325using System.IO;
    2426using System.Linq;
    2527
    2628namespace HeuristicLab.Problems.Instances.TSPLIB {
    27   public class TSPLIBTSPInstanceProvider : TSPLIBInstanceProvider<TSPData> {
     29  public class TSPLIBHomogeneousPTSPInstanceProvider : TSPLIBInstanceProvider<PTSPData> {
     30    private static readonly double[] probabilities = new[] { 0.1, 0.2, 0.4, 0.5, 0.6, 0.8, 0.9, 1.0 };
    2831
    2932    public override string Name {
    30       get { return "TSPLIB (symmetric TSP)"; }
     33      get { return "TSPLIB (homogeneous symmetric PTSP)"; }
    3134    }
    3235
     
    3740    protected override string FileExtension { get { return "tsp"; } }
    3841
    39     protected override TSPData LoadInstance(TSPLIBParser parser) {
     42    public override IEnumerable<IDataDescriptor> GetDataDescriptors() {
     43      var tspDescriptors = base.GetDataDescriptors().OfType<TSPLIBDataDescriptor>();
     44      foreach (var desc in tspDescriptors) {
     45        foreach (var p in probabilities) {
     46          yield return new TSPLIBHomogeneousPTSPDataDescriptor(
     47            desc.Name + "-" + p.ToString(CultureInfo.InvariantCulture.NumberFormat),
     48            desc.Description,
     49            desc.InstanceIdentifier,
     50            p == 1.0 ? desc.SolutionIdentifier : null,
     51            p);
     52        }
     53      }
     54    }
     55
     56    protected override PTSPData LoadInstance(TSPLIBParser parser, IDataDescriptor descriptor = null) {
    4057      parser.Parse();
    4158      if (parser.FixedEdges != null) throw new InvalidDataException("TSP instance " + parser.Name + " contains fixed edges which are not supported by HeuristicLab.");
    42       var instance = new TSPData();
     59      var instance = new PTSPData();
    4360      instance.Dimension = parser.Dimension;
    4461      instance.Coordinates = parser.Vertices != null ? parser.Vertices : parser.DisplayVertices;
     
    7390        + Environment.NewLine + Environment.NewLine
    7491        + GetInstanceDescription();
     92      var ptspDesc = descriptor as TSPLIBHomogeneousPTSPDataDescriptor;
     93      instance.Probabilities = ptspDesc != null ? Enumerable.Range(0, instance.Dimension).Select(_ => ptspDesc.Probability).ToArray()
     94                                                : Enumerable.Range(0, instance.Dimension).Select(_ => 0.5).ToArray();
     95
    7596      return instance;
    7697    }
    7798
    78     protected override void LoadSolution(TSPLIBParser parser, TSPData instance) {
     99    protected override void LoadSolution(TSPLIBParser parser, PTSPData instance) {
    79100      parser.Parse();
    80101      instance.BestKnownTour = parser.Tour.FirstOrDefault();
    81102    }
    82103
    83     public TSPData LoadData(string tspFile, string tourFile, double? bestQuality) {
     104    public PTSPData LoadData(string tspFile, string tourFile, double? bestQuality) {
    84105      var data = LoadInstance(new TSPLIBParser(tspFile));
    85106      if (!String.IsNullOrEmpty(tourFile)) {
  • branches/PTSP/HeuristicLab.Problems.Instances.TSPLIB/3.3/TSPLIBInstanceProvider.cs

    r12012 r13412  
    4545    protected abstract string FileExtension { get; }
    4646
    47     protected abstract T LoadInstance(TSPLIBParser parser);
     47    protected abstract T LoadInstance(TSPLIBParser parser, IDataDescriptor descriptor = null);
    4848    protected abstract void LoadSolution(TSPLIBParser parser, T instance);
    4949
     
    7474        var stream = entry.Open();
    7575        var parser = new TSPLIBParser(stream);
    76         var instance = LoadInstance(parser);
     76        var instance = LoadInstance(parser, id);
    7777
    7878        if (!String.IsNullOrEmpty(descriptor.SolutionIdentifier)) {
  • branches/PTSP/HeuristicLab.Problems.Instances.TSPLIB/3.3/TSPLIBTSPInstanceProvider.cs

    r12012 r13412  
    3737    protected override string FileExtension { get { return "tsp"; } }
    3838
    39     protected override TSPData LoadInstance(TSPLIBParser parser) {
     39    protected override TSPData LoadInstance(TSPLIBParser parser, IDataDescriptor descriptor = null) {
    4040      parser.Parse();
    4141      if (parser.FixedEdges != null) throw new InvalidDataException("TSP instance " + parser.Name + " contains fixed edges which are not supported by HeuristicLab.");
  • branches/PTSP/HeuristicLab.Problems.Instances/3.3

    • Property svn:ignore
      •  

        old new  
        33Plugin.cs
        44*.user
         5*.DotSettings
  • branches/PTSP/HeuristicLab.Problems.Instances/3.3/HeuristicLab.Problems.Instances-3.3.csproj

    r12722 r13412  
    1919    <DebugType>full</DebugType>
    2020    <Optimize>false</Optimize>
    21     <OutputPath>..\..\bin\</OutputPath>
     21    <OutputPath>..\..\..\..\trunk\sources\bin\</OutputPath>
    2222    <DefineConstants>DEBUG;TRACE</DefineConstants>
    2323    <ErrorReport>prompt</ErrorReport>
     
    2828    <DebugType>pdbonly</DebugType>
    2929    <Optimize>true</Optimize>
    30     <OutputPath>..\..\bin\</OutputPath>
     30    <OutputPath>..\..\..\..\trunk\sources\bin\</OutputPath>
    3131    <DefineConstants>TRACE</DefineConstants>
    3232    <ErrorReport>prompt</ErrorReport>
     
    4242  <PropertyGroup Condition="'$(Configuration)|$(Platform)' == 'Debug|x64'">
    4343    <DebugSymbols>true</DebugSymbols>
    44     <OutputPath>..\..\bin\</OutputPath>
     44    <OutputPath>..\..\..\..\trunk\sources\bin\</OutputPath>
    4545    <DefineConstants>DEBUG;TRACE</DefineConstants>
    4646    <DebugType>full</DebugType>
     
    5959  </PropertyGroup>
    6060  <PropertyGroup Condition="'$(Configuration)|$(Platform)' == 'Release|x64'">
    61     <OutputPath>..\..\bin\</OutputPath>
     61    <OutputPath>..\..\..\..\trunk\sources\bin\</OutputPath>
    6262    <DefineConstants>TRACE</DefineConstants>
    6363    <Optimize>true</Optimize>
     
    7878  <PropertyGroup Condition="'$(Configuration)|$(Platform)' == 'Debug|x86'">
    7979    <DebugSymbols>true</DebugSymbols>
    80     <OutputPath>..\..\bin\</OutputPath>
     80    <OutputPath>..\..\..\..\trunk\sources\bin\</OutputPath>
    8181    <DefineConstants>DEBUG;TRACE</DefineConstants>
    8282    <DebugType>full</DebugType>
     
    9595  </PropertyGroup>
    9696  <PropertyGroup Condition="'$(Configuration)|$(Platform)' == 'Release|x86'">
    97     <OutputPath>..\..\bin\</OutputPath>
     97    <OutputPath>..\..\..\..\trunk\sources\bin\</OutputPath>
    9898    <DefineConstants>TRACE</DefineConstants>
    9999    <Optimize>true</Optimize>
     
    112112  </PropertyGroup>
    113113  <ItemGroup>
     114    <Reference Include="HeuristicLab.Common-3.3">
     115      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Common-3.3.dll</HintPath>
     116      <Private>False</Private>
     117    </Reference>
     118    <Reference Include="HeuristicLab.PluginInfrastructure-3.3">
     119      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.PluginInfrastructure-3.3.dll</HintPath>
     120      <Private>False</Private>
     121    </Reference>
    114122    <Reference Include="Microsoft.CSharp" />
    115123    <Reference Include="System" />
     
    121129    <Compile Include="ProblemInstanceManager.cs" />
    122130    <Compile Include="IProblemInstanceExporter.cs" />
     131    <Compile Include="Types\PTSPData.cs" />
    123132    <Compile Include="Types\ATSPData.cs" />
    124133    <Compile Include="Types\JSSPData.cs" />
     
    146155  <ItemGroup>
    147156    <None Include="HeuristicLab.snk" />
    148   </ItemGroup>
    149   <ItemGroup>
    150     <ProjectReference Include="..\..\HeuristicLab.Common\3.3\HeuristicLab.Common-3.3.csproj">
    151       <Project>{A9AD58B9-3EF9-4CC1-97E5-8D909039FF5C}</Project>
    152       <Name>HeuristicLab.Common-3.3</Name>
    153       <Private>False</Private>
    154     </ProjectReference>
    155     <ProjectReference Include="..\..\HeuristicLab.PluginInfrastructure\3.3\HeuristicLab.PluginInfrastructure-3.3.csproj">
    156       <Project>{94186A6A-5176-4402-AE83-886557B53CCA}</Project>
    157       <Name>HeuristicLab.PluginInfrastructure-3.3</Name>
    158       <Private>False</Private>
    159     </ProjectReference>
    160157  </ItemGroup>
    161158  <Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" />
  • branches/PTSP/HeuristicLab.Problems.Instances/3.3/Types/DistanceHelper.cs

    r12012 r13412  
    2121
    2222using System;
    23 using System.Collections.Generic;
    24 using System.Linq;
    25 using System.Text;
    2623
    2724namespace HeuristicLab.Problems.Instances {
    2825  public enum DistanceMeasure { Direct, Euclidean, RoundedEuclidean, UpperEuclidean, Geo, Manhattan, Maximum, Att };
    29  
     26
    3027  public static class DistanceHelper {
    3128    /// <summary>
     
    3532    public static double[,] GetDistanceMatrix(DistanceMeasure distanceMeasure, double[,] coordinates, double[,] distances, int dimension) {
    3633      if (distances != null) return distances;
    37      
     34
    3835      distances = new double[dimension, dimension];
    3936      for (int i = 0; i < dimension - 1; i++)
     
    4441
    4542      return distances;
     43    }
     44
     45    public static double GetDistance(DistanceMeasure distanceMeasure, double x1, double y1, double x2, double y2) {
     46      switch (distanceMeasure) {
     47        case DistanceMeasure.Att:
     48          return AttDistance(x1, y1, x2, y2);
     49        case DistanceMeasure.Direct:
     50          throw new ArgumentException("Direct distance measure requires distance matrix for distance calculation.");
     51        case DistanceMeasure.Euclidean:
     52          return EuclideanDistance(x1, y1, x2, y2);
     53        case DistanceMeasure.Geo:
     54          return GeoDistance(x1, y1, x2, y2);
     55        case DistanceMeasure.Manhattan:
     56          return ManhattanDistance(x1, y1, x2, y2);
     57        case DistanceMeasure.Maximum:
     58          return MaximumDistance(x1, y1, x2, y2);
     59        case DistanceMeasure.RoundedEuclidean:
     60          return Math.Round(EuclideanDistance(x1, y1, x2, y2));
     61        case DistanceMeasure.UpperEuclidean:
     62          return Math.Ceiling(EuclideanDistance(x1, y1, x2, y2));
     63        default:
     64          throw new InvalidOperationException("Distance measure is not known.");
     65      }
    4666    }
    4767
  • branches/PTSP/HeuristicLab.Problems.Instances/3.3/Types/PTSPData.cs

    r13408 r13412  
    1 using System;
    2 using System.Collections.Generic;
    3 using System.Linq;
    4 using System.Text;
    5 using HeuristicLab.Problems.Instances;
    6 
    7 namespace HeuristicLab.Problems.PTSP {
     1
     2namespace HeuristicLab.Problems.Instances {
     3  /// <summary>
     4  /// Describes instances of the Probabilistic Traveling Salesman Problem (PTSP).
     5  /// </summary>
    86  public class PTSPData : TSPData {
     7    /// <summary>
     8    /// The probabilities for each of the cities to appear in a route.
     9    /// </summary>
    910    public double[] Probabilities { get; set; }
    1011  }
  • branches/PTSP/HeuristicLab.Problems.PTSP.Tests-3.3/PTSPMoveEvaluatorTest.cs

    r12380 r13412  
    1 using System;
     1#region License Information
     2/* HeuristicLab
     3 * Copyright (C) 2002-2015 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;
    223using HeuristicLab.Common;
    324using HeuristicLab.Core;
     
    627using HeuristicLab.Random;
    728using Microsoft.VisualStudio.TestTools.UnitTesting;
    8 using System.Diagnostics;
    929
    10 namespace HeuristicLab.Problems.PTSP.Tests_3._3 {
     30namespace HeuristicLab.Problems.PTSP.Tests {
    1131  /// <summary>
    1232  ///This is a test class for PTSP move evaluators
     
    1535  public class PTSPMoveEvaluatorTest {
    1636    private const int ProblemSize = 10;
     37    private const int RealizationsSize = 100;
    1738    private static DoubleMatrix coordinates;
    1839    private static DistanceMatrix distances;
    1940    private static Permutation tour;
    2041    private static MersenneTwister random;
    21     private static ItemList<ItemList<IntValue>> realizations;
    22     private static DoubleArray ProbabilityMatrix;
     42    private static ItemList<BoolArray> realizations;
     43    private static DoubleArray probabilities;
    2344
    2445    [ClassInitialize]
     
    2748      coordinates = new DoubleMatrix(ProblemSize, 2);
    2849      distances = new DistanceMatrix(ProblemSize, ProblemSize);
    29       for (int i = 0; i < ProblemSize; i++) {
     50      for (var i = 0; i < ProblemSize; i++) {
    3051        coordinates[i, 0] = random.Next(ProblemSize * 10);
    3152        coordinates[i, 1] = random.Next(ProblemSize * 10);
    3253      }
    33       for (int i = 0; i < ProblemSize - 1; i++) {
    34         for (int j = i + 1; j < ProblemSize; j++) {
     54      for (var i = 0; i < ProblemSize - 1; i++) {
     55        for (var j = i + 1; j < ProblemSize; j++) {
    3556          distances[i, j] = Math.Round(Math.Sqrt(Math.Pow(coordinates[i, 0] - coordinates[j, 0], 2) + Math.Pow(coordinates[i, 1] - coordinates[j, 1], 2)));
    3657          distances[j, i] = distances[i, j];
     
    3859      }
    3960
    40       ProbabilityMatrix = new DoubleArray(ProblemSize);
    41       for (int i = 0; i < ProblemSize; i++) {
    42         ProbabilityMatrix[i] = random.NextDouble();
     61      probabilities = new DoubleArray(ProblemSize);
     62      for (var i = 0; i < ProblemSize; i++) {
     63        probabilities[i] = random.NextDouble();
    4364      }
    4465
    45       int numRealizations = 100;
    46       int countOnes = 0;
    47       realizations = new ItemList<ItemList<IntValue>>(numRealizations);
    48       for (int i = 0; i < numRealizations; i++) {
    49         ItemList<IntValue> newRealization = new ItemList<IntValue>();
     66      realizations = new ItemList<BoolArray>(RealizationsSize);
     67      for (var i = 0; i < RealizationsSize; i++) {
     68        var countOnes = 0;
     69        var newRealization = new BoolArray(ProblemSize);
    5070        while (countOnes < 4) { //only generate realizations with at least 4 cities visited
    5171          countOnes = 0;
    52           newRealization.Clear();
    53           for (int j = 0; j < ProblemSize; j++) {
    54             if (ProbabilityMatrix[j] > random.NextDouble()) {
    55               newRealization.Add(new IntValue(1));
    56               countOnes++;
    57             } else {
    58               newRealization.Add(new IntValue(0));
    59             }
     72          for (var j = 0; j < ProblemSize; j++) {
     73            newRealization[j] = random.NextDouble() < probabilities[j];
     74            if (newRealization[j]) countOnes++;
    6075          }
    6176        }
    62         countOnes = 0;
    6377        realizations.Add(newRealization);
    6478      }
     
    6882
    6983    [TestMethod]
    70     [TestCategory("Problems.TravelingSalesman")]
     84    [TestCategory("Problems.ProbabilisticTravelingSalesman")]
    7185    [TestProperty("Time", "short")]
    7286    public void InversionMoveEvaluatorTest() {
     87      var beforeMatrix = EstimatedProbabilisticTravelingSalesmanProblem.Evaluate(tour, distances, realizations)[0];
    7388
    74       EstimatedProbabilisticTravelingSalesmanProblem ePTSP = new EstimatedProbabilisticTravelingSalesmanProblem();
     89      for (var i = 0; i < 500; i++) {
     90        var move = StochasticInversionSingleMoveGenerator.Apply(tour, random);
     91        var moveMatrix = PTSPEstimatedInversionMoveEvaluator.EvaluateByDistanceMatrix(tour, move, distances, realizations);
     92        InversionManipulator.Apply(tour, move.Index1, move.Index2);
     93        var afterMatrix = EstimatedProbabilisticTravelingSalesmanProblem.Evaluate(tour, distances, realizations)[0];
    7594
    76       double beforeMatrix = ePTSP.EvaluateWithParams(distances, ProbabilityMatrix, realizations, tour)[0];
    77 
    78       for (int i = 0; i < 500; i++) {
    79         var move = StochasticInversionSingleMoveGenerator.Apply(tour, random);
    80 
    81         double moveMatrix = PTSPEstimatedInversionEvaluator.EvaluateByDistanceMatrix(tour, move, distances,realizations);
    82 
    83         string failureString = string.Format(@"Inversion move is calculated with quality {0}, but actual difference is {4}.
    84 The move would invert the tour {1} between values {2} and {3}.", moveMatrix.ToString(), tour.ToString(), tour[move.Index1].ToString(), tour[move.Index2].ToString(), "{0}");
    85 
    86         InversionManipulator.Apply(tour, move.Index1, move.Index2);
    87 
    88         double afterMatrix = ePTSP.EvaluateWithParams(distances, ProbabilityMatrix, realizations, tour)[0];
    89 
    90         Assert.IsTrue(Math.Abs(moveMatrix).IsAlmost(Math.Abs(afterMatrix - beforeMatrix)), string.Format(failureString, (Math.Abs(afterMatrix - beforeMatrix)).ToString()));
     95        Assert.IsTrue(Math.Abs(moveMatrix).IsAlmost(Math.Abs(afterMatrix - beforeMatrix)),
     96          string.Format(@"Inversion move is calculated with quality {0}, but actual difference is {4}.
     97The move would invert the tour {1} between values {2} and {3}.",
     98          moveMatrix, tour, tour[move.Index1], tour[move.Index2], Math.Abs(afterMatrix - beforeMatrix)));
    9199
    92100        beforeMatrix = afterMatrix;
     
    95103
    96104    [TestMethod]
    97     [TestCategory("Problems.TravelingSalesman")]
     105    [TestCategory("Problems.ProbabilisticTravelingSalesman")]
    98106    [TestProperty("Time", "short")]
    99107    public void InsertionMoveEvaluatorTest() {
     108      var beforeMatrix = EstimatedProbabilisticTravelingSalesmanProblem.Evaluate(tour, distances, realizations)[0];
    100109
    101       EstimatedProbabilisticTravelingSalesmanProblem ePTSP = new EstimatedProbabilisticTravelingSalesmanProblem();
     110      for (var i = 0; i < 500; i++) {
     111        var move = StochasticTranslocationSingleMoveGenerator.Apply(tour, random);
     112        var moveMatrix = PTSPEstimatedInsertionMoveEvaluator.EvaluateByDistanceMatrix(tour, move, distances, realizations);
     113        TranslocationManipulator.Apply(tour, move.Index1, move.Index1, move.Index3);
     114        var afterMatrix = EstimatedProbabilisticTravelingSalesmanProblem.Evaluate(tour, distances, realizations)[0];
    102115
    103       double beforeMatrix = ePTSP.EvaluateWithParams(distances, ProbabilityMatrix, realizations, tour)[0];
    104 
    105       for (int i = 0; i < 500; i++) {
    106         var move = StochasticTranslocationSingleMoveGenerator.Apply(tour, random);
    107 
    108         double moveMatrix = PTSPEstimatedInsertionEvaluator.EvaluateByDistanceMatrix(tour, move, distances, realizations);
    109 
    110         string failureString = string.Format(@"Inversion move is calculated with quality {0}, but actual difference is {4}.
    111 The move would invert the tour {1} between values {2} and {3}.", moveMatrix.ToString(), tour.ToString(), tour[move.Index1].ToString(), tour[move.Index2].ToString(), "{0}");
    112 
    113         TranslocationManipulator.Apply(tour, move.Index1, move.Index1, move.Index3);
    114 
    115         double afterMatrix = ePTSP.EvaluateWithParams(distances, ProbabilityMatrix, realizations, tour)[0];
    116 
    117         Assert.IsTrue(Math.Abs(moveMatrix).IsAlmost(Math.Abs(afterMatrix - beforeMatrix)), string.Format(failureString, (Math.Abs(afterMatrix - beforeMatrix)).ToString()));
     116        Assert.IsTrue(Math.Abs(moveMatrix).IsAlmost(Math.Abs(afterMatrix - beforeMatrix)),
     117          string.Format(@"Insertion move is calculated with quality {0}, but actual difference is {4}.
     118The move would invert the tour {1} between values {2} and {3}.",
     119          moveMatrix, tour, tour[move.Index1], tour[move.Index2], Math.Abs(afterMatrix - beforeMatrix)));
    118120
    119121        beforeMatrix = afterMatrix;
     
    122124
    123125    [TestMethod]
    124     [TestCategory("Problems.TravelingSalesman")]
     126    [TestCategory("Problems.ProbabilisticTravelingSalesman")]
    125127    [TestProperty("Time", "short")]
    126128    public void AnalyticalTest() {
    127       for (int i = 0; i < 10; i++) {
    128         tour = new Permutation(PermutationTypes.RelativeUndirected, ProblemSize, random);
    129         EstimatedProbabilisticTravelingSalesmanProblem ePTSP = new EstimatedProbabilisticTravelingSalesmanProblem();
    130         double estimated = ePTSP.EvaluateWithParams(distances, ProbabilityMatrix, realizations, tour)[0];
     129      for (var i = 0; i < 10; i++) {
     130        var perm = new Permutation(PermutationTypes.RelativeUndirected, ProblemSize, random);
     131        var estimated = EstimatedProbabilisticTravelingSalesmanProblem.Evaluate(perm, distances, realizations)[0];
    131132
    132         AnalyticalProbabilisticTravelingSalesmanProblem aPTSP = new AnalyticalProbabilisticTravelingSalesmanProblem();
    133         double analytical = aPTSP.EvaluateWithParams(distances, ProbabilityMatrix, tour);
    134         Console.WriteLine(Math.Abs(analytical-estimated));
     133        var analytical = AnalyticalProbabilisticTravelingSalesmanProblem.Evaluate(perm, distances, probabilities);
     134        Console.WriteLine(Math.Abs(analytical - estimated));
    135135      }
    136136    }
  • branches/PTSP/HeuristicLab.Problems.PTSP.Views/3.3/HeuristicLab.Problems.PTSP.Views-3.3.csproj

    r13202 r13412  
    8484      <Private>False</Private>
    8585    </Reference>
     86    <Reference Include="HeuristicLab.Random-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     87      <SpecificVersion>False</SpecificVersion>
     88      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Random-3.3.dll</HintPath>
     89      <Private>False</Private>
     90    </Reference>
    8691    <Reference Include="System" />
    8792    <Reference Include="System.Core" />
  • branches/PTSP/HeuristicLab.Problems.PTSP.Views/3.3/PathPTSPTourView.cs

    r12306 r13412  
    2222using System;
    2323using System.Drawing;
    24 using System.Windows.Forms;
    2524using HeuristicLab.Core.Views;
    2625using HeuristicLab.Data;
     
    156155      }
    157156    }
    158 
    159157    private void Content_ProbabilitiesChanged(object sender, EventArgs e) {
    160158      if (InvokeRequired)
  • branches/PTSP/HeuristicLab.Problems.PTSP.Views/3.3/Plugin.cs.frame

    r12317 r13412  
    1 using HeuristicLab.PluginInfrastructure;
     1#region License Information
     2/* HeuristicLab
     3 * Copyright (C) 2002-2015 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 HeuristicLab.PluginInfrastructure;
     23
    224namespace HeuristicLab.Problems.PTSP.Views {
    3     [Plugin("HeuristicLab.Problems.PTSP.Views", "3.3.11.$WCREV$")]
    4     [PluginFile("HeuristicLab.Problems.PTSP.Views-3.3.dll", PluginFileType.Assembly)]
    5   [PluginDependency("HeuristicLab.Common", "3.3")]
    6   [PluginDependency("HeuristicLab.Core", "3.3")]
    7   [PluginDependency("HeuristicLab.Core.Views", "3.3")]
    8   [PluginDependency("HeuristicLab.Data", "3.3")]
    9   [PluginDependency("HeuristicLab.Encodings.PermutationEncoding", "3.3")]
    10   [PluginDependency("HeuristicLab.MainForm", "3.3")]
    11   [PluginDependency("HeuristicLab.MainForm.WindowsForms", "3.3")]
    12   [PluginDependency("HeuristicLab.Optimization", "3.3")]
    13   [PluginDependency("HeuristicLab.Optimization.Views", "3.3")]
    14   [PluginDependency("HeuristicLab.Parameters", "3.3")]
    15   [PluginDependency("HeuristicLab.Problems.PTSP", "3.3")]
    16     public class Plugin : PluginBase {
    17     }
     25  [Plugin("HeuristicLab.Problems.PTSP.Views", "3.3.13.$WCREV$")]
     26  [PluginFile("HeuristicLab.Problems.PTSP.Views-3.3.dll", PluginFileType.Assembly)]
     27  [PluginDependency("HeuristicLab.Common", "3.3")]
     28  [PluginDependency("HeuristicLab.Core", "3.3")]
     29  [PluginDependency("HeuristicLab.Core.Views", "3.3")]
     30  [PluginDependency("HeuristicLab.Data", "3.3")]
     31  [PluginDependency("HeuristicLab.Encodings.PermutationEncoding", "3.3")]
     32  [PluginDependency("HeuristicLab.MainForm", "3.3")]
     33  [PluginDependency("HeuristicLab.MainForm.WindowsForms", "3.3")]
     34  [PluginDependency("HeuristicLab.Optimization", "3.3")]
     35  [PluginDependency("HeuristicLab.Optimization.Views", "3.3")]
     36  [PluginDependency("HeuristicLab.Parameters", "3.3")]
     37  [PluginDependency("HeuristicLab.Problems.PTSP", "3.3")]
     38  [PluginDependency("HeuristicLab.Random", "3.3")]
     39  public class HeuristicLabProblemsPTSPViewsPlugin : PluginBase {
     40  }
    1841}
  • branches/PTSP/HeuristicLab.Problems.PTSP.Views/3.3/ProbabilisticTravelingSalesmanProblemView.cs

    r12269 r13412  
    2121
    2222using System;
    23 using System.Windows.Forms;
     23using HeuristicLab.Data;
    2424using HeuristicLab.MainForm;
    2525using HeuristicLab.Optimization.Views;
    26 using HeuristicLab.Problems.PTSP;
    27 using HeuristicLab.Data;
     26using HeuristicLab.Random;
    2827
    2928namespace HeuristicLab.Problems.PTSP.Views {
     
    4039
    4140    /// <summary>
    42     /// Initializes a new instance of <see cref="ProbabilisticTravelingSalesmanView"/>.
     41    /// Initializes a new instance of <see cref="ProbabilisticTravelingSalesmanProblemView"/>.
    4342    /// </summary>
    4443    public ProbabilisticTravelingSalesmanProblemView() {
     
    4746
    4847    protected override void DeregisterContentEvents() {
    49       Content.CoordinatesParameter.ValueChanged -= new EventHandler(CoordinatesParameter_ValueChanged);
    50       Content.ProbabilityMatrixParameter.ValueChanged -= new EventHandler(ProbabilityParameter_ValueChanged);
    51       //Content.BestKnownQualityParameter.ValueChanged -= new EventHandler(BestKnownQualityParameter_ValueChanged);
    52       Content.BestKnownSolutionParameter.ValueChanged -= new EventHandler(BestKnownSolutionParameter_ValueChanged);
     48      Content.CoordinatesParameter.ValueChanged -= CoordinatesParameter_ValueChanged;
     49      Content.ProbabilitiesParameter.ValueChanged -= ProbabilityParameter_ValueChanged;
     50      Content.BestKnownSolutionParameter.ValueChanged -= BestKnownSolutionParameter_ValueChanged;
    5351      base.DeregisterContentEvents();
    5452    }
    5553    protected override void RegisterContentEvents() {
    5654      base.RegisterContentEvents();
    57       Content.CoordinatesParameter.ValueChanged += new EventHandler(CoordinatesParameter_ValueChanged);
    58       Content.ProbabilityMatrixParameter.ValueChanged += new EventHandler(ProbabilityParameter_ValueChanged);
    59       //Content.BestKnownQualityParameter.ValueChanged += new EventHandler(BestKnownQualityParameter_ValueChanged);
    60       Content.BestKnownSolutionParameter.ValueChanged += new EventHandler(BestKnownSolutionParameter_ValueChanged);
     55      Content.CoordinatesParameter.ValueChanged += CoordinatesParameter_ValueChanged;
     56      Content.ProbabilitiesParameter.ValueChanged += ProbabilityParameter_ValueChanged;
     57      Content.BestKnownSolutionParameter.ValueChanged += BestKnownSolutionParameter_ValueChanged;
    6158    }
    6259    protected override void OnContentChanged() {
     
    6562        pathPTSPTourView.Content = null;
    6663      } else {
    67         pathPTSPTourView.Content = new PathPTSPTour(Content.Coordinates, Content.ProbabilityMatrix, Content.BestKnownSolution, new DoubleValue(Content.BestKnownQuality));
     64        pathPTSPTourView.Content = new PathPTSPTour(Content.Coordinates, Content.Probabilities, Content.BestKnownSolution, new DoubleValue(Content.BestKnownQuality));
    6865      }
    6966    }
     
    7774      pathPTSPTourView.Content.Coordinates = Content.Coordinates;
    7875    }
    79 
    8076    private void ProbabilityParameter_ValueChanged(object sender, EventArgs e) {
    81       pathPTSPTourView.Content.Probabilities = Content.ProbabilityMatrix;
    82     }
    83     private void BestKnownQualityParameter_ValueChanged(object sender, EventArgs e) {
    84       pathPTSPTourView.Content.Quality = new DoubleValue(Content.BestKnownQuality);
     77      pathPTSPTourView.Content.Probabilities = Content.Probabilities;
    8578    }
    8679    private void BestKnownSolutionParameter_ValueChanged(object sender, EventArgs e) {
    8780      pathPTSPTourView.Content.Permutation = Content.BestKnownSolution;
     81      pathPTSPTourView.Content.Quality = new DoubleValue(Content.Evaluate(Content.BestKnownSolution, new MersenneTwister()));
    8882    }
    8983  }
  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/AnalyticalPTSP.cs

    r12306 r13412  
    1 using System;
    2 using System.Collections.Generic;
    3 using System.Linq;
    4 using System.Text;
    5 using System.Threading.Tasks;
    6 using HeuristicLab.Optimization;
    7 using HeuristicLab.PluginInfrastructure;
     1#region License Information
     2/* HeuristicLab
     3 * Copyright (C) 2002-2015 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 HeuristicLab.Common;
    823using HeuristicLab.Core;
     24using HeuristicLab.Data;
     25using HeuristicLab.Encodings.PermutationEncoding;
    926using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    10 using HeuristicLab.Problems.Instances;
    11 using HeuristicLab.Encodings.PermutationEncoding;
    12 using HeuristicLab.Common;
    13 using HeuristicLab.Parameters;
    14 using HeuristicLab.Data;
    1527
    1628namespace HeuristicLab.Problems.PTSP {
    17   [Item("Analytical Probabilistic Traveling Salesman Problem", "Represents an analytical Probabilistic Traveling Salesman Problem.")]
    18   [Creatable("Problems")]
     29  [Item("Analytical Probabilistic Traveling Salesman Problem (PTSP)", "Represents a probabilistic traveling salesman problem where the expected tour length is calculated exactly.")]
     30  [Creatable(CreatableAttribute.Categories.CombinatorialProblems)]
    1931  [StorableClass]
    20   public sealed class AnalyticalProbabilisticTravelingSalesmanProblem : ProbabilisticTravelingSalesmanProblem, IStorableContent,
    21   IProblemInstanceConsumer<PTSPData> {
     32  public sealed class AnalyticalProbabilisticTravelingSalesmanProblem : ProbabilisticTravelingSalesmanProblem {
    2233
    2334    [StorableConstructor]
    2435    private AnalyticalProbabilisticTravelingSalesmanProblem(bool deserializing) : base(deserializing) { }
    25     private AnalyticalProbabilisticTravelingSalesmanProblem(AnalyticalProbabilisticTravelingSalesmanProblem original, Cloner cloner)
    26       : base(original, cloner) {
     36    private AnalyticalProbabilisticTravelingSalesmanProblem(AnalyticalProbabilisticTravelingSalesmanProblem original, Cloner cloner) : base(original, cloner) { }
     37    public AnalyticalProbabilisticTravelingSalesmanProblem() {
     38      Operators.Add(new BestPTSPSolutionAnalyzer());
    2739    }
    2840
     
    3143    }
    3244
    33     public override double Evaluate(Individual individual, IRandom random) {
    34       Permutation p = individual.Permutation();
    35       // Compute A and B matrices
    36       DoubleMatrix A = new DoubleMatrix(p.Length, p.Length - 1);
    37       DoubleMatrix B = new DoubleMatrix(p.Length, p.Length - 1);
    38       //for (int i = 0; i < p.Length; i++) {
    39       //  for (int k = 0; k < p.Length - 1; k++) {
    40       //    double firstPartial = 0;
    41       //    for (int r = k; k < p.Length - 1; r++) {
    42       //       double sum0 = DistanceMatrix[p[i],p[i+r]]* ProbabilityMatrix[0, p[i]] * ProbabilityMatrix[0, p[i+r]];
    43       //       for(int s = i+1; s < i+r; s++) {
    44       //         sum0 = sum0 * (1 - ProbabilityMatrix[0, p[s]]);
    45       //       }
    46       //       firstPartial+=sum0;
    47       //    }
    48       //    double secondPartial = 0;
    49       //    for (int r = k; k < p.Length - 1; r++) {
    50       //       double sum1 = DistanceMatrix[p[i-r],p[i]]* ProbabilityMatrix[0, p[i-r]] * ProbabilityMatrix[0, p[i]];
    51       //       for (int s = i + 1; s < p.Length-1; s++) {
    52       //         sum1 = sum1 * (1 - ProbabilityMatrix[0, p[s]]);
    53       //       }
    54       //       for (int t = 1; t < i-1; t++) {
    55       //         sum1 = sum1 * (1 - ProbabilityMatrix[0, p[t]]);
    56       //       }
    57       //       secondPartial+=sum1;
    58       //    }
    59       //    A[i, k] = firstPartial;
    60       //    B[i, k] = secondPartial;
    61       //  }
    62       //}
    63      
     45    public override double Evaluate(Permutation tour, IRandom random) {
    6446      // Analytical evaluation
    6547      double firstSum = 0;
    66       for (int i = 0; i < p.Length - 1; i++) {
    67         for (int j = i + 1; j < p.Length - 1; j++) {
    68           double sum1 = DistanceMatrix[p[i], p[j]] * ProbabilityMatrix[p[i]] * ProbabilityMatrix[p[j]];
     48      for (int i = 0; i < tour.Length - 1; i++) {
     49        for (int j = i + 1; j < tour.Length - 1; j++) {
     50          double sum1 = DistanceMatrix[tour[i], tour[j]] * Probabilities[tour[i]] * Probabilities[tour[j]];
    6951          for (int k = i + 1; k < j; k++) {
    70             sum1 = sum1 * (1 - ProbabilityMatrix[p[k]]);
     52            sum1 = sum1 * (1 - Probabilities[tour[k]]);
    7153          }
    72           A[i, j - 1] = sum1;
    7354          firstSum += sum1;
    7455        }
    7556      }
    7657      double secondSum = 0;
    77       for (int j = 0; j < p.Length - 1; j++) {
     58      for (int j = 0; j < tour.Length - 1; j++) {
    7859        for (int i = 0; i < j; i++) {
    79           double sum2 = DistanceMatrix[p[j], p[i]] * ProbabilityMatrix[p[i]] * ProbabilityMatrix[p[j]];
    80           for (int k = j + 1; k < p.Length - 1; k++) {
    81             sum2 = sum2 * (1 - ProbabilityMatrix[p[k]]);
     60          double sum2 = DistanceMatrix[tour[j], tour[i]] * Probabilities[tour[i]] * Probabilities[tour[j]];
     61          for (int k = j + 1; k < tour.Length - 1; k++) {
     62            sum2 = sum2 * (1 - Probabilities[tour[k]]);
    8263          }
    8364          for (int k = 1; k < i; k++) {
    84             sum2 = sum2 * (1 - ProbabilityMatrix[p[k]]);
     65            sum2 = sum2 * (1 - Probabilities[tour[k]]);
    8566          }
    86           B[i, j] = sum2;
    8767          secondSum += sum2;
    8868        }
    89       }
    90       foreach (var op in Operators.OfType<PTSPAnalyticalInversionMovePathEvaluator>()) {
    91         op.AParameter.Value = A;
    92         op.BParameter.Value = B;
    9369      }
    9470      return firstSum + secondSum;
    9571    }
    9672
    97     public double EvaluateWithParams(DistanceMatrix distances, DoubleArray probabilities, Permutation individual) {
    98       Permutation p = individual;
    99       // Compute A and B matrices
    100       DoubleMatrix A = new DoubleMatrix(p.Length, p.Length - 1);
    101       DoubleMatrix B = new DoubleMatrix(p.Length, p.Length - 1);
     73    public static double Evaluate(Permutation tour, DistanceMatrix distanceMatrix, DoubleArray probabilities) {
    10274      // Analytical evaluation
    103       double firstSum = 0;
    104       for (int i = 0; i < p.Length; i++) {
    105         for (int j = i + 1; j < p.Length; j++) {
    106           double sum1 = distances[p[i], p[j]] * probabilities[p[i]] * probabilities[p[j]];
    107           for (int k = i + 1; k < j; k++) {
    108             sum1 = sum1 * (1 - probabilities[p[k]]);
     75      var firstSum = 0.0;
     76      for (var i = 0; i < tour.Length; i++) {
     77        for (var j = i + 1; j < tour.Length; j++) {
     78          var sum1 = distanceMatrix[tour[i], tour[j]] * probabilities[tour[i]] * probabilities[tour[j]];
     79          for (var k = i + 1; k < j; k++) {
     80            sum1 = sum1 * (1 - probabilities[tour[k]]);
    10981          }
    110           A[i, j - 1] = sum1;
    11182          firstSum += sum1;
    11283        }
    11384      }
    114       double secondSum = 0;
    115       for (int j = 0; j < p.Length; j++) {
    116         for (int i = 0; i < j; i++) {
    117           double sum2 = distances[p[j], p[i]] * probabilities[p[i]] * probabilities[p[j]];
    118           for (int k = j + 1; k < p.Length; k++) {
    119             sum2 = sum2 * (1 - probabilities[p[k]]);
     85      var secondSum = 0.0;
     86      for (var j = 0; j < tour.Length; j++) {
     87        for (var i = 0; i < j; i++) {
     88          var sum2 = distanceMatrix[tour[j], tour[i]] * probabilities[tour[i]] * probabilities[tour[j]];
     89          for (var k = j + 1; k < tour.Length; k++) {
     90            sum2 = sum2 * (1 - probabilities[tour[k]]);
    12091          }
    121           for (int k = 0; k < i; k++) {
    122             sum2 = sum2 * (1 - probabilities[p[k]]);
     92          for (var k = 0; k < i; k++) {
     93            sum2 = sum2 * (1 - probabilities[tour[k]]);
    12394          }
    124           B[j,i] = sum2;
    12595          secondSum += sum2;
    12696        }
    12797      }
    128       foreach (var op in Operators.OfType<PTSPAnalyticalInversionMovePathEvaluator>()) {
    129         op.AParameter.Value = A;
    130         op.BParameter.Value = B;
    131       }
    13298      return firstSum + secondSum;
    13399    }
    134 
    135     public AnalyticalProbabilisticTravelingSalesmanProblem() {
    136       Operators.Add(new PTSPAnalyticalInversionMovePathEvaluator());
    137     }
    138 
    139     public override void Load(PTSPData data) {
    140       base.Load(data);
    141       foreach (var op in Operators.OfType<PTSPAnalyticalInversionMovePathEvaluator>()) {
    142         op.ProbabilitiesParameter.Value = ProbabilityMatrix;
    143       }
    144     }
    145 
    146100  }
    147101}
  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Analyzers/BestPTSPSolutionAnalyzer.cs

    r12799 r13412  
    3232namespace HeuristicLab.Problems.PTSP {
    3333  /// <summary>
    34   /// An operator for analyzing the best solution of Traveling Salesman Problems given in path representation using city coordinates.
     34  /// An operator for analyzing the best solution of probabilistic traveling salesman problems given in path representation.
    3535  /// </summary>
    3636  [Item("BestPTSPSolutionAnalyzer", "An operator for analyzing the best solution of Probabilistic Traveling Salesman Problems given in path representation using city coordinates.")]
     
    4141    }
    4242
    43     public LookupParameter<BoolValue> MaximizationParameter {
    44       get { return (LookupParameter<BoolValue>)Parameters["Maximization"]; }
     43    public ILookupParameter<BoolValue> MaximizationParameter {
     44      get { return (ILookupParameter<BoolValue>)Parameters["Maximization"]; }
    4545    }
    46     public LookupParameter<DoubleMatrix> CoordinatesParameter {
    47       get { return (LookupParameter<DoubleMatrix>)Parameters["Coordinates"]; }
     46    public ILookupParameter<DoubleMatrix> CoordinatesParameter {
     47      get { return (ILookupParameter<DoubleMatrix>)Parameters["Coordinates"]; }
    4848    }
    49     public ScopeTreeLookupParameter<Permutation> PermutationParameter {
    50       get { return (ScopeTreeLookupParameter<Permutation>)Parameters["Permutation"]; }
     49    public IScopeTreeLookupParameter<Permutation> PermutationParameter {
     50      get { return (IScopeTreeLookupParameter<Permutation>)Parameters["Permutation"]; }
    5151    }
    52     public ScopeTreeLookupParameter<DoubleValue> QualityParameter {
    53       get { return (ScopeTreeLookupParameter<DoubleValue>)Parameters["Quality"]; }
     52    public IScopeTreeLookupParameter<DoubleValue> QualityParameter {
     53      get { return (IScopeTreeLookupParameter<DoubleValue>)Parameters["Quality"]; }
    5454    }
    55     public LookupParameter<DoubleArray> ProbabilityMatrixParameter {
    56       get { return (LookupParameter<DoubleArray>)Parameters["ProbabilityMatrix"]; }
     55    public ILookupParameter<DoubleArray> ProbabilitiesParameter {
     56      get { return (ILookupParameter<DoubleArray>)Parameters["Probabilities"]; }
    5757    }
    58     public LookupParameter<PathPTSPTour> BestSolutionParameter {
    59       get { return (LookupParameter<PathPTSPTour>)Parameters["BestSolution"]; }
     58    public ILookupParameter<PathPTSPTour> BestSolutionParameter {
     59      get { return (ILookupParameter<PathPTSPTour>)Parameters["BestSolution"]; }
    6060    }
    61     public ValueLookupParameter<ResultCollection> ResultsParameter {
    62       get { return (ValueLookupParameter<ResultCollection>)Parameters["Results"]; }
     61    public IValueLookupParameter<ResultCollection> ResultsParameter {
     62      get { return (IValueLookupParameter<ResultCollection>)Parameters["Results"]; }
    6363    }
    64     public LookupParameter<DoubleValue> BestKnownQualityParameter {
    65       get { return (LookupParameter<DoubleValue>)Parameters["BestKnownQuality"]; }
     64    public ILookupParameter<DoubleValue> BestKnownQualityParameter {
     65      get { return (ILookupParameter<DoubleValue>)Parameters["BestKnownQuality"]; }
    6666    }
    67     public LookupParameter<Permutation> BestKnownSolutionParameter {
    68       get { return (LookupParameter<Permutation>)Parameters["BestKnownSolution"]; }
     67    public ILookupParameter<Permutation> BestKnownSolutionParameter {
     68      get { return (ILookupParameter<Permutation>)Parameters["BestKnownSolution"]; }
    6969    }
    7070
     
    8181      Parameters.Add(new ScopeTreeLookupParameter<Permutation>("Permutation", "The PTSP solutions given in path representation from which the best solution should be analyzed."));
    8282      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("Quality", "The qualities of the PTSP solutions which should be analyzed."));
    83       Parameters.Add(new LookupParameter<DoubleArray>("ProbabilityMatrix", "The matrix which contains the probabilities of each of the cities."));
     83      Parameters.Add(new LookupParameter<DoubleArray>("Probabilities", "This list describes for each city the probability of appearing in a realized instance."));
    8484      Parameters.Add(new LookupParameter<PathPTSPTour>("BestSolution", "The best PTSP solution."));
    8585      Parameters.Add(new ValueLookupParameter<ResultCollection>("Results", "The result collection where the best PTSP solution should be stored."));
    8686      Parameters.Add(new LookupParameter<DoubleValue>("BestKnownQuality", "The quality of the best known solution of this PTSP instance."));
    8787      Parameters.Add(new LookupParameter<Permutation>("BestKnownSolution", "The best known solution of this PTSP instance."));
    88 
    89       MaximizationParameter.Hidden = true;
    90       CoordinatesParameter.Hidden = true;
    91       PermutationParameter.Hidden = true;
    92       QualityParameter.Hidden = true;
    93       ProbabilityMatrixParameter.Hidden = true;
    94       BestSolutionParameter.Hidden = true;
    95       ResultsParameter.Hidden = true;
    96       BestKnownQualityParameter.Hidden = true;
    97       BestKnownSolutionParameter.Hidden = true;
    9888    }
    9989
    10090    public override IOperation Apply() {
    101       DoubleMatrix coordinates = CoordinatesParameter.ActualValue;
    102       ItemArray<Permutation> permutations = PermutationParameter.ActualValue;
    103       ItemArray<DoubleValue> qualities = QualityParameter.ActualValue;
    104       DoubleArray probabilities = ProbabilityMatrixParameter.ActualValue;
    105       ResultCollection results = ResultsParameter.ActualValue;
    106       bool max = MaximizationParameter.ActualValue.Value;
    107       DoubleValue bestKnownQuality = BestKnownQualityParameter.ActualValue;
     91      var coordinates = CoordinatesParameter.ActualValue;
     92      var permutations = PermutationParameter.ActualValue;
     93      var qualities = QualityParameter.ActualValue;
     94      var probabilities = ProbabilitiesParameter.ActualValue;
     95      var results = ResultsParameter.ActualValue;
     96      var max = MaximizationParameter.ActualValue.Value;
     97      var bestKnownQuality = BestKnownQualityParameter.ActualValue;
    10898
    109       int i = -1;
    110       if (!max)
    111         i = qualities.Select((x, index) => new { index, x.Value }).OrderBy(x => x.Value).First().index;
    112       else i = qualities.Select((x, index) => new { index, x.Value }).OrderByDescending(x => x.Value).First().index;
     99      var i = !max ? qualities.Select((x, index) => new { index, x.Value }).OrderBy(x => x.Value).First().index
     100                   : qualities.Select((x, index) => new { index, x.Value }).OrderByDescending(x => x.Value).First().index;
    113101
    114102      if (bestKnownQuality == null ||
     
    119107      }
    120108
    121       PathPTSPTour tour = BestSolutionParameter.ActualValue;
     109      var tour = BestSolutionParameter.ActualValue;
    122110      if (tour == null) {
    123         tour = new PathPTSPTour(coordinates,probabilities, (Permutation)permutations[i].Clone(), new DoubleValue(qualities[i].Value));
     111        tour = new PathPTSPTour(coordinates, probabilities, (Permutation)permutations[i].Clone(), new DoubleValue(qualities[i].Value));
    124112        BestSolutionParameter.ActualValue = tour;
    125113        results.Add(new Result("Best PTSP Solution", tour));
  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/DistanceMatrix.cs

    r12191 r13412  
    1 using System;
     1#region License Information
     2/* HeuristicLab
     3 * Copyright (C) 2002-2015 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;
    223using System.Collections.Generic;
    324using HeuristicLab.Common;
  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/EstimatedPTSP.cs

    r12799 r13412  
    1 using System.Text;
    2 using System.Threading.Tasks;
    3 using HeuristicLab.Optimization;
    4 using HeuristicLab.PluginInfrastructure;
     1#region License Information
     2/* HeuristicLab
     3 * Copyright (C) 2002-2015 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 System.Linq;
     24using HeuristicLab.Common;
    525using HeuristicLab.Core;
     26using HeuristicLab.Data;
     27using HeuristicLab.Encodings.PermutationEncoding;
     28using HeuristicLab.Parameters;
    629using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    730using HeuristicLab.Problems.Instances;
    8 using HeuristicLab.Encodings.PermutationEncoding;
    9 using HeuristicLab.Common;
    10 using HeuristicLab.Parameters;
    11 using HeuristicLab.Data;
    1231using HeuristicLab.Random;
    13 using System;
    14 using System.Linq;
    1532
    1633namespace HeuristicLab.Problems.PTSP {
    17   [Item("Estimated Probabilistic Traveling Salesman Problem", "Represents an estimated Probabilistic Traveling Salesman Problem.")]
    18   [Creatable("Problems")]
     34  [Item("Estimated Probabilistic Traveling Salesman Problem (PTSP)", "Represents a probabilistic traveling salesman problem where the expected tour length is estimated by averaging over the length of tours on a number of, so called, realizations.")]
     35  [Creatable(CreatableAttribute.Categories.CombinatorialProblems)]
    1936  [StorableClass]
    20   public sealed class EstimatedProbabilisticTravelingSalesmanProblem : ProbabilisticTravelingSalesmanProblem, IStorableContent,
    21   IProblemInstanceConsumer<PTSPData> {
    22 
     37  public sealed class EstimatedProbabilisticTravelingSalesmanProblem : ProbabilisticTravelingSalesmanProblem {
    2338
    2439    #region Parameter Properties
    25     public ValueParameter<ItemList<ItemList<IntValue>>> RealizationsParameter {
    26       get { return (ValueParameter<ItemList<ItemList<IntValue>>>)Parameters["Realizations"]; }
    27     }
    28     public ValueParameter<IntValue> RealizationsSizeParameter {
    29       get { return (ValueParameter<IntValue>)Parameters["RealizationsSize"]; }
    30     }
    31 
     40    public IValueParameter<ItemList<BoolArray>> RealizationsParameter {
     41      get { return (IValueParameter<ItemList<BoolArray>>)Parameters["Realizations"]; }
     42    }
     43    public IFixedValueParameter<IntValue> RealizationsSizeParameter {
     44      get { return (IFixedValueParameter<IntValue>)Parameters["RealizationsSize"]; }
     45    }
    3246    #endregion
    3347
    3448    #region Properties
    35     public ItemList<ItemList<IntValue>> Realizations {
     49    public ItemList<BoolArray> Realizations {
    3650      get { return RealizationsParameter.Value; }
    3751      set { RealizationsParameter.Value = value; }
    3852    }
    3953
    40     public IntValue RealizationsSize {
    41       get { return RealizationsSizeParameter.Value; }
    42       set { RealizationsSizeParameter.Value = value; }
     54    public int RealizationsSize {
     55      get { return RealizationsSizeParameter.Value.Value; }
     56      set { RealizationsSizeParameter.Value.Value = value; }
    4357    }
    4458    #endregion
     
    5165    }
    5266    public EstimatedProbabilisticTravelingSalesmanProblem() {
    53       Parameters.Add(new ValueParameter<IntValue>("RealizationsSize", "Size of the sample for the estimation-based evaluation"));
    54       Parameters.Add(new ValueParameter<ItemList<ItemList<IntValue>>>("Realizations", "The concrete..."));
    55 
    56       Operators.RemoveAll(x => x is ISingleObjectiveMoveEvaluator);
    57       Operators.RemoveAll(x => x is IMoveGenerator);
    58       Operators.RemoveAll(x => x is IMoveMaker);
     67      Parameters.Add(new FixedValueParameter<IntValue>("RealizationsSize", "Size of the sample for the estimation-based evaluation", new IntValue(100)));
     68      Parameters.Add(new ValueParameter<ItemList<BoolArray>>("Realizations", "The list of samples drawn from all possible stochastic instances.", new ItemList<BoolArray>()));
    5969
    6070      Operators.Add(new BestPTSPSolutionAnalyzer());
    6171
    62       Operators.Add(new PTSPEstimatedInversionEvaluator());
    63       Operators.Add(new PTSPEstimatedInsertionEvaluator());
     72      Operators.Add(new PTSPEstimatedInversionMoveEvaluator());
     73      Operators.Add(new PTSPEstimatedInsertionMoveEvaluator());
    6474      Operators.Add(new PTSPExhaustiveInversionLocalImprovement());
    6575      Operators.Add(new PTSPExhaustiveInsertionLocalImprovement());
    6676
    67       Operators.Add(new Exhaustive25MoveGenerator());
    68       Operators.Add(new Stochastic25MultiMoveGenerator());
    69       Operators.Add(new Stochastic25SingleMoveGenerator());
     77      Operators.Add(new ExhaustiveTwoPointFiveMoveGenerator());
     78      Operators.Add(new StochasticTwoPointFiveMultiMoveGenerator());
     79      Operators.Add(new StochasticTwoPointFiveSingleMoveGenerator());
    7080      Operators.Add(new TwoPointFiveMoveMaker());
    71       Operators.Add(new PTSP25MoveEvaluator());
     81      Operators.Add(new PTSPTwoPointFiveMoveEvaluator());
    7282
    7383      Encoding.ConfigureOperators(Operators.OfType<IOperator>());
    74       foreach (var twopointfiveMoveOperator in Operators.OfType<I25MoveOperator>()) {
     84      foreach (var twopointfiveMoveOperator in Operators.OfType<ITwoPointFiveMoveOperator>()) {
    7585        twopointfiveMoveOperator.TwoPointFiveMoveParameter.ActualName = "Permutation.TwoPointFiveMove";
    7686      }
    77       RealizationsSize = new IntValue(100);
     87
    7888      RegisterEventHandlers();
    7989    }
     
    8393    }
    8494
    85     public override double Evaluate(Individual individual, IRandom random) {
    86       Permutation p = individual.Permutation();
     95    [StorableHook(HookType.AfterDeserialization)]
     96    private void AfterDeserialization() {
     97      RegisterEventHandlers();
     98    }
     99
     100    private void RegisterEventHandlers() {
     101      RealizationsSizeParameter.Value.ValueChanged += RealizationsSizeParameter_ValueChanged;
     102    }
     103
     104    private void RealizationsSizeParameter_ValueChanged(object sender, EventArgs e) {
     105      UpdateRealizations();
     106    }
     107
     108    public override double Evaluate(Permutation tour, IRandom random) {
    87109      // Estimation-based evaluation
    88       MersenneTwister r = new MersenneTwister();
    89       double estimatedSum = 0;
    90       for (int i = 0; i < Realizations.Count; i++) {
     110      var estimatedSum = 0.0;
     111      for (var i = 0; i < Realizations.Count; i++) {
    91112        int singleRealization = -1, firstNode = -1;
    92         for (int j = 0; j < Realizations[i].Count; j++) {
    93           if (Realizations[i][p[j]].Value == 1) {
     113        for (var j = 0; j < Realizations[i].Length; j++) {
     114          if (Realizations[i][tour[j]]) {
    94115            if (singleRealization != -1) {
    95               estimatedSum += DistanceMatrix[singleRealization, p[j]];
     116              estimatedSum += GetDistance(singleRealization, tour[j]);
    96117            } else {
    97               firstNode = p[j];
     118              firstNode = tour[j];
    98119            }
    99             singleRealization = p[j];
     120            singleRealization = tour[j];
    100121          }
    101122        }
    102123        if (singleRealization != -1) {
    103           estimatedSum += DistanceMatrix[singleRealization, firstNode];
    104         }
    105       }
    106       return estimatedSum / RealizationsSize.Value;
    107     }
    108 
    109     public double[] EvaluateWithParams(DistanceMatrix distances, DoubleArray probabilities, ItemList<ItemList<IntValue>> realizations, Permutation individual ) {
     124          estimatedSum += GetDistance(singleRealization, firstNode);
     125        }
     126      }
     127      return estimatedSum / RealizationsSize;
     128    }
     129
     130    /// <summary>
     131    /// An evaluate method that can be used if mean as well as variance should be calculated
     132    /// </summary>
     133    /// <param name="tour">The tour between all cities.</param>
     134    /// <param name="distanceMatrix">The distances between the cities.</param>
     135    /// <param name="realizations">A sample of realizations of the stochastic instance</param>
     136    /// <returns>A vector with length two containing mean and variance.</returns>
     137    public static double[] Evaluate(Permutation tour, DistanceMatrix distanceMatrix, ItemList<BoolArray> realizations) {
    110138      // Estimation-based evaluation
    111       MersenneTwister r = new MersenneTwister();
    112       double estimatedSum = 0;
    113       double[] partialSums = new double[realizations.Count];
    114       for (int i = 0; i < realizations.Count; i++) {
     139      var estimatedSum = 0.0;
     140      var partialSums = new double[realizations.Count];
     141      for (var i = 0; i < realizations.Count; i++) {
    115142        partialSums[i] = 0;
    116143        int singleRealization = -1, firstNode = -1;
    117         for (int j = 0; j < realizations[i].Count; j++) {
    118           if (realizations[i][individual[j]].Value == 1) {
     144        for (var j = 0; j < realizations[i].Length; j++) {
     145          if (realizations[i][tour[j]]) {
    119146            if (singleRealization != -1) {
    120               partialSums[i] += distances[singleRealization, individual[j]];
     147              partialSums[i] += distanceMatrix[singleRealization, tour[j]];
    121148            } else {
    122               firstNode = individual[j];
     149              firstNode = tour[j];
    123150            }
    124             singleRealization = individual[j];
     151            singleRealization = tour[j];
    125152          }
    126153        }
    127154        if (singleRealization != -1) {
    128           partialSums[i] += distances[singleRealization, firstNode];
     155          partialSums[i] += distanceMatrix[singleRealization, firstNode];
    129156        }
    130157        estimatedSum += partialSums[i];
    131158      }
    132       double mean = estimatedSum / realizations.Count;
    133       double variance = 0;
    134       for (int i = 0; i < realizations.Count; i++) {
     159      var mean = estimatedSum / realizations.Count;
     160      var variance = 0.0;
     161      for (var i = 0; i < realizations.Count; i++) {
    135162        variance += Math.Pow((partialSums[i] - mean), 2);
    136163      }
    137164      variance = variance / realizations.Count;
    138       return new double[] {mean,variance};
    139     }
    140 
    141    
    142 
    143     private void RegisterEventHandlers() {
    144       //RealizationsSizeParameter.ValueChanged += new EventHandler(RealizationsSizeParameter_ValueChanged);
    145       RealizationsSize.ValueChanged += new EventHandler(RealizationsSizeParameter_ValueChanged);
    146       //RealizationsSizeParameter.Value.ValueChanged += new EventHandler(RealizationsSizeParameter_ValueChanged);
    147     }
    148 
    149     private void RealizationsSizeParameter_ValueChanged(object sender, EventArgs e) {
    150       UpdateRealizations();
     165      return new[] { mean, variance };
     166    }
     167
     168    public double GetDistance(int from, int to) {
     169      if (UseDistanceMatrix) return DistanceMatrix[from, to];
     170      return DistanceCalculator.Calculate(from, to, Coordinates);
    151171    }
    152172
    153173    private void UpdateRealizations() {
    154       MersenneTwister r = new MersenneTwister();
    155       int countOnes = 0;
    156       Realizations = new ItemList<ItemList<IntValue>>(RealizationsSize.Value);
    157       for (int i = 0; i < RealizationsSize.Value; i++) {
    158         ItemList<IntValue> newRealization = new ItemList<IntValue>();
    159         while (countOnes < 4) { //only generate realizations with at least 4 cities visited
     174      var realizations = new ItemList<BoolArray>(RealizationsSize);
     175      var rand = new MersenneTwister();
     176      for (var i = 0; i < RealizationsSize; i++) {
     177        var newRealization = new BoolArray(Probabilities.Length);
     178        var countOnes = 0;
     179        while (countOnes < 4) { // only generate realizations with at least 4 cities visited
    160180          countOnes = 0;
    161           newRealization.Clear();
    162           for (int j = 0; j < DistanceMatrix.Rows; j++) {
    163             if (ProbabilityMatrix[j] > r.NextDouble()) {
    164               newRealization.Add(new IntValue(1));
    165               countOnes++;
    166             } else {
    167               newRealization.Add(new IntValue(0));
    168             }
     181          for (var j = 0; j < Probabilities.Length; j++) {
     182            newRealization[j] = Probabilities[j] < rand.NextDouble();
     183            if (newRealization[j]) countOnes++;
    169184          }
    170185        }
    171         countOnes = 0;
    172186        Realizations.Add(newRealization);
    173187      }
     188      Realizations = realizations;
    174189    }
    175190
     
    178193      UpdateRealizations();
    179194
    180       foreach (var op in Operators.OfType<PTSPMoveEvaluator>()) {
    181         op.RealizationsParameter.Value = Realizations;
    182       }
    183       foreach (var op in Operators.OfType<PTSPExhaustiveInversionLocalImprovement>()) {
    184         op.RealizationsParameter.Value = Realizations;
    185       }
    186       foreach (var op in Operators.OfType<PTSP25MoveEvaluator>()) {
    187         op.RealizationsParameter.Value = Realizations;
    188       }
    189 
     195      foreach (var op in Operators.OfType<IEstimatedPTSPOperator>()) {
     196        op.RealizationsParameter.ActualName = RealizationsParameter.Name;
     197      }
    190198    }
    191199  }
  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/HeuristicLab.Problems.PTSP-3.3.csproj

    r13202 r13412  
    9393      <Private>False</Private>
    9494    </Reference>
    95     <Reference Include="HeuristicLab.Problems.Instances-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
    96       <SpecificVersion>False</SpecificVersion>
    97       <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Problems.Instances-3.3.dll</HintPath>
    98       <Private>False</Private>
    99     </Reference>
    100     <Reference Include="HeuristicLab.Problems.Instances.TSPLIB-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
    101       <SpecificVersion>False</SpecificVersion>
    102       <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Problems.Instances.TSPLIB-3.3.dll</HintPath>
    103       <Private>False</Private>
    104     </Reference>
    10595    <Reference Include="HeuristicLab.Random-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
    10696      <SpecificVersion>False</SpecificVersion>
    10797      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Random-3.3.dll</HintPath>
     98      <Private>False</Private>
    10899    </Reference>
    109100    <Reference Include="System" />
     
    118109  </ItemGroup>
    119110  <ItemGroup>
    120     <Compile Include="PTSPData.cs" />
    121     <Compile Include="PTSPLIBInstanceProvider.cs" />
    122111    <None Include="Properties\AssemblyInfo.cs.frame" />
    123112    <None Include="Plugin.cs.frame" />
    124113    <Compile Include="AnalyticalPTSP.cs" />
    125114    <Compile Include="Analyzers\BestPTSPSolutionAnalyzer.cs" />
     115    <Compile Include="DistanceCalculators\MaximumDistance.cs" />
     116    <Compile Include="DistanceCalculators\ManhattanDistance.cs" />
     117    <Compile Include="DistanceCalculators\GeoDistance.cs" />
     118    <Compile Include="DistanceCalculators\DistanceCalculator.cs" />
     119    <Compile Include="DistanceCalculators\AttDistance.cs" />
     120    <Compile Include="DistanceCalculators\UpperEuclideanDistance.cs" />
     121    <Compile Include="DistanceCalculators\RoundedEuclideanDistance.cs" />
     122    <Compile Include="DistanceCalculators\EuclideanDistance.cs" />
    126123    <Compile Include="DistanceMatrix.cs" />
    127124    <Compile Include="EstimatedPTSP.cs" />
    128125    <Compile Include="Improvers\PTSPExhaustiveInsertionLocalImprovement.cs" />
    129126    <Compile Include="Improvers\PTSPExhaustiveInversionLocalImprovement.cs" />
    130     <Compile Include="Interfaces\I25MoveOperator.cs" />
    131     <Compile Include="Interfaces\IPTSPMoveEvaluator.cs" />
    132     <Compile Include="MoveEvaluators\OneShift\PTSPEstimatedInsertionEvaluator.cs" />
    133     <Compile Include="MoveEvaluators\PTSPMoveEvaluator.cs" />
    134     <Compile Include="MoveEvaluators\TwoOpt\PTSPAnalyticalInversionMovePathEvaluator.cs" />
    135     <Compile Include="MoveEvaluators\TwoOpt\PTSPEstimatedInversionEvaluator.cs" />
    136     <Compile Include="MoveEvaluators\TwoPointFiveOpt\PTSP25MoveEvaluator.cs" />
    137     <Compile Include="MoveGenerators\Exhaustive25MoveGenerator.cs" />
    138     <Compile Include="MoveGenerators\Stochastic25MultiMoveGenerator.cs" />
    139     <Compile Include="MoveGenerators\Stochastic25SingleMoveGenerator.cs" />
    140     <Compile Include="MoveGenerators\TwoPointFiveMoveGenerator.cs" />
    141     <Compile Include="MoveMakers\TwoPointFiveMoveMaker.cs" />
     127    <Compile Include="Interfaces\IEstimatedPTSPOperator.cs" />
     128    <Compile Include="Interfaces\ITwoPointFiveMoveOperator.cs" />
     129    <Compile Include="Interfaces\IEstimatedPTSPMoveEvaluator.cs" />
     130    <Compile Include="Moves\OneShift\PTSPEstimatedInsertionMoveEvaluator.cs" />
     131    <Compile Include="Moves\EstimatedPTSPMoveEvaluator.cs" />
     132    <Compile Include="Moves\TwoOpt\PTSPEstimatedInversionMoveEvaluator.cs" />
     133    <Compile Include="Moves\TwoPointFiveOpt\PTSPTwoPointFiveMoveEvaluator.cs" />
     134    <Compile Include="Moves\TwoPointFiveOpt\ExhaustiveTwoPointFiveMoveGenerator.cs" />
     135    <Compile Include="Moves\TwoPointFiveOpt\StochasticTwoPointFiveMultiMoveGenerator.cs" />
     136    <Compile Include="Moves\TwoPointFiveOpt\StochasticTwoPointFiveSingleMoveGenerator.cs" />
     137    <Compile Include="Moves\TwoPointFiveOpt\TwoPointFiveMoveGenerator.cs" />
     138    <Compile Include="Moves\TwoPointFiveOpt\TwoPointFiveMoveMaker.cs" />
    142139    <Compile Include="Moves\TwoPointFiveOpt\TwoPointFiveMove.cs" />
    143140    <Compile Include="PathPTSPTour.cs" />
     
    149146    <None Include="HeuristicLab.snk" />
    150147  </ItemGroup>
    151   <ItemGroup />
     148  <ItemGroup>
     149    <ProjectReference Include="..\..\HeuristicLab.Problems.Instances\3.3\HeuristicLab.Problems.Instances-3.3.csproj">
     150      <Project>{3540e29e-4793-49e7-8ee2-fea7f61c3994}</Project>
     151      <Name>HeuristicLab.Problems.Instances-3.3</Name>
     152      <Private>False</Private>
     153    </ProjectReference>
     154  </ItemGroup>
    152155  <Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" />
    153156  <PropertyGroup>
  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Improvers/PTSPExhaustiveInsertionLocalImprovement.cs

    r12261 r13412  
    2121
    2222using System;
     23using System.Threading;
    2324using HeuristicLab.Common;
    2425using HeuristicLab.Core;
     
    2930using HeuristicLab.Parameters;
    3031using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    31 using System.Threading;
    3232
    3333namespace HeuristicLab.Problems.PTSP {
     
    3636  /// </summary>
    3737  /// <remarks>
    38   /// The operator tries to improve the probabilistic traveling salesman solution by swapping two randomly chosen edges for a certain number of times.
     38  /// The operator tries to improve the probabilistic traveling salesman solution by inserting a city in the tour between two other cities for a certain number of times.
    3939  /// </remarks>
    4040  [Item("PTSPExhaustiveInsertionLocalImprovement", "An operator that improves probabilistic traveling salesman solutions. The operator tries to improve the probabilistic traveling salesman solution by swapping two randomly chosen edges for a certain number of times.")]
    4141  [StorableClass]
    42   public sealed class PTSPExhaustiveInsertionLocalImprovement : SingleSuccessorOperator, ILocalImprovementOperator {
    43  
     42  public sealed class PTSPExhaustiveInsertionLocalImprovement : SingleSuccessorOperator, IEstimatedPTSPOperator, ILocalImprovementOperator {
     43
    4444    public ILookupParameter<IntValue> LocalIterationsParameter {
    4545      get { return (ILookupParameter<IntValue>)Parameters["LocalIterations"]; }
     
    7474    }
    7575
    76     public IValueParameter<ItemList<ItemList<IntValue>>> RealizationsParameter {
    77       get { return (IValueParameter<ItemList<ItemList<IntValue>>>)Parameters["Realizations"]; }
     76    public ILookupParameter<ItemList<BoolArray>> RealizationsParameter {
     77      get { return (ILookupParameter<ItemList<BoolArray>>)Parameters["Realizations"]; }
    7878    }
    7979
    8080    [StorableConstructor]
    81     protected PTSPExhaustiveInsertionLocalImprovement(bool deserializing) : base(deserializing) { }
    82     protected PTSPExhaustiveInsertionLocalImprovement(PTSPExhaustiveInsertionLocalImprovement original, Cloner cloner)
    83       : base(original, cloner) {
    84     }
     81    private PTSPExhaustiveInsertionLocalImprovement(bool deserializing) : base(deserializing) { }
     82    private PTSPExhaustiveInsertionLocalImprovement(PTSPExhaustiveInsertionLocalImprovement original, Cloner cloner) : base(original, cloner) { }
    8583    public PTSPExhaustiveInsertionLocalImprovement()
    8684      : base() {
     
    9391      Parameters.Add(new LookupParameter<BoolValue>("Maximization", "True if the problem should be maximized or minimized."));
    9492      Parameters.Add(new LookupParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
    95       Parameters.Add(new ValueParameter<ItemList<ItemList<IntValue>>>("Realizations", "The concrete..."));
     93      Parameters.Add(new LookupParameter<ItemList<BoolArray>>("Realizations", "The list of samples drawn from all possible stochastic instances."));
    9694    }
    9795
     
    10098    }
    10199
    102     public static void Improve(Permutation assignment, DoubleMatrix distances, DoubleValue quality, IntValue localIterations, IntValue evaluatedSolutions, bool maximization, int maxIterations, CancellationToken cancellation, ItemList<ItemList<IntValue>> realizations) {
    103       DistanceMatrix distanceM = (DistanceMatrix)distances;
    104       for (int i = localIterations.Value; i < maxIterations; i++) {
     100    public static void Improve(Permutation assignment, DoubleMatrix distances, DoubleValue quality, IntValue localIterations, IntValue evaluatedSolutions, bool maximization, int maxIterations, CancellationToken cancellation, ItemList<BoolArray> realizations) {
     101      var distanceM = (DistanceMatrix)distances;
     102      for (var i = localIterations.Value; i < maxIterations; i++) {
    105103        TranslocationMove bestMove = null;
    106104        double bestQuality = 0; // we have to make an improvement, so 0 is the baseline
    107105        double evaluations = 0.0;
    108106        foreach (var move in ExhaustiveInsertionMoveGenerator.Generate(assignment)) {
    109           double moveQuality = PTSPEstimatedInsertionEvaluator.EvaluateByDistanceMatrix(assignment, move, distanceM, realizations);
     107          double moveQuality = PTSPEstimatedInsertionMoveEvaluator.EvaluateByDistanceMatrix(assignment, move, distanceM, realizations);
    110108          int min = Math.Min(move.Index1, move.Index3);
    111109          int max = Math.Max(move.Index2, move.Index3 + (move.Index2 - move.Index1));
     
    135133      var localIterations = LocalIterationsParameter.ActualValue;
    136134      var evaluations = EvaluatedSolutionsParameter.ActualValue;
    137       var realizations = RealizationsParameter.Value;
     135      var realizations = RealizationsParameter.ActualValue;
    138136      if (localIterations == null) {
    139137        localIterations = new IntValue(0);
  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Improvers/PTSPExhaustiveInversionLocalImprovement.cs

    r12380 r13412  
    2121
    2222using System;
     23using System.Threading;
    2324using HeuristicLab.Common;
    2425using HeuristicLab.Core;
     
    2930using HeuristicLab.Parameters;
    3031using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    31 using System.Threading;
    3232
    3333namespace HeuristicLab.Problems.PTSP {
     
    4040  [Item("PTSPExhaustiveInversionLocalImprovement", "An operator that improves probabilistic traveling salesman solutions. The operator tries to improve the probabilistic traveling salesman solution by swapping two randomly chosen edges for a certain number of times.")]
    4141  [StorableClass]
    42   public sealed class PTSPExhaustiveInversionLocalImprovement : SingleSuccessorOperator, ILocalImprovementOperator {
    43  
     42  public sealed class PTSPExhaustiveInversionLocalImprovement : SingleSuccessorOperator, IEstimatedPTSPOperator, ILocalImprovementOperator {
     43
    4444    public ILookupParameter<IntValue> LocalIterationsParameter {
    4545      get { return (ILookupParameter<IntValue>)Parameters["LocalIterations"]; }
     
    7474    }
    7575
    76     public IValueParameter<ItemList<ItemList<IntValue>>> RealizationsParameter {
    77       get { return (IValueParameter<ItemList<ItemList<IntValue>>>)Parameters["Realizations"]; }
     76    public ILookupParameter<ItemList<BoolArray>> RealizationsParameter {
     77      get { return (ILookupParameter<ItemList<BoolArray>>)Parameters["Realizations"]; }
    7878    }
    7979
    8080    [StorableConstructor]
    81     protected PTSPExhaustiveInversionLocalImprovement(bool deserializing) : base(deserializing) { }
    82     protected PTSPExhaustiveInversionLocalImprovement(PTSPExhaustiveInversionLocalImprovement original, Cloner cloner)
    83       : base(original, cloner) {
    84     }
     81    private PTSPExhaustiveInversionLocalImprovement(bool deserializing) : base(deserializing) { }
     82    private PTSPExhaustiveInversionLocalImprovement(PTSPExhaustiveInversionLocalImprovement original, Cloner cloner) : base(original, cloner) { }
    8583    public PTSPExhaustiveInversionLocalImprovement()
    8684      : base() {
     
    9391      Parameters.Add(new LookupParameter<BoolValue>("Maximization", "True if the problem should be maximized or minimized."));
    9492      Parameters.Add(new LookupParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
    95       Parameters.Add(new ValueParameter<ItemList<ItemList<IntValue>>>("Realizations", "The concrete..."));
     93      Parameters.Add(new LookupParameter<ItemList<BoolArray>>("Realizations", "The list of samples drawn from all possible stochastic instances."));
    9694    }
    9795
     
    10098    }
    10199
    102     public static void Improve(Permutation assignment, DoubleMatrix distances, DoubleValue quality, IntValue localIterations, IntValue evaluatedSolutions, bool maximization, int maxIterations, CancellationToken cancellation, ItemList<ItemList<IntValue>> realizations) {
    103       DistanceMatrix distanceM = (DistanceMatrix)distances;
    104       for (int i = localIterations.Value; i < maxIterations; i++) {
     100    public static void Improve(Permutation assignment, DoubleMatrix distances, DoubleValue quality, IntValue localIterations, IntValue evaluatedSolutions, bool maximization, int maxIterations, CancellationToken cancellation, ItemList<BoolArray> realizations) {
     101      var distanceM = (DistanceMatrix)distances;
     102      for (var i = localIterations.Value; i < maxIterations; i++) {
    105103        InversionMove bestMove = null;
    106104        double bestQuality = 0; // we have to make an improvement, so 0 is the baseline
    107105        double evaluations = 0.0;
    108106        foreach (var move in ExhaustiveInversionMoveGenerator.Generate(assignment)) {
    109           double moveQuality = PTSPEstimatedInversionEvaluator.EvaluateByDistanceMatrix(assignment, move, distanceM, realizations);
     107          double moveQuality = PTSPEstimatedInversionMoveEvaluator.EvaluateByDistanceMatrix(assignment, move, distanceM, realizations);
    110108          evaluations += 2 * (move.Index2 - move.Index1 + 1) / (double)assignment.Length;
    111109          if (maximization && moveQuality > bestQuality
     
    132130      var localIterations = LocalIterationsParameter.ActualValue;
    133131      var evaluations = EvaluatedSolutionsParameter.ActualValue;
    134       var realizations = RealizationsParameter.Value;
     132      var realizations = RealizationsParameter.ActualValue;
    135133      if (localIterations == null) {
    136134        localIterations = new IntValue(0);
  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Interfaces/IEstimatedPTSPMoveEvaluator.cs

    r13408 r13412  
    2424using HeuristicLab.Encodings.PermutationEncoding;
    2525using HeuristicLab.Optimization;
    26 using System;
    2726
    2827namespace HeuristicLab.Problems.PTSP {
    29   public interface IPTSPMoveEvaluator : ISingleObjectiveMoveEvaluator, IMoveOperator, IPermutationMoveOperator {
    30     Type EvaluatorType { get; }
     28  public interface IEstimatedPTSPMoveEvaluator : IEstimatedPTSPOperator, ISingleObjectiveMoveEvaluator, IPermutationMoveOperator {
    3129    ILookupParameter<DoubleMatrix> CoordinatesParameter { get; }
    3230    ILookupParameter<DistanceMatrix> DistanceMatrixParameter { get; }
    3331    ILookupParameter<BoolValue> UseDistanceMatrixParameter { get; }
    34 
    3532  }
    3633}
  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Interfaces/IEstimatedPTSPOperator.cs

    r13408 r13412  
    2222using HeuristicLab.Core;
    2323using HeuristicLab.Data;
    24 using HeuristicLab.Encodings.PermutationEncoding;
    25 using HeuristicLab.Optimization;
    26 using System;
    2724
    2825namespace HeuristicLab.Problems.PTSP {
    29   public interface IPTSPMoveEvaluator : ISingleObjectiveMoveEvaluator, IMoveOperator, IPermutationMoveOperator {
    30     Type EvaluatorType { get; }
    31     ILookupParameter<DoubleMatrix> CoordinatesParameter { get; }
    32     ILookupParameter<DistanceMatrix> DistanceMatrixParameter { get; }
    33     ILookupParameter<BoolValue> UseDistanceMatrixParameter { get; }
    34 
     26  public interface IEstimatedPTSPOperator : IItem {
     27    ILookupParameter<ItemList<BoolArray>> RealizationsParameter { get; }
    3528  }
    3629}
  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Interfaces/ITwoPointFiveMoveOperator.cs

    r13408 r13412  
    1 using HeuristicLab.Core;
     1#region License Information
     2/* HeuristicLab
     3 * Copyright (C) 2002-2015 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 HeuristicLab.Core;
    223using HeuristicLab.Optimization;
    3 using System;
    4 using System.Collections.Generic;
    5 using System.Linq;
    6 using System.Text;
    7 using System.Threading.Tasks;
    824
    925namespace HeuristicLab.Problems.PTSP {
    10   public interface I25MoveOperator : IMoveOperator {
     26  public interface ITwoPointFiveMoveOperator : IMoveOperator {
    1127    ILookupParameter<TwoPointFiveMove> TwoPointFiveMoveParameter { get; }
    1228  }
  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Moves/EstimatedPTSPMoveEvaluator.cs

    r13408 r13412  
    2525using HeuristicLab.Data;
    2626using HeuristicLab.Encodings.PermutationEncoding;
     27using HeuristicLab.Operators;
    2728using HeuristicLab.Parameters;
    2829using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    29 using HeuristicLab.Operators;
    30 using HeuristicLab.Optimization;
    3130
    3231namespace HeuristicLab.Problems.PTSP {
    33   /// <summary>
    34   /// A base class for operators which evaluate TSP solutions.
    35   /// </summary>
    36   [Item("PTSPMoveEvaluator", "A base class for operators which evaluate TSP moves.")]
     32  [Item("EstimatedPTSPMoveEvaluator", "A base class for operators which evaluate TSP moves.")]
    3733  [StorableClass]
    38   public abstract class PTSPMoveEvaluator : SingleSuccessorOperator, IPTSPMoveEvaluator, IMoveOperator {
     34  public abstract class EstimatedPTSPMoveEvaluator : SingleSuccessorOperator, IEstimatedPTSPMoveEvaluator {
    3935
    40     public abstract Type EvaluatorType { get; }
    4136    public override bool CanChangeName {
    4237      get { return false; }
     
    5550      get { return (ILookupParameter<BoolValue>)Parameters["UseDistanceMatrix"]; }
    5651    }
    57     public IValueParameter<ItemList<ItemList<IntValue>>> RealizationsParameter {
    58       get { return (IValueParameter<ItemList<ItemList<IntValue>>>)Parameters["Realizations"]; }
     52    public ILookupParameter<ItemList<BoolArray>> RealizationsParameter {
     53      get { return (ILookupParameter<ItemList<BoolArray>>)Parameters["Realizations"]; }
    5954    }
    60 
    6155    public ILookupParameter<DoubleValue> QualityParameter {
    6256      get { return (ILookupParameter<DoubleValue>)Parameters["Quality"]; }
     
    6559      get { return (ILookupParameter<DoubleValue>)Parameters["MoveQuality"]; }
    6660    }
     61    public ILookupParameter<DistanceCalculator> DistanceCalculatorParameter {
     62      get { return (ILookupParameter<DistanceCalculator>)Parameters["DistanceCalculator"]; }
     63    }
    6764
    6865    [StorableConstructor]
    69     protected PTSPMoveEvaluator(bool deserializing) : base(deserializing) { }
    70     protected PTSPMoveEvaluator(PTSPMoveEvaluator original, Cloner cloner) : base(original, cloner) { }
    71     protected PTSPMoveEvaluator()
     66    protected EstimatedPTSPMoveEvaluator(bool deserializing) : base(deserializing) { }
     67    protected EstimatedPTSPMoveEvaluator(EstimatedPTSPMoveEvaluator original, Cloner cloner) : base(original, cloner) { }
     68    protected EstimatedPTSPMoveEvaluator()
    7269      : base() {
    7370      Parameters.Add(new LookupParameter<Permutation>("Permutation", "The solution as permutation."));
     
    7572      Parameters.Add(new LookupParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
    7673      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."));
    77       Parameters.Add(new ValueParameter<ItemList<ItemList<IntValue>>>("Realizations", "The concrete..."));
     74      Parameters.Add(new LookupParameter<ItemList<BoolArray>>("Realizations", "The list of samples drawn from all possible stochastic instances."));
    7875      Parameters.Add(new LookupParameter<DoubleValue>("Quality", "The quality of a TSP solution."));
    7976      Parameters.Add(new LookupParameter<DoubleValue>("MoveQuality", "The evaluated quality of a move on a TSP solution."));
    80     }
    81 
    82     [StorableHook(HookType.AfterDeserialization)]
    83     private void AfterDeserialization() {
    84       // BackwardsCompatibility3.3
    85       #region Backwards compatible code (remove with 3.4)
    86       LookupParameter<DoubleMatrix> oldDistanceMatrixParameter = Parameters["DistanceMatrix"] as LookupParameter<DoubleMatrix>;
    87       if (oldDistanceMatrixParameter != null) {
    88         Parameters.Remove(oldDistanceMatrixParameter);
    89         Parameters.Add(new LookupParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
    90         DistanceMatrixParameter.ActualName = oldDistanceMatrixParameter.ActualName;
    91       }
    92       #endregion
     77      Parameters.Add(new LookupParameter<DistanceCalculator>("DistanceCalculator", "The class that can compute distances between coordinates."));
    9378    }
    9479
    9580    public override IOperation Apply() {
    96       Permutation permutation = PermutationParameter.ActualValue;
    97       DoubleMatrix coordinates = CoordinatesParameter.ActualValue;
     81      var permutation = PermutationParameter.ActualValue;
     82      var coordinates = CoordinatesParameter.ActualValue;
    9883      double relativeQualityDifference = 0;
    9984      if (UseDistanceMatrixParameter.ActualValue.Value) {
    100         DistanceMatrix distanceMatrix = DistanceMatrixParameter.ActualValue;
    101         if (distanceMatrix == null) {
    102           if (coordinates == null) throw new InvalidOperationException("Neither a distance matrix nor coordinates were given.");
    103           distanceMatrix = CalculateDistanceMatrix(coordinates);
    104           DistanceMatrixParameter.ActualValue = distanceMatrix;
    105         }
     85        var distanceMatrix = DistanceMatrixParameter.ActualValue;
     86        if (distanceMatrix == null) throw new InvalidOperationException("The distance matrix has not been calculated.");
    10687        relativeQualityDifference = EvaluateByDistanceMatrix(permutation, distanceMatrix);
    10788      } else {
    10889        if (coordinates == null) throw new InvalidOperationException("No coordinates were given.");
    109         relativeQualityDifference = EvaluateByCoordinates(permutation, coordinates);
     90        var distanceCalculator = DistanceCalculatorParameter.ActualValue;
     91        if (distanceCalculator == null) throw new InvalidOperationException("Distance calculator is null!");
     92        relativeQualityDifference = EvaluateByCoordinates(permutation, coordinates, distanceCalculator);
    11093      }
    111       DoubleValue moveQuality = MoveQualityParameter.ActualValue;
     94      var moveQuality = MoveQualityParameter.ActualValue;
    11295      if (moveQuality == null) MoveQualityParameter.ActualValue = new DoubleValue(QualityParameter.ActualValue.Value + relativeQualityDifference);
    11396      else moveQuality.Value = QualityParameter.ActualValue.Value + relativeQualityDifference;
     
    11598    }
    11699
    117     protected abstract double CalculateDistance(double x1, double y1, double x2, double y2);
    118100    protected abstract double EvaluateByDistanceMatrix(Permutation permutation, DistanceMatrix distanceMatrix);
    119     protected abstract double EvaluateByCoordinates(Permutation permutation, DoubleMatrix coordinates);
    120 
    121     private DistanceMatrix CalculateDistanceMatrix(DoubleMatrix c) {
    122       DistanceMatrix distanceMatrix = new DistanceMatrix(c.Rows, c.Rows);
    123       for (int i = 0; i < distanceMatrix.Rows; i++) {
    124         for (int j = 0; j < distanceMatrix.Columns; j++)
    125           distanceMatrix[i, j] = CalculateDistance(c[i, 0], c[i, 1], c[j, 0], c[j, 1]);
    126       }
    127       return (DistanceMatrix)distanceMatrix.AsReadOnly();
    128     }
     101    protected abstract double EvaluateByCoordinates(Permutation permutation, DoubleMatrix coordinates, DistanceCalculator distanceCalculator);
    129102  }
    130103}
  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Moves/OneShift/PTSPEstimatedInsertionMoveEvaluator.cs

    r13408 r13412  
    2020#endregion
    2121
     22using System;
    2223using HeuristicLab.Common;
    2324using HeuristicLab.Core;
     
    2627using HeuristicLab.Parameters;
    2728using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    28 using System;
    2929
    3030namespace HeuristicLab.Problems.PTSP {
    31   [Item("PTSPEstimatedInsertionEvaluator", "Evaluates an insertion move (1-shift)")]
     31  [Item("PTSPEstimatedInsertionMoveEvaluator", "Evaluates an insertion move (1-shift)")]
    3232  [StorableClass]
    33   public class PTSPEstimatedInsertionEvaluator : PTSPMoveEvaluator, IPermutationTranslocationMoveOperator {
    34 
    35     public override Type EvaluatorType {
    36       get { return typeof(PTSPEstimatedInsertionEvaluator); }
    37     }
     33  public class PTSPEstimatedInsertionMoveEvaluator : EstimatedPTSPMoveEvaluator, IPermutationTranslocationMoveOperator {
     34
    3835    public ILookupParameter<TranslocationMove> TranslocationMoveParameter {
    3936      get { return (ILookupParameter<TranslocationMove>)Parameters["TranslocationMove"]; }
    4037    }
    4138
    42     public IValueParameter<ItemList<ItemList<IntValue>>> RealizationsParameter {
    43       get { return (IValueParameter<ItemList<ItemList<IntValue>>>)Parameters["Realizations"]; }
    44     }
    45 
    4639    [StorableConstructor]
    47     protected PTSPEstimatedInsertionEvaluator(bool deserializing) : base(deserializing) { }
    48     protected PTSPEstimatedInsertionEvaluator(PTSPEstimatedInsertionEvaluator original, Cloner cloner) : base(original, cloner) { }
    49     public PTSPEstimatedInsertionEvaluator()
     40    protected PTSPEstimatedInsertionMoveEvaluator(bool deserializing) : base(deserializing) { }
     41    protected PTSPEstimatedInsertionMoveEvaluator(PTSPEstimatedInsertionMoveEvaluator original, Cloner cloner) : base(original, cloner) { }
     42    public PTSPEstimatedInsertionMoveEvaluator()
    5043      : base() {
    5144      Parameters.Add(new LookupParameter<TranslocationMove>("TranslocationMove", "The move to evaluate."));
     
    5346
    5447    public override IDeepCloneable Clone(Cloner cloner) {
    55       return new PTSPEstimatedInsertionEvaluator(this, cloner);
    56     }
    57 
    58     public static double EvaluateByCoordinates(Permutation permutation, TranslocationMove move, DoubleMatrix coordinates, PTSPEstimatedInsertionEvaluator evaluator) {
    59       int edge1source = permutation.GetCircular(move.Index1 - 1);
    60       int edge1target = permutation[move.Index1];
    61       int edge2source = permutation[move.Index2];
    62       int edge2target = permutation.GetCircular(move.Index2 + 1);
    63       if (move.Index2 - move.Index1 >= permutation.Length - 2) return 0;
    64       double moveQuality = 0;
    65       // remove two edges
    66       moveQuality -= evaluator.CalculateDistance(coordinates[edge1source, 0], coordinates[edge1source, 1],
    67             coordinates[edge1target, 0], coordinates[edge1target, 1]);
    68       moveQuality -= evaluator.CalculateDistance(coordinates[edge2source, 0], coordinates[edge2source, 1],
    69         coordinates[edge2target, 0], coordinates[edge2target, 1]);
    70       // add two edges
    71       moveQuality += evaluator.CalculateDistance(coordinates[edge1source, 0], coordinates[edge1source, 1],
    72         coordinates[edge2source, 0], coordinates[edge2source, 1]);
    73       moveQuality += evaluator.CalculateDistance(coordinates[edge1target, 0], coordinates[edge1target, 1],
    74         coordinates[edge2target, 0], coordinates[edge2target, 1]);
    75       return moveQuality;
    76     }
    77 
    78     public static double EvaluateByDistanceMatrix(Permutation permutation, TranslocationMove move, DistanceMatrix distanceMatrix, ItemList<ItemList<IntValue>> realizations) {
    79       Permutation afterMove = new Permutation(PermutationTypes.RelativeUndirected,permutation);
     48      return new PTSPEstimatedInsertionMoveEvaluator(this, cloner);
     49    }
     50
     51    public static double EvaluateByCoordinates(Permutation permutation, TranslocationMove move, DoubleMatrix coordinates, DistanceCalculator distanceCalculator, ItemList<BoolArray> realizations) {
     52      var afterMove = new Permutation(PermutationTypes.RelativeUndirected, permutation);
    8053      TranslocationManipulator.Apply(afterMove, move.Index1, move.Index1, move.Index3);
    8154      double moveQuality = 0;
    82       int[] edges = new int[12];
    83       int[] indices = new int[12];
     55      var edges = new int[12];
     56      var indices = new int[12];
    8457      edges[0] = permutation.GetCircular(move.Index1 - 1);
    85       indices[0] = decreaseCircularIndex(permutation.Length, move.Index1);
     58      indices[0] = DecreaseCircularIndex(permutation.Length, move.Index1);
    8659      edges[1] = permutation[move.Index1];
    8760      indices[1] = move.Index1;
     
    8962      indices[2] = move.Index1;
    9063      edges[3] = permutation.GetCircular(move.Index1 + 1);
    91       indices[3] = increaseCircularIndex(permutation.Length, move.Index1);
     64      indices[3] = IncreaseCircularIndex(permutation.Length, move.Index1);
    9265
    9366      edges[6] = afterMove.GetCircular(move.Index3 - 1);
    94       indices[6] = decreaseCircularIndex(afterMove.Length, move.Index3);
     67      indices[6] = DecreaseCircularIndex(afterMove.Length, move.Index3);
    9568      edges[7] = afterMove[move.Index3];
    9669      indices[7] = move.Index3;
     
    9871      indices[8] = move.Index3;
    9972      edges[9] = afterMove.GetCircular(move.Index3 + 1);
    100       indices[9] = increaseCircularIndex(afterMove.Length, move.Index3);
     73      indices[9] = IncreaseCircularIndex(afterMove.Length, move.Index3);
    10174
    10275      if (move.Index3 > move.Index1) {
     
    12093      }
    12194      int[] aPosteriori = new int[12];
    122       Permutation tempPermutation;
    123       foreach (ItemList<IntValue> realization in realizations) {
     95      foreach (var realization in realizations) {
    12496        for (int i = 0; i < edges.Length; i++) {
     97          Permutation tempPermutation;
    12598          if (i < 6) {
    12699            tempPermutation = permutation;
     
    128101            tempPermutation = afterMove;
    129102          }
    130           if (realization[edges[i]].Value == 1) {
     103          if (realization[edges[i]]) {
    131104            aPosteriori[i] = edges[i];
    132105          } else {
    133             int j=1;
    134             if (i%2==0) {
     106            int j = 1;
     107            if (i % 2 == 0) {
    135108              // find nearest predecessor in realization if source edge
    136               while (realization[tempPermutation.GetCircular(indices[i] - j)].Value == 0) {
     109              while (!realization[tempPermutation.GetCircular(indices[i] - j)]) {
    137110                j++;
    138111              }
     
    140113            } else {
    141114              // find nearest successor in realization if target edge
    142               while (realization[tempPermutation.GetCircular(indices[i] + j)].Value == 0) {
     115              while (!realization[tempPermutation.GetCircular(indices[i] + j)]) {
     116                j++;
     117              }
     118              aPosteriori[i] = tempPermutation.GetCircular(indices[i] + j);
     119            }
     120          }
     121        }
     122        if (!(aPosteriori[0] == aPosteriori[2] && aPosteriori[1] == aPosteriori[3]) &&
     123          !(aPosteriori[0] == aPosteriori[4] && aPosteriori[1] == aPosteriori[5]) &&
     124          !(aPosteriori[2] == aPosteriori[4] && aPosteriori[3] == aPosteriori[5])) {
     125          // compute cost difference between the two a posteriori solutions
     126
     127          moveQuality += distanceCalculator.Calculate(aPosteriori[6], aPosteriori[7], coordinates)
     128                       + distanceCalculator.Calculate(aPosteriori[8], aPosteriori[9], coordinates)
     129                       + distanceCalculator.Calculate(aPosteriori[10], aPosteriori[11], coordinates)
     130                       - distanceCalculator.Calculate(aPosteriori[0], aPosteriori[1], coordinates)
     131                       - distanceCalculator.Calculate(aPosteriori[2], aPosteriori[3], coordinates)
     132                       - distanceCalculator.Calculate(aPosteriori[4], aPosteriori[5], coordinates);
     133        }
     134        Array.Clear(aPosteriori, 0, aPosteriori.Length);
     135      }
     136      // return average of cost differences
     137      return moveQuality / realizations.Count;
     138    }
     139
     140    public static double EvaluateByDistanceMatrix(Permutation permutation, TranslocationMove move, DistanceMatrix distanceMatrix, ItemList<BoolArray> realizations) {
     141      var afterMove = new Permutation(PermutationTypes.RelativeUndirected, permutation);
     142      TranslocationManipulator.Apply(afterMove, move.Index1, move.Index1, move.Index3);
     143      double moveQuality = 0;
     144      var edges = new int[12];
     145      var indices = new int[12];
     146      edges[0] = permutation.GetCircular(move.Index1 - 1);
     147      indices[0] = DecreaseCircularIndex(permutation.Length, move.Index1);
     148      edges[1] = permutation[move.Index1];
     149      indices[1] = move.Index1;
     150      edges[2] = permutation[move.Index1];
     151      indices[2] = move.Index1;
     152      edges[3] = permutation.GetCircular(move.Index1 + 1);
     153      indices[3] = IncreaseCircularIndex(permutation.Length, move.Index1);
     154
     155      edges[6] = afterMove.GetCircular(move.Index3 - 1);
     156      indices[6] = DecreaseCircularIndex(afterMove.Length, move.Index3);
     157      edges[7] = afterMove[move.Index3];
     158      indices[7] = move.Index3;
     159      edges[8] = afterMove[move.Index3];
     160      indices[8] = move.Index3;
     161      edges[9] = afterMove.GetCircular(move.Index3 + 1);
     162      indices[9] = IncreaseCircularIndex(afterMove.Length, move.Index3);
     163
     164      if (move.Index3 > move.Index1) {
     165        edges[4] = permutation[move.Index3];
     166        indices[4] = move.Index3;
     167        edges[5] = permutation.GetCircular(move.Index3 + 1);
     168        indices[5] = indices[9];
     169        edges[10] = afterMove.GetCircular(move.Index1 - 1);
     170        indices[10] = indices[0];
     171        edges[11] = afterMove[move.Index1];
     172        indices[11] = move.Index1;
     173      } else {
     174        edges[4] = permutation.GetCircular(move.Index3 - 1);
     175        indices[4] = indices[6];
     176        edges[5] = permutation[move.Index3];
     177        indices[5] = move.Index3;
     178        edges[10] = afterMove[move.Index1];
     179        indices[10] = move.Index1;
     180        edges[11] = afterMove.GetCircular(move.Index1 + 1);
     181        indices[11] = indices[3];
     182      }
     183      int[] aPosteriori = new int[12];
     184      foreach (var realization in realizations) {
     185        for (int i = 0; i < edges.Length; i++) {
     186          Permutation tempPermutation;
     187          if (i < 6) {
     188            tempPermutation = permutation;
     189          } else {
     190            tempPermutation = afterMove;
     191          }
     192          if (realization[edges[i]]) {
     193            aPosteriori[i] = edges[i];
     194          } else {
     195            int j = 1;
     196            if (i % 2 == 0) {
     197              // find nearest predecessor in realization if source edge
     198              while (!realization[tempPermutation.GetCircular(indices[i] - j)]) {
     199                j++;
     200              }
     201              aPosteriori[i] = tempPermutation.GetCircular(indices[i] - j);
     202            } else {
     203              // find nearest successor in realization if target edge
     204              while (!realization[tempPermutation.GetCircular(indices[i] + j)]) {
    143205                j++;
    144206              }
     
    160222    }
    161223
    162     private static int decreaseCircularIndex(int length, int index) {
    163       int result = index - 1;
     224    private static int DecreaseCircularIndex(int length, int index) {
     225      var result = index - 1;
    164226      if (result == -1) {
    165227        result = length - 1;
     
    168230    }
    169231
    170     private static int increaseCircularIndex(int length, int index) {
    171       int result = index + 1;
     232    private static int IncreaseCircularIndex(int length, int index) {
     233      var result = index + 1;
    172234      if (result == length + 1) {
    173235        result = 0;
     
    176238    }
    177239
    178     protected override double EvaluateByCoordinates(Permutation permutation, DoubleMatrix coordinates) {
    179       return EvaluateByCoordinates(permutation, TranslocationMoveParameter.ActualValue, coordinates, this);
     240    protected override double EvaluateByCoordinates(Permutation permutation, DoubleMatrix coordinates, DistanceCalculator distanceCalculator) {
     241      return EvaluateByCoordinates(permutation, TranslocationMoveParameter.ActualValue, coordinates, distanceCalculator, RealizationsParameter.ActualValue);
    180242    }
    181243
    182244    protected override double EvaluateByDistanceMatrix(Permutation permutation, DistanceMatrix distanceMatrix) {
    183       return EvaluateByDistanceMatrix(permutation, TranslocationMoveParameter.ActualValue, distanceMatrix, RealizationsParameter.Value);
    184     }
    185 
    186     protected override double CalculateDistance(double x1, double y1, double x2, double y2) {
    187       return Math.Round(Math.Sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)));
     245      return EvaluateByDistanceMatrix(permutation, TranslocationMoveParameter.ActualValue, distanceMatrix, RealizationsParameter.ActualValue);
    188246    }
    189247  }
  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Moves/TwoOpt/PTSPEstimatedInversionMoveEvaluator.cs

    r13408 r13412  
    2020#endregion
    2121
     22using System;
    2223using HeuristicLab.Common;
    2324using HeuristicLab.Core;
     
    2627using HeuristicLab.Parameters;
    2728using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    28 using System;
    2929
    3030namespace HeuristicLab.Problems.PTSP {
    31   /// <summary>
    32   /// An operator to evaluate inversion moves (2-opt).
    33   /// </summary>
    34   [Item("PTSPInversionMovePathEvaluator", "Evaluates an inversion move (2-opt) by summing up the length of all added edges and subtracting the length of all deleted edges.")]
     31  [Item("PTSPEstimatedInversionMoveEvaluator", "Evaluates an inversion move (2-opt) over several realizations of tours by summing up the length of all added edges and subtracting the length of all deleted edges.")]
    3532  [StorableClass]
    36   public class PTSPEstimatedInversionEvaluator : PTSPMoveEvaluator, IPermutationInversionMoveOperator {
    37     public override Type EvaluatorType {
    38       get { return typeof(PTSPEstimatedInversionEvaluator); }
    39     }
     33  public class PTSPEstimatedInversionMoveEvaluator : EstimatedPTSPMoveEvaluator, IPermutationInversionMoveOperator {
     34
    4035    public ILookupParameter<InversionMove> InversionMoveParameter {
    4136      get { return (ILookupParameter<InversionMove>)Parameters["InversionMove"]; }
    4237    }
    4338
    44    
    45 
    4639    [StorableConstructor]
    47     protected PTSPEstimatedInversionEvaluator(bool deserializing) : base(deserializing) { }
    48     protected PTSPEstimatedInversionEvaluator(PTSPEstimatedInversionEvaluator original, Cloner cloner) : base(original, cloner) { }
    49     public PTSPEstimatedInversionEvaluator()
     40    protected PTSPEstimatedInversionMoveEvaluator(bool deserializing) : base(deserializing) { }
     41    protected PTSPEstimatedInversionMoveEvaluator(PTSPEstimatedInversionMoveEvaluator original, Cloner cloner) : base(original, cloner) { }
     42    public PTSPEstimatedInversionMoveEvaluator()
    5043      : base() {
    5144      Parameters.Add(new LookupParameter<InversionMove>("InversionMove", "The move to evaluate."));
     
    5346
    5447    public override IDeepCloneable Clone(Cloner cloner) {
    55       return new PTSPEstimatedInversionEvaluator(this, cloner);
     48      return new PTSPEstimatedInversionMoveEvaluator(this, cloner);
    5649    }
    5750
    58     public static double EvaluateByCoordinates(Permutation permutation, InversionMove move, DoubleMatrix coordinates, PTSPEstimatedInversionEvaluator evaluator) {
    59       int edge1source = permutation.GetCircular(move.Index1 - 1);
    60       int edge1target = permutation[move.Index1];
    61       int edge2source = permutation[move.Index2];
    62       int edge2target = permutation.GetCircular(move.Index2 + 1);
    63       if (move.Index2 - move.Index1 >= permutation.Length - 2) return 0;
     51    public static double EvaluateByCoordinates(Permutation permutation, InversionMove move, DoubleMatrix coordinates, DistanceCalculator distanceCalculator, ItemList<BoolArray> realizations) {
    6452      double moveQuality = 0;
    65       // remove two edges
    66       moveQuality -= evaluator.CalculateDistance(coordinates[edge1source, 0], coordinates[edge1source, 1],
    67             coordinates[edge1target, 0], coordinates[edge1target, 1]);
    68       moveQuality -= evaluator.CalculateDistance(coordinates[edge2source, 0], coordinates[edge2source, 1],
    69         coordinates[edge2target, 0], coordinates[edge2target, 1]);
    70       // add two edges
    71       moveQuality += evaluator.CalculateDistance(coordinates[edge1source, 0], coordinates[edge1source, 1],
    72         coordinates[edge2source, 0], coordinates[edge2source, 1]);
    73       moveQuality += evaluator.CalculateDistance(coordinates[edge1target, 0], coordinates[edge1target, 1],
    74         coordinates[edge2target, 0], coordinates[edge2target, 1]);
    75       return moveQuality;
    76     }
    77 
    78     public static double EvaluateByDistanceMatrix(Permutation permutation, InversionMove move, DistanceMatrix distanceMatrix, ItemList<ItemList<IntValue>> realizations) {
    79       double moveQuality = 0;
    80       int[] edges = new int[4];
    81       int[] indices = new int[4];
     53      var edges = new int[4];
     54      var indices = new int[4];
    8255      edges[0] = permutation.GetCircular(move.Index1 - 1);
    83       indices[0] = move.Index1-1;
     56      indices[0] = move.Index1 - 1;
    8457      if (indices[0] == -1) indices[0] = permutation.Length - 1;
    8558      edges[1] = permutation[move.Index1];
     
    8861      indices[2] = move.Index2;
    8962      edges[3] = permutation.GetCircular(move.Index2 + 1);
    90       indices[3] = move.Index2+1;
     63      indices[3] = move.Index2 + 1;
    9164      if (indices[3] == permutation.Length + 1) indices[3] = 0;
    92       int[] aPosteriori = new int[4];
    93       foreach (ItemList<IntValue> realization in realizations) {
    94         for (int i = 0; i < edges.Length; i++) {
    95           if (realization[edges[i]].Value == 1) {
     65      var aPosteriori = new int[4];
     66      foreach (var realization in realizations) {
     67        for (var i = 0; i < edges.Length; i++) {
     68          if (realization[edges[i]]) {
    9669            aPosteriori[i] = edges[i];
    9770          } else {
    98             int j=1;
    99             if (i%2==0) {
     71            var j = 1;
     72            if (i % 2 == 0) {
    10073              // find nearest predecessor in realization if source edge
    101               while(realization[permutation.GetCircular(indices[i]-j)].Value==0) {
     74              while (!realization[permutation.GetCircular(indices[i] - j)]) {
    10275                j++;
    10376              }
     
    10578            } else {
    10679              // find nearest successor in realization if target edge
    107               while(realization[permutation.GetCircular(indices[i]+j)].Value==0) {
     80              while (!realization[permutation.GetCircular(indices[i] + j)]) {
     81                j++;
     82              }
     83              aPosteriori[i] = permutation.GetCircular(indices[i] + j);
     84            }
     85          }
     86        }
     87        // compute cost difference between the two a posteriori solutions
     88        if (!(aPosteriori[0] == aPosteriori[2] && aPosteriori[1] == aPosteriori[3])) {
     89          moveQuality = moveQuality
     90            + distanceCalculator.Calculate(0, 2, coordinates)
     91            + distanceCalculator.Calculate(1, 3, coordinates)
     92            - distanceCalculator.Calculate(0, 1, coordinates)
     93            - distanceCalculator.Calculate(2, 3, coordinates);
     94        }
     95        Array.Clear(aPosteriori, 0, aPosteriori.Length);
     96      }
     97      // return average of cost differences
     98      return moveQuality / realizations.Count;
     99    }
     100
     101    public static double EvaluateByDistanceMatrix(Permutation permutation, InversionMove move, DistanceMatrix distanceMatrix, ItemList<BoolArray> realizations) {
     102      double moveQuality = 0;
     103      var edges = new int[4];
     104      var indices = new int[4];
     105      edges[0] = permutation.GetCircular(move.Index1 - 1);
     106      indices[0] = move.Index1 - 1;
     107      if (indices[0] == -1) indices[0] = permutation.Length - 1;
     108      edges[1] = permutation[move.Index1];
     109      indices[1] = move.Index1;
     110      edges[2] = permutation[move.Index2];
     111      indices[2] = move.Index2;
     112      edges[3] = permutation.GetCircular(move.Index2 + 1);
     113      indices[3] = move.Index2 + 1;
     114      if (indices[3] == permutation.Length + 1) indices[3] = 0;
     115      var aPosteriori = new int[4];
     116      foreach (var realization in realizations) {
     117        for (var i = 0; i < edges.Length; i++) {
     118          if (realization[edges[i]]) {
     119            aPosteriori[i] = edges[i];
     120          } else {
     121            var j = 1;
     122            if (i % 2 == 0) {
     123              // find nearest predecessor in realization if source edge
     124              while (!realization[permutation.GetCircular(indices[i] - j)]) {
     125                j++;
     126              }
     127              aPosteriori[i] = permutation.GetCircular(indices[i] - j);
     128            } else {
     129              // find nearest successor in realization if target edge
     130              while (!realization[permutation.GetCircular(indices[i] + j)]) {
    108131                j++;
    109132              }
     
    122145    }
    123146
    124     protected override double EvaluateByCoordinates(Permutation permutation, DoubleMatrix coordinates) {
    125       return EvaluateByCoordinates(permutation, InversionMoveParameter.ActualValue, coordinates, this);
     147    protected override double EvaluateByCoordinates(Permutation permutation, DoubleMatrix coordinates, DistanceCalculator distanceCalculator) {
     148      return EvaluateByCoordinates(permutation, InversionMoveParameter.ActualValue, coordinates, distanceCalculator, RealizationsParameter.ActualValue);
    126149    }
    127150
    128151    protected override double EvaluateByDistanceMatrix(Permutation permutation, DistanceMatrix distanceMatrix) {
    129       return EvaluateByDistanceMatrix(permutation, InversionMoveParameter.ActualValue, distanceMatrix, RealizationsParameter.Value);
    130     }
    131 
    132     protected override double CalculateDistance(double x1, double y1, double x2, double y2) {
    133       return Math.Round(Math.Sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)));
     152      return EvaluateByDistanceMatrix(permutation, InversionMoveParameter.ActualValue, distanceMatrix, RealizationsParameter.ActualValue);
    134153    }
    135154  }
  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Moves/TwoPointFiveOpt/ExhaustiveTwoPointFiveMoveGenerator.cs

    r13408 r13412  
    1 using System;
     1#region License Information
     2/* HeuristicLab
     3 * Copyright (C) 2002-2015 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;
    223using System.Collections.Generic;
    324using System.Linq;
    425using HeuristicLab.Common;
    526using HeuristicLab.Core;
     27using HeuristicLab.Encodings.PermutationEncoding;
    628using HeuristicLab.Optimization;
    729using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    8 using HeuristicLab.Encodings.PermutationEncoding;
    9 using HeuristicLab.Parameters;
    10 using HeuristicLab.Operators;
    1130
    1231namespace HeuristicLab.Problems.PTSP {
    13   [Item("Exhaustive25MoveGenerator", "Generates all possible inversion and shift moves (2.5-opt) from a given permutation.")]
     32  [Item("Exhaustive 2.5-MoveGenerator", "Generates all possible inversion and shift moves (2.5-opt) from a given permutation.")]
    1433  [StorableClass]
    15   class Exhaustive25MoveGenerator : TwoPointFiveMoveGenerator, IExhaustiveMoveGenerator {
    16     public override bool CanChangeName {
    17       get { return false; }
     34  public sealed class ExhaustiveTwoPointFiveMoveGenerator : TwoPointFiveMoveGenerator, IExhaustiveMoveGenerator {
     35
     36    [StorableConstructor]
     37    private ExhaustiveTwoPointFiveMoveGenerator(bool deserializing) : base(deserializing) { }
     38    private ExhaustiveTwoPointFiveMoveGenerator(ExhaustiveTwoPointFiveMoveGenerator original, Cloner cloner) : base(original, cloner) { }
     39    public ExhaustiveTwoPointFiveMoveGenerator() : base() { }
     40
     41    public override IDeepCloneable Clone(Cloner cloner) {
     42      return new ExhaustiveTwoPointFiveMoveGenerator(this, cloner);
    1843    }
    1944
    20     [StorableConstructor]
    21     protected Exhaustive25MoveGenerator(bool deserializing) : base(deserializing) { }
    22     protected Exhaustive25MoveGenerator(Exhaustive25MoveGenerator original, Cloner cloner) : base(original, cloner) { }
    23     public Exhaustive25MoveGenerator()
    24       : base() {
    25     }
    26 
    27     public override IDeepCloneable Clone(Cloner cloner) {
    28       return new Exhaustive25MoveGenerator(this, cloner);
    29     }
    30    
    3145    public static TwoPointFiveMove[] Apply(Permutation permutation) {
    3246      return Generate(permutation).ToArray();
     
    3549    public static IEnumerable<TwoPointFiveMove> Generate(Permutation permutation) {
    3650      int length = permutation.Length;
    37       if (length == 1) throw new ArgumentException("Exhaustive25MoveGenerator: There cannot be a 2.5 move given a permutation of length 1.", "permutation");
     51      if (length == 1) throw new ArgumentException("Exhaustive 2.5-MoveGenerator: There cannot be a 2.5 move given a permutation of length 1.", "permutation");
    3852      int totalMoves = (length) * (length - 1) / 2;
    3953
     
    4458              // doesn't make sense to inverse the whole permutation or the whole but one in case of relative undirected permutations
    4559              if (j - i >= length - 2) continue;
    46               yield return new TwoPointFiveMove(i, j,true);
     60              yield return new TwoPointFiveMove(i, j, true);
    4761              yield return new TwoPointFiveMove(i, j, false);
    4862            }
    4963          }
    5064        } else { // when length is 3 or less, there's actually no difference, but for the sake of not crashing the algorithm create a dummy move
    51           yield return new TwoPointFiveMove(0, 1,true);
     65          yield return new TwoPointFiveMove(0, 1, true);
    5266        }
    5367      } else {
    5468        for (int i = 0; i < length - 1; i++)
    5569          for (int j = i + 1; j < length; j++) {
    56             yield return new TwoPointFiveMove(i, j,true);
     70            yield return new TwoPointFiveMove(i, j, true);
    5771            yield return new TwoPointFiveMove(i, j, false);
    5872          }
  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Moves/TwoPointFiveOpt/PTSPTwoPointFiveMoveEvaluator.cs

    r13408 r13412  
    2020#endregion
    2121
    22 using System;
    2322using HeuristicLab.Common;
    2423using HeuristicLab.Core;
     
    2726using HeuristicLab.Parameters;
    2827using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    29 using HeuristicLab.Optimization;
    30 using HeuristicLab.Operators;
    3128
    3229namespace HeuristicLab.Problems.PTSP {
    33   /// <summary>
    34   /// A base class for operators which evaluate TSP solutions.
    35   /// </summary>
    36   [Item("PTSP25MoveEvaluator", "Operator that evaluates 2.5-p-opt moves of PTSP")]
     30  [Item("PTSP 2.5-MoveEvaluator", "Operator that evaluates 2.5-p-opt moves of PTSP")]
    3731  [StorableClass]
    38   public class PTSP25MoveEvaluator : SingleSuccessorOperator, I25MoveOperator, ISingleObjectiveMoveEvaluator {
    39     public ILookupParameter<Permutation> PermutationParameter {
    40       get { return (ILookupParameter<Permutation>)Parameters["Permutation"]; }
    41     }
    42     public ILookupParameter<DoubleMatrix> CoordinatesParameter {
    43       get { return (ILookupParameter<DoubleMatrix>)Parameters["Coordinates"]; }
    44     }
    45     public ILookupParameter<DistanceMatrix> DistanceMatrixParameter {
    46       get { return (ILookupParameter<DistanceMatrix>)Parameters["DistanceMatrix"]; }
    47     }
    48     public ILookupParameter<BoolValue> UseDistanceMatrixParameter {
    49       get { return (ILookupParameter<BoolValue>)Parameters["UseDistanceMatrix"]; }
    50     }
    51     public IValueParameter<ItemList<ItemList<IntValue>>> RealizationsParameter {
    52       get { return (IValueParameter<ItemList<ItemList<IntValue>>>)Parameters["Realizations"]; }
    53     }
     32  public class PTSPTwoPointFiveMoveEvaluator : EstimatedPTSPMoveEvaluator, ITwoPointFiveMoveOperator {
     33
    5434    public ILookupParameter<TwoPointFiveMove> TwoPointFiveMoveParameter {
    5535      get { return (ILookupParameter<TwoPointFiveMove>)Parameters["TwoPointFiveMove"]; }
    5636    }
    57     public ILookupParameter<DoubleValue> QualityParameter {
    58       get { return (ILookupParameter<DoubleValue>)Parameters["Quality"]; }
    59     }
    60     public ILookupParameter<DoubleValue> MoveQualityParameter {
    61       get { return (ILookupParameter<DoubleValue>)Parameters["MoveQuality"]; }
    62     }
    6337
    6438    [StorableConstructor]
    65     protected PTSP25MoveEvaluator(bool deserializing) : base(deserializing) { }
    66     protected PTSP25MoveEvaluator(PTSP25MoveEvaluator original, Cloner cloner) : base(original, cloner) { }
    67     public PTSP25MoveEvaluator()
     39    protected PTSPTwoPointFiveMoveEvaluator(bool deserializing) : base(deserializing) { }
     40    protected PTSPTwoPointFiveMoveEvaluator(PTSPTwoPointFiveMoveEvaluator original, Cloner cloner) : base(original, cloner) { }
     41    public PTSPTwoPointFiveMoveEvaluator()
    6842      : base() {
    69       Parameters.Add(new LookupParameter<Permutation>("Permutation", "The solution as permutation."));
    70       Parameters.Add(new LookupParameter<DoubleMatrix>("Coordinates", "The city's coordinates."));
    71       Parameters.Add(new LookupParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
    72       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."));
    73       Parameters.Add(new ValueParameter<ItemList<ItemList<IntValue>>>("Realizations", "The concrete..."));
    7443      Parameters.Add(new LookupParameter<TwoPointFiveMove>("TwoPointFiveMove", "The move to evaluate."));
    75       Parameters.Add(new LookupParameter<DoubleValue>("Quality", "The quality of a TSP solution."));
    76       Parameters.Add(new LookupParameter<DoubleValue>("MoveQuality", "The evaluated quality of a move on a TSP solution."));
    7744    }
    7845
    7946    public override IDeepCloneable Clone(Cloner cloner) {
    80       return new PTSP25MoveEvaluator(this, cloner);
     47      return new PTSPTwoPointFiveMoveEvaluator(this, cloner);
    8148    }
    8249
    83     [StorableHook(HookType.AfterDeserialization)]
    84     private void AfterDeserialization() {
    85       // BackwardsCompatibility3.3
    86       #region Backwards compatible code (remove with 3.4)
    87       LookupParameter<DoubleMatrix> oldDistanceMatrixParameter = Parameters["DistanceMatrix"] as LookupParameter<DoubleMatrix>;
    88       if (oldDistanceMatrixParameter != null) {
    89         Parameters.Remove(oldDistanceMatrixParameter);
    90         Parameters.Add(new LookupParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
    91         DistanceMatrixParameter.ActualName = oldDistanceMatrixParameter.ActualName;
    92       }
    93       #endregion
     50    protected override double EvaluateByCoordinates(Permutation permutation, DoubleMatrix coordinates, DistanceCalculator distanceCalculator) {
     51      var move = TwoPointFiveMoveParameter.ActualValue;
     52      var realizations = RealizationsParameter.ActualValue;
     53      return EvaluateByCoordinates(permutation, coordinates, distanceCalculator, move, realizations);
    9454    }
    9555
    96     public override IOperation Apply() {
    97       Permutation permutation = PermutationParameter.ActualValue;
    98       DoubleMatrix coordinates = CoordinatesParameter.ActualValue;
    99       double relativeQualityDifference = 0;
    100       if (UseDistanceMatrixParameter.ActualValue.Value) {
    101         DistanceMatrix distanceMatrix = DistanceMatrixParameter.ActualValue;
    102         if (distanceMatrix == null) {
    103           if (coordinates == null) throw new InvalidOperationException("Neither a distance matrix nor coordinates were given.");
    104           distanceMatrix = CalculateDistanceMatrix(coordinates);
    105           DistanceMatrixParameter.ActualValue = distanceMatrix;
    106         }
    107         relativeQualityDifference = EvaluateByDistanceMatrix(permutation, distanceMatrix);
    108       }
    109       DoubleValue moveQuality = MoveQualityParameter.ActualValue;
    110       if (moveQuality == null) MoveQualityParameter.ActualValue = new DoubleValue(QualityParameter.ActualValue.Value + relativeQualityDifference);
    111       else moveQuality.Value = QualityParameter.ActualValue.Value + relativeQualityDifference;
    112       return base.Apply();
     56    public static double EvaluateByCoordinates(Permutation permutation, DoubleMatrix coordinates, DistanceCalculator distanceCalculator, TwoPointFiveMove move, ItemList<BoolArray> realizations) {
     57      if (move.IsInvert) {
     58        return PTSPEstimatedInversionMoveEvaluator.EvaluateByCoordinates(permutation,
     59          new InversionMove(move.Index1, move.Index2, move.Permutation),
     60          coordinates, distanceCalculator, realizations);
     61      } else {
     62        return PTSPEstimatedInsertionMoveEvaluator.EvaluateByCoordinates(permutation,
     63          new TranslocationMove(move.Index1, move.Index1, move.Index2),
     64          coordinates, distanceCalculator, realizations);
     65      }
    11366    }
    11467
    115     protected double CalculateDistance(double x1, double y1, double x2, double y2) {
    116       return Math.Round(Math.Sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)));
     68    protected override double EvaluateByDistanceMatrix(Permutation permutation, DistanceMatrix distanceMatrix) {
     69      var move = TwoPointFiveMoveParameter.ActualValue;
     70      var realizations = RealizationsParameter.ActualValue;
     71      return EvaluateByDistanceMatrix(permutation, distanceMatrix, move, realizations);
    11772    }
    11873
    119     private static int decreaseCircularIndex(int length, int index) {
    120       int result = index - 1;
    121       if (result == -1) {
    122         result = length - 1;
     74    public static double EvaluateByDistanceMatrix(Permutation permutation, DistanceMatrix distanceMatrix, TwoPointFiveMove move, ItemList<BoolArray> realizations) {
     75      if (move.IsInvert) {
     76        return PTSPEstimatedInversionMoveEvaluator.EvaluateByDistanceMatrix(permutation,
     77          new InversionMove(move.Index1, move.Index2, move.Permutation),
     78          distanceMatrix, realizations);
     79      } else {
     80        return PTSPEstimatedInsertionMoveEvaluator.EvaluateByDistanceMatrix(permutation,
     81          new TranslocationMove(move.Index1, move.Index1, move.Index2),
     82          distanceMatrix, realizations);
    12383      }
    124       return result;
    125     }
    126 
    127     private static int increaseCircularIndex(int length, int index) {
    128       int result = index + 1;
    129       if (result == length + 1) {
    130         result = 0;
    131       }
    132       return result;
    133     }
    134    
    135 
    136     public static double EvaluateInversionByDistanceMatrix(Permutation permutation, TwoPointFiveMove move, DistanceMatrix distanceMatrix, ItemList<ItemList<IntValue>> realizations) {
    137       double moveQuality = 0;
    138       int[] edges = new int[4];
    139       int[] indices = new int[4];
    140       edges[0] = permutation.GetCircular(move.Index1 - 1);
    141       indices[0] = decreaseCircularIndex(permutation.Length, move.Index1);
    142       edges[1] = permutation[move.Index1];
    143       indices[1] = move.Index1;
    144       edges[2] = permutation[move.Index2];
    145       indices[2] = move.Index2;
    146       edges[3] = permutation.GetCircular(move.Index2 + 1);
    147       indices[3] = increaseCircularIndex(permutation.Length, move.Index2);
    148       int[] aPosteriori = new int[4];
    149       foreach (ItemList<IntValue> realization in realizations) {
    150         for (int i = 0; i < edges.Length; i++) {
    151           if (realization[edges[i]].Value == 1) {
    152             aPosteriori[i] = edges[i];
    153           } else {
    154             int j = 1;
    155             if (i % 2 == 0) {
    156               // find nearest predecessor in realization if source edge
    157               while (realization[permutation.GetCircular(indices[i] - j)].Value == 0) {
    158                 j++;
    159               }
    160               aPosteriori[i] = permutation.GetCircular(indices[i] - j);
    161             } else {
    162               // find nearest successor in realization if target edge
    163               while (realization[permutation.GetCircular(indices[i] + j)].Value == 0) {
    164                 j++;
    165               }
    166               aPosteriori[i] = permutation.GetCircular(indices[i] + j);
    167             }
    168           }
    169         }
    170         // compute cost difference between the two a posteriori solutions
    171         if (!(aPosteriori[0] == aPosteriori[2] && aPosteriori[1] == aPosteriori[3])) {
    172           moveQuality = moveQuality + distanceMatrix[aPosteriori[0], aPosteriori[2]] + distanceMatrix[aPosteriori[1], aPosteriori[3]] - distanceMatrix[aPosteriori[0], aPosteriori[1]] - distanceMatrix[aPosteriori[2], aPosteriori[3]];
    173         }
    174         Array.Clear(aPosteriori, 0, aPosteriori.Length);
    175       }
    176       // return average of cost differences
    177       return moveQuality / realizations.Count;
    178     }
    179     public static double EvaluateInsertionByDistanceMatrix(Permutation permutation, TwoPointFiveMove move, DistanceMatrix distanceMatrix, ItemList<ItemList<IntValue>> realizations) {
    180       Permutation afterMove = new Permutation(PermutationTypes.RelativeUndirected, permutation);
    181       TranslocationManipulator.Apply(afterMove, move.Index1, move.Index1, move.Index2);
    182       double moveQuality = 0;
    183       int[] edges = new int[12];
    184       int[] indices = new int[12];
    185       edges[0] = permutation.GetCircular(move.Index1 - 1);
    186       indices[0] = decreaseCircularIndex(permutation.Length, move.Index1);
    187       edges[1] = permutation[move.Index1];
    188       indices[1] = move.Index1;
    189       edges[2] = permutation[move.Index1];
    190       indices[2] = move.Index1;
    191       edges[3] = permutation.GetCircular(move.Index1 + 1);
    192       indices[3] = increaseCircularIndex(permutation.Length, move.Index1);
    193 
    194       edges[6] = afterMove.GetCircular(move.Index2 - 1);
    195       indices[6] = decreaseCircularIndex(afterMove.Length, move.Index2);
    196       edges[7] = afterMove[move.Index2];
    197       indices[7] = move.Index2;
    198       edges[8] = afterMove[move.Index2];
    199       indices[8] = move.Index2;
    200       edges[9] = afterMove.GetCircular(move.Index2 + 1);
    201       indices[9] = increaseCircularIndex(afterMove.Length, move.Index2);
    202 
    203       if (move.Index2 > move.Index1) {
    204         edges[4] = permutation[move.Index2];
    205         indices[4] = move.Index2;
    206         edges[5] = permutation.GetCircular(move.Index2 + 1);
    207         indices[5] = indices[9];
    208         edges[10] = afterMove.GetCircular(move.Index1 - 1);
    209         indices[10] = indices[0];
    210         edges[11] = afterMove[move.Index1];
    211         indices[11] = move.Index1;
    212       } else {
    213         edges[4] = permutation.GetCircular(move.Index2 - 1);
    214         indices[4] = indices[6];
    215         edges[5] = permutation[move.Index2];
    216         indices[5] = move.Index2;
    217         edges[10] = afterMove[move.Index1];
    218         indices[10] = move.Index1;
    219         edges[11] = afterMove.GetCircular(move.Index1 + 1);
    220         indices[11] = indices[3];
    221       }
    222       int[] aPosteriori = new int[12];
    223       Permutation tempPermutation;
    224       foreach (ItemList<IntValue> realization in realizations) {
    225         for (int i = 0; i < edges.Length; i++) {
    226           if (i < 6) {
    227             tempPermutation = permutation;
    228           } else {
    229             tempPermutation = afterMove;
    230           }
    231           if (realization[edges[i]].Value == 1) {
    232             aPosteriori[i] = edges[i];
    233           } else {
    234             int j = 1;
    235             if (i % 2 == 0) {
    236               // find nearest predecessor in realization if source edge
    237               while (realization[tempPermutation.GetCircular(indices[i] - j)].Value == 0) {
    238                 j++;
    239               }
    240               aPosteriori[i] = tempPermutation.GetCircular(indices[i] - j);
    241             } else {
    242               // find nearest successor in realization if target edge
    243               while (realization[tempPermutation.GetCircular(indices[i] + j)].Value == 0) {
    244                 j++;
    245               }
    246               aPosteriori[i] = tempPermutation.GetCircular(indices[i] + j);
    247             }
    248           }
    249         }
    250         if (!(aPosteriori[0] == aPosteriori[2] && aPosteriori[1] == aPosteriori[3]) &&
    251           !(aPosteriori[0] == aPosteriori[4] && aPosteriori[1] == aPosteriori[5]) &&
    252           !(aPosteriori[2] == aPosteriori[4] && aPosteriori[3] == aPosteriori[5])) {
    253           // compute cost difference between the two a posteriori solutions
    254           moveQuality = moveQuality + distanceMatrix[aPosteriori[6], aPosteriori[7]] + distanceMatrix[aPosteriori[8], aPosteriori[9]] + distanceMatrix[aPosteriori[10], aPosteriori[11]];
    255           moveQuality = moveQuality - distanceMatrix[aPosteriori[0], aPosteriori[1]] - distanceMatrix[aPosteriori[2], aPosteriori[3]] - distanceMatrix[aPosteriori[4], aPosteriori[5]];
    256         }
    257         Array.Clear(aPosteriori, 0, aPosteriori.Length);
    258       }
    259       // return average of cost differences
    260       return moveQuality / realizations.Count;
    261     }
    262     protected double EvaluateByDistanceMatrix(Permutation permutation, DistanceMatrix distanceMatrix) {
    263       TwoPointFiveMove currentMove = TwoPointFiveMoveParameter.ActualValue;
    264       if (currentMove.IsInvert) {
    265         return EvaluateInversionByDistanceMatrix(permutation, currentMove, distanceMatrix, RealizationsParameter.Value);
    266       } else {
    267         return EvaluateInsertionByDistanceMatrix(permutation, currentMove, distanceMatrix, RealizationsParameter.Value);
    268       }
    269     }
    270 
    271     private DistanceMatrix CalculateDistanceMatrix(DoubleMatrix c) {
    272       DistanceMatrix distanceMatrix = new DistanceMatrix(c.Rows, c.Rows);
    273       for (int i = 0; i < distanceMatrix.Rows; i++) {
    274         for (int j = 0; j < distanceMatrix.Columns; j++)
    275           distanceMatrix[i, j] = CalculateDistance(c[i, 0], c[i, 1], c[j, 0], c[j, 1]);
    276       }
    277       return (DistanceMatrix)distanceMatrix.AsReadOnly();
    27884    }
    27985  }
  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Moves/TwoPointFiveOpt/StochasticTwoPointFiveMultiMoveGenerator.cs

    r13408 r13412  
    2424using HeuristicLab.Data;
    2525using HeuristicLab.Encodings.PermutationEncoding;
    26 using HeuristicLab.Operators;
    2726using HeuristicLab.Optimization;
    2827using HeuristicLab.Parameters;
     
    3029
    3130namespace HeuristicLab.Problems.PTSP {
    32   [Item("Stochastic25MultiMoveGenerator", "Randomly samples n from all possible inversion and shift moves (2.5-opt) from a given permutation.")]
     31  [Item("Stochastic 2.5-MultiMoveGenerator", "Randomly samples n from all possible inversion and shift moves (2.5-opt) from a given permutation.")]
    3332  [StorableClass]
    34   class Stochastic25MultiMoveGenerator : TwoPointFiveMoveGenerator, IMultiMoveGenerator, IStochasticOperator {
     33  public sealed class StochasticTwoPointFiveMultiMoveGenerator : TwoPointFiveMoveGenerator, IMultiMoveGenerator, IStochasticOperator {
    3534    public ILookupParameter<IRandom> RandomParameter {
    3635      get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
     
    4645
    4746    [StorableConstructor]
    48     protected Stochastic25MultiMoveGenerator(bool deserializing) : base(deserializing) { }
    49     protected Stochastic25MultiMoveGenerator(Stochastic25MultiMoveGenerator original, Cloner cloner) : base(original, cloner) { }
    50     public Stochastic25MultiMoveGenerator()
     47    private StochasticTwoPointFiveMultiMoveGenerator(bool deserializing) : base(deserializing) { }
     48    private StochasticTwoPointFiveMultiMoveGenerator(StochasticTwoPointFiveMultiMoveGenerator original, Cloner cloner) : base(original, cloner) { }
     49    public StochasticTwoPointFiveMultiMoveGenerator()
    5150      : base() {
    5251      Parameters.Add(new LookupParameter<IRandom>("Random", "The random number generator."));
     
    5554
    5655    public override IDeepCloneable Clone(Cloner cloner) {
    57       return new Stochastic25MultiMoveGenerator(this, cloner);
     56      return new StochasticTwoPointFiveMultiMoveGenerator(this, cloner);
    5857    }
    5958
    6059    public static TwoPointFiveMove[] Apply(Permutation permutation, IRandom random, int sampleSize) {
    61       int length = permutation.Length;
    62       TwoPointFiveMove[] moves = new TwoPointFiveMove[sampleSize];
    63       for (int i = 0; i < sampleSize; i++) {
    64         moves[i] = Stochastic25SingleMoveGenerator.Apply(permutation, random);
     60      var moves = new TwoPointFiveMove[sampleSize];
     61      for (var i = 0; i < sampleSize; i++) {
     62        moves[i] = StochasticTwoPointFiveSingleMoveGenerator.Apply(permutation, random);
    6563      }
    6664      return moves;
     
    6866
    6967    protected override TwoPointFiveMove[] GenerateMoves(Permutation permutation) {
    70       IRandom random = RandomParameter.ActualValue;
    71       return Apply(permutation, random, SampleSizeParameter.ActualValue.Value);
     68      return Apply(permutation, RandomParameter.ActualValue, SampleSizeParameter.ActualValue.Value);
    7269    }
    7370  }
  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Moves/TwoPointFiveOpt/StochasticTwoPointFiveSingleMoveGenerator.cs

    r13408 r13412  
    2323using HeuristicLab.Common;
    2424using HeuristicLab.Core;
     25using HeuristicLab.Encodings.PermutationEncoding;
    2526using HeuristicLab.Optimization;
    2627using HeuristicLab.Parameters;
    2728using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    28 using HeuristicLab.Operators;
    29 using HeuristicLab.Encodings.PermutationEncoding;
    30 
    3129
    3230namespace HeuristicLab.Problems.PTSP {
    33   [Item("Stochastic25SingleMoveGenerator", "Randomly samples a single from all possible inversion and shift moves (2.5-opt) from a given permutation.")]
     31  [Item("Stochastic 2.5-SingleMoveGenerator", "Randomly samples a single from all possible inversion and shift moves (2.5-opt) from a given permutation.")]
    3432  [StorableClass]
    35   class Stochastic25SingleMoveGenerator : TwoPointFiveMoveGenerator, IStochasticOperator, ISingleMoveGenerator {
     33  public sealed class StochasticTwoPointFiveSingleMoveGenerator : TwoPointFiveMoveGenerator, IStochasticOperator, ISingleMoveGenerator {
    3634    public ILookupParameter<IRandom> RandomParameter {
    3735      get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
     
    3937
    4038    [StorableConstructor]
    41     protected Stochastic25SingleMoveGenerator(bool deserializing) : base(deserializing) { }
    42     protected Stochastic25SingleMoveGenerator(Stochastic25SingleMoveGenerator original, Cloner cloner) : base(original, cloner) { }
    43     public Stochastic25SingleMoveGenerator()
     39    private StochasticTwoPointFiveSingleMoveGenerator(bool deserializing) : base(deserializing) { }
     40    private StochasticTwoPointFiveSingleMoveGenerator(StochasticTwoPointFiveSingleMoveGenerator original, Cloner cloner) : base(original, cloner) { }
     41    public StochasticTwoPointFiveSingleMoveGenerator()
    4442      : base() {
    4543      Parameters.Add(new LookupParameter<IRandom>("Random", "The random number generator."));
     
    4745
    4846    public override IDeepCloneable Clone(Cloner cloner) {
    49       return new Stochastic25SingleMoveGenerator(this, cloner);
     47      return new StochasticTwoPointFiveSingleMoveGenerator(this, cloner);
    5048    }
    5149
    5250    public static TwoPointFiveMove Apply(Permutation permutation, IRandom random) {
    5351      int length = permutation.Length;
    54       if (length == 1) throw new ArgumentException("Stochastic25SingleMoveGenerator: There cannot be an inversion move given a permutation of length 1.", "permutation");
     52      if (length == 1) throw new ArgumentException("Stochastic 2.5-SingleMoveGenerator: There cannot be an inversion move given a permutation of length 1.", "permutation");
    5553      int index1 = random.Next(length - 1);
    5654      int index2 = random.Next(index1 + 1, length);
     
    6361      bool isInvert = random.NextDouble() > 0.5;
    6462      return new TwoPointFiveMove(index1, index2, isInvert);
    65      
     63
    6664    }
    6765
    6866    protected override TwoPointFiveMove[] GenerateMoves(Permutation permutation) {
    69       IRandom random = RandomParameter.ActualValue;
    70       return new TwoPointFiveMove[] { Apply(permutation, random) };
     67      return new[] { Apply(permutation, RandomParameter.ActualValue) };
    7168    }
    7269  }
  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Moves/TwoPointFiveOpt/TwoPointFiveMove.cs

    r12272 r13412  
    1 using HeuristicLab.Common;
     1#region License Information
     2/* HeuristicLab
     3 * Copyright (C) 2002-2015 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 HeuristicLab.Common;
    223using HeuristicLab.Core;
    324using HeuristicLab.Encodings.PermutationEncoding;
     
    526
    627namespace HeuristicLab.Problems.PTSP {
    7   public class TwoPointFiveMove : Item {
    8    
     28  [Item("2.5-Move", "Represents a 2.5-move.")]
     29  [StorableClass]
     30  public sealed class TwoPointFiveMove : Item {
     31    [Storable]
     32    public int Index1 { get; protected set; }
     33    [Storable]
     34    public int Index2 { get; protected set; }
     35    [Storable]
     36    public Permutation Permutation { get; protected set; }
     37    [Storable]
     38    public bool IsInvert { get; protected set; }
     39
    940    [StorableConstructor]
    10     public TwoPointFiveMove() : this(-1, -1,null, true) { }
    11     protected TwoPointFiveMove(bool deserializing) : base(deserializing) { }
    12     protected TwoPointFiveMove(TwoPointFiveMove original, Cloner cloner)
     41    public TwoPointFiveMove() : this(-1, -1, null, true) { }
     42    private TwoPointFiveMove(bool deserializing) : base(deserializing) { }
     43    private TwoPointFiveMove(TwoPointFiveMove original, Cloner cloner)
    1344      : base(original, cloner) {
    1445      this.Index1 = original.Index1;
    1546      this.Index2 = original.Index2;
    1647      this.IsInvert = original.IsInvert;
    17       if (original.Permutation != null)
    18         this.Permutation = cloner.Clone(original.Permutation);
     48      this.Permutation = cloner.Clone(original.Permutation);
    1949    }
    2050    public TwoPointFiveMove(int index1, int index2, Permutation permutation, bool isinvert)
     
    3464    }
    3565
    36     [Storable]
    37     public int Index1 { get; protected set; }
    38     [Storable]
    39     public int Index2 { get; protected set; }
    40     [Storable]
    41     public Permutation Permutation { get; protected set; }
    42     [Storable]
    43     public bool IsInvert { get; protected set; }
    44 
    4566    public override IDeepCloneable Clone(Cloner cloner) {
    4667      return new TwoPointFiveMove(this, cloner);
  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Moves/TwoPointFiveOpt/TwoPointFiveMoveGenerator.cs

    r13408 r13412  
    3232  [Item("TwoPointFiveMoveGenerator", "Base class for all inversion and shift (2.5-opt) move generators.")]
    3333  [StorableClass]
    34   public abstract class TwoPointFiveMoveGenerator : SingleSuccessorOperator, I25MoveOperator, IMoveGenerator {
     34  public abstract class TwoPointFiveMoveGenerator : SingleSuccessorOperator, ITwoPointFiveMoveOperator, IMoveGenerator {
    3535    public override bool CanChangeName {
    3636      get { return false; }
    3737    }
     38
    3839    public ILookupParameter<Permutation> PermutationParameter {
    3940      get { return (ILookupParameter<Permutation>)Parameters["Permutation"]; }
     
    4243      get { return (LookupParameter<TwoPointFiveMove>)Parameters["TwoPointFiveMove"]; }
    4344    }
    44     protected ScopeParameter CurrentScopeParameter {
    45       get { return (ScopeParameter)Parameters["CurrentScope"]; }
    46     }
    4745
    4846    [StorableConstructor]
    4947    protected TwoPointFiveMoveGenerator(bool deserializing) : base(deserializing) { }
    5048    protected TwoPointFiveMoveGenerator(TwoPointFiveMoveGenerator original, Cloner cloner) : base(original, cloner) { }
    51     public TwoPointFiveMoveGenerator()
     49    protected TwoPointFiveMoveGenerator()
    5250      : base() {
    5351      Parameters.Add(new LookupParameter<Permutation>("Permutation", "The permutation for which moves should be generated."));
     
    5755
    5856    public override IOperation Apply() {
    59       Permutation p = PermutationParameter.ActualValue;
    60       TwoPointFiveMove[] moves = GenerateMoves(p);
    61       Scope[] moveScopes = new Scope[moves.Length];
     57      var p = PermutationParameter.ActualValue;
     58      var moves = GenerateMoves(p);
     59      var moveScopes = new Scope[moves.Length];
    6260      for (int i = 0; i < moveScopes.Length; i++) {
    6361        moveScopes[i] = new Scope(i.ToString());
    6462        moveScopes[i].Variables.Add(new Variable(TwoPointFiveMoveParameter.ActualName, moves[i]));
    6563      }
    66       CurrentScopeParameter.ActualValue.SubScopes.AddRange(moveScopes);
     64      ExecutionContext.Scope.SubScopes.AddRange(moveScopes);
    6765      return base.Apply();
    6866    }
  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Moves/TwoPointFiveOpt/TwoPointFiveMoveMaker.cs

    r13408 r13412  
    1 using HeuristicLab.Common;
     1#region License Information
     2/* HeuristicLab
     3 * Copyright (C) 2002-2015 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 HeuristicLab.Common;
    223using HeuristicLab.Core;
    324using HeuristicLab.Data;
     
    1132  [Item("TwoPointFiveMoveMaker", "Peforms an inversion and shift (2.5-opt) on a given permutation and updates the quality.")]
    1233  [StorableClass]
    13   public class TwoPointFiveMoveMaker : SingleSuccessorOperator, I25MoveOperator, IMoveMaker {
     34  public class TwoPointFiveMoveMaker : SingleSuccessorOperator, ITwoPointFiveMoveOperator, IMoveMaker {
    1435    public override bool CanChangeName {
    1536      get { return false; }
    1637    }
     38
    1739    public ILookupParameter<DoubleValue> QualityParameter {
    1840      get { return (ILookupParameter<DoubleValue>)Parameters["Quality"]; }
     
    2749      get { return (ILookupParameter<Permutation>)Parameters["Permutation"]; }
    2850    }
     51
    2952    [StorableConstructor]
    3053    protected TwoPointFiveMoveMaker(bool deserializing) : base(deserializing) { }
     
    4366
    4467    public override IOperation Apply() {
    45       TwoPointFiveMove move = TwoPointFiveMoveParameter.ActualValue;
    46       Permutation permutation = PermutationParameter.ActualValue;
    47       DoubleValue moveQuality = MoveQualityParameter.ActualValue;
    48       DoubleValue quality = QualityParameter.ActualValue;
     68      var move = TwoPointFiveMoveParameter.ActualValue;
     69      var permutation = PermutationParameter.ActualValue;
     70      var moveQuality = MoveQualityParameter.ActualValue;
     71      var quality = QualityParameter.ActualValue;
    4972
    5073      if (move.IsInvert) {
     
    5376        TranslocationManipulator.Apply(permutation, move.Index1, move.Index1, move.Index2);
    5477      }
    55      
     78
    5679      quality.Value = moveQuality.Value;
    5780
  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/PTSP.cs

    r13202 r13412  
    2020#endregion
    2121
     22using System;
    2223using HeuristicLab.Common;
    2324using HeuristicLab.Core;
     
    3031
    3132namespace HeuristicLab.Problems.PTSP {
    32   [Item("Probabilistic Traveling Salesman Problem", "Represents a Probabilistic Traveling Salesman Problem.")]
     33  [Item("Probabilistic Traveling Salesman Problem (PTSP)", "Represents a Probabilistic Traveling Salesman Problem.")]
    3334  [StorableClass]
    34   public abstract class ProbabilisticTravelingSalesmanProblem : SingleObjectiveBasicProblem<PermutationEncoding>, IStorableContent,
     35  public abstract class ProbabilisticTravelingSalesmanProblem : SingleObjectiveBasicProblem<PermutationEncoding>,
    3536  IProblemInstanceConsumer<PTSPData> {
    3637    private static readonly int DistanceMatrixSizeLimit = 1000;
     
    4041      get { return (OptionalValueParameter<DoubleMatrix>)Parameters["Coordinates"]; }
    4142    }
     43    public OptionalValueParameter<DistanceCalculator> DistanceCalculatorParameter {
     44      get { return (OptionalValueParameter<DistanceCalculator>)Parameters["DistanceCalculator"]; }
     45    }
    4246    public OptionalValueParameter<DistanceMatrix> DistanceMatrixParameter {
    4347      get { return (OptionalValueParameter<DistanceMatrix>)Parameters["DistanceMatrix"]; }
    4448    }
    45     public ValueParameter<BoolValue> UseDistanceMatrixParameter {
    46       get { return (ValueParameter<BoolValue>)Parameters["UseDistanceMatrix"]; }
     49    public IFixedValueParameter<BoolValue> UseDistanceMatrixParameter {
     50      get { return (IFixedValueParameter<BoolValue>)Parameters["UseDistanceMatrix"]; }
    4751    }
    4852    public OptionalValueParameter<Permutation> BestKnownSolutionParameter {
    4953      get { return (OptionalValueParameter<Permutation>)Parameters["BestKnownSolution"]; }
    5054    }
    51     public ValueParameter<DoubleArray> ProbabilityMatrixParameter {
    52       get { return (ValueParameter<DoubleArray>)Parameters["ProbabilityMatrix"]; }
     55    public IValueParameter<DoubleArray> ProbabilitiesParameter {
     56      get { return (IValueParameter<DoubleArray>)Parameters["Probabilities"]; }
    5357    }
    54 
    55 
    5658    #endregion
    5759
     
    6163      set { CoordinatesParameter.Value = value; }
    6264    }
     65    public DistanceCalculator DistanceCalculator {
     66      get { return DistanceCalculatorParameter.Value; }
     67      set { DistanceCalculatorParameter.Value = value; }
     68    }
    6369    public DistanceMatrix DistanceMatrix {
    6470      get { return DistanceMatrixParameter.Value; }
    6571      set { DistanceMatrixParameter.Value = value; }
    6672    }
    67     public BoolValue UseDistanceMatrix {
    68       get { return UseDistanceMatrixParameter.Value; }
    69       set { UseDistanceMatrixParameter.Value = value; }
     73    public bool UseDistanceMatrix {
     74      get { return UseDistanceMatrixParameter.Value.Value; }
     75      set { UseDistanceMatrixParameter.Value.Value = value; }
    7076    }
    7177    public Permutation BestKnownSolution {
     
    7379      set { BestKnownSolutionParameter.Value = value; }
    7480    }
    75     public DoubleArray ProbabilityMatrix {
    76       get { return ProbabilityMatrixParameter.Value; }
    77       set { ProbabilityMatrixParameter.Value = value; }
     81    public DoubleArray Probabilities {
     82      get { return ProbabilitiesParameter.Value; }
     83      set { ProbabilitiesParameter.Value = value; }
    7884    }
    7985
    8086    #endregion
    81 
    8287
    8388    public override bool Maximization {
     
    8792    [StorableConstructor]
    8893    protected ProbabilisticTravelingSalesmanProblem(bool deserializing) : base(deserializing) { }
    89     protected ProbabilisticTravelingSalesmanProblem(ProbabilisticTravelingSalesmanProblem original, Cloner cloner)
    90       : base(original, cloner) {
    91     }
    92 
    93     public ProbabilisticTravelingSalesmanProblem() {
     94    protected ProbabilisticTravelingSalesmanProblem(ProbabilisticTravelingSalesmanProblem original, Cloner cloner) : base(original, cloner) { }
     95    protected ProbabilisticTravelingSalesmanProblem() {
    9496      Parameters.Add(new OptionalValueParameter<DoubleMatrix>("Coordinates", "The x- and y-Coordinates of the cities."));
     97      Parameters.Add(new OptionalValueParameter<DistanceCalculator>("DistanceCalculator", "Calculates the distance between two rows in the coordinates matrix."));
    9598      Parameters.Add(new OptionalValueParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
    96       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)));
     99      Parameters.Add(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)));
    97100      Parameters.Add(new OptionalValueParameter<Permutation>("BestKnownSolution", "The best known solution of this TSP instance."));
    98       Parameters.Add(new ValueParameter<DoubleArray>("ProbabilityMatrix", "The matrix which contains the probabilities of each of the cities."));
     101      Parameters.Add(new ValueParameter<DoubleArray>("Probabilities", "This list describes for each city the probability of appearing in a realized instance."));
    99102
    100103      Coordinates = new DoubleMatrix(new double[,] {
     
    105108      });
    106109
    107       ProbabilityMatrix = new DoubleArray(new double[] { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 });
     110      Probabilities = new DoubleArray(new double[] { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 });
     111    }
    108112
     113    public override double Evaluate(Individual individual, IRandom random) {
     114      return Evaluate(individual.Permutation(), random);
    109115    }
     116
     117    public abstract double Evaluate(Permutation tour, IRandom random);
    110118
    111119    public virtual void Load(PTSPData data) {
    112120      if (data.Coordinates == null && data.Distances == null)
    113121        throw new System.IO.InvalidDataException("The given instance specifies neither coordinates nor distances!");
    114       if (data.Dimension > DistanceMatrixSizeLimit && (data.DistanceMeasure == DistanceMeasure.Att
    115         || data.DistanceMeasure == DistanceMeasure.Manhattan
    116         || data.DistanceMeasure == DistanceMeasure.Maximum))
    117         throw new System.IO.InvalidDataException("The given instance uses an unsupported distance measure and is too large for using a distance matrix.");
    118       if (data.Coordinates != null && data.Coordinates.GetLength(1) != 2)
    119         throw new System.IO.InvalidDataException("The coordinates of the given instance are not in the right format, there need to be one row for each customer and two columns for the x and y coordinates.");
     122      if (data.Dimension > DistanceMatrixSizeLimit && (data.Coordinates == null || data.Coordinates.GetLength(0) != data.Dimension || data.Coordinates.GetLength(1) != 2))
     123        throw new System.IO.InvalidDataException("The given instance is too large for using a distance matrix and there is a problem with the coordinates.");
     124      if (data.Coordinates != null && (data.Coordinates.GetLength(0) != data.Dimension || data.Coordinates.GetLength(1) != 2))
     125        throw new System.IO.InvalidDataException("The coordinates of the given instance are not in the right format, there need to be one row for each customer and two columns for the x and y coordinates respectively.");
     126
     127      switch (data.DistanceMeasure) {
     128        case DistanceMeasure.Direct:
     129          DistanceCalculator = null;
     130          if (data.Dimension > DistanceMatrixSizeLimit && Coordinates != null) {
     131            DistanceCalculator = new EuclideanDistance();
     132            UseDistanceMatrix = false;
     133          } else UseDistanceMatrix = true;
     134          break;
     135        case DistanceMeasure.Att: DistanceCalculator = new AttDistance(); break;
     136        case DistanceMeasure.Euclidean: DistanceCalculator = new EuclideanDistance(); break;
     137        case DistanceMeasure.Geo: DistanceCalculator = new GeoDistance(); break;
     138        case DistanceMeasure.Manhattan: DistanceCalculator = new ManhattanDistance(); break;
     139        case DistanceMeasure.Maximum: DistanceCalculator = new MaximumDistance(); break;
     140        case DistanceMeasure.RoundedEuclidean: DistanceCalculator = new RoundedEuclideanDistance(); break;
     141        case DistanceMeasure.UpperEuclidean: DistanceCalculator = new UpperEuclideanDistance(); break;
     142        default: throw new ArgumentException("Distance measure is unknown");
     143      }
    120144
    121145      Name = data.Name;
    122146      Description = data.Description;
    123147
    124       ProbabilityMatrix = new DoubleArray(data.Probabilities);
    125 
    126       if (data.BestKnownTour != null) {
    127         BestKnownSolution = new Permutation(PermutationTypes.RelativeUndirected, data.BestKnownTour);
    128       }
    129 
     148      Probabilities = new DoubleArray(data.Probabilities);
     149      BestKnownSolution = data.BestKnownTour != null ? new Permutation(PermutationTypes.RelativeUndirected, data.BestKnownTour) : null;
    130150      Coordinates = data.Coordinates != null && data.Coordinates.GetLength(0) > 0 ? new DoubleMatrix(data.Coordinates) : null;
    131151      DistanceMatrix = new DistanceMatrix(data.GetDistanceMatrix());
  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Plugin.cs.frame

    r12317 r13412  
    1 using HeuristicLab.PluginInfrastructure;
     1#region License Information
     2/* HeuristicLab
     3 * Copyright (C) 2002-2015 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 HeuristicLab.PluginInfrastructure;
     23
    224namespace HeuristicLab.Problems.PTSP {
    3     [Plugin("HeuristicLab.Problems.PTSP", "Provides an implementation of the PTSP", "3.3.11.$WCREV$")]
    4     [PluginFile("HeuristicLab.Problems.PTSP-3.3.dll", PluginFileType.Assembly)]
    5   [PluginDependency("HeuristicLab.Collections", "3.3")]
    6   [PluginDependency("HeuristicLab.Common", "3.3")]
    7   [PluginDependency("HeuristicLab.Common.Resources", "3.3")]
    8   [PluginDependency("HeuristicLab.Core", "3.3")]
    9   [PluginDependency("HeuristicLab.Data", "3.3")]
    10   [PluginDependency("HeuristicLab.Encodings.PermutationEncoding", "3.3")]
    11   [PluginDependency("HeuristicLab.Operators", "3.3")]
    12   [PluginDependency("HeuristicLab.Optimization", "3.3")]
    13   [PluginDependency("HeuristicLab.Parameters", "3.3")]
    14   [PluginDependency("HeuristicLab.Persistence", "3.3")]
    15   [PluginDependency("HeuristicLab.Problems.Instances", "3.3")]
    16   [PluginDependency("HeuristicLab.Random", "3.3")]
    17     public class Plugin : PluginBase {
    18     }
     25  [Plugin("HeuristicLab.Problems.PTSP", "Provides an implementation of the probabilistic traveling salesman problem (PTSP)", "3.3.13.$WCREV$")]
     26  [PluginFile("HeuristicLab.Problems.PTSP-3.3.dll", PluginFileType.Assembly)]
     27  [PluginDependency("HeuristicLab.Collections", "3.3")]
     28  [PluginDependency("HeuristicLab.Common", "3.3")]
     29  [PluginDependency("HeuristicLab.Common.Resources", "3.3")]
     30  [PluginDependency("HeuristicLab.Core", "3.3")]
     31  [PluginDependency("HeuristicLab.Data", "3.3")]
     32  [PluginDependency("HeuristicLab.Encodings.PermutationEncoding", "3.3")]
     33  [PluginDependency("HeuristicLab.Operators", "3.3")]
     34  [PluginDependency("HeuristicLab.Optimization", "3.3")]
     35  [PluginDependency("HeuristicLab.Parameters", "3.3")]
     36  [PluginDependency("HeuristicLab.Persistence", "3.3")]
     37  [PluginDependency("HeuristicLab.Problems.Instances", "3.3")]
     38  [PluginDependency("HeuristicLab.Random", "3.3")]
     39  public class HeuristicLabProblemsPTSPPlugin : PluginBase {
     40  }
    1941}
  • branches/PTSP/PTSP.sln

    r12261 r13412  
    22Microsoft Visual Studio Solution File, Format Version 12.00
    33# Visual Studio 2013
    4 VisualStudioVersion = 12.0.31101.0
     4VisualStudioVersion = 12.0.40629.0
    55MinimumVisualStudioVersion = 10.0.40219.1
    66Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Problems.PTSP-3.3", "HeuristicLab.Problems.PTSP\3.3\HeuristicLab.Problems.PTSP-3.3.csproj", "{97198965-AFEA-496B-B3B1-316905C43FD6}"
     
    1010Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Problems.PTSP.Tests-3.3", "HeuristicLab.Problems.PTSP.Tests-3.3\HeuristicLab.Problems.PTSP.Tests-3.3.csproj", "{CBEC171A-F7EC-460D-94E2-D58625811D99}"
    1111EndProject
     12Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Problems.Instances.TSPLIB-3.3", "HeuristicLab.Problems.Instances.TSPLIB\3.3\HeuristicLab.Problems.Instances.TSPLIB-3.3.csproj", "{CE0F99D6-1C56-48A9-9B68-3E5B833703EF}"
     13EndProject
     14Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Problems.Instances-3.3", "HeuristicLab.Problems.Instances\3.3\HeuristicLab.Problems.Instances-3.3.csproj", "{3540E29E-4793-49E7-8EE2-FEA7F61C3994}"
     15EndProject
    1216Global
    1317  GlobalSection(SolutionConfigurationPlatforms) = preSolution
    1418    Debug|Any CPU = Debug|Any CPU
     19    Debug|x64 = Debug|x64
     20    Debug|x86 = Debug|x86
    1521    Release|Any CPU = Release|Any CPU
     22    Release|x64 = Release|x64
     23    Release|x86 = Release|x86
    1624  EndGlobalSection
    1725  GlobalSection(ProjectConfigurationPlatforms) = postSolution
    1826    {97198965-AFEA-496B-B3B1-316905C43FD6}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
    1927    {97198965-AFEA-496B-B3B1-316905C43FD6}.Debug|Any CPU.Build.0 = Debug|Any CPU
     28    {97198965-AFEA-496B-B3B1-316905C43FD6}.Debug|x64.ActiveCfg = Debug|Any CPU
     29    {97198965-AFEA-496B-B3B1-316905C43FD6}.Debug|x86.ActiveCfg = Debug|Any CPU
    2030    {97198965-AFEA-496B-B3B1-316905C43FD6}.Release|Any CPU.ActiveCfg = Release|Any CPU
    2131    {97198965-AFEA-496B-B3B1-316905C43FD6}.Release|Any CPU.Build.0 = Release|Any CPU
     32    {97198965-AFEA-496B-B3B1-316905C43FD6}.Release|x64.ActiveCfg = Release|Any CPU
     33    {97198965-AFEA-496B-B3B1-316905C43FD6}.Release|x86.ActiveCfg = Release|Any CPU
    2234    {90B6CA12-9791-4430-B2D7-CD3ED7F75E2B}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
    2335    {90B6CA12-9791-4430-B2D7-CD3ED7F75E2B}.Debug|Any CPU.Build.0 = Debug|Any CPU
     36    {90B6CA12-9791-4430-B2D7-CD3ED7F75E2B}.Debug|x64.ActiveCfg = Debug|Any CPU
     37    {90B6CA12-9791-4430-B2D7-CD3ED7F75E2B}.Debug|x86.ActiveCfg = Debug|Any CPU
    2438    {90B6CA12-9791-4430-B2D7-CD3ED7F75E2B}.Release|Any CPU.ActiveCfg = Release|Any CPU
    2539    {90B6CA12-9791-4430-B2D7-CD3ED7F75E2B}.Release|Any CPU.Build.0 = Release|Any CPU
     40    {90B6CA12-9791-4430-B2D7-CD3ED7F75E2B}.Release|x64.ActiveCfg = Release|Any CPU
     41    {90B6CA12-9791-4430-B2D7-CD3ED7F75E2B}.Release|x86.ActiveCfg = Release|Any CPU
    2642    {CBEC171A-F7EC-460D-94E2-D58625811D99}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
    2743    {CBEC171A-F7EC-460D-94E2-D58625811D99}.Debug|Any CPU.Build.0 = Debug|Any CPU
     44    {CBEC171A-F7EC-460D-94E2-D58625811D99}.Debug|x64.ActiveCfg = Debug|Any CPU
     45    {CBEC171A-F7EC-460D-94E2-D58625811D99}.Debug|x86.ActiveCfg = Debug|Any CPU
    2846    {CBEC171A-F7EC-460D-94E2-D58625811D99}.Release|Any CPU.ActiveCfg = Release|Any CPU
    2947    {CBEC171A-F7EC-460D-94E2-D58625811D99}.Release|Any CPU.Build.0 = Release|Any CPU
     48    {CBEC171A-F7EC-460D-94E2-D58625811D99}.Release|x64.ActiveCfg = Release|Any CPU
     49    {CBEC171A-F7EC-460D-94E2-D58625811D99}.Release|x86.ActiveCfg = Release|Any CPU
     50    {CE0F99D6-1C56-48A9-9B68-3E5B833703EF}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
     51    {CE0F99D6-1C56-48A9-9B68-3E5B833703EF}.Debug|Any CPU.Build.0 = Debug|Any CPU
     52    {CE0F99D6-1C56-48A9-9B68-3E5B833703EF}.Debug|x64.ActiveCfg = Debug|x64
     53    {CE0F99D6-1C56-48A9-9B68-3E5B833703EF}.Debug|x64.Build.0 = Debug|x64
     54    {CE0F99D6-1C56-48A9-9B68-3E5B833703EF}.Debug|x86.ActiveCfg = Debug|x86
     55    {CE0F99D6-1C56-48A9-9B68-3E5B833703EF}.Debug|x86.Build.0 = Debug|x86
     56    {CE0F99D6-1C56-48A9-9B68-3E5B833703EF}.Release|Any CPU.ActiveCfg = Release|Any CPU
     57    {CE0F99D6-1C56-48A9-9B68-3E5B833703EF}.Release|Any CPU.Build.0 = Release|Any CPU
     58    {CE0F99D6-1C56-48A9-9B68-3E5B833703EF}.Release|x64.ActiveCfg = Release|x64
     59    {CE0F99D6-1C56-48A9-9B68-3E5B833703EF}.Release|x64.Build.0 = Release|x64
     60    {CE0F99D6-1C56-48A9-9B68-3E5B833703EF}.Release|x86.ActiveCfg = Release|x86
     61    {CE0F99D6-1C56-48A9-9B68-3E5B833703EF}.Release|x86.Build.0 = Release|x86
     62    {3540E29E-4793-49E7-8EE2-FEA7F61C3994}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
     63    {3540E29E-4793-49E7-8EE2-FEA7F61C3994}.Debug|Any CPU.Build.0 = Debug|Any CPU
     64    {3540E29E-4793-49E7-8EE2-FEA7F61C3994}.Debug|x64.ActiveCfg = Debug|x64
     65    {3540E29E-4793-49E7-8EE2-FEA7F61C3994}.Debug|x64.Build.0 = Debug|x64
     66    {3540E29E-4793-49E7-8EE2-FEA7F61C3994}.Debug|x86.ActiveCfg = Debug|x86
     67    {3540E29E-4793-49E7-8EE2-FEA7F61C3994}.Debug|x86.Build.0 = Debug|x86
     68    {3540E29E-4793-49E7-8EE2-FEA7F61C3994}.Release|Any CPU.ActiveCfg = Release|Any CPU
     69    {3540E29E-4793-49E7-8EE2-FEA7F61C3994}.Release|Any CPU.Build.0 = Release|Any CPU
     70    {3540E29E-4793-49E7-8EE2-FEA7F61C3994}.Release|x64.ActiveCfg = Release|x64
     71    {3540E29E-4793-49E7-8EE2-FEA7F61C3994}.Release|x64.Build.0 = Release|x64
     72    {3540E29E-4793-49E7-8EE2-FEA7F61C3994}.Release|x86.ActiveCfg = Release|x86
     73    {3540E29E-4793-49E7-8EE2-FEA7F61C3994}.Release|x86.Build.0 = Release|x86
    3074  EndGlobalSection
    3175  GlobalSection(SolutionProperties) = preSolution
Note: See TracChangeset for help on using the changeset viewer.