BAB 2 LANDASAN TEORI

BAB 2 LANDASAN TEORI

Bab ini akan membahas tentang teori dan konsep dasar yang mendukung pembangunan dari system penjadwalan yang dibuat.

2.1 Penjadwalan Pengertian jadwal menurut kamus besar bahasa Indonesia adalah pembagian waktu berdasarkan rencana pengaturan urutan kerja, daftar atau tabel kegiatan atau rencana kegiatan dengan pembagian waktu pelaksanaan yang terperinci, sedangkan pengertian penjadwalan adalah proses, cara, perbuatan menjadwalkan atau memasukkan dalam jadwal (Nadiya, 2015). Penjadwalan pada prinsipnya terjadi baik untuk periode yang panjang (misalnya tahunan) ataupun periode yang lebih pendek (misalnya harian atau periode jam). Penjadwalan yang dimaksudkan di sini adalah penjadwalan jangka pendek karena penjadwalan jangka panjang biasanya dibahas dengan pendekatan lain seperti manajemen projek. Kalau pun penjadwalan jangka panjang tadi bukan bersifat projek, yaitu seperti kegiatan rutin tahunan, maka pendekatan penjadwalan jangka pendek ini pun dapat kita terapkan pada kasus tersebut (Mursyid, 2010).

2.1.1 Tipe-Tipe Penjadwalan Terdapat tiga tipe penjadwalan berada secara bersama-sama pada sistem operasi yang kompleks (Managemen Informatika, 2011) yaitu: 1.

Penjadwal jangka pendek (short-tem scheduller) Penjadwal ini bertugas menjadwalkan alokasi pemroses diantara prosesproses

ready

di

memori

utama.

Sasaran

utama

penjadwal

ini

memaksimalkan kinerja untuk memenuhi satu kumpulan kriteria yang

Universitas Sumatera Utara

diharapakan. Penjadwal ini dijalankan setiap terjadi pengalihan proses untuk memilih proses berikutnya yang harus dijalankan. 2.

Penjadwal jangka menengah (medium-term scheduller) Setelah eksekusi selama suatu waktu, proses mungkin ditunda karena membuat permintaan layanan masukan/keluaran atau memanggil suatu system call. Proses-proses tertunda tidak dapat membuat suatu kemajuan selesai sampai kondisi-kondisi yang menyebabkan tertunda dihilangkan. Agar ruang memori dapat bermanfaat, maka proses dipindah dari memori utama ke memori sekunder agar tersedia ruang untuk prosesproseslain. Kapasitas memori utama terbatas untuk sejumlah proses aktif. Aktivitas pemindahan proses yang tertunda dari memori utama ke memori sekunder disebut swapping. Penjadwal jangka menengah adalah menangani proses-proses swapping. Proses-proses mempunyai kepentingan kecil saat itu sebagai proses yang tertunda. Tetapi, begitu kondisi yang membuatnya terunda hilang dan proses dimasukkan kembali ke memori utama dan ready. Penjadwal jangka menengah mengendalikan transisi dari suspended-ready (dari keadaan suspend ke ready) proses-proses swapping.

3.

Penjadwal jangka panjang (long-term scheduller) Penjadwal jangka panjang bekerja terhadap antrian batch dan memilih batch berikutnya yang harus dieksekusi. Batch biasanya adalah proses-proses dengan penggunaan sumber daya yang intensif (yaitu waktu proses, memori, perangkat I/O), program-program ini berprioritas rendah, digunakan sebagai pengisi (agar pemroses sibuk) selama periode aktivitas job-job interaktif rendah.Sasaran utama penjadwal jangka pangjang adalah memberi keseimbangan job-job campuran.


2.1.2 Teknik-Teknik dalam Melakukan Penjadwalan Ada dua jenis penjadwalan secara umum yaitu (Taufik, 2013): 1.

Penjadwalan Maju (Forward Scheduling) pekerjaan dimulai sedini mungkin sehingga pekerjaaan selesai sebelum batas waktu yang dijanjikan (due date). Konsekuensinya adalah terjadinya akumulasi persediaaan sampai pekerjaan tersebut diperlukan pada pusat kerja berikutnya.

2.

