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

proposed in [31] for solving the mentioned problem by HS. The first algorithm,
named HSPR, is based on Prüfer representation and the second one, called HSNPI, is
based on Node Parent Representation (NPI) encoding proposed in [31, 32].
HSPR, HSNPI, and the GA-based algorithm [23] are applied to real data networks.
These real networks are obtained from three synthetic instances of the OR-Library
called steinb10, steinb11, and steinb18 which are used for the graphical Steiner tree
problem. The networks were modified for multicast routing in [31].
Table 1 summarizes the results obtained by applying the HS and GA-based algo-
rithms on the instance networks from the OR-Library. The statistically significant best
solutions have been shown in bold. The results provide evidence that the HS outper-
forms GA in all except for three instances. Table 1 shows that the ratio of the high-
quality solutions for HS ranges from 93% to 98%. However, considering both the
tractability of an NP-hard problem and the low time complexity of the problem, it is
still of practical sense. Table 1 shows that for the small groups the cost deviation of
HS is approximately zero and solutions are very close to the optimal one.

Table 1. Simulation results for HS and GA on real topologies

HS GA

# of
Multicast
Group

Network
Topology

Optimal
Cost

Success
Ratio (%)
Steinb10 10 75 18,891 97 31,215 98
Steinb10 20 162 20,026 93 32,024 92
Steinb10 30 234 17,142 95 28,023 93
Steinb11 10 62 16,043 98 24,888 96
Steinb11 20 145 16,803 99 26,902 98
Steinb11 30 237 27,651 96 24,539 96
Steinb15 20 174 19,446 98 26,052 97
Steinb15 30 261 24,871 97 34,558 94
Steinb15 40 328 20,623 94 27,340 95
The analysis presented in [31] on real and random networks shows that while the
problem of optimal constrained multicast routing is NP-hard [33], the meta-heuristic
model based on HS produces good solutions. Also empirical performance shows that
the HSNPI algorithm results in the best overall performance with regard to total tree
cost in a comparison with a recently developed algorithm based on GA and a modi-
fied version of heuristic BSMA algorithm.
Figure 7 shows the execution time of HSPR, HSNPI, BSMA [13], and GA [23] al-
gorithms on a randomly generated network with a different size. As seen in Figure 7,
the HSNPI and BSMA models yield very competitive execution time, especially
when network nodes are smaller than 45. When they are smaller than 45, the execu-
tion time of HSNPI model is almost same as BSMA model. Although the BSMA has
a slightly better execution time than HSNPI, the difference in average cost of HSNPI

Mean # of
Iterations

Success
Ratio (%)

Mean # of
Iterations