Kekuatan Semut dan Program Komputer

903 views

Kekuatan Semut dan Program Komputer

Kekuatan Semut dan Program Komputer. Semut adalah binatang yang menakjubkan. Jatuhkan sesuatu yang enak di lantai dan mereka akan dengan cepat membangun jalan raya yang efisien dari sarang mereka ke makanan tersebut dan kembali untuk membawa pulang potongan makanan. Mereka dapat melakukan ini meskipun sangat tidak mempunyai penglihatan mata, tidak ada bisa bersuara untuk berbicara satu sama lain.

Kekuatan Semut dan Program Komputer

Begitu luar biasa kemampuan ini sehingga pada tahun 1990-an para ilmuwan komputer mulai bertanya-tanya apakah mereka dapat meniru perilaku semut dalam program komputer yang dirancang untuk memecahkan masalah yang kompleks.

Saat ini, algoritma optimisasi koloni semut (ACOs) banyak digunakan untuk menyelesaikan masalah di mana banyak komponen perlu dikombinasikan dengan beberapa cara optimal: apakah itu memutuskan rute pengiriman armada truk atau jadwal dokter di rumah sakit.

Kekuatan Semut dan Program Komputer
Semut sangat pandai membentuk jalan

Bagaimana semut melakukannya?

Semut berkomunikasi menggunakan zat kimia yang disebut feromon. “Ketika semut bergerak, mereka dapat meninggalkan feromon di tanah,” jelas Marco Dorigo dari Université Libre de Bruxelles, yang mengemukakan gagasan ACO dalam tesis PhD-nya dan telah ikut menulis buku seminal tentang topik tersebut. “Dan jika mereka merasakan [jejak] feromon sudah ada di tanah, mereka memiliki kemungkinan lebih tinggi untuk mengikuti jejak itu daripada pergi ke arah yang berbeda.” Jika cukup banyak semut yang menyukai jejak tertentu, putaran umpan balik terjadi: feromon yang telah mereka simpan akan menarik lebih banyak semut ke jejak, yang meningkatkan konsentrasi feromon di sepanjang jejaknya, yang pada gilirannya akan menarik lebih banyak semut.

Menariknya, para ahli biologi telah menunjukkan bahwa mekanisme ini sendiri dapat memungkinkan semut untuk secara kolektif menemukan rute pendek antara sumber makanan dan sarang mereka. Pada 1990, Jean-Louis Deneubourg dan koleganya menawarkan koloni semut dua rute yang menghubungkan sarang mereka ke daerah yang belum mereka jelajahi dan di mana mereka bisa menemukan makanan. Dalam satu percobaan salah satu rute dua kali lebih panjang dari yang lain dan ternyata, pada sebagian besar percobaan, semua semut akhirnya memilih jalur yang lebih pendek.

Pilihan ini tentu saja bisa karena kemampuan naluri semut untuk mengukur jarak. Jika ini masalahnya, maka kita tidak akan berharap semut lebih suka satu rute daripada yang lain jika kedua rute sama-sama panjang. Tetapi dalam percobaan di mana kedua jalur memiliki panjang semut yang sama juga akhirnya lebih memilih satu rute dari yang lain.

“Ahli biologi telah menunjukkan bahwa kita dapat menjelaskan perilaku ini hanya dari feromon saja,” kata Dorigo. Awalnya semut akan membuat pilihan acak tentang jalur mana yang harus diambil, tetapi begitu satu rute memiliki lebih banyak feromon daripada yang lain, mereka akan memilih yang itu. Ketika satu rute dua kali lebih panjang dari yang lain, maka yang lebih pendek akan dengan cepat mengumpulkan lebih banyak feromon: semut yang bepergian di rute pendek akan menjadi yang pertama untuk mencapai sumber makanan dan untuk memulai perjalanan mereka kembali ke rumah, menelusuri kembali langkah-langkah mereka. Dengan cara ini, rute yang lebih pendek mengumpulkan feromon lebih cepat dan umpan balik positif muncul.

Ketika kedua jalur memiliki panjang yang sama, semut akan secara acak memilih jalur yang akan diambil dengan peluang 50:50. Tetapi seperti membalik koin yang adil beberapa kali tidak akan memberi kita tepat 50% kepala dan 50% ekor, fluktuasi acak akan menyebabkan salah satu dari dua jalur untuk mengambil lebih banyak feromon.

