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

Fig. 4. Schematic of school bus routing network
number of computational runs are the same in both algorithms. In HS, the number of
function evaluations is 1,000 and the number of runs is 20 with different HMS, HMCR,
and PAR. In GA, the number of function evaluations is 1,000 (= population size × num-
ber of generations) and the number of runs is 20 with different population size, cross-
over rate, and mutation rate, recommended by Koumousis and Georgiou [11].
Both algorithms could find the global optimum solution. However, HS reached it
twice while GA did it once out of 20 different runs. The average costs were $399,870
in HS, and $409,597 in GA. In addition, HS performed each run slightly faster than
GA on the same machine.
6 QoS Based Multicast Routing
Many newer applications on the Internet fit into the model where the same informa-
tion is sent to multiple receivers with varying quality of service (QoS) constraints
concurrently, such as an audio conference, interactive multimedia games and web-
base learning. These applications are better supported by a model termed multicast
where information is sent to a specific group simultaneously and is only duplicated
for delivery purposes when necessary in the most efficient way. Two important QoS
constraints are the bandwidth constraint and the end-to-end delay constraint. The QoS
based multicast routing problem is a known NP-complete problem that depends on (1)
a bounded end-to-end delay and link bandwidth along the paths from the source to
each destination, and (2) a minimum cost of the multicast tree.
Accordingly, multicast routing plays a critical role in the bulk of these new appli-
cations. Designing multicast routing algorithms is technically challenging and a com-
plicated task to deliver multimedia information in a timely, smooth, synchronized
manner over a decentralized, shared network environment.
Generally, there are two approaches to solve this problem: (1) obtaining an optimal
solution in exponential time; (2) obtaining near-optimal solutions by metaheuristic