Penjadwalan Mundur (Backward Scheduling) Kegiatan operasi yang terakhir dijadwalkan lebih dulu, yang selanjutnya secara berturut-turut ditentukan jadwal untuk kegiatan sebelumnya satu per satu secara mundur. Konsekuensi dapat meminimalkan persediaaan karena baru selesai pada saat pekerjaan tersebut diperlukan pada stasiun kerja berikutnya. Catatan: harus disertai dengan perencanaan dan estimasi waktu tenggang yang akurat, tidak terjadi break down selama proses maupun perubahan due date yang lebih cepat.

2.1.3 Hal-Hal yang Harus Diperhatikan dalam Melakukan Penjadwalan Ada beberapa hal penting yang sifatnya strategis dapat kita raih jika melakukan penjadwalan dengan baik (Mursyid, 2010): 1.

Penjadwalan yang baik membuat organisasi dapat menggunakan aset atau sumber dayanya dengan lebih efisien dan berefek positif juga pada pencapaian tujuannya.

2.

Kapasitas yang fleksibel dalam memenuhi kebutuhan pelanggan.

3.

Kepastian dalam melaksanakan penjadawalan yang akan dibuat.

2.1.4 Implikasi Strategi Penjadwalan Ada 4 macam implikasi dalam strategi penjadwalan (Taufik, 2013), yaitu: 1. Dengan penjadwalan yang baik, penggunaan aset perusahaan menjadi lebih efektif sehingga biaya menjadi rendah.


2. Penggunaan kapasitas menjadi bertambah karena perputaran aktivas menjadi lebih besar. 3. Pelayanan pelanggan (customer service) menjadi lebih baik. 4. Mendapatkan keunggulan kompetitif.

2.1.5 Keputusan-Keputusan dalam Penjadwalan Setiap organisasi yang menjadi objek penelitian selalu memiliki keputusan dalam penjadwalan. Ini berfungsi sebagai objek kajian dalam sistem pendukung keputusan nantinya menentukan rancangan penelitian. Perhatikan tabel dibawah ini, contoh-contoh organisasi beserta keputusannya. Tabel 2.1.Keputusan dalam Penjadwalan Organisasi

Keputusan Dalam Penjadwalan

Rumah Sakit

Ruang operasi, Perawat, Security, Pasien Rawat Jalan

Universitas

Ruang kelas, Alat Audiovisual, Penjadwalan Dosen dan Mahasiswa, Jadwal Kursus

Pabrik

Produksi, Pembelian Bahan, Gaji

Café

Cheef, Bartender, Pelayan, Entertainer

Bandara Udara

Jadwal Penerbangan

2.1.6 Strategi Penjadwalan Terdapat dua strategi penjadwalan, yaitu: 1.

Penjadwalan nonpreemptive (run – to – completion) Begitu proses diberi jatah waktu pemroses maka pemroses tidak dapat diambil alih oleh proses lain sampai proses itu selesai.

2.

Penjadwalan preemptive Saat proses diberi jatah waktu pemroses maka pemroses dapat diambil alih proses lain sehingga proses disela sebelum selesai dan harus dilanjutkan menunggu jatah waktu pemroses tiba kembali pada proses itu.


Penjadwalan preemptive berguna pada sistem dimana proses-proses yang mendapat perhatian tanggapan pemroses secara cepat. Misalnya: a.

Pada sistem waktu nyata, kehilangan interupsi (yaitu interupsi tidak segera dilayani) dapat berakibat fatal.

b.

Pada sistem interaktif/time-sharing, penjadwalan preemptive penting agar dapat menjamin waktu tanggap yang memadai. Penjadwalan preemptive bagus, tapi tidak tanpa ongkos. Peralihan

proses (yaitu proses beralih ke proses lain) memerlukan overhead (karena banyak tabel yang dikelola). Agar preemptive efektif, banyak proses harus berada di memori utama sehingga proses-proses tersebut dapat segera running begitu diperlukan. Menyimpan banyak proses tak running benarbenar di memori merupakan suatu overhead tersendiri.

