Engineering, Technology & Applied Science Research Vol. 8, No. 4, 2018, 3172-3176 3172  
  

www.etasr.com Qasem & Massadeh: Solving Cell Placement Problem Using Harmony Search Algorithms 
 

Solving Cell Placement Problem Using Harmony 
Search Algorithms 

 

Rose M. Al Qasem 
Department of Computer Engineering 
Faculty of Engineering Technology 

Al Balqa Applied University 
Amman, Jordan 

rose.alqasem@fet.edu.jo 

Samah M. Massadeh 
Department of Computer Engineering 
Faculty of Engineering Technology 

Al Balqa Applied University 
Amman, Jordan 

samah.massadeh@fet.edu.jo

 

Abstract—Cell placement is a phase in the chip design process, in 
which cells are assigned to physical locations. A placement 
algorithm is a way that satisfies the objectives and minimizes the 
total area while keeping enough space for routing. Cell placement 
is an NP-complete problem of very large size. In order to solve 
this problem, diversified heuristic algorithms are used. In this 
work, a new algorithm is proposed based on the harmony search 
algorithm. The harmony search algorithm mimics music 
improvisation process to find the optimal solution. Cell placement 
problem has many constraints, so in this work, the harmony 
search algorithm is modified to adapt to these constraints. 
Experiment results show that this algorithm is efficient for 
solving cell placement and is characterized by good performance, 
solution quality and likelihood of optimality. 

Keywords-optimization; harmony search ; cell placement 

I. INTRODUCTION 
Chip design is a process of consecutive phases, and one of 

the important phases in creating a VLSI circuit is physical 
design. The physical design process has four consecutive steps, 
namely partitioning, cell placement, routing and compaction. In 
the cell placement stage, the description of the physical layout 
of the cells is produced by assigning geometric coordinates to 
the cells. The smaller feature size is the objective of this 
placement. The small size has many advantages like higher 
performance and lower power consumption. The objective of 
the placement algorithm is to find a layout that optimally or 
nearly optimally minimizes a cost function. The cost function 
realizes that the major part is the area, but quite often involves 
the aspect ratio, to make the chip as close to square as possible. 
Cell placement is one of the NP-complete problems which are 
generally combinatorial in nature and have a noisy solution 
space. Several heuristic optimization techniques have been 
produced to solve the placement problem by using a set of 
diversified algorithms like genetic algorithms [1] and simulated 
annealing [2]. A comprehensive summary of those techniques 
is introduced in [3]. 

Harmony search (HS) is a phenomenon-mimicking meta-
heuristic algorithm which has been proposed in [4]. HS is a 
novel approach inspired from the musical process of searching 
a perfect state of harmony as in music improvisation where the 

pitch of each musical instrument is improved to accomplish 
this better state of harmony. The pitch determines the quality of 
music, just as the fitness function value determines the quality 
of solutions. Furthermore, the musician improvisations are 
analogous to local and global search schemes in optimization 
strategies. HS has been used to solve various types of 
optimization problems, such as traveling salesperson problem 
[4], function optimization [5], mechanical structure design [6], 
tour routing [7], water network design [8], pipe network 
optimization [9], vehicle routing [10] and optimization of data 
classification systems [11]. It is showing significant 
improvements over other heuristics. It can be produced for both 
continuous and discrete variables. A special discrete variation 
of the HS is produced on the basis of introducing the stochastic 
derivatives for the discrete variables involved [12]. For the 
class of binary optimization problems, the HS algorithm is 
equivalent to a certain evolutionary algorithm as shown in [13]. 
A lot of modified HS algorithms have been studied in order to 
enhance the performance of the original version [14, 15]. 

In this work, we present a solution to the cell placement 
problem using the HS methodology, and in future work we will 
compare its performance with well-known evolutionary 
algorithms. The results show that the proposed algorithm can 
improve the quality of the solution. The rest of the paper is 
organized as follows: Section II describes briefly the cell 
placement problem. Section III gives a formal description of 
the HS theory, and Section IV demonstrates the proposed HS 
algorithm for cell placement, followed by presentation and 
discussion of the experimental results in Section V. Finally, 
Section VI wraps up our work. 

II. CELL PLACEMENT PROBLEM: REPRESENTATION AND 
FITNESS 

