TELKOM
NIKA
, Vol.11, No
.4, Dece
mbe
r
2013, pp. 83
5~8
4
4
ISSN: 1693-6
930,
accredited
A
by DIKTI, De
cree No: 58/DIK
T
I/Kep/2013
DOI
:
10.12928/TELKOMNIKA.v11i4.1384
835
Re
cei
v
ed Ap
ril 28, 2013; Revi
sed
Jul
y
1
4
, 2013; Acce
pted Septem
ber 12, 20
13
Improved Harmony Search Algorithm with Chaos for
Absolute Value Equation
Longqua
n Yong*
1
, San
y
a
ng Liu
2
, Shouheng Tuo
3
, Kai
Gao
4
1,2,3,4
School of Science,
Xid
i
an Unive
r
sity
, Xi’an 71007
1, China
1
School of M
a
thematics a
nd Com
pute
r
Scie
n
c
e, Sha
anxi Universit
y
of Technolo
g
y
Han
z
h
ong 7
2
3001, China
*Co
rre
sp
ondi
ng autho
r, e-mail: yonglon
gqua
n@126.
com
1
, yonglo
ngqu
an
@gm
a
il.com
1
,
liusa
nyang
@126.com
2
A
b
st
r
a
k
Pada tulis
an i
n
i, penc
ari
an h
a
rmoni
plus c
h
aos di
ti
ngk
atka
n (HSCH) d
i
saj
i
kan u
n
tuk
me
mec
ahk
a
n
persa
maan ni
l
a
i abso
l
ut (AVE)
A
x -
|
x
| =
b
, di mana
A
ada
lah
matriks
persegi se
mb
aran de
ng
an n
ila
i
sing
ular
mel
e
bihi satu. Has
il simulas
i
dal
am
me
mec
a
h
k
an beb
era
p
a
masal
ah AV
E yang diber
i
k
an
me
nu
njukk
an
bahw
a al
gorit
ma HS
CH ad
ala
h
vali
d da
n
lebi
h baik d
a
r
i algor
itma H
S
klasik (HS) da
n
alg
o
ritma HS d
eng
an o
perator
mutasi
difere
n
s
ial (HSDE).
Ka
ta
k
unc
i:
pe
rsamaa
n nil
a
i
mutl
ak, nil
a
i si
ngu
lar, har
mo
n
i
penc
aria
n, ke
kacau
a
n
A
b
st
r
a
ct
In this paper,
an improv
ed h
a
rmony searc
h
w
i
th
chaos (HSCH) is prese
n
ted for solvin
g NP-har
d
abso
l
ute va
lu
e
equ
ation (AV
E
)
A
x - |
x
| =
b
, w
here
A
is a
n
arbitrary s
q
u
a
re
matrix w
h
o
s
e sing
ul
ar val
ues
exceed one. The sim
u
lation
resu
lts in s
o
lving some giv
e
n AVE pr
oblem
s
dem
onstr
ate that the HS
CH
alg
o
rith
m is v
a
lid
and
outp
e
r
forms the cl
a
ssical HS a
l
go
rithm (HS) a
n
d
HS alg
o
rith
m w
i
th differe
ntial
mutati
on o
per
a
t
or (HSDE).
Ke
y
w
ords
: ab
solute va
lu
e eq
uatio
n, sing
ular
value, har
mon
y
search, chao
s
1. Introduc
tion
We cons
ider the abs
o
lu
te v
a
lue equation (AVE):
A
xx
b
(1)
whe
r
e
nn
A
R
,
,
n
x
bR
, and
x
denotes t
he vecto
r
wi
th absolute
values
of e
a
ch
comp
one
nt of
x
. A slightly
more general
form of t
he
AVE (1) was introduced in John [1] and
investigate
d
in a more g
e
n
e
ral context in Manga
sa
ria
n
[2].
As we
re
sh
o
w
n in
Cottle
et al.[3] the general NP
-ha
r
d line
a
r
com
p
lementa
r
ity probl
em
(LCP
) that
subsume
s
ma
ny mathemat
ical p
r
og
ram
m
ing p
r
obl
e
m
s
can
be f
o
rmul
ated a
s
an
absolute value equation such
as
(1).
This im
plies
that AVE (1) is NP-hard i
n
general form.
Theo
retical a
nalysi
s
focu
ses o
n
the the
o
rem
of
alternatives, vario
u
s e
quivalent
reform
ulatio
ns,
and the
exist
ence an
d no
n
e
xisten
ce of
solution
s. J
o
h
n
[1] provid
ed
a theo
rem of
the alternatives
for a more general form
of AVE (1),
A
xB
x
b
,
and e
n
lighte
n
s the
relatio
n
between th
e
AVE (1) and t
he interval
m
a
trix. The AVE (1) i
s
sh
own to be equiv
a
lent to
the bilinear
program
,
the gene
ralized LCP, and the standa
rd
LCP if 1 is n
o
t an eigenva
l
ue of
A
by Ma
nga
sari
an [4].
Based o
n
the LCP refo
rmulation, suff
icient
conditi
ons for the e
x
istence and
nonexisten
c
e of
solutio
n
s a
r
e
given.
Prokopyev proved that the
AVE
(1) can be equivalent
ly reformulated as a standard LCP
without any assumption [5]
on
A
and
B
, and discusse
d uniqu
e solva
b
ility of AVE
(1). Hu an
d
Hua
ng reformulated a
system of ab
sol
u
te value eq
u
a
tion as
a st
anda
rd line
a
r compl
e
ment
arity
probl
em with
out any assu
mption [6] a
nd gave so
m
e
existence and co
nvex
ity results for the
s
o
lution s
e
t of the AVE (1).
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 11, No. 4, Decem
ber 20
13 : 835 – 844
836
It is worth mentioning that any LCP can
be r
educed to the AVE (1), which o
w
n
s
a ver
y
s
p
ec
ial and simple s
t
ruc
t
ure. Hence how to s
o
lv
e the AVE (1) direc
t
ly attrac
ts
muc
h
attention
.
Bas
ed
on a
new reformulat
ion of the AVE (1) as
the minimization of
a
par
amet
er-f
ree piecewise
linear
co
nca
v
e minimizati
on problem
on a polyh
e
d
ral
set, Ma
nga
sari
an p
r
opo
sed a fin
i
te
comp
utationa
l algorithm th
at is solve
d
b
y
a finite
succession of line
a
r prog
ram
s
[7]. In the recent
intere
sting p
aper of Man
gasaria
n, a semism
oot
h Newton meth
o
d
is prop
ose
d
for solving
th
e
AVE (1), whi
c
h largely shortens
the computation tim
e
than the
successi
on of linear programs
(SLP) meth
o
d
[8]. It shows that the se
mismo
o
th Ne
wton iterates
are
well defin
ed and b
oun
ded
whe
n
the sin
gular valu
es
of
A
exceed 1. Ho
wever, the
global li
nea
r
conve
r
ge
nce of the method
is only gua
ra
nteed un
der
more
strin
g
e
n
t conditio
n
than the si
ng
ular value
s
o
f
A
exceed
1.
Manga
sa
rian
formulated
the NP-hard
n
-dime
n
si
onal kn
ap
sa
ck fea
s
ibility problem a
s
an
equivalent A
VE (1) in
an
n
-dim
en
siona
l noninte
ger real varia
b
le
space [9] and
prop
osed a
finite
succession of linear programs
for solving the AVE (1).
A generalize
d
Ne
wton me
thod, whi
c
h h
a
s glo
bal an
d
finite convergen
ce, wa
s p
r
opo
se
d
for the AVE by Zhang et
al. The method utilizes
both the semismooth and the smoothing
Ne
wton step
s, in which the
semismooth
Ne
wton
step
guarantee
s th
e finite conve
r
gen
ce a
nd the
smoothi
ng Newton ste
p
contri
bute
s
to the
global
convergen
ce [10]. A smoothing
Ne
wton
algorith
m
to solve the AV
E (1)
wa
s prese
n
ted by
L
ouis
Ca
ccetta. The algo
rith
m wa
s prove
d
to
be globally co
nverge
nt [11]
and
the conv
erge
nce rate wa
s quad
ra
ti
c unde
r the condition that the
sing
ular valu
es of
A
exceed
1. This cond
ition was we
ake
r
than the one used in Manga
sa
rian.
Rec
ently, AVE (1) has
been inves
t
i
gated in the literature [12-15].
In this pape
r, we p
r
esent a
n
improve
d
h
a
rm
o
n
y sea
r
ch with ch
ao
s (HS
C
H). By followin
g
cha
o
tic ergo
dic orbits, we
embed ch
ao
s in the
pitch
adjustme
n
t operation of HS with ce
rtain
prob
ability (RGR). More
over, ch
ao
s
is i
n
co
rpo
r
ate
d
into HS to con
s
tru
c
t a chaot
ic HS, whe
r
e
the
parall
e
l popul
ation-b
a
sed
evolutiona
ry sea
r
ching
abi
lity of HS and chaoti
c
se
arching be
ha
vior
are
rea
s
o
nab
ly combin
ed.
The n
e
w
alg
o
rithm p
r
op
o
s
ed i
n
this
pa
per,
called
HSCH. Simulat
i
on
results an
d compa
r
ison
s d
e
mon
s
trate th
e effect
ivene
ss a
nd efficie
n
cy of the pro
posed HS
CH.
In s
e
c
t
ion 2,
we give
s
o
me lemmas
that
ensure the s
o
lution to
AVE (1), and pres
ent
HSCH metho
d
. Nume
ri
cal
simulatio
n
s
and
comp
ari
s
on
s a
r
e p
r
o
v
ided in Se
ction 3 by solving
s
o
me given
AVE problems
with
s
i
ngular values
of
A
excee
d
ing 1.
Section 4 concl
ude
s the
pape
r.
We n
o
w de
scribe
our notati
on. All vecto
r
s will
be
col
u
mn vecto
r
s u
n
less tran
spo
s
ed to
a
row ve
ctor. The scalar (i
nn
er) p
r
odu
ct of two vectors
x
and
y
in the n-dimen
s
ion
a
l real spa
c
e
n
R
will be denot
ed by
,
x
y
. The notation
mn
A
R
will si
gnify a real
mn
matrix. For suc
h
a
matrix
T
A
will denote the transpose of
A
. For
nn
A
R
the 2-no
rm will be denote
d
by ||
A
||.
2. Rese
arch
Metho
d
2.1. Prelimin
aries
Firs
tly, we give s
o
me lemmas
of AVE, w
h
ic
h
indic
a
ted that the s
o
lution to AVE is
unique.
The followi
ng result
s by M
angasarian and Meyer [4] charac
teri
ze
solvability of AVE.
Lemma 2.1
For a matrix
nn
A
R
, the followi
ng condition
s are equivalent.
(i) The
sing
ul
ar value
s
of
A
excee
d
1.
(ii)
1
1
A
.
Lemma 2.2
(Mangasarian,
AVE with unique solution).
(i) The AVE (1) is uni
quely
solvable for
any
n
bR
if singula
r
values of
A
exceed 1.
(ii) The AVE (1) is uni
quely
solvable for
any
n
bR
if
1
1
A
.
Define
1
()
:
n
f
xR
R
by
1
2
()
xx
fx
A
xb
A
x
b
，
.
(2)
It is
c
l
ear that
*
x
is a solution
of the AVE (1) if and only if
*
ar
g
m
i
n
()
x
fx
.
Sinc
e
()
f
x
is a nondifferen
t
iable functi
on,
mi
n
()
f
x
is
a
nondifferentia
ble
optimizatio
n
problem. Followi
ng we pre
s
ent
an improve
d
HS algorithm for so
lving
nondifferentia
ble optimization pro
b
lem (2).
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
Im
proved
Harm
ony Search
Algorithm
with Cha
o
s for A
b
sol
u
te Value
Equation (L
o
ngqu
an Yong
)
837
2.2. Classica
l Harmon
y
Search
Algori
t
hm
Since h
a
rm
o
n
y sea
r
ch (HS) wa
s prop
ose
d
by Gee
m
ZW et al.[16], it has d
e
velope
d
rapidly an
d h
a
s sho
w
n si
g
n
ificant pote
n
t
ial in solving
variou
s dif
f
icu
l
t problem
s [1
7].
Similar to the GA and part
i
cle swa
r
m al
gorit
hm
s [18-19], the HS method is a
rand
om
sea
r
ch te
chn
i
que. It doe
s not re
quire
any pri
o
r
d
o
main
kno
w
l
edge,
su
ch
as the
gradi
ent
informatio
n o
f
the objecti
ve function
s. Unfort
un
atel
y, empirical
study
ha
s shown that the
cla
ssi
cal HS method som
e
times suffe
rs from a
slow sea
r
ch sp
eed, and it is not suitabl
e for
handli
ng the
multi-mod
a
l p
r
oble
m
s [17].
More late
st HS algorithm can be found in
Osama et al.[20], Swagatam et al. [2
1], and
Mohamm
ed e
t
al.[22].
The ste
p
s in t
he pro
c
e
d
u
r
e
of classical h
a
rmo
n
y sea
r
ch algorith
m
are as follo
ws:
Step 1
. Initialize the p
r
oble
m
and algo
rit
h
m paramete
r
s.
Step 2
. Initialize the harmony memory.
Step 3
. Impro
v
ise a ne
w ha
rmony.
Step 4
. Up
da
te the harmo
ny memory.
Step 5
. Ch
eck the stop
pin
g
crite
r
ion.
These step
s
are de
scri
bed
in the next five sub
s
e
c
tion
s.
Initializ
e the
problem and algorithm parameters
In Step 1, the optimization
probl
em is
sp
ecified a
s
foll
ows:
Minimize
()
f
x
s
u
bjec
t to
,
1
,
2
,
,
ii
x
Xi
N
,
whe
r
e
()
f
x
is an
objective fu
nction;
x
is the set of ea
ch deci
s
io
n variabl
e
i
x
;
N
is
the
numbe
r of deci
s
ion varia
b
les,
i
X
is
the set of the p
o
ssible
ra
nge
o
f
values fo
r
each de
ci
sio
n
variable,
:
L
U
ii
i
i
X
xX
x
. The HS algo
rithm paramet
ers a
r
e al
so
spe
c
ified in
this step.
These are th
e harm
ony m
e
mory
size
(HMS), o
r
the
numbe
r of solution vecto
r
s in the h
a
rm
ony
memory; h
a
rmony mem
o
ry co
nsi
deri
n
g rate
(H
MCR); pit
c
h a
d
j
u
sting
rate
(PAR); an
d t
h
e
numbe
r of improvisation
s
(Tmax), or sto
pping
crite
r
io
n.
The h
a
rm
ony
memo
ry (HM
)
is
a me
mory location
wh
ere
all the
sol
u
tion vecto
r
s
(set
s of
deci
s
io
n variable
s
) are st
ored. Thi
s
HM is si
milar t
o
the genetic pool in the GA. Here, HMCR
and PAR a
r
e
param
eters
that are u
s
e
d
to improve
the solution
vector. Both are define
d
in
step 3.
Initializ
e the
harmon
y
me
mor
y
In Step 2, the HM m
a
trix is filled
with a
s
many
ran
d
o
mly gene
rat
ed solution v
e
ctors a
s
the HMS
11
1
11
1
12
22
2
22
2
12
12
()
()
()
()
HM
()
()
HM
S
H
M
S
H
M
S
HM
S
H
M
S
H
M
S
N
N
N
xx
x
xf
x
f
x
xx
x
xf
x
f
x
xx
x
xf
x
f
x
.
Impro
v
ise a
ne
w
harmon
y
A new ha
rm
ony vector,
''
'
'
12
(,
,
,
)
N
x
xx
x
, is gen
erate
d
based o
n
three rule
s:
memory con
s
ideratio
n, pitch adjustm
ent
and ran
dom
sele
ction. Generating a n
e
w ha
rmony
is
calle
d ‘improvisation’. In th
e memo
ry co
nsid
erat
io
n, the value
of the first de
ci
sio
n
variabl
e
'
1
x
for
the new ve
ct
or is
cho
s
e
n
from any of th
e val
ues in th
e spe
c
ified
HM. The HM
CR, whi
c
h vari
es
betwe
en 0 a
n
d
1, is the
rat
e
of cho
o
si
ng
one val
ue f
r
om the hi
stori
c
al value
s
stored i
n
the HM,
while (1-
HM
CR) is the rate of rando
mly sele
ct
ing on
e value from the po
ssi
ble range of value
s
.
'1
2
'
'
i
f
rand<HMCR
,
othe
r
w
i
s
e
,
(,
,
,
)
,
,
HM
S
ii
i
i
i
ii
xx
x
x
x
xX
Whe
r
e ra
nd is a rando
m numbe
r betwe
en 0 and 1. F
o
r example, a HMCR of 0.85 indicate
s that
the HS algori
thm will choo
se the deci
si
on variabl
e value from hi
storically
stored values in t
he
HM with an 85% proba
bil
i
ty or
from the entir
e possible rang
e with a (100–85
)% proba
bility.
Every compo
nent obtaine
d by the memory co
nsi
d
e
r
ation is exa
m
ined to det
ermin
e
wheth
e
r it
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 11, No. 4, Decem
ber 20
13 : 835 – 844
838
sho
u
ld be pit
c
h-adju
s
ted.
This op
eratio
n use
s
the PAR para
m
ete
r
, which is the rate of pitch
adju
s
tment a
s
follows:
Pitch adju
s
tin
g
deci
s
io
n for
'
i
x
'
'
'
r
a
nd
i
f
r
a
nd<PA
R,
othe
r
w
i
s
e,
,
,
i
i
i
bw
x
x
x
Whe
r
e
bw
is
an arbit
r
ary di
stan
ce ba
nd
width; ran
d
is a rando
m nu
mber b
e
twe
e
n
0 and 1.
In Step 3, HM con
s
id
erati
on, pitch a
d
j
u
stm
ent o
r
random
sel
e
ct
ion is a
pplied
to each
variable of th
e new h
a
rm
o
n
y vector in turn.
Upda
te ha
rmon
y
memor
y
If the new ha
rmony ve
ctor,
''
'
'
12
(,
,
,
)
N
x
xx
x
is
better than the wors
t harmony in the
HM, judg
ed i
n
term
s of the obje
c
tive function valu
e, the new
harm
ony is in
clud
e
d
in the HM a
nd
the existing worst ha
rmo
n
y is exclu
ded from the HM.
Chec
k sto
p
p
i
ng criterion
If the stoppin
g
crite
r
ion (m
aximum num
ber of im
provisation
s
) i
s
sat
i
sfied, com
p
u
t
ation is
terminate
d
. Otherwi
se, Ste
p
s 3 an
d 4 are repe
ated.
2.3. Impro
v
e
d
HS Algorithm With Chaos
Experiment
s with the standard HS algo
rithm
over the bench
m
ark problem
s sh
ow that
the algorith
m
suffers from the pro
b
lem of
pre
m
ature a
nd/
or false
co
nverge
nce, slo
w
conve
r
ge
nce esp
e
ci
ally over mu
ltimod
al
fitness lan
d
scap
e.
To enri
c
h the
searchin
g be
havior and to avoi
d being trappe
d into local optimum, cha
o
tic
dynamics i
s
i
n
co
rpo
r
ate
d
into the ab
ove HS alg
o
rith
m. The well-known logi
stic
equatio
n (Li
u
et
al., 2005), which exhibit
s
the sen
s
itive depe
nden
ce on initial con
d
ition
s
, is employed for
con
s
tru
c
ting
hybrid HS. Th
e logisti
c
equ
ation is defin
ed as follo
ws.
10
(1
)
,
(
0
,
1
)
nn
n
xx
x
x
,
whe
r
e
is the control pa
ra
meter,
x
is a variable an
d
0,
1
,
2,
n
. Although th
e above
equatio
n is determini
stic, it ex
hibits cha
o
tic dynamics whe
n
4
and
0
{
0
.25
,
0.5
,
0.75
}
x
.
That is, it
exhibits the
sen
s
itive d
epen
den
ce
on initial
co
ndition
s, whi
c
h i
s
the b
a
si
c
cha
r
a
c
teri
stic of chao
s. A minute diffe
ren
c
e in
the
initial value
of the chaotic variable would
result in a consid
era
b
le differen
c
e in its long
time behavior. The track of chaoti
c
variable ca
n
travel ergodi
cally over th
e w
hol
e search
spa
c
e. In
gene
ral, the
above chao
tic variabl
e h
a
s
spe
c
ial
cha
r
a
c
ters, i.e. erg
odicity
, pse
u
d
o
-rand
omne
ss and irre
gula
r
ity.
The process
of the chaoti
c
local search
coul
d be defi
ned thro
ugh t
he followi
ng e
quation:
(1
)
(
)
(
)
4(
1
)
,
1
,
2
,
,
.
kk
k
ii
i
cx
cx
cx
i
n
whe
r
e
i
cx
is
the
i
th chaotic variabl
e, and
k
denote
s
th
e iteration nu
mber. Obvio
u
sly,
()
k
i
cx
is
distrib
u
ted in
the rang
e (0,
1
) und
er the
con
d
ition
s
that
(0)
(
0
,
1
)
\
{
0
.
2
5
,
0.5
,
0.75
}
i
cx
.
Based
on th
e pro
p
o
s
ed
HS algo
rithm
with the
cha
o
tic lo
cal
sea
r
ch,
a hybri
d
HS with
cha
o
s
strate
g
y
named HS
CH i
s
propo
sed, in whi
c
h
HS is ap
plied
to perform gl
obal explo
r
ati
o
n
and
cha
o
tic l
o
cal
se
arch i
s
empl
oyed t
o
perfo
rm lo
cally ori
ented
sea
r
ch (expl
o
itation) fo
r the
solutio
n
s resulted by the HS [23]. The pro
c
ed
ure of HSCH is de
scrib
ed in Fig
u
r
e 1.
The h
a
rm
ony
of wo
rst fitn
ess in th
e HM nee
ds to
be imp
r
oved.
We
add
ch
a
o
tic lo
cal
sea
r
ch to pit
c
h adju
s
ting
of HS alg
o
rithm
.
Beside
s, to
maintain p
o
p
u
lation dive
rsi
t
y, several n
e
w
harm
ony are
generated b
y
chaos with
certain
prob
ability (RG
R
) and inco
rpo
r
ated in the new
HM. Thu
s
, the re
sulting
HM memb
ers are exp
e
ct
ed to have better fitness than that of the
origin
al on
es.
This
strateg
y
can
also
o
v
erco
me
the
prem
ature
sh
ortco
m
ing
of
the re
gula
r
HS
method. Figu
re 2 sh
ows th
e comp
utat
io
n pro
c
ed
ure of the HSCH
Algorithm.
Rem
a
r
k
1.
RGR i
s
a pa
ra
meter in th
e range
(0.1,0.3
), whi
c
h
cont
rol the ne
w ha
rmony’
s
gene
ration. Compa
r
ed
with
the standa
rd
HS algo
rithm, the time com
p
lexity is also
O
(n*Tmax
)
.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
Im
proved
Harm
ony Search
Algorithm
with Cha
o
s for A
b
sol
u
te Value
Equation (L
o
ngqu
an Yong
)
839
Figure 1. Pse
udo Code of the HSCH Alg
o
rithm
Figure 2. The
fl
owch
art of the HSCH Alg
o
rithm.
Procedure HSC
H
algo
rithm
Initia
te_p
aram
et
ers()
Initia
li
ze_HM()
(1
,
)
cx
r
a
n
d
n
,
/
/
n
deno
tes th
e
number of var
i
ables
While
(no
t
_term
i
nation)
new
H
M
(
i
dw
or
s
t
,
:
)
x
,
For
i
= 1
to
n
do
If
( rand
< HMCR)
//memor
y
consider
ation
S
e
l
e
ct on
e h
a
rm
on
y f
r
om
H
M
random
l
y
:
new
U
{
1,
2,
,
H
M
S
}
,
j
xx
j
;
Elseif
(
rand<
PAR)
ne
w
n
e
w
,
4(
1
)
,
2(
0
.
5
)
ii
i
ii
i
bw
cx
c
x
cx
xx
c
x
Elseif
( r
a
nd < RGR)
ne
w
4(
1
)
,
()
,
ii
i
LU
L
ii
i
i
i
c
x
cx
cx
x
xc
x
x
x
End
End for
Upda
t
e
ha
rmony
me
mory
HM
//
if a
p
pl
ic
a
b
le
End w
h
ile
End pr
oc
e
dur
e
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 11, No. 4, Decem
ber 20
13 : 835 – 844
840
3. Computati
onal Res
u
lts
and Analy
s
is
In this section we perform
some
numeri
c
al te
sts in order to illustra
t
e
the implem
entation
and efficien
cy of
the prop
ose
d
method
. All t
he exp
e
rime
nts we
re performed
on Wind
ows XP
system run
n
i
ng
on a
Hp
5
40 lapto
p
wit
h
Intel(R)
Co
re(TM) 2
×
1.8
G
Hz
and
2G
B RAM, and
the
cod
e
s
were written in Matla
b
R2
010
b.
3.1. AVE Problems
AVE 1.
Let
A
be a matrix whose dia
gonal elem
e
n
ts are 50
0 and the non
diago
nal
element
s are cho
s
en ra
ndomly from
the interval
[1
,
2
]
such
t
hat
A
is symmetric. Let
()
bI
e
A
where
I
is the
identity matrix of order
n
and
e
is
1
n
vector
who
s
e
ele
m
e
n
ts
are all equ
al to unity. Since singula
r
valu
es matrix
A
are all greater than 1, this AVE is uniquely
solvabl
e by Lemma 2.2, an
d the uniqu
e solutio
n
is
(1
,
1
,
,
1
)
T
x
.
AVE 2.
Let the matrix
A
is
given by
,1
1
,
4,
,
0
,
1
,
2
,
,
.
ii
i
i
i
i
i
j
a
n
aan
a
i
n
Let
e
I
A
b
)
(
where
I
is the identity
matrix orde
r
n
and
e
is
1
n
vector who
s
e ele
m
ent
s
are all equ
al to unity. Since singula
r
valu
es matrix
A
are all greater than 1, this AVE is uniquely
solvabl
e by Lemma 2.2, an
d the uniqu
e solutio
n
is
(1
,
1
,
,
1
)
T
x
.
Here the data
(
A
,
b
) can b
e
generated by
following Mat
l
ab script
s:
Figure 3. Generatin
g data
(
A
, b) of AVE1 and AVE2 by the Matlab scripts
In AVE1, we s
e
t the random-num
ber generator to the s
t
ate of 0
s
o
that the s
a
me data
c
a
n
be
r
e
ge
ne
r
a
te
d
.
AVE 3.
Foll
owing we cons
ider some
randomly
generated AVE problem wit
h
s
i
ngular
values of
A
exceedin
g
1 wh
e
r
e the data (
A
, b
) are ge
nerated by the Matlab script
s:
rand('state',0);
A=rand(n,n)'*rand(n,n)+n*eye(n);
b=(A-eye(n,n))*ones(n,1);
Since sin
gula
r
values matrix
A
are all g
r
eate
r
than 1, this AVE is
uniqu
ely solvable by
Lemma 2.2, a
nd the uniq
u
e
solution i
s
(1
,
1
,
,
1
)
T
x
.
3.2. Parameters Setting
Simulations were carried out
to compare the optimi
z
ation (mi
n
imi
z
ation)
capabilities of
the prop
ose
d
method (HS
C
H) with re
spect to: (a)
classical HS (HS,[16]), (b)
HSDE [24]. To
make the co
mpari
s
o
n
fair, the populations for a
ll the competito
r
algorith
m
s (f
or all probl
e
m
s
tested) we
re initialized usi
ng
the
sa
me
rando
m
se
e
d
s. The
HS-v
ariant
s algo
rit
h
m paramete
r
s
n=input('Dim. of matrix A=')
rand('state',0);
A1=zeros(n,n);
for i=1:n
for j=1:n
if i==j
A1(i,j)=500;
elseif i>j
A1(i,j)=1+rand;
else
A1(i,j)=0;
end
end
end
A=A1+(tril(A1,-1))';
b=(A-eye(n))*ones(n,1)
n=input('Dim. of matrix A=')
A1=zeros(n,n);
for i=1:n
for j=1:n
if (j==i)
A1(i,j)=4*n;
else (j~=i)
A1(i,i+1)=n;
A1(j+1,j)=n;
end
end
end
A=A1(1:n,1:n);
b=(A-eye(n,n))*ones(n,1);
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
Im
proved
Harm
ony Search
Algorithm
with Cha
o
s for A
b
sol
u
te Value
Equation (L
o
ngqu
an Yong
)
841
w
e
re
s
e
t the
s
a
me
par
a
m
e
t
er
s
:
ha
r
m
on
y memo
r
y
s
i
z
e
H
M
S=1
5
,
ha
r
m
on
y memo
r
y
con
s
id
eratio
n
rate HM
CR= 0.6, and the numbe
r of
im
provisation
s
Tmax=1
000
0
.
In HSCH, RGR
is cho
s
en
to
be 0.2. In
cla
ssi
cal
HS, we
set pit
c
h a
d
j
u
sting
rate P
A
R=
0.35. Le
t the initial po
int
0
x
sele
cted ra
n
domly in the given interval
[-1,1].
3.3. Results
To judge the
accura
cy of different algo
rithms,
30
ind
epen
dent ru
n
s
of each of the three
algorith
m
s
were
ca
rri
ed o
u
t and th
e be
st, the me
an,
the worst fitness value
s
, a
nd the
stan
d
a
rd
deviation (Std) we
re re
corded. Table 1 and Tabl
e 2 comp
ares th
e algorithm
s on the quality o
f
the optimum
solution for every AVE problem of n=50 and n=100.
Table 1. The
Statis
tic
a
l Res
u
lts
for 30 R
uns
on Three given AVE P
r
oblems
of n=50
Func
tio
n
A
l
g
o
ri
th
m
Best
Mean
W
o
rst
Std
Meanti
me(s
)
AVE
1
HS
1.9212e+006
2.4428e+006
2.7472e+006
2.1384e+005
3.3491e+000
HSDE
2.4191e+006
2.8184e+006
3.3670e+006
2.4710e+005
8.6240e+000
HSCH
8.6124e+002
2.4157e+003
5.8259e+003
9.8149e+002
3.2177e+000
AVE
2
HS
5.0163e+005
5.8305e+005
6.9679e+005
5.0863e+004
2.2462e+000
HSDE
5.2221e+005
6.3777e+005
7.1661e+005
5.1238e+004
7.5728e+000
HSCH
1.0527e+002
4.5098e+002
9.3967e+002
1.8878e+002
2.2710e+000
AVE
3
HS
1.4234e+006
1.8979e+006
2.3000e+006
2.0344e+005
3.0794e+000
HSDE
1.6272e+006
2.0878e+006
2.6212e+006
2.4014e+005
9.5309e+000
HSCH
1.3668e+002
8.7209e+002
1.7458e+003
4.2185e+002
3.0651e+000
Table 2. The
Statis
tic
a
l Res
u
lts
for 30 R
uns
on Three given AVE P
r
oblems
of n=100
Func
tio
n
A
l
g
o
ri
th
m
Best
Mean
W
o
rst
Std
Meanti
me(s
)
AVE
1
HS
8.7139e+006
9.8264e+006
1.1049e+007
5.6466e+005
8.3361e+000
HSDE
9.4194e+006
1.0785e+007
1.1997e+007
6.5037e+005
2.3022e+001
HSCH
1.8661e+005
2.5579e+005
3.9843e+005
4.9279e+004
8.4083e+000
AVE
2
HS
7.1403e+006
8.0176e+006
8.6583e+006
3.9421e+005
6.8993e+000
HSDE
7.7324e+006
8.6878e+006
9.5392e+006
4.8861e+005
2.1845e+001
HSCH
1.3697e+005
2.0031e+005
2.6792e+005
3.5899e+004
6.5297e+000
AVE
3
HS
9.4440e+007
1.0742e+008
1.1928e+008
5.5482e+006
1.1561e+001
HSDE
9.6570e+007
1.1399e+008
1.2838e+008
7.6645e+006
2.3033e+001
HSCH
5.6216e+005
9.9070e+005
1.4030e+006
2.2014e+005
1.1020e+001
Figure 4 an
d
Figure 5 sho
w
the
conve
r
gen
ce an
d its boxplot of the be
st fitness in the
popul
ation for the different
algorith
m
s (HSCH,
HS, HSDE) for every AVE probl
em of n=50 a
nd
n=1
00. The value
s
plotted for every ge
neratio
n are averag
ed over
30
indep
e
ndent run
s
. The
boxplot is the
best fitness i
n
the final po
pulati
on fo
r the differe
nt algorithm
s (HS
CH, HS,
HSDE)
for c
o
rres
ponding AVE problem.
3.4. Analy
s
is
We
can
se
e
that in all instan
ce
s the
HSCH alg
o
rithm perfo
rm
s extrem
ely well, and
finally converges to the un
ique sol
u
tion of t
he AVE.The behavio
r of the two former algo
rith
ms
(HS and
HS
DE) is si
milar for all given AVE problem
s. From the computati
on result
s, the HSDE
algorithm is
clearly the wors
t algorithm for a
ll given AVE problems
,
while
the HS
CH algorithm is
the best.
4. Conclusio
n
We have pro
posed HSCH algorithm fo
r solving ab
solute value equation
Ax
-|
x
| =
b
unde
r the co
ndition that the sin
gula
r
values of
A
e
x
c
e
ed
1
.
T
h
e H
M
me
mber
s
in
H
S
CH
algorith
m
are
fine-tune
d b
y
the
chao
s
operator to i
m
prove th
eir affinities so
that enhan
ced
optimizatio
n perfo
rman
ce
s can be a
c
hie
v
ed. This en
sure
s that the explorat
ive p
o
we
r of HSCH is
on averag
e greate
r
than that of HS
and
HSDE, whi
c
h
in turn result
s into better accuracy of the
HSCH alg
o
rit
h
m. Several
simulatio
n
ex
ample
s
have
been used
to verify
t
he effectivene
ss
of the
prop
osed m
e
thods.
Com
p
ared
with th
e
HS an
d HS
DE, better o
p
timization
re
sults a
r
e o
b
tai
n
e
d
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 11, No. 4, Decem
ber 20
13 : 835 – 844
842
by using HS
CH
approaches.
Future
works
will also focus on
studying the appli
c
ations of
HSCH
on engi
nee
rin
g
optimizatio
n probl
em
s.
Figure 4. The convergence and box
plot
of the best fitness fo
r given AVE problems of n=50
0
10
00
2
000
30
00
4
000
500
0
60
00
7
000
80
00
9
000
1
000
0
10
3
10
4
10
5
10
6
10
7
It
e
r
a
t
i
o
n
A
v
erage be
s
t
F
i
t
nes
s
AV
E
1
F
u
nc
t
i
on
HS
HS
D
E
HS
C
H
0
0.
5
1
1.
5
2
2.
5
3
3.
5
x 1
0
6
HS
H
S
DE
HS
C
H
B
e
s
t
F
i
t
nes
s
AV
E
1
F
u
nc
t
i
on
0
1000
2000
3000
4000
5000
6000
7000
8000
9000
1
0000
10
2
10
3
10
4
10
5
10
6
10
7
I
t
er
at
i
o
n
A
v
e
r
age bes
t
F
i
t
n
e
s
s
AVE
2
F
u
nc
t
i
on
HS
HS
D
E
HS
C
H
0
1
2
3
4
5
6
7
x 1
0
5
HS
HS
D
E
HS
CH
Be
s
t
F
i
tn
e
s
s
AVE
2
Fu
n
c
t
i
o
n
0
1000
2000
3000
4000
5000
6000
7000
8000
9000
1
0000
10
2
10
3
10
4
10
5
10
6
10
7
I
t
er
at
i
o
n
A
v
e
r
age bes
t
F
i
t
n
e
s
s
AVE
3
F
u
nc
t
i
on
HS
HS
DE
HS
CH
0
0.
5
1
1.
5
2
2.
5
x 1
0
6
HS
HS
D
E
HS
CH
Be
s
t
F
i
tn
e
s
s
AVE
3
Fu
n
c
t
i
o
n
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
Im
proved
Harm
ony Search
Algorithm
with Cha
o
s for A
b
sol
u
te Value
Equation (L
o
ngqu
an Yong
)
843
Figure 5. The convergence and box
plot
of the best fitness fo
r given AVE problems of n=100
Ackn
o
w
l
e
dg
ments
This
wo
rk is
sup
porte
d by
Nation
al
Nat
u
ral S
c
ien
c
e
Found
ation
o
f
China
un
de
r G
r
ant
No.60
974
082
, Scientific
Re
sea
r
ch Prog
ra
m Fun
ded by Shaanxi Provincial Education
Dep
a
rtme
nt unde
r Gra
n
t No. 12JK
086
3, 11JK1
0
66,
and Innovation Foun
datio
n of Graduat
e
Student by Xidian University under G
r
ant
No. K50513
1
0000
4.
0
10
00
20
00
3
000
4
000
5000
6000
7
000
8000
9000
1000
0
10
5
10
6
10
7
10
8
It
e
r
a
t
i
o
n
A
v
er
age be
s
t
F
i
t
n
e
s
s
AV
E
1
Fu
n
c
t
i
o
n
HS
HS
D
E
HS
C
H
0
2
4
6
8
10
12
x 1
0
6
HS
HS
DE
HS
C
H
B
e
s
t
F
i
tn
e
s
s
AV
E
1
F
unc
t
i
on
0
1000
2000
3000
4000
5000
6000
7000
8000
9000
1
0000
10
5
10
6
10
7
10
8
I
t
er
at
i
o
n
A
v
erage be
s
t
F
i
t
nes
s
AVE
2
F
u
nc
t
i
on
HS
HS
DE
HS
CH
0
1
2
3
4
5
6
7
8
9
10
x 1
0
6
HS
HS
DE
HS
C
H
B
e
s
t
F
i
t
nes
s
AVE
2
F
unc
t
i
o
n
0
1000
2
000
3000
4000
5000
6000
7000
8000
9000
10000
10
6
10
7
10
8
10
9
I
t
er
at
i
o
n
A
v
e
r
age bes
t
F
i
t
n
e
s
s
AV
E
3
F
u
nc
t
i
on
HS
HS
D
E
HS
C
H
0
2
4
6
8
10
12
x 1
0
7
HS
HS
D
E
HS
CH
B
e
s
t
F
i
tn
e
s
s
AVE
3
Fu
n
c
t
i
o
n
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 11, No. 4, Decem
ber 20
13 : 835 – 844
844
Referen
ces
[1]
Jiri Rohn. A Theo
rem of the Alter
nativ
es for the Eq
uation Ax+B|x|=b.
Linea
r and Multiline
a
r
Algebra
, 200
4,52 (6
):421
-426.
[2]
Manga
sa
rian
O.L. Absolute value
prog
rammi
ng.
Com
putational Opti
m
i
zation an
d
Aplications
, 2
007, 36(1): 4
3
-53.
[3]
R.
W. Cottle and
G. Dant
zig.
Comple
mentary
pivo
t theory of m
a
thematical p
r
og
rammi
ng.
Linea
r Algeb
ra and its Appl
ication
s
. 196
8,1:103-125.
[4]
Manga
sa
rian
O.L., Meyer, R.R. Ab
solute value
equation
s
.
Linear Alg
ebra a
nd its
Applicatio
ns
,
2006, 41
9(5
)
:
359-3
67.
[5]
Oleg Pro
k
opy
ev. On equivalent reformu
l
ations for ab
solute value
equatio
ns.
Com
putational
Optim
i
zation and Appli
c
ati
ons
, 20
09, 44
(3): 36
3-3
72.
[6]
Shen-Lon
g Hu, Zheng
-Hai
Hua
ng. A n
o
te on ab
sol
u
te value eq
uation
s
.
Opti
m
.
Lett
.2010,
4(3
)
: 417-424
.
[7]
Manga
sa
rian
O.L. Absol
u
te value e
qua
tion sol
u
tion
via con
c
ave
minimization.
Optim
.
Lett
.
2007, 1(1): 3-8.
[8]
Manga
sa
rian
O.L. A gene
rl
aize
d ne
wton
method fo
r a
b
sol
u
te value
equatio
ns.
O
p
tim
.
Lett
.
2009, 3(1): 1
01-1
08.
[9]
Manga
sa
rian,
O.L. Knap
sa
ck fe
asi
b
ility as
an a
b
sol
u
te valu
e equatio
n
solvabl
e by
su
ccessive li
near p
r
o
g
ra
m
m
ing.
Optim
.
Lett
. 2009, 3(2):161
-1
70.
[10]
C. Zhan
g,Q. J. Wei. Glo
b
a
l and Finite
C
onve
r
ge
nce
of a General
ized
Ne
wton
Method for
Absolute Val
ue Equation
s
.
Jou
r
nal of O
p
tim
i
zation Theory an
d Ap
plicatio
ns
. 20
09(1
4
3
)
:391
-
403.
[11]
Loui
s Caccett
a
, Biao Qu, G
uangl
u Zho
u
. A globally an
d qua
drati
c
all
y
convergent
method fo
r
absolute valu
e equatio
ns.
Com
putation
a
l Optim
i
zation and Appli
c
a
t
ions
. 201
1, 48(1
)
: 45-5
8
.
[12]
Long
quan Y
ong, Sanyan
g Liu, Shemin Z
hang an
d Fang'a
n Deng. A New Method for
Absolute Val
ue Equation
s
Based on
Harmo
n
y Search Algo
rithm.
ICIC Ex
press
Letters
, Part
B: Applications
, 2011,2
(
6
)
:1231
-12
36.
[13]
Long
quan
Yo
ng, Shou
hen
g Tuo.
Qua
s
i-Ne
wton M
e
th
od to Ab
solut
e
Value E
qua
tions b
a
sed
on Aggreg
ate Functi
on.
Jou
r
na
l of System
s Scien
c
e an
d Mathem
atical
Sc
ie
nc
es
,201
2,32(1
1
):1
4
2
7
-14
36.
[14]
Long
quan Y
ong, Sanyan
g Liu,Zha
ng
Jian
-ke,Ch
en
Tao,De
ng F
ang-an. A New Fe
asi
b
le
Interior Poi
n
t Method to
Absolute Val
ue Equatio
n
s
.
Journal of
Jilin Un
iversi
ty (Sci
ence
Edition)
, 201
2, 50 (5):8
87-891.
[15]
Long
quan Yo
ng. An Iterative Method fo
r Absol
u
te Value Equatio
ns Pro
b
lem.
Information
,
2013,1
6
(1
):7-12.
[16]
Geem Z W,
Kim J H, Lo
ganath
an G V. A new
heuristi
c optimization algo
rit
h
m: harmony
sea
r
c
h
.
Simul
a
tion
, 2001,7
6
: 60-68.
[17]
Lee K S,
Geem Z
W.
A new m
e
ta-heu
ri
stic
algorith
m
for contin
uou
s engin
eeri
ng
optimizatio
n: harm
ony se
ar
ch theo
ry and
pra
c
tice.
Co
m
puter Meth
ods in A
pplie
d Mechani
cs
and Engin
e
e
r
ing
, 2005,1
9
4
:
3902-3
933.
[18]
Lakshmi
Ravi, S.G. Bharathi dasa
n
.PSO base
d
Opti
mal Powe
r Flow with Hy
b
r
i
d
Distri
buted
Gene
rato
rs a
nd UPF
C
.
Tel
k
om
nika
,2
01
2,10(3
)
.
[19]
Andi Muham
mad Ilyas, M. Natsir
Rah
m
an. Econ
o
m
ic Di
spat
ch
Therm
a
l Ge
nerato
r
Usin
g
Modified Improved Particl
e
Swarm
Optim
i
zation.
Tel
k
o
m
nika
,2012,1
0
(3
): 459-470
.
[20]
Osa
m
a Alia, Rajeswa
r
i Mandava.T
h
e
variant
s of the harmony search a
l
gorithm: an
overview.
Arti
ficial Intelligence
Review
, 2011,3
6
: 49-68.
[21]
Swagata
m
Das, Arp
an M
u
kh
opa
dhyay
, Anwit Roy,
Ajith Abrah
a
m, Bijaya K. Panigra
h
i.
Exploratory P
o
we
r of the Harmo
n
y Search Algo
rithm: Analysis
and
Improveme
n
ts for Gl
oba
l
Numeri
cal Optimization.
IEEE Transactions On System
s, M
an,
and Cybernetics, Part B:
Cybernetics
, 2011,4
1
:89-1
06.
[22]
Mohamm
ed
Azmi Al-Beta
r
, Iyad Abu Dou
s
h, Aha
m
ad Taju
din
Khader, Mo
hamme
d A.
Awadall
ah. Novel sele
ction schem
es for harm
o
n
y
search.
Ap
p
lie
d
Ma
the
m
a
t
ic
s
and
Com
putation
,
2012, 218:6
0
95-6
117.
[23]
Shouhe
ng Tu
o, Longqu
an Yong. Improv
ed Harm
ony Search Algori
t
hm with Cha
o
s.
Journal
of Com
putational Inform
ation Syst
em
s
,2012,8 (1
0) : 4
269- 4
276.
[24]
Prithwi
s
h Ch
akrabo
rty,Go
urab
Gh
osh Roy,
Swa
gat
am Das,
Dha
v
al Jain, Ajith
Abrah
a
m. A
n
Improved Harmo
n
y Search Algo
rith
m with Differential Mut
a
tion Ope
r
at
or.
Jou
r
nal
Fundam
enta Inform
aticae
, 2009, 95
(4
):4
01-4
26.
Evaluation Warning : The document was created with Spire.PDF for Python.