BAB 2 LANDASAN TEORI. Pada penelitian ini kami menggunakan teori-teori Computer Vision yang

BAB 2 LANDASAN TEORI

Pada penelitian ini kami menggunakan teori-teori Computer Vision yang diperbaiki dengan teori Fuzzy Evolitionary Algorithm yang merupakan gabungan dari Fuzzy Logic dan Genetic Algorithm. 2.1.

Intelegensia Semu Istilah kecerdasan buatan sebenarnya berasal dari bahasa Inggris: “Artificial Intelligence”. Jika diartikan tiap kata, artificial artinya buatan, sedangkan intelligence adalah kata sifat yang berarti cerdas. Jadi artificial intelligence maksudnya adalah sesuatu buatan atau suatu tiruan yang cerdas. Cerdas di sini kemungkinan maksudnya adalah kepandaian atau ketajaman dalam berpikir, seperti halnya otak manusia dalam menyelesaikan suatu masalah. Kecerdasan

buatan

(Artificial

Intelligence)

didefinisikan

sebagai

kecerdasan yang ditunjukkan oleh suatu entitas buatan. Sistem seperti ini umumnya dianggap sebagai computer. Kecerdasan diciptakan dan dimasukkan kedalam suatu mesin (komputer) agar dapat melakukan pekerjaan seperti yang dapat dilakukan manusia. Kecerdasan buatan ini bukan hanya ingin mengerti apa itu sistem kecerdasan, tapi juga mengkonstruksinya. Tidak ada definisi yang memuaskan untuk kecerdasan. Definisi untuk kecerdasan yang berlaku saat ini :

10

11 

Kemampuan untuk memperoleh pengetahuan dan menggunakannya.



A yang diukur oleh sebuah ‘Test Kecerdasan’.

2.1.1 Latar Belakang Intelegensia Semu Pada awal diciptakannya, computer hanya difungsikan sebagai alat komputasi belaka. Seiring dengan perkembangan waktu, penggunaan computer semakin mendominasi kehidupan manusia sehingga computer tidak hanya digunakan sebagai alat hitung saja, tetapi lebih dari itu yaitu menggantikan beberapa pekerjaan yang biasanya dilakukan oleh manusia. Manusia menjadi pintar dalam menyelesaikan segala permasalahan yang dihadapi karena manusia mempunyai pengetahuan dan pengalaman. Pengetahuan didapatkan dari proses belajar, pengalaman didapatkan karena perjalanan waktu dan kehidupan yang dialami oleh manusia. Semakin banyak bekal pengetahuan dan pengalaman yang dimiliki oleh seseorang, diharapkan orang tersebut lebih mampu menyelesaikan masalah yang dihadapinya. Namun bekal pengetahuan saja tidak cukup, manusia juga diberikan akal untuk melakukan penalaran, mengambil kesimpulan berdasarkan pengetahuan dan pengalaman yang dimilikinya. Tanpa memiliki kemampuan penalaran yang baik, tidak ada artinya manusia itu memiliki pengetahuan dan pengalaman sebanyak apapun. Demikian juga sebaliknya, walaupun seorang manusia memiliki kemampuan penalaran yang baik, namun tanpa bekal pengetahuan dan pengalaman yang memadai, manusia juga tidak dapat menyelesaikan masalahnya dengan baik. Agar komputer bisa bertindak seperti dan sebaik manusia, maka komputer juga harus diberi bekal pengetahuan dan diberikan kemampuan untuk

12 menalar. Untuk itu, artificial intelligence akan mencoba untuk memberikan beberapa metode untuk membekali computer dengan kedua komponen tersebut agar computer bisa menjadi mesin yang cerdas. 2.1.2 Definisi Intelegensia Semu Menyatakan computer itu cerdas tentu tergantung sudut pandang dari orang yang memanfaatkan computer tersebut. Karena itulah sangat sulit untuk mendefinisikan dengan pasti apa yang dimaksud dengan kecerdasan buatan itu. Menurut John McCarthy, 1965, Artificial Intelligence adalah untuk mengetahui dan memodelkan proses – proses berpikir manusia dan mendesai mesin agar dapat menirukan perilaku manusia. Menurut Russell dan Norvig (2003, p5) definisi tentang kecerdasan buatan dikembangkan berdasarkan empat kelompok kategori, yaitu : 

Sistem yang berpikir selayaknya manusia berfikir (thinking humanly).



Sistem yang bertindak selayaknya manusia bertindak (acting humanly).



Sistem yang berpikir secara rasional (thinking rationally).



Sistem yang bertindak secara rasional (actingt rationally).

Dari keempat perspektif diatas, pengertian kecerdasan buatan dapat dipandang dari berbagai sudut pandang, antara lain: 

Sudut pandang kecerdasan Kecerdasan buatan akan membuat mesin menjadi cerdas, yaitu mampu berbuat seperti apa yang dilakukan oleh manusia.



Sudut pandang penelitian

13 Kecerdasan buatan adalah suatu studi bagaimana membuat mesin atau computer dapat melakukan sesuatu sebaik yang dikerjakan oleh manusia. Ada beberapa bidang (domain) yang sering dibahas oleh para peneliti meliputi: a. Mundane Task 

Persepsi (vision & speech)



Bahasa alami (understanding, generation & translation)



Pemikiran yang bersifat commonsense



Robot kontrol

b. Formal Task 

Games / permainan



Matematika (geometri, logika, kalkulus integral, pembuktian)

c. Expert Task 

Analisis finansial



Analisis medikal



Analisis ilmu pengetahuan



Rekayasa

(desain,

pencarian

kegagalan,

perencanaan

manufaktur)  Sudut pandang bisnis Kecerdasan buatan adalah sekumpulan peralatan (tools) yang sangat powerfull dan metodelogis dalam menyelesaikan masalah bisnis. 

Sudut pandang pemrograman

14 Kecerdasan buatan meliputi studi tentang pemrograman simbolik, penyelesaian masalah (problem solving) dan pencarian (searching). Untuk melakukan aplikasi kecerdasan buatan ada dua bagian utama yang sangat dibutuhkan, yaitu : 

Basis Pengetahuan (Knowledge Base) Berisi fakta – fakta, teori, pemikiran dan hubungan antara satu dengan yang lainnya.



Motor Inferensi (Inference Engine) Yaitu kemampuan menarik kesimpulan berdasarkan pengalaman.

2.1.3 Sejarah Intelegensia semu Intelegensia semu merupakan inovasi baru di bidang ilmu pengetahuan. Mulai ada sejak muncul computer modern, yakni pada 1940 dan 1950. Dalam literatur, orang pertama yang dianggap sebagai pionir dalam mengembangkan mesin cerdas (intelligence machine) adalah Alan Turing, seorang matematikawan asal Inggris yang memulai karir saintifiknya di awal tahun 1930-an. Di tahun 1937 ia menulis paper tentang konsep mesin universal (universal machine). Kemudian, selama perang dunia ke-2 ia dikenal sebagai pemain kunci dalam penciptaan Enigma, sebuah mesin encoding milik militer Jerman. Setelah perang, Turing membuat automatic computing engine. Ia dikenal juga sebagai pencipta pertama program komputer untuk bermain catur, yang kemudian program ini dikembangkan dan dimainkan di komputer milik Manchester University. Karyakaryanya ini, yang kemudian dikenal sebagai Turing Machine, dewasa ini masih dapat ditemukan aplikasi-aplikasinya.

15 Beliau melakukan percobaan Turing (Turing Test) yaitu sebuah komputer melalui terminalnya ditempatkan pada jarak jauh. Di ujung yang satu ada terminal dengan software AI dan diujung lain ada sebuah terminal dengan seorang operator. Operator itu tidak mengetahui kalau di ujung terminal lain dipasang software AI. Mereka berkomunikasi dimana terminal di ujung memberikan respon terhadap serangkaian pertanyaan yang diajukan oleh operator. Dan sang operator itu mengira bahwa ia sedang berkomunikasi dengan operator lainnya yang berada pada terminal lain. Turing beranggapan bahwa jika mesin dapat membuat seseorang percaya bahwa dirinya mampu berkomunikasi dengan orang lain, maka dapat dikatakan bahwa mesin tersebut cerdas (seperti layaknya manusia). Beberapa tulisannya yang berkaitan dengan prediksi perkembangan komputer di masa datang akhirnya juga ada yang terbukti. Misalnya tentang ramalannya bahwa di tahun 2000-an komputer akan mampu melakukan percakapan dengan manusia. Meski tidak ditemukan dalam paper-papernya tentang istilah resmi artificial intelligence, namun para peneliti di bidang ini sepakat untuk menobatkan Turing sebagai orang pertama yang mengembangkan kecerdasan buatan . Secara ilmu pengetahuan, istilah kecerdasan buatan untuk selanjutnya disebut sebagai AI (artificial intelligence), pertama kali diperkenalkan oleh Warren McCulloch, seorang filsuf dan ahli perobatan dari Columbia University, dan Walter Pitts, seorang matematikawan muda pada tahun 1943, (Negnevitsky, 2004). Mereka mengajukan suatu teori tentang jaringan saraf tiruan (artificial neural network) untuk selanjutnya disebut sebagai ANN, bahwa setiap neuron

16 dapat dipostulasikan dalam dua keadaan biner, yaitu ON dan OFF. Mereka mencoba menstimulasi model neuron ini secara teori dan eksperimen di laboratorium. Dari percobaan, telah didemonstrasikan bahwa model jaringan saraf yang mereka ajukan mempunyai kemiripan dengan mesin Turing, dan setiap fungsi perhitungan dapat dapat diselesaikan melalui jaringan neuron yang mereka modelkan. Pentingnya kecerdasan buatan menjadi nyata bagi negara-negara yang berperan sejak tahun 1970. Para pemimpin negara yang mengakui potensialnya kecerdasan buatan mengharap mendapat persetujuan jangka panjang untuk sumber-sumber yang memerlukan dana intensif. Awalnya, kecerdasan buatan hanya ada di universitas-universitas dan laboratorium penelitian, dan hanya sedikit produk yang dihasilkan dan dikembangkan. Menjelang akhir 1970-an dan 1980-an, mulai dikembangkan secara penuh dan hasilnya berangsur-angsur dipublikasikan di khalayak umum. 2.1.4 Tujuan Intelegensia Semu Adapun tujuan Intelegensia Semu adalah sebagai berikut: 

Untuk mengembangkan metode dan sistem untuk menyelesaikan masalah,masalah intelektual

yang

manusia,

biasa misalnya

diselesaikan pengolahan

melalui

aktifivitas

citra,perencanaan,

peramalan dan lain-lain, meningkatkan kinerja sistem informasi yang berbasis komputer. 

Untuk meningkatkan pengertian/pemahaman kita pada bagaimana otak manusia bekerja

17 2.1.5 Beda Intelegensia Semu dan Kecerdasan Alami Kelebihan kecerdasan buatan : 

Lebih bersifat permanent Kecerdasan alami bisa berubah karena sifat manusia pelupa. Kecerdasan buatan tidak berubah selama system computer dan program tidak mengubahnya.



Lebih mudah diduplikasi dan disebarkan Mentransfer pengetahuan manusia dari 1 orang ke orang lain membutuhkan proses yang sangat lama dan keahlian tidak akan pernah dapat diduplikasi dengan lengkap. Jadi jika pengetahuan terletak pada suatu system computer, pengetahuan tersebut dapat disalin dari computer dan dapat dengan mudah dipindahkan ke computer yang lain



Lebih murah Menyediakan layanan computer akan lebih mudah dan murah dibandingkan mendatangkan seseorang untuk mengerjakan sejumlah pekerjaan dalam jangka waktu yang sangat lama.



Bersifat konsisten karena kecerdasan buatan adalah bagian dari teknologi computer sedangkan kecerdasan alami senantiasa berubah – ubah.



Dapat didokumentasi

18 Keputusan yang dibuat computer dapat didokumentasi dengan mudah dengan cara melacak setiap aktivitas dari system tersebut. Kecerdasan alami sangat sulit direproduksi. 

Lebih cepat



Lebih baik

Kelebihan kecerdasan alami : 

Kreatif

:

manusia

memiliki

kemampuan

untuk

menambah

pengetahuan, sedangkan pada kecerdasan buatan untuk menambah pengetahuan harus dilakukan melalui system yang dibangun 

Memungkinkan orang untuk menggunakan pengalaman secara langsung. Sedangkan pada kecerdasan buatan harus bekerja dengan input – input simbolik.



Pemikiran manusia dapat digunakan secara luas, sedangkan kecerdasan buatan sangat terbatas.

2.2

Citra Digital Digital image adalah representasi dari gambar dua dimensi yang merupakan sebuah set terbatas dari nilai-nilai digital , seperti pixel atau elemen gambar. (Anonymous, 2007, Wikipedia).

2.3

Piksel Pixel adalah elemen terkecil pada sebuah citra digital. Pixel ini sendiri memegang nilainya masing-masing seperti warna atau tingkat brightness (cahaya). Pixel-pixel pada digital image ditempatkan pada kolom dan baris yang telah ditetapkan, jadi digital image itu sendiri adalah kumpulan dari pixel-pixel

19 yang tersusun sedemikian rupa,

memiliki bentuk dan warna yang beragam

sehingga dapat terlihat sebagai satu kesatuan gambar seperti yang selama ini kita lihat. Banyaknya pixel menentukan kualitas dan besarnya ukuran file dari suatu citra gambar. Semakin banyak jumlah pixel yang dipakai, semakin baik kualitas gambar dan semakin besar ukuran file dari gambar tersebut. Keanekaragaman warna dari pixel tergantung dari bit depth yang dipakai. Setiap pixel memiliki tiga atau empat variabilitas secara khas, seperti red, green dan blue atau cyan, magenta, yellow dan black. Hubungan antara tiap-tiap pixel (Gonzalez dan Woods, 1993, p40):  Neighbours of a Pixel Neighbours of a pixel atau bisa disebut juga tetangga dari sebuah pixel dengan pixel p terletak dalam koordinat p(x,y), memiliki pixel-pixel tetangga sebagai berikut: (x-1,y+1)

(x,y+1)

(x+1,y+1)

(x-1,y)

(x,y)

(x+1,y)

(x-1,y-1)

(x,y-1)

(x+1,y-1)

Tabel 2.1. neighbours dari pixel 

Connectivity Konektivitas diantara pixel adalah sebuah konsep penting yang digunakan didalam membangun batas dari objek-objek dan komponenkomponen dari area didalam citra. Konektivitas pixel yang satu dengan

20 pixel lainnya di tentukan oleh letak pixel itu sendiri dan toleransi skala warna yang ada pada citra. 2.4

Soft Computing Dalam beberapa dekade terakhir, perkembangan sistem proses informasi di dalam model kotak hitam, telah membuat prospek evolusi ilmiah menuju kepada perkembangan sistem kecerdasan, dengan memungkinkan dibuat modelmodel dari fenomena alam secara otomatis oleh mereka sendiri, dan pada akhirnya perumusan mereka merupakan hukum-hukum fisik di dalam batas hubungan-hubungan yang abstrak. Sistem kecerdasan pada dasarnya merupakan suatu sistem yang berusaha meniru cara berfikir manusia. Peniruan cara berfikir tersebut terdiri atas dua bagian yaitu peniruan proses berfikir dan peniruan proses komputasi.

