Algoritma GA (Genetic Algorithm) / Algoritma Genetika 26


Algoritma Genetika adalah salah satu algoritma yang digunakan untuk mengoptimasi hasil akhir berdasarkan sebaran inputan data acak. Contoh kasus yang akan dibahas kali ini adalah untuk mengoptimasi performa mobil dengan mengupgrade parts tertentu.
Algoritma Genetika adalah proses pencarian yang didasarkan pada seleksi alam. Teknik ini secara umum digunakan untuk menghasilkan solusi optimasi dan teknik pencarian. Algoritma Genetika menggunakan teknik yang diinspirasi dari teori evolusi alam, seperti seleksi, warisan, crossover, dan mutasi.



Pada contoh kasus ini, diasumsikan ada 3 kategori parts yang ingin diupgrade, yaitu knalpot, rem, dan mesin.
Masing-masing item memiliki biaya sendiri dan besar poin performa yang dihasilkan.
Maka tentukan pasangan parts dengan jumlah poin performa paling tinggi dan biayanya termasuk dalam biaya yang dimiliki
Contoh data untuk masing-masing kategori adalah sebagai berikut
Knalpot

Nama Item Biaya Poin Performa
Knalpot 1 2500 10
Knalpot 2 5000 15
Knalpot 3 3500 11
Knalpot 4 2000 8
Knalpot 5 4000 12

Rem
Nama Item Biaya Poin Performa
Rem 1 500 3
Rem 2 1000 5
Rem 3 800 4
Rem 4 700 4
Rem 5 1200 6

Mesin
Nama Item Biaya Poin Performa
Mesin 1 10000 30
Mesin 2 9000 25
Mesin 3 12000 40
Mesin 4 10500 33
Mesin 5 9500 28

Langkah pertama adalah memasukkan data-data yang digunakan.
Contoh data adalah sebagai berikut



Sebelum masuk kedalam bagian perhitungan, ada beberapa inputan data yang harus diketahui, yaitu
* Tentukan besar modal yang dimiliki
Diasumsikan dalam kasus ini, modal yang tersedia adalah 15000

* Tentukan iterasi
Diasumsikan dalam kasus ini, akan dilakukan 5 kali perulangan mutasi dan crossover dalam sekali perhitungan

* Tentukan besar popsize
popsize adalah jumlah baris data yang dibuat dalam satu kali iterasi
Diasumsikan dalam kasus ini, jumlah popsize adalah 10

* Tentukan probabilitas crossover
probabilitas crossover adalah persentase jumlah baris data crossover yang dibuat dalam satu kali iterasi
nantinya jumlah baris data crossover = popsize * probabilitas crossover
Diasumsikan dalam kasus ini, probabilitas crossover adalah 0.4, sehingga nantinya muncul 4 baris data crossover

* Tentukan probabilitas mutasi
probabilitas mutasi adalah persentase jumlah baris data mutasi yang dibuat dalam satu kali iterasi
nantinya jumlah baris data mutasi = popsize * probabilitas mutasi
Diasumsikan dalam kasus ini, probabilitas mutasi adalah 0.3, sehingga nantinya muncul 3 baris data mutasi


Langkah-langkah penggunaan algoritma ini adalah

1. Inisialisasi Populasi awal
Populasi adalah baris data sebanyak inputan popsize.
Isi dari populasi adalah pengambilan data secara acak dari masing-masing kategori
Jika total biaya pada baris acak tersebut melebihi modal, maka ulangi pengambilan acak.

2. Hitung Fitness untuk setiap baris data
Semakin tinggi nilai fitness, maka baris data tersebut semakin mendekati data optimal
Rumus untuk nilai fitness bisa disesuaikan, tergantung banyak parameter yang ingin digunakan dalam perhitungan
Diasumsikan dalam kasus ini, rumus nilai fitness adalah hanya melalui jumlah poin performa yang dihasilkan masing-masing parts terpilih

