Evolutionary Computing (Algoritma Genetika)

Algoritma Genetika

Algoritma genetika merupakan evolusi/ perkembangan dunia computer dalam bidang kecerdasan buatan (artificial intelligence). Sebenarnya kemunculan algoritma genetika ini terinspirasi oleh teori evolusi Darwin (walaupun pada kenyatanya teori tersebut terbukti keliru) dan teori-teori dalam ilmu biologi, sehingga banyak istilah dan konsep biologi yang digunakan. Karena itu sesuai dengan namanya, proses-proses yang terjadi dalam algoritma genetika samadengan apa yang terjadi pada evolusi biologi. Algoritma genetika merupakan teknik pencarian nilai optimum secara stochastic berdasarkan mekanisme seleksi alam. Algoritma genetika berbeda dengan teknik konvergensi konvensional yang lebih bersifat deterministik. Metodenya sangat berbeda dengan kebanyakan algoritma optimasi lainnya, yaitu mempunyai ciri-cirinya sebagai berikut:

Algoritma genetika merupakan evolusi/ perkembangan dunia computer dalam bidang kecerdasan buatan (artificial intelligence). Sebenarnya kemunculan algoritma genetika ini terinspirasi oleh teori evolusi Darwin (walaupun pada kenyatanya teori tersebut terbukti keliru) dan teori-teori dalam ilmu biologi, sehingga banyak istilah dan konsep biologi yang digunakan. Karena itu sesuai dengan namanya, proses-proses yang terjadi dalam algoritma genetika sama dengan apa yang terjadi pada evolusi biologi. Algoritma genetika merupakan teknik pencarian nilai optimum secara stochastic berdasarkan mekanisme seleksi alam. Algoritma genetika berbeda dengan teknik konvergensi konvensional yang lebih bersifat deterministik.

Metodenya sangat berbeda dengan kebanyakan algoritma optimasi lainnya, yaitu mempunyai ciri-cirinya sebagai berikut:

A.      Menggunakan hasil pengkodean dari parameter, bukan parameter itu sendiri. 

B.      Bekerja pada populasi bukan pada sesuatu yang unik. 

C.       Menggunakan nilai satu-satunya pada fungsi dalam prosesnya.Tidak mengunakan fungsi luar atau pengetahuan luar lainnya.

D.      Menggunakan fungsi transisi probabilitas, bukan sesuatu yang pasti.

PRINSIP DASAR ALGORITMA GENETIK

A.      Operator-Operator Genetika

Tiga operator dasar yang sering digunakan dalam Algoritma Genetika adalah reproduksi, pindah silang (crossover), dan mutasi. Dalam proses reproduksi, setiap individu populasi pada suatu generasi diseleksi berdasarkan nilai fitnessnya untuk bereproduksi guna menghasilkan keturunan. Probabilitas terpilihnya suatu individu untuk bereproduksi adalah sebesar nilai fitness individu tersebut dibagi dengan jumlah nilai fitness seluruh individu dalam populasi (Davis, 1991)

B.      Parameter Parameter Genetika

Parameter-parameter genetika berperan dalam pengendalian operator-operator genetika yang digunakan dalam optimasi menggunakan Algoritma Genetika (Davis, 1991; Sundhararajan, 1994; Sastry, 2004). Parameter Genetika yang sering digunakan meliputi ukuran populasi (N), probabilitas pindah silang (Pc), dan probabilitas mutasi (Pm). Pemilihan ukuran populasi yang digunakan tergantung pada masalah yang akan diselesaikan. Untuk masalah yang lebih kompleks biasanya diperlukan ukuran populasi yang lebih besar guna mencegah konvergensi prematur (yang menghasilkan optimum lokal).

Pada tiap generasi, sebanyak Pc*N individu dalam populasi mengalami pindah silang. Makin besar nilai Pc yang diberikan, makin cepat struktur individu baru yang diperkenalkan ke dalam populasi. Jika nilai Pc yang diberikan terlalu besar, individu yang merupakan kandidat solusi terbaik dapat hilang lebih cepat dibanding seleksi untuk peningkatan kinerja. Sebaliknya, nilai Pc yang rendah dapat mengakibatkan stagnasi karena rendahnya angka eksplorasi. Probabilitas mutasi adalah probabilitas dimana setiap posisi bit pada tiap string dalam populasibaru mengalami perubahan secara acak setelah proses seleksi. Dalam satu generasi, dengan L panjang struktur, kemungkinan terjadi mutasi sebanyak Pm*N*L.

  

