TELK
OMNIKA,
V
ol.16,
No
.6,
December
2018,
pp
.
2747–2755
ISSN:
1693-6930,
accredited
First
Gr
ade
b
y
K
emenr
istekdikti,
Decree
No:
21/E/KPT/2018
DOI:
10.12928/TELK
OMNIKA.v16i6.9691
2747
Reinf
or
ced
Island
Model
Genetic
Algorithm
to
Solve
Univer
sity
Cour
se
Timetab
ling
Alfian
Akbar
Gozali,
Shig
eru
Fujim
ura
*
Gr
aduate
School
of
IPS
,
W
aseda
Univ
ersity
2-7
Hibikino
,
W
akamatsu,
Kitakyushu,
Fukuoka
808-0135,
J
apan
*
Corresponding
author
,
e-mail:
alfian@tass
.telk
om
univ
ersity
.ac.id
Abstract
The
Univ
ersity
Course
Timetab
ling
Prob
lem
(UCTP)
is
a
scheduling
prob
lem
of
assigning
teaching
e
v
ent
in
cer
tain
time
and
room
b
y
consider
ing
the
constr
aints
of
univ
ersity
stak
eholders
such
as
students
,
lecturers
,
depar
tments
,
etc.
This
prob
lem
become
s
complicated
f
or
univ
ersities
which
ha
v
e
immense
n
umber
of
students
and
lecturers
.
Theref
ore
,
a
scalab
le
and
reliab
le
timetab
ling
solv
er
is
needed.
Ho
w
e
v
er
,
current
solv
ers
and
gener
ic
solution
f
ailed
to
meet
se
v
er
al
specific
UCTP
.
Moreo
v
er
,
some
univ
ersit
ies
implement
student
sectioning
prob
lem
with
individual
student
specific
constr
aints
.
This
research
introduces
the
Reinf
orced
Asynchronous
Island
Model
Genetic
Algor
ithm
(RIMGA)
to
optimiz
e
the
r
esource
usage
of
the
computer
.
RIMGA
will
configure
the
sla
v
e
that
has
completed
its
process
to
helping
other
machines
that
ha
v
e
y
et
to
complete
theirs
.
This
research
sho
ws
that
RIMGA
not
only
impro
v
es
time
perf
or
mance
in
the
computational
e
x
ecution
process
,
it
also
off
ers
g
reater
oppor
tunity
to
escape
the
local
optim
um
tr
ap
than
pre
vious
model.
K
e
yw
or
ds:
univ
ersity
course
timetab
ling
prob
lem,
island
model,
genetic
algor
ithm
Cop
yright
c
2018
Univer
sitas
Ahmad
Dahlan.
All
rights
reser
ved.
1.
Intr
oduction
The
Univ
ersity
Course
Timetab
ling
Prob
lem
(UCTP)
is
a
scheduling
prob
lem
of
assigning
teaching
e
v
ent
in
cer
tain
time
and
room
b
y
consider
ing
the
constr
aints
of
univ
ersity
stak
eholders
such
as
students
,
lecturers
,
depar
tments
,
etc.
The
constr
aints
could
be
hard
(encour
aged
to
be
fulfilled)
or
soft
(better
to
be
fulfilled)
constr
aints
.
Timetab
ling
itself
is
conside
red
an
NP-Hard
prob
lem
[4].
Some
univ
ersities
such
as
T
elk
om
Univ
ersity
[5]
ha
v
e
a
large
population
of
students
and
lecturers
,
and
so
their
constr
aints
are
also
g
reat
as
a
result.
This
condition
could
mak
e
the
prob
lem
e
v
en
more
complicated.
In
addition,
the
student
body
in
T
elk
om
Univ
ersity
has
increased
from
6,570
students
in
2010
to
21,698
in
2016.
The
n
umber
is
a
result
of
the
merging
of
f
our
univ
ersities:
T
elk
om
Institute
of
T
echnology
,
T
elk
om
P
olytechnic
,
T
elk
om
Institute
of
Management
and
T
elk
om
School
of
Ar
ts
.
The
univ
ersity
timetab
ling
solv
er
m
ust,
as
a
result,
meet
a
ne
w
specification:
scalability
.
One
of
the
most
recent
researches
is
the
application
of
genetic
algor
ithms
(GAs),
which
is
inspired
b
y
the
theor
y
of
e
v
olution.
This
method
has
been
used
to
solv
e
man
y
actual
UCTP
cases
.
There
are
se
v
er
al
GA
models
such
as
inf
or
med
GA
[10],
par
allel
GA
[2],
NSG
A
II
[11,
9],
Adaptiv
e
Real
Cod
ed
GA
[13],
Hybr
id
Fuzzy
and
GA
[6],
Quantum
Ev
olutionar
y
Computing
[1],
and
distr
ib
uted
model
GA
[14]
that
ha
v
e
been
proposed.
This
research
u
sed
the
distr
ib
uted
model
GA,
or
what
is
kno
wn
usually
as
Island
Model
GA
[14],
out
of
all
these
models
.
W
e
ha
v
e
chosen
this
model
f
or
its
high
scalability
.
F
or
the
univ
ersity
course
timetab
ling
itself
,
Gozali
et
al.
introduced
Asynchronous
Island
Model
GA
(AIMGA)
[5].
This
model
succeeded
in
solving
actual
UCTP
cases
in
the
T
elk
om
Univ
ersity
Sch
ool
of
Engineer
ing
with
a
satisfying
result.
Ho
w
e
v
er
,
when
it
w
as
r
un
under
v
ar
ious
computer
specifications
,
f
aster
computers
w
ere
idle
aft
er
ha
ving
completed
their
tasks
while
the
slo
w
er
ones
w
ere
still
r
unning.
This
idling
prob
lem
left
an
oppor
tunity
to
be
e
xploited
f
or
more
efficient
perf
or
mance
.
Receiv
ed
Ma
y
21,
2018;
Re
vised
No
v
ember
2,
2018;
Accepted
No
v
ember
23,
2018
Evaluation Warning : The document was created with Spire.PDF for Python.
TELK
OMNIKA
ISSN:
1693-6930
2748
Theref
ore
,
w
e
are
going
to
introduce
the
Reinf
orced
AIMGA
(RIMGA)
to
impro
v
e
time
perf
or
mance
in
the
computational
e
x
ecution
process
.
At
the
same
time
,
w
e
also
off
er
g
reater
oppor
tunity
to
escape
the
local
optim
um
tr
ap
than
the
con
v
entional
AIMGA.
T
ak
en
together
,
the
contr
ib
utions
of
this
w
or
k
are
(1)
introducing
RIMGA
as
a
br
and
ne
w
mechanism
to
complement
common
AIMGA,
(2)
designing
the
T
elk
om
Univ
ersity
UCTP
,
and
(3)
analyzing
RIMGA
perf
or
mance
in
handling
T
elk
om
UCTP
.
This
paper
consists
of
se
v
en
sections
.
The
remainder
of
this
paper
is
organiz
ed
as
f
ollo
ws
.
Section
2
talks
about
the
mechanism
of
proposed
method,
RIMGA
and
its
par
ameters
,
handles
AIMGA’
s
idling
prob
lem.
Section
3
introduces
the
research
method
which
is
split
into
tw
o
subsections:
designing
T
elk
om
UCTP
and
its
RIMGA
implementation.
Section
4
sho
ws
ho
w
w
e
conducted
the
e
xper
iment,
results
,
and
its
discussion.
The
last
b
ut
not
the
least,
section
5
tak
es
place
as
the
conclusion
of
this
w
or
k.
2.
The
Pr
oposed
Method
2.1.
Reinf
or
ced
State
The
AIMGA
could
solv
e
the
synchronous
model
w
aiting
prob
lem,
b
ut
in
reality
,
it
is
f
ound
that
there
is
still
an
oppor
tunity
to
increase
the
AIMGA
efficiency
.
There
is
almost
no
prob
lem
if
the
specification
of
the
computers
is
not
too
diff
erent.
If
,
ho
w
e
v
er
,
the
y
are
actually
under
a
v
er
y
diff
erent
specification,
there
will
be
sla
v
es
that
complete
their
tasks
f
aster
than
other
sla
v
es
.
Such
a
condition
will
mak
e
the
f
aster
sla
v
es
idle
while
the
slo
w
er
ones
are
still
r
unning
their
tasks
.
The
RIMGA
w
as
introduced
in
this
paper
to
increase
the
AIMGA
efficiency
.
The
main
idea
of
th
e
RIMGA
is
ho
w
the
idle
island
(computer)
can
be
utiliz
ed
fur
ther
to
help
another
r
unning
island.
The
idle
island
as
an
island
that
has
reached
its
stop
condition
has
to
find
another
island
which
is
still
r
unning.
The
idle
island
will
reinf
orce
that
island
to
complete
its
process
more
quic
kly
.
Figure
1
illustr
ates
the
diff
erence
betw
een
the
asynchronous
and
the
RIMGA.
Figure
1.
The
diff
erence
of
tw
o
island
GA
Models
The
AIMGA
isolates
each
computer
to
r
un
separ
ately
so
that
each
computer
can
complete
its
task
without
w
aiting
f
or
other
computers
to
complete
theirs
.
The
reinf
orced
model
tr
ies
to
utiliz
e
the
idle
time
(g
r
a
y
cell)
of
sla
v
e
2
from
the
asynchronous
one
.
After
sla
v
e
2
has
completed
its
task,
it
w
ould
help
sla
v
e
1
to
finish
its
task
(gener
ation
3).
As
sho
wn
in
the
Master
Island
state
diag
r
am
in
Figure
2-master
state
,
the
RIMGA
implements
the
reinf
orced
function.
It
tr
ies
to
find
an
island
that
has
not
completed
its
task
to
be
helped
b
y
the
island
that
has
.
This
attempt
aims
to
maximiz
e
the
productivity
of
the
model
b
y
optimizing
the
utility
of
the
idle
island
that
has
completed
its
task.
Figure
2-sla
v
e
state
sho
ws
that
the
RIMGA
star
ts
when
there
is
an
island
that
has
completed
all
its
process
.
The
master
will
e
v
aluate
and
choose
which
of
th
e
islands
that
has
not
completed
Reinf
orced
Island
Model
Genetic
Algor
ithm
to
Solv
e
Univ
ersity
...
(Alfian
Akbar
Gozali)
Evaluation Warning : The document was created with Spire.PDF for Python.
2749
ISSN:
1693-6930
Figure
2.
Master-Sla
v
e
Island
State
diag
r
am
its
task
to
be
helped
b
y
the
island
that
has
.
There
are
se
v
er
al
consider
ations
in
pic
king
the
island
to
be
helped
and
ho
w
to
gener
ate
its
population.
Such
consider
ations
are
presented
as
reinf
orced
par
ameters
.
2.2.
Reinf
or
ced
P
arameter
s
Reinf
orced
par
ameters
are
par
ameters
that
control
ho
w
the
reinf
orced
state
beha
v
es
.
The
master
island
will
use
the
reinf
orced
par
ameters
to
control
ho
w
the
islands
that
ha
v
e
completed
their
tasks
to
help
those
th
at
ha
v
e
not.
There
are
three
reinf
orced
par
ameters:
the
island
state
,
island
pr
ior
ity
,
and
individual
pic
king
method.
The
reinf
orced
par
ameters
are
defined
as
f
ollo
ws
.
The
set
of
(sla
v
e)
islands
is
e
xpressed
b
y
S
.
The
set
of
islands
that
ha
v
e
completed
their
tasks
is
represented
b
y
F
,
those
that
h
a
v
e
not
b
y
U
,
and
those
that
are
helped
b
y
H.
Let
F
S
,
U
S
,
and
H
S
where
F
=
U
.
The
reinf
orced
par
ameters
are
e
xpressed
as
f
p
j
p
=
f
tr
ue;
f
al
se
gg
such
that
p
1
is
the
island
state
,
p
2
the
island
pr
ior
ity
,
and
p
3
the
individual
pic
king
method.
The
first
par
ameter
is
the
island
state
.
The
island
state
is
a
condition
to
deter
mine
whether
an
island
that
is
being
helped
b
y
another
island
or
not.
This
par
ameter
will
deter
mine
whether
the
reinf
orcement
direction
is
div
e
rgent
(balance
f
or
all
islands
that
ha
v
e
not
completed
their
tasks)
or
con
v
ergent
(islands
that
ha
v
e
,
one
b
y
one).
An
island
that
is
helped
b
y
another
island
e
xpressed
as
H
i
.
R
(
a;
b
)
is
a
function
that
deter
mines
whether
island
a
m
ust
help
island
b
or
not.
R
(
a;
b
)
will
retur
n
tr
ue
if
p
1
is
tr
ue
and
island
b
has
not
been
helped
b
y
another
island
y
et.
If
R
(
a;
b
)
=
tr
ue
,
island
a
helps
island
b
and
the
state
of
island
b
will
be
changed
to
being
helped.
hel
p
(
a;
b
)
is
a
procedure
in
which
island
a
helps
island
b
.
R
(
f
:
8
F
;
u
:
8
U
)
=
(
tr
ue;
if
(
p
1
=
tr
ue
)
\
(
u
=
2
H
)
f
al
se;
other
w
ise
if
(
R
(
f
;
u
)
=
tr
ue
)
)
hel
p
(
f
;
u
)
;
u
h
(1)
The
second
par
ameter
is
island
priority
.
It
has
tw
o
choices:
those
could
be
based
on
the
least
n
umber
of
iter
ations
or
on
the
poorest
(largest)
fitness
.
These
choices
ref
er
to
the
f
actors
are
the
most
impor
tant
,
the
n
umber
of
iter
ations
or
fitness
v
alue
.
If
the
least
n
umber
of
iter
ations
w
ere
activ
ated
(
p
2
=
tr
ue
),
the
island
that
has
completed
its
task
will
find
and
help
another
island
which
has
the
least
n
umber
of
iter
ations
.
Otherwise
,
if
the
poorest
fitness
w
ere
activ
ated
(
p
2
=
f
al
se
),
the
island
that
has
completed
its
task
will
find
and
help
another
island
that
has
the
lo
w
est
fitness
v
alue
.
Let
iter
ation(s)
retur
n
the
current
iter
ation
of
island
s
and
fitness
retur
n
the
best
current
TELK
OMNIKA
V
ol.
16,
No
.
6,
December
2018
:
2747
2755
Evaluation Warning : The document was created with Spire.PDF for Python.
TELK
OMNIKA
ISSN:
1693-6930
2750
fitness
of
island
s
.
s
=
(
ar
g
min
(
iter
ation
(
u
:
8
U
))
;
if
(
p
1
=
tr
ue
)
ar
g
min
(
f
itness
(
u
:
8
U
))
;
other
w
ise
(2)
The
third
par
ameter
is
individual
pic
king
method
.
This
par
ameter
deter
mines
the
w
a
y
of
pic
king
individuals
from
an
island
that
going
to
be
helped
(reinf
orced).
There
are
tw
o
w
a
ys
of
pic
king
individuals
.
Th
e
first
(
p
3
=
tr
ue
)
is
b
y
pic
king
the
best
individual
from
helped
island
and
duplicating
it
into
as
man
y
as
the
individual
n
umbers
of
a
population.
The
second
(
p
3
=
f
al
se
)
is
b
y
pic
king
the
best
population
from
helped
island
or
usually
the
last
population
fr
om
it.
The
second
w
a
y
has
the
consequence
of
the
best
individual
b
uc
k
et
in
the
master
ha
ving
to
be
changed
into
the
best
population
b
uc
k
et.
In
other
w
ords
,
the
master
island
m
ust
k
eep
the
best
population
from
e
v
er
y
island
r
ather
than
the
best
individual.
3.
Resear
c
h
Method
3.1.
UCTP
in
T
elk
om
Univer
sity
The
UCTP
in
T
elk
om
Univ
ersity
is
a
student-le
v
el
timetab
ling
(student
sectioning)
prob
lem.
As
ref
erenced
from
T
omas
Muller
et
al.,
Student
sectioning
is
the
prob
lem
of
assigning
students
to
classes
of
a
subject
while
respecting
individual
st
udent
requests
along
with
additional
constr
aints
.
F
or
e
xample
,
a
student
cannot
attend
tw
o
classes
which
o
v
er
lap
in
time[7].
Theref
ore
,
the
fulfillment
of
each
of
the
students’
pref
erence
is
encour
aged
as
w
ell.
This
approach
has
been
implemented
in
pre
vious
researches
[10,
5]
in
T
elk
om
Univ
ersit
y
and
other
univ
ersities
such
as
Purdue
[8]
and
W
ater
loo
Univ
ersity
[3].
Lik
e
an
y
other
UCTP
,
T
elk
om
Univ
ersity
is
a
minim
um
optimization
prob
lem.
The
objectiv
e
is
to
minimiz
e
all
the
predefined
constr
aint
violation
f
or
each
of
the
teaching
e
v
ents
.
Such
that
a
teaching
e
v
ent
is
an
e
v
ent
of
a
lecturer
l
in
a
room
r
at
time
t
class
c
f
or
a
set
of
students
S
.
Which
is
defined
b
y
f
ollo
wing
notation:
e
=
(
l
;
r
;
t;
c;
S
)
(3)
With
ref
erence
from
pre
vious
researchers
[10,
5,
2],
this
research
used
tw
o
types
of
constr
aints
,
the
hard
and
the
soft
constr
aints
.
Hard
constr
aint
(HC)
is
a
constr
aint
that
m
ust
be
satisfied.
Soft
constr
aint
(SC)
ought
more
to
be
satisfied
to
impro
v
e
the
quality
of
the
timetab
ling.
As
the
constr
aints
are
w
or
king
in
the
same
UCTP
cases
,
the
types
of
HCs
and
SCs
used
f
or
this
research
are
e
xactly
the
same
as
the
pre
vious
research
conducted
b
y
Suy
anto
[10]
and
Gozali
[5].
Let
i
=
1
::
5
be
hard
constr
aints
and
i
=
6
::
12
be
soft
constr
aints
.
As
hard
constr
aints
m
ust
be
f
ar
bigger
r
ather
than
soft
constr
aints
,
the
objectiv
e
function
becomes:
Minimiz
e
V
=
5
X
i
=1
M
V
i
+
12
X
i
=6
V
i
(4)
where
V
is
a
violation
v
alue
f
or
each
i
constr
aint.
The
symbol
M
means
a
v
er
y
big
n
umber
so
that
M
V
i
is
m
uch
larger
than
V
i
.
With
regard
to
the
T
elk
om
Univ
ersity
UCTP
in
this
research,
the
HC
v
alues
are
set
m
uch
higher
than
SC
so
that
the
GA
will
pr
ior
itiz
e
poor
fitness
more
because
of
HC
.
By
treating
the
SCs
this
,
the
y
became
the
f
ocus
after
all
HCs
ha
v
e
been
satisfied.
The
penalty
v
alue
of
SCs
is
designed
to
be
propor
tional
to
its
influence
.
F
or
e
xample
,
as
a
lectur
ing
e
v
ent
has
a
lecturer
and
around
50
students
,
the
r
atio
of
lecturer
SC
to
student
SC
should
be
1:50.
3.2.
RIMGA
f
or
UCTP
Directed
chromosome
will
be
used
f
or
the
chromosome
representation.
Directed
chromosome
mimics
the
real-w
or
ld
representation
which,
in
this
case
,
is
the
univ
ersity
timetab
ling
representation.
Reinf
orced
Island
Model
Genetic
Algor
ithm
to
Solv
e
Univ
ersity
...
(Alfian
Akbar
Gozali)
Evaluation Warning : The document was created with Spire.PDF for Python.
2751
ISSN:
1693-6930
Thus
,
the
chromosome
,
as
sho
wn
in
Figure
3,
is
the
representation
(mapping)
from
the
real-w
or
ld
timetab
le
.
Figure
3.
Directed
chromosome
Fur
ther
more
,
since
the
AIMGA
model
w
as
der
iv
ed
from
the
single
model,
the
AIMGA
core
(individual
reproduction
and
e
v
aluation
of
fitness)
w
as
the
same
as
the
single
model.
The
AIMGA
implemented
Inf
or
med
GA
core
,
which
applied
local
search
and
only
used
directed
m
utation
o
v
er
crosso
v
er
[10].
Der
iv
ed
from
pre
vious
researchers
[5,
10],
this
r
esearch
also
uses
tw
o
stages
of
the
inf
or
med
GA,
class-le
v
el
timetab
ling
(stage
1)
and
student-le
v
el
timetab
ling
(stage
2).
The
significant
diff
erence
betw
een
these
tw
o
stages
lies
in
stage
1
which
e
xcludes
student
constr
aints
.
That
is
because
the
student
e
v
aluation
time
process
took
m
uch
longer
time
due
to
a
large
n
umber
of
students
.
The
ne
xt
stage
will
include
student
constr
aints
.
Directed
m
utation
which
is
an
additional
w
a
y
to
impro
v
e
the
process
efficiency
of
the
GA
w
as
also
used.
4.
Result
and
Discussion
This
research
e
xper
iment
has
three
goals:
to
implement
the
AIMGA
concept
into
the
T
elk
om
Univ
ersity
UCTP
,
analyz
e
RIMGA
par
ameters
,
and
compare
the
RIMGA
with
the
ordinar
y
AIMGA.
W
e
conduct
the
first
three
e
xper
iments
with
the
regard
of
implementing
and
analyzing
RIMGA
par
ameters
,
while
the
last
e
xper
iment
is
f
or
compar
ing
with
con
v
entional
AIMGA.
Dataset
used
in
this
research
w
as
T
elk
om
Univ
ersity
Engineer
ing
School,
a
f
aculty
in
T
elk
om
Univ
ersity
,
at
odd
semester
f
or
enrollment
y
ears
2011/2012.
This
f
aculty
had
char
acter
istics
as
e
xplained
in
T
ab
le
1.
T
ab
le
1.
Inf
or
med
GA
Scheme
No
Attrib
utes
V
alue
1
Classes
813
2
Rooms
80
3
Students
6570
4
A
v
er
age
n
umber
of
classes
per
students
6.481
5
A
v
er
age
n
umber
of
meetings
per
class
2.752
6
Lecturers
316
7
A
v
er
age
classes
per
lecturers
2.582
4.1.
Result
and
Discussion
This
section
e
xplains
the
test
scenar
io
which
aims
to
test
three
reinf
orced
state
par
ameters:
the
island
state
,
island
pr
ior
ity
and
individual
pic
king
method.
Each
test
will
be
r
un
thr
ice
with
5
islands
[5]
in
sequence
.
This
n
umber
is
considered
sufficient
because
there
are
already
statistically
significant
diff
erences
b
y
using
the
3
test
results
.
The
specifications
of
the
computer
used
f
or
this
test
are
tw
o
computers
with
Core
i5
and
4GB
memor
y
,
one
computer
with
Core2Duo
(2.8
GHz)
TELK
OMNIKA
V
ol.
16,
No
.
6,
December
2018
:
2747
2755
Evaluation Warning : The document was created with Spire.PDF for Python.
TELK
OMNIKA
ISSN:
1693-6930
2752
and
2
GB
memor
y
,
and
tw
o
computers
with
Core2Duo
(2.6
GHz)
an
d
1
GB
memor
y
b
ut
from
diff
erent
man
uf
acturers
.
W
e
use
fitness
and
e
x
ecution
time
as
the
e
v
aluation
par
ameters
.
4.1.1.
Island
State
T
est
T
ab
le
2
sho
ws
the
results
f
or
the
island
state
test.
F
rom
this
tab
le
,
ignor
ing
the
island
state
is
better
than
consider
ing
the
island
state
.
By
ignor
in
g
the
island
state
,
more
than
one
f
aster
sla
v
e
can
help
the
slo
w
est
sla
v
e
so
that
the
slo
w
est
sla
v
e
can
reach
its
stopping
cr
iter
ia
sooner
.
The
result
is
in
line
with
the
computer
specifications
of
the
islands
that
are
v
er
y
diff
erent.
Theref
ore
,
balancing
the
process
b
y
consider
ing
the
island
state
is
not
as
eff
ectiv
e
as
ignor
ing
it.
Thus
,
the
ne
xt
test
scenar
io
used
the
ignor
ing
of
the
island
state
configur
ation.
T
ab
le
2.
Island
State
T
est
Result
T
est
Number
Ignoring
island
state
Considering
island
state
Best
Dur
ation
Best
Dur
ation
Fitness
(hh:mm:ss)
Fitness
(hh:mm:ss)
1
11520
16:55:59
11900
18:48:36
2
11950
16:52:33
11480
18:53:38
3
11840
16:30:32
11940
18:48:41
A
vera
g
e
11770
16:46:21
11773
18:50:18
4.1.2.
Island
Priority
T
est
T
ab
le
3
sho
ws
the
test
result
f
or
this
scenar
io
.
It
indicates
that
f
or
the
dur
ation
of
e
x
ecution
and
best
fitness
,
and
the
least
n
umber
of
iter
ations
ga
v
e
better
result
r
ather
than
the
poorest
fitness
.
The
dur
ation
inter
v
al
betw
een
them
is
just
around
9
min
utes
.
The
slo
w
er
sla
v
e
with
the
least
n
umber
of
iter
ations
is
requires
more
help
so
f
ar
.
This
condition
sho
ws
that
the
GA
perf
or
mance
depends
more
on
the
current
gener
ation
than
fitness
.
Thus
,
k
eeping
the
slo
w
er
island
with
f
e
w
er
gener
ations
w
ould
be
better
than
poor
fitness
.
The
result,
which
places
the
current
gener
ation
abo
v
e
fitness
,
means
that
population
in
each
island
is
ab
le
to
k
eep
their
div
ersity
.
It
is
easier
f
or
the
island
to
a
v
oid
the
local
optim
um
tr
ap
due
to
its
div
ersity
.
F
or
this
case
,
theref
ore
,
adding
gener
ations
is
better
than
increasing
fitness
.
Finally
,
according
to
the
result,
the
ne
xt
test
will
use
the
least
n
umber
of
iter
ations
.
T
ab
le
3.
Island
Pr
ior
ity
T
est
Result
T
est
Number
The
least
iteration
n
umber
s
The
w
or
st
fitness
Best
Dur
ation
Best
Dur
ation
Fitness
(hh:mm:ss)
Fitness
(hh:mm:ss)
1
11520
16:55:59
13310
17:20:29
2
11950
16:52:33
12410
16:51:01
3
11840
16:30:32
12130
16:34:14
A
vera
g
e
11770
16:46:21
12616
16:55:15
Reinf
orced
Island
Model
Genetic
Algor
ithm
to
Solv
e
Univ
ersity
...
(Alfian
Akbar
Gozali)
Evaluation Warning : The document was created with Spire.PDF for Python.
2753
ISSN:
1693-6930
4.1.3.
Individual
Pic
king
Method
T
est
The
test
result
f
or
individual
pic
king
method
test
is
sho
wn
in
T
ab
le
4.
It
is
sho
wn
in
this
tab
le
that
the
best
population
cop
y
is
super
ior
to
the
b
est
individual
duplication
in
fitness
v
alue
.
By
consuming
about
21
more
min
utes
in
e
x
ecution
time
,
the
best
population
cop
y
produced
a
fitness
v
alue
11,650.
This
w
as
better
than
the
12,430
from
the
best
individual
duplication.
T
ab
le
4.
Individual
Pic
king
Method
T
est
Result
T
est
Number
The
best
population
cop
y
The
best
individual
duplication
Best
Dur
ation
Best
Dur
ation
Fitness
(hh:mm:ss)
Fitness
(hh:mm:ss)
1
11520
16:55:59
12750
16:32:50
2
11950
16:52:33
12440
16:15:05
3
11840
16:30:32
12100
16:28:54
A
vera
g
e
11770
16:46:21
12430
16:25:36
Pic
king
the
best
population
is
better
r
ather
than
cop
ying
the
best
individual
into
a
population
mean
f
or
this
case
,
the
gener
ation
trend
still
tends
to
tr
ap
in
a
local
optim
um.
Thus
,
pic
king
a
whole
best
population
and
contin
uing
the
process
with
it
will
help
the
island
that
did
not
complete
its
task
to
increase
its
div
ersity
.
This
par
ameter
,
which
is
similar
to
the
Island
Pr
ior
ity
T
est
e
xplanation,
is
also
e
xper
imental.
The
T
empor
al-Salient
Scheme
[12]
could
be
implemented
to
direct
the
solutions
this
prob
lem.
Ho
w
e
v
er
,
lik
e
the
pre
vious
e
xample
,
the
research
uses
island
order
instead
of
the
T
empor
al-Salient
Scheme
f
or
the
sak
e
of
time
efficiency
.
4.1.4.
Comparison
T
est
of
RIMGA
The
last
e
xper
iment
is
to
compare
the
perf
or
mance
of
the
AIMGA
and
the
RIMGA.
The
goal
of
this
process
is
to
analyz
e
ho
w
f
ar
the
RIMGA
could
beat
the
AIMGA
in
perf
or
mance
.
The
test
w
as
r
un
in
tw
o
phase:
maxim
um
fitness
and
time
constr
aint.
Maxim
um
fitness
constr
aint
test
w
as
done
to
compare
their
time
perf
or
mance
to
r
each
same
fitness
and
vice
v
ersa.
Done
in
the
same
w
a
y
as
the
pre
vious
test,
this
test
w
as
done
in
three
consecutiv
e
times
to
obtain
the
a
v
er
age
.
T
ab
le
5-Dur
ation
sho
ws
the
test
result
with
same
maxim
um
fitness
.
The
ter
minate
condition
of
this
tr
ial
is
fitness=10000.
T
ab
le
5
indicates
that
AIMGA
e
x
ecution
time
w
as
almost
t
wice
of
the
RIMGA.
T
ab
le
5.
Maxim
um
Fitness
Limitation
T
est
Result
Model
Duration
(hh:mm:ss)
Fitness
RIMGA
16:55:59
9980
AIMGA
24:00:00
9980
T
ab
le
5-Fitness
sho
ws
the
result
of
the
24-hour
test.
When
both
r
an
f
or
24
hours
,
there
w
as
no
significant
diff
erence
betw
een
the
RIMGA
and
the
AIMGA
in
gener
al.
W
e
can
theref
ore
conclude
that,
o
v
er
all,
the
implementation
of
the
Reinf
orced
function
impro
v
es
the
AIMGA
perf
or
mance
in
obtaining
a
good
result.
In
addition,
the
result
will
be
the
same
if
the
y
still
ha
v
e
the
same
GA
core
.
TELK
OMNIKA
V
ol.
16,
No
.
6,
December
2018
:
2747
2755
Evaluation Warning : The document was created with Spire.PDF for Python.
TELK
OMNIKA
ISSN:
1693-6930
2754
5.
Conc
lusions
This
resear
c
h
has
sho
wn
that
the
AIMGA
can
solv
e
the
T
elk
om
Univ
ersity
UCTP
with
acceptab
le
accur
acy
represented
b
y
the
GA
fitness
v
alue
.
Fur
ther
more
,
b
y
implementing
the
RIMGA,
the
timetab
ling
result
accur
acy
increases
in
perf
or
mance
to
ne
xt
le
v
el.
This
ne
w
approach
can
obtain
the
same
result
as
the
AIMGA
in
a
f
aster
(about
twice)
e
x
ecution
time
with
a
some
what
similar
eff
ect
when
the
y
r
un
under
the
same
time
constr
aint.
Thus
,
the
reinf
orced
state
is
an
e
xcellent
choice
if
w
e
w
ant
to
obtain
good
results
more
quic
kly
.
The
optim
um
configur
ation
par
ameters
of
the
RIMGA
f
or
T
elk
om
UCTP
are
Island
State:
ignored,
Island
Pr
ior
ity:
the
least
iter
ation
n
umbers
,
and
Individual
Pic
king:
the
best
population
cop
y
.
Although
this
study
f
ocuses
on
the
T
elk
om
Univ
ersity
UCTP
,
the
findings
ma
y
w
ell
ha
v
e
a
bear
ing
on
other
UCTPs
with
similar
char
acter
istics
as
the
T
elk
om
Univ
ersity
UCTP
.
T
ak
en
together
,
this
research
confir
ms
that
the
RIMGA
can
solv
e
the
UCTP
with
scalability
issues
.
This
study
also
contr
ib
utes
additional
e
vidences
that
encour
age
the
use
o
f
the
reinf
orced
function
in
the
AIMGA.
The
results
of
the
e
xper
iment
could
ser
v
e
as
the
basis
f
or
future
researchers
in
settin
g
its
par
ameters
.
In
addition,
fur
ther
studies
still
need
to
be
conducted
f
or
the
RIMGA
f
or
better
real-w
or
ld
implementation.
Fur
ther
studies
on
its
netw
or
k
cost
is
also
necessar
y
to
in
v
estigate
its
real
computational
time
and
cost.
The
RIMGA
also
still
needs
to
be
implemented
in
a
simpler
prob
lem
to
study
the
correct
consider
ations
in
the
par
ameter
adjustment.
Ac
kno
wledgments
Indonesia
Endo
wment
Fund
f
or
Education
(LPDP),
a
scholarship
from
Ministr
y
of
Finance
,
Repub
lic
of
Indonesia,
suppor
ts
this
w
or
k.
W
e
conduct
this
research
while
at
Gr
aduate
School
of
Inf
or
mation,
Production,
and
Systems
,
W
aseda
Univ
ersity
,
J
apan.
Ref
erences
[1]
N.
K.
Ar
y
ani,
A.
Soepr
ijanto
,
I.
M.
Y
.
Negar
a,
and
M.
Sy
ai’in.
Economic
dispatch
using
quantum
e
v
olutionar
y
algor
ithm
in
electr
ical
po
w
er
system
in
v
olving
distr
ib
uted
gener
ators
.
Inter
national
Jour
nal
of
Electr
ical
and
Computer
Engineer
ing
,
7(5):2365
2373,
Oct.
2017.
[2]
K.
Banczyk,
T
.
Boinski,
and
H.
Kr
a
wczyk.
P
ar
allelisation
of
genetic
algor
ithms
f
or
solving
univ
ersity
timetab
ling
prob
lems
.
In
Inter
national
Symposium
on
P
ar
allel
Computing
in
Electr
ical
Engineer
ing
(P
ARELEC’06)
,
pages
325–330,
Sept
2006.
[3]
M.
W
.
Car
ter
.
A
comprehensiv
e
course
timetab
ling
and
student
scheduling
system
at
the
univ
ersity
of
w
ater
loo
.
In
E.
Bur
k
e
and
W
.
Erben,
editors
,
Pr
actice
and
Theor
y
of
A
utomated
Timetab
ling
III:
Third
Inter
national
Conf
erence
,
P
A
T
A
T
2000
K
onstanz,
Ger
man
y
,
A
ugust
16–18,
2000
Selected
P
apers
,
pages
64–82,
Ber
lin,
Heidelberg,
2001.
Spr
inger
Ber
lin
Heidelberg.
[4]
M.
Gare
y
and
D
.
S
.
Johnson.
Computer
and
Intr
actability
.
W
.H.
F
reeman
and
Compan
y
,
Ne
w
Y
or
k,
1979.
[5]
A.
A.
Gozali,
J
.
Tir
ta
w
angsa,
and
T
.
A.
Basuki.
Asynchronous
Island
Model
Genetic
Algor
ithm
f
or
Univ
ersity
Course
Timetab
ling.
In
Proceedings
of
the
10th
Inter
national
Conf
erence
on
the
Pr
actice
and
Theor
y
of
A
utomated
Timetab
ling
,
pages
179–187,
Y
or
k,
2014.
P
A
T
A
T
.
[6]
Q.
K
otimah,
W
.
F
.
Mahm
udy
,
and
V
.
N.
Wija
y
anin
g
r
um.
Optimization
of
fuzzy
tsukamoto
membership
function
using
genetic
algor
ithm
to
deter
mine
the
r
iv
er
w
ater
.
Inter
national
Jour
nal
of
Electr
ical
and
Computer
Engineer
ing
,
7(5):2838
2846,
Oct.
2017.
[7]
T
.
Muller
and
K.
Murr
a
y
.
Comprehensiv
e
approach
to
student
sectioning.
Annals
of
Oper
ations
Research
,
181:249–269,
2010.
[8]
K.
Murr
a
y
,
T
.
Muller
,
and
H.
Rudo
v
a.
Modeling
and
Solution
of
a
Comple
x
Univ
ersity
Course
Timetab
ling
Prob
lem.
In
E.
K.
Bur
k
e
and
H.
Rudo
v
´
a,
editors
,
Pr
actice
and
Theor
y
of
A
utomated
Timetab
ling
VI
,
n
umber
3867
in
Lecture
Notes
in
Computer
Science
,
pages
189–209.
Spr
inger
Ber
lin
Heidelberg,
A
ug.
2006.
DOI:
10.1007/978-3-540-77345-0
13.
[9]
A.
W
.
Pr
atama,
A.
Buono
,
R.
Hida
y
at,
and
H.
Harsa.
Estimating
par
ameter
of
nonlinear
bias
correction
method
using
nsga-ii
in
daily
precipitation
data.
TELK
OMNIKA
,
16(1):241
249,
Reinf
orced
Island
Model
Genetic
Algor
ithm
to
Solv
e
Univ
ersity
...
(Alfian
Akbar
Gozali)
Evaluation Warning : The document was created with Spire.PDF for Python.
2755
ISSN:
1693-6930
F
eb
.
2018.
[10]
Suy
anto
.
An
Inf
or
med
Genetic
Algor
ithm
f
or
Univ
ersity
Course
a
nd
Student
Timetab
ling
Prob
lems
.
Ar
tificial
Intelligence
Soft
Computing
Lecture
Notes
of
Computer
Science
,
Spr
inger
Ber
lin
Heidelberg
,
6114:229–236,
2010.
[11]
F
.
Titel
and
K.
Belarbi.
A
mix
ed
binar
y-real
nsga
ii
algor
ithm
ensur
ing
both
accur
acy
and
inter
pretability
of
a
neuro-fuzzy
controller
.
Inter
national
Jour
nal
of
Electr
ical
and
Computer
Engineer
ing
,
7(5):2614
2626,
Oct.
2017.
[12]
S
.
Tsutsui,
Y
.
Fujimoto
,
and
A.
Ghosh.
F
or
king
genetic
algor
ithms:
Gas
with
search
space
division
schemes
.
Ev
olutionar
y
Computation
,
5(1):61–80,
March
1997.
[13]
Umar
,
Firdaus
,
A.
Soepr
ijanto
,
and
O
.
P
enangsang.
Optimal
e
xpenditure
and
benefit
cost
based
location,
siz
e
and
type
of
dgs
in
microg
r
ids
systems
using
adaptiv
e
real
coded
genetic
algor
ithm.
TELK
OMNIKA
,
16(1):10
17,
F
eb
.
2016.
[14]
D
.
Whitle
y
,
S
.
Rana,
and
R.
B
.
Hec
k
endor
n.
Island
Model
Genetic
Algor
ithms
and
Linear
ly
Separ
ab
le
Prob
lems
.
Lecture
Notes
in
Computer
Science
,
Spr
inger
Ber
lin
Heidelberg
,
1305:109–125,
1997.
TELK
OMNIKA
V
ol.
16,
No
.
6,
December
2018
:
2747
2755
Evaluation Warning : The document was created with Spire.PDF for Python.