Performance analysis of GA and PBIL variants for real-world location-allocation problems.

Ankrah, Reginald; Regnier-Coudert, Olivier; McCall, John; Conway, Anthony; Hardwick, Andrew

Abstract

The Uncapacitated Location-Allocation problem (ULAP) is a major optimisation problem concerning the determination of the optimal location of facilities and the allocation of demand to them. In this paper, we present two novel problem variants of Non-Linear ULAP motivated by a real-world problem from the telecommunication industry: Uncapacitated Location-Allocation Resilience problem (ULARP) and Uncapacitated Location-Allocation Resilience problem with Restrictions (ULARPR). Problem sizes ranging from 16 to 100 facilities by 50 to 10000 demand points are considered. To solve the problems, we explore the components and configurations of four Genetic Algorithms [1], [2], [3] and [4] selected from the ULAP literature. We aim to understand the contribution each choice makes to the GA performance and so hope to design an Optimal GA configuration for the novel problems.We also conduct comparative experiments with Population-Based Incremental Learning (PBIL) Algorithm on ULAP. We show the effectiveness of PBIL and GA with parameter set: random and heuristic initialisation, tournament and fined grained tournament selection, uniform crossover and bitflip mutation in solving the proposed problems.

Citation

ANKRAH, R., REGNIER-COUDERT, O., MCCALL, J., CONWAY, A. and HARDWICK, A. 2018. Performance analysis of GA and PBIL variants for real-world location-allocation problems. In Proceedings of the 2018 IEEE congress on evolutionary computation (CEC 2018), 8-13 July 2018, Rio de Janeiro, Brazil. Piscataway, NJ: IEEE [online], article number 8477727. Available from: https://doi.org/10.1109/CEC.2018.8477727

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 2018 IEEE congress on evolutionary computation (CEC 2018)
• Start Date: Jul 8, 2018
• End Date: Jul 13, 2018
• Acceptance Date: Mar 15, 2018
• Online Publication Date: Jul 8, 2018
• Publication Date: Oct 4, 2018
• Deposit Date: Jun 22, 2018
• Publicly Available Date: Jul 8, 2018
• Publisher: Institute of Electrical and Electronics Engineers (IEEE)
• Peer Reviewed: Peer Reviewed
• Article Number: 8477727
• DOI: https://doi.org/10.1109/CEC.2018.8477727
• Keywords: Uncapacitated facility location problem; Uncapacitated facility location resilience problem; Uncapacitated facility location resilience problem with restrictions; Genetic algorithm; Population based incremental learning algorithm
• Public URL: http://hdl.handle.net/10059/2960
• Contract Date: Jun 22, 2018