Inter
national
J
our
nal
of
Electrical
and
Computer
Engineering
(IJECE)
V
ol.
7,
No.
6,
December
2017,
pp.
3583
–
3592
ISSN:
2088-8708
3583
I
ns
t
it
u
t
e
o
f
A
d
v
a
nce
d
Eng
ine
e
r
i
ng
a
nd
S
cie
nce
w
w
w
.
i
a
e
s
j
o
u
r
n
a
l
.
c
o
m
CHN
and
Swap
Heuristic
to
Solv
e
the
Maximum
Independent
Set
Pr
oblem
Bouhouch
Adil
1
,
Loqman
Chakir
2
,
and
El
Qadi
Abderrahime
3
1
T
eam
TIM,
High
School
of
T
echnology
,
CEDoc-SF
A
f
aculty
of
sciences,
Moulay
Ismail
Uni
v
ersity
,
Meknes,
Morocco
2
department
of
informatics,
Sciences
F
aculty
,
Dhar
Mehraz,
Sidi
Mohammed
Ben
Abdellah
Uni
v
ersity
,Fez,
Morocco
3
LASTIMI,
High
School
of
T
echnology
-
Mohammed
V
Uni
v
ersity
of
Rabat,
Morocco
Article
Inf
o
Article
history:
Recei
v
ed:
Jan
9,
2017
Re
vised:
Jun
14,
2017
Accepted:
Jul
3,
2017
K
eyw
ord:
Max-Stable
problem
Independent
set
CHN
Local
search
Combinatory
problems
Graph
ABSTRA
CT
W
e
describe
a
ne
w
approach
to
solv
e
the
problem
to
find
the
maximum
independent
set
in
a
gi
v
en
Graph,
kno
wn
also
as
Max-Stable
set
problem
(MSSP).
In
this
paper
,
we
sho
w
ho
w
Max-Stable
problem
can
be
reformulated
into
a
linear
problem
under
quadratic
constraints,
and
then
we
resolv
e
the
QP
result
by
a
h
ybrid
approach
based
Continuous
Hopfeild
Neural
Netw
ork
(CHN)
and
Local
Search.
In
a
manner
that
the
solution
gi
v
en
by
the
CHN
will
be
the
starting
point
of
the
local
search.
The
ne
w
approach
sho
wed
a
good
performance
than
the
original
one
which
e
x
ecutes
a
suite
of
CHN
runs,
at
each
e
x
ecution
a
ne
w
leaner
constraint
is
added
into
the
resolv
ed
model.
T
o
pro
v
e
the
ef
ficienc
y
of
our
approach,
we
present
some
computational
e
xperiments
of
solving
random
generated
problem
and
typical
MSSP
instances
of
real
life
problem.
Copyright
c
2017
Institute
of
Advanced
Engineering
and
Science
.
All
rights
r
eserved.
Corresponding
A
uthor:
Name
Bouhouch
Adil
Af
filiation
T
eam
TIM,
High
School
of
T
echnology
Meknes
Address
High
School
of
T
echnology
Meknes
Moulay
Ismail
uni
v
ersity
Meknes
Morocco
Phone
+212664786422
Email
bouhouch.adil@gmail.com
1.
INTR
ODUCTION
The
Max-Stable
Set
Problem
(MSSP)
is
a
problem
that
attempts
to
find
the
lar
gest
independent
s
et
at
a
gi
v
en
graph.
All
the
nodes
included
in
the
i
ndependent
set
must
respect
the
condition
that
the
y
are
not
pairwise
connected
by
an
arc.
Max-table
is
lar
gely
applied
in
man
y
areas:
case-based
reasoning
[1],
com-
puter
vision
[2],
scheduling,
...
.
Max-Stableis
a
Strong
NP-Hard
problem
while
it’
s
hard
to
be
approximate.
Therefore,
solving
MSSP
in
polynomial
time
for
arbitrary
graph
case
is
unlik
ely
.
F
or
arbitrary
graph
there
are
man
y
e
xact
algorithm
which
enumerating
all
cliques
and
select
the
one
with
the
maximal
cardinality
.
T
o
our
kno
wledge
Harary
[3]
w
as
the
first
one
who
introduced
in
the
literature
an
e
xact
method.
Loukakis
[4]
generated
all
maximal
independent
sets
le
xicographically
introduced
by
a
depth-first
enumerati
v
e
algorithm.
Their
study
includes
a
comparison
ag
ainst
Re
gneri
[5]
and
Tsukiyama
[6]
algorithmes.
The
theoretical
superior
ef
ficienc
y
of
their
algorithm
is
also
reinforced
by
computational
results,
moreo
v
er
there
method
w
as
lar
gely
f
aster
than
that
proposed
by
Tsukiyama
[6]
and
that
introduced
by
Bron
[7].
After
tw
o
years,
Loukakis
[8]
imported
additional
change
to
their
pr
e
vious
w
ork
[4]
and
impro
v
e
it
by
three
speed-up.
In
the
years
1988s,
Johnson
[9]
introduced
an
e
xact
approach
which
determines
all
maximal
stable
sets
in
le
xicographic
order
.
The
approach
get
each
independent
set
by
times
comple
xity
of
order
O
(
n
3
)
.
Chiba
[10]
proposed
an
algorithm
to
the
maximal
cliques
on
the
order
O
(
a
(
G
)
m
)
of
times
comple
xity
-where
a(G)
is
the
arboricity
of
graph
G-
,
this
is
o
v
er
the
time
comple
xity
of
[6].
Based
on
the
Born
[7]
w
ork,
T
omita
[11]
proposed
an
impro
v
ed
v
ariant
ha
ving
comple
xity
equal
to
O
(3
n=
3
)
.
Intuiti
v
ely
,
it
seems
that
e
xacts
approaches
are
better
to
solv
e
Ma
x
-
stable
problem.
The
y
consist
to
enumerate
all
possible
independent
set
and
then
select
the
one
which
ha
v
e
the
maxi-
mum
of
cardinality
[12].
Ho
we
v
er
,
the
analysis
of
the
comple
xit
y
discouraged
this
idea
for
lar
ge
graph.
In
this
J
ournal
Homepage:
http://iaesjournal.com/online/inde
x.php/IJECE
I
ns
t
it
u
t
e
o
f
A
d
v
a
nce
d
Eng
ine
e
r
i
ng
a
nd
S
cie
nce
w
w
w
.
i
a
e
s
j
o
u
r
n
a
l
.
c
o
m
,
DOI:
10.11591/ijece.v7i6.pp3583-3592
Evaluation Warning : The document was created with Spire.PDF for Python.
3584
ISSN:
2088-8708
case
heuristic
methods
pro
v
ed
to
be
an
ef
ficient
alternati
v
e
a
w
ay
to
solv
e
lar
ge
problem
instances.
The
second
cate
gories
contains
Meta-heuristic
methods
which
e
xplore
the
search
space,
local
search
methods
and
h
ybrid
methods.
In
[13]
sho
w
ho
w
to
b
uild
a
good
h
ybrid
strate
gies.
Recently
,
man
y
approach
based
neural
netw
ork
w
as
de
v
eloped
to
solv
e
combinatorial
and
hard
optimisation
problem.
The
authors
of
[14]in
v
estig
ate
Continu-
ous
Hopfield
Neural
Netw
ork
(CHN)
to
solv
e
lar
gess
instances
of
Max-Stable
problems.
The
mean
idea
is
to
e
x
ecute
the
CHN
man
y
times.
The
role
of
first
run
is
to
find
a
v
alid
initial
solution
of
MSSP
by
CHN
and
a
quadratic
reformulation.
In
the
second
step
the
cardinality
of
the
solution
gi
v
en
by
first
run
is
added
as
linear
constraint
to
the
resolution
model,
then
the
y
run
CHN
ag
ain.
The
second
step
can
be
repeated
until
to
ha
v
e
no
solution
impro
v
ement.
In
this
paper
we
propose
ne
w
h
ybrid
approach,
in
order
to
tak
e
adv
antage
of
he
f
aster
con
v
er
gence
of
CHN
in
the
one
hand.
In
the
second
hand,
the
Local
Search
which
look
through
neighborhods
to
find
the
best
one.
T
o
solv
e
MSSP
by
LS,
There
are
man
y
successful
heuristic
[15,
16,
17,
18,
19,
20]
.
The
common
among
them
is
The
start
with
a
random
solution
and
impro
v
e
it
re
gularly
by
v
ery
simple
operations
lik
e
deletions
of
nodes
whi
ch
don’
t
meet
the
adjacent
condition
,
insertions
of
ne
w
nodes
or
sw
aps
(case
when
current
node
succeed
by
its
neighbors).
This
paper
is
structured
as
follo
ws:
In
section
2.
we
present
the
resolution
model
bested
CHN
which
is
di
vided
into
man
y
steps:we
introduce
the
continuous
Hopfeild
netw
ork,
ne
xt
we
gi
v
e
t
he
reformulation
of
maximum
stable
set
problem
as
a
0-1
quadratic
program,
then
we
b
uild
an
adapted
ener
gy
function
of
CHN.
Section
3.
is
de
v
oted
to
impro
v
e
the
solution
by
LS.
Experimental
results
are
presented
in
the
last
section.
2.
CONTINUOUS
HOPFEILD
NEURAL
NETW
ORK
T
O
SOL
VE
MSSP
In
this
section
we
present
an
o
v
ervie
w
of
[14]
approach
which
implement
CHN
to
solv
e
a
quadratic
model
of
MSSP
.
2.1.
The
continuous
Hopfield
neural
netw
ork
CHN
is
a
fully
connected
neural
Model
with
one
layer
.
It
w
as
Introduced
by
Hopfield
in
the
year
1980
to
solv
e
combinat
orial
problems.
Further
,
Hopfield
[21]
proposed
an
ener
gy
functions
to
solv
e
man
y
opti-
mization
probl
ems
as
linear
programming
problems,
analog
to
digital
con
v
ersion,
graph
coloring
problem,TSP
,
processing
image
and
.
The
e
v
olution
of
CHN
dynamic
is
controlled
by
The
follo
wing
dif
ferential
equation:
dy
dt
=
x
+
T
x
+
i
b
(1)
where
x
:
v
ector
of
neurons
input
y
:
v
ector
of
output
T
:
the
Matrix
of
weight
between
each
neurones
pairs
Neurons
output
is
go
v
erned
by
function:
x
i
=
g
(
y
i
)
=
1
2
(1
+
tanh(
y
i
u
0
))
w
ith
u
0
>
0
and
i
=
1
;
:::;
n
The
g
function
is
bounded
(
g
(
u
)
2
[0
;
1]
)
and
u
0
is
a
parameter
to
estimate
the
g
ain
(or
slope)
of
the
acti
v
ation
function.
The
limit
point
of
the
CHN
u
e
by
this
dif
fere
ntial
system
e
xists
such
that
u
(
t
)
=
u
e
8
t
t
e
(and
t
e
0
),
this
point
is
called
an
equilibrium
point
The
ener
gy
of
CHN
is
a
L
yapuno
v
function
defined
as:
E
(
x
)
=
1
2
x
t
T
x
(
i
b
)
t
x
+
n
X
i
=1
1
i
Z
x
i
0
g
1
(
v
)
dv
If
T
is
symmetric
then
the
equilibrium
points
e
xistence
is
guaranteed.
So,
an
y
combinatorial
problems
formu-
late
as
the
follo
wing
e
xpression
can
be
solv
ed
by
The
CHN:
E
(
x
)
=
1
2
x
t
T
x
(
i
b
)
t
x
(2)
IJECE
V
ol.
7,
No.
6,
December
2017:
3583
–
3592
Evaluation Warning : The document was created with Spire.PDF for Python.
IJECE
ISSN:
2088-8708
3585
The
matrix
T
is
called
also
matrix
of
weights
connections
and
just
inhibitory
connection
is
all
o
wed
on
this
symmetric
matrix.
E
(
x
)
e
v
aluate
at
the
h
ypercube
[0
;
1]
n
and
con
v
er
ge
to
the
corners
of
this
n-dimensional
space.
T
o
solv
e
a
combinatorial
problem
by
CHN
we
need
just
to
associate
the
ener
gy
function
of
CHN
with
the
objecti
v
e
function
of
problem
to
be
minimized,
so
that
the
minimum
of
E
(
x
)
coincide
with
the
combinatorial
problem
solution.
Implicitly
,
the
inputs
of
netw
ork
outputs
represent
the
problem
solution.
T
o
sho
w
ho
w
we
can
mapping
a
combinatorial
problem
to
be
associated
with
it
neural
model
we
tak
e
the
assignment
problem.
It
is
a
easier
and
direct
model
to
be
mapped.
So,
we
consider
the
follo
wing
model
of
assignment
problem
with
n
v
ariables
m
linear
constraint:
(
QP
)
8
>
>
<
>
>
:
M
in
1
2
x
t
Qx
+
q
t
x
S
ubj
ectto
Ax
=
b
x
i
2
f
0
;
1
g
i
=
1
;
:::::n
Furthermore,
we
he
need
to
define
the
follo
wing
set
to
solv
e
this
QP:
H
f
x
2
[0
;
1]
n
g
:
the
Hamming
h
ypercube
H
c
f
x
2
f
0
;
1
g
n
g
:
the
corners
of
the
Hamming
h
ypercube.
H
f
f
x
2
H
c
:
Ax
=
b
g
:
feasible
solution
set.
T
o
map
the
QP
bello
w
,
we
must
respect
some
conditions
so
that
local
minimums
of
the
QP
to
be
associated
with
the
CHN
limit.
The
ener
gy
can
also
be
defined
by
tw
o
terms:
E
(
x
)
=
E
0
(
x
)
+
E
R
(
x
)
8
x
2
H
Where:
the
term
E
0
(
x
)
is
associated
with
the
problem
objecti
v
e
function.
the
quadratic
function
E
R
(
x
)
ha
v
e
tw
o
objecti
v
es.
The
first
one,
is
to
penalizes
the
connections
which
violated
at
last
one
constraint.
The
second
one,
concerns
to
guarantees
that
the
CHN
con
v
er
ge
to
a
v
alid
solution.
T
o
perform
a
good
mapping,
this
function
must
be
constant
in
FxH
and
ding
a
well
choice.
F
or
this
problem
an
adapted
generalized
function
is
proposed
in
[22]:
E
(
x
)
=
2
x
t
Qx
+
1
2
(
Ax
)
t
(
Ax
)
+
x
t
diag
(
)(1
x
)
+
t
Ax
8
x
2
H
(3)
W
ith
parameters
2
R
+
;
2
R
n
;
2
R
N
and
a
m
m
matrix
.
The
goal
of
this
w
ork
is
to
solv
e
the
maximum
cardinality
of
the
independent
set
by
impro
ving
the
pre
vious
approach
based
on
the
CHN
proposed
by
[14].
The
main
idea
of
last
w
ork
is
to
con
v
ert
the
M
SSP
as
CHN
ener
gy
function.
Before
mapping
problem
used
a
quadratic
0-1
model
to
represent
the
MSSP
.
In
the
section
2.2.,
we
describe
the
reformulation
of
MSSP
,
then
we
present
the
solving
approach
in
the
section
2.3..
2.2.
F
ormulation
of
the
Maximum
Stable
Set
Pr
oblem
Let
G
=
(
V
;
E
)
an
undirected
graph
with
V
a
set
of
n
nodes
and
E
the
set
of
m
edges.
An
independent
set
of
a
gra
ph
G
is
a
set
of
nodes
S
with
the
property
that
an
y
node
nodes
in
S
is
not
connected
by
a
direct
edges
to
others
nodes
of
S
.
The
MSSP
c
o
ns
ist
to
determine
the
independent
set
which
ha
v
e
the
cardinal
ity
maximum
(
G
)
.
So,
the
objecti
v
e
function
to
maximize
is
the
number
of
nodes
which
are
pairwise
independent,
rather
we
re-
formulate
the
connection
penalty
by
a
quadratic
constraint
which
represent
direct
edge
connection.
T
o
perform
the
reformulation,
we
define
the
binary
v
ariables
x
i
such
that:
x
i
=
1
if
v
i
2
S
0
Otherwise
Let
S
V
be
a
stable
set
of
nodes.
F
or
ea
ch
node
v
i
of
t
he
graph
G
,
we
ha
v
e
the
follo
wing
relations:
CHN
and
Swap
Heuristic
to
Solve
the
Maximum
Independent
Set
...
(Bouhouc
h
adil)
Evaluation Warning : The document was created with Spire.PDF for Python.
3586
ISSN:
2088-8708
T
o
be
v
alid
S
must
don’
t
contains
t
w
o
adjacent
node.
So,
for
tw
o
node
v
i
and
v
j
in
S
:
there
corresponding
neurones
x
i
and
x
j
we
ha
v
e:
let
p
i
j
a
connection
penalty
between
v
i
and
v
j
.
(
v
i
;
v
j
)
2
S
=
)
x
i
=
1
andx
j
=
1
(
v
i
;
v
j
)
2
E
=
)
p
ij
x
i
x
j
=
0
=
)
p
ij
=
0
(
v
i
;
v
j
)
=
2
E
=
)
p
ij
x
i
x
j
=
1
=
)
p
ij
=
1
No
w
we
can
define
the
quantity:
P
(
x
)
=
n
X
i
=1
n
X
j
=1
p
ij
x
i
x
j
(4)
Referring
to
all
connections
constraints
imposed
in
2.2..
W
e
ha
v
e
P
(
h
)
=
0
when
all
nodes
in
S
are
pairwise
not
adjacent.
W
ith
p
ij
=
1
if
(
v
i
;
v
j
)
2
E
0
Otherwise
(5)
The
objecti
v
e
function
to
be
minimised
is
:
f
(
x
)
=
n
X
i
=1
x
i
Finally
,
the
QP
of
the
MSSP
problem
can
be
formulated
as:
(
QP
)
8
>
>
>
>
>
>
>
>
<
>
>
>
>
>
>
>
>
:
M
in
f
(
x
)
=
n
X
i
=1
x
i
S
ubj
ect
to
P
(
x
)
=
n
X
i
=1
n
X
j
=1
p
ij
x
i
x
j
=
0
x
2
f
0
;
1
g
n
After
the
reformulation
of
MSSP
problem
as
a
quadrati
c
0-1
programming,
it
can
be
solv
ed
by
an
y
adapted
approach
by
minimizing
the
linear
function
under
quadratic
constraints
(
QP
)
,
such
as
interior
point,
semidefinite
relaxations
[23]
or
lagrangian
relaxations[24].
I
n
this
paper
we
are
interested
in
a
v
ery
dif
ferent
approach
based
on
CHN
[14].
In
the
last
approach
authors
propose
to
solv
e
the
MSSP
into
tw
o
phases.
First,
solving
the
QP
of
MSSP
by
CHN.
W
e
note
by
be
the
v
alue
found
by
CHN.
Second,
changing
QP
model
formulation
by
adding
a
ne
w
constraint
to
the
objecti
v
e
function
such
as:
(
N
QP
)
8
>
>
>
>
>
>
>
>
>
>
>
>
>
<
>
>
>
>
>
>
>
>
>
>
>
>
>
:
M
in
f
(
x
)
=
n
X
i
=1
x
i
S
ubj
ect
to
P
(
x
)
=
n
X
i
=1
n
X
j
=1
p
ij
x
i
x
j
=
0
n
X
i
=1
x
i
x
2
f
0
;
1
g
n
Then
the
y
solv
e
the
ne
w
quadratic
problem(NQP)
by
a
second
CHN
associated
to
this
ne
w
reformulation
(
C
H
N
2
)
.
In
this
w
ork
we
propose
to
replace
the
second
run
C
H
N
2
by
the
local
search
heuristic.
On
other
w
ords,
the
solution
gi
v
en
by
the
first
run
on
the
QP
will
be
the
starting
point
of
the
local
search.
IJECE
V
ol.
7,
No.
6,
December
2017:
3583
–
3592
Evaluation Warning : The document was created with Spire.PDF for Python.
IJECE
ISSN:
2088-8708
3587
2.3.
A
continuous
Hopfield
netw
ork
to
solv
e
MSSP
No
w
The
MSSP
w
as
reformulate
as
QP
,
the
ne
xt
step
is
to
find
an
adapted
ener
gy
function
,
we
choose
the
same
one
introduced
by
[14]:
E
(
x
)
=
n
X
i
=1
x
i
+
1
2
n
X
i
=1
n
X
j
=1
b
ij
x
i
x
j
+
n
X
i
=1
x
i
(1
x
i
)
(6)
The
adv
antage
of
this
ener
gy
e
xpression
is
more
associated
with
the
objecti
v
e
function,
it’
s
relax
ed
by
the
quadratic
constraint.
by
corresponding
the
Equation
(2)
with
Equation
(6),
we
deduce
the
weights
and
thresholds:
T
i;j
=
p
ij
+
2
i;j
i
b
i
=
(7)
W
ith
ij
represent
the
Kroneck
er
symbol.
ij
=
1
if
i
=
j
0
if
i
6
=
j
Matrix
p
is
gi
v
en
by
Equation
(5),
the
v
alues
of
parameter
s
,
and
are
critical
to
reach
the
CHN
equilibrium
points
into
a
v
alid
solution
of
MSSP
.
The
study
of
partial
deri
v
ati
v
es
of
the
generalized
ener
gy
function
led
to
control
those
parameters
to
guide
the
con
v
er
gence
to
a
feasible
solution:
@
E
(
x
)
@
x
i
=
E
i
(
x
)
=
+
n
X
j
=1
b
ij
x
j
+
(1
2
x
i
)
T
o
determine
the
parameters-setting,
T
ala
v
an
[25]
used
the
h
yperplane
method
analyse
to
study
@
E
(
x
)
.
This
procedure
consist
of
partition
the
Hamming
h
ypercube
H
by
a
h
yperplane
containing
all
feasible
solutions
so
that
tw
o
properties
mus
t
be
respect
ed
by
the
CHN
e
v
olution:
first,
adding
an
y
solution
not
belong-
ing
to
this
h
yperplane,
second,
dropping
out
an
y
infeasible
solution
belonging
to
the
h
yperplane.
Also,
some
conditions
are
imposed
to
determine
these
parameters-setting
easily:
>
0
;
0
T
o
minimize
the
objecti
v
e
function,
we
fix
ed
the
follo
wing
constraint:
>
0
T
o
escape
the
stability
of
the
interior
points
x
2
H
H
C
,
the
ne
xt
constraint
is
necessary:
T
i;i
=
2
0
While
MSSP
model
contains
just
one
constraint
then
we
ha
v
e:
H
C
H
F
=
f
x
2
H
C
=h
(
x
)
>
0
g
Let
x
2
H
C
H
F
,
so
for
tw
o
adjacents
nodes
x
i
and
x
j
are
in
the
stable
set
S
,
then
x
i
=
x
j
=
1
and
therefore
the
acti
v
ation
of
x
i
will
be
discouraged
if
E
0
i
(
x
)
where
>
0
.
Based
to
this
study
the
parameter
settings
are
restricted
by
the
follo
wing
condition:
+
A
feasible
solution
can
be
reached
if
the
follo
wing
conditions
are
respected:
>
0
;
>
0
;
0
+
=
(8)
The
question
then
is
about
making
good
choice
of
t
hese
parameter
under
the
condition
bello
w
to
calculate
the
weights
and
thresholds
of
the
C
H
N
.,The
adv
antage
of
resolving
MSSP
b
y
Continuous
dynamic
of
Hopfield
neural
netw
ork
is
that
CHN
are
v
ery
f
ast
b
ut
al
w
ays
con
v
er
ge
to
a
local
minima,
in
[14]
authors
insert
some
linear
constraint
to
perturb
the
netw
ork
weights
and
consequently
escaping
from
all
local
minima
less
than
threshold
.
This
method
appear
ef
ficient,
b
ut
the
control
of
CHN
con
v
er
gence
become
dif
ficult.
.
CHN
and
Swap
Heuristic
to
Solve
the
Maximum
Independent
Set
...
(Bouhouc
h
adil)
Evaluation Warning : The document was created with Spire.PDF for Python.
3588
ISSN:
2088-8708
3.
PR
OPOSED
APPR
O
A
CH
Hopfeild
neural
netw
ork
con
v
er
ge
f
aster
,
b
ut
it
con
v
er
ges
closely
to
the
nearest
local
minima
of
the
starting
point.
So
man
y
time
the
netw
ork
gi
v
es
a
no
good
solution.
T
o
o
v
ercome
this
weakness
man
y
solution
w
as
proposed
to
escape
from
local
minima.
In
[14],
authors
propose
to
add
a
linear
constraint
which
restrict
a
lo
wer
bound
of
the
minimum
cardinality
of
the
solution,
as
sho
wn
in
[14],
the
insertion
of
ne
w
constraint
to
the
QP
leads
t
o
impro
v
e
the
solution,
b
ut
in
contrast
of
obtained
numerical
results,
we
remark
that
netw
ork
f
ailed
to
gi
v
e
a
v
alid
solution
man
y
time.
T
o
impro
v
e
this
meta-heuristic
approach,
we
propose
to
use
a
h
ybridization
with
other
heuristic.
It
seems
beneficial
to
combine
CHN
with
an
adapted
local
search.
In
[16]
authors
pro
v
e
that
sw
ap(1,2)
gi
v
e
a
good
performance.
Algorithm
(1)
sho
w
the
proposed
local
search
based
Sw
ap
heuristic.
As
described,
this
process
by
replacing
each
node
n
in
the
the
gi
v
en
initial
solution
by
tw
o
nodes
u
and
v
.
The
chosen
u
and
v
must
be
neighbors
of
n.
Therefore,
the
solution
is
impro
v
ed
at
each
time
by
adding
one
node.
This
last
search
is
do
wn
in
linear
times.
This
is
possible
by
adding
a
collection
of
neighborhods
set
V
(
n
)
which
store
for
each
graph
node
the
set
of
it
adjacent
nodes.
The
Local
search
w
ork
directly
on
the
solution
gi
v
en
by
the
CHN.
W
e
note
that
to
check
if
a
node
n
of
the
graph
is
in
the
solution,
we
v
erify
if
its
associated
CHN
node
is
acti
v
e.
Also,
to
reduce
the
time
to
find
the
neighbors
of
the
candidate
node
which
can
be
replaced,
we
maintaining
a
stack
T
o
v
isit
of
v
alid
candidate
to
visit.
After
e
xamine
each
node,
we
remo
v
ed
it
from
the
candidate
list,
and
go
to
the
ne
xt
until
the
list
T
o
v
isit
become
empty
.
Although,
we
added
to
the
candidates
list
T
o
v
isit
an
y
ne
w
insert
node
in
the
solution
S.
In
this
w
ork,
we
implement
the
direct
and
simple
local
search
based
on
sw
ap
heuristic.
F
or
this,
to
replace
the
current
candidate
node
n
,
we
consider
just
the
first
pair
of
node
u
,
v
founded,
which
meet
conditions.
Ne
v
ertheless,
we
can
add
more
impro
v
ement
to
this
LS,
lik
e
sorting
V(n)
by
number
adjacent
neighbor
in
the
solution
[26]
or
plateau
search
[16].
Function
S
w
ap
1
2
(
S,T
:
)
:
Solution
In
:
T
o
v
isit
:
Stack
of
candidate
nodes
V
(
i
)
:
Set
of
neighborhood
of
the
node
i
Out
:
Impr
o
v
ed
Solution
T
o
v
isit
=
S
While
(
T
o
v
isit
is
not
empty
)
do
n
=
pop
(
T
o
v
isit
)
F
or
(
u;
v
)
2
V
(
n
)
V
(
n
)
do
H
av
e
Ad
j
acent
in
S
=
f
al
se
If
(
u
=
2
S
and
u
=
2
S
and
T
(
u;
v
)
=
)
then
If
(
is
mar
k
ed
(
u
)
=
f
al
se
and
is
mar
k
ed
(
v
)
=
f
al
se
)
then
F
or
(
a
6
=
n
)
2
S
do
If
(
T
(
u;
a
)
=
or
T
(
v
;
a
)
=
)
then
H
av
e
Ad
j
acent
in
S
=
tr
ue
Break
end
If
end
F
or
If
(
H
av
e
Ad
j
acent
in
S
=
f
al
se
)
then
replace
n
by
u
and
v
add
u
and
v
T
o
v
isit
Break
end
If
end
If
end
If
end
F
or
mark(n)
done
End
Algorithm
1.
Local
search
algorithm
Naturally
,
CHN
attempted
to
minimize
the
number
conflicted
constraints,
therefore,
some
times
netw
ork
can
stabilise
with
not
null
Ener
gy
E
6
=
0
,
and
gi
v
es
an
in
v
alid
solution.
T
o
o
v
ercome
this
problem,
we
add
a
local
heuristic
called
Remo
v
e
Process.
It
delete
nodes
from
the
solution
until
to
being
v
alid.
IJECE
V
ol.
7,
No.
6,
December
2017:
3583
–
3592
Evaluation Warning : The document was created with Spire.PDF for Python.
IJECE
ISSN:
2088-8708
3589
Sort
S
by
number
of
Adjacent
F
or
each
v
2
S
do
if(
9
u
2
S
/
(
u;
v
)
2
E
)
delate
v
end
F
or
Algorithm
2.
Delate
Process
4.
NUMERICAL
RESUL
T
T
o
sho
w
the
ef
ficienc
y
of
our
approach,
we
present
a
computational
results.
First,
we
run
the
solv
er
on
the
random
indirected
generated
graphs.
The
used
generator
return
a
G
n;p
random
graph,
also
kno
wn
as
an
Erd
˜
os-R
´
en
yi
graph
or
a
binomial
graph
[27],
where
n
the
number
of
nodes
and
the
graph
density
which
can
be
determinate
by
the
probability
for
edge
creation
p
.
So
we
generated
fi
v
e
classes
classified
by
t
he
number
of
graph
nodes
from
100
to
500,
and
for
each
class,
the
density
p
v
aried
from
10%
to
100%.
F
or
a
gi
v
en
p
we
generate
random
100
instances.
Figure
1
plot
the
CPU
time
tack
ed
by
CHN,
C
H
N
2
-the
impro
v
ed
v
ariant
[14]-
and
CHNSw
ap.
The
comparison
is
do
wn
under
fixing
the
density
D
=
50%
and
v
arying
the
numbers
of
nodes.
Practically
,
the
curv
es
of
CHN
and
CHNSw
ap
are
superposed.
Figure
1.
the
CPU
time
as
a
function
of
number
of
nodes.
Figure
2
gi
v
e
the
e
v
olution
of
times
of
CHNSw
ap
approach
as
function
of
the
graph
density
(D),
respecti
v
ely
,
for
classes
V=100,
V=300
and
V=500.
W
e
note
that
left
v
ertical
axis
is
the
times
performed
by
CHN
and
the
right
for
LS.
It
is
clear
that
the
problem
dif
ficulty
increases
as
the
number
of
nodes
increases.
The
same
remark
can
be
seen
at
all
tested
graph
classes.
T
o
study
the
solution
quality
we
run
our
approach
on
selected
instance
from
the
benchmark
DIMA
CS[28].
CHN
and
Swap
Heuristic
to
Solve
the
Maximum
Independent
Set
...
(Bouhouc
h
adil)
Evaluation Warning : The document was created with Spire.PDF for Python.
3590
ISSN:
2088-8708
Figure
2.
the
CPU
t
imes
tack
ed
by
CHN
and
LS
in
CHNSw
ap
(a)Class
of
graph
containing
100
nodes
(b)Class
of
graph
containing
300
nodes
(c)Class
of
graph
containing
500
nodes
CHN
CHNSw
ap
Graphs
V
E
(
G
)
Min
Mean
Best
Min
Mean
Best
brock200
2.clq
200
9876
12
8
8
8
9
9
9
brock200
4.clq
200
13089
17
11
11
11
13
13,99
14
C250.9.clq
250
27984
24
34
34
34
37
37,69
38
c-f
at200-1.clq
200
1534
58
12
12
12
12
12
12
c-f
at200-2.clq
200
3235
44
23
24
24
24
24
24
c-f
at200-5.clq
200
8473
30
58
58
58
58
58
58
DSJC125.9.col
125
6961
44
30
30,08
31
32
32
32
frb30-15-1.clq
450
83198
55
20
20
20
24
24
24
gen200
p0.9
44.clq
200
17910
44
31
31
31
35
35,77
36
hamming6-4.clq
64
704
4
2
2,42
3
4
4
4
johnson16-2-4.clq
120
5460
8
6
6,35
7
8
8
8
johnson8-2-4.clq
28
210
14
2
4
6
4
4
4
johnson8-4-4.clq
70
1855
11
8
8,91
9
10
13,27
14
k
eller4.clq
171
9435
126
11
6
5
7
7
7
MANN
a27.clq
378
70551
126
117
117
117
117
117,98
121
MANN
a9.clq
45
918
16
12
12
12
15
15,76
16
p
hat300-1.clq
300
10933
8
6
6
6
6
6,51
8
p
hat300-2.clq
300
21928
25
22
22
22
24
24,99
25
p
hat300-3.clq
300
33390
36
29
30,89
31
33
33,97
34
san200
0.7
1.clq
200
13930
18
15
15
15
15
15
16
san200
0.9
3.clq
200
17910
44
31
31
31
33
33
33
san400
0.9
1.clq
400
71820
100
39
44,15
46
52
52,98
53
T
able
1.
Comparison
of
solution
quality
between
CHN
and
CHNSw
ap
o
v
er
DIMA
CS
IJECE
V
ol.
7,
No.
6,
December
2017:
3583
–
3592
Evaluation Warning : The document was created with Spire.PDF for Python.
IJECE
ISSN:
2088-8708
3591
Graphs
E
V
CHN(ms)
Sw
ap(ms)
johnson8-2-4.clq
210
28
2,12
0,01
MANN
a9.clq
918
45
3,18
0
,06
hamming6-4.clq
704
64
1,62
0,18
johnson8-4-4.clq
1855
70
9,53
0,12
johnson16-2-4.clq
5460
120
25,65
0,32
DSJC125.9.col
6961
125
7,14
0,32
C125.9.clq
6963
125
9,88
0,08
C125.9.clq
6963
125
9,44
0,06
k
eller4.clq
9435
171
41,06
0,31
c-f
at200-1.clq
1534
200
77,86
1,17
c-f
at200-2.clq
3235
200
61,01
0,95
c-f
at200-5.clq
8473
200
34,64
0,61
brock200
2.clq
9876
200
76,04
0,7
2
brock200
4.clq
13089
200
65,54
0,4
san200
0.7
1.clq
13930
200
16,09
0,5
gen200
p0.9
44.clq
17910
200
4,58
0,44
san200
0.9
3.clq
17910
200
2,5
0,68
C250.9.clq
27984
250
8,92
0,71
p
hat300-1.clq
10933
300
163,3
2,38
p
hat300-2.clq
21928
300
159,36
2,43
p
hat300-3.clq
33390
300
139,28
1,07
MANN
a27.clq
70551
378
160,81
0
,82
san400
0.9
1.clq
71820
400
115,3
1,82
frb30-15-1.clq
83198
450
362,35
2,31
T
able
2.
T
imes
performance
The
ef
ficienc
y
of
the
proposed
approach
is
reinforced
by
the
e
xperimental
results.
T
able
1
sho
ws
t
hat
our
method
gi
v
es
good
result
then
used
CHN
alone.
T
able
2
sho
w
the
time
added
by
the
impro
v
ement
process
with
local
heuristics
ag
ainst
the
time
needed
by
CHN.
It’
s
clear
that
impro
v
ement
is
do
wn
with
adding
non-
significant
time.
Our
approach
is
v
ery
po
werful
from
a
theoretical
point
of
vie
w
.
This
approach
gi
v
es
a
good
performance
compared
with
the
impro
v
ed
approach
C
H
N
2
proposed
by
[14]
which
crush
often
with
no
v
alid
solution.
5.
CONCLUSION
In
the
last
decade
se
v
eral
areas
ha
v
e
applied
MSSP
problem
and
Max-Clique
problem.
So,
man
y
heuristic
were
de
v
eloped.
In
this
sense
we
directed
our
contrib
ution.
In
this
w
ork,
a
ne
w
approach
has
been
proposed
based
CHN
and
sw
ap
local
heuristic
to
solv
e
the
maximal
cardinali
ty
of
independent
sets.
The
MSSP
is
solv
ed
into
three
step:
First,
it
is
reformulate
as
quadratic
problem.
Second,
the
QP
is
associated
with
CHN
ener
gy
function,
then
we
stabilise
CHN
t
o
con
v
er
ge
at
the
solution.
Third,
the
local
search
process
performed
by
starting
from
the
solution
gi
v
en
in
the
second
step.
It
same
dif
ficult
to
inte
grating
the
local
heuristic
in
the
main
loop
of
CHN
stabilisation
for
this
we
ha
v
e
chosen
the
collaborati
v
e
h
ybridisation
between
CHN
and
LS.
W
e
e
x
ecuted
a
series
of
e
xperiments
in
order
to
pro
v
e
the
ef
ficienc
y
re
g
arding
the
time
comple
xity
and
the
solution
of
quality
.
The
time
allo
wed
to
LS
is
v
ery
smal
l
so
that
we
can
assert
that
our
approach
is
able
to
find
the
maximal
independent
set
for
v
ery
lar
ge
graph.
Furthermore,
the
rate
of
success
to
gi
v
e
a
v
alid
solution
is
up
to
100%
in
our
approach.
W
e
note
that
this
approach
can
be
used
to
solv
e
the
Max-Clique
problem
special
for
perfect
graph
by
solving
the
graph
dual.
REFERENCES
[1]
I.
Iglezakis,
“The
conflict
graph
for
ma
intaining
casebased
reasoning
systems,
”
in
International
Confer
-
ence
on
Case-Based
Reasoning
.
Springer
,
2001,
pp.
263–275.
CHN
and
Swap
Heuristic
to
Solve
the
Maximum
Independent
Set
...
(Bouhouc
h
adil)
Evaluation Warning : The document was created with Spire.PDF for Python.
3592
ISSN:
2088-8708
[2]
D.
H.
Ballard
and
C.
M.
Bro
wn,
“Computer
vision,
article,
4
pages
prentice-hall,
”
Engle
wood
Clif
fs,
Ne
w
J
er
se
y
,
belie
ved
to
be
published
mor
e
than
one
year
prior
to
the
filing
date
of
the
pr
esent
application
,
1982.
[3]
F
.
Harary
and
I.
C.
Ross,
“
A
procedure
for
clique
detection
using
the
group
matrix,
”
Sociometry
,
v
ol.
20,
no.
3,
pp.
205–215,
1957.
[4]
E.
Loukakis
and
C.
Tsouros,
“
A
depth
first
search
algorithm
to
generate
the
f
amily
of
maximal
indepen-
dent
sets
of
a
graph
le
xicographically
,
”
Computing
,
v
ol.
27,
no.
4,
pp.
349–366,
1981.
[5]
M.
Re
gneri,
“Finding
all
cliques
of
an
undirected
graph,
”
in
SeminarCurr
ent
T
r
ends
in
IE
WS
J
un
,
2007.
[6]
S.
Tsukiyama,
M.
Ide,
H.
Ariyoshi,
and
I.
Shiraka
w
a,
“
A
ne
w
algorithm
for
generating
all
the
maximal
independent
sets,
”
SIAM
J
ournal
on
Computing
,
v
ol.
6,
no.
3,
pp.
505–517,
1977.
[7]
C.
Bron
and
J.
K
erbosch,
“
Algorithm
457:
finding
a
ll
cliques
of
an
undirected
graph,
”
Communications
of
the
A
CM
,
v
ol.
16,
no.
9,
pp.
575–577,
1973.
[8]
E.
Loukakis,
“
A
ne
w
bac
ktracking
algorithm
for
generating
the
f
amily
of
maximal
independent
sets
of
a
graph,
”
Computer
s
&
Mathematics
with
Applications
,
v
ol.
9,
no.
4,
pp.
583–589,
1983.
[9]
D.
S.
Johnson,
M.
Y
annakakis,
and
C.
H.
P
apadimitriou,
“On
generating
all
maximal
independent
sets,
”
Information
Pr
ocessing
Letter
s
,
v
ol.
27,
no.
3,
pp.
119–123,
1988.
[10]
N.
Chiba
and
T
.
Nishizeki,
“
Arboricity
and
subgraph
listing
algorithms
,
”
SIAM
J
ournal
on
Computing
,
v
ol.
14,
no.
1,
pp.
210–223,
1985.
[11]
E.
T
omita,
A.
T
anaka,
and
H.
T
akahashi,
“The
w
orst-case
time
comple
xity
for
finding
all
the
cliques,
”
T
echnical
Report
TR-C5,
UEC,
T
ech.
Rep.,
1988.
[12]
C.
Mannino
and
A.
Sassano,
“
An
e
xact
algorithm
for
the
maximum
stable
set
problem,
”
Computational
Optimization
and
Applications
,
v
ol.
3,
no.
3,
pp.
243–258,
1994.
[13]
Q.
Duan,
T
.
W
.
Liao,
and
H.
Y
i,
“
A
comparati
v
e
study
of
dif
ferent
local
search
application
strate
gies
in
h
ybrid
metaheuristics,
”
Applied
Soft
Computing
,
v
ol.
13,
no.
3,
pp.
1464–1477,
2013.
[14]
M.
Ettaouil,
C.
Loqman,
and
K.
Elmoutaouakil,
“Impro
v
ed
optimal
competiti
v
e
hopfield
netw
ork
for
the
maximum
stable
set
problem,
”
International
J
ournal
on
Computer
Science
&
Engineering
,
v
ol.
2,
no.
6,
pp.
2071–2077,
2010.
[15]
R.
Battiti
and
M.
Protasi,
“Reacti
v
e
local
search
for
the
maximum
clique
problem
1,
”
Algorithmica
,
v
ol.
29,
no.
4,
pp.
610–637,
2001.
[16]
A.
Grosso,
M.
Locatelli,
and
F
.
Della
Croce,
“Combining
sw
aps
and
node
weights
in
an
adapti
v
e
greedy
approach
for
the
maximum
clique
problem,
”
J
ournal
of
Heuristics
,
v
ol.
10,
no.
2,
pp.
135–152,
2004.
[17]
P
.
Hansen,
N.
Mladeno
vi
´
c,
and
D.
Uro
ˇ
se
vi
´
c,
“V
ariable
neighborhood
search
for
the
maximum
clique,
”
Discr
ete
Applied
Mathematics
,
v
ol.
145,
no.
1,
pp.
117–125,
2004.
[18]
K.
Katayama,
A.
Hamamoto,
and
H.
Narihisa,
“
An
ef
fecti
v
e
local
search
for
the
maximum
clique
prob-
lem,
”
Information
Pr
ocessing
Letter
s
,
v
ol.
95,
no.
5,
pp.
503–511,
2005.
[19]
W
.
Pullan
and
H.
H.
Hoos,
“Dynamic
local
search
for
the
maximum
clique
problem,
”
J
ournal
of
Artificial
Intellig
ence
Resear
c
h
,
v
ol.
25,
pp.
159–185,
2006.
[20]
S.
Richter
,
M.
Helmert,
and
C.
Gretton,
“
A
stochastic
local
search
approach
to
v
erte
x
co
v
er
,
”
in
Annual
Confer
ence
on
Artificial
Intellig
ence
.
Springer
,
2007,
pp.
412–426.
[21]
J.
J.
Hopfield,
“Neural
netw
orks
and
ph
ysical
systems
with
emer
gent
collecti
v
e
computational
abilities,
”
Pr
oceedings
of
the
national
academy
of
sciences
,
v
ol.
79,
no.
8,
pp.
2554–2558,
1982.
[22]
M.
Ettaouil,
C.
Loqman,
K.
Haddouch,
and
Y
.
Hami,
“Maximal
constraint
satisf
action
problems
solv
ed
by
continuous
hopfield
netw
orks.
”
WSEAS
T
r
ansactions
on
Computer
s
,
v
ol.
12,
no.
2,
pp.
29–40,
2013.
[23]
M.
Ettaouil
and
C.
Loqman,
“Constraint
satisf
action
problems
solv
ed
by
semidefinite
relaxations,
”
WSEAS
T
r
ansactions
on
Computer
s
,
v
ol.
7,
no.
7,
pp.
951–961,
2008.
[24]
B.
Thiong
ane,
A.
Nagih,
and
G.
Plateau,
“
An
adapted
step
size
algorithm
for
a
0-1
biknapsack
lagrangean
dual,
”
Annals
of
Oper
ations
Resear
c
h
,
v
ol.
139,
no.
1,
pp.
353–373,
2005.
[25]
P
.
M.
T
ala
v
´
an
and
J.
Y
´
a
˜
nez,
“The
generalized
quadratic
knapsack
problem.
a
neuronal
netw
ork
approach,
”
Neur
al
networks
,
v
ol.
19,
no.
4,
pp.
416–428,
2006.
[26]
D.
V
.
Andrade,
M.
G.
Resende,
and
R.
F
.
W
erneck,
“F
ast
local
search
for
the
maximum
independent
set
problem,
”
J
ournal
of
Heuristics
,
v
ol.
18,
no.
4,
pp.
525–547,
2012.
[27]
S.
Choudum,
“
A
simple
proof
of
the
erdos-g
allai
theorem
on
graph
sequences,
”
Bulletin
of
the
A
ustr
alian
Mathematical
Society
,
v
ol.
33,
no.
01,
pp.
67–70,
1986.
[28]
“The
second
dimacs
implementation
challenge,
”
ftp://dimacs.rutgers.edu/pub/challenge/graph/benchmarks/clique/,
1992.
IJECE
V
ol.
7,
No.
6,
December
2017:
3583
–
3592
Evaluation Warning : The document was created with Spire.PDF for Python.