Knapsack Problem dan Algoritma Genetika

Knapsack problem adalah permasalah untuk memilih n barang dari N barang yang tersedia dimana n barang tadi akan dimasukan kedalam sebuah kantong. Namun terdapat masalah dimana kekuatan kantong untuk menahan beban terbatas kekuatannya. Sehingga n barang yang terpilih harus memiliki berat maksimum namun masih bisa menahan berat dari n benda yang terpilih tadi.

sumber : vi.wikipidia.org

Untuk menyelesaikan masalah ini diperlukan sebuah metode atau algoritma untuk mencari n barang dengan berat maksimum yang dapat ditempuh tersebut. misalnya kita memiliki 10 barang dimana akan diambil beberapa barang untuk dimasukkan kedalam kantong, kita akan menggunakan algoritma genetika. Individu didifinisikan sebagai daftar barang-barang yang dimasukan kedalam kantong, misalnya diantaranya adalah (1000010000) dan (1110000001) dimana 1 dinyatakan barang masuk kedalam kantong dan 0 tidak dimasukan sehingg untuk individu petama hanya barang 1 dan 6 yang masuk sedangkan untuk individu kedua hanya barang 1,2,3 dan 10 yang akan masuk. masing-masing individu akan dihitung nilai fitnessnya dimana fungsinya menyatakan selisih antara kapasitas maksimum kantong dikurangi berat benda-benda yang akan dimasukan. Fungsi dinyatakan maksimum jika mendekati 0 dan tidak negatif. Semua individu akan di crossoverkan dan dimutasikan sehingga misalnya sampai pada generasi ke 10 maka didapat sebuah solusi optimal dengan individu terpilih (1111000011) dimana hanya barang 1,2,3,4,9 dan 10 yang hanya dimasukan.

Algoritma Genetika (genetic algorithm) dan TSP problem

Algoritma genetik adalah suatu metode yang baru ditemukan pada abad ke 20. Algoritma genetika ditemukan oleh john holland prinsip dari algoritma genetika terinspirasi dari proses seleksi alam seperti teori yang di kemukakan oleh Darwin. Dalam algoritma genetika juga dapat disebut sebagai metode pencarian yang pararel. konsep dari algoritma genetika adalah penyeleksi individu - individu dimana tiap-tiap individu mewakili sebuah solusi dari permasalahan yang diberikan. Dalam algoritma genetika terdapat dua operator utama yaitu, crossover dan  mutasi. 

Salah satu permasalahan yang dapat diselesaikan oleh algoritma genetika adalah masalah travelling salesmen problem (TSP problem). Inti dari masalah TSP ini adalah untuk menemukan rute tercepat untuk menelusuri beberapa kota dimana satu kota hanya dikunjungi satu kali.

Gambar diatas digambarkan ada 4 kota yang saling terhubung, maka akan dicari susunan kota yang akan dikunjungi dengan harapan dapat meminimumkan jarak yang ditempuh.

Pada gambar 2 akan dicari jarak terpendek dari 8 kota. kita akan generate individu-individu yang akan jadi kandidat solusi dimana tiap2 kormosom berisi gen dengan susunan kota yang akan dikunjungi, misal didifinisikan funsi fetness adalah jumlah jarak yang ditempuh dari kunjungan 8 kota. salah satu conoh kromosom adalah sebaai berikut (1,2,4,3,5,6,8,7). kita akan melakukan crossover dan mutasi namun kalau melakukan crossover biasa kita akan kesulitan karena dapat menghilangkan kunjungan kesalah satu kota dan ada kota yang di kunjungi lebih dari sekali. Solusinya kita akan melakukan order crossover. langkahnya sebagai berikut.

parent 1 : (1 2 | 3 5 4 7| 6 8)

parent 2 : (2 3 | 1 4 5 6 |7 8)

kemudian O1 nya : (- - | 3547|--)

dan O2 nya (--|1456|--)