In this work, each solution is a sequence represented by the 
normalized polish notation (RPN) [16]. The sequence includes 
module names and two relational operators: for n blocks, a 
string with n blocks (cells) and n-1 operators of the + or * type, 
corresponding to a vertical or horizontal cut respectively. As an 
example, the expression (12+34*+5+67+*) is an encoding for 
the arrangement representing a possible solution as illustrated 
in Figure 1. 



  

exi
[16
fitn
far
cal

wh
pla
enc
ass
rel
val
of 
rat

sum
im
com
the
bet
the
sta
pit
the
po
var
the
or 
HS
heu
or 
HS
par
con

wh
wh
fun
by 

1) 

ma
sol

Engineerin

www.etasr

Commonly, 
isting ones by
6, 17]. The q
ness value. Th
r the solution i
lculated by the

F= (1
here, T is th
acement, L an
closing all the
sociated with t
lative significa
lue of the fact
α are used to 

tio is not optim

III.

HS algorith
mmarize HS,

mprovisation d
mposed, the m
e music pitche
tter state of ha
e optimal solu
age, the musici
tch from the m
e memory or 
ssible pitches
riable picks a 
e memory, tak
take a random

S algorithm fo
uristic and the
consideration

S algorithm co
rameters: har
nsideration rat

A. The GS
The HS alg

here a single 
hich optimizes
nction. The de
 the following

Step 1 

Initialize the 
atrix contains
lutions to th

ng, Technology

r.com 

Fig. 1.  S

the new solu
y using certain
quality of the 
he proposed m
is from the op
e following eq1 )    
he total area 
nd W are the l
e cells and the
the solution. T
ance of the as
tor α is within
favor square 

mized. 

. HARMONY
m has been 
, it is requir

done for the h
musicians try v
es stored in t

armony is anal
utions to the p
ian can select 

memory, perfor
perform a ran
s. Similarly, 
value from th

ke a value adja
m value from t
ormalized thes
e three corresp

n, pitch (soluti
ontrols the thre
rmony mem
te (HMCR), an

SA Behavior 

gorithm tries t
objective is 

s (minimizes o
etails of the h

g steps. 

harmony sear
s a certain n
he problem u

y & Applied Sci

 
Slicing structure. 

utions are rep
n methods whi

new solution
measure of the 
ptimal one. Th
quation:  

of all cells 
length and wid
e product WL 
The factor α us
spect ratio to 
n the range of 
arrangements

Y SEARCH ALGO

proposed in
red to idealiz
harmony. Wh
various possib
the memory. T
logous to the p
problem. In m
one of three o
rm a pitch adja
ndom pitch fro
in HS algori

hree options: t
acent to any v
the domain of 
e three option
ponding proce
ion) adjustmen
ee options by m

mory (HM), 
nd pitch adjust

to solve optim
considered, b

or maximizes)
harmony algor

rch memory (H
number of ra
under conside

ience Research

Qasem & M

produced from
ich are presen

n is evaluated
fitness reflect

he fitness meas

 (1)

regardless o
dth of the rect
represents th

sed to determin
the actual are
[0–1]; small v
. If α=1 then a

ORITHM  

n [4]. In ord
ze the proce

hen the harmo
ble combinatio
This search fo
procedure of fi
music improvi
options: perform
acent to any ot
om the range 
ithm each de
take any value
value in the me
f all possible v
ns for making 
ess are memor
nt and random
means of three
harmony me
tment rate (PA

mization prob
by finding a v
) a certain obj
rithm are illus

HM), the initia
andomly gen
eration. For a

h V

Massadeh: Solv
 

m the 
nted in 
d by a 
ts how 
sure is 

of the 
tangle 
e area 
ne the 

ea, the 
values 
aspect 

der to 
ess of 
ony is 
ons of 
for the 
inding 
isation 
m any 
ther in 
of all 

ecision 
e from 
emory 
values. 
a new 
ry use 
mness. 
e main 
emory 

AR). 

blems, 
vector 
ective 

strated 

al HM 
erated 
an n-

dim
mem

whe
dim

2)

pro
com













whe
loca



whe
The
use

3)

eva
the 
rep
is d

4)

max

effe
of t
app

Vol. 8, No. 4, 20

ving Cell Placem

mension proble
mory size) is r