2.1.7 Penjadwalan Berprioritas (Managemen Informatika, 2011) Ide penjadwalan adalah tiap proses diberikan prioritas dan proses berprioritas tinggi running (mendapat jatah waktu proses). Prioritas dapat diberikan secara: 1. Prioritas Statis Prioritas statis berarti prioritas tak berubah Keunggulan:a. Mudah diimplementasikan b. Mempunyai overhead relatif kecil Kelemahan: Penjadwalan tak tanggap perubahan lingkungan yang mungkin menghendaki penyesuaian prioritas. 2. Prioritas Dinamis Prioritas dinamis merupakan mekanisme menanggapi perubahan lingkungan system beroperasi. Prioritas awal diberikan ke proses mungkin hanya berumur pendek setelah disesuaikan ke nilai yanglebih tepat sesuai lingkungan. Keunggulan: waktu tanggap sistem yang baik.


Kelemahan:

Implementasi mekanisme prioritas dinamis lebih kompeks dan mempunyai overhead lebih besar. Overhead ini diimbangi dengan peningkatan daya tanggap sistem.

Contoh Penjadwalan Berprioritas Proses-proses yang sangat banyak operasi I/O menghabiskan kebanyakan waktu menunggu selesainya operasi I/O. Proses-proses ini diberi prioritas sangat tinggi sehingga begitu proses memerlukan pemroses segera diberikan, proses akan segera memulai permintaan I/O berikutnya hingga mengakibatkan proses blocked menunggu selesainya operasi I/O. Dengan demikian pemroses dapat dipergunakan proses-proses lain. Proses-proses I/O bound berjalan paralel bersama prosesproses lain yang benar-benar memerlukan pemroses, sementara proses-proses I/O bound itu menunggu selesainya operasi DMA. Proses-proses yang sangat banyak operasi I/O kalau harus menuggu lama untuk memakai pemroses (karena prioritas rendah) hanya akan membebani meori karena harus disimpan tanpa perlu prosesproses itu dimemori karena tidak selesaiselesai menunggu operasi I/O dan menunggu jatah pemroses.

2.1.8 Sasaran Utama Penjadwalan Proses Kriteria untuk mengukur dan optimasi kinerja penjadwalan (Managemen Informatika, 2011): 1. Adil (Fairness) Adil adalah proses-proses diperlukan sama yaitu mendapatkan jatah waktu pemroses yang sama dan tak ada proses yang tidak kebagian layanan pemroses sehingga mengalami startvision. Sasaran pendjadwalan seharusnya menjamin tiap proses mendapat pelayanan dari pemroses yang adil.


2. Efesiensi Efesiensi atau utilisasi pemroses dihitung dengan perbandingan (rasio) waktu sibuk pemroses. Sasaran penjadwalan adalah menjaga agar pemroses tetap dalam keadaan sibuk sehingga efesiensi mencapai maksimum. Sibuk adalah pemroses tidak menganggur, termasuk waktu yang dihabiskan untuk mengeksekusi program pemakai dan sistem operasi. 3. Waktu tanggap (response time) Waktu tanggap berbeda untuk: a. Waktu tanggap pada sistem interaktif (Interaktif) Waktu tanggap dalam sistem interaktif didefinisikan sebagai waktu yang dihabiskan dari saat karakter terakhir dari perintah dimasukkan atau transaksi sampai hasil pertama muncul dilayar (terminal). Waktu tanggap ini disebut terminal response time. b. Waktu tanggap pada sistem waktu nyata (Real Time) Pada sistem waktu nyata, waktu tanggap didefinisikan sebagai waktu dari saat kejadian (internal atau eksernal) sampai instruksi pertama rutin layanan yang dimaksud dieksekusi, disebut event response time. Sasaran pendjadwalan adalah meminimalkan waktu tanggap. 4.

Turn Arround Time

Turn arround time adalah waktu yang dihabiskan dari saat program atau job mulai masuk ke system sampai proses diselesaikan sistem. Waktu yang dimaksud adalah waktu yang dihabiskan dalam sistem, diekspresikan sebagai jumlah waktu eksekusi (waktu pelayanan job) dan waktu menunggu, yaitu; Turn Arround Time = waktu eksekusi + waktu tunggu

(1)

Sasaran penjadwalan adalah meminimalkan turn arround time.


5. Throughtput Throughtput adalah jumlah kerja yang dapat diselesaikan dalam satu unit waktu. Cara untuk mengekspresikan throughput adalah dengan jumlah job pemakai yang dapat dieksekusi dalam satu unit/interval waktu. Sasaran penjadwalan adalah memaksimalkan jumlah job yang diproses per satu interval waktu. Lebih tinggi angka throughput, lebih banyak kerja yang dilakukan sistem. Kriteria-kriteria tersebut saling bergabung dan dapat pula saling bertentangan sehingga tidak dimungkinkan optimasi semua kriteria secara simultan.

