|
Re^2: Travelling problem (Anyone better 86850?)
by roboticus (Chancellor) 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.
| [reply]
[d/l] |
|
|
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.
| [reply] |
Re^2: Travelling problem (Anyone better 86850?)
by tangent (Parson) 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.
| [reply] |
|
|
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.
| [reply]
[d/l] |
|
|
By widening the net, and a bit more shuffling I get:
84860
85075
85294
85469
85489
85509
85684
85923
| [reply]
[d/l] |
|
|
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?
| [reply] |
|
|
|
|
| [reply] |
|
|
> 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.
| [reply] |
|
|
| [reply] |
|
|
|
|
|
|
|
|
|
|
|
|
|
| [reply] |
|
|
|
|
|
Re^2: Travelling problem (Anyone better 82991?)
by BrowserUk (Patriarch) on Dec 22, 2013 at 18:17 UTC
|
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
| [reply]
[d/l] |
|
|
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.
| [reply] |
|
|
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.
| [reply] |
|
|
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
| [reply]
[d/l] |
|
|
No, your lists only contain 23 items
| [reply] |
|
|