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.
This paper introduces the edge-based contiguous p-median (ECpM) problem, which partitions the roads in a network into a given number of compact and contiguous territories. We develop two binary programming formulations that minimize the total network distance from each road to its assigned center node. The first uses an exponential number of cut-set contiguity (CSC) constraints and is solved with a branch-and-cut (B&C) algorithm that checks incumbent solutions for contiguity and adds violated CSC constraints as needed. The second is a compact formulation that imposes a stronger form of contiguity through shortest-path contiguity (SPC) constraints. These constraints are added up front, and the formulation is solved directly with an off-the-shelf solver. Despite this stronger requirement, we show that SPC-based ECpM has the same optimal objective value as ECpM with general contiguity and even the relaxed edge-based p-median (EpM). As a result, the SPC constraints preserve at least one optimal EpM solution and can therefore strengthen the EpM formulation. We also establish three structural properties of ECpM solutions and use them to derive three families of inequalities that further strengthen these formulations. Computational experiments on 84 instances from 14 real-world road networks show that adding the SPC constraints to EpM enables all instances to be solved to optimality and reduces solution times. In contrast, EpM without these constraints and CSC-based ECpM reach the time limit on six and eight instances, respectively. The proposed inequalities reduce both counts to one and further reduce solution times.
Zeyad Kassem, Behnam Jabbari-Marand, Adolfo R. Escobedo
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
Parent selection methods are widely used in evolutionary computation to accelerate the optimization process, yet their theoretical benefits are still poorly understood. In this paper, we address this gap by proposing a parent selection strategy for the (μ+1) genetic algorithm (GA) that prioritizes the selection of maximally distant parents for crossover. We show that, with an appropriately chosen population size, the resulting algorithm solves the Jumpk problem in O(k4knlog(n)) expected time. This bound is significantly smaller than the best known bound of O(nμlog(μ)+nlog(n)+nk−1) for any (μ+1)~GA using no explicit diversity-preserving mechanism and a constant crossover probability. To establish this result, we introduce a novel diversity metric that captures both the maximum distance between pairs of individuals in the population and the number of pairs achieving this distance. The main novelty of our analysis is that it relies on crossover as a mechanism for creating and maintaining diversity throughout the run, rather than using crossover only in the final step to combine already diversified individuals. The insights provided by our analysis contribute to a deeper theoretical understanding of the role of crossover in the population dynamics of genetic algorithms.
Andre Opris, Denis Antipov
University of Passau Passau, Germany · Sorbonne Université, CNRS, LIP6 Paris, France
Evolutionary algorithms have been used for a wide range of multi-objective combinatorial optimization problems. Despite practical success, theoretical results on the runtime of evolutionary algorithms for multi-objective combinatorial problems are rather limited. One classical problem that has been investigated is the multi-objective minimum spanning tree problem for which runtime bounds have been obtained to compute all extremal corner points of the Pareto front. With this paper, we provide some more detailed insights into the structure of the Pareto front when the edge weights take on a small number of distinct values. Based on these insights, we derive new runtime results for evolutionary multi-objective algorithms and complement our theoretical results with experimental investigations.
Narges Tavassoli Kejani, Andrew M. Sutton, Frank Neumann
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