TUGAS UTS

download html download

Tugas UTS

1.      1. Jelaskan secara singkat apa yang dimaksud dengan Algoritma Genetika (GA) ?

Algoritma adalah serangkaian langkah-langkah untuk memecahkan masalah. Sebuah algoritma genetika adalah metode pemecahan masalah yang menggunakan genetika sebagai modelnya pemecahan masalah. Ini adalah teknik pencarian untuk solusi dan perkiraan untuk optimasi dan pencari masalah.

2.      2. Jelaskan tentang proses mutasi ?

Proses mutasi dilakukan dengan cara mengganti satu gen yang terpilih secara acak dengan suatu nilai baru yang didapat secara acak. Mutasi diperlukan untuk mengembalikan informasi bit yang hilang akibat pindah silang. Mutasi diterapkan dengan probabilitas yang sangat kecil. Jika mutasi dilakukan terlalu sering, maka akan menghasilkan individu yang lemah karena konfigurasi gen pada individu yang unggul akan dirusak. Berdasarkan bagian yang termutasi, proses mutasi dapat dibedakan atas tiga bagian.

• Mutasi pada tingkat kromosom, semua gen dalam kromosom berubah.

• Mutasi pada tingkat gen, semua bit dalam satu gen akan berubah, contoh gen nomor 2 mengalami mutasi.

• Mutasi pada tingkat hanya satu bit yang berubah.

3.      3. Jelaskan tentang peoses crossover ?

Crossover adalah operator algoritma genetika yang membutuhkan parameter dua kromosom. Dua buah kromosom tersebut disebut kromosom induk. Operator ini akan menghasilkan dua buah kromosom baru. Ada beberapa jenis crossover yang sering digunakan dalam algoritma genetika antara lain:

Ordered Based Crossover

Ordered based Crossover diawali dengan menentukan posisi-posisi gen secara random pada induk pertama misalnya didapatkan posisi 3,4,6 dan 9 pada induk.

P1= ( 1 2 3 4 5 6 7 8 9 )

P1= ( 4 5 2 1 8 7 6 9 3 )

Kemudian Gen-gen pada induk yang berada tepat dibawah posisi-posisi tersebut dicatat yaitu 2,1,7 dan 3 untuk Q1 disalin dari P1 dengan menghilangkan angka-angka 2,1,7 dan3 tersebut sehingga menjadi

Q1= ( x x x 4 5 6 x 8 9 )

Subset 2,1,7, dan 3 ini di masukan dalam Q1 dimulai dari kiri dengan mempertahankan urutan sehingga menjadi:

Q1 = (2 1 7 4 5 6 3 8 9)

Untuk Q2 diperlukan sama hanya perlu meukar induk pertama menjadi induk kedua dan induk kedua menjadi induk pertama yang menjadi:

Q2 = (3 5 2 1 8 7 4 6 9)

One-Point Crossover

Contoh kerja operator ini adalah dengan menentukan crossover point (gen tertentu). Kromosom baru pertama berisi gen pertama sampai gen crossover point dari kromosom induk pertama ditambah dengan gen dari crossover point sampai gen terakhir dari kromosom induk kedua. Kromosom baru kedua berisi gen pertama sampai gen crossover point dari induk kedua ditambahkan dengan gen dari crossover point sampai gen dari kromosom induk pertama.

Two-Point Crossover

Proses Two-Point Crossover hampir sama dengan prosedur One-Point Crossover, kecuali pada Two-Point Crossover harus dipilih dua crossover point dan hanya gen yang ada di antara kedua crossover point itu yang akan ditukarkan.

Metode ini dapat menjadi bagian awal dan akhir dari kromosom dan hanya menukar bagian tengahnya saja.

N-Point Crossover

Prosedur N-Point Crossover hampir sama baik dengan prosedur one-point crossover maupun two-point crossover, hanya saja dalam n-point crossover ini harus dipilih n crossover point dan hanya gen di antara crossover point ganjil dan genap yang dapat ditukarkan sedangkan gen diantara genap dan ganjil operator crossover tidak berubah. Atau dengan kata lain harus dipilih posisi n dan hanya bit antara ganjil dan genap posisi crossover yang akan dihilangkan.

Contoh: P1= 9 7 6 3 2 8

  P2= 2 1 9 7 4 5

Jika didapatkan angka random untuk n=3 dan diacak 1,2 dan 4 sebagai posisi dari gen yang akan di crossover, didapatkan kromosom turunan:

T1= 9 1 6 3 4 5

T2= 2 7 9 7 2 8