3. Lakukan perhitungan crossover
Crossover adalah pembuatan baris data baru berdasarkan baris data pada populasi awal
Ambil 2 baris data awal secara acak, kemudian tukar datanya pada sebuah kategori acak, catat hasilnya menjadi 2 baris data baru
Inputan probabilitas = 0.4, maka akan dihasilkan 0.4 * 10 = 4 data baru
Karena dalam sekali perhitungan menghasilkan 2 baris data baru, maka hanya perlu melakukan 2x perhitungan

4. Hitung Fitness untuk setiap baris data baru pada perhitungan crossover

5. Lakukan perhitungan mutasi
Mutasi adalah pembuatan baris data baru berdasarkan baris data pada populasi awal
Ambil 1 baris data awal secara acak, kemudian ganti data pada sebuah kategori acak, catat hasilnya menjadi baris data baru
Inputan probabilitas = 0.3, maka akan dihasilkan 0.3 * 10 = 3 data baru

6. Hitung Fitness untuk baris data baru pada perhitungan mutasi

7. Urutkan baris data ini berdasarkan fitness tertinggi
Kemudian ambil data sebanyak popsize, dan data ini akan digunakan untuk perhitungan selanjutnya

8. Ulangi perhitungan crossover, mutasi dan sorting (point nomor 3 – 7) sebanyak parameter jumlah iterasi
Setelah itu akan didapatkan data paling optimal, yaitu baris data paling awal / pertama

/br>

Hasil akhir adalah: (klik untuk perbesar gambar)

cmd3c


Contoh modul / source code dalam bahasa VB (Visual Basic) dapat didownload disini:



Jika membutuhkan jasa kami dalam pembuatan program, keterangan selanjutnya dapat dilihat di Fasilitas dan Harga
Jika ada yang kurang paham dengan langkah-langkah algoritma diatas, silahkan berikan komentar Anda.
Selamat mencoba.


Tinggalkan sebuah komentar

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *

26 pemikiran di “Algoritma GA (Genetic Algorithm) / Algoritma Genetika

  • Chandra

    Sore min, makasih sudah bahas algoritma genetika dan ada source codenya. Jadi agak paham2 dikit judul skripsi yang dipilihin dosen karena pas pengumpulan saya telat. 🙁

    Masalahnya yang dibahas penjadwalan otomatis dan saya bingung mulai darimana bikinnya. Struktur gennya ada saran min? Benar2 ngeblank soalnya.

    Terima kasih.

    • pip Penulis

      Sebelumnya saya ucapkan terima kasih telah berkunjung ke situs saya.

      Saya ingin bertanya, penjadwalan tentang apakah yang dimaksud, karena ada banyak contoh kasus penjadwalan.
      Disini saya asumsikan saja penjadwalan yang dimaksud adalah penjadwalan mata kuliah. Mudah-mudahan pemisalan ini cocok dengan kasus anda.
      Untuk penjadwalan mata kuliah, maka
      Gen adalah mata kuliah itu sendiri.
      Populasi adalah jumlah mata kuliah yang diperbolehkan dalam sebuah jadwal kuliah.
      Nilai Fitness bisa dihitung dari jumlah menit / sks dari masing-masing mata kuliah, semakin tinggi nilainya, berarti semakin banyak mata kuliah yang masuk ke dalam jadwal.

      Sebagai langkah awal pembuatan program, silahkan anda download contoh source code yang sudah saya sediakan pada halaman ini. Setelah Anda mempelajari dan memahami alur program tersebut, maka anda cukup melakukan sedikit modifikasi skrip agar sesuai dengan contoh kasus anda. Jika masih memiliki kesulitan dalam pembuatan program, bisa langsung menggunakan jasa saya 🙂
      Semoga membantu

      • Chandra

        Penjadwalan kelas laboratorium min, jadi yang mengajar nanti adalah asisten dosen. Bingung mau mulai darimana soalnya, jumlah ruangnya kan terbatas, asdos sendiri juga punya jadwal kuliah sendiri, belum lagi mata kuliah yang diajarkan kan tergantung asdosnya mampu ngajar atau tidak, apalagi ada kuota minimalnya.

        Sudah didownload min, tapi di laptop masih pakai Visual Studio 2008. Ngefek ga? Baca2 source codenya tetap galau bagaimana jadi penjadwalannya. 🙁

        Nanti kalau sudah frustasi ane minta bantuannya min, ortu udah kasih deadline tahun depan soalnya. Bisa dibantu teorinya juga kan min jasanya?

        • pip Penulis

          Saya kira penjadwalan mata kuliah, ternyata penjadwalan kelas laboratorium. Tapi pada intinya kedua topik tersebut mirip, sehingga:
          gen adalah mata kuliah yang diajarkan
          populasi adalah beberapa solusi jadwal kuliah yang tersusun dari beberapa mata kuliah
          nilai fitness dihitung dari jumlah menit / sks dari semua mata kuliah dalam jadwal

          Sewaktu men-generate populasi awal secara acak, setiap gen yang dimasukkan dalam populasi harus sudah memenuhi syarat-syarat yang ada. Disinilah dilakukan pengecekan seperti keterbatasan jumlah ruang, jadwal kuliah asdos, dan kuota minimal. Semakin banyak syarat-syarat yang diajukan, maka semakin kompleks program yang dibuat.
          Setelah populasi sudah terbentuk, maka perlu dilakukan proses crossover dan mutasi pada 1 atau beberapa gen. Setelah mengalami proses tersebut, maka harus dilakukan pengecekan syarat-syarat diatas agar populasi yang terbentuk masih tetap memenuhi syarat-syarat yang ada.
          Langkah terakhir adalah melakukan seleksi populasi untuk digunakan dalam perhitungan berikutnya. Populasi dengan nilai fitness yang lebih tinggi akan disimpan, dan sisanya akan dibuang. Kemudian lakukan kembali proses crossover dan mutasi sampai batasan perulangan sudah terpenuhi.

          Pada intinya, tingkat kesulitan program tergantung syarat-syarat yang digunakan. Jika tidak ingin programnya terlalu susah, jangan terlalu banyak memasukkan syarat dalam pembentukan jadwal kuliah. Hal tersebut bisa dicegah dalam penulisan batasan masalah pada laporan skripsi anda. Daripada anda kesulitan sendiri dalam membuat program, lebih baik syarat-syarat nya dikurangi. Jika tetap ingin memasukkan syarat-syarat tersebut, dan masih kesulitan dalam pembuatan programnya, bisa menggunakan jasa saya 🙂

          Skrip yang saya sertakan diatas saya buat dengan menggunakan Microsoft Visual Studio 2012. Lebih aman jika anda menggunakan software tersebut, tetapi bisa saja anda coba dengan versi yang lebih lama. Jika tidak ada perbedaan sintaks antara kedua tahun tersebut, seharusnya tidak akan menyebabkan error.

          Penjelasan teori juga bisa saya bantu apabila masih terdapat kesulitan. Silahkan hubungi saya melalui salah satu kontak yang terdapat pada halaman Hubungi kami. Terima kasih.

        • pip Penulis

          Baik, komunikasi selanjutnya kita lakukan secara pribadi.

          Terima kasih telah berkunjung di website ini, dan terima kasih karena telah menggunakan jasa kami.

  • Shinta

    min, bisa dijelaskan tentang perbedaan serta kegunaan algoritma kelelawar dengan algoritma genetika? Apakah algoritma kelelawar juga dapat digunakan untuk pengoptimalan penjadwalan?

  • Bobby Kevin Shearer

    Min, mau nanya dong. Kalo untuk optimasi tata letak ruangan apakah bisa menggunakan GA selain dengan VB? Karena saya sedang menyusun laporan kerja praktek dengan topik tsb. Thanks

    • pip Penulis

      Semua topik yang memiliki tujuan penelitian untuk mengoptimasi tentu saja pada umumnya bisa diselesaikan dengan semua algoritma pada kategori Algoritma Optimasi termasuk di dalamnya adalah algoritma pada pos ini. Tetapi tetap harus melihat secara spesifik, karena kondisi masing-masing kasus akan berbeda, sehingga mungkin ada algoritma tertentu yang jauh lebih baik digunakan daripada algoritma ini.

  • Alvin S.

    Permisi Mas saya mau bertanya, bila kasus tersebut saya asumsikan dengan kasu pencarian rute terpendek apakah akan tetap sama ?
    Terima kasih atas ilmu yang sangat bermanfaat ini mas
    assalamu’alaikum

    • pip Penulis

      Algoritma ini tentu saja bisa digunakan untuk menyelesaikan permasalahan pencarian jalur terpendek. Yang perlu anda lakukan adalah membangkitkan populasi dengan menggunakan jalur acak dan kemudian mengganti nilai fitness dengan menghitung nilai jarak (karena kasus anda adalah pencarian jalur terpendek).

      • Alvin S.

        Terima Kasih Mas Infonya, sekarang setelah saya melihat contoh yang sampean share kok saya berpikir sepertinya mutasinya kok tidak ada fungsinya ya mas ? atau saya yg kurang paham. Maaf mas mohon dijelaskan. Terima Kasih Mas
        Assalamu’alaikum

        • pip Penulis

          Mutasi adalah salah satu proses dari algoritma genetika, dimana individu yang terpilih akan mengalami mutasi gen, yaitu perubahan nilai gen individu tersebut tanpa dipengaruhi oleh faktor luar. Proses ini adalah salah satu cara untuk menemukan solusi yang lebih baik daripada solusi sebelumnya. Walaupun dalam implementasi ternyata tidak ditemukan solusi yang lebih baik, prosesnya harus tetap disertakan karena merupakan bagian dari algoritma ini.

    • pip Penulis

      Tentu saja hal tersebut dapat dilakukan, tetapi tidak dapat dijelaskan secara mudah karena topik yang saya gunakan disini berbeda dengan topik optimasi fungsi Himmelblau yang saya gunakan pada pembahasan algoritma lainnya. Diperlukan penyesuaian skrip di beberapa bagian agar dapat melakukan hal tersebut

    • pip Penulis

      Pada kasus penjadwalan berarti anda perlu memasukkan mata kuliah ke dalam slot jadwal kuliah sesuai ketentuan yang telah disepakati. Cara perhitungan fitness dapat dilakukan dengan mencari jadwal kuliah dengan isian terbanyak / sks terbanyak / slot kosong paling sedikit / kondisi – kondisi lainnya

  • Aditya

    Dari beberapa penelitian Algoritma k-Nearest Neighbor, untuk nilai K bisa dioptimalkan dengan menggunakan Algoritma Genetika.
    Nah kira-kira bagaimana gan cara mengimplementasikannya?

    • pip Penulis

      Tentu saja hal tersebut dapat dilakukan. Pada intinya setiap kali perulangan dalam algoritma genetika akan digunakan nilai K yang berbeda untuk mencari nilai K manakah yang memberikan hasil paling baik.

  • allansyah

    boss bisa minta program dengan kasus yg di atas gk boss?
    ana disuru buat program dengan metode AG (tugas Kampus )
    tapi ane bingung boss cara buat nya.
    terimakasih seblmnya boss

  • Allansyah

    bang bisa minta file project di atas gk bang..
    biar ane langsung Run aja bang…
    soal ane dsru buat program algoritma genetik ( tugas kuliah )
    dan waktunya udah mepet bang…
    ane belum terlalu faham dengan visual basik
    Trimaksih sebelumnya….

    • pip Penulis

      File diatas sudah merupakan file proyek secara keseluruhan. Setelah anda menjalankan VIsual Studio, buat proyek baru dengan tipe “Console Application”, kemudian salin isi skrip pada file yang disediakan atau anda bisa menimpa langsung modul kosong pada proyek tersebut