Perhitungan evolusioner
Dalam ilmu komputer, komputasi evolusioner adalah sebuah keluarga algoritme untuk optimasi global yang terinspirasi oleh evolusi biologis, dan subbidang kecerdasan buatan dan komputasi lunak yang mempelajari algoritme ini. Dalam istilah teknis, mereka adalah keluarga pemecah masalah trial and error berbasis populasi dengan karakter optimasi metaheuristik atau stokastik.
Dalam komputasi evolusioner, sekumpulan kandidat solusi awal dihasilkan dan diperbarui secara berulang. Setiap generasi baru dihasilkan dengan menghapus solusi yang kurang diinginkan secara stokastik, dan memperkenalkan perubahan acak kecil serta, tergantung pada metodenya, mencampurkan informasi orang tua. Dalam terminologi biologi, sebuah populasi solusi akan mengalami seleksi alam (atau seleksi buatan), mutasi, dan kemungkinan rekombinasi. Hasilnya, populasi akan berevolusi secara bertahap untuk meningkatkan kebugaran, dalam hal ini fungsi kebugaran yang dipilih dari algoritma.
Teknik komputasi evolusioner dapat menghasilkan solusi yang sangat optimal dalam berbagai pengaturan masalah, sehingga membuatnya populer dalam ilmu komputer. Banyak varian dan ekstensi yang tersedia, yang cocok untuk kelompok masalah dan struktur data yang lebih spesifik. Komputasi evolusioner juga terkadang digunakan dalam biologi evolusioner sebagai prosedur eksperimental in silico untuk mempelajari aspek-aspek umum dari proses evolusi secara umum.
Sejarah
Konsep meniru proses evolusi untuk memecahkan masalah berasal dari sebelum munculnya komputer, seperti ketika Alan Turing mengusulkan metode pencarian genetik pada tahun 1948. Mesin-u tipe-B Turing menyerupai jaringan saraf primitif, dan hubungan antara neuron dipelajari melalui semacam algoritma genetik. Mesin-u tipe P-nya menyerupai metode pembelajaran penguatan, di mana sinyal kesenangan dan rasa sakit mengarahkan mesin untuk mempelajari perilaku tertentu. Namun, makalah Turing tidak dipublikasikan hingga tahun 1968, dan ia meninggal pada tahun 1954, sehingga karya awal ini tidak banyak berpengaruh pada bidang komputasi evolusioner yang kemudian berkembang.
Komputasi evolusioner sebagai sebuah bidang dimulai dengan sungguh-sungguh pada tahun 1950-an dan 1960-an. Ada beberapa upaya independen untuk menggunakan proses evolusi dalam komputasi pada masa ini, yang berkembang secara terpisah selama kurang lebih 15 tahun. Tiga cabang muncul di tempat yang berbeda untuk mencapai tujuan ini: strategi evolusi, pemrograman evolusioner, dan algoritma genetika. Cabang keempat, pemrograman genetik, akhirnya muncul pada awal tahun 1990-an. Pendekatan-pendekatan ini berbeda dalam metode seleksi, mutasi yang diizinkan, dan representasi data genetik. Pada tahun 1990-an, perbedaan antara cabang-cabang historis tersebut mulai kabur, dan istilah 'komputasi evolusioner' diciptakan pada tahun 1991 untuk menunjukkan sebuah bidang yang mencakup keempat paradigma tersebut.
Pada tahun 1962, Lawrence J. Fogel memprakarsai penelitian Pemrograman Evolusioner di Amerika Serikat, yang dianggap sebagai upaya kecerdasan buatan. Dalam sistem ini, mesin keadaan berhingga digunakan untuk memecahkan masalah prediksi: mesin ini akan dimutasi (menambah atau menghapus keadaan, atau mengubah aturan transisi keadaan), dan yang terbaik dari mesin yang bermutasi ini akan berevolusi lebih lanjut di generasi mendatang. Mesin finite state terakhir dapat digunakan untuk menghasilkan prediksi saat dibutuhkan. Metode pemrograman evolusioner berhasil diterapkan pada masalah prediksi, identifikasi sistem, dan kontrol otomatis. Metode ini akhirnya diperluas untuk menangani data deret waktu dan memodelkan evolusi strategi permainan.
Pada tahun 1964, Ingo Rechenberg dan Hans-Paul Schwefel memperkenalkan paradigma strategi evolusi di Jerman. Karena teknik penurunan gradien tradisional menghasilkan hasil yang mungkin terjebak pada minima lokal, Rechenberg dan Schwefel mengusulkan agar mutasi acak (yang diterapkan pada semua parameter beberapa vektor solusi) dapat digunakan untuk menghindari minima ini. Solusi anak dihasilkan dari solusi induk, dan solusi yang lebih sukses dari keduanya disimpan untuk generasi selanjutnya. Teknik ini pertama kali digunakan oleh keduanya untuk menyelesaikan masalah optimasi dalam dinamika fluida. Awalnya, teknik optimasi ini dilakukan tanpa komputer, melainkan mengandalkan dadu untuk menentukan mutasi acak. Pada tahun 1965, perhitungan dilakukan sepenuhnya oleh mesin.
John Henry Holland memperkenalkan algoritma genetika pada tahun 1960-an, dan dikembangkan lebih lanjut di Universitas Michigan pada tahun 1970-an. Sementara pendekatan lain difokuskan untuk memecahkan masalah, Holland terutama bertujuan untuk menggunakan algoritma genetika untuk mempelajari adaptasi dan menentukan bagaimana adaptasi tersebut dapat disimulasikan. Populasi kromosom, yang direpresentasikan sebagai string bit, ditransformasikan oleh proses seleksi buatan, memilih bit 'alel' tertentu dalam string bit. Di antara metode mutasi lainnya, interaksi antara kromosom digunakan untuk mensimulasikan rekombinasi DNA antara organisme yang berbeda. Sementara metode sebelumnya hanya melacak satu organisme optimal pada satu waktu (membuat anak-anak bersaing dengan orang tua), algoritma genetika Holland melacak populasi besar (membuat banyak organisme bersaing setiap generasi).
Pada tahun 1990-an, sebuah pendekatan baru untuk komputasi evolusioner yang kemudian disebut pemrograman genetik muncul, yang antara lain dianjurkan oleh John Koza. Dalam kelas algoritme ini, subjek evolusi itu sendiri adalah program yang ditulis dalam bahasa pemrograman tingkat tinggi (telah ada beberapa upaya sebelumnya pada awal tahun 1958 untuk menggunakan kode mesin, namun tidak banyak berhasil). Bagi Koza, program-program tersebut adalah ekspresi Lisp S, yang dapat dianggap sebagai pohon sub-ekspresi. Representasi ini memungkinkan program untuk menukar sub-pohon, yang mewakili semacam pencampuran genetik. Program dinilai berdasarkan seberapa baik mereka menyelesaikan tugas tertentu, dan nilai tersebut digunakan untuk seleksi buatan. Induksi urutan, pengenalan pola, dan perencanaan merupakan aplikasi yang sukses dari paradigma pemrograman genetik.
Banyak tokoh lain yang berperan dalam sejarah komputasi evolusioner, meskipun karya mereka tidak selalu masuk ke dalam salah satu cabang sejarah utama bidang ini. Simulasi komputasi evolusi yang paling awal menggunakan algoritma evolusi dan teknik kehidupan buatan dilakukan oleh Nils Aall Barricelli pada tahun 1953, dengan hasil pertama yang dipublikasikan pada tahun 1954. Pelopor lain pada tahun 1950-an adalah Alex Fraser, yang mempublikasikan serangkaian makalah tentang simulasi seleksi buatan. Seiring dengan meningkatnya minat akademis, peningkatan dramatis dalam kekuatan komputer memungkinkan aplikasi praktis, termasuk evolusi otomatis program komputer. Algoritme evolusioner sekarang digunakan untuk memecahkan masalah multi-dimensi secara lebih efisien daripada perangkat lunak yang dihasilkan oleh perancang manusia, dan juga untuk mengoptimalkan desain sistem.
Teknik
Algoritme evolusioner
Algoritma evolusioner merupakan bagian dari komputasi evolusioner yang umumnya hanya melibatkan teknik-teknik yang mengimplementasikan mekanisme yang terinspirasi dari evolusi biologis seperti reproduksi, mutasi, rekombinasi, seleksi alam, dan bertahan hidup yang terkuat. Kandidat solusi untuk masalah optimasi berperan sebagai individu dalam sebuah populasi, dan fungsi biaya menentukan lingkungan tempat solusi "hidup" (lihat juga fungsi kebugaran). Evolusi populasi kemudian terjadi setelah penerapan operator di atas secara berulang-ulang.
Dalam proses ini, ada dua kekuatan utama yang menjadi dasar sistem evolusi: Rekombinasi (misalnya persilangan) dan mutasi menciptakan keragaman yang diperlukan dan dengan demikian memfasilitasi kebaruan, sementara seleksi bertindak sebagai kekuatan yang meningkatkan kualitas.
Banyak aspek dari proses evolusi yang bersifat stokastik. Informasi yang berubah karena rekombinasi dan mutasi dipilih secara acak. Di sisi lain, operator seleksi dapat bersifat deterministik atau stokastik. Dalam kasus terakhir, individu dengan kebugaran yang lebih tinggi memiliki peluang lebih tinggi untuk dipilih daripada individu dengan kebugaran yang lebih rendah, tetapi biasanya bahkan individu yang lemah pun memiliki peluang untuk menjadi orang tua atau bertahan hidup.
Algoritme evolusi dan biologi
Algoritma genetika memberikan metode untuk memodelkan sistem biologi dan biologi sistem yang terkait dengan teori sistem dinamik, karena digunakan untuk memprediksi keadaan sistem di masa depan. Ini hanyalah cara yang jelas (tetapi mungkin menyesatkan) untuk menarik perhatian pada karakter perkembangan biologi yang teratur, terkendali dengan baik, dan sangat terstruktur.
Namun, penggunaan algoritma dan informatika, khususnya teori komputasi, di luar analogi dengan sistem dinamis, juga relevan untuk memahami evolusi itu sendiri.
Pandangan ini memiliki manfaat untuk mengakui bahwa tidak ada kontrol pusat perkembangan; organisme berkembang sebagai hasil dari interaksi lokal di dalam dan di antara sel-sel. Gagasan yang paling menjanjikan tentang paralelisme program-pengembangan tampaknya adalah gagasan yang menunjuk pada analogi yang tampaknya dekat antara proses di dalam sel, dan operasi tingkat rendah komputer modern. Dengan demikian, sistem biologis seperti mesin komputasi yang memproses informasi input untuk menghitung keadaan berikutnya, sehingga sistem biologis lebih dekat dengan komputasi daripada sistem dinamik klasik.
Lebih jauh lagi, mengikuti konsep dari teori komputasi, proses mikro dalam organisme biologis pada dasarnya tidak lengkap dan tidak dapat diputuskan (kelengkapan (logika)), menyiratkan bahwa "ada lebih dari sekadar metafora kasar di balik analogi antara sel dan komputer."
Analogi komputasi juga meluas ke hubungan antara sistem pewarisan dan struktur biologis, yang sering dianggap mengungkap salah satu masalah paling mendesak dalam menjelaskan asal-usul kehidupan.
Automata evolusioner, sebuah generalisasi dari mesin Turing Evolusioner, telah diperkenalkan untuk menyelidiki sifat-sifat yang lebih tepat dari komputasi biologis dan evolusioner. Secara khusus, mereka memungkinkan untuk mendapatkan hasil baru tentang ekspresi komputasi evolusioner. Hal ini menegaskan hasil awal tentang ketidakpastian evolusi alami dan algoritma serta proses evolusi. Evolutionary finite automata, subkelas paling sederhana dari Evolutionary automata yang bekerja dalam mode terminal dapat menerima bahasa arbitrer melalui alfabet yang diberikan, termasuk bahasa yang dapat dihitung secara non-rekursif (misalnya, bahasa diagonalisasi) dan bahasa yang dapat dihitung secara rekursif tetapi tidak rekursif (misalnya, bahasa mesin Turing universal).
Disadur dari: en.wikipedia.org