4.      4. Jelaskan secara singkat proses aplikasi GA pada kontrol motor ?

    Perbaikan kinerja sistem dilakukan dengan perancangan sistem PID berdasarkan metoda algoritma  genetika. Proses algoritma genetika yang digunakan diperlihatkan oleh Gambar . Populasi awal yang digunakan pada sistem ini adalah 50, nilai populasi ini diambil secara acak . Diagram alir algoritma genetika.

Seleksi individu untuk menghasilkan generasi yang berhasil, memainkan aturan yang terpenting pada sistem algoritma genetik. Pada penelitian ini, tipe seleksi yang digunakan adalah metoda pemeringkatan nilai normalisasi dari distribusi geometri, sesuai dengan (13). Nilai r adalah normalisasi dari distribusi, q adalah probabilias dari terpilihnya populasi terbaik dan n adalah jumlah anggota dalam populasi. Menggunakan nilai fitness dari setiap individu, maka individu yang lebih baik mempunyai peluang terpilih yang lebih tinggi[6].

Persilangan yang digunakan dalam penelitian ini adalah metoda interpolasi dari dua orang tua untuk menghasilkan 2 anak, seperti pada (14) dan (15). Nilai anak pertama dan kedua adalah c1 dan c2. Nilai orang tua pertama dan kedua adalah p1 dan p2, sedangkan a adalah bilangan acak yang bebas dipakai.

Pada tahap mutasi terdapat perubahan parameter yang diambil secara acak dari orang tua menggunakan distribusi probabilitas.

5    5. Jelaskan suatu contoh aplikasi GA berikut penjelasannya (dari jurnal atau TA) ?

ALGORITMA GENETIKA DALAM PEMILIHAN SPESIFIKASI KOMPUTER

Algoritma genetika adalah algoritma yang memanfaatkan proses seleksi alamiah yang dikenal dengan proses evolusi. Dalam proses evolusi, individu secara terus-menerus mengalami perubahan gen untuk menyesuaikan diri dengan lingkungan hidupnya. Proses seleksi alamiah ini melibatkan perubahan gen yang terjadi pada individu melalui proses perkembangbiakan. Konsep dasar dari proses evolusi dapat dianalogikan dengan serangkaian individu di alam yang saling berkompetisi untuk mempertahankan hidupnya, salah satu caranya adalah dengan penyesuian diri dengan lingkungannya. Karakteristik tiap individu dalam mempertahankan hidup dapat ditentukan oleh inti dasar yang disebut sebagai gen. Sedangkan kromosom adalah kumpulan dari gen yang merupakan komponen utama individu dalam berkembang biak. Kromosom dibentuk dari komposisi gen yang berderet teratur didalamnya. Fungsi dari gen dapat dilihat dari posisi gen yang tersimpan dalam tiap segmen  yang khas dari kromosom yang disebut locus. Gen yang terletak pada locus  yang bersesuaian dari kromosom yang mempunyai pekerjaan yang sama disebut alele.  
  Dalam kompetisi mempertahankan hidup akan mendorong adanya dominasi dari individu yang kuat terhadap individu yang lemah. Individu yang kuat akan terus bertahan hidup sedangkan individu yang lemah akan pelan-pelan tersingkir dan kemudian mati. Individu yang hidup akan terus berusaha menyesuaikan diri dengan lingkungannya yang bisa menimbulkan variasi dalam suatu keturunan. Hal ini terjadi karena beberapa sebab antara lain : 
1.      Adanya mutasi gen, yaitu perubahan gen dari individu. 
2.   Adanya rekombinasi (pindah silang) gen dalam suatu keturunan yang menghasilkan variasi-variasi  kromosom baru. 
      Pada algoritma genetika, untuk mencari solusi optimal maka individu akan mengalami evolusi dari generasi ke generasi dengan terjadinya variasi genetika dan seleksi alam. Seleksi alam dianggap sebagai proses optimasi dari individu-individu tersebut. Jadi individu yang unggul, yang mampu beradaptasi dengan lingkungannya adalah individu yang muncul sebagai solusi yang optimal.  
           Algoritma genetika merupakan prosedur iteratif, bekerja dengan suatu set untaian yang disebut populasi sebagai kandidat solusi dengan jumlah yang konstan. Populasi ini kemudian berkembang biak dari generasi ke generasi melalui operator genetik seperti pindah silang dan mutasi. Selama tiap langkah iterasi yang disebut generasi, struktur dalam populasi akan dievaluasi dan selanjutnya akan diseleksi untuk menentukan populasi pada generasi selanjutnya. Tiap kandidat solusi akan mempunyai nilai fitness yang memperlihatkan kelebihan dari suatu solusi dibandingkan solusi yang lainnya. Lebih tinggi nilai fitness suatu individu maka akan lebih besar kemungkinan individu tersebut untuk bertahan hidup dan menghasilkan keturunan. 