Deneubourg dan rekan-rekannya menghasilkan model matematika yang menggambarkan mekanisme feromon. Dalam model, kemungkinan seekor semut memilih salah satu jalur tergantung pada jumlah feromon yang sudah ada di dalamnya. Menjalankan model di komputer, para ilmuwan menemukan persis perilaku yang ditampilkan oleh semut nyata.

Semua ini adalah contoh dari sesuatu yang disebut stigmergy: individu, dalam hal ini semut, membuat tanda pada lingkungan mereka yang kemudian memandu tindakan individu lain. Umpan balik menghasilkan yang kemudian mengarah pada munculnya perilaku yang tampaknya terkoordinasi dan sistematis – dalam hal ini, memilih rute cepat.

Mengapa manusia melakukannya?

“Dalam percobaan Deneubourg, semut menyelesaikan masalah optimisasi,” kata Dorigo. “Ini masalah optimasi sederhana bagi kita manusia, karena ketika manusia melihat (pilihan antara dua jalur) mereka segera tahu mana yang lebih pendek. Tapi ada banyak masalah [lain] di dunia nyata yang dapat dimodelkan sebagai apa yang disebut masalah optimisasi kombinatorial. “
 
Kekuatan Semut dan Program Komputer
Marco Dorigo
Salah satu contohnya adalah rute kendaraan. Kita memiliki armada truk dan barang yang disimpan di sejumlah depot yang perlu dikirim ke sejumlah pelanggan di lokasi tertentu. Rute apa yang harus diambil truk untuk meminimalkan biaya transportasi, sambil tetap berpegang pada beberapa kendala tambahan, misalnya semua truk harus kembali ke rumah pada malam hari?
Ketika kita memiliki beberapa truk maka mungkin kita dapat menemukan solusi yang optimal, tetapi karena jumlah truk bertambah masalah menjadi terlalu sulit bahkan untuk komputer yang paling kuat. Waktu yang dibutuhkan algoritma komputer mana pun yang dikenal untuk menemukan solusinya segera melampaui usia Alam Semesta. “Jelas Dorigo. (Faktanya, masalah perutean kendaraan adalah apa yang oleh para ahli teori kompleksitas disebut “NP keras”, dapat menemukan lebih banyak di sini.) Banyak masalah lain yang melibatkan pengaturan waktu atau penjadwalan sama sulitnya.
 

Kesamaan dari masalah-masalah semacam ini, terlepas dari kesulitan mereka, adalah bahwa mereka semua dapat terwakili dalam suatu jaringan. Dalam kasus truk, jaringan hanyalah jaringan jalan yang menghubungkan semua tempat truk harus pergi. Untuk masalah lain, pengaturan representasi jaringan memerlukan sedikit lebih banyak pekerjaan, tetapi begitu dibangun, memberikan deskripsi masalah yang jelas dan ringkas. 

Baigamana Komputer Melakukan Ini

Gagasan di balik optimasi koloni semut adalah untuk membuat algoritma yang meniru perilaku semut untuk menemukan solusi yang optimal, atau hampir optimal, untuk masalah tersebut. Diberi masalah dunia nyata, kita mulai dengan menerjemahkannya ke masalah optimisasi pada jaringan. Jaringan dengan mudah direpresentasikan dalam komputer, demikian juga semut buatan, yang disebut agen, bergerak di atasnya. Tempat feromon diambil oleh “feromon buatan”, yaitu, angka yang terkait dengan tautan di jaringan: semakin tinggi angkanya, semakin banyak feromon yang dikaitkan dengan tautan tersebut.

Kekuatan Semut dan Program Komputer
Foto Jarak dekat dari Seekor Semut

Sistem ini dimulai dengan jumlah kecil feromon buatan yang sama pada semua mata rantai dan para agen membuat pilihan acak tentang mata rantai mana yang mereka bawa. Ketika agen telah menemukan solusi, misalnya jalur dari simpul awal ke simpul akhir, ia akan mengevaluasi kualitas larutan. Kemudian akan menambahkan sejumlah feromon buatan ke tautan yang terkandung dalam larutan yang sebanding dengan kualitas larutan. Jumlah feromon buatan yang dikaitkan dengan tautan bias pilihan agen buatan yang duduk di simpul yang terhubung ke tautan itu: semakin banyak feromon, semakin tinggi kemungkinan agen memilih untuk melakukan perjalanan menuruni tautan itu.

