Re: GAs and TSP-Type Problems

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


-- 
Posted via Mailgate.ORG Server - http://www.Mailgate.ORG