HM=

,,
,

ere, (x ,x ,…
mension of the 

Step 2 

Improvise a n
oduced based 
mponent of new

Generate a ran

Compare the
HMCR is d
component fr

If R1<HMCR
HM, it is cho
vector 

The obtained
PAR, where 
candidate solu

Generate a ne

If R2<PAR, tx = x ±
ere BW is ba
al search 

If the conditio
solution is genx = l
ere l, u is the 
e generation o
e of all the HM

Step 3 

Update HM: 
aluated. If its 

worst memb
laced by the n

deleted.  

Step 4 

Repeat Step 
ximum iteratio

The paramete
ects in the opti
the challengin
propriate valu

018, 3172-3176

ment Problem U

em, a HM w
represented by, ,…,, ,…,... ,…,…,x 	  ) is a c
problem. 

new solution 
on harmony m
w solution xj i

ndom number

e random num
defined as th
rom the HM m

R, the xj of th
osen from the 

d solution xj 
the PAR de

ution selected 

ew random num

then adjust therand(0,1).BW
andwidth facto

on R1<HMCR
nerated randomu l .rand
lower and upp
f new solution

M vectors. 

After the n
objective func
ber in the HM
new solution. O

2 to Step 3 u
ons) is satisfie

ers of HMCR
imization perf

ng topics for th
ues for these

6 

Using Harmony

with the size o
y the following

   

candidate solu

from the HM
memory consi
is obtained as 

r R1 within the

mber R1 wit
he probabilit

members. 

he new solutio
jth dimension

is further mu
etermines the
from the HM 

mber R2 withi

e obtained soluW   
or, which is u

R fails, the xj v
mly as followsd(0,1)  
per bound for 
ns in the HS st

ew solution 
ction value is 
M, the worst
Otherwise, the

until a termina
ed. 

R and PAR us
formance of th
he HS algorith
e parameters. 

3173  

y Search Algor