Pengembangan

suatu

sistem

yang

memiliki

kecerdasan

komputasional dikenal dengan istilah soft computing. Soft computing berusaha untuk mengintegrasikan beberapa paradigma model perhitungan meliputi artificial neural network, fuzzy logic dan genetic algorithms. 2.4.1 Pengertian Soft Computing adalah kumpulan teknik – teknik perhitungan dalam ilmu komputer, inteligensia semu, machine learning dan beberapa disiplin ilmu teknik lainnya, yang berusaha untuk mempelajari, memodelkan, dan menganalisa fenomena yang sangat rumit : untuk metoda yang lebih konvensional yang tidak memberikan biaya rendah, analitis dan solusi lengkap. Soft Computing adalah segolongan metoda yang mampu mengolah data dengan baik walaupun didalamnya terdapat ketidakpastian, ketidakakuratan maupun kebenaran parsial (Prof. Lotfi A Zadeh, 1992).

21 2.4.2 Sejarah Istilah soft computing dicetus pertama kali pada tahun 1990 sehubungan dengan ide untuk mendirikan BISC (Berkeley Initiative in Soft Computer) oleh Prof. L.A.Zadeh dari Berkeley University. Soft computing, berbeda dengan conventional (hard) computing, memungkinkan toleransi terhadap input, proses dan output yang bersifat tidak akurat(imprecision), tidak pasti (uncertainty) dan setengah benar (partial truth). 2.4.3 Soft Computing sebagai Solusi Metoda soft computing menempati posisi yang menarik dalam perkembangan metoda komputasi dan pemecahan masalah pada saat ini. Hal ini karena ditawarkan solusi yang menarik dan kemudahan implementasi dari metoda ini untuk memecahkan masalah-masalah yang tadinya sangat sulit dipecahkan dengan komputer dengan menggunakan metoda komputasi konvensional. Dengan adanya toleransi terhadap imprecision, uncertainty dan partial truth, diharapkan akan dapat menciptakan suatu system yang cerdas (intelligent systems), handal (robustness), mudah diproses atau dijalankan (tractability) dan membutuhkan biaya yang lebih murah (low solution cost). Karakteristik ini menempatkan soft computing sebagai salah satu solusi yang dapat digunakan untuk memecahkan berbagai masalah yang terdapat pada domain dunia nyata (real-world domain). Disekeliling kita terdapat banyak contoh dari berbagai masalah yang berkarakteristik demikian, antara lain :

22 -

bagaimana kita mampu membaca berbagai macam corak tulisan tangan, atau bahkan pada tulisan itu ada sebagian yang terhapus

-

bagaimana membuat AC agar mengatur sendiri suhunya secara otomatis, sehingga udara didalam ruangan terasa nyaman

-

bagaimana mengenali sesorang, padahal tidak seluruh wajahnya dapat terlihat Solusi berbagai masalah yang terdapat pada domain ini tidak mudah

dihitung dengan berbagai model analitik yang ada. Diperlukan solusi yang seolah memiliki kecerdasan sehingga mampu menyelesaikan masalah – masalah yang sedemikian kompleks itu. Disinilah soft computing menjadi suatu solusi atas permasalahan tersebut. Metoda soft computing diinspirasikan oleh cara manusia memecahkan suatu masalah. Namun pendekatan soft computing ini berbeda dengan metoda Artificial Intelligence yang menggunakan pendekatan simbolik. Pada pendekatan simbolik yang bertumpu pada Physical Symbol System (PSS), jawaban suatu masalah harus berdasarkan dari keadaan yang konsisten dari data yang ada (Newel and Simon, 1976) karena Physical Symbol System tak dapat memberikan solusi bila keadaan chaos. Dengan kata lain knowledge base yang menjadi basis dari pencarian solusi harus bersifat koheren, konsisten, dan reasonable (Delgrande and Mylopulos, 1986). Pada sistem konvensional, jawaban akan diberikan apabila seluruh syarat dari permasalahan terpenuhi. Ini menyebabkan sebagian besar dari pendekatan simbolik akan berakhir pada sistem yang bersifat semi-decidable. Sistem tidak akan memberikan jawaban bila seluruh kondisi yang diketahui tidak dipenuhi.

23 Bila keadaan tidak terpenuhi, atau jawaban tidak tertemukan sistem ini akan memberikan jawaban yang bersifat negatif, sifat inilah yang dikenal dengan sifat semi-decidable dari sistem ini. 2.4.4 Pencarian Solusi dengan Metoda Soft Computing Metoda soft computing, tidak menggunakan satu algoritma yang pasti untuk memecahkan suatu masalah. Suatu teknik hanyalah mendeskripsikan interaksi antar sub sistem, bukanlah langkah pemecahan permasalahan secara detail. Sehingga dapat dilukiskan pemecahan menggunakan diagram sebagai berikut:

Gambar 2.1. Pemecahan masalah dengan Soft Computing Pada problem space, untuk problem yang ingin dipecahkan, telah diketahui contoh penyelesaian, yang biasanya dilakukan oleh human. Informasi yang bersifat pemetaan dari masalah ke solusi inilah yang akan diberikan kepada perangkat soft computing. Dengan memberikan sistem secara terus menerus melalui proses pelatihan maupun optimasi, solusi untuk seluruh problem space dapat ditemukan. Jadi dalam perancangan sistem, tidak perhan didefinisikan

24 bagaimana solusi tersebut dicapai, yang ada hanyalah contoh-contoh, ataupun aturan-aturan kecil dari sistem tersebut. 2.4.5 Metoda Soft Computing Mengacu pada definisi yang diberikan oleh Zadeh, metoda – metoda dalam soft computing dapat dikategorikan ke dalam tiga kategori besar: o

Fuzzy Logic

o

Artificial Neural Network

o

Probabilistic Reasoning

Kemudian ditambah dengan : o Genetic Algorithm o Evolutionary Computation o Belief Network o Chaos Theory Metoda – metoda ini sebenarnya bukanlah sesuatu yang baru yang diadakan setelah konsep soft computing yang dirumuskan. Yang terjadi justru sebaliknya. Metoda – metoda Fuzzy Logic, Artificial Neural Network, Probabilistic Reasoning maupun Genetic Algorithm telah ada lebih dahulu. Fuzzy Logic telah berkembang sejak tahun 1965. Konsep – konsep dasar Neural Network telah digali sejak tahun 1940an. Demikian halnya dengan Probabilistic Reasoning dan Genetic Algorithm yang bukan merupakan hal baru. Oleh karena itu, Zadeh menyebut soft computing sebagai reinkarnasi dari metoda – metoda diatas. Walaupun semua konsep dan teori diatas adalah untuk memproses system dan menyelesaikan masalah yang bersifat uncertainty, keberadaan semua konsep

25 dan teori tersebut seharusnya tidak dilihat sebagai suatu persaingan (competitive) tetapi lebih dilihat sebagai saling melengkapi (complementary). Tidak ada satu konsep atau teoripun yang bersifat perfect, powerful, dan general untuk menyelesaikan semua masalah dalam real-world application, sehingga penggunaan suatu konsep atau teori bergantung dan disesuaikan dengan jenis dan karakteristik dari permasalahan dan aplikasinya. Bahkan, untuk dapat membentuk suatu complicated system yang cerdas (intelligent system), harus diperlukan suatu hybrid system melalui penggabungan beberapa konsep dan teori dari soft computing . Lebih lanjut lagi, dalam konsep soft computing, metoda – metoda ini ibarat pilar , slaing mendukung dan bekerjasama dalam memecahkan suatu permasalahan. Keunggulan yang diperoleh dari kerjasama metoda – metoda itu lebih ditekankan daripada keunggulan individual salah satu daripadanya. Kekurangan satu metoda akan ditutup dengan kelebihan metoda lainnya. Keunggulan satu metoda disumbangkan, sehingga segi – segi positif dari metode yang ada tersebut dapat dimanfaatkan secara optimal (). 2.4.6 Tujuan Soft Computing Tujuan soft computing adalah terbentuknya High Machine Intelligence Quotient (HMIQ), suatu system yang mampu mengolah informasi seperti cara berpikir manusia, mempunyai kemampuan untuk menyelesaikan permasalahan non-linier dan tidak ada model matematisnya (tractability), serta dapat diimplementasikan dengan biaya rendah. Adapun tujuan metode soft computing adalah :

26 a.

Non-linearitas

dan

kompleksitas

problema.

Kemampuan

menyelesaikan problematika yang sulit dan tidak bisa diselesaikan dengan metoda biasa b.

Kemampuan memanipulir parameter yang tidak pasti ( sesuatu yang tidak bisa diukur secara pasti, misalnya mengukur kadar cinta )

c.

Kemampuan men-generalisir solusi

d.

Kemampuan klasifikasi dan kuantifikasi data, misalnya dengan lebih mudahnya pengerjaan kasus regresi linier dengan teknologi ini daripada dengan fuzzy logic.

e.

Kemampuan mengatasi keterbatasan data, misalnya pada dunia statistic.

2.5

Image Processing Image Processing atau pengolahan citra adalah bentuk dari pemrosesan informasi yang mana menerima input berupa citra atau gambar seperti foto ,frame atau video.Hasil output dari image processing tidaklah harus berupa image, tetapi dapat berupa bagian dari image tersebut. Pengolahan citra ini juga bertujuan untuk memperbaiki citra awal, yang mungkin memiliki beberapa kerusakan yang terjadi sewaktu gambar diambil dengan menggunakan kamera atau scanner. Tetapi tujuan dari pengolahan citra ini tidaklah hanya untuk memperbaiki citra-citra yang rusak, tetapi untuk mengoptimalkan nilai dari sebuah citra.

2.5.1 Grayscale Greyscale atau Grayscale adalah sebuah teknik yang digunakan dalam pengolahan citra untuk menghasilkan sebuah citra yang memiliki nilai dari putih

27 yang memiliki intensitas paling besar sampai hitam yang memiliki intensitas paling rendah seperti yang terlihat pada gambar 2.2 .

Gambar 2.2 contoh skala yang digunakkan pada greyscale Greyscale sering sekali dipergunakan untuk menghitung intensitas cahaya pada sebuah gambar berwarna. Greyscale memiliki 256 intensitas pada gambar 8-bit yang dimulai dari nol(putih) sampai 255(hitam).Berikut kami tampilkan sebuah contoh gambar berwarna dengan gambar greyscale-nya.

Gambar 2.3 contoh gambar berwarna dan greyscale 2.5.2 Histogram Salah satu cara untuk memperbaiki suatu citra digital adalah dengan mengatur level dari brightness dan contrast-nya. Pertama-tama, kami akan menggambarkan variasi-sebuah brightness pada suatu citra dengan menggunakan histogram citra tersebut dan bagaimana suatu citra dapat dimanipulasi dengan merubah histogram citra tersebut. Histogram akan menempatkan beberapa piksel dengan brightness level mereka yang sesuai. Untuk piksel dengan ukuran level brightness sebesar 8-bit maka

brightness akan memiliki grey level yang berkisar antara nol(hitam)

sampai 255(putih). Sehingga histogram yang memiliki nilai brightness yang

28 lebih kecil akan terlihat lebih gelap dibandingkan dengan yang memiliki nilai lebih besar. Gambar

2.4

menunjukkan

gambar

sebuah

ban

mobil

dengan

histogramnya. Histogram pada gambar 2.4 menunjukkan bahwa tidak semua grey level yang ada dalam histogram terpakai. Dapat kita lihat bahwa histogram yang memiliki grey level dibawah 120 memiliki tingkat kegelapan yang lebih gelap, dimana warna gelap tersebut dimiliki oleh ban mobil dan bagian bawah mobil, serta bayangan mobil yang memiliki warna cenderung hitam.Disini juga terlihat bahwa apabila suatu gambar memiliki warna yang cenderung gelap maka secara

keseluruhan

histogram

akan

berkonsentrasi

kearah

kiri(hitam).Bandingkanlah gambar 2.5 tersebut dengan gambar 2.5 yang mana gambar tersebut adalah gambar yang sama, tetapi telah dinaikkan nilai brightness-nya. Sekarang histogram cenderung merata dan agak sedikit terkonsentrasi ke arah kanan(putih).

Gambar 2.4. sebuah ban mobil dan histogramnya

29

Gambar 2.5. ban mobil dan histogramnya Disini kita dapat melihat bahwa kita belum memakai seluruh dari grey level yang tersedia. Kita dapat menarik histogram citra tersebut sehingga semua grey level yang tersedia sepenuhnya terpakai, dan teknik itu akan menghasilkan citra yang lebih jelas. Histogram ini juga dapat memperlihatkan kejanggalan bila didalam citra tersebut terdapat noise apabila histogram yang ideal telah kita ketahui. Sehingga kami dapat menghilangkan noise tersebut. Proses ini tidak hanya semata-mata kami lakukan untuk mendapatkan citra yang lebih baik, tetapi juga untuk lebih memudahkan

tugas-tugas

kami dalam teknik-teknik pemprosesan citra

selanjutnya. 2.5.3 Histogram normalisasi Seperti yang sudah dibahas diatas bahwa pada histogram terdapat jarak yang berkisar antara nol(hitam) sampai 255(putih) dimana dari seluruh grey level yang tersedia tidak semuanya terpakai dalam suatu histogram. Cara yang paling populer untuk menarik kisaran jarak intensitas suatu histogram adalah dengan cara histogram normalisasi. Dengan cara inilah histogram yang asli ditarik dan digeser untuk memenuhi seluruh dari 256 level yang tersedia(0-255).

30 Histogram dari citra awal adalah O diawali dari Omin sampai Omax level brightness, kita dapat menaikkan skala citra sehingga piksel pada gambar yang baru N terdapat pada level output minimum Nmin sampai level maksimum Nmax, sehingga Nx,y = (Nmax - Nmin / Omax - Omin )

*

(Ox,y - Omin ) + Nmin

V

(Mark Nixon & Alberto Aguado)

2.5.4 Histogram equalisation Histogram equalisation adalah suatu proses non-linear yang bertujuan untuk memberikan nilai pencahayaan citra yang sesuai dengan analisis visual manusia. Histogram equalisation bertujuan untuk merubah citra, sehingga gambar yang dihasilkan memiliki histogram yang lebih merata, dimana bisa membuat semua level brightness suatu histogram dapat terpakai. Untuk jarak dari suatu brightness level M, histogram menempatkan point untuk setiap levelnya dengan level. Dan untuk setiap input(citra awal) dan setiap output(citra baru), angka dari poin-poin per level dinotasikan sebagai O(l) dan N(l) (untuk 0 < l < M). Untuk image dengan betuk persegi(seperti pixel), terdapat N2 poin pada input dan output, maka jumlah poin per-levelnya sama dengan

