Re: GAs and TSP-Type Problems

"Kent Paul Dolan" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]
> "Costas Vlachos" <[EMAIL PROTECTED]> wrote:
>
> [see the original]
>
> You can much simplify/shrink your genome by doing it differently.
>
> 1) make your home base implicit, and modifiy your fitness function to
> include the distance from and to it for each salesperson's route
>
> 2) use an ordinary permutation genome to represent the rest of the
> cities; that way you can use the well-known permutation genome crossover
> and mutation operators on this part
>
> 3) add a separate, differently maintained piece to the genome, an array
> with an entry for each salesperson, telling how many cities that
> salesperson visits; populate it by zeroing the array, adding "1" for a
> city, city by city randomly to each array entry until you have exactly
> enough counts for your number of cities;  these counts are then used
> by the fitness function, counting off from the left end of part (2) to
> assign city routes to salespersons
>
> Your only novel design issue then is the mutation and crossover for part
> (3), which must maintain the contract that the total count remains
> constant: mutation is easy, just move one count from one array slot to
> another; crossover is harder, but what might for example work is doing
> an ordinary one point crossover, and then making up for the mismatch on
> the total number of cities by adding one or subtracting one at random to
> or from the child genome array entries in the direction needed until the
> total is correct, being careful not to let any entry go below zero.
>
> There are lots of example TSP/GA demos, mine is one such:
>
> http://www.well.com/user/xanthian/java/TravellerDoc.html
>
> For numbers of points of your problem's size it is fairly effective, but
> for large number of cities, waiting out a solution is tedious; my
> current 7776 node example has been running at 2GHZ for a population of
> 100 for 24 days, and while the best genome's tour is exceptionally
> good-looking, some of the others are still quite disorganized, perhaps
> because I've had mutation set too high; I recently cut it back to a
> nominal 1/10000 child genomes being mutated, from a prior 1/100.
>
> xanthian.
>
> On the bright side, if I don't manage to crash the run somehow, I'm
> already past 3/4ths of a trillion city to city distance calculations,
> and I'd love once in my life to say I did a trillion of something.



Thanks for the very useful ideas. Minimising chromosome redundancy will
probably help a lot. As it is at the moment (the way I described it in my
original message) only a small fraction of it contains useful info.

Had a look at your page, your Java program looks very impressive. Good luck
with your TSP/GA run!

cheers,
Costas