BAB II LANDASAN TEORI. Suatu graph merupakan suatu pasangan { E(G), V(G) } dimana :

BAB II LANDASAN TEORI

2.1 Defenisi Graph Suatu graph merupakan suatu pasangan { E(G), V(G) } dimana : •

V(G) adalah sebuah himpunan terhingga yang tidak kosong ( non empty finite set) yang elemennya disebut vertek (point/simpul/bahul).

•

E(G) adalah suatu family dengan elemen-elemennya adalah pasangan yang tidak berurut dari vertek V(G) yang disebut dengan edge (line/rusuk).

Secara umum suatu graph dengan p vertek dan q edge disebut sebuah (p,q) graph yang dapat ditulis G (p,q).

2.1.1 Graph Terhubung (Connected Graph) Sebuah graph dikatakan terhubung apabila setiap pasang 2 vertek dari graph G terdapat sedikitnya sebuah edge (lintasan). Graph terhubung dapat digambarkan sebagai berikut :

V1

V3

V2

V5 V6

V4

V7

V8

Gambar 2.1. Graph terhubung 2.1.2 Graph Tak Berarah (undirected graph) Berdasarkan jenis garis-garisnya, graph dibedakan menjadi 2 kategori yaitu Graph Tak Berarah (Undirected Graph) dan Graph Berarah (Directed Graph =

Universitas Sumatera Utara

Digraph). Dalam permasalahan yang akan dibahas, penulis menggunakan Graph Tak Berarah yang akan diuraikan dalam sub-bab ini.

2.1.2.1 Graph Sederhana (Simple Graph) Graph sederhana (simple graph) adalah graph yang tidak mempunyai loop ataupun garis paralel. Graph sederhana dapat digambarkan sebagai berikut : A

B

A

C

B

E

C

D

F

Gambar 2.2: Graph sederhana

2.1.2.2 Graph Lengkap (Complete Graph) Graph lengkap dengan n titik (simbol K n ) adalah graph sederhana dengan n titik dimana setiap 2 titik berbeda dihubungkan dengan suatu garis. Banyaknya garis dalam suatu graph lengkap dengan n titik adalah lengkap dapat dirumuskan sebagai berikut : K n =

n(n − 1) buah. Maka sebuah graph 2 n(n − 1) . 2

Gambar 2.3 : Graph lengkap dengan K5


2.2 VRP (Vehicle Routing Problem) Andaikan ada satu jenis komoditi ditempatkan disebuah depot (i=0) dengan K kendaraan (vehicle) yang berpangkalan di depot tersebut yang mempunyai kapasitas sama yaitu W. Andaikan ada N pelanggan (customer) dinyatakan dengan i=1,2,3,…,N dengan masing-masing permintaan sebesar d i , 1≤ i ≤N, jarak antara dua lokasi i dan j diketahui sebesar c ij, jarak tempuh maksimum yang diijinkan adalah T. Masalah utama dalam masalah vehicle routing ini adalah bagaimana menentukan rute untuk K kendaraan tersebut sedemikian sehingga setiap pelanggan terlayani tepat satu kendaraan, permintaan terpenuhi, muatan sepanjang rute tidak melampaui kapasitas W, panjang rute dari depot keliling kembali ke depot lagi tidak melampaui T dan akhirnya jumlah total panjang rute seluruh K kendaraan minimum. Bentuk graph dari permasalahan vrp dapat digambarkan sebagai berikut : V8

V1

DEPOT

V7

V2

V6 V3 V5 V4 Gambar 2.4 : Rute Perjalanan Vehicle

2.2.1 Formulasi Matematika VRP Formulasi matematika dari masalah vehicle routing adalah sebagai berikut : N N  K  min z = ∑∑  cij ∑ xijk  =i 0=j 0  = k 1 


dengan kendala : N

K

= ∑∑ xijk 1=j 1, 2...N =i 0= k 1 N

N

= ∑ xilk − ∑ xljk 0

= k 1, 2...K

=i 0=j 0

l = 0,1...N N

= ∑ x0 jk 1=k 1, 2...K j =1

N



N

∑ d ∑ x

i =i 1 =j 0

ijk



N

  ≤W 

k= 1, 2...K

≤T

k= 1, 2...K

N

∑∑ c .x

=i 0=j 0

ij

ijk K

yi − y j + N ∑ xijk =1 ≤ N − 1

i ≠ j =1, 2...N

k =1

1, bila kendaraan k melayani j setelah melayani i.

xijk =

0, bila tidak demikian.

2.2.2 Jenis-Jenis Vehicle Routing Problem Pada permasalahan vrp dapat kita temukan berbagai kombinasi jenis elemen yang merupakan masalah dasar dari vehicle routing. Jenis-jenis kombinasi dasar dari vehicle routing yang telah diperkenalkan antara lain Capacitated Vehicle Routing Problem (CVRP), the VRP with Time Windows (VRPTW), Time Dependent variant (TDVRPTW), the VRP with Pickup and Delivery (VRPPD), dan the Dynamic VRP (DVRP).


2.3 Algoritma Genetika Algoritma Genetika merupakan suatu algoritma yang terinspirasi dari teori evolusi Darwin yang menyatakan bahwa kelangsungan hidup suatu makhluk dipengaruhi aturan bahwa yang kuat adalah yang menang. Algoritma Genetika merupakan algoritma pencarian hasil terbaik yang berdasarkan atas perkawinan dan seleksi gen secara alami. Algortima genetika (AG) pertama kali dirintis oleh John Holland dari Universitas Michigan pada tahun 1960-an, algoritma genetika telah diaplikasikan secara luas pada berbagai bidang. Algoritma genetika banyak digunakan untuk memecahkan masalah optimasi, walaupun pada kenyataannya juga memiliki kemampuan yang baik untuk masalah-masalah selain optimasi. John Holland menyatakan bahwa setiap masalah yang berbentuk adaptasi (alami maupun buatan) dapat diformulasikan dalam terminologi genetika. Pada algoritma genetika, teknik pencarian dilakukan sekaligus atas sejumlah solusi yang mungkin dikenal dengan istilah populasi. Individu yang terdapat dalam satu populasi disebut dengan istilah kromosom. Kromosom ini merupakan suatu solusi yang masih berbentuk simbol. Populasi awal dibangun secara acak, sedangkan populasi berikutnya merupakan hasil evolusi kromosom-kromosom melalui iterasi yang disebut dengan generasi. Pada setiap generasi, kromosom akan melalui proses evaluasi dengan menggunakan alat ukur yang disebut dengan fungsi fitness. Nilai fitness dari suatu kromosom akan menunjukkan kualitas dari kromosom dalam populasi tersebut. Generasi berikutnya dikenal dengan istilah anak (offspring) terbentuk dari gabungan dua kromosom generasi sekarang yang bertindak sebagai induk (parent) dengan menggunakan operator penyilangan (crossover). Selain operator penyilangan, suatu kromosom dapat juga dimodifikasi dengan menggunakan operator mutasi. Populasi generasi yang baru dibentuk dengan cara menyeleksi nilai fitness dari kromosom induk (parent) dan nilai fitness dari kromosom anak (offspring), serta menolak kromosom-kromosom yang lainnya sehingga ukuran populasi (jumlah kromosom dalam suatu populasi) konstan. Setelah melalui beberapa generasi, maka Algoritma Genetika akan konvergen ke kromosom yang terbaik.


2.3.1 Komponen-komponen Algoritma Genetika Pada dasarnya algoritma genetika memiliki 7 komponen, antara lain : a.

Pendefenisian Individu

Pendefenisian individu merupakan proses pertama yang harus dilakukan dalam Algoritma Genetika yang menyatakan salah satu solusi yang mungkin dari suatu permasalahan yang diangkat. Pendefenisian individu dilakukan dengan mendefenisikan jumlah dan tipe dari gen yang digunakan dan tentunya dapat mewakili solusi permasalahan yang diangkat. Sebuah kromosom dibentuk dari komponen-komponen penyusun yang disebut sebagai gen dan nilainya dapat berupa bilangan numerik, biner, simbol ataupun karakter tergantung dari permasalahan yang ingin diselesaikan.

