BAB 2 LANDASAN TEORI
2.1
Teknik Simulasi Teknik Simulasi merupakan cara menampilkan kembali kondisi suatu keadaan
dalam bentuk model untuk dipelajari, diuji, dan sebagainya. Banyak para ahli memberikan definisi tentang simulasi (E. Suryani, 2006). Beberapa diantaranya adalah sebagai berikut : a. Emshoff dan Simon (1970) Simulasi didefinisikan sebagai suatu model sistem dimana komponennya direpresentasikan oleh proses-proses aritmatika dan logika yang dijalankan computer untuk memperkirakan sifat-sifat dinamis sitem tersebut. b. Shannon (1975) Simulasi merupakan proses perancangan model dari system nyata yang dilanjutkan dengan pelaksanaan eksperimen terhadap model untuk mempelajari perilaku sistem atau evaluasi strategi. c. Banks dan Carson (1984) Simulasi adalah tiruan dari sistem nyata yang dikerjakan secara manual atau komputer, yang kemudian diobservasi dan disimpulkan untuk mempelajari karakterisasi sistem. d. Hoover dan Perry (1990) Simulasi merupakan proses perancangan model matematis atau logis dari sistem nyata, melakukan eksperimen terhadap model dengan menggunakan komputer untuk menggambarkan, menjelaskan dan memprediksi perilaku sistem.
7 e. Law dan Kelton (1991) Simulasi didefinisikan sebagai sekumpulan metode dan aplikasi untuk menirukan atau merepresentasikan perilaku dari suatu sistem nyata, yang biasanya dilakukan pada komputer dengan menggunakan perangkat lunak tertentu. f. Chosnevis (1994) Simulasi merupakan proses aplikasi membangun model dari sistem nyata atau usulan sistem, melakukan eksperimen dengan model tersebut untuk menjelaskan perilaku sistem, mempelajari kinerja sistem, atau untuk membangun sistem baru sesuai dengan kinerja yang diinginkan.
Simulasi mempelajari atau memprediksi sesuatu yang belum terjadi dengan cara membuat model sistem yang dipelajari dan selanjutnya mengadakan eksperimen secara numerik dengan menggunakan komputer. Simulasi menurut tekniknya dapat dibedakan menjadi dua, yaitu simulasi secara langsung (physical simulation) dan simulasi dengan bantuan komputer (computer simulation). Computer simulation biasanya digunakan apabila simulasi tersebut tidak dapat diterapkan secara langsung di lapangan. Computer Simulation ini diikuti dengan penggunaan komputer untuk mengkombinasikan komponen-komponen dari model masalah dan melakukan suatu analisis untuk mengetahui akibat dari hubungan antar komponen tersebut.
2.2
Sistem Informasi Geografis Sistem Informasi Geografis (SIG) pada dasarnya merupakan gabungan tiga unsur
pokok yaitu sistem, informasi, dan geografis. Dengan melihat unsur-unsur pokoknya,
8 maka jelas sistem informasi geografis merupakan salah satu sistem informasi dengan tambahan unsur “geografis”. Sistem Informasi Geografis diartikan sebagai sistem informasi yang digunakan untuk memasukkan, menyimpan, memanggil kembali, mengolah, menganalisis, dan menghasilkan data bereferensi geografis atau data geospasial, untuk mendukung keputusan dalam perencanaan dan pengelolaan penggunaan lahan, sumber daya alam, lingkungan transportasi, fasilitas kota, dan pelayanan umum lainnya. Beberapa kemampuan SIG : a. Dapat mengumpulkan data geografi. b. Dapat mengitegrasikan data geografi (spasial dan atribut) c. Dapat memeriksa, mengupdate, data geografi. d. Dapat menyimpan dan memanggil kembali data geografi. e. Dapat memanipulasi data geografi. f. Dapat menganalisa data geografi. g. Dapat menghasilkan output. Menurut Prahasta (2005), SIG dapat merepresentasikan real world (dunia nyata) di atas monitor komputer sebagaimana lembaran peta dapat merepresentasikan dunia nyata di atas kertas. SIG menyimpan semua informasi sebagai atribut-atribut di dalam basis data. Kemudian, SIG membentuk dan menyimpannya di dalam tabel-tabel (relational). Setelah itu, SIG menghubungkan atribut-atribut yang ada dengan tabel-tabel yang bersangkutan. Dengan demikian, atribut-atribut tersebut dapat diakses melalui lokasi-lokasi unsur-unsur peta, dan sebaliknya. SIG menghubungkan sekumpulan unsurunsur peta dengan atribut-atributnya di dalam satuan-satuan yang disebut layer. Kumpulan dari layer-layer ini akan membentuk basis data SIG. Dengan demikian,
9 perancangan basis data merupakan hal yang esensial di dalam SIG. Rancangan basis data akan menentukan efektivitas dan efisiensi proses-proses masukan, pengelolaan, dan keluaran SIG. Informasi grafis suatu objek dapat dimasukkan dalam bentuk : a. Titik Titik adalah representasi paling sederhana untuk suatu objek. Pada skala besar suatu bangunan ditampilkan dengan polygon, tetapi dalam skala kecil ditampilkan dengan menggunakan titik. b. Garis Garis adalah bentuk linier yang akan menghubungkan paling sedikit dua titik dan digunakan untuk merepresentasikan objek-objek satu dimensi. c. Polygon Digunakan untuk merepresentasikan objek-objek dua dimensi, suatu danau, batas propinsi, dan lain-lain.
2.3
Pemetaan Menurut Prahasta (2005), peta adalah suatu alat peraga untuk menyampaikan
suatu ide berupa sebuah gambar mengenai tinggi rendahnya suatu daerah (topografi), penyebaran penduduk, jaringan jalan dan hal lainnya yang berhubungan dengan kedudukan dalam ruang. Peta dilukiskan dengan skala tertentu dengan tulisan atau simbol sebagai keterangan yang dapat dilihat dari atas. Peta dapat meliputi wilayah yang luas, dapat juga hanya mencakup wilayah yang sempit. Peta dalam bahasa Inggris yang berarti map, dan dalam bahasa Yunani berupa mappa. Ilmu pengetahuan yang mempelajari peta disebut kartografi.
10 Menurut Kamus Besar Bahasa Indonesia, peta adalah gambar atau lukisan pada kertas dan sebagainya yang menunjukkan letak tanah, laut, sungai, gunung, dan sebagainya atau dapat juga diartikan bahwa peta merupakan representasi melalui gambar dari suatu daerah yang menyatakan sifat-sifat seperti batas daerah, sifat permukaan. Ada beberapa jenis peta menurut kegunaannya yang terdapat dalam The World Encyclopedia (1991) : a. General Reference Map (Peta Referensi Umum) Peta ini digunakan untuk mengidentifikasi dan verivikasi macam-macam bentuk geografi termasuk fitur tanah, badan air, perkotaan, jalan, dan lain sebagainya. b. Mobility Map Peta ini bermanfaat dalam membantu masyarakat dalam menentukan jalur dari satu tempat ke tempat lainnya, digunakan untuk perjalanan di darat, laut, maupun udara. c. Thematic Map (Peta tematik) Peta ini menunjukkan penyebaran dari objek tertentu seperti populasi, curah hujan, sumber daya alam. d. Inventory Map (Peta inventaris) Peta ini menunjukkan lokasi dari fitur khusus misalnya : posisi semua gedung di wilayah Jakarta Barat.
2.4
Teori Tentang Jalan Teori tentang jalan ini diperlukan untuk mengetahui informasi-informasi
mengenai jalan yang digunakan sebagai media untuk meletakkan tempat sampah dalam program yang akan dibuat nantinya.
11 2.4.1 Pengertian Jalan Pengertian jalan menurut Kamus Besar Bahasa Indonesia adalah tempat untuk lalu-lintas orang, kendaraan, dan sebagainya. Sedangkan menurut UU RI No. 13 tahun 1980 tentang jalan, jalan adalah prasarana perhubungan darat yang diperuntukkan bagi lalu-lintas kendaraan dan orang. Pengertian lainnya yang juga disebutkan di dalamnya, jalan adalah prasarana perhubungan darat dalam bentuk apapun meliputi segala bagian jalan termasuk bagian pelengkap dan diperuntukkan bagi lalu-lintas. Bagian pelengkap yang dimaksudkan adalah bangunan yang tidak dapat dipisahkan dari jalan, antara lain jembatan, lintas atas (overpass), lintas bawah (underpass), tempat parkir, gorong-gorong, tembok penahan, dan saluran air jalan. Perlengkapan jalan antara lain rambu-rambu jalan, rambu-rambu lalu lintas, tanda-tanda jalan, pagar pengamanan lalu-lintas, pagar daerah milik jalan dan patok-patok daerah milik jalan.
2.4.2
Jenis Jalan Beberapa jenis jalan menurut UU RI No. 13 tahun 1980 :
a. Jalan arteri adalah jalan yang melayani angkutan utama dengan ciri-ciri perjalanan jarak jauh, kecepatan rata-rata tinggi, dan jumlah kendaraan masuk dibatasi secara efisien. b. Jalan kelektor adalah jalan yang melayani angkutan pengumpulan atau pembagian dengan ciri-ciri jarak perjalanan sedang, kecepatan rata-rata sedang, jumlah jalan masuk dibatasi.
12 c. Jalan lokal adalah jalan yang melayani angkutan setempat dengan ciri-ciri jarak perjalanan sedang, kecepatan rata-rata sedang, dan jumlah jalan masuk tidak dibatasi.
2.5
Teori Tentang Tempat Sampah
2.5.1 Pengertian Sampah Pengertian sampah menurut Kamus Besar Bahasa Indonesia adalah barang atau benda yang dibuang karena tidak terpakai lagi (misalnya kotoran seperti daun, kertas, dan sebagainya). 2.5.2
Jenis - Jenis Sampah Berdasarkan sumbernya, sampah dibedakan menjadi 6 jenis, yaitu :
a. Sampah alam Sampah yang diproduksi di kehidupan liar diintegrasikan melalui proses daur ulang alami, seperti halnya daun-daun kering di hutan yang terurai menjadi tanah. Di luar kehidupan liar, sampah-sampah ini dapat menjadi masalah, misalnya daun-daun kering di lingkungan pemukiman. b. Sampah manusia Sampah manusia adalah istilah yang biasa digunakan terhadap hasil-hasil pencernaan manusia, seperti feces dan urin. Sampah manusia dapat menjadi bahaya serius bagi kesehatan karena dapat digunakan sebagai vector (sarana perkembangan) penyakit. c. Sampah konsumsi Sampah konsumsi merupakan sampah yang dihasilkan oleh pengguna barang, dengan kata lain adalah sampah-sampah yang dibuang ke tempat sampah. Ini
13 adalah sampah yang umum dipikirkan manusia. Meskipun demikian, jumlah sampah kategori ini masih jauh lebih kecil dibandingkan sampah-sampah yang dihasilkan dari proses pertambangan dan industri. d. Sampah nuklir e. Sampah industri f. Sampah pertambangan
Berdasarkan sifatnya, sampah dibedakan menjadi 3 jenis, yaitu : a. Sampah anorganik/kering Sampah anorganik yaitu sampah yang tidak dapat terurai oleh mikroorganisme. Contohnya plastik, karet, kain, timah, besi, dan sebagainya. b. Sampah organik/basah Sampah organik yaitu sampah yang mudah terurai oleh mikroorganisme sehingga mudah membusuk. Contohnya dedaunan, daging, sayuran, dan buah-buahan. c. Sampah Berbahaya Beracun (B3) Sampah berbahaya beracun adalah sejenis sampah yang dapat membahayakan manusia baik secara langsung maupun tidak langsung. Contohnya baterai bekas, sampah medis/rumah sakit, bahan kimia seperti air raksa, dan sebagainya.
Berdasarkan bentuknya, sampah dibedakan menjadi 2 jenis, yaitu : a. Sampah padat Sampah padat adalah segala bahan buangan selain kotoran manusia, urine dan sampah cair. Dapat berupa sampah rumah tangga: sampah dapur, sampah kebun, plastik, metal, gelas dan lain-lain. Menurut bahannya sampah ini dikelompokkan
14 menjadi sampah organik dan sampah anorganik. Sampah organik merupakan sampah yang berasal dari barang yang mengandung bahan-bahan organik, seperti sisa-sisa sayuran, hewan, kertas, potongan-potongan kayu dari peralatan rumah tangga, potongan-potongan ranting, rumput pada waktu pembersihan kebun dan sebagainya. b. Sampah cair Sampah cair adalah bahan cairan yang telah digunakan dan tidak diperlukan kembali dan dibuang ke tempat pembuangan sampah. Sampah cair ini meliputi limbah hitam (yaitu sampah cair yang dihasilkan dari toilet yang mengandung patogen berbahaya), dan limbah rumah tangga (yaitu sampah cair yang dihasilkan dari dapur, kamar mandi, dan tempat cucian).
Sampah yang berada pada setiap fase materi padat, cair, atau gas ketika dilepaskan ke udara bebas dalam fase cair dan gas, sampah dapat dikatakan sebagai emisi/polusi.
2.5.3
Tempat Sampah Tempat sampah yaitu tempat untuk menampung sampah secara sementara, yang
biasanya terbuat dari logam atau plastik. Tempat sampah merupakan fasilitas terpenting dalam penanganan masalah sampah yang ada. Ketersediaan tempat sampah di lokasilokasi yang optimal menjadi salah satu penentu terciptanya kebersihan lingkungan. Di dalam ruangan, tempat sampah umumnya disimpan di dapur untuk membuang sisa keperluan dapur seperti kulit buah atau botol. Ada juga tempat sampah khusus kertas yang digunakan di kantor. Beberapa tempat sampah memiliki penutup pada
15 bagian atasnya untuk menghindari keluarnya bau yang dikeluarkan sampah. Tempat sampah dalam ruangan umumnya dilapisi kantong untuk memudahkan pembuangan sehingga tidak perlu memindahkan tempat sampah ketika sudah penuh. Beberapa tempat umum seperti taman memiliki tempat sampah yang ditempatkan di sisi sepanjang jalan yang secara frekuentif dapat ditemukan di sisi sepanjang jalan. Hal ini untuk menghindari kebiasaan membuang sampah sembarangan yang dapat mengganggu keindahan dan kesehatan lingkungan serta etika sosial.
2.6
Algoritma Kata algoritma berasal dari latinisasi nama seorang ahli matematika dari
Uzbekistan, Al Khawarizmi (770-840), sebagaimana tercantum pada terjemahan karyanya dalam bahasa latin dari abad ke-12 “Algorithmi de numero Indorum”. Pada awalnya kata algoritma adalah istilah yang merujuk kepada aturan-aturan aritmetis untuk menyelesaikan persoalan dengan menggunakan bilangan numerik arab (sebenarnya dari India, seperti tertulis pada judul di atas). Pada abad ke-18, istilah ini berkembang menjadi algoritma, yang mencakup semua prosedur atau urutan langkah yang jelas dan diperlukan untuk menyelesaikan suatu permasalahan. Secara formal, berdasarkan Kamus Besar Bahasa Indonesia, algoritma didefinisikan sebagai urutan logis pengambilan keputusan untuk pemecahan masalah. 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
16 menjalankan algoritma. Algoritma akan dapat selalu berakhir untuk semua kondisi awal yang memenuhi kriteria. Algoritma berbeda dengan program. Program adalah kumpulan instruksi komputer untuk melaksanakan tugas tertentu sehingga menghasilkan output yang diharapkan, sedangkan metode dan tahapan sistematis dalam program adalah algoritma. Program ditulis menggunakan bahasa pemrograman. Program merupakan implementasi dari bahasa pemrograman. Algoritma sering mempunyai langkah pengulangan (iterasi) atau memerlukan keputusan (logika Boolean dan perbandingan) sampai tugasnya selesai.
2.7
Algoritma Genetik Algoritma genetik adalah suatu algoritma pencarian yang berbasis pada
mekanisme seleksi alam dan genetika. Algoritma genetik merupakan salah satu algoritma yang sangat tepat digunakan dalam menyelesaikan masalah optimasi kompleks, yang sulit dilakukan oleh metode konvensional. (A. Desiani dan M. Arhami,2006) Sifat algoritma genetika adalah mencari kemungkinan-kemungkinan dari calon solusi untuk mendapatkan yang optimal bagi penyelesaian masalah. Ruang cakupan dari semua solusi yang layak, yaitu obyek-obyek di antara solusi yang sesuai, dinamakan ruang pencarian. Tiap titik dalam ruang pencarian merepresentasikan satu solusi yang layak. Tiap solusi yang layak dapat ditandai dengan nilai fitness-nya bagi masalah. Algoritma genetik bekerja dari populasi yang merupakan himpunan solusi yang dihasilkan secara acak. Solusi yang dicari dalam algoritma genetik adalah titik (satu atau lebih) di antara solusi yang layak dalam ruang pencarian. Setiap anggota himpunan yang
17 merepresentasikan suatu solusi masalah dinamakan kromosom. Kromosom ini disusun oleh nilai yang menyatakan satuan dasar yang membentuk suatu arti tertentu. Satuan ini bisa berupa nilai biner, float, integer maupun karakter. Satuan disebut Gen, dan nilai dari gen disebut allele. Kromosom dalam suatu populasi berevolusi dalam iterasi yang dinamakan generasi. Pada setiap generasi, kromosom akan melalui proses evaluasi dengan menggunakan alat ukur yang disebut dengan fungsi fitness. Nilai fitness dari suatu kromosom akan menunjukkan kualitas kromosom populasi tersebut. Generasi berikutnya dikenal dengan istilah anak (off-spring) terbentuk dari gabungan 2 kromosom generasi sekarang yang bertindak sebagai induk (parent) dengan menggunakan operator penyilangan (crossover). Selain operator penyilangan, suatu kromosom dapat juga dimodifikasi dengan menggunakan operator mutasi. Populasi generasi yang baru dibentuk dengan cara menyeleksi nilai fitness dari kromosom induk (parent) dan nilai fitness dari kromosom anak (off-spring), serta menolak kromosom-kromosom yang lainnya sehingga ukuran populasi (jumlah kromosom dalam suatu populasi) konstan. Setelah melalui beberapa generasi, maka algoritma ini akan konvergen ke kromosom terbaik.
2.7.1. Struktur Dasar Algoritma Genetik Algoritma Genetik memiliki struktur-struktur dasar yang digunakan dalam menyelesaikan suatu masalah optimalisasi. Menurut, Thiang,dkk (2001) struktur dasar algoritma genetik adalah sebagai berikut :
18 a. Membangkitkan populasi awal Populasi ini dibangkitkan secara random sehingga didapatkan solusi awal. Populasi itu sendiri terdiri atas sejumlah kromosom yang merepresentasikan solusi yang diinginkan. b. Membentuk generasi baru Untuk membentuk generasi baru, digunakan operator reproduksi/seleksi, crossover, dan mutasi. Proses ini dilakukan berulang-ulang sehingga didapatkan jumlah kromosom yang cukup untuk membentuk generasi baru dimana generasi baru ini merupakan representasi dari solusi baru. Generasi baru ini dikenal dengan istilah anak (off-spring). c. Evaluasi solusi Proses ini akan mengevaluasi setiap populasi dengan menghitung nilai fitness setiap kromosom dan mengevaluasinya sampai terpenuhi kriteria berhenti. Bila kriteria berhenti belum terpenuhi maka akan dibentuk lagi generasi baru dengan mengulangi langkah kedua. Beberapa kriteria berhenti yang sering digunakan antara lain : berhenti pada generasi tertentu, berhenti setelah dalam beberapa generasi berturut-turut didapatkan nilai fitness tertinggi tidak berubah, berhenti bila dalam n generasi berikut tidak didapatkan nilai fitness yang lebih tinggi.
19
Gambar 2.1 Siklus Algoritma Genetika 2.7.2 Implementasi Algoritma Genetik Implementasi algoritma genetik secara umum memiliki tahapan proses (algoritma) sebagai berikut : a. Membuat populasi awal yang terdiri dari n buah kromosom (kandidat solusi untuk masalah yang ada) b. Menghitung fitness cost setiap kromosom dalam populasi. c. Melakukan pengulangan proses seleksi, crossover, mutasi hingga n buah kromosom baru (off-spring) terbentuk. d. Mengganti populasi lama dengan populasi yang baru terbentuk. e. Kembali ke langkah (b). Namun sebelum menentukan implementasi, ada beberapa hal penting yang harus dilakukan, yaitu : a. Memilih jenis pengkodean suatu masalah ke Algoritma Genetik. b. Menentukan operator genetik yang digunakan. c. Melakukan seleksi yang diperlukan.
20 Setelah melakukan hal-hal di atas, algoritma genetik dapat diimplementasikan ke dalam program.
2.7.3
Representasi Populasi Awal Menurut Suyanto (2005), ada banyak jenis representasi, beberapa yang sering
digunakan yaitu : a. Representasi biner Ini adalah representasi yang paling sederhana dan paling umum. Pada representasi biner ini, setiap gen hanya bisa bernilai 0 atau 1. Bilangan biner dapat digunakan untuk mempresentasikan “ya” atau “tidak”. Bilangan biner juga dapat digunakan untuk mengkodekan bilangan bulat maupun real. Misalnya, suatu bilangan bulat 12 bisa direpresentasikan ke dalam 5 bit sebagai 01100. Representasi ini banyak digunakan karena mempermudah pemrograman di dalam proses algoritma genetik seperti crossover dan mutasi. Pengkodean Bilangan Floating, prinsip untuk mengubah bilangan bilangan float ke biner adalah dengan mengubah bilangan float tersebut menjadi bilangan interger terlebih dahulu, setelah itu bilangan integer tersebut baru diubah dalam biner. Untuk mengubah bilangan float ke integer adalah dengan mengalikan bilangan tersebut dengan 10m dimana m = jumlah angka di belakang koma dari float yang akan diubah ke biner. Jika ruang solusi dari algoritma genetik adalah antara a ≤ x ≤ b dimana x adalah bilangan float, maka :
2 n −1 < (b − a) * 10 m ≤ 2 n − 1
21 Demikian pula dengan proses sebaliknya untuk mengubah dari bilangan biner ke bentuk bilangan float maka proses pertama kali adalah dengan mendapatkan nilai integer dari bilangan biner tersebut kemudian dihitung nilai floatnya. Rumus yang dapat digunakan untuk mengubah bilangan biner ke float adalah :
x = a + int*
(b − a) 2n − 1
Dimana int adalah nilai int dari bilangan biner yang akan diubah. b. Representasi integer Pada representasi ini, setiap gen bisa bernilai bilangan bulat (integer). Bilangan bulat bisa digunakan untuk merepresentasikan nomor urut, posisi, jenis, atau kuantitas obyek. Dengan representasi ini, ukuran kromosom menjadi lebih sederhana. c. Representasi real Permasalah praktis di dunia nyata mungkin saja membutuhkan tingkat ketelitian sangat tinggi. Jika representasi biner maupun integer tidak bisa mencapai tingkat ketelitian yang diinginkan, maka bisa menggunakan representasi real. d. Representasi permutasi Untuk masalah tertentu, kita mungkin saja tidak bisa menggunakan representasi biner, integer, maupun real. Misalnya dalam mencari solusi “urutan” bukan “nilai”.
22 2.7.4
Operator Genetik dalam Algoritma Genetik Algoritma Genetik memiliki operator-operator genetik yang digunakan dalam
menyelesaikan masalah optimalisasi. Operator-operator tersebut meliputi Seleksi, Rekombinasi (crossover), dan mutasi.
2.7.4.1 Metode-Metode Seleksi Setelah mengetahui jenis representasi yang dibutuhkan maka pembangkitan generasi awal (parent) dapat dilakukan. Langkah pertama yang dilakukan dalam seleksi ini adalah pencarian nilai fitness. Masing-masing individu dalam suatu wadah seleksi akan menerima probabilitas reproduksi yang tergantung pada nilai objektif dirinya sendiri terhadap nilai objektif dari semua individu dalam wadah seleksi tersebut. Metode-metode seleksi yang bisa digunakan untuk memilih individu atau kromosom sebagai orang tua, yaitu : a. Roulette Wheel Selection Dalam metode ini, kromosom-kromosom yang ada dalam populasi ditempatkan ke dalam roda yang disebut “roulette wheel”. Setiap kromosom menempati potongan roda dengan ukuran yang proposional dengan nilai fitness cost yang dimilikinya. Putaran dilakukan sebanyak n kali, dan pada setiap putaran, kromosom yang berada di bawah penanda roda dipilih sebagai parent untuk generasi berikutnya. Metode ini merupakan metode yang digunakan oleh Holland pada Algoritma Genetik yang dikembangkan olehnya. Kelemahan utama metode ini adalah bila terdapat satu kromosom yang memiliki fitness cost yang tinggi sekali, sebagai contoh 90% dari keseluruhan roda, maka kromosom-kromosom lainnya hanya menempati 10% dari
23 keseluruhan roda. Akibatnya, setiap putaran roda kemungkinan besar menghasilkan kromosom yang sama sehingga populasi baru hanya dihuni oleh kromosom yang sama. Kondisi ini disebut sebagai konvergensi dini (“premature convergence”). b. Elitism Menurut Suyanto,2005 metode ini pertama kali diperkenalkan oleh Kenneth De Jong (1975). Dalam metode ini beberapa gen terbaik dari setiap generasi diambil dan disimpan. Tujuan metode ini adalah mencegah hilangnya gen-gen terbaik karena tidak terpilih untuk melakukan crossover atau mutasi. Banyak penelitian yang menemukan bahwa metode ini meningkatkan kinerja Algoritma Genetik secara signifikan. c. Rank Selection Metode ini merupakan alternatif untuk mencegah terjadinya konvergensi dini yang terlalu cepat. Dalam metode ini kromosom-kromosom dalam populasi dirangking berdasarkan fitness cost yang dimiliki. Pemilihan kromosom tidak didasarkan pada nilai fitness cost, namun didasarkan pada nilai rangking yang diberikan. Hal ini bertujuan untuk mengurangi perbedaan nilai yang besar seperti yang dapat terjadi pada metode Roulette Wheel Selection. d. Tournament Selection Dalam metode ini 2 buah kromosom dipilih secara acak dari populasi. Sebuah angka r dipilih secara acak dari angka-angka di antara 0 dan 1. Sebuah parameter k ditentukan (misalnya k = 0,75). Jika r < k, maka kromosom dengan fitness cost yang lebih baik dipilih, dan jika sebaliknya, kromosom dengan fitness
24 cost yang lebih rendah yang dipilih. Kedua kromosom tersebut kemudian dikembalikan ke populasi dan dapat dipilih lagi. e. Steady-State Selection Dalam metode ini hanya sebagian kecil kromosom dari populasi yang diganti dalam setiap generasi. Biasanya kromosom-kromosom yang memiliki fitness cost rendah diganti dengan kromosom-kromosom baru hasil crossover dan mutasi dari kromosom-kromosom dengan fitness cost yang tinggi. Metode ini sering digunakan dalam rule-based system dimana proses pembelajaran memiliki peran penting dan semua anggota populasi secara bersama-sama (tidak secara individual) memecahkan masalah yang ada.
2.7.4.2 Rekombinasi (crossover) Rekombinasi (crossover) adalah operator dari algoritma genetik yang melibatkan dua induk untuk membentuk kromosom baru. Pindah silang menghasilkan titik baru dalam ruang pencarian yang siap untuk diuji. Operasi ini tidak selalu dilakukan pada semua individu yang ada. Individu dipilih secara acak untuk dilakukan crossing dengan Pc antara 0,6 s/d 0,95. Jika crossover tidak dilakukan, maka nilai dari induk akan diturunkan kepada keturunan. Prinsip dari crossover ini adalah melakukan operasi (pertukaran, aritmatika) pada gen-gen yang bersesuaian dari dua induk untuk menghasilkan individu baru. Proses crossover dilakukan pada setiap individu dengan probabilitas crossover yang ditentukan.
25 Operator crossover ini bergantung pada representasi kromosom yang dilakukan. Cara melakukan crossover dapat dibagi berdasarkan jumlah posisi yang dipilih, yaitu single-point crossover atau two-point crossover. a. Single-point crossover Crossover satu titik dan banyak titik biasanya digunakan untuk representasi kromosom dalam biner. Pada crossover satu titik, posisi crossover k (k = 1,2,...,N-1) dengan N = panjang kromosom diseleksi secara random. Variabel-variabel ditukar antar kromosom pada titik tersebut untuk menghasilkan anak.
Gambar 2.2 Ilutrasi Crossover Satu Titik Pada P = 0.70, posisi acak yang dipilih jatuh pada bit ke-4, sehingga kromosom terbagi menjadi dua, yaitu bit 1-3 dan 4-7. Bit 4-7 dari kedua kromosom tersebut ditukar sehingga menghasilkan 2 kromosom baru.
26 Pada P = 0.95, tidak ada pertukaran karena ditentukan probabilitas Crossover yang ditentukan yaitu 0.9. Pada P = 0.35, posisi acak yang dipilih jatuh pada bit ke-2, sehingga bit 2-7 dari kedua kromosom ditukar dan menghasilkan 2 kromosom baru. Begitu juga pada P = 0.65 dimana posisi acak yang dipilih jatuh pada bit ke-5, sehingga bit 5-7 dari kedua kromosom tersebut ditukar dan menghasilkan 2 kromosom baru. b. Two-point crossover Pada crossover dua titik pada prinsipnya sama dengan single-point crossover. Bedanya, pada two-point crossover, dua buah posisi yang dipilih secara acak, sehingga membagi kromosom menjadi 3 bagian. Tujuan dari twopoint crossover adalah untuk menukar bagian yang berada di antara dua posisi acak tersebut (bagian tengah kromosom).
Gambar 2.3 Ilustrasi Crossover dua titik
27 Pada P = 0.70, posisi acak yang dipilih jatuh pada bit ke-4 dan ke-6, sehingga bagian yang berada pada dua posisi bit tersebut ditukar, yaitu bit ke-4 sampai bit ke-6 dan terbentuklah 2 kromosom baru. Pada P = 0.95, tidak terjadi crossover karena probabilitas Crossover yang ditentukan yaitu 0.9. Pada P = 0.35, posisi acak yang dipilih jatuh pada bit ke-2 dan ke-5. Bagian yang berada pada bit ke-2 dan ke-5 pun ditukar dan menghasilkan 2 kromosom baru. Pada P = 0.65, posisi acak yang dipilih jatuh pada bit ke-4 dan ke-5. Oleh karena itu, bit ke-4 dan ke-5 pada 2 buah kromosom tersebut ditukar dan menghasilkan 2 kromosom baru.
c. Crossover banyak titik Pada crossover banyak titik, m posisi penyilangan Ki (k=1,2,...,N-1, i=1,2,...,m) dengan N = panjang kromosom diseleksi secara random dan tidak boleh ada posisi yang sama, serta diurutkan naik. Variabel-variabel ditukar antar kromosom pada titik tersebut untuk menghasilkan kromosom baru.
Gambar 2.4 Ilustrasi Crossover banyak titik Pada gambar tersebut, posisi acak yang dipilih yaitu bit ke-2, ke-4, dan ke-6. Oleh karena itu, bit yang berada pada posisi ke-2 sampai ke-4 kedua
28 kromosom ditukar. Begitu juga dengan bit ke-6 sampai ke-7 ditukar sehingga menghasilkan 2 kromosom baru. Crossover pada banyak titik dilakukan untuk mendapatkan kromosom anak yang mewarisi sifat kedua parent-nya.
Secara umum, proses crossover dapat digambarkan dengan diagram alir sebagai berikut :
Gambar 2.5 Diagram Alir Proses Crossover Pada diagram di atas, proses dimulai dengan pengambilan 2 induk yang dicari nilai probabilitas nya secara acak antara 0 sampai 1. Apabila probabilitas yang ada lebih kecil dari probabilitas crossover yang ditentukan, maka proses crossover akan dijalankan. Sebaliknya, apabila tidak memenuhi kriteria yang ada, maka proses crossover tidak dijalankan.
29 2.7.4.3 Mutasi Mutasi yaitu penambahan, pengurangan, atau perubahan sebagian kromosom yang diharapkan akan memberikan nilai fitness yang lebih baik. Mutasi dilakukan dengan cara memilih satu atau beberapa posisi gen dalam kromosom dan kemudian mengganti nilainya. Peluang mutasi (pm) didefinisikan sebagai persentasi dari jumlah total gen pada populasi yang mengalami mutasi. Peluang mutasi mengendalikan banyaknya gen baru yang akan dimunculkan untuk dievaluasi. Jika peluang mutasi terlalu kecil, banyak gen yang mungkin berguna tidak pernah dievaluasi. Tetapi bila peluang mutasi ini terlalu besar, maka akan terlalu banyak gangguan acak, sehingga anak akan kehilangan kemiripan dari induknya, dan juga algoritma kehilangan kemampuan untuk belajar dari histori pencarian. Kromosom hasil mutasi harus diperiksa, apakah masih berada pada domain solusi, dan bila perlu bisa dilakukan perbaikan. Proses mutasi dapat dilihat dari diagram alir berikut ini :
Gambar 2.6 Diagram Alir Proses Mutasi
30 2.7.5 Cara Kerja Algoritma Genetik Dalam menentukan lokasi penempatan suatu fasilitas baru di antara fasilitasfasilitas yang sudah ada, harus diperhatikan total biaya yang akan dikeluarkan sehingga bisa minimum. Untuk meminimumkan total biaya digunakan rumus : n
C = ∑ Wi ( X i − X ) 2 + (Yi − Y ) 2 i =1
dimana, C = total biaya
Wi = bobot fasilitas lama ke - i X i = absis koordinat fasilitas lama ke - i
X = absis koordinat fasilitas baru Yi = ordinat koordinat fasilitas lama ke – i
Y = ordinat koordinat fasilitas baru
31 Contoh kasus : Apabila diketahui 11 lokasi tempat sampah yang sudah ada seperti pada tabel :
Representasi kromosom dilakukan dengan representasi biner, dengan dua variabel absis (X) dan ordinat (Y). Range untuk X adalah absis terkecil sampai absis terbesar dari koordinat lokasi fasilitas yang sudah ada yaitu [10 39]. Range untuk Y adalah ordinat terkecil sampai ordinat terbesar dari koordinat lokasi fasilitas yang sudah ada yaitu [3 38]. Untuk panjang kromosom L dapat dirumuskan sebagai berikut :
Li =
[ log[(b − a )10 2
n
]]
+1
Dimana selang yang diinginkan untuk variabel x adalah [a b], dan n adalah nilai presisi yang diinginkan. Sementara untuk nilai x dapat dirumuskan sebagai berikut :
[
(
)]
x = a + (b − a ) / 2 L − 1 * v Karena ada 2 variabel yaitu x dan y, maka 1 kromosom terdiri atas 2 gen. Gen1 mewakili variable x dan Gen2 mewakili variabel y. Dalam kasus ini presisi yang
32 diinginkan adalah 2 angka desimal, maka panjang kromosom untuk Gen1 dan Gen2 adalah : Panjang Kromosom1 ( L1 ) =
[ log[(39 − 10)10
Panjang Kromosom2 (L 2 ) =
[ log[(38 − 3)10
2
2
2
2
]]
+ 1 = 12
]]
+ 1 = 12
Sehingga panjang kromosom (L) = 12 + 12 = 24. Untuk penentuan parameter yaitu ukuran populasi (popsize), peluang crossover (Pc), dan peluang mutasi (Pm). Nilai ini juga ditentukan berdasarkan permasalahan yang akan dipecahkan. Dalam hal ini, ada beberapa rekomendasi yang dapat digunakan, antara lain : a. Untuk permasalahan yang memiliki kawasan cukup besar, De Jong merekomendasikan untuk nilai parameter kontrol : (popsize : pc : pm) = (50 : 0.6 : 0.001) b. Bila rata-rata fitness setiap generasi digunakan sebagai indikator, makan Grefenstete merekomendasikan : (popsize : pc : pm) = (30 : 0.95 : 0.01) c. Bila fitness dari individu terbaik dipantau pada setiap generasi, maka usulannya adalah : (popsize : pc : pm) = (80 : 0.45 : 0.01)
2.8
Model Rekayasa Piranti Lunak Model rekayasa piranti lunak yang dipakai penulis adalah sekuensial linear.
Model ini biasanya disebut juga model “air terjun” (waterfall). Model ini merupakan pendekatan kepada perkembangan perangkat lunak yang sistematik dan sekuensial yang
33 mulai pada tingkat dan kemajuan sistem pada seluruh analisis, desain, kode, pengujian, dan pemeliharaan. Penjelasan tahapan dalam Waterfall Model adalah sebagai berikut : a. Analisis Kebutuhan Proses pengumpulan kebutuhan diintensifkan dan difokuskan, khususnya pada perangkat lunak. Tujuan dari tahap ini adalah untuk mengetahui kebutuhan piranti lunak, sumber informasi piranti lunak, fungsi-fungsi yang dibutuhkan, kemampuan piranti lunak dan antar muka piranti lunak tersebut. b. Perancangan Proses perancangan merupakan representasi kebutuhan ke bentuk perangkat lunak yang dapat dinilai kualitasnya sebelum dilakukan pengkodean. Tahap ini meliputi perancangan struktur data, perancangan arsitektur piranti lunak, perancangan rincian prosedur dan perancangan user interface. c. Pengkodean Tahapan ini mengkodekan hasil perancangan ke bahasa pemrograman. d. Implementasi dan Pengujian Setelah program selesai dikode, program akan diujicobakan dan juga dilakukan pengujian. Pengujian dilakukan secara menyeluruh hingga semua perintah dan fungsi telah diuji sampai output yang dihasilkan oleh program sesuai dengan yang diharapkan. e. Pemeliharaan Pemeliharaan perangkat lunak dilakukan karena sering terjadinya perubahan dan peningkatan fungsi piranti lunak. Hal ini sesuai permintaan pemakai, maka piranti lunak yang telah selesai dibuat perlu dipelihara agar dapat
34 mengantisipasi permintaan pemakai terhadap fungsi-fungsi baru. Bila terjadi perubahan berarti membalikkan tahapan ke tahapan yang lebih awal.
Gambar 2.7 Waterfall Model
2.9
Eight Golden Rules Untuk merancang sistem interaksi manusia dan komputer yang baik, harus
memperhatikan delapan aturan emas dalam perancangan antarmuka meliputi : a. Konsisten dalam merancang tampilan (Strive for consitency) b. Memungkinkan pengguna menggunakan shortcuts secara berkala (Enable
frequent user to use shortcuts) c. Memberikan umpan balik yang informatif (Offer informative feed back) d. Merancang dialog untuk menghasilkan keadaan akhir (Design dialogs to yield
closure) e. Memberikan penanganan kesalahan (Offer simple error handling) f. Mengijinkan pembalikkan aksi dengan mudah (Permit easy reversal of actions) g. Mendukung pengguna menguasai sistem (Support internal locus of control) h. Mengurangi beban jangka pendek pada pengguna (Reduce short-term memory
load)
