Lompat ke isi

Algoritma evolusioner

Ensiklopedia Pengetahuan Universitas Islam Sultan Agung

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),[10] 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 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.[11][12][13]
    • 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.[14][15]
  • 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.[16][17][18]

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.[19][20] 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.[21][22]

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)≤F(x'2)≤F(x'3)≤⋯≤F(x'k)≤⋯

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

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.[26] 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.[27][28]

Aplikasi

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

Simulasi komputer Tierra dan Avida mencoba memodelkan dinamika makroevolusi .

Galeri

[49][50]

Bibliografi

Pranala luar

Referensi

  1. ↑ Davide Farinati. A survey on dynamic populations in bio-inspired algorithms. Genetic Programming and Evolvable Machines. December 2024. Vol. 25 (2). doi:10.1007/s10710-024-09492-4.
  2. ↑ P. A. Vikhar. 2016 International Conference on Global Trends in Signal Processing, Information Computing and Communication (ICGTSPICC). 2016. hlm. 261–265. doi:10.1109/ICGTSPICC.2016.7955308. ISBN 978-1-5090-0467-6.
  3. ↑ J. P. Cohoon. "Evolutionary Algorithms for the Physical Design of VLSI Circuits" in Advances in Evolutionary Computing: Theory and Applications. Springer Verlag. 2003. hlm. 683–712. ISBN 978-3-540-43330-9.
  4. ↑ Adam Slowik. Evolutionary algorithms and their applications to engineering problems. Neural Computing and Applications. 2020. Vol. 32 (16). hlm. 12363–12379. doi:10.1007/s00521-020-04832-8.
  5. ↑ Marek Mika. Modelling and solving grid resource allocation problem with network resources for workflow applications. Journal of Scheduling. 2011. Vol. 14 (3). hlm. 291–306. doi:10.1007/s10951-009-0158-0.
  6. ↑ International Conference on the Applications of Evolutionary Computation. The conference is part of the Evo* series. The conference proceedings are published by Springer.
  7. ↑ Thomas Jansen. Proceedings of the 9th annual conference on Genetic and evolutionary computation. Association for Computing Machinery. 7 July 2007. hlm. 939–946. doi:10.1145/1276958.1277148. ISBN 978-1-59593-697-4.
  8. ↑ Yaochu Jin. Advanced Fuzzy Systems Design and Applications. Physica-Verlag HD. 2003. Vol. 112. hlm. 49–71. doi:10.1007/978-3-7908-1771-3_2. ISBN 978-3-7908-2520-6.
  9. ↑ Jorge Tavares. Genetic Programming. Springer. 2004. Vol. 3003. hlm. 389–398. doi:10.1007/978-3-540-24650-3_37. ISBN 978-3-540-21346-8.
  10. ↑ J. P. Cohoon. "Evolutionary Algorithms for the Physical Design of VLSI Circuits" in Advances in Evolutionary Computing: Theory and Applications. Springer Verlag. 2003. hlm. 683–712. ISBN 978-3-540-43330-9. Cohoon, J. P.; Karro, J.; Lienig, J. (2003). "Evolutionary Algorithms for the Physical Design of VLSI Circuits" in Advances in Evolutionary Computing: Theory and Applications (PDF) . London: Springer Verlag. pp. 683– 712. ISBN 978-3-540-43330-9 .
  11. ↑ Volker Nissen. Fuzzy Logik. Springer. 1994. hlm. 33–40. doi:10.1007/978-3-642-79386-8_5. ISBN 978-3-642-79386-8.
  12. ↑ V. N. Coelho. Hybrid Self-Adaptive Evolution Strategies Guided by Neighborhood Structures for Combinatorial Optimization Problems. Evol Comput. 2016. Vol. 24 (4). hlm. 637–666. doi:10.1162/EVCO_a_00187.
  13. ↑ Adam Slowik. Evolutionary algorithms and their applications to engineering problems. Neural Computing and Applications. 1 August 2020. Vol. 32 (16). hlm. 12363–12379. doi:10.1007/s00521-020-04832-8.
  14. ↑ Xiaoliang Ma. A Survey on Cooperative Co-Evolutionary Algorithms. IEEE Transactions on Evolutionary Computation. 2019. Vol. 23. hlm. 421–441. doi:10.1109/TEVC.2018.2868770.
  15. ↑ Elena Popovici. Handbook of Natural Computing. Springer Berlin Heidelberg. 2012. hlm. 987–1033. doi:10.1007/978-3-540-92910-9_31. ISBN 978-3-540-92910-9.
  16. ↑ Justin K. Pugh. Quality Diversity: A New Frontier for Evolutionary Computation. Frontiers in Robotics and AI. 2016-07-12. Vol. 3. doi:10.3389/frobt.2016.00040.
  17. ↑ Joel Lehman. Proceedings of the 13th annual conference on Genetic and evolutionary computation. ACM. 2011-07-12. hlm. 211–218. doi:10.1145/2001576.2001606. ISBN 9781450305570.
  18. ↑ Antoine Cully. Robots that can adapt like animals. Nature. 2015-05-27. Vol. 521 (7553). hlm. 503–507. doi:10.1038/nature14422.
  19. ↑ Lawrence Davis. Handbook of genetic algorithms. Van Nostrand Reinhold. 1991. ISBN 0-442-00173-8.
  20. ↑ Jens Lienig. An evolutionary algorithm for the routing of multi-chip modules. Parallel Problem Solving from Nature — PPSN III. Springer. 1994. Vol. 866. hlm. 588–597. doi:10.1007/3-540-58484-6_301. ISBN 978-3-540-58484-1.
  21. ↑ Lawrence Davis. Handbook of genetic algorithms. Van Nostrand Reinhold. 1991. ISBN 0-442-00173-8.
  22. ↑ Handbook of Memetic Algorithms. Springer Berlin Heidelberg. 2012. Vol. 379. doi:10.1007/978-3-642-23247-3. ISBN 978-3-642-23246-6.
  23. ↑ Yee Leung. Degree of population diversity - a perspective on premature convergence in genetic algorithms and its Markov chain analysis. IEEE Transactions on Neural Networks. 1997. Vol. 8 (5). hlm. 1165–1176. doi:10.1109/72.623217.
  24. ↑ Martina Gorges-Schleuter. A comparative study of global and local selection in evolution strategies. Parallel Problem Solving from Nature — PPSN V. Springer Berlin Heidelberg. 1998. Vol. 1498. hlm. 367–377. doi:10.1007/bfb0056879. ISBN 978-3-540-65078-2.
  25. ↑ Bernabe Dorronsoro. Cellular Genetic Algorithms. Springer US. 2008. Vol. 42. doi:10.1007/978-0-387-77610-1. ISBN 978-0-387-77609-5.
  26. ↑ David E. Goldberg. The theory of virtual alphabets. Parallel Problem Solving from Nature. Springer-Verlag. 1990. Vol. 496. hlm. 13–22. doi:10.1007/bfb0029726. ISBN 978-3-540-54148-6.
  27. ↑ J. Stender. Genetic algorithms in optimisation, simulation, and modelling. IOS Press. 1994. ISBN 90-5199-180-0.
  28. ↑ Zbigniew Michalewicz. Genetic Algorithms + Data Structures = Evolution Programs. Springer. 1996. ISBN 978-3-662-03315-9.
  29. ↑ International Conference on the Applications of Evolutionary Computation. The conference is part of the Evo* series. The conference proceedings are published by Springer.
  30. ↑ Ernesto Sanchez. Industrial Applications of Evolutionary Algorithms. Springer Berlin Heidelberg. 2012. Vol. 34. doi:10.1007/978-3-642-27467-1. ISBN 978-3-642-27466-4.
  31. ↑ Evolutionary algorithms in engineering and computer science : recent advances in genetic algorithms, evolution strategies, evolutionary programming, genetic programming, and industrial applications. Wiley and Sons. 1999. ISBN 0-585-29445-3.
  32. ↑ J. P. Cohoon. "Evolutionary Algorithms for the Physical Design of VLSI Circuits" in Advances in Evolutionary Computing: Theory and Applications. Springer Verlag. 2003. hlm. 683–712. ISBN 978-3-540-43330-9.
  33. ↑ Adam Slowik. Evolutionary algorithms and their applications to engineering problems. Neural Computing and Applications. 2020. Vol. 32 (16). hlm. 12363–12379. doi:10.1007/s00521-020-04832-8.
  34. ↑ Mitsuo Gen. Genetic Algorithms and Engineering Optimization. John Wiley & Sons, Inc. 1999-12-17. doi:10.1002/9780470172261. ISBN 978-0-470-17226-1.
  35. ↑ Marek Mika. Modelling and solving grid resource allocation problem with network resources for workflow applications. Journal of Scheduling. 2011. Vol. 14 (3). hlm. 291–306. doi:10.1007/s10951-009-0158-0.
  36. ↑ Keshav P. Dahal. Evolutionary scheduling. Springer. 2007. doi:10.1007/978-3-540-48584-1. ISBN 978-3-540-48584-1.
  37. ↑ Wilfried Jakob. Fast Rescheduling of Multiple Workflows to Constrained Heterogeneous Resources Using Multi-Criteria Memetic Computing. Algorithms. 2013-04-22. Vol. 6 (2). hlm. 245–277. doi:10.3390/a6020245.
  38. ↑ David G. Mayer. Evolutionary Algorithms and Agricultural Systems. Springer US. 2002. doi:10.1007/978-1-4615-1717-7. ISBN 978-1-4613-5693-6.
  39. ↑ Christian Blume. Optimized Collision Free Robot Move Statement Generation by the Evolutionary Software GLEAM. Real-World Applications of Evolutionary Computing. Springer. 2000. Vol. 1803. hlm. 330–341. doi:10.1007/3-540-45561-2_32. ISBN 978-3-540-67353-8.
  40. ↑ Claus Aranha. Application of a Memetic Algorithm to the Portfolio Optimization Problem. AI 2008: Advances in Artificial Intelligence. Springer Berlin Heidelberg. 2008. Vol. 5360. hlm. 512–521. doi:10.1007/978-3-540-89378-3_52. ISBN 978-3-540-89377-6.
  41. ↑ Evolutionary Computation in Economics and Finance. Physica-Verlag HD. 2002. Vol. 100. doi:10.1007/978-3-7908-1784-3. ISBN 978-3-7908-2512-1.
  42. ↑ J.D. Lohn. IEEE Antennas and Propagation Society Symposium, 2004. June 2004. Vol. 3. hlm. 2313–2316 Vol.3. doi:10.1109/APS.2004.1331834. ISBN 0-7803-8302-8.
  43. ↑ Gary Fogel. Evolutionary Computation in Bioinformatics. Elsevier. 2003. doi:10.1016/b978-1-55860-797-2.x5000-8. ISBN 978-1-55860-797-2.
  44. ↑ Wilfried Jakob. Applying Evolutionary Algorithms Successfully - A Guide Gained from Realworld Applications. KIT Scientific Publishing. 2021. Vol. 170. doi:10.5445/IR/1000135763.
  45. ↑ Wilfried Jakob. Applying Evolutionary Algorithms Successfully - A Guide Gained from Realworld Applications. KIT Scientific Publishing. 2021. Vol. 170. doi:10.5445/IR/1000135763.
  46. ↑ Darrell Whitley. An overview of evolutionary algorithms: practical issues and common pitfalls. Information and Software Technology. 2001. Vol. 43 (14). hlm. 817–831. doi:10.1016/S0950-5849(01)00188-4.
  47. ↑ A.E. Eiben. Introduction to Evolutionary Computing. Springer Berlin Heidelberg. 2015. hlm. 147–163. doi:10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1.
  48. ↑ Edd Gent. Artificial intelligence is evolving all by itself. Science AAAS. 13 April 2020.
  49. ↑ P.A. Simionescu. 2006 IEEE International Conference on Evolutionary Computation. 2006. hlm. 1647–1653. doi:10.1109/CEC.2006.1688506. ISBN 0-7803-9487-9.
  50. ↑ P.A. Simionescu. Computer Aided Graphing and Simulation Tools for AutoCAD Users. CRC Press. 2014. ISBN 978-1-4822-5290-3.

Sumber dan atribusi

Konten artikel ini diadaptasi dari Wikipedia bahasa Indonesia, revisi 29482607 (2026-07-21T09:22:18Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.


Diperoleh dari "https://wiki.unissula.ac.id/index.php?title=Algoritma_evolusioner&oldid=1172"