This paper addresses the scalability dimension of a multi-agent framework for solving combinatorial optimization problems using metaheuristics. The related literature discusses several properties of multi-agent systems. However, an important property that has received little attention is scalability, which refers to the ability of a system to perform useful work uniformly as the dimension of the system itself increases. This article introduces a methodology for assessing the scalability of multi-agent frameworks using scenarios with one, two, four, eight, ten, fifty, thirty, forty, fifty, and sixty agents. The framework Multi-Agent Architecture for Metaheuristics (AMAM) is the adopted architecture for performing the computational tests, using instances of the Vehicle Routing Problem with Time Windows (VRPTW) and the Unrelated Parallel Machine Scheduling Problem with Sequence-Dependent Setup Times (UPMSP-ST). The proposed methodology uses the obtained values concerning the objective function and the associated runtimes of the instanced problems to perform statistical measurements and tests that revealed an improvement in the framework’s performance concerning the quality of solutions despite the slight increase in runtime for the VRPTW case. The results of a linear regression approach concerning the objective function data showed an adequate representation of agent inclusion but, regarding the runtime values, did not demonstrate such precise adjustments. The final results suggest that the adopted framework is scalable and demonstrates a robust response to the increase in the number of agents in its structure.
Maria Amélia Lopes Silva, Jardell Fillipe da Silva, Sérgio Ricardo de Souza e Marcone Jamilson Freitas Souza (2024). UFV - Campus Florestal, CEFET-MG and UFOP 2024
This article was submitted to Engineering Applications of Artificial Intelligence on 12/26/2023, Accepted 23 November 2024, Available online 23 December 2024.
DOI - 10.1016/j.engappai.2024.109738.
The AMAM Framework is available here: https://github.com/mamelials/AMAM-Multiagente-Architecture-for-Metaheuristics. The AMAM Framework was implemented in Java, with JDK~8, using IDE Eclipse.
The experiments aim to investigate the performance of the AMAM Framework when the number of agents grows. The objective is to evaluate the structure regarding its scalability. Based on the heterogeneity of the ways of measuring scalability, the experiments assess whether the inclusion of agents in the framework has a direct influence on its performance concerning the quality of the obtained results for the objective function values as well as the obtained runtimes.
Todos as análises estatisticas são apresentadas na pasta statistical_analysis.
The experiments were divided into 4 sessions. To facilitate the interpretation of the analyses, .R files were created for each session, as follows:
The raw data for each problem can be found in the following .csv files:
VRPTW vrp_data.csv
UPMSP-ST pmp_data.csv
To better present the results visually, dynamic files were created for each problem addressed.
The results were obtained using the computational cluster of the Federal University of Viçosa - UFV, maintained by the Scientific and Technological Development Support Division https://dct.ufv.br. The used computer node has the following configurations: Intel Xeon Silver 4216 processor (22 MB Cache, 2.1 GHz, 16 cores 384 GB RAM), totaling 64 execution cores, with the Linux CentOS operating system. The codes used in this work are available on GitHub.
For the instantiation of the AMAM Framework, the experiments used the following sets of instances available in the literature:
VRPTW: the set of
UPMSP-ST: the set of instances proposed by Vallada (2011), available at http://soa.iti.es/problem-instances. To evaluate AMAM, we chose
\end{enumerate}
All used instances are available in folder instances.
The parameters for the methods used are found in folder parameters.
The parameters for the experiments are found in folder tests.
