Novas meta-heurísticas variantes do algoritmo golden ball com chaves aleatórias enviesadas explorando o paralelismo: uma análise comparativa aplicada ao problema do caixeiro viajante

Abstract

The development of metaheuristics inspired by nature has gained prominence in the area of combinatorial optimization, especially to solve complex problems that are computationally challenging. The Golden Ball (GB) algorithm is one such approach, inspired by the behavior of soccer players during a match, where the search for solutions is compared to the strategy of a team in a championship. However, the efficiency of GB can be limited in large-scale or highly complex problems. In this context, the integration of the Biased Random Key (BRK) technique into GB emerges as a promising alternative, allowing the representation of solutions through random keys and generalizing the method’s ability to work with different problems. In addition, the development of the new techniques Biased Random Key Golden Ball Instanced (BRKGB-I), Biased Random Key Golden Ball World Championship (BRKGB-WC) and Biased Random Key Golden Ball Brazilian Football Championship (BRKGB-BFC), variants of the GB algorithm that incorporate parallel computing mechanisms, aims to improve both computational efficiency and the quality of the solutions obtained. These approaches seek to exploit the potential of parallelism to optimize algorithm performance in complex problems, ensuring more effective exploration of the search space and obtaining high-quality solutions in less time, especially in problems such as the Traveling Salesman Problem (TSP), which is widely used as a benchmark to evaluate optimization algorithms. The results obtained with the new variants demonstrate that the combination of techniques inspired by nature, such as GB, with modern approaches to parallelism and solution representation, such as BRK, can lead to significant advances in solving combinatorial optimization problems. The highlight is BRKGB-BFC, which simulates a Brazilian soccer championship, suggesting that the incorporation of competitive and collaborative dynamics can be particularly effective in improving the quality of solutions while maintaining a competitive execution time.