Di bidang kecerdasan buatan, algoritma evolusioner (EA) adalah bagian dari perhitungan total populasi berdasarkan optimasi metaheuristik. EA menggunakan mekanisme yang terinspirasi oleh perkembangan biologis seperti reproduksi, mutasi, rekombinasi, dan seleksi. Solusi kandidat dalam masalah algoritma optimasi evolusioner memainkan peran individu dalam populasi. Dan juga fungsi fitness menentukan kualitas jawaban.
Algoritme evolusi sering kali memperkirakan solusi untuk semua jenis masalah dengan baik. Karena idealnya mereka tidak membuat asumsi tentang lanskap kebugaran yang mendasarinya. Metode yang digunakan untuk pemodelan evolusioner dan algoritme genetika biasanya terbatas pada studi proses mikroevolusi dan model perencanaan berdasarkan tahapan seluler. Di sebagian besar aplikasi EA nyata, kompleksitas komputasi merupakan faktor penghalang.
Sebenarnyamasalah ini terkait dengan estimasi fungsi fitness. Pendekatan kebugaran adalah salah satu solusi untuk mengatasi kesulitan ini. Namun, EA yang tampaknya sederhana dapat memecahkan masalah yang seringkali rumit. Oleh karena itu, tidak ada hubungan langsung antara kompleksitas urutan dan masalah. Lebih jelasnya dapat ditemukan di buku "Evolutionary Algorithms".
Pelaksanaan
Langkah pertama adalah membuat populasi awal individu secara acak.
Langkah kedua adalah menilai kesesuaian setiap individu dalam kelompok ini (batas waktu, kesiapan yang cukup, dll).
Langkah ketiga - ulangi langkah regenerasi berikut hingga selesai:
- Pilih orang yang paling cocok untuk pembibitan (orang tua).
- Membawa individu baru yang telah melewati algoritma evolusi menggunakan crossover dan mutasi untuk mendapatkan keturunan.
- Menilai kebugaran individu orang baru.
- Ganti populasi yang paling tidak sesuai dengan mereka.
Tipe
Genetic Algorithm adalah urutan evolusioner, jenis Expert Advisor yang paling populer. Solusi untuk masalah dicari dalam bentuk string angka (secara tradisional biner, meskipun representasi terbaik biasanya yang lebih mencerminkan masalah yang dipecahkan) dengan menerapkan operator seperti rekombinasi dan mutasi (kadang-kadang satu, dalam beberapa kasus keduanya). Expert Advisor jenis ini sering digunakan dalam masalah optimasi. Nama lain untuk ini adalah fetura (dari bahasa Latin untuk "kelahiran"):
- Pemrograman genetik. Ini menyajikan solusi sebagai kode komputer, dan kesesuaiannya ditentukan oleh kemampuannya untuk melakukan tugas komputasi.
- Pemrograman evolusioner. Mirip dengan algoritma genetika evolusioner, tetapi strukturnya tetap dan parameter numeriknya dapat berubah.
- Pemrograman ekspresi gen. Mengembangkan aplikasi komputer, tetapi mengeksplorasi sistem genotipe-fenotipe, di mana proyek dengan ukuran berbeda dikodekan pada kromosom linier dengan panjang tetap.
- Strategi. Bekerja dengan vektor bilangan real sebagai representasi dari solusi. Biasanya menggunakan algoritma tingkat mutasi evolusioner adaptif.
- Pengembangan diferensial. Berdasarkan perbedaan vektor dan karena itu terutama cocok untuk masalah optimasi numerik.
- Neuroevolution. Mirip dengan pemrograman evolusioner dan algoritma genetika. Tetapi yang terakhir adalah jaringan saraf tiruan, yang menggambarkan struktur dan bobot koneksi. Encoding genom bisa langsung atau tidak langsung.
Perbandingan dengan proses biologis
Keterbatasan yang mungkin dari banyak algoritma evolusioner adalah tidak adanya perbedaan yang jelas antara genotipe dan fenotipe. Di alam, telur yang dibuahi mengalami proses kompleks yang dikenal sebagai embriogenesis untuk menjadi matang. Pengkodean tidak langsung ini dianggap membuat pencarian genetik lebih dapat diandalkan (yaitu, kecil kemungkinannya menyebabkan mutasi yang fatal) dan juga dapat meningkatkan kemampuan organisme untuk berkembang. Tidak langsung seperti itu (dengan kata lain,penyandian generatif atau perkembangan) juga memungkinkan evolusi untuk mengeksploitasi keteraturan dalam lingkungan.
Pekerjaan terbaru dalam embriogenesis buatan atau sistem perkembangan berusaha untuk mengatasi masalah ini. Saat memprogram ekspresi gen, wilayah genotipe-fenotipe berhasil dieksplorasi, di mana yang pertama terdiri dari kromosom multigen linier dengan panjang tetap, dan yang kedua dari banyak pohon ekspresi atau program komputer dengan berbagai ukuran dan bentuk.
Teknik terkait
Algoritma meliputi:
- Optimasi koloni semut. Hal ini didasarkan pada gagasan bahwa serangga mencari makanan dengan menghubungkannya dengan feromon untuk membentuk jalur. Sangat cocok untuk optimasi kombinatorial dan masalah grafik.
- Algoritme penggeser akar. Penciptanya terinspirasi dari fungsi akar tumbuhan di alam.
- Algoritma untuk koloni lebah buatan. Berdasarkan perilaku lebah madu. Ini terutama diusulkan untuk optimasi numerik dan diperluas untuk memecahkan masalah kombinatorial, terbatas, dan multiobjektif. Algoritma lebah didasarkan pada perilaku mencari makan serangga. Ini telah diterapkan di banyak aplikasi seperti perutean dan penjadwalan.
- Optimasi kawanan partikel - berdasarkan ide perilaku kawanan hewan. Dan juga terutama cocok untuk tugas proses numerik.
Metode metaheuristik populer lainnya
- Berburu pencarian. Metode berdasarkan penangkapan kelompok hewan tertentu, seperti serigala, misalnya, yangmembagi tugas mereka untuk mengepung mangsanya. Masing-masing anggota algoritma evolusioner berhubungan dengan yang lain dalam beberapa cara. Hal ini terutama berlaku untuk pemimpin. Ini adalah metode optimasi berkelanjutan yang diadaptasi sebagai metode proses kombinatorial.
- Cari berdasarkan pengukuran. Tidak seperti metode metaheuristik berbasis alam, algoritma proses adaptif tidak menggunakan metafora sebagai prinsip utamanya. Sebaliknya, ia menggunakan metode berorientasi kinerja sederhana berdasarkan memperbarui parameter rasio dimensi pencarian di setiap iterasi. Algoritma Firefly terinspirasi oleh bagaimana kunang-kunang menarik satu sama lain dengan cahaya yang berkedip. Ini sangat berguna untuk optimasi multimodal.
- Mencari harmoni. Berdasarkan ide-ide perilaku musisi. Dalam hal ini, algoritma evolusioner adalah cara yang tepat untuk optimasi kombinatorial.
- adaptasi Gaussian. Berdasarkan teori informasi. Digunakan untuk memaksimalkan kinerja dan ketersediaan rata-rata. Contoh algoritma evolusioner dalam situasi ini: entropi dalam termodinamika dan teori informasi.
Memetic
Metode hibrida berdasarkan gagasan Richard Dawkins tentang meme. Biasanya mengambil bentuk algoritma berbasis populasi yang dikombinasikan dengan prosedur pembelajaran individu yang mampu melakukan perbaikan lokal. Menekankan penggunaan pengetahuan khusus masalah dan upaya untuk mengatur pencarian mendetail dan global dengan cara yang sinergis.
Evolusioneralgoritma adalah pendekatan heuristik untuk masalah yang tidak dapat dengan mudah diselesaikan dalam waktu polinomial, seperti masalah klasik NP-hard dan hal lain yang akan memakan waktu terlalu lama untuk diproses secara mendalam. Ketika digunakan secara independen, mereka biasanya digunakan untuk masalah kombinatorial. Namun, algoritme genetika sering digunakan bersama dengan metode lain, bertindak sebagai cara cepat untuk menemukan beberapa tempat awal yang optimal untuk digunakan.
Premis algoritme evolusi (dikenal sebagai penasehat) cukup sederhana mengingat Anda sudah familiar dengan proses seleksi alam. Ini berisi empat langkah utama:
- inisialisasi;
- pilihan;
- operator genetik;
- akhir.
Masing-masing langkah ini secara kasar sesuai dengan aspek tertentu dari seleksi alam dan menyediakan cara mudah untuk memodulasi kategori algoritma tersebut. Sederhananya, di EA, anggota yang paling cocok akan bertahan dan berkembang biak, sedangkan anggota yang tidak layak akan mati dan tidak berkontribusi pada kumpulan gen generasi berikutnya.
Inisialisasi
Untuk memulai algoritme, Anda harus membuat sekumpulan solusi terlebih dahulu. Populasi akan berisi sejumlah kemungkinan pernyataan masalah, sering disebut sebagai anggota. Mereka sering dihasilkan secara acak (dalam batasan tugas) atau, jika beberapa pengetahuan sebelumnya diketahui, sementara berpusat di sekitar apa yang dianggap ideal. Adalah penting bahwa populasi mencakup berbagai solusi,karena pada dasarnya adalah kumpulan gen. Oleh karena itu, jika seseorang ingin menjelajahi banyak kemungkinan yang berbeda dalam suatu algoritma, ia harus berusaha untuk memiliki banyak gen yang berbeda.
Pilihan
Setelah populasi dibuat, anggotanya sekarang harus dievaluasi sesuai dengan fungsi fitness. Fungsi fitness mengambil karakteristik anggota dan memberikan representasi numerik seberapa fit anggota tersebut. Membuatnya seringkali bisa sangat sulit. Penting untuk menemukan sistem yang baik yang secara akurat mewakili data. Ini sangat spesifik untuk masalah ini. Sekarang perlu menghitung kecocokan semua peserta dan memilih beberapa anggota terbaik.
Beberapa fungsi tujuan
EA juga dapat diperluas untuk menggunakan sistem ini. Ini agak memperumit proses, karena alih-alih mengidentifikasi satu titik optimal, satu set diperoleh saat menggunakannya. Himpunan solusi disebut perbatasan Pareto dan berisi elemen yang sama-sama cocok dalam arti bahwa tidak ada yang mendominasi yang lain.
Operator genetika
Langkah ini mencakup dua sub-langkah: crossover dan mutasi. Setelah memilih istilah terbaik (biasanya 2 teratas, tetapi angka ini dapat bervariasi), mereka sekarang digunakan untuk membuat generasi berikutnya dalam algoritme. Dengan menerapkan karakteristik orang tua terpilih, terciptalah anak-anak baru yang merupakan campuran kualitas. Ini seringkali sulit tergantung pada jenis datanya, tetapi biasanya dalam masalah kombinatorialsangat mungkin untuk mencampur dan menghasilkan kombinasi yang valid.
Sekarang perlu untuk memperkenalkan materi genetik baru ke dalam generasi. Jika langkah penting ini tidak diambil, ilmuwan akan sangat cepat terjebak dalam ekstrem lokal dan tidak mendapatkan hasil yang optimal. Langkah ini adalah mutasi, dan dilakukan dengan cukup sederhana, mengubah sebagian kecil anak sedemikian rupa sehingga mereka sebagian besar tidak mencerminkan himpunan bagian dari gen orang tua. Mutasi biasanya terjadi secara probabilistik, karena probabilitas seorang anak akan mendapatkannya, serta tingkat keparahannya, ditentukan oleh distribusi.
Pemutusan
Pada akhirnya, algoritma harus berakhir. Ini biasanya terjadi dalam dua kasus: apakah telah mencapai waktu eksekusi maksimum, atau telah mencapai ambang batas kinerja. Pada titik ini, solusi akhir dipilih dan dikembalikan.
Contoh algoritma evolusioner
Sekarang, untuk mengilustrasikan hasil dari proses ini, Anda perlu melihat penasihat beraksi. Untuk melakukan ini, kita dapat mengingat bagaimana beberapa generasi dinosaurus belajar berjalan (secara bertahap menguasai tanah), mengoptimalkan struktur tubuh mereka dan menerapkan kekuatan otot. Meskipun reptil generasi awal tidak bisa berjalan, penasihat mampu mengembangkan mereka dari waktu ke waktu melalui mutasi dan persilangan menjadi bentuk yang bisa berjalan.
Algoritme ini menjadi semakin relevan di dunia modern, karena solusi berdasarkan algoritma ini semakin banyak digunakan di industri seperti pemasaran digital, keuangan, dankesehatan.
Di mana EA digunakan?
Lebih luas lagi, algoritme evolusi digunakan dalam berbagai aplikasi seperti pemrosesan gambar, perutean kendaraan, pengoptimalan komunikasi seluler, pengembangan perangkat lunak, dan bahkan pelatihan jaringan saraf tiruan. Alat-alat ini adalah inti dari banyak aplikasi dan situs web yang digunakan orang setiap hari, termasuk Google Maps dan bahkan game seperti The Sims. Selain itu, bidang medis menggunakan EA untuk membantu membuat keputusan klinis mengenai pengobatan kanker. Faktanya, algoritma evolusioner sangat kuat sehingga dapat digunakan untuk menyelesaikan hampir semua masalah optimasi.
Hukum Moore
Meningkatnya prevalensi EO didorong oleh dua faktor utama: daya komputasi yang tersedia dan akumulasi kumpulan data yang besar. Yang pertama dapat dijelaskan oleh Hukum Moore, yang pada dasarnya menyatakan bahwa jumlah daya komputasi di komputer berlipat ganda kira-kira setiap dua tahun. Prediksi ini telah berlangsung selama beberapa dekade. Faktor kedua berkaitan dengan meningkatnya ketergantungan pada teknologi, yang memungkinkan institusi untuk mengumpulkan data dalam jumlah yang sangat besar, yang memungkinkan mereka untuk menganalisis tren dan mengoptimalkan produk.
Bagaimana algoritma evolusioner dapat membantu pemasar?
Kondisi pasar berubah dengan cepat dan sangat kompetitif. Hal ini telah memaksa manajer pemasaran untuk bersaing untuk pengambilan keputusan yang lebih baik. Peningkatan tersediadaya komputasi telah mendorong pekerja untuk menggunakan EA untuk pemecahan masalah.
Optimasi konversi
Salah satu tujuan utama adalah untuk meningkatkan tingkat pengunjung ke situs. Masalah ini bermuara pada pengoptimalan jumlah pengguna yang melakukan apa yang diinginkan pemasar. Misalnya, jika sebuah perusahaan menjual laptop, idealnya adalah meningkatkan jumlah pengunjung situs yang akhirnya membeli produk tersebut. Inilah inti dari optimasi tingkat konversi.
Salah satu aspek yang sangat penting adalah pilihan antarmuka pengguna. Jika desain web tidak terlalu ramah pengguna, ada orang yang akhirnya tidak membeli produk karena satu dan lain alasan. Tujuannya kemudian adalah untuk mengurangi jumlah pengguna yang akhirnya tidak melakukan konversi, yang meningkatkan keuntungan keseluruhan.
