Preserving Functionally Equivalent Subsequences in Service-Composition Crossover

Genetic algorithms that assemble web-service workflows produce new candidate workflows by splicing two parent workflows together. The best current operators do two things. They cut the parents where consecutive services sit far apart on the network, and they protect the stretch of services that both parents share. The protection has a blind spot. It only recognizes a shared stretch when both parents use the identical services, identified by the same ID. Service repositories are full of near-substitutes: different services that consume and produce almost the same data concepts. Two parents that have found the same functional sub-plan with different providers look unrelated to the operator, so the operator cuts through that sub-plan.

We propose to replace exact matching with matching by functional equivalence. Each service in the repository is described by its set of input and output data concepts. We build a neighborhood graph over these descriptions using UMAP (a nonlinear dimensionality-reduction method that first builds a weighted "fuzzy" neighbor graph over the data and then lays it out in low dimensions). The parents are then aligned with a soft version of longest-common-subsequence matching, in which two services count as a match if they are strong neighbors in that graph. The aligned sub-plan is inherited intact. At each aligned position, the offspring takes whichever of the two equivalent providers is network-closer to its neighbors. Distance-guided cuts are applied only outside the aligned region. The claim is testable and could fail. The experiments are built so that UMAP has to earn its place against raw set-overlap similarity and against a control that preserves just as much structure at random.

Core Claim

The claim has two parts. First, on distributed data-intensive web service composition, a crossover that preserves functionally aligned subsequences should beat one that preserves only identical subsequences, under an equal evaluation budget. Second, the gain should come from the meaning of the alignment, not from simply preserving more.

The first part extends the current best operator, GA-LCS. This operator is introduced in A memetic algorithm with distance-guided crossover: distributed data-intensive web service composition and reused in A Novel Repair-Based Multi-objective Algorithm for QoS-Constrained Distributed Data-Intensive Web Service Composition. It locks the exact longest common subsequence of the two parents and cuts only outside it. Both papers leave exact symbolic matching untouched, and so do the related shared-arc operator in An effective hybrid search algorithm for the multiple traveling repairman problem with profits and the similar-tour pairing in A Hybrid Genetic Algorithm for the min-max Multiple Traveling Salesman Problem. That shared assumption is what we relax.

The second part of the claim is also where UMAP enters as a similarity measure. It is a candidate lens, not a foregone conclusion. Service concept sets are sparse, high-dimensional binary vectors, much like mutation profiles. UMAP-assisted K-means clustering of large-scale SARS-CoV-2 mutation datasets shows that UMAP on Jaccard distances groups such profiles into coherent neighborhoods better than PCA does. Clustering with UMAP: Why and How Connectivity Matters shows that raw nearest-neighbor graphs in such spaces are distorted by "hubs", meaning points that appear as neighbors of disproportionately many others. That paper also shows that refining the graph with mutual neighbors and shortest-path neighborhoods improves downstream structure. Both results motivate the design. Neither is evidence about optimization, because neither paper touches evolutionary search.

Mechanism

We compute UMAP's fuzzy neighbor graph once per repository, over the Jaccard distances between services' input and output concept sets. The layout step is optional; we use the graph weights themselves, $w_{uv} \in [0,1]$, as the similarity between services $u$ and $v$. Using the graph rather than a 2D projection avoids the distortions that projections introduce.

For parents $A$ and $B$, we compute a weighted soft longest common subsequence:

$$L(i,j)=\max\big(L(i-1,j),\;L(i,j-1),\;L(i-1,j-1)+w_{A_iB_j}\,\mathbb{1}[w_{A_iB_j}\ge\tau]\big).$$

Here $L(i,j)$ is the best alignment score between the first $i$ services of $A$ and the first $j$ services of $B$. The indicator $\mathbb{1}[\cdot]$ admits a match only when the similarity exceeds a threshold $\tau$. Setting $\tau=1$ with $w_{uu}=1$ recovers exact LCS, which is GA-LCS.

The traced-back alignment defines the protected block. At each aligned pair, the offspring keeps the provider with smaller summed network distance to its predecessor and successor, measured on the same WS-DREAM-derived latency data the prior work uses. This is where distance guidance acts inside the block. Outside the block, cuts follow the largest-consecutive-distance rule of GA-II. The offspring is then decoded to a valid workflow graph and repaired with the backward decoding procedure from the two DWSC papers above.

Soft matching protects more of each parent than exact matching does. The diversity-loss tension documented for structure-preserving operators in HG-means and EHSA-MTRPP therefore applies here with more force. We address it with a schedule on $\tau$ that starts high and relaxes only while population diversity stays above a floor. We report diversity throughout.