b. Nilai Fitness 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. Pengertian nilai fitness ini sendiri adalah nilai yang menyatakan baik tidaknya suatu solusi (individu). Algoritma Genetika bertujuan mencari individu dengan nilai fitness yang paling tinggi. Umumnya kromosom ber-fitness tinggi akan bertahan dan berlanjut kegenerasi berikutnya. Kromosom yang telah terbentuk akan berevolusi secara berkelanjutan yang disebut dengan generasi. Dalam tiap generasi kromosom-kromosom tersebut dievaluasi tingkat keberhasilan nilai solusinya terhadap masalah yang ingin diselesaikan menggunakan ukuran yang disebut dengan nilai fitness. Nilai fitness inilah yang dijadikan acuan dalam mencapai nilai optimal dalam Algoritma Genetika.

c. Seleksi Proses seleksi adalah proses evaluasi kualitas setiap kromosom di dalam populasi untuk memperoleh peringkat calon solusi. Seleksi bertujuan untuk memberikan kesempatan reproduksi yang lebih besar bagi anggota populasi yang paling fit. Proses seleksi dilakukan dengan mencari kromosom terbaik dalam satu generasi, dimana untuk menentukan suatu kromosom terbaik dapat dilihat dari nilai fitness-nya. Proses seleksi dilakukan dengan mengevaluasi setiap kromosom berdasarkan nilai fitness untuk mendapatkan peringkat terbaik. Selanjutnya dipilih secara acak, kromosom-kromosom


yang mengalami proses rekombinasi. Umumnya kromosom ber-fitness tingggi yang berpeluang lebih besar untuk terpilih. Kromosom dengan kualitas yang lebih baik akan memiliki peluang lebih besar untuk terpilih sebagai calon kromosom generasi berikutnya. Kemampuan Algoritma Genetika untuk memproduksi kromosom yang lebih baik secara progresif tergantung pada penekanan selektif (Selektif Pressure) yang diterapkan ke populasi. Penekanan selektif dapat diterapkan dalam dua cara yaitu dengan membuat lebih banyak kromosom anak yang dipelihara dalam populasi dan memilih hanya kromosom-kromosom terbaik bagi generasi berikut. Walaupun induk dipilih secara acak, metode ini akan terus menghasilkan kromosom yang lebih baik berhubungan dengan penekanan selektif yang diterapkan pada individu anak tersebut. Cara lainnya adalah dengan memilih induk yang lebih baik ketika membuat keturunan baru. Dengan metode ini, hanya kromosom sebanyak yang dipelihara dalam populasi yang perlu dibuat bagi generasi berikutnya. Walaupun penekanan selektif tidak diterapkan ke level keturunan, metode ini akan terus menghasilkan kromosom yang lebih baik, karena adanya penekanan selektif yang diterapkan ke induk. Terdapat beberapa metode seleksi untuk mendapatkan calon induk yang baik, namun proses seleksi yang biasa digunakan adalah Roulette Wheel Selection (Seleksi Roda Roulette). Sesuai dengan namanya, metode ini menirukan permainan roulettewheel dimana masing-masing kromosom menempati potongan lingkaran pada roda roulette secara proporsional sesuai dengan nilai fitness-nya.

d. Perkawinan Silang (Crossover) Salah satu komponen paling penting dalam Algoritma Genetika adalah crossover atau perkawinan silang, dikenal juga dengan pindah silang. Crossover bertujuan menambah keanekaragaman kromosom digenerasi berikutnya berdasarkan kromosomkromosom dari generasi saat ini. Crossover melibatkan dua induk untuk menghasilkan keturunan yang baru. Crossover dilakukan dengan melakukan pertukaran gen dari dua induk secara acak. Kromosom baru yang terbentuk akan mewarisi sebagian dari sifat kromosom induknya. Dalam proses ini dilakukan penukaran bagian gen yang telah dipilih posisinya secara acak dalam satu kromosom. Dalam proses ini, perkawinan silang yang terjadi adalah perkawinan antar seluruh gen dalam suatu generasi.


