A ripple-spreading genetic algorithm for the network coding problem
Hu, Xiao-Bing, Leeson, Mark S. and Hines, Evor (2010) A ripple-spreading genetic algorithm for the network coding problem. In: 2010 IEEE World Congress on Computational Intelligence, Barcelona, Spain, 18-23 Jul 2010. Published in: IEEE Congress on Evolutionary Computation pp. 1-8.Full text not available from this repository.
Official URL: http://dx.doi.org/10.1109/CEC.2010.5586023
The network coding problem (NCP) is an NP-hard combinatorial problem, and genetic algorithms (GAs) have recently been applied to address this problem. This paper reports a novel ripple-spreading GA (RSGA) for the NCP. In contrast to existing GAs where a chromosome directly represents a solution, the proposed RSGA separates chromosomes and solutions by introducing a purpose-designed pre-problem for the NCP. In the pre-problem, the nodes in the NCP are projected into an artificial space, in which some ripple epicenters are randomly generated. Then a specially parameterized ripple-spreading process is employed such that as ripples (starting from the epicenters) spread out in the artificial space, the incoming signals and outgoing signals of all nodes will be individually determined, according to the amplitudes of the ripples which have reached the node. Changing the values of the ripple-spreading parameters will result in different information flows in the networks. Therefore, a simple binary-string based GA, unlike existing GAs which employ permutation representations for the NCP, can be used to optimize the values of the ripple-spreading parameters, in order to find a good solution to the NCP. A potential advantage of the RSGA is its scalability in complex networks, where permutation representation based GAs may face serious memory-efficiency problems. The effectiveness of the proposed RSGA is illustrated in the context of some experiments.
|Item Type:||Conference Item (Paper)|
|Divisions:||Faculty of Science > Engineering|
|Journal or Publication Title:||IEEE Congress on Evolutionary Computation|
|Book Title:||IEEE Congress on Evolutionary Computation|
|Page Range:||pp. 1-8|
|Access rights to Published version:||Restricted or Subscription Access|
|Conference Paper Type:||Paper|
|Title of Event:||2010 IEEE World Congress on Computational Intelligence|
|Type of Event:||Other|
|Location of Event:||Barcelona, Spain|
|Date(s) of Event:||18-23 Jul 2010|
Actions (login required)