A fast heuristic for genetic algorithms in link weight optimization

Genetic algorithms are a useful tool for link weight optimization in intra-domain traffic engineering where the maximum link load is to be minimized. As a local heuristic, the weight of the maximum loaded link is increased to speed up the search for a near-optimal solution. We show that implementing this heuristic as directed mutation outperforms an implementation as an inner loop in both quality of the result and number of calls to the objective function when used together with caching. Optimal mutation rates result in surprisingly high cache hit ratios.