“Jika kita seorang agen buatan yang duduk di sebuah simpul, pada awalnya pilihan yang saya miliki semuanya sama, jadi saya membuat pilihan acak,” jelas Dorigo. “Setelah beberapa saat beberapa tepi akan memiliki lebih banyak feromon karena mereka telah digunakan lebih banyak atau karena mereka termasuk dalam solusi yang lebih baik daripada yang lain. Kemudian saya memiliki probabilitas sedikit lebih tinggi untuk memilih tepi-tepi itu. Ini berlangsung sepanjang waktu, dengan banyak agen secara paralel, dan pada titik tertentu sistem menemukan solusi yang baik. “

Menggunakan ide ini Dorigo, Gianni Di Caro dan Luca Gambardella telah mengembangkan, tidak hanya satu algoritma untuk memecahkan masalah tertentu, tetapi seluruh kerangka kerja yang dapat disesuaikan dengan masalah optimasi kombinatorial apa pun yang ingin kita pecahkan.

Seberapa baik komputer melakukannya?

Cukup bagus, dalam latihan. Optimalisasi koloni semut ada di sana dengan algoritma state-of-the-at yang digunakan untuk memecahkan masalah optimisasi kombinatorial kehidupan nyata yang sulit. Idealnya, ilmuwan komputer seperti Dorigo ingin membuktikan secara matematis bahwa algoritma berkinerja baik, misalnya dengan menunjukkan bahwa waktu yang dibutuhkan untuk algoritma seperti itu untuk menemukan solusi yang baik untuk masalah (misalnya truk penjadwalan) tidak tumbuh dengan cepat dengan ukuran masalah (mis. jumlah truk).

Kekuatan Semut dan Program Komputer
Semut lebih kuat dari yang kita kira … meskipun mereka perlu bertindak secara kolektif untuk mencapai kekuatan itu.

Namun sejauh ini, hasil teorinya lemah. Semua yang dapat ditunjukkan oleh para ahli teori secara umum adalah bahwa, mengingat jumlah waktu yang tak terbatas, algoritma optimisasi koloni semut akan menemukan solusi optimal untuk masalah yang telah mereka pecahkan.

“Ini sepertinya hasil yang sangat tidak berguna,” aku Dorigo. Jumlah waktu yang tidak terbatas adalah apa yang tidak dimiliki orang yang mencoba memecahkan masalah pengoptimalan dunia nyata. Tetapi ada satu titik pada hasilnya: dalam teori bisa saja algoritma tidak pernah menemukan solusi optimal. Setidaknya kemungkinan itu telah dikesampingkan. Untuk beberapa algoritma tertentu di dalam kelas optimasi koloni semut, ada hasil teoritis tentang seberapa cepat mereka menemukan solusi yang optimal, tetapi ini adalah persis yang kinerjanya buruk dalam praktiknya. “Ini tidak hanya berlaku untuk optimasi koloni semut, tetapi untuk sebagian besar kerangka kerja algoritmik yang dirancang untuk menyelesaikan masalah optimisasi kombinatorial.” kata Dorigo.

Masih ada juga tantangan menarik tentang sisi praktis ACOs. Saat ini, jika kita ingin menggunakan framework, Anda harus mencari tahu sendiri mana dari keluarga algoritma ACOs yang paling cocok untuk masalah Anda. “Satu arah penelitian yang sangat menjanjikan adalah membuat proses ini otomatis,” kata Dorigo. Ini berarti membangun sebuah algoritma yang, mengingat masalah tertentu, menemukan algoritma ACOs terbaik untuk kita gunakan.

Jadi, makhluk-makhluk kecil itu, yang tidak selalu kita lihat dengan simpati, tidak hanya mengilhami cara memecahkan masalah yang rumit, tetapi juga menimbulkan masalah yang menantang untuk melatih pikiran generasi peneliti baru.

Demikian Kekuatan Semut dan Program Komputer

Sebelumnya Keindahan Segitiga Ajaib 3 x 3

Tinggalkan Balasan

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *

Situs ini menggunakan Akismet untuk mengurangi spam. Pelajari bagaimana data komentar Anda diproses.