Perkawinan Silang (Crossover) juga dapat berakibat buruk jika ukuran populasinya sangat kecil. Dalam suatu populasi yang sangat kecil, suatu kromosom dengan gen-gen yang mengarah ke solusi akan sangat cepat menyebar ke kromosomkromosom lainnya. Untuk mengatasi masalah ini digunakan suatu aturan bahwa perkawinan silang hanya bisa dilakukan dengan suatu probabilitas tertentu ρc . Artinya pindah silang bisa dilakukan hanya jika suatu bilangan random yang dibangkitkan kurang dari probabilitas yang ditentukan tersebut. Pada umumnya probabilitas tersebut diset mendekati 1. Probabilitas crossover ρc merupakan nilai perbandingan jumlah kromosom yang diharapkan akan mengalami perkawinan silang terhadap jumlah kromosom dalam suatu populasi. Probabilitas crossover yang tinggi akan memungkinkan pencapaian alternatif solusi yang lebih bervariasi dan mengurangi kemungkinan menghasilkan nilai optimum yang tidak dikehendaki. Tetapi bila nilai ini terlalu tinggi akan mengakibatkan pemborosan waktu untuk melakukan perhitungan di daerah solusi yang tidak menjanjikan hasil yang optimal.

e. Mutasi Mutasi menciptakan individu baru dengan melakukan modifikasi satu atau lebih gen dalam individu yang sama. Mutasi berfungsi untuk menggantikan gen yang hilang dari populasi selama proses seleksi serta menyediakan gen yang tidak ada dalam populasi awal, sehingga mutasi akan meningkatkan variasi populasi. Dalam proses ini dilakukan mutasi atau penukaran pasangan gen yang telah dipilih secara acak dalam satu kromosom. Penukaran pasangan ini dilakukan pada dua gen dalam suatu kromosom. Melalui mutasi, kromosom baru dapat diciptakan dengan melakukan modifikasi terhadap satu atau lebih karakter pada kromosom yang sama. Cara termudah untuk melakukan mutasi adalah dengan mengubah satu atau lebih bagian dalam kromosom dan hal ini tergantung pada probabilitas mutasi. Probabilitas mutasi menentukan probabilitas jumlah gen di dalam satu populasi yang diharapkan mengalami mutasi. Apabila nilai probabilitas mutasi terlalu kecil, banyak kromosom


yang berguna mungkin tidak akan muncul dalam populasi, tetapi apabila terlalu tinggi maka keturunan yang dihasilkan akan kehilangan sifat-sifat yang mungkin saja merupakan sifat yang unggul dari induknya dan Algoritma Genetika akan kehilangan kemampuan untuk belajar dari pencarian-pencarian sebelumnya.

f. Elitisme Proses seleksi dilakukan secara random sehingga tidak ada jaminan bahwa suatu individu yang bernilai fitness tertinggi akan selalu terpilih. Walaupun individu bernilai fitness tertinggi terpilih, mungkin saja individu tersebut akan rusak (nilai fitness-nya menurun) karena proses perkawinan silang. Untuk menjaga agar individu bernilai fitness tertinggi tersebut tidak hilang selama proses evolusi, maka perlu dibuat satu atau beberapa kopinya. Prosedur inilah yang dikenal sebagai elitisme. Proses ini dilakukan untuk mempertahankan individu yang terbaik dari tiap generasi, karena setelah dilakukan proses perkawinan silang dan mutasi, kemungkinan untuk kehilangan kromosom yang terbaik sangat besar. Proses elitisme ini dilakukan dengan menggantikan kromosom terburuk dari generasi berikutnya dengan kromosom terbaik dari generasi sebelumnya apabila kromosom yang baru tersebut tidak lebih buruk dari yang lama.

g. Evaluasi Solusi Proses evaluasi dilakukan dengan menghitung nilai fitness dari setiap kromosom dalam suatu generasi. Bila ada kromosom yang tidak mempunyai informasi titik tujuan maka kromosom ini dianggap mempunyai nilai fitness terbesar dan dikatakan tidak valid. Proses ini akan mengevaluasi setiap populasi dengan menghitung nilai fitness setiap kromosom dan mengevaluasinya sampai terpenuhi kriteria berhenti. Beberapa kriteria berhenti yang sering digunakan antara lain : 1. Berhenti pada generasi tertentu.


2. Berhenti setelah dalam beberapa generasi berturut-turut didapatkan nilai fitness tertinggi tidak berubah. 3. Berhenti bila dalam n generasi berikut tidak didapatkan nilai fitness yang lebih tinggi.

