A Binary Grasshopper Optimization Algorithm for Solving Uncapacitated Facility Location Problem

Abstract

The Uncapacitated Facility Location Problem (UFLP) is a real-world binary optimization problem that aims to find the number of facilities to open, minimizing the total cost of exchange between customers and facilities, as well as the opening costs of these facilities. UFLP is classified as an NP-Hard problem. Metaheuristic methods are often preferred to solve UFLP due to their ability to find acceptable solutions in a reasonable time and its NPHard characteristics. Grasshopper Optimization Algorithm (GOA) is a continuous metaheursitics optimization algorithm. In the literature, although some binary versions of the GOA algorithm have been used to solve problems such as feature selection, knapsack, scheduling and cluster covering, its performance analysis has not been conducted on UFLP which is pure binary optimization problem. In this study, a novel binary version of the GOA integrated with a novel binarization procedure is proposed for solving the UFLP. In the binarization procedure, a probability-based update strategy has been developed for generating new candidate solutions. This approach ensures the probability of determining the effect of the global best solution on the candidate solution. Besides, during the population update phase, there are two different mechanisms to update the global best solution and other grasshoppers. To enhance diversity in the grasshopper population, an alpha parameter has been integrated into the original algorithm. It was aimed to improve the quality of the candidate solutions by the integration of the alpha parameter. The performance of the proposed algorithm is assessed on the CAP and M* datasets. The obtained GAP values for the CAP 71-CAP A, CAP B, and CAP C problems are 0, 0.14, and 0.18, respectively. The GAP is 0 for the MO1-MO5, MP2, MP3, and MQ1-MQ3 problems, and GAP <= 0.24 for the remaining problems. The results were compared with other state-of-the-art binary optimization algorithms. The experimental results show that the proposed method is superior to the other compared algorithms and is an effective algorithm for solving UFLPs.