Untuk mendapatkan image dengan histogram yang merata maka kita harus mengkumulatifkan level awal p untuk di transformasikan agar dapat memenuhi level akhir q pada histogram yang baru.Sehingga rumusnya menjadi:

31

Karena output dari histogram diharapkan merata, maka kumulatif histogram dengan level p haruslah merupakan rata-rata dari seluruh jumlah fraksi yang ada. Maka jumlah dari poin per level pada gambar baru merupakan rasio dari jumlah poin dengan jarak dari level gambar baru:

Sehingga histogram kumulatif dari gambar baru adalah :

Dengan menggabungkan rumus ini dengan rumus persamaan diatas, maka didapatkan :

Rumus ini dapat memetakan output piksel pada level q, dari input piksel pada level p dengan cara:

Dengan rumus ini kita dapat membuat suatu fungsi yang dapat menyediakan histogram dari gambar baru yang memiliki level merata.Fungsi ini dapat

kita

tentukan

dengan

cara

menggunakan

rumus

diatas

dan

menggunakannya sebagai fungsi persamaan (E) dari level (q) dan memiliki gambar (O), sehingga didapat:

32

Maka gambar yang baru memiliki rumus :

Dengan cara ini kita dapat mendapatkan gambar dengan kualitas yang jauh lebih baik dibandingkan dengan gambar asalnya. Performa dari cara ini sungguh sangat meyakinkan sejak cara ini dapat memetakan gambar dengan baik sehingga sesuai dengan visualisasi mata manusia. 2.5.5

Thresholding Thresholding adalah suatu proses yang digunakan untuk menghasilkan citra biner yaitu citra dengan hanya dua warna, yaitu: hitam dan putih. Operator ini memilih piksel yang memiliki nilai tertentu, atau lingkup tertentu. Proses ini dapat dilakukan apabila kita telah mengetahui brightness level(atau contrast) dari gambar tersebut. Bentuk teknik Thresholding ada 2 macam, yaitu: Uniform Thresholding dan Adaptive Thresholding. Didalam uniform thresholding metode yang digunakan adalah dengan menentukan suatu batas level, yang nantinya akan dipergunakan untuk menentukan warna piksel. Piksel yang levelnya lebih dari threshold level akan dirubah menjadi putih, dan sebaliknya piksel yang levelnya ada di bawah dari level threshold akan dirubah menjadi hitam. Seperti yang kami tampilkan pada gambar 2.6(a) merupakan gambar original yang kami dapat dari meja kerja matlab dan gambar 2.6(b) adalah hasil thresholding dari gambar 2.6(a).

33

Gambar2.6(a) dan gambar 2.6(b) Pada gambar diatas ditunjukkan citra hasil thresholding dengan nilai threshold sebesar 128 dimana piksel-piksel yang memiliki nilai 128 keatas dirubah menjadi putih dan piksel yang bernilai 128 kebawah dirubah menjadi hitam. Pada teknik thresholding, sebenarnya masih ada lagi teknik yang lebih lanjut, teknik ini dikenal dengan nama optimal thresholding.Teknik ini biasa digunakan

untuk

memisahkan

suatu

objek

gambar

dengan

latar

belakangnya.Teknik ini dapat melihat perbedaan intensitas yang terdapat pada latar belakang dan objek sehingga dapat menentukan nilai sebuah threshold yang sesuai.

Gambar 2.7. optimal thresholding Gambar 2.7. merupakan sebuah contoh dari pengambilan nilai threshold pada optimal thresholding dengan menggunakan metode Otsu (Otsu, 1979).

34 Metode ini adalah metode yang paling populer diantara semua metode thresholding yang ada. Teknik Otsu ini memaksimalkan kecocokan dari sebuah threshold sehingga dapat memisahkan objek dengan latar belakangnya.Semua ini didapatkan dengan memilih nilai threshold yang memberikan pembagian kelas yang terbaik untuk semua pixel yang ada didalam image. Dasarnya adalah dengan menggunakan histogram yang telah dinormalisasi dimana jumlah tiap poin pada setiap level dibagi dengan jumlah total poin pada image.

Gambar 2.8. hasil thresholding dengan metode Otsu 2.5.6 Edge detection Perbedaan yang signifikan sebuah image brightness sangat menarik untuk beberapa alasan. Alasan yang pertama adalah sebuah tepian dari objek biasanya memiliki perbedaan intensitas cahaya (image yang terang bisa terdapat di latar belakang yang gelap atau sebaliknya image yang gelap bisa berada di latar belakang yang terang).dan alasan yang kedua adalah perbedaan tersebut dapat pula muncul akibat dari pola yang terbentuk dari perbedaan intensitas cahaya(zebra memiliki garis tubuh, macan tutul memiliki bintik-bintik pada tubuhnya atau garis-garis yang terbentuk karena bayangan). Poin-poin dimana sebuah image memiliki perbedaan intensitas cahaya yang tajam itulah yang sering disebut edges atau edge points. (David A.Forsyth & Jean Ponce, Computer Vision A Modern Approach). Tetapi untuk menemukan

35 garis yang cocok untuk disebut sebagai eges tidaklah mudah. Secara tipikal sangat sulit bagi kita untuk menentukan manakah edge yang berguna(perlu) dan manapula edge yang tidak berguna(tidak perlu).Dan untuk memenuhi semua itu sangat dibutuhkan informasi ber-level tinggi. Tidak kurang dari itu dibutuhkan pengetahuan sistem visual tentang apasajakah yang menarik yang sering terjadi pada sebuah edge dan juga dimanakah edge-edge itu berada.

(a)

(b)

(c) Gambar 2.9. Contoh edge detecting

Diatas adalah sebagian contoh dari edge detection yang mana gambar (a) adalah gambar asli koin-koin, gambar (b) adalah edge detection dengan menggunakan Sobel filter dan gambar (c) adalah contoh edge detection dengan menggunakan filter Canny. Setiap filter akan menghasilkan edge detection yang bervariasi. Berikut ini adalah macam – macam metode pendeteksian tepi :

36 

Roberts Cross Edge Detector Operator Roberts Cross melakukan pengukuran gradien spasial 2-D yang sederhana dan cepat pada sebuah gambar. Operator tersebut menandai daerah-daerah yang memiliki gradien spasial tinggi yang kemungkinan besar merupakan sebuah edge. Pada penggunaan umumnya, masukan untuk operator tersebut merupakan sebuah gambar grayscale, begitu juga dengan keluarannya. Nilai piksel di setiap titik pada hasil keluaran merepresentasikan perkiraan skala absolut dari gradien spasial dari gambar masukan pada titik tersebut. Pada teorinya, operator Roberts Cross terdiri dari sepasang matriks konvolusi 2x2. Satu matriks merupakan hasil rotasi 90o terhadap matriks lainnya.

Gambar 2.10. Matriks konvolusi Reberts Cross Matriks ini didesain agar dapat merespon dengan maksimal pada edge yang bersudut 45ƒ ke batas piksel, satu matriks untuk dua orientasi sudut 90o. Matriks ini dapat

37 digunakan secara terpisah pada gambar masukan, untuk menghasilkan pengukuran yang terpisah dari komponen gradien pada setiap orientasi (Gx dan Gy). Matriks-matriks ini dapat selanjutnya dikombinasikan untuk mencari skala absolut dari gradien pada setiap titik dan orientasi dari gradien tersebut. Skala gradien adalah sebagai berikut:

Walaupun biasanya, skala rata-rata dihitung dengan menggunakan:

yang dapat diproses dengan lebih cepat. Sudut dari orientasi pada edge yang meyebabkan kenaikan pada gradien spasial (relatif kepada orientasi batas piksel) adalah sebagai berikut:

Pada hal ini, orientasi 0 digunakan dengan pandangan bahwa arah dari kontras maksimum dari hitam ke putih berjalan dari kiri ke kanan, dan sudut lain dihitung berlawanan arah jarum jam dari rumus ini. Seringkali, skala absolut merupakan astu-satunya keluaran yang dilihat user, dua komponen dari gradien diproses dan ditambahkan dalam sebuah single pass dari gambar masukan dengan menggunakan operator pseudo-convolotion.

38

Gambar 2.11. Matriks Pseudo-Convolution Matriks

pseudo-convolution

dapat

menghasilkan

perhitungan skala gradien rata-rata yang lebih cepat dengan menggunakan rumus:



Sobel Edge Detector Operator Sobel melakukan pengukuran spasial 2-D pada sebuah gambar dan menguatkan daerah-daerah yang memiliki gradien spasial tinggi untuk setiap edge yang bersangkkutan. Biasanya operator Sobel digunakan untuk mencari skala gradien absolut rata-rata pada setiap titik pada gambar grayscale masukan. Pada teorinya, operator Sobel terdiri dari matriks konvolusi 3x3. Satu matriks merupakan hasil rotasi 90o terhadap matriks lainnya. Matriks ini sangat mirip dengan operator Roberts Cross.

39

Gambar 2.12. Matriks konvolusi Sobel Matriks-matriks ini didesain untuk dapat merespon dengan maksimal terhadap edge yang berjalan secara vertikal dan horizontal relatif terhadap batas piksel, satu matriks untuk dua orientasi sudut 90o. Matriks ini dapat digunakan secara terpisah pada gambar masukan, untuk menghasilkan pengukuran yang terpisah dari komponen gradien pada setiap orientasi (Gx dan Gy). Matriks-matriks ini dapat selanjutnya dikombinasikan untuk mencari skala absolut dari gradien pada setiap titik dan orientasi dari gradien tersebut. Skala gradien adalah sebagai berikut:

Walaupun biasanya, skala rata-rata dihitung dengan menggunakan:

yang dapat diproses dengan lebih cepat.

40 Sudut dari orientasi pada edge yang meyebabkan kenaikan pada gradien spasial (relatif kepada orientasi batas piksel) adalah sebagai berikut:

Pada hal ini, orientasi 0 digunakan dengan pandangan bahwa arah dari kontras maksimum dari hitam ke putih berjalan dari kiri ke kanan, dan sudut lain dihitung berlawanan arah jarum jam dari rumus ini. Seringkali,

skala

absolut

merupakan

satu-satunya

keluaran yang dilihat user, dua komponen dari gradien diproses dan ditambahkan dalam sebuah single pass dari gambar masukan dengan menggunakan operator pseudo-convolotion.

Gambar 2.13. Matriks Pseudo-Convolution Matriks

pseudo-convolution

dapat

menghasilkan

perhitungan skala gradien rata-rata yang lebih cepat dengan menggunakan rumus:

41 

Prewitt Edge Detector Pengenalan tepi Compass adalah sebuah pendekatan alternative untuk gradient turunan dari pengenalan tepi. Operasi ini biasanya menghasilkan dua buah citra / gambar, yang satu memperkirakan ukuran dari gradient tepi lokal dan yang satu memperkirakan orientasi tepi dari citra yang dimasukkan.

Ketika menggunakan pengenalan tepi Compass, citra tersebut dikonvolusikan menggunakan sebuah set matriks konvolusi, dimana setiap matriks yang sensitive kepada batas gambar / citra dalam orientasi yang berbeda. Untuk setiap piksel ukuran gradient dari batas lokal diperkirakan dengan respon maksimum dari delapan matriks pada lokasi piksel berikut :

dimana Gi adalah respon dari matriks i pada posisi piksel yang dipilih dan n adalah jumlah dari matriks konvolusi. Orientasi batas lokal diperkirakan dengan orientasi dari matriks yang memberikan respon maksimum. Berikut ini adalah dua dari delapan matriks :

42

Gambar 2.14 Matriks pengenalan tepi Prewitt compass yang sensitive pada 0€ and 45€.

Seluruh set dari delapan matriks dihasilkan dengan mengambil salah satu matriks dan memutar koefisiennya searah jarum jam. Setiap matriks yang dihasilkan sensitive kepada orientasi tepi lainnya dengan jarak dari 0€ sampai 315€ dalam menghasilkan matriks 45€, dimana 0€ merujuk pada sebuah tepi vertical.

Respon maksimum |G| untuk setiap piksel memberikan menaikkan harga nilai dari piksel yang berhubungan ukuran gambar keluaran. Nilai dari orientasi gambar keluaran terletak antara 1 dan 8, bergantung pada salah satu matriks dari delapan buah matriks yang menghasilkan respon maksimum.

Pengenalan tepi ini juga dikenal dengan nama edge template matching, karena satu set dari template tepi yang dicocokan ke gambar, setiap template mewakili sebuah tepi

43 dalam orientasi tertentu. Ukuran dan orientasi tepi kemudian tersebut ditentukan oleh template yang paling cocok dengan area lokal dari piksel.

Pengenalan tepi Compass adalah cara yang paling cocok untuk memperkirakan ukuran dan orientasi dari sebuah tepi. Ketika turunan dari gradient pengenalan tepi membutuhkan waktu penghitungan untuk memperkirakan orientasi dari ukuran dalam arah x- dan y-, pengenalan tepi Compass mendapatkan nilai orientasi langsung dari matriks dengan respon maksimum. Operator Compass disini dibatasi sampai delapan kemungkinan orientasi; tetapi pengalaman menunjukkan bahwa orientasi yang paling berhubungan belum tentu lebih akurat.

Di sisi lain, operator compass membutuhkan delapan konvolusi untuk setiap piksel, dimana operator gradient hanya membutuhkan dua, sebuah matriks menjadi sensitive pada tepi pada arah vertical dan sebuah matriks yang sensitive pada tepi pada arah horizontal.



Zero Crossing Detector

Zero crossing detector mencari tempat dalam laplacian dari sebuah gambar dimana nilai dari laplacian lebih besar dari nol contohnya titik dimana laplacian mengalami perubahan tanda. Titik seperti itu biasanya terjadi pada tepi dalam gambar

44 contohnya titik dimana intensitar dari sebuah image berubah secara terus – menerus, tetapi hal tersebut juga dapat terjadi pada tempat yang tidak mudah berasosiasi dengan tepi. Hal yang terbaik adalah dengan menganggap zero crossing detector sebagai sejenis fitur pendeteksi daripada sebuah pendeteksi tepi. Zero crossing selalu terletak pada closed contours dan juga keluaran dari zero crossing detector biasanya adalah sebuah gambar biner dengan ketebalan garis berpiksel tunggal yang menunjukan posisi dari titik zero crossing.

Titik awal dari zero crossing detector adalah sebuah gambar yang telah diolah menggunakan Laplacian dari Gaussian filter. Zero crossing yang hasilnya sangat dipengaruhi oleh ukuran dari Gaussian digunakan untuk tingkat kehalusan dari operator ini. Ketika tingkat kehalusan dinaikan maka sedikit demi sedikit kontur dari zero crossing akan ditemukan, dan sisanya yang tersisa dari proses tersebut akan berhubungan denga fitur gambar dengan ukuran yang lebih besar.

Inti dari zero crossing detector adalah Laplacian dari filter Gaussian dan kemudian pengetahuan dari operator akan diasumsikan disini. Seperti yang telah dijelaskan, tepi dari gambar memberi kenaikan pada zero crossing dalam keluaran LoG. Sebagai contoh, gambar berikut menunjukkan respon dari filter 1-D LoG pada step edge dari gambar..

