Algoritma evolusioner

**Algoritma evolusioner** (bahasa Inggris: *Evolutionary algorithm* atau disingkat **EA**) adalah teknik komputasi yang terinspirasi dari mekanisme dasar evolusi biologis. Algoritma ini digunakan untuk menyelesaikan masalah optimasi atau pencarian solusi yang sulit, terutama ketika tidak tersedia metode eksak maupun algoritmik yang efisien. EA termasuk ke dalam metaheuristik dan juga merupakan algoritma berbasis populasi yang terinspirasi oleh biologi. Selain itu, EA juga merupakan bagian dari komputasi evolusioner yang merupakan cabang dari kecerdasan komputasional. Mekanisme utama evolusi biologis yang ditiru oleh EA adalah reproduksi, mutasi, rekombinasi, dan seleksi. Dalam implementasinya, solusi kandidat masalah optimasi diperlakukan sebagai individu dalam sebuah populasi, sementara fungsi *fitness* digunakan untuk menilai kualitas solusi (lihat juga fungsi kerugian). Evolusi populasi kemudian berlangsung melalui penerapan berulang operator-operator tersebut.

Algoritma evolusioner sering menunjukkan kinerja yang baik dalam menghampiri solusi berbagai jenis permasalahan karenaalgoritma ini tidak membuat asumsi tertentu mengenai bentuk fitness landscape yang mendasarinya secara. Penerapan teknik algoritma evolusioner untuk pemodelan evolusi biologis umumnya terbatas pada eksplorasi proses mikroevolusi, serta pada model perencanaan berbasis proses seluler. Dalam sebagian besar aplikasi EA yang sebenarnya, kompleksitas komputasi menjadi faktor pembatas. Kompleksitas ini terutama disebabkan oleh evaluasi fungsi *fitness* yang umumnya dapat diatasi dengan aproksimasi *fitness*. Meskipun demikian, EA yang tampaknya sederhana dapat memecahkan masalah yang seringkali rumit. Oleh karena itu, tidak selalu terdapat hubungan langsung antara kompleksitas algoritma dengan kompleksitas masalah.

## Definisi umum
Berikut ini adalah contoh algoritma evolusi yang umum:

# Menghasilkan populasi awal (generasi pertama) individu secara acak.
# Mengevaluasi *fitness* setiap individu dalam populasi.
# Memeriksa, apakah tujuan tercapai dan algoritma dapat dihentikan.
# Memiliki individu sebagai orang tua, individu yang memiliki fitness yang lebih tinggi lebih disukai.
# Menghasilkan keturunan dengan persilangan (meniru reproduksi ).
# Menerapkan operasi mutasi pada keturunannya.
# Memilih individu yang *fitness*-nya lebih rendah untuk diganti dengan individu baru (meniru konsep seleksi alam).
# Kembali ke 2.

## Jenis
Teknik-teknik yang serupa biasanya berbeda dalam hal representasi genetik maupun implementasi detail lainnya, serta bergantung pada sifat masalah yang diterapkan.

* Algoritma genetika – Jenis EA yang paling populer. Solusi direpresentasikan dalam bentuk rangkaian angka (biasanya biner, meskipun representasi terbaik biasanya yang mencerminkan masalah yang sedang dipecahkan), dengan menerapkan operator seperti rekombinasi dan mutasi (terkadang salah satu dan terkadang keduanya). Jenis EA ini sering digunakan dalam masalah optimasi .
* Pemrograman Genetik – Solusi direpresentasikan dalam bentuk program komputer, dan *fitness* ditentukan dari kemampuan program tersebut dalam menyelesaikan suatu permasalahan komputasional. Ada banyak varian Pemrograman Genetik:
** Pemrograman genetika Cartesian
** Pemrograman ekspresi gen
** Evolusi tata bahasa
** Pemrograman genetik linier
** Pemrograman multi ekspresi
* Pemrograman evolusioner – Mirip dengan strategi evolusi, tetapi menggunakan seleksi deterministik untuk semua orang tua.
* Strategi evolusi (ES) – Menggunakan vektor bilangan riil sebagai representasi solusi, dan biasanya menggunakan laju mutasi adaptif. Metode ini terutama digunakan untuk optimasi numerik, meskipun terdapat juga varian untuk tugas kombinatorial.
** CMA-ES
** Strategi evolusi alami
* Evolusi diferensial – Berdasarkan selisih vektor sehingga cocok untuk masalah optimasi numerik .
* Algoritma koevolusi – Mirip dengan algoritma genetika dan strategi evolusi, tetapi solusi yang dihasilkan dibandingkan berdasarkan hasil interaksinya dengan solusi lain. Solusi dapat bersaing atau bekerja sama selama proses pencarian. Algoritma koevolusi sering digunakan dalam skenario di mana lanskap *fitness* bersifat dinamis, kompleks, atau melibatkan interaksi kompetitif.
* Neuroevolusi – Mirip dengan pemrograman genetik, tetapi genom merepresentasikan jaringan saraf tiruan dengan mendeskripsikan struktur dan bobot koneksi. Pengkodean genom dapat bersifat langsung maupun tidak langsung.
* Sistem pengklasifikasi belajar (*Learning classifier system*, LCS) – Solusi berupa seperangkat pengklasifikasi (aturan atau kondisi).
** Michigan-LCS berevolusi pada level pengklasifikasi individual.
** Pittsburgh-LCS menggunakan populasi dari himpunan pengklasifikasi. Awalnya, pengklasifikasi hanya berupa biner, tetapi kini juga mencakup tipe riil, jaringan saraf, atau S-*expression*. Penilaian *fitness* biasanya menggunakan pendekatan pembelajaran penguatan (*reinforcement learning*) berbasis kekuatan atau akurasi, maupun pembelajaran terawasi.
* Algoritma Kualitas–Keragaman – Algoritma QD secara bersamaan bertujuan untuk menghasilkan solusi berkualitas tinggi dan beragam. Tidak seperti algoritma optimasi tradisional yang hanya berfokus pada pencarian solusi terbaik untuk suatu masalah, algoritma QD mengeksplorasi beragam solusi di seluruh ruang masalah dan mempertahankan solusi yang tidak hanya berkinerja tinggi, tetapi juga beragam dan unik.

## Latar belakang teoretis
Prinsip teoretis berikut berlaku untuk semua atau hampir semua EA.

### Teorema tidak ada makan siang gratis
Menurut teorema tidak ada makan siang gratis dalam optimasi, semua strategi optimasi sama efektifnya jika dipertimbangkan pada himpunan semua masalah optimasi. Dengan kata lain, tidak ada algoritma evolusioner yang secara fundamental lebih baik daripada yang lain apabila domain permasalahan tidak dibatasi. Dalam praktiknya, himpunan permasalahan selalu terbatas, sehingga algoritma evolusioner dapat ditingkatkan kinerjanya dengan memanfaatkan pengetahuan spesifik suatu masalah. Hal ini dapat dilakukan, misalnya, dengan memilih kekuatan mutasi tertentu, menggunakan representasi solusi yang sesuai dengan permasalahan, atau dengan membangun sebagian populasi awal melalui heuristik. Selain itu, algoritma evolusioner dapat diperkaya dengan heuristik, prosedur pencarian lokal, atau metode terkait permasalahan dalam proses pembentukan keturunan. Bentuk perluasan ini dikenal sebagai algoritma memetik (memetic algorithm), yang memadukan evolusi populasi dengan optimasi lokal. Pendekatan ini banyak digunakan dalam aplikasi praktis karena dapat mempercepat proses pencarian solusi dan meningkatkan ketahanan algoritma.

### Konvergensi
Untuk algoritma evolusioner dengan elitisme (*elitist evolutionary algorithms*), yaitu varian yang selain keturunannya (*offspring*) juga digunakan setidaknya individu terbaik dari generasi induk untuk membentuk generasi berikutnya, terdapat bukti umum mengenai konvergensi dengan syarat bahwa optimum memang ada. Tanpa mengurangi keumuman, pembuktian biasanya dilakukan dengan asumsi bahwa masalah yang diselesaikan adalah pencarian maksimum.

