Lompat ke isi

Algoritma evolusioner: Perbedaan antara revisi

Ensiklopedia Pengetahuan Universitas Islam Sultan Agung

Maintenance script (bicara | kontrib)

37.956 suntingan
Maintenance script (bicara | kontrib)
37.956 suntingan
Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 29482607; atribusi sumber disertakan.
 
Maintenance script (bicara | kontrib)
37.956 suntingan
Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi
 
Baris 1: Baris 1:
'''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 genetika|rekombinasi]], dan [[Seleksi alam|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''' ([[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.<ref>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.</ref> Selain itu, EA juga merupakan bagian dari [[komputasi evolusioner]] yang merupakan cabang dari kecerdasan komputasional.<ref>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.</ref> Mekanisme utama evolusi biologis yang ditiru oleh EA adalah [[reproduksi]], [[mutasi]], [[Rekombinasi genetika|rekombinasi]], dan [[Seleksi alam|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.
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.<ref>J. P. Cohoon. [https://www.ifte.de/mitarbeiter/lienig/cohoon.pdf "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.</ref> 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.<ref>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.</ref><ref>Marek Mika. [http://link.springer.com/10.1007/s10951-009-0158-0 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.</ref><ref>[https://www.evostar.org/ International Conference on the Applications of Evolutionary Computation]. The conference is part of the Evo* series. The conference proceedings are published by Springer.</ref> Oleh karena itu, tidak selalu terdapat hubungan langsung antara kompleksitas algoritma dengan kompleksitas masalah.


== Definisi umum ==
== Definisi umum ==
Berikut ini adalah contoh algoritma evolusi yang umum:
Berikut ini adalah contoh algoritma evolusi yang umum:<ref>Thomas Jansen. [https://dl.acm.org/doi/abs/10.1145/1276958.1277148 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.</ref><ref>Yaochu Jin. [https://link.springer.com/chapter/10.1007/978-3-7908-1771-3_2 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.</ref><ref>Jorge Tavares. [https://link.springer.com/chapter/10.1007/978-3-540-24650-3_37 Genetic Programming]. Springer. 2004. Vol. 3003. hlm. 389–398. doi:10.1007/978-3-540-24650-3_37. ISBN 978-3-540-21346-8.</ref>


# Menghasilkan populasi awal (generasi pertama) individu secara acak.
# Menghasilkan populasi awal (generasi pertama) individu secara acak.
Baris 18: Baris 18:
Teknik-teknik yang serupa biasanya berbeda dalam hal representasi genetik maupun implementasi detail lainnya, serta bergantung pada sifat masalah yang diterapkan.
Teknik-teknik yang serupa biasanya berbeda dalam hal representasi genetik maupun implementasi detail lainnya, serta bergantung pada sifat masalah yang diterapkan.


* [[Algoritma genetik]]a – 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 [[Optimisasi|optimasi]] .
* [[Algoritma genetik]]a – Jenis EA yang paling populer. Solusi direpresentasikan dalam bentuk rangkaian angka (biasanya biner, meskipun representasi terbaik biasanya yang mencerminkan masalah yang sedang dipecahkan),<ref>J. P. Cohoon. [https://www.ifte.de/mitarbeiter/lienig/cohoon.pdf "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). [https://www.ifte.de/mitarbeiter/lienig/cohoon.pdf ''"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 .</ref> dengan menerapkan operator seperti rekombinasi dan mutasi (terkadang salah satu dan terkadang keduanya). Jenis EA ini sering digunakan dalam masalah [[Optimisasi|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 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 genetika Cartesian]]
Baris 26: Baris 26:
** [[Pemrograman multi ekspresi]]
** [[Pemrograman multi ekspresi]]
* [[Pemrograman evolusioner]] – Mirip dengan strategi evolusi, tetapi menggunakan seleksi deterministik untuk semua orang tua.
* [[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.
* 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.<ref>Volker Nissen. [https://link.springer.com/chapter/10.1007/978-3-642-79386-8_5 Fuzzy Logik]. Springer. 1994. hlm. 33–40. doi:10.1007/978-3-642-79386-8_5. ISBN 978-3-642-79386-8.</ref><ref>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.</ref><ref>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.</ref>
** CMA-ES
** CMA-ES
** Strategi evolusi alami
** Strategi evolusi alami
* [[Evolusi diferensial]] – Berdasarkan selisih vektor sehingga cocok untuk masalah [[Optimisasi|optimasi numerik]] .
* [[Evolusi diferensial]] – Berdasarkan selisih vektor sehingga cocok untuk masalah [[Optimisasi|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.
* [[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.<ref>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.</ref><ref>Elena Popovici. [https://link.springer.com/referenceworkentry/10.1007/978-3-540-92910-9_31 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.</ref>
* [[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.
* [[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).
* [[Sistem pengklasifikasi belajar]] (''Learning classifier system'', LCS) – Solusi berupa seperangkat pengklasifikasi (aturan atau kondisi).
** [[Michigan-LCS]] berevolusi pada level pengklasifikasi individual.
** [[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 [[Pemelajaran terarah|pembelajaran terawasi]].
** 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 [[Pemelajaran terarah|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.
* [[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.<ref>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.</ref><ref>Joel Lehman. [http://dx.doi.org/10.1145/2001576.2001606 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.</ref><ref>Antoine Cully. [http://dx.doi.org/10.1038/nature14422 Robots that can adapt like animals]. ''Nature''. 2015-05-27. Vol. 521 (7553). hlm. 503–507. doi:10.1038/nature14422.</ref>


== Latar belakang teoretis ==
== Latar belakang teoretis ==
Baris 41: Baris 41:


=== Teorema tidak ada makan siang gratis ===
=== 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.
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.<ref>Lawrence Davis. [https://archive.org/details/handbookofgeneti0000unse_w2h0 Handbook of genetic algorithms]. Van Nostrand Reinhold. 1991. ISBN 0-442-00173-8.</ref><ref>Jens Lienig. [http://link.springer.com/10.1007/3-540-58484-6_301 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.</ref> 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.<ref>Lawrence Davis. [https://archive.org/details/handbookofgeneti0000unse_w2h0 Handbook of genetic algorithms]. Van Nostrand Reinhold. 1991. ISBN 0-442-00173-8.</ref><ref>[http://link.springer.com/10.1007/978-3-642-23247-3 Handbook of Memetic Algorithms]. Springer Berlin Heidelberg. 2012. Vol. 379. doi:10.1007/978-3-642-23247-3. ISBN 978-3-642-23246-6.</ref>


=== Konvergensi ===
=== Konvergensi ===
Baris 52: Baris 52:
Artinya, nilai kebugaran (''fitness value'') merepresentasikan sebuah [[barisan]] yang [[Fungsi monoton|monotonik]] tak-menurun yang dibatasi oleh keberadaan optimum. Dari sini, maka barisan tersebut berkonvergensi menuju optimum.
Artinya, nilai kebugaran (''fitness value'') merepresentasikan sebuah [[barisan]] yang [[Fungsi monoton|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.
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.<ref>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.</ref> 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.<ref>Martina Gorges-Schleuter. [http://link.springer.com/10.1007/BFb0056879 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.</ref><ref>Bernabe Dorronsoro. [http://link.springer.com/10.1007/978-0-387-77610-1 Cellular Genetic Algorithms]. Springer US. 2008. Vol. 42. doi:10.1007/978-0-387-77610-1. ISBN 978-0-387-77609-5.</ref>


=== Alfabet virtual ===
=== 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.
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.<ref>David E. Goldberg. [http://link.springer.com/10.1007/BFb0029726 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.</ref> 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.<ref>J. Stender. ''Genetic algorithms in optimisation, simulation, and modelling''. IOS Press. 1994. ISBN 90-5199-180-0.</ref><ref>Zbigniew Michalewicz. [https://archive.org/details/geneticalgorithm0000mich Genetic Algorithms + Data Structures = Evolution Programs]. Springer. 1996. ISBN 978-3-662-03315-9.</ref>


== Aplikasi ==
== 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.
Bidang-bidang yang algoritma evolusi digunakan secara praktis hampir tidak terbatas<ref>[https://www.evostar.org/ International Conference on the Applications of Evolutionary Computation]. The conference is part of the Evo* series. The conference proceedings are published by Springer.</ref> dan berkisar dari industri,<ref>Ernesto Sanchez. [http://link.springer.com/10.1007/978-3-642-27467-1 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.</ref><ref>[https://www.wiley.com/en-us/Evolutionary+Algorithms+in+Engineering+and+Computer+Science%3A+Recent+Advances+in+Genetic+Algorithms%2C+Evolution+Strategies%2C+Evolutionary+Programming%2C+Genetic+Programming+and+Industrial+Applications-p-9780471999027 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.</ref> teknik,<ref>J. P. Cohoon. [https://www.ifte.de/mitarbeiter/lienig/cohoon.pdf "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.</ref><ref>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.</ref><ref>Mitsuo Gen. [http://doi.wiley.com/10.1002/9780470172261 Genetic Algorithms and Engineering Optimization]. John Wiley & Sons, Inc. 1999-12-17. doi:10.1002/9780470172261. ISBN 978-0-470-17226-1.</ref> penjadwalan kompleks,<ref>Marek Mika. [http://link.springer.com/10.1007/s10951-009-0158-0 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.</ref><ref>Keshav P. Dahal. ''Evolutionary scheduling''. Springer. 2007. doi:10.1007/978-3-540-48584-1. ISBN 978-3-540-48584-1.</ref><ref>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.</ref> pertanian,<ref>David G. Mayer. [http://link.springer.com/10.1007/978-1-4615-1717-7 Evolutionary Algorithms and Agricultural Systems]. Springer US. 2002. doi:10.1007/978-1-4615-1717-7. ISBN 978-1-4613-5693-6.</ref> perencanaan pergerakan robot,<ref>Christian Blume. [http://link.springer.com/10.1007/3-540-45561-2_32 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.</ref> keuangan<ref>Claus Aranha. [http://link.springer.com/10.1007/978-3-540-89378-3_52 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.</ref><ref>[http://link.springer.com/10.1007/978-3-7908-1784-3 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.</ref> hingga penelitian<ref>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.</ref><ref>Gary Fogel. [https://linkinghub.elsevier.com/retrieve/pii/B9781558607972X50008 Evolutionary Computation in Bioinformatics]. Elsevier. 2003. doi:10.1016/b978-1-55860-797-2.x5000-8. ISBN 978-1-55860-797-2.</ref> 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.<ref>Wilfried Jakob. [https://publikationen.bibliothek.kit.edu/1000135763/121278298 Applying Evolutionary Algorithms Successfully - A Guide Gained from Realworld Applications]. KIT Scientific Publishing. 2021. Vol. 170. doi:10.5445/IR/1000135763.</ref> Sejumlah publikasi telah ditulis khusus untuk pemula, dengan tujuan membantu menghindari kesalahan dasar dan meningkatkan peluang keberhasilan proyek aplikasi EA.<ref>Wilfried Jakob. [https://publikationen.bibliothek.kit.edu/1000135763/121278298 Applying Evolutionary Algorithms Successfully - A Guide Gained from Realworld Applications]. KIT Scientific Publishing. 2021. Vol. 170. doi:10.5445/IR/1000135763.</ref><ref>Darrell Whitley. [https://linkinghub.elsevier.com/retrieve/pii/S0950584901001884 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.</ref><ref>A.E. Eiben. [http://link.springer.com/10.1007/978-3-662-44874-8 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.</ref> Publikasi ini umumnya menekankan pertanyaan mendasar: kapan sebuah masalah sebaiknya diselesaikan dengan algoritma evolusioner, dan kapan lebih baik menggunakan pendekatan lain.


== Contoh ==
== Contoh ==
Pada tahun 2020, [[Google]] menyatakan bahwa AutoML-Zero mereka berhasil menemukan kembali algoritma klasik seperti konsep jaringan saraf.
Pada tahun 2020, [[Google]] menyatakan bahwa AutoML-Zero mereka berhasil menemukan kembali algoritma klasik seperti konsep jaringan saraf.<ref>Edd Gent. [https://www.science.org/content/article/artificial-intelligence-evolving-all-itself Artificial intelligence is evolving all by itself]. ''Science AAAS''. 13 April 2020.</ref>


[[Simulasi komputer]] ''Tierra'' dan ''Avida'' mencoba memodelkan dinamika [[makroevolusi]] .
[[Simulasi komputer]] ''Tierra'' dan ''Avida'' mencoba memodelkan dinamika [[makroevolusi]] .


== Galeri ==
== Galeri ==
 
<ref>P.A. Simionescu. [http://faculty.tamucc.edu/psimionescu/PDFs/WCCI2006-Paper7204(1).pdf 2006 IEEE International Conference on Evolutionary Computation]. 2006. hlm. 1647–1653. doi:10.1109/CEC.2006.1688506. ISBN 0-7803-9487-9.</ref><ref>P.A. Simionescu. ''Computer Aided Graphing and Simulation Tools for AutoCAD Users''. CRC Press. 2014. ISBN 978-1-4822-5290-3.</ref>
 
== Referensi ==
 


== Bibliografi ==
== Bibliografi ==
* Ashlock, D. (2006), ''Evolutionary Computation for Modeling and Optimization'', Springer, New York, [[doi:10.1007/0-387-31909-3]]  .
* Ashlock, D. (2006), ''Evolutionary Computation for Modeling and Optimization'', Springer, New York, [[doi:10.1007/0-387-31909-3]]  .
* 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. (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, .
Baris 81: Baris 77:
* Holland, J. H. (1992), ''[https://books.google.com/books?id=5EgGaBkwvWcC Adaptation in Natural and Artificial Systems]'', MIT Press, Cambridge, MA, .
* 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, , [[doi:10.1007/978-3-662-07807-5]].
* Michalewicz, Z.; Fogel, D.B. (2004), ''How To Solve It: Modern Heuristics''. Springer, Berlin, Heidelberg, , [[doi:10.1007/978-3-662-07807-5]].
*
*  
*
*  
* Price, K., Storn, R.M., Lampinen, J.A., (2005). [https://books.google.com/books?id=hakXI-dEhTkC ''Differential Evolution: A Practical Approach to Global Optimization''], Springer, Berlin, Heidelberg, , [[doi:10.1007/3-540-31306-0]].
* Price, K., Storn, R.M., Lampinen, J.A., (2005). [https://books.google.com/books?id=hakXI-dEhTkC ''Differential Evolution: A Practical Approach to Global Optimization''], Springer, Berlin, Heidelberg, , [[doi:10.1007/3-540-31306-0]].
* Ingo Rechenberg (1971), ''Evolutionsstrategie - Optimierung technischer Systeme nach Prinzipien der biologischen Evolution'' (PhD thesis). Reprinted by Fromman-Holzboog (1973). [[ISBN (identifier)|ISBN]]&nbsp;[[Special:BookSources/3-7728-1642-8|<bdi>3-7728-1642-8</bdi>]]
* Ingo Rechenberg (1971), ''Evolutionsstrategie - Optimierung technischer Systeme nach Prinzipien der biologischen Evolution'' (PhD thesis). Reprinted by Fromman-Holzboog (1973). [[ISBN (identifier)|ISBN]]&nbsp;[[Special:BookSources/3-7728-1642-8|<bdi>3-7728-1642-8</bdi>]]
* Hans-Paul Schwefel (1974), ''Numerische Optimierung von Computer-Modellen'' (PhD thesis). Reprinted by Birkhäuser (1977).
* 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 (identifier)|ISBN]]&nbsp;[[Special:BookSources/0-471-57148-2|<bdi>0-471-57148-2</bdi>]]
* Hans-Paul Schwefel (1995), ''[https://www.researchgate.net/publication/220690578_Evolution_and_Optimum_Seeking Evolution and Optimum Seeking]''. Wiley & Sons, New York. [[ISBN (identifier)|ISBN]]&nbsp;[[Special:BookSources/0-471-57148-2|<bdi>0-471-57148-2</bdi>]]
* Simon, D. (2013), [http://academic.csuohio.edu/simond/EvolutionaryOptimization ''Evolutionary Optimization Algorithms''] , Wiley & Sons,
* Simon, D. (2013), [http://academic.csuohio.edu/simond/EvolutionaryOptimization ''Evolutionary Optimization Algorithms''] , Wiley & Sons,  
* Kruse, Rudolf; Borgelt, Christian; Klawonn, Frank; Moewes, Christian; Steinbrecher, Matthias; Held, Pascal (2013), [https://books.google.com/books?id=yQVGAAAAQBAJ ''Computational Intelligence: A Methodological Introduction'']. Springer, London. [[ISBN (identifier)|ISBN]]&nbsp;[[Special:BookSources/978-1-4471-5012-1|<bdi>978-1-4471-5012-1</bdi>]], [[doi:10.1007/978-1-4471-5013-8]].
* Kruse, Rudolf; Borgelt, Christian; Klawonn, Frank; Moewes, Christian; Steinbrecher, Matthias; Held, Pascal (2013), [https://books.google.com/books?id=yQVGAAAAQBAJ ''Computational Intelligence: A Methodological Introduction'']. Springer, London. [[ISBN (identifier)|ISBN]]&nbsp;[[Special:BookSources/978-1-4471-5012-1|<bdi>978-1-4471-5012-1</bdi>]], [[doi:10.1007/978-1-4471-5013-8]].
*
*  


== Pranala luar ==
== Pranala luar ==
* [https://www.staracle.com/general/evolutionaryAlgorithms.php Tinjauan Umum Sejarah dan Ragam Algoritma Evolusi]
* [https://www.staracle.com/general/evolutionaryAlgorithms.php Tinjauan Umum Sejarah dan Ragam Algoritma Evolusi]


 
== Referensi ==
<references />


== Sumber dan atribusi ==
== Sumber dan atribusi ==


Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Algoritma+evolusioner&oldid=29482607 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.
Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Algoritma+evolusioner&oldid=29482607 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.
<!-- WIKI_UNISSULA_PRESENTATION_V4 -->

Revisi terkini sejak 23 Agustus 2026 04.15

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"