search

heal-research / HeuristicLab

HeuristicLab - An environment for heuristic and evolutionary optimization
https://dev.heuristiclab.com
GNU General Public License v3.0
34 stars 16 forks source link

Implement the probabilistic traveling salesman problem #2221

Closed HeuristicLab-Trac-Bot closed 8 years ago

HeuristicLab-Trac-Bot commented 10 years ago

Issue migrated from trac ticket # 2221

milestone: HeuristicLab 3.3.14 | component: Problems.ProbabilisticTravelingSalesman | priority: medium | resolution: done

2014-07-24 12:34:06: @abeham created the issue

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^2^) 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. [[http://www.sciencedirect.com/science/article/pii/S0377221705005783|ScienceDirect]]

HeuristicLab-Trac-Bot commented 9 years ago

2015-03-09 15:12:17: apolidur changed status from new to accepted

HeuristicLab-Trac-Bot commented 9 years ago

2015-03-09 15:12:17: apolidur removed owner

HeuristicLab-Trac-Bot commented 9 years ago

2015-03-09 15:58:32: apolidur commented

r12166: Initial commit of the branch

HeuristicLab-Trac-Bot commented 9 years ago

2015-03-10 16:01:21: apolidur commented

r12183: Adding exact and sampling evaluation functions

HeuristicLab-Trac-Bot commented 9 years ago

2015-03-11 14:34:27: apolidur commented

r12191: Splitting PTSP into Analytical and Estimated

HeuristicLab-Trac-Bot commented 9 years ago

2015-03-18 12:01:40: apolidur commented

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

HeuristicLab-Trac-Bot commented 9 years ago

2015-03-19 17:17:19: apolidur commented

r12228: Local improvement operator for VNS

HeuristicLab-Trac-Bot commented 9 years ago

2015-03-26 16:15:14: apolidur commented

r12261: Fixing MoveEvaluators after running unit tests

HeuristicLab-Trac-Bot commented 9 years ago

2015-03-30 16:27:21: apolidur commented

r12269: Adding Tests and Views for PTSP

HeuristicLab-Trac-Bot commented 9 years ago

2015-03-31 16:58:32: apolidur commented

r12272: Adding 2.5-opt-EEs operators to PTSP

HeuristicLab-Trac-Bot commented 9 years ago

2015-04-13 17:44:58: apolidur commented

r12306: Prepared PTSP for instance input

HeuristicLab-Trac-Bot commented 9 years ago

2015-04-15 18:06:17: apolidur commented

r12317: Fixing PluginDependencies

HeuristicLab-Trac-Bot commented 9 years ago

2015-04-17 15:54:46: @Shabbafru commented

r12322 fixed project files of PTSP branch

HeuristicLab-Trac-Bot commented 9 years ago

2015-05-04 18:31:41: apolidur commented

r12380: Small refactoring and code cleaning

HeuristicLab-Trac-Bot commented 9 years ago

2015-05-09 17:26:43: apolidur commented

r12387: Fixing RealizationsSize parameter not updating

HeuristicLab-Trac-Bot commented 9 years ago

2015-07-22 13:50:31: apolidur commented

r12799: Adding path Analyzers and some other fixes

HeuristicLab-Trac-Bot commented 8 years ago

2015-11-17 09:28:13: @abeham changed status from accepted to assigned

HeuristicLab-Trac-Bot commented 8 years ago

2015-11-17 09:28:13: @abeham changed owner from apolidur to @abeham

HeuristicLab-Trac-Bot commented 8 years ago

2015-11-17 09:28:27: @abeham changed status from assigned to accepted

HeuristicLab-Trac-Bot commented 8 years ago

2015-11-17 09:29:05: @abeham commented

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

HeuristicLab-Trac-Bot commented 8 years ago

2015-11-26 09:32:24: @abeham changed milestone from HeuristicLab 3.3.x Backlog to HeuristicLab 3.3.14

HeuristicLab-Trac-Bot commented 8 years ago

2015-11-28 23:39:10: @abeham changed component from ### Undefined ### to Problems.ProbabilisticTravelingSalesman

HeuristicLab-Trac-Bot commented 8 years ago

2015-11-28 23:39:10: @abeham commented

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
HeuristicLab-Trac-Bot commented 8 years ago

2015-11-30 21:06:20: @abeham commented

r13423: minor changes

HeuristicLab-Trac-Bot commented 8 years ago

2015-11-30 21:14:45: @abeham changed status from accepted to reviewing

HeuristicLab-Trac-Bot commented 8 years ago

2015-11-30 21:14:45: @abeham changed owner from @abeham to @Shabbafru

HeuristicLab-Trac-Bot commented 8 years ago

2015-11-30 21:14:45: @abeham commented

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)
HeuristicLab-Trac-Bot commented 8 years ago

2015-12-02 11:21:40: @Shabbafru commented

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.
HeuristicLab-Trac-Bot commented 8 years ago

2015-12-02 11:22:24: @Shabbafru uploaded file AnalyticalPTSP.cs.patch (1.8 KiB)

Patch mentioned in review comments

HeuristicLab-Trac-Bot commented 8 years ago

2015-12-02 11:22:59: @Shabbafru changed status from reviewing to assigned

HeuristicLab-Trac-Bot commented 8 years ago

2015-12-02 11:22:59: @Shabbafru changed owner from @Shabbafru to @abeham

HeuristicLab-Trac-Bot commented 8 years ago

2015-12-15 09:27:35: @abeham changed status from assigned to accepted

HeuristicLab-Trac-Bot commented 8 years ago

2015-12-15 16:39:26: @abeham changed status from accepted to reviewing

HeuristicLab-Trac-Bot commented 8 years ago

2015-12-15 16:39:26: @abeham changed owner from @abeham to @Shabbafru

HeuristicLab-Trac-Bot commented 8 years ago

2015-12-15 16:39:26: @abeham commented

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.

HeuristicLab-Trac-Bot commented 8 years ago

2015-12-16 12:11:58: @Shabbafru changed status from reviewing to readytorelease

HeuristicLab-Trac-Bot commented 8 years ago

2015-12-16 12:11:58: @Shabbafru changed owner from @Shabbafru to @abeham

HeuristicLab-Trac-Bot commented 8 years ago

2015-12-16 12:11:58: @Shabbafru commented

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

HeuristicLab-Trac-Bot commented 8 years ago

2015-12-16 12:18:59: @Shabbafru commented

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?

HeuristicLab-Trac-Bot commented 8 years ago

2015-12-16 12:50:33: @mkommend commented

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.

HeuristicLab-Trac-Bot commented 8 years ago

2015-12-16 13:22:09: @Shabbafru commented

Replying to [comment:29 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!

HeuristicLab-Trac-Bot commented 8 years ago

2015-12-17 10:45:19: @abeham commented

r13476: reverted change r13472

HeuristicLab-Trac-Bot commented 8 years ago

2015-12-17 23:06:51: @abeham commented

r13484: integrated PTSP into trunk

HeuristicLab-Trac-Bot commented 8 years ago

2015-12-21 21:07:32: @abeham changed status from readytorelease to closed

HeuristicLab-Trac-Bot commented 8 years ago

2015-12-21 21:07:32: @abeham removed resolution

HeuristicLab-Trac-Bot commented 8 years ago

2015-12-21 21:07:32: @abeham commented

r13486: merged r13484 to stable