Crossover and mutation based cloning parent for degree Constrained Minimum Spanning Tree Problem (d-MSTP)

In this paper we present a survey on Genetic Operators for d-MST problem with a discussion. The contribution has two parts. The first part contains the specification of the proposed operators of crossing and mutation. The new operators offer the locality, complete heredity, and are nevertheless computationally efficient. We target to generate only valid solutions without intermediate stages such detection´s cycle and elimination´s cycle. The encoding used is based edges-set. So, we present crossover algorithm and mutation algorithm. D-MST problem is applied to topological conception in wireless and connected network. In wireless network and particularly in Ad Hoc network and especially in routing algorithms as OLSR based MPR. Selected nodes as a multipoint relay (MPR) by some neighbor are modeled by spanning tree to cover all nodes. So, spanning tree concept is applied to optimize the tree with the constraint of the degree of selected node as an MPR. In the second part, we aim to optimize the topology of network and we apply the proposed operators to degree-Constrained Minimum Spanning Tree Problem (D-MST). For simulation we take a complete graph with nine nodes with simulation´s parameters used in [Zou and al]. We give simulation´s results and a comparative study between [Lixia Hanr and al]´s results and [Zou and al]´s results and proposed operators. We conclude that the spanning tree of MPR evaluated by our operators is reached with reduced number of evaluation and all solutions are valid.