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(*).

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

• Intuition about TSP solutions is frequently wrong, and is hard to develop [but then, developing that intuition in me and others was my primary goal for writing Traveller in the first place].

• A better Elastic Net algorithm would be very nice. It needs some way to shuttle waypoints along the curve once an approximate solution is first achieved, to allow the net to explore ways to reduce its length. Right now, the first waypoint to reach a city "sufficiently closely" is locked to that city forever more, and waypoints ahead of or behind it on the path around the closed-loop net have no way to displace it, or to bypass it along the net to find better use elsewhere.
  I've even seen [other, less robust, made that way by me] versions of Elastic Net fail to put a waypoint near one or more cities at all, due to this blockage leaving fewer waypoints than cities in a part of the combined pattern, while a surplus of waypoints elsewhere go unemployed.
  Elastic Net, by starting with a radially symmetric set of cities, is easily seduced by problem layouts which are also radially symmetric, but whose solutions are not. A different seeder I've written starting with Elastic Net, that starts the waypoints randomly distributed near the cities and strung in order with a greedy seeder used on the waypoints instead of the cities, behaves quite differently in the approximate TSP solutions it produces, even though the same elastic net algorithm first draws the net inward toward an approximation of the original Elastic Net's starting circle half the radius of the playfield.

• A mix of initial population genome seeders is very useful, as each will have problem types for which it excels, and problems for which it does poorly. The fast way to the solved polyspiral started with another seeder, a greedy one, that got it nearly correct in one of about 230 tries, so that the problem was solved exactly with about five improvements.

• There is still no free lunch with regards to solving the TSP, though I'm busily cobbling code in my homeless situation to make that lunch as cheap as possible for the hobbiest!

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

• Windows Explorer, "copy window to clipboard".

  Please excuse Microsoft's typically buggy software in WinXP, which fails to capture the entire window frame when taking a snapshot of an individual window.

  [Actually, if you look closely, the missing right edges of the frames are there, pasted to the left edges of the frames. Bleah. It is utterly typical of Microsoft to release a software beta version as a commercial product.]

  I didn't have the patience to fix this Microsoft-ware bogosity by capturing the whole screen for each shot and cropping out the window images one by one. This document began life as a throw-away web page, but any effort done into the teeth of Microsoft's utter disdain for quality will always take longer than you can possibly anticipate, even taking this warning into account in advance.

  [The artifacts of the decorative red border inside the frame are mine. I haven't figured out yet how Java lets me make sure a panel repaints itself entirely during an expose event, so only the black canvas is being updated in a timely manner.]

• Windows Picture and Fax Viewer.

  Viewed full sized, several of these images show missing or broken lines in that viewer, which sent me into a panicked scurry gathering tools to "fix" them. The lines aren't broken, the Microsoft *.png viewing capability is. Viewed with competently written software (e.g., freeware The Gimp) the lines are seen to be intact.

• Internet Explorer release 6.0.

  When this web page is viewed in that browser with pictures turned off, with the alternate text wordwrapped in the web page source onto several lines between the opening and closing double quote for ease of maintenance, the box displaying the alternate text for the last picture crops that text long, complicated descriptive text in the vertical center of a line [counts as two bugs, one for not displaying the whole text, the other for cropping text in mid-glyph, something characterized as unsatisfactory at least as early as 1977 in SIGGRAPH publications and 1979 in ANSI X3H3 publications.]

  [Yes, I've heard of "longdesc" (or whatever) in HTML 4.01, that doesn't excuse this mess, since "longdesc" is still too poorly documented to use.]

  When the mouse button is hovered over that alternate text, a large popup bubble attempts to display the text.

  • The bubble flashes into and out of existence several times a second, in a way calculated to cause a grand mal seizure in epileptics.
  • There is no attempt to flow the text properly in the bubble; it is an ugly mess.

  When the mouse cursor is instead hovered over the default image icon, the text stops flashing many times a second, and instead shows up, displays steadily, but disappears after a second or two, far insufficient time to read the contents. The word wrapping is equally flawed in this case.

  [Joining the alternative text into one long, unmaintainable quoted string (of the kind made infamous in browser "see page source" windows) for each image fixed the word wrap formatting problems and the flashing bubbles, but not the early cutoff of the large alternative text, nor the briefness of the popup duration. This shouldn't have been necessary, HTML source text is supposed to be free format with regards to whitespace, newlines being interchangable with spaces, except inside a <pre> tag, and the flashing was unforgivable with any input format for the alternative text.]

  The browser does not respect the HTML 4.01 alphabetic entity spellings for left and right single and double quotes, so you get the ugly ones instead of the graceful ones, since I don't remember the hexadecimal versions, and from offline, can't look them up.

• Windows XP, release level unknown, but it was in a brand new computer as purchased 2002/08/06 or so.

  Time sharing performance between compute bound applications and finger speed interactive applications is deeply flawed, to the point that I had to convert Traveller to the Macintosh model of cooperative multitasking, with explicit wait() executions hundreds of times a second, to be able to type text in an editor window at all to compose this web page while Traveller ran.

  Replacing the Blue Screen of Death with a black one with popcorn visual surprises and static sound effects is no improvement. XP still crashes to the bare metal when assaulted by mere user software. Luckily, the extremely competently written (thanks, Bram) vim() editor keeps a keystroke-by-keystroke journal file, so all I lost was time, not typing. [Vim() is recommended to everyone sick of losing work to MS-Word when Windows crashes. You don't really need word processed text for 99.9% of text uses anyway, so using an overly complicated, fragile fritterware tool like MS-Word is a waste of your time. When you need pre-press production quality text layout, learn how to write open-standard HTML [It's easy, really, and the results can be shared by passing around one line URLs instead of multi-megabyte porkware documents that drag your corporate email system to its knees!] in a robust charity-ware text editor instead, and print your fancily formatted hardcopy from that.] At least the snotty "you forgot to shut down Windows properly" message is gone. The premier entity shutting down Windows improperly is still Windows, as ever. Maybe Bill Gates is learning humility?

  [Of course, having Windows instead whine to me about not instantly letting it submit bug reports from my thoroughly offline homeless person's computer is still mind-bogglingly stupid and insulting.]

  [That is exceeded, though, in sheer gall, by the initial computer startup message that if I, homeless, phoneless, connectionless, and too indigent for long distance toll charges, don't contact Microsoft online or by (pay-)phone next to my running computer where I can enter the indicated passwords, within a month to get a code to keep my operating system working, it will shut itself down on the presumption that I stole the software. Somehow this presumption that the purchaser is by default a thief failed to be mentioned in the product ads, service contract, or on the outside of the box. I can hardly wait to have it proved to me that only rich people are allowed to run WinXP for more than a month despite having bought and paid for it, for lack of a Redmond-approved set of life circumstances that allow timely contact with Microsoft. An intelligent alternative overlooked by Microsoft would have been to have the hardware vendor who first purchased and installed the OS software pursue this certification and install the password needed, as a normal part of doing business, not the end user customer to whom doing so might be effectively impossible, and who in any case has no obligation to be burdened with efforts to prove that the hardware vendor who installed it came by the software honestly, nor way of assuring in advance of purchase, or indeed at all, that this is so.]

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