A Multi-Parent Edge Assembly Crossover Driven Hybrid Genetic Algorithm for the Hamiltonian p-Median Problem
Authors: Junkai Huang, Pengfei He, Jin-Kao Hao, Xin Yao
Organizations: School of Automation and Key Laboratory of Measurement and Control of Complex Systems of Engineering, Ministry of Education, Southeast University, Nanjing 210096, China · School of Data Science, Lingnan University, Hong Kong SAR, China · LERIA, Université d’Angers, 2 Boulevard Lavoisier, 49045 Angers, France
The Hamiltonian p-median problem seeks to partition the vertices of a graph into exactly p disjoint cycles while minimizing their total cost. This paper presents a hybrid genetic algorithm incorporating a multi-parent edge assembly crossover operator. The crossover combines a base solution with multiple donor solutions in a single recombination operation, thereby expanding the space of available edge exchanges. It uses virtual copies of the base solution to establish edge balance, together with an auxiliary directed graph and a budgeted search to construct valid AB-cycles. Extensive experiments on 215 benchmark instances across four sets show that the proposed algorithm improves the best-known solution values for 34 instances and matches those for another 168. Additional experiments indicate that a moderate number of parents provides beneficial diversity, whereas excessive parent counts, particularly when p is large, lead to excessive population dispersion and hinder convergence.
Figures & tables
Fig. 1: The illustration of joint multigraph Gmp .
Fig. 2: Construction of auxiliary graph: (a) joint multigraph Gmp ; (b) directional state nodes suv and svu associated with edge (u,v) ; and (c) auxiliary directed graph G′=(S,A) .
Fig. 3: Illustration of RBFS to generate distance labels.
Parameter
Section
Description
Value
Lmax
III-C
maximum length of an accepted AB-cycle
80
b
III-C
number of successors retained at each expansion
8
k
III
number of parent solutions used in mpEAX
7
TABLE I: Parameters used in HGAmp .
Set
Pair algorithms
Best
Average
#Wins
#Ties
#Losses
p -value
#Wins
#Ties
#Losses
p -value
S
HGAmp vs. BKS
0
55
0
1.00
–
–
–
–
HGAmp vs. re-HGA
0
55
0
1.00
0
55
0
1.00
HGAmp vs. re-PGVNS
–
–
–
–
–
–
–
–
M
HGAmp vs. BKS
0
55
0
1.00
–
–
–
–
HGAmp vs. re-HGA
0
55
0
1.00
1
54
0
1.00
TABLE II: Summary of results between HGAmp and the reference algorithms on the four sets of benchmark instances.
Fig. 4: mpEAX versus EAX on eight instances.
Fig. 5: The distance between offspring solutions and the base solution.
Fig. 6: Population distance over the search on u1060 .
Fig. 7: Pre-restoration route-count deviation on rat783 and u1060 .
Fig. 9: Effects of Lmax and b on solution quality relative to the default configuration.
Combinatorial optimization finds the best feasible choices among discrete alternatives in routing, scheduling, graph problems, and resource allocation.
School of Computing and Augmented Intelligence, Arizona State University, Tempe, Arizona, 85281 · Edward P. Fitts Department of Industrial and Systems Engineering, North Carolina State University, Raleigh, North Carolina, 27606
Univ. Lille, CNRS, Centrale Lille, UMR 9189 CRIStal, F-59000, France · University of Minnesota Duluth, Minnesota, USA · Optimisation and Logistics, School of Computer Science and Information Technology, Adelaide University, Adelaide, Australia