PaperlayerView exact revision on arXiv

Source-linked AI summary

Evolutionary Multitasking for Single-objective Continuous Optimization: Benchmark Problems, Performance Metric, and Baseline Results

Bingshui Da, Yew-Soon Ong, Liang Feng, A. K. Qin, Abhishek Gupta, Zexuan Zhu, Chuan-Kang Ting, Ke Tang, Xin Yao

arXiv:1706.03470v1cs.NE

TL;DR

The report addresses the need for benchmark problems to evaluate multitask single-objective optimization across different task relationships. It proposes nine composite problems, a performance metric, and baseline results. The MFEA outperforms single-task optimization in seven of the nine benchmark examples, while the two inferior cases have very low task similarity.

  • Problem

    The report proposes benchmarks for evaluating multitask single-objective optimization across problems with varying relationships between tasks.

    Source: §I · p. 1

  • Method

    The report constructs nine task combinations, uses a rank-correlation metric for inter-task synergy, and provides baseline results for the MFEA and single-task optimization.

    Source: §I · p. 1, A. Performance Metric · p. 8, B. Baseline Results · p. 8

  • Results

    The MFEA is superior to single-task optimization in seven of nine benchmark examples, while its two inferior cases have very low inter-task similarity.

    Source: B. Baseline Results · p. 8

  • Takeaways & Limitations

    The nine benchmarks, performance metric, and baseline results are intended to support future development and testing of multitask optimization algorithms.

    Source: §VII · p. 8, §VI · p. 8

    The synthetic benchmarks do not account for phenotypic overlap, because their variables lack substantial contextual meaning.

    Source: B. Similarity Tuning and… · p. 5

Abstract

from arXiv · show

In this report, we suggest nine test problems for multi-task single-objective optimization (MTSOO), each of which consists of two single-objective optimization tasks that need to be solved simultaneously. The relationship between tasks varies between different test problems, which would be helpful to have a comprehensive evaluation of the MFO algorithms. It is expected that the proposed test problems will germinate progress the field of the MTSOO research.

I. INTRODUCTION

The report develops benchmark problems and a performance metric to support evolutionary multitasking research. It formalizes MFO as a single-population approach to solving multiple tasks, with individual performance compared through task-specific ranks and scalar fitness.

I. INTRODUCTION

  • The report proposes nine composite benchmarks, a faster rank-correlation measure of inter-task synergy, and sample baseline results to support future MFO development.The measure avoids the partial derivatives and search-space integrals used by an earlier metric.Source: §I · p. 1

A. Preliminary

  • MFO simultaneously navigates multiple minimization tasks by treating each task objective as an additional factor influencing a single population.A solution is multifactorially optimal if it globally optimizes at least one task.Source: A. Preliminary · p. 2
  • Individuals are encoded in a unified search space and decoded into task-specific solutions for evaluating their performance on each task.The population comparison uses task-specific factorial costs and ranks, with constraint violations penalized in factorial cost.Source: A. Preliminary · p. 2
  • Each individual’s skill factor is its best-ranked task, and its scalar fitness is the reciprocal of its rank on that task.Scalar fitness enables population comparison; the comparison depends on the other individuals in the population.Source: A. Preliminary · p. 2

B. Multifactorial Evolution: A Framework for Effective Multitasking

The MFEA combines genetic inheritance with task-associated skill factors in one population. It selectively evaluates individuals on a single task, reducing the need to evaluate every individual on every task.

B. Multifactorial Evolution: A Framework for Effective Multitasking

  • The MFEA assigns each individual a skill factor and evaluates it only on that task, avoiding exhaustive per-individual evaluation across all tasks.Initial skill factors are distributed so each task has a fair number of representatives.Source: B. Multifactorial Evolution: A… · pp. 2–3
  • The algorithm creates offspring through crossover and mutation, evaluates them on their assigned tasks, then selects the fittest members from the parent-offspring pool.The underlying genetic mechanisms may be borrowed from population-based algorithms, with offspring evaluation adapted to skill factors.Source: B. Multifactorial Evolution: A… · pp. 2–3
  • Offspring inherit a parent’s skill factor through selective imitation, and are decoded and evaluated on a task associated with at least one parent.The skill factor represents the individual’s task-associated cultural trait.Source: B. Multifactorial Evolution: A… · p. 3