C.      Fungsi Fitness

Dalam Algoritma Genetika, fungsi fitness merupakan pemetaan fungsi obyektif dari masalah yang akan diselesaikan (Goldberg, 1989). Setiap masalah yang berbeda yang akan diselesaikan memerlukan pendefinisian fungsi fitness yang berbeda.

Misalkan fungsi obyektif g(x) berupa fungsi besaran yang ingin diminimumkan, maka bentuk fungsi fitness f(x) dapat dinyatakan sebagai:

f(x) = Cmax g(x), untuk g(x) < Cmax, = 0, untuk g(x) ³ Cmax ……………………...(1)

Cmax dapat diambil sebagai koefisien masukan, misalnya nilai g terbesar yang dapat diamati, nilai g terbesar pada populasi saat ini, atau nilai g terbesar k generasi terakhir.

D.     Siklus Eksekusi Algoritma Genetika

Dalam satu siklus iterasi (yang disebut generasi) pada Algoritma Genetika terdapat dua tahap, yaitu tahap seleksi dan tahap rekombinasi (Goldberg, 1989; Jun He, et.al., 2005). Secara garis besar, siklus eksekusi Algoritma Genetika dapat diringkas dalam bentuk diagram alir. Tahap seleksi dilakukan dengan mengevaluasi kualitas setiap individu dalam populasi untuk mendapat peringkat kandidat solusi. Berdasarkan hasil evaluasi, selanjutnya dipilih individu-individu yang akan mengalami rekombinasi. Tahap rekombinasi meliputi proses-proses genetika untuk mendapatkan populasi baru kandidat-kandidat solusi.

Sejarah Singkat Algoritma Genetika

Awal sejarah perkembangan dari algoritma genetika (genetic algorithm) dimulai pada tahun 1960. Pada waktu itu, I. Rochenberg dalam bukunya yang berjudul “Evolution Strategies” mengemukakan tentang evolusi computer (computer evolutionary) yang kemudian dikembangkan oleh peneliti lain. Algoritma genetika sendiri pertama kali dikembangkan oleh John Holland pada tahun 1970-an di New York Amerika Serikat yang dikembangkan bersama mahasiswa dan rekan-rekannya. Hal tersebut bisa dibuktikan dengan adanya buku yang dibuat oleh Holland dengan judul “Adaptation in Natural and Artificial System” yang diterbitkan pada tahun 1975. 

Lalu tujuh belas tahun kemudian, John Koza melakukan penelitian suatu program yang berkembang dengan menggunakan algoritma genetika. Program yang dikenal dengan sebutan metode “Genetic Programming” tersebut dibuat menggunakan LISP (bahasa pemrogramannya dapat dinyatakan dalam bentuk parse tree yaitu objek kerjanya pada algoritma genetika). Sampai sekarang algoritma genetika ini terus digunakan untuk memecahkan permasalahan yang sulit dipecahkan dengan menggunakan algoritma konvensional. 

Aplikasi Algortima Genetika

Sejak pertama kali dirintis oleh John Holland pada tahun 1960-an, algoritma genetika telah dipelajari, diteliti, dan diaplikasikan secara luas pada berbagai bidang. Algoritma genetika banyak digunakan pada masalah praktis yang berfokus pada pencarian parameter-parameter optimal. Hal ini membuat banyak orang mengira bahwa algoritma genetika hanya bisa digunakan untuk masalah optimasi. Pada kenyataannya, algoritma juga memiliki performansi yang bagus untuk masalah-masalah selain optimasi . Keuntungan penggunaan algoritma genetika sangat jelas terlihat dari kemudahan implementasi dan kemampuannya untuk menemukan solusi yang bagus (bisa diterima) secara cepat untuk masalah-masalah berdimensi tinggi. Algoritma genetika sangat berguna dan efisien untuk masalah-masalah dengan karakteristik sebagai berikut:

a.       Ruang masalah sangat besar, kompleks, dan sulit dipahami. 

b.    Kurang atau bahkan tidak ada pengetahuan yang memadai untuk merepresentasikan masalah ke dalam ruang pencarian yang lebih sempit. 

c.        Tidak tersedianya analisis matematika yang memadai. 

d.       Ketika metode-metode konvensional sudah tidak mampu meyelesaikan masalah yang dihadapi.

e.       Solusi yang diharapkan tidak harus paling optimal, tetapi cukup bagus atau bisa diterima.

f.         Terdapat batasan waktu, misalnya real time system atau sistem waktu nyata.

Hal-Hal Yang Harus Dilakukan Dalam Menggunakan Algoritma Genetika

1.  Mendefinisikan individu, dimana individu menyatakan salah satu solusi (penyelesaian) yang mungkin dari permasalahan yang diangkat.

2.    Mendefinisikan nilai fitness, yang merupakan ukuran baik-tidaknya sebuah individu atau baik-tidaknya solusi yang didapatkan.

3. Menentukan proses pembangkitan populasi awal. Hal ini biasanya dilakukan dengan menggunakan pembangkitan acak seperti random-walk.

4.       Menentukan proses seleksi yang akan digunakan.

5.       Menentukan proses perkawinan silang (cross-over) dan mutasi gen yang akan digunakan.

Hal penting yang harus diketahui dalam pemakaian Algoritma Genetika

1. Algoritma Genetika adalah algoritma yang dikembangkan dari proses pencarian solusi menggunakan pencarian acak, ini terlihat pada proses pembangkitan populasi awal yang menyatakan sekumpulan solusi yang dipilih secara acak.

2.    Berikutnya pencarian dilakukan berdasarkan proses-proses teori genetika yang
memperhatikan pemikiran bagaimana memperoleh individu yang lebih baik, sehingga
dalam proses evolusi dapat diharapkan diperoleh individu yang terbaik.

Beberapa Implementasi Algoritma Genetika Yang Sudah Dilakukan

1.   Algoritma Genetika untuk mengoptimalkan model antenna array dengan memperbesar main-lobe dan menurunkan side-lobe

2.       Algoritma Genetika untuk menyusun jadwal kuliah di PENS-ITS

3.       Algoritma Genetika untuk menyelesaikan TSP (Traveling Salesman Problem)

4.       Algoritma Genetika untuk menyusun jadwal pendistribusian produk (TSP multikriteria)

5.       Algoritma Genetika untuk menyelesaikan masalah Knapsack

6.       Algoritma Genetika untuk menentukan filter optimal yang dapat mereduksi noise pada gambar

7.       Algoritma Genetika untuk menentukan nilai maksimal atau minimal sistem non
linier.

8.       Algoritma Genetika untuk mencari bentuk lingkaran pada suatu gambar

9.       Algoritma Genetika untuk menentukan posisi suatu obyek gambar pada keseluruhan gambar.

10.   Algoritma Genetika untuk menyusun jadwal penguji proyek akhir di Jurusan Telekomunikasi dan Jurusan Teknologi Informasi PENS-ITS.

11.   Algoritma Genetika untuk menentukan pembobot nilai optimal dalam melakukan ranking pegawai.

12.   Algoritma Genetika untuk peramalan time-series.

Algoritma Genetika Untuk Langkah Berikutnya

1.       Algoritma Genetika sangat handal untuk melakukan proses pencarian dan optimasi.

2.   Salah satu hal yang menggembirakan adalah kecepatan komputasi algoritma genetika untuk proses optimasi bisa dikatakan sangat baik.

3.       Proses-proses optimasi yang membutuhkan kecepatan komputasi dengan kompleksitas
yang tinggi membutuhkan algoritma genetika.

Referensi :

http://bow-masbow.blogspot.co.id/2010/10/all-about-genetic-algorithm-algoritma.html

http://ngampusmulu.blogspot.co.id/2015/06/algoritma-genetika.html#.WEBO0dJ97IU

http://blogdavidaritonang.blogspot.co.id/2013/07/aplikasi-algoritma-genetika.html