N-Mates Evaluation: a New Method to Improve the Performance of Genetic Algorithms in Heterogeneous Multi-Agent Systems

Multi-Agent Systems (MASs) are a widely used paradigm for modeling agents that interact with each other to solve problems. Genetic algorithms represent methods mimicking natural evolution and have been successfully applied in various domains, including MASs. While evolving controllers for homogeneous agents can be considered a relatively trivial task, evolving a collective ability in a group of heterogeneous agents strongly depends on the individual’s characteristics. In a genetic algorithm, the selection of the individuals forming the MAS is random and the evaluation of the group performance is affected by both the agent’s ability and the environmental complexity. Consequently, the emergent dynamics of the system can be highly unpredictable, and the success or failure of the MAS may be inaccurately evaluated. To mitigate the effect of chance, we proposed a novel technique - called n-mates evaluation - which allows for a better estimation of each individual’s effectiveness and its contribution to the final performance of the MAS. Results collected from three different cooperative benchmark tasks indicate that the proposed method is effective and outperforms a traditional genetic algorithm.