A binary grasshopper optimization algorithm for solving uncapacitated facility location problem

Ahmet Babalık

doi:10.1016/j.jestch.2025.102031

2025-05-01

PRE

Ahmet Babalık

Aybuke Babadag *

DOI：10.1016/j.jestch.2025.102031

原文链接

原文求助

摘要

En 中文

未考虑容量限制的设施选址问题（UFLP）是一个现实世界的二元优化问题，旨在确定开设的设施数量，以最小化客户与设施之间的交换总成本以及这些设施的开设成本。UFLP被归类为NP难问题。由于元启发式方法能够在合理时间内找到可接受的解，且考虑到UFLP的NP难特性，因此通常更倾向于使用它们来求解UFLP。蚱蜢优化算法（GOA）是一种连续的元启发式优化算法。在现有文献中，虽然已有一些GOA算法的二元版本被用于解决特征选择、背包问题、调度和聚类覆盖等问题，但针对UFLP（一个纯粹的二元优化问题）的性能分析尚未进行。本研究提出了一种结合新型二值化过程的GOA二元版本，用于求解UFLP。在二值化过程中，开发了一种基于概率的更新策略来生成新的候选解。这种方法确保了确定全局最优解对候选解影响的可能性。此外，在种群更新阶段，存在两种不同的机制来更新全局最优解和其他蚱蜢。为了增强蚱蜢种群的多样性，将alpha参数整合到原始算法中。旨在通过整合alpha参数来提高候选解的质量。所提出算法的性能在CAP和M*数据集上进行评估。对于CAP 71-CAP A、CAP B和CAP C问题的GAP值分别为0、0.14和0.18。对于MO1-MO5、MP2、MP3和MQ1-MQ3问题的GAP为0，其余问题的GAP≤0.24。将结果与其他最先进的二元优化算法进行比较。实验结果表明，所提出的方法优于其他比较算法，是求解UFLP的有效算法。

Keyword:

Binary optimization

Discrete optimization

Grasshopper optimization algorithm

Uncapacitated facility location problem