45

Gambar 2.15 Respon dari filter 1-D LoG pada a step edge. Grafik sebelah kiri menunjukkan sebuah gambar 1-D, dengan panjang 200 piksel, dan mengandung step edge. Grafik sebelah kanan menunjukkan dari sebuah filter 1-D LoG dengan Gaussian yang mengalami deviasi 3 piksel.

Tetapi, zero crossing juga terjadi pada bagian gambar yang gradiennya mulai bertambah atau berkurang, dan ini mungkin terjadi pada bagian yang bukan tepi. Tidak jarang zero crossing ditemukan pada daerah dengan gradien yang sangat rendah dimana intensitas dari gradien bergerak naik dan turun di sekitar nol.

Ketika gambar telah difilter dengan filter LoG, sisanya yang harus dilakukan adalah mendeteksi zero crossing. Hal ini dapat dilakukan dalam beberapa cara.

Cara yang paling mudah adalah dengan threshold keluaran LoG pada titik nol, untuk menghasilkan gambar biner dimana

46 batasan antara daerah gambar bagian depan dan daerah latar belakang gambar mewakili lokasi dari titik zero crossing. Batasan ini dapat dengan mudah dideteksi danditandai dalam sekali proses, contohnya menggunakan operator morfologi. Sebagai contoh, untuk menemukan titik batas, kita hanya butuh menandai setiap titik gambar bagian depan yang memiliki sedikitnya satu neighbor latar belakang.

Masalahnya teknik ini akan merubah lokasi dari tepi zero crossing baik ke sisi terang dari tepi atau ke sisi gelap dari tepi, tergantung dari keputusan untuk mencari tepi dari daerah gambar bagian depan atau daerah gambar latar belakang.

Teknik yang lebih baik adalah menganggap titik dari kedua sisi dari batas threshold, dan memilih titik dengan ukuran terendah dari Laplacian, yang diharapkan mendekati zero crossing.

Sejak zero crossing gagal secara umum di antara dua piksel dalam gambar yang telah difilter dengan filter LoG, sebuah representasi alternatif keluaran adalah sebuah garis gambar yang secara sebagian menukar setengah piksel yang berseberangan dan setengah piksel yang berhubungan dengan gambar aslinya. Representasi seperti itu dikenal dengan dual

47 lattice. Hal ini tentu saja tidak membuat zero crossing lebih akurat.

Pendekatan yang lebih akurat adalah dengan melakukan sebuah interpolasi untuk memperkirakan posisi dari zero crossing pada sebuah precision sub-piksel.



Line Detection

Ketika tepi adalah sebuah tipe normal akhir dalam sebuah gambar, garis tipis dalam sebuah gambar cukup sering terjadi yang membuat hal tersebut berguna untuk mekanisme pemisahan untuk mendeteksi bagian – bagian dari gambar.

Operator dari pendeteksi garis terdiri dari sebuah matriks konvolusi untuk mendeteksi keberadaan garis dengan lebar yang berbeda

n,

pada

orientasi

tertentu

θ.

Gambar

berikut

menunjukkan kelompok dari empat buah matriks, dimana setiap matriks merespon pada suatu garis dengan lebar piksel ganda pada orientasi tertentu yang ditampilkan

48 Gambar 2.16 Empat matriks pendeteksi garis yang memberikan respon maksimal pada horizontal, vertical, dan oblique garis dengan ketebalan piksel tunggal.

Jika Ri melambangkan respon dari matriks I, maka setiap matriks dapat dihubungkan dengan sebuah gambar dan, untuk titik tertentu, jika |Ri| > |Rj| untuk semua j ≠ i maka titik tersebut mungkin berisi sebuah garis yang orientasi dan lebarnya berhubungan dengan matriks i tersebut. Biasanya Ri di threshold untuk menghilangkan garis halus yang berhubungan denga tepid an fitur lain dengan intensitas gradient yang memiliki ukuran berbeda dengan lebar garis yang diinginkan.



Canny Edge Detector

Operator

Canny

didesain

untuk

menjadi

sebuah

pendeteksi tepi yang optimal( berdasarkan criteria tertentu). Canny

menggunakan

sebuah

gambar

grayscale,

dan

menghasilkan sebuah gambar yang menampilkan posisi dari intensitas dan akhir yang telah ditemukan.

Operator Canny bekerja dalam sebuah proses bertingkat. Pertama

gambar

akan

diperhalus

dengan

menggunakan

konvolusi Gaussian. Kemudian sebuah operator turunan pertama dari 2-D digunakan untuk menghaluskan gambar pada daerah yang telah ditandai dengan sebagian turunan pertama yang

49 tinggi. Tepi ini diberikan kenaikan menjadi lipatan dalam ukuran gradient gambar. Kemudian algritma tersebut mencari puncak dari lipatan ini dan memberi nilai nol pada semua piksel yang bukan merupakan puncak lipatan yang menghasilkan garis tipis pada gambar keluaran, sebuah proses yang dikenal dengan nonmaximal suppression. Proses pencarian ini menampilkan hysteresis yang dikendalikan oleh dua thresholds: T1 dan T2 dengan T1 > T2. Pencarian hanya dapat dimulai pada titik dimana nilai lipatan lebih tinggi dari T1. Pencarian kemudian berlanjut dalam dua arah keluar dari titik tersebut hingga tinggi dari lipatan tersebut bernilai kurang dari T2. Hysteresis ini membantu untuk meyakinkan bahwa tepi yang memiliki noise tidak rusak menjadi banyak bagian tepi.

2.6

Fuzzy Logic Fuzzy Logic adalah metodologi pemecahan masalah dengan beribu – ribu aplikasi dalam pengendali yang tersimpan dan pemrosesan informasi. Fuzzy logic menyediakan cara sederhana untuk menggambarkan kesimpulan pasti dari informasi yang ambigu, samar – samar, atau tidak tepat. Sedikit banyak, fuzzy logic menyerupai pembuatan keputusan pada manusia dengan kemampuannya untuk bekerja dari data yang ditafsirkan dan mencari solusi yang tepat. Fuzzy logic pada dasarnya merupakan logika bernilai banyak (multivalued logic) yang dapat mendefinisikan nilai diantara keadaan konvensional seperti ya atau tidak, benar atau salah, hitam atau putih, dan sebagainya. Penalaran fuzzy

50 menyediakan cara untuk memahami kinerja dari system dengan cara menilai input dan output system dari hasil pengamatan. 2.6.1 Sejarah Konsep Fuzzy Logic diperkenalkan oleh Prof. Lotfi Zadeh dari Universitas California di Berkeley pada 1965, dan dipresentasikan bukan sebagai suatu metodologi control, tetapi sebagai suatu cara pemrosesan data dengan memperkenankan penggunaan partial set membership dibanding crisp set membership atau non-membership. Pendekatan pada set teori ini tidak diaplikasikan pada system control sampai tahun 70an karena kemampuan computer yang tidak cukup pada saat itu. Profesor Zadeh berpikir bahwa orang tidak membutuhkan kepastian, masukan informasi numeric, dan belum mampu terhadap control adaptif yang tinggi. Konsep fuzzy logic kemudian berhasil diaplikasikan dalam bidang control oleh E.H. Mamdani. Sejak saat itu aplikasi fuzzy berkembang kian pesat. Di tahun 1980an negara Jepang dan negara – negara di Eropa secara agresif membangun produk nyata sehubungan dengan konsep logika fuzzy yang diintegrasikan dalam produk – produk kebutuhan rumah tangga seperti vacuum cleaner, microwave oven dan kamera video. Sementara pengusaha di Amerika Serikat tidak secepat itu mencakup teknologi ini. Fuzzy logic berkembang pesat selama beberapa tahun terakhir. Terdapat lebih dari dua ribu produk dipasaran yang menggunakan konsep fuzzy logic, mulai dari mesin cuci hingga kereta berkecepatan tinggi. Setiap aplikasi tentunya menyadari beberapa keuntungan dari

fuzzy

logic

produktifitasnya.

seperti

performa,

kesederhaan,

biaya

rendah

dan

51 2.6.2 Alasan Penggunaan Fuzzy Logic Fuzzy logic menawarkan beberapa karakteristik unik yang menjadikannya suatu pilihan yang baik untuk banyak masalah control. Karakteristik tersebut antara lain : a. sudah menjadi sifatnya yang kuat selama tidak membutuhkan ketepatan, input yang bebas derau, dan dapat diprogram untuk gagal dengan aman jika sensor arus balik dimatikan atau rusak. Control output adalah fungsi control halus meskipun jarak variasi input yang cukup besar. b. Selama fuzzy logic controller memproses aturan – aturan yang dibuat user yang memerintah system control target, ia dapat dimodifikasi dengan mudah untuk meningkatkan atau mengubah secara drastis performa system. Sensor yang baru dapat dengan mudah digabungkan kedalam system secara sederhana dengan menghasilkan aturan memerintah yang sesuai. c. Fuzzy logic tidak terbatas pada sedikit masukan umpan-balik dan satu atau dua output control, tidak juga penting untuk menilai atau menghitung parameter rata - rata perubahan dengan tujuan agar ia diimplementasikan. Sensor data yang menyediakan beberapa indikasi untuk aksi dan reaksi system sudah cukup. Hal ini memungkinkan sensor menjadi murah dan tidak tepat sehingga menghemat biaya system keseluruhan dan kompleksitas rendah. d. Karena operasi – operasi yang berbasiskan aturan, jumlah input yang masuk akal dapat diproses ( 1 sampai 8 atau lebih ) dan banyak

52 output ( 1 sampai 4 atau lebih ) dihasilkan, walaupun pendefinisian rulebase secara cepat menjadi rumit jika terlalu banyak input dan output dipilih untuk implementasi tunggal selama pendefinisian rules(aturan), hubungan timbal baliknya juga harus didefinisikan. Akan lebih baik jika memecah system kedalam potongan – potongan yang lebih kecil dan menggunakan fuzzy logic controllers yang lebih kecil untuk didistribusikan pada system, masing – masing dengan tanggung jawab yang lebih terbatas. e. Fuzzy Logic dapat mengontrol system nonlinier yang akan sulit atau tidak mungkin untuk dimodelkan secara matematis. Hal ini membuka pintu bagi system control yang secara normal dianggap tidak mungkin untuk otomatisasi. Sedangkan karakteristik utama dari fuzzy logic yang ditemukan oleh Prof. Lotfi A. Zadeh adalah sebagai berikut: 

Dalam fuzzy logic, penalaran tepat dipandang sebagai suatu kasus terbatas dari penalaran kira –kira.



Dalam fuzzy logic segala sesuatunya adalah masalah derajat.



System logis manapun dapat difuzzifikasi.



Dalam fuzzy logic, pengetahuan diinterpretasikan sebagai koleksi dari fuzzy yang dipaksakan pada sekumpulan variable.



Kesimpulan dipandang sebagai sebuah proses dari perkembangan pembatas elastis.

53 2.6.3 Bagaimana Fuzzy Logic Digunakan Adapun langkah – langkah penggunaan fuzzy logic adalah sebagai berikut: a. Definisikan obyektif dan criteria control : 

Apa yang kita coba control ?



Apa yang harus kita lakukan untuk mengontrol system ?



Respon seperti apa yang kita butuhkan ?



Apa mode kegagalan system yang mungkin ?

b. Tentukan hubungan antara input dan output serta memilih jumlah minimum variable input pada mesin fuzzy logic(secara khusus error dan rata – rata perubahan error). c. Dengan menggunakan struktur berbasis aturan dari fuzzy logic, jabarkan permasalahan control ke dalam aturan IF X AND Y THEN Z yang mendefinisikan respon output system yang diinginkan untuk kondisi input system yang diberikan. Jumlah dan kompleksitas dari rules bergantung pada jumlah parameter input yang diproses dan jumlah variable fuzzy yang bekerjasama dengan tiap – tiap parameter. Jika mungkin, gunakan setidaknya satu variable dan turunan waktunya. Walaupun mungkin untuk menggunakan sebuah parameter tunggal yang error saat itu juga tanpa mengetahui rata – rata perubahannya, hal ini melumpuhkan kemampuan system untuk meminamalisasi keterlampauan untuk sebuah tingkat input.

54 d. Buat fungsi keanggotaan yang menjelaskan nilai input atau output yang digunakan didalam rules. e. Buat

rutinitas

proses

awal

dan

akhir

yang

penting

jika

diimplementasikan dalam software, sebaliknya program rules kedalam mesin hardware fuzzy logic. f. Test system, evaluasi hasil, atur rules dan fungsi keanggotaan, dan retest sampai hasil yang memuaskan didapat. 2.6.4 Himpunan Fuzzy Sangat penting sekali bagi kita untuk terlebih dahulu mengetahui apa itu crisp set atau yang dikenal juga dengan conventional set, sebelum kita mengarah pada bagaimana himpunan fuzzy dibuat untuk kekurangan pada crisp set.

2.6.4.1 Crisp Set Dalam kebanyakan jenis pemikiran setiap harinya, dan refleksi bahasa darinya, orang – orang menggunakan crisp set untuk mengelompokan sesuatu. Menjadi anggota dari crisp set adalah seluruhnya berhubungan atau tidak sama sekali. Seorang wanita dikatakan hamil ataupun tidak, ia tidak pernah “hamil sebagian” atau “sedikit hamil”. Berpikir dengan crisp set menjadikan segala sesuatunya lebih sederhana, karena sesuatu bisa merupakan anggota dari suatu crisp set atau tidak. Crisp set dapat digunakan untuk merepresentasikan gambaran pengertian hitam dan putih. Seringkali juga, saat sesuatu itu merupakan anggota dari sebuah crisp set maka ia kemudian (pada waktu yang sama) bukan merupakan anggota dari crisp set manapun. Kembali hal ini menyederhanakan penggunaan logika dengan proses

55 pemikiran semacam ini. Konstruksi linguistik yang menggambarkan jenis pemikiran ini dapat benar – benar berguna, terutama saat kategori crisp digunakan. Pada himpunan tegas (crisp), nilai keanggotaan suatu item x dalam suatu himpunan A, yang sering ditulis dengan

ˆA[x], memiliki 2 kemungkinan, yaitu

(Kusumadewi, 2004 : p3) : 

Satu (1), yang berarti bahwa suatu item menjadi anggota dalam suatu himpunan, atau



Nol (0), yang berarti bahwa suatu item tidak menjadi anggota dalam suatu himpunan.

Untuk lebih jelasnya, bisa dilihat dari contoh dibawah ini :

Gambar 2.17. Himpunan MUDA, PAROBAYA, dan TUA Dari gambar diatas dapat dijelaskan bahwa : 

Apabila seseorang berusia 34 tahun, maka ia dikatakan MUDA (ˆMUDA[34] = 1);



Apabila seseorang berusia 35 tahun, maka ia dikatakan TIDAK MUDA (ˆMUDA[35] = 0);