of HMS (harm
g matrix: 

 (2)

ution and n i

M. Each soluti
idering rules.
follows: 

e range [0-1] 

th a HMCR. 
ty of selectin

on comes from
n of a random

utated accordin
e probability 
to be mutated

in the range [0

ution as follow

 (3)

used to contro

variable of the
s: 

 (4)

the given prob
trategies make

is generated, 
better than th

t member wi
e generated sol

ation criterion 

sually have cr
he HS strategy
hm is choosin

Authors in 

rithms 

mony 

s the 

ion is 
Each 

The 
ng a 

m the 
m HM 

ng to 
of a 

d. 

0-1] 

ws: 

ol the 

e new 

blem. 
es full 

it is 
hat of 
ill be 
lution 

(e.g. 

ritical 
. One 

ng the 
[18] 



Engineering, Technology & Applied Science Research Vol. 8, No. 4, 2018, 3172-3176 3174  
  

www.etasr.com Qasem & Massadeh: Solving Cell Placement Problem Using Harmony Search Algorithms 
 

produced an adaptive method for adjusting PAR and BW 
parameters in the improved HS (IHS) algorithm. In this 
method, in order to improve the performance of the HS, the 
values of PAR and BW increase and decrease dynamically and 
respectively with the growth of HS iterations. The updates of 
PAR and BW are often case dependent and are therefore 
difficult to determine. 

IV. HS ALGORITHM BASED CELL PLACEMENT PROBLEM 
As mentioned above, cell placement can be represented as a 

two-dimensional bin packing problem, where its main goal is 
to order the cells in a way that minimizes the area and produces 
near square shape while providing enough space for routing. In 
this work, we propose a new algorithm for cell placement 
problem based on HS algorithm, in which each pitch will be an 
agent looking for an optimal solution in the search space. It is 
difficult to solve the cell placement problem by the traditional 
HS algorithm, because this problem needs meet simultaneously 
several constraints. For this reason, the update of pitch 
(solution) depends on some rules, so as to solve the cell 
placement problem by using harmony search algorithm, there 
are some modifications that must be done as will be shown in 
the following procedure. The HS algorithm based cell 
placement problem is outlined as follows: 

1. Harmony memory initialization 

1.1 Randomly generate initial population harmony 
memory of vectors (solutions) (X1,X2,…,XHMS ) as many 
as the HMS where Xi =x   , i=1…HMS and    j=1…n, n is 
the dimension of the problem. 

1. 2 Store the vectors in HM matrix as shown in (2).  

2. Construction and evaluation of new solution candidate. 

2. 1 Generate a new vector Xnew: 

For each component (decision variable) x of the new 
vector Xnew 

do { 
Generate random number R1 within the range [0-1] 
If (R1<HMCR)  
Then 
{ 
Let the decision variable  in X

new be the jth dimension of 
a randomly selected HM member( ). This selection must 
meet the constraints of the cell placement problem, otherwise 
another HM member should be selected.  

Generate random number R2 within the range [0-1] 
If (R2<PAR) 
Then  
Apply pitch adjustment distance BW to mutate  as 

follows: 
If selected HM member       is cell 
Then x = ± BW    (5) 
Otherwise  x =     (6) 
} 

Else  
Let  in X

new be a random value. 
Where   ∈  {1, 2… m},   m is the number of cells. 
} 

2.2 Evaluate the fitness of Xnew by objective fitness 
function f as in (1). 

3. Update harmony memory  

If the fitness of new solution Xnew   is better than the fitness 
of the worst HM member 

Then  
Replace the worst HM member with new solution Xnew. 
Else   
Disregard Xnew. 

4. If Stopping Criteria Not Met Then Go to step 2 Else Stop.  

The effects of parameters are analyzed. The best 
performance of HS algorithm for solving placement problem is 
detected, when the values of the parameters are set as follows: 
HMS is the size of the HM. It generally varies from 50 to 100 
and the used value is 60. HMCR is the rate of choosing a value 
from the HM. It generally varies from 0.7 to 0.99 and the used 
value is 0.8. PAR is the rate of choosing a neighboring value. It 
generally varies from 0.1 to 0.5 and the used value is 0.22. BW 
is the amount of maximum change in solution adjustment and 
the used value is 1. It is possible to vary the parameters values 
as the search progresses. 

V. RESULTS 
The quality measures used in this study include the 

following: average fitness value for a set of runs, number of 
iterations employed (elapsed time), and number of successes in 
a set of runs (success rate). In this work, the performance of the 
HS algorithm for solving the cell placement problem was 
evaluated by using two methods. In the first method, instances 
from MCNC benchmark are chosen to assess the quality of the 
solutions. In the second method, the algorithm is performed on 
three cases of cell placement problem generated randomly and 
have known optimal solutions to measure the possibility of 
reaching the optimal solution.  

In the first test, three cases from MCNC benchmarks, 
Xerox with 10 cells, Ami33 with 33 cells, and Ami49 with 49 
cells, were chosen and tested. Table I shows a summary of the 
obtained results. The measure used in this test is the quality of 
solution in terms of wasted area. The number of replicates 
which carried out for each problem is 10 runs, each with 
different random starts. The algorithm is brought to stop when 
6000 iterations have passed since the last improvement was 
happened or the number of iterations reaches 20,000, 40,000 
and 60,000 for Xerox, Ami33 and Ami49 respectively. The 
results for the three instances of MCNC benchmark are 
summarized in Table I. The percentage of wasted area for the 
best, worst and mean case is noted in the last three columns of 
the table. The obtained results present that the proposed 
algorithm achieves good area utilization in the best and mean 
wasted area. Figure 2 illustrates the search improvement of the 
algorithm through time, waste area versus iterations number for 
Ami49 and Ami33. The figure clearly indicates that through 



  
the
res

10
in 
wit
the
wit
In 
wit
Th
ini
sol
25
me
lik
res
col
har
ran
mo
alg
the

TA

Engineerin

www.etasr

e passage of ti
sults. 

T

 # of c
Xerox 10
Ami33 33
Ami49 49

Fig. 2.  Searc

In order to p
, 20 and 30 ce
the first case
th total area o
e second case
th total area o
the third case
th total area o

he number of 
itial populatio
lution is achie
,000 and 40,00
etric used to ev
kelihood of op
sult for the suc
lumn of Table
rmony search 
ndom trials. T
ost runs. In 
gorithm is 70%
e last case.  

Fig. 3.  

ABLE II.  ART

# of cells 
10 
20 
30 

ng, Technology

r.com 

ime the propo

TABLE I.  B

 
cells # of Iter
0 20,0
3 40,0
9 60,0

ch progress. Wast

perform the se
ells were gene

e, an instance 
f 25 square un
, an instance 

of 100 square 
e, an instance 
of 225 square 
trials for each

on. The algo
ved or the num
00 for case1, c
valuate the pro
ptimality or s
ccess rate for 
e II, in the fir
based cell pla

The algorithm 
the second c

%, whereas the

Artificial proble

TIFICIAL PROBLEM

# of iteration
10,000 
25,000 
40,000 

y & Applied Sci

osed algorithm

BENCHMARK RESU

W
rations Best 
000 3.3 
000 5.4 
000 7.5 

 

te area vs iteration

cond test, thre
erated. As illu
is produced b

nits into 10 var
is produced b
units into 20 v
is produced b

units into 30 v
h case is 10 t

orithm is halt
mber of iterati
case2 and case
oposed algorith
success rate. T
each case. As
rst case, the s
acement is 90%
obtained the 

case, the suc
e success rate 

 

ems for known op

M OF KNOWN OPTI

ns  Success R

ience Research

Qasem & M

m can achieve 

ULTS 

Wasted Area (%)
Worst M

6.2 4
8.8 6
9.5 8

 
ns (Ami49, Ami3

ee optimal cas
ustrated in Fig
by cutting a s
rious size bloc
by cutting a s
various size b
by cutting a s
various size b
times with dif
ted if the op
ions reaches 10
e3 respectively
hm in this test
Table II show
s shown in the
success rate fo
% over 10 dif
optimal solut

ccess rate fo
dropped to 5

 
ptimal solution  

IMAL SOLUTION 

Rate(out of 10) 
9 
7 
5 

h V

Massadeh: Solv
 

better 

) 
Mean 

4.8 
6.5 
8.5 

33). 

ses for 
gure 3, 
square 
cks. In 
square 
blocks. 
square 
blocks. 
fferent 
ptimal 
0,000, 
y. The 
t is the 
ws the 
e third 
for the 
fferent 
ion in 
r this 
0% in 

pro
bett
size

plac
pro
solu
exp
algo
find
real
ave
that
cell
com
algo

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

Vol. 8, No. 4, 20

ving Cell Placem

It is clear th
oblems, but on
ter performan
e. 

In this work a
cement probl

oposed algorith
ution quality
periments sho
orithm appea
ding the optim
lizes promisin

erage of waste
t the HS algor
l placement pr
mparison betw
orithms. 

T. W. Manikas
and Standard C
and Systems, V

G. Nan, M. Li
Standard Cell P
Notes in Compu

K. Shahookar, P
Computer Surv

Z. W. Geem, 
optimization al
pp. 60–68, 2001

K. S. Lee, Z. W
engineering op
Computer Meth
No. 36–38, pp. 

K. S. Lee, Z. W
the harmony se
9-10, pp. 781–7

Z. W. Geem, C
orienteering pro
Science, Vol. 36

Z. W. Geem, “O
harmony search
277, 2010  

Z. W. Geem, 
optimization: ap
of Modelling an

] Z. W. Geem, K
Vehicle Routin
12, pp. 1552–15

] X. Wang, X. Z.
and harmony 
systems”, Intern
1-2, pp. 80–88, 

] Z. W. Geem, “N
design variables
1, pp. 223–230,

] M. Padberg, “
problems”, in: O
2012 

] M. G. H. Omra
Mathematics an

