Genetic Algorithm

Genetic Algorithm(atau GA) adalah teknik pencarian dalam bidang komputasi untuk menemukan solusi benar atau pendekatan untuk masalah optimasi dan pencarian. Teknik dalam GA didasarkan pada biologi evolusioner seperti pewarisan, mutasi, seleksi dan crossover.

GA diimplementasikan sebagai proses simulasi yang dijabarkan sebagai berikut: Populasi dari representasi abstrak (disebut kromosom, genotip, atau genom) dari candidate solution (disebut individual, atau fenotip) dari optimasi yang berevolusi ke solusi yang lebih baik. Biasanya solusi direpresentasikan ke dalam string biner. Evolusi dimulai dari populasi dari individu yang dihasulkan secara random dan terjadi dalam generasi. Di setiap generasi, fitness dari setiap individu dalam populasi dievaluasi, beberapa individu dipilih secara stokastik(berdasarkan fitness) dan dimodifikasi(crossover dan kemungkinan mutasi) untuk membentuk populasi baru. Populasi baru lalu dimanfaatkan untuk iterasi selanjutnya. Secara umum, algoritma selesai jika telah menghasilkan generasi maksimum atau hasil dalam populasi dirasa memuaskan (berdasarkan berbagai parameter).

Dalam GA biasanya ada 2 hal yang harus didefinisikan:

  1. Representasi genetis dari domain solusi
  2. Fungsi fitness untuk mengevaluasi solusi domain.

Representasi standar dari solusi adalah array of bits, karena memudahkan operasi crossover. Fungsi fitness didefinisikan dari representasi genetis dan kualitas dari representasi solusi. Setelah keduanya didefinisikan, GA berlanjut ke inisialisasi populasi dari solusi secara acak, lalu berkembang lewat perulangan aplikasi mutasi, crossover dan seleksi.

Inisialisasi

Awalnya, beberapa solusi individual dihasilkan secara acak untuk membentuk populasi awal yang ukurannya tergantung sifat dari masalah.

Seleksi

Dalam setiap generasi baru, proporsi dari populasi yang ada dipilih untuk menghasilkan generasi selanjutnya. Solusi individual dipilih lewat proses fitness, dimana solusi yang lebih baik (diukur dari fungsi fitness) lebih mungkin dipilih. Metode seleksi yang umum dipakai adalah roulette wheel dan tournament.

Reproduksi

Langkah selanjutnya adalah menghasilkan generasi selanjutnya dari populasi solusi dari hasil seleksi lewat operasi genetik crossover (atau rekombinasi) dan/atau mutasi

Terminasi

Proses ini diulang sampai tercapai kondisi akhir. Kondisi akhir yang umum antara lain:

  • Solusi yang ditemukan memenuhi kriteria minimum
  • Jumlah generasi tertentu telah tercapai
  • Telah mencapai waktu komputasi tertentu
  • Tidak dapat dihasilkan hasil yang lebih baik
  • Inspeksi manual
  • Kombinasi dari kondisi di atas.

Pseudo-code

1. Pilih populasi awal

2. Evaluasi fitness dari tiap individu dalam populasi

3. Iterasi:

    • Pilih individu terbaik untuk reproduksi
    • Hasilkan generasi baru lewat crossover dan mutasi dan menghasilkan anak
    • Evaluasi fitness dari setiap individu anak
    • Ganti bagian populasi terburuk dengan anak

4. Sampai kondisi akhir tercapai

Demikian artikel singkat tentang GA ini

Referensi:

http://en.wikipedia.org tentang GA.

About dnial

You don't see anything You don't hear anything You don't know anything Move along and pretend nothing happen

Posted on 25 April, 2007, in programming, writting. Bookmark the permalink. 2 Komentar.

  1. Dan? Kau kenapa? Ada masalah? Putus ama pacar? Atau salah minum obat? Abis dugem dan masih mabuk? Tulisan ini kayak bukan Daniel deh….😀

  2. Sekali-sekali posting tentang programming mosok ga oleh?
    Sithik ae lho…
    Ini yo gara-gara tugas Intelegensia Mesin seh asline…

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

%d blogger menyukai ini: