Solving NP-Complete Problems by Harmony Search - Music-Inspired Harmony Search Algorithm: Theory and Applications - page 61

Fig. 6. Solution by HS for 15 node network
One of the most important decisions in applying evolutionary algorithms to the
multicast problem is how to encode the solutions. Prüfer numbers offer a deceptively
elegant coding of spanning trees. In a complete undirected graph with n nodes, there
are n n-2 distinct spanning trees.
In edge set representation, each tree is directly represented as a set of its edges. In
characteristic vector representation, each solution is represented by a binary vector of
|E| bits in which k th bit indicates whether k th edge is or is not part of the tree. Prede-
cessor coding is another representation which designates a root for the tree and then
records the predecessor of each node in the tree. In NPI each tree is traversed with
breadth-first search (BFS) or depth-first search (DFS) algorithms and each node with
its parent's index is inserted to a list in consecutive cells. After determining the repre-
sentation method, the solutions are encoded in the target representation and inserted
into the solutions' pool.
6.2 Application on Real Benchmark Networks
In recent years various optimization methodologies have been developed for con-
structing optimal multicast constrained trees. SA [17], GA [18-23] and TS [24-29]
are general high-level procedures that coordinate simple heuristics and rules to find
good approximate solutions to computationally difficult combinatorial optimization
problems. These methods have been previously employed to solve the problem of
multicast routing, and results showed that these methods are suitable to achieve near-
optimal results within a reasonable time [22, 23, 26, 30]. Two algorithms are