PRINSIP KERJA

Prinsip kerja dari suatu algoritma genetika dapat digambarkan sebagai berikut. 

Gambar 1 Langkah-langkah Algoritma Genetika

Dari gambar 1 dapat dijelaskan dalam tiga struktur utama yaitu sebagai berikut : 

1.      Membangkitkan populasi awal, yaitu dengan proses acak sehingga didapatkan solusi awal. 

2.      Membentuk generasi baru dengan menggunakan 3 operator yaitu seleksi, pindah silang, dan mutasi. 

3.      Evaluasi solusi, yaitu dengan menghitung nilai fitness tiap kromosom sampai memenuhi kriteria yang diinginkan.

Komponen-komponen dari algoritma genetika dapat dijelaskan sebagai berikut : 

1.      Populasi, yaitu kumpulan dari beberapa kromosom. Individu bisa dikatakan sama dengan kromosom, yang merupakan sebuah solusi yang dibangkitkan dalam algoritma genetika dan dibentuk dari kumpulan gen. Gen merupakan suatu nilai yang menyatakan satuan dasar yang membentuk suatu arti tertentu. Nilai dari gen ini bisa biner, float, dan kombinatorial. 

2.      Fungsi Fitness, yaitu nilai yang menyatakan baik tidaknya suatu solusi (individu). Semakin besar nilai fitness suatu individu maka semakin baik pula solusinya. Algoritma genetika bertujuan mencari individu dengan nilai fitnessyang paling tinggi.

Setiap alele merepresentasikan masing-masing perangkat komputer dan mempunyai bobot sendiri. Bobot merupakan nilai tingkatan perangkat keras dimana nilainya didapatkan dari distributor komputer. Bobot_max merupakan nilai bobot maksimum dan n merupakan jumlah gen dalam satu kromosom. 

3.      Seleksi, proses ini dilakukan untuk mendapatkan calon induk yang baik. Dalam pengertian induk yang baik akan menghasilkan keturunan yang baik. Semakin tinggi nilai fitness suatu individu semakin besar kemungkinannya untuk terpilih. Seleksi dapat dilakukan dengan cara roulette wheel. Seleksi roulette wheel untuk memilih induk dilakukan dengan menggunakan persentase fitness setiap individu, dimana setiap individu mendapatkan luas bagian sesuai dengan persentase nilai fitnessnya.

 4.      Pindah silang (cross over), yaitu merupakan salah satu operator dalam algoritma genetika yang melibatkan dua induk untuk menghasilkan keturunan yang baru. Pindah silang dilakukan dengan melakukan pertukaran gen dari dua induk secara acak. Ada dua macam pindah silang yaitu pindah silang satu titik dan pindah silang banyak titik. Pada aplikasi ini digunakan pindah silang satu titik. Pindah silang dilakukan dengan cara menentukan posisi awal dan akhir gen pada individu yang akan dikawinkan secara acak. Kemudian dilakukan penukaran nilai gen induk 1 dan induk 2 dari posisi awal sampai dengan posisi akhir untuk diperoleh anak 1 dan anak 2 seperti terlihat pada Gambar 2 berikut:

Induk 1

Anak 1

Induk 2

Anak 2

Gambar 2 Proses pindah silang

Dari Gambar 2 dapat dilihat bahwa proses pindah silang terjadi pada satu titik yaitu pada gen ke-3 dan ke-4. 

5.      Mutasi, yaitu merupakan operator yang menukar nilai pada gen, misalnya gennya bernilai 0 menjadi 1. Mutasi dilakukan dengan memberikan nilai inversi atau menggeser nilai gen pada gen yang terpilih untuk dimutasikan. Pada aplikasi ini mutasi dilakukan dengan cara menggeser posisi gen yang dimutasi. Penggeseran ini dilakukan dengan melakukan penambahan atau pengurangan pada posisi tersebut.

ANALISA 
     Pengujian dimulai dengan memberikan informasi kebutuhan yang diinginkan dengan batasan dana yang dipunyai. Dari nilai-nilai tersebut algoritma genetika akan melalukan iterasi (Gambar 9) untuk mencari nilai keluaran dengan fitness optimal dengan harga yang mendekati batasan dana yang ada.

Gambar 9 Hasil Iterasi Algoritma Genetika

 

Setelah semua proses algoritma genetika dijalankan maka pengguna dapat mengetahui keluaran yang diinginkan. Gambar 10 merupakan tampilan dari form solusi.

 

Gambar 10 Form Solusi