2.3.2 Parameter Genetik Yang disebut dengan parameter disini adalah parameter kontrol Algoritma Genetika, yaitu : ukuran populasi (popsize), probabilitas crossover (peluang crossover - ρc ) dan probabilitas mutasi (peluang mutasi - ρ m ). Nilai parameter ini ditentukan juga berdasarkan permasalahan yang akan dipecahkan. Tidak ada aturan pasti tentang berapa nilai setiap parameter ini. (Koza, 2001). Ukuran populasi kecil berarti hanya tersedia sedikit pilihan untuk crossover dan sebagian kecil dari domain solusi saja yang dieksplorasi untuk setiap generasinya. Sedangkan bila terlalu besar, kinerja Algoritma Genetika menurun. Penelitian menunjukkan ukuran populasi besar tidak mempercepat proses pencarian solusi. Disarankan ukuran populasi berkisar antara 2030, probabilitas crossover umumnya berkisar antara 0,6 sampai dengan 0,9 dan probabilitas mutasi kecil berkisar 0.5%-1% atau sekitar 1 dibagi dengan jumlah gen. Jumlah generasi besar berarti semakin banyak iterasi yang dilakukan, dan semakin besar domain solusi yang akan dieksplorasi (Nico saputro dan Yento, 2004). Menurut Kusumadewi dan Purnomo (2005), ada beberapa rekomendasi yang bisa digunakan untuk menentukan nilai parameter tersebut, antara lain : a. Untuk permasalahan yang memiliki kawasan solusi cukup besar, De Jong merekomendasikan untuk nilai parameter control : (popsize; ρc ; ρ m ) = (50; 0,6; 0,001) b. Bila rata-rata fitness setiap generasi digunakan sebagai indikator, maka Grefenstette merekomendasikan : (popsize; ρc ; ρ m ) = (30; 0,95; 0,01) c. Bila fitness dari individu terbaik dipantau pada setiap generasi, maka usulannya adalah : (popsize; ρc ; ρ m ) = (80; 0,45; 0,01)


2.3.3 Mekanisme Kerja Algoritma Genetika Algoritma genetika dimulai dengan pembentukan sejumlah solusi yang dilakukan secara acak. Sebuah solusi yang dibangkitkan dalam algoritma genetika disebut sebagai kromosom, sedangkan kumpulan kromosom-kromosom tersebut disebut sebagai populasi. Sebuah kromosom dibentuk dari komponen-komponen penyusun disebut sebagai gen dan nilainya dapat berupa bilangan numerik, biner, simbol atau pun karakter tergantung dari permasalahan yang ingin diselesaikan. Kromosom-kromosom tersebut akan berevolusi secara berkelanjutan yang disebut dengan generasi. Dalam tiap generasi, kromosom-kromosom tersebut dievaluasi tingkat keberhasilan nilai solusinya terhadap masalah yang ingin diselesaikan dengan menggunakan ukuran yang disebut dengan nilai fitness. Untuk memilih kromosom yang tetap dipertahankan untuk generasi selanjutnya dilakukan proses yang disebut dengan seleksi. Proses seleksi kromosom menggunakan konsep teori evolusi Darwin yaitu kromosom yang mempunyai nilai fitness tinggi akan memiliki peluang lebih besar untuk terrpilih lagi pada generasi selanjutnya. Kromosom-kromosom baru yang disebut dengan kromosom anak (offspring), dibentuk dengan cara melakukan perkawinan antar kromosom-kromosom dalam satu generasi yang disebut sebagai proses perkawinan silang (crossover). Mekanisme perubahan susunan unsur penyusun makhluk hidup akibat adanya faktor alam yang disebut dengan mutasi direpresentasikan sebagai proses berubahnya satu atau lebih nilai gen dalam kromosom dengan suatu nilai acak. Jumlah gen dalam populasi yang mengalami mutasi ditentukan oleh parameter yang dinamakan mutation rate. Setelah beberapa generasi akan dihasilkan kromosom-kromosom yang nilai gen-gennya konvergen ke suatu nilai tertentu yang merupakan solusi terbaik yang dihasilkan oleh algoritma genetika terhadap permasalahan yang ingin diselesaikan. Secara umum, blok diagram dari mekanisme sistem kerja algoritma genetika digambarkan sebagai berikut :


Bangkitkan populasi awal

Apakah kriteria optimasi tercapai

Evaluasi fungsi tujuan

ya

Individuindividu terbaik

Tidak

Mulai

Seleksi

