Lompat ke isi

Algoritma genetik

Dari Wikipedia bahasa Indonesia, ensiklopedia bebas

Algoritma genetik adalah teknik pencarian yang di dalam ilmu komputer untuk menemukan penyelesaian perkiraan untuk optimisasi dan masalah pencarian. Algoritma genetik adalah kelas khusus dari algoritme evolusioner dengan menggunakan teknik yang terinspirasi oleh biologi evolusioner seperti warisan, mutasi, seleksi alam dan rekombinasi (atau crossover)

Algoritma Genetik pertama kali dikembangkan oleh John Holland pada tahun 1970-an di New York, Amerika Serikat. Dia beserta murid-murid dan teman kerjanya menghasilkan buku berjudul "Adaption in Natural and Artificial Systems" pada tahun 1975.

Algoritma Genetik khususnya diterapkan sebagai simulasi komputer di mana sebuah populasi representasi abstrak (disebut kromosom) dari solusi-solusi calon (disebut individual) pada sebuah masalah optimisasi akan berkembang menjadi solusi-solusi yang lebih baik. Secara tradisional, solusi-solusi dilambangkan dalam biner sebagai string '0' dan '1', walaupun dimungkinkan juga penggunaan penyandian (encoding) yang berbeda. Evolusi dimulai dari sebuah populasi individual acak yang lengkap dan terjadi dalam generasi-generasi. Dalam tiap generasi, kemampuan keseluruhan populasi dievaluasi, kemudian multiple individuals dipilih dari populasi sekarang (current) tersebut secara stochastic (berdasarkan kemampuan mereka), lalu dimodifikasi (melalui mutasi atau rekombinasi) menjadi bentuk populasi baru yang menjadi populasi sekarang (current) pada iterasi berikutnya dari algoritma.

Sejarah

[sunting | sunting sumber]

Pada tahun 1950, Alan Turing mengusulkan sebuah “learning machine” yang akan berjalan sejajar dengan prinsip-prinsip evolusi.[1] Simulasi komputer mengenai evolusi mulai dilakukan sejak tahun 1954 melalui karya Nils Aall Barricelli, yang menggunakan komputer di Institute for Advanced Study di Princeton, New Jersey.[2][3] Publikasinya pada tahun 1954 tidak mendapat perhatian luas. Mulai tahun 1957, ahli genetika kuantitatif asal Australia, Alex Fraser, menerbitkan serangkaian makalah tentang simulasi seleksi buatan pada organisme dengan banyak lokus yang mengendalikan suatu sifat terukur. Dari awal inilah, simulasi komputer tentang evolusi oleh para biolog menjadi semakin umum pada awal 1960-an, dan metode-metodenya dijelaskan dalam buku Fraser dan Burnell (1970) serta Crosby (1973). Simulasi Fraser memasukkan semua elemen penting dari algoritma genetika modern. Selain itu, Hans-Joachim Bremermann menerbitkan serangkaian makalah pada 1960-an yang juga menggunakan populasi solusi untuk memecahkan masalah optimasi melalui rekombinasi, mutasi, dan seleksi. Penelitiannya juga memasukkan komponen-komponen yang kini dikenal sebagai algoritma genetika modern. Pelopor awal lain yang patut dicatat mencakup Richard Friedberg, George Friedman, dan Michael Conrad. Banyak makalah awal kemudian dicetak ulang oleh Fogel (1998).

Meskipun Barricelli, dalam karya yang ia laporkan pada tahun 1963, telah mensimulasikan evolusi kemampuan memainkan sebuah permainan sederhana, evolusi artifisial baru diakui luas sebagai metode optimasi berkat karya Ingo Rechenberg dan Hans-Paul Schwefel pada 1960-an dan awal 1970-an—kelompok Rechenberg berhasil memecahkan masalah-masalah rekayasa yang kompleks melalui strategi evolusi. Pendekatan lain adalah teknik pemrograman evolusioner dari Lawrence J. Fogel, yang diusulkan untuk menghasilkan kecerdasan buatan. Pemrograman evolusioner pada awalnya menggunakan mesin keadaan hingga untuk memprediksi lingkungan, lalu menggunakan variasi dan seleksi untuk mengoptimalkan logika prediktifnya. Algoritma genetika secara khusus menjadi populer melalui karya John Holland pada awal 1970-an, terutama melalui bukunya Adaptation in Natural and Artificial Systems (1975). Karyanya berakar pada studi mengenai sel automata yang dilakukan oleh Holland dan para mahasiswanya di University of Michigan. Holland memperkenalkan kerangka formal untuk memprediksi kualitas generasi berikutnya, yang dikenal sebagai Schema Theorem Holland. Penelitian mengenai algoritma genetika tetap bersifat teoretis hingga pertengahan 1980-an, ketika Konferensi Internasional Pertama tentang Algoritma Genetika diselenggarakan di Pittsburgh, Pennsylvania.[4]

