TSPTW with Genetic Algorithm

Question

I am implementing TSPTW(Travelling salesman with time window) with Genetic Algorithm with 81 cities, I applied the following steps:

mutation prob=0.03
population size=100
-Generate random population according to the value of population size intialized
-Sort the generated population
-Looping for populations and determine two parents by roulette selection, apply crossover on the parents, get child and add it to children list
-I am saving the best solution over the algorithm
-Sort the Children, replace worst tour in populations with best one of children
until no good children is existing is better than worst solution in populations
-loop (1 to population size)in all populations and Apply mutation of each worst solution with solution i , if the mutated solution is better than the worst solution of children. I insert it in populations in its place according to its fitness function and remove the worst one.

I can't find a good result, and I run it to specific high time, but I found sometimes it stuck with solution and can't get better result. I changed the

parameters(population size=20000 ,1000,100, mutation probability=0.03,0.02,..)

I've also tested it with cycle crossover, and ordered crossover

I would like to know, are my steps right ? How I can specify population size and mutation probability correctly?

Your mutation is wrong. Mutation can happen to any of the children, not just the worst (if my reading of your last step is correct). This is probably not the source of your problem though, hence not an answer. — NWS
I have already add better children in populations, so when the mutation is done on populations, it also include some better children — Yasmin
Looking at your steps again, i suspect you are getting confused as to how to crossover and generate a new population. Have you read : en.wikipedia.org/wiki/Genetic_algorithm and the articles en.wikipedia.org/wiki/Selection_%28genetic_algorithm%29 & en.wikipedia.org/wiki/Crossover_%28genetic_algorithm%29 ? — NWS

Andreas Andreas · Accepted Answer · 2013-05-30T11:27:04

Your algorithm is probably too elitistic. It only allows better solutions to enter your population. I assume at some point it will consist of all similar individuals. With no diversity left and your elitistic replacement only the low amount of mutation could introduce new genetic material.

I would recommend using elitism only in that you only let the best individual from the previous generation survive. The rest of the individuals should all be replaced by the new generation.

Or you could go with the offspring selection approach that we invented. For each child to survive it must be better than the better of its parents. Otherwise they're discarded and a new pair of parents is selected to produce a new child. You loop to produce new children until you have enough to fill a new population. Then you replace your population and start anew. The offspring selection genetic algorithm usually outperforms the genetic algorithm in terms of quality that it can achieve. It's implemented in HeuristicLab. You should be able to model the TSPTW if you open a VRPTW and allow only one vehicle.

Another option would be to go with a trajectory-based algorithm e.g. based on tabu search, such as the unified tabu search. The constraint relaxation is probably needed due to the time windowed solution and to get to different local optima.

TSPTW with Genetic Algorithm

1 Answers