Opened 3 years ago

Closed 17 months ago

#2221 closed feature request (done)

Implement the probabilistic traveling salesman problem

Reported by: abeham Owned by: abeham
Priority: medium Milestone: HeuristicLab 3.3.14
Component: Problems.ProbabilisticTravelingSalesman Version: 3.3.10
Keywords: Cc:

Description

The heterogeneous PTSP would be preferred where each city can have a different probability. A few notes:

  • Representation: path encoding (Permutation)
  • Fitness function: O(n2) weighted probability of each edge
  • Moves: 2-p-opt (Inversion) and 1-shift (Insertion) with efficient fitness difference calculation (Bianchi and Campbell 2007) + local improvement operator for these moves
  • Analyzer could probably be reused from tsp (PathTspTour)

Bianchi, L., Campbell, A.M., 2007. Extension of the 2-p-opt and 1-shift algorithms to the heterogeneous probabilistic traveling salesman problem. European Journal of Operational Research 176, pp. 131-144. ScienceDirect

Attachments (1)

AnalyticalPTSP.cs.patch (1.8 KB) - added by ascheibe 17 months ago.
Patch mentioned in review comments

Download all attachments as: .zip

Change History (34)

comment:1 Changed 2 years ago by apolidur

  • Owner set to apolidur
  • Status changed from new to accepted

comment:2 Changed 2 years ago by apolidur

r12166: Initial commit of the branch

comment:3 Changed 2 years ago by apolidur

r12183: Adding exact and sampling evaluation functions

comment:4 Changed 2 years ago by apolidur

r12191: Splitting PTSP into Analytical and Estimated

comment:5 Changed 2 years ago by apolidur

r12219: First version of 1-shift and 2-p-opt moves

comment:6 Changed 2 years ago by apolidur

r12228: Local improvement operator for VNS

comment:7 Changed 2 years ago by apolidur

r12261: Fixing MoveEvaluators after running unit tests

comment:8 Changed 2 years ago by apolidur

r12269: Adding Tests and Views for PTSP

comment:9 Changed 2 years ago by apolidur

r12272: Adding 2.5-opt-EEs operators to PTSP

comment:10 Changed 2 years ago by apolidur

r12306: Prepared PTSP for instance input

comment:11 Changed 2 years ago by apolidur

r12317: Fixing PluginDependencies

comment:12 Changed 2 years ago by ascheibe

r12322 fixed project files of PTSP branch

comment:13 Changed 2 years ago by apolidur

r12380: Small refactoring and code cleaning

comment:14 Changed 2 years ago by apolidur

r12387: Fixing RealizationsSize parameter not updating

comment:15 Changed 22 months ago by apolidur

r12799: Adding path Analyzers and some other fixes

comment:16 Changed 18 months ago by abeham

  • Owner changed from apolidur to abeham
  • Status changed from accepted to assigned

comment:17 Changed 18 months ago by abeham

  • Status changed from assigned to accepted

comment:18 Changed 18 months ago by abeham

r13202: reverse engineered PTSPData and added simple instance provider based on TSPLIB

comment:19 Changed 17 months ago by abeham

  • Milestone changed from HeuristicLab 3.3.x Backlog to HeuristicLab 3.3.14

comment:20 Changed 17 months ago by abeham

  • Component changed from ### Undefined ### to Problems.ProbabilisticTravelingSalesman

r13412:

  • 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

comment:21 Changed 17 months ago by abeham

r13423: minor changes

comment:22 Changed 17 months ago by abeham

  • Owner changed from abeham to ascheibe
  • Status changed from accepted to reviewing

Please test and review the branch. A few notes:

  • There are two problems, one that estimates the true expected tour length and the other that calculates the expected tour length exactly
  • Moves only exist for the estimated PTSP, the analytical PTSP can only be solved by algorithms that make use of crossover and/or mutation
  • I replaced the TSP's use of different evaluators to handle different distance measures with a distance calculator class and thus require only one evaluator class (we should probably do that in the standard TSP as well)
  • Problem instances are adaptations of the TSPLIB instances (but reproducible so that always the same instances are generated)
  • There exist homogeneous instances (all probabilities are the same) and heterogeneous ones (randomly chosen probabilities)

comment:23 Changed 17 months ago by ascheibe

