Genetic local search algorithm for network coding resources minimization
Zhjian Qu, Xiaohong Liu, Jingjing Huang, Xiao Tan · 2012
We propose an efficient solution to minimize the network coding resources which refers to the coded links with throughput constraints. For this proved NP-hard problem, genetic algorithm has showed great superiority for better solving it. However, due to its own high constraints of throughput, there exist too many infeasible solutions over the entire search space while using the binary encoding for genetic algorithm, which provides more difficulties to search the optimal solution. To tackle this problem more efficiently, we construct a completely different solution space which is based on the end-to-end routings from the source to all the destinations. This newly constructed search space just contains those solutions subjected to the required rate constraints and generally has a smaller size compared with binary encoding representation. In order to speed up the search process, an excellent local search procedure has also been designed for each feasible solution. Simulation results over four topologies show significant improvements in terms of the ability to get the optimal solution and the algorithmic convergence speed.