Information Technology Reference
In-Depth Information
Solving NP-Complete Problems by Harmony Search
Mehrdad Mahdavi
Department of Computer Engineering, Sharif University of Technology, Tehran, Iran
mahdavi@ce.sharif.edu
Abstract.
In the last few years, there has been explosive growth in the application of Harmony
Search (HS) in solving NP-complete problems in computer science. The success of the HS al-
gorithm in finding relatively good solutions to these problems discriminates it as an affirmative
alternative to other conventional optimization techniques. This chapter surveys the existing
literature on the application of HS in combinatorial optimization problems. We begin by pre-
senting HS based algorithms for solving problems such as Sudoku puzzle, music composition,
orienteering problem, and vehicle routing. We then turn to solve a multicast routing problem
with two constraints (i.e. bandwidth and delay constraints). Finally, we show how to apply HS
to a clustering problem.
Keywords:
Harmony Search, Sudoku Puzzle, Music Composition, Orienteering Problem, Ve-
hicle Routing, Multicast Routing, Clustering.
1 Introduction
Many real world applications in computer science are NP-complete problems which
have a growing importance in the scientific and industrial world. No polynomial-time
algorithm has yet been discovered for NP-complete problems, nor has anyone yet
been able to prove that no polynomial-time algorithm can exit for any one of them. In
many real life settings, high quality solutions to these problems such as multicast
routing, clustering, and vehicle routing are required in a very short amount of time,
and many algorithms to tackle them have been developed. In cases, especially when
large scale problems are considered, metaheuristics are one of the best alternatives
people can often rely on since exact algorithms take exponential time to find an opti-
mal solution. This chapter deals with some harmony search applications in computer
science, especially NP-complete problems, for example: a Sudoku puzzle, a music
composition, a generalized orienting problem, a vehicle routing problem, a multicast
routing problem, and a document clustering problem.
The Sudoku puzzle consists of a partially completed row-column grid of cells par-
titioned into blocks, to be filled with a prescribed set of
N
distinct symbols (typically
the numbers {1, ...,
N
}), so that each row, column and block contains exactly one of
each element of the set. The puzzle can be solved using a variety of algorithms. This
chapter shows how efficiently and effectively Sudoku puzzle can be solved using the
HS algorithm.
Music composition is analogous to optimization in some ways and could be formu-
lated as an optimization problem which is solvable by metaheuristic algorithms. Also,
HS mimics musicians' behaviors such as random play, memory-based play, and pitch-
adjusted play when they perform improvisation. Thus, there clearly exists similarity.
This chapter shows the HS application with music composition.
Search WWH ::
Custom Search