This paper deals with the Optimum Communication Spanning Tree Problem (OCST) which is well known as an NP-hard problem. For solving the problem, we uses an evolutionary approach. This paper presents a new effective tree encoding and proposes a tree construction routine (TCR) to generate a tree from the encoding. The basic principle is to break a cycle. We also propose a new crossover operator that focuses on the inheritance of parental information and the use of network information. Consequently, we confirm that the proposed algorithm is superior to other algorithms applied to the OCST problem or other tree problems. Moreover, our method can find a better solution than the solution which was previously known as the best solution. In addition, we analyzed the locality and diversity property of encoding and observed that the proposed method has high locality and at the same time it preserves population diversity for many generations. Finally, we conclude that these properties are the main reasons why the proposed method outperforms the other encodings.

A novel evolutionary algorithm is described for designing the topology of spanning tree-based communication networks. Two specific performance objectives are dealt with: the optimum communication spanning tree problem (OCSTP), and the quadratic minimum spanning tree problem (q-MST). Improved network performance is reliably obtained when using the proposed algorithm on accepted benchmark instances, in comparison with the previous best-known approaches. The same methodology can be applied straightforwardly to the design of communication networks with other objectives.