Selasa, 14 April 2009

Algoritma Semut

Algoritma semut diperkenalkan oleh Moyson dan Manderick dan secara meluas dikembangkan oleh Marco Dorigo, merupakan teknik probabilistik untuk menyelesaikan masalah komputasi dengan menemukan jalur terbaik melalui grafik. Algoritma ini terinspirasi oleh perilaku semut dalam menemukan jalur dari koloninya menuju makanan.

Pada dunia nyata, semut berkeliling secara acak, dan ketika menemukan makanan mereka kembali ke koloninya sambil memberikan tanda dengan jejak feromon. Jika semut-semut lain menemukan jalur tersebut, mereka tidak akan bepergian dengan acak lagi, melainkan akan mengikuti jejak tersebut, kembali dan menguatkannya jika pada akhirnya merekapun menemukan makanan.

Seiring waktu, bagaimanapun juga jejak feromon akan menguap dan akan mengurangi kekuatan daya tariknya. Lebih lama seekor semut pulang pergi melalui jalur tersebut, lebih lama jugalah feromon menguap. Sebagai perbandingan, sebuah jalur yang pendek akan berbaris lebih cepat, dan dengan demikian kerapatan feromon akan tetap tinggi karena terletak pada jalur secepat penguapannya. Penguapan feromon juga mempunyai keuntungan untuk mencegah konvergensi pada penyelesaian optimal secara lokal. Jika tidak ada penguapan sama sekali, jalur yang dipilih semut pertama akan cenderung menarik secara berlebihan terhadap semut-semut yang mengikutinya. Pada kasus yang demikian, eksplorasi ruang penyelesaian akan terbatasi.

Oleh karena itu, ketika seekor semut menemukan jalur yang bagus (jalur yang pendek) dari koloni ke sumber makanan, semut lainnya akan mengikuti jalur tersebut, dan akhirnya semua semut akan mengikuti sebuah jalur tunggal. Ide algoritma koloni semut adalah untuk meniru perilaku ini melalui 'semut tiruan' berjalan seputar grafik yang menunjukkan masalah yang harus diselesaikan.

Algoritma optimisasi koloni semut telah digunakan untuk menghasilkan penyelesaian yang mendekati optimal pada masalah salesman yang melakukan perjalanan. Algoritma semut lebih menguntungkan daripada pendekatan penguatan tiruan (simulaten annealing) dan algoritma genetik saat grafik mungkin berubah secara dinamis; algoritma koloni semut dapat berjalan secara kontinyu dan menyesuaikan dengan perubahan secara waktu nyata (real time). Hal ini menarik dalam routing jaringan dan sistem transportasi urban.

Algoritma Genetika

Algoritma Genetika adalah salah satu algoritma metaheuristic yang biasa digunakan untuk melakukan pencarian solusi yang paling optimal (maximize atau minimize). Cara kerja algoritma ini mensimulasikan fenomena dari evolusi alam. Intinya adalah, spesies yang paling unggul akan memiliki kesempatan untuk bertahan hidup yang lebih besar.

Konsep dasar algoritma ini sebenarnya sederhana. Kromoson merepresentasikan sebuah solusi potensial terhadap sebuah masalah. Proses pencarian solusi potensial berikutnya dapat dibayangkan sebagai sebuah proses evolusi terhadap populasi dari kromosom.

Pada saat proses pencarian solusi potensial berikutnya, algoritma ini akan menselaraskan dua tujuan:

  • Eksploitasi solusi-solusi terbaik
  • Eksplorasi ruang pencarian

Keromantisan algoritma genetika terletak pada dua tujuan tersebut. Eksplorasi ruang pencarian ibaratnya seseorang yang sedang mencari pasangan. Dia akan memperluas “ruang pencarian” ketika dalam proses pencarian, tapi ketika sudah menemukan yang cocok, dia akan fokus terhadap yang satu itu dan “mengeksploitasi” (dalam arti mencoba lebih mengenal) pasangannya tersebut.

Tapi tentunya analogi tersebut tidak sepenuhnya cocok di dunia nyata. Karena, algoritma genetika akan terus mencari pada ruang pencarian, walau sudah menemukan solusi potensial, sampai menemukan kondisi berhenti.

Sumber

Tidak ada komentar:

Posting Komentar