Changeset 12228


Ignore:
Timestamp:
03/19/15 17:16:39 (7 years ago)
Author:
apolidur
Message:

#2221: Local improvement operator for VNS

Location:
branches/PTSP
Files:
4 added
6 edited

Legend:

Unmodified
Added
Removed
  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/AnalyticalPTSP.cs

    r12219 r12228  
    6666      for (int i = 0; i < p.Length - 1; i++) {
    6767        for (int j = i + 1; j < p.Length - 1; j++) {
    68           double sum1 = DistanceMatrix[p[i], p[j]] * ProbabilityMatrix[p[i]].Value * ProbabilityMatrix[p[j]].Value;
     68          double sum1 = DistanceMatrix[p[i], p[j]] * ProbabilityMatrix[p[i]] * ProbabilityMatrix[p[j]];
    6969          for (int k = i + 1; k < j; k++) {
    70             sum1 = sum1 * (1 - ProbabilityMatrix[p[k]].Value);
     70            sum1 = sum1 * (1 - ProbabilityMatrix[p[k]]);
    7171          }
    7272          A[i, j - 1] = sum1;
     
    7777      for (int j = 0; j < p.Length - 1; j++) {
    7878        for (int i = 0; i < j; i++) {
    79           double sum2 = DistanceMatrix[p[j], p[i]] * ProbabilityMatrix[p[i]].Value * ProbabilityMatrix[p[j]].Value;
     79          double sum2 = DistanceMatrix[p[j], p[i]] * ProbabilityMatrix[p[i]] * ProbabilityMatrix[p[j]];
    8080          for (int k = j + 1; k < p.Length - 1; k++) {
    81             sum2 = sum2 * (1 - ProbabilityMatrix[p[k]].Value);
     81            sum2 = sum2 * (1 - ProbabilityMatrix[p[k]]);
    8282          }
    8383          for (int k = 1; k < i; k++) {
    84             sum2 = sum2 * (1 - ProbabilityMatrix[p[k]].Value);
     84            sum2 = sum2 * (1 - ProbabilityMatrix[p[k]]);
    8585          }
    8686          B[i, j] = sum2;
  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/EstimatedPTSP.cs

    r12219 r12228  
    5656      Operators.Add(new PTSPEstimatedInversionMovePathEvaluator());
    5757      Operators.Add(new PTSPEstimatedInsertionEvaluator());
     58      Operators.Add(new PTSPExhaustiveInversionLocalImprovement());
     59      Operators.Add(new PTSPExhaustiveInsertionLocalImprovement());
    5860      Encoding.ConfigureOperators(Operators.OfType<IOperator>());
    5961    }
     
    6870        realizations.Add(new ItemList<IntValue>());
    6971        for (int j = 0; j < data.Dimension; j++) {
    70           if (ProbabilityMatrix[j].Value > r.NextDouble()) {
     72          if (ProbabilityMatrix[j] > r.NextDouble()) {
    7173            realizations.ElementAt(i).Add(new IntValue(1));
    7274          } else {
     
    7678       
    7779      }
     80
    7881      foreach (var op in Operators.OfType<PTSPPathMoveEvaluator>()) {
     82        op.RealizationsParameter.Value = realizations;
     83      }
     84      foreach (var op in Operators.OfType<PTSPExhaustiveInversionLocalImprovement>()) {
    7985        op.RealizationsParameter.Value = realizations;
    8086      }
  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/HeuristicLab.Problems.PTSP-3.3.csproj

    r12219 r12228  
    2121    <ErrorReport>prompt</ErrorReport>
    2222    <WarningLevel>4</WarningLevel>
     23    <PlatformTarget>AnyCPU</PlatformTarget>
    2324  </PropertyGroup>
    2425  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' ">
     
    112113    <Compile Include="DistanceMatrix.cs" />
    113114    <Compile Include="EstimatedPTSP.cs" />
     115    <Compile Include="Improvers\PTSPExhaustiveInsertionLocalImprovement.cs" />
     116    <Compile Include="Improvers\PTSPExhaustiveInversionLocalImprovement.cs" />
    114117    <Compile Include="Interfaces\IPTSPPathMoveEvaluator.cs" />
    115118    <Compile Include="Interfaces\IPTSPMoveEvaluator.cs" />
     
    119122    <Compile Include="MoveEvaluators\TwoOpt\PTSPAnalyticalInversionMovePathEvaluator.cs" />
    120123    <Compile Include="MoveEvaluators\TwoOpt\PTSPEstimatedInversionMovePathEvaluator.cs" />
     124    <Compile Include="PathPTSPTour.cs" />
    121125    <Compile Include="PTSP.cs" />
    122126    <Compile Include="Plugin.cs" />
  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/MoveEvaluators/TwoOpt/PTSPAnalyticalInversionMovePathEvaluator.cs

    r12219 r12228  
    3535  public class PTSPAnalyticalInversionMovePathEvaluator : PTSPPathMoveEvaluator, IPermutationInversionMoveOperator {
    3636
    37     private static ItemList<DoubleValue> probabilities;
     37    private static DoubleArray probabilities;
    3838    private static DoubleMatrix A;
    3939    private static DoubleMatrix B;
     
    4646    }
    4747
    48     public IValueParameter<ItemList<DoubleValue>> ProbabilitiesParameter {
    49       get { return (IValueParameter<ItemList<DoubleValue>>)Parameters["Probabilities"]; }
     48    public IValueParameter<DoubleArray> ProbabilitiesParameter {
     49      get { return (IValueParameter<DoubleArray>)Parameters["Probabilities"]; }
    5050    }
    5151
     
    103103        case 1:
    104104          if (j == i + 1) {
    105             return (1/(1-probabilities[i+1].Value))*A[i,2]+(1 - probabilities[i].Value)*(A[i+1,1]-A[i+1,probabilities.Capacity-1]);
     105            return (1/(1-probabilities[i+1]))*A[i,2]+(1 - probabilities[i])*(A[i+1,1]-A[i+1,probabilities.Length-1]);
    106106          } else if (i == j) {
    107107            return A[i,1];
    108108          } else {
    109109            // Equation 25
    110             return ((1 - probabilities[i].Value) / (1 - probabilities[j].Value)) * RecursiveExpectedCost(1, i + 1, j - 1) + (1 - probabilities[i].Value) * (1);
     110            return ((1 - probabilities[i]) / (1 - probabilities[j])) * RecursiveExpectedCost(1, i + 1, j - 1) + (1 - probabilities[i]) * (1);
    111111          }
    112112         
    113113        case 2:
    114114          if (j == i + 1) {
    115             return (1 - probabilities[i + 1].Value) * (B[i, 1] - B[i, probabilities.Capacity - 1]) + (1 / (1 - probabilities[i].Value)) * (B[i + 1, 2]);
     115            return (1 - probabilities[i + 1]) * (B[i, 1] - B[i, probabilities.Length - 1]) + (1 / (1 - probabilities[i])) * (B[i + 1, 2]);
    116116          } else if (i == j) {
    117117            return B[i,1];
     
    123123        case 3:
    124124          if (j == i + 1) {
    125             return A[i, 2] + A[i + 1, 1] - A[i + 1, probabilities.Capacity - 1] + B[i, 1] - B[i, probabilities.Capacity - 1] + B[i + 1, 2];
     125            return A[i, 2] + A[i + 1, 1] - A[i + 1, probabilities.Length - 1] + B[i, 1] - B[i, probabilities.Length - 1] + B[i + 1, 2];
    126126          } else if (i == j) {
    127127            return A[i,1]+B[i,1];
  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/PTSP.cs

    r12219 r12228  
    4040  public abstract class ProbabilisticTravelingSalesmanProblem : SingleObjectiveBasicProblem<PermutationEncoding>, IStorableContent,
    4141  IProblemInstanceConsumer<TSPData> {
     42    private static readonly int DistanceMatrixSizeLimit = 1000;
     43
    4244    #region Parameter Properties
    4345    public OptionalValueParameter<DoubleMatrix> CoordinatesParameter {
     
    5355      get { return (OptionalValueParameter<Permutation>)Parameters["BestKnownSolution"]; }
    5456    }
    55     public OptionalValueParameter<ItemList<DoubleValue>> ProbabilityMatrixParameter {
    56       get { return (OptionalValueParameter<ItemList<DoubleValue>>)Parameters["ProbabilityMatrix"]; }
     57    public ValueParameter<DoubleArray> ProbabilityMatrixParameter {
     58      get { return (ValueParameter<DoubleArray>)Parameters["ProbabilityMatrix"]; }
    5759    }
    5860    public ValueParameter<IntValue> SampleSizeParameter {
     
    7981      set { BestKnownSolutionParameter.Value = value; }
    8082    }
    81     public ItemList<DoubleValue> ProbabilityMatrix {
     83    public DoubleArray ProbabilityMatrix {
    8284      get { return ProbabilityMatrixParameter.Value; }
    8385      set { ProbabilityMatrixParameter.Value = value; }
     
    105107      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)));
    106108      Parameters.Add(new OptionalValueParameter<Permutation>("BestKnownSolution", "The best known solution of this TSP instance."));
    107       Parameters.Add(new OptionalValueParameter<ItemList<DoubleValue>>("ProbabilityMatrix", "The matrix which contains the probabilities of each of the cities."));
     109      Parameters.Add(new ValueParameter<DoubleArray>("ProbabilityMatrix", "The matrix which contains the probabilities of each of the cities."));
     110
     111      Coordinates = new DoubleMatrix(new double[,] {
     112        { 100, 100 }, { 100, 200 }, { 100, 300 }, { 100, 400 },
     113        { 200, 100 }, { 200, 200 }, { 200, 300 }, { 200, 400 },
     114        { 300, 100 }, { 300, 200 }, { 300, 300 }, { 300, 400 },
     115        { 400, 100 }, { 400, 200 }, { 400, 300 }, { 400, 400 }
     116      });
     117
     118      ProbabilityMatrix = new DoubleArray(new double[] {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1});
    108119     
    109120    }
    110121
    111122    public virtual void Load(TSPData data) {
     123      if (data.Coordinates == null && data.Distances == null)
     124        throw new System.IO.InvalidDataException("The given instance specifies neither coordinates nor distances!");
     125      if (data.Dimension > DistanceMatrixSizeLimit && (data.DistanceMeasure == DistanceMeasure.Att
     126        || data.DistanceMeasure == DistanceMeasure.Manhattan
     127        || data.DistanceMeasure == DistanceMeasure.Maximum))
     128        throw new System.IO.InvalidDataException("The given instance uses an unsupported distance measure and is too large for using a distance matrix.");
     129      if (data.Coordinates != null && data.Coordinates.GetLength(1) != 2)
     130        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.");
     131
     132      Name = data.Name;
     133      Description = data.Description;
     134
     135      bool clearCoordinates = false, clearDistanceMatrix = false;
     136      if (data.Coordinates != null && data.Coordinates.GetLength(0) > 0)
     137        Coordinates = new DoubleMatrix(data.Coordinates);
     138      else clearCoordinates = true;
     139
     140      // reset them after assigning the evaluator
     141      if (clearCoordinates) Coordinates = null;
     142      if (clearDistanceMatrix) DistanceMatrix = null;
     143
    112144      DistanceMatrix = new DistanceMatrix(data.GetDistanceMatrix());
    113145      // Get Probabilities of cities using random with seed from hash function on the Name of the instance
    114       ProbabilityMatrix = new ItemList<DoubleValue>(data.Dimension);
     146      ProbabilityMatrix = new DoubleArray(data.Dimension);
    115147      Random r = new Random(data.Name.GetHashCode());
    116148      for (int i = 0; i < data.Dimension; i++) {
    117         ProbabilityMatrix.Add(new DoubleValue(r.NextDouble()));
     149        ProbabilityMatrix[i] = r.NextDouble();
    118150      }
    119151      Encoding.Length = data.Dimension;
     152
     153      OnReset();
    120154    }
    121155  }
  • branches/PTSP/PTSP.sln

    r12166 r12228  
    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}"
     7EndProject
     8Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Problems.PTSP.Views-3.3", "HeuristicLab.Problems.PTSP.Views\3.3\HeuristicLab.Problems.PTSP.Views-3.3.csproj", "{90B6CA12-9791-4430-B2D7-CD3ED7F75E2B}"
    79EndProject
    810Global
     
    1618    {97198965-AFEA-496B-B3B1-316905C43FD6}.Release|Any CPU.ActiveCfg = Release|Any CPU
    1719    {97198965-AFEA-496B-B3B1-316905C43FD6}.Release|Any CPU.Build.0 = Release|Any CPU
     20    {90B6CA12-9791-4430-B2D7-CD3ED7F75E2B}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
     21    {90B6CA12-9791-4430-B2D7-CD3ED7F75E2B}.Debug|Any CPU.Build.0 = Debug|Any CPU
     22    {90B6CA12-9791-4430-B2D7-CD3ED7F75E2B}.Release|Any CPU.ActiveCfg = Release|Any CPU
     23    {90B6CA12-9791-4430-B2D7-CD3ED7F75E2B}.Release|Any CPU.Build.0 = Release|Any CPU
    1824  EndGlobalSection
    1925  GlobalSection(SolutionProperties) = preSolution
Note: See TracChangeset for help on using the changeset viewer.