Selesai

Pindah Silang Bangkitkan populasi baru

Mutasi

Gambar 2.5 Mekanisme sistem kerja Algoritma Genetika genetika

2.3.4 Hybrid Algoritma Genetika Banyak penelitian yang membuktikan bahwa standart GA sering digunakan dalam pencarian permasalahan local optimum, khususnya pada permasalahan yang cukup besar. Akibat permasalahan yang cukup besar ini, penelitian mengenai GA terus berkembang untuk mengkombinasikan terhadap algoritma lainnya salah satu dengan mengkombinasikan terhadap kendali logika fuzzy. Kombinasi ini disebut hybrid. Sebagai salah satu ilustrasi teknik local search yang sering dilakukan sebagai berikut :


procedure : Hibridisasi Algoritma Genetika input : parameter GA begin t  0; populasi awal P(t); fitness eval (P); while (not termination condition) do crossover P(t) menghasilkan offspring C(t); mutasi P(t) menghasilkan offspring C(t); local search C(t); fitness eval (C); Seleksi P(t+1) dari P(t) dan C(t); t  t+1; end output : Solusi terbaik; end

2.4 Kendali Logika Fuzzy Pemikiran utama teori logika fuzzy adalah memetakan sebuah ruang input ke dalam ruang output dengan menggunakan IF-THEN rules. Pemetaan dilakukan dalam suatu Fuzzy Inference System (FIS). Urutan rule bisa sembarangan. FIS mengevaluasi rule secara simultan untuk menghasilkan kesimpulan. Oleh karena itu, semua rule harus lebih didefinisikan lebih dahulu sebelum kita membangun sebuah FIS yang akan digunakan untuk menginterprestasikan semua rule tersebut.


Input

Black Box

Input

Output

Output

FIS

IF-THEN rules

Input

Output

(interpretations)

(assignments)

Gambar 2.6 : Konsep umum kronologi proses FIS merupakan sebuah metode yang dapat menginterprestasikan harga-harga dalam vektor input. Menarik kesimpulan berdasarkan sekumpulan IF-THEN rules yang diberikan dan kemudian menghasilkan vektor output.

2.4.1 Fungsi Keanggotaan Fungsi keanggotaan mendefenisikan bagaimana tiap titik dalam ruang input dipetakan menjadi bobot atau derajat keanggotaan antara 0 dan 1. Didalam teori himpunan, ruang input juga dikenal sebagai universe of discourse. Secara umum, beberapa kesimpulan tentang himpunan dan fungsi keanggotaan fuzzy diberikan dibawah ini : 1. Fuzzy ser menekankan konsep variabel samar (vague or fuzzy variable) seperti variabel hari akhir minggu, suhu panas, pelari cepat, dll.


2. Fuzzy set mengizinkan keanggotaan parsial dari suatu himpunan seperti hari jumat yang dianggap sebagai hari akhir minggu namun dengan derajat dibawah satu. 3. Derajat keanggotaan fuzzy dalam fuzzy set berkisar antara 0 sampai 1. 4. Tiap fungsi keaggotaan µ berasosiasi dengan sebuah fuzzy set tertentu dan memetekan suatu nilai input ke nilai derajat keanggotaan yang sesuai. Misalnya dalam kasus fuzzy set orang berbadan “tinggi” mempunyai fungsi keanggotaan sendiri, yaitu µ tinggi yang berbeda dengan fungsi keanggotaan dari fuzzy set orang berbadan “rendah”, yaitu µ rendah.