Research Program

The work has three stages. First, we build service concept vectors and fuzzy graphs for all WSC-2008 and WSC-2009 repositories. For each repository we measure a substitutability density: the fraction of services that have at least one neighbor above $\tau$ with compatible outputs.

Second, we implement the operator inside the same genetic algorithm, decoder, repair, and local-search code as GA-LCS, so that only the crossover differs.

Third, we run the comparisons and ablations below. We then analyze where gains occur, on which repositories and at which generations, and what they cost in wall time. The embedding is a one-time cost per repository, and the alignment is quadratic in chromosome length.

Baselines

The naive reference is blind index crossover, meaning random cut points with the same decoder and repair. On WSC08-1 it has a reported mean normalized fitness of 0.54 over 30 runs, where lower is better. This figure appears in both A memetic algorithm with distance-guided crossover and A Novel Repair-Based Multi-objective Algorithm.

The strongest existing competitors are GA-LCS and GA-II from the same papers. Both report a mean fitness of 0.42 on WSC08-1. GA-LCS is the most direct competitor because our operator is exactly GA-LCS with the match test loosened. For WSC-2009 the file gives no per-instance numbers ("no reported result found on Lacuna for WSC-2009 per-instance fitness"), so we re-run all baselines ourselves.

Fairness rules apply to every method. All methods share the augmented instances, the decoder, the repair procedure, the population size, and a fixed budget of fitness evaluations. Each method gets the same hyperparameter tuning budget. We run 30 independent seeds per instance.

Beating GA-LCS means a lower mean fitness at equal evaluations, significant under the Wilcoxon signed-rank test at 0.05 as in the prior work, on a majority of the 13 repositories. It also means no loss on the others.

We also compare against the memetic variants with distance-guided local search from Composing Distributed Data-Intensive Web Services Using Distance-Guided Memetic Algorithm. That local search already inserts closer substitute services, so it partly overlaps with our in-block provider choice.

We also plan to include Cluster-Guided Genetic Algorithm for Distributed Data-intensive Web Service Composition, provided its operator can be reimplemented. The file gives no details of its mechanism, so we cannot say in advance how it relates.

The ablations isolate the key ingredient. They swap the similarity $w$ among five options: exact ID, raw Jaccard, cosine distance in PCA space, distance in the UMAP 2D layout, and the UMAP fuzzy graph with and without the mutual-neighbor and path-neighbor refinements. One further ablation turns off the in-block provider choice, so that we inherit parent $A$'s provider every time.

Why not just…?

Why not just use raw Jaccard overlap between concept sets as the match score? This is the most serious threat, and it may work equally well. The hub distortion reported by Clustering with UMAP matters for clustering thousands of points. A repository's service set may be small or structured enough that raw overlap suffices. The raw-Jaccard ablation settles this directly. If it ties UMAP, we will report soft-subsequence preservation itself as the contribution and drop UMAP as unnecessary.

Why not just give GA-LCS a larger population or more generations? The whole comparison is at equal fitness evaluations, and we report anytime curves of best fitness against evaluations. A soft operator that only helps early, and that GA-LCS catches up with at the end, would show up as crossing curves. We would report that as a speed result, not a quality result.

Why not just let distance-guided local search substitute providers after a standard crossover? Local search already swaps in closer services near the largest distance gap, and its cost is a known open issue in the memetic papers. We run the memetic GA-LCS at equal evaluations counting local-search calls. If it matches our operator, the value of alignment-aware preservation is small. If our operator matches it without local search, that addresses the open question of when local search is worth triggering.

Why not just preserve more of each parent, regardless of similarity? Soft matching could win simply by copying longer blocks. A control preserves blocks of the same length distribution as our operator, but aligned at random positions. It isolates whether functional equivalence matters.

Proposed Experiments

We use WSC08-1 through WSC08-8 and WSC09-1 through WSC09-5, augmented with WS-DREAM locations and uniform-random transfer and processing attributes exactly as in the two DWSC papers, so that our GA-LCS and blind baselines can be checked against the reported 0.42 and 0.54 on WSC08-1. Metrics are mean and spread of normalized fitness over 30 seeds, Wilcoxon tests, and anytime fitness-versus-evaluations curves. We also track population diversity, defined as the mean pairwise edit distance and the fraction of unique chromosomes. Two further metrics are the fraction of offspring needing repair and total wall time including embedding.

Two checks are decisive. First, the gain over GA-LCS should grow with a repository's substitutability density. If gains appear where there is nothing to substitute, the mechanism is not what we claim. Second, the operator must beat the length-matched random-preservation control. If neither holds, the proposal fails cleanly.