BAB II KAJIAN TEORI
Secara umum, pada bab ini membahas mengenai kajian teori yang digunakan dalam penelitian yaitu graf, vehicle routing problem (VRP), capacitated vehicle routing problem (CVRP), metode penyelesaian CVRP, algoritma sweep, dan algoritma genetika. A. Graf 1.
Definisi Graf Graf G didefinisikan sebagai pasangan himpunan (V, E), ditulis dengan
notasi G = (V, E). Dalam hal ini, V merupakan himpunan tidak kosong dari simpul-simpul (vertices atau node) digambarkan dalam titik-titik, dan E adalah himpunan sisi-sisi (edges atau arcs) digambarkan dalam garis-garis yang menghubungkan sepasang simpul (Munir, 2009). Dapat dikatakan graf adalah kumpulan dari simpul-simpul yang dihubungkan oleh sisi-sisi. 2.
Jenis-jenis Graf Graf dapat dikelompokkan beberapa kategori (jenis) bergantung pada
sudut pandang pengelompokkannya. Pengelompokkan graf dapat dipandang berdasarkan ada tidaknya sisi ganda atau sisi gelang (loop), berdasarkan jumlah simpul atau berdasarkan orientasi arah pada sisi (Munir, 2009). Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf, maka secara umum graf dapat digolongkan menjadi dua jenis: 1.
Graf sederhana (simple graph)
8
Graf yang tidak mengandung gelang maupun sisi ganda dinamakan graf sederhana. Pada graf sederhana, sisi adalah pasangan tak-terurut (unordered pairs). Jadi menuliskan sisi (u,v) sama saja dengan (v,u). a. Graf nol Graf nol adalah graf tidak memiliki rusuk atau himpunan rusuknya merupakan himpunan kosong. Gambar 2.1 berkut ini menunjukkan graf nol dengan lima buah simpul.
Gambar 2.1 Contoh Graf Nol dengan 5 Simpul b. Graf lengkap Graf lengkap adalah graf sederhana yang setiap simpulnya mempunyai sisi ke semua simpul lainnya. Graf lengkap dengan n buah simpul dilambangkan dengan Kn. Setiap simpul pada Kn berderajat n-1. Contoh graf lengkap ditunjukkan oleh Gambar 2.2.
Gambar 2.2 Graf Lengkap Kn,
9
c. Graf teratur (Regular graphs) Graf teratur adalah graf yang setiap simpulnya mempunyai derajat yang sama, apabila derajat setiap simpul adalah r, maka graf tersebut disebut sebagai graf teratur derajat r. Contoh graf teratur berderjat dua ditunjukkan oleh Gambar 2.3.
Gambar 2.3 Graf Teratur Derajat 2 2.
Graf tak-sederhana (unsimple graph) Graf yang memuat sisi ganda atau gelang dinamakan graf tak sederhana (unsimple graph). Ada dua macam graf tak sederhana, yaitu graf ganda (multigraph) dan graf semu (pseudograph). Graf ganda adalah graf yang memuat sisi ganda. Sisi ganda yang menghubungkan sepasang simpul bisa lebih dari dua. Graf semu adalah graf yang memuat gelang (loop). Graf semu lebih umum daripada graf ganda, karena sisi pada graf semu dapat terhubung ke dirinya sendiri (Munir, 2009). Graf berdasarkan ada tidaknya sisi gelang atau sisi ganda dapat dilihat pada gambar 2.4
10
2 2
1
e4
4
e4
4
4
e8
e6
e5
e7 3
(a)
e2
1
e6
e5
e3
e1
e2
1
3
2
e3
e1
e7 3
(b)
(c)
Gambar 2.4 (a). Graf sederhana, (b). Graf ganda, (c). Graf semu Sisi pada graf dapat mempunyai orientasi arah. Berdasarkan orientasi arah pada sisi, maka secara umum graf dibedakan atas dua jenis: 1.
Graf tak-berarah (undirected graph) Graf yang sisinya tidak mempunyai orientasi arah disebut graf tak-berarah. Pada graf tak-berarah, urutan pasangan simpul yang dihubungkan oleh sisi tidak diperhatikan. jadi (u,v) = (v,u) adalah sisi yang sama.
2.
Graf berarah (directed graph atau digraph) Graf yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah. Sisi berarah dapat dinyatakan dengan sebutan busur (arc). Pada graf berarah, (u,v) dan (v,u) menyatakan dua buah busur yang berbeda, dengan kata lain (u,v) ≠ (v,u). Untuk busur (u,v), simpul u dinamakan simpul asal (initial vertex) dan simpul v dinamakan simpul terminal (terminal vertex) (Munir, 2009). 1
3
(a)
2
1
4
3
2
(b)
4
Gambar 2.5 (a). Graf tak berarah, (b). Graf berarah
11
3.
Graf Berbobot (Weighted Graph) Graf berbobot adalah graf yang setiap sisinya diberi sebuah harga
(bobot). Bobot pada tiap sisi dapat berbeda-beda bergantung pada masalah yang dimodelkan dengan graf. Bobot dapat menyatakan jarak antara dua buah kota, biaya perjalanan antara dua buah kota, waktu tempuh pesan (message) dari sebuah simpul komunikasi ke simpul komunikasi lain, ongkos produksi, dan sebagainya (Munir, 2009). Untuk lebih jelasnya, graf berbobot dapat digambarkan pada gambar 2.6 berikut :
5
a
b 3
11
14
c
10 9
d
6
e
Gambar 2.6 Graf berbobot 4.
Keterhubungan Graf
Definisi 2.1. Graf tak-berarah G disebut graf terhubung (connected graph) jika setiap pasang simpul u dan v di dalam himpunan V terdapat lintasan dari u ke v ( yang juga harus berarti ada lintasan dari u ke v). Jika tidak, maka G disebut graf tak-terhubung (disconnected graph). 1
1
2
2 5
3
4
3
4
(b)
(a)
Gambar 2.7 (a). Graf terhubung, (b). Graf tak terhubung
12
Definisi 2.2. simpul-simpul berdekatan dengan
dan
disebut berdekatan (adjacent) atau
jika ada suat busur e, sedemikian sehingga
Busur e dikatakan menggabungkan (join)
.
dan
Contoh: Simpul
pada graf berikut berdekatan (adjacent) dengan
berdekatan dengan karena
Busur
dikatakan menggabungkan (join)
. Untuk hal yang sama
Gambar 2.8 Simpul Definisi 2.3. simpul
dan
dan
, tetapi tidak dan
, oleh
.
berdekatan (adjacent) dengan
bersisian pada (incident on) busur e atau dikatakan
busur e bersisian dengan (incident to) simpul
dan
jika
Contoh: Pada gambar 2.8, busur
bersisian dengan simpul
dan
karena
Definisi 2.4. barisan simpul-simpul dan busur-busur pada graf G berselang-seling yaitu:
yang dimulai dari suatu simpul
dan berakhir pada suatu simpul sedemikian sehingga
untuk
(tiap busur bersisian dengan tiap dua simpul pada barisan tersebut), dikatakan sebagai suatu jalan (walk) pada G.
13
Jalan pada graf dapat dinotasikan dengan sebagai jalan berakhir di simpul
dan dapat dikatakan
yang bermakna barisan dimulai dari simpul awal
dan
.
Contoh: Diberikan Graf G3 seperti pada gambar dibawah.
Gambar 2.9 Graf Sederhana G3 Misal diketahui bahwa Berarti
merupakan suatu jalan pada graf G3.
dapat ditulis lebih sederhana
sebagai Diberikan Maka
juga merupakan suatu jalan, walaupun busur
dan
dilewati lebih
dari satu kali. Definisi 2.5. Panjang (length) dari suatu jalan
adalah banyaknya
busur yang muncul (dilalui) sepanjang barisan. Contoh: Diberikan graf seperti pada Gambar 2.9. Jalan
dan
.
14
Jalan
mempunyai panjang empat karena barisan melalui busur sebanyak empat
buah. Jalan
mempunyai panjang enam, karena melalui empat busur yang
berbeda namun dua busur berulang sehingga panjangnya menjadi enam. Definisi 2.6. Lintasan (path) adalah jalan dengan semua simpul dalam barisannya berbeda. Contoh: Diberikan graf seperti pada Gambar 2.9. Jalan
dan
Berdasarkan definisi lintasan, maka bukan suatu lintasan.
merupakan suatu lintasan sedangkan
bukan lintasan karena ada simpul yang dilewati lebih
dari satu kali, yaitu simpul Definisi 2.7. Suatu barisan simpul-simpul dan rusuk-rusuk (jalan) dikatakan tertutup (close) apabila
Jika
Maka dikatakan terbuka (open).
Contoh: Diberikan graf seperti pada Gambar 2.9. Jalan
dan
.
Dimisalkan bahwa tertutup, sedangkan
, maka dan
merupakan jalan
merupakan jalan terbuka karena simpul awalnya
tidak sama dengan simpul akhirnya. Definisi 2.8. Jalur/jejak (trail) adalah jalan dengan semua busur dalam barisannya berbeda. Contoh: Diberikan graf seperti pada Gambar 2.9.
15
Jalan
, , maka
, dan
merupakan suatu jalur sedangkan
bukan merupakan suatu jalur karena barisan yaitu busur
dan
melewati busur yang sama,
dan busur
Definisi 2.9. Siklus (cycle) adalah jalan tertutup (closed walk) dengan simpul tidak berulang, kecuali simpul awal sama dengan simpul akhir. Dengan kata lain, siklus adalah lintasan yang tertutup. Contoh: Diberikan graf seperti pada Gambar 2.9. dan
merupakan siklus pada graf tersebut.
Definisi 2.10. Sirkuit (circuit) adalah jalan tertutup (closed walk) dengan busur tidak berulang atau dengan kata lain sirkuit adalah jalur yang tertutup. Contoh: Diberikan graf seperti pada Gambar 2.9. dan 5.
merupakan sirkuit pada graf tersebut.
Representasi Graf Pemrosesan graf dengan program komputer memerlukan representasi
graf dalam memori. Terdapat beberapa representasi graf yang mungkin untuk dilakukan yaitu sebagai berikut: a.
Matriks ketetanggaan (adjacency matrix). Definisi 2.11. Misalkan G = (V, E) adalah graf dengan n simpul, n ≥ 1. Matriks ketetanggaan G adalah matriks yang berukuran n x n. Bila matriks tersebut dinamakan matriks A = [aij], maka nilai elemen matriks A [aij] akan
16
bernilai 1 bila simpul i dan simpul j bertetanggaan dan akan bernilai 0 bila simpul i dan simpul j tidak bertetangga. Contoh matriks ketetanggaan (adjacency matrix) ditunjukkan oleh Gambar 2.10.
Gambar 2.10 Graf terhubung dengan matriks ketetanggaannya b.
Matriks ikatan Definisi 2.12. Misalkan { ikatan jika
} Matriks
merupakan graf dengan n simpul dan (
) berdimensi n x n disebut matriks
sama dengan banyaknya sisi yang menghubungkan simpul
dan Contoh matriks ikatan ditunjukkan oleh Gambar 2.11.
Gambar 2.11 Matriks ikatan berukuran 4 x 4
17
c.
Matriks kehadiran Definisi 2.13. Misalkan sisi,
{
merupakan graf dengan n simpul dan m } , dan
{
}
Matriks
berdimensi n x m disebut matriks kehadiran jika { Contoh matriks kehadiran ditunjukkan oleh Gambar 2.12.
Gambar 2.12 Matriks kehadiran berukuran 4 x 6 B. Vehicle Routing Problem (VRP) Vehicle routing problem (VRP), atau dapat disebut juga dengan Vehicle Sceduling Problem, berhubungan dengan distribusi produk atau barang jadi antara depot dengan konsumen. VRP pertama kali dikenalkan oleh Dantzig dan Ramser pada tahun 1959. VRP ini memegang peranan penting pada manajemen distribusi dan telah menjadi salah satu permasalahan dalam optimalisasi kombinasi yang dipelajari secara luas. Model dan algoritmanya dapat digunakan secara efektif tidak hanya untuk pengiriman dan pengambilan barang, tetapi juga dapat diaplikasikan untuk masalah sistem transportasi sehari-hari, seperti untuk perencanaan rute bis sekolah, pengumpulan sampah, pembersihan jalan, rute pedagang keliling, dan lainnya.
18
Secara sederhana, VRP merupakan permasalahan yang meliputi konstruksi rute-rute dari sejumlah kendaraan yang dimulai dari suatu depot utama menuju ke lokasi sejumlah konsumen dengan jumlah permintaan tertentu. Tujuannya adalah untuk meminimumkan biaya total tanpa melebihi kapasitas kendaraan. VRP merupakan manajemen distribusi barang yang memperhatikan pelayanan, periode waktu tertentu, sekelompok konsumen dengan sejumlah kendaraan yang berlokasi pada satu atau lebih depot yang dijalankan oleh sekelompok pengendara, menggunakan road network yang sesuai. Solusi dari sebuah VRP yaitu menentukan sejumlah rute, yang masing-masing dilayani oleh suatu kendaraan yang berasal dan berakhir pada depot asalnya, sehingga kebutuhan pelanggan terpenuhi dengan tetap memenuhi kendala operasional yang ada, juga dengan meminimalkan baiaya transportasi global (Toth dan Vigo, 2002). Terdapat empat tujuan umum dari VRP (Toth dan Vigo, 2002) yaitu : 1.
Meminimalkan biaya transportasi global, terkait dengan jarak dan biaya tetap yang berhubungan dengan kendaraan.
2.
Meminimalkan jumlah kendaraan (atau pengemudi) yang dibutuhkan untuk melayani semua konsumen.
3.
Menyeimbangkan rute, untuk waktu perjalanan dan muatan kendaraan.
4.
Meminimalkan pinalti akibat service yang kurang memuaskan terhadap konsumen, seperti keterlambatan pengiriman dan lain sebagainya. Beberapa komponen beserta karakteristiknya yang terdapat dalam
masalah VRP (Toth dan Vigo, 2002) yaitu :
19
1.
Jaringan jalan Jaringan jalan biasanya direpresentasikan dalam sebuah graf. Jaringan jalan terdiri edge (rusuk) yang mempresentasikan bagian jalan yang digunakan, dan vertex (titik) yang mempresentasikan konsumen dan depot.
2.
Konsumen Konsumen atau pelanggan direpresentasikan dengan vertex (titik). Setiap konsumen memiliki jumlah permintaan yang berbeda-beda yang dapat mempengaruhi lamanya waktu bongkar muat (loading unloading) barang. Pada beberapa konsumen, biasanya time windows atau rentang waktu kapan konsumen tersebut dapat dilayani.
3.
Depot Depot direpresentasikan oleh vertex (titik). Depot merupakan tempat awal dan akhir dari suatu rute kendaraan. Depot memiliki sejumlah kendaraan dengan jenis dan kapasitas tertentu yang dapat digunakan dalam mendistribusikan barang atau jasa pada jam operasional depot yang telah ditentukan (time windows depot).
4.
Kendaraan Kendaraan yang digunakan dalam proses distribusi memiliki kapasitas yang membatasi permintaan konsumen, yaitu dimana jumlah permintaan konsumen tidak boleh melebihi kapasitas kendaraan tersebut. Selain itu, kendaraan juga memiliki biaya yang berhubungan dengan penggunaan kendaraan, baik yang meliputi biaya pengeluaran untuk bahan bakar maupun sewa kendaraan.
20
5.
Pengemudi Pengemudi memiliki kendala seperti jam kerja harian, tambahan waktu lembur apabila diperlukan, jumlah dan jam istirahat, serta durasi maksimum perjalanan. Terdapat beberapa variasi dalam permasalahan utama VRP (Toth dan
Vigo, 2002) yaitu : 1.
Capacitated Vehicle Routing Problem (CVRP) CVRP merupakan jenis VRP yang setiap kendaraannya memiliki kapasitas terbatas.
2.
Vehicle Routing Problem with Pick up and Delivery (VRPPD) VRPPD merupakan jenis VRP dengan pelayanan jemput dan pelayanan antar dalam setiap permintaan pelanggan.
3.
Distance Constrained Vehicle Routing Problem (DCVRP) DCVRP merupakan jenis VRP dengan kendala batasan panjang rute.
4.
Vehicle Routing Problem with Multiple Depot (MDVRP) MDVRP merupakan jenis VRP yang memiliki banyak depot dalam melakukan pelayanan terhadap pelanggan.
5.
Split Delivery Vehicle Routing Problem (SDVRP) SDVRP merupakan jenis VRP dimana pelayanan terhadap pelanggan dilakukan dengan menggunakan kendaraan yang berbeda-beda.
6.
Vehicle Routing Problem with Time Windows (VRPTW) VRPTW merupakan jenis VRP dengan kendala kapasitas kendaraan dan batasan waktu (time windows) pada setiap pelanggan dan depot.
21
C. Capacitated Vehicle Routing Problem (CVRP) Capacitated Vehicle Routing Problem (CVRP) merupakan salah satu variasi yang paling umum dari masalah VRP, dimana terdapat penambahan kendala berupa kapasitas kendaraan yang homogen (identik) untuk mengunjungi sejumlah agen sesuai dengan permintaannya masing-masing. Permasalahan CVRP, total jumlah permintaan agen dalam satu rute tidak melebihi kapasitas kendaraan yang melayani rute tersebut, setiap agen dikunjungi satu kali oleh satu kendaraan dan semua rute dimulai dan berakhir di depot. Permasalahan CVRP mempunyai tujuan meminimumkan total jarak tempuh rute perjalanan kendaraan yang digunakan dalam mendistribusikan barang dari tempat pengiriman (depot) ke masing-masing agen. Pemodelan untuk CVRP memiliki parameter-parameter sebagai berikut : n
: banyaknya jumlah agen,
q
: kapasitas setiap kendaraan,
di
: permintaan agen i dan
cij
: jarak tempuh perjalanan dari agen i ke agen j. Semua parameter dianggap nilai integer tidak negatif. Sejumlah kendaraan
homogen dengan dengan kapasitas terbatas q dan sebuah depot utama, dengan indeks 0, melakukan pengiriman ke agen, dengan indeks 1 sampai n permasalahannya adalah menentukan rute pasti setiap kendaraan dimulai dan diakhiri didepot. Setiap agen harus dipasangkan dengan tepat satu rute, karena setiap agen hanya bisa dilayani oleh satu kendaraan. Jumlah seluruh permintaan agen yang ada pada setiap rute harus berada dalam batas kapasitas kendaraan.
22
Tujuannya adalah untuk meminimalkan total jarak tempuh perjalanan. (Wijaya dkk, 2004). Model matematika dari CVRP didefinisikan sebagai suatu graf .
Dimana
{
} merupakan
himpunan
simpul
yang
merepresentasikan agen-agen yang akan dilayani dengan permintaan yang sudah diketahui dan depot berada di simpul 0. Jaringan jalan yang digunakan oleh kendaraan dinyatakan sebagai himpunan rusuk berarah E yaitu penghubung depot dengan agen dan juga penghubung antar agen,
{
|
} Semua
rute dimulai dari 0 dan berakhir di 0. Himpunan kendaraan K merupakan kumpulan kendaraan yang homogen dengan kapasitas q. Setiap agen i untuk setiap
memiliki permintaan di sehingga panjang rute dibatasi oleh kapasitas
kendaraan. Setiap rusuk
memiliki jarak tempuh cij dan jarak tempuh
diasumsikan simetris, contoh cij = cji, dan juga bahwa cii = cjj = 0. Satu-satunya variabel keputusan adalah
:
{
Model matematika untuk CVRP adalah sebagai berikut :
∑ ∑∑
(2.1)
dengan kendala
∑∑
(2.2)
23
∑
∑
(2.3)
∑
(2.4)
∑
∑
(2.5)
∑
(2.6)
{
}
(2.7)
Model diatas merupakan model pemrograman bilangan bulat biner yang bertujuan meminimumkan total jarak tempuh perjalanan. Kendala (2.2) memastikan bahwa setiap agen hanya dikunjungi tepat satu kali oleh suatu kendaraan, kendala (2.3) menyatakan permintaan semua agen dalam satu rute tidak melebihi kapasitas kendaraan, kendala (2.4) menyatakan setiap rute berawal dari depot, kendala (2.5) menyatakan bahwa setiap kendaraan yang mengunjungi satu titik pasti akan meninggalkan titik tersebut, kendala (2.6) menyatakan setiap rute berakhir di depot 0 dan kendala (2.7) menyatakan variabel keputusan merupakan variabel biner. Berdasarkan definisi CVRP, diperoleh suatu kesimpulan mengenai input dari permasalahan CVRP sebagai berikut : 1. Input permasalahan CVRP adalah daftar permintaan setiap agen, daftar jarak agen, dan kapasitas kendaraan.
24
2. Dalam terminologi graf kumpulan agen atau titik pada permasalahan CVRP adalah sebuah graf lengkap dengan bobot rusuk adalah jarak antar agen. D. Metode Penyelesaian CVRP Penyelesaian
masalah
VRP
akan
semakin
kompleks
dengan
bertambahnya kendala terhadap kasus yang harus diselesaikan. Kendala tersebut dapat berupa batasan waktu (time windows), permintaan (demand), jenis dan kapasitas kendaraan yang berbeda, batas maksimum jam kerja operator kendaraan, hambatan perjalanan, dan sebagainya. Secara umum, VRP dapat diselesaikan dengan menggunakan dua jenis pendekatan, yaitu pendekatan eksak dan pendekatan heuristik (Toth dan Vigo, 2002). Penyelesaian melalui pendekatan heuristik dalam VRP dapat dibagi menjadi dua, yaitu pendekatan heuristik klasik dan pendekatan heuristik modern (metaheuristik). 1.
Pendekatan Eksak Penyelesaian solusi CVRP melalui pendekatan eksak dilakukan dengan
menghitung setiap solusi yang mungkin sampai ditemukan solusi terbaik. Terdapat beberapa algoritma eksak utama penyelesaian CVRP, yaitu Branch and Bound, Branch and Cut, dan Set Covering Based. Penyelesaian solusi CVRP melalui pendekatan eksak secara umum akan menghabiskan waktu yang lama. Hal tersebut dikarenakan CVRP termasuk dalam permasalahan NP-hard (Non Polynomial-hard), kompleksitas penyelesaian permasalahan akan meningkat secara eksponensial dengan semakin rumitnya permasalahan. Hingga saat ini, belum ada algoritma eksak yang mampu menyelesaikan kasus-kasus yang terdiri lebih dari lima puluh konsumen secara konsisten (Toth dan Vigo, 2002). Oleh
25
karena itu, dilakukan berbagai penelitian terhadap algoritma heuristik untuk menyederhanakan penyelesaian CVRP. 2.
Pendekatan Heuristik Klasik Pendekatan heuristik klasik memberikan suatu cara untuk menyelesaikan
permasalahan optimasi yang lebih sulit dan dengan kualitas dan waktu penyelesaian yang lebih cepat daripada solusi eksak. Pendekatan heuristik tidak terlalu mengeksplorasi ruang pencarian solusi dan biasanya menghasilkan solusi dengan kualitas yang cukup baik dengan waktu perhitungan yang singkat. Beberapa contoh algoritma heuristik klasik adalah Saving, Sweep, Two Phase, dan lain-lain. Berdasarkan kualitas solusi yang diperoleh melalui pendekatan heuristik klasik berdasarkan konstruksi sederhana dan teknik perbaikan lokal tidak dapat menandingi implementasi metode heuristik modern. Namun, kesederhanaan dalam penggunaannya membuat algoritma heuristik klasik, seperti Sweep dan Saving Algorithm, tetap menjadi metode yang populer dan banyak digunakan sebagai dasar dalam perangkat lunak komersil. 3.
Pendekatan Heuristik Modern/Metaheuristik Pendekatan heuristik modern, lebih dikenal dengan metaheuristik, adalah
prosedur pencarian solusi umum untuk melakukan eksplorasi yang lebih dalam pada daerah yang menjanjikan dari ruang solusi yang ada (Dreo, Petrowsky dan Taillard, 2006). Perbedaannya dengan heuristik klasik adalah diperbolehkannya perusakan solusi atau penurunan fungsi tujuan. Pendekatan metaheuristik memecahkan masalah dengan melakukan perbaikan mulai dengan satu atau lebih
26
solusi awal. Solusi awal ini bisa dihasilkan melalui dua cara, yaitu diperbolehkan melalui pendekatan heuristik ataupun diperoleh secara acak. Kualitas solusi yang dihasilkan dari metode ini jauh lebih baik daripada heuristik klasik. Beberapa contoh metaheuristik adalah Genetic Algorithm, Simulated Annealing, Tabu Search, Ant Colony System, Differential Evolution, dan lain-lain. Metaheuristik secara konsisten mampu menghasilkan solusi yang berkualitas tinggi jika dibandingkan dengan heuristik klasik, meskipun lebih memakan waktu yang lebih lama. Prinsip dasar algoritma metaheuristik adalah pencarian lokal dan pencarian populasi. Dalam metode pencarian lokal, eksplorasi yang intensif dilakukan terhadap ruang solusi dengan berpindah dari satu solusi ke solusi tetangga lainnya yang potensial dalam satu lingkungan (neighbourhood). Algoritmanya biasa dimulai dengan solusi awal x1 dan berpindah pada tiap iterasi t dari solusi x1 ke solusi xt+1 dalam satu lingkungan N(xt) dari xt, hingga persyaratan tertentu dicapai. Jika fungsi tujuan f(x) menandakan biaya dari x, maka f(xt+1) tidak selalu lebih kecil dari f(xt). Oleh karenanya, dibutuhkan kehatihatian untuk menghindari perputaran (cycling) pada iterasi. E. Algoritma Sweep Algoritma
sweep
merupakan
metode
yang
sederhana
dalam
perhitungannya, bahkan untuk memecahkan masalah yang cukup besar. Keakuratan metode ini rata-rata kesalahan perhitungannya adalah sekitar 10 %. Keakuratan metode ini adalah pada cara pembuatan jalur rutenya. Algoritma sweep terdiri dari dua tahap, pertama yaitu tahap pengelompokkan (clustering)
27
yang mana pengelompokkan awal dilakukan dengan menggabungkan titik-titik dalam satu cluster berdasarkan kapasitas maksimal kendaraan. Permintaan total dalam satu cluster mungkin akan melebihi kapasitas kendaraan, karenanya beberapa titik dimasukkan ke cluster berikutnya. Tahap kedua yaitu dengan menentukan urutan rute dari setiap cluster menggunakan metode Nearest Neighbour (Gunadi, 2002). Diagram alir algoritma sweep ditunjukkan pada gambar berikut : Mulai
Menggambar titik-titik dalam bidang koordinat kartesius
Mengubah koordinat kartesius menjadi koordinat polar
Tidak Jumlah permintaan Kapasitas kendaraan
Ya Menentukan rute distribusi menggunakan metode Nearest Neighbour
Selesai
Gambar 2.13 Diagram alir algoritma sweep
28
F. Algoritma Genetika 1.
Pengertian Algoritma Genetika Algoritma genetika pertama kali diperkenalkan oleh John Holland dalam
bukunya yang berjudul “Adaption in natural and artificial systems”, dan oleh De Jong dalam bukunya “Adaption of the behavior of a class of genetic adaptive systems”, yang keduanya diterbitkan pada tahun 1975. Yang merupakan dasar dari algoritma genetika (Davis, 1991). Kemunculan Algoritma Genetika diinspirasikan dari teori-teori dalam ilmu biologi, sehingga banyak istilah dan konsep biologi yang digunakan dalam Algoritma Genetika. Sesuai dengan namanya, proses-proses yang terjadi dalam Algoritma Genetika sama dengan apa yang terjadi pada evolusi biologi yaitu seleksi, crossover, dan mutasi. Algoritma Genetika merupakan teknik pencarian yang didasarkan atas mekanisme seleksi dan genetik natural. Algoritma genetika berbeda dengan teknik pencarian konvensional, dimana pada algoritma genetika inisialisasi populasi awal dilakukan secara acak. Tiap individu dalam populasi yang merepresentasikan suatu solusi permasalahan disebut kromosom. Kromosom ini akan berevolusi melalui iterasi berkelanjutan yang disebut generasi. Pada setiap generasi, kromosom dievaluasi berdasarkan nilai fungsi fitness (Gen dan Cheng, 2000). Nilai fitness adalah nilai yang menunjukkan nilai ketangguhan kromosom dalam beradaptasi terhadap masalah. Untuk menghasilkan generasi berikutnya (offspring) didapatkan dari perkawinan silang (crossover) atau memodifikasi kromosom menggunakan operator mutasi (mutation) dengan harapan akan
29
menghasilkan kromosom baru dengan tingkat fitness yang lebih tinggi sebagai generasi baru atau keturunan (offspring) berikutnya. Suatu generasi baru dibentuk melalui proses seleksi beberapa induk (parents) dan anak (offspring), sesuai dengan nilai fitness, dan melalui eliminasi kromosom lainnya agar ukuran populasi tetap konstan. Kromosom yang sesuai memiliki kemungkinan tertinggi untuk dipilih. Setelah beberapa generasi maka algoritma genetika akan konvergen dengan kromosom terbaik, yang merupakan solusi optimal (Goldberg, 1989). 2.
Aplikasi Algoritma Genetika Algoritma genetika sudah banyak digunakan pada masalah praktis yang
berfokus pada pencarian parameter-parameter atau solusi yang optimal. Hal ini membuat banyak orang mengira bahwa algoritma genetika hanya dapat digunakan untuk menyelesaikan masalah optimasi saja. Namun, pada kenyataanya algoritma genetika juga memiliki kemampuan untuk menyelesaikan masalah-masalah selain optimasi. Algoritma genetika banyak diaplikasikan untuk berbagai macam permasalahan, yaitu (Suyanto, 2005: 3-4) : a.
Optimasi Beberapa penggunaan algoritma genetika untuk optimasi antara lain untuk optimasi numerik dan optimasi kombinatorial seperti Traveling Salesman Problem (TSP), Perancangan Integrated Circuit atau IC, Job Scheduling, dan optimasi video dan suara.
b.
Pemrograman Otomatis
30
Algoritma genetika untuk pemrograman otomatis antara lain untuk melakukan proses evolusi terhadap program komputer dalam merancang struktur komputasional, seperti cellular automata dan sorting networks c.
Machine Learning Algoritma genetika juga telah berhasil diaplikasikan untuk memprediksi struktur protein. Algoritma genetika juga berhasil diaplikasikan dalam perancangan neural networks (jaringan syaraf tiruan) untuk melakukan proses evolusi terhadap aturan-aturan pada learning classifier system atau symbolic production system dan dapat digunakan untuk mengontrol robot.
d.
Model Ekonomi Dalam bidang ekonomi, algoritma genetika digunakan untuk memodelkan proses-proses inovasi dan pembangunan bidding strategies.
e.
Model Sistem Imunisasi Penggunaan algoritma genetika dalam bidang ini untuk memodelkan berbagai aspek pada sistem imunisasi alamiah, termasuk somatic mutation selama kehidupan individu dan menemukan keluarga dengan gen ganda (multi gen families) sepanjang waktu evolusi.
f.
Model ekologis Algoritma genetika juga dapat digunakan untuk memodelkan fenomena ekologis seperti host-parasite co-evolution, simbiosis dan aliran sumber di dalam ekologi.
31
3.
Keuntungan Menggunakan Algoritma Genetika Keuntungan penggunaan algoritma genetika terlihat dari kemudahan
implementasi dan kemampuannya untuk menemukan solusi yang optimal dan bisa diterima secara cepat untuk masalah-masalah berdimensi tinggi. Algoritma genetika sangat berguna dan efisien untuk masalah dengan karakteristik sebagai berikut : a.
Ruang masalah sangat besar, kompleks, dan sulit dipahami,
b.
Kurang atau bahkan tidak ada pengetahuan yang memadai untuk merepresentasikan masalah ke dalam ruang pencarian yang lebih sempit,
c.
Tidak tersedianya analisis matematika yang memadai,
d.
Ketika metode-metode konvensional sudah tidak mampu menyelesaikan masalah yang dihadapi,
e.
Solusi yang diharapkan tidak harus paling optimal, tetapi cukup “bagus” atau bisa diterima,
f.
Terdapat batasan waktu, misalnya dalam real time system atau sistem waktu nyata.
4.
Karakteristik Algoritma Genetika
a.
Istilah dalam algoritma genetika Beberapa definisi penting yang perlu diperhatikan dalam membangun
penyelesaian masalah menggunakan algoritma genetika adalah sebagai berikut (Satriyanto, 2009) : 1.
Gen (Genotype) merupakan sebuah nilai yang menyatakan satuan dasar yang membentuk arti tertentu dalam satu kesatuan gen yang dinamakan kromosom.
32
Dalam algoritma genetika, gen ini dapat berupa bilangan biner, float, integer, karakter, dan kombinatorial. 2.
Allele merupakan nilai dari sebuah gen.
3.
Kromosom merupakan gabungan gen-gen yang membentuk nilai tertentu.
4.
Individu merupakan suatu nilai atau keadaan yang menyatakan salah satu solusi yang mungkin dari permasalahan yang diangkat.
5.
Populasi merupakan sekumpulan individu yang akan diproses bersama dalam satu siklus proses evolusi. Populasi terdiri dari sekumpulan kromosom.
6.
Induk adalah kromosom yang akan dikenai operasi genetika (crossover).
7.
Crossover adalah operasi genetika yang mewakili proses perkembangbiakan antar individu.
8.
Offspring adalah kromosom yang merupakan hasil dari operasi genetika (crossover) dikenal keturunan atau sebagai anak.
9.
Mutasi merupakan operasi genetika yang mewakili proses mutasi dalam perjalanan hidup individu. Mutasi berperan menghasilkan perubahan acak dalam populasi, yang berguna untuk menambah variasi dari kromosomkromosom dalam sebuah populasi.
10. Proses seleksi merupakan proses yang mewakili proses seleksi alam (natural selection) dari teori Darwin. Proses ini dilakukan untuk menentukan induk dari operasi genetika (crossover) yang akan dilakukan untuk menghasilkan keturunan (offspring). 11. Nilai fitness merupakan penilaian yang menentukan bagus tidaknya sebuah kromosom.
33
12. Fungsi evaluasi adalah fungsi yang digunakan untuk menentukan nilai dari nilai fitness. Fungsi evaluasi ini merupakan sekumpulan kriteria-kriteria tertentu dari permasalahan yang ingin diselesaikan. 13. Generasi merupakan satuan dari populasi setelah mengalami operasi-operasi genetika, berkembang biak, dan menghasilkan keturunan. Pada akhir dari setiap generasi, untuk menjaga agar jumlah kromosom dalam populasi tetap konstan, kromosom-kromosom yang mempunyai nilai fitness yang rendah dan memiliki peringkat dibawah nilai minimal akan dihapus dari populasi. b. Skema alur algoritma genetika Skema algoritma genetika pertama kali dikemukakan oleh David Goldberg (1989), dengan skema tersebut dapat dilihat pada gambar berikut :
Gambar 2.14 Skema algoritma genetika oleh David Goldberg (1989) Siklus
ini
kemudian
diperbaiki
oleh
beberapa
ilmuwan
yang
mengembangkan algoritma genetika, yaitu Zbignew Michalewichz dengan menambahkan operator elitism dan membalik proses seleksi setelah proses reproduksi.
34
Gambar 2.15 Skema Algoritma Genetika oleh Michalewichz (1996) 5.
Komponen Algoritma Genetika Ada 6 komponen utama dalam algoritma genetika, yaitu : teknik
penyandian (pengkodean), membangkitkan populasi awal, fungsi fitness, seleksi, crossover (pindah silang), mutasi, dan elitism. Masing-masing komponen akan dibahas sebagai berikut : a.
Teknik Pengkodean Teknik pengkodean adalah bagaimana mengkodekan gen dari kromosom,
dimana gen merupakan bagian dari kromosom. Satu gen biasanya akan mewakili satu variabel. Agar dapat diproses melalui algoritma genetika, maka alternatif solusi tersebut harus dikodekan terlebih dahulu ke dalam bentuk kromosom. Masing-masing kromosom berisi sejumlah gen yang mengkodekan informasi yang disimpan didalam kromosom (Kusumadewi, 2003: 280). Gen dapat direpresentasikan dalam bentuk: string bit, pohon, array bilangan real, daftar aturan, elemen permutasi, elemen program, atau representasi
35
lainnya yang dapat diimplementasikan untuk operator genetika. Dengan demikian kromosom dapat direpresentasikan dengan menggunakan: 1) String bit
: 10011, 01101, 11101, dst.
2) Bilangan real
: 65.65, -67.98, 562.88, dst.
3) Elemen permutasi
: E2, E10, E5, dst.
4) Daftar aturan
: R1, R2, R3, dst.
5) Elemen program
: pemrograman genetika
6) Struktur lainnya. b. Membangkitkan Populasi Awal (Spanning) Membangkitkan populasi awal adalah membangkitkan sejumlah individu secara acak atau melalui prosedur tertentu. Ukuran populasi tergantung pada masalah yang akan dipecahkan dan jenis operator genetika yang akan diimplementasikan. Setelah ukuran populasi ditentukan, kemudian dilakukan inisialisasi terhadap kromosom yang terdapat pada populasi tersebut. Inisialisasi kromosom dilakukan secara acak, namun demikian harus tetap memperhatikan domain solusi dan kendala permasalahan yang ada (Kusumadewi, 2003: 282). Terdapat berbagai teknik dalam pembangkitan populasi awal diantaranya adalah random generator, pendekatan tertentu, dan permutasi gen. Pada penelitian ini pembangkitan populasi awal dilakukan dengan menggunakan random generator. Inti dari cara ini adalah melibatkan pembangkitan bilangan random dalam interval (0,1) untuk setiap nilai gen sesuai dengan representasi kromosom yang digunakan.
36
c.
Evaluasi Nilai Fitness Evaluasi nilai fitness berfungsi untuk mengukur kualitas dari sebuah
solusi dan memungkinkan tiap solusi untuk dibandingkan (Michalewicz, 1996: 72). Suatu individu dievaluasi berdasarkan suatu fungsi tertentu sebagai ukuran performansinya. Di dalam evolusi alam, individu yang bernilai fitness tinggi yang akan bertahan hidup. Sedangkan individu yang bernilai fitness rendah akan mati. Pada masalah optimasi jika solusi yang dicari adalah memaksimalkan sebuah fungsi
(dikenal sebagai masalah maksimasi), maka nilai fitness yang digunakan
adalah nilai dari fungsi
tersebut, yakni
(dimana
Tetapi jika masalahnya adalah meminimalkan fungsi fungsi
adalah nilai fitness).
(masalah minimasi), maka
tidak bisa digunakan secara langsung. Hal ini disebabkan adanya aturan
bahwa individu yang memiliki nilai fitness tinggi lebih mampu bertahan hidup pada generasi berikutnya. Oleh karena itu nilai fitness yang bisa digunakan adalah (2.8)
Dengan nilai h merupakan nilai dari individu, yang artinya semakin kecil nilai h, maka semakin besar nilai fitnessnya. Tetapi hal ini akan menjadi masalah jika h bernilai 0, yang mengakibatkan
bisa bernilai tak hingga jika
. Untuk
mengatasinya, h perlu ditambah sebuah bilangan sangat kecil sehingga nilai fitnessnya menjadi
(2.9)
37
dengan a adalah bilangan yang dianggap sangat kecil (konstanta) dan bervariasi sesuai dengan masalah yang akan diselesaikan (Suyanto, 2005:10). d. Seleksi (Selection) Seleksi merupakan pemilihan dua buah kromosom untuk dijadikan sebagai induk yang dilakukan secara proposional sesuai dengan nilai fitnessnya (Michalewicz, 1996: 75). Masing-masing individu yang diseleksi akan diberikan probabilitas reproduksi tergantung dari nilai objektif dirinya sendiri terhadap nilai objektif dari semua individu dalam seleksi tersebut. Nilai fitness inilah yang nantinya akan digunakan pada tahap seleksi berikutnya. Terdapat beberapa metode seleksi menurut Kusumadewi (2003: 282), yaitu seleksi ranking (rank-based fitness assignment), seleksi roulette wheel (roulette wheel selection), stochastic universal sampling, seleksi lokal (local selection), seleksi dengan pemotongan (truncation selection), dan seleksi dengan turnamen (tournament selection). Dalam penelitian ini menggunakan metode seleksi roulette wheel (roulette wheel selection). Pada roulette wheel selection, setiap kromosom dalam suatu populasi memiliki tempat yang sesuai dengan proporsinya terhadap total nilai fitness. Kromosom-kromosom dipetakan kedalam suatu segmen secara berurutan, hingga tiap-tiap segmen kromosom memiliki ukuran yang sesuai dengan nilai fitnessnya. Langkah pertama dari seleksi adalah menghitung nilai fitness masing-masing kromosom. Setelah itu dihitung proporsi masing-masing kromosom berdasarkan perbandingan probabilitas antara nilai fitness setiap kromosom dengan total nilai fitness. Langkah selanjutnya adalah membangkitkan bilangan real random antara
38
0 dan 1 untuk menentukan kromosom yang bertahan hidup dan menjadi induk (Nugroho, 2010:25). Ilustrasi roulette wheel selection dapat dilihat pada gambar 2.15.
Gambar 2.16 Roulette wheel selection (Obitko, 1998) Cara kerja roulette wheel selection adalah sebagai berikut : 1.
Dihitung nilai fitness dari masing-masing individu (
dimana i adalah
individu ke-1 s/d ke-n). 2.
Dihitung total fitness semua individu.
3.
Dihitung probabilitas masing-masing individu.
4.
Dari probabilitas tersebut, dihitung jatah masing-masing individu pada angka 1 sampai 100
5.
Dibangkitkan bilangan random antara 1 sampai 100.
6.
Dari bilangan random yang dihasilkan, ditentukan individu mana yang terpilih dalam proses seleksi.
Urutan langkah proses seleksi menggunakan metode roda roulette, dapat digambarkan sebagai berikut : Misalkan diberikan sebuah contoh populasi beserta nilai fitnessnya yang ditunjukkan pada tabel 2.1.
39
Tabel 2.1. Contoh Populasi Beserta Fitnessnya Kromosom
Fitness
Kromosom 1
0,1111
Kromosom 2
0,2000
Kromosom 3
0,0588
Kromosom 4
0,2000
Kromosom 5
0,0400
Total Fitness
0,6099
Langkah selanjutnya adalah menentukan nilai segmen untuk masing-masing kromosom yang ditunjukkan pada tabel 2.2. Tabel 2.2 Nilai Probabilitas dan Segmen untuk masing-masing Kromosom Kromosom
Nilai Fitness
Probabilitas
Segmen
Kromosom 1
0,1111
18%
1-17
Kromosom 2
0,2000
33%
18-50
Kromosom 3
0,0588
10%
51-60
Kromosom 4
0,2000
33%
61-93
Kromosom 5
0,0400
6%
94-100
Berikut ditunjukkan hasil segmen dalam sebuah roda roulette yang ditunjukkan pada gambar 2.17.
40
Kromosom 1 18%
Kromosom 5 6%
Kromosom 2 33%
Kromosom 3 10%
Kromosom 4 33%
Gambar 2.17 Segmen untuk masing-masing Kromosom Langkah selanjutnya adalah memutar roda roulette sebanyak kromosom dalam populasi tersebut sebanyak 5 kali, setiap kali putaran akan menghasilkan suatu bilangan random dengan rentang antara 1-100 yang menunjukkan daerah atau segmen dari kromosom. Berikut ini adalah hasil kromosom yang terpilih setelah 5 kali putaran yang ditunjukkan pada tabel 2.4. Tabel 2.3. Hasil kromosom yang terpilih setelah 5 kali putaran Putaran ke -
Daerah Terpilih
Kromosom terpilih
1
40
Kromosom 2
2
76
Kromosom 4
3
84
Kromosom 4
4
15
Kromosom 1
5
35
Kromosom 2
41
e.
Pindah Silang (crossover) Pindah Silang (crossover) adalah operator dari algoritma genetika yang
melibatkan dua induk untuk membentuk kromosom baru. Pindah silang menghasilkan keturunan baru dalam ruang pencarian yang siap diuji. Operasi ini tidak selalu dilakukan pada setiap individu yang ada. Individu dipilih secara acak untuk dilakukan crossover dengan Pc (Probabilitas Crossover) antara 0,6 sampai dengan 0,95. Jika pindah silang tidak dilakukan, maka nilai dari induk akan diturunkan kepada keturunan. Prinsip dari pindah silang ini adalah melakukan operasi pertukaran pada gen yang bersesuaian dari induk untuk menghasilkan individu baru. Proses crossover dilakukan pada setiap individu dengan probabilitas crossover yang ditentukan. Secara skematis proses crossover seperti pada gambar 2.18.
Gambar 2.18 Sistematika proses crossover
42
Dari gambar 2.18, jika bilangan p yang dibangkitkan secara acak kurang dari probabilitas crossover (probCO), maka kedua induk dilakukan operasi pindah silang (crossover). Tetapi jika bilangan p yang dibangkitkan lebih dari atau sama dengan probCO, maka tidak dilakukan operasi pindah silang. Salah satu teknik crossover yang dapat digunakan adalah order crossover (OX) yang diperkenalkan oleh Davis (W.S.E. Tanjung, 2010). Teknik ini diawali dengan membangkitkan dua bilangan acak. Kemudian gen yang berada diantara kedua bilangan acak tersebut (substring) disalin ke ke keturunan (offspring) dengan posisi yang sama pada masing-masing kromosom orang tua. Langkah berikutnya untuk mendapatkan offspring pertama adalah adalah dengan mengurutkan gen yang berada dalam kromosom orang tua kedua dengan urutan gen yang pertama adalah dari gen yang berada pada posisi setelah bilangan acak kedua yang telah dibangkitkan sebelumnya lalu diikuti oleh gen-gen yang berada pada posisi sebelum bilangan acak pertama dan diakhiri dengan gen-gen yang berada pada posisi diantara kedua bilangan acak. Kemudian gen yang telah diurutkan tadi dibandingkan dengan offspring pertama. Apabila gen yang terurut tersebut mengandung gen yang berada pada offspring pertama, maka abaikan gen tersebut dari urutan. Kemudian masukkan urutan yang baru saja didapat ke offspring pertama dengan cara memasukkan urutan gen pada posisi setelah bilangan acak kedua terlebih dahulu pada offspring pertama dan sisanya dimasukkan pada posisi sebelum bilangan acak pertama. Untuk menghasilkan offspring kedua dilakukan cara yang sama untuk kromosom orang tua pertama. Contoh 2.4 order crossover
43
Dari 2 induk diketahui : P1 = (1 2 3 | 4 5 6 7 | 8 9) P2 = (4 5 2 | 1 8 7 6 | 9 3) Dibangkitkan 2 bilangan acak sebelum gen induk-1 dan setelah gen induk-1. Hal yang sama juga dilakukan untuk induk-2. Didapatkan keturunan dengan gen yang sama: O1 = (x x x | 4 5 6 7 | x x) O2 = (x x x | 1 8 7 6 | x x) Langkah berikutnya untuk mendapatkan keturunan pertama adalah mengurutkan gen yang berada pada induk kedua dengan urutan gen yang berada pada posisi setelah bilangan acak kedua diikuti dengan gen yang berada pada posisi sebelum bilangan acak pertama dan diakhiri dengan gen yang berada pada posisi diantara kedua bilangan acak. 9-3-4-5-2-1-8-7-6 Kemudian gen yang telah diurutkan tersebut dibandingkan dengan keturunan pertama. Apabila gen tersebut ada pada keturunan kedua maka abaikan gen tersebut dari urutan itu. Kemudian masukkan urutan yang baru saja didapat pada keturunan dengan cara memasukkan urutan gen pada posisi setelah bilangan acak kedua terlebih dahulu dan sisanya dimasukkan pada posisi sebelum bilangan acak pertama. Begitu juga untuk menghasilkan keturunan kedua. Keturunan 1 diperoleh :
44
O1 = (x x x | 4 5 6 7 | x x) O1 = (2 1 8 | 4 5 6 7 | 9 3) Dengan jalan yang sama buat O2 sehingga : O2 = (x x x | 1 8 7 6 | x x) O2 = (3 4 5 | 1 8 7 6 | 9 2) Keterangan : P1 = Induk 1 P2 = Induk 2 O1 = Keturunan 1 (anak ke-1) O2 = Keturunan 2 (anak ke-2) f.
Mutasi Mutasi merupakan proses untuk mengubah nilai dari satu atau beberapa
gen dalam suatu kromosom. Operasi mutasi yang dilakukan pada kromosom dengan tujuan untuk memperoleh kromosom-kromosom baru sebagai kandidat solusi pada generasi mendatang dengan fitness yang lebih baik, dan lamakelamaan menuju solusi optimum yang diinginkan. Penekanan selektif memegang peranan yang penting. Jika dalam proses pemilihan kromosom-kromosom cenderung terus pada kromosom yang memiliki fitness yang tinggi saja, konvergensi prematur akan sangat mudah terjadi (Murniarti, 2009). Secara skematis proses mutasi dapat digambarkan sebagai berikut:
45
Gambar 2.19 Sistematika Proses Mutasi Dari gambar 2.19, jika p merupakan bilangan random yang dibangkitkan kurang dari probabilitas mutasi (probMut) maka individu hasil crossover dilakukan proses mutasi sedangkan jika bilangan p yang dibangkitkan lebih dari atau sama dengan probMut, maka individu hasil crossover tidak dilakukan proses mutasi. Teknik mutasi yang digunakan dalam penelitian ini adalah teknik swapping mutation. Teknik ini diawali dengan memilih dua bilangan acak kemudian gen yang berada pada posisi bilangan acak pertama ditukar dengan gen yang berada pada bilangan acak kedua dalam probabilitas tertentu (Suyanto, 2005: 67). Contoh 2.5 swapping mutation Individu = (1 2 3 4 5 6 8 9 7) Memindahkan 8 ke 2, sehingga didapatkan individu baru: Individu = (1 8 3 4 5 6 2 9 7)
46
g.
Elitism Elitism merupakan proses untuk menjaga agar individu bernilai fitness
tertinggi tersebut tidak hilang selama evolusi. Proses seleksi dilakukan secara random sehingga tidak ada jaminan bahwa suatu individu yang bernilai fitness tertinggi akan selalu dipilih. Walaupun individu bernilai fitness tertinggi terpilih, mungkin saja individu tersebut akan rusak (nilai fitness menurun) karena proses pindah silang. Oleh karena itu, untuk menjaga agar individu bernilai fitness tertinggi tersebut tidak hilang selama evolusi, maka perlu dibuat satu atau beberapa copynya (Suyanto, 2005: 14). h. Pembentukkan Populasi Baru Proses membangkitkan populasi baru bertujuan untuk membentuk populasi baru yang berbeda dengan populasi awal. Pembentukkan populasi baru ini didasarkan pada keturunan-keturunan baru hasil mutasi ditambah dengan individu terbaik setelah dipertahankan dengan proses elitism. Setelah populasi baru terbentuk, kemudian mengulangi langkah-langkah evaluasi nilai fitness, proses seleksi, proses pindah silang, proses mutasi pada populasi baru untuk membentuk populasi baru selanjutnya. 6.
Parameter Algoritma Genetika Dalam proses algoritma genetika terdapat parameter-parameter yang
akan dibutuhkan dalam pemrosesan algoritma genetika. Pemilihan parameter genetika menentukan kinerja algoritma genetika dalam memecahkan masalah. Ada tiga parameter dasar dari algoritma genetika, yaitu ukuran populasi, jumlah generasi, probabilitas crossover (Pc), dan probabilitas mutasi (Pm).
47
1) Ukuran populasi Ukuran populasi adalah jumlah kromosom yang ada pada populasi. Semakin besar jumlah populasi yang diinputkan dalam parameter jumlah populasi, semakin besar variasi kromosom yang dihasilkan. Hal tersebut berpengaruh pada besarnya kesempatan untuk mendapatkan solusi terbaik. Memilih jumlah populasi yang tepat akan meningkatkan kinerja dari algoritma genetika. Apabila jumlah populasi terlalu kecil, maka algoritma genetika hanya akan mempunyai alternatif solusi yang sedikit. Namun, jika jumlah populasi terlalu besar proses algoritma genetika cenderung menjadi lambat dalam menemukan solusi. Ukuran populasi yang sering digunakan oleh peneliti yang sudah ada adalah 20 sampai 30, tetapi terkadang ukuran 50 sampai 100 juga dilaporkan baik. Beberapa penelitian juga menunjukan bahwa ukuran populasi yang baik tergantung dari pengkodean, yaitu ukuran dari barisan yang dikodekan. 2) Jumlah Generasi Jumlah generasi adalah jumlah proses yang dijalani untuk suatu rangkaian proses algoritma genetika. Suatu proses rangkaian algoritma genetika dimulai dari proses seleksi, crossover, mutasi sampai pembentukan populasi baru. Proses algoritma genetika akan dihentikan apabila jumlah generasi sudah terpenuhi. Solusi yang diambil adalah kromosom dengan nilai fitness terbaik dari generasi terakhir. 3) Probabilitas Crossover (Pc) Probabilitas crossover menyatakan seberapa sering proses crossover akan terjadi antara dua kromosom orang tua. Jika tidak terjadi crossover, satu orang tua
48
dipilih secara random dengan probabilitas yang sama dan diduplikasi menjadi anak. Jika terjadi crossover, keturunan dibuat dari bagian-bagian kromosom orang tua. Jika probabilitas crossover 100% maka keseluruhan keturunan baru dibuat dengan crossover. Namun sebaliknya jika probabilitas crossover 0% maka seluruh generasi baru dibuat dari salinan kromosom-kromosom populasi lama yang belum tentu menghasilkan populasi yang sama dengan populasi sebelumnya, karena adanya penekanan selektif. Hasil penelitian yang sudah ada dan pernah dilakukan oleh praktisi algoritma genetika menunjukan bahwa sebaiknya angka probabilitas crossover cukup tinggi yaitu sekitar 80% sampai dengan 95% untuk memberikan hasil yang baik. Untuk beberapa permasalahan juga sebaiknya probabilitas crossover sekitar 60% bisa memberikan hasil yang baik. 4) Probablitas Mutasi (Pm) Probabliltas
mutasi
menyatakan
seberapa
sering
bagian-bagian
kromosom akan dimutasikan. Jika tidak ada mutasi, keturunan diambil atau disalin langsung setelah crossover tanpa perubahan. Jika mutasi dilakukan, maka bagian-bagian tertentu kromosom diubah. Jika probabilitas mutasinya 100%, keseluruhan kromosom diubah. Jika probabilitas mutasinya 0%, maka tidak ada yang diubah. Probablitas mutasi dalam ruang algoritma genetika seharusnya diberi nilai yang kecil. Umumnya, probabilitas mutasi diset untuk mendapatkan rata-rata satu mutasi per kromosom, yaitu angka/allele = 1/(panjang kromosom). Dari hasil penelitian yang sudah pernah dilakukan, menunjukkan bahwa angka probabilitas terbaik adalah 0,5% sampai 1%. Hal ini karena tujuan mutasi ini sendiri adalah
49
menjaga perbedaan kromosom dalam populasi, untuk menghindari terjadinya konvergen prematur. Rekomendasi parameter algoritma genetika menurut Obitko, (1998) adalah sebagai berikut: Ukuran Populasi : 20-30 Probabilitas Crossover : 80%-95% Probabilitas Mutasi : 0,5%-1% Ada beberapa rekomendasi lain yang bisa digunakan, antara lain : (Kusumadewi, 2003). a.
Untuk permasalahan yang memiliki kawasan solusi cukup besar, De Jong merekomendasikan untuk nilai parameter kontrol: (popsize;Pc;Pm) = (50;0.6;0.001)
b.
Bila rata-rata fitness setiap generasi digunakan sebagai indikator, maka Grefenstette merekomendasikan: (popsize;Pc;Pm) = (30;0.95;0.01)
c.
Bila fitness dari individu terbaik dipantau pada setiap generasi, maka usulannya adalah: (popsize;Pc;Pm) = (80;0.45;0.01)
d.
Ukuran populasi sebaiknya tidak lebih kecil dari 30, untuk sembarang jenis permasalahan.
G. Penelitian yang Relevan Beberapa penelitian tentang CVRP dan algoritma genetika telah banyak dilakukan antara lain “Algoritma Genetika pada Penyelesaian Capacitated Vehicle
50
Routing Problem (Optimasi Rute Pendistribusian Aqua Galon PT. Tirta Investama” oleh Adam Arif Dirgantara, penelitian ini menggunakan algoritma genetika dalam menyelesaikan CVRP dengan menggunakan data dari peneliti sebelumnya yang menggunakan algoritma branch & bound serta clarke & wright savings. Algoritma genetika menghasilkan solusi yang lebih baik daripada metode clarke & wright savings tetapi solusi algoritma genetika tidak sebaik metode branch & bound. Selanjutnya penelitian oleh Kustanto yang berjudul “Optimasi Rute Distribusi Tabung Gas Elpiji menggunankan Algoritma Genetika (Studi Kasus PT. Restu Ajimanunggal Surakarta” penelitian ini membandingkan solusi yang dihasilkan dari algoritma Djikstra, Algoritma Greedy, serta Algoritma Genetika dengan bantuan program Arc View GIS dengan memperhatikan hambatan jalan yang dilewati. Hasil yang diperoleh bahwa rute optimal dari algoritma Djikstra dan Greedy akan lebih jauh optimal jika dibandingkan dengan rute optimal yang dihasilkan algoritma genetika. Selain penelitian yang menggunakan algoritma genetika sebagai metode penyelesaiannya terdapat juga penelitian tentang CVRP dengan metode heuristik yaitu Algoritma Sweep sebagai metode penyelesaiannya oleh Wahyu Kartika Cahyaningsih yang berjudul “Penyelesaian Capacitated Vehicle Routing Problem (CVRP) menggunakan algoritma sweep untuk optimasi rute distribusi surat kabar Kedaulatan Rakyat”. Hasil dari penelitian ini adalah bahwa algoritma sweep menghasilkan total jarak tempuh kendaraan dan waktu tempuh yang lebih baik daripada total jarak tempuh kendaraan dan waktu tempuh perusahaan saat ini yaitu
51
dengan jarak 142,9 km dan waktu tempuh 210 menit sedangkan milik perusahaan yaitu dengan jarak 174,9 km dan waktu tempuh 233 menit. Menghasilkan penghematan jarak tempuh sebesar 18,29 %. Terdapat persamaan dan perbedaan penelitian ini dengan penelitian sebelumnya. Persamaannya yaitu dalam penelitian ini menggunakan algoritma genetika sebagai metode penyelesaiannya seperti penelitian Adam Arif Dirgantara dan Kustanto. Perbedaannya yaitu dalam metode seleksi yang digunakan, dalam penelitian Adam Arif Dirgantara menggunakan metode seleksi ranking sedangkan pada penelitian ini menggunakan Roulette Wheel Selection dan perbedaan dalam menentukan nilai paramater yang digunakan dalam algoritma genetika seperti Ukuran Populasi, Jumlah Generasi, Probabilitas Mutasi dan Probabilitas Crossover. Data yang digunakan adalah data sekunder dari skripsi Wahyu Kartika Cahyaningsih yang berjudul “Penyelesaian Capacitated Vehicle Routing Problem (CVRP) Menggunakan Algoritma Sweep untuk Optimasi Rute Distribusi Surat Kabar Kedaulatan Rakyat” tahun 2015. Karena data yang digunakan sama, maka hasil dari penelitian ini dapat dibandingkan dengan hasil penelitian dari Wahyu Kartika Cahyaningsih.
52
