Sukses Beralgoritma

SUKSES BERALGORITMA SRY WAHYUNI Sukses beralgoritma 2012 i KATA PENGANTAR Puji dan syukur penulis panjatkan ke kehadirat Tuhan Yang Maha Kuasa, karena atas berkat dan rahmat-Nyalah sehingga penulis dapat menyelesaikan penulisan buku ini dengan judul “Sukses Beralgoritma”. Buku ini merupakan pengalaman yang sangat berharga, meskipun dalam penyusunannya menemui banyak hambatan dan masih terdapat banyak kekurangan di dalamnya. Kritik dan saran sangat diharapkan untuk kesempurnaan buku ini. Dengan segala kerendahan dan ketulusan hati penulis ucapkan terima kasih yang begitu besar kepada Tuhan Yesus Kristus yang telah membimbing dan menyertai penulis untuk tetap sabar dan setia dalam penulisan buku ini bahkan selama perkuliahan. Tak lupa juga trima kasih yang sebesar-besarnya kepada semua pihak khususnya dosen yang senantiasa mendukung penulis selama proses perkuliahan. Dalam kesempatan ini pula penulis menyampaikan rasa syukur dan terima kasih atas segala bantuan, kerja sama dan dukungan selama ini sehingga penulis dapat mencapai kesuksesan menyelesaikan penyusunan buku ini. Penulis menyadari bahwa buku ini masih jauh dari kesempurnaan sehingga saran dan masukan yang sifatnya membangun dari semua pihak sangat saya hargai. Akhir kata penulis menaruh harapan besar semoga buku ini dapat memberikan manfaat bagi semua pihak. Makassar, Oktober 2012 Penulis Sukses beralgoritma 2012 ii DAFTAR ISI KATA PENGANTAR…………………………………………………. i DAFTAR ISI ...................................................................................... ii TENTANG PENULIS...................................................................... iii BAB I PENGANTAR ALGORITMA A. DEFINISI ALGORITMA .................................................. 2 B. DESAIN ALGORITMA .................................................... 2 C. ANALISIS ALGORITMA…………………….…………... 4 BAB II PERANCANGAN ALGORITMA A. MASALAH PENCARIAN DATA.................................. 6 B. PENCARIAN BISEKSI (BAGI-DUA).......................... 8 C. BINARY SEARCH TREE (BST)………….................... 12 BAB III ALGORITMA MERGE SORT A. MERGE SORT................................................................... 16 B. RECURRENCE ................................................................ 22 BAB IV STRATEGI ALGORITMA (I) A. METODE GREEDY ........................................................ 28 B. DYNAMIC PROGRAMMING …................................... 30 BAB V STRATEGI ALGORITMA (II) A. ALGORITMA METAHEURISTIK................................ 38 B. ALGORITMA GENETIKA……..…................................. 39 C. JARINGAN SYARAF TIRUAN………………………… 53 DAFTAR PUSTAKA………………............................................... 59 Sukses beralgoritma 2012 iii TENTANG PENULIS Sry Wahyuni lahir di Makale, 22 Januari 1993. Putri ketiga pasangan Eliusat Loly – Orpha Saranga’ ini tengah menempuh pendidikan di Universitas Hasanuddin, Prodi statistika, Jurusan Matematika, Fakultas MIPA. Alumni SMAN 1 Makale ini memulai pendidikannya di Unhas semenjak tahun 2011. Kini ia berada di tahun kedua (semester 3). Dengan memiliki visi-misi dan konsentrasi hidup yaitu “hidup sukses” , ia menulis buku ini dengan judul “sukses beralgoritma”. Harapan agar setiap orang mendapatkan terobosan pemahaman yang sangat bermakna ketika setiap orang membaca buku ini. Ini adalah buku pertama yang ia tulis disertakan harapan agar boleh menginspirasi setiap orang yang ingin belajar algoritma. Sry Wahyuni terlahir dari keluarga sederhana dan bahagia. Dengan kasih sayang orang tua yang membesarkannya, ia sekarang tumbuh menjadi seorang mahasiswa yang diharapkan dapat mengharumkan nama keluarga tercinta. Gadis periang ini juga diberkahi kasih sayang dari dua pria penyayang di sisinya. Sebut saja Ellya dan Melky, dua orang kakak yang juga turut mengambil bagian dalam perjalanan kehidupannya menuju kedewasaan , kebahagiaan dan kesuksesan. Akhir kata, penulis mengungkapkan kebahagian atas segala pengalaman yang ia rasakan selama penulisan buku ini. Selamat membaca. Yeshua Hamasiah Bless. Cheers Sukses beralgoritma 2012 1 BAB 1 PENGANTAR ALGORITMA Sukses beralgoritma 2012 2 A. DEFINISI ALGORITMA  Prosedur komputasional yang terdefinisi dengan baik yang membutuhkan nilai (atau himpunan nilai) sebagai input dan menghasilkan nilai (atau himpunan nilai) sebagai output  Alat bantu (tools) menyelesaikan masalah komputasional yang terdefinisi dengan baik (well-defined computational problem)  Metode penyelesaian yang logis dan ‘wajib’ benar (correctness) sesuai keinginan masalah (desired solution) B. DESAIN ALGORITMA – Pseudocode: Kode untuk memudahkan pemahaman algoritma yang dapat ditransformasi kedalam berbagai Bahasa Pemrograman. – Kompleksitas algoritma: Analisis kebutuhan dari algoritma, khususnya waktu komputasi dan kapasitas memory. – Strategi algoritma: Perancangan kadang membutuhkan strategi perancangan algoritma tertentu. Dalam kuliah ini: Greedy algorithm, divide-and-conquer, dynamic programming dan strategi-strategi algoritma meta-heuristik untuk masalah optimisasi. Ketentuan pseucode: • Indent menyatakan struktur blok. • Statemen perulangan dikonstruksi dengan while, for dan repeat. • Statemen penyeleksian kondisi/syarat dikonstruksi dengan if, then dan else. • Simbol “^” menyatakan komentar untuk statemen baris-baris berikutnya. • Penugasan berganda (multiple assignment) i ÷ j ÷ e menyatakan penugasan/pemberian nilai e kedalam i dan j; pernyataan ini ekivalen dengan i ÷ j lalu diikuti j ÷ e. Alogritma Insertion-Sort Insertion-Sort(A) perulangan untuk patokan 1. for to 2. key 3. Sisip A[j] ke dalam barisan terurut A[1..j-1] 4. 5. while ⋀ 6. 7. 8. Sukses beralgoritma 2012 3 Contoh kasus pengurutan data: Barisan bilangan A (31,41,26,35). Urutkan data dari terkecil ke terbesar! Untuk j = 2 to 4 (j=2) -> key=A[2]=41 i=2-1=1 ketika ( i=1 > 0 A[2] > key=41) T F A[2]=key (j=3) -> key=A[3]=26 i=3-1=2 ketika ( i=2 > 0 A[2] > key=26) T T 26 A[3]=A[2] i=2-1=1 ketika ( i=1 > 0 A[1] > key=26) T T A[2]=A[1] 26 (j=4) -> key=A[4]=35 i=4-1=3 ketika ( i=3 > 0 A[3] > key=35) T T 35 A[4]=A[3] i=3-1=2 ketika ( i=2 > 0 A[2] > key=35) T F 31 41 26 35 31 41 41 35 31 31 41 35 26 31 41 41 26 31 35 41 Sukses beralgoritma 2012 4 A[3]=key i=2-1=1 ketika ( i=1 > 0 A[1] > key=35) T F A[3]=key (j=5) -> key=A[5] (proses berhenti karena tidak ada A[5]) C. ANALISIS ALOGRITMA • Kasus Terbaik Suatu alogritma dikatakan kasus terbaik pada saat statementnya atau pernyataannnya terpenuhi dan t = 1. Laju komputasinya dalam fungsi linier. ∑ • Kasus Terburuk Suatu alogritma dikatakan kasus terburuk pada saat statementnya atau pernyataannnya tidak terpenuhi dan t = 0. Laju komputasinya dalam fungsi kuadratik. ∑ ( ) ( ) 26 31 35 41 Sukses beralgoritma 2012 5 BAB 2 PERANCANGAN ALGORITMA Sukses beralgoritma 2012 6 A. MASALAH PENCARIAN DATA Searching problem Input : Barisan n bilangan asli (a1, a2, …, an) dalam larik A dan sebuah bilangan key yang ingin dicari. Output : Lokasi key dalam A. Jika key tidak ditemukan dalam A, tambahkan key sebagai unsur terakhir. Contoh: Input barisan bilangan: A = (31, 41, 59, 26, 41, 58) dan key = 26. Algoritma pencarian (searching algorithm), output menghasilkan posisi key adalah 4. Pencarian Linier Linear-Search(A, key) cost times 1 ada ÷ False c1 1 2 for i ÷ 1 to length[A] c2 n + 1 3 if A[i] = key then c3 n 4 posisi ÷ i c4 ¿ = n i i t 1 5 ada ÷ True c5 ¿ = n i i t 1 6 if not(ada) then c6 1 7 posisi ÷ length[A] + 1 c7 s 8 A[posisi] ÷ data C8 S ) 3 2 ( 2 2 ) ( 1 + + + = ¿ = s t n n T n i i ada ÷ False Pernyataan ini ditentukan di awal, yakni merupakan penentu pada kondisi awal. Bagian ini di proses sebanyak 1 kali. Karena hanya satu kali ditentukan pada bagian awal. for i ÷ 1 to length[A] Di sini length[A]=n. Pada bagian ini, akan diproses sebanyak n+1, karena data yang ada sebanyak n, dan 1 untuk mengecek kembali, apakah i yang selanjutnya masih memenuhi length [A], dengan kata lain bahwa sudah tidak ada unsur setelah n. if A[i] = key then Waktu komputasinya sebanyak n. Karena ada n data yang akan di uji apakah nilainya sama dengan key. Sukses beralgoritma 2012 7 posisi ÷ i Waktu komputasinya adalah ¿ = n i i t 1 . dimana nilai t sangat tergantung pada n (jumlah / panjang data) yang terkesekusi. Apabila i=1 maka , jika i = 2 maka dan seterusnya sampai banyaknya data. ada ÷ True Untuk pernyataan di atas terlihat bahwa tereksekusi sebanyak ∑ dimana nilai t juga tergantung pada n yang tereksekusi dan bernilai benar. if not(ada) then Pernyataan di atas akan tereksekusi sebanyak 1 kali, karena merupakan kondisi awal juga, ketika key tidak ditemukan pada barisan data yang tersedia. posisi ÷ length[A] + 1 Pernyataan di atas akan tereksekusi sebanyak s kali. Dalam hal ini, s adalah sebuah variabel bebas. Pernyataan ini akan dieksekusi apabila key yang dicari tidak ditemukan dalam barisan bilangan. Namun jika key ada, maka pernyataan ini akan dilangkahi. A[posisi] ÷ data Pernyataan di atas juga akan tereksekusi sebanyak s kali. Pernyataan ini merupakan lanjutan dari pernyataan di atasnya. Jika pernyataan di atas tereksekusi sebanyak s kali maka pernyataan ini juga akan turut tereksekusi. KASUS TERBAIK DAN KASUS TERBURUK a) Kasus Terburuk: Semua unsur dalam larik A sama dengan key. (Dalam hal ini, n t n i i = ¿ =1 dan s = 0) Untuk kasus terburuk terjadi ketika . Contohnya: Diberikan data 23,23,23,23 dengan Key=23 Setiap unsur akan mengeksekusi setiap pernyataan berulang-ulang sebanyak n. 3 4 ) 3 2 ( 2 2 ) ( 1 + = + + + = ¿ = n s t n n T n i i b) Kasus Terbaik: Tidak terdapat satu pun unsur dalam larik A sama dengan key. (Dalam hal ini, 0 1 = ¿ = n i i t dan s = 1) Dalam hal ini, semua data akan dieksekusi sebanyak satu kali. Namun key yang dicari tidak ditemukan dalam barisan data. Misalnya A = 23, 45, 67, 87 dan key = 90 maka sintaks-sintaks akan di proses hingga terakhir. 5 2 ) 3 2 ( 2 2 ) ( 1 + = + + + = ¿ = n s t n n T n i i Sukses beralgoritma 2012 8 CONTOH A = (31, 41, 59, 26, 41, 58) , Key = 26 URAIAN PSEUCODE: ada ÷ False for i ÷ 1 to length[A] karena length [A]=6, maka akan menjadi for i=1 to 6 for i ÷ 1 to 6 if A[i] = key if 31 = key (FALSE) then Karena pernyataan if 31 = Key bernilai “FALSE” maka eksekusi dilanjutkan for i ÷ 2 to 6 if A[i] = key if 41 = key (FALSE) then Karena pernyataan if 41 = Key bernilai “FALSE” maka eksekusi dilanjutkan. for i ÷ 3 to 6 if A[i] = key if 59 = key (FALSE) then Karena pernyataan if 59 = Key bernilai “FALSE” maka eksekusi dilanjutkan for i ÷ 4 to 6 if A[i] = key if 26 = key (TRUE) then posisi ÷ 4 ada ÷ True Karena pernyataan if 26 = Key bernilai “TRUE” maka eksekusi dihentikan pada posisi A[4], Sehingga output akan menghasilkan posisi key adalah 4. B. PENCARIAN BISEKSI (BAGI-DUA) Metode pencarian bagidua atau pencarian biner (binary search). Metode ini digunakan untuk kebutuhan pencarian dengan waktu yang cepat. Prinsip metode ini adalah membagi dua data. Kemudian data dicari secara bersamaan dari dua sisi, yakni Sukses beralgoritma 2012 9 dari depan dan belakang. Hal ini dimaksudkan agar waktu komputasi lebih cepat dan efisien. Bisection-Search(A, key) cost times 1 ada ÷ False c 1 1 2 for i ÷ 1 to length[A] /2( c 2 ½ n + 1 3 if A[i] = key then c 3 ½ n 4 posisi ÷ i c 4 ¿ = 2 1 n i i t 5 ada ÷ True c 5 ¿ = 2 1 n i i t 6 if A[n – i + 1] = key then c 6 ½ n 7 posisi ÷ n – i + 1 c 7 ¿ = 2 1 n i i p 8 ada ÷ True c 8 ¿ = 2 1 n i i p 9 if not(ada) then c 9 1 10 posisi ÷ length[A] + 1 c 10 s 11 A[posisi] ÷ data c 11 s ) 3 2 ( 2 2 ) ( 2 2 1 1 2 3 + + + + = ¿ ¿ = = s p t n n T n n i i i i ada ÷ False Pernyataan ini ditentukan di awal, yakni merupakan penentu pada kondisi awal. Bagian ini di proses sebanyak 1 kali. Karena hanya satu kali ditentukan pada bagian awal. for i ÷ 1 to length[A] /2( Pernyataan ini akan tereksekusi sebanyak 1/2 n+1. Maksudnya adalah tereksekusi sebanyak n ½ (Jumlah/panjang data dibagi dua), dibagi dua agar dalam satu waktu bisa dilakukan dua perintah sekaligus yaitu dari unsur paling depan dan belakang, sedangkan + 1 untuk mengecek kembali bahwa ⁄ adalah unsur terakhir dari deret tersebut (tidak ada unsur lain lagi). Digunakan tanda ( ) pada for i ÷ 1 to length[A] /2( artinya dilakukan pembulatan ke atas. if A[i] = key then Pernyataan ini akan tereksekusi sebanyak ⁄ , maksudnya adalah tereksekusi sebanyak ⁄ (jumlah data/panjang data dibagi dua), dibagi dua agar dalam satu waktu dapat dikerjakan dua perintah sekaligus. Dalam hal ini pernyataan di atas merupakan perintah eksekusi unsur pada bagian depan. Sukses beralgoritma 2012 10 posisi ÷ i Pada pernyataan di atas terlihat bahwa tereksekusi sebanyak ∑ dimana nilai t sangat tergantung pada ⁄ (jumlah / panjang data dibagi dua) yang tereksekusi. Dalam hal ini bukan nilai n pada awal melainkan n yang tereksekusi, misalnya dari panjang ⁄ = 3 namun yang hanya terkeksekusi adalah ⁄ =2 maka running timenya dapat di tulis ∑ ada ÷ True Pernyataan ini akan tereksekusi sebanyak ∑ dimana nilai t juga tergantung pada ⁄ yang tereksekusi dan bernilai benar, misalnya pada barisan 25,25,25,31 dan key=25 maka ada ÷ True akan tereksekusi sebanyak ∑ if A[n – i + 1] = key then Pernyataan ini akan tereksekusi sebanyak ⁄ , maksudnya adalah tereksekusi sebanyak ⁄ (jumlah data/panjang data dibagi dua), dibagi dua agar dalam satu waktu dapat dikerjakan dua perintah sekaligus. Dalam hal ini pernyataan di atas merupakan perintah eksekusi unsur pada bagian belakang. posisi ÷ n – i + 1 Pernyataan ini akan tereksekusi sebanyak ∑ dimana nilai t sangat tergantung pada ⁄ (jumlah / panjang data dibagi dua) yang terkesekusi. Dalam hal ini bukan nilai ⁄ pada awal melainkan ⁄ yang tereksekusi, misalnya dari panjang ⁄ = 3 hanya terkeksekusi ⁄ maka running timenya dapat di tulis ∑ . ada ÷ True Pernyataan ini akan tereksekusi sebanyak ∑ dimana nilai t juga tergantung pada ⁄ yang tereksekusi dan bernilai benar, misalnya pada barisan 21,21,21,31 dan key=21 maka ada ÷ True akan tereksekusi sebanyak ∑ , karena pada saat ⁄ ⁄ =2 bernilai benar (ada ÷ True). if not(ada) then Pernyataan ini akan tereksekusi sebanyak 1 kali, karena merupakan kondisi awal juga, ketika key tidak ditemukan pada barisan yang tersedia. posisi ÷ length[A] + 1 Pernyataan ini akan tereksekusi sebanyak s, dalam hal ini tergantung pada pernyataan di atas, jika pernyataan tersebut terpenuhi maka akan di eksekusi sebanyak s. A[posisi] ÷ data Pernyataan ini akan tereksekusi sebanyak s, dalam hal ini jika pernyataan 9 terpenuhi makan pernyataan di atas juga dapat terpenuhi sehingga akan dieksekusi sebanyak s. Sukses beralgoritma 2012 11 CONTOH: A= (31, 41, 59, 26, 41, 58) dan key = 26 URAIAN PSEUCODE: ada ÷ False for i ÷ 1 to length[A]/2 karena length [A]=6, maka akan menjadi for i=1 to 3 for i ÷ 1 to 3 (dari depan) if A[1] = key then if 31 = key then (FALSE) (dari belakang) if A[6] = key then if 58 = key then (FALSE) Karena pernyataan masih bernilai salah (ada ÷ False) maka eksekusi dilanjutkan. for i ÷ 2 to 3 (depan) if A[2] = key then if 41 = key then (FALSE) (belakang) if A[5] = key then if 41 = key then (FALSE) Karena pernyataan masih bernilai salah (ada ÷ False) maka eksekusi dilanjutkan. for i ÷ 3 to 3 (depan) if A[3] = key then if 59 = key then (FALSE) (belakang) if A[4] = key then if 26 = key then (TRUE) posisi ÷ 4 ada ÷ True Sukses beralgoritma 2012 12 Karena pernyataan bernilai benar (ada ÷ True) maka eksekusi dihentikan pada posisi A[4], sehingga output menghasilkan posisi Key adalah 4. Kasus Terbaik Dan Kasus Terburuk  Kasus Terburuk: Semua unsur dalam larik A sama dengan key. (Dalam hal ini, 2 1 2 1 2 2 , n i i n i i n n p t = = ¿ ¿ = = dan s = 0) Untuk kasus terburuk terjadi ketika Kasus ini terjadi bila nilai dari larik A itu sama semua dengan key yang ditentukan. Misalnya A = 36, 36, 36, 36 dan key = 36. Maka setiap unsur akan mengeksekusi semua unsur ini secara berulang sebanyak . 3 ) 3 2 ( 2 2 ) ( 2 7 1 1 2 3 2 2 + = + + + + = ¿ ¿ = = n s p t n n T n n i i i i  Kasus Terbaik: Terdapat tepat satu unsur dalam larik A sama dengan key. (Dalam hal ini, 1 atau 1 2 2 1 1 = = ¿ ¿ = = n n i i i i p t dan s = 0) untuk kasus terbaik terjadi ketika contoh kasus: Diberikan barisan bilangan 21,31,41,51,61,71 dengan key = 61 Untuk unsur yang tidak sama dengan key yaitu i = 1 dan 3 (A[1],A[3],A[4],A[6] ) tidak perlu mengeksekusi pernyataan. Namun langsung saja pada pernyataan, kecuali untuk i = 2 (A[2],A[5]. Maka deperoleh sehingga disebut sebagai kasus terbaik. 5 ) 3 2 ( 2 2 ) ( 2 3 1 1 2 3 2 2 + = + + + + = ¿ ¿ = = n s p t n n T n n i i i i Dengan metode ini (bagi-dua) maka membuat waktu komputasi (running time) pencarian data menjadi lebih cepat. Namun pengembangan alamiah hanya mengurangi ½ + ¼ + 1/8 + 1/16 dari jumlah data n. C. BINARY SEARCH TREE (BST) • Struktur Data: Prosedur penyimpanan data dalam bentuk tertentu sedemikian sehingga operasi dasar pada algoritma menjadi lebih efisien atau optimal. • Pohon biner adalah pohon yang setiap simpulnya memiliki anak paling banyak berjumlah 2. Anak-anak tersebut dibedakan antara anak kiri (left child) dan anak kanan (right child). Karena ada perbedaan urutan anak, maka pohon biner adalah pohon terurut. Pohon biner merupakan jenis pohon yang paling populer karena sering dimanfaatkan. Pohon biner memang memiliki banya aplikasi, misalnya dalam sorting atau untuk menghitung hasil evaluasi suatu ekspresi aritmatika. Sukses beralgoritma 2012 13 • Metode Binary searh tree lebih memudahkan kita dalam masalah pencarian data, dengan cara yang mudah yaitu bagi unsur ke dalam dua sisi, sisi kiri untuk unsur yang lebih kecil sedangkan sisi kanan untuk unsur yang lebih besar. Contoh kasus: Diberikan barisan bilangan 36, 34, 35, 32, 38, 37, 39 dengan Key =37, tunjukan dengan metode Binary Search Tree! 1. Di sini yang menjadi patokan adalah 36. 2. Masukkan angka yang lebih kecil untuk sisi kiri, dan angka yang lebih besar untuk sisi kanan. Mulailah melakukan pencarian data, mulai dari atas. Jika bilangan yang dicari lebih kecil, maka cari ke arah (cabang) bagian kiri. Namun jika bilangan yang dicari lebih besar, maka carilah ke arah kanan. Begitu selanjutnya sampai diperoleh key yang dicari. Diperoleh Langkah 1: Karena key(37)>36, maka kita cari ke arah kanan Langkah 2: Karena key(37)1, maka : a. DIVIDE: bagi table a menjadi dua bagian, bagian kiri dan bagian kanan, masing- masing bagian berukuran n/2 elemen. b. CONQUER: secara rekursif, terapkan algoritma D-and-C pada masing-masing bagian. c. MERGE: gabung hasil pengurutan kedua bagian sehingga diperoleh table a yang terurut. Dengan menerapkan kedua aturan diatas secara terus menerus maka nantinya akan didapatkan list yang terurut. Pseudo Code untuk algoritma MergeSort adalah sebagai berikut: Sukses beralgoritma 2012 17 Untuk menyederhanakan perhitungan kompleksitas waktu MergeSort, kita membuat asumsi ukuran tabel adalah perpangkatan dari 2, yaitu n= dengan k adalah bilangan bulat positif . Kompleksitas waktu dihitung dari jumlah perbandingan dengan elemen- elemen tabel. T(n) = jumlah perbandingan pada pengurutan dua buah subtabel + jumlah perbandingan pada prosedur Merge. Kompleksitas prosedur Merge adalah t(n) = cn = O(n), sehingga kompleksitas algoritma Merge Sort menjadi (dalam bentuk relasi rekurens): { ( ) dalam hal ini,a dan c adalah konstanta. Penyelesaian persamaan rekurens: T(n) =T(n/2)+cn = 2(2T(n/4) + cn/2) + cn = 4T(n/4) + 2cn = 4(2T(n/8) + cn/4) + 2 cn = ... = 2k T(n/2k)+kcn Divide and Conquer merupakan algoritma yang berprinsip memecah-mecah permasalahan yang terlalu besar menjadi beberapa bagian kecil sehingga lebih mudah untuk diselesaikan. Langkah-langkah umum algoritma Divide and Conquer :  Divide : Membagi masalah menjadi beberapa upa-masalah yang memiliki kemiripan dengan masalah semula namun berukuran lebih kecil ( idealnya berukuran hampir sama ).  Conquer : Memecahkan ( menyelesaikan ) masing-masing upa-masalah ( secara rekursif ).  Combine : Menggabungkan solusi masing-masing upa-masalah sehingga membentuk solusi masalah semula. Merge sort pseucode Merge-Sort(A, p, r): if p < r then q¬(p+r)/2 Merge-Sort(A, p, q) Merge-Sort(A, q+1, r) Merge(A, p, q, r) Sukses beralgoritma 2012 18 if p < r then Bagian ini di proses sebanyak O(1). q¬(p+r)/2 Pernyataan ini akan dieksekusi sebanyak n/2. Karena data dibagi dua. Merge-Sort(A, p, q) Merge-Sort(A, q+1, r) Pernyataan ini waktu komputasinya adalah T(n/2). Pada bagian ini merupakan proses divide yaitu data dipecah (dibagi-bagi) hingga potongan terkecil. Merge(A, p, q, r) Pernyataan ini waktu komputasinya adalah O(n). Bagian ini merupakan proses combine, yaitu data digabungkan kembali. Contoh kasus: Penyelesaian dengan dengan Divide and Conquer. Misalkan tabel A berisi elemen-elemen sebagai berikut: A= 4 12 23 9 21 1 35 2 24 Algoritma MinMaks: 1. Untuk kasus n = 1 atau n = 2, SOLVE: Jika n = 1, maka min = maks = An. Jika n = 2, maka bandingkan kedua elemen untuk menentukan min dan maks. 2. Untuk kasus n > 2, a. DIVIDE: Bagi dua tabel A secara rekursif menjadi dua bagian yang berukuran sama, yaitu bagian kiri dan bagian kanan. Sukses beralgoritma 2012 19 b. CONQUER: Terapkan algoritma Divide and Conquer untuk masing-masing bagian, dalam hal ini min dan maks dari tabel bagian kiri dinyatakan dalam peubah min1 dan maks1, dan min dan maks dari tabel bagian kanan dinyatakan dalam peubah min2 dan maks2. c. COMBINE: Bandingkan min1 dengan min2 untuk menentukan min tabel A. Bandingkan maks1 dengan maks2 untuk menentukan maks tabel A. Tinjau kembali soal di atas DIVIDE dan CONQUER: Bagi tabel menjadi dua bagian sampai berukuran 1 atau 2 elemen: 4 12 23 9 21 1 35 2 24 4 12 23 9 21 1 35 2 24 4 12 23 9 21 1 35 2 24 SOLVE dan COMBINE: Tentukan min dan maks masing-masing bagian tabel, lalu gabung: 4 12 23 9 21 1 35 2 24 min=4 min=9 min=1 min=35 min=2 maks=12 maks=23 maks=21 maks=35 maks=24 4 12 23 9 21 1 35 2 24 min = 4 min = 1 min = 2 maks=23 maks = 21 maks=35 4 12 23 9 21 1 35 2 24 min = 4 min = 1 maks = 23 maks = 35 4 12 23 9 21 1 35 2 24 min = 1 maks = 35 Jadi, nilai minimum tabel = 1 dan nilai maksimum = 35. Merge Sort : contoh lain Pertama, data dibagi 2 bagian, selanjutnya tiap bagian dibagi lagi menjadi dua bagian, demikian selanjutnya hingga data tidak dapat dibagi lagi. Tahap ini merupakan divide. Sukses beralgoritma 2012 20 Setelah dibagi hingga potongan terkecil, data tesebut diurutkan kembali. Setelah data diurutkan kembali, maka tahap terakhir adalah data tersebut disatukan/dikombain. Implementasi Merge Sort : #include #include #include void printv(char* in, int *v, int n) { Sukses beralgoritma 2012 21 printf("%s", in); int i = 0; for (; i < n; ++i) printf("%d ", v[i]); printf("\n"); } void merge(int *v, int p, int q, int r) { int i = p; int j = q + 1; int *tmp = (int*)malloc((r - p + 1) * sizeof(int)); int k = 0; while ((i b a , dan ) (n f fungsi yang diketahui; ini perlu diketahui/dipahami dan dihafal, karena sekali anda melakukan ini penentuan batas asimtotis untuk rekurensi sederhana akan mudah. Rumus untuk menyelesaikan rekurensi berbentuk: Andaikan ) ( ) ( n f b n aT n T + | . | \ | = Di mana, a ≥ 1, b > 1, and f(n) > 0 Case 1: if f(n) = O(n log b a - c ) for some c > 0, then: T(n) = O(n log b a ) Case 2: if f(n) = O(n log b a ), then: T(n) = O( n log b a lgn) Case 3: if f(n) = O(n log b a+ε ) for some c > 0, and if af(n/b) ≤ cf(n) for some c < 1 and all sufficiently large n, then: T(n) = O(f(n)) n n/2 n/4 n/2 n/4 n/4 n/4 Sukses beralgoritma 2012 25 Contoh: 1. 2. 3. 4. ( ) 2 3 log 1 log 9 2 ( ) ( / 2) 1 1, 2; 1 also ( ) 1, ( ) (1) ( ) (lg ) ( Case 2: Cas ) 9 ( / 3) 9, 3; ( ) , ( ) ( ) with 1 ( ) e 1: T n T n a b n f n f n T n n T n T n n a b f n n f n O n T n n ÷c = + = = = = = O ¬ = O = + = = = = c = ¬ = O 4 4 2 log 3 0.793 log 3 log 2 1 ( ) 3 ( / 4) lg 3, 4; ( ) lg , ( ) ( ) with 0.2 Regularity condition ( / ) 3( / 4) l Case g( / 4) (3/ 4) lg ( ) for 3/ 4 ( ) ( lg ) ( ) 2 ( / 2) lg 2, 2; 3: T n T n n n a b n n f n n n f n n af n b n n n n cf n c T n n n T n T n n n a b n n f +c = + = = = = = O c ~ ¬ = s = = = O = + = = = 1 1 ( ) lg , ( ) ( ) with ? also l neither Case 3 nor Case 2! g / lg n n n f n n n n n n +c = = O c = ¬ Sukses beralgoritma 2012 26 Sukses beralgoritma 2012 27 BAB 4 STRATEGI ALGORITMA (I) METODE GREEDY & DYNAMIC PROGRAMMING Sukses beralgoritma 2012 28 Ada banyak macam strategi algoritma yang biasanya digunakan. Khusus pada bab ini, strategi algoritma yang akan dibahas adalah metode greedy dan dynamic programming. A. Metode Greedy Prinsip metode greedy ini adalah: “take what you can get now!”. Algoritma greedy membentuk solusi langkah per langkah (step by step). Pada setiap langkah, terdapat banyak pilihan yang perlu dieksplorasi. Oleh karena itu, pada setiap langkah harus dibuat keputusan yang terbaik dalam menentukan pilihan. Pada setiap langkah, kita membuat pilihan optimum lokal (local optimum) dengan harapan bahwa langkah sisanya mengarah ke solusi optimum global (global optimum). Algoritma greedy adalah algoritma yang memecahkan masalah langkah per langkah. Pada setiap langkah: o Mengambil pilihan yang terbaik yang dapat diperoleh pada saat itu tanpa memperhatikan konsekuensi ke depan (prinsip “take what you can get now!”) o Berharap bahwa dengan memilih optimum lokal pada setiap langkah akan berakhir dengan optimum global. Skema umum dari algoritma greedy disusun oleh elemen-elemen sebagai berikut : 1. Himpunan kandidat Himpunan ini berisi elemen-elemen pembentuk solusi. 2. Himpunan solusi Himpunan ini berisi bagian dari himpunan kandidat yang terpilih sebagai solusi persoalan. 3. Fungsi seleksi Fungsi ini adalah fungsi yang pada setiap langkah memilih solusi yang paling memungkinkan mencapai solusi optimal. 4. Fungsi kelayakan Fungsi ini memasukkan kandidat-kandidat yang layak dari himpunan kandidat ke himpunan solusi. 5. Fungsi obyektif Yaitu fungsi yang memaksimumkan atau meminimumkan nilai solusi Contoh kasus: Tinjau masalah penukaran uang Langkah strategi metode greedy: - Pada setiap langkah, pilihlah koin dengan nilai terbesar dari himpunan koin yang tersisa. Misal: diberikan jumlah uang A = $ 32, koin yang tersedia: $1, $5, $10, dan $25 Langkah 1 :pilih 1 buah koin $25 (Total = 25) 1 koin uang $20= $20 Sukses beralgoritma 2012 29 Sisa = $7 Langkah 2 :pilih 1 buah koin $5 (Total = 25 + 5 = 30) 1 koin uang $5= $5 Sisa = $2 Langkah 3 :pilih 2 buah koin $1 (Total = 25+5+1+1= 32) 2 koin uang $1= $2 Sisa = 0 - Solusi: Jumlah koin minimum = $4 (solusi optimal!) Catatan:  Algoritma greedy tidak beroperasi secara menyeluruh terhadap semua alternatif solusi yang ada (sebagaimana pada metode exhaustive search).  Terdapat beberapa fungsi SELEKSI yang berbeda, sehingga kita harus memilih fungsi yang tepat jika kita ingin algoritma menghasilkan solusi optiamal. Kesimpulan: Jadi, pada sebagian masalah, metode greedy tidak selalu berhasil memberikan solusi yang optimal. Kelebihan dan kelemahan metode greedy: Kelebihan:  Kompleksitas ruangnya rendah. Memori yang dibutuhkan tidak besar, karena langkah sebelumnya tidak disimpan. Kita terus memperhatikan langkah di depan saja. Sehingga sangat kecil kemungkinan mengalami masalah ketersediaan memori.  Mudah diimplementasikan, algoritma greedy sangat mudah untuk diimplementasikan pada persoalan-persoalan yang ada.  Kompleksitas waktunya rendah, sehingga jarang mengalami masalah dalam lamanya waktu pencarian langkah. Kelemahan:  Hasilnya belum tentu optimal.  Hanya mencari solusi terbaik saat itu, padahal nelum tentu terbaik untuk langkah berikutnya. Sukses beralgoritma 2012 30 B. Dynamic Programming Dynamic programming problems adalah masalah multi tahap(multistage) dimana keputusan dibuat secara berurutan (in sequence). Pemrograman dinamis (dynamic programming) adalah metode pemecahan masalah dengan cara menguraikan solusi menjadi sekumpulan langkah (step) atau tahapan (stage) sedemikian rupa sehingga solusi dari permasalahan ini dapat dipandang dari serangkaian keputusan-keputusan kecil yang saling berkaitan satu dengan yang lain. Penyelesaian persoalan dengan pemrograman dinamis ini akan menghasilkan sejumlah berhingga pilihan yang mungkin dipilih, lalu solusi pada setiap tahap-tahap yang dibangun dari solusi pada tahap sebelumnya, dan dengan metode ini kita menggunakan persyaratan optimasi dan kendala untuk membatasi sejumlah pilihan yang harus dipertimbangkan pada suatu tahap. Karakteristik Persoalan yang dimiliki oleh Program Dinamis: o Persoalan dapat dibagi menjadi beberapa tahap (stage), yang pada setiap tahap hanya dapat diambil satu keputusan. o Masing-masing tahap terdiri dari sejumlah status (state) yang berhubungan dengan tahap tersebut. Secara umum, status merupakan bermacam kemungkinan masukan yang ada pada tahap tersebut. Jumlahnya bisa berhingga atau tak berhingga. o Hasil dari keputusan yang diambil pada setiap tahap ditransformasikan dari status yang bersangkutan ke status berikutnya pada tahap berikutnya. o Ongkos (cost) pada suatu tahap meningkat secara teratur (steadily) dengan bertambahnya jumlah tahapan. o Ongkos pada suatu tahap bergantung pada ongkos tahap-tahap yang sudah berjalan dan ongkos pada tahap tersebut. o Keputusan terbaik pada suatu tahap bersifat independen terhadap keputusan yang dilakukan pada tahap sebelumnya. o Adanya hubungan rekursif yang mengidentifikasikan keputusan terbaik untuk setiap status pada tahap k memberikan keputusan terbaik untuk setiap status pada tahap k + 1. o Prinsip optimalitas berlaku pada persoalan tersebut. Langkah-langkah Pengembangan Algoritma Program Dinamis sebagai berikut : a) Karakteristikkan struktur solusi optimal. b) Definisikan secara rekursif nilai solusi optimal. c) Hitung nilai solusi optimal secara maju atau mundur. d) Konstruksi solusi optimal. Contoh kasus: Joe tinggal di new York dan akan pergi ke LA. Dia berencana menginap di rumah temannya dalam perjalanan tersebut. Joe punya teman di Columbus, Nashville, Louisville, Kansas, Omaha, Dallas, San Antonio, dan Denver. Joe tahu setelah satu hari Sukses beralgoritma 2012 31 perjalanan dia akan mencapai Columbus, Nashville atau Louisville. Setelah perjalanan 2 hari akan mencapai Kansas, Omaha, atau Dallas. Setelah 3 hari perjalanan akan mencapai Denver atau San Antonio. Setelah 4 hari akan mencapai LA. Untuk meminimalkan jarak, kemana Joe harus menginap setiap malam dalam perjalanannya ? Stage 3: Kansas = {New York, Columbus} cost Kansas=1230 Omaha= {New York, Columbus} cost Omaha=1340 Dallas={New York, Nashville} cost Dallas= 1560 Stage 4: Denver={ New York, Columbus, Kansas} cost Denver=1840 San Antonio={ New York, Nashville, Dallas} cost San Antonio=1830 Stage 5: LA={ New York, Columbus, Kansas, Denver } cost LA=2870 Jadi jarak optimal yang diperoleh adalah 2870 Kelebihan dan kelemahan metode dynamic programming: Kelebihan:  mengoptimalkan penyelesaian suatu masalah tertentu yang diuraikan menjadi sub- sub masalah yang lebih kecil yang terkait satu sama lain dengan tetap memperhatikan kondisi dan batasan permasalahan tersebut.  Proses pemecahan suatu masalah yang kompleks menjadi sub-sub masalah yang lebih kecil membuat sumber permasalahan dalam rangkaian proses masalah tersebut menjadi lebih jelas untuk diketahui.  Pendekatan dynamic programming dapat diaplikasikan untuk berbagai macam masalah pemrograman matematik, karena dynamic programming cenderung lebih fleksibel daripada teknik optimasi lain. Sukses beralgoritma 2012 32  Prosedur perhitungan dynamic programming juga memperkenankan bentuk analisis sensitivitas terdapat pada setiap variabel status (state) maupun pada variabel yang ada di masing-masing tahap keputusan (stage).  Dynamic programming dapat menyesuaikan sistematika perhitungannya menurut ukuran masalah yang tidak selalu tetap dengan tetap melakukan perhitungan satu per satu secara lengkap dan menyeluruh. Kelemahan:  Penggunaan dynamic programming jika tidak dilakukan secara tepat, akan mengakibatkan ketidakefisienan biaya maupun waktu. Karena dalam menggunakan dynamic programming diperlukan keahlian, pengetahuan, dan seni untuk merumuskan suatu masalah yang kompleks, terutama yang berkaitan dengan penetapan fungsi transformasi dari permasalahan tersebut. Contoh Kasus: Diberikan sebuah kotak berukuran 15cmx35cm. 35 15 Jenis kotak, ada 4 buah yang akan disusun ke dalam kotak tersebut: 6 cm Kotak 3 Kotak 1 Kotak2 Kotak4 Sukses beralgoritma 2012 33 Penyelesaian dengan metode greedy: Kotak 4 dan kotak 1 tersebut disusun seperti di bawah ini: Sehingga diperoleh luas yang dianggap bisa menempati kotak tersebut dengan luas yang optimum. 4 2 4 4 10 Kotak yang telah disusun tersebut dimasukkan ke dalam kota besar yang berukuran 15x35 cm. jumlah kotak yang dimasukkan adalah sebanyak 9 buah, sehingga diperoleh sbb: 10 10 10 Tempat yang kosong masih dapat diisi dengan kotak berukuran 4x2 cm.. jumlah kotak yang dimasukkan adalah sebanyak 14 buah. Sehingga diperoleh: 35 Dapat dihitung luas dari sisa kotak yang tidak terisi adalah: 35 + 9 + 12 =56 1 3 Sukses beralgoritma 2012 34 Penyelesaian dengan dynamic programming: Pada metode ini, kotak yang akan diisi dibagi 2 bagian. Sehingga kita akan mengisi kotak tersebut dengan 2 step. Hasilnya menjadi seperti di bawah ini: 8cm 7cm 35 cm Kemudian dari 4 kotak yang ada dibentuklah susunan kotak yang sesuai sehingga dapat dimasukkan ke dalam kota utama di atas. Berikut adalah kotak yang sesuai dengan kotak utama (kotak ini dibentuk dari kotak 1 dan kotak 2): STEP 1: Kotak tersebut kemudian diisi ke dalam kotak utama bagian (I) STEP 2: Selanjutnya kita akan mengisi kotak bagian (II). Kembali kita meninjau kotak yang telah disusun, ternyata masih biasa digunakan untuk mengisi kotak bagian (II) ini. Sehingga diperoleh: 8cm 7cm 3cm I II Sukses beralgoritma 2012 35 Selanjutnya kita meninjau kembali tempat yang masi belum terisi, ternyanya masih ada kotak yang dapat diisi ke dalam, yakni kotak berukuran 4x2 cm. Setelah diisi, kita memperoleh hasil sebagai berikut: Sisa kotak yang kosong adalah= 4+9=13 Kesimpulan: Jika kita membandingkan metode greedy dengan metode dynamic programming, maka yang mendapatkan sisa kotak yang paling minimum adalah metode dynamic programming. Jadi metode yang paling optimal adalah dynamic programming. Prinsip Optimalitas • Pada program dinamis, rangkaian keputusan yang optimal dibuat dengan menggunakan Prinsip Optimalitas. • Prinsip Optimalitas: jika solusi total optimal, maka bagian solusi sampai tahap ke-k juga optimal. • Prinsip optimalitas berarti bahwa jika kita bekerja dari tahap k ke tahap k + 1, kita dapat menggunakan hasil optimal dari tahap k tanpa harus kembali ke tahap awal. • ongkos pada tahap k +1 = (ongkos yang dihasilkan pada tahap k ) + (ongkos dari tahap k ke tahap k + 1) • Dengan prinsip optimalitas ini dijamin bahwa pengambilan keputusan pada suatu tahap adalah keputusan yang benar untuk tahap-tahap selanjutnya. • Pada metode greedy hanya satu rangkaian keputusan yang pernah dihasilkan, sedangkan pada metode program dinamis lebih dari satu rangkaian keputusan. Hanya rangkaian keputusan yang memenuhi prinsip optimalitas yang akan dihasilkan. Sukses beralgoritma 2012 36 Sukses beralgoritma 2012 37 BAB 5 STRATEGI ALGORITMA (II) Sukses beralgoritma 2012 38 A. Algoritma Metaheuristik Heuristik berasal dari kata Yunani Heuriskein yang berarti seni untuk menemukan strategi dalam menyelesaikan persoalan sedangkan meta berarti metodologi tingkat tinggi atau lanjut (Talbi, 2009). Di dalam ilmu komputer, metode heuristik merupakan suatu teknik untuk penyelesaian permasalahan yang tidak menekankan pada pembuktian apakah solusi yang didapatkan adalah benar (pembuktian apakah suatu solusi adalah benar merupakan fokus dari metode penyelesaian analitik), tetapi lebih menekankan pada performa komputasi dan kesederhanaan. Metode heuristik merupakan suatu metode penyelesaian yang menggunakan konsep pendekatan Menurut Talbi (2009), metaheuristik dapat didefinisikan sebagai metode lanjut (advanced) berbasis heuristic untuk menyelesaikan persoalan optimisasi secara efisien. Metaheuristik didefinisikan sebagai metode optimisasi yang dilakukan dengan memperbaiki kandidat penyelesaian secara iteratif sesuai dengan fungsi objektifnya. Metode ini mampu menghasilkan penyelesaian yang baik dalam waktu yang cepat (acceptable), tetapi tidak menjamin bahwa penyelesaian yang dihasilkan merupakan penyelesaian terbaik (optimal). Metode metaheuristik banyak dipakai dalam optimisasi stokastik (optimisasi stokastim merupakan optimisasi yang memiliki derajat ketidakpastian atau random). Metaheuristik dapat menggunakan domain pengetahuan khusus dalam bentuk heuristik yang dikendalikan dengan strategi tingkat lanjuti) Metaheuristik dapat menggunakan pengalaman yang didapat selama proses pencarian untuk menuntun proses pencarian. Dalam menentukan apakah metaheuristik adalah metode yang sesuai untuk menyelesaikan suatu permasalahan, ada beberapa hal yang perlu diperhatikan misalnya kompleksitas permasalahan, ukuran input, struktur input dan waktu yang diperlukan untuk menyelesaikan masalah tersebut. Secara umum metehauristik dipakai untuk masalah-masalah yang komplek dan tidak bisa diselesaikan dengan mudah secara analitikal/eksak. Tidaklah terlalu bermanfaat menggunakan metaheuristik untuk persoalan yang dengan mudah dan cepat dapat diselesaikan secara eksak (penyelesaian eksak merupakan penyelesaian terbaik, tetapi seringkali metode ini tidak dapat diterapkan pada permasalahan optimisasi, sehingga dipakailah metode pendekatan). Metaheuristik pada sebenarnya adalah metode pendekatan yang didasarkan pada metode heuristik. Sehingga tidak heran bahwa metode heuristik sering kali diintegrasikan didalam metodeme taheuristik. Perbedaan utaman dari metode heuristik dan metaheuristik adalah: metode heuristik bersifat problem dependent sedangkan metode metaheuristik bersifat problem independent. Sukses beralgoritma 2012 39 B. Algoritma Genetika Algoritma genetika adalah algoritma komputasi yang diinspirasi teori evolusi yang kemudian diadopsi menjadi algoritma komputasi untuk mencari solusi suatu permasalahan dengan cara yang lebih “alamiah”. Salah satu aplikasi algoritma genetika adalah pada permasalahan optimasi kombinasi, yaitu mendapatkan suatu nilai solusi optimal terhadap suatu permasalahan yang mempunyai banyak kemungkinan solusi. Dalam tulisan ini akan dibahas teori dasar algoritma genetika beserta contoh aplikasinya dalam menyelesaikan suatu permasalahan optimasi kombinasi sederhana. Algoritma genetika adalah algoritma heuristik adaptif (metaheuristik) yang memiliki dasar pemikiran atau gagasan evolusioner untuk proses seleksi alami dan genetika. Konsep dasar dari algoritma genetika dirancang untuk menirukan proses di dalam sistem alami yang penting bagi evolusi makhluk hidup untuk dapat terus bertahan hidup, yang secara rinci teori ini dicetuskan oleh Charles Darwin yaitu “Survival of the Fittest”. Dengan menirukan teori dari Charles Darwin, algoritma genetika dapat digunakan, untuk mencari solusi dari segala macam permasalahan dalam ilmu pengetahuan seperti dalam mencari solusi penjadwalan job shop. Pelopor pertama penggunaan metode algoritma genetika adalah John Holland pada tahun 60-an. Algoritma genetika menggunakan analogi seleksi alam yang bekerja dari suatu populasi yang terdiri dari berbagai individu (gen), yang masing-masing individu mempresentasikan suatu solusi yang mungkin muncul dari persoalan yang dihadapi. Dalam hal ini, individu yang terpilih dilambangkan dengan sebuah nilai fitness yang digunakan untuk mencari solusi terbaik dari persoalan yang ada. Teori Dasar Algoritma Genetika Algoritma genetika yang dikembangkan oleh Goldberg adalah algoritma komputasi yang diinspirasi teori evolusi Darwin yang menyatakan bahwa kelangsungan hidup suatu makhluk dipengaruhi aturan “yang kuat adalah yang menang”. Darwin juga menyatakan bahwa kelangsungan hidup suatu makhluk dapat dipertahankan melalui proses reproduksi, crossover, dan mutasi. Konsep dalam teori evolusi Darwin tersebut kemudian diadopsi menjadi algoritma komputasi untuk mencari solusi suatu permasalahan dengan cara yang lebih “alamiah”. Sebuah solusi yang dibangkitkan dalam algoritma genetika disebut sebagai chromosome, sedangkan kumpulan chromosome-chromosome tersebut disebut sebagai populasi. Sebuah chromosome dibentuk dari komponen-komponen penyusun yang disebut sebagai gen dan nilainya dapat berupa bilangan numerik, biner, simbol ataupun karakter tergantung dari permasalahan yang ingin Sukses beralgoritma 2012 40 diselesaikan. Chromosome-chromosome tersebut akan berevolusi secara berkelanjutan yang disebut dengan generasi. Dalam tiap generasi chromosome- chromosome tersebut dievaluasi tingkat keberhasilan nilai solusinya terhadap masalah yang ingin diselesaikan (fungsi_objektif) menggunakan ukuran yang disebut dengan fitness. Untuk memilih chromosome yang tetap dipertahankan untuk generasi selanjutnya dilakukan proses yang disebut dengan seleksi. Proses seleksi chromosome menggunakan konsep aturan evolusi Darwin yang telah disebutkan sebelumnya yaitu chromosome yang mempunyai nilai fitness tinggi akan memiliki peluang lebih besar untuk terpilih lagi pada generasi selanjutnya. Chromosome-chromosome baru yang disebut dengan offspring, dibentuk dengan cara melakukan perkawinan antar chromosome-chromosome dalam satu generasi yang disebut sebagai proses crossover. Jumlah chromosome dalam populasi yang mengalami crossover ditetukan oleh paramater yang disebut dengan crossover_rate. Mekanisme perubahan susunan unsur penyusun mahkluk hidup akibat adanya faktor alam yang disebut dengan mutasi direpresentasikan sebagai proses berubahnya satu atau lebih nilai gen dalam chromosome dengan suatu nilai acak. Jumlah gen dalam populasi yang mengalami mutasi ditentukan oleh parameter yang dinamakan mutation_rate. Setelah beberapa generasi akan dihasilkan chromosome-chromosome yang nilai gen-gennya konvergen ke suatu nilai tertentu yang merupakan solusi terbaik yang dihasilkan oleh algoritma genetika terhadap permasalahan yang ingin diselesaikan. Prosedure Algoritma Genetika Algoritma genetik yang umum menyaratkan dua hal untuk didefinisikan: (1) representasi genetik dari penyelesaian, (2) fungsi kemampuan untuk mengevaluasinya. Representasi baku adalah sebuah larik bit-bit. Larik jenis dan struktur lain dapat digunakan dengan cara yang sama. Hal utama yang membuat representasi genetik ini menjadi tepat adalah bahwa bagian-bagiannya mudah diatur karena ukurannya yang tetap, yang memudahkan operasi persilangan sederhana. Representasi panjang variabel juga digunakan, tetapi implementasi persilangan lebih kompleks dalam kasus ini. Representasi seperti pohon diselidiki dalam pemrograman genetik dan representasi bentuk bebas diselidiki di dalam HBGA. Fungsi kemampuan didefinisikan di atas representasi genetik dan mengukur kualitas penyelesaian yang diwakili. Fungsi kemampuan selalu tergantung pada masalah. Sebagai contoh, jika pada ransel kita ingin memaksimalkan jumlah benda (obyek) yang dapat kita masukkan ke dalamnya pada beberapa kapasitas yang tetap. Representasi penyelesaian mungkin berbentuk larik bits, dimana tiap bit mewakili obyek yang berbeda, dan nilai bit (0 atau 1) menggambarkan apakah obyek tersebut ada di dalam ransel atau tidak. Tidak setiap representasi seperti ini Sukses beralgoritma 2012 41 valid, karena ukuran obyek dapat melebihi kapasitas ransel. Kemampuan penyelesaian adalah jumlah nilai dari semua obyek di dalam ransel jika representasi itu valid, atau jika tidak 0. Dalam beberapa masalah, susah atau bahkan tidak mungkin untuk mendefinisikan lambang kemampuan, maka pada kasus ini digunakan IGA. Sekali kita mendefinisikan representasi genetik dan fungsi kemampuan, algoritma genetik akan memproses inisialisasi populasi penyelesaian secara acak, dan memperbaikinya melalui aplikasi pengulangan dengan aplikasi operator- operator mutasi, persilangan, dan seleksi. Secara sederhana, algoritma umum dari algoritma genetik ini dapat dirumuskan menjadi beberapa langkah, yaitu: 1. Membentuk suatu populasi individual dengan keadaan acak 2. Mengevaluasi kecocokan setiap individual keadaan dengan hasil yang diinginkan 3. Memilih individual dengan kecocokan yang tertinggi 4. Bereproduksi, mengadakan persilangan antar individual terpilih diselingi mutasi 5. Mengulangi langkah 2 - 4 sampai ditemukan individual dengan hasil yang diinginkan. Pada umumnya suatu penerapan algoritma genetika secara generasional sederhana terdiri dari 3 bagian, yaitu: 1. Memilih populasi awal (inisial populasi) 2. Evaluasi nilai fitness dari setiap individu didalam populasi 3. Ulangi sampai proses berhenti (nilai fitness terbaik terpenuhi) a) Pilih individu terbaik berdasar ranking untuk reproduksi b) Bentuk generasi baru melalui pindah silang dan mutasi untuk menghasilkan keturunan baru (child) c) Evaluasi nilai fitness keturunan yang dihasilkan Jika diilustrasikan, maka proses algoritma genetika yang dilakukan dapat terlihat seperti gambar berikut: Sukses beralgoritma 2012 42 Definisi Individu Individu menyatakan solusi yaitu nilai x. Nilai x sebagai individu dinyatakan dalam nilai biner. Individu dinyatakan dalam 8 gen biner dengan batas 0 sampai dengan 1 yang berarti sat bit setara dengan 2-8 Sebagai contoh: 10001001 = (128+8+1)/256 = 0.5352 01010010 = (2+16+64)/256 = 0.3203 Fungsi Fitness Fungsi fitness dinyatakan sebagai fungsi f(x), karena yang dicari adalah nilai maksimum. Membangkitkan Populasi Awal Membangkitkan sejumlah individu, misalkan satu populasi terdiri dari 8 individu, maka dibangkitkan 8 individu dengan 8 gen biner yang dibangkitkan secara acak. Seleksi Seleksi roulette whell untuk memilih induk dilakukan dengan menggunakan prosentasi fitness setiap individu, dimana setiap individu mendapatkan luas bagian sesuai dengan prosentase nilai fitnessnya. Sukses beralgoritma 2012 43 Hitung Total Fitness Menghitung prosentase fitness dan penentuan bidang Aplikasi Algoritma Genetika Berikut adalah contoh aplikasi algoritma genetika yang digunakan untuk menyelesaikan masalah kombinasi. Misalkan ada persamaan a+2b+3c+4d = 30, kita mencari nilai a, b, c, dan d yang memenuhi persamaan diatas. Kita mencoba menggunakan algoritma genetika untuk menyelesaikan permasalahan diatas. Diagram alir dari algoritma genetika untuk menyelesaikan permasalahan diatas dapat dilihat pada Gambar 1. Sukses beralgoritma 2012 44 Penjelasan mengenai langkah-langkah penyelesaian permasalahan diatas menggunakan algoritma genetika adalah sebagai berikut: Sukses beralgoritma 2012 45 1. Pembentukan chromosome Karena yang dicari adalah nilai a, b, c, d maka variabel a, b, c, d dijadikan sebagai gen-gen pembentuk chromosome. Batasan nilai variabel a adalah bilangan integer 0 sampai 30. Sedangkan batasan nilai variabel b, c, dan d adalah bilangan integer 0 sampai 10. 2. Inisialisasi Proses inisialisasi dilakukan dengan cara memberikan nilai awal gen-gen dengan nilai acak sesuai batasan yang telah ditentukan. Misalkan kita tentukan jumlah populasi adalah 6, maka: Chromosome[1] = [a;b;c;d] = [12;05;03;08] Chromosome[2] = [a;b;c;d] = [02;01;08;03] Chromosome[3] = [a;b;c;d] = [10;04;03;04] Chromosome[4] = [a;b;c;d] = [20;01;10;06] Chromosome[5] = [a;b;c;d] = [01;04;03;09] Chromosome[6] = [a;b;c;d] = [20;05;07;01] 3. Evaluasi Chromosome Permasalahan yang ingin diselesaikan adalah nilai variabel a, b, c, dan d yang memenuhi persamaan a+2b+3c+4d = 30, maka fungsi_objektif yang dapat digunakan untuk mendapatkan solusi adalah fungsi_objektif(chromosome) = | (a+2b+3c+4d) – 30 | Kita hitung fungsi_objektif dari chromosome yang telah dibangkitkan: fungsi_objektif(chromosome[1]) = Abs(( 12 + 2*5 + 3*3 + 4*8 ) - 30) = Abs((12 + 10 + 9 + 32 ) - 30) = Abs(63 - 30) = 33 fungsi_objektif(chromosome[2]) = Abs(( 2 + 2*1 + 3*8 + 4*3 ) - 30) = Abs(( 2 + 2 + 24 + 12 ) - 30) = Abs(40 - 30) = 10 fungsi_objektif(chromosome[3]) = Abs(( 10 + 2*4 + 3*3 + 4*4 ) - 30) = Abs(( 10 + 8 + 9 + 16 ) - 30) = Abs(43 - 30) = 13 fungsi_objektif(chromosome[4]) = Abs(( 20 + 2*1 + 3*10 + 4*6 ) - 30) = Abs(( 20 + 2 + 30 + 24 ) - 30) = Abs(76 - 30) = 46 fungsi_objektif(chromosome[5]) = Abs(( 1 + 2*4 + 3*3 + 4*9 ) - 30) = Abs(( 1 + 8 + 9 + 36 ) - 30) = Abs(54 - 30) Sukses beralgoritma 2012 46 = 24 fungsi_objektif(chromosome[6]) = Abs(( 20 + 2*5 + 3*7 + 4*1 ) - 30) = Abs(( 20 + 10 + 21 + 4) - 30) = Abs(55 - 30) = 25 Rata-rata dari fungsi objektif adalah: rata-rata = (33+10+13+46+24+25)/6 = 151 / 6 = 25.167 4. Seleksi Chromosome Proses seleksi dilakukan dengan cara membuat chromosome yang mempunyai fungsi_objektif kecil mempunyai kemungkinan terpilih yang besar atau mempunyai nilai probabilitas yang tinggi. Untuk itu dapat digunakan fungsi fitness = (1/(1+fungsi_objektif)), fungsi_objektif perlu ditambah 1 untuk menghindari kesalahan program yang diakibatkan pembagian oleh 0. fitness[1] = 1 / (fungsi_objektif[1]+1) = 1 / 34 = 0.0294 fitness[2] = 1 / (fungsi_objektif[2]+1) = 1 / 11 = 0.0909 fitness[3] = 1 / (fungsi_objektif[3]+1) = 1 / 14 = 0.0714 fitness[4] = 1 / (fungsi_objektif[4]+1) = 1 / 47 = 0.0212 fitness[5] = 1 / (fungsi_objektif[5]+1) = 1 / 25 = 0.0400 fitness[6] = 1 / (fungsi_objektif[6]+1) = 1 / 26 = 0.0385 total_fitness = 0.0294 + 0.0909 + 0.0714 + 0.0212 + 0.04 + 0.0385 = 0.2914 Rumus untuk mencari probabilitas: P[i] = fitness[i] / total_fitness P[1] = 0.0294 / 0.2914 = 0.1009 P[2] = 0. 0909 / 0.2914 = 0.3119 Sukses beralgoritma 2012 47 P[3] = 0. 0714 / 0.2914 = 0.2450 P[4] = 0. 0212 / 0.2914 = 0.0728 P[5] = 0.04 / 0.2914 = 0.1373 P[6] = 0.0385 / 0.2914 = 0.1321 Dari probabilitas diatas dapat kita lihat kalau chromosome ke 2 yang mempunyai fitness paling besar maka chromosome tersebut mempunyai probabilitas untuk terpilih pada generasi selanjutnya lebih besar dari chromosome lainnya. Untuk proses seleksi kita gunakan roulete wheel, untuk itu kita harus mencari dahulu nilai kumulatif probabilitasnya: C[1] = 0.1009 C[2] = 0.1009+ 0.3119 = 0.4128 C[3] = 0.1009+ 0.3119 + 0.2450 = 0.6578 C[4] = 0.1009+ 0.3119 + 0.2450 + 0.0728 = 0.7306 C[5] = 0.1009+ 0.3119 + 0.2450 + 0.0728 + 0.1373 = 0.8679 C[6] = 0.1009+ 0.3119 + 0.2450 + 0.0728 + 0.1373 + 0.1321= 1 Setelah dihitung cumulative probabilitasnya maka proses seleksi menggunakan roulete-wheel dapat dilakukan. Prosesnya adalah dengan membangkitkan bilangan acak R dalam range 0-1. Jika R[k] < C[1] maka pilih chromosome 1 sebagai induk, selain itu pilih chromosome ke-k sebagai induk dengan syarat C[k-1] < R < C[k]. Kita putar roulete wheel sebanyak jumlah populasi yaitu 6 kali (bangkitkan bilangan acak R) dan pada tiap putaran, kita pilih satu chromosome untuk populasi baru. Misal: R[1] = 0.201 R[2] = 0.284 R[3] = 0.009 R[4] = 0.822 R[5] = 0.398 R[6] = 0.501 Angka acak pertama R[1] adalah lebih besar dari C[1] dan lebih kecil daripada C[2] maka pilih chromosome[2] sebagai chromosome pada populasi baru, dari bilangan acak yang telah dibangkitkan diatas maka populasi chromosome baru hasil proses seleksi adalah: chromosome[1] = chromosome[2] chromosome[2] = chromosome[2] chromosome[3] = chromosome[1] chromosome[4] = chromosome[5] chromosome[5] = chromosome[2] chromosome[6] = chromosome[3] Chromosome baru hasil proses seleksi: Sukses beralgoritma 2012 48 chromosome[1] = [02;01;08;03] chromosome[2] = [02;01;08;03] chromosome[3] = [12;05;03;08] chromosome[4] = [01;04;03;09] chromosome[5] = [02;01;08;03] chromosome[6] = [10;04;03;04] 5. Crossover Setelah proses seleksi maka proses selanjutnya adalah proses crossover. Metode yang digunakan salah satunya adalah one-cut point, yaitu memilih secara acak satu posisi dalam chromosome induk kemudian saling menukar gen. Chromosome yang dijadikan induk dipilih secara acak dan jumlah chromosome yang mengalami crossover dipengaruhi oleh parameter crossover_rate ( ρc ). Pseudo-code untuk proses crossover adalah sebagai berikut: begin k← 0; while(k< chromosome[4] chromosome[4] >< chromosome[5] chromosome[5] >< chromosome[1] Posisi cut-point crossover dipilih menggunakan bilangan acak 1-3 sebanyak jumlah crossover yang terjadi, misal C[1] = 1 C[2] = 1 C[3] = 2 offspring[1] = chromosome[1] >< chromosome[4] = [02;01;08;03] >< [01;04;03;09] = [02;04;03;09] offspring[4] = Chromosome[4] >< Chromosome[5] = [01;04;03;09] >< [02;01;08;03] = [01;01;08;03] offspring[5] = Chromosome[5] >< Chromosome[1] = [02;01;08;03] >< [02;01;08;03] = [02;01;08;03] Dengan demikian populasi Chromosome setelah mengalami proses crossover menjadi: chromosome[1] = [02;04;03;09] chromosome[2] = [02;01;08;03] chromosome[3] = [12;05;03;08] chromosome[4] = [01;01;08;03] chromosome[5] = [02;01;08;03] chromosome[6] = [10;04;03;04] 6. Mutasi Jumlah chromosome yang mengalami mutasi dalam satu populasi ditentukan oleh parameter mutation_rate. Proses mutasi dilakukan dengan cara mengganti satu gen yang terpilih secara acak dengan suatu nilai baru yang didapat secara acak. Prosesnya adalah sebagai berikut. Pertama kita hitung dahulu panjang total gen yang ada dalam satu populasi. Dalam kasus ini panjang total gen adalah total_gen = (jumlah gen dalam chromosome) * jumlah populasi = 4 * 6 = 24 Sukses beralgoritma 2012 50 Untuk memilih posisi gen yang mengalami mutasi dilakukan dengan cara membangkitkan bilangan integer acak antara 1 sampai total_gen, yaitu 1 sampai 24. Jika bilangan acak yang kita bangkitkan lebih kecil daripada variabel mutation_rate (ρm) maka pilih posisi tersebut sebagai sub-chromosome yang mengalami mutasi. Misal ρm kita tentukan 10% maka diharapkan ada 10% dari total_gen yang mengalami populasi: jumlah mutasi = 0.1 * 24 = 2.4 = 2 Misalkan setelah kita bangkitkan bilangan acak terpilih posisi gen 12 dan 18 yang mengalami mutasi. Dengan demikian yang akan mengalami mutasi adalah chromosome ke-3 gen nomor 4 dan Chromosome ke-5 gen nomor 2. Maka nilai gen pada posisi tersebut kita ganti dengan bilangan acak 0-30. Misalkan bilangan acak yang terbangkitkan adalah 2 dan 5. Maka populasi chromosome setelah mengalami proses mutasi adalah: chromosome[1] = [02;04;03;09] chromosome[2] = [02;01;08;03] chromosome[3] = [12;05;03;02] chromosome[4] = [01;01;08;03] chromosome[5] = [02;05;08;03] chromosome[6] = [10;04;03;04] Setelah proses mutasi maka kita telah menyelesaikan satu iterasi dalam algoritma genetika atau disebut dengan satu generasi. Maka fungsi_objective setelah satu generasi adalah: chromosome[1] = [02;04;03;09] fungsi_objektif[1] = Abs(( 2 + 2*4 + 3*3 + 4*9 ) - 30) = Abs(( 2 + 8 + 9 + 36 ) - 30) = Abs( 55 - 30) = 25 chromosome[2] = [02;01;08;03] fungsi_objektif[2] = Abs(( 2 + 2*1 + 3*8 + 4*3 ) - 30) = Abs(( 2 + 2 + 24 + 12 ) - 30) = Abs(40 - 30) = 10 chromosome[3] = [12;05;03;02] fungsi_objektif[3] = Abs(( 12 + 2*5 + 3*3 + 4*2 ) - 30) = Abs(( 12 + 10 + 9 + 8 ) - 30) Sukses beralgoritma 2012 51 = Abs(39 - 30) = 9 chromosome[4] = [01;01;08;03] fungsi_objektif[4] = Abs(( 1 + 2*1 + 3*8 + 4*3 ) - 30) = Abs(( 1 + 2 + 24 + 12 ) - 30) = Abs(39 - 30) = 9 chromosome[5] = [02;05;08;03] fungsi_objektif[5] = Abs(( 2 + 2*5 + 3*8 + 4*3 ) - 30) = Abs(( 2 + 10 + 24 + 12 ) - 30) = Abs(48 - 30) = 18 chromosome[6] = [10;04;03;04] fungsi_objektif[6] = Abs(( 10 + 2*4 + 3*3 + 4*4 ) - 30) = Abs(( 10 + 8 + 9 + 16 ) - 30) = Abs(43 - 30) = 13 Rata-rata fungsi objektif setelah satu generasi adalah: rata-rata = ( 25 + 10 + 9 + 9 + 18 + 13) / 6 = 84 / 6 = 14.0 Dapat dilihat dari hasil perhitungan fungsi objektif diatas bahwa setelah satu generasi, nilai hasil rata-rata fungsi_objektif lebih menurun dibandingkan hasil fungsi_objektif pada saat sebelum mengalami seleksi, crossover dan mutasi. Hal ini menunjukkan bahwa chromosome atau solusi yang dihasilkan setelah satu generasi lebih baik dibandingkan generasi sebelumnya. Maka pada generasi selanjutnya chromosome-chromosome yang baru adalah: chromosome[1] = [02;04;03;09] chromosome[2] = [02;01;08;03] chromosome[3] = [12;05;03;02] chromosome[4] = [01;01;08;03] chromosome[5] = [02;05;08;03] chromosome[6] = [10;04;03;04] Sukses beralgoritma 2012 52 Chromosome-chromosome ini akan mengalami proses yang sama seperti generasi sebelumnya yaitu proses evaluasi, seleksi, crossover dan mutasi yang kemudian akan menghasilkan chromosome-chromosome baru untuk generasi yang selanjutnya. Proses ini akan berulang sampai sejumlah generasi yang telah ditetapkan sebelumnya. Setelah 50 generasi didapatkan chromosome yang terbaik adalah: Chromosome = [07;05;03;01] Jika didekode maka: a=7 ; b=5 ; c=3 ; d=1 Jika dihitung terhadap persamaan f = a+2b+3c+4d: 7 + (2*5) + (3*3) + (4*1) = 30 Penyilangan atau Crossover Sebuah kromosom yang mengarah pada solusi yang bagus bisa diperoleh dari proses memindah-silangkan dua buah kromosom. Penyilangan dua buah kromosom dimaksud un-tuk menghasilkan kromosom anak atau “offspring”. Kromosom anak yang terbentuk akan mewarisi sebagian sifat kromosom induknya. Pada crossover ada satu parameter yang sangat penting yaitu peluang crossover “pc”. Contoh Proses Penyilangan. Jika solusi yang dicari adalah X1 = 0 dan X2 = 0, maka kromosom Anak 1 memiliki nilai finess tinggi dan menuju pada solusi yang dicari Mutasi Pada mutasi ada satu parameter penting yaitu peluang (probabilitas) mutasi atau “pmut” yang menunjukkan prosentase jumlah total gen pada populasi yang akan Sukses beralgoritma 2012 53 mengalami mutasi. Untuk semua gen yang ada, jika bilangan ran-dom yang dibangkitkan kurang dari probabilitas mutasi “pmut” yang ditentukan, maka ubah gen tersebut menjadi nilai kebalikannya. Biasanya “pmut” diset sebagai 1/n, “n” adalah jumlah gen dalam kromosom. Dengan “pmut” sebesar ini berarti mutasi hanya terjadi pada 1 gen saja. Contoh Proses Mutasi. Bilangan random yang dihasilkan lebih kecil dari probabilitas mutasi pmu terjadi pada gen g10 sehingga gen g10 berubah dari 1 menjadi 0 Membentuk Individu Baru Anak hasil perkawinan silang dan mutasi menjadi generasi baru untuk dilakukan proses regenerasi . Pada generasi berikutnya, individu terbaik (nilai fitness terbesar) dapat dipertahankan dengan proses elitism C. Jaringan Syaraf Tiruan Berawal dari sistem mesin Von Neumann, sistem komputer pada saat ini telah berkembang pesat. Jaringan syaraf tiruan (JST) terjemahan dari Artificial Neural Network, merupakan suatu model dari sistem syaraf biologis yang disederhanakan sebagai suatu alternatif sistem komputasi. (Penelitian Jaringan Syaraf Tiruan,1993). Meskipun kecepatan proses yang telah dicapai komputer dewasa ini lebih cepat jika Sukses beralgoritma 2012 54 dibandingkan dengan proses yang dilakukan otak manusia, komputer masih belum bisa menandingi universilitas kemampuan pada otak manusia. Struktur sel syaraf biologis Sel syaraf biologis atau disebut juga Neuron memiliki tiga komponen penyusun yang saling bekerja sama untuk mengolah sinyal-sinyal informasi. Tiga komponen tersebut adalah dendirt, soma atau badan sel dan axon seperti tampak pada gambar 1. Dendrit merupakan serabut saraf yang bercabang-cabang pendek dan berjumlah lebih dari satu ini bertugas menerima sinyal dari neuron lain. Sinyal listrik ini dilewatkan melalui celah sinapsis (sianapsis gap) yang pada perjalanan biologisnya terjadi proses kimiawi dengan penskalaan frekuensi sinyal, pada jaringan syaraf tiruan proses ini disebut pembentukan bobot. Sinyal yang diterima diolah oleh soma dan kemudian dijumlahkan. Gambar 1. Struktur Sel Syaraf Biologis Untuk mengirimkan informasi ke sel lain, sinyal dilewatkan melalui axon yang merupakan serabut syaraf tunggal dan pada ujungnya bercabang-cabang. Selanjutnya sinyal akan melalui celah sinapsis dan disampaikan ke soma lain oleh dendrit neuron tersebut. Sehingga dengan terintegrasi dan terkoneksinya neuron satu dengan yang lain akan dapat melaksanakan aktifitas secara teratur sesuai kebutuhan. Struktur jaringan saraf tiruan JST disusun oleh elemen – elemen pemroses yang berada pada lapisan-lapisan yang berhubungan dan diberi bobot. Dengan serangkaian inputan diluar sistem yang diberikan kepadanya jaringan ini dapat memodifikasi bobot yang akan dihasilkannya, sehingga akan menghasilkan output yang konsisten sesuai dengan input yang diberian kepadanya. Setiap elemen pemroses melaksanakan operasi matematika yang sudah ditentukan dan menghasilkan (hanya) sebuah harga Sukses beralgoritma 2012 55 keluaran dari satu ataupun banyak masukan. Struktur jaringan akan ditunjukkan seperti pada gambar berikut ini : Gambar 2. Model tiruan neuron Sebuah pemodelan neuron memiliki masukan Xp sebanyak p, yang berasal dari sel lain atau dari inputan luar (bukan dari neuron). Selanjutnya setiap inputan diberi pembobot Wkp. Masing – masing inputan Xp akan dikalikan dengan pembobot Wk yang berkesesuaian. Untuk semua hasil perkalian akan dijumlahkan sebagaimana pada persamaan dibawah ini : (1) dan hasil persamaan tersebut akan menjadi masukan bagi fungsi aktivasi untuk mendapatkan tingkat derajat sinyal keluaran pada neuron, dimana terdapat bermacam-macam jenis fungsi aktivasi. Untuk jenis fungsi sigmoid dapat dideskripsikan dengan persamaan : (2) dengan grafik yang ditunjukkan sebagai berikut : Gambar 3. Grafik fungsi sigmoid Pada umumnya sinyal fungsi aktivasi yang dikeluarkan tiap neuron berbeda, hal ini dikarenakan berbedanya nilai bobot yang diterima tiap neuron berbeda. Sukses beralgoritma 2012 56 Pemodelan jaringan pada syaraf tiruan sering dikategorikan menjadi tiga yaitu : Single layer, multi layer dan competitve layer. Namun pada pembahasan kali ini hanya akan dibahas single layer dan multi layer, karena mengingat kaidah pelatihannya menggunakan algoritma backpropagation. Secara umum , tiap unit pada lapisan (Layer) yang sama atau dapat kita sebut neuron mempunyai tingkah laku yang sama untuk pemrosesan sinyal data. Hanya hal terpenting yang perlu diperhatikan adalah penentuan penggunaan jenis fungsi aktifasi pada masing-masing unit pada lapisan tersebut dan pola koneksi pembobot antar lapisan. Namun biasanya unit pada lapisan yang sama mempunyai jenis fungsi aktifasi yang sama dan pola koneksi pembobot yang sama pula. Untuk pemilihan jumlah layer bukan berarti pemilihan layer untuk neuron, namun pemilihan layer untuk penghubung jalur pembobot antar neuron. Jadi variabel terpenting untuk pengenalan pola adalah pembobotnya. Faktor Keberhasilan Jaringan Syaraf Tiruan Jaringan Syaraf Tiruan mengalami “booming” dan diminati beberapa tahun terakhir ini, dan sangat sukses digunakan untuk memecahkan berbagai masaalah dalam berbagai disiplin ilmu seperti : bidang finansial, kedokteran, teknik, geologi dan fisika. Lebih jauh lagi, bahwa sesuatu masaalah dengan menggunakan Jaringan Syaraf Tiruan dapat diprediksi, dikelompokkan dan dikontrol. Ada beberapa faktor yang mendukung keberhasilan tersebut antara lain : Handal. Jaringan Syaraf Tiruan adalah teknik pemodelan yang sangat memuaskan yang dapat membuat model suatu fungsi yang sangat kompleks. Khususnya Jaringan Syaraf Tiruan nonlinear. Sejak beberapa tahun, model linear umumnya digunakan dimana model linear dikenal dengan strategi optimasi. Jaringan Syaraf Tiruan juga menggunakan model nonlinear dengan berbagai variabel. Mudah digunakan. Jaringan Syaraf Tiruan dipelajari dengan contoh. Pengguna Jaringan Syaraf Tiruan mengumpulkan data dan melakukan pembelajaran algoritma untuk mempelajari secara otomatis struktur data, sehingga pengguna tidak memerlukan pengetahuan khusus mengenai bagaimana memilih dan mempersiapkan data, bagaimana memilih Jaringan Syaraf Tiruan yang tepat, bagaimana membaca hasil, tingkatan pengetahuan yang diperlukan untuk keberhasilan Menggunakan Jaringan Syaraf Tiruan tidak lebih dari pemecahan masalah yang menggunakan metode statistik nonlinear yang telah dikenal. Aplikasi Jaringan Syaraf Tiruan Sukses beralgoritma 2012 57 Jaringan Syaraf Tiruan mampu menggambarkan setiap situasi adanya sebuah hubungan antara variabel predictor (independents, inputs) dan variabel predicted (dependents, outputs), ketika hubungan tersebut sangat kompleks dan tidak mudah untuk menjelaskan kedalam istilah yang umum dari “correlations” atau “differences between groups”. Kegunaan Jaringan saraf tiruan pada umumnya digunakan untuk tugas atau pekerjaan yang kurang praktis jika dikerjakan secara manual. Kegunaan Dalam Kehidupan Nyata  Perkiraan Fungsi, atau Analisis Regresi, termasuk prediksi time series dan modeling.  Klasifikasi, termasuk pengenalan pola dan pengenalan urutan, serta pengambil keputusan dalam pengurutan.  Pengolahan data, termasuk penyaringan, pengelompokan, dan kompresi.  Robotik Kesimpulan Jaringan Syaraf Tiruan mulai dilirik banyak kalangan karena mempunyai banyak kelebihan dibandingkan system konvensional. Jaringan Syaraf Tiruan mewakili pikiran manusia untuk mendekatkan diri dengan komputer, maksudnya Jaringan Syaraf Tiruan dirancang agar komputer dapat bekerja seperti/layaknya otak manusia. Berikut ini beberapa keunggulan dari Jaringan Syaraf Tiruan adalah : - Adaptive learning: Suatu kemampuan untuk melakukan suatu kegiatan yang didasarkan atas data yang diberikan pada saat pembelajaran atau dari pengalaman sebelumnya. - Self-Organisation: Dapat membuat organisasi sendiri atau me- representasikan informasi yang didapat pada saat pembelajaran. - Real Time Operation: Dapat menghasilkan perhitungan parallel dan dengan device hardware yang khusus yang dibuat akan memberikan keuntungan dengan adanya kemampuan tersebut. - Fault Tolerance melalui Redundant Information Coding: Kerusakan pada bagian tertentu dari jaringan akan mengakibatkan penurunan kemampuan. - Beberapa jaringan mempunyai kemampuan untuk menahan kerusakan besar pada jaringan. - Kelebihan Jaringan Syaraf Tiruan terletak pada kemampuan belajar yang dimilikinya. Dengan kemampuan tersebut pengguna tidak perlu merumuskan kaidah atau fungsinya. Jaringan Syaraf Tiruan akan Sukses beralgoritma 2012 58 belajar mencari sendiri kaidah atau fungsi tersebut. Dengan demikian Jaringan Syaraf Tiruan mampu digunakan untuk menyelesaikan masalah yang rumit dan atau masalah yang terdapat kaidah atau fungsi yang tidak diketahui. - Kemampuan Jaringan Syaraf Tiruan dalam menyelesaikan masalah yang rumit telah dibuktikan dalam berbagai macam penelitian. Sukses beralgoritma 2012 59 DAFTAR PUSTAKA Ilmukomputer.com http://id.wikipedia.org http://eprints.undip.ac.id/2226/1/1_Sarwadi_-_Anjar_Krismi.pdf Membangun Jaringan Syaraf Tiruan, Sri Kusumadewi, 2004, Graha Ilmu, Yogyakarta Neural Network by Nikolay Nikolaef http://homepages.gold .ac.uk/nikolaef/cis311.html.course_outline_for_fall_2004