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.
1.2 Sejarah Perkembangan EC
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.
1.2.1 Algoritma Genetika
Teknik yang paling populer dalam penelitian komputasi evolusi adalah algoritma 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 ada
interaksi". Analogi tersebut dapat ditarik langsung ke gen dalam organisme biologis. Setiap gen
merupakan entitas yang secara struktural independen dari gen lainnya.
Gambar 1.1 Bit-string crossover
1.2.2 Pemrograman Genetik
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 Subtree crossover
1.2.3 Strategi Evolusi
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
1.2.4 Pemrograman Evolusioner
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.
1.3 Fitur Komputasi Evolusioner
Dalam sebuah algoritma evolusioner, skema representasi dipilih oleh peneliti untuk menentukan
set solusi yang membentuk ruang pencarian untuk algoritma. Sejumlah solusi individu diciptakan
untuk membentuk populasi awal. Langkah-langkah berikut ini kemudian diulang iteratif sampai solusi
telah ditemukan yang memenuhi kriteria terminasi yang telah ditentukan. Setiap individu dievaluasi
menggunakan fungsi khusus untuk masalah yang dipecahkan. Individu baru, atau keturunan, yang
dihasilkan dari orang tua menggunakan operator reproduksi.
Dalam konteks ini, diperkenalkan tiga fitur dasar evolusi biologis:
1. Gen istimewa dan genetika populasi
2. Kode genetik adaptif
3. Pembelahan genotipe dan fenotipe
1.4 Keuntungan Komputasi Evolusioner
Perhitungan evolusi menggambarkan bidang penyidikan yang menyangkut semua algoritma
evolusioner dan menawarkan keuntungan praktis untuk beberapa masalah optimasi. Keuntungan
meliputi kesederhanaan pendekatan, respon yang kuat untuk mengubah keadaan, fleksibilitas dan
sebagainya. Bagian ini menguraikan beberapa keuntungan dan menawarkan saran dalam merancang
algoritma evolusioner untuk pemecahan masalah dunia nyata.
1.4.1 Kesederhanaan Konseptual
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.
1.4.2 Luas Berlakunya
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.7 Flowchart algoritma evolusioner
1.4.3 Hibridisasi dengan Metode Lain
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.
1.4.4 Paralelisme
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.
1.4.5 Kuat untuk Perubahan Dinamis
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 sistemcart-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.8 Sistem cart-pole
1.4.6 Memecahkan Masalah yang Tidak Memiliki Solusi
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.
1.5 Aplikasi Komputasi Evolusioner
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.
Algoritma
evolusioner yang demikian membuat efisien karena fleksibel, dan relatif
mudah untuk berhibridisasi dengan heuristik domain-dependent.
0 komentar:
Posting Komentar