Workaround for extended Traveling Salesman Problem

classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
Report Content as Inappropriate

Workaround for extended Traveling Salesman Problem

Владимир Большуткин

I'm working on solving Extending Traveling Salesman Problem with Genetic Algorithms using JGAP. 'Extension' just requires me to add few more genes to chromosomes. 

But as far as I understood, default implementations of permutational crossovers (such as GreedyCrossover) assume that chromosome contains only these ordered genes (maybe with some offset but I'm not sure). I've already implemented a workaround suitable for me.

Now I'm writing to you to ask, is there a reason of exactly this architecture for TSP. Or maybe, my workaround may be accepted as a contribution, i.e. patch (if it is correct)?

Why I think, current solution is not satisfiable:
-we have no full control on our genes (it is difficult to add new genes)
-integer genes that are part of permutation cannot mutate (but must be able to mutate according to theory behind GA [all genes must be independent])

-Create own gene (I called it OrderAwareGene) that deals with permutations. Currently it is based on CompositeGene.
-Create special GreedyCrossover implementation to work exactly with genes of such type.

Now I can create a chromosome with 1 OrderAwareGene and few other genes.

Could you estimate this workaround? Is this contribution interesting for you?

Best regards,

P.S. I tried to write to development mailing list but with no success.

Learn Windows Azure Live!  Tuesday, Dec 13, 2011
Microsoft is holding a special Learn Windows Azure training event for
developers. It will provide a great way to learn Windows Azure and what it
provides. You can attend the event by watching it streamed LIVE online.  
Learn more at http://p.sf.net/sfu/ms-windowsazure
jgap-users mailing list
[hidden email]