Re: Travelling Salesman Problem

[darrell whitley <whitley@CS.ColoState.EDU>]

There are MUCH better systems than Evolver.
Both ICGA 1997 and PPSN 1998 had papers on systems
that solved upto 3000 cities to optimality.

Darrell Whitley 

|-----------------------------------------------------------------|  o__               
| Darrell Whitley            EMAIL:  whitley@cs.colostate.edu     |  .>/ _       
| Computer Science           PHONE: (970) 491-5373                |(*),\(*)    
| Colorado State University  FAX: (970) 491-2466                  |
| Fort Collins, CO 80523     http://www.cs.colostate.edu/~whitley | 99:3,850       
|-----------------------------------------------------------------| 98:3,506 
|     *** GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE  ***    | 97:3,355
|  ** GECCO-2000 **  Las Vegas, Nevada USA, July 8-12, 2000       | 96:3,215 
| Chair: Darrell Whitley; Submission deadline: January 26, 2000   | 95:3,030 
| WEB: www.genetic-programming.org  or  www.genetic-algorithm.org | 94:3,145 
|-----------------------------------------------------------------|   Miles

On Thu, 2 Dec 1999, David Bosomworth wrote:

> Hi there,
> 
> I'm conducting some research into using Genetic Algorithms in a problem
> identical to the Travelling salesman problem and came across this list
> with interest.
> 
> I've conducted some trials using a genetic algorithm software package
> called 'Evolver'. The trials were based around varying the number of
> destinations and measuring the performance of the software as the number
> of destinations (and hence obviously permutations) increases.
> 
> The number of destinations used were 25,50,75,100,133. We found that
> Evolver performed worse than human performance above 25 destinations. 
> 
> I was wondering if anyone had come across any similar research into the
> TSP and in particular I'm trying to determine: 
> 
> *	Is there a maximum threshold number of destinations that can be
> handled by genetic algorithms in the TSP example?
> 
> *	Are there any better (& more powerful) genetic algorithm
> software packages than 'Evolver' available?
> 
> Also rather surprisingly, plotting the total time taken to go round all
> the destinations against number of destinations gave a pretty straight
> line - (I would have expected a genetic algorithm to give a more random
> result). 
> 
> 
> Kind Regards
> 
> David Bosomworth
> 
> 
>