Algoritma genetik

Algoritma genetik adalah teknik pencarian yang di dalam ilmu komputer untuk menemukan penyelesaian perkiraan untuk optimisasi dan masalah pencarian. Algoritma genetik adalah kelas khusus dari algoritme evolusioner dengan menggunakan teknik yang terinspirasi oleh biologi evolusioner seperti warisan, mutasi, seleksi alam dan rekombinasi (atau crossover)

Algoritma Genetik pertama kali dikembangkan oleh John Holland pada tahun 1970-an di New York, Amerika Serikat. Dia beserta murid-murid dan teman kerjanya menghasilkan buku berjudul "Adaption in Natural and Artificial Systems" pada tahun 1975.

Algoritma Genetik khususnya diterapkan sebagai simulasi komputer di mana sebuah populasi representasi abstrak (disebut kromosom) dari solusi-solusi calon (disebut individual) pada sebuah masalah optimisasi akan berkembang menjadi solusi-solusi yang lebih baik. Secara tradisional, solusi-solusi dilambangkan dalam biner sebagai string '0' dan '1', walaupun dimungkinkan juga penggunaan penyandian (encoding) yang berbeda. Evolusi dimulai dari sebuah populasi individual acak yang lengkap dan terjadi dalam generasi-generasi. Dalam tiap generasi, kemampuan keseluruhan populasi dievaluasi, kemudian multiple individuals dipilih dari populasi sekarang (current) tersebut secara stochastic (berdasarkan kemampuan mereka), lalu dimodifikasi (melalui mutasi atau rekombinasi) menjadi bentuk populasi baru yang menjadi populasi sekarang (current) pada iterasi berikutnya dari algoritma.

Sejarah

Pada tahun 1950, Alan Turing mengusulkan sebuah “learning machine” yang akan berjalan sejajar dengan prinsip-prinsip evolusi.^[1] Simulasi komputer mengenai evolusi mulai dilakukan sejak tahun 1954 melalui karya Nils Aall Barricelli, yang menggunakan komputer di Institute for Advanced Study di Princeton, New Jersey.^[2][3] Publikasinya pada tahun 1954 tidak mendapat perhatian luas. Mulai tahun 1957, ahli genetika kuantitatif asal Australia, Alex Fraser, menerbitkan serangkaian makalah tentang simulasi seleksi buatan pada organisme dengan banyak lokus yang mengendalikan suatu sifat terukur. Dari awal inilah, simulasi komputer tentang evolusi oleh para biolog menjadi semakin umum pada awal 1960-an, dan metode-metodenya dijelaskan dalam buku Fraser dan Burnell (1970) serta Crosby (1973). Simulasi Fraser memasukkan semua elemen penting dari algoritma genetika modern. Selain itu, Hans-Joachim Bremermann menerbitkan serangkaian makalah pada 1960-an yang juga menggunakan populasi solusi untuk memecahkan masalah optimasi melalui rekombinasi, mutasi, dan seleksi. Penelitiannya juga memasukkan komponen-komponen yang kini dikenal sebagai algoritma genetika modern. Pelopor awal lain yang patut dicatat mencakup Richard Friedberg, George Friedman, dan Michael Conrad. Banyak makalah awal kemudian dicetak ulang oleh Fogel (1998).

Meskipun Barricelli, dalam karya yang ia laporkan pada tahun 1963, telah mensimulasikan evolusi kemampuan memainkan sebuah permainan sederhana, evolusi artifisial baru diakui luas sebagai metode optimasi berkat karya Ingo Rechenberg dan Hans-Paul Schwefel pada 1960-an dan awal 1970-an—kelompok Rechenberg berhasil memecahkan masalah-masalah rekayasa yang kompleks melalui strategi evolusi. Pendekatan lain adalah teknik pemrograman evolusioner dari Lawrence J. Fogel, yang diusulkan untuk menghasilkan kecerdasan buatan. Pemrograman evolusioner pada awalnya menggunakan mesin keadaan hingga untuk memprediksi lingkungan, lalu menggunakan variasi dan seleksi untuk mengoptimalkan logika prediktifnya. Algoritma genetika secara khusus menjadi populer melalui karya John Holland pada awal 1970-an, terutama melalui bukunya Adaptation in Natural and Artificial Systems (1975). Karyanya berakar pada studi mengenai sel automata yang dilakukan oleh Holland dan para mahasiswanya di University of Michigan. Holland memperkenalkan kerangka formal untuk memprediksi kualitas generasi berikutnya, yang dikenal sebagai Schema Theorem Holland. Penelitian mengenai algoritma genetika tetap bersifat teoretis hingga pertengahan 1980-an, ketika Konferensi Internasional Pertama tentang Algoritma Genetika diselenggarakan di Pittsburgh, Pennsylvania.^[4]

