ALGORITMA GENETIKA DALAM PROGRAM PENCARIAN JALUR ALTERNATIF Wahyu Trianto Nugroho(1), Joko purwadi(2), Nugroho Agus Haryono(3)
Abstrak: Pencarian jalur alternatif pada saat terjadi kemacetan atau penutupan jalan bisa dilakukan dengan mengingat setiap jalan yang terhubung dengan jalan terse'but, tapi hal ini hanya bisa dilakukan oleh pengguna jasa kendaraan yang suOan mengenal jalan tersebut. Bentuk permasalahan yang terjadi diubah dalam beniuk graf dimana liap tiiit merupakan
perwujudan dari tiap persimpangan yang ada pada peta, sedangkan jaraknya diwujudkan dalam bentuk garis. Pencarian jaraknya adalah dimulai dengan penginputan titik asal dan titik tujuan. Melalui
perhitungan dengan algoritma genetika maka akan didapat jalur yang menurut sistem merupakan jalur yang dapat dilewati, dan jika terjadinya kemacetan paO-a lalur tersebut sistem akan mencari ulang jalur alternatifnya dengan titik awal adalah persimpangan dimana kemacetan terjadi.
Algoritma Genetika merupakan algoritma pencarian yang berdasarkan pada genetik dan seleksi alam. Dikarena prosesnya menggunakan evolusiyang dlwakilidengan'Oitangan random, maka hasil yang didapat bervariasi mulai dari diketahui jaluialternatif pali-ng baik, iampai jalur yang diinginkan tidak didapat. Kata Kunci : graf, algoritma genetika, jalur alternatif, kecerdasan buatan.
1.
Pendahuluan Jalan darat merupakan sarana utama yang mampu menghubungkan satu tempat ke tempat yang lain. Hal ini mengakibatkan tingkat mobilitas yang terjadi saigat tinggi, dan tidak semua jalan yang ada di lndonesia memiliki lebar yang sama, sehingga piOa a[tiirnya timbul penumpukan kendaraan pada jalan-jalan tertentu. Kemacetan yang terjadi akan sangat baik jika dapat di hindari dengan mencari jalur yang lain, tetapi akan timbul permasalahan baru jika pengguna jalan tersebut rierupakan orang yang tidak mengenal daerah itu, sehingga dengan terpaksa pengguna jalan tersebut menunggu dengan waktu yang lama untuk melewatijalan dengan antrian t<enOarain yang panjang. Penggunaan algoritma genetika yang merupakan algoritma pencariln neuristit Oapat dipakai untuk mendapatkan solusi yang tepat untuk pencarianlalur alternatif dengan memilih jalur dengan nilai jarak seminimum mungkin.
2. TeoriGraf Karya Euler pada problem Jembatan . konsep graf Eulerian
Konigsberg (1735) yang kemudian menghasilkan merupakan awaldari lahirnya teori glaf. Euleimeiyatakan bahwa jika suatu pseudograf G mempunyai sirkuit Euler (jatan tertutup yang memuat semua sisinya dan masingmasing h_any-a sekali) maka G pasti terhubung dan derajat setiap titiknya genapn. Graf merupakan diagram yang memuat titiktitik yang disebut-"verteks" yang masingmasing dapat dihubungkan dengan garis yang disebut dengan iegde,,. Graf tak berarah (Undirected Graph) G didefinisikan sebigai pasangan himpunan (V(G), E(G))' dimana V(G) adalah himpunan tak kosong dari elemen-etemen yang disebut iitit< lvertdr6i dan E(G) adalah hippunan (mungkin kosong) dari pasangan tak terurui (ui4 aarititik tiiik u,v di V ygng disebut sisi (egde), Selanjutnya sisi e = (u,v) dalam graf G at
(t.),Mahasiswa
klotik Informatika, Fakultas Tehtik, Universitas Kristen Duta wacana Joko Purwadi, S.Kom., M.Kom., Dosen Teknik Informatika, Fakuhas Teknik, Universitas Kristen Duta Wacana (3),Nugroho Agus Haryono. S.Si., M.Si., Dosen Teknik Informatika, Fakultas Tbknik, (Jniversitas Kristen Duta Wacana t.' Profesor Edy Tri Baskoro, Mengenalkan Indonesia Melalui Teori Graf, Pidato Ilmiah Guru Besar Institut kknologi Bandung, I 3 Juli 2007, Balai Perternuan llmiah ITB t'^'
62 JURNAL INFORMATIKA, VOLUME 4 NOMOR 1, APRIL
2OO8
3.
Algoritma Genetika Genetic Algorithm (GA) merupakan algoritma pgncarian yang berdasarkan pada mekanisme sistem natural yakni genetik dan seleksi alam'. Algoritma ini dapat dipakai untuk mendapatkan solusi pencarian yang terbaik dari beberapa solusiyang ada dengan menggunakan proses evolusi.
Munculnya algoritma ini pertama kali di ungkapkan oleh John Holland pada awal tahun 60 an dan di tuangkan dalam bukunya yang berjud J Adaptation in Naturat and Artificial Sysfem6.
Algoritma genetika yang diperkenalkan oleh Holland pada masa itu tergolong umum dan sederhana, algoritmanya sendiriterdiri dari langkah-langkah sebagai berikut :
1. 2. 3. 4.
5.
inisialisasi populasi Evaluasi setiap kromosom dan populasi berdasarkan fitness Pilih suatu kromosom dari populasi dengan nilaifitness terbaik
Lakukan perkawinan silang (crossover) antar kromosom, jika tidak ada persilangan lanjutkan langkah 5 a. Pilih pasangan dalam populasi dengan probabilitas sama b. Tentukan titik perkawinan silang antara 1 sampai L dengan probabilitas sama, dimana L adalah Panjang kromosom c. Lakukan rekombinasi kromosom dan mutasi pada kromosom jika ada keturunan baru yang dihasilkan ditempatkan pada populasi baru Jika populasi baru belum penuh, lakukan langkah 3 Populasi baru penuh (umlah populasi baru = jumlah populasi lama) kembali ke langkah 2
Algoritma Genetika dapat di aplikasikan dalam berbagai macam bentuk, salah satunya adalah pehcarian jalur alternatif. Pencarian jalur ini berupaya untuk mencarijalur lain selain jalur yang biasa dilewati. Sebagai contoh kasus dapat di mulai dari berapa pertanyaan berikut, a. Ada berapa jalur yang bisa dilewati untuk berjalan dari satu tempat ke tempat yang lain? b. Apakah jalur yang dilewati adalah jalur yang paling optimal? c. Adakah gangguan yang terjadi pada jalur yang akan dilewati?
4.
Hasil lmplementasi Algoritma Genetika Pada Pencarian Jalur Alternatif Hasil implemenetasiAlgoritma Genetika kedalam program dapat dilihat pada gambar 4.1 dimana jalur yang baru dengan titik asal dan titik tujuan tanpa pemotongan jalur atau tanpa terjadi kemacetan. Penggunaan program dimulai dengan pemilihan bentuk graf, dilanjutkan dengan pemilihan jumlah iterasi dalam untuk program pencarian jalur alternatif, serta penentuan titik awal dan titik akhir pada graf. Pada gambar 4.1 dapat diketahui bahwa bentuk graf dengan node awal 19 dan node akhir 2 akan mbnghasilkan jalur dengan format 19-21-7-18-16-29-2, atau dengan kata lain ketika dari Jl. Dr. Wahidin akan ke hotel garuda di ujung jalan malioboro melewati Jl. Lempuyangan dan Jl. Abu Bakar Ali, sedangkan proses pencarian jalur tersebut dapat dilihat dengan menekan tombol "history" bentuknya dapat dilihat pada gambar 4.2
(5) Aries Syamsuddin, PengenalanAlgoritma Genetik, Kuliah umum ilmukomputercom, 23 oktober 2007, http://www.ilmukomputer.org/wp-content/ uploads/2006/08/aries-genetik.zip. (6) Rennard, Jean Philippe Ph.D, Genetic Algorithm hewer: Demonstration of a Genetic Algorithm, 23 ohober 2007,
h t tp :
//www. re n n ard.
org / al ife / en g I is h/g avin trgb.
h tm
I
Nugroho, Algoritma Genetika Dalam Program pencarian Jalur Atternatif 63
Gambar 4.1 Form Pencarian JalurAlternatif tanpa Pemotongan
a#dcpa*eE
-.
l1:g$l$tt
'.,:
+ *h.4..!!r: g.*w si":sil: iri
il-ffir*,r;1$-$t*.F&s.!.t.$i-$!$$-114.f$+13,f44as-ffi.3s-tdd&r$1{i"r&F-#*:$.tr{S.Str:+r1.?1 iie-w+r!:+* !*qf14stf"lFft-9&fi"f;!8-4s+f-&:fr1&-915.r9:'i.13.;1-11tg3t*l .tts"r*d*f*ry+:*{tH3l-p* tuw$................*3r1*.11'l.t&l&1F3"1$"}$.S-FjS'!&.3:-134i"J&1F.51*'1S4.1&.444.1S.;+e9#efr.e
{ffi#l$-4
+ffi}S"Sr1.S*W.Sr1g4449
-,:.l
r$.fl.}}.tFtS.1:i"+!FS'',5r:F&.S9361$.r"j.S.id,S}&1i"3"***.tg.S.*+etstdffi:t}ffi4.$+::+m.6i-++,rg.t*=ti * L{@#rei lgt"ii{;Sq-D-{,1;.."8_r'::qlB:99rd+:.1b;06.r:6r " drFdG. fApc g bO6li ,}i f-ftf; v.rffirs!:+.#:1$J1"?.t&{"1*.}iHt1.f+.}S4-;F5;$.J*-:-F+i$.4"$"S+'r+S+SS"rasbf*#,trm* fr,,*lm$.*!,,"*,f:fq rrw+;wlc' lJ}.J;.*,4.1-1.!JlJ 4,1171:8!-\J{.?:E:itr10_rr{3trg::$'b-Slb, d6rre- otqA15-Fi a0au,s" u FrmmL+S:19F1'l4B-11.1$'*.1+:S'4'tS.1&::-:$.13.f*"F.1s"1$.3S'-i..ti.$'i4.9I4+3.i+*]/t#f*xw +ffi{€.tE *,#41.*tr*#F}n r'4m:mre Q rgt4t'5:S&1+5-}J9-55 j$61:9.59.jd.jj"6:3.1!:r'u5r' n ,JGE6l {,r; itrA",rd+t@ 0Mt r,ffisr' 14 '9\:66{.bt{rtJ!6:*ir.4.d1;a.tgF*:j'4-j!C:lrj d ,tu.ff. C&S{ Ft rl&l Ai. il9&
-a!#s;l+
,l
I -.
Fwrimi H*d $ri*ke $1
FII##ffi&*1,IS$"f'1+.S.1$+84'1.I"*.tS+lS'S'S,f$.1+gjS-e+.H.{-{.6';S}.{.?{++:ird*f'Im *ffi.FF.,S1iSS *e e'iH4 F:tmw*,+f:tSil-?.1&lg-l*.S1.S"{*S.l*.}St}?1.!pI9:{31$.3-!&.1S4.1&.{9.4.18,1$""rr#,*f**!rS.#J-{.FU:+!SS Eh:**H KtrffiFs t: 1*+1"f"}&"1$*e+.1.S.;S$S']S.1$.*i.131$4i4$.+1*"tg'44$.d$",{'1fi"S *:i rd*fd#+ : *ffil$-f*.1 :$.ffi. {it , S.d$,t$ 4:1-&SSS4.{'1+.}€4:IS"i€jS'*4.1.d1"S}$i*$3}14.ff.:$fF$"r tuffihe $&rf*m:: #ffi+. $r; *m*.**: ttt** ,,(ij@!+ 5 19'pj{t5lu4t ?g.j.S.4S!}.S j}81:.:,!"tJS-+e*r6-,t&tS-\ @FM; ,:rnOg A. Ori;; Of, hii:t '. tuwdei.r-*: l$;1.1.i+-t#S'?.1.+fS'+;8.16 t?'tt-TJ,lFt}-ltJ-rS.|SdTF,{ FEl$eg. * dd;firxp: e.m*.rX: h:S}*, *i :S{6**
(s4&*l+*-
1S$.:f'14'?9.1r-"1tt*+J4?.1;,+.t*.i4"1.t+3i"J/*.I$,ggj+g,td.s.A.#1+:*.t*"":e*a;$G,*ffiS,Hlb-tlH d;.;t
,Esw!*rdi+*r'1+:11"131$"13-81.!*.f*.i'.1$.fi4.1f";4.1t"18.FJS1$.*f.1*":'t3I9F-ISr3.lB."ir**F**+ *ffii-irE;${s+s"ql-*:i [r{ffirk*-*r i$"31-l.t*.'l]1$31+-t$4-?ii"!&?";$-1i]-"91-I]$.1t.S-1.91{$i4-*}{"i*.14"*:r{*fiffi:A*#5 fls.:*S4+.$.;e$ei3 ritffiEffii:rlS.1+:'+.1$J+*{ltS.S!8";+tSt*"S.1S9,ffi{,1"?.S.T{,S.*S!4St";S-:rr$;S-}*}r+s +ty${.Ff. **&* tl,tt+}lr
4ffiffi}fqrd+w#rffi6*
*o;,#o;fii.rii irildia+n +F*,F,r*,*s.+F qlffir{*S:l+tl.r,1*,1G.}*-31-*.+ .$ff"lF (q*
m rc
q
1
95.S
q
;fl+, t.1 t
."
g
T B.t,'
J
h.r$ 1*+*.1$,3.18 I64-rs.*+-1.r$-*s 3.3!"rS-!S.i}tF,1x+.1$.41S-{$4.1$;$-
",1
S
r
: .' I
r_.9
H
4ts rb-E 6
r.6
^S
Ga;mbar 4.2 Form History Jalur Tanpa Pemotongan
i
Pada jalur ini didapat jalur teroptimal pada saat pencarian berlangsung yaitu pada jalur 19-21-7-18-16-29-2 dan ketika terjadi kemacetan pada jalur 7 ke 18 maka pengguna dbpat melakukan pencarian ulang jalur alternatifnya dengan memutuskan jalur dari node 7ke node 1B dan menjadikan jalur ke 7 sebagai titik awal pencarian. Hasil pencarian jalur setelah pemutusan jalur tersebut dapat dilihat pada form hasil pencarian dengan pemotongan seperti gambar 4.3.
64 JURNAL INFORMATIKA, VOLUME
4 NOMOR
1, APRIL 2OO8
Gambar 4.3 Form Pencarian Jalur Alternatif dengan Pemotongan
Pada gambar 4.3 dapat dilihat jika jalur baru terbentuk dengan menggunakan node ke 7 atau dari lempuyangan melewati jl. Suryatmajan dan akhirnya melewati malioboro ke ujung malioboro dekat hotel garuda, atau jalur dibuat dengan melewati node 7-24-22-17-12-8-23-14-92.
Jalur yang terbentuk tidak dilengkapi dengan aturan jika jalur tersebut terkena kondisi jalan dengan ketentuan harus searah.
5.
Analisis Hasil Penelitian Pada bagian ini akan dijabarkan analisis implementasi algoritma genetika untuk menemukan jalur alternatif. Analisis dimulai dari proses perhitungan algoritma genetika yang
digunakan untuk menemukan jalur alternatif.
Perhitungan dapat dilihat beberapa tahap dimana tahap pertama dimulai dengan penentuan jumlah iterasi dimana jumlah iterasi ini digunakan untuk menentukan proses perulangan yang akan dilakukan oleh sistem dalam menemukan jalur alternatif. Tahap kedua adalah penentuan parameter-parameter yang akan digunakan untuk proses pencarian jalur dimana parameter-parameter tersebut sudah ditentukan diawal pembuatan program. Parameter tersebut dapat dilihat pada tabel 5.1 yang berisi parameter genetika beserta nilainya. Tabel 5.1
Parameter Genetika
Jumlah Iterasi Jumlah Node
Tahap ketiga adalah tahap pembentukan populasi awal dimana populasi tersebut merupakan bentuk dari beberapa solusi yang dapat terbentuk dari kasus yang ditentukan.
Nugroho, Algoritma Genetika Dalam program pencarian Jalur Atternatif 6s
Pembentukan populasi awal dapat dilihat pada tabel 5.2 yang berisi no urutan kromosom7
berserta node-nodenya.
Tabel 5.2
Bentuk PopulasiAwal
t
g-tt- i l-t s-t t+
t- I
:-t r -t-r g4-6-ll?-
5-19-5-f[ffi
9-2i - I 3- I 5-?S-15-3- I 5-:*- 1 9-54S-5"8!l-5-?&6- I -?-3ruIS-?l-?-18-3-t l -2,?,t5-s-t5-9-15-? 8-?-?8- t t; -4-6r
r
1
-3-36;1ffi
_j_ffi ffi
9:a! :ii"::9- I 3- I 5-3- r 8- I 6-4- 1 & I 8-3_ l 9- 1 3_2 191:4Q:i-?0-S-?0-s-?0-s-?0-5-? 0-6- I -2-9-25-eI 9-5-2S-{,4*6-r -6- I -S-4- I 6-28- I 6_,r_61 _j_g-2_e-lj_s_?FT4_23-TnfrJa I
1
Tahap keempat adalah tahap pemberian fungsi evaluasi yang digunakan untuk mencari jalur alternatif, dimana fungsi fungsi tersebut adalah fungsi fitnes, tuigsifitnes relatif, dan fungsi fitnes komulaitf. Pencarian fungsitersebut didasarkan padl rumus seperti berikut :
NilaiFitnes
I r_ |--.------
15.11
,"
i1
dengan,
-
j = node tujuan
p = jarak antar node F = nilaifitnes tiap kromosom
-
Fitnes Relatif dan fitnes komulatif
!
i totfitnes
= b, i I
dengan
i=1,2,..., j
+" =totfitnes
Pr
dengan Pr = fitnes relatif tiap kromosom
Qt =P,r,Q,r=QottPu dengan,
Qu ft
15.21
=
15.3I 15.41
= fitnes komulatif = 2,3,...,j
Penggunaan funggi evaluasi diterapkan pada populasi yang ada, sehingga akan didapai populasi penuh seperti pada tabel 5.3 yang berisi populasi beserta n-ilaifitnesnyal-
o) Kromosom metapakan kumpulan
dari beberapa gen atau node
66 JURNAL INFORMATIKA, VOLUME
4 NOMOR
1, APRIL 2OO8
Tabel 5.3 uh beserta
t9 -5 -20 -5 -20 -6
-2-9 -2 -9 -2 5 -8
- 12 -8
-23 -
t2-24 -12 -8 -2 s -29 - r 6- 4-6 - r - 6 -20 19 -2t - t3 -t 5 -\3 -2t -13 -21 -7 -18-4-6-l -228-l 6- 1 8-3-l 5-t3-21-13-21-13-29-3-298
I
-l
Evaluasi
0.0008
0.rt27
0.1127
0.0007
0.0986
0.2113
0.0018
o.2535
0.4648
0.0004
0.0563
0.5211
0.0006
0.0845
0.6056
0.0009
0.1268
0.7324
0.0005
o.0704
0.8028
0.0006
0.0845
0.8873
0.0004
0.0563
0.9436
0.0004
0.0s63
0.9999
-
t3-29 I9
-2t -7 - 18 - 1 6 -28 -2-l -6 -20 - 5 -20 - I s - 13 -
2t - t3 -t
5 -13 -l 5-3 - 1 8- I 6-4
-l 6-4-1
6
-4 -28
-2 | - 13 - I s -20 -1 5 -3 -I s -20 - t 5 -20 - s -20 -20 -6 - | -2-9 - t 4-9 -2-9 - r 4 -9 -2-28 -r 5 -28 t9 - 5 -20 -s -20 -5 -20 -6 -l -2-28 -2 - 1 -2 -28 -2 1
9
5
9 -25 -9
-l
4-9 -2-r - 6 -20 - 6 -4 - |
6-4
-20 -6 -1 -2 -9 -2 s -8 -2 5 -9 6 -20 - 6 -4 - 6 -20 - 5 -20 t9 -26-22-24-t2-t7 -12-24-22-t7 -12-8 12-24-7 -24-22-17 -10 -23 -r 4-9 -l 4-9 -2t 9 -2 | -7 - I
25
8
-3 - t 5
-28-2-28 - | 6 -4-
28-16-28-16 t9-21-7 -29-13- 1 s-3- 1 8-16-4-16-l 8-319 -
t3 -2 l -7 - | 8- | 6 -28 -2-9 - t
-
4 -9 - | 4 -9 - t 4
23-14 t
9
-s -20 - 5 -20 -6 -20 -5 -20 -5 -20 -5 -20 -6 - | -2s -9 - r 4 -23 -8 -23 -8 - 12 -r7 -22-26 - t I
2 -9
t9 - s -20 - 6-4 -6 - | -6 - | - 6 -4 - t 6-28 -l | -2-9
6-4-6
-
-2-9 -25 -8-23 -1 4-23 -10-23-8
Tahap kelima dilakukan seleksi setiap kromosomnya dengan menggunakan metode Routette Wheel Selection, yang menggunakan bilangan random sebagai bilangan pembandingnya, dan hasil seleksinya dapat dilihat di tabel 5.4 dimana bentuk populasi baru muncul setelah proses seleksi. Tabel 5.4
baru hasil seleksi
t9-21-7-
8
-3 - r 5
-20 -6 - | -2 -9 -2s -8 -25 -9 -2s -
28-2-28- 6 -4 -6 -20 -6-4 -6 -20 - s -20 t9 -2t -7 -18- | 6-28-2-I -6-20-5 -20 -l 5 -t3 I 3-1 5-13-l 5-3-1 8-16-4-16 -4-t6-4-28 1
9
-2 T -7 - I 8 - | 6-28 -2- | -6 -20 -5 -20 -l
13-1 5-1
-
-21 -
3-15-3-18-16-4-t6-4-16-4-28
t9 - s -20 -6 -49
5-t 3
-21
6-
| -6- 1 -6-4- r 6 -28 -l
6
-4 - 6 - | -2
-
-2-9 -25 -8-23 -t 4-23 -10-23 -8 9-5
-20 - 5 -20 -6 - | -2-9 -2-9 -25 -8 - 12 -8 -23 -8 -
2-24- 12-8 -2s -29 - r 6 -4- 6 - l - 6-20 9 -21 -7 -t8- r6-28-2-t -6-20-5 -20 -l 3- 1 5- 1 3- 1 5-3 19
5
-t3 -21 -
-18-16-4-16-4-16-4-28
0.0009
0.1268
03324
0.0018
0.2535
0.4648
0.0018
0.2s35
0.4648
0.0004
0.0563
0.9999
0.0008
0.1t27
0.112'7
0.0018
0.253s
0.4648
0.0005
0.0104
0.8028
0.0007
0.0986
0.2113
-26-22-24-12-lt -12-24-22-11 -12-8- 12-
24 -7 -24 -22 -
1',7
- | 0 -23 - I 4 -9 - t 4 -9 -2 -28 -
t 6-28 -
I6 I
9
-2t - t 3 - | 5 - 13 -21 -13 -2 I -7 - t 8 -4-6 -l -2-28 8-3-l s-1 3-2t-r3-21-13-29-3-29-t3-29
I 6-1
Nugroho, Algoritma Genetika Dalam Program pencarian Jalur Atternatif 67
l9-2t-7-29-13- 15-3- I 8-16-4-1 6-l 8-3-19-132l -7 -18-t 6-28-2-9 -t 4-9 -t 4-9 -l 4-23 -1 4 t9 -21 - t3 -r 5 -20 - 1 5 -3 - I 5 -20 - I 5 -20 -5 _20 20 -6- | -2-9 - I 4 -9 -2-9 - I 4 -9 -2 -28 - t 5 -28
_s _
0.5211
Tahap keenam adalah proses penyilangan dan proses mutasi dimana proses ini dilakukan untuk mencari variasi bentuk kromosom ynag baru. Penyilangan dilakukan dengan menggunakan metode Multi Point Crossover dan dalam kasus ini jumlah titik potong ada dua buah yaitu pada gen ke-dua dan gen tengah kromosom. Setelah melatui proses penyillngan dan mutasi maka akan didapat populasi baru sepertitampak pada tabel 5.5 Pada tabel 5.5 hasil populasi akhirterlihat jika nilaijaluryang baru adalah dari node 19 ke node 2 melalui node21-7-18-16-29, atau dengan kata lain ketika dariJl. Dr. Wahidin akan ke hotel garuda di ujung jalan malioboro melewati Jl. Lempuyangan dan Jl. Abu BakarAli. Ketika terjadi pemutusan jalur dari node 7 ke node 18 proses penyelesaian masih dengan perhitungan yang sama tetapi node asal merupakan node awal pemutusan dan jalur yang terpotong tidak akan ikut dalam proses pencarian, sehingga diperoleh jalur alternatif yang melewati node 24-22-17-12-8-23-14-9-2, atau dari lempuyangan melewati ji. Suryatmajan- dai akhirnya melewati malioboro ke ujung malioboro dekat hotel garuda. Tabel 5.5
akhir
t9 -21 -7 -18-3 -l 5 -20-6-t -2-9 -25 -8-25 -9 -2s 6 -4 - 6 -20 -6 - 4 - 6 -20 - s -20 9 -21 -7 - I 8 -t 6-28 -2- | -6-20 - 5 -20 - | 5 - t3 -2t -
28 -2 -28 - t
3- I 5- I 3- 1 5-3- 1 8- I 6-4-1 69 -21 -7
4-6-4-16-28
-t 8-t 6-28-2-t -6-20-5 -20 -1 5 -13 -21 1 8- 1 6-4- I 6- 4-6-4-t6-28
3- 1 5- 1 3- I 5-3-
-20 -6 -4-6 -t -6 - | -6-4- I 6 -28 - | 6-4 -6 - | -2-2-9 -25 -8-23 - I 4-23 - t0 -23 -8 I 9 -21 -7 -t 8 -l 6-28-2- l -6-20 -s -20 - I 5 - t3 -2t | 3 - I 5 -12-24 -t2-8-25 -28 -t 6 -4 - 6 - I - 6 -20 I 9 -21 -7 -18 - | 6-28 -2- | -6 -20 - 5 -20 - I s - 1 3 -2 I 19 - 5
9
5-3-18-16-4-16-4-6-4-t6-28 I 9 -26-22-24 - t2- t7 - 12-24 -22 - t7 - t2 -8 - I 2 l 3- 1 5- r 3- I
24 -7
-24-22-17 - I 0 -23 - I 4 -9
- I 4 -9
-2 -28 - I 6 -
0.0009
0.0928
0.0928
0.0018
0.1
856
0.2784
0.0018
0.1856
0.4640
0.0004
0.0412
0.5052
0.0018
0.1856
0.6908
0.0018
0.1856
0.8764
0.0005
0.0515
0.9279
0.0007
0.0722
0.1001
0.0006
0.0619
1.062
0.0004
0.0412
1.1032
28-16 I 9 -21 - t3
-I
5
- 13 -21 - t3 -2 t -7 - I
I -4 -6 - | -2 -28 -
3-21-13-21-13-29-3-29-13-29 19-21-7 -29-t3-1 5-3- 1 8-16-4-16-1 8-3-191
6- I 8-3- 1 5-
t 3 -21 -7 - I
1
-t
-28 -2-9 - I 4 -9 - t 4 -9 - I 4 -23 -t 4 | 9 -21 - 1 3 - 1 5 -20 - 1 5 -3 -t 5 -20 - t 5 -20 - s -20 - 5 20 -6-I -2-9 - I 4 -9 -2-9 - I 4 -9 -2 -28 - I 5 -28 8
6
6. Kesimpulan Berdasarkan perancangan dan implementasi sistem dapat diambil beberapa kesimpulan
sebagai berikut: Hasil pencarian jalur alternatif bervariasi. Hal ini ditentukan oleh beberapa faktor diantaranya jumlah iterasi, jumlah egde, dan jumlah node.
Penggunaan bilangan random menjadikan beberapa kali pencarian yang dilakukan tidak dapat mendapatkan hasil yang diharapkan.
r
68 JURNAL INFORMATIKA, VOLUME 4 NOMOR 1, APRIL 2OO8
7. Daftar Pustaka Aries Syamsuddin, Pengenalan Algoritma Genetik, Kuliah umum
ilmukomputer.com,
hftp://www.ilmukomputer.orq/wp-contenUuploads/2O06/08/aries-qenetik.zip, 23 oktober 2007 Gross, Jonathan, Jay Yellen., Graph Theory and lts Applications., CRS Press., London., 1998
- Teknik Heuristik., Ghaha llmu., Yogyakarta., 2005 Profesor Edy Tri Baskoro, Mengenalkan lndonesia Melalui Teori Graf, Pidato llmiah Guru Besar lnstitutTeknologi Bandung, Balai Pertemuan llmiah lTB, 13 Juli 2007 Rennard, Jean Philippe Ph.D, Genetic Algorithm Wewer: Demonstration of a Genetic Algorith m, hff p ://www.rennard.orq/al ife/enql ish/Gavi ntrsb. html, 23 oktobe r 20O7 Komputel Wahana, Panduan Praffiis Pemrograman Borland Delphi 7.0, Andi Offset, Kusumadewi, Sri, Hari Purnomo., Penyelesaian Masalah Optimasi dengan Teknik
Yogyakarta, 2003
Alam, M. Agus
J, MySQL
Seruer versi 5 dan Aplikasinya dalam Wsual Basic 6 dan Delphi,
Elex Media Komputindo, Jakarta, 2005
Madcoms, Seri Panduan Pemrograman Yogyakarta, 2006
:
Pemrograman Borland Delphi 7, Andi Offset,
