Genetic Algorithm- A Literature Review

Paper Review oleh Rheivant Bosco Theoffilus, Aditya Samagan Cahyo Bagaskoro, Galuh Putra Warman, Richard, Adriel Lazaro Fitzhan.

Editor: Amalia Zahra, S.Kom., Ph.D.

Referensi: Lambora, A., Gupta, K., & Chopra, K. (2019, February). Genetic algorithm-A literature review. In 2019 International Conference on Machine Learning, Big Data, Cloud and Parallel Computing (COMITCon) (pp. 380-384). IEEE.

Genetic Algorithm (GA) merupakan algoritma yang berdasarkan prinsip seleksi genetika yang dikenalkan oleh John Holland pada tahun 1970. Pada umumnya, algoritma ini digunakan pada machine learning dan problem optimization. Dengan bantuan artificial intelligence dan optimisasi alat pencarian, GA sangat efektif digunakan untuk mencari data pada data-data yang besar dan tidak terorganisir ataupun suatu masalah yang sangat kompleks, baik dibatasi ataupun tidak dibatasi.

Function atau fungsi pada GA sangat dipengaruhi oleh dua konsep utama dari Natural Evolution. Konsep yang pertama adalah natural selection dan yang kedua adalah dinamika genetik yang melibatkan operasi genetik yang berbeda seperti crossover, mutasi, dan lain-lain. Oleh karena itu, algoritma ini sangatlah efektif dalam aplikasi yang beragam seperti pencarian, optimisasi, pengambilan keputusan, machine learning, robotika, dan masih banyak lagi.

Operation in GA:

Gambar 1. Genetic Algorithm Flow Chart

1. Selection

Memilih kromosom yang merupakan solusi dalam bentuk bilangan biner. Setiap bit atau gen dari kromosom mempresentasikan aspek dari solusi tersebut.

Contoh :

Kromosom 1 = 1000101001

Kromosom 2 = 0010001101

1. Crossover

Fungsi crossover adalah untuk memperoleh kromosom child (offspring) dari kromosom parents. Proses eksekusi crossover dapat dilakukan dengan berbagai macam metode; salah satu metode yang mudah yaitu secara random. Selain itu crossover juga bisa menggunakan metode yang kompleks dan rumit sesuai dengan kebutuhan untuk mendapatkan hasil offspring yang diinginkan.

Contoh :

Kromosom 1 = 1000101001

Kromosom 2 = 0010001101

Offspring 1 = 1000101101

Offspring 2 = 0010001001

1. Mutation

Mutasi merupakan cara yang sengaja dibuat dalam menyelesaikan masalah untuk mencegah semua solusi pada populasi jatuh pada local optima. Proses dari mutasi ini sangat bergantung pada kromosom yang dikode.

1. Crossover and Mutation Probability

Mengandung dua parameter dasar yang disebut Crossover Probability dan Mutation Probability.

• Crossover probability

Berhubungan dengan tingkat frekuensi dari crossover. Jika offspring adalah duplikat dari parent, maka tidak ada crossover. Jika crossover terjadi pada dua bagian dari crossover parent, maka akan membentuk offspring.

• Mutation probability

Dapat digambarkan sebagai peluang bagian kromosom yang dapat bermutasi. Ketika mutasi tersebut absen, maka offspring akan memproduksi tanpa perubahan segera sebelum crossover. Nilai probabilitas mutasi berbanding lurus dengan perubahan kromosom. Proses mutasi ini juga membantu GA untuk mencegah adanya kejatuhan pada local extremes. Frekuensi terjadinya mutasi harus rendah karena jika tidak, GA akan berubah menjadi pencarian acak.

Advantages:

• Tidak memerlukan informasi imitatif
• Metode lebih luas dan optimum dalam mencari solusi.
• Memiliki kemampuan yang selaras.
• Meningkatkan dan mengoptimalkan fungsi dengan memiliki masalah yang beragam .
• Berfokus dalam mencari solusi optimum.
• Menghasilkan jawaban dari masalah yang akan berkembang seiring berjalannya waktu.
• Baik ketika digunakan pada kasus dengan area ruang pencarian yang besar.

Application Implementation:

1. Network Routing Protocol

Dengan memilih rute jalur terpendek berdasarkan panjang kromosom yang berbanding lurus pada jaringan Genetic Algorithm (GA). Algorithm dijkstra secara efektif mengatasi hal yang sama pada masalah yang dikembangkan GA digunakan pada kasus yang melibatkan jaringan pada multi node.

1. Image Processing

Sebuah pencarian yang dapat dilakukan menggunakan Genetic Algorithm secara komprehensif dan kuat untuk mendapatkan hasil pencarian global yang optimal, optimisasi hasilnya tergantung pada kode kromosom, untuk image segmentation juga dapat ditingkatkan dengan pemilihan parameter yang optimal. Image enhancement berkaitan dengan kualitas gambar yang baik.

1. Data Mining

Dengan tujuan untuk menemukan nilai yang optimum pada pendekatan untuk meminimalkan supply chain cost dengan metode dalam rantai manajemen untuk mengendalikan rantai pasokan secara efektif.

1. Computer Games

Genetic Algorithm dalam permainan komputer terdapat di dalam aplikasi dengan tujuan untuk menciptakan game yang realistis bagi para pemain, dengan langkah-langkah untuk menciptakan teknik algoritma secara efektif agar para pemain tidak mengulangi kesalahan pada permainan sebelumnya.