Chapter 1 : Evolutionary Computation (EC)
BAB I
EVOLUTIONARY COMPUTATION (EC)
1.1 PENDAHULUAN [kembali]
Prinsip Darwin "Survival of the fittest" dapat digunakan sebagai titik awal dalam memperkenalkan perhitungan evolusi. Biota yang berevolusi mendemonstrasikan perilaku kompleks di setiap tingkat: sel, organ, individu dan populasi. spesies biologi telah memecahkan masalah kekacauan, kesempatan, interaktifitas nonlinear dan temporalitas. Masalah-masalah ini terbukti setara dengan metode klasik optimasi. Konsep evolusi dapat diterapkan untuk masalah dimana solusi heuristik tidak memiliki hasil yang memuaskan. Akibatnya, algoritma evolusioner dibutuhkan untuk praktik pemecahan masalah
Teknik perhitungan evolusi (EC) mengubah prinsip-prinsip evolusi menjadi algoritma yang dapat digunakan untuk mencari solusi optimal untuk masalah. Dalam pencarian algoritma, sejumlah kemungkinan untuk menemukan solusi terbaik dalam jumlah waktu yang tetap. Untuk ruang pencarian dengan hanya sejumlah kecil dari solusi yang mungkin, semua solusi dapat diperiksa dalam jumlah waktu yang optimal. algoritma pencarian tradisional dengan sampel acak atau sampel heuristik memiliki ruang pencarian satu solusi pada suatu waktu dengan harapan menemukan solusi optimal. Aspek kunci yang membedakan algoritma pencarian evolusioner dari algoritma tradisional tersebut adalah basis populasi.
Dalam kasus perhitungan evolusi, ada empat paradigma sejarah sebagai dasar dari banyak aktifitas di lingkungan: algoritma genetika (Holland, 1975), pemrograman genetik (Koza, 1992, 1994), strategi evolusioner (Recheuberg, 1973), dan pemrograman evolusioner (Forgel et al., 1966). Perbedaan mendasar antara paradigma terletak pada sifat dari skema representasi, operator reproduksi dan metode seleksi.
Teknik yang paling populer adalah algoritme genetika. Dalam Algoritma Genetika tradisional, representasi yang digunakan adalah fixed-length bit string. Setiap posisi dalam string diasumsikan mewakili fitur tertentu dari individu , dan nilai yang disimpan dalam posisi yang mewakili bagaimana fitur diungkapkan dalam solusi. Biasanya, string "dievaluasi sebagai kumpulan fitur struktural dari solusi yang memiliki sedikit atau tidak adanya interakasi". Analogi tersebut dapat ditarik langsung ke gen dalam organisme biologis. Setiap gen merupakan entitas yang secara struktural indenpenden dari yang lainnya.
 |
| Gambar 1.1 Bit-String Crossover |
Dalam program genetik standar, representasi yang digunakan adalah pohon variabel fungsi dan nilai-nilai. Setiap daun di pohon adalah label dari set yang tersedia dari label nilai. Setiap node internal pohon adalah label dari set yang tersedia dari label fungsi. Seluruh pohon sesuai dengan fungsi tunggal yang dapat dievaluasi. Sebuah daun dievaluasi sebagai nilai yang sesuai. Fungsi dievaluasi menggunakan argumen yang merupakan hasil dari evaluasi anak-anaknya. algoritma genetika dan pemrograman genetik mirip dalam banyak hal, kecuali bahwa operator reproduksi disesuaikan dengan representasi pohon. Operator yang paling umum digunakan adalah subtree Crossover, di mana seluruh subtree bertukar antara dua orang tua (lihat Gambar. 1.3). Dalam program genetik standar, semua nilai dan fungsi diasumsikan kembali dalam jenis yang sama, meskipun fungsi dapat bervariasi dalam jumlah argumen yang mereka ambil.
 |
| Gambar 1.2 Mutasi Bit-Flipping |
 |
