Evolutionary Programming
Pengenalan
Evolutionary Programming, diusulkan oleh Lawrence J. Fogel pada tahun 1960, merupakan sebuah strategi optimasi stokhastik yang mirip dengan Genetic Algorithm, tetapi lebih menekankan pada hubungan sifat antara induk dan anak , dari pada mengemulasikan operator genetik tertentu seperti yang terjadi di alam. Evolutionary Programming mirip dengan Evolution Strategy, walaupun kedua pendekatan tersebut berkembang masing-masing.
Seperti ES dan GA, EP merupakan sebuah metode optimasi di mana ketika teknik-teknik lain seperti gradien turunan atau langsung, penemuan analisis tidak memungkinan. Fungsi optimasi kombinatorik dan bernilai riil di mana permukaan optimasi atau grafik fitness bergelombang, memiliki banyak solusi-solusi local optima, sangat cocok untuk Evolutionary Programming.
Sejarah
Buku pada tahun 1996, “Artificial Intelligence Through Simulated Evolution” oleh Fogel, Owens dan Walsh merupakan publikasi pertama untuk aplikasi EP, walaupun banyak paper-paper lain yang sudah ada sebelumnya. Pada buku tersebut, finite state automata dievolusikan untuk memprediksikan rangkaian simbol yang dihasilkan oleh proses-proses Markov dan urutan waktu yang berubah-ubah. Prediksi evolusionari seperti itu dimotivasi oleh sebuah pengakuan bahwa prediksi merupakan sebuah kunci dalam perilaku yang cerdas (didefinisikan dalam konteks perilaku adaptif, di mana organisme cerdas harus mengantisipasi kejadian-kejadian untuk dapat mengadaptasikan perilaku untuk mencapai sebauh tujuan).
Pada tahun 1992, Konferensi tahunan pertama tentang Evolutionary Programming diadakan di La Jolla, CA. Konferensi-konferensi selanjutnya telah diadakan setiap tahun. Konferensi-konferensi tersebut menarik perhatian grup-grup akademik yang beragam, peneliti-peneliti komersial dan militer yang melakukan pegembangan teori EP dan mengimplementasikan EP untuk masalah-masalah optimasi yang beragam, baik pada bidang engineering dan biologi.
Proses
Untuk EP, seperti GA, terdapat sebuah asumsi bahwa sebuah grafik fitness dapat dikarakterisasi pada konteks variabel, dan sebuah solusi optimal sesuai dengan konteks variabel tersebut. Sebagai contoh, jika seseorang ingin mencari jalur terpendek dalam TSP, setiap solusi merupakan sebuah jalur. Panjang dari jalur tersebut dapat diekspresikan dalam sebuah angka, yang akan digunakan sebagai fitness dari solusi tersebut. Grafik fitness untuk masalah ini dapat dikarakterisasikan sebagai permukaan atas yang proporsional dengan panjang jalur dalam kumpulan jalur-jalur yang memungkinkan. Tujuannya adalah untuk mencari sebuah jalur terpendek yang optimal dalam kumpulan solusi tersebut, atau lebih praktisnya, untuk mencari jalur paling pendek dengan sangat cepat.
Metode dasar EP tediri dari 3 langkah (Ulang sampai sebuah threshold untuk iterasi telah terlebihi atau solusi yang diinginkan telah tercapai):
1. Pilih populasi awal secara acak. Jumlah dari solusi pada sebuah populasi memiliki relevansi yang erat dengan kecepatan optimasi, tetapi tidak ada jawaban yang pasti mengenai berapa banyak yang seharusnya terdapat pada sebuah populasi.
2. Setiap solusi direplikasi menjadi sebauh populasi yang baru. Masing-masing dari solusi anak ini mengalami mutasi menurut sebuah tipe distribusi mutasi, dengan skala minor sampai ekstrim dengan tipe mutasi kontinuum di antaranya. Skala dari mutasi ditentukan oleh perubahan fungsional dari induk.
3. Setiap solusi anak akan dievaluasi dengan menghitung fitness-nya. Biasanya, sebuah turnamen stokhastik diadakan untuk menentukan N solusi yang akan dipertahankan untuk populasi solusi, meskipun biasanya hal ini dilakukan secara deterministik. Tidak ada syarat bahwa ukuran populasi harus tetap, tetapi, juga tidak ada batasan bahwa setiap induk menhasilkan sebuah solusi anak.
ref : dari berbagai sumber
