Genetic local search for multicast routing

We describe a population-based search algorithm for cost minimization of multicast routing. The algorithm utilizes the partially mixed crossover operation (PMX) and a landscape analysis in a pre-processing step. The aim of the landscape analysis is to estimate the depth Γ of the deepest local minima in the landscape generated by the routing tasks and the objective function. The analysis employs simulated annealing with a logarithmic cooling schedule (LSA). The local search performs alternating sequences of descending and ascending steps for each individual of the population, where the length of a sequence with uniform direction is controlled by the estimated value of Γ. We present results from computational experiments on a synthetic routing tasks, and we provide experimental evidence that our genetic local search procedure, that combines LSA and PMX, performs better than algorithms using either LSA or PMX only.