Produk Komersial

[sunting | sunting sumber]

Pemanfaatan algoritma genetika dalam ranah komersial mulai mendapatkan momentum pada akhir dekade 1980-an. Salah satu tonggak awalnya adalah ketika General Electric memperkenalkan produk algoritma genetika pertama di dunia, berupa seperangkat perangkat lunak berbasis mainframe yang ditujukan untuk pengoptimalan proses industri. Langkah tersebut menandai masuknya teknologi evolusioner ke dalam praktik rekayasa berskala besar.

Perkembangan lebih lanjut terjadi pada tahun 1989 ketika Axcelis, Inc. meluncurkan Evolver, perangkat lunak algoritma genetika komersial pertama yang dapat digunakan pada komputer desktop. Keberadaannya menarik perhatian publik, termasuk liputan dari jurnalis teknologi The New York Times, John Markoff, pada tahun 1990. Selama beberapa tahun, Evolver menjadi satu-satunya perangkat algoritma genetika interaktif yang tersedia secara komersial, sebelum kemudian dijual kepada Palisade pada tahun 1997 dan dikembangkan hingga mencapai versi keenam.[5]

Prosedur Algoritma Genetik

[sunting | sunting sumber]

Algoritma genetik yang umum menyaratkan dua hal untuk didefinisikan: (1) representasi genetik dari penyelesaian, (2) fungsi kemampuan untuk mengevaluasinya.

Representasi baku adalah sebuah larik bit-bit. Larik jenis dan struktur lain dapat digunakan dengan cara yang sama. Hal utama yang membuat representasi genetik ini menjadi tepat adalah bahwa bagian-bagiannya mudah diatur karena ukurannya yang tetap, yang memudahkan operasi persilangan sederhana. Representasi panjang variabel juga digunakan, tetapi implementasi persilangan lebih kompleks dalam kasus ini. Representasi seperti pohon diselidiki dalam pemrograman genetik dan representasi bentuk bebas diselidiki di dalam HBGA.

Fungsi kemampuan didefinisikan di atas representasi genetik dan mengukur kualitas penyelesaian yang diwakili. Fungsi kemampuan selalu tergantung pada masalah. Sebagai contoh, jika pada ransel kita ingin memaksimalkan jumlah benda (objek) yang dapat kita masukkan ke dalamnya pada beberapa kapasitas yang tetap. Representasi penyelesaian mungkin berbentuk larik bits, di mana tiap bit mewakili objek yang berbeda, dan nilai bit (0 atau 1) menggambarkan apakah objek tersebut ada di dalam ransel atau tidak. Tidak setiap representasi seperti ini valid, karena ukuran objek dapat melebihi kapasitas ransel. Kemampuan penyelesaian adalah jumlah nilai dari semua objek di dalam ransel jika representasi itu valid, atau jika tidak 0. Dalam beberapa masalah, susah atau bahkan tidak mungkin untuk mendefinisikan lambang kemampuan, maka pada kasus ini digunakan IGA.

Sekali kita mendefinisikan representasi genetik dan fungsi kemampuan, algoritma genetik akan memproses inisialisasi populasi penyelesaian secara acak, dan memperbaikinya melalui aplikasi pengulangan dengan aplikasi operator-operator mutasi, persilangan, dan seleksi.

Secara sederhana, algoritma umum dari algoritma genetik ini dapat dirumuskan menjadi beberapa langkah, yaitu:

  1. Membentuk suatu populasi individual dengan keadaan acak
  2. Mengevaluasi kecocokan setiap individual keadaan dengan hasil yang diinginkan
  3. Memilih individual dengan kecocokan yang tertinggi
  4. Bereproduksi, mengadakan persilangan antar individual terpilih diselingi mutasi
  5. Mengulangi langkah 2 - 4 sampai ditemukan individual dengan hasil yang diinginkan

Metodologi

[sunting | sunting sumber]

Proses kerja algoritma genetika berlangsung melalui serangkaian tahapan yang dirancang untuk meniru mekanisme evolusi biologis. Setelah prinsip dasar mengenai representasi genetika, fungsi fitness, serta operator dasar ditetapkan, algoritma kemudian dijalankan melalui siklus berulang yang terdiri atas beberapa langkah utama. Setiap langkah memiliki peran penting dalam membentuk dinamika evolusi populasi kandidat solusi, mulai dari pembentukan populasi awal hingga evaluasi akhir yang menentukan kapan proses dihentikan. Tahapan-tahapan berikut menggambarkan mekanisme operasional algoritma genetika secara sistematis dan mendetail.

