13
BAB 2 LANDASAN TEORI
2.1
Algoritma Dalam matematika dan komputasi, algoritma merupakan kumpulan perintah
untuk menyelesaikan suatu masalah. Perintah-perintah ini dapat diterjemahkan secara bertahap dari awal hingga akhir. Masalah tersebut dapat berupa apa saja, dengan catatan untuk setiap masalah, ada kriteria kondisi awal yang harus dipenuhi sebelum menjalankan algoritma. Algoritma akan dapat selalu berakhir untuk semua kondisi awal yang memenuhi kriteria, dalam hal ini berbeda dengan heuristic (kondisi file sebelumnya). Algoritma sering mempunyai langkah pengulangan (iterasi) atau memerlukan keputusan (logika Boolean dan perbandingan) sampai tugasnya selesai. Desain dan analisis algoritma adalah suatu cabang khusus dalam ilmu komputer yang
mempelajari karakteristik
dan performa dari suatu algoritma dalam
menyelesaikan masalah, terlepas dari implementasi algoritma tersebut. Dalam cabang disiplin ini algoritma dipelajari secara abstrak, terlepas dari sistem komputer atau bahasa pemrograman yang digunakan. Algoritma yang berbeda dapat diterapkan pada suatu masalah dengan kriteria yang sama. Kompleksitas dari suatu algoritma merupakan ukuran seberapa banyak komputasi yang dibutuhkan algoritma tersebut untuk menyelesaikan masalah. Secara informal, algoritma yang dapat menyelesaikan suatu permasalahan dalam waktu yang singkat memiliki kompleksitas yang rendah, sementara algoritma yang membutuhkan waktu lama untuk menyelesaikan masalahnya mempunyai kompleksitas yang tinggi.
2.1.1 Klasifikasi Algoritma Terdapat beragam klasifikasi algoritma dan setiap klasifikasi mempunyai alasan tersendiri. Salah satu cara untuk melakukan klasifikasi jenis-jenis algoritma adalah
14
dengan memperhatikan paradigma dan metode yang digunakan untuk mendesain algoritma tersebut. Beberapa paradigma yang digunakan dalam menyusun suatu algoritma akan dipaparkan dibagian ini. Masing- masing paradigma dapat digunakan dalam banyak algoritma yang berbeda ( Knuth, DE, 1973 ). a) Divide and Conquer, paradigma untuk membagi suatu permasalahan besar menjadi permasalahan-permasalahan yang lebih kecil. Pembagian masalah ini dilakukan terus menerus sampai ditemukan bagian masalah kecil yang mudah untuk dipecahkan. Singkatnya menyelesaikan keseluruhan masalah dengan membagi masalah besar dan kemudian meme cahkan permasalahanpermasalahan kecil yang terbentuk. b) Dynamic programming, paradigma pemrograman dinamik akan sesuai jika digunakan pada suatu masalah yang mengandung sub-struktur yang optimal dan mengandung beberapa bagian permasalahan yang tumpang tind ih . Paradigma ini sekilas terlihat mirip dengan paradigma Divide and Conquer, sama-sama
mencoba
untuk
membagi
permasalahan
menjadi
sub
permasalahan yang lebih kecil, tapi secara intrinsik ada perbedaan dari karakter permasalahan yang dihadapi. c) Metode serakah,
Sebuah algoritma serakah
mirip
dengan
sebuah
pemrograman dinamik, bedanya jawaban dari submasalah tidak perlu diketahui dalam setiap tahap dan menggunakan pilihan "serakah" apa yang dilihat terbaik pada saat itu. 2.1.2 Efisiensi Algoritma Dalam menganalisis efisiensi suatu algoritma, khusunya berpusat pada kecepatan algoritma sebagai fungsi masukannya dan menentukan jumlah langkah yang dilakukan; sedangkan waktu eksekusi (running time) bergantung pada bahasa pemrograman, kualitas kode program yang dihasilkan, dan mesin yang digunakan. Ketiga faktor tersebut penting, namun menghasilkan kecepatan atau kemunduran waktu eksekusi algoritma yang konstan; sebuah PC 2 GHz lebih cepat dibandingkan
15
PC 1 GHz, bahasa pemrograman yang dikompilasi memproses sepuluh kali lebih cepat daripada yang interpretasi, kode program yang “rapi” akan 30% lebih cepat daripada yang “tidak rapi”, dan sebagainya. Akan tetapi, algoritma yang lebih efisien akan menghasilkan kecepatan yang sebanding dengan ukuran masukannya. Selain itu, menganalisis efisiensi algoritma dapat juga dengan menunjukkan analisis worst case. Analisis worst case menentukan waktu eksekusi terlama (keadaan terburuk) suatu algoritma. Misalnya, pencarian dalam sebuah daftar (list), maka worst case-nya, objek yang dicari ditemukan (tidak ditemukan) dengan melewati seluruh daftar tersebut. Analisis worst case berguna karena bagaimanapun, waktu eksekusi algoritma tidak mungkin lebih lambat daripada batasan yang ditetapkan. Algoritma dengan worst case yang “baik”, waktu eksekusinya akan selalu lebih “cepat”. 2.1.3 Krite ria Analisis Program Beberapa hal yang harus diperhatikan dalam menganalisis algoritma : 1. Kebenaran (Correctness) Ada tiga hal yang dipertimbangkan dalam membuktikan kebenaran suatu algoritma. Sebelum menentukan apakah algoritma tersebut adalah benar, harus dipahami dengan jelas definisi tentang “benar”. “Benar” dapat diartikan sebagai masukan yang diharapkan dan keluaran yang dihasilkan untuk setiap masukan. Untuk membuktikan kebenaran suatu program, program yang besar dan kompleks dapat dibagi dalam beberapa modul kecil. Sehingga, jika dapat dibuktikan bahwa modul- modul kecil adalah benar, maka seluruh program juga benar. 2. Jumlah Operasi yang Dilakukan (Amount of Work Done) Ukuran
jumlah
operasi
yang
dilakukan
dapat
digunakan
untuk
membandingkan dua algoritma untuk masalah yang sama, sehingga dapat ditentukan algoritma yang lebih efisien. Akan lebih baik jika ukuran jumlah operasi dapat menandakan waktu eksekusi yang sebenarnya dari kedua algoritma yang dibandingkan, namun sebaiknya tidak menggunakan waktu
16
eksekusi karena beberapa alasan. Pertama, kecepatan pemrosesan setiap komputer berbeda. Kedua, setiap gaya pemrograman bervariasi dalam menghitung jumlah instruksi yang dieksekusi oleh program. Untuk menentukan efisiensi suatu algoritma, maka pengukuran harus terlepas dari penggunaan komputer dan gaya pemrograman yang bervariasi. Maka, efisiensi suatu algoritma dapat diukur dengan menghitung jumlah operasi dasar yang dilakukan oleh algoritma tersebut. M isalnya, untuk menemukan x dalam daftar nama,
maka operasi dasarnya adalah
membandingkan x dengan setiap entri pada daftar tersebut. 3. Analisis Worst Case Jumlah operasi yang dilakukan tidak dapat digambarkan dengan sebuah nilai karena jumlah langkah tidak sama untuk setiap masukan. Misalnya, menyelesaikan dua belas sistem persamaan linier dapat menghemat pekerjaan jika banyak koefisiennya bernilai nol.Dengan demikian, yang harus dilakukan adalah menghitung ukuran masukan untuk sebuah masalah. Misalnya, untuk menemukan x dalam daftar nama, maka masukannya adalah jumlah nama yang ada dalam daftar tersebut.Namun, jika ukuran masukannya tetap, jumlah operasi yang dilakukan tergantung pada masukan tertentu. Dengan demikian, tingkah laku suatu algoritma dapat diga mbarkan sebagai kompleksitas worst case. 4. Optimal (Optimality) Untuk menganalisis suatu algoritma, biasanya selalu menggunakan kelas algoritma dan ukuran kompleksitas, misalnya, jumlah operasi dasar yang dilakukan. Sebuah algoritma disebut optimal (untuk worst case) jika tidak ada algoritma yang dapat melakukan operasi dasar yang lebih sedikit (untuk worst case). 5. Lower Bound Untuk membuktikan bahwa suatu algoritma adalah optimal, tidak diperlukan menganalisis setiap algoritma. Dengan membuktikan teorema-teorema yang
17
menentukan lower bound pada jumlah operasi yang diperlukan untuk menyelesaikan masalah, maka algoritma yang dapat melakukan jumlah operasi tersebut disebut optimal. 2.1.4 Analisis Program Ada dua hal yang diperhatikan dalam menganalisis sebuah program, yaitu waktu dan ruang. Waktu yaitu waktu yang diperlukan untuk mengeksekusi algoritma pada beberapa masukan. Ruang yaitu memori yang digunakan oleh algoritma ketika mengeksekusi masukan tersebut. Namun, analisis program ini akan lebih d ifokuskan pada analisis waktu ( Thiang,2001 ) Ada dua definisi umum tentang analisis waktu : 1. Waktu eksekusi program pada masukan tertentu adalah jumlah instruksi yang dijalankan oleh program pada masukan tersebut. Umumnya, ukuran masukan dinyatakan dengan n dan waktu eksekusinya sebagai fungsi dari n. Pada masukan n, waktu eksekusinya bervariasi tergantung pada masukan tertentu. Misalnya, pencarian dalam sebuah array, target mungkin saja berada pada elemen pertama, terakhir, atau bahkan tidak ditemukan. 2. Worst case waktu eksekusi algoritma pada masukan n adalah jumlah instruksi maksimum yang dieksekusi oleh algoritma untuk setiap masukan n tersebut. Worst case dinyatakan sebagai fungsi dari n. Umumnya, worst case menyatakan tingkat pertumbuhan (rate of growth) waktunya; yaitu seberapa cepat bertumbuh ketika n menjadi ∞. Untuk pencarian linier pada array n, waktu eksekusinya bertumbuh secara linier dengan n. Jadi, rate of growthnya adalah linier. Umumnya, order of growth dinyatakan dengan notasi bigO. Definisi big O: misalkan f dan g adalah dua buah fungsi dari bilangan bulat ke bilangan riil. Dapat dikatakan bahwa f(x) adalah O(g(x)) jika ada suatu konstanta C dan k sedemikian hingga |f(x)| ≤ C|g(x)|, saat x > k. (Munir, 2002). Saat menganalisa pertumbuhan dari fungsi kompleksitas, f(x) dan g(x) selalu positif. Oleh karena itu, persyaratan big-O diatas dapat disederhanakan menjadi f(x) ≤ Cg(x) saat x > k.
18
2.2
Bahasa Pemograman
Bahasa program merupakan suatu wahana untuk menuangkan pikiran manusia yang dapat dimengerti oleh mesin komputer sehingga bernilai guna. Suatu bahasa program akan terikat aturan dari paradigma bahasa. Ada berbagai macam paradigma bahasa : Prosedural, Fungsional, Deklaratif, Object Oriented, Konkuren. Adapun konsep-konsep dasar dalam pemograman adalah sebagai berikut (Munir,2002) : a. Simulasi , sensibilitas terhadap masalah dan kemungkinan solusi. Kegiatan dilakukan di kelas, melalui permainan. Contoh : Mengurutkan tinggi badan mahasiswa dari tinggi
ke pendek atau sebaliknya. Permainan dapat
dilakukan secara manual maupun dengan komputer. b. Analisis masalah secara lebih formal dan membuat spesifikasi dan algoritma dalam notasi yang ditetapkan. Mahasiswa harus menuliskan solusi algoritmiknya dalam notasi standar di kelas. Penulisan notasi algoritmik bertujuan untuk menyeragamkan pemahaman tentang algoritma program yang terbebas dari sintak (aturan) penulisan bahasa program. c. Menulis program, yaitu menterjemahkan notasi algoritmik ke dalam sintak bahasa program. d. Debugging dan menguji coba program. Hal ini bertujuan untuk mendapatkan program yang benar. Program dikatakan benar jika terbebas dari salah lojik dan sintak bahasa. Secara ideal mahasiswa hanya diberi kesempatan untuk me-run program sebanyak 2 kali : pertama untuk membersihkan program dari kesalahan sintak dan kedua untuk mendapatkan program benar. Pada tahap ini diharapkan tidak terjadi kesalahan lojik jika analisa benar. e. Mengamati peristiwa eksekusi, perlu dilakukan untuk meningkatkan kepercayaan bahwa jika analisa benar maka sisa pekerjaan menjadi mudah.
19
Pada pemrograman prosedural, aspek ini penting untuk memahami fenomena eksekusi dan perubahaan nilai suatu struktur data. f.
Membaca program : orang akan dapat menulis dengan baik kalau sering membaca. Hal ini juga berlaku dalam memprogram. Kegiatan yang dapat dilakukan di kelas adalah dengan saling tukar menukar teks algoritma, dan saling mengkritik algoritma teman. Mahasiswa harus berlatih sendiri pada kegiatan belajar bersama.
g. Membuktikan kebenaran program secara formal , satu-satunya hal yang menjamin kebenaran, tetapi kontradiktif dan sulit diterapkan dalam kehidupan sehari- hari. Program yang hanya lima baris pembuktiannya bisa sehalaman, sehingga seringkali tidak pernah diterapkan dalam aplikasi nyata. Aktifitas ini dicakup dalam matakuliah Analisis Algoritma.
2.3
Algoritma Genetika
2.3.1 Pengertian Algoritma Genetika Algoritma genetika adalah suatu algoritma pencarian yang meniru mekanisme dari genetika alam. Algoritma Genetika banyak dipakai pada aplikasi bisnis, teknik maupun pada bidang keilmuan lainnya. Algoritma ini dimulai dengan kumpulan solusi yang disebut dengan populasi. Solusi-solusi dari sebuah populasi diambil dan digunakan untuk membentuk populasi yang baru. Hal ini dimotivasi dengan harapan bahwa populasi yang baru dibentuk tersebut akan lebih baik daripada yang lama. Solusi-solusi yang dipilih untuk membentuk solusisolusi yang baru dipilih sesuai dengan fitness mereka masing- masing (Juniawati, 2003). Dalam buku dengan judul “Adaption in Natural and Artificial System” yang terbit pada tahun 1975, prinsip algoritma genetika diambil dari teori Darwin yaitu setiap makhluk hidup akan menurunkan satu atau beberapa karakter ke anak atau keturunannya (Bambrick, 1975). Di dalam proses tersebut dapat terjadi variasi yang disebabkan karena adanya mutasi, sehingga keturunan yang dihasilkan dapat
20
mempunyai kelebihan bahkan tidak memiliki kekurangan dari orangtuanya. Setiap makhluk hidup akan mengalami seleksi alam, sehingga makhluk hidup yang mempunyai kemampuan untuk beradaptasi dengan lingkungan sekitarnya dapat bertahan sampai generasi selanjutnya. Semakin bagus atau sesuai fitness dari sebuah solusi maka solusi tersebut mempunyai peluang besar untuk dipilih. Proses ini dilakukan berulang sampai kondisi tertentu dipenuhi.
2.3.2 Beberapa Definisi Penting Dalam Algoritma Genetika
Beberapa definisi penting dalam algoritma genetika antara lain : a) Genotype (Gen), sebuah nilai yang menyatakan satuan dasar yang membentuk suatu arti tertentu dalam satu kesatuan gen yang dinamakan kromosom. Dalam algoritma genetika, gen ini bisa berupa nilai biner, float, integer maupun karakter. b) Allele, merupakan nilai dari gen. c) Kromosom, gabungan gen- gen yang membentuk nilai tertentu. d) Individu, menyatakan satu nilai atau keadaan yang menyatakan salah satu solusi yang mungkin dari permasalahan yang diangkat. e) Populasi, merupakan sekumpulan individu yang akan diproses bersama dalam satu siklus proses evolusi. f) Generasi, menyatakan satu-satuan siklus proses evolusi. g) NilaiFitness, menyatakan seberapa baik nilai dari suatu individu atau solusi yang didapatkan.
2.3.3 Dasar Algoritma Genetika Algoritma genetika pertama kali dikemukakan oleh John Holland awal tahun 1975. John Holland mengemukakan bahwa algoritma genetika merupakan program komputer yang meniru proses evolusi alam. Kerangka dasar dari algoritma genetika sering disebut Simple Genetic Algorithm oleh John Holland dinyatakan sebagai berikut (Bambrick, 1975) : 1. [Start] ,Generasi populasi pertama secara random sebanyak n individu.
21
2. [Fitness], Evaluasi nilai fitness f(x) dari setiap individu x didalam populasi. 3. [New Population], Bentuk populasi baru dengan melakukan pengulangan langkah-langkah dibawah ini sehingga didapatkan populasi baru. a. [Selection], Pilih 2 individu sebagai orangtua dari sebuah populasi sesuai dengan fitness mereka (Semakin baik fitness, maka semakin besar peluang mereka untuk dipilih). b. [Crossover], Lakukan persilangan antara kedua orangtua sesuai dengan probabilitas crossover untuk membentuk keturunan yang baru. Jika tidak terjadi persilangan maka keturunan yang dihasilkan akan sama persis dengan orangtuanya. c. [Mutation], Mutasi setiap keturunan yang baru sesuai dengan probabilitas mutasi di setiap gen. d. [Accepting], Tempatkan keturunan yang baru sebagai populasi yang baru. 4. [Replace], Gunakan populasi yang baru dibentuk untuk menjalankan algoritma. 5. [Test], Jika kondisi akhir dipenuhi maka berhenti dan tampilkan solusi dari populasi. 6. [Loop], Kembali ke nomor 2.
2.4
Penerapan Algoritma Matematika
2.4.1 Membangun Generasi Awal Langkah pertama dalam algoritma ini adalah membentuk sejumlah populasi awal yang digunakan untuk mencari penyelesaian optimal. Populasi awal yang dibangun dalam tugas akhir ini dengan menggunakan bilangan random (acak) dengan range bilangan yang telah ditentukan.
2.4.2 Representasi Kromosom Algoritma genetika tidak beroperasi dengan penyelesaian asli dari suatu masalah
22
tetapi beroperasi dengan dengan penyelesaian yang te lah direpresentasikan. Representasi kromosom merupakan proses pengkodean dari penyelesaian asli dari suatu permasalahan. Pengkodean kandidat penyelesaian ini disebut dengan kromosom. Pengkodean tersebut meliputi penyandian gen, dengan satu gen mewakili satu variabel.
2.4.3 Fungsi Fitness
Fungsi fitness digunakan untuk proses evaluasi kromosom agar memperoleh kromosom yang diinginkan. Fungsi ini membedakan kualitas dari kromosom untuk mengetahui seberapa baik kromosom yang dihasilkan. Semakin tinggi nilai fitness akan semakin besar kemungkinan kromosom tersebut terpilih ke generasi berikutnya. Jadi nilai penalty berbanding terbalik dengan nilai fitness, semakin kecil nilai penalty (jumlah pelanggaran) semakin besar nilai fitnessnya.
2.4.4 Seleksi Setiap kromosom yang terdapat dalam populasi akan melalui proses seleksi untuk dipilih menjadi orangtua. Sesuai dengan teori Evolusi Darwin maka kromosom yang baik akan bertahan dan menghasilkan keturunan yang baru untuk generasi selanjutnya. Ada beberapa metode seleksi (Munir, 2005), yaitu a. Steady-State Selection, Pemikiran utama dari metode seleksi ini adalah sebagian kromosom dari generasi lama tetap bertahan atau berada di generasi selanjutnya. Algoritma genetika menerapkan pemikiran tersebut dengan cara, didalam setiap generasi sejumlah kromosom yang mempunyai nilai fitness tinggi dipilih untuk diproses untuk menghasilkan keturunan yang baru sedangkan kromosom dengan nilai fitness rendah dibuang. b. Elitism, Pembentukan populasi baru dengan crossover dan mutasi ada kemungkinan kromosom yang paling baik hilang. Oleh karena itu metode ini sebagai tahap awal memasukkan kromosom dengan nilai fitness yang paling baik atau beberapa kromosom dengan nilai fitnes yang tinggi atau cukup
23
tinggi dari generasi yang lama kedalam generasi yang baru. Kemudian sisa kromosom dalam generasi yang baru diperoleh dengan cara reproduksi biasa. c. Roulette Wheel Selection, Kromosom dipilih berdasarkan nilai fitness, semakin besar nilai fitness maka kromosom tersebut mempunyai peluang untuk dipilih beberapa kali.
2.4.5 Ope rator Genetika Operator genetika dipergunakan untuk mengkombinasi (modifikasi) individu dalam aliran populasi guna mencetak individu pada generasi berikutnya. Ada dua operator genetika yaitu crossover dan mutation (Suyanto, 2005). 1. Persilangan (Crossover ) Operator persilangan merupakan operasi yang bekerja untuk menggabungan dua kromosom orangtua (parent) menjadi kromosom baru (offspring). Tidak semua kromosom mengalami persilangan. Jumlah kromosom dalam populasi yang mengalami persilangan ditentukan oleh paramater yang disebut dengan crossover rate (probabilitas persilangan) . Jenis operator persilangan yaitu: a. One point crossover Sebuah titik crossover dipilih, selanjutnya string biner mulai dari awal kromosom sampai dengan titik tersebut disalin dari salah satu orangtua ke keturunannya, kemudian sisa bit keturunan disalin dari orangtua yang kedua. b. Two point crossover Dua titik crossover dipilih, selanjutnya string biner mulai dari awal kromosom sampai dengan titik crossover pertama disalin dari salah satu orangtua ke keturunannya kemudian mulai dari titik crossover pertama sampai dengan titik kedua disalin dari orangtua kedua. Sisanya disalin dari orangtua pertama. 2. Mutasi Setelah crossover dilakukan, proses reproduksi dilanjutkan dengan mutasi. Hal ini dilakukan untuk
menghindari solusi-solusi dalam populasi
mempunyai nilai lokal optimum. Mutasi adalah proses mengubah gen dari
24
keturunan secara random. Tidak setiap gen selalu dimutasi tetapi mutasi dikontrol dengan probabilitas tertentu yang disebut dengan mutation rate (probabilitas mutasi) dengan notasi Pm. Jenis operator mutasi antara lain: a. Mutasi Terarah Mutasi terarah tergantung dari informasi gen. Informasi gen tersebut berupa nilai pelanggaran gen (violation score). Ini berarti bahwa setiap gen mempunyai peluang yang berbeda untuk terjadi mutasi. Gen yang mempunyai nilai pelanggaran yang lebih besar maka gen tersebut mempunyai peluang untuk terjadi mutasi. Mutasi ini menghubungkan nilai pelanggaran relatif (nilai pelanggaran suatu gen dibagi dengan nilai pelanggaran total suatu kromosom) dengan probabilitas terjadinya mutasi dari suatu gen pada kromosom. Hubungan tersebut dinyatakan secara matematis sebagai berikut: nri = n(i)1+ntotal pmi = (1+nr(i))2pm Keterangan persamaan: nr(i)
= nilai pelanggaran relative gen ke- i.
ntotal
= nilai pelanggaran total kromosom.
pm(i)
= probabilitas mutasi gen ke-i.
pm
= probabilitas mutasi
2.4.6 Parameter Genetika Pengoperasian algoritma genetika dibutuhkan 4 parameter (Suyanto, 2005) yaitu:
1. Probabilitas Persilangan (Probability Crossover) Menunjukkan kemungkinan crossover terjadi antara 2 kromosom. Jika tidak terjadi crossover maka keturunannya akan sama persis dengan kromosom orangtua, tetapi tidak berarti generasi yang baru akan sama persis dengan
25
generasi yang lama. Jika probabilitas crossover 100% maka semua keturunannya dihasilkan dari crossover. Crossover dilakukan dengan harapan bahwa kromosom yang baru akan lebih baik.
2. Probabilitas Mutasi (Probability Mutation) Menunjukkan kemungkinan mutasi terjadi pada gen-gen yang menyusun sebuah kromosom. Jika tidak terjadi mutasi maka keturunan yang dihasilka n setelah crossover tidak berubah. Jika terjadi mutasi bagian kromosom akan berubah. Jika probabilitasnya 100 %, semua kromosom dimutasi. Jika probabilitasnya 0%, tidak ada yang mengalami mutasi.
3. Jumlah Individu Menunjukkan jumlah kromosom yang terdapat dalam populasi (dalam satu generasi). Jika hanya sedikit kromosom dalam populasi maka algoritma genetika akan mempunyai sedikit variasi kemungkinan untuk melakukan crossover antara orangtua karena hanya sebagian kecil dari search space yang dipakai. Sebaliknya jika terlalu banyak maka algoritma genetika akan berjalan lambat.
4. Jumlah Populasi Menentukan jumlah populasi atau banyaknya generasi yang dihasilkan, digunakan sebagai batas akhir proses seleksi, persilangan, dan mutasi.
