All about Genetic Algorithm (Algoritma Genetika)

Pengertian / Apa yang Dimaksud dengan Algoritma Genetika

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 dengan lingkungan hidupnya. “Hanya individu-individu yang kuat yang mampu bertahan”. Proses seleksi alamiah ini melibatkan perubahan gen yang terjadi pada individu melalui proses perkembangbiakan.



Dalam algoritma genetika ini, proses perkembang-biakan ini menjadi proses dasar yang menjadi perhatian utama, dengan dasar berpikir: “Bagaimana mendapatkan keturunan yang lebih baik”. Algoritma genetika ini ditemukan oleh John Holland dan dikembangkan oleh muridnya David Goldberg.

Beberapa Definisi Penting Dalam Algoritma Genetika

Genotype (Gen), sebuah nilai yang menyatakan satuan dasar yang membentuk suatu arti tertentu dalam satu kesatuan gen yang dinamakan kromosom. Dalam algoritma genetika, gen ini bisa berupa nilai biner, float, integer maupun karakter, atau kombinatorial.

Allele, nilai dari gen.

Kromosom, gabungan gen-gen yang membentuk nilai tertentu.

Individu, menyatakan satu nilai atau keadaan yang menyatakan salah satu solusi yang mungkin dari permasalahan yang diangkat.

Populasi, merupakan sekumpulan individu yang akan diproses bersama dalam satu siklus proses evolusi.

Generasi, menyatakan satu-satuan siklus proses evolusi.

Nilai Fitness, menyatakan seberapa baik nilai dari suatu individu atau solusi yang didapatkan.

Sejarah Algoritma Genetika

Teori darwin yang sempat membuat orang orang berfikir bahwa manusia berasal dari kera, bahkan lebih rendah telah membuat membutakan kita sekitar abad 19 hingga beberapa tahun belakangan ini. Pada abad ke 19 banyak ilmuwan yang mencoba untuk membuktikan dan mensimulasikannya. Neo darwinisme yang menyebutkan bahwa sejarah kehidupan mahkluk hidu[ adalah melalui suatu mekanisme proses statistika yang terjadi antara populasi dan spesies, yang dikenal dengan proses manipulasi genetika. Proses ini masing-masing adalah reproduksi, mutasi, kompetisi dan pemilihan.

Cikal bakal penggunaan GA untuk pencarian dalam sistem buatan di prakarsai oleh beberapa ahli biologi yang menggunakan komputer digital untuk mengerjakan simulasi dari sistem genetika. Diantara para ahli tersebut adalah:

1. Baricelli, N.A pada tahun 1957 melakukan penelitian tentang proses evolusi simbiogenetik yang direalisasikan dengan sistem artificial.
2. Baricelli, N.A pada tahun 1962 mengajukan teory evolusi dan analisis numeriknya
3. Fraser, A.S pada tahun 1960 menyimulasikan sistem genetika dengan komputer, yang meliputi aspek-aspek S-linkage,dominasi dan epistasis.

Meskipun penelitian –penelitian tersebut bertujuan untuk meneliti gejala alam namun yang mereka kerjakan secar kebetulan memiliki pemikiran paralel yang memunculkan ide tentang Genetic Algorithm.

Fraser mensimulasikan evolusi dari 15 bit Biner sebagai string generasi dan menghitung presentasi dari induvidu-induvidu yang terpilih oleh fenotip dengan generasi-generasi yang berurutan.pada saat itu fraser tidak menyebutkan dalam laporannya bahwa algoritma pencarian dalam gejala alam akan berguna dalam sistem buatan, namun ternyata hasil dari penmuannya ternyata menyerupai optimasi fungsi.

Hal itulah yang memberikan inspirasi bagi John Holand dan murid-muridnya untuk mengaplikasikan proses genetika ini pada sistem buatan.holand menancapkan pondasi dalam karya tulisnya pada teory sistem adaptif yaitu:

1. Concern efficient adaptive systems(1962)
2. Information prosessing and prosesing systems(1962)
3. Outline for a logical theory of adaptive sistems(1962)

Tahun 1962-1965 holand mengajar tentang theory of adaptive sistem dan sering memberikan seminar-seminar tentang ini. Dalam masa itu penyempurnaan GA makin jelas. Selanjutnya dibuatlah rumus standart untuk GA ini.

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.