Traveller Cautionary Note: The pretty solution isn't always the correct one!

[Skip straight to the rant.]

One of the things that makes the Traveling Salesman Problem challenging is that it sometimes defies your intuition of what properties a solution should have. Here is a demonstration of a radially symmetric set of cities which has a solution tour which is anything but radially symmetric. To give away the game up front, the issue is that with an odd number of polyspiral arms, the tour cannot just follow adjacent arms out and back in as pairs to achieve a shortest length tour in a symmetric pattern.

Here, Traveller 1.21 with KPD mods, in an as yet unreleased developmental version after release epsilon, is working on solving a nine armed polyspiral with 81 total points in the tour, a very modest sized problem for Traveller, though it has a brute force solution time at 500 megaflops of 1.2858 * 10^105 years, one hundred thousand times longer than the universe is expected to take to have evaporated its last proton.

This is one of the city layouts I designed specifically to give Traveller ulcers, so I'd have to work harder myself to make the code much more capable in general, to solve even these hard cases without heuristics designed to cater to those cases specifically.

A popular approximate solver for the Symmetric Euclidian Traveling Salesman Problem, the simplest subspecies of the TSP, the one with which Traveller deals, is the Elastic Net. Here, Traveller's Elastic Net, adapted from code published by Alexander Budnik, is used as a seeder (one of several Traveller employs individually or in a mix), to produce excellent quality initial genomes to speed Traveller's search for an optimum solution.

Here we'll follow the action in a table of screenshots(*).

A small pink circle contains a circle of cyan dots, from which spiral arms of eight more cyan dots radiate out in a left tending pattern. Elastic Net uses a set of waypoints, three times as many in number as the cities in the problem setup, and some sophisticated mathematics to attract them in a tour-length conserving manner toward the city locations. To start, the waypoints are arranged in a small circle centered in the playfield. This isn't quite that circle, this is an already-growing version that was the earliest one I could capture in real time without putting a starting pause in the code.
A somewhat larger pink circle contains a circle of cyan dots, from which spiral arms of eight more cyan dots radiate out in a left tending pattern. The circle is beginning to flatten into a nonagon, barely detectably. A few tens of fast iterations later, the circle has grown, and is beginning to display the corners of a nonagon. Those corners will quickly become pseudopods.
A closed curve of pink dots connected by short green lines still smaller than the dot's diameters, shaped like a short armed sea starfish with nine arms, sits centered over a polyspiral, a pattern of cyan dots radiating in nine left tending rows from a circle of such dots at a common center.  The starfish pattern is about two thirds the diameter of the polyspiral pattern. Now the elastic net is starting to approximate grossly the pattern of the tour cities, though it hasn't "noticed" yet that the spiral arms twist to the left.
A closed curve of pink dots connected by short green lines a bit longer than than the dot's diameters, shaped like a long armed sea starfish with nine arms, sits centered over a polyspiral, a pattern of cyan dots radiating in nine left tending rows from a circle of such dots at a common center.  The starfish pattern reaches from the second to the eighth dot of each arm of the polyspiral pattern.  Each arm is slightly distorted rightward toward a nearby row of polyspiral dots Weighting factors in the algorithm for cities with no waypoints near them, at this point strongly draw the net toward the extreme points, which have become very attractive, both at the center and at the outside. The arms of the elastic net "flower" are starting to distort to follow the leftward twists of the polyspiral arms.
A pattern of pink dots connected by green lines takes a shape reminiscent of a Black Eyed Susan flower blossom, with each of nine petals distinct and separate from the ones to either side. It sits centered over a nine armed polyspiral of cyan dots radiating symmetrically in left tending spirals from a small circle of such dots near the center of the image.  The flower has begun to warp itself to match the polyspiral, with a bulge in each petal following closely the polyspiral row to its right. The arms of the elastic net fatten to try to approximate the cities in both adjacent arms of the polyspiral. At this point a weakness of Elastic Net becomes apparent; waypoints quarrel over ownership of cities sometimes.
A figure shaped like a nine bladed child's pinwheel, comprised of pink dots connected by green lines, is the foreground of the image.  It is now matched to the background of the image, a polyspiral of cyan dots radiating in left tending fashion from a small circle of dots at the center.  Each spiral row of the polyspiral has only nine cyan dots in total, and there are nine arms, making 81 dots in all.  There are three times that many pink dots in the pinwheel.  The curved sides of the pinwheel blades follow the spirals, then the straight sides return directly to the center, crossing a blue dot in the next spiral to the left. Here, less some succeeding tiny adjustments nearly invisible on the screen, is the elastic net's best approximate alignment of waypoints to cities in a "shortest" tour.
A pattern like a nine bladed windmill, with short arms holding the blades away from the center, so that no edge intersects another, is comprised of cyan dots connected by yellow lines. Here is the genome seed, symmetric, pretty, and seductive, which corresponds to the elastic net's approximation above, gotten by matching each city with its closest waypoint, and then putting the cities into a genome in the order of the corresponding matched waypoints around their elastic net.
A figure vaguely reminiscent of the Pueblo Indian god of mischief is seen, constructed by connecting the cyan dots of a nine row polyspiral with yellow lines.  The centermost circle of dots is connected in order as a circle except for a gap where what we will call the first and ninth spiral arms connect to it from their second dots outward.  The first and ninth spiral arms are then connected out to their ends, and then across to the end of the second and eighth spiral arms respectively.  Those latter two rows of dots are then connected in order in to their second dots outward.  This pattern repeats where the eighth row of dots connects at its second dot outward to the same dot of the seventh row of dots, thence to that rows outer end, across to the end of the sixth row of dots, inward to its second dot outward, and across to the second dot outward of the fifth row of dots.  There the pattern symmetry breaks down badly.  Meanwhile, at the second row of dots, second dot out, the path connects across to the second dot out of the third row of dots, and thence to that row's outer end, where again the symmetry fails.  Meanwhile, the fifth spiral's second dot outward connects to the fourth spiral's second dot outward, then out to the fourth spiral's fifth dot outward.  The path then returns to the fifth spiral, third dot outward, and out to the fifth spiral's end.  Meanwhile, from the end of the third spiral, the path goes to the sixth dot outward of the fourth spiral, out to the end of the fourth spiral.  Finally, the ends of the fourth and fifth spiral are connected, closing the path. And here, the point of this essay, is the completely different, and unsymmetric, final optimal tour for this polyspiral city layout.

