Genetic Algorithm

Read Also

Metoda genetic algoritma diinspirasikan dan berdasarkan pada proses evolusi yang terjadi pada makhluk hidup. Proses evolusi ini bertujuan untuk menghasilkan keturunan yang lebih baik. Demikan juga metoda genetic algoritma, bekerja dengan suatu cost function sebagai fungsi yang menguji kualitas solusi yang dalam hal ini dilambangkan sebagai suatu individu dalam satu generasi. Suatu solusi akan di-kodekan dengan kode string dan dapat dianggap seperti DNA, kemudian akan dikawinkan dengan solusi lainnya. Suatu individu baru terlahir dianggap sebagai solusi baru. Sehingga pada dasarnya GA ini merupakan proses search yang berdasarkan seleksi alami dan genetika. Tujuan dari metoda ini adalah menghasilkan individu turunan yang lebih baik, turunan adalah bentuk dari solusi yang ingin dicapai. Seleksi merupakan pemilihan solusi yang tepat diantara solusi yang ada, dilakukan dengan cara rangking atau turnamen, tetapi pada dasarnya adalah memilih individu yang lebih baik.

Biasanya ada 2 yang wajib diperhatikan dalam Genetic Algorithm, pemecahan masalah dan evaluasi.Berangkat dari parameter untuk optimasi dimana kita harus mengoptimalkan manfaat dari target atau meminimalkan kesalahan yang mungkin. Kita dapat memandang suatu problem sebagai black box dengan beberapa tombol yang dianggap sebagai parameter. Hasil dari black box hanya didapat dari suatu fungsi perhitungan yang menandakan baik tidaknya kombinasi dari beberapa parameter yang berbeda. Kebanyakan masalah untuk Genetic Algorithm adalah nonlinear. Dengan kata lain, setiap parameter tidak dapat digunakan untuk memecahkan masalah tanpa bantuan dari parameter lain. Jadi setiap parameter tidak dapat berdiri sendiri.

            Asumsi pertama, suatu variabel(parameter) direpresentasikan sebagai string. GA dimulai dengan serangkaian solusi awal (kromosom), yang disebut populasi. Populasi ini akan ber-evolusi menjadi populasi yang berbeda melalui serangkaian iterasi. Pada akhir iterasi, GA mengembalikan anggota populasi yang terbaik sebagai solusi untuk problem tersebut. Pada setiap iterasi (generasi), proses evolusi yang terjadi adalah sebagai berikut:

1.   Dua anggota populasi (parent) dipilih berdasarkan pada suatu distribusi populasi.

Kedua anggota ini kemudian dikombinasikan atau dikawinkan melalui operator crossover (pindah silang) untuk menghasilkan anak (offspring).

2.   Dengan probabilitas yang rendah, anak ini akan mengalami perubahan oleh operator mutasi.

3.   Apabila anak sesuai untuk populasi tersebut, suatu skema penggantian (replacement scheme) diterapkan untuk memilih anggota populasi yang akan digantikan oleh anak.

4.   Proses ini terus berulang sampai dicapai kondisi tertentu, misalnya sampai jumlah iterasi tertentu.

Ada beberapa pengertian yang harus diketahui :

• Kromosom : serangkaian nilai gen.
• Gen : mempunyai nilai berupa suatu alfabet S, misalnya {0,1}.
• Solusi : direpresentasikan oleh suatu kromosom.
• Skema : pola gen yang menggambarkan suatu subset dari string yang memiliki kesamaan pada posisi gen tertentu.
• Orde : banyaknya simbol khusus pada suatu skema.
• Defining length : jarak antara simbol khusus paling kiri dan paling kanan.

Misal: 10* adalah skema yang mewakili himpunan kromosom yang mempunyai nilai 1 pada bit pertama dan 0 pada bit kedua. Skema tersebut memiliki orde 2 dan defining length-nya adalah 1.

