Pemodelan Ant Colony Optimization untuk Masalah Task Allocation dalam Sistem Multi-Agen dengan Multi-Target
Date
2022Author
Rodiah, Iis
Hardhienata, Medria Kusuma Dewi
Buono, Agus
Metadata
Show full item recordAbstract
Masalah task allocation dalam sistem multi-agen dapat dipandang sebagai suatu masalah optimasi dalam mengalokasikan sejumlah agen terhadap tugas. Terdapat beberapa pendekatan yang dapat digunakan untuk menyelesaikan masalah optimasi tersebut dan salah satunya adalah metode heuristik seperti algoritme Ant Colony Optimization (ACO). Penelitian terdahulu menunjukkan bahwa algoritme ACO dengan modifikasi pada fungsi heuristik memiliki kinerja lebih baik dalam meminimumkan biaya penyelesaian tugas suatu masalah task allocation sistem multi-agen daripada algoritme ACO dasar. Meskipun demikian, penerapan algoritme ACO dengan modifikasi tersebut belum mempertimbangkan kondisi ketika terdapat lebih dari satu tugas yang harus diselesaikan. Ketika terdapat lebih dari satu tugas, masalah optimasi yang ada berkembang menjadi masalah optimasi alokasi agen-agen heterogen terhadap lebih dari satu tugas yang membutuhkan berbagai macam kemampuan. Salah satu kendala yang timbul dalam masalah optimasi tersebut adalah overlapping agent yang harus diminimumkan agar penyelesaian semua tugas dapat dilakukan secepat mungkin.
Untuk menyelesaikan masalah task allocation sistem multi-agen dengan multi-target, penelitian ini mengembangkan algoritme ACO dengan memodifikasi beberapa elemen yaitu konstruksi kandidat solusi, fungsi heuristik dan fungsi efisiensi. Kinerja dari algoritme ACO hasil modifikasi pada penelitian ini dioptimumkan dengan meminimumkan biaya penyelesaian tugas dan juga meminimumkan overlapping agent. Selain itu, kemampuan sistem secara keseluruhan juga dimaksimumkan untuk meningkatkan efisiensi koalisi agen. Simulasi menunjukkan bahwa algoritme ACO hasil modifikasi mempunyai kinerja yang lebih baik dari algoritme pembanding dalam menurunkan biaya penyelesaian tugas sebesar ±11.87%. Algoritme pembanding yang dimaksud yaitu algoritme ACO yang telah dikembangkan pada penelitian sebelumnya untuk menyelesaikan masalah task allocation sistem multi-agen. Selain itu, hasil simulasi juga menunjukkan bahwa algoritme ACO hasil modifikasi pada penelitian ini memiliki keunggulan yang signifikan dalam meminimumkan overlapping agent dengan menurunkan bobot overlapping sebesar ±55.11%. Dari hasil tersebut dapat disimpulkan bahwa algoritme ACO yang diusulkan pada penelitian ini dapat digunakan untuk menyelesaikan masalah task allocation dalam sistem multi-agen untuk multi-target. Task allocation in multi-agent system can be defined as an optimization problem in allocating several agents to the task. There are several approaches to solving the problem and one of them is heuristic method such as Ant Colony Optimization (ACO) algorithm. Preceding studies have shown that the ACO algorithm with modifications especially to the heuristic function has better performance in minimizing the task completion cost of task allocation problem in multi-agent system than the basic ACO algorithm. However, the application of those modified ACO algorithms had not considered the condition when there is more than one task to be completed. In the case when there is more than one task, the problem is to optimize the allocation of heterogeneous agents to those multiple tasks which require several capabilities. One of the obstacles that arise in such an optimization problem is the overlapping agent which should be minimized to complete all tasks as quickly as possible.
This study develops the ACO algorithm by modifying several elements so that it could solve the task allocation problem of multi-agent system with multi-target. Those elements are the construction of candidate solutions, heuristic functions and efficiency functions. The performance of the modified ACO algorithm in this study is optimized by minimizing the task completion cost and also by minimizing overlapping agents. We also maximize the overall system capabilities in order to increase efficiency of the agent coalition. The simulations indicate that the modified ACO algorithm has better performance than the benchmark algorithm in reducing the task completion cost by ±11.87%. The benchmark algorithm that we use in this study is the ACO algorithm which has been developed in previous study to solve task allocation problem in multi-agent system. In addition, the simulation results also show that the modified ACO algorithm in this study has significantly decreased the number of overlapping agents by reducing the overlapping weight by ±55.11%. From these results, it can be concluded that the ACO algorithm proposed in this study can be used to solve the task allocation problem in multi-agent system for multi-target.