Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight
 
PerlMonks  

Re: Travelling problem (Anyone better 86850?)

by BrowserUk (Pope)
on Dec 22, 2013 at 02:56 UTC ( #1068082=note: print w/ replies, xml ) Need Help??


in reply to Travelling problem

Given the sample dataset supplied in Re^4: Travelling problem, anyone got a better (lower) total distance than 86850?


With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.


Comment on Re: Travelling problem (Anyone better 86850?)
Re^2: Travelling problem (Anyone better 82991?)
by BrowserUk (Pope) on Dec 22, 2013 at 18:17 UTC

    There are better solutions than 84860:

    83907: 0 1 10 15 6 11 7 2 18 19 17 14 4 21 9 13 22 8 3 12 5 20 16 83666: 0 1 10 15 6 11 7 2 18 19 17 14 21 9 4 13 22 8 3 12 5 20 16 83633: 0 1 10 15 6 11 7 2 18 19 17 14 21 4 9 13 22 8 3 12 5 20 16 82991: 0 1 10 15 6 11 7 2 18 19 17 4 14 21 9 13 22 8 3 12 5 20 16

      Wow, I'm impressed about your ability to find that fast a very good solution. I don't know the perfect value. But 84860km seems to be a very short distance for the 24 places.

      Of course I want to try to write my own code. But it would be interesting for me which algorithm you used. Until now I did not have success with the Graph module. See Re^3: Travelling problem

      Now I'll try the minimal hamilton path.

        I'm using a genetic algorithm (based loosely on Re^15: Divide array of integers into most similar value halves (Updated)), it gets close very quickly, but has no guarantee to ever find the best. Nor any guarantees about the quality of what it does find. (Nor even any criteria by which to judge that.)

        It took less than a minute to find 86850, but much, much longer to refine that to 84860.

        I threw the implementation I've been using together late last night and it is pretty crude and messy. Once I've cleaned it up I'll post it.


        With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
        Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
        "Science is about questioning the status quo. Questioning authority".
        In the absence of evidence, opinion is indistinguishable from prejudice.

      Ignore this!. Programmer error! There are better solutions than 84860:

      83907: 0 1 10 15 6 11 7 2 18 19 17 14 4 21 9 13 22 8 3 12 5 20 16 83666: 0 1 10 15 6 11 7 2 18 19 17 14 21 9 4 13 22 8 3 12 5 20 16 83633: 0 1 10 15 6 11 7 2 18 19 17 14 21 4 9 13 22 8 3 12 5 20 16 82991: 0 1 10 15 6 11 7 2 18 19 17 4 14 21 9 13 22 8 3 12 5 20 16
        No, your lists only contain 23 items
Re^2: Travelling problem (Anyone better 86850?)
by tangent (Curate) on Dec 23, 2013 at 15:30 UTC
    Best I could get is also 86850. Used a simple genetic algorithm - mutate using crossover points, exchange, reverse, and a bit of shuffling. Then cull all the losers and repeat. Quite ruthless really. First time I have tried this approach, seems very powerful.

    Update: Sorry BrowserUK, I updated it within about 20 seconds of posting, you are indeed quick off the mark.

      Best I could get is also 8650.

      I think you dropped a digit? (The absolute minimum is 74,283 and that's impossible :)


    With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.
      Quite ruthless really. First time I have tried this approach, seems very powerful.

      You mustn't be too ruthless though. You have to allow some of the less good candidates to evolve otherwise the algorithm will lock into a local minima and never explore further.

      For example, there are at least 8 better solutions than the 86850:

      84860 85075 85294 85469 85509 85684 85982 86197

      But these will never be discovered by minor evolution from the 86850 solution.

      You have to allow some radical variations (with significantly less good scores) to evolve for a while to discover these better ones.


      With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice.
        That makes sense. I found I had to keep adding variations to avoid dead ends, the shuffles in particular helped. How would you choose those 'radical variations'? At random from the laggards, or according to some other criteria, some way of spotting potential?
        By widening the net, and a bit more shuffling I get:
        84860 85075 85294 85469 85489 85509 85684 85923
      > First time I have tried this approach, seems very powerful.

      Well not sure if this problem isn't too easy for a good test, considering that the naive approach already gives a solution of 95166, which is probably good enough in most cases.

      I have the impression that a little branch and bound with just the 3 or 4 shortest edges per node (instead of just one) would quickly produce much better results.

      Cheers Rolf

      ( addicted to the Perl Programming Language)

      ) at least for the OP.

        I have the impression that a little branch and bound with just the 3 or 4 shortest edges per node (instead of just one) would quickly produce much better results.

        Prove it! (You've done a great job of quoting wikipedia; how about putting some of your reading into practice?)


        With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
        Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
        "Science is about questioning the status quo. Questioning authority".
        In the absence of evidence, opinion is indistinguishable from prejudice.

        My branch and bound is running on the three shortest nodes for 27hrs now. Best so far 88491.

Re^2: Travelling problem (Anyone better 86850?)
by roboticus (Canon) on Dec 23, 2013 at 18:11 UTC

    BrowserUk:

    Prompted by LanX's suggestion to use a genetic algorithm, I put one together (code in the readmore section below).

    So far, both times I ran it, it found a path totalling 84860. I just started a longer run (100,000 generations with a larger population (300) to see if anything interesting pops up.

    Update: Oops! Replied to the wrong node. Also, should've refreshed the page. When I started coding, there weren't so many replies!

    Update 2: I let the other run go for about 80K generations, but it never found anything better.

    ...roboticus

    When your only tool is a hammer, all problems look like your thumb.

      Similar methodology to mine, and the same problem.

      Many times it will find the minima well within your 1000 generations; but on those occasions where it settles into a false minima; it doesn't (seem to; limited runs) matter how many more generations you run it for; it will never find it.

      That's what I've been trying to find a solution to for the last couple of days. So far, without much success.

      The problem appears to be that if you discard too vigorously, you settle into re-trying variations of the same paths over and over without ever introducing any "new blood".


      With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1068082]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others avoiding work at the Monastery: (13)
As of 2014-12-18 20:19 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?





    Results (61 votes), past polls