018, 3172-3176

ment Problem U

hat this algor
n the other si
nce for the pr

VI. CO
a new algorithm
em which is 
hm has achie

y and the l
ow that the 
ars in terms 
mal solution, 
ng area utiliza
ed area for a se
rithm is one ef
roblem. Hence
ween this alg

REFER
, M. H. Mickle, “
Cell Placement”, 

Vol. 2, pp 115-118

i, D. Lin, J. Ko
Placement”, Adv
uter Science, Vol

P. Mazumder, “V
ey, Vol. 23, No. 2

J. H. Kim, G
lgorithm: harmon
1 

W. Geem, “A new
ptimization: har
hods in Applied 
3902–3933, 2005

W. Geem, “A new 
earch algorithm”, 
798, 2004 

C. L. Tseng, Y. 
oblem: best tourin
612, pp. 741–750

Optimal cost desi
h”, Engineering 

J. H. Kim, G
pplication to pipe
nd Simulation, Vo

K. S. Lee, Y. Par
ng”, American Jo
557, 2005 

. Gao, S. J. Ovask
search method i
national Journal o
2009 

Novel derivative o
s”, Applied Math
, 2008 
“Harmony Search
Operations Resea

an, M. Mahdavi, 
nd Computation, V

6 

Using Harmony

rithm is robu
de it needs en