Suatu kromosom dengan panjang n dapat juga dipandang sebagai instance (anggota) dari 2ⁿ skema. Misal, kromosom 101 adalah suatu instance dari 8 skema, yaitu ***, 1**, *0*, **1, 10*, 1*1, *01, dan 101. Algoritma Genetika tidak secara eksplisit dalam menangani skema, namun konsep skema sangat penting dalam analisis perilaku Algoritma Genetika dalam pemecahan suatu masalah.

            Ada 3 prinsip dalam GA :

1.Reproduksi

            Reproduksi merupakan proses dimana setiap individu dari populasi melahirkan individu baru dengan sifatnya/kelakuannya masing-masing. Kelakuan individu baru ini dinamakan value dari suatu fungsi fitness. Pemilihan individu orang tua bergantung pada nilai fungsi fitness dari individu-individu tersebut di dalam populasinya. Kegunaan dari pemilihan orang tua dalam GA adalah untuk memberikan kesempatan bereproduksi terhadap seluruh anggota populasi yang terbaik. Ada banyak cara untuk menyelenggarakan pemilihan orang tua, salah satunya adalah pemilihan orang tua. Sehingga semakin lama populasi yang terbentuk akan semakin kecil.

2.Cross Over

          As described in the previous section there exist also a lot of different types of Mating/Crossover. One easy to understand type is the random mating with a defined probability and the b_nX crossover type. This type is described most often, as the parallel to the Crossing Over in genetics is evident:

1.    P_M percent of the individua of the new population will be selected randomly and mated in pairs.

2.    A crossover point (see fig.2) will be chosen for each pair

3.    The information after the crossover-point will be exchanged between the two individua of each pair.

In fact, more often a slightly different algorithm called b_uX is used. This crossover type usually offers higher performance in the search.

1.    P_M percent of the individua of the new population will be selected randomly and mated in pairs.

2.    With the probability P_C, two bits in the same position will be exchanged between the two individua. Thus not only one crossover point is chosen, but each bit has a certain probability to get exchanged with its counterpart in the other gene. (This is called the uniform operator)

Ada banyak tipe Crossover. Salah satu yang paling mudah dipahami adalah crossover random dengan probability yang telah ditentukan dan b_nX tipe crossover. Singkatnya sebagai berikut :

1.   P_M adalah persen suatu individu dalam populasi akan dipilih secara random untuk dilakukan crossover.

2.   Crossover point akan dipilih dari setiap pasangan.

3.   Informasi yang terletak setelah crossover point akan ditukarkan antara 2 individu dalam setiap pasangan.

Kenyataannya, seringkali algoritma yang berbeda digunakan (dinamakan b_uX). Tipe ini biasanya menawarkan performansi yang lebih dalam pencarian. Algoritma sebagai berikut :

1.   P_M adalah persen suatu individu dalam populasi akan dipilih secara random untuk dilakukan crossover.

2.   Dengan probabilitas P_{C ,} 2 bit dalam posisi yang sama akan dipertukarkan antara 2 individu.Jadi  tidak hanya  1 crossover point yang dibutuhkan, tetapi 2 crossover point.

3.Mutasi

            Mutasi diperlukan untuk mengembalikan informasi bit yang hilang akibat cross over. Mutasi diterapkan dengan probabilitas sangat kecil. Jika mutasi dilakukan terlalu sering, maka akan menghasilkan individu yang lemah karena konfigurasi bit pada kromosom yang unggul akan dirusak. Berdasarkan bagian yang termutasi, proses mutasi dapat dibedakan atas tiga bagian:

1.   Tingkat kromosom: semua gen dalam kromosom berubah

2.   Tingkat gen: semua bit dalam satu gen akan berubah. Misal gen 2 yang  mengalami mutasi

3.      Tingkat bit: hanya satu bit yang berubah.

PEMILIHAN ORANG TUA

         Pemilihan orang tua didasarkan pada proportional selection scheme, yaitu: Setiap kromosom dipilih sebagai parent berdasarkan suatu probabilitas yang proporsional terhadap nilai fitness masing-masing. Salah satu teknik yang sering digunakan adalah Roulette Wheel. Penentuan fungsi fitness bergantung pada masalah yang akan dioptimasi.