IMPLEMENTASI ALGORITMA GENETIKA UNTUK PENCARIAN RUTE PALING OPTTMUM Anies Hannawati,Thiang, Eleazar Fakultas Teknologi lndustri, JurusanTeknik Elektro, Universitas Kristen Petra Jl. Siwalankerto121-131, Surabaya,60236 ac'icl ac.icl; thians(/lpeter'Dertra' E-mail : an i es:?iipetra.
Abstrak
Algoritma genetika dapat digunakan untuk menyelesaikan masalah optimasi yang kompleks ieperti ntZncari rute paling optimum dengan memperhatikan kondisi jalan misalnya *epidatan lalulintas, jalan satu arah dan lain-lain. Dalam maknlah ini akan dijelaskan tentang algorinta genetika untuk nrcncari rute yang paling optimurn dari titik asal ke titik pin"ropon 'tuiuan. Kriteria optimim disini adalah waktu danjarak tempuhyang paling minimal dari titik asal *i tttitctujuan dingan memperhatikan berbagai kondisi ialan seperti kepadatan lalulintas, ialan satu arah atau dua arah, juga syarat harus melalui titik tertentu. Sistematgoritmi ginetika yang telah didisain menggunakanrepresentasikromosom dalant juga bentuk bit string. Karena itu jenis nrutasi yang digunakan adalah mutasi bit. Sistem ini metode gabungan antara yaitu roulette wheel, elitism dan menggunakanbiberapa metode selelcsi ,ort"it" wheel dan elitism. Ada dua jenis crossoveryang digunakan yaitu one cut point crossover dan two cut point crossover. Beberapapengujian telah dilakukan untuk menguji sistem ini. Pengujian dilakukan dengan variasijumlah-kromoiom dalam satu populasi, variasi nilai crossover rate, variasi nilai mutation rate, iariasi metode seleel<si dan variasi metode crossover. Dari hasil pengujian, dapat disimpulkan bahwa secara keselunthan, algoritma genetika yang telah didisain dapat berjalan dengan baik dan dapat menyelesaikanpermasalahan' Kata Kunci : algoritma genetika, krontoson,mutasi, selel<si,populasi, reproduksi l.
Pendahuluan
Ilmu pengetahuandan teknologi pada akhir-akhir ini berkembangdengan begitu pesatnya. Seiring dengan itu muncul berbagai masalah-masalahyang baru, antara lain adalah masalah juga optimasi. Optimasi adalah pencarian nilai-nilai variabel yang dianggap optimal, efektif dan efisien untuk mencapai hasil yang diinginkan. Masalah optimasi ini beraneka ragam tergantung jumlah dari bidangnya, misalnya dalam-industri antara lain pengaturan jam kerja karyawan, ini masalah penelitian persediaanlahan baku, jalur distribusi yang optimal, dan sebagainya.Dalam optimasi yang dipilih uauUn masalah dalam bidang transportasi, dimana akan dicari optimasi dalam pencarian rute terpendek, waktu tercepat dan kondisi-kondisi yang timbul didalamnya untuk jalan/kota. sebuahjalur perjalanan dari posisi awal menuju posisi tujuan pada suatu peta lokasi yang dari optimal variabel nilainilai mendapatkan untuk Untuk iiu aipatutan suatu metode/cara tersebut, optimasi masalah pemecahan p€rumusanmasalah-masalahtersebut.Bermula dari tuntutan pada tahun 70-an muncul sebuah algoritrna baru yang dikenal dengan algoritma genetika yang berfungsi untuk memberikan solusi untuk masalah optimasi tersebut. Selanjutnya makalah ini akan diorganisasisebagaiberikut, bagian kedua akan menjelaskan secarasingkat mengenai algoritma genetika secaraumum. Berikutnya, akan dijelaskan mengenai disain sistem yang membahas mengenai perencanaandan pembuatan perangkat lunak, diikuti d,cnganpetrgujiatriistem dari perangkatlunak yang telah dibuat. Terallrir, akan disimpulkan halral yang berkaitan denganpenelitian ini.
ImplementasiAlgoritma Genetikauntuk PencarianRute PalingOptimum
2.
A-3r
Algoritma Genetika(r'2)
Algoritma genetika.merupakansuatu metode pencarian yang didasarkan pada mekanisme dari seleksi dan genetika natural. Secara umum, blok diagram dari mekanisme kerja algoritma genetika ini adalah seperti yang terlihat pada Gambar 1.
PENENTUANNILAI AWAL
POPULASIAWAL
PROSES TEWTNSILANG
PROSES SELEKSI
EVALUASI& KRITERIA PENGHENTIAN RECENERASI
Gambar I. Diagram Alir Algoritm Genetika
Algoritma genetika dimulai dengan.pembentukan sejumlah alternatif pemecahan yang populasi.. Pembentukan populasi awal dalam algoritma genetika dilakukan secara acak. frds mflm populasi tersebut terdapatanggotapopulasi yang disebut dengankromosom, yang berisikan mfumsi solusi dari sekian banyak alternatif solusi masalahyang dihadapi. Kromosom-kromosom mengalami evolusi melalui sejumlah iterasi yang disebut generasi. Dalam setiap perjalanan fu generasi, kromosom-kromosom tersebut akan dievaluasi menggunakan suatu fungsi yang wm dengan fungsi obyektif. Setiap generasi akan menghasilkan lcromosom-kromosom yang ffitr hrro png dibentuk dari generasi sebelumnya dengan menggunakan operator reproduksi, kawin nmrmgdan mutasi. Kromosom-kromosom yang mempunyai nilai obyel:tif yang baik akan memiliki yang lebih tinggi untuk tersbleksi. Setelah beberapa kali proses generasi tersebut dnbilitas algoritma genetika akan menunjukkan kromosom yang terbaik, yang diharapkan ffifuhm, solusi yang optimal ataupun mendekati optimal dari problem yang dihadapi. Hal lain
Komputer dan SistemIntelijen (KOMMIT2002) Proceedings, Auditorium UniversitasGunadarma,Jakarta,2l - 22 Agustus2002
A-32
yang perlu diperhatikan adalah representasi kromosom yaitu bagaimana mengkodekan suatu genetika. utt"*"Uf rutusi itu menjadi laomosorriyang akan diprosesmenggunakanalgoritma proses reproOutcsi merupakan'suutu ptosrs untuk membentuk keturunan baru dengan sebely-nV.amerupakan mewariskan sifat-sifat yarrg ,urn" dari kromosom induk. Proses reproduksi Hal ini dilakukan yang lamalcromosom induk fror". duplikasi aan tiAai menghilangkan-sifat hilang begitu yang akan baik tidak halam pror", algoritma genetikauntuk menjagasifat-sifat induk saja.
proses kawin silang memerlukan dua kromosom induk Proses ini dilakukan dengan dari kromosom menukar sebagian informasi pada kromosom induk pertama dengan informasi rate yang crossover adalah silang kawin proses induk kedua. Parameter yang penting dalam lcawin silang mengalami akan nilai perbandingan jumlah-kromosom yang diharapkan memungkinkan akan yang tinggi -"*put"., terhadap jumlah Lro*oro* daiam satu populasi. Crossover rate alternatif solusi yang lebih bervariasi dan mengurangi kemungkinan menghasilkan nilai p.*"p"iir yang tidak dike-hendaki- Tetapi bila nilai ini terlalu tinggi akan mengakibatkan ipti*rr* *utto untuk melakukan perhitungan di daerah solusi yang tidak menjanjikan hasil p"-boro.* yang optimal. proses mutasi merupakan salah satu &ri operator genetika untuk menghasilkan perubahan satu acak pada satu lcromoso*. buru terniudah untuk melakukan mutasi adalah dengan mengubah rate Mutation rate. atau iebih bagian dalam kromosom dan.hal ini tergantung pada mutation mutasi. menentukan piobabilitas jumlah bit di dalam satu populasi yang diharapkan mengalami muncul Apabila nilai mutation rui" terlalu kecil, banyak bit+it yang berguna rnungkin tidak akan sifar kehilangan akan yang dihasilkan keturunan maka aAam populasi, tetapi apabila terlalu tinggi genetika algoritma dan tuanya orang dari yang unggul sifat yan! mungkin-saja merupakan sifai akan tehilangut k"*u*puan untuk belajar dari pencarian-pencarian sebelumnya' proses seleksi proses evolusi yang menghasilkan generasi baru dari generasi"aA.ir generasi sebelumnya.Generasi-generasiyang baru dapat terdiri dari laomosom-kromosom induk RouletteIan turunan. Metode seleksi pada algoritma genetika ada bermacam-macam,antara lain Steady-State Selection, Toumament Selection, Rank Bolizmann, Wheel, Elitism, Sigma Scaling, Selection,.dan gabungandari metodemetodetersebut. 3.
Disain Sistem Algoritma Genetika untuk Mencari Rute Paling Optimum
p"J-ilq Dalam penelitian ini, algoritma genetika diimplementasikan untuk mencari rute yang memiliki rute adalah disini optimum dari tilik asal ke titik tujuan. Pengertianrute optimum genetika waktu tempuh dan total jaraknya paling minimal. Berikut akan dijelaskansistem algoritma yang telah didisain dan pembuatanproseduruntuk prosesalgoritma genetika' 3.1
Disain SistemAlgoritma Genetika
Representasi kromosom merupakan cara bagaimana mengkodekan suatu altematif genetika- Dalam solusi itu menjadi kromosom yang akan diproses menggunakan algoritma Panjang bit string. bit bentuk dalam penelitian ini, representasi kromosom yang digunakan ioo*ororn yatrg akatt digunakan dapat ditentukan dari persamaanberikut:
r =(s-rhc
(1)
jumlah bit dari dimana p adalahpanjang bit kromosom; S adalahjumlah spoVtitik dan C adalah percabangan maksimal yang dikodekan dalam biner. banyaknya yang dianggap F*iung bit t&sebut bukan merupakan nilai yang mutlak, melainkan nilai .,aman',agai tJat< terjadi unsolvedcondition,yaitu kromosom tidak memberikan solusi pemecahan jumlah hop maksimal yang mampu masalah. Fanlang kromosom itu sebegarnyamerepresentasikan titik ke titik lain yang merupakan satu dari perpindahan proses dilakukan. Hop merupakan rumus: dari tetangganya.Jumlah hop maksimal dapat diperoleh
A-33
ImplementasiAlgoritma Genetikauntuk PencarianRute Paling Optimum
p
H=L
(2) C
dimana H adalah jumlah hop maksimal yang mampu dilakukan, P adalah panjang lcromosomdan Cadalahjumlahbitdari banyaknya percabanganmaksimal yang dikodekandalambiner Teknik dekode kromosom yang digunakan dalam representasikromosom adalah sebaga berikut: l. Pemberian ID/nomor, dilakukan agar dapat dikenali untuk setiap percabangan dari masingmasing spot pada gambarrute 2. Pemotongan kromosom, dilakukan sebesarjumlah bit dari maksimal banyaknya percabangan yang dikodekan ke dalam biner 3. Pendekodeanbit-bit, dilakukan sesuai dengan nomor cabang menjadi sederet hop-hop yang akan menghasilkan sebuahrute perjalanan Dalam penelitian ini, permasalahanoptimasi yang ingin dicapai adalah rute yang paling optimum dengan parameter waktu tempu dan jarak yang paling minimal. Karena itu, fungsi obyektifyang digunakan dalam sistem ini adalahsebagaiberikut: i
(i
\
\ i =t
)
*(v"w).| f(*,,)=(v,o)*|r, Ir, 1., i=l
(3)
dimana f (x,t) adalah fungsi obyektif, j adalahjumlah hop yang diperlukan hingga mencapai titik tujuan ataupun jumlah hop maksimal apabila titik tujuan tidak dicapai, x adalahjarak antar titik, t adalah waktu antar titik, v adalah kecepatan konstan, %D adalah bobot persentase untuk jarak dan %W adalahbobot persentaseuntuk waktu. Berikut ini, Tabel I menunjukkan spesifikasi dari sistem algoritma genetika yang telah didisain dan parameter-parameter yang digunakan dalam pembuatan perangkat lunak untuk algoritma genetika. Tabel I. SpesifikasiSistemAlgoritma Genetika dan Perangkat Lunak Jumlah Spot
MaksimumPercabansan JumlahPopulasi PanjangKromosom maksimum Jumlah Hop maksimum Metoded Seleksi yang digunakan
32 Spot 8 Percabansan
(l - 400) Dapatdiubah-ubah 96 Bit 32Hop l. SeleksiRoulette-Wheel
2. SeleksiElitism 3. SeleksiGabungan
JenisProsesReproduksi JenisProsesMutasi Nilai Mutationrate JenisProsesKawin Silang
S stim Duplikasi S stimBit 0- I 1. Sistimsatutitik potong 2. Sistimduatitik potong
Nilai crossoverrate Kriteria Penghentian Regenerasi Syarat
0- 1 10000 senerasiberikut tidak ada yans lebih optimum l. Rute harus dilewati
2. Rutetidakbolehdilewati
Proceedings,Komputer dan Sistem Intelijen (KOMMIT2002) Auditorium Universitas Gunadarma,Jakarta,2l - 22 Agustus 2002
L-34
3.2
Pembuatan Prosedur Algoritma Genetika
Perangkatlunak algoritma genetikadidisain denganmenggunakanbahasaprogram pascal. Prosedur-proseduryang dibutuhkan oleh algoritma genetikaini, antaralain: o ProsedurAngka Acak Angka acaHrandom yang digunakan dalam algoritma genetika ini memakai fungsi yang telah disediakan oleh bahasaprogram pascal. o ProsedurReproduksi Prosedur ini akan menduplikasi ulang kromosom induk secaralengkap sehingga menghasilkan turunan baru yang sama dengan induknya. ProsedurKawin Silang Prosedur ini akan memilih dua krornosom induk yang akan mengalami proses.kawin silang secara acak, kemudian menetukan satu atau dua titik potong secara acak pula. Setelah titik potong ini terpilih maka dilakukan proses penukaran informasi dari kedua kromosom itu berdasarkantitik potong yang telah ditentukan.Probabilitassebuahkromosom akan mengalami kawin silang atau tidak, bergantungpada nilai crossoverrate yang diinputkan melalui PC. ProsedurMutasi Prosedurmutasi yang akan digunakan adalahmutasi bit. Setiapbit dari kromosom tersebutakan mempunyai peluang sendiri untuk mengalamimutasi. Probabilitasterjadinya mutasi pada setiap bit ditentukan oleh nilai mutation rate yang diinputkan melalui PC. ProsedurSeleksi Seleksi yang digunakan dalam penelitian ini adalahmetode roulette-wheel, metode elitism dan gabungan kedua metode tersebut. Dalam metode roulette-wheel, peluang setiap lcomosom untuk terseleksi sebanding dengan nilai obyektifnya. Semakin besar nilai obyektif, maka semakin besar peluang untuk terseleksi. Karena permasalahanoptimasi yang ingin dicapai adalah mencari wakfu tempuh dan jarak yang paling minimal, maka untuk metode seleksi roulette-wheel, fungsi obyektif masing-masingkromosom akan diubah dengan menggunakan Dersamaanberikut:
f'(*,)= .f(r)^- +,f(")"* - f(r,)
(4)
obye}tif baru, ,f(t)"*.adalah nilai obyektif maksimum, ,f(")r" adalah nilai obyektif minimum dan /(x,) adalah nilai obyektif sebelumnya.Metode elitism melakukan proses seleksi dengan mengambil laomosom terbaik sebanyak jumlah populasinya.Metode gabunganyang dipakai dalam penelitian ini menggunakankomposisi 30% populasi diperoleh dari metode elitsm dan sisanyadenganmemakai metode roulette-wheel. dimana f'(*,)adalah
nilai
ProsedurPopulasi Awal Prosedur ini akan membangkitkan sejumlah kromosom secaraacak untuk membentuk populasi awal. Jumlah kromosom dalam satu polulasi dapat bervariasi sesuai dengan setting awal yang telah ditentukan. ProsedurPenghitunganGenerasi Prosedur ini dibuat untuk memeriksa apakah kriteria berhenti dari algoritma genetika sudah dipenuhi atau tidak. Hal ini dilakukan dengan menghitung jumlah generasi sampai batas maksimum yang diberikan. Bila dalam jumlah generasiyang ditentukan tidak ada kromosom yang lebih baik maka algoritma genetika akan berhenti melakukan proses iterasi. Semakinbesar
ImplementasiAlgoritma Genetikauntuk pencarianRute paling Optimum
A-3s
nilai batas maksimum generasi tersebut maka hasilnya dapat menjadi lebih baik, namun akan memerlukan prosesyang lebih lama. o Prosedur PengukuranJarak Prosedur ini untuk mengukurjarak denganmenggunakanpersamaanpythagoras. o Prosedur Pengukuran Wakfu Prosedurpengukuranwaktu ini dibagi menjadi dua bagian yaitu waktu untuk jam-jam sibuk dan waktu untuk jam-jam normal. e Prosedur Syarat Prosedur syarat merupakan prosedur untuk memeriksa apakah syarat yang diberikan sudah tercapai atau belum, yaitu syarat rute yang harus dilewati dan tidak boleh dilewati. Jika syarat yang diberikan sudah tercapai, maka kromosom tersebut akan menjadi kromosom yang valid, sedangkanjika syaratyang diberikan tidak tercapai,maka kromosom tersebut dianggap invalid. 1.
Pengujian Sistem
Pengujian proses algoritma genetika dilakukan dengan melakukan perubahan nilai parameter yang digunakan, yaitu nilai crossover rate, nilai mutation rate maupun nilai jumlah lromosom per populasi. Selain itu, pengujianjuga dilakukan dengan memberikanbeberapa syaratsyarat untuk melihat tingkat keberhasilannya.Percobaandilakukan dengan mencari rute terpendek dan waktu tersingkat berdasarkan kondisi rute, yang akan dibagi menjadi beberapa bagian berdasarkanada atau tidaknya syarat untuk pengujian jarak saja dan p"nguliutr jarak dan waku. Benruk rute pengujian dapat dilihat pada Gambar 2. Pengujian yang dilakulan aOatatrmencari rute paling optimum dari titik spot menuju ke titik spot 32.
Gambar 2. Rute Pengujian
Melalui perhitungan secaramanual didapatkan nilai obyektif yang terbaik adalah 569.52 lrn dan rute yangterpendekadalahrute dari spot I - 2-lg-21-27 -zg -32. Hasil pengujian sistem yang paling sederhana,tanpa menggunakansyarat,juga menghasilkannilai Fng sama denganperhitunganmanual. Tabel 2 menunjukkan beberapahasifpengujian yang telah dilakukan dari pengujian di atastadi denganmenggunakanmentode seleksi roulette-wheel. Tabel 3 rrenunjukkan beberapa hlil pengujian yang telah dilakukan dari pengujian yang sama dengan menggunakanmentode seleksielitsm dan tabel 4 menunjukkan beberapahasil pingujian yang telah dilakukan dari pengujian yang sama dengan menggunakanmentod" rll"kri guUutrgundari metode roulette-wheeldan elitsm.
Proceedings,Komputer dan Sistem Intelijen (KOMMIT2002) Auditorium UniversitasGunadarma,Jakarta,2l -22 Agustus 2002
A-36
Tabel2. Beberapa Hasit Penguiian dengan Metode Selel<siRoulette-Wheel, Variasi Nilai Crossover Rate dan Mutation Rate
t{o
Nilai Nilai Crossover Mutasi
I
2 3 4 5 6 7 8 9
t0 l1
t2 13 l4 15 16 T7 l8
t9 20 2l
22 23 24 25 26 27 28 29 30 3l
32 33 34 35 36
(dt)
1 I I I I I
0.01 0.05 0 .1 0.3 0.5
2 4' l3
l4
Tetbaik 569.52 569.52 569.52 569.52 569.52
0.7
10
s69.52
I
0.9
ll
0.9 0.9 0.9 0.9 0.9 0.9 0.9
0.01 0.05 0.1
l1 10 13 14
569.52 65t.62
0.8 0.8
0.3
13
r0-
s69.57 569.s2 569.52
Akhir Generasi 2745 r-2-t8-2t-27-28-32 1479 t-2-t8-2r-27-28-32 r-2-r8-2r-27-28-32 1408 Rute
t-2-18-2r-27-28-32 L-2-t8-21-27-28-32 t-2-18-21-27-28-32 r-2-r8-2t-27-28-32 | -2-I 8-r9-20-21-27-28-32 r-2-18-21-27 -28-32 r-2-18-2r-27-28-32 r-2-t8-21-27-28-32 t-2-t8-na7-28-32 r-2-18-19-20-28-32
1036
t-2-t8-21-27-28-32 r-2-18-21-27-28-32 t-2-t8-21-27-28-32 t-2-t8-2r-27-28-32
r065
t-2-18-21-27-28-32
lM7 l1 6 4
!220 1.188 1109 tM7
t443
I 138 1141 r-2-r8-2r-27-28-32 I 1 3 9 t-2-18-21-27-28-32 1257 1-2-18-21-27-28-32 1 3 4 8
0.5 4.7
10
569.s2
ll
577.08
0.9
10
s69.52
0.01 0.05 0.1 0.3
t1 t2
569.52 569.52
10 10
s69.52
0.8 0.8 0.8
0.s
13 10
569.52 569.52 569,52
l0
569.s2
0.6 0.6
0.01 0.05
0.6 0.6
0 .1 0.3
23 t6 t3
0.6 0.6 0.6 0.4 0.4 0.4 0.4 0.4
0.5 0.7 0.9
r-2-t8-21-27-28-32 r-2-t8-2r-27-28-32 r-2-t8-21-27-28-32 na7 1-2-t8-21-27-28-32 1095 r-2-t8-21-27-28-32 s69.52 11 7 5 r-2-t8-21-27-28-32 s69.52 1399 1-2-t8-2r-27-28-32 s69.52 19 696.39 | -6-2-r 8-r9-20- -20-28-32 1036 1-2-18-21-27-28-3? 2700 569.52 t092 t-2-r8-21-27-28-32 569.52 1016 r-2-t8-19-20-28-32 s77.08 r093 r-2-18-21-27-28-32 569.52 t279 r-2-18-21-27-28-32 569.52
0.8 0.8
0.4 0.4 0.1
37 38 39
0 .1 0.1 0 .1
40 4L
0.1 0.1
42
Waktu Obyektif
0.1
0.7 0.9
0.01 0.05 0.1
0.3 0.5 4.7 0.9 0.01
0.05 0 .1 0.3 0.5 0.7 0.9
11 10 11 13 924 10 9 l0
t2
569.52 569.52 569.52 569.52
I 118 1368 1043 1030 2788 1742 1384
569.52 634.97
r-2-r8-2r-27-28-32
1628
t-6-18-21-2748-32
t2 10
s69.s2
11 l0
569.s2 569.s2
t2 t5
569.52
L-2-r8-21-27-28-32 L2-,3A1-27-28-32 t-2-r8-21-27-28-32 t-2-18-21-27-28-32 r-2-t8-2r-27-28-32 r-2-18-21-27-28-32
t209 1309
16 ll
569.52
s69.s2
1089 1237 1116 t349 1676
A- 37
ImplementasiAlgoritma Genetikauntuk PencarianRute Paling Optimum
Tabel 3. Beberapa Hasil Pengujian dengan Metode SeleksiElitism, Variasi Nilai CrossoverRate dan Mutation Rate No. I
2 J
Nilai Waktu Obyektif Nilai (dt) Terbaik Mutasi Crossover 569.52 I 0.0r t5 I t7 569.52 0.05 569.52 I 0.1 il
4 5 6
I
1
I I
8 9 10 l1 l2 13 l4
15
r6
I I
0.9 0.9 0.9 0.9 0.9 0.9 0.9 0.8 0.8 0.8
0.3 0.5 0.7
0.9 0.01 0.05 0.1 0.3 0.5
0 .7
t3 9 7 6 0
0.05 0.1 0.3 0.5 0.7 0.9
569.s2
t-2-18-21-27-28-32
r 183
569.52 569.52 569.52 569.52 569.52 569.52
t-2-t8-21-27-28-32
r337
t-2-t8-21-27-28-32 t-2-18-2t-27 -28-32
2057
l-2-r8-2t-27-28-32 t-2-t8-21-27 -28-32 t-2-18-21-27-28-32
1063 1018 1316
569.s2
t-2-r8-2r-27-28-32
l11l
2 9
0 9 0
0.05
24
0.6 0.6 0.6
0.1
I
0 .3 0.5
0 0
0.6
0.7 0.9 0.01 0.05 0.1
1 0 9 6
0 .3 0.5
0
0.7 0.9 0.01 0.05
0
0.4
aa
0.4
34 35 36 37 38
0.4
39
0 .1
40 41
0.1 0.1 0.1
A'
0.4
0 .1 0.1 0.1
2
J
I
930.66 r,2-r 8-17-22-| 6-22-27-28-32 569.52 t-2-18-21-27-28-32 t-2-r8-2t-27-28-32 569.52 569.52 r-2-r8-2r-27-28-32 r-2-18-2r-27-28-32 569.52 t-2-18-2t-27-28-32 569.52 s69.s2 t-2-18-21-27-28-32 1-2-18-21-27-28-32 569.52 1-2-18-21-27-28-32 569.s2 r-2-r8-21-27-28-32 569.52 1-2-18-21-27-28-32 569.52 1-2-18-21-27-28-32 569.52 t-2-r8-21-27-28-32 569.52
4
569.s2
r-2- 8-2r-27-28-32
2
569.52
.+
s69.52 569.52
s69.52
r-2- 8-21-27-78-32
0.5
2l l0 l0
l-2- 8-2r-2748-32 l-2- 8-21-27-28-32 l-2- 8-2r-27-28-32
569.52
0.7
t2
s69.52
t-2- 8-2t-27-28-32 L-2- 8-2r-27-28-32
0.9
It
s69.s2
r-2- 8-21-27-28-32
0 .1 0 .3
t22s
t-2-t8-2r-27-28-32
0.6
JJ
1668 t79
t-2-t8-2t-27-28-32
s69.s2
6 5
0 3 1
32
r-2-r8-2r-27-28-32
1385 t774 t554
0.8 0.6
0.6 0.4 0.4 0.4
t852
1389 t01l
t-2-18-2t-27 -28-32 t-2-t8-21-27-28-32
2l 22 23
29 30 31
t-2-18-21-27-28-32
tzt5
569.52
0 .8
27 28
I 905
s69.52 s69.52
20
25 26
r876
t-2-r8-2t-27-28-32 r-2-r8-2t-27-28-32 t-2-t8-21-27-28-32 t-2-t8-21-27-28-32
1
0 .8
0.0r
L-2-18-21-27-28-32
2
18 T9
0.8
s69.52 s69.52
Akhir Generasi
t-2- 8-2r-27-28-32 t-2-r8-2r-27-28-32
1 -t
0.9
0 .0 1
569.52 569.52 569.52 569.52
Rute
r23l
t3r4
1408
tt22 I 105 1114 I 104 I 133 1078 1015 1782 t415 1071 I 188 I 138 t529
r526 r524 2228 1099 I131
13t2 tt94
Proceedings,Konputer dan Sistem Inrelijen (KOMMIT2002) Audirorium Universitas Gunadarma, Jakarta,2l _ 22 Agustus 2002
TM 1. Wry Hasil ParyujiandanganMetodeSeleksiGabungan ian Elitisn, Yariasi Nilai crossoverRate dan Mutation Rate Rmtac-nhd lio I
2 a
J
4 5 6 7 8 9 l0
Nilai Nilai Waktu Obyektif (d0 Crossover Mutasi Terbaik
I I
0.0r 569.52 s69.52 0.0s 15 569.52
t-2-18-2t-27-28-32 t-2-18-2t-27-28-32
I I I
0.1
ll
L-2-t8-2t-27-28-32
0.3
t2 t2
7
I
l3
I 0.9 0.9 0.9 0.9 0.9 0.9
t4
0.9
15 l6 I7 18 19 20 2l
0.8 0.8
li
t2
22 23
24 25 26 27 28
29 30 3l
32 33 34
Rute
0 .8 0 .8 0.8 0.8 0.8 0.6 0.6 0.6 0.6 0.6 0.6 0.6 0.4 0.4 0.4
0.4 0.4 0.4
35
0.4
36 37 38 39 40 4l 42
0.1 0.1 0.1 0.1 0.1 0.1 0.1
0.5
0.7 0.9
0.0r 0.05 0.1 0.3 0.5
0.7 0.9 0.01
l0 i9 22 l3 T7 14
t7 12 t6 24
0.05 0.1 0.3 0.5 0.7 0.9 0.01 0.05 0.1
0.3
l7
0.5 0.7 0.9 0.01
ll
0.0s 0 .1 0.3 0.5
0.7 0.9 0.01
0.0s 0.1
0.3 0.5
15 l0 9 0 l5
569.52 569.52
1272
s69.s2
r-2-r8-2r-27-28-32
2r19
630.93 r-2-| 8: t9 -20- r 9 -20-28-32
569.s2 569.52 569.52 569.52 569.52 569.52
569.s2 569.52
569.s2 569.s2 569.s2
1-2-18-2r-27 -28-32 I-2-t8-21-27-28-32 r-2-18-2r-27-28-32 l-2-18-21-2 t--28-32
1.-2-18-2r-27 -28-32 1-2-r8-2r-27-28-32 I-2-r8-2r-27-28-32
622.r2
t-2-r8-2t-20-28-32
t7 12
569.52 569.52 569.52 569-52 569.52
l-2-t8-2t-27-28-32 l-2-t8-21-27-28-32
t-2-18-21-27-28-32 1-2-r8-2r-27-28-32 t-2-t8-21-27-28-32
l9 l0 9 9
t0
569.s2
9 l3 l3 l0
577.48 569.52 577.08
t-2-18-2r-27-28-32 l-2-t8-19-20-28-32 t-2-18-2r-27-28-32 1-2-r8-19-20-28-32
s69.52 s69.52
l-2-t8-21-27-28-32 l-2-18-2r-27-28-32
569.52 569.52
r-2-r8-2r-27-28-32 r-2-r8-2r-27-28-32
0.9
l0
t264 2702 1657 11 3 3 1014
10s4 1681 l 387 1098
r826 1271 1828 l 198 1393
t-2-18-2r-27-28-32 t5t2 | -2-6-t-2-r8-2| -27-28-32 122r r-2-18-21-27-28-32 1 ll1 r-2-18-2t-27-28-32 l9 8 l 1-2-t8-2r-27-28-32 1005 r-2-18-2t-27-28-32 1002
840.88 569.52 569.52 569.52 569.52 569.52
0.7
1015
1-2-18-2t-27-28-32 1 8 0 1
l2
s69.52
1257
2440 r-2-t8-2r-2i-28-32 1440 t-2-t8-2t-21-28-32 1 8 2 0 r-2-t8-2r-21-28-32 1 51 5 I-2-18-21-27 -28-32 1856
l-2-t8-21-27-28-32
t2 t0
r6t2 r268
s69.52
13
ll ll
2435
t-2-18-2r-27-28-32 t-2-t8-2t-27-28-32 I-2-t8-2t-27-28-32
s69.s2
569.52 569.52
l3 t4
Akhir Generasi
l-2-t8-2t-27-28-32
1007 1071
lt02 1416 1352 t046 1308
t032 1030
ImplementasiAlgoritma Genetikauntuk PencarianRute Paling Optimum
A-39
Beberapa hal yang didapat dari hasil pengujian, meliputi perbandingan antara metodeyang diuji, adalah sebagai metode seleksi yang dipakai dan perbandingannilai parameter-parameter berikut: . Berdasarkan metode seleksi yang digunakan, dalam tiap pengujian maka terlihat bahwa metode seleksi yang terbaik didalam pengujian ini adalahmetoderoulette-wheel. . Berdasarkanperbandinganjumlah titik potong dalam proseskarvin silang maka terlihat bahwa satu titik potong lebih baik daripadadua titik potong. . Nilai mutation rate yang besar (0.3 - 1) memberikan hasil optimal yang lebih cepat daripada nilai yang kecil, sedangkanperbedaannilai crossover rate tidak terlalu banyak berpengaruh terhadapprosesperhitungan algoritma genetikapada penelitian ini. . Waktu proses yang dibutuhkan rata-rata untuk masing-masing metode seleksi berdasarkan pengujian di atas sangat tergantung terhadap jumlah kromosom yang dipakai dan juga banyaknya syarat yang dimasukkan. 5.
Kesimpulan
Dari hasil pengujian dapat ditarik beberapa kesimpulan menarik mengenai metode ini. Algoritma genetika cukup efektif dan mudah digunakan khususnya dalam hal mencari rute terpendek dan waktu tersingkat berdasarkan kondisi rute. Algoritma ini menunjukkan keunggulannyapada saat dilakukan perhitungan denganmemakai bobot jarak terhadapwakfu. Hal ini akan memakan waktu lebih lama untuk perhitungan matematika biasa. Sernakin kompleks bentuk rutenya, maka makin sulit dilakukan perhitungan denganmetode matematika biasa. Secara keseluruhan, algoritma genetika yang telah didisain dapat berjalan dengan baik dan dapat menyelesaikanpermasalahan.
6.
ttl
tzl i3l l4l t5l t6l
Daftar Pustaka Gen, Mitsuo,andCheng,Runwei. "Genetic Algorithms And EngineeringDesign". Edited by Hamid R.Parsaei.United StatesOf America: John Wiley and Sons,1997 Goldberg, David E. "Genetic Algorithms in Search, Optimization, and Machine Learning". Addison-WesleyPublishingCompany, I 989. 1996. Mitchell, Melanie, "An IntroductionTo GeneticAlgorithm", Massachusetts, Davis, Lawrence. "Handbook Of Genetic Algorithms". New York Van Nostrand Reinhold,1991 Man,K.F, et al. "Genetic Algorithms For Control And Signal Processing". London: Springer,1997. Thiang, Ronald Kurniawan, Hany Ferdinando, "Implementation of Genetic Algorithm on MCS51 Microcontroller for Finding the Shortest Path". Prosiding Seminar of Intelligent Technologyand Its Applications (SITIA 2001),ITS-Surabaya,Mei 2001