Inisialisasi

[sunting | sunting sumber]

Ukuran populasi bergantung pada sifat masalahnya, namun biasanya terdiri dari ratusan atau ribuan kemungkinan solusi. Sering kali, populasi awal dibangkitkan secara acak, sehingga mencakup seluruh rentang kemungkinan solusi (ruang pencarian). Dalam beberapa kasus, solusi dapat “ditanam” (seeded) pada area di mana solusi optimal kemungkinan ditemukan, atau distribusi peluang pengambilan sampel disesuaikan untuk memfokuskan pencarian pada area yang dianggap lebih penting.[6]

Seleksi

[sunting | sunting sumber]

Pada setiap generasi berikutnya, sebagian dari populasi yang ada dipilih untuk bereproduksi membentuk generasi baru. Solusi individu dipilih melalui proses berbasis kelayakan, di mana solusi yang lebih fit (diukur oleh fitness function / fungsi kelayakan) umumnya memiliki peluang lebih besar untuk dipilih. Beberapa metode seleksi menilai fitness setiap solusi dan memilih solusi terbaik secara preferensial. Metode lain hanya menilai sampel acak dari populasi, karena proses penilaian seluruh populasi dapat memakan waktu sangat lama.

Fitness function didefinisikan berdasarkan representasi genetika dan mengukur kualitas solusi yang direpresentasikan. Fitness function selalu bergantung pada masalah yang dipecahkan. Misalnya, pada masalah knapsack, tujuan utamanya adalah memaksimalkan total nilai objek yang dapat dimasukkan ke dalam tas berkapasitas tetap. Representasi solusi bisa berupa array bit, di mana setiap bit mewakili objek tertentu, dan nilainya (0 atau 1) menunjukkan apakah objek tersebut dimasukkan ke dalam tas. Tidak semua representasi semacam itu valid, karena ukuran objek dapat melebihi kapasitas tas. Kelayakan dari suatu solusi adalah jumlah nilai semua objek yang dimasukkan ke dalam tas jika representasinya valid, atau 0 jika tidak valid.

Pada beberapa masalah, sulit atau bahkan tidak mungkin untuk mendefinisikan fitness function secara eksplisit; dalam kasus tersebut, simulasi dapat digunakan untuk menentukan nilai fungsi fitness dari suatu fenotipe (misalnya, dinamika fluida komputasional digunakan untuk menentukan hambatan udara sebuah kendaraan yang bentuknya direpresentasikan sebagai fenotipe), atau bahkan digunakan interactive genetic algorithms.

Operator Genetika

[sunting | sunting sumber]

Langkah berikutnya adalah menghasilkan generasi kedua dari populasi solusi berdasarkan individu-individu yang terpilih, melalui kombinasi operator genetika: crossover (atau rekombinasi) dan mutasi.

Untuk setiap solusi baru yang akan dihasilkan, sepasang solusi “orang tua” dipilih dari kumpulan kandidat yang telah dipilih sebelumnya. Dengan menghasilkan solusi “anak” melalui metode crossover dan mutasi, diperoleh solusi baru yang biasanya mewarisi banyak karakteristik dari kedua “orang tua” tersebut. Pasangan orang tua baru dipilih untuk setiap anak berikutnya, dan proses ini berlanjut hingga populasi baru dengan ukuran yang sesuai terbentuk. Meskipun metode reproduksi yang menggunakan dua orang tua lebih “terinspirasi biologi”, beberapa penelitian[7][8] menunjukkan bahwa menggunakan lebih dari dua “orang tua” dapat menghasilkan kromosom dengan kualitas yang lebih tinggi.

Proses-proses tersebut pada akhirnya menghasilkan generasi berikutnya yang berbeda dari generasi awal. Secara umum, rata-rata fitness meningkat, karena hanya organisme terbaik dari generasi pertama yang dipilih untuk bereproduksi, ditambah sebagian kecil solusi yang kurang fit. Solusi yang kurang fit ini penting untuk menjaga keragaman genetika dalam kumpulan orang tua, sehingga memastikan keragaman genetika pada generasi berikutnya.

Pendapat para ahli terbagi mengenai pentingnya crossover dibanding mutasi. Banyak referensi dalam Fogel (2006) menunjukkan argumen yang mendukung pentingnya pencarian berbasis mutasi.

Meskipun crossover dan mutasi dikenal sebagai operator genetika utama, operator lain seperti regrouping, colonization-extinction, atau migration juga dapat digunakan dalam algoritma genetika.