Review Comments

  • MarsagliaRandom
    • License header is missing
    • Wouldn't it be better to use a random number generator from HeuristicLab.Random? The comment says that this generator is here because the one from .NET might change which would result in different instances. But we have the ones from HL.Random for the same reason, so I think we could use them?
    • I have no idea if this random number generator is correct and on what this is based on. Maybe a reference in the comment would help for the case that you don't want to switch to HL.Random.
  • In TSPLIBHomogeneousPTSPInstanceProvider, the probabilities vector is missing 0.3 and 0.7. Is there a reason for this?
  • TSPLIBHeterogeneousPTSPInstanceProvider and TSPLIBHomogeneousPTSPInstanceProvider are very similar. Method LoadData is the same, LoadInstance is the same except the last few lines. I thought about merging these two because the homogeneous and heterogeneous instances can be generated easily by one provider, but it would probably be a little bit of a problem with the descriptors and the data that gets stored in them (probability vs. seed). But maybe you could add a base class to reduce code duplication?
  • Problems.PTSP and Problems.PTSP.Views misses the Linux PreBuildEvent
  • Problems.PTSP and Problems.PTSP.Views are missing x86 and x64 platforms
  • The unit test "AnalyticalTest" can be removed as it does not contain an assert statement
  • The AssemblyFileVersion is not correct in AssemblyInfo.cs.frame in Problems.PTSP and Problems.PTSP.Views
  • PTSP: I think the parameter DistanceCalculator could be hidden because this shouldn't be changed by the user as it is just set when loading the problem data.
  • Analytical PTSP:
    • Because executing the analytical PTSP takes a long time, I did a little profiling. It seems that the excessive access of the probabilites parameter takes most of the runtime of the algorithm. I used a GA, std. settings except generations limited to 2 generations and a280 problem instance. This takes with parallel engine around 68 seconds on my hardware. With the enclosed patch it takes around 12 seconds.
    • There is a static Evaluate and normal, overriden Evalute method. They seem to just differ in how variables are defined (e.g. int vs. var) and how long the loops go (e.g. tour.Length vs. tour.Length - 1). Should this maybe be the pattern where we have the overriden Evaluate just calling the static Evaluate?
    • When I create a new GA, select Analytical PTSP, and click Run I can an exception because the DistanceMatrix is not set which is needed in the evaluation function. When I switch to another instance everything works fine.

Changed 17 months ago by ascheibe

Patch mentioned in review comments

comment:24 Changed 17 months ago by ascheibe

  • Owner changed from ascheibe to abeham
  • Status changed from reviewing to assigned

comment:25 Changed 17 months ago by abeham

  • Status changed from assigned to accepted

comment:26 Changed 17 months ago by abeham

  • Owner changed from abeham to ascheibe
  • Status changed from accepted to reviewing

r13470:

  • implemented review comments
    • hid rng as private class, implemented djb2 hash function (hash function implementation may also change)
    • added missing probabilities
    • base class for instance providers
    • prebuild event events
    • build platforms
    • unit test will be removed on trunk integration
    • corrected assembly file version
    • distance calculator parameter was not hidden, can be changed by user, updates distance matrix
    • fixed performance problems (ouch!) also for estimated ptsp (inlined GetDistance method)
  • added moves (full evaluation) for analytical tsp
  • added local improvement operators for analytical ptsp
  • added recalculation of distance matrix when parameters change
  • still lots of other changes

Please review again, there are still some substantial changes.

comment:27 Changed 17 months ago by ascheibe

  • Owner changed from ascheibe to abeham
  • Status changed from reviewing to readytorelease

Reviewed and tested r13470. I just fixed a reference in the instances project in r13472; other than that I have no other comments.

comment:28 Changed 17 months ago by ascheibe

I just saw that the reference that I removed in r13472 is also in the trunk project and seems to not upset the unit test. I'm not sure why this is the case or am I overlooking something?

comment:29 follow-up: Changed 17 months ago by mkommend

References in general never upset the unit tests, because if an assembly / project is referenced but not needed it is not linked to the generated library. As the unit test only analyzes compiled assemblies, it does not see referenced but unused libraries, and hence does not fails.

comment:30 in reply to: ↑ 29 Changed 17 months ago by ascheibe

Replying to mkommend:

References in general never upset the unit tests, because if an assembly / project is referenced but not needed it is not linked to the generated library. As the unit test only analyzes compiled assemblies, it does not see referenced but unused libraries, and hence does not fails.

Ah, ok, thanks!

comment:31 Changed 17 months ago by abeham

r13476: reverted change r13472

comment:32 Changed 17 months ago by abeham

r13484: integrated PTSP into trunk

comment:33 Changed 17 months ago by abeham

  • Resolution set to done
  • Status changed from readytorelease to closed

r13486: merged r13484 to stable

Note: See TracTickets for help on using tickets.