BAB 2 LANDASAN TEORI
2.1.
Fuzzy Relation Dalam dunia ini, banyak hal bersifat tidak pasti dimana derajat kepastian (degree
of preciseness) hal-hal tersebut secara intuisi berbeda-beda. Di sini, fuzzy set dapat dijadikan alternatif untuk merepresentasikan hal-hal yang tidak pasti itu. Misalkan D adalah domain data. Sebuah set X dalam domain D yang menyatakan suatu properti yang tidak bisa secara pasti dipenuhi oleh elemen D, dapat dinyatakan sebagai suatu fuzzy set X terhadap D. Fuzzy set ini dapat didefinisikan sebagai pemetaan D ke interval [ 0,1] yang ditentukan oleh sebuah membership function µ, dan dapat didefinisikan sebagai berikut: µx :D→[0,1] dimana X adalah sebuah fuzzy set dalam D dan µX adalah membership function dari fuzzy set. Membership function adalah suatu fungsi untuk menentukan derajat keanggotaan elemen dalam D terhadap fuzzy set X. Fuzzy Relation dapat didefinisikan sebagai suatu konsep untuk menyatakan relasi berupa fuzzy antara dua entity dalam sebuah domain. Relasi ini dinyatakan dalam interval [0,1], yang merupakan derajat asosiasi dari dua entity tersebut. Untuk lebih jelas, perhatikan contoh berikut: Misalkan R adalah sebuah fuzzy relation antara dua set X = {NYC, Paris} dan Y= {Beijing, NYC, London}, yang merepresentasikan konsep relasi “sangat jauh”.
6 Relasi ini dapat ditulis dengan notasi sebagai
Relasi ini juga dapat direpresentasikan dalam bentuk matriks dua dimensi sebagai berikut: NYC
Paris
Beijing
1
0.9
NYC
0
0.7
0.6
0.3
London
Konsep fuzzy relation tersebut dapat diperluas (extended) menjadi relasi berupa fuzzy antara dua fuzzy set dalam sebuah domain. Relasi ini dapat dihitung dengan menggunakan konsep fuzzy conditional probability relation. Misalkan µX dan µY adalah dua membership function dalam domain D, untuk dua fuzzy set X dan Y, dari fuzzy power set F (D) . R adalah sebuah fuzzy conditional probability relation antara dua fuzzy set X dan Y, yang dinyatakan oleh pemetaan R: F(D) x F(D)→[0,1] , dan didefinisikan sebagai
dimana R(X,Y) berarti derajat asosiasi Y terhadap X dan |Y| = cardinality dari Y. Sebagai contoh, misalkan ada 3 buah pastisi fuzzy set dalam domain
merupakan
7 D={d1,d2,d3,d4,d5,d6} yang memiliki nilai
Derajat kemiripan P1 terhadap P2 dapat dihitung sebagai berikut,
Sedangkan derajat kemiripan P2 terhadap P1 adalah
Tabel 2.1 di bawah ini menunjukkan derajat kemiripan dari ketiga partisi tersebut (Perhatikan bahwa R(P1,P2)=0.29 tetapi R(P2,P1) = 0.20) Tabel 2.1 Derajat Kemiripan R(X,Y) dari Partisi X/Y
P1
P2
P3
P1
1.00
0.29
0
P2
0.20
1.00
0.15
P3
0
0.29
1.00
Di sisi lain, setiap elemen data dalam D dapat direpresentasikan sebagai fuzzy set terhadap P dengan rumus
contohnya,
8
diartikan sebagai nilai true dari dari preposisi “if P1 then d1” atau nilai true d1 yang diberikan oleh P1. Dengan demikian dihasilkan fuzzy set elemen dalam D terhadap P sebagai berikut:
Dengan menggunakan rumus diatas, derajat kemiripan antara setiap elemen data dalam domain D dapat dihitung. Derajat kemiripan antara elemen ditunjukan pada Tabel 2.2. Tabel 2.2 Derajat Kemiripan R(X,Y) dari Elemen X/Y
D1
D2
D3
D4
D5
D6
D1
1.00
0.69
0.15
0
0
0
D2
0.80
1.00
0.36
0.27
0
0
D3
0.20
0.41
1.00
0.56
0
0
D4
0
0.24
0.43
1.00
0.60
0.60
D5
0
0
0
0.44
1.00
1.00
D6
0
0
0
0.44
1.00
1.00
9 2.2.
Genetic Algorithms (Algoritma Genetik) Genetic Algorithms adalah sebuah algoritma pencarian solusi yang dibuat
dengan menerapkan mekanisme evolusi genetika makhluk hidup dalam dunia biologi. Genetic Algorithms memiliki konteks yang lebih sederhana, karena tidak sekompleks dan serumit evolusi genetik dalam dunia biologi. Dalam dunia biologi, semua makhluk hidup memiliki sel, dan setiap sel terdiri dari kromosom-kromosom (susunan DNA) yang menjadi “blueprint“ dari makhluk hidup tersebut. Setiap kromosom terbagi menjadi gen-gen yang menentukan sifat-sifat makhluk hidup tersebut, seperti warna mata. Ciri yang berbeda-beda pada gen-gen tersebut dikenal dengan nama allele, seperti pada warna mata terdapat warna biru, coklat, dan sebagainya. Sama seperti dunia biologi, dalam Genetic Algorithms, juga terdapat kromosom, yang merupakan kandidat solusi untuk suatu masalah (problem). Kromosom ini juga terdiri dari gen-gen, yang dapat berupa bit-bit tunggal atau kumpulan beberapa bit yang merupakan elemen pembentuk kromosom. Bit-bit tunggal tersebut merupakan allele dari gen pada Genetic Algorithms. Hanya bedanya, dalam aplikasi Genetic Algorithms, setiap makhluk hidup (individu) tidak memiliki sel dan hanya memiliki satu kromosom.
2.2.1. Sejarah Singkat Genetic Algorithms Genetic Algorithms pertama kali ditemukan oleh John Holland pada tahun 1960an dan kemudian dikembangkan bersama murid-murid dan rekan kerjanya di Universitas Michigan pada tahun 1960-an sampai 1970-an. Tujuan Holland mengembangkan Genetic Algorithms saat itu bukan untuk mendesain suatu algoritma yang dapat memecahkan suatu masalah, namun lebih mengarah ke studi mengenai
10 fenomena adaptasi yang terjadi di alam dan mencoba menerapkan mekanisme adaptasi alam tersebut ke dalam sistem komputer. Genetic Algorithms yang dibuat Holland merupakan sebuah metode untuk memindahkan satu populasi kromosom (terdiri dari bit-bit 1 dan 0) ke populasi baru dengan menggunakan “seleksi alam” dan operator genetik seperti crossover, mutation (mutasi), dan inversion. Crossover menukar bagian kecil dari dua kromosom, mutasi mengganti secara acak nilai gen beberapa lokasi pada kromosom, dan inversion membalikkan urutan beberapa gen yang berurutan dalam kromosom. Dasar teori inilah yang menjadi dasar kebanyakan program yang menggunakan Genetic Algorithms saat ini.
2.2.2. Implementasi Genetic Algorithms Implementasi Genetic Algorithms secara umum memiliki tahapan proses (algoritma) sebagai berikut: a. Membuat populasi awal yang terdiri dari n buah kromosom (kandidat solusi untuk masalah yang ada) b. Menghitung fitness cost setiap kromosom dalam populasi. c. Melakukan pengulangan proses seleksi, crossover, mutasi hingga n buah kromosom baru (offspring) terbentuk. d. Mengganti populasi lama dengan populasi yang baru terbentuk. e. Kembali ke langkah (b). Namun sebelum melakukan implementasi, ada beberapa hal penting yang harus dilakukan, yaitu: a. Memilih jenis pengkodean suatu masalah ke Genetic Algorithms.
11 b. Menentukan operator genetik yang digunakan. c. Melakukan seleksi yang diperlukan. Setelah menentukan hal-hal di atas, Genetic Algorithms dapat diimplementasikan ke dalam program.
2.2.2.1.Pengkodean (encoding) suatu masalah ke Genetic Algorithms Cara pengkodean suatu kromosom merupakan faktor dalam menentukan kesuksesan sebuah Genetic Algorithms. Cara mengkodekan kromosom bergantung pada jenis masalah yang dihadapi. Jenis-jenis pengkodean yang umum digunakan adalah sebagai berikut: a. Binary Encodings Binary encodings adalah proses pengkodean dengan menggunakan bit 1 dan bit 0. Pengkodean ini merupakan pengkodean yang paling umum digunakan, termasuk oleh Holland pada awal penelitian tentang Genetic Algorithms. Contoh:
Kromosom A : 100101101110101 Kromosom B : 111010001011011 b. Many-Character and Real-Valued Encodings Pengkodean ini menggunakan huruf abjad (alphabet) atau angka real sebagai bentuk kromosom. Contoh:
Kromosom A : 1.235 2.215 1.525 0.223 5.412 Kromosom B : ABDGHFJSHDNBSHDHFNPODI
12 Jenis pengkodean tidak terbatas hanya pada dua pengkodean di atas, namun dapat dikembangkan lebih lanjut sesuai dengan masalah yang dihadapi.
2.2.2.2.Metode-Metode Seleksi Setelah menentukan jenis pengkodean yang digunakan, berikutnya adalah pemilihan
metode
seleksi
yang
digunakan
dalam
Genetic
Algorithms.
Tujuan dari seleksi adalah untuk menghasilkan kromosom yang dianggap layak melanjutkan kehidupan pada generasi berikutnya. Metode-metode seleksi antara lain: a. Roulette Wheel Selection Dalam metode ini, kromosom-kromosom yang ada dalam populasi ditempatkan ke dalam sebuah roda yang disebut “roulette wheel”. Setiap kromosom menempati potongan roda dengan ukuran yang proposional dengan fitness cost yang dimilikinya. Putaran dilakukan sebanyak n kali, dan pada setiap putaran, kromosom yang berada di bawah penanda roda dipilih sebagai parent untuk generasi berikutnya. Metode ini merupakan metode yang digunakan Holland pada Genetic Algorithms yang dikembangkan olehnya. Kelemahan utama metode ini adalah bila terdapat satu kromosom yang memiliki fitness cost yang tinggi sekali, sebagai contoh 90% dari keseluruhan roda, maka kromosom-kromosom yang lain hanya menempati 10% dari keseluruhan roda. Akibat dari kondisi ini, setiap putaran roda kemungkinan besar menghasilkan kromosom yang sama sehingga populasi baru hanya dihuni oleh kromosom yang sama.
13 Kondisi ini disebut sebagai “premature convergence” (konvergensi dini). b. Elitism Metode ini pertama kali diperkenalkan oleh Kenneth De Jong (1975). Dalam metode ini, beberapa gen terbaik dari setiap generasi diambil dan disimpan. Tujuan dari metode ini adalah mencegah hilangnya gen-gen terbaik karena tidak terpilih untuk melakukan crossover atau mutasi. Banyak penelitian yang menemukan bahwa metode ini dapat meningkatkan kinerja Genetic Algorithms secara signifikan. c. Rank Selection Metode ini merupakan alternatif untuk mencegah terjadinya konvergensi dini yang terlalu cepat. Dalam metode ini, kromosom-kromosom dalam populasi dirangking berdasarkan fitness cost yang dimiliki. Pemilihan kromosom tidak didasarkan pada nilai fitness cost, namun didasarkan pada nilai rangking yang diberikan. Hal ini bertujuan untuk mengurangi perbedaan nilai yang besar seperti yang dapat terjadi pada metode Roulette Wheel Selection. d. Tournament Selection Dalam metode ini, dua buah kromosom dipilih secara acak dari populasi. Sebuah angka r dipilih secara acak dari angka-angka di antara 0 dan 1. Sebuah parameter k ditentukan (misalnya k = 0.75). Jika r < k, maka kromosom dengan fitness cost yang lebih baik dipilih, dan jika sebaliknya, kromosom dengan fitness cost lebih rendah yang dipilih. Kedua kromosom tersebut kemudian dikembalikan ke populasi dan dapat dipilih lagi.
14 e. Steady-State Selection Dalam metode ini, hanya sebagian kecil kromosom dari populasi yang diganti dalam setiap generasi. Biasanya kromosom-kromosom yang memiliki fitness cost rendah diganti dengan kromosom-kromosom baru hasil crossover dan mutasi dari kromosom-kromosom dengan fitness cost tinggi. Metode ini sering digunakan dalam rule-based system dimana proses pembelajaran memiliki peran penting dan semua anggota populasi secara bersama-sama (tidak secara individual) memecahkan masalah yang ada.
2.2.2.3.Operator-Operator Genetik dalam Genetic Algorithms Langkah berikutnya adalah menentukan operator genetik yang digunakan dalam Genetic Algorithms. Penentuan operator genetik ini sangat bergantung pada jenis pengkodean yang dipilih. Dua buah operator genetik yang paling umum dan sering digunakan dalam implementasi Genetic Algorithms adalah: a. Crossover (Kawin Silang) Crossover dilakukan dengan cara menukar bagian kecil dari dua buah kromosom (parent) yang berbeda sehingga diperoleh kromosom baru yang masih memiliki sifat-sifat kromosom parent-nya. Cara melakukan crossover dapat dibagi berdasarkan jumlah posisi yang dipilih, yaitu single-point crossover dan two-point crossover. Pada single-point crossover, satu buah posisi dipilih secara acak dan membagi kromosom menjadi dua bagian. Satu bagian dari kromosom ditukarkan dengan kromosom lain yang juga telah dibagi menjadi 2.
15 Contoh single-point crossover :
Kromosom A : 1001011 | 01110101 Kromosom B : 1110100 | 01011011 Pada contoh ini, posisi acak yang dipilih jatuh pada bit ke-8 sehingga kromosom terbagi menjadi 2, yaitu bit 1-7 dan bit 8-15. Bit 8-15 dari kedua kromosom tersebut ditukar sehingga menghasilkan dua kromosom baru sebagai berikut:
Kromosom A : 1001011 | 01011011 Kromosom B : 1110100 | 01110101 Two-point crossover pada prinsipnya sama dengan single-point crossover. Bedanya, pada two-point crossover, dua buah posisi yang dipilih secara acak, sehingga membagi kromosom menjadi tiga bagian. Tujuan dari two-point crossover adalah untuk menukar bagian yang berada di antara dua posisi acak tersebut (bagian tengah kromosom). Contoh two-point crossover:
Kromosom A : 10010 | 110111 | 0101
Kromosom B : 11101 | 000101 | 1011
16 Pada contoh diatas, posisi acak jatuh pada bit ke-6 dan bit ke-11. Bagian yang ditukar adalah bit 6-11 yang berada di tengah kromosom. Hasil pertukaran menghasilkan kromosom berikut:
Kromosom A : 10010 | 000101 | 0101 Kromosom B : 11101 | 110111 | 1011 Selain dua metode di atas, ada satu metode yang disebut uniform crossover, di mana pertukaran dilakukan dengan cara menukar bit-bit kedua kromosom parent secara acak. b. Mutation (Mutasi) Mutasi adalah perubahan nilai gen (allele) dalam kromosom secara permanen sehingga kromosom tersebut mengalami perubahan bentuk. Mutasi dilakukan dengan cara memilih satu atau beberapa posisi gen dalam kromosom dan kemudian mengganti nilainya. Pada binary encodings, mutasi dilakukan dengan meng-invert nilai gennya, yaitu 0 diganti menjadi 1 dan sebaliknya. Contoh mutasi:
Kromosom A : 100100001010101 Kromosom A* : 100000101001111
Kromosom B : 1.235 2.215 1.525 0.223 5.412 Kromosom B* : 1.235 2.637 1.525 0.223 5.883
17 Dalam kebanyakan aplikasi Genetic Algorithms, dua operator ini tidak dipilih untuk digunakan salah satunya saja, tetapi digunakan secara bersamasama. Keseimbangan yang tepat dalam penggunaan crossover, mutasi, dan seleksi merupakan bagian yang sangat penting dalam Genetic Algorithms. Keseimbangan ini juga sangat tergantung pada pengkodean dan fungsi untuk menentukan fitness cost.
2.3.
Model Rekayasa Piranti Lunak Model rekayasa piranti lunak yang dipakai penulis adalah model sekuensial
linear. Model ini biasa disebut juga model “air terjun” (waterfall). Model ini merupakan sebuah pendekatan kepada perkembangan perangkat lunak yang sistemaik dan sekuensial yang mulai pada tingkat dan kemajuan system pada seluruh analisis, desain, kode, pengujian dan pemeliharaan. Penjelasan tahapan dalam Waterfall Model adalah sebagai berikut : 1. Analisis Kebutuhan Proses pengumpulan kebutuhan diintensifkan dan difokuskan, khususnya pada perangkat lunak. Tujuan dari tahap ini adalah untuk mengetahui kebutuhan piranti lunak, sumber informasi piranti lunak, fungsi-fungsi yang dibutuhkan, kemampuan piranti lunak dan antar muka piranti lunak tersebut. 2. Perancangan Proses perancangan merupakan representasi kebutuhan ke bentuk perangkat lunak yang dapat dinilai kualitasnya sebelum dilakukan pengkodean. Tahap
18 ini meliputi perancangan struktur data, perancangan arsitektur piranti lunak, perancangan rincian prosedur dan perancangan user interface. 3. Pengkodean Tahapan ini mengkodekan hasil perancangan ke bahasa pemrograman. 4. Implementasi dan Pengujian Setelah program aplikasi selesai dikode, program akan diujicobakan dan juga dilakukan pengujian. Pengujian dilakukan secara menyeluruh hingga semua perintah dan fungsi telah diuji sampai output yang dihasilkan oleh program sesuai dengan yang diharapkan. 5. Pemeliharaan Pemeliharaan perangkat lunak dilakukan karena sering terjadinya perubahan dan peningkatan fungsi piranti lunak. Hal ini sesuai permintaan pemakai, maka piranti lunak yang telah selesai dibuat perlu dipelihara agar dapat mengantisipasi permintaan pemakai terhadap fungsi-fungsi baru. Bila terjadi perubahan berarti membalikan tahapan ke tahapan yang lebih awal. Untuk lebih jelasnya, tahapan ini dapat dilihat pada gambar 2.1.
19
ANALISIS
DESAIN
CODING DAN DEVELOPMENT IMPLEMENTASI DAN TESTING PEMELIHARAAN
Gambar 2.1. Model Waterfall
2.4.
Interaksi Manusia dan Komputer Saat ini program yang baik selain dituntut dari segi fungsi, sangatlah
memperhatikan segi interaktif dan penggunaan yang mudah dimengerti (user friendly). Shneiderman (1998, p15) menjelaskan lima kriteria yang harus dipenuhi oleh suatu program yang user friendly yaitu : 1. Waktu belajar yang tidak lama 2. Kecepatan penyajian informasi yang tepat. 3. Tingkat kesalahan pemakaian rendah 4. Penghafalan sesudah melampaui jangka waktu. 5. Kepuasan pribadi. Suatu program yang interaktif dapat dengan mudah dibuat dan dirancang dengan suatu perangkat bantu pengembang sistem antarmuka, seperti Visual Basic, PHP, dan sebagainya. Menurut Shneiderman (1998, p74-75) untuk merancang sistem interaksi
20 manusia dan komputer yang baik, harus memperhatikan delapan aturan utama dibawah ini, yaitu : 1. Strive for consistency (Bertahan untuk konsistensi) 2. Enable frequent user to use shortcuts (Memperbolehkan pengguna sering memakai shortcut) 3. Offer informative feed back (Memberikan umpan balik yang informatif). 4. Design dialogs to yield closure (Pengorganisasian yang baik sehingga pengguna mengetahui kapan awal dan akhir dari suatu aksi). 5. Offer simple error handling (Penanganan kesalahan yang sederhana). 6. Permit easy reversal of actions (Mengizinkan pembalikan aksi (undo dengan mudah). 7. Support internal locus of control (Pemakai menguasai sistem atau inisiator, bukan responden) 8. Reduce short term memorcy load (Mengurangi beban ingatan jangka pendek, dimana manusia hanya dapat mengingat 7 ± 2 satuan informasi sehingga perancangannya harus sederhana).
