Download an executable jar file containing the Traveller release "epsilon" Java 1.4 source code, a makefile, the byte compiled classes, a copy of this document with accompanying screenshots, some licenses, and other documentation.

Traveller.jar

[I've completely given up trying to present Traveller here as an applet. Sorry about that. Applets don't work using standard mechanisms in my non-standard MS-Windows 98/Cygwin development environment, and I have no computer to test my web site over whose operation I have control. Writing software you cannot test properly is just a fast way to a bad reputation and a nervous breakdown. Those interested in running Traveller in their own Java runtime environment are still invited to download the jar file and enjoy themselves, where it starts out looking like this. [Screenshots for this document for the epsilon release of Traveller are from a "nested grid" layout, run a couple of times to show different features. The problem size is 337 cities, the population size is 40 members. This is Traveller's most difficult current layout pattern, much harder than random layouts because its fitness landscape is full of very deep local optima potholes, and so far I only know that it cannot be completely solved in 117,000+ seconds at the current state of Traveller's heuristics, though I ran out of patience with only two more fixes needed, easily determined by eye in this regular layout pattern.]


Traveller Splash Panel

One would think, as crucial as applet presentation is to the successful evangelizing of Java, that how to make Java applets run from browser windows would be as well documented and supported in Sun's documention as is the Java language API, but such is emphatically not the case. Grrrr.]

What is this Traveller applet?

Traveller is a Java language application which sets up and runs a choice of many genetic algorithm heuristics to solve a particular variety of the famous Traveling Salesman Problem, while letting the user have a lot of control over the algorithms used and the problem characteristics.

The spelling of the name "Traveller".

It is best to lay this controversial issue to rest at once. Scott Robert Ladd (henceforth "SRL" or "Scott") wrote the original of this demo as an applet for the ("Blind" version of the) Symmetrical Euclidean Traveling Salesman Problem, and he used an alternative spelling "Traveller", for which he has apparently received endless grief. He came back, on his spiffy Coyote Gulch web site (from which Traveller comes), to defend the spelling as an accepted alternative. Well, yes and no. You will find it in many dictionaries. It is an acceptable spelling under British rules (which earlier followed the current American rules), to double the "l", but the American rules double the consonant when adding a suffix, only when

Which latter is not the case for the word "travel". Nevertheless, it is Scott's original work, and Scott's choice, so until he changes his mind, the spelling stays as Scott and the British do it, and it is we Yanks who will have to show the stiff upper lip in these trying times. Besides, the spelling is now so embedded in the existing code class names and such, it would be a chore to rip it out at this point, and then the British would just declare war in retaliation for the insult to their orthography, and... .

What is the status of the Traveller source code?

Scott's original code was published under the GNU Public License, or GPL. My additions and modifications are freeware, since I'm not into legalisms. Under the Berne copyright convention, both Scott and I hold copyright on the code we separately wrote, automatically. [What the status is of the stuff mishmashed together I haven't a clue, best take the conservative approach and assume it is all GPLed.] My license of my copyright to you is that you may do whatever you want with my code, whether for commercial or private use, as long as you don't try to hold me responsible for the consequences. Credit to me as the author would be polite, but is not required. Scott's license to you is contained in the GPL; the most recent version of the GPL is available online from the Free Software Foundation, at

GNU Public License or by surface mail request from:
     Free Software Foundation, Inc.
     59 Temple Place - Suite 330
     Boston, MA 02111-1307, USA.

and also included in the files COPYING and COPYING.LIB (two considerably different licenses) in the Traveller.jar file.

For purposes of contacting me about my copyright (please don't), I am most recently living homeless at

     Kent Paul Dolan
     General Delivery
     Clovis, California, United States of America 93612-9999

but I am more usually known and reliably contacted since 1988 as xanthian@well.com or known as "xanthian", or since 1986 as "Kent, the man from xanth", but henceforth will be known here as "KPD".

Glossary

Traveller uses some unfamiliar words, and some familiar words in specialized ways. Here are the most important of them.

city
codon
node
vertex

The SETSP (see next section) involves travels through a set of Euclidean (x,y) coordinate pairs laid out on a two dimensional coordinate system. From the point of view of the human "traveling salesman" model, these are "cities". From the point of view of the graph which the cities and paths connecting them create, these are "nodes" or "vertices". From the point of view of a genetic algorithm, these smallest individual components of the genome are "codons". In particular, for Traveller, those codons contain a number which is the city's name.

chromosome
genome
tour

The aggregate of genetic information which a genetic algorithm manipulates in a single reproducing entity, and which its designer uses to describe the problem in term of its domain of discourse is precisely a "genome", or more colloquially a "chromosome". From the viewpoint of the human "traveling salesman" model, the Traveller genome encodes the salesman's "tour". This tour, and thus the genome, is independent of the description that starts with one particular one of its cities/nodes; it is like a ring, with no distinguished beginning or end, and this realization becomes important when implementing genetic algorithms.

edge
link
path

The connection by a straight line from one coordinate pair of a tour to the next is an "edge" from the point of view of the graph which the nodes define, occasionally a "link" or "path" from the point of view of the traveler and city model. What is important to Traveller and to the solution of the SETSP is the length of this link, and even more the sum of the lengths of all the links in the current tour, which sum is the genome's fitness.

What is the Symmetrical Euclidean Traveling Salesman Problem (SETSP), and why should I care?

Briefly but carefully expressed, the SETSP is this. In the two dimensional Cartesian coordinate system plane, with the usual Euclidean distance metric, and distances between coordinate pairs the same in both directions, given a set of coordinate pair locations, conceptually "cities", and an agent, conceptually "a traveler"; then, find for that traveler the closed circuit path that goes through each of those cities once and only once, and which has the shortest total length.

This problem is interesting for several reasons.

So just how hard is "very hard"?

I use 79 cities as my benchmark point, for sentimental reasons. I call it my "particle death of the universe"-sized problem (or my "the end of the matter"-sized problem).

My computer runs at a half-a-gigaHertz clock cycle, and, I think, does one floating-point operation per cycle. To evaluate the fitness of an SETSP tour ("genome") takes (at least) seven floating-point operations ("flops") per city.

My computer is made of matter, largely consisting of protons. All the protons in the universe are expected to have disintegrated in 10^100 years (That's a 1 with 100 zeros after it). The universe is currently about 15,000,000,000 years old, a submicroscopic beginning on such a time-span.

The brute force exhaustive search approach to solving the SETSP is to form every possible permutation of the cities (in no particular order of creating the permutations so that no fitness evaluation shortcuts are available), evaluate the path length ("fitness") for each permutation, and select the one with the shortest path length ("best fitness").

In attempting to solve a 79 city problem by the brute force exhaustive search approach, my computer, sadly, would fail, as it would see all its protons disintegrate first. Solving that problem at the speed of my computer would require just under 9*10^101 years, or just 90 times longer than it will take the last proton in the universe to disintegrate.

Maybe a bigger computer would help? [Excuse me if I drop a digit or two answering, the last time I read the needed numbers was a very long time ago.] Well, if all the matter in the entire universe, around 10^70 protons and neutrons, were turned into computers like my computer, it would be sufficient to make about 10^46 of them. If a 79 city SETSP problem instance were partitioned evenly among them and a massively parallel brute force solution attempted, granted not all the protons would have disintegrated after 10^56 years, but probably all interest in the problem solution would have disintegrated by then.

So, perhaps the brute force approach is not the best choice.

My best approach to solving the SETSP so far, finds the exact solution for a 79 city case, occasionally in as little as 40 minutes, though more often in a couple of hours, using a mix of genetic algorithms and good approximate solution initial seed genomes. [ UPDATE: as of 2002/03/25, Traveller solves 80 cities with a population of 80 members and "best practice" settings (on an even grid, so I know the right answer) in 61 seconds including setup time. Looks like I'm making progress.]

Paid professionals, using gangs of computers working in concert, and much more sophisticated algorithms, have exactly solved problems of around 15,000 cities in under a year, as their current "high water mark". Literally cities, in this case, they were working from a modern German map.

The problems of similar complexity to the SETSP, prevalent in integrated circuit design, feature millions of way-points, and are not exactly solvable in general in commercially useful times by any known algorithm. Simulated annealing is the heuristic algorithm of choice, last I read (and works well enough that we now have computers that sit on our laps and run half a gigaHertz).

What is the Blind Traveling Salesman Problem, and why did Scott choose it?

The traveling salesman (or here, the algorithm which represents that salesman) is blind when the only information available to the genetic algorithm part of the code for use about the path lengths is the total length of the circuit, not any of the city to city distances that make up that circuit.

This version of the problem is particularly suitable for genetic algorithm approaches, which insist on a single fitness metric. Also, it removes the complexity of various algorithms that attempt to improve performance by taking advantage of more local information.

Unlike the purity of Scott's version, mine makes available many "sighted cheats", to be turned on at the user's option. Providing good starting seed genomes, as with the minimal spanning tree seeds, is obviously one such cheat. All of my permutation algorithms are technically cheats because they save work by not calculating the full circuit fitness, but they could in concept just as easily compute and work with the full fitness, so their approach isn't as big a cheat. The "optimize near a point" group of heuristics are completely sighted cheats, they take advantage of knowing city locations to pick the cities nearest a point in the play-field to try to optimize some characteristic of the tour near just those few cities (they should be as awesome as they seem, too; they is certainly complicated enough compared to the lean beauty of Scott's Cyclic Crossover, say). Similarly, when implemented, local optimization seeds, probably from 2-OPT or 3-OPT (whatever those are) approaches, when I can steal some working code, or a greedy algorithm, when I feel like bothering to code one, or that spiffy relaxation of an ellipse to a solution I've seen several places on the Net, [done, see "Elastic Net" below] would all be sighted cheats providing good seeds.

So why does Traveller use a genetic algorithm instead of doing a direct solution?

Because no one in all that research time has ever found a polynomial time direct solution, and it is quite possible that no such direct solution even exists.

Where no direct solution algorithm exists, but the problem needs solving anyway, computer programmers and other researchers and practitioners employ heuristics, methods that seem to work well most of the time but cannot be proved to work all of the time, and sometimes don't. Every computer weather forecast you've ever seen was done with a heuristic, for example. No direct computational solution to the weather forecasting problem in feasible time is known to exist. The less understood the problem domain is, the chancier use of heuristics becomes, thus hurricanes arrive unexpectedly at your picnics.

However, the programming concept of genetic algorithms is that they help us find solutions, quickly anyway, for which no fast, direct solution is known, and where we don't very well understand the problem domain. Genetic algorithms are often used for problems whose solution is not well understood, and they often perform very well, in commercially successful ways. However, genetic algorithms themselves are not very well understood. Understanding them better is one of the goals of Traveller.

What a genetic algorithm does is to imitate that highly successful technique seen in nature, evolution by natural selection. Because computer algorithms' generations can run so much faster than the generation times of nature, this very inefficient process that takes millions of years in nature to create a higher brow line, finds solutions much more quickly in a computer. Typically genetic algorithms employ these parts.

The purposes of the SRL version of the applet Traveller.

Scott wrote Traveller as code to be part of a textbook. It is meant to be of a tutorial nature, efficient in the small with fast generation times, but not blindingly fast to find a solution, not industrial strength, not meant for huge problem sizes, and not the perfect algorithm (no one has found one, and if one existed, it would probably be too complicated for use in a textbook). Keep this in mind when trying to evaluate Scott's version of Traveller.

[After my hack, slash, and burn attacks changing his code, Traveller still doesn't have any of those features, they were in conflict with my goals too, but my version no longer would serve Scott's purposes at all, it is much too big and complicated for one thing,

[As of this moment of writing during construction of the Traveller "epsilon" source code release, the Unix "wc()" command claims that Traveller contains 97 source code files, of 33,039 lines of code or 897,299 source code bytes, while this current document in HTML source code form just passed a quarter megabyte in size.]

and by design is never "finished" for another, so any comparison of the two implementations needs to take into account their quite different goals.]

The purposes of the KPD version of the applet Traveller.

I do research programming in computational complexity as a hobby, and the SETSP is the natural choice of the hobbyist programmer. I also needed to learn Java — Sun's platform independent programming language, to have any chance of ever being employed again. Stealing Scott's working code (for which I'd lusted for a couple of years, there were so many things I wanted to change) gave me a chance to start with a functioning framework into which I could introduce new code of the type I understood, while learning more from types new to me as I modified them.

I love to mentor. This code is meant to allow others, just by playing with the applet controls, to gain an intuition and a deeper understanding of how Genetic Algorithms, and this SETSP genetic algorithm in particular, perform both when things are going well, and when problems occur. I wrote this code mostly to teach myself to have that deeper understanding, a gut level understanding of genetic algorithms.

I have no faith in single trick approaches to genetic algorithms. We use a genetic algorithm when we don't understand the problem domain well enough to code an efficient direct solution of the problem, and there is no more reason to suspect that we understand the problem domain well enough to select a single heuristic that will work for all data sets.

I do have "faith" in kitchen sink approaches to genetic algorithms, and want to test that faith by showing that genetic algorithms perform better when a mix of heuristics, metaheuristics, and seeding methods are used simultaneously. Thus there are as many algorithms as I could reasonably steal or create embedded in Traveller, with a control panel to turn them on or off as desired. This kitchen sink approach is not original with me, but goes back to early numerical algorithm research literature I read back in the 1960s, long since lost to me. [Other hobbyists, lusting to see their favorite SETSP heuristic running in Traveller's mix, are invited to enter negotiations to send me source code; don't just send it without asking, my email box is small.]

[I have experience of another kind with genetic algorithms, too, which can stand as an object lesson to other programmers. The genetic algorithm concept and resulting mechanism is so immensely powerful, that adding heuristics which are full of bugs and don't do at all what is expected, still can improve the performance of the mix. The genetic algorithm in nature, after all, runs quite adequately off the input of mutation and blind chance, so handing the computer genetic algorithm mechanism a source of genomes that differ in some new way or according to some new distribution of changes, is equally important with handing it a heuristic that is well designed and lovingly crafted. Thus, the rest of the story is that you cannot trust that your algorithm is working as you planned, just because the genetic mechanism can use its output to solve the given (SETSP or other class of) problems, and that such a seductive "testing technique" proves exactly that your heuristic doesn't break the genome badly enough to make it unusable, and nothing much else.]

I was originally coding this application in MITs StarLogo for Java, but that language ran out of steam for me. I am intentionally creating something very complex, and that language has hard-coded limitations on application complexity that started to warp my coding into an unmaintainable mess. It is great for other purposes, and I still use it, but not for an endlessly growing single application. Needing to get away from StarLogo, and not ready to try to write a C++ GUI with the limited tool libraries at my disposal, I decided to turn to Java with its rich abstract windowing interface class collection, and found Scott's applet waiting to be abused.

The Traveller application on the screen.

Traveller has become visually a plethora of framed windows [some that persist, and some pop-up windows that exist only as long as the corresponding parts of the code are running], into which I divided Traveller's screen interface, as my additions overwhelmed Scott's original one window design. The Traveller application now consists of the following main parts.