[Traveller solved this, in this instance, in 821 seconds, on a two gigahertz large-memory laptop. Solution times are of course very dependent on the mix of Traveller seeders, metaheuristics, heuristics, and control values selected by the user, besides the capacities of the underlying hardware.]


If there are lessons to be learned from this, these will do:

[With some luck, my computer won't be stolen with the only current copy of my software efforts, again, or me be thrown in jail for being homeless, again, before I can finish reconstructing the lost parts of the next Traveller release, clean up the documentation, and get it all up on the Web. I comfort myself that even Galileo had problems getting his research published, and I'm certainly not a genius like Galileo, otherwise I'd try for a MacArthur grant, except I'm about twice too old, also.]

Cheers,
    xanthian

2002/09/02 23:17

[Oh, and in my never ending quest to be more politically correct than thou, try viewing this page with images turned off. Creating what you see that way was a lot of extra work and I'd like the effort to be appreciated [and imitated among you web developers] by the 99.9 percent of the population to whom it is usually invisible and not considered.]

(*) Microsoft commercial software product bugs, encountered just while developing this one simple web page, that wasted my precious time by bucketfulls.

Grrrr.

"No guarantee of fitness for merchantability?" You said a mouthfull, Bill Gates, except for "guarantee" read "semblance".

Foolhardily of me, perhaps, to post this, but being so poor there is nothing of value for which I can be sued by Microsoft's pantheon of truth-suppressing lawyers, I figure that publicizing repeatedly, truthfully, and reproducably the problems Microsoft's uniformly horrible software quality causes me as a customer or user [and has, without a single exception, in the many, many products in their line, operating systems, compilers, management tools, word processing tools, databases, spreadsheets, server software, browsers, and data presentation tools, among others, which various employment has compelled me to use since 1983] will be a practice imitated by others, and in the mass will eventually warn the computer naïve [most of software purchasing management, for example, the human equivalent of lemmings: "If everyone else ran off a cliff, would you run off it too, knowing 'there is safety in numbers'?" "No?" "If everyone else bought horrible quality software from a monopolist, would you buy it too, knowing 'there is safety in numbers'?" "Yes?" "Can you explain the difference, since your ability to be productive lies smashed to the bottom in either case?"] to seek operating systems and other software tools from more reliable, reputable, ethical commercial or freeware community sources.

[Ah, a perfect example of world-famous "Kentish grammar" to wrap up this rant.]

[Back to the brag.]

Interested in hiring Unix software development talent, and willing to endure someone not afraid to tell you when you're about to run off a cliff, and with the experience to back it up?