Dari sifat penerimaan keturunan elitis dan adanya optimum, dapat disimpulkan bahwa pada setiap generasi k, peningkatan nilai kebugaran F dari masing-masing individu terbaik x' akan terjadi dengan suatu probabilitas P > 0. Dengan demikian:

: F(x'_1) \leq F(x'_2) \leq F(x'_3) \leq \cdots \leq F(x'_k) \leq \cdots

Artinya, nilai kebugaran (*fitness value*) merepresentasikan sebuah barisan yang monotonik tak-menurun yang dibatasi oleh keberadaan optimum. Dari sini, maka barisan tersebut berkonvergensi menuju optimum.

Karena pembuktian tersebut tidak memberikan pernyataan mengenai kecepatan konvergensi, maka hasilnya kurang bermanfaat dalam penerapan praktis EA. Namun, hal ini tetap membenarkan rekomendasi untuk menggunakan EA yang bersifat elitis. Akan tetapi, ketika menggunakan model populasi panmiktik yang umum, EA elitis cenderung lebih cepat mengalami konvergensi prematur dibandingkan dengan yang non-elitis. Dalam model populasi panmiktik, pemilihan pasangan (lihat langkah 4 pada definisi umum) dilakukan sedemikian rupa sehingga setiap individu dalam seluruh populasi dapat menjadi pasangan kawin. Sebaliknya, dalam populasi non-pan mictic, pemilihan dibatasi dengan sesuai, sehingga kecepatan penyebaran individu yang lebih baik berkurang dibandingkan dengan populasi panmiktik. Dengan demikian, risiko umum terjadinya konvergensi prematur pada EA elitis dapat dikurangi secara signifikan dengan menggunakan model populasi yang sesuai, yang membatasi pemilihan pasangan.

### Alfabet virtual
Dengan teori alfabet virtual, David E. Goldberg menunjukkan pada tahun 1990 bahwa dengan menggunakan representasi bilangan real, suatu EA yang memakai operator rekombinasi klasik (misalnya *uniform* atau n-point *crossover*) tidak dapat mencapai area tertentu dari ruang pencarian, berbeda dengan pengkodean menggunakan bilangan biner. Dari hasil ini muncul rekomendasi bahwa EA dengan representasi real sebaiknya menggunakan operator aritmetika untuk rekombinasi (misalnya rata-rata aritmetika atau rekombinasi intermediat). Dengan operator yang sesuai, representasi berbasis bilangan real lebih efektif dibandingkan representasi biner, bertentangan dengan pendapat sebelumnya.

## Aplikasi
Bidang-bidang yang algoritma evolusi digunakan secara praktis hampir tidak terbatas dan berkisar dari industri, teknik, penjadwalan kompleks, pertanian, perencanaan pergerakan robot, keuangan hingga penelitian dan seni. Penerapan sebuah EA biasanya menuntut perubahan pola pikir bagi pengguna yang belum berpengalaman, karena pendekatannya berbeda dengan metode eksak konvensional yang umumnya diajarkan dalam kurikulum teknik maupun disiplin lain. Misalnya, fungsi kebugaran (*fitness function*) tidak hanya harus merumuskan tujuan akhir, tetapi juga harus mendukung proses pencarian evolusioner menuju tujuan tersebut. Dalam konteks penjadwalan, jika tujuan adalah menghindari puncak pemakaian sumber daya (misalnya tenaga kerja atau konsumsi energi), penilaian tidak cukup hanya berdasarkan nilai maksimum penggunaan. Sebaliknya, jumlah dan durasi terjadinya kelebihan beban pada tingkat yang masih dapat diterima juga perlu dipertimbangkan, sehingga pengurangan meskipun kecil tetap diberi penghargaan dalam proses pencarian. Sejumlah publikasi telah ditulis khusus untuk pemula, dengan tujuan membantu menghindari kesalahan dasar dan meningkatkan peluang keberhasilan proyek aplikasi EA. Publikasi ini umumnya menekankan pertanyaan mendasar: kapan sebuah masalah sebaiknya diselesaikan dengan algoritma evolusioner, dan kapan lebih baik menggunakan pendekatan lain.