| Gambar 1.3 Sub-tree Corssover |
Dalam strategi evolusi, representasi yang digunakan adalah panjang vektor real. Seperti dengan bitstrings algoritma genetika, setiap posisi dalam vektor sesuai dengan fitur individu. Namun, fitur dianggap berperilaku daripada struktural. "Akibatnya, interaksi non-linear antara fitur selama evaluasi diharapkan yang memaksa pendekatan yang lebih holistik untuk mengembangkan solusi" (Angeline, 1996).
Operator reproduksi utama dalam strategi evolusi adalah mutasi Gaussian, dimana nilai acak dari distribusi Gaussian ditambahkan ke setiap elemen dari vektor individu untuk menciptakan keturunan baru (lihat Gambar. 1.4). Operator lain yang digunakan adalah rekombinasi menengah, dimana vektor dari dua orang tua yang rata-rata sama, elemen dengan elemen, membentuk keturunan baru (lihat Gambar. 1.5). Efek dari operator ini mencerminkan perilaku yang bertentangan dengan penafsiran struktural representasi sejak pengetahuan tentang nilai-nilai elemen vektor digunakan untuk memperoleh elemen vektor baru.
Gambar 1.4 Mutasi Gaussian
Gambar 1.5 Rekombinasi menengah
Pemrograman evolusioner mengambil ide yang mewakili fenotip individu dari mesin statis yang mampu merespons rangsangan lingkungan dan mengembangkan operator untuk melakukan perubahan struktural dan perilaku dari waktu ke waktu. Ide ini diterapkan untuk berbagai masalah termasuk masalah prediksi, optimasi dan pembelajaran mesin.
Representasi yang digunakan dalam pemrograman evolusioner biasanya disesuaikan dengan domain masalah. Salah satu representasi yang umum digunakan adalah panjang vektor real. Perbedaan utama antara pemrograman evolusioner dan pendekatan sebelumnya adalah bahwa tidak ada pertukaran materi antara individu dalam populasi dibuat. Dengan demikian, hanya operator mutasi yang digunakan. Untuk representasi vektor bernilai real, pemrograman evolusioner sangat mirip dengan strategi evolusi tanpa rekombinasi.
Fitur Evoulioner Biologis adalah sebagai berikut :
1. Gen Istimewa
2. Kode Genetik Adaptif
3. Pembelahan Genotipe dan Fenotipe
Perhitungan evolusi menggambarkan bidang penyidikan yang menyangkut semua algrotitma evolusioner dan menawarkan keuntungan praktis untuk beberapa masalah optimasi. Keuntungan-keuntungannya adalah sebagai berikut :
Gambar 1.7 menunjukkan diagram alir dari algoritma evolusioner yang diterapkan untuk optimasi fungsi. Algoritma ini terdiri dari inisialisasi, variasi berulang dan seleksi dalam indeks kinerja. Selama iterasi dari variasi acak dan seleksi, populasi dapat dikumpulkan untuk solusi optimal. Efektivitas algoritma evolusi tergantung pada variasi dan seleksi operator yang diterapkan pada representasi yang dipilih dan inisialisasi.
Algoritma evolusioner dapat diterapkan untuk setiap masalah yang dapat dirumuskan sebagai masalah optimalisasi fungsi. Untuk mengatasi masalah ini, membutuhkan struktur data untuk mewakili solusi, untuk mengevaluasi solusi dari solusi lama. Representasi harus memungkinkan untuk operator variasi yang mempertahankan hubungan perilaku antara orang tua dan anak. Perubahan kecil dalam struktur induk akan menyebabkan perubahan kecil pada keturunannya, dan juga perubahan besar dalam induk akan menyebabkan perubahan drastis pada keturunannya. Dalam hal ini, algoritma evolusioner dikembangkan, sehingga mereka disetel dengan cara adaptif diri. Hal ini membuat perhitungan evolusi untuk diterapkan ke daerah-daerah luas meliputi masalah kombinatorial diskrit, masalah mixed-integer dan sebagainya.
 |
| Gambar 1. 6 Flowchart Algoritma Evolusioner |
Algoritma evolusioner dapat dikombinasikan dengan teknik optimasi yang lebih tradisional, seperti penggunaan minimisasi konjugat-gradien yang digunakan setelah pencarian utama dengan algoritma evolusioner. Hal ini juga dapat melibatkan aplikasi simultan algoritma seperti penggunaan pencarian evolusi untuk struktur model ditambah dengan pencarian gradien untuk nilai parameter. Selanjutnya, perhitungan evolusi dapat digunakan untuk mengoptimalkan kinerja jaringan saraf, sistem fuzzy, sistem produksi, sistem nirkabel dan struktur program lain.
Evolusi adalah proses yang sangat paralel. Evaluasi setiap solusi dapat ditangani secara paralel dan seleksi hanya membutuhkan beberapa tindakan. Akibatnya, waktu yang diperlukan untuk aplikasi mungkin berbanding terbalik dengan jumlah prosesor. Selain itu, mesin komputasi saat ini memberikan kecepatan komputasi yang cukup untuk menghasilkan solusi untuk masalah sulit dalam waktu yang wajar.
Perhitungan evolusi dapat digunakan untuk menyesuaikan solusi dengan perbahan keadaan. Populasi yang dihasilkan dari evolusi memberikan dasar untuk perbaikan lebih lanjut dan dalam banyak kasus, tidak perlu mengulang populasi secara acak. Metode adaptasi dalam menghadapi lingkungan yang dinamis merupakan kunci keuntungan. Misalnya, Wielaud (1990) menerapkan algoritma genetika untuk mengembangkan jaringan saraf berulang untuk mengontrol sistem cart-pole yang terdiri dari dua kutub seperti ditunjukkan pada Gambar. 1.8. Beberapa peneliti menggunakan algoritma evolusioner untuk mengoptimalkan jaringan saraf untuk mengontrol tanaman ini untuk panjang tiang yang berbeda.
 |
| Gambar 1.7 Cart Pole |
Keuntungan dari algoritma evolusioner termasuk kemampuannya untuk mengatasi masalah di luar keahlian manusia. Para ahli mungkin tidak setuju, tidak memenuhi syarat, tidak konsisten atau hanya dapat menyebabkan kesalahan. Kecerdasan buatan dapat diterapkan untuk beberapa masalah sulit yang membutuhkan kecepatan komputasi yang tinggi, tetapi mereka tidak dapat bersaing dengan kecerdasan manusia. Fogel (1995) menyatakan kecerdasan buatan sebagai "Mereka memecahkan masalah, tetapi mereka tidak memecahkan masalah bagaimana memecahkan masalah." Sebaliknya, perhitungan evolusioner menyediakan metode untuk memecahkan masalah bagaimana untuk memecahkan masalah.
Aplikasi komputasi evolusi mencakup bidang-bidang berikut:
· Obat-obatan (misalnya dalam deteksi kanker payudara).
· Aplikasi Rekayasa (termasuk listrik, mekanik, sipil, produksi, penerbangan dan robotika).
· Masalah Traveling salesman.
· Mesin intelijen.
· Sistem ahli.
· Jaringan desain dan routing.
· Jaringan komunikasi nirkabel kabel.
· dan sebagainya.
No comments:
Post a Comment