C. Search Space Unification

The MFEA unifies task representations so genetic material can be processed in one search space and shared during crossover. This report uses random keys to build synthetic continuous multitask problems from common optimization functions.

C. Search Space Unification

  • The unified search-space dimension is the maximum dimensionality among tasks, and each task decodes its own number of variables from the shared chromosome.Task variables with similar contextual meaning should be aligned; taking the first task-specific number of variables is one option when no prior mapping is available.Source: C. Search Space Unification · p. 3
  • Random-key chromosomes encode each variable as a continuous value in [0, 1], which is linearly mapped to the relevant task’s box-constrained phenotype space.Although the representation can accommodate continuous and discrete optimization, this report focuses on synthetic continuous problems.Source: C. Search Space Unification · p. 3

III. INDIVIDUAL TASKS IN COMPOSITE BENCHMARK PROBLEMS

  • The composite benchmark problems use seven commonly used optimization functions as ingredients.D denotes search-space dimensionality, and x is the design-variable vector.Source: §III · p. 4

7) Schwefel:

The report uses Spearman’s rank correlation to quantify inter-task synergy, drawing on task ranks across a unified representation space. Under perfect rank agreement, improvement on either minimization task also improves the other without additional evaluations.

IV. CONSTRUCTION OF BENCHMARK PROBLEMS

  • Global-optimum intersection and fitness-landscape correspondence are identified as ingredients of complementarity between tasks.Source: §IV · p. 4

A. Spearman’s rank correlation coefficient

  • Spearman’s rank correlation measures synergy as the Pearson correlation between the tasks’ factorial ranks for solutions decoded from the unified space.The report treats the coefficient as a representation of task synergy.Source: A. Spearman’s rank correlation… · p. 4
  • The report samples 1,000,000 points in the unified search space to calculate the rank-correlation measure.Source: A. Spearman’s rank correlation… · p. 4
  • Perfect ordinal agreement between two minimization tasks means any cost-reducing step for one also reduces the other’s cost without additional evaluations.This guarantee applies to the family of functions characterized by high ordinal correlation.Source: A. Spearman’s rank correlation… · p. 4

B. Similarity Tuning and Classification of Benchmark Problems

The benchmark design combines three degrees of optimum intersection with three Spearman-similarity levels, yielding nine problem sets. The report also specifies baseline evaluation conditions and notes that phenotypic overlap is not used to classify its synthetic tasks.

B. Similarity Tuning and Classification of Benchmark Problems

  • The benchmark classifies task pairs by complete, partial, or no global-optimum intersection and by high, medium, or low Spearman similarity, forming nine problem sets.Similarity decreases as the Sphere function is shifted; the report defines low as Rs < 0.2, medium as 0.2 ≤ Rs < 0.8, and high as Rs ≥ 0.8.Source: B. Similarity Tuning and… · pp. 4–5
  • Phenotypic overlap of decision variables is not applied as a classification condition for these synthetic benchmark functions.The report cites the lack of substantial contextual meaning in synthetic functions as the reason for excluding this condition.Source: B. Similarity Tuning and… · p. 5

V. PROBLEM SPECIFICATIONS AND BASELINE RESULTS

  • Baseline MFEA and SOEA results use a population of 100, 100,000 total evaluations, and averages over 20 runs, with identical parameter settings.The evaluation uses rmp = 0.3 for MFEA and omits uniform crossover-like variable swapping.Source: §V · p. 5
  • Table III summarizes problem-pair properties, while the report defines M as a rotation matrix and o as an optimum location in the original search space.The complete-intersection illustration projects the unified search space onto its first and second axes.Source: §V · p. 5, Table III · p. 6, Figure 2 · p. 6

A. Benchmark Problems with Complete Intersection of Global Optima

These examples hold the global optima completely intersected in unified space while varying task similarity. Their reported similarity ranges from 1.0000 to 0.0002 across the three cases.

1) Complete Intersection and High Similarity (CI+HS):

2) Complete Intersection and Medium Similarity (CI+MS):

