Evolutionary Computation (Komputasi Evolusi)

Komputasi Evolusi



Komputasi evolusi (Evolutionary Computation /EC) mengabstraksi prinsip-prinsip evolusi ke dalam algoritma yang dapat digunakan untuk mencari solusi optimal dalam suatu masalah. Di sebuah algoritma pencarian, sejumlah solusi yang mungkin untuk masalah yang tersedia dan tugas dari algoritma tersebut adalah untuk menemukan solusi terbaik dalam jumlah waktu yang tetap. 


Dalam sejarah komputasi evolusi terdapat empat paradigma sejarah yang berfungsi sebagai pondasi dari bidang ini yaitu :
1, Algoritma genetika (Holland, 1975)
2. Pemrograman genetika (Koza, 1992, 1994)
3. Strategi evolusi (Recheuberg, 1973)
4. Pemrograman evolusi (Forgel et al, 1966)

2.1 Algoritma Genetika

Teknik yang paling populer dalam penelitian komputasi evolusi adalah algoritma genetika.  Dalam algoritma genetika tradisional, representasi yang digunakan adalah sebuah string dengan panjang yang tetap. Setiap posisi dalam string diasumsikan mewakili suatu fitur dari sebuah individu, dan nilai yang disimpan di posisi itu mewakili bagaimana fitur tersebut dinyatakan dalam sebuah solusi. 

Operator reproduksi yang utama yang digunakan adalah crossover bit-string, dimana dua buah string digunakan sebagai induk dan individu baru dibentuk dengan menukar sub-urutan dia antara kedua string tersebut. Operator populer lainnya adalah bit-flipping mutation, dimana satu bit dalam sebuah string dibalik untuk membentuk string keturunan baru.

Semua operator juga dibatasi untuk memanipulasi string dengan cara yang konsisten dengan interpretasi struktural gen. Untuk contoh, terdapat dua gen di lokasi yang sama pada dua string yang dapat ditukar antar induk, tetapi tidak digabungkan berdasarkan nilai-nilai mereka.

 2.2 Pemrograman Genetika

Dalam standar program genetika, representasi yang digunakan adalah pohon fungsi dan nilai yang berikuran variabel, Tiap daun dalam pohon merupakan label dari sebuah set nilai label yang tersedia. Tiap cabang internal dalam pohon tersebut merupakan label dari set fungsi label yang tersedia. Keseluruhan pohon berkaitan dengan satu fungsi yang dapat dievaluasi. Umumnya, pohon dievaluasi dengan kedalaman paling kiri-cara pertama. Sebuah daun dievaluasi sebagai nilai yang sesuai. Fungsi dievaluasi menggunakan argumen yang merupakan hasil dari evaluasi anak-anaknya. 

 Operator yang paling umum digunakan adalah subtree crossover, dimana keseluruhan subtree ditukar antar induk. Prinsip penutupan (Closure Principle) yang dikemukan oleh Koza memungkinkan subtree apa pun untuk dapat dipertimbangkan secara struktural setara dengan subtree yang lain, dan memastikan bahwa operator seperti persilangan sub-tree akan selalu menghasilkan keturunan yang sah.




2.3 Strategi Evolusi

 Dalam strategi evolusi, representasi yang digunakan adalah vektor dengan panjang yang ditentukan dan memiliki nilai riil. Seperti halnya string bit dari algoritma genetika, setiap posisi dalam vektor seusia dengan fitur individu. Namun, fitur dipertimbangkan menjadi perilaku daripada struktural.

Operator reproduksi utama dalam strategi evolusi adalah mutasi Gaussian, dimana nilai acak dari distribusi Gaussian ditambahkan ke setiap elemen dari suatu vektor individu untuk membuat keturunan baru. Operator lain yang digunakan adalah rekombinasi menengah, dimana vektor dari dua induk diratakan bersama, elemen demi elemen, untuk membentuk suatu keturunan baru.

Umumnya di strategi evolusi, N induk dipilih seragam secara acak dan tidak didasarkan pada kebugaran, lebih dari N keturunan yang dihasilkan melalui penggunaan rekombinasi, dan kemudian N yang selamat dipilih secara deterministik. Individu yang bertahan hidup dipilih baik dari keturunan N yang terbaik.



2.4 Pemrograman Evolusi

 Pemrograman evolusi mengambil sebuah gagasan untuk mewakili fenotipik individu sekutu sebagai meisn yang mampu untuk bertindak kepada ransangan dari luar dan mengenmbangkan operator untuk melakukan perubahan struktural dan perilaku dari waktu ke waktu. Ide ini diterapkan pada berbagai masalah termasuk masalah prediksi, pembelajaran dan pembelajaran mesin.

 Representasi yang digunakan dalam pemrograman evolusi biasanya dirancang untuk domain masalah. Salah satu representasi yang biasa digunakan adalah vektor yang memiliki nilai. Metode pemilihan yang umum adalah memilih semua individu dalam populasi menjadi induk N, untuk mutasi setiap orang tua untuk membentuk anak N, dan untuk pemilihan secara probabilitas, berdasarkan kebugaran, N yang selamat dari total 2N individu akan membentu generasi selanjutnya.

 3. Fitur Komputasi Evolusi 

Terdapat tiga fitur fundamental dari evolusi biologis :

 1. Gen partikular dan genetika populasi;
2. Kode genetik adaptif;
3. Dikotomi genotipe dan fenotipe.

 Setiap fenomena dipilih untuk mewakili titik-titik yang berbeda dalam spektrum kemungkinan hubungan antara komputasi dan teori evolusi biologis. Hal pertama yang dilakukan adalah mencari tahu apakah komputasi evolosi saat ini telah sepenuhnya mentransfer dasar-dasar dari evolusi biologis. Yang kedua, menunjukkan bagaimana para teoritis dari evolusi biologis dan komputasi evolusi dapat berkontribusi pada pemahaman umum mengenai abstraksi evolusi. Yang ketiga, adalah menggambarkan pertanyaan tentang evolusi biologis pada komputasi evolusi yang tampaknya lebih cocok untuk diatasi dibanding evolusi biologis.

 3.1 Gen Partikular dan Genetika Populasi

 Genetika populasi klasik dan sistem komputasi evolusi eksperimental telah berfokus pada apakah dan bagaimana konteks ini mempromosikan tekanan selektif untuk keterkaitan gen ke "kompleks gen yang saling beradaptasi". Pengamatan yang lebih sederhana adalah bahwa novel, potensi alel yang menguntungkan untuk efek epistatik negatif adalah integral untuk keberhasilan mikro-evolusi. Probabilitas akan mendukung fiksasi alel yang merupakan  "pemain tim" yang baik, untuk mempercepat proses adaptif. Ini mempertahankan pewarisan non-campuran dan bahkan pergeseran genetik, tetapi tidak jelas apakah metode tersebut menggabungkan filter implisit genetika populasi untuk alel "primadona" yang hanya menawarkan keuntungan adaptif mereka ketika konteks genetik mereka biasa saja.

 3.2 Buku Kode Adaptif

 Biologi molekular Central Dogma, menghubungkan gen ke fenotipe dengan menyatakan bahwa DNA dintranskripsikan menjadi RNA, yang kemudian diterjemahkan menjadi protein. Istilah transkripsi dan terjemahannya cukup jelas : RNA adalah bahan kimia yang bersaudara dengan DNA, keduanya adalah polimer yang dibentuk dari alfabet empat huruf kimia (nukleotida), dan transkripsi tidak lebih dari sebuah proses dari melengkapi DNA, huruf demi huruf masuk ke dalam RNA. 

 3.3 Dikotomi Genotip/Fenotip
Teori terkini tentang asal-usul dikotomi ini berfokus pada penemuan bahwa RNA dapat bertindak baik sebagai media penyimpanan genetik, dan sebagai molekul katalitik. Dalam inti metabolisme yang paling terkonservasi, semua organisme yang diketahui ditemukan menggunakan molekul RNA dalam peran yang biasanya kita berikan pada protein.


Namun, jawaban untuk bagaimana dikotomi berevolusi sebagian besar menutupi pertanyaan mengapa RNA mengembangkan representasi fenotipe yang berbeda secara kualitatif. Jawaban biologis yang tepat adalah bahwa ukuran alfabet asam amino yang lebih besar melepaskan keragaman katalitik yang lebih besar untuk replikator, dengan peningkatan kecanggihan metabolisme terkait yang mengoptimalkan replikasi diri. 

 Mengingat keberadaan genotip asam nukleat dan fenotip protein nukleat dalam kehidupan, biologi sulit sekali menilai signifikansi evolusi “bahasa representasional” ini. Jelas koloni komputasi evolusi jauh di depan biologi dalam memformalkan konsep. bahasa representasional, dan mengeksplorasi apa artinya. Biologi akan meningkat ketika programmer evolusioner menempatkan sistem kita dalam temuan mereka, menggambarkan potensi inspirasi biologis dari komputasi evolusi.

 4. Keunggulan dari Komputasi Evolusi 

Komputasi evolusioner, menggambarkan bidang investigasi yang menyangkut semua algoritma evolusi dan memberikan keuntungan praktis untuk beberapa masalah optimasi. Keuntungannya termasuk pendekatan sederhana, responsnya yang kuat terhadap keadaan yang berubah, fleksibilitas, dan sebagainya. 

4.1 Konseptual Sederhana
Keuntungan utama dari perhitungan evolusi adalah bahwa hal itu sederhana secara konsep. Gambar dibawah menunjukkan diagram alur dari algoritma evolusioner yang diterapkan untuk optimasi fungsi. Algoritma terdiri dari inisialisasi, variasi berulang, dan seleksi berdasarkan indeks kinerja. Secara khusus, tidak ada informasi gradien yang perlu disajikan ke algoritma. Lebih dari iterasi variasi acak dan seleksi populasi dapat dibuat untuk bertemu dengan solusi optimal. Efektivitas suatu algoritma evolusi tergantung pada variasi dan operator seleksi sebagaimana diterapkan pada representasi dan inisialisasi yang dipilih.

4.2 Penerapan yang Lebih Luas

Algoritma evolusioner dapat diterapkan pada masalah yang dapat dirumuskan sebagai masalah optimasi fungsi. Untuk menyelesaikan masalah ini, diperlukan struktur data untuk mewakili solusi, untuk mengevaluasi solusi baru dari solusi lama. Representasi dapat dipilih oleh manusia berdasarkan intuisinya. Representasi harus memungkinkan operator variasi yang memelihara hubungan perilaku antara induk dan anak. Perubahan kecil dalam struktur induk akan menyebabkan perubahan kecil pada keturunan, dan perubahan besar yang sama pada induk akan menyebabkan perubahan drastis pada keturunan. Dalam hal ini, algoritma evolusi dikembangkan, sehingga dapat diatur dengan cara adaptif sendiri. Ini membuat perhitungan evolusi diterapkan pada cakupan luas pada area, masalah kombinasi diskrit, masalah campuran bilangan bulat, dan sebagainya.

4.3 Hibridisasi dengan Metode Lain

Algoritma evolusi dapat dikombinasikan dengan teknik optimasi yang lebih tradisional. Ini sesederhana penggunaan minimalisasi konjugat-gradien yang digunakan setelah pencarian primer dengan algoritma evolusi. Ini juga dapat melibatkan aplikasi simultan dari algoritma seperti penggunaan pencarian evolusi untuk struktur model yang digabungkan dengan pencarian gradien untuk nilai parameter. Selanjutnya, perhitungan evolusioner dapat digunakan untuk mengoptimalkan kinerja jaringan saraf, sistem fuzzy, sistem produksi, sistem nirkabel, dan struktur program lainnya.

4.4 Sifat Paralel

Evolusi adalah proses yang sangat paralel. Ketika komputer pengolah yang terdistribusi menjadi lebih populer tersedia, akan ada potensi yang meningkat untuk menerapkan komputasi evolusioner untuk masalah yang lebih kompleks. Umumnya solusi individu dievaluasi secara independen dari evaluasi yang ditugaskan untuk solusi yang bersaing. Evaluasi setiap solusi dapat ditangani secara paralel dan pemilihan hanya memerlukan beberapa operasi serial. Akibatnya, waktu berjalan yang diperlukan untuk suatu aplikasi mungkin berbanding terbalik dengan jumlah prosesor. Selain itu, mesin komputasi saat ini memberikan kecepatan komputasi yang cukup untuk menghasilkan solusi saat masalah sulit dalam waktu yang wajar.

4.5 Perubahan Kuat ke Dinamis

Komputasi evolusioner tidak dapat digunakan untuk mengadaptasi solusi pada keadaan yang berubah. Populasi yang dihasilkan dari solusi yang dikembangkan memberikan dasar untuk perbaikan lebih lanjut dan dalam banyak kasus, tidak perlu menginisialisasi ulang populasi secara acak. Metode adaptasi dalam menghadapi lingkungan yang dinamis adalah kuncinya. Sebagai contoh, Wielaud (1990) menerapkan algoritma genetika untuk mengembangkan jaringan saraf berulang untuk mengontrol sistem poles-gerobak yang terdiri dari dua kutub. Pada gambar dibawah, tujuannya adalah untuk mempertahankan kereta di antara batas-batas lintasan sementara keduanya tidak membiarkan salah satu kutub melebihi sudut maksimum yang ditentukan. Kontrol yang tersedia di sini adalah gaya, yang digunakan untuk menarik dan mendorong gerobak. Kesulitan di sini adalah kesamaan panjang tiang.


4.6 Menyelesaikan Masalah yang Tidak Terpecahkan

Keuntungan dari algoritma evolusi mencakup kemampuannya untuk mengatasi masalah yang tidak ada keahlian manusianya. Meskipun keahlian manusia harus digunakan ketika dibutuhkan dan tersedia, sering terbukti kurang memadai untuk rutinitas pemecahan masalah otomatis. Kecerdasan artifisial dapat diterapkan pada beberapa masalah sulit yang membutuhkan kecepatan komputasi tinggi, tetapi mereka tidak dapat bersaing dengan kecerdasan manusia. 
5. Penggunaan dari Komputasi Evolusi 

Aplikasi perhitungan evolusi meliputi bidang-bidang berikut :

1. Medis/Ilmu Kedokteran (misalnya dalam deteksi kanker payudara).
2. Aplikasi Teknik (termasuk listrik, mekanik, sipil, produksi, penerbangan, dan robotika).
3. Masalah penjual keliling.
4. Kecerdasan mesin.
5. Sistem dari para ahli
6. Desain dan pengaturan rute jaringan
7. Jaringan komunikasi berkabel dan nirkabel, dan sebagainya.

6. Rangkuman 

Meskipun sejarah perhitungan evolusi berasal dari tahun 1950-an dan 1960-an, namun dalam 10 tahun terakhir algoritma evolusi mampu memecahkan masalah dunia nyata pada komputer desktop. Tiga fitur dasar dari algoritma evolusi biologis juga dibahas. Untuk gen praktis, kami bertanya apakah perhitungan Evolusi dapat diperoleh dari biologi dengan mempertimbangkan dinamika terperinci di mana alel menguntungkan menyerang populasi tipe liar. Kode genetik adaptif menggambarkan bagaimana perhitungan evolusi dan penelitian evolusi biologis dapat berkontribusi pada pemahaman umum tentang dinamika evolusi. Untuk dikotomi genotipe dan fenotipe, biologi sulit sekali untuk menilai signifikansi bahasa representasional.
at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)