2.4.2 IF-THEN Rule Logika fuzzy bekerja berdasar aturan-aturan yang dinyatakan dalam bentuk pernyataan IF-THEN. Sebuah aturan fuzzy tunggal berbentuk sebagai berikut : If x is A then y is B dimana A dan B adalah linguistic values (seperti panas, dingin, tinggi, rendah dll) yang didefinisikan dalam rentang variabel X dan Y. Pernyataan “x is A” disebut antecedent atau premise sedangkan pernyataan “y is B” disebut consequent (kesimpulan). Sebuah contoh dari aturan fuzzy tunggal adalah : if pelayanan is biasa then bonus is sedang Antecedent dalam IF-THEN rule merupakan interpretasi yang dinyatakan dalam bentuk derajat keanggotaan antara 0 dan 1. Dalam hal ini, kata biasa dalam antecedent dinyatakan dalam bentuk bilangan derajat keanggotaan dari variabel input pelayanan dan dinotasikan µ biasa (pelayanan). Dengan kata lain, bagian IF bisa dimaknai dengan : If derajat keanggotaan pelayanan = µ biasa (pelayanan) Menginterpretasikan sebuah IF-THEN rule meliputi dua bagian. Pertama, mengevaluasi antecedent, yaitu melakukan fuzzifikasi pada input dan menerapkan operasi-operasi logika fuzzy dengan operator-operator fuzzy. Kedua, proses implikasi yaitu menerapkan hasil operasi logika fuzzy pada bagian antecedent untuk mengambil keputusan / kesimpulan dengan mengisikan fuzzy set keluaran ke variabel keluaran. Secara umum, ada tiga tahap penginterpretasian IF-THEN rule sebagai berikut : 1. Fuzzifikasi yakni menentukan derajat keanggotaan dari variabel masukan / variabel input.


2. Operasi fuzzy logic untuk melakukan operasi-operasi fuzzy logic. Antecedent memakai operator And yang biasa digantikan dengan fungsi minimum yaitu memilih variabek input mana yang memiliki derajat keanggotaan terkecil. 3. Implikasi sebagai menerapkan metode implikasi untuk menentukan bentuk akhir himpunan fuzzy keluaran. Consequent dari fuzzy rule ditentukan dengan “mengisikan” fuzzy set keluran ke variabel keluaran.

2.5

Hubungan antara algoritma genetika dengan kendali logika fuzzzy

Adapun hubungan antara algoritma genetika dan kendali logika fuzzzy dapat diuraikan dalam langkah-langkah sebagai berikut : a. Langkah-langkah hybrid algoritma genetika dengan kendali logika fuzzy : Langkah 1

: Inisialisasi populasi awal pada semua kromosom secara acak.

Langkah 2

: Set nilai parameter, tentukan nilai fitness dari 1/total jarak dan probabilitas fitness dari nilai fitnes / total fitnes kemudian seleksi kromosom-kromosom induk sebagai pemilihan induk yang terbaik.

Langkah 3

: Lakukan persilangan (crossover) pada dua kromosom induk untuk menghasilkan kromosom anak (offspring).

Langkah 4

: Lakukan proses mutasi pada kromosom offspring. Pada langkah 3 dan langkah 4, kedua probabilitas dari probabilitas crossover dan probabilitas mutasi akan diatur/ dikontrol dengan melakukan proses kendali logika fuzzy.

Langkah 5

: kembali pada langkah 2 sampai pada iterasi maksimum sehingga memperoleh kromosom yang terbaik.

Langkah 6

: Selesai dengan kromosom terbaik.


b. Kendali logika fuzzy Langkah-langkah yang dilakukan adalah sebagai berikut : Prosedur : untuk mengontrol nilai parameter algoritma genetika Langkah1

: Hitung perubahan nilai pada rata-rata nilai fitness antara generasi sekarang dengan generasi sebelumnya.

Langkah 2

: Tentukan nilai pengontrol antara generasi sekarang dengan generasi sebelumnya menggunakan tabel pengambilan keputusan fuzzy.

Langkah 3

: Setelah melakukan nilai pengontrol diatas, hitung nilai perubahan pada probabilitas crossover dan probabilitas mutasi.

Langkah 4

: Update nilai probabilitas crossover dan probabilitas mutasi.

Langkah 5

: kembali pada loop algoritma genetika.

Sehingga pada langkah-langkah diatas dapat ditunjukkan dengan diagram alir (flowchart) dari hybrid algoritma genetika dengan kendali logika fuzzy adalah sebagai berikut :


Mulai

Input Data

Pembentukan Populasi

Seleksi

Pilih r

TIDAK r< pc? YA

Automatic fine-tuning

Crossover

Pilih r

TIDAK r< pm? YA Mutasi

Iterasi max

TIDAK

YA Cari Kromosom Terpendek

AkhirBAB III GAMBAR 2.7 : FLOWCHART Universitas Sumatera Utara

BAB II LANDASAN TEORI. Suatu graph merupakan suatu pasangan { E(G), V(G) } dimana :

Recommend Documents