Apabila seseorang berusia 35 tahun kurang 1 hari, maka ia dikatakan TIDAK MUDA (ˆMUDA[35 – 1hr] = 0);

56 

Apabila seseorang berusia 35 tahun, maka ia dikatakan PAROBAYA (ˆPAROBAYA[35] = 1);



Apabila seseorang berusia 34 tahun, maka ia dikatakan TIDAK PAROBAYA (ˆPAROBAYA[34] = 0);



Apabila seseorang berusia 55 tahun, maka ia dikatakan PAROBAYA (ˆPAROBAYA[55] = 1);



Apabila seseorang berusia 35 tahun kurang 1 hari, maka ia dikatakan TIDAK PAROBAYA (ˆPAROBAYA[35 – 1hr] = 0);

Dari sini bisa dikatakan bahwa pemakaian himpunan crisp untuk menyatakan umur sangat tidak adil, adanya perubahan kecil saja pada suatu nilai mengakibatkan perbedaan kategori yang cukup signifikan. Oleh karena itu digunakanlah himpunan fuzzy untuk mengantisipasi hal tersebut. 2.6.4.2 Fuzzy Set Logika fuzzy lahir berdasarkan fenomena – fenomena alam yang serba tidak tepat dan samar ditinjau dari cara berpikir manusia, dimana pada kenyataannya tidak ada suatu kondisi atau pernyataan yang tepat 100% benar atau 100% salah. Prof. Lotfi A. Zadeh mengemukakan bahwa true atau false dalam logika Boolean tidak dapat merepresentasikan pernyataan yang tidak pasti yang berada diantara pernyataan true atau false tadi, seperti yang sering terjadi dalam dunia nyata. Untuk merepresentasikan nilai ketidakpastian antara true atau false tersebut, Prof. Lotfi A. Zadeh mengembangkan suatu teori berdasarkan conventional set yang disebutnya fuzzy set (himpunan fuzzy). Sebagai ganti dari

57 pernyataan dengan nilai seluruhnya true atau semuanya false, logika fuzzy memberikan nilai yang spesifik pada setiap nilai diantara pernyataan true atau false dengan menentukan fungsi kenaggotaan (membership function) bagi tiap nilai input dari proses fuzzy (crisp input) dan derajat keanggotaan (degree of membership) yaitu menyatakan derajat dari crisp input sesuai membership function antara 0 sampai 1, sehingga memungkinkan bagi suatu persamaan memiliki nilai true dan false secara bersamaan. Menurut Prof. Lotfi A Zadeh, fuzzy set adalah sebuah kelas dari obyek dengan serangkaian kesatuan dari grades of membership(nilai keanggotaan). Sebuah set dikarakterisasikan oleh sebuah fungsi keanggotaan (karakteristik) yang memberikan tiap obyek sebuah nilai keanggotaan yang rentang nilainya antara 0 dan 1. Gagasan pencantuman (inclusion), penyatuan (union), persimpangan (intersection), pelengkap (complement), hubungan (relation), kecembungan (convexity), dan sebagainya diberikan pada set tersebut, dan berbagai macam sifat dari pemikiran ini dalam konteks dari fuzzy set dibangun. Secara khusus, dalil untuk fuzzy set cembung dibuktikan tanpa perlu fuzzy set terputus. Aturan umum untuk teori fuzzy set dituliskan sebagai berikut:

dimana n merupakan jumlah kemungkinan. Rumusan diatas menyatakan bahwa kita dapat mengambil n jumlah event yang mungkin dan menggunakan f untuk menghasikan hasil tunggal yang mungkin.

58 Untuk lebih jelasnya mengenai himpunan fuzzy dapat dilihat pada contoh persoalan dibawah ini (Kusumadewi, 2004 : p5):

Gambar 2.18 Himpunan fuzzy untuk variable Umur Dengan adanya himpunan fuzzy memungkinkan seseorang untuk dapat masuk kedalam 2 himpunan yang berbeda, MUDA dan PAROBAYA, PAROBAYA dan TUA, dan sebagainya. Seberapa besar eksistensinya dalam himpunan tersebut dapat dilihat pada nilai keanggotaannya. Dari gambar diatas, dapat dilihat bahwa : 

Seseorang yang berumur 40 tahun, termasuk dalam himpunan MUDA dengan ˆMUDA[40] = 0,25; namun dia juga termasuk dalam himpunan PAROBAYA dengan ˆPAROBAYA[40] = 0,5.



Seseorang yang berumur 50 tahun, termasuk dalam himpunan MUDA dengan ˆMUDA[50] = 0,25; namun dia juga termasuk dalam himpunan PAROBAYA dengan ˆPAROBAYA[50] = 0,5.

Kalau pada himpunan crisp, nilai kenaggotaan hanya ada 2 kemungkinan, yaitu 0 atau 1, pada himpunan fuzzy nilai keanggotaan terletak pada rentang 0 sampai 1. apabila x memiliki nilai keanggotaan fuzzy

ˆA[x] = 0 berarti x tidak

59 menjadi anggota himpunan A, demikian pula apabila x memiliki nilai keanggotaan fuzzy ˆA[x] = 1 berarti x menjadi anggota penuh pada himpunan A. Terkadang kemiripan antara keanggotaan fuzzy dengan probabilitas menimbulkan kerancuan. Keduanya memiliki nilai pada interval [0,1], namun interpretasi nilainya sangat berbeda antara kedua kasus tersebut. Keanggotaan fuzzy memberikan suatu ukuran terhadap pendapat atau keputusan, sedangkan probabilitas mengindikasikan proporsi terhadap keseringan suatu hasil bernilai benar dalam jangka panjang. Misalnya, jika nilai keanggotaan suatu himpunan fuzzy MUDA adalah 0,9 maka tidak perlu dipermasalahkan berapa seringnya nilai itu diulang secara individual untuk mengharapkan suatu hasil yang hampir pasti muda. Di lain pihak, nilai probabilitas 0,9 muda berarti 10% dari himpunan tersebut diharapkan tidak muda. Himpunan fuzzy memiliki 2 atribut, yaitu (Kusumadewi, 2004 : p6) : 

Linguistik Yaitu penamaan suatu grup yang mewakili suatu keadaan atau kondisi tertentu dengan menggunakan bahasa alami, seperti : MUDA, PAROBAYA, TUA.



Numeris Yaitu suatu nilai (angka) yang menunjukan ukuran dari suatu variable seperti : 40, 25, 50, dsb.

2.6.5 Fuzzy Set Operation Fuzzy set operation dalah operasi yang dilakukan pada fuzzy set. Operasi – operasi ini merupakan generalisasi dari operasi crisp set. Terdapat lebih dari

60 satu generalisasi yang mungkin. Operasi – operasi yang paling banyak digunakan secara luas disebut standard fuzzy set operations. Terdapat tiga operasi yaitu : fuzzy unions, fuzzy intersections, dan fuzzy complements. 2.6.5.1 Fuzzy Unions Fungsi keanggotaan dari Union dari dua fuzzy set A dan B dengan fungsi keanggotaan

ˆA dan ˆB berturut – turut ditetapkan sebagai maksimum dari dua

fungsi keanggotaan tersendiri. Ini disebut standar maksimum.

Gambar 2.19 Grafik Fungsi Fuzzy Unions Operasi Union dalam teori fuzzy set ekuivalen dengan operasi OR pada aljabar Boolean. Sifat (property) dari fuzzy union mencakup: 

Boundary Condition u(a , 0) = a



Monotonicity

61 b ≤ d secara tidak langsung menyatakan u(a , b) ≤ u(a , d) 

Commutativity u(a , b) = u(b , a)



Associativity u (a , u(b , d)) = u(u (a , b) , d)



Continuity u adalah fungsi yang berkelanjutan (continuous)



Superidempotency u (a , a) > a



Strict monotonicity a1 < a2 dan b1 < b2 secara tidak langsung menyatakan bahwa U(a1, b1) < U(a2, b2)

Keterangan : u menyatakan union a, b, d, a1, a2, b1, b2 menyatakan fuzzy set 2.6.5.2 Fuzzy Intersections Fungsi keanggotaan dari Intersection dari dua fuzzy set A dan B dengan fungsi keanggotaan ˆA dan ˆB berturut – turut ditetapkan sebagai minimum dari dua fungsi keanggotaan tersendiri. Ini disebut standar minimum.

62

Gambar 2.20 Grafik Fungsi Fuzzy Intersections Operasi Intersection dalam teori fuzzy set ekuivalen dengan operasi AND pada aljabar Boolean. Sifat (property) dari fuzzy intersection mencakup: 

Boundary Condition i(a , 1) = a



Monotonicity b ≤ d secara tidak langsung menyatakan i(a , b) ≤ i(a , d)



Commutativity i(a , b) = i(b , a)



Associativity i (a , i(b , d)) = i(i (a , b) , d)



Continuity i adalah fungsi yang berkelanjutan (continuous)



Subidempotency i (a , a) ≤ a

63 Keterangan : i menyatakan intersectiona, b, d, a1, a2, b1, b2 menyatakan fuzzy set 2.6.5.3 Fuzzy Complements Fungsi keanggotaan dari Intersection dari sebuah fuzzy set A dengan fungsi keanggotaan

ˆA ditetapkan sebagai negasi dari fungsi keanggotaan yang

ditentukan. Ini disebut standar negasi.

Gambar 2.21 Grafik Fungsi Fuzzy Complements Operasi Complement dalam teori fuzzy set ekuivalen dengan operasi NOT pada aljabar Boolean. Sifat (property) dari fuzzy complement mencakup: 

Boundary Condition c(0) = 1 dan c(1) = 0



Monotonicity Untuk semua a, b [0 , 1], jika a ≤ b maka c(a) ≥ c(b)

64 

Continuity c adalah fungsi yang berkelanjutan (continuous)



Involutions c adalah suatu involution, yang berarti bahwa c(c(a)) = a untuk setiap a [0 , 1]