## Contoh
Pada tahun 2020, Google menyatakan bahwa AutoML-Zero mereka berhasil menemukan kembali algoritma klasik seperti konsep jaringan saraf.

Simulasi komputer *Tierra* dan *Avida* mencoba memodelkan dinamika makroevolusi .

## Galeri

Berkas:Two-population_EA_search_(2).gif|al=A two-population EA search over a constrained Rosenbrock function with bounded global optimum| Pencarian EA dua populasi atas fungsi Rosenbrock yang dibatasi dengan optimum global yang dibatasi
Berkas:Two-population_EA_search_(3).gif|al=A two-population EA search over a constrained Rosenbrock function. Global optimum is not bounded.| Pencarian EA dua populasi pada fungsi Rosenbrock yang dibatasi. Optimum global tidak terbatas.
Berkas:Estimation_of_Distribution_Algorithm_animation.gif|al=Estimation of distribution algorithm over Keane's bump function| Estimasi algoritma distribusi atas fungsi bump Keane
Berkas:Two_population_EA_animation.gif|al=A two-population EA search of a bounded optima of Simionescu's function| Pencarian EA dua populasi dari optima terbatas fungsi Simionescu


## Referensi

## Bibliografi

* Ashlock, D. (2006), *Evolutionary Computation for Modeling and Optimization*, Springer, New York,   .
* Bäck, T. (1996), *[https://books.google.com/books?id=htJHI1UrL7IC Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms]*, Oxford Univ. Press, New York, .
* Bäck, T., Fogel, D., Michalewicz, Z. (1999), *Evolutionary Computation 1: Basic Algorithms and Operators*, CRC Press, Boca Raton, USA, .
* Bäck, T., Fogel, D., Michalewicz, Z. (2000), *Evolutionary Computation 2: Advanced Algorithms and Operators*, CRC Press, Boca Raton, USA,  .
* Banzhaf, W., Nordin, P., Keller, R., Francone, F. (1998), *Genetic Programming - An Introduction*, Morgan Kaufmann, San Francisco, .
* Eiben, A.E., Smith, J.E. (2003), *Introduction to Evolutionary Computing*, Springer, Heidelberg, New York,  .
* Holland, J. H. (1992), *[https://books.google.com/books?id=5EgGaBkwvWcC Adaptation in Natural and Artificial Systems]*, MIT Press, Cambridge, MA, .
* Michalewicz, Z.; Fogel, D.B. (2004), *How To Solve It: Modern Heuristics*. Springer, Berlin, Heidelberg, , .
* 
* 
* Price, K., Storn, R.M., Lampinen, J.A., (2005). ''Differential Evolution: A Practical Approach to Global Optimization'', Springer, Berlin, Heidelberg, , .
* Ingo Rechenberg (1971), *Evolutionsstrategie - Optimierung technischer Systeme nach Prinzipien der biologischen Evolution* (PhD thesis). Reprinted by Fromman-Holzboog (1973). ISBN&nbsp;
* Hans-Paul Schwefel (1974), *Numerische Optimierung von Computer-Modellen* (PhD thesis). Reprinted by Birkhäuser (1977).
* Hans-Paul Schwefel (1995), *[https://www.researchgate.net/publication/220690578_Evolution_and_Optimum_Seeking Evolution and Optimum Seeking]*. Wiley & Sons, New York. ISBN&nbsp;
* Simon, D. (2013), ''Evolutionary Optimization Algorithms'' , Wiley & Sons, 
* Kruse, Rudolf; Borgelt, Christian; Klawonn, Frank; Moewes, Christian; Steinbrecher, Matthias; Held, Pascal (2013), ''Computational Intelligence: A Methodological Introduction''. Springer, London. ISBN&nbsp;, .
* 

## Pranala luar

* Tinjauan Umum Sejarah dan Ragam Algoritma Evolusi