  Generalization, i.e., the ability of solving problem instances that are not
available during the system design and development phase, is a critical goal
for intelligent systems. A typical way to achieve good generalization is to
learn a model from vast data. In the context of heuristic search, such a
paradigm could be implemented as configuring the parameters of a parallel
algorithm portfolio (PAP) based on a set of training problem instances, which
is often referred to as PAP construction. However, compared to traditional
machine learning, PAP construction often suffers from the lack of training
instances, and the obtained PAPs may fail to generalize well. This paper
proposes a novel competitive co-evolution scheme, named Co-Evolution of
Parameterized Search (CEPS), as a remedy to this challenge. By co-evolving a
configuration population and an instance population, CEPS is capable of
obtaining generalizable PAPs with few training instances. The advantage of CEPS
in improving generalization is analytically shown in this paper. Two concrete
algorithms, namely CEPS-TSP and CEPS-VRPSPDTW, are presented for the Traveling
Salesman Problem (TSP) and the Vehicle Routing Problem with Simultaneous
Pickup-Delivery and Time Windows (VRPSPDTW), respectively. Experimental results
show that CEPS has led to better generalization, and even managed to find new
best-known solutions for some instances.