2.6.6 Himpunan Klasik vs Himpunan Fuzzy Perbedaan himpunan fuzzy dengan himpunan klasik dapat diilustrasikan pda gambar dibawah ini. Dari gambar tersebut dapat terlihat himpunan fuzzy memiliki batas yang tidak jelas, sedangkan himpunan klasik memiliki batas yang jelas. Pada gambar 6 tanda ‘)’ mengartikan batas akhir dari sebuah scope dan tanda ‘[‘ mengartikan batas awal sebuah scope dari himpunan klasik.

Gambar 2.22

Gambar 2.23

65 Rentang suhu yang dinyatakan dalam : 2.22 Himpunan Fuzzy 2.23 Himpunan Klasik 2.6.7 Sistem Fuzzy Ada beberapa hal yang perlu diketahui dalam memahami system fuzzy, yaitu (Kusumadewi, 2004 : p6) : a. Variable fuzzy Variable fuzzy merupakan variable yang hendak dibahas dalam suatu system fuzzy. Contoh : umur, temperature, pertmintaan, dsb. b. Himpunan fuzzy Himpunan fuzzy merupakan suatu grup yang mewakili suatu kondisi atau keadaan tertentu dalam suatu variable fuzzy. Lebih lengkap mengenai himpunan fuzzy dapat dilihat pada section 2.11.4.2 diatas. c.

Semesta Pembicaraan Semesta

pembicaraan

adalah

keseluruhan

nilai

yang

diperbolehkan untuk dioperasikan dalam suatu variable fuzzy. Semesta pembicaraan merupakan himpunan bilangan real yang senantiasa naik (bertambah) secara monoton dari kiri ke kanan. Nilai semesta pembicaraan dapat berupa bilangan positif maupun negative. Adakalanya nilai semesta pembicaraan ini tidak dibatasi batas atasnya. Contoh :  Semesta pembicaraan untuk variable umur : [0 +∞]

66  Semesta pembicaraan untuk variable temperature : [0 40] d. Domain Domain himpunan fuzzy adalah keseluruhan nilai yang diijinkna dalam semesta pembicaraan dan boleh dioperasikan dalam suatu himpunan fuzzy. Seperti halnya semesta pembicaraan, domain merupakan himpunan bilangan real yang senantiasa naik (bertambah) secara monoton dari kiri ke kanan. Nilai domain dapat berupa bilangan positif maupun negative. Contoh domain himpunan fuzzy : 

MUDA

=



PAROBAYA =

[35,

55]



TUA

[45,

+∞]

=

[0,

45]

2.6.8 Fungsi Keanggotaan (Membership Function) Fungsi keanggotaan (membership function) adalah suatu kurva yang menunjukan pemetaan titik – titik input data kedalam nilai keanggotaanya (sering juga disebut dengan derajat keanggotaan) yang memiliki interval antara 0 sampai 1 (Kusumadewei, 2004 : p8). Salah satu cara yang dapat digunakan untuk mendapatkan nilai keanggotaan adalah dengan melalui pendekatan fungsi. Ada beberapa fungsi yang bisa digunakan. 2.6.8.1 Representasi Linier Pada representasi linear, pemetaan input ke derajat keanggotaannya digambarkan sebagai suatu garais lurus. Bentuk ini paling sederhana dan menjadi pilihan yang baik untuk mendekati suatu konsep yang kurang jelas.

67 Ada 2 keadaaan himpunan fuzzy yang linear. Pertama, kenaikan himpunan dimulai pada nilai domain yang memiliki derajat keanggotaan nol [0] bergerak ke kanan menuju ke nilai domain yang memiliki derajat keanggotaan lebih tinggi.

Gambar2.24 . Representasi Linear Naik Fungsi keanggotaan :

Kedua, merupakan kebalikan yang pertama. Garis lurus dimulai dari nilai domain dengan derajat keanggotaan tertinggi pada sisi kiri, kemudian bergerak menurun ke nilai domain yang memiliki derajat keanggotaan lebih rendah.

68

Gambar 2.25 Representasi linear Turun Fungsi keanggotaan :

2.6.8.2 Representasi Kurva Segitiga Kurva Segitiga pada dasarnya merupakan gabungan antara 2 garis (linear) seperti terlihat pada gambar .

Gambar2.26. Kurva Segitiga

69 Fungsi keanggotaan :

2.6.8.3 Representasi Kurva Trapesium Kurva Trapesium pada dasarnya seperti bentuk segitiga, hanya saja ada beberapa titik yang memiliki nilai keanggotaan 1 ( Gambar ).

Gambar 2.27 Kurva Trapesium Fungsi keanggotaan :

2.6.8.4 Representasi Kurva Bentuk Bahu Daerah

yang terletak

ditengah – tengah suatu

variable

yang

direpresentasikan dalma bentuk segitiga, pada sisi kanan dan kirinya akan naik

70 dan turun (misalkan : DINGIN bergerak ke SEJUK bergerak ke HANGAT dan bergerak ke PANAS). Tetapi terkadang salah satu sisi dari variable tersebut tidak mengalami perubahan. Sebagai contoh, apabila telah mencapai kondisi PANAS, kenaikan temperature akan tetap berada pada kondisi PANAS. Himpunan fuzzy ‘bahu’ , bukan segitiga, digunakan utnuk mengakhiri variable suatu daerah fuzzy. Bahu kiri bergerak dari benar ke salah, demikian juga bahu kanan bergerak dari salah ke benar. Gambar menunjukkan variable TEMPERATUR dengan daerah bahunya.

TEMPERATUR DINGIN

SEJUK

NORMAL

HANGAT

PANAS

Gambar 2.28 Grafik Kurva Bentuk Bahu 2.6.8.5 Representasi Kurva-S Kurva PERTUMBUHAN dan PENYUSUTAN merupakan kurva-S atau sigmoid yang berhubungan dengan kenaikan dan penurunan permukaan secara tak linear. Kurva-S didefinisikan dengan menggunakan 3 parameter, yaitu : nilai keanggotaan nol (α), nilai keanggotaan lengkap (γ), dan titik infleksi atau crossover (β) yaitu titik yang memiliki domain 50% benar. Gambar menunjukan karakteristik kurva-S dalam bentuk skema.

71 Kurva-S untuk PERTUMBUHAN akan bergerak dari sisi paling kiri (nilai keanggotaan = 0) ke sisi paling kanan (nilai keanggotaan = 1). Fungsi keanggotaannya akan tertumpu pada 50% nilai keanggotaan yang sering disebut dengan titik infleksi (gambar ). Fungsi keanggotaan pada kurva PERTUMBUHAN adalah :

Kurva-S untuk PENYUSUTAN akan bergerak dari sisi paling kanan (nilai keanggotaan = 1) ke sisi paling kiri (nilai keanggotaan = 0) seperti terlihat Gambar. Fungsi keanggotaan pada kurva PENYUSUTAN adalah :

2.6.8.6 Representasi Kurva Bentuk Lonceng (Bell Curve) Untuk merepresentasikan bilangan fuzzy, biasanya digunakan kurva berbentuk lonceng. Kurva berbentuk lonceng ini terbagi atas 3 kelas, yaitu himpunan fuzzy π, beta, dan Gauss. Perbedaan ketiga kurva ini terletak pada gradiennya.

72 2.6.8.6.1 Kurva π Kurva π berbentuk lonceng dengan derajat keanggotaan 1 terletak pada pusat dengan domain (γ), dan lebar kurva (β) seperti terlihat pada gambar . Nilai kurva untuk suatu nilai domain x diberikan sebagai :

2.6.8.6.2 Kurva BETA Seperti halnya kurva PI, kurva BETA juga berbentuk lonceng namun lebih rapat. Kurva ini juga didefinisikan dengan 2 parameter, yaitu nilai pada domain yang menunjukan pusat kurva (γ), dan setengah lebar kurva (β) seperti terlihat pada gambar. Nilai kurva untuk suatu nilai domain x diberikan sebagai :

B ( x ; γ , β ) = 1 / ( 1 + ( ( x – γ ) - β )2 2.6.8.6.3 Kurva GAUSS Jika kurva PI dan kurva BETA menggunakan 2 parameter yaitu (γ) dan (β), kurva GAUSS juga menggunakan (γ) untuk menunjukkan nilai domain pada pusat kurva, dan (k) yang menunjukkan lebar kurva. Nilai kurva untuk suatu nilai domain x diberikan sebagai :

G ( x ; k , γ ) = e –k(γ–x)^2 2.6.9 Fuzzy Logic Controller Dalam

perkembangan

selanjutnya,

pada

tahun

1973

Zadeh

memperkenalkan variable linguistic dimana nilai dijelaskan dengan kata – kata dan aturan – aturan IF–THEN yang merupakan basis pengetahuan dari sistem

73 fuzzy. Melalui variabel linguistik dan aturan-aturan IF–THEN tersebut, Zadeh telah membuat konsep dasar dari pengaplikasian sistem fuzzy pada sistem kontrol. Pengaplikasiannya secara langsung baru direalisasikan pada tahun 1975 oleh Mamdani dan Assilian. Mereka membuat kerangka kerja dasar dari kontroler logika fuzzy (fuzzy logic controller) dan menerapkannya pada pengendalian mesin uap. DaIam Fuzzy Logic Controller, himpunan fuzzy yang merupakan pendekatan numerik diubah menjadi label yang merupakan pendekatan kualitatif, yang kemudian akan digunakan untuk membuat rule - rule. Dengan membership function yang saling tuinpang tindih menyebabkan transisi dari hangat ke panas berlangsung secara bertahap. Dalam sistem kontrol dengan logika fuzzy, logika fuzzy menghubungkan bahasa dan kemampuan berfikir manusia kedalam dunia nyata. Dengan logika fuzzy, transfer function yang kompleks dapat dihindari. Logika fuzzy mcmbuat hubungan antara input dan output dalam sebuah kelompok pemyataan IF THEN berdasarkan pengalaman operator. Dalam sistem Fuzzy Logic Controller terdapat beberapa proses, yaitu: 2.6.9.1 Fuzzyfication Fuzzyfication merupakan proses pemetaan nilai-nilai input (crisp input) yang berasal yang berasal dari sistem yang dikontrol (besaran non fuzzy) ke dalam himpunan fuzzy menurut fungsi keanggotaannya. Himpunan fuzzy Iersebut merupakan fuzzy input yang akan diolah secara fuzzy pada proses berikutnya. Untuk mengubah crisp input menjadi fuzzy input, terlebih dahulu harus menentukan membership function untuk tiap crisp input, kemudian proses

74 fuzzyfikasi akan mengambil crisp input dan membandingkan dengan membership function yang telah ada untuk menghasilkan harga fuzzy input. 2.6.9.2 Rules Evaluation Pada tahap rule evaluation ini diproses hubungan antara nilai-nilai input (crisp input) dan nilai-nilai output (crisp output) yang dikehendaki dengan aturan-aturan (rules). Aturan ini nantinya yang akan menentukan respon sistem terhadap berbagai kondisi setting point dan gangguan yang terjadi pada sistem. Rules yang dipakai adalah jenis “IF-THEN“. Berikut ini contoh rules. IF Err is Normally big (antecendent 1) and AEn is Normally big (antecendent 2) THEN output is Normally big (consequent). Pada antecendent input variable = label, juga pada consequent output variable = label Pada penggunaan dua antecendent atau lebih, untuk mempermudah dapat digunakan matriks. Proses rule evaluation akan mengevaluasi Fuzzy input yang didapat dari proses fuzzyfikasi untuk tiap antecendent dari rule dengan menentukan rule strength dari tiap-tiap rule, karena antecendent dihubungkan dengan operator AND maka rule strength diambil dari strength value yang terkecil dari antecendent. Proses selanjutnya adalah menentukan Fuzzy output dengan membandingkan rule strength dari semua rule yang mempunyai label conscquent yang sama. 2.6.9.3 Defuzzyfication Pada tahap ini dilakukan pemetaan bagi nilai-nilai fuzzy output yang dihasilkan pada tahap rules evaluation ke nilai-nilai output kuantitatif yang sesuai dengan sistem yang diharapkan. Ada berbagai metode untuk melakukan proses defuzzyfication, diantaranya metode Center Of Grafity (COG), dimana

75 metode ini akan menghitung pusat titik berat pada semua membership function output yang dipenuhi untuk menentukan besarnya output yang harus diberikan. Pada proses defuzzyfikasi dengan metode COG setiap output membership function yang mempunyai nilai diatas Fuzzy output dipotong, pemotongan ini disebut lamda cut. Hasil dari membership function yang telah terpotong digabungkan lalu dihitung dengan COG secara keseluruhan. Metode COG juga dapat dilakukan pada output membership function yang berbentuk singleton. Output membership function singleton merupakan sebuah garis vertikal tunggal. Pemotongan pada output membership function dilakukan dengan pengurangan tinggi garis vertikal tersebut pada nilai fuzzy output. Nilai yang lebih tinggi dari fuzzy output dibuang dan hasil pemotongan tersebut kemudian dihitung dengan COG. 2.6.10 Cluster Analysis Analisis Pengelompokan (cluster analysis), disebut juga analisis segmentasi (segmentation analysis) atau analisis taksonomi (taxonomy analysis), merupakan seperangkat tehnik untuk mencapai pekerjaan mempilah – pilah objek – objek (observasi) menjadi subset – subset yang relatif homogen, berdasarkan kesamaan – kesamaan antar objek. Clustering adalah klasifikasi obyek kedalam kelompok yang berbeda, atau lebih tepatnya, pembagian sebuah set data kedalam subset – subset (cluster), sehingga data dalam tiap subset (idealnya) berbagi beberapa sifat umum – seringkali dekatnya bergantung pada beberapa perhitungan jarak yang dijelaskan. Pengelompokan data (data clustering) adalah tehnik umum untuk analisis data

76 statistic, yang digunakan pada banyak bidang, termasuk machine learning, data mining, pengenalan pola, analisis citra dan bioinformatik. Contoh penggunaan analisis pengelompokan dalam berbagai bidang: 

Biologi : Taksonomi atau mengelompokkan tumbuh-tumbuhan, hewan, dsb.



Astronomi : Bintang-bintang dikelompokkan dalam suatu gugus (misalnya yang sifat pancarannya sama)



Meteorologi : Curah hujan, kelembaban, tekanan udara bisa mengelompokkan wilayah-wilayah tertentu yang sifatnya sama



Geologi : Untuk mengetahui sebaran bebatuan atau tanah yang sifatnya sama

2.6.10.1 Tipe-tipe Clustering Terdapat

dua jenis algoritma pengelompokan data

antara lain

pengelompokkan hierarkis dan pengelompokan partisional. Clustering dua arah, co-clustering atau biclustering adalah metode pengelompokkan dimana bukan hanya obyek yang dikelompokkan tetapi juga sifat-sifat dari obyek, contohnya, jika data direpresentasikan dalam sebuah matriks data, maka baris dan kolom akan dikelompokkan secara bersamaan. 2.6.10.1.1 Hierarchical Clustering Algoritma hierarkis menemukan cluster berturut-turut menggunakan cluster yang dibangun sebelumnya, atau dengan kata lain pembagian data kedalam kelompok-kelompok tertentu tidak dilakukan dalam satu langkah. Bahkan, serangkaian pembagian terjadi, yang mungkin berjalan dari sebuah

77 cluster tunggal yang berisikan semua obyek ke n cluster yang masing-masing berisi sebuah obyek tunggal. Hierarchical Clustering dibagi kedalam dua metode antara lain : 

Agglomerative Method Didapat dengan serangkaian penyatuan n obyek kedalam kelompokkelompok. Metode ini lebih umum digunakan.



Divisive Method Memisahkan n obyek secara berturut-turut kedalam finer grouping. Hierarchical Clustering dapat ditunjukkan dengan sebuah diagram dua dimensi yang dikenal sebagai dendogram yang mengilustrasikan penyatuan atau pemisahan yang dibuat pada tiap urutan tahap dari analisis. Contoh dendogram diberikan seperti dibawah ini :

Gambar 2.29 Dendogram Prosedur pengelompokan hierarkis agglomerative menghasilkan serangkaian pembagian data, Pn, Pn-1, ....... , P1 . Pn yang pertama berisi n kelompok obyek tunggal, P1 berisi kelompok tunggal yang berisi semua permasalahan n.

78 Pada tiap tahap tertentu metode ini bekerja sama dengan dua cluster yang paling mirip. Perbedaan antara metode timbul karena cara yang berbeda-beda dalam menetapkan jarak (atau kemiripan) antar cluster. Beberapa tehnik agglomerative akan dijelaskan dibawah ini. 

Single Linkage Clustering Salah satu metode pengelompokan hierarkis agglomerative yang paling sederhana adalah pertalian tunggal, dikenal juga dengan tehnik tetangga terdekat (nearest neighbor). Pendefinisian sifat dari metode ini adalah bahwa jarak antar kelompok ditetapkan sebagai jarak antara pasangan obyek terdekat, dimana hanya pasangan yang berisikan satu obyek dari tiap kelompok yang dipertimbangkan. Dalam metode pertalian tunggal, D(r,s) dirumuskan sebagai : D(r,s) = Min { d(i,j) : dimana obyek i didalam cluster r dan obyek j didalam cluster s } Disini jarak antara pasangan obyek (i,j) yang mungin dihitung, dimana obyek i didalam cluster r dan obyek j didalam cluster s. Nilai minimum dari jarak ini adalah jarak antara cluster r dan s. Dengan kata lain, jarak antara dua cluster adalah nilai dari link terpendek antar cluster. Pada tiap tahap dari hierarchical clustering, cluster r dan s, untuk D(r,s) minimum, digabungkan.

79

Gambar 2.30 Single Linkage Clustering 

Complete Linkage Clustering Metode pengelompokan Complete Linkage , disebut juga furthest neighbor, adalah kebalikan dari single linkage. Jarak antar kelompok ditetapkan sebagai jarak antar pasangan obyek terjauh, satu dari tiap-tiap kelompok. Dalam metode ini, D(r,s) dirumuskan sebagai : D(r,s) = Max { d(i,j) : dimana obyek i didalam cluster r dan obyek j didalam cluster s } Disini jarak antara pasangan obyek (i,j) yang mungin dihitung, dimana obyek i didalam cluster r dan obyek j didalam cluster s dan nilai minimum dari jarak ini adalah jarak antara cluster r dan s. Dengan kata lain, jarak antara dua cluster adalah nilai dari link terpanjang antar cluster. Pada tiap tahap dari hierarchical clustering, cluster r dan s, untuk D(r,s) minimum, digabungkan.

80

Gambar 2.31 Complete Linkage Clustering 

Average Linkage Clustering Jarak antar dua cluster ditetapkan sebagai jarak rata-rata antar semua pasangan obyek, dimana tiap-tiap pasangan dibentuk dari satu obyek dari masing-masing kelompok. Dalam metode ini, D(r,s) dirumuskan sebagai : D(r,s) = Trs / ( Nr * Ns)

Dimana Trs adalah jumlah dari semua jarak pasangan antara cluster r dan cluster s. Nr dan Ns adalah ukuran dari cluster r dan s berturut-turut. Pada tiap tahap dari hierarchical clustering, cluster r dan s, untuk D(r,s) minimum, digabungkan.

Gambar 2.32 Average Linkage Clustering

81 

Average Group Linkage Dengan metode ini, kelompok akan direpresentasikan oleh nilai mean untuk tiap-tiap variable, oleh karena itu, vektor mean, dan jarak inter-group ditetapkan sebagai jarak antar dua vektor mean tersebut. Dalam metode average group linkage, dua cluster r dan s digabungkan sehingga, setelah penggabungan, jarak rata-rata pasangan dalam cluster yang diperbaharui adalah minimum. Anggap saja kita menandakan cluster baru yang dibentuk dengan penggabungan cluster r dan s, sebagai t. Maka D(r,s), jarak antara cluster r dan s dirumuskan sebagai : D(r,s) = rata-rata { d(i,j) : dimana observasi i dan j ada didalam cluster t, cluster dibentuk dengan penggabungan cluster r dan s } Pada tiap tahap dari hierachical clustering, cluster r dan s, untuk D(r,s)

minimum, digabungkan. Dalam kasus ini, kedua cluster tersebut

digabungkan sehingga cluster yang baru dibentuk akan memiliki jarak pasangan minimum antara titik-titik didalamnya. 

Ward’s Hierarchical Clustering Method Ward (1963) mengajukan sebuah prosedur clustering mencoba untuk membentuk pembagian dalam cara yang meminimalisasikan asosiasi yang hilang dengan tiap-tiap pengelompokan, dan untuk mengukur kehilangan tersebut dalam sebuah bentuk yang dapat ditafsirkan. Pada tiap langkah dalam analisis, kesatuan dari semua pasangan cluster yang mungkin dipertimbangkan dan dua cluster yang hasil penyatuannya dalam peningkatan minimum dalam hal hilangnya informasi dikombinasikan.

82 2.6.10.1.2 Partitional Clustering Berbeda dengan hierarchical clustering, pada metode pengelompokkan parsional ini, pembagian data kedalam kelompok-kelompok tertentu justru dilakukan dalam satu langkah. Partitional Clustering, pada sisi lain, berusaha secara langsung untuk mendekomposisikan set data kedalam sebuah set cluster yang terputus-putus. Fungsi standar yang algoritma pengelompokan berusaha untuk meminimalisasinya, mungkin menekankan pada struktur local dari data, dengan menugaskan cluster untuk mencapai puncaknya dalam fungsi kepadatan kemungkinan, atau struktur global. Secara khusus, criteria global menyangkut meminimalkan beberapa ukuran ketidakcocokan dalam sample pada tiap cluster, saat memaksimalkan ketidakcocokan pada cluster yang berbeda. 2.6.10.1.2.1 K-Means Clustering K-means (MacQueen,1967) adalah salah satu algoritma unsupervised learning paling sederhana yang menyelesaikan masalah pengelompokan yang umum dikenal. Prosedurnya mengikuti cara yang sederhana dan mudah untuk mengklasifikasikan set data yang diberikan melalui sejumlah tertentu cluster (diasumsikan k cluster) menentukan prioritas. Gagasan utamanya adalah untuk menetapkan k centroid, satu untuk masing-masing cluster. Centroid ini seharusnya ditempatkan dalam cara yang cerdik karena lokasi yang berbeda menyebabkan hasil yang berbeda pula. Jadi, pilihan terbaik untuk menempatkannya sejauh mungkin satu sama lain. Langkah selanjutnya adalah menjadikan tiap point masuk dalam set data yang diberikan dan mengasosiasikannya ke centroid terdekat. Ketika tidak ada point yang pending, langkah pertama sempurna dan groupage awal selesai. Pada titik ini

83 kita perlu mengkalkulasi ulang k centroid baru sebagai barycenter dari cluster yang didapat dari tahap sebelumnya. Setelah kita mendapatkan k centroid baru ini, ikatan baru harus dilakukan antara data set point yang sama dan centroid baru terdekat. Perulangan dilakukan. Dari hasil perulangan ini kita mungkin memperhatikan bahwa k centroid mengubah lokasinya langkah demi langkah hingga akhirnya tidak ada lagi perubahan yang bisa dilakukan. Dengan kata lain centroid tidak bergerak lagi. Algoritma ini bertujuan pada peminimalan sebuah fungsi obyektif, dalam hal ini fungsi error kuadrat. Fungsi obyektifnya :

adalah ukuran jarak yang dipilih antara data point

dimana pusat cluster

dan

, adalah sebuah indikator jarak pada n data point dari pusat

cluster. Adapun algoritmanya terdiri dari langkah-langkah sebagai berikut : 

Tempatkan k point kedalam ruang yang direpresentasikan oleh obyekobyek yang dikelompokkan. Point ini menerangkan centroid grup awal.



Arahkan tiap obyek ke grup yang memiliki centroid terdekat.



Ketika semua obyek telah diarahkan, hitung ulang posisi dari k centroid.

84 

Ulangi langkah 2 dan 3 sampai centroid tidak lagi bergerak. Hal ini menciptakan pemisahan obyek ke dalam grup yang mana matriks yang diminimalkan dapat dihitung.

2.6.10.1.2.2 QT Clustering Algorithm QT (Quality Threshold) Clustering(Heyer et al,1999) adalah suatu metode alternatif dalam pemisahan data, diciptakan untuk pengelompokan gen. Hal ini memerlukan penetapan yang banyaknya cluster awal, dan selalu menghasilkan hasil yang sama ketika dijalankan berkali – kali. 2.6.10.2 Perhitungan Jarak Sebuah langkah penting dalam pengelompokan adalah dengan memilih sebuah ukuran jarak, yang akan menentukan bagaimana kesamaan dua elemen diperhitungkan. Hal ini akan memperngaruhi bentuk cluster, dimana beberapa elemen mungkin saling berdekatan satu sama lain mengacu pada satu jarak atau saling menjauh. Terdapat sejumlah perhitungan jarak inter-observasi dan jarak intercluster yang berbeda-beda untuk digunakan sebagai criteria saat menggabungkan cluster terdekat kedalam kelompok yang lebih besar atau pada saat menentukan hubungan antara sebuah point ke satu cluster. Perlu diketahui bahwa pada saat dua atau lebih variable digunakan untuk mendefinisikan jarak, variable yang satu dengan magnitudo yang besar akan mendominasi, jadi untuk mencegah hal ini umum dilakukan untuk menstandarisasikan semua variable dahulu. 2.6.10.2.1 The Euclidean Distance Euclidean Distance merupakan pengukur jarak yang paling umum digunakan. Perlu diperhatikan bahwa Euclidean Distance biasanya dihitung dari

85 data yang mentah, dan bukan dari data yang sudah distandarkan. Metode ini memiliki kelebihan tertentu misalnya jarak antara dua obyek tidak dipengaruhi oleh penambahan obyek baru ke dalam analisis. Bagaimanapun, jarak dapat dipengaruhi oleh perbedaan dalam skala antar dimensi dimana jarak diperhitungkan. Euclidean Distance dirumuskan sebagai:

distance(x,y) = {

i

(xi - yi)2 }•

2.6.10.2.2 City Block Distance City Block Distance, dikenal juga dengan nama Block Distance atau Manhattan Distance, merupakan perbedaan rata-rata antar dua atau lebih dimensi yang digunakan untuk menetapkan jarak:

distance(x,y) =

i

|xi - yi|

2.6.10.2.3 Chebychev Distance Pengukur jarak ini cocok digunakan dalam kasus dimana seseorang ingin mendefinisikan dua obyek sebagai suatu perbedaan jika mereka berbeda pada satu dimensi. Chebychev Distance dirumuskan sebagai:

distance(x,y) = Maximum|xi - yi| 2.6.10.2.4 Mahanalobis Distance Pengukur jarak ini diperkenalkan oleh P.C. Mahanalobis pada 1936. Mahanalobis Distance berdasarkan pada korelasi antar variable dimana pola yang berbeda dapat diidentifikasi dan dianalisa. Hal ini merupakan cara yang berguna dalam menentukan kemiripan sample set yang belum diketahui ke yang sudah diketahui. Dirumuskan sebagai:

86

2.6.10.2.5 Hamming Distance Hamming Distance menghitung jumlah minimum dari substitusi yang dibutuhkan untuk mengubah anggota yang satu ke anggota lainnya. Hamming Distance antara dua string dari panjang yang sama adalah jumlah posisi yang mana symbol korespondensinya berbeda. Richard Hamming, yang memperkenalkan Hamming distance dalam makalah fundamentalnya mengenai pendeteksian error dan kode pendeteksian error (1950), memperkenalkan Hamming codes. Kode Hamming ini digunakan dalam bidang telekomunikasi untuk menghitung jumlah bit yang dibalik dalam bentuk biner yang panjangnya tetap sebagai estimasi error, sehingga terkadang disebut juga signal distance. 2.6.10.3 Fuzzy Clustering Fuzzy Clustering merupakan bagian dari ruang lingkup logika fuzzy. Fuzzy Clustering merupakan salah satu tehnik untuk menentukan cluster optimal dalam suatu ruang vector jarak antar vector yang sangat berguna bagi pemodelan fuzzy terutama dalam mengidentifikasi aturan-aturan fuzzy. Dalam Fuzzy Clustering, elemen data dapat berada dalam satu atau lebih cluster, dan asosiasi dengan tiap elemen adalah serangkaian level keanggotaan. Hal ini mengindikasikan kekuatan asosiasi antara elemen data dan cluster tertentu. Fuzzy Clustering adalah sebuah proses menetapkan level keanggotaan ini, dan kemudian menggunakannya untuk menetapkan elemen data ke satu atau lebih cluster.

87 Ada beberapa algoritma Clustering data, diantaranya adalah 

Fuzzy C-Means (FCM) FCM

adalah suatu teknik peng-cluster-an data yang mana

keberadaan tiap-tiap titik data dalam suatu cluster ditentukan oleh derajat keanggotaan. Teknik ini pertama kali diperkenalkan oleh Jim Bezdek pada tahun 1981. Fuzzy C – Means ( FCM ) adalah algoritma pengclusteran yang terawasi, sebab pada FCM kita perlu tahu terlebih dahulu jumlah cluster yang akan dibentuk. Apabila jumlah cluster yang akan dibentuk belum diketahui sebelumnya, maka kita harus menggunakan algoritma yang tidak terawasi. 

Subtractive Clustering Subtractive clustering didasarkan atas ukuran densitas (potensi) titik – titik data dalam suatu ruang (variabel). Konsep dasar dari subtractive clustering adalah menentukan daerah – daerah dalam suatu variabel yang memiliki densitas tinggi terhadap titik – titik di sekitarnya. Titik dengan jumlah tetangga terbanyak akan dipilih sebagai pusat cluster. Titik yang sudah terpilih sebagai pusat cluster ini kemudian akan dikurangi densitasnya. Kemudian algoritma akan memilih titik lain yang memiliki tetangga terbanyak untuk dijadikan pusat cluster yang lain. Hal ini akan dilakukan berulang – ulang hingga semua titik diuji.

2.6.10.4 Fuzzy C-Means (FCM) Algoritma FCM merupakan salah satu algoritma Fuzzy Clustering yang umum digunakan . Tehnik ini diperkenalkan oleh Prof. Jim Bezdek pada 1981.

88 Algoritma FCM mencoba untuk membagi kumpulan elemen X={ ,

, ... ,

}

kedalam koleksi c fuzzy cluster berkenaan dengan criteria yang diberikan. Diberikan set data yang terbatas, algoritma mengembalikan pusat c cluster V dimana V = , i =1, 2, ... , c dan matriks partisi U : U=

, i =1, ..., c, j =1,..., n

dimana

adalah nilai numeric dalam [0,1] yang memberitahukan tingkatan

kemana

masuk ke dalam cluster ke-i.

Algoritma FCM menurut Sri Kusuma Dewi dan Hari Purnomo (2004,p84-85) diberikan sebagai berikut : 1. Input data yang akan di-cluster X, berupa matriks yang berukuran n x m (n = jumlah sample data , m = atribut setiap data). Xij = data sample ke -i (i = 1,2, ... , n), atribut ke -j (j = 1,2, ... , m). 2. Tentukan jumlah cluster (c), pangkat (w), maksimum iterasi (MaxIter), error terkecil yang diharapkan (ξ), fungsi objektif awal (P0 = 0), dan iterasi awal (t = 1). 3. Bangkitkan bilangan random μik, i = 1,2, … , n; k = 1,2, … , c; sebagai elemen – elemen matriks partisi awal U. Hitung jumlah setiap kolom (atribut) : Qj = ( ∑ dari k = 1 hingga c) μik, dengan j= 1,2,…,m. Hitung: μik = μik / Qj

89 4. Hitung pusat cluster ke-k : Vkj, dengan k = 1,2, ... ,c; dan j = 1,2, ... , m. 5. Hitung fungsi obyektif pada iterasi ke – t, Pt 6. Hitung perubahan matriks partisi 7. Cek kondisi berhenti :

2.7



Jika (| Pt – Pt-1 | < ξ) atau (t > MaxIter), maka berhenti;



Jika tidak, t= t+1, ulangi langkah ke – 4.

Genetic Algorithm

2.7.1 Sejarah Simulasi komputer dari evolusi dimulai sejak awal 1954 dengan pekerjaan dari Nils Aall Barricelli, yang menggunakan komputer di Institute of Advanced Study, Princetown, New Jersey. Tetapi, publikasinya pada tahun 1954 tidak diketahui secara luas. Mulai tahun 1957, ahli genetika asal Australia Alex Fraser mempublikasikan beberapa tulisan mengenai simulasi proses seleksi dari organisme dengan beberapa loci yang mengendalikan ancaman/ gangguan yang dapat diukur. Dari awal ini, simulasi komputer dari evolusi biologi menjadi lebih dikenal pada awal 1960, dan metode – metodenya dituliskan dalam beberapa buku oleh Fraser, Burnell(1970), dan Crosy(1973). Simulasi yang dilakukan oleh Fraser mengandung seluruh elemen penting dari algoritma genetika modern. Sebagai tambahan, Hans Bremermann mempublikasikan beberapa tulisan pada tahun 1960 yang juga mengadopsi sebuah populasi dari solusi untuk mengoptimisasi masalah, rekombinasi yang terjadi, mutasi dan seleksi. Penelitian Bremermann juga memasukkan elemen dari modern algoritma genetika. Pelopor awal lainnya yang layak diketahui antara lain Richard Friedberg, George

90 Friedman, dan Michael Conrad yang tulisannya dicetak ulang oleh Fogel pada tahun 1998. Walaupun Barricelli, dalam pekerjaan yang dilaporkannya pada tahun 1963, telah mensimulasikan kemampuan evolusi untuk memainkan permainan sederhana, evolusi buatan menjadi metode optimisasi yang diakui secara luas sebagai suatu hasil pekerjaan dari Ingo Rechenberg dan Hans-Paul Schwefel pada tahun 1960 dan awal 1970 – kelompoknya dapat menyelesaikan masalah teknik yang rumit melalui strategi evolusi. Pendekatan lainnya adalah teknik pemrograman evolusioner dari Lawrence J. Fogel, yang dimaksudkan untuk menentukan

kecerdasan

buatan.

Pemrograman

evolusioner

awalnya

menggunakan mesin finite state untuk memperkirakan lingkungan, dan menggunakan variasi dan seleksi untuk mengoptimisasi predictive logics. Genetic Algorithm menjadi terkenal melalui karya John Holland pada awal 1970, dan bukunya Adaptation in Natural and Artificial System (1975). Karyanya awalnya ditujukan untuk pembelajaran cellular automata, yang dilakukan oleh Holland dan murid – muridnya pada University of Michigan. Holland memperkenalkan framework yang diformalisasikan untuk memperkirakan kualitas dari generasi selanjutnya, yang dikenal sebagai Holland’s Schema Theorem. Penelitian mengenai Genetic Algorithm sebagian besar hanya bersifat teori hingga pertengahan 1980, ketika Konferensi Internasional Pertama mengenai Algoritma Genetika diadakan di Pittsburgh, Pennsylvania. Dengan meningkatnya ketertarikan akademis, perkembangan secara besar dalam kemampuan komputasi desktop memungkinkan untuk percobaan aplikasi dari teknik baru ini. Pada akhir 1980, General Electric mulai menjual produk

91 pertama Genetic Algorithm di dunia, peralatan berbasis mainframe yang ditujukan untuk proses industri. Pada 1989, Axcels,Inc. meluncurkan Evolver, produk Genetic Algorithm kedua di dunia dan pertama untuk komputer desktop yang dituliskan oleh John Markoff , penulis mengenai teknologi untuk New York Times. 2.7.2 Definisi Genetic Algortihm (GA) adalah sebuah teknik pencarian yang digunakan dalam komputasi untuk mencari solusi yang tepat atau hampir tepat untuk optimisasi dan masalah pencarian. Genetic algorithm dikategorikan sebagai pencarian global secara heuristic. Teknik ini merupakan kelas lain dari evolutionary algorithm (juga dikenal sebagai evolutionary computation) yang menggunakan teknik – teknik yang diinspirasikan oleh evolusi dalam biologi seperti penurunan sifat, mutasi, seleksi, cross over (disebut juga rekombinasi). Hal ini dilakukan dengan menciptakan sebuah populasi yang terdiri dari individu-individu yang setiap individunya merepresentasikan kromosom seperti yang terdapat pada DNA kita. Individu-individu pada populasi tersebut kemudian mengalami sebuah proses evolusi. Genetic Algorithm diimplementasikan sebagai sebuah simulasi komputer dimana sebuah populasi dari representasi abstrak (disebut kromosom atau genotype atau genome) dari calon kandidat solusi ( disebut individu atau phenotypes) untuk sebuah optimisasi masalah yang berubah menjadi solusi yang lebih baik. Secara tradisional, solusi direpresentasikan dalam bentuk biner sebagai 0 atau 1, tetapi representasi lain juga dapat dilakukan. Evolusi biasanya

92 dimulai dari populasi dari individu yang ditentukan secara acak dan terjadi di setiap generasi. Pada setiap generasi, kecocokan individu dalam populasi dievaluasi kembali, beberapa individu dipilih dari populasi mereka berdasarkan dari kecocokan mereka dengan fungsi fitness, dan diubah (direkombinasikan dan mungkin bermutasi secara acak) untuk membentuk suatu populasi baru. Populasi baru tersebut kemudian digunakan untuk iterasi selanjutnya dari algoritma. Biasanya, algoritma akan berhenti ketika jumlah maksimum dari generasi telah dihasilkan atau tingkat kecocokan yang telah ditentukan telah terpenuhi untuk populasi tersebut. Jika algoritma tersebut telah berhenti akibat jumlah maksimal dari generasi, sebuah solusi yang memuaskan mungkin belum tercapai. Genetic algorithm dapat digunakan dalam bidang ilmu komputer, ekonomi, kimia, matematika fisika dan bidang – bidang lainnya. Genetic algorithm membutuhkan dua hal untuk ditentukan yaitu sebuah representasi genetika dari wilayah solusi dan fitness function untuk mengevaluasi wilayah solusi. Representasi standar dari solusi adalah sebuah kumpulan bilangan biner. Kumpulan dari tipe lain dan susunan lainnya dapat digunakan dengan cara yang sama. Hal utama yang membuat representasi genetik ini dapat digunakan adalah bagian dimana bagian – bagiannya dapat dengan mudah diatur akibat ukurannya yang tetap, yang memungkinkan operasi persilangan yang sederhana. Representasi dari panjang variabel mungkin juga dapat digunakan, tetapi penggunaan persilangan lebih rumit dalam hal ini. Representasi yang seperti

93 pohon ditemukan dalam pemrograman genetik dan representasi seperti grafik ditemukan dalam pemrograman evolusioner. Fitness function ditentukan berdasarkan representasi genetik dan menentukan kualitas dari solusi yang direpresentasikan. Fitness function adalah sebuah masalah yang tergantung pada hal lain. Sebagai contoh, dalam masalah knapsack dalam memaksimalkan nilai total dari obyek – obyek yang diletakkan dalam sebuah knapsack dengan kapasitas yang ditentukan. Representasi dari sebuah solusi mungkin berupa array of bits dimana setiap bit merepresentasikan objek yang berbeda dan nilai dari bit (0 atau 1) merepresentasikan apakah suatu obyek berada dalam knapsack atau tidak. Tidak setiap representasi berlaku karena ukuran dari obyek – obyek mungkin melebihi kapasitas dari knapsack. Kecocokan dari solusi merupakan jumlah nilai dari seluruh obyek dalam knapsack bila representasinya berlaku, atau jika 0 hal yang sebaliknya yang terjadi. Dalam beberapa masalah, terdapat kesulitan atau bahkan tidak mungkin untuk menentukan kecocokan; dalam hal ini genetic algorithm yang interaktif digunakan. Ketika kita memiliki representasi genetik dari fitness function telah ditentukan, GA akan melanjutkan operasi selanjutnya yaitu menginisialisasi sebuah populasi dari solusi secara acak, kemudian mengembangkannya melalui aplikasi yang berulang – ulang dari operator mutasi, persilangan, pembalikan dan seleksi.

94 Pada tahap inisialisasi, awalnya beberapa individu solusi ditentukan secara acak untuk membentuk populasi awal. Ukuran populasi bergantung pada sifat dari masalah, tetapi biasanya berisi beberapa ratus atau beberapa ribu solusi yang memungkinkan. Secara tradisional, populasi ditentukan secara acak, dan mengandung seluruh daerah dari solusi yang memungkinkan (daerah pencarian). Biasanya, solusi – solusi mungkin tersebar di daerah dimana solusi yang optimal mungkin ditemukan.

Pada tahap seleksi, pada setiap generasi turunan, sebagian dari populasi yang ada dipilih untuk membuat generasi yang baru. Individu solusi dipilih melalui proses berdasarkan sebuah fitness, dimana solusi yang lebih cocok (seperti yang diukur oleh sebuah fitness function) lebih mungkin untuk dipilih. Metode pemilihan yang pasti memperkirakan kecocokan dari setiap solusi dan menentukan ke arah mana solusi yang paling baik berada. Metode lain hanya memperkirakan sebuah contoh acak dari populasi dan tentu saja proses ini mungkin memakan lebih banyak waktu. Sebagian besar fungsi dirancang dan dibuat sedemikian rpa sehingga sebagian kecil dari solusi yang kurang cocok terpilih. Ini membantuk untuk menyimpan penyimpangan dari populasi yang besar, menghindari konvergensi awal dari solusi yang kurang baik.

Langkah yang selanjutnya diambil adalah menentukan generasi kedua dari populasi solusi dari individu yang terpilih melalui operator genetik yaitu persilangan (yang juga disebut rekombinasi), dan / atau mutasi. Untuk setiap solusi yang baru yang dihasilkan, sepasang “induk” dari solusi dipilih untuk menghasilkan keturunan dari penampung yang telah dipilih sebelumnya. Dengan

95 memproduksi keturunan solusi menggunakan metode – metode persilangan dan mutasi tersebut, solusi baru tercipta yang biasanya memiliki karakteristik dari induknya. Induk baru dipilih untuk setiap keturunan, dan proses tersebut berlanjut hingga sebuah populasi baru dari solusi dengan ukuran yang telah ditentukan tercipta. Proses ini menghasilkan kromosom dari generasi selanjutnya yang berbeda dengan generasi awal. Biasanya rata – rata fitness akan meningkat dengan prosedur ini untuk populasi, akibat hanya organime terbaik dari generasi pertama yang dipilih untuk peranakan, dan akibat digunakannya sebagian kecil dari solusi yang kurang cocok, untuk alasan - alasan yang telah disebutkan di atas.

Crossover

Gambar2.33. Proses terjadinya crossover Mutation

Gambar 2.34. Proses terjadinya mutasi (mutation) Proses di atas diulangi secara terus menerus hingga kondisi untuk terminasi telah tercapai. Kondisi – kondisi yang berhenti biasanya antara lain sebuah solusi telah ditemukan yang memenuhi kriteria minimum yang telah

96 ditentukan, jumlah generasi yang telah ditentukan telah tercapai, fitness untuk solusi dengan tingkatan tertinggi telah didapat atau telah didapat kondisi dimana iterasi selanjutnya tidak menghasilkan hasil yang lebih baik, pengamatan secara manual, atau kombinasi dari hal – hal yang telah disebutkan tersebut. GA bekerja sesuai dengan langkah-langkah seperti di bawah ini: 1. Tentukan jumlah individu (kromosom) dari sebuah populasi. 2. Mengetes setiap kromosom tentang seberapa baik kromosom tersebut dalam menyelesaikan masalah yang sedang kita hadapi. 3. Pilih dua kromosom dari populasi tersebut secara acak dengan Sesuai dengan crossover rate akan terdapat kemungkinan menggunakan metode roulette. 4. terjadinya crossover pada sebuah titik yang acak. 5. Sesuai dengan mutation rate akan terdapat kemungkinan terjadinya mutasi yang akan mengubah kode genetik dari sebuah kromosom. 6. Ulangi tahap 2 sampai 5

hingga didapatkan kembali jumlah

kromosom yang sesuai dengan populasi yang semula. 7. Ulangi tahap 2 sampai 6 hingga tercapai solusi terbaik atau telah mencapai jumlah generasi yang telah ditentukan.

97 2.8

Evolutionary Programming

2.8.1 Pengenalan Evolutionary Programming, diusulkan oleh Lawrence J. Fogel pada tahun 1960, merupakan sebuah strategi optimasi stokhastik yang mirip dengan Genetic Algorithm, tetapi lebih menekankan pada hubungan sifat antara induk dan anak , dari pada mengemulasikan operator genetik tertentu seperti yang terjadi di alam. Evolutionary Programming mirip dengan Evolution Strategy, walaupun kedua pendekatan tersebut berkembang masing-masing. Seperti ES dan GA, EP merupakan sebuah metode optimasi di mana ketika teknik-teknik lain seperti gradien turunan atau langsung, penemuan analisis tidak memungkinan. Fungsi optimasi kombinatorik dan bernilai riil di mana permukaan optimasi atau grafik fitness bergelombang, memiliki banyak solusi-solusi local optima, sangat cocok untuk Evolutionary Programming. 2.8.2 Sejarah Buku pada tahun 1996, "Artificial Intelligence Through Simulated Evolution" oleh Fogel, Owens dan Walsh merupakan publikasi pertama untuk aplikasi EP, walaupun banyak paper-paper lain yang sudah ada sebelumnya. Pada buku tersebut, finite state automata dievolusikan untuk memprediksikan rangkaian simbol yang dihasilkan oleh proses-proses Markov dan urutan waktu yang berubah-ubah. Prediksi evolusionari seperti itu dimotivasi oleh sebuah pengakuan bahwa prediksi merupakan sebuah kunci dalam perilaku yang cerdas

98 (didefinisikan dalam konteks perilaku adaptif, di mana organisme cerdas harus mengantisipasi kejadian-kejadian untuk dapat mengadaptasikan perilaku untuk mencapai sebauh tujuan). Pada tahun 1992, Konferensi tahunan pertama tentang Evolutionary Programming diadakan di La Jolla, CA.

Konferensi-konferensi selanjutnya

telah diadakan setiap tahun. Konferensi-konferensi tersebut menarik perhatian grup-grup akademik yang beragam, peneliti-peneliti komersial dan militer yang melakukan pegembangan teori EP dan mengimplementasikan EP untuk masalahmasalah optimasi yang beragam, baik pada bidang engineering dan biologi. 2.8.3 Proses Untuk EP, seperti GA, terdapat sebuah asumsi bahwa sebuah grafik fitness dapat dikarakterisasi pada konteks variabel, dan sebuah solusi optimal sesuai dengan konteks variabel tersebut. Sebagai contoh, jika seseorang ingin mencari jalur terpendek dalam TSP, setiap solusi merupakan sebuah jalur. Panjang dari jalur tersebut dapat diekspresikan dalam sebuah angka, yang akan digunakan sebagai fitness dari solusi tersebut. Grafik fitness untuk masalah ini dapat dikarakterisasikan sebagai permukaan atas yang proporsional dengan panjang jalur dalam kumpulan jalur-jalur yang memungkinkan. Tujuannya adalah untuk mencari sebuah jalur terpendek yang optimal dalam kumpulan solusi tersebut, atau lebih praktisnya, untuk mencari jalur paling pendek dengan sangat cepat.

99 Metode dasar EP tediri dari 3 langkah (Ulang sampai sebuah threshold untuk iterasi telah terlebihi atau solusi yang diinginkan telah tercapai): 1. Pilih populasi awal secara acak. Jumlah dari solusi pada sebuah populasi memiliki relevansi yang erat dengan kecepatan optimasi, tetapi tidak ada jawaban yang pasti mengenai berapa banyak yang seharusnya terdapat pada sebuah populasi. 2. Setiap solusi direplikasi menjadi sebauh populasi yang baru. Masing-masing dari solusi anak ini mengalami mutasi menurut sebuah tipe distribusi mutasi, dengan skala minor sampai ekstrim dengan tipe mutasi kontinuum di antaranya. Skala dari mutasi ditentukan oleh perubahan fungsional dari induk. 3. Setiap solusi anak akan dievaluasi dengan menghitung fitness-nya. Biasanya,

sebuah

turnamen

stokhastik

diadakan

untuk

menentukan N solusi yang akan dipertahankan untuk populasi solusi, meskipun biasanya hal ini dilakukan secara deterministik. Tidak ada syarat bahwa ukuran populasi harus tetap, tetapi, juga tidak ada batasan bahwa setiap induk menhasilkan sebuah solusi anak. 2.8.4 Evolutionary Programming dan Genetic Algorithm Ada dua perbedaan utama antara EP dan GA:.

100 Pertama tidak ada batasan dalam representasi. Pendekatan umum GA terdiri dari mengubah solusi masalah menjadi sebuah rangkaian dari simbol representatif, Genome. Pada EP, representasinya mengikuti masalahnya. Sebuah jaringan saraf dapat direpresentasikan dengan cara yang sama dengan bagaimana jaringan tersebut bekerja, contohnya, karena operasi mutasi tidak membutuhkan perubahan (encoding) yang linear. (Dalam kasus ini, topologi yang tetap, weight yang bernilai riil dapat diubah langsung sebagai nilai riil-nya dan mutasi terjadi dengan mengubah vektor weight dengan menambahkan derau Gaussian dengan nilai rata-rata nol (zero mean Gaussian mutation). Untuk topologi yang berubahubah sering digunakan penembahan dan pengurangan terdistribusi Poisson). Kedua, operasi mutasi mengubah aspek dari solusi sesuai dengan distribusi. Selanjutnya, skala mutasi sering kali berkurang seiring dengan tercapainya global optima.