Source-linked AI summary
Towards Efficient Evaluation of Evolutionary Transfer Optimization: Case Studies on Task-Parameterized Applications
Yanchen Li, Xiaoming Xue, Kay Chen Tan
TL;DR
As ETO scales across more tasks or larger per-task workloads, repeated application evaluation can drive runtime growth. This paper reformulates serial kinematic-arm and B-spline trajectory evaluations into parallel-suitable matrix forms, achieving 256.72× and 93.91× end-to-end speedups while maintaining close numerical agreement with reference evaluations.
Problem
In larger-scale ETO, application evaluation can add substantial runtime growth alongside optimization operations, motivating analysis of cross-task and within-task evaluation scaling.
Method
The paper develops an accumulation-matrix reformulation for cross-task kinematic-arm evaluation and a blending-matrix reformulation for within-task B-spline trajectory evaluation.
Results
256.72× end-to-end speedup was achieved for kinematic-arm MTO at K = 5000, and 93.91× for B-spline trajectory STO at R = 6000, with close numerical agreement to reference evaluations.
Takeaways & Limitations
Problem-side reformulation provides a practical opportunity to improve ETO efficiency as task count or within-task evaluation workload increases.
Takeaways & Limitations
The study covers only two continuous task-parameterized applications, and its reformulations remain application-specific; some matrix forms may trade additional storage for lower runtime.
Abstract
from arXiv · showhide
As evolutionary transfer optimization (ETO) scales to larger collections of related tasks, problem evaluation can become a major source of runtime growth. This work studies problem-side evaluation scaling in task-parameterized applications and reformulates application-specific serial computations into forms suitable for parallel execution. We organize evaluation scaling into two levels: the number of evaluated tasks and the workload within each task. In multi-task optimization, matrix-recursive kinematic-arm evaluation is reformulated using an accumulation-matrix representation of cumulative link directions. In sequential transfer optimization, pointwise B-spline trajectory evaluation is reformulated using a blending-matrix representation for trajectory and collision computations. Both reformulations maintain close numerical agreement with their reference evaluations and substantially reduce runtime, yielding $256.72\times$ and $93.91\times$ end-to-end speedups, respectively. These results demonstrate problem-side reformulation as a practical route toward scalable ETO. Both application implementations and experimental scripts are released as open source to support reproducibility and reuse.
I. INTRODUCTION
As ETO scales across related tasks, repeated application evaluation can become a major runtime source. The paper separates cross-task and within-task scaling and studies two matrix reformulations for parallel execution.
- Evaluation scaling: Task-parameterized applications share an evaluation procedure while differing in task-specific parameters.This structure motivates reformulating repeated serial computations rather than changing the optimization problem.
- Evaluation scaling: Evaluation runtime grows with both the number of evaluated tasks K and the workload within each task.The shared evaluator applies task-specific parameters and internal workload parameters repeatedly across populations and tasks.
- Reformulation strategy: The paper targets serial evaluation calculations that can be reformulated into mathematically equivalent forms suitable for parallel execution.This guideline addresses both cross-task and within-task evaluation scaling.
- Case studies: Kinematic-arm multi-task optimization uses an accumulation-matrix reformulation to reduce serial work as the task count increases.The reformulation targets cross-task evaluation scaling.
- Case studies: B-spline trajectory sequential transfer optimization uses a blending-matrix reformulation to reduce sample-wise serial workload while checking numerical agreement and runtime reduction.This case targets within-task scaling as trajectory sample counts increase.
II. CASE STUDY I: CROSS-TASK EVALUATION SCALING IN KINEMATIC-ARM OPTIMIZATION
The kinematic-arm case study examines cross-task evaluation scaling in multi-task optimization, where candidate evaluations are repeated across parameterized tasks. It derives and validates an accumulation-matrix reformulation for parallel evaluation.
- Cross-task scaling: Kinematic-arm optimization exposes cross-task scaling because candidate evaluations are repeatedly performed across tasks as K increases.The study treats the number of evaluated tasks as the main scaling factor.
- Reformulation: The study derives an accumulation-matrix reformulation after formulating the matrix-recursive evaluation.The reformulation is designed for parallel evaluation across tasks.
- Validation: Evaluation and end-to-end multi-task optimization experiments validate the reformulation.The validation uses kinematic-arm optimization with task-wise repeated evaluation.
A. Problem Formulation and Matrix-Recursive Evaluation
The kinematic-arm problem optimizes joint angles so the final link approaches a fixed target, with tasks differing by arm length and joint-angle range. Its reference evaluator constructs the arm recursively joint by joint.
- Problem formulation: Each task varies total arm length Lk and joint-angle range αmax,k while sharing the same evaluation procedure.The arm has D rotational joints and D equal-length links, and candidates encode the joint angles.
- Reference evaluation: The matrix-recursive evaluator rotates the current orientation and extends the arm by one link at each joint.The recursion uses planar homogeneous coordinates to construct intermediate arm configurations.
- Objective: The fitness is defined from the final endpoint's distance to the target under a maximization formulation.The endpoint after the final link is the quantity used in the task fitness.
- Evaluation cost: The joint-wise recursion is repeated across population individuals and then amplified across tasks in multi-task optimization.This repeated dependency creates evaluation scaling with population size N and task count K.
- Runtime evaluation: Figure 3 compares evaluation runtime against joint count and task count, plus one-generation end-to-end runtime under increasing K.The figure reports means over three repeated measurements with standard-deviation error bars.
B. Accumulation-Matrix Reformulation
The accumulation-matrix reformulation replaces the recursive transformation chain with cumulative link directions and direct link projections. These operations produce the same endpoint while enabling joint evaluation across candidates and tasks on parallel processors.
- Cumulative directions: The absolute orientation of each link equals the cumulative sum of its relative joint angles.This observation removes the need for recursively dependent transformation matrices.
- Cumulative directions: A fixed prefix-sum matrix converts relative joint angles into all cumulative link directions in one bulk operation.The reformulation replaces joint-wise transformation recursion with a matrix computation.
- Endpoint computation: After cumulative directions are computed, horizontal and vertical projections are reduced directly to obtain the final endpoint.The endpoint calculation avoids constructing intermediate matrices M1 through MD.
- Parallel evaluation: The reformulation preserves the reference endpoint and supports joint operations across candidates and tasks.Additional candidate and task axes allow N candidates across K tasks to be evaluated jointly.
C. Experimental Validation
The kinematic-arm reformulation closely matches matrix-recursive evaluation while reducing runtime growth as joints and tasks increase. In end-to-end MA-MTO, it reaches a 256.72× speedup at K = 5000.
- 2.561 × 10−8 ± 1.600 × 10−10 mean absolute fitness discrepancy confirms close agreement between the two evaluation forms.The maximum absolute discrepancy across seeds, tasks, and individuals was 3.576 × 10−7.
- The accumulation-matrix evaluation remains nearly constant as joint count D increases, unlike the matrix-recursive evaluation.
- The accumulation-matrix evaluation shows little runtime growth as task count K increases, while matrix-recursive evaluation scales rapidly.
- 256.72× speedup is achieved by the accumulation-matrix reformulation in end-to-end MA-MTO at K = 5000.The validation uses a 100-generation budget with K = 5000, N = 16, and D = 60.
III. CASE STUDY II: WITHIN-TASK EVALUATION SCALING IN B-SPLINE TRAJECTORY OPTIMIZATION
The STO case study examines a B-spline trajectory optimization problem in which increasing trajectory resolution raises the workload of evaluating one target task.
- B-spline trajectory STO represents within-task evaluation scaling through increasing trajectory sample count for a single target task.
A. Problem Formulation and Pointwise Evaluation
The trajectory problem optimizes a smooth B-spline path between fixed endpoints while avoiding square obstacles, and its pointwise evaluation traverses trajectory samples sequentially.
- The candidate solution specifies the vertical coordinates of D internal control points, while horizontal coordinates and endpoints are fixed.The start and goal positions are (0, 0) and (1, 1), and the total number of control points is C = D+2.
- A cubic B-spline combines neighboring control points using position-dependent coefficients generated by Cox–de Boor recursion.The cubic degree is δ = 3.
- The pointwise evaluation forms R trajectory samples by sequentially combining four neighboring control points at each sampling position.R is the evaluation-workload parameter, while the decision dimension D remains unchanged.
- Fitness combines sampled path length with penalties for obstacles intersected by any segment between consecutive trajectory samples.Each collided obstacle contributes the penalty ρ once, including boundary contact.
- Increasing R enlarges the serial within-task workload because trajectory samples are traversed sequentially despite joint local combinations and obstacle checks.
B. Blending-Matrix Reformulation
The blending-matrix reformulation aligns all local B-spline coefficients into a common matrix structure, replacing sample-wise traversal with joint matrix operations for trajectory, path-length, and collision computations.
- The coefficient matrix B aligns the local coefficients of all R sampling positions to a common control-point axis.
- Each matrix row embeds one local control-point window, with the final row selecting the prescribed goal point.
- A single matrix multiplication obtains the complete trajectory and replaces sequential sample traversal with a unified parallel-suitable computation.Each of the first R−1 rows contains δ + 1 consecutive nonzero coefficients.
- The complete path length is computed jointly from consecutive-point differences of the trajectory matrix.
- All R−1 trajectory segments are evaluated jointly against M obstacles, followed by a column-wise reduction for collision penalties.
- The matrix structure extends to population-based evaluation by adding a candidate axis, preserving the formulation while reducing repeatedly amplified serial workload.
C. Experimental Validation
The experiments validate numerical agreement between pointwise and matrix-based trajectory evaluation, then show that the matrix reformulation preserves end-to-end performance as within-task workload increases.
- Experimental setup: The study constructs a reproducible B-spline trajectory optimization testbed with explicitly specified spline, obstacle, and evaluation configurations.Each task uses D = 60 decision variables and M = 20 square obstacles with collision penalty ρ = 20.
- Numerical validation: The matrix reformulation is first compared with pointwise evaluation using identical candidate solutions.The comparison tests numerical agreement before measuring runtime scaling.
- Numerical validation: 1.101 × 10−5 ± 3.011 × 10−6 mean absolute fitness discrepancy confirms close agreement across 10 random seeds.The maximum absolute discrepancy over all seeds and individuals was 3.052 × 10−5.
- End-to-end validation: 93.91× speedup at R = 6000 is achieved in end-to-end MS-STO runtime with the matrix reformulation.The pointwise runtime grows rapidly with R, whereas the matrix runtime remains nearly unchanged.
- End-to-end validation: MS-STO obtained collision-free trajectories in 4/10 runs, with feasible runs averaging a final trajectory length of 3.365±0.587.The best feasible trajectory length was 2.586 under D = 60, R = 6000, and a 100-generation budget.
IV. CONCLUSION
The paper concludes that application-side evaluation reformulation can improve ETO efficiency at increasing task scales, while its evidence remains limited to two application-specific continuous cases.
- Conclusion: The two case studies expose cross-task scaling in kinematic-arm optimization and within-task scaling in B-spline trajectory optimization.Both cases replace recursive or sample-wise serial computation with structured matrix forms suitable for parallel execution.
- Conclusion: Both reformulations maintain close numerical agreement while substantially reducing isolated evaluation and end-to-end runtime.The conclusion identifies mathematically equivalent matrix reformulations as the common mechanism across both applications.
- Conclusion: Application evaluation provides a practical opportunity to improve ETO efficiency at increasing task scales.This conclusion concerns problem-side evaluation rather than the full range of optimization operations.
- Limitations and future work: The study is limited to two continuous task-parameterized applications, and its reformulations remain application-specific.The authors call for reusable principles across broader problem classes and further work on algorithm-side scaling.
- Future direction: Scalable algorithmic execution combined with efficient problem evaluation is intended to support substantially larger collections of tasks.The conclusion presents this as an intended direction rather than a demonstrated result of the present study.