Algoritma Genetika
Dalam ilmu komputer dan riset operasi, algoritma genetika (GA) adalah metaheuristik yang terinspirasi oleh proses seleksi alam yang termasuk dalam kelas yang lebih besar yaitu algoritma evolusioner (EA). Algoritma genetika biasanya digunakan untuk menghasilkan solusi berkualitas tinggi untuk masalah optimasi dan pencarian dengan mengandalkan operator yang terinspirasi secara biologis seperti mutasi, crossover, dan seleksi. Beberapa contoh aplikasi GA termasuk mengoptimalkan pohon keputusan untuk kinerja yang lebih baik, memecahkan teka-teki sudoku, optimasi hiperparameter, inferensi sebab akibat, dan lain-lain.
Metodologi
Masalah optimasi
Dalam algoritma genetika, sebuah populasi kandidat solusi (disebut individu, makhluk, organisme, atau fenotipe) untuk sebuah masalah optimasi berevolusi menuju solusi yang lebih baik. Setiap kandidat solusi memiliki sekumpulan properti (kromosom atau genotipe) yang dapat dimutasi dan diubah; secara tradisional, solusi direpresentasikan dalam bentuk biner sebagai string 0 dan 1, tetapi pengkodean lain juga dimungkinkan.
Evolusi biasanya dimulai dari populasi individu yang dibangkitkan secara acak, dan merupakan proses yang berulang, dengan populasi di setiap iterasi disebut generasi. Pada setiap generasi, kebugaran setiap individu dalam populasi dievaluasi; kebugaran biasanya merupakan nilai dari fungsi objektif dalam masalah optimasi yang sedang dipecahkan. Individu yang lebih fit dipilih secara stokastik dari populasi saat ini, dan genom setiap individu dimodifikasi (direkombinasi dan mungkin dimutasi secara acak) untuk membentuk generasi baru. Generasi baru dari kandidat solusi kemudian digunakan dalam iterasi algoritma berikutnya. Umumnya, algoritme akan berhenti ketika jumlah generasi maksimum telah dihasilkan, atau tingkat kebugaran yang memuaskan telah dicapai untuk populasi.
Algoritma genetika pada umumnya membutuhkan
Representasi standar dari setiap kandidat solusi adalah sebagai sebuah larik bit (disebut juga bit set atau bit string).Larik dengan tipe dan struktur lain dapat digunakan dengan cara yang sama. Sifat utama yang membuat representasi genetika ini nyaman adalah bagian-bagiannya mudah disejajarkan karena ukurannya yang tetap, yang memfasilitasi operasi crossover sederhana. Representasi panjang variabel juga dapat digunakan, tetapi implementasi persilangan lebih kompleks dalam kasus ini.
Representasi seperti pohon dieksplorasi dalam pemrograman genetik dan representasi bentuk grafik dieksplorasi dalam pemrograman evolusioner; campuran kromosom linier dan pohon dieksplorasi dalam pemrograman ekspresi gen.Setelah representasi genetik dan fungsi fitness didefinisikan, GA akan menginisialisasi populasi solusi dan kemudian memperbaikinya melalui aplikasi berulang dari operator mutasi, crossover, inversi, dan seleksi.
Inisialisasi
Ukuran populasi bergantung pada sifat masalah, tetapi biasanya berisi beberapa ratus atau ribuan solusi yang mungkin. Seringkali, populasi awal dibuat secara acak, sehingga memungkinkan seluruh kemungkinan solusi (ruang pencarian). Kadang-kadang, solusi dapat "diunggulkan" di area di mana solusi optimal kemungkinan besar akan ditemukan atau distribusi probabilitas pengambilan sampel disetel untuk fokus pada area-area yang lebih diminati.
Seleksi
Selama setiap generasi yang berurutan, sebagian dari populasi yang ada dipilih untuk direproduksi untuk generasi baru. Solusi individu dipilih melalui proses berbasis kebugaran, di mana solusi yang lebih bugar (yang diukur dengan fungsi kebugaran) biasanya lebih mungkin untuk dipilih. Metode seleksi tertentu menilai kecocokan setiap solusi dan secara khusus memilih solusi terbaik. Metode lain hanya menilai sampel acak dari populasi, karena proses sebelumnya mungkin sangat memakan waktu.
Fungsi kebugaran didefinisikan melalui representasi genetik dan mengukur kualitas solusi yang direpresentasikan. Fungsi kebugaran selalu bergantung pada masalah. Sebagai contoh, dalam masalah knapsack, seseorang ingin memaksimalkan nilai total objek yang dapat dimasukkan ke dalam knapsack dengan kapasitas tertentu. Representasi dari solusi dapat berupa sebuah larik bit, di mana setiap bit merepresentasikan objek yang berbeda, dan nilai dari bit tersebut (0 atau 1) merepresentasikan apakah objek tersebut ada di dalam ransel atau tidak. Tidak semua representasi seperti itu valid, karena ukuran objek bisa saja melebihi kapasitas ransel. Kecocokan solusi adalah jumlah nilai dari semua objek di dalam knapsack jika representasi tersebut valid, atau 0 jika tidak.
Dalam beberapa masalah, sulit atau bahkan tidak mungkin untuk mendefinisikan ekspresi fitness; dalam kasus ini, simulasi dapat digunakan untuk menentukan nilai fungsi fitness dari sebuah fenotipe (misalnya dinamika fluida komputasi digunakan untuk menentukan hambatan udara dari kendaraan yang bentuknya dikodekan sebagai fenotipe), atau bahkan algoritma genetika interaktif digunakan.
Operator genetika
Langkah selanjutnya adalah menghasilkan populasi generasi kedua dari solusi-solusi yang terpilih, melalui kombinasi operator genetik: crossover (juga disebut rekombinasi), dan mutasi.
Untuk setiap solusi baru yang akan dihasilkan, sepasang solusi "induk" dipilih untuk dikawinkan dari kumpulan solusi yang telah dipilih sebelumnya. Dengan menghasilkan solusi "anak" menggunakan metode persilangan dan mutasi di atas, solusi baru dibuat yang biasanya memiliki banyak karakteristik yang sama dengan "induknya". Orang tua baru dipilih untuk setiap anak baru, dan prosesnya berlanjut hingga populasi solusi baru dengan ukuran yang sesuai dihasilkan. Meskipun metode reproduksi yang didasarkan pada penggunaan dua orang tua lebih "terinspirasi oleh biologi", beberapa penelitian menunjukkan bahwa lebih dari dua "orang tua" menghasilkan kromosom yang lebih berkualitas.
Proses-proses ini pada akhirnya menghasilkan populasi kromosom generasi berikutnya yang berbeda dari generasi awal. Secara umum, rata-rata kebugaran akan meningkat dengan prosedur ini untuk populasi, karena hanya organisme terbaik dari generasi pertama yang dipilih untuk berkembang biak, bersama dengan sebagian kecil solusi yang kurang cocok. Solusi yang kurang cocok ini memastikan keanekaragaman genetik dalam kumpulan genetik orang tua dan oleh karena itu memastikan keanekaragaman genetik generasi anak-anak berikutnya.
Terdapat perbedaan pendapat mengenai pentingnya persilangan versus mutasi. Ada banyak referensi dalam Fogel (2006) yang mendukung pentingnya pencarian berbasis mutasi.Meskipun crossover dan mutasi dikenal sebagai operator genetik utama, ada kemungkinan untuk menggunakan operator lain seperti pengelompokan ulang, kolonisasi-kepunahan, atau migrasi dalam algoritme genetik.
Perlu dilakukan tuning parameter seperti probabilitas mutasi, probabilitas crossover, dan ukuran populasi untuk menemukan pengaturan yang masuk akal untuk kelas masalah yang sedang dikerjakan. Tingkat mutasi yang sangat kecil dapat menyebabkan penyimpangan genetik (yang bersifat non-ergodik). Laju rekombinasi yang terlalu tinggi dapat menyebabkan konvergensi prematur pada algoritma genetika. Laju mutasi yang terlalu tinggi dapat menyebabkan hilangnya solusi yang baik, kecuali jika seleksi elitis digunakan. Ukuran populasi yang memadai memastikan keanekaragaman genetik yang cukup untuk masalah yang dihadapi, tetapi dapat menyebabkan pemborosan sumber daya komputasi jika diatur ke nilai yang lebih besar dari yang dibutuhkan.
Heuristik
Selain operator utama di atas, heuristik lain dapat digunakan untuk membuat perhitungan lebih cepat atau lebih kuat. Heuristik spesiasi menghukum crossover antara kandidat solusi yang terlalu mirip; hal ini mendorong keanekaragaman populasi dan membantu mencegah konvergensi dini ke solusi yang kurang optimal.
Disadur dari: en.wikipedia.org