kemudian susunan q nya 78231456 kemudian eliminasi 3 5 4 7 sehingga tersisa 8216 sehingga :

O1 : (16354782 )

dengan cara serupa untuk O2 didapat : ( 37145682)  

sehingga dengan melakukan crossover dan mutasi selama beberapa generasi akan dihasilkan solusi terbaik misalnya setelah generasi ke tujuh didapat susunan 61253478 misalnya dengan jarak minimum 20 km. 

Logika FUZZY dan Sistem Inferensi Fuzzy

Logika fuzzy sering berkaitan dengan cara kerja himpunan fuzzy. Dalam logika fuzzy, sebuah elemen dalam suatu himpunan dinyatakan dengan derajat keanggotaannya. Tidak seperti himpunan crisp, elemen dari suatu himpunan dinyatakan dengan iya atau tidak. Misalnya seekor bebek adalah angota himpunan unggas atau tidak.

Dalam logika fuzzy keanggotaan suatu elemen dalam suatu himpunan sering dinyatakan dengan derajat kebebasan. misalnya untuk suhu 39 derajat celcius, dia masuk himpunan hangat dan bisa juga masuk dalam himpunan panas, tetapi dia hanya ikut pada himpunan panas 0.2 dan pada himpunan hangat 0.8.

untuk mencari nilai/derajat keanggotaan perlu sebuah funsi keanggotaan. Fungsi keanggotan dalam logika fuzzy ada banyak. Yang sering digunakan misalnya adalah fungsi segitiga, trapesium atau gauss. untuk mendapatkan nilai/derajat keanggotaan cukup masukan nilai x ke dalam fungsi yang bersangkutan.

Sistem inferensi fuzzy adalah sekumpulan dari aturan - atauran IF - THAN yang digunakan untuk mencari nilai sesuatu. Contoh dari aturan fuzzy misalnya adalah sebagai berikut : misalkan x adalah suhu, y adalah angin, dan z adalah kelembapan udara. maka aturan fuzzy nya adalah  IF x is panas AND y is sedang THAN  z is sedang. maksudnya adalah jila suhu panas dan angin bertiup sedang maka kelembapan udara sedang.

Sistem inferensi fuzzy banyak digunakan untuk mengakuisisi dari pengetahuan seorang pakar akan sesuatu. misalnya seperti contoh diatas, kita berusaha untuk mengakuisisi pengetahuan seorang ahli cuaca untuk memprediksi kelembapan udara.

Database terdistribusi (Distributed DBMS)

Dalam dunia data base dikenal database terdistribusi atau distributed DBMS. Maksud dari distributed DBMS berarti data base bisa tersebar dibeberapa node. Node disini bisa berarti local server yang menyimpan sebagian dari database. Kelebihan suatu distributed DBMS adalah bahwa tidak seperti centralized DBMS yang apabila diserang maka semua node atau semua yang memerlukan data base tidak bisa diakses siapa pun.

Dalam distributed DBMS data-data disebar ke beberapa node. Misalnya sebuah perusahaan yang memakai distributed DBMS maka kantor pusatnya hanya aka menyimpan database untuk kantor pusat dan kantor cabang (boleh disebut node) juga hanya menyimpan database yang dibutuhkan oleh lokal kantor cabang tersebut.

Meskipun dalam distributed DBMS database disebar dibeberapa tempat, tetapi dalam konteks logikanya tetap menjadi sebuah kesatuan database. Misalnya distributed database yang tabel-tabelnya tersebar dibeberapa node, maka jika sebuah node atau kantor cabang mencoba mengakses database dari node lainya(kantor cabang lainya) maka dapat melakukan permintaan atau request seperti pada centralized DBMS. 

Satu yang pasti harus menjadi perhatian adalah dibutuhkannya jaringan koneksi trasfer data untuk distributed DBMS. jadi satu kelemahan dari distributed DBMS adalah harus membangun infrastruktur jaringan yang memadai.