Parameter seperti probabilitas mutasi, probabilitas crossover, dan ukuran populasi perlu disesuaikan agar sesuai dengan tingkat kompleksitas masalah yang dikerjakan. Laju mutasi yang terlalu kecil dapat menyebabkan genetic drift (yang bersifat non-ergodik). Tingkat rekombinasi yang terlalu tinggi dapat menyebabkan premature convergence. Laju mutasi yang terlalu besar dapat menghilangkan solusi yang baik, kecuali jika digunakan mekanisme seleksi elitis. Ukuran populasi yang memadai memastikan keragaman genetika yang cukup, tetapi jika terlalu besar dapat memboroskan sumber daya komputasi.

Heuristik

[sunting | sunting sumber]

Selain operator utama, berbagai heuristik lain dapat digunakan untuk mempercepat atau meningkatkan ketahanan perhitungan. Heuristik speciation memberi penalti pada crossover antara solusi kandidat yang terlalu mirip; pendekatan ini menjaga keragaman populasi dan membantu mencegah premature convergence menuju solusi yang kurang optimal.[9][10]

Terminasi

[sunting | sunting sumber]

Proses generasi ini diulang hingga suatu kondisi penghentian tercapai. Kondisi penghentian yang umum meliputi:

  • Sebuah solusi ditemukan yang memenuhi kriteria minimum.
  • Jumlah generasi yang telah ditentukan tercapai.
  • Anggaran yang dialokasikan (waktu/uang komputasi) telah habis.
  • Fitness dari solusi dengan peringkat tertinggi telah mencapai atau berada pada plateau sehingga iterasi berikutnya tidak menghasilkan peningkatan.
  • Penghentian berdasarkan inspeksi manual.
  • Kombinasi dari beberapa kondisi di atas.
  1. ↑ Turing, A. M. (1950-10-01). "I.—COMPUTING MACHINERY AND INTELLIGENCE". Mind (dalam bahasa Inggris). LIX (236): 433–460. doi:10.1093/mind/LIX.236.433. ISSN 1460-2113.
  2. ↑ Galloway, Alexander R. (2012-01). "The Computational Image of Organization: Nils Aall Barricelli". Grey Room. 46: 26–45. doi:10.1162/grey_a_00059. ISSN 1526-3819.
  3. ↑ Barricelli, Nils Aall (1962-03). "Numerical testing of evolution theories". Acta Biotheoretica. 16 (1–2): 69–98. doi:10.1007/bf01556771. ISSN 0001-5342.
  4. ↑ Rechenberg, Ingo (1973). Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Problemata, 15. Stuttgart-Bad Cannstatt: Frommann-Holzboog. ISBN 978-3-7728-0373-4.
  5. ↑ "Evolver™ 2.0 a genetic algorithm for spreadsheets". Computers & Mathematics with Applications. 26 (12): 94. 1993-12. doi:10.1016/0898-1221(93)90064-3. ISSN 0898-1221.
  6. ↑ Luque-Rodriguez, Maria; Molina-Baena, Jose; Jimenez-Vilchez, Alfonso; Arauzo-Azofra, Antonio (2022-11-27). "Initialization of Feature Selection Search for Classification". Journal of Artificial Intelligence Research (dalam bahasa Inggris). 75: 953–983. doi:10.1613/jair.1.14015. ISSN 1076-9757.
  7. ↑ Eiben, A. E.; Raué, P. -E.; Ruttkay, Zs. (1994). Genetic algorithms with multi-parent recombination. Berlin, Heidelberg: Springer Berlin Heidelberg. hlm. 78–87. ISBN 978-3-540-58484-1.
  8. ↑ Capcarrere, Mathieu S., ed. (2005). Advances in artificial life: 8th European Conference, ECAL 2005, Canterbury, UK, September 5-9, 2005: proceedings. Lecture notes in artificial intelligence. Berlin ; New York: Springer. ISBN 978-3-540-28848-0.
  9. ↑ Deb, Kalyanmoy; Spears, William M. Speciation methods. IOP Publishing Ltd. ISBN 0-7503-0895-8.
  10. ↑ Shir, Ofer M. (2012). Rozenberg, Grzegorz; Bäck, Thomas; Kok, Joost N. (ed.). Niching in Evolutionary Algorithms (dalam bahasa Inggris). Berlin, Heidelberg: Springer Berlin Heidelberg. hlm. 1035–1069. doi:10.1007/978-3-540-92910-9_32. isbn 9783540929093.. ISBN 978-3-540-92909-3.
Diperoleh dari "https://id.wikipedia.org/w/index.php?title=Algoritma_genetik&oldid=28701499"