BAB 2 LANDASAN TEORI
2.1 Artificial Intelligence 2.1.1 Definisi dan Penjelasan Singkat AI (Artificial Intelligence) didefinisikan sebagai kecerdasan yang ditunjukkan oleh suatu entitas buatan. Sistem seperti ini umumnya dianggap komputer. Kecerdasan diciptakan dan dimasukkan ke dalam suatu mesin (komputer) agar dapat melakukan pekerjaan seperti yang dapat dilakukan manusia. Beberapa macam bidang yang menggunakan kecerdasan buatan antara lain sistem pakar, permainan komputer (games), logika fuzzy, jaringan syaraf tiruan dan robotika. AI membentuk cabang yang sangat penting pada ilmu komputer, berhubungan dengan perilaku, pembelajaran dan adaptasi yang cerdas dalam sebuah mesin. Penelitian dalam AI menyangkut pembuatan mesin untuk mengotomatisasikan tugas-tugas yang membutuhkan perilaku cerdas. Termasuk contohnya adalah pengendalian, perencanaan dan penjadwalan, kemampuan untuk menjawab diagnosa dan pertanyaan pelanggan, serta pengenalan tulisan tangan, suara dan wajah. Sistem AI sekarang ini sering digunakan dalam bidang ekonomi, obat-obatan, teknik dan militer, seperti yang telah dibangun dalam beberapa aplikasi perangkat lunak komputer rumah dan video game.
6
7
2.2 Algoritma Genetika 2.2.1 Definisi dan pengertian dasar Algoritma Kata algoritma berasal dari nama seorang ahli matematika dari Uzbekistan Al Khawārizmi ,sebagaimana tercantum pada terjemahan karyanya dalam bahasa latin dari abad ke-12 "Algorithmi de numero Indorum". Pada awalnya kata algoritma adalah istilah yang menunjuk kepada aturan-aturan aritmetis untuk menyelesaikan persoalan dengan menggunakan bilangan numerik Arab. Pada abad ke-18, istilah ini berkembang menjadi algoritma, yang mencakup semua prosedur atau urutan langkah yang jelas dan diperlukan untuk menyelesaikan suatu permasalahan.
2.2.2 Teori Genetika Teori tentang genetika sudah berkembang sejak lama. Teori yang menyatakan bahwa makhluk hidup menurunkan sifat dari induknya telah dikembangkan sejak zaman pra-sejarah. Dimana teori tersebut digunakan dalam proses penyatuan jenis tumbuhan maupun hewan untuk didapatkan sifat yang sesuai dengan keinginan. Walaupun begitu, ilmu genetika modern yang menelusuri proses penurunan sifat itu dimulai sejak pertengahan abad ke-19 yang dilakukan oleh Gregor Mendel. Walaupun dia tidak tahu basis utama dari kesamaan sifat yang diturunkan itu, Mendel mengobservasi bahwa makhluk hidup menurunkan sifat melalui sebuah unit penurunan yang bukan lain adalah gen. Sejak ditemukan penurunan sifat melalui gen inilah proses perkembangan teori
8
genetika ini berkembang dengan pesat. Mendel menyatakan gen terbagi dalam berbagai bagian dalam sel makhluk hidup yang adalah DNA, sebuah molekul yang dibangun dari himpunan 4 nucleotide yang berbeda. 4 nucleotide ini terhimpun secara selang seling dimana akan terbentuk himpunan DNA yang berbeda – beda. Himpunan yang berbeda inilah yang akhirnya akan menghasilkan sifat yang berbeda - beda pula. Himpunan nucleotide tersebut akan di terjemahkan oleh sel membentuk asam amino yang nantinya akan menghasilkan protein, hubungan antara himpunan nucleotide tersebut dengan asam amino itulah yang disebut kode genetik. Untuk itu sampai saat ini banyak peneliti yang terus bereksperimen dengan mengganti – ganti himpunan susunan dari DNA agar dapat menghasilkan bentuk sifat yang diinginkan dari makhluk hidup.
2.2.3 Sejarah Algoritma Genetika Teori Darwin yang sempat membuat orang orang berfikir bahwa manusia berasal dari kera, bahkan lebih rendah telah membuat membutakan kita sekitar abad 19 hingga beberapa tahun belakangan ini. Pada abad ke 19 banyak ilmuwan yang mencoba untuk membuktikan dan mensimulasikannya. Neo darwinisme yang menyebutkan bahwa sejarah kehidupan mahkluk hidup adalah melalui suatu mekanisme proses statistika yang terjadi antara populasi dan spesies, yang dikenal dengan proses manipulasi genetika. Proses ini masing-masing adalah reproduksi, mutasi, kompetisi dan pemilihan.
9
Cikal bakal penggunaan GA (Algoritma Genetika) untuk pencarian dalam sistem buatan diprakarsai oleh beberapa ahli biologi yang menggunakan komputer digital untuk mengerjakan simulasi dari sistem genetika. Diantara para ahli tersebut adalah: 1.
Baricelli, N.A pada tahun 1957 melakukan penelitian tentang proses evolusi
simbiogenetik yang direalisasikan dengan sistem artificial. 2.
Baricelli, N.A pada tahun 1962 mengajukan teori evolusi dan analisis
numeriknya 3.
Fraser, A.S pada tahun 1960 menyimulasikan sistem genetika dengan
komputer, yang meliputi aspek-aspek S-linkage,dominasi dan epistasis. Meskipun penelitian–penelitian tersebut bertujuan untuk meneliti gejala alam namun yang mereka kerjakan secar kebetulan memiliki pemikiran paralel yang memunculkan ide tentang Algoritma Genetika. Fraser mensimulasikan evolusi dari 15 bit Biner sebagai string generasi dan menghitung presentase dari individu-individu yang terpilih oleh fenotip dengan generasigenerasi yang berurutan. Pada saat itu Fraser tidak menyebutkan dalam laporannya bahwa algoritma pencarian dalam gejala alam akan berguna dalam sistem buatan, namun ternyata hasil dari penemuannya ternyata menyerupai optimasi fungsi. Hal itulah yang memberikan inspirasi bagi John Holand dan murid-muridnya untuk mengaplikasikan proses genetika ini pada sistem buatan. Holand menancapkan pondasi dalam karya tulisnya pada teori sistem adaptif yaitu:
10
1.
Concern efficient adaptive systems (1962)
2.
Information prosessing and prosesing systems (1962)
3.
Outline for a logical theory of adaptive systems (1962)
Tahun 1962-1965 Holand mengajar tentang theory of adaptive system dan sering memberikan seminar-seminar tentang ini. Dalam masa itu penyempurnaan GA makin jelas. Selanjutnya dibuatlah rumus standart untuk GA ini.
2.2.4 Operasi Dalam Algoritma Genetika Dalam Algoritma Genetika ada 3 operasi penting yang digunakan. Operasi itu akan terus diulang sampai batas waktu yang ditentukan atau sampai menemukan nilai fitness yang sama dalam suatu populasi. Operasi penting itu adalah : 1. Selection (Seleksi) Seleksi adalah tahap dari Algoritma Genetika ketika memilih gen-gen dari populasi yang ada dan kemudian akan dilanjutkan ke tahap selanjutnya yaitu perkembangbiakan (Crossover dan Mutation). Ada beberapa algoritma khusus untuk menjalankan tahap seleksi ini. Contohnya adalah cara roulette-wheel yang langkah-langkahnya adalah sebagai berikut : 1. Fungsi fitness ditentukan pada tiap-tiap individu. Kemudian dinormalisasi. Maksud dari normalisasi ini adalah dengan membagi nilai fitness tiap individu dengan
11
jumlah total dari total fitness yang ada, sehingga jumlah total dari semua fitness pada populasi adalah 1. 2. Populasi diurutkan menurun berdasarkan nilai fitness 3. Kemudian nilai fitness yang sudah ada diakumulasikan berdasarkan gen yang sudah diurutkan. Sehingga nilai fitness suatu individu adalah jumlah dari nilai fitness individu itu dan nilai fitness individu sebelumnya. 4. Random nilai R dari 0 sampai dengan 1 5. Individu yang dipilih adalah individu yang mempunyai nilai akumulasi fitness di atas R. Ada pula beberapa algoritma yang digunakan selain roulette-wheel tersebut. Yang digunakan oleh kebanyakan orang adalah dengan menentukan sendiri batas dari fitness yang diinginkan. Kalau kurang atau melewati batas yang ditentukan maka individu terebut akan dibuang atau diseleksi. Kalau sesuai dengan batas yang ditentukan maka individu tersebut akan dipilih dan kemudian akan dilanjutkan ke proses selanjutnya. 2. Crossover Crossover kalau diterjemahkan secara harafiah ke dalam Bahasa Indonesia adalah Perkawinan Silang. Memang benar yang dilakukan pada tahap ini adalah dengan mengawinkan atau mengkombinasikan 2 individu agar diperoleh individu yang baru. Yang dapat dimisalkan dengan menyilangkan 2 parents (orang tua) dan juga akan menghasilkan 2 children (anak).
12
Ada beberapa jenis crossover : 1. One Point Crossover Yaitu menyilangkan 2 individu dengan 1 batas yang tertentu pada kedua parents. Contoh :
Gambar 2.1 One Point Crossover.
2. Two-point crossover Yaitu menyilangkan 2 individu dengan 2 batas yang tertentu pada kedua parents. Contoh :
Gambar 2.2 Two Point Crossover.
3. Cut and Splice Crossover
13
Yaitu menyilangkan 2 individu dengan 1 atau lebih batas yang tidak ditentukan pada kedua parents. Contoh :
Gambar 2.3 Cut and Splice Crossover.
3. Mutation (mutasi) Mutasi adalah dengan memutasi atau mengganti salah satu gen dengan gen lain pada suatu individu tertentu. Bukan semua individu pada populasi melaikan hanya satu individu yang mengalami mutasi tersebut. Hal ini dilakukan agar diharapkan menemukan individu yang mempunyai nilai fitness yang diinginkan.
2.2.5 Konsep algoritma genetika Algoritma Genetika khususnya diterapkan sebagai simulasi komputer dimana sebuah populasi representasi abstrak (kromosom) dari solusi-solusi calon (individual) pada sebuah masalah optimisasi akan berkembang menjadi solusi-solusi yang lebih baik. Secara tradisional, solusi-solusi dilambangkan dalam biner sebagai string '0' dan '1', walaupun dimungkinkan juga penggunaan penyandian (encoding) yang berbeda. Evolusi dimulai dari
14
sebuah populasi individual acak yang lengkap dan terjadi dalam generasi-generasi. Dalam tiap generasi, kemampuan keseluruhan populasi dievaluasi, kemudian multiple individuals dipilih dari populasi sekarang (current) tersebut secara stochastic (berdasarkan kemampuan mereka), lalu dimodifikasi (melalui mutasi atau rekombinasi) menjadi bentuk populasi baru yaitu populasi sekarang (current) pada iterasi berikutnya dari algoritma. Dalam teori genetika sebuah individu akan mengalami perkembang biakan, dimana pada saat perkembangbiakan tersebut terdapat penurunan sifat kepada keturunannya (offspring). Keturunan ini dapat memiliki sifat gabungan dari kedua parent. Pada saat penurunan sifat maka akan terdapat individu baru yang akan di seleksi alam. Bila turunan tersebut mampu baik maka akan mampu bertahan, sebaliknya pula bila tidak maka akan musnah. Pada akhirnya kita akan mendapat keturunan yang terbaik. Pada akhirnya individu yang terbaik tersebut adalah solusi optimal bagi permasalahan kita.
2.2.6 Mekanisme Algoritma Genetika Mekanisme yang ada dalam Algoritma Genetika adalah sangat sederhana, yaitu hanya melibatkan penyalinan string dan pertukaran bagian string. Siklus perkembangbiakan GA diawali dengan pembuatan himpunan solusi secara acak yang dinamakan populasi. Dimana didalamnya terdapat individu-individu yang dinamakan
kromosom.
Kromosom
ini
secara
lambat
laun
mengalami
iterasi
’Perkembangbiakan’ dalam sebuah generasi. Selama dalam sebuah generasi kromosom-
15
kromosom ini di evaluasi dengan menggunakan rumus yang telah ditentukan dengan rumus fitness. Untuk menciptakan generasi berikutnya dengan kromosom yang baru (offspring) dapat dilakukan dengan menggabungkan dua potongan kromosom yang telah didapatkan dengan operator crossover atau mutasi. Sebuah generasi baru sebelum dievaluasi lagi, maka dia melalui proses seleksi berdasarkan fungsi fitnessnya. Dari kreasi ini kromosomkromosom yang paling fit mempunyai kemungkinan besar untuk diseleksi. Setelah beberapa generasi maka algoritma ini akan mengalami konvergen pada kromosom terbaik yang merupakan nilai optimum dari permasalahan yang diselesaikan.
2.2.7 Proses Algoritma Genetika Siklus Algoritma Genetika bisa Disingkat sebagai berikut :
Populasi Awal
Seleksi Individu
Reproduksi : Crossover dan Mutasi Populasi Baru
Gambar 2.4 Siklus Algoritma Genetika.
16
Langkah pertama dalam pemecahan masalah dengan GA adalah pengkodean terhadap masalah yang akan kita pecahkan. Pada algoritma ini dalam mengasumsikan sebuah solusi untuk sebuah persoalan dimungkinkan dengan diwakili oleh satu set parameter. Parameter ini dinamakan gen. Berisi nilai-nilai yang bersatu membentuk string (Kromosom). Selanjutnya kromosom yang berkumpul membentuk populasi. Dari sebuah populasi inilah GA memulai untuk pencarian. Dalam GA fungsi Fitness harus dirancang sesuai dengan masing-masing masalah yang akan diselesaikan. Misalnya saja untuk masalah mencari rute terpendek dari suatu perjalanan, maka fungsi Fitnessnya adalah jarak tempuh. Sedangkan untuk optimasi penjadwalan kuliah fungsi Fitnessnya melibatkan faktor-faktor seperti adanya dua kuliah atau lebih yang akan diajarkan dalam satu kelas, kepadatan dosen mengajar setiap hari, penempatan kuliah dan praktikum tidak semestinya. Sebagai contoh untuk pengkodean jika kita mempunyai masalah yaitu mencari maximum sebuah fungsi dari 3 variabel(x,y,z) dan akan menampikan masing-masing variabel dengan 6 bit. Dari contoh ini kita melakukan pengkodean dengan membentuk kromosom yang terdiri dari 3 gen yang masing-masing gen terdiri dari 6 bit sehingga sebuah kromosom terdiri dari 18 bit. Suatu hal yang sangat mendasar dari GA adalah bahwa algoritma ini bekerja pada daerah pengkodean dan daerah solusi. Operasi genetika (Crossover dan Mutasi) bekerja
17
pada daerah pengkodean, sedang proses evaluasi dan proses seleksi bekerja pada daerah solusi. Dalam reperesentasi nonbiner, ada dua hal yang perlu diperhatikan untuk pengkodean baik dalam fenotip ataupun genetik, yaitu: 1.
Feasibilitas dan legalitas dari sebuah kromosom
2.
Pemetaan
Feasibilitas adalah apakah solusi/kromosom berada pada daerah yang feasible dari domain permasalahan InFeasibilitas kromosom menghilangkan kealamian batasan-batasan dalam permasalah optimasi. Legalitas adalah apakah suatu solusi/kromosom dapat menyelesaikan masalah. Untuk beberapa permasalahan kasus metode pinalti telah diajukan untuk mengatasi kasus kromosom yang tidak dimungkinkan. Dalam permasalan kasus optimasi nilai optimum secara typikal akan berada di wilayah antara daerah yang mungkin ataupun yang tidak mungkin. Penerapan metode pinalti akan mengeksploitasi pencarian GA pada nilai optimum di dua daerah tersebut. Kromosom-kromosom yang tidak legal menghilangkan kealamian dari teknik encoding. Untuk beberapa permasalah kombinasional, beberapa cara digunakan untuk menghindari keturunan yang tidak legal karena tidak dapat mewakili suatu solusi, dalam arti kromosom tersebut tidak dapat di evaluasi. Salah satu cara, misalnya PMX (Partially Matched Crossover) operator. Metode ini digunakan untuk mencegah dihasilkannya
kromosom yang tidak mungkin dan tidak ilegal.
18
Pemetaan dari kromosom-kromosom ke solusi memungkinkan satu dari tiga kasus ini terjadi: 1.
Pemetaan dari 1 ke –n
2.
Pemetaan dari 1 ke 1
3.
Pemetaan dari –n ke 1
Pemetaan 1 ke 1 merupakan pemetaan terbaik, karena dari pemetaan ini satu kromosom dapat dipasangkan dengan satu solusi. Pada pemetaan –n ke 1, sejumlah –n kromosom mewakili satu solusi yang sama, sedangkan pemetaan 1 ke –n adalah pemetaan yang tidak diinginkan karena merelasikan satu kromosom dengan banyak solusi, yang menjelaskan banyak solusi sehingga menjadi tidak jelas solusi mana yang sebenarnya yang ditujukan.
2.3 VRP(Vehicle Routing Problem) VRP merupakan program non-linear yang mencari sebuah solusi pemecahan masalah. Program ini pertama kali ditemukan oleh Dantzig and Ramser pada tahun 1959. VRP terdiri dari penentuan rute kendaraan yang melayani beberapa pelanggan. Setiap kendaraan memiliki kapasitas angkut, dan setiap pelanggan memiliki demand. Tiap pelanggan dikunjungi tepat satu kali dan total demand tiap rute tidak boleh melebihi kapasitas angkut kendaraan. Dalam VRP sendiri dikenal pula istilah depot, dimana tiap kendaraan harus berangkat dan kembali ke depot itu. Hal tersebutlah yang menyebabkan VRP sering disebut sebagai permasalahan n-TSP.
19
Faktor yang sering muncul pada VRP adalah masalah kapasitas yang dikenal dengan nama Capacitated Vehicle Routing Problem (CVRP) dan juga masalah batasan waktu yang dikenal sebagai Vehicle Routing Problem with Time Windows (VRPTW). Kedua permasalahan ini dapat digabungkan dengan prioritas utama yaitu semua permintaan terpenuhi batas waktunya. Ada pun beberapa macam tipe Vehicle Routing Problem (VRP) berdasarkan faktor – faktor yang ditemui: •
Capacitated VRP (VRP)
Faktor : setiap kendaraan mempunyai kapasitas yang terbatas. •
VRP With Time Windows (VRPTW)
Faktor : pelanggan harus dilayani dengan waktu tertentu •
Multiple Depot VRP (MDVRP)
Faktor : distributor memiliki banyak depot •
VRP With Pick-Up and Delivering (VRPPD)
Faktor : pelanggan diperbolehkan mengembalikan barang ke depot asal dan menerima barang dari pelanggan •
Split Delivery VRP (SDVRP)
Faktor : pelanggan dilayani dengan kendaraan berbeda
20
•
Stochastic VRP (SVRP)
Faktor : munculnya random values (seperti jumlah pelanggan, jumlah permintaan, waktu perjalanan atau waktu pelayanan) •
Periodic VRP
Faktor : pengantaran hanya dilakukan di hari tertentu 2.3.1 VRPTW Menurut Kallehauge dkk. (2001), vehicle routing problem dengan time windows (VRPTW) adalah perluasan dari VRP. Jika pada VRP ditambahkan time window pada masing–masing konsumen, maka permasalahan tersebut menjadi VRPTW. Untuk VRPTW, selain adanya kendala kapasitas kendaraan, terdapat tambahan kendala yang mengharuskan kendaraan untuk melayani tiap konsumen pada time frame tertentu. Kendaraan boleh datang sebelum time window “open”, tetapi konsumen tersebut tidak dapat dilayani sampai time window “open”. Kendaraan tidak diperbolehkan untuk datang setelah time window “closed”. Tangiah
(1995)
mendefinisikan
VRPTW
sebagai
permasalahan
untuk
menjadwalkan sekumpulan kendaraan, dengan kapasitas dan travel time terbatas, dari central depot kesekumpulan konsumen yang tersebar secara geografis, dengan demand diketahui, dalam time windows tertentu. Time windows adalah two sided, yang berarti bahwa tiap konsumen harus dilayani saat atau setelah earliest time, dan sebelum latest time dari konsumen tersebut. Jika kendaraan datang ke konsumen sebelum earliest time dari
21
konsumen tersebut, maka akan menghasilkan idle atau waktu tunggu. Kendaraan yang datang ke konsumen setelah latest time adalah tardy. Terdapat pula waktu service yang diperlukan untuk melayani tiap konsumen. Biaya rute dari suatu kendaraan adalah total dari waktu travel (proposional dengan jarak), waktu tunggu, dan waktu service, yang diperlukan untuk mengunjungi sekumpulan konsumen. Homberger dkk. (1999) mendefinisikan permasalahan VRPTW sebagai berikut: n konsumen akan dilayani dari sebuah depot, dengan sejumlah kendaraan yang memiliki kapasitas, Q, yang sama. Untuk tiap konsumen i, i=1, 2, ..., n, terdapat demand qi, waktu service si, dan service time window zi=[ei, fi]. Lower bound ei merupakan waktu paling awal untuk melakukan service, dan upper bound fi, waktu paling lambat untuk melakukan service. Demand qi dari konsumen i harus dipenuhi dengan sekali service saja, dalam batas time window zi. Sebagai tambahan, e0 merupakan waktu paling awal untuk kendaraan berangkat dari depot i, i=0, dan f0 merupakan waktu paling lambat untuk kendaraan kembali ke depot. Data mengenai lokasi dari depot, dan konsumen, jarak terpendek dij, serta waktu travel d’ij antara dua lokasi, diketahui. Tujuannya untuk menentukan jadwal rute yang feasible, yaitu pertama untuk meminimalkan jumlah kendaraan, dan kedua untuk meminimalkan total jarak travel. Konsumen tidak dapat dilayani diluar time window mereka masing–masing. Tetapi kendaraan diperbolehkan untuk datang sebelum lower bound dari time window. Apabila hal ini terjadi, maka kendaraan harus menunggu sampai batas waktu paling awal service tersebut dapat dilakukan.
