Jaringan Syaraf Tiruan - Algoritma Genetika
Alam selalu menjadi sumber inspirasi bagi seluruh umat manusia. Genetic Algorithms (GAs) adalah algoritma berbasis pencarian yang didasarkan pada 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 kolega di Universitas Michigan, terutama David E. Goldberg dan sejak itu telah dicoba pada berbagai masalah pengoptimalan dengan tingkat keberhasilan yang tinggi.
Dalam GAs, kami memiliki kumpulan atau populasi solusi yang mungkin untuk 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, namun mereka bekerja jauh lebih baik daripada pencarian lokal acak (di mana kita 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 mendapatkan 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 lainnya, GA juga memiliki beberapa keterbatasan. Ini termasuk -
GA tidak cocok untuk semua masalah, terutama masalah yang sederhana dan tersedia informasi turunannya.
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 Gas 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 menyelesaikan 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. Namun, dalam kebanyakan situasi dunia nyata, kami memiliki masalah yang sangat kompleks yang disebut sebagai lanskap, yang terbuat dari banyak puncak dan banyak lembah, yang menyebabkan metode tersebut gagal, karena metode tersebut memiliki kecenderungan inheren untuk terjebak pada optimalisasi lokal seperti yang ditunjukkan pada gambar berikut.
Mendapatkan Solusi yang Baik dengan Cepat
Beberapa masalah sulit seperti Travelling Salesman Problem (TSP), memiliki aplikasi dunia nyata seperti pencarian jalan 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.
Bagaimana Menggunakan GA untuk Masalah Pengoptimalan?
Kita sudah tahu bahwa optimasi adalah tindakan membuat sesuatu seperti desain, situasi, sumber daya, dan sistem seefektif mungkin. Proses optimasi ditunjukkan pada diagram berikut.
Tahapan Mekanisme GA untuk Proses Optimasi
Berikut tahapan mekanisme GA saat digunakan untuk optimasi masalah.
Hasilkan populasi awal secara acak.
Pilih solusi awal dengan nilai kebugaran terbaik.
Gabungkan kembali solusi yang dipilih menggunakan operator mutasi dan saling silang.
Masukkan keturunan ke dalam populasi.
Sekarang jika kondisi stop terpenuhi, maka kembalikan solusi dengan nilai fitness terbaiknya. Lain, lanjutkan ke langkah 2.