3) Complete Intersection and Low Similarity (CI+LS):

  • The CI+LS pair uses 50D rotated Ackley and Schwefel tasks whose distinct original-space optima completely intersect in unified space, with similarity 0.0002.The reported optima are 42.0969 in each Ackley dimension and 420.9687 in each Schwefel dimension, under their respective stated search spaces.Source: 3) Complete Intersection and Low… · p. 6

B. Benchmark Problems with Partial Intersection of Global Optima

The benchmark set varies how task optima overlap and how similar their landscapes are. The supplied examples include partial-intersection cases and a figure describing a no-intersection case.

B. Benchmark Problems with Partial Intersection of Global Optima

1) Partial Intersection and High Similarity (PI+HS):

  • In PI+HS, 50D rotated Rastrigin and shifted Sphere have similarity 0.8670 and optima differing in the final 25 coordinates.Task 1's optimum is all zeros; Task 2's first 25 coordinates are zero and its remaining coordinates are 20.Source: 1) Partial Intersection and High… · p. 7

2) Partial Intersection and Medium Similarity (PI+MS):

  • In PI+MS, the tasks are 50D rotated and shifted Ackley and 50D Rosenbrock, with optima differing in the final 25 coordinates.Task 1's optimum has 25 zeros followed by 25 ones; Task 2's optimum is all ones.Source: 2) Partial Intersection and Medium… · p. 7
  • Fig. 4 describes a no-intersection case in which the two tasks' global optima differ across all variables in the unified search space.The caption labels the distinct optima y1 and y2.Source: Figure 4 · p. 7

3) Partial Intersection and Low Similarity (PI+LS):

The supplied examples span low-similarity partial intersection and no-intersection benchmarks, with the latter also represented at high similarity.

3) Partial Intersection and Low Similarity (PI+LS):

C. Benchmark Problems with No Intersection of Global Optima

  • The no-intersection category is defined by optima that do not overlap in the unified search space.The passage points to Fig. 2 as an illustration for D = 2.Source: C. Benchmark Problems with No… · p. 7

1) No Intersection and High Similarity (NI+HS):

2) No Intersection and Medium Similarity (NI+MS):

The supplied no-intersection examples include medium- and low-similarity task pairs. The performance metric standardizes outcomes across tasks and repetitions to compare algorithms overall.

2) No Intersection and Medium Similarity (NI+MS):

  • NI+MS pairs 50D rotated and shifted Griewank with 50D rotated Weierstrass, with similarity 0.3669.Their global optima are respectively all 10s and all 0s.Source: 2) No Intersection and Medium… · p. 8

3) No Intersection and Low Similarity (NI+LS):

A. Performance Metric

  • The metric compares stochastic algorithms across tasks using normalized best results from repeated runs, with equal function-evaluation effort per task.Normalization uses each task's mean and standard deviation across all algorithms and repetitions.Source: A. Performance Metric · p. 8
  • An algorithm's score sums its normalized results across tasks and repetitions, and a smaller score indicates superior overall performance.Source: A. Performance Metric · p. 8

B. Baseline Results

The baseline comparison reports MFEA outperforming SOEA in seven of nine benchmark cases. The report provides benchmark problems, a performance metric, and baseline results for future algorithm development and testing.

B. Baseline Results

  • The convergence and score plots also show MFEA superior in seven of nine cases; the two weaker cases have very low task similarity.The report notes that absent latent synergy can potentially make multitasking ineffective through negative transfer.Source: B. Baseline Results · p. 8

VII. CONCLUSIONS

  • The report presents nine benchmark problems, a performance metric, and baseline results to support future development and testing of multitask optimization algorithms.Its long-term aim is an evolutionary multitasking engine with performance comparable, or consistently superior, to state-of-the-art serial evolutionary optimizers.Source: §VII · p. 8

B. Baseline Results

  • MFEA is reported superior to SOEA in seven of nine benchmark examples.Table IV reports scores after 100,000 total function evaluations for both tasks combined; its caption identifies average performance as means with bracketed standard deviations.Source: B. Baseline Results · p. 8, Table IV · p. 9
Loading 1706.03470v1…