Implement the probabilistic traveling salesman problem

[abeham]

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

• Representation: path encoding (Permutation)
• Fitness function: O(n²) 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

[apolidur]

r12166: Initial commit of the branch

[apolidur]

r12183: Adding exact and sampling evaluation functions

[apolidur]

r12191: Splitting PTSP into Analytical and Estimated

[apolidur]

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

[apolidur]

r12228: Local improvement operator for VNS

[apolidur]

r12261: Fixing MoveEvaluators after running unit tests

[apolidur]

r12269: Adding Tests and Views for PTSP

[apolidur]

r12272: Adding 2.5-opt-EEs operators to PTSP

[apolidur]

r12306: Prepared PTSP for instance input

[apolidur]

r12317: Fixing PluginDependencies

[ascheibe]

r12322 fixed project files of PTSP branch

[apolidur]

r12380: Small refactoring and code cleaning

[apolidur]

r12387: Fixing RealizationsSize parameter not updating

[apolidur]

r12799: Adding path Analyzers and some other fixes

[abeham]

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

[abeham]

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

[abeham]

r13423: minor changes

[abeham]

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)

[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.

[ascheibe]

Patch mentioned in review comments

[abeham]

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.

[ascheibe]

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

[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?

[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.

[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!

[abeham]

r13476: reverted change r13472

[abeham]

r13484: integrated PTSP into trunk

[abeham]

r13486: merged r13484 to stable