Produk Komersial

Pemanfaatan algoritma genetika dalam ranah komersial mulai mendapatkan momentum pada akhir dekade 1980-an. Salah satu tonggak awalnya adalah ketika General Electric memperkenalkan produk algoritma genetika pertama di dunia, berupa seperangkat perangkat lunak berbasis mainframe yang ditujukan untuk pengoptimalan proses industri. Langkah tersebut menandai masuknya teknologi evolusioner ke dalam praktik rekayasa berskala besar.

Perkembangan lebih lanjut terjadi pada tahun 1989 ketika Axcelis, Inc. meluncurkan Evolver, perangkat lunak algoritma genetika komersial pertama yang dapat digunakan pada komputer desktop. Keberadaannya menarik perhatian publik, termasuk liputan dari jurnalis teknologi The New York Times, John Markoff, pada tahun 1990. Selama beberapa tahun, Evolver menjadi satu-satunya perangkat algoritma genetika interaktif yang tersedia secara komersial, sebelum kemudian dijual kepada Palisade pada tahun 1997 dan dikembangkan hingga mencapai versi keenam.^[5]

Prosedur Algoritma Genetik

Algoritma genetik yang umum menyaratkan dua hal untuk didefinisikan: (1) representasi genetik dari penyelesaian, (2) fungsi kemampuan untuk mengevaluasinya.

Representasi baku adalah sebuah larik bit-bit. Larik jenis dan struktur lain dapat digunakan dengan cara yang sama. Hal utama yang membuat representasi genetik ini menjadi tepat adalah bahwa bagian-bagiannya mudah diatur karena ukurannya yang tetap, yang memudahkan operasi persilangan sederhana. Representasi panjang variabel juga digunakan, tetapi implementasi persilangan lebih kompleks dalam kasus ini. Representasi seperti pohon diselidiki dalam pemrograman genetik dan representasi bentuk bebas diselidiki di dalam HBGA.

Fungsi kemampuan didefinisikan di atas representasi genetik dan mengukur kualitas penyelesaian yang diwakili. Fungsi kemampuan selalu tergantung pada masalah. Sebagai contoh, jika pada ransel kita ingin memaksimalkan jumlah benda (objek) yang dapat kita masukkan ke dalamnya pada beberapa kapasitas yang tetap. Representasi penyelesaian mungkin berbentuk larik bits, di mana tiap bit mewakili objek yang berbeda, dan nilai bit (0 atau 1) menggambarkan apakah objek tersebut ada di dalam ransel atau tidak. Tidak setiap representasi seperti ini valid, karena ukuran objek dapat melebihi kapasitas ransel. Kemampuan penyelesaian adalah jumlah nilai dari semua objek di dalam ransel jika representasi itu valid, atau jika tidak 0. Dalam beberapa masalah, susah atau bahkan tidak mungkin untuk mendefinisikan lambang kemampuan, maka pada kasus ini digunakan IGA.

Sekali kita mendefinisikan representasi genetik dan fungsi kemampuan, algoritma genetik akan memproses inisialisasi populasi penyelesaian secara acak, dan memperbaikinya melalui aplikasi pengulangan dengan aplikasi operator-operator mutasi, persilangan, dan seleksi.

Secara sederhana, algoritma umum dari algoritma genetik ini dapat dirumuskan menjadi beberapa langkah, yaitu:

1. Membentuk suatu populasi individual dengan keadaan acak
2. Mengevaluasi kecocokan setiap individual keadaan dengan hasil yang diinginkan
3. Memilih individual dengan kecocokan yang tertinggi
4. Bereproduksi, mengadakan persilangan antar individual terpilih diselingi mutasi
5. Mengulangi langkah 2 - 4 sampai ditemukan individual dengan hasil yang diinginkan