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.^[1] Selain itu, EA juga merupakan bagian dari komputasi evolusioner yang merupakan cabang dari kecerdasan komputasional.^[2] 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.^[3] 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.^[4][5][6] Oleh karena itu, tidak selalu terdapat hubungan langsung antara kompleksitas algoritma dengan kompleksitas masalah.

Definisi umum

Berikut ini adalah contoh algoritma evolusi yang umum:^[7][8][9]

1. Menghasilkan populasi awal (generasi pertama) individu secara acak.
2. Mengevaluasi fitness setiap individu dalam populasi.
3. Memeriksa, apakah tujuan tercapai dan algoritma dapat dihentikan.
4. Memiliki individu sebagai orang tua, individu yang memiliki fitness yang lebih tinggi lebih disukai.
5. Menghasilkan keturunan dengan persilangan (meniru reproduksi ).
6. Menerapkan operasi mutasi pada keturunannya.
7. Memilih individu yang fitness-nya lebih rendah untuk diganti dengan individu baru (meniru konsep seleksi alam).
8. 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),^[3] 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.^[10][11][12]
  • 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.^[13][14]
• 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.^[15][16][17]

Latar belakang teoritis

Prinsip teoritis 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.^[18][19] 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.^[18][20]

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 ${\displaystyle k}$, peningkatan nilai kebugaran ${\displaystyle F}$ dari masing-masing individu terbaik ${\displaystyle x'}$ akan terjadi dengan suatu probabilitas ${\displaystyle P>0}$. Dengan demikian:

${\displaystyle 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.^[21] 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.^[22][23]

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.^[24] 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.^[25][26]

Aplikasi

Bidang-bidang yang algoritma evolusi digunakan secara praktis hampir tidak terbatas^[6] dan berkisar dari industri,^[27][28] teknik,^[3][4][29] penjadwalan kompleks,^[5][30][31] pertanian,^[32] perencanaan pergerakan robot,^[33], keuangan^[34][35] hingga penelitian^[36][37] 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.^[38] Sejumlah publikasi telah ditulis khusus untuk pemula, dengan tujuan membantu menghindari kesalahan dasar dan meningkatkan peluang keberhasilan proyek aplikasi EA.^[38][39][40] 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.^[41]

Simulasi komputer Tierra dan Avida mencoba memodelkan dinamika makroevolusi .

Galeri

^[42][43]

• 
  Pencarian EA dua populasi atas fungsi Rosenbrock yang dibatasi dengan optimum global yang dibatasi
• 
  Pencarian EA dua populasi pada fungsi Rosenbrock yang dibatasi. Optimum global tidak terbatas.
• 
  Estimasi algoritma distribusi atas fungsi bump Keane
• 
  Pencarian EA dua populasi dari optima terbatas fungsi Simionescu