Algoritma Genetika

Algoritma genetika adalah sebuah algoritma yang terinspirasi dari teori evolusi mahluk hidup, dimana individu dalam populasi berubah untuk beradaptasi(evolusi) dari generasi ke generasi dan hanya indivitu terbaik yang dapat bertahan. Individu baru pada generasi selanjutnya merpuakan persilangan dari gen orangtuanya dan mempunyai kemunginan untuk bermutasi.

Pada pengaplikasinnya individu yang dimaksud adalah sebuah solusi untuk masalah pada dunia nyata yang akan dipecahkan oleh algoritma genetika. Populasi yang berisikan sekumpulan individu akan menghasilkan individu baru yaitu solusi lainnya yang merupakan rekombinasi dari dua buah individu. Individu tersebut memiliki kemungkinan untuk bermutasi.

 

Individu

Agar sebuah masalah dapat dipecahkan oleh algoritma genetika, maka diperlukan adanya representasi dari masalah yang akan dicari solusinya. Algoritma genetika merepresentasikan solusi sebagai sebuah individu, sama dengan di alam individu menyimpan karakteristik dirinya dalam kromosom DNA.Kromosom ini dapat di sandikan dalam integer, real, biner dan kombinasi.

Fungsi fitness

Untuk mendapatkan solusi maka diperlukan Individu yang terbaik. Untuk mengukur baik tidaknya suatu individu diperlukan adanya fungsi fitness. Fungsi fitness merupakan sebuah fungsi untuk mengukur kecocokan suatu solusi dari sebuah masalah yaitu sebuah individu. Fungsi ini disesuaikan dengan masalah yang ingin diselesaikan.

Rekombinasi

Sebuah individu baru merupakan hasil dari rekombinasi kedua orangtuanya. Gen-gen dari kedua orang tua akan saling bertukar dan menghasilkan kromosom baru yang menentukan karakeristik dari kromosom anak. Cara rekombinasi disesuaikan dengan pengkodean kromosom.

Mutasi

Mutasi merupakan perubahan acak yang terjadi pada satu atau lebih gen.Pada algoritma genetika mutasi juga melakukan hal yang sama terhadap gen, yaitu mengubah secara acak gen yang ada pada kromosom namun dengan algoritma tertentu sesuai dengan pengkodean kromosom.

Seleksi Individu

Setelah pengukuran kecocokan setiap individu dilakukan, maka selanjutnya dilakukan seleksi dan menjadi orangtua untuk individu baru di generasi selanjutnya. Seleksi individu dilakukan agar individu yang terbaiklah yang bertahan dan individu atau solusi yang buruk dibuang. Pada algoritma genetika terdapat beberapa cara untuk melakukan seleksi.

Seleksi Orangtua

Untuk menciptakan individu baru diperlukan sepasang orangtua. Pemilihan orangtua pada algoritma genetika biasanya proporsional terhadap niai kecocokan(fitness) dari populasi yang ada. Sama dengan seleksi individu, terdapat beberapa cara untuk memilih orangtua.

Perbandingan dengan Algoritma Penjadwalan Sebelumnya

Penjelasan tentang apa dan langkah-langkah algorima penjadwalan :

First Come First Served (FCFS)

• algoritma ini mengutamakan proses yang lebih dulu datang
• salah satu kelemahannya adalah memiliki waiting time yang cukup lama
• algoritma ini merupakan algoritma nonpreemptive

Shortest Job First

• Proses disesuaikan dengan panjang CPU burst berikutnya
• waiting timenya kecil sehingga penggunannya cukup optimal
• kelemahan dari algoritma ini adalah tidak mengetahui panjang dari CPU burst selanjutnya
• Algoritma ini bisa merupakan preemptive atau nonpreemptive. Jika preemptive, proses   datang dengan sisa CPU burst yang kecil daripada yang sedang dieksekusi, maka proses tersebut akan menggantikan proses yang sedang dieksekusi

Round Robin

• Algoritma ini mengatur  proses yang terdapat pada antrian. Proses akan mendapat jatah sebesar time quantum.
• CPU akan dialokasikan ke proses selanjutnya bila time quantum-nya habis atau proses sudah selesai
• Tidak ada prioritas dalam proses

Penjadwalan dengan prioritas

• Algoritma ini memberikan prioritas kepada proses yang memiliki prioritas lebih
• Proses yang didahulukan adalah proses yang memiliki skala prioritas terbesar
• Algoritma ini merupakan preemptive dan nonpreemptive
• Kelemahan  algoritma prioritas adalah proses dengan prioritas kecil tidak mendapat space CPU. Hal ini dapat diatasi dengan aging, prioritas akan dapat semakin meninggi apabila semakin lama waktu menunggu proses dijalankan

Algoritma Penjadwalan Dengan Algoritma Genetika

Algoritma genetika untuk penjadwalan proses digunakan untuk menemukan rangkaian dari urutan proses optimal yang akan di jalankan oleh prosesor.[3]Sebuah algoritma penjadwalan dikatakan optimal apabila algoritma tersebut mengoptimasi hal-hal berikut:

• Memaksimalkan kerja CPU
  waktu yang ada harus sebanyak mungkin digunakan untuk bekerja
• Memaksimalkan jumlah proses yang selesai per satuan waktu (troughput)
  Troughput dapat dijadikan ukuran untuk menilai suatu algoritma penjadwalan
• Meminimalkan turnaround time
  Waktu datangnya proses ke antrian sampai proses tersebut selesai dinamakan turnaround time.
• Meminimalkan waktu tunggu
  Waktu tunggu adalah waktu sebuah proses menunggu di antrian ready
• Memaksimalkan waktu respon
  Waktu respon adalah waktu yang diperlukan sebuah proses untuk merespon.

Pengkodean dari gen pada kromosom yang digunakan adalah pengkodean permutasi[1][3] karena masalah yang akan diselesaikan adalah permasalahan kombinatorial. Rekombinasi danmutasi yang digunakan merupakan rekombinasi dan mutasi untuk pengkodean kromosom permutasi.

 

Perbandingan

Dibandingkan dengan algoritma penjadwalan yang umum, algoritma penjadwalan dengan algoritma genetika berbeda dalam hal [1] :

• Algoritma genetika menciptakan beberapa solusi dalam populasi dan memilih yang terbaik dari solusi tersebut, berbeda dengan algoritma lainnya yang hanya memiliki satu solusi.
• Algoritma menyelesaikan masalah dengan parameter yang sudah di kodekan, tidak dengan parameter secara langsung.
• Algoritma genetika menggunakan fungsi fitness untuk mengukur kecocokan suatu solusi, oleh karena itu algoritma genetika dapat digunakan pada berbagai macam masalah optimasi baik diskrit maupun continyu. Dengan syarat pengkodean dan pengdekodean kromosomnya tepat.
• Algoritma genetika bersifat probabilistik dibandingan dengan algorima lain yang bersifat deterministik.

 

 

 

Kesimpulan

Algoritma penjadwalan biasa berbeda dengan algoritma penjadwalan yang berbasis algoritma genetika dalam jumlah solusi yang dihasilkan,  cara menyelesaikan masalah, cara mengukur kecocokan dan sifat dari solusinya.

References

[1] Gupta, M., & Gupta, S. (2013). Optimized Processor Scheduling Algorithms using Genetic Algorithm Approach. International Journal of Advanced Research in Computer and Communication Engineering, 2415-2417.

[2] Kumar, R., Gill, S., & Kaushik, A. (2011). An Impact of cross over operator on the performance of Genetic algorithm under. International Conference on Communication Systems and Network Technologies. doi:10.1109/CSNT.2011.150

[3] Singh, P., Singh, V., & Pandey, A. (2014). Analysis and Comparison of CPU Scheduling Algorithms. International Journal of Emerging Technology and Advanced Engineering, 91-95.

 

Artikel Blog ini disusun oleh Kelompok 13, Kelas IF-36-01,  Mata Kuliah Sistem Operasi Semester Ganjil TA 2014/2015

Anggota kelompok:

• Aditya Arya Mahesa (1103120040)
• Januarta (1103120050)
• Dieka Nugraha Karyana (1103120057)