Algoritma Genetika - Pendahuluan

Genetic Algorithm (GA) adalah teknik optimasi berbasis pencarian yang didasarkan pada prinsip Genetics and Natural Selection. Ini sering digunakan untuk menemukan solusi yang optimal atau mendekati optimal untuk masalah-masalah sulit yang jika tidak membutuhkan waktu seumur hidup untuk menyelesaikannya. Ini sering digunakan untuk memecahkan masalah pengoptimalan, penelitian, dan pembelajaran mesin.

Pengantar Pengoptimalan

Optimasi adalah proses dari making something better. Dalam proses apa pun, kami memiliki satu set input dan satu set output seperti yang ditunjukkan pada gambar berikut.

Pengoptimalan mengacu pada menemukan nilai masukan sedemikian rupa sehingga kita mendapatkan nilai keluaran "terbaik". Definisi "terbaik" bervariasi dari satu masalah ke masalah lainnya, tetapi dalam istilah matematika, ini mengacu pada memaksimalkan atau meminimalkan satu atau lebih fungsi objektif, dengan memvariasikan parameter masukan.

Himpunan semua solusi atau nilai yang memungkinkan yang dapat digunakan oleh input membuat ruang pencarian. Dalam ruang pencarian ini terdapat satu titik atau sekumpulan titik yang memberikan solusi optimal. Tujuan pengoptimalan adalah untuk menemukan titik atau kumpulan titik tersebut di ruang pencarian.

Apa itu Algoritma Genetika?

Alam selalu menjadi sumber inspirasi bagi seluruh umat manusia. Genetic Algorithms (GAs) adalah algoritma berbasis pencarian berdasarkan konsep seleksi alam dan genetika. GAs adalah bagian dari cabang komputasi yang jauh lebih besar yang dikenal sebagaiEvolutionary Computation.

GAs dikembangkan oleh John Holland dan mahasiswa serta koleganya di Universitas Michigan, terutama David E. Goldberg dan sejak itu telah dicoba pada berbagai masalah pengoptimalan dengan tingkat keberhasilan yang tinggi.

Di GAs, kami memiliki file pool or a population of possible solutionsuntuk masalah yang diberikan. Solusi-solusi ini kemudian mengalami rekombinasi dan mutasi (seperti pada genetika alami), menghasilkan anak-anak baru, dan prosesnya berulang selama beberapa generasi. Setiap individu (atau solusi kandidat) diberi nilai kesesuaian (berdasarkan nilai fungsi objektifnya) dan individu yang lebih bugar diberi kesempatan lebih tinggi untuk kawin dan menghasilkan individu yang lebih "bugar". Hal ini sejalan dengan Teori Darwinian tentang “Survival of the Fittest”.

Dengan cara ini kami terus "mengembangkan" individu atau solusi yang lebih baik dari generasi ke generasi, sampai kami mencapai kriteria penghentian.

Algoritma Genetika cukup diacak di alam, tetapi mereka bekerja jauh lebih baik daripada pencarian lokal acak (di mana kami hanya mencoba berbagai solusi acak, melacak yang terbaik sejauh ini), karena mereka mengeksploitasi informasi sejarah juga.

Keuntungan dari GAs

Gas memiliki berbagai keunggulan yang membuatnya menjadi sangat populer. Ini termasuk -

Tidak memerlukan informasi turunan (yang mungkin tidak tersedia untuk banyak masalah dunia nyata).
Lebih cepat dan lebih efisien dibandingkan dengan metode tradisional.
Memiliki kemampuan paralel yang sangat baik.
Mengoptimalkan fungsi kontinu dan diskrit serta masalah multi-tujuan.
Memberikan daftar solusi "baik" dan bukan hanya satu solusi.
Selalu mendapat jawaban atas masalah yang menjadi lebih baik dari waktu ke waktu.
Berguna ketika ruang pencarian sangat besar dan ada banyak parameter yang terlibat.

Batasan GAs

Seperti teknik apa pun, GA juga memiliki beberapa keterbatasan. Ini termasuk -

GA tidak cocok untuk semua masalah, terutama masalah yang sederhana dan yang informasi turunannya tersedia.
Nilai kebugaran dihitung berulang kali yang mungkin mahal secara komputasi untuk beberapa masalah.
Menjadi stokastik, tidak ada jaminan atas optimalitas atau kualitas solusi.
Jika tidak diterapkan dengan benar, GA mungkin tidak menyatu dengan solusi optimal.

GA - Motivasi

Algoritma Genetika memiliki kemampuan untuk memberikan solusi yang “cukup baik” “cukup cepat”. Hal ini membuat algoritme genetik menarik untuk digunakan dalam memecahkan masalah pengoptimalan. Alasan mengapa GAs dibutuhkan adalah sebagai berikut -

Memecahkan Masalah Sulit

Dalam ilmu komputer, ada sekumpulan besar masalah, yaitu NP-Hard. Maksud dasarnya adalah bahwa, bahkan sistem komputasi yang paling kuat pun membutuhkan waktu yang sangat lama (bahkan bertahun-tahun!) Untuk memecahkan masalah itu. Dalam skenario seperti itu, GA terbukti menjadi alat yang efisien untuk disediakanusable near-optimal solutions dalam waktu singkat.

Kegagalan Metode Berbasis Gradien

Metode tradisional berbasis kalkulus bekerja dengan memulai dari titik acak dan dengan bergerak ke arah gradien, hingga kita mencapai puncak bukit. Teknik ini efisien dan bekerja sangat baik untuk fungsi tujuan puncak tunggal seperti fungsi biaya dalam regresi linier. Tetapi, dalam kebanyakan situasi dunia nyata, kita memiliki masalah yang sangat kompleks yang disebut sebagai lanskap, yang terbuat dari banyak puncak dan banyak lembah, yang menyebabkan metode seperti itu gagal, karena metode tersebut menderita kecenderungan inheren untuk terjebak pada optimasi lokal. seperti yang ditunjukkan pada gambar berikut.

Mendapatkan Solusi yang Baik dengan Cepat

Beberapa masalah sulit seperti Travelling Salesperson Problem (TSP), memiliki aplikasi dunia nyata seperti pencarian jalur dan Desain VLSI. Sekarang bayangkan Anda menggunakan sistem Navigasi GPS, dan dibutuhkan beberapa menit (atau bahkan beberapa jam) untuk menghitung jalur "optimal" dari sumber ke tujuan. Penundaan dalam aplikasi dunia nyata seperti itu tidak dapat diterima dan oleh karena itu solusi yang "cukup baik", yang diberikan "cepat" adalah yang diperlukan.