2.2 Algoritma Genetika Algoritma ini ditemukan di Universitas Michigan, Amerika Serikat oleh John Holland (1975) melalui sebuah penelitian dan dipopulerkan oleh salah satu muridnya, David Goldberg. Algoritma genetik adalah algoritma yang berusaha menerapkan pemahaman mengenai evolusi alamiah pada tugas-tugas pemecahanmasalah (problem solving). Pendekatan yang diambil oleh algoritma ini adalah dengan menggabungkan secara acak berbagai pilihan solusi terbaik di dalam suatu kumpulan untuk mendapatkan generasi solusi terbaik berikutnya yaitu pada suatu kondisi yang memaksimalkan kecocokannya atau lazim disebut fitness. Generasi ini akan merepresentasikan perbaikanperbaikan pada populasi awalnya. Dengan melakukan proses ini secara berulang, algoritma ini diharapkan dapat mensimulasikan proses evolusioner (Nugraha, 2008). Algoritma genetika merupakan algoritma pencarian yang menerapkan proses seleksi alam dan evolusi yang dikemukakan oleh Charles Darwin. Algoritma genetika pertama kali diperkenalkan oleh John Holland (1975) dari Universitas Michigan. John Holland menyatakan bahwa setiap masalah yang berbentuk adaptasi (alami maupun buatan) dapat diformulasikan kedalam terminologi genetika (Saraswat & Prayanthi, 2012).


Algoritma genetika bukanlah solusi terbaik untuk memecahkan segala masalah. Sebagai contoh, metode tradisional telah diatur untuk untuk mencari penyelesaian dari fungsi analitis convex yang “berperilaku baik” yang variabelnya sedikit. Pada kasus-kasus ini, metode berbasis kalkulus lebih unggul dari algoritma genetik karena metode ini dengan cepat menemukan solusi minimum ketika algoritma genetik masih menganalisa bobot dari populasi awal. Untuk problemproblem ini pengguna harus mengakui fakta dari pengalaman ini dan memakai metode tradisional yang lebih cepat tersebut. Akan tetapi, banyak persoalan realistis yang berada di luar golongan ini. Selain itu, untuk persoalan yang tidak terlalu rumit, banyak cara yang lebih cepat dari algoritma genetik (Nugraha, 2008). Sifat algoritma genetika adalah mencari kemungkinan-kemungkinan dari kandidat solusi untuk mendapatkan yang optimal untuk penyelesaian masalah. Ruang cakupan dari semua solusi yang layak (feasible), yaitu objek-objek diantara solusi yang sesuai, dinamakan ruang pencarian (search space). Tiap titik dalam ruang pencarian mempresentasikan satu solusi yang layak. Tiap solusi yang layak dapat ditandai dengan nilai fitness-nya bagi masalah. Algoritma genetika bekerja dari populasi yang merupakan himpunan solusi yang dihasilkan secara acak. Setiap anggota himpunan yang merepresentasikan satu solusi masalah. Suatu solusi masalah berevolusi dalam iterasi yang dinamakan generasi, tiap solusi masalah dievaluasi berdasarkan fungsi evaluasi (fitness function). Pada algoritma genetika, fitness biasanya dapat berupa fungsi objektif dari masalah yang akan dioptimalisasi (Saraswati& Prayanthi, 2012). Tabel 2.2.Perbandingan Istilah pada Sistem Alamiah dengan Algoritma Genetika Sistem Alamiah Kromosom Gen Allel Locus Genotip Fenotip

Algoritma Genetika String Fitur, Karakter atau Detektor Nilai Fitur Posisi String Struktur Set Parameter, Solusi Alternatif, Struktur yang didecode


Epitasis

Non Linieritas

2.2.1 Beberapa Definisi Penting Dalam Algoritma Genetik a.

Genotype (gen) adalah sebuah nilai yang menyatakan satuan dasar yang membentuk suatu arti tertentu dalam satu kesatuan gen yang dinamakan kromosom. Dalam Algoritma Genetik, gen ini bisa berupa nilai biner, float, integer, maupun karakter.

b.

Allel adalah nilai dari gen.

c.

Kromosom adalah gabungan dari gen-gen yang membentuk nilai tertentu.

d.

Individu menyatakan satu nilai dari keadaan yang menyatakan salah satu siklus proses evolusi.

e.

Populasi merupakan sekumpulan individu yang akan diproses bersama dalam satu siklus proses evolusi.

f.

Generasi menyatakan satuan siklus proses evolusi.

g.

Nilai fitness menyatakan seberapa baik nilai dari suatu individu atau solusi yang didapatkan.

. . .

Populasi


Gambar 2.1 Ilustrasi representasi penyelesaian permasalahan dalam algoritma genetika

Algoritma genetik secara umum dapat diilustrasikan dalam Flowchat yang dapat dilihat padagambar berikut:

Mulai

Mutasi

Populasi Awal

Kreteria Berhenti Terpenuhi?

Crossover

tidak

Seleksi

ya Evaluasi Fitness

Hasil

Selesai

Gambar 2.2 Flowchat Algoritma Genetika

2.2.2 Proses Algoritma Genetika(Novandry Widyastuti, 2008) 1.

Start Generate populasi pertama secara random sebanyak nindividu.

2.

Fitness Evaluasi nilai fitness f(x) dari setiap individu x didalampopulasi.

3.

New Populasi 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 sesuaidengan probabilitas mutasi di setiap gen. d. Accepting Tempatkan keturunan yang baru sebagaipopulasi yang baru. 4.

Replace Gunakan populasi yang baru dibentuk untukmenjalankan algoritma.

5.

Test Jika kondisi akhir dipenuhi maka berhenti dan tampilkansolusi dari populasi.

6.

Loop Kembali ke nomor 2.

2.2.3 Struktur Umum Dari Suatu Algoritma Genetik Dapat Didefinisikan Dengan Langkah-Langkah Sebagai Berikut (Suhartono, 2015) 1.

Membangkitkan populasi awal (generate)


Populasi awal ini dibangkitkan secara random sehingga didapatkan solusi awal.

Populasi

itu

sendiri terdiri dari sejumlah kromosom yang

mempresentasikan solusi yang diinginkan. 2.

Membentuk generasi baru Dalam membentuk generasi baru digunakan tiga operator yaitu operator reproduksi/seleksi, crossover, dan mutasi. Proses ini dilakukan berulangulang sehingga didapatkan jumlah kromosom yang cukup untuk membentuk generasi baru dimana generasi baru ini merupakan representasi dari solusi baru.

3.

Evaluasi solusi Proses ini mengevaluasi setiap populasi dengan menghitung nilai fitness setiap kromosom dan mengevaluasinya sampai terpenuhi kriteria berhenti. Bila kriteria berhenti belum terpenuhi maka dibentuk lagi generasi baru dengan mengulangi langkah 2. Beberapa kriteria berhenti yang sering digunakan antara lain: a. Berhenti pada generasi tertentu. b. Berhenti setelah dalam beberapa generasi berturut-turut didapatkan nilai fitness tertinggi tidak berubah. c. Berhenti bila dalam n generasi berikut tidak didapatkan nilai fitness yang lebih tinggi.

2.2.4 Komponen-Komponen Utama Algoritma Genetika (Suhartono, 2012) 1.

Teknik pengkodean Pengkodean adalah suatu teknik untuk menyatakan populasi awal sebagai calon solusi suatu masalah ke dalam suatu kromosom sebagai suatu kunci pokok

persoalan

ketika

menggunakan

Algoritma

Genetik.

Teknik

pengkodean ini meliputi pengkodean gen dan kromosom. Gen merupakan bagian dari kromosom. Satu gen biasanya akan mewakili satu variable. Gen dapat direpresentasikan dalam bentuk string bit, pohon, array bilangan real,


daftar aturan, elemen permutasi, elemen program, atau representasi lainnya yang dapat diimplementasikan untuk operator genetik. Oleh karena itu, kromosom dapat direpresentasikan sebagai: 1. String bit: 11001, 10111 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. Contoh: 11001011 + 11011111 = 11001111. 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. Contoh: 11001011 + 11011111 = 11011111 2. Array bilangan real: 7.9, 9.7, -70 3. Elemen permutasi: E5, E8, E11 4. Daftar aturan: R1, R2, R3 5. Elemen program: pemrograman genetika 2.

Prosedur inisialisasi Ukuran populasi tergantung pada masalah yang akan dipecahkan dan jenis operator genetik yang akan diimplementasikan. Setelah ukuran populasi ditentukan, kemudian harus dilakukan inisialisasi terhadap kromosom yang terdapat pada populasi tersebut. Inisialisasi kromosom dilakukan secara acak, namun demikian harus tetap memperhatikan domain solusi dan kendala permasalahan yang ada.


3.

Evaluasi fitness Evaluasi fitness merupakan dasar untuk proses seleksi. Langkah-langkahnya yaitu string dikonversi ke parameter fungsi, fungsi objektifnya dievaluasi, kemudian mengubah fungsi objektif tersebut ke dalam fungsi fitness. Dimana untuk maksimalisasi problem, fungsi fitness dipergunakan sebagai dasar untuk menseleksi individu pada generasi berikutnya. Untuk permasalahan minimalisasi, nilai fitness adalah inversi dari nilai minimal yang diharapkan.

Rumus fitness yang digunakan, (Suhartono, 2015) adalah sebagai berikut: 𝐹𝐹𝑖𝑖𝑡𝑡𝑛𝑛𝑒𝑒𝑠𝑠𝑠𝑠= 1 / 1+(𝐹𝐹1𝐵𝐵1+𝐹𝐹2𝐵𝐵2+⋯)

(2)

Keterangan: Bn = Bobot pelanggaran

n = 1, 2 . . . n

Fn = Banyaknya pelanggaran 4.

Seleksi Proses seleksi bertujuan untuk memilih individu-individu yang akan dipilih untuk proses persilangan dan mutasi, sehingga akan diperoleh calon induk yang baik. Induk yang baik akan menghasilkan keturunan yang baik. Langkah pertama dalam seleksi yaitu 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. Nilai fitness inilah yang nantinya akan digunakan pada tahap seleksi berikutnya.

Ada beberapa metode untuk memilih kromosom yang digunakan antara lain:

a. Roulette wheel selection Seleksi ini dilakukan dengan cara menyeleksi parent dengan tujuan untuk mempertahankan nilai fitness-nya agar memiliki kesempatan untuk diseleksi adalah kromoson yang baik. Proses ini diibaratkan seperti permainan roda rolet (roullette wheel), di mana semua kromosom


ditempatkan dalam populasi, setiap tempat besar sesuai dengan fungsi fitness. Kromosom dipilih berdasarkan nilai fitness, semakin besar nilai fitness maka kromosom tersebut mempunyai peluang untuk dipilih beberapa kali. Metode seleksi roda rolet merupakan metode yang paling sederhana, dan sering juga dikenal dengan nama stochastic sampling with replacement.

b. Selekssi good fitness Seleksi ini dilakukan dengan cara setengah dari jumlah populasi yang memiliki nilai fitness yang paling rendah akan dihilangkan, sehingga selalu hanya tersisa sekelompok solusi yang terbaik. Solusi yang tersisa hasil dari seleksi tersebut disebut populasi induk. Karena jumlah populasi harus tetap, maka perlu di-generate solusi baru sebanyak setengah dari jumlah populasi yang ada. Ada 2 cara yang digunakan untuk mengenerate solusi baru, yaitu dengan cara reproduksi kromosom baru dan mutasi dari solusi induk. Tujuan men-generate solusi baru ini adalah untuk menemukan alternatif solusi yang lebih baik dari solusi-solusi yang sudah dihasilkan.

2.2.5 Teknik-Teknik dalam Algortima Genetik Ada 4 teknik yang dapat dilihat dalam Speech Recognition (Nugraha, 2008) yaitu: 1.

Fitness Function Setiap individual dievaluasi dengan fitness function. Sebuah fitness function mengembalikan nilai tertinggi untuk individual yang terbaik. Individu akan diurutkan berdasarkan nilai atau disebut dengan selection.

2.

Crossover Untuk setiap pasang induk, sebuah titik crossover akan dipilih secara random dari posisi dalam string. Pada gambar titik crossover terletak pada indeks ketiga dalam pasangan pertama dan setelah indeks kelima pada pasangan kedua.


3.

Mutasi Pada mutasi, tiap lokasi menjadi sasaran mutasi acak, dengan probabilitas independen yang kecil. Sebuah digit dimutasikan pada anak pertama, ketiga, dan keempat. Algoritma genetika mengkombinasikan suatu kecenderungan menaik dengan pengeksplorasian acak diantara thread pencarian paralel. Keuntungan secara matematis dapat tunjukkan bahwa bila posisi dari kode genetik di permutasikan di awal dengan urutan acak, crossover tidak memberikan keunggulan. Secara intuisi, keuntungannya didapat dari kemampuan crossover untuk menggabungkan blok-blok huruf berukuran besar yang telah berevolusi secara independen untuk melakukan fungsi yang bermanfaat sehingga dapat menaikkan tingkat granularity di mana pencarian dilakukan.

4.

Schema Teori dari algoritma genetik menjelaskan cara kerjanya menggunakan ide dari suatu schema, suatu substring di mana beberapa posisi tidak disebutkan. Dapat ditunjukkan bahwa, bila fitness rata-rata dari schema berada di bawah mean maka jumlah instansiasi dari schema di dalam populasi akan bertambah seiring bertambahnya waktu. Jelas sekali bahwa efek ini tidak akan signifikan bila bit-bit yang bersebelahan sama sekali tidak berhubungan satu sama sekali, karena akan ada beberapa blok kontigu yang memberikan keuntungan yang konsisten. Algoritma genetik paling efektif dipakai bila schema-schema berkorespondensi menjadi komponen berati dari sebuah solusi. Sebagai contoh, bila string adalah representasi dari sebuah antena, maka schema merepresentasikan komponen-komponen dari antena, seperti reflector dan deflector. Sebuah komponen yang baik cenderung akan berkerja baik pada rancangan yang berbeda.

2.2.6 Contoh-contoh Pengaplikasian Algoritma Genetik


Menurut (Suyanto, 2005) algoritma genetika telah banyak diaplikasikan untuk penyelesaian masalah dan pemodelan dalam bidang teknologi, bisnis dan entertainment seperti: a.

Optimasi Algoritma genetika untuk optimasi numerik dan optimasi kombinatorial seperti Traveling Salesman Problem (TSP), perancangan Integrated circuit atau IC, optimasi video dan suara.

b.

Pemrograman Otomatis Algoritma genetika telah digunakan untuk melakukan proses evolusi terhadap program komputer untuk merancang struktur komputasiona, seperti cellular automata dan sorting network.

c.

Machine Learning Algoritma genetika telah berhasil diaplikasikan untuk memprediksi struktur protein, dan berhasil diaplikasikan dalam perancangan neural networks (jaringan syaraf tiruan) untuk melakukan proses evolusi terhadap aturanaturan pada learning classifier system atau symbolic production system, juga digunakan untuk mengontrol robot.

d.

Model Ekonomi Algoritma genetika telah digunakan untuk memodelkan proses-proses inovasi dan pembangunan bidding strategies.

e.

Model Sistem Imunisasi Algoritma genetika telah berhasil digunakan untuk memodelkan berbagai aspek pada sistem imunisasi alamiah, termasuk somatic mutation selama kehidupan individu dan menemukan keluarga dengan gen ganda (multi-gene families) sepanjang waktu evolusi.

f.

Model Ekologis


Algoritma genetika berhasil digunakan untuk memodelkan fenomena ekologis seperti host-parasite co-evolutions, simbiosis, dan aliran sumber daya dalam ekologi. g.

Interaksi antara Evolusi dan Belajar Algoritma genetika telah digunakan untuk mempelajari bagaimana proses belajar suatu individu bisa mempengaruhi proses evolusi suatu species dan sebaliknya.

2.2.7 Masalah-masalah yang Bisa Diselesaikan dengan Algoritma Genetik Algoritma genetika sangat berguna dan efisien untuk masalah-masalah dengan karakteristik sebagai berikut (Suyanto, 2005): a.

Ruang masalah sangat besar, kompleks, dan sulit dipahami.

b.

Kurang atau bahkan tidak ada pengetahuan yang memadai untuk merepresentasikan masalah ke dalam ruang pencarian yang lebih sempit.

c.

Tidak tersedianya analisis matematika yang memadai.

d.

Ketika metode-metode konvensional sudah tidak mampu meyelesaikan masalah yang dihadapi.

e.

Solusi yang diharapkan tidak harus paling optimal, tetapi cukup bagus atau bisa diterima.

f.

Terdapat batasan waktu, misalnya real time system atau sistem waktu nyata.

2.3Implimentasi Perancangan Perangkat Lunak (Software)

2.3.1HTML HTML singkatan dari Hyper Text Markup Language, merupakan bahasa komputer yang ditulis pada suatu halaman file untuk memberitahu browser anda bagaimana sebuah halaman hendak ditampilkan. HTML adalah bahasa yang digunakan untuk memberitahu browser bagaimana untuk menampilkan suatu


halaman sesuai dengan yang kita inginkan, seperti posisi, ukuran, warna dan lainlain. Bahasa tersebut terdiri dari berbagai kode- kode yang masing- masing memiliki fungsi dan tugasnya masing- masing. Ketika anda melihat sebuah halaman di browser komputer anda, yang anda lihat sebenarnya adalah penerjemahan perintah HTML yang dilakukan oleh browser anda dari sebuah halaman.

2.3.2PHP Kepanjangan dari PHP adalah "Hypertext Preprocessor" (ini merupakan singkatan rekursif). Jadi, Apa itu PHP? PHP adalah bahasa scripting web HTML-embedded. Ini berarti kode PHP dapat disisipkan ke dalam HTML halaman Web. Ketika sebuah halaman PHP diakses, kode PHP dibaca atau "diurai" oleh server. Output dari fungsi PHP pada halaman biasanya dikembalikan sebagai kode HTML, yang dapat dibaca oleh browser. Karena kode PHP diubah menjadi HTML sebelum halaman dibuka, pengguna tidak dapat melihat kode PHP pada halaman. Ini membuat halaman PHP cukup aman untuk mengakses database dan informasi aman lainnya.

2.3.3CSS CSS adalah kependekan dari Cascading Style Sheet. CSS merupakan salah satu kode pemrograman yang bertujuan untuk menghias dan mengatur gaya tampilan/layout halaman web supaya lebih elegan dan menarik.CSS adalah sebuah teknologi internet yang direkomendasikan oleh World Wide Web Consortium atau W3C pada tahun 1996. Awalnya, CSS dikembangkan di SGML pada tahun 1970, dan terus dikembangkan hingga saat ini. CSS telah mendukung banyak bahasa markup seperti HTML, XHTML, XML, SVG (Scalable Vector Graphics) dan Mozilla XUL (XML User Interface Language).

2.3.4 Database


Database adalah kumpulan data yang tersusun secara sistematis sehingga akan memudahkan pengguna untuk mengakses dan mengatur sehingga akan menghasilkan sebuah informasi yang efektif dan efisien. Database dapat berdiri-sendiri dan juga dapat digabung menjadi satu kesatuan. Menggabung dua atau lebih jenis database disebut mengkorelasikan. Sistem manajemen database merupakan software yang digunakan untuk mengelola database Sampai pengaturan hak akses.

Basis Data: Himpunan kelompok data (arsip) yang saling berhubungan, yang diorganisasi sedemikian rupa, sehingga kelak dapat dimanfaatkan kembali dengan cepat.

2.3.5 Sublime text Sublime Text itu adalah salah satu text editor yang biasa digunakan oleh para programmer, khususnya Web Developer. Bisa diibaratkan sebagai senjata-nya Web Developer. Setiap web developer wajib untuk menggunakan Sublime Text sebagai ‘senjata harian’-nya.

2.3.6 XAMPP XAMPP adalah perangkat lunak bebas, yang mendukung banyak sistem operasi, merupakan kompilasi dari beberapa program. Fungsinya adalah sebagai server yang berdiri sendiri (localhost), yang terdiri atas program Apache HTTP Server, MySQLdatabase,

dan penerjemah bahasa yang

ditulis

dengan

Bahasa

pemograman PHP dan Perl. Nama XAMPP merupakan singkatan dari X (empat sistem operasi apapun), Apache, MySQL, PHP dan Perl. Program ini tersedia dalam GNU General Public License dan bebas, merupakan web server yang mudah digunakan yang dapat melayani tampilan halaman web yang dinamis.


BAB 2 LANDASAN TEORI

Recommend Documents