Nonlinear Network Optimization—An Embedding Vector Space Approach

Abstract

This paper proposes a normed-space vector representation of networks which allows defining evolutionary operators for network optimization that resemble continuous-space operators. These operators are employed here to build a genetic algorithm which becomes generic for the optimization of tree networks, without the requirement of any special encoding scheme. Such a genetic algorithm has been compared with several encoding-based genetic algorithms, on 25 and 50-node instances of the optimal communication spanning tree and of the quadratic minimum spanning tree, and has been shown to outperform all other algorithms in a stochastic dominance analysis. The proposed approach has also been applied to an electric power distribution network design (a multibranch problem), outperforming the results presented in a former reference (which have been obtained with an Ant Colony algorithm). The results of some landscape dispersion analysis suggest that the proposed normed-space network vector representation is analogous to some continuous-variable space dilation operations, which define favorable space coordinates for optimization.