Dalam bidang kecerdasan buatan, algoritma evolusi (EA) ialah subset daripada jumlah pengiraan populasi berdasarkan pengoptimuman metaheuristik. EA menggunakan mekanisme yang diilhamkan oleh pembangunan biologi seperti pembiakan, mutasi, penggabungan semula dan pemilihan. Penyelesaian calon dalam masalah algoritma pengoptimuman evolusi memainkan peranan individu dalam populasi. Dan juga fungsi kecergasan menentukan kualiti jawapan.
Algoritma evolusi selalunya menganggarkan penyelesaian kepada semua jenis masalah dengan baik. Kerana idealnya mereka tidak membuat sebarang andaian tentang landskap kecergasan asas. Kaedah yang digunakan untuk pemodelan evolusi dan algoritma genetik biasanya terhad kepada kajian proses mikroevolusi dan model perancangan berdasarkan peringkat selular. Dalam kebanyakan aplikasi EA sebenar, kerumitan pengiraan adalah faktor penghalang.
Sebenarnyaisu ini berkaitan dengan anggaran fungsi kecergasan. Pengiraan kecergasan adalah salah satu penyelesaian untuk mengatasi kesukaran ini. Walau bagaimanapun, EA yang kelihatan mudah boleh menyelesaikan masalah yang selalunya rumit. Oleh itu, tidak boleh ada hubungan langsung antara kerumitan urutan dan masalah. Butiran lanjut boleh didapati dalam buku "Algoritma Evolusi".
Pelaksanaan
Langkah pertama ialah mencipta populasi awal individu secara rawak.
Langkah kedua ialah menilai kesesuaian setiap individu dalam kumpulan ini (had masa, kesediaan yang mencukupi, dll.).
Langkah ketiga - ulangi langkah penjanaan semula berikut hingga selesai:
- Pilih orang yang paling sesuai untuk pembiakan (ibu bapa).
- Bawa individu baharu yang telah melepasi algoritma evolusi menggunakan silang silang dan mutasi untuk mendapatkan zuriat.
- Menilai kecergasan individu orang baharu.
- Ganti populasi yang paling kurang cergas dengan mereka.
Jenis
Algoritma Genetik ialah jujukan evolusi, jenis Penasihat Pakar yang paling popular. Penyelesaian kepada masalah dicari dalam bentuk rentetan nombor (secara tradisinya binari, walaupun representasi terbaik biasanya yang lebih mencerminkan masalah yang sedang diselesaikan) dengan menggunakan operator seperti penggabungan semula dan mutasi (kadang-kadang satu, dalam beberapa kes kedua-duanya.). Penasihat Pakar jenis ini sering digunakan dalam masalah pengoptimuman. Nama lain untuk ini ialah fetura (dari bahasa Latin untuk "kelahiran"):
- Pengaturcaraan genetik. Ia membentangkan penyelesaian sebagai kod komputer, dan kesesuaiannya ditentukan oleh keupayaan mereka untuk melaksanakan tugas pengiraan.
- Pengaturcaraan evolusi. Sama seperti algoritma genetik evolusi, tetapi strukturnya tetap dan parameter berangkanya boleh berubah.
- Memprogram ekspresi gen. Membangunkan aplikasi komputer, tetapi meneroka sistem genotip-fenotip, di mana projek dengan saiz berbeza dikodkan pada kromosom linear panjang tetap.
- Strategi. Bekerja dengan vektor nombor nyata sebagai perwakilan penyelesaian. Biasanya menggunakan algoritma kadar mutasi evolusi penyesuaian diri.
- Pembangunan berbeza. Berdasarkan perbezaan vektor dan oleh itu sesuai terutamanya untuk masalah pengoptimuman berangka.
- Neuroevolution. Sama seperti pengaturcaraan evolusi dan algoritma genetik. Tetapi yang terakhir adalah rangkaian saraf tiruan, menerangkan struktur dan berat sambungan. Pengekodan genom boleh secara langsung atau tidak langsung.
Perbandingan dengan proses biologi
Had kemungkinan banyak algoritma evolusi ialah kekurangan perbezaan yang jelas antara genotip dan fenotip. Secara semula jadi, telur yang disenyawakan mengalami proses kompleks yang dikenali sebagai embriogenesis untuk menjadi matang. Pengekodan tidak langsung ini dianggap menjadikan carian genetik lebih dipercayai (iaitu, kurang berkemungkinan menyebabkan mutasi maut) dan juga boleh meningkatkan keupayaan organisma untuk berkembang. Tidak langsung sedemikian (dengan kata lain,pengekodan generatif atau perkembangan) juga membenarkan evolusi mengeksploitasi keteraturan dalam persekitaran.
Kerja terkini dalam embriogenesis buatan atau sistem perkembangan berusaha untuk menangani isu ini. Apabila pengaturcaraan ekspresi gen, rantau genotip-fenotip berjaya diterokai, di mana yang pertama terdiri daripada kromosom multigen linear dengan panjang tetap, dan yang kedua daripada banyak pokok ekspresi atau program komputer pelbagai saiz dan bentuk.
Teknik berkaitan
Algoritma termasuk:
- Pengoptimuman koloni semut. Ia berdasarkan idea bahawa serangga mencari makanan dengan menyambung dengan feromon untuk membentuk laluan. Terutamanya sesuai untuk pengoptimuman gabungan dan masalah graf.
- Algoritma gelangsar akar. Pencipta diilhamkan oleh fungsi akar tumbuhan di alam semula jadi.
- Algoritma untuk koloni lebah tiruan. Berdasarkan tingkah laku lebah madu. Ia terutamanya dicadangkan untuk pengoptimuman berangka dan diperluaskan untuk menyelesaikan masalah kombinatorial, bersempadan, dan berbilang objektif. Algoritma lebah adalah berdasarkan tingkah laku mencari makan serangga. Ia telah digunakan dalam banyak aplikasi seperti penghalaan dan penjadualan.
- Pengoptimuman kawanan zarah - berdasarkan idea tingkah laku kumpulan haiwan. Dan juga sesuai terutamanya untuk tugasan proses berangka.
Kaedah metaeuristik popular lain
- Carian berburu. Kaedah berdasarkan penangkapan kumpulan haiwan tertentu, seperti serigala, contohnya, yangmengagihkan tugas mereka untuk mengepung mangsa. Setiap ahli algoritma evolusi berkaitan dengan yang lain dalam beberapa cara. Ini adalah benar terutamanya untuk pemimpin. Ini ialah kaedah pengoptimuman berterusan yang disesuaikan sebagai kaedah proses gabungan.
- Cari mengikut ukuran. Tidak seperti kaedah metaheuristik berasaskan alam semula jadi, algoritma proses penyesuaian tidak menggunakan metafora sebagai prinsip utamanya. Sebaliknya, ia menggunakan kaedah berorientasikan prestasi mudah berdasarkan mengemas kini parameter nisbah dimensi carian pada setiap lelaran. Algoritma Firefly diilhamkan oleh cara kelip-kelip menarik antara satu sama lain dengan cahaya berkelip mereka. Ini amat berguna untuk pengoptimuman pelbagai mod.
- Cari keharmonian. Berdasarkan idea tingkah laku pemuzik. Dalam kes ini, algoritma evolusi ialah cara untuk mengoptimumkan gabungan.
- Penyesuaian Gaussian. Berdasarkan teori maklumat. Digunakan untuk memaksimumkan prestasi dan ketersediaan purata. Contoh algoritma evolusi dalam situasi ini: entropi dalam termodinamik dan teori maklumat.
Memetik
Kaedah hibrid berdasarkan idea meme Richard Dawkins. Ia biasanya berbentuk algoritma berasaskan populasi digabungkan dengan prosedur pembelajaran individu yang mampu melakukan pemurnian tempatan. Menekankan penggunaan pengetahuan khusus masalah dan percubaan untuk mengatur carian terperinci dan global secara sinergistik.
Evolusialgoritma ialah pendekatan heuristik kepada masalah yang tidak boleh diselesaikan dengan mudah dalam masa polinomial, seperti masalah NP-hard klasik dan apa-apa lagi yang akan mengambil masa terlalu lama untuk diproses secara menyeluruh. Apabila digunakan secara bebas, ia biasanya digunakan untuk masalah gabungan. Walau bagaimanapun, algoritma genetik sering digunakan seiring dengan kaedah lain, bertindak sebagai cara cepat untuk mencari berbilang tempat permulaan yang optimum untuk digunakan.
Premis algoritma evolusi (dikenali sebagai penasihat) agak mudah memandangkan anda sudah biasa dengan proses pemilihan semula jadi. Ia mengandungi empat langkah utama:
- initialization;
- pilihan;
- pengendali genetik;
- end.
Setiap langkah ini secara kasarnya sepadan dengan aspek tertentu pemilihan semula jadi dan menyediakan cara mudah untuk memodulasi kategori algoritma tersebut. Ringkasnya, dalam EA, ahli yang paling cergas akan bertahan dan membiak, manakala ahli yang tidak sihat akan mati dan tidak menyumbang kepada kumpulan gen generasi akan datang.
Inisialisasi
Untuk memulakan algoritma, anda mesti membuat satu set penyelesaian terlebih dahulu. Populasi akan mengandungi bilangan arbitrari penyataan masalah yang mungkin, sering dirujuk sebagai ahli. Mereka sering dijana secara rawak (dalam kekangan tugas) atau, jika beberapa pengetahuan terdahulu diketahui, secara tentatif tertumpu pada perkara yang dianggap ideal. Adalah penting bahawa penduduk meliputi pelbagai penyelesaian,kerana ia pada asasnya adalah kumpulan gen. Oleh itu, jika seseorang ingin meneroka banyak kemungkinan berbeza dalam algoritma, seseorang harus berusaha untuk mempunyai banyak gen yang berbeza.
Pilihan
Apabila populasi telah dibuat, ahlinya kini mesti dinilai mengikut fungsi kecergasan. Fungsi kecergasan mengambil ciri-ciri ahli dan memberikan gambaran berangka tentang kesesuaian ahli itu. Menciptanya selalunya sangat sukar. Adalah penting untuk mencari sistem yang baik yang mewakili data dengan tepat. Ini sangat khusus untuk masalah ini. Kini anda perlu mengira kesesuaian semua peserta dan memilih beberapa ahli terbaik.
Fungsi objektif berbilang
EA juga boleh diperluaskan untuk menggunakan sistem ini. Ini agak merumitkan proses, kerana bukannya mengenal pasti satu titik optimum, satu set diperoleh apabila menggunakannya. Set penyelesaian dipanggil sempadan Pareto dan mengandungi unsur-unsur yang sama sesuai dalam erti kata bahawa tiada satu pun daripada mereka mendominasi yang lain.
Pengendali genetik
Langkah ini termasuk dua sub-langkah: silang dan mutasi. Selepas memilih istilah terbaik (biasanya 2 teratas, tetapi nombor ini boleh berbeza-beza), ia kini digunakan untuk mencipta generasi seterusnya dalam algoritma. Dengan menerapkan ciri-ciri ibu bapa yang dipilih, terciptalah anak-anak baru yang merupakan campuran kualiti. Ini selalunya sukar bergantung pada jenis data, tetapi biasanya dalam masalah gabunganadalah mungkin untuk mencampur dan mengeluarkan gabungan yang sah.
Kini adalah perlu untuk memperkenalkan bahan genetik baharu ke dalam generasi. Jika langkah penting ini tidak diambil, saintis akan sangat cepat terjebak dalam ekstrem tempatan dan tidak mendapat hasil yang optimum. Langkah ini adalah mutasi, dan ia dilakukan secara ringkas, mengubah sebahagian kecil kanak-kanak dengan cara yang kebanyakannya tidak mencerminkan subset gen ibu bapa. Mutasi biasanya berlaku secara probabilistik, memandangkan kebarangkalian kanak-kanak akan mendapatnya, serta keterukannya, ditentukan oleh pengedaran.
Penamatan
Pada akhirnya, algoritma mesti tamat. Ini biasanya berlaku dalam dua kes: sama ada ia telah mencapai beberapa masa pelaksanaan maksimum atau ia telah mencapai ambang prestasi. Pada ketika ini, penyelesaian akhir dipilih dan dikembalikan.
Contoh algoritma evolusi
Sekarang, untuk menggambarkan hasil proses ini, anda perlu melihat penasihat bertindak. Untuk melakukan ini, kita boleh ingat bagaimana beberapa generasi dinosaur belajar berjalan (secara beransur-ansur menguasai tanah), mengoptimumkan struktur badan mereka dan menggunakan kekuatan otot. Walaupun reptilia generasi awal tidak boleh berjalan, penasihat dapat mengubahnya dari semasa ke semasa melalui mutasi dan silang kepada bentuk yang boleh berjalan.
Algoritma ini menjadi semakin relevan dalam dunia moden, kerana penyelesaian berdasarkannya semakin digunakan dalam industri seperti pemasaran digital, kewangan danpenjagaan kesihatan.
Di manakah EA digunakan?
Secara lebih meluas, algoritma evolusi digunakan dalam pelbagai jenis aplikasi seperti pemprosesan imej, penghalaan kenderaan, pengoptimuman komunikasi mudah alih, pembangunan perisian dan juga latihan rangkaian saraf tiruan. Alat ini adalah nadi kepada kebanyakan apl dan tapak web yang digunakan oleh orang ramai setiap hari, termasuk Peta Google dan juga permainan seperti The Sims. Di samping itu, bidang perubatan menggunakan EA untuk membantu membuat keputusan klinikal mengenai rawatan kanser. Malah, algoritma evolusi sangat teguh sehingga boleh digunakan untuk menyelesaikan hampir semua masalah pengoptimuman.
Undang-undang Moore
Kelaziman EO yang semakin meningkat didorong oleh dua faktor utama: kuasa pengkomputeran yang tersedia dan pengumpulan set data yang besar. Yang pertama boleh diterangkan oleh Undang-undang Moore, yang pada asasnya menyatakan bahawa jumlah kuasa pengkomputeran dalam komputer berganda kira-kira setiap dua tahun. Ramalan ini telah berlaku selama beberapa dekad. Faktor kedua berkaitan dengan pergantungan yang semakin meningkat pada teknologi, yang membolehkan institusi mengumpul jumlah data yang sangat besar, yang membolehkan mereka menganalisis arah aliran dan mengoptimumkan produk.
Bagaimanakah algoritma evolusi boleh membantu pemasar?
Keadaan pasaran berubah dengan pantas dan sangat kompetitif. Ini telah memaksa pengurus pemasaran bersaing untuk membuat keputusan yang lebih baik. Peningkatan tersediakuasa pengkomputeran telah menyebabkan pekerja menggunakan EA untuk menyelesaikan masalah.
Pengoptimuman penukaran
Salah satu matlamat utama adalah untuk meningkatkan kadar pelawat ke tapak. Masalah ini berpunca daripada mengoptimumkan bilangan pengguna yang melakukan apa yang pemasar mahu. Sebagai contoh, jika syarikat menjual komputer riba, yang ideal adalah untuk meningkatkan bilangan pelawat tapak yang akhirnya membeli produk tersebut. Inilah intipati pengoptimuman kadar penukaran.
Salah satu aspek penting yang mengejutkan ialah pilihan antara muka pengguna. Jika reka bentuk web tidak begitu mesra pengguna, ada orang yang akhirnya tidak membeli produk untuk satu sebab atau yang lain. Matlamatnya ialah untuk mengurangkan bilangan pengguna yang akhirnya tidak menukar, yang meningkatkan keuntungan keseluruhan.