roblems with 

ONCLUSION  

m was present
 based on H

eved good res
likelihood of
performance 
of increasing
and the qual

ation in terms
et of trials. Th
fficient algorit
e, in future wo
gorithm and o

RENCES 
“A Genetic Algor
45th Midwest S

8, 2002 

ou, “Adaptive Sim
vances in Natural
. 3612, pp. 943-9

VLSI Cell Placem
2, pp. 143–220, 1

G. V. Loganatha
ny search,” Simu

w meta-heuristic al
rmony search t
Mechanics and 

5 

structural optimi
Computers and S

Park, “Harmony 
ng in China”, Lec
0, Springer, 2005 

ign of water distr
Optimization, Vo

G. V. Loganath
e network design
ol. 22, No. 2, pp. 

rk, “Application 
ournal of Applied

ka, “Fusion of clo
in optimisation 
of Bio-Inspired Co

of harmony searc
hematics and Com

h Algorithms fo
arch Proceedings, 

“Global-best har
Vol. 198, No. 2, p

3175  

y Search Algor

ust for small 
nhancement t
medium and 

ted to solve th
HS algorithm. 
sults regarding
f optimality.

of the prop
g success rate
lity of solutio
s of minimum
his study evide
thm for solvin
ork we will m
other optimiz

rithm for Mixed 
Symposium on C

mulated Anneali
l Computation, L
47, Springer, 200

ment Techniques”,
991 

an, “A new he
ulation, Vol. 76, N

lgorithm for cont
theory and pra
Engineering, Vol

zation method ba
Structures, Vol. 8

search for gener
cture Notes in Com

ribution networks
ol. 38, No. 3, pp

han, “Harmony 
n”, International J
125–133, 2002  

of Harmony Sea
d Sciences, Vol.

onal selection alg
of fuzzy classifi
omputation, Vol.

ch algorithm for d
mputation, Vol. 19

or binary optimi
pp. 343–348, Sp

rmony search”, A
pp. 643–656, 2008

rithms 

 size 
to get 
large 

he cell 
 The 
g the 

The 
posed 
e for 
on. It 

m and 
ences 

ng the 
make a 
zation 

Macro 
Circuits 

ng for 
Lecture 
05 

, ACM 

euristic 
No. 2, 

tinuous 
actice”, 
l. 194, 

ased on 
82, No. 

ralized 
mputer 

s using 
p. 259-

search 
Journal 

arch to 
2, No. 

orithm 
fication 

1, No. 

discrete 
99, No. 

ization 
ringer, 

Applied 
8 



Engineering, Technology & Applied Science Research Vol. 8, No. 4, 2018, 3172-3176 3176  
  

www.etasr.com Qasem & Massadeh: Solving Cell Placement Problem Using Harmony Search Algorithms 
 

[15] Q. K. Pan, P. N. Suganthan, J. J. Liang, M. F. Tasgetiren, “A local-best 
harmony search algorithm with dynamic subpopulations”, Engineering 
Optimization, Vol. 42, No. 2, pp. 101–117, 2010 

[16] D. F. Wong, C. L. Liu, “A New Algorithm for Floorplan Design”, 23rd 
ACM/IEEE Design Automation Conference, Las Vegas, Nevada, USA, 
pp. 101–107, February 6, 1986 

[17] J. P. Cohoon, S. U. Hedge, W. N. Martin, D. S. Richards, “Distributed 
genetic algorithms for the floorplan design problem”, IEEE Transactions 
on Computer-Aided Design, Vol. 10, No. 4, pp. 483–492, 1991 

[18] M. Mahdavi, M. Fesanghary, E. Damangir, “An improved harmony 
search algorithm for solving optimization problems”, Applied 
Mathematics and Computation, Vol. 188, No. 2, pp. 1567–1579, 2007