1. Jelaskan konsep dasar dari algoritma genetik!
Konsep dasar algoritma genetika sebenarnya dirancang untuk menyimulasikan proses-proses dalam sistem alam yang diperlukan untuk evolusi, khususnya teori evolusi alam yang dicetuskan oleh Charles Darwin, yaitu survival of the fittest. Menurut teori ini, di alam terjadi persaingan antara individu-individu untuk memperebutkan sumber daya alam yang langka sehingga makhluk yang kuat mendominasi makhluk yang lebih lemah.
Algoritmagenetik adalah teknik pencarian heuristik yang didasarkan pada gagasan evolusi seleksi alam dan genetik. Algoritma ini memanfaatkan proses seleksi alamiah yang dikenal dengan proses evolusi. Dalam proses evolusi, individu secara terus-menerus mengalami perubahan gen untuk menyesuaikan dengan lingkungan hidupnya. “Hanya individu-individu yang kuat yang mampu bertahan.
2. Permasalahan-permasalahan apa saja yang membutuhkan algoritma genetika?
a. Ruang pencarian sangat besar, kompleks, atau kurang difahami
b. Tidak ada pengetahuan yang memadai untuk menyederhanakan ruang pencarian yang sangat besar menjadi ruang pencarian yang lebih sempit.
c. Tidak ada anilisis matematis yang bisa menangani ketika metode konvensional gagal menyelesaikan masalah yang dihadapi.
d. Solusiyang dihasilkan tidak harus optimal, asal sudah memenihu kriteria sudah bisa diterima.
e. Mempunyai kemungkinan solusi yang jumlahnya tak hingga.
f. Membutuhkan solusi “real-time” yaitu yang bisa didapatkan dengan cepat sehingga dapat diimplementasikan untuk permasalahan yang mempunyai perubahan yang cepat.
3. Jelaskan aplikasi dari algoritma genetika!
Algoritma genetika telah digunakan utk memecahkan masalah dan pemodelan di bidang teknik, bisnis dan hiburan, termasuk:
a. Optimasi: algoritma genetika byk digunakan dlm berbagai tugas optimasi, termasuk optimasi numerik, dan masalah-masalah optimasi kombinatorial seperti Traveling Salesman Problem (TSP), desain sirkuit, Job Shop Scheduling dan optimasi video & kualitas suara.
b. Pemrograman Otomatis: algoritma genetika telah digunakan utk berevolusi thd program komputer utk melakukan tugas-tugas yg spesifik dan merancang struktur komputasi lain, misalnya selular automata dan sorting networking.
c. Machine Learning: algoritma genetika byk digunakan utk aplikasi mesin-learning, termasuk klasifikasi dan prediksi struktur protein. Algoritma genetika juga telah digunakan utk merancang jst dan utk mengendalikan robot.
d. Model ekonomi : algoritma genetika telah digunakan utk memodelkan proses inovasi, pengembangan strategi penawaran dan munculnya pasar ekonomi.
e. Model Sistem Imunisasi: algoritma genetika telah digunakan utk memodelkan berbagai aspek sistem kekebalan tubuh alami, termasuk mutasi somatik selama masa hidup individu dan menemukan keluarga dengan gen ganda selama evolusi.
f. Model ekologi:algoritma genetika telah digunakan utk memodelkan fenomena ekologi seperti host-parasite co-evolution, simbiosis dan arus sumber daya dlm ekologi.
g. Ieraksi antara evolusi dan pembelajaran : algoritma genetika telah digunakan utk mempelajari bagaimana individu belajar dan memengaruhi proses evolusi suatu spesies satu sama lain.
4. Jelaskan pengertian dari gen, allele, kromosom, individu, dan populasi!
a. Gen (genotype) adalah variabel dasar yg membentuk suatu kromosom. Dalam algoritma genetika, gen ini bs bernilai biner, float,integer maupun karakter.
b. Allele adalah nilai dari suatu gen, bisa berupa biner,float,integer maupun karakter.
c. Kromosom adalah gabungan dari gen-gen yg membentuk arti tertentu. Ada beberapa macam bentuk kromosom, yaitu :
- Kromosom biner adalah kromosom yang disusun dari gen-gen yang bernilai biner. Kromosom ini mempunyai tingkat ketelitian yang diharapkan. Kromosom ini bagus bila digunakan untuk permasalahan yang parameter dan range nilainya tertentu.
- Kromosom float adalah kromosom yang disusun dari gen-gen yang bernilai pecahan, termasuk gen yaang bernilai bulat. Kromosom ini mirip model yg jumlah parameternya banyak. Tingkat keberhasilan dari kromosom ini rendah dalam kecepatan (jumlah kecepatan)
- Kromosom string yaitu kromosom yang disusun dari gen-gen yang bernilai string
- Kromosom kombinatorial yaitu kromosom yang disusun dari gen-gen yang dinilai berdasarkan urutannya.
5. Jelaskan siklus dari algoritma genetik.!
David Goldberg adalah orang yang pertama kali memperkenalkan siklus algoritma genetik sebagai berikut.
Siklus dimulai dari membuat populasi awal secara acak, kemudian setiap individu dihitung nilai fitnessnya. Proses berikutnya adalah menyeleksi individu terbaik, kemudian dilakukan cross-over dan dilanjutkan oleh proses mutasi sehingga terbentuk populasi baru. Selanjutnya populasi baru ini mengalami siklus yang sama dengan populasi sebelumnya. Proses ini berlangsung terus hingga generasi ke-n.
Siklus ini kemudian diperbaiki oleh Zbigniew Michalewicz dengan menambahkan satu proses elitisme dan membalik proses reproduksi dahulu, kemudian proses seleksi seperti berikut.
6. Jelaskan komponen-komponen utama dari algoritma genetika!
Untuk mengimplementasikan algoritma genetika, ada 8 komponen utama yang harus dilakukan:
1. Teknik encoding/decoding gen dari individu.
2. Membangkitkan populasi awal secara random dengan terlebih dahulu menentukan jumlah individu dalam populasi tersebut.
3. Nilai fitness (nilai dari fungsi tujuan)
4. Elitisme (prosedur untuk mengcopy individu yang mempunyai nilai fitness tertinggi sebanyak 1 (bila jumlah individu dalam populasi ganjil) atau 2 ( bila jumlah individu dalam populasi adalah genap)
5. Seleksi
6. Cross-over (pindah silang)
Operasi pindah silang antar kromosom yang dilakukan untuk membentuk individu baru yang lebih baik.
7. Mutasi (untuk melakukan modifikasi satu atau lebih nilai gen dalam kromosom yang sama.
8.Penggantian populasi (agar semua individu awal dari satu generasi diganti oleh temporer individu hasil proses pindah silang dan mutasi)
7. Diketahui fungsi f(x1,x2,x3) = 2x12 + 3x22-4x3 . Nilai x dibatasi pada [-4 4]
a. Buatlah populasi awal secara acak, yang terdiri dari 6 individu yang dikodekan secara biner!
b. Bila diinginkan mencari nilai maksimal fungsi f(x1,x2,x3) tentukan individu yang mempunyai nilai terbaik.
c. Bila proses etilisme dijalankan, tentukan individu yang harus disimpan dalam variabel temporer.
d. Tentukan nilai LFR dari masing-masing individu!
e. Gunakan metode seleksi roulettte-wheel untuk proses crossover satu titik potong dan simpanlah individu-individu baru hasil crossover ke dalam variabel temporer, jika diketahui probabilitas crossover prob=0,9!
f. Lakukan proses mutasi untuk mendapatkan populasi yang baru, jika nilai probabilitas mutasi p=1/5
g. Tentukan susunan individu pada populasi yang baru!
8. Sama dengan soal nomor 7, hanya saja sekarang individu dikodekan dengan kode diskrit desimal.!
0 komentar: