+.
-.
L-+l
Proceeding Presentasi Hasii Penelitian Hibah Prograrn Desentralistrsi, Sentralisasi clan
l'libah lntcrnal L,npas'Iahun 20 l4
Pemodelan ArtiJicial Immune System Terdistribusi Berbasis Clonal Selection (Studi Kasus Persoalan Optimasi Traveling Sales Person Problem)
Oleh: Ayi Purbasari, S1'.MT Fakultas teknik Uuivcrsitas Pasundat.t J1. Dr. Setiabudhi No. 193 Bandung
Pendahuluan Arti/iciul Inunune System (AIS) (Timmis & Castro. 2002), merupakan salah satu bioitrspirecl contptLtittg )'allg terinspirasi dari perilaku sisteln itnnn yang bersilat adaptil dan self-orguttizirig. Terdapat empat teori utama sistem itnuu sebagai landasan AIS, melahirkan empat kelompok besar; yaitu algoritma seleksi negatif (Forrest & Reauchernin, 1997) untuk penyelesaian deteksi intrusi (Dasgupta, 1999). algorihna seleksi clonal (Castro & Zuben, 2002) untuk pengenalan pola dan optimasi, algoritma jaringan irnun (Timmis & Castro, 2002) dan algoritma sel dendrit (Greensmith J,
2008) untuk klasifikasi. Namun
dengan
semakin banyaknya algoritma AIS sebagai altematif solusi, AIS dituntut menghasilkan perfbrma solusi yang semakin baik untuk persoalan yang semakin kornpleks. Para peneliti AIS tnemandang AIS sebagai i n t e r d i sp I i n cr ty p er sp e c trle (Tirnm i s, Andrer'v,
Owen,
& Clark ,
2008) (Timmis,
2006)
(Tirnn-ris &. Hart, 2005), dimana peranan pernodelan diperlukan utrtuk pemahaman tentang aspek-aspek komputasi dari sistem imun.
A. B., 2005)
untuk meuyelesaikan persoalatt kompeks. Penelitian ini berlr-t1tian sebagai berikut:
1. Membangun model paralel
bt gct P e n c I iti cut
Un
i
l et's
i t tt
sP
tts un d t r n
Yatlg
niempertitnbangkan perilaku terdistribusi clari sistetl imutr. 2. Mengetahui properti dari rnodel paralel yang mempengaruhi kinerja komputasi. 3. Mengetahui apakah model paralel yang dibangun berpotensi rnenghasilkan tnodel komputasi yang lebih baik dari sisi kinerja komputasi (waktu komputasi). Tinjauan A rtiJic iu I Immu n e S),stem ArtiJic i ul I m mun e S)'ste,n De Castro dan Von Z:tben (Castro & Zuben, 2002) mengernttkakan AIS sebagai '-o conrpttttttiortul s;,-stem ltusecl uport tnetttphor't
q/ lhe biological intntune
.fi''\tettt ".
Perkembangan AIS tidak lepas dari teori imuu yang menyertainya. Error! Reference source rnet'augkum
perkerr"rbaugan AIS dan para permarkasauya
Tabel 1 Pemrakarsa
I rti/icia I Inunune Systent Awal porerapan
feoli
AIS
lmnutne Ne ttvork
lntmttne
Ilur.rt dan
Moclel jaringan
l\'etvrtrk
Cookc,
irnult
Pernarkasa,/
-I'ahun
dilanjut
(Jeme, 74)
Tirmnis dan
Ncal. 1995
Negdtiv ,9election
mengungkapkan
gagasan bairrva sistetn imuu bersifat inhererrlly
L em
rrenjadi potensi rlenghasilkan algoritma AIS terclistribr-rsi cleugan per[ortra yarlg lebih baik. Dengan clemikian. diperlukan penelitian yang fokr-rs kcpada petnodelan terdistribr.rsi AIS
not found.di barvah ini
Algoritma seleksi clonal tnerupakan salah satu algoritrna terinspirasi sistern imun yarg didasari oleh teori Cional Selection dari Bumet (Timrnis & Castro, 2002). Algoritrna ini digunakan untuk penyelesaian optimasi dengan pendekatan heuristik dan berbasis populasi. Seperti halnya pendekatan berbasis populasi pada urlult-lnya, algoritma ini membutuhkan waktu komputasi yang tidak sedikit (Tirnrnis & Castro. 2002). Di lain sisr. Watkins (Watkins, Bi, & Phadke, 2003)
(Watkins
ltutullal , lraik dalam koutrol, respolls. proses rnaturasi, clan tnanajemen populasi sel. Hal ini
tu
C
lontl
Se
I
ectiott
Negatit'e Se lection
Forrcst dkk, 1994
(.lonol
cle C'astro
,Selectiott
dan Von
M endeteksi
manipulasi data yang discbabkan oleh virus di sistetl kotnputer Pcrsoalur Dclgenalan pola
t09
f
..-'-ffi-.-
.&-}, )
\&lK/
ri
Proceecling Presenlasi Hasil I,cnelitian I libah prosrant Desentralisasi. Sentralisasi dan FIibah intenral Iinpas Tahun 2014 (Burnet, 59)
Do n.qer Theo ( I
ry
Zuben. 2002
optilnasi rnultirnoclal.
Dendrit Cell
Greenstnillr
tllgorithnt.s
dan
Matzinger 994)
Clon al
clan lirngsi
1.
Aickelin. r00.+
S electio
Clonel
Klasifikasi
rt Algo rith nt
Selectiort Algorithm cliinspirasi dari teori Clonul Selection tentang imunitas yang diperlukan (acquired irnmunity). Teori ini
cligagas Bumet tentang perilaku clan kernampuan dari antibodi pada sistern inrlri ctctlttirecl. Ltspirasi itu seltdiri datang clari prinsip seleksi llatural clari teori Danuvinian. bahrva antigen r.nemilih lirnlbsit yang bersesuaian, baik sel B atau sel T. Ketika
limtbsit terpilih, maka akan terikat ke daerah antigenik dan sel akan memperbanyak cliri clan melebur ke dalarn sel plasma atau tneubeutuk sel memori. Sel plasrna r ernilik',vaktu hidup yang pendek, sernentara sel rnemori hidup lebih larna dan berperan
untuk antisipasi ketika terjadi
- -?-...r:-^-
--e
I
--I-.-^
€
ee Zr
peristir.va
I
il t:r iril
i' I,:,
iAr lii
;t: lr,',*Jl.l
i.
i' i:i,:; llrl i
Beberapa pendekatan paralelisasi CSA sudah dilakukan oleh peneliti lain Sebagai penugasas ar,val, Watskin (Warkins, Bi, & phaclke. 2003) tidak spesifik untuk algoritma seleksi clonal dan diterapkan untuk persoalan pengenalan
pola. Flongbing (Hongbing, Sicheng,
&.
Jianguo, 2010) menerapkan paralelisme CSA
urrtuk prediksi struktur protein dengan menegunakan Open-Mpi. Sedangkan Dabrowski dan Kobale (Dabrorvski & Kubale,
1
Tata Keria Pada penelitian
ini,
digunakan pendekatan
mengacu kepada Conceptuol /ratnework yang diusung oleh Stepney (Stepney, Smrth, &
Timrnis, 2005) dengan dipadukan clengan prinsip desain paralel dari Bantev (Banrey, 2007) dapat diiihat pada Gambar 2 cli barvah
€>e LL
Gambar
i. i
2008) nienggunakan kornputasi CSA paraiel untuk persoalan per.varnaan graf-.
pengenalan antigen yang sama. (Castro & Zuben, 2002) (Brownlee, 2009) (Brownlee, 2008).
kemudian diganti dengan yang baru secara Secara diagramatis. algorihna seieksi clonal dapat digambarkan seperti pada Gambar
acak.
1111.
fI
Seleksi clonal (Castro &
Zuben,1999)
Algoritma seleksi clonal merupakan algoritma dari inspirasi peristiwa seleksi clonal. prinsip dasar algoritma ini adalah heuristik berbasis populasi. Terdapat populasi antibodi N, masing-masing menetapkan solusi acak untuk proses optimasi. Pada setiap iterasi, antibodi terbaik dipilih, kloning, dan bermutasi untuk membangun suatu calon populasi baru.
Antibodi baru kemudian dievaluasi
dan
persentase tertentu dari antibodi terbaik ditambahkan ke populasi asli. prosentase antibodi terburuk dari generasi sebelumnya
110
Gambar 2 Pendekatan Con ceptual .t'rurnework, merupakan frcrmework yang diusung oleh stepney (Stepney, Smith, &
Timmis, 2005 ) utlluk bi o -in sp rerl ett gin eri n g pada umulnnya dan sistem irnun pada i
khususnya. Sedangkan
e
aspek-aspek
perancangan komputasi paralel diusung
Banrey (Bamey, 2007)^ terdiri dari: dekomposrsi. dimana persoalan dapat
Lembogrt PettaIition IJnit,ersitus Pcrsundort
-.-
*r&l
Proceetling Presentasi Hasil Pcnclitian Hibah Program Desentralisrsi, Sentralisasi clan Hibalr Internal Unpas Tahun 201.1
didekomposisi berdasarkan data atau fungsi/task; komunikasi, antar task; sinkronisasi antar proses paralel tersebut diperoleh; dependensi data, memperhatikan apakalr data bersifat dependen; locttl bctlcncilrg.
emperhatikan apakair pendistribusian j urnlah pekerjaan yang sama untuk rneminimasi la.r,t idle; sedangkan gronuluritu.s' merupakan
Tabel 2 Inspirasi seleksi clonal Elemcn kor.nputasi
l]lcmen sistern irntur
inspilasi rrulti-
Eler.nen sistcrn irnun inspilasi
single-
nonr r lafi rrr
Elernen penll oscs
I3agian-bagian
Nodus llrnla:
l'ripulirsi
[)ata
n-r
terclin
scl
kurnpulan
u
Iang dibangun di tiap-tiap noclus 1imlh. sehirigga tcrdrpat rlulti-
perbandingan antara komputasi terhadap
clalarn
noclus linr1i:
I'opulasi
terdiri
kurnpulan scl B l,irng dibangun di noclus limla
tersebut. tcrdapat
sc'hingga
population
tunggal:
komunikasi. Kornunikasi
Berikut gambaran
kerja
tata
penelitian
Mengirirnkan infinnasi
M cngirirnkan
inlbmrasi pt4rulasi
populasi
terhaik-
rnelalui mernorv cellclalarn scbuah notlus limfi (inhat.
rnelalui
lncrnu-v cell. antar
disertasi:
notlus
lirrh.
terbaik"
Model komputasi paralel terinspirasi seleksi clonal Berdasarkan inspirasi, dilakukan dekomposisi data dan fungsi serta penetapan komunikasi antar task. Berdsarkan populasi, terdapat dua model yaitu multi-population dan singlepopulcttir,ttt.
Gambar 3 Tata kerja penelitian disertasi
Penelitian
ini
memberi kontribusi
berdasarkan
untuk algoritma terinspirasi seleksi clonal
:
dalam
bidang sains dan bagian engineering. Bagian sains terkait dengan komputasi, terutama ditemui ketika membahas teori dasar Artificial Immune System, khususnya bagian seleksi clonal, dengan mengamati perilaku interaksi
dan terdistribusi tanpa kontrol
Seclangkan
komnnikasi, yaitu master-slave dan multico mmr.tni cation, sehingga mendapatkan empat kelompok model kornputasi paralel. Tabel 3 berikut ini adalah model komputasi paralel Tabel 3 Model komputasi paralel untuk i seleksi clonal algoritma terin Narna rnodel (inspirasi
populasi ,'rnodel kornunikasi)
Dapat dilakukan parlisi ptpulas:i alv a l'.)
terpusat,
menghasilkan model dan algoritma komputasi paralel. Bagian engineering diternui ketika mengaplikasikan model dan algoritma ini pada persoalan, dalam hal ini persoalan optimasi dengan studi kasus persoalan Traveling Salesman Problem (TSP).
Global single-population mastcr-slale rnodcl. S inglc-populati on coarse-graincd rnoclcl M ultiple-population master-slavc modcl coalse-qrained rnodel
Dapat dilakukan parrisi populasi rL.h ir')
Ya
Ya
Tidak
Ti,LL
Ya
'l'idak -l
Ya
Tidak
idak
Ya -l-idak
Tidak
Ya l idak
Hasil dan Pembahasan Hasil dari penelitian ini berupa pemetaan
inpirasi seleksi clonal dengan elemen komputasi paralel, empat model komputasi para,lel, metode penerapan algoritma paralel untuk kasus optimasi kombinatorial TSP, dan
verifikasi dengan eksperimen
yang
memperlihatkan best cost dan waktu eksekusi. Error! Reference source not found. berikut ini rangkuman inspirasi seleksi clonal dipetakan dengan elemen komputasi:
L em
b cLgct
P en cl iti
an
Lin i y ersi
t
u
s Pu
s Lm
d ott
111
Proceeding Presentasi Hasil I']cnelitian Hibah Progranr Desentralisasi. Sentralisasi clan Hibah Internal lJnpas fahun 20 I 4
:
T+
operasi seleksi clonal, maka model ini diberi nama s ingle -p opula tion coars e-grained model.
i
:
i
i
!.u.*
Model ini didetailkan dengan
i
:i
,] I
qi,r
I ^,u"
+
$,"r
:i
model
komputasi yang dapat dilihat pada Error! Reference source not found. di bawah ini:
L i i
;I ,
i
1"l1.i:*:, l
Ket. i.\iti:i;::::
rr,!r'r.?MLL
titr\\\\
Komunikasi antar
Gambar 4
G I o bo
I
s
in g I e-p
cryt
t r
I rr
ri
ort
trt u s
ter--
Garnbar 6 Model kornputasi Multi-poptrlation clengan komunikasi
slaye nrctlel
Pada rnodel ini, populasi disiapkan oleh proses ntoster, kemudian dikirirn ke proses sluye. Selanjutnya, tiap ,slave melakukan
operasi seleksi clonai berupa evaluasi (perhitungan u//inity), seleksi, kloning dan lripermutasi, serta replocemeilt. Populasi
terbaik yang terdapat pada masing-masing s/oye kemudian dikirimkanke moster. Mqster mengkoleksi dan melakukan evaluasi sefia seleksi untuk seluruh populasi terbaik tersebut lalu mengirimkan kembali ke proses .r/rzve.
Ket.
KomLrnikasi antar penlroses
'i -l
N'Ietode penerapan algoritma paralal terinspirasi seleksi clonal
Berikut irri adalah metode penerapan algoritrna seleksi clonal paralel sebagai solusi persoalan optimasi, dapat dilihat pada Gambar 7. Pada metode tersebut, input berupa
persoalan optimasi, dalam hal ini adalah persoalan TSP. Output berupa solusi yang diharapkan, serla kinerja komputasi berupa waktu eksekusi. Terdapat dua fase, yaitu fase itrunune engineering dan lase purollel contputing. Sebelurn dieksekusi, persoalan yang akan dicarikan solusinya, mengalarni fase yang disebut dengan intnrune engineering terlebih dahulu. Pada f-ase ini, dilakukan representasi persoaian yaitu proses pemetaan antara pararnater-pararneter persoalan dengan parameter yang ada pada algoritma seleksi clonal.
r&
Gambar 5 Multipl e-popLilution crtrrr.se-grrinecl model
Pada
model ini,
populasi disiapkan oleh
proses tnoster) kernudian dikirirn ke proses sluye. Selanjutnya, tiap elemen petnroses
melakukan operasi seleksi clonal berupa evaluasi (perhitungan cffinity), seleksi, klonilg dan hiperrnutasi, serta replocemenr. Populasi terbaik yang terdapat pada masing-masing elernen pelnroses kernudian dikirimkan ke seluruh proses elemen pemroses lainnya. Proses diulang sampai dengan kriteria berhenti. Karena granularitas komputasi di tiap elemen pemroses besar, yaitu seluruh proses
I
t2
lrc.ii
Ket. i:lfl:r::::: iri
i
i.,.:,1
rikl-: *; Komunikr.,'.,.
4L-f*"r - sl #*l "@\v/ r-qfur "i"-
Gambar Z fr,l"toJ" penerapan algoritma seleksi clonal paralel Seiain itu. ditetapkan offinity maturation, yaitu fungsi yang nellerapkan nilai optirnal dari
Lentbttga Pt:rteIitittn flniyersitas Postndun
El
ffi:T iXtffi
ifi::'ll;lll ffi
'os'u*
D
es
entrar
i s as
i'
S
entrari s asi dan
Sesuai metode pellerapan algoritrna. perlr-l dilakukan pemetaan persoalan TSP dengan algoritrna seleksi clottal paralel 1'ang clapat
dilihat pada Tabel '1. Verifikasi clilakukan dengan eksperimeu pada lingkungarr implementasi 1'ang terdiri dari dr'ra liligkurlgarl
yaitu lingkungan rutLlticrtre dan
atau banyaknya populasi yallg dievaluasi sejumlah tertentu. Selain itu, algorittna dilengkapi dengan variasi parlisi data dan populasi, serta pettgaturan fiekuensi
lingkungatr
clltster. Kluster yang digunakan. terdiri dari 1 hettchotle dan 16 cott'tpute notle. Pada
eksperimen ini digunakan digunakan 8 cotnltrtte trotle. Spesifikasi teknis dari hetrclnotle CPUs 32x2.90GH2. melllory 126.13GB. local disk 895.46,5GB deugau Linux 2.6.32-219. Sedangkan ;:nluk cctntptrtc rrnrle CPUs l6x2.l0GHz, memory 1-5.66GB.
komunikasi. Algoritrna diirnplernentasikan di bahasa pelnrogralnan yaltg mendukuttg mocle1 paralel mas.\'oge po.;sittg. clalatll hal rlli cligunakan bahasa Java clcngau pustaka MPJExpress sebagai impletneutator Stctncktrcl Messoge Pctssing lnter/itce (MPI) yal1g menerapkan model pemrogramau Sirrg/e InstrLtctiort Multiple Prrtgrcttrt (SPMD). Program dieksekusi di lingkungan pemrogralnau paralel, baik itu cluster ataupun mttlticore. Sebagai rnasukau, diberikan variasi jumlah elemen pemroses di masing-masing
eksekusi. Program akan
'four optir.nal dari Garnbar 9 rlataset Berlin52
(ianrbar 8 Koordinat dari clataset Bcrlin52.tsp
persoalan. Dalam kasus TSP fungsi t1f/init-v yang diharapkan adalah nilai tour minirnal. Setelah penetapan keduanya, algoritma seleksi clonal paralel siap dieksekusi. Algorittna iui dilengkapi dengan parameter-paratneter terkait seleksi clonal, yailu jumlah popuiasi, jumlah seleksi, clone factor dan mLtlute /irctor sefia kriteria penghentiau proses. dapat berupa jumlah generasi atau solusi telah diternukan"
loca1 disk
142.835G8.
Algoritma diimplementasikan dengan bahasa Java datt MPJExpress sebagai pustaka Messuge Pa.s^iirrg
Interfoce (MPf). Tabel 4 Pernetaan persoalan TSP clengau algoritma Scleksi clonal Inisialisasi
menghasilkan
Populasi
keiuaran berupa solusi yang diharapkan dan kinerj a waktu eksekusi.
Eksperimen untuk verifikasi
Troveling Sulesmun Problem
Evaluasi: cek rtJJinil'
merupakan salah satu contoh Probletn deugan kompleksitas O(rt!). Berikut sambaran titik-titik koordinat dari dataset
Seleksi: a/liniry rnaturatiott
diperoleh terlihat pada
Kloning
(TSP), kasus l\rP-
Berlin52.tsp dengan tour optillltun yang
flipennutasi
TSP
Kumpulan tour yang dibarrgkitkan secara acak. ferdapat (n-1)l Kernungkinan tour yang dapat dibangkitkan. Populasi rnerupakan sebagian dati tour terscbut. Banyaknya tour yang dibangkitkarl sebesar ukurln populasi yang clitetapkan. Evaluasi tnelakukan pengece-kan alflnltu tiap tour yang sudah dibangkitkan yaitu cost yang tliperlukan dalam tnelnbcntuk toul'tersebut. .lflinitt'tni merupakan seberapa dekat cost suatu tour dengai best .:ost oplimal. N,takin dekat. naka u.lfinitt rnakin tiuggi dan terseleksi. I)eristirva pengcopyatl tour terscleksi sebarivak clone ltrttor: /) 1-oul yang sudah dicopy akau rrengalall.ti h!,perrnutasi sesuzii clengan probabtlitas s!-suiri clcngan nrttlalt' fictor: 1r
Replacernent
I'urgaurbilan tour-toul tcl-baik. tour
(Ldit
terburuk dari populasi awal akan digantikan oleh tour terbaik dari hasil kloning dan hipeululasi. sc'iunllah ukuran
receptor/elisitasr )
t nd ttn re p l uc e nte n l tl. Kriteria berlienti dengan nilai jurnlah
r
Garnbar
s dan Gambar 9
Kriteria belhenti
di bawah ini: ll
F
l- -i;"0:i ;- ] ------ :
,.r,.-------ai.,
-
i :
', ' l:+@-J pi . ,' *s.01 -
-,
-:-.-.----..!
*,
,ee
S.*- 9
:
u
1-1*- ; -- i -l--.--f. .0.-...9..........j
aLli En
Pefiukaran tour-tour tcrbaik Yang
pemroses
elernen pemroses ke elemcrr pelnloscs
Jihr'ilkarr,,leh dari tnrsittg-rnlsirte lirinrrla
,JM*--i \ ]
:
:"
,..._....... ..;. ..-.......-........:...
t lil tir
'-. \.
g!!ga!r
Kornunikasi iurtar eletnen
:1..
, --+--.---,
;
.
[0 ]lfir llili
l6ur
ls[ ]ff
i
i,flr t ' i,,4. t ' : {r ,V\/ : t0t (0 ts
lmo
lm l{i lffi lM
-\
lm{
x
Lcmbugu Penelitictn LJnit'ersitcts Pcrstmdun
il3
(,4.*-
\w{wl:
r*
Proceecling f'resentasi Hasi] Penelitial I Iibah Program Descntralisasi. Sentr-alisasi Ilibah lntcrnal l,hpas lahun 20i4
r.lan
menunggu seluruh sloye
selesai
meiakukan tasknya. Sementara itu, slave
harus selalu lnenullgu master selesai rnelakukan task. Selain itu, data yang bersifat dependent, yaitu tiap data saling bergantung antar generasi. menl,ebabkan
seluruh sluye harus lnellurlggu master
r kut skenario eksperimen Berik
Nama data set yang digunakan
selesai meiakukan kornputasi Burrita1,l. Berlin52.
KroA100.
2)
tsp225
Known Best Cost dari TSPLib
7.542. 21.282,
Jumlah maksimum generasi
N. inisialisasi populasi
n,jumlah seleksi
lainnya. Setiap pelnroses
Ukuran data populasi yang dikomunikasikan
parameter
Clone factor B Mutate factor 6 Jumlah elemen pemrosesan
Lingkungan pemrosesan
3)
I(onsekuensi dari penerapan komunikasi
mtrlti-cottrtttuniccttion
50 10
ukuran populasi /
jumlah elemen pemroses, atau N 0.1
2.5
2.4,8
sebelum digabungkan dengan populasi
terbaik dari rnasing-masing perrroses lainnya. Gambar 10 dan Garnbar 11 merupakan grafik-grafik rangkuman
eksperimen rnerrgenai
luster Data populasi.
frekuensi, P.,lc,,uh,,,,""" ::-11:1,;.r:J,:lrDd.,p
partisi. dan konrunikasi
berdasarkan penelitian berikut:
1)
model
114
i i$
di atas adalah sebagai
master-sluye. master
w
pengalurall
kru l r5,.k,,.i
$$n* g r$ "g
sB
$
{ft *L&silLu&f,uililsfl
dirangkr_un
Enam model komputasi yang kemudian diimplernentasikan menjadi algorihna komputasi paralel, terdiri dari single populotron atau nuilti populutitttt, dipadukan dengau penerapan parlisi data dan j.,gu rnodel kornunikasi. Model komunikasi master-slove memerlukan waktu eksekusi yang tidak sedikit dibandingkan dengan rnodel mtltiplecornmtniccttion. Hal ini dikarenakan, pada
itu.
pengaturan komunikasi, keragaman populasi terbaik di rnasing-masing pemroses terjaga dengan sendirinya
Multicore,
hal yang dapat
adanya
pel)gaturan kornunikasi antar peltrroses menjadi sangat pentir-rg untuk memperoleh waktu eksekusi yang lebih lebih baik. Di lain sisi, best cost yang diperoleh sernakin membaik. Hal ini diperkirakan dengan
model
Beberapa
adalah
overheutl kornunikasi. Karena
C
Aspek pengamatan
melatr
1,':urg diperlr,rkan.
14. 52. 1 00.
225 r 00,000
Ukuran partisi :
Nilai
Di lain sisi, multi-cclntttunicotiotr rnembuat setiap pemroses mengirimkan hasil komputasinya kepada pemroses lainnya tanpa harus meuunggll satll salra tasknya rnasing-rnasing sebanlrak generasi
3.916 Jumlah simpul percobaan
data
(populasi terbaik tiap ger-rerasi).
,;,rli;,,r.-;,
i,r,
r,:
::,i
rr r:.:l;-.',;,:i1.,,r,,:,
Gambar 10 Pengaruh frekuensi komunikasi terhadap rvaktu eksekusi pli!rrLh h.t{i8r ji KDmh:itnri hd:rdrp [r,t Lr* 0rhtrt &ii1!2
ut$i$$x$$u$$s$*elx $ftru$$tr$ffiffiffietuffiffi&ffiffiff
harus
Lem
b ag
u P e r r e I i r i ct t r (J n iy er s it cr s P ct s wt clcut
a---
qql
Pt'ocee tling Presentasi Hasil Penelitian Hibah Prograur Desentralisasi. Sentralisasi clan I-[rbah Irternal Unpas Tahun 2014
Gambar 11 Pengaruh frekuensi komunikasi terlradap best cost
4)
Seiain jumlah generasi, ukurar populasi arval temyata sangat mempengaruhi \vaktu
eksekusi, dengan deilikian, populasi arval sela1u dibuat
ukuran sekecil
rnungkin.
5)
Dari sisi kinerja komputasi dar best cosl
untuk tour terbaik, model
dengan
menerapkan single population dan paltisi data. baik partisi di awal populasi saja atau di rurl dan aklrir geuet'asi. tnernputtyei kine{a yang lebih baik. Terurtarna jika digunakan untuk lingkunran komputasi dcnqan jumlah pemroses yang banyak.
6) Dibandingkan
dengan knolvu best cost dari TSPLib, didapatkan irasil terbaik yang
terjadi komunikasi pengiriman populasi terbaik dari tiap elernen pemroses. Terlihat
bahwa, model yang diusulkan pada penelitian iri baik rnodei 1 atau kedua. setara cler-rgan uodel ttsulan Dabrou,ski yang meuerapkan model ring dettgatt keteraturan kornunikasi. Natnun dilihat clari sisi best costnya, tlodel yallg
c'liusulkan pacla penelitian ini rnenghasilkan best cost yang lebih baik.
Garnbar 12 di bawah ini tnetupakan gambaran pembanding besl cost per jurllah elernen pelnroses per dataset. Sedangkan Garnbar 13 tnerupakan perbandingau rvaktu eksekusi pel jurnlah elerncr.r pelnroscs per clatasct. ,.r(r
Partirrkri^o
ra.n.t'
1lr,|nt
!i.
r!u, 2f5
terangkum dalanr Tabel 5.
rri;
1)
ffig I#H ffiffiH
Tabel 5 Best cost setelah pengaturan liekuensi
kornunikasi Gambar 12 Perbandingan besl cosl per jumlah elemen pemroses per dataset 52
tt4itt entut ,!6ra! lmPl !?,
[email protected] &ryin iuolin €,s.n Plhrose a4,8
teihnnhsrn Wslrr
It $
i**.
mE w*
?,j
$##l-.
Hasil terbaik untuk percobaan
8)
100.000 generasi adalah adalah 8T.0i% (M4; npS) untuk dataset berlin52.tsp, 53.43% (Ml; np4) untuk dataset kroA100, 17.18% (M1; np4) untuk dataset tsp22,5. Secara ratarata. model 1 memiliki hasil terbaik. Dibandingkan dengan model yalrg
dihasilkan oleh peneliti lain, Dari grafik terliirat bahrva best cost terbaik diperoleh dari algoritma yang diusulkan penelitian ini, kecuali untuk dataset kroA100 dan tsp225 pada pemroses 8, model usulan Hongbing menghasilkan best cost yang sangat baik. Namun, jika dilihat waktu ekekusi yang dibutuhkannya, model tersebut memerlukan waktu eksekusi yang sangat lama. Hal ini dikarenakan model
tidak melakukan pengaturan liekuensi kornunikasi. Tiap generasi
tersebut
I- em b
aga P en el iti on
LIn iv
ersito s P cr.t un rl o n
Kesimpulan Kesimpulan pada penelitian ini adalah sebagai berikut: 1. Untuk membangun model paralel seleksi
clonal, tahapan pertama adalah memperhatikan aspek perilaku terdistribusi dan sistem imun. Dalam hal ini perilaku inisialisasi data populasi dan
komunikasi antar elemen pelnroses. Terdapat dua alternatif inisialisasi data populasi, yaitu populasi tunggal dan populasi banyak, dilengkapi dengan perilaku komunikasi antar seluruh elemen sistem. Setelah itu, dilakukan penerapan
115
,6--t
f
Prctceetlitrg Presentasi Hasil Pcnclitian Hibah Progratn Desentralisasi. Scntralisasi darl Ilibalr Intcrnal Unpas Tahun 20 l.l
berbasis agent ataupun pemodelan rnatematis dan pemodelan dengan
pendekatan berorientasi
objek.
uma Internasiona No I
.llavelinq
Pernahaman tentang sistetn itnuu yang
baik. akan
inspirasi
Sirlesrncrr
Dari sisi komputasi, penelitian dilanjLrtkan untuk pengarnatan kinerja paralelisme
.llgtrithtn
menghasilkan
sefia
Clonol
ngukur skalabilitas tnoclel komputasi, yaitu dengan meuerapkan
rncl
persoalan TSP yang lebih besarikorr-ipleks dan persoalan nyata detrgan prinsip dasar TSP.
r
r
tirt
g
P robl
pp. I I 005-
Applied
il017.2014
Enginecring llesearclr (rJA.rjR) ), Research Indi:t
Orr Par:illel
[]ntuk
Hcuristik Mrxlel Llasccl on ('/orral
dipublikasikan
.\elecrion
March 2015
,,1lqo r
Vol
13.
No l:
Publicrtirns. elkorrnrka ( lclccorntnunic atiur
-f
C'ornputing Electror.rics ancl
C'urtrol)
irh ttr
nternasional tidak terindex
uma No
.l
I
( ompr(er
salesperrnan lebih dari satu orang (m). Salah satu peirerapan rl-TSP adalah u:ntuk l"ehicle Ro
Narna Jumal Intemational Joumal ol
ahun
Ditelirna: 2 Deserrrbcr 7011
('ornmunication
model kompr,(asi paralel untuk ukuran
dapat diujicobakan untuk kasus lainnya, rnisalkan rn-TSP ata LI Multi T-r'ot'elirtg Sulesntan Probletn. ditnana persoalan irti merupakan pengembangan dari TSP dengart
Dipublikasikan Vol. 9, No. 21,
Se le<::rion
Data l)artition
7
me
Dari sisi kasus pcrsoalan optimasi nrodel clatt algoritma .vang dihasilkan oleh penelitian ini.
-[
I'rohlcnr br
kornputasi yang lebih baik lagi,
2.
terindex
uclul A Nerv Approach to Solvc- N'lultiple
J
Tahun Dipublikasikan.
uclr"rl
[:rperirlerrts tvith a C'lontl
Vol.
St'lcttion
20 14.
10.
No. [.
pp 59-7I,
.1lgor ith nr
Nama Junal Internatioual .loumal of C'ornputational Intell igencc Research
(l.rc'lR), Rescarch Inclia
ern (VRP).
Publications.
Rrlvlvlr
Htoup
Penulis dilalrirkan pada tanggal 24 Mei 1972 di Garut. Ia lulus dari SMP 12 Bandung dan SMA Negeri 3 Bandung pada tahun 1990. Ia memperoleh gelar Sarjana Teknik pada tahun 1998 dan gelar Magister Teknik pada tahun 2002 di Departemen Teknik lnfbrmatika, Institut Teknoiogi Bandung.
uma Na sional No Judul 1
L ent
b o
go P en eI iti ttn
(Jn
iversit os
P a s un
-2014.
MPJExpress Scopus Konferensi Intemas onal (termdex Sc No
.ludr-rl
J
Parallel ization L'lonul Selat:tion
Algorithn witlt Message Passing Model and NI I'.l Express
Konferensi No .Iudul Studi dan
Implementasi
cl
un
a
Moclel -
5
,tR PUBLIKASI
Algoritn,a
Cybermatik
Passins
dan mempunyai tiga orang anak Rifqi
Dan
Paralel
Dipublikas ikan, Vol 2. No 1,
dengan Java Message
Promovenda menikah dengan Arief Zulianto
Muhammad Fikri (18 tahun), Rifqa Az-Zalra Nur fitria (11 tahun) dan Riefa Ramadina Nur Asy-syifa (4 tahun).
Model Kornputasi
Seleksi
pe laksaua
Program Studi Teknik Informatika di STMIK PN{BI pada tahun 2002-2003. Sejak 2004, ia bergabr-rng menjadi anggota staf pengajar di Program Studi Teknik hrfonnatika, Fakultas Teknik Universitas Bandung.
idak terakreditasl Nama Jurnal Tahun
Clonai
Sejak tahun 1998 sarnpai dengan 2001. ia rnenjadi staf tenaga tidak tetap pada Lernbaga Pengabdian Masyarakat (LPM) ITB. dan
kemudian rneniadi stafiketua
(t
-l
ahun ilcce pted. Registerecl. )02I December, 20
l4
Narna Konfcrensi lntemational Scis-ntitlc C'onlLrence on Applied Sciences and Engine-ering,
Kuala [-umpur
Tahun
Nama
2014
Konferensi Konferensi Nasional
117
Procecr:ling Presenlasi [lasil Pcnelitian ilibah progranr Dcsentralisasi. Sertralisasi dan Hibah Interrurl I lnpts l ahLrn 201.1
Algoritma Terinspirasi Sistem Lnun:
Clonul Sclac/iorr
Dipane-gara.
Algorithnt Uc'apAN TERrlra
Sistem
Informasi (KNSD, ITB - STMIK Makassar
KrstH
Penufis mengucapkan syukur
clan
Alhamdulillah ke hadirat Allah SWT atas segala rahtnat dan )tidayairNya yang telair
clilimpahkan kepada penulis,
sehinega
penelitian hibah desentralisasi doktorai dan penyl-lslutalt laporan setta ringkasannya iui clapat clisclesaikan pacla u,aktunva.
Terirna kasih disarnpaikan kepada Departemen Penclidikan dan Kebudayaan atas bantuan Hibah Desentralisasi Doktor yang diterirna selarna ini.
'Ierima kasih disarnpaikan kepada Universitas Pasundan, khususnya Lembaga penelitian,
Fakultas Teknik dan program
Studi
Infbrmatika, atas bantuan dan dukungan yang diterirna selama pendidikan program doktor 1nl.
Terima kasih disampaikan kepada seluruh Tim Pernbirnbing dan Penguji pada prograrn Studi Sekolah Tinggi Elektro lnformatika Instrtut
Teknologi Bandung, atas bantuan dan dukungan yang diterima selama pendiclikan program doktor ini. Serta terima kasih kepada seluruh piliak yang ilarnatlya tidak dapat disebutkan satu per satu
yang telah
membantu penulis
selarna
rnelaksanakan penelitian hibah desentralisasi doktor ini.
118
Lembogu PeneI ititrn Ltnit,ersittts psstndctn
f
