Evolutionary Large-Scale Global Optimization
An Introduction
Mohammad Nabi Omidvar1

Xiaodong Li2

1 School of Computer Science

University of Birmingham
m.omidvar@cs.bahm.ac.uk
2 School of Science
RMIT University, Melbourne, Australia
xiaodong.li@rmit.edu.au

Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

1 / 84

Outline
1

Introduction: Large Scale Global Optimization

2

Approaches to Large-Scale Optimization

3

Variable Interaction: Definitions and Importance

4

Interaction Learning: Exploiting Modularity

5

Conclusion

6

Questions

Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

2 / 84

Optimization

min f (x), x = (x1 , . . . , xn ) ∈ Rn

(1)

s.t. : g(x) ≤ 0(2)h(x) = 0(3)

Can be converted to unconstrained optimization using:Penalty method;
Lagrangian;Augmented Lagrangian.
Our focus is unconstrained optimization. We must learn how to walk
before we can run.

Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

3 / 84

Large Scale Global Optimization (LSGO)
How large is large?
The notation of large-scale is not fix.
Changes over time.
Diﬀers from problem to problem.
The dimension at which existing methods start to fail.

State-of-the-art (EC)
Binary: ≈ 1 billion [a].
Integer (linear): ≈ 1 billion [b], [c].
Real: ≈ 1000-5000.
[a] Kumara Sastry, David E Goldberg, and Xavier Llora. “Towards billion-bit optimization via a parallel estimationof distribution algorithm”. In: Genetic and Evolutionary Computation Conference. ACM. 2007, pp. 577–584.
[b] Kalyanmoy Deb and Christie Myburgh. “Breaking the Billion-Variable Barrier in Real-World Optimization
Using a Customized Evolutionary Algorithm”. In: Genetic and Evolutionary Computation Conference. ACM. 2016,
pp. 653–660.
[c] Kalyanmoy Deb and Christie Myburgh. “A population-based fast algorithm for a billion-dimensional resource
allocation problem with integer variables”. In: European Journal of Operational Research 261.2 (2017),
pp. 460–474.
Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

4 / 84

Large Scale Global Optimization: Applications
Why large-scale optimization is important?
Growing applications in various fields.
Target shape design optimization [a].
Satellite layout design [b].
! Parameter estimation in large scale biological systems [c].
! Seismic waveform inversion [d].
! Parameter calibration of water distribution systems [e].
! Vehicle routing [f].
!
!

[a] Zhenyu Yang et al. “Target shape design optimization by evolving B-splines with cooperative coevolution”.
In: Applied Soft Computing 48 (Nov. 2016), pp. 672–682.
[b] Hong-Fei Teng et al. “A dual-system variable-grain cooperative coevolutionary algorithm: satellite-module
layout design”. In: IEEE transactions on evolutionary computation 14.3 (Dec. 2010), pp. 438–455.
[c] Shuhei Kimura et al. “Inference of S-system models of genetic networks using a cooperative coevolutionary
algorithm”. In: Bioinformatics 21.7 (Apr. 2005), pp. 1154–1163.
[d] Chao Wang and Jinghuai Gao. “High-dimensional waveform inversion with cooperative coevolutionary
diﬀerential evolution algorithm”. In: IEEE Geoscience and Remote Sensing Letters 9.2 (Mar. 2012), pp. 297–301.
[e] Yu Wang et al. “Two-stage based ensemble optimization framework for large-scale global optimization”. In:
European Journal of Operational Research 228.2 (2013), pp. 308–320.
[f] Yi Mei, Xiaodong Li, and Xin Yao. “Cooperative coevolution with route distance grouping for large-scalecapacitated arc routing problems”. In: IEEE Transactions on Evolutionary Computation 18.3 (2014), pp. 435–449.

Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

5 / 84

Large Scale Global Optimization: Research

Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

6 / 84

Large Scale Global Optimization: Research

Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

7 / 84

The Challenge of Large Scale Optimization

Why is it diﬃcult?
Exponential growth in the size of search space (curse ofdimensionality).

Research Goal
Improving search quality (get to the optimal point).
Improving search eﬃciency (get there fast).

Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

8 / 84

Large Scale Global Optimization: Evolutionary Approaches

1

Initialization

2

Sampling and Variation Operators

3

Approximation and Surrogate Modeling4

Local Search and Memetic Algorithms

5

Decomposition and Divide-and-Conquer

6

Parallelization (GPU, CPU)

7

Hybridization

Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

9 / 84

Initialization Methods
Study the importance of initialization methods [1] in large-scale
optimization.

[1] Borhan Kazimipour, Xiaodong Li, and A Kai Qin. “A review of population initialization techniques for evolutionary
algorithms”. In: Evolutionary Computation (CEC), 2014 IEEE Congress on. IEEE. 2014, pp. 2585–2592.
Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

10 / 84

Initialization Methods
Inconclusive evidence for or against initialization methods:
Uniform design works worse than RNG, while good-lattice point andopposition-based methods perform better [1].
! Another study showed that population size has a more significant eﬀect
than the initialization [2].
! Achieving uniformity is diﬃcult in high-dimensional spaces [3].
! Yet another study suggest comparing average performances may notreveal the eﬀect of initialization [4].
!

Shortcomings:
It is diﬃcult to isolate the eﬀect of initialization.
Diﬀerent eﬀect on diﬀerent algorithms (mostly tested on DE).
! Numerous parameters to study.
!
!

[1] Borhan Kazimipour, Xiaodong Li, and A Kai Qin. “Initialization methods for large scale global optimization”. In: IEEE
Congress on Evolutionary Computation. IEEE. 2013, pp. 2750–2757.
[2] Borhan Kazimipour, Xiaodong Li, and A Kai Qin. “Eﬀects of population initialization on diﬀerential evolution for large
scale optimization”. In: IEEE Congress on Evolutionary Computation. IEEE. 2014, pp. 2404–2411.
[3] Borhan Kazimipour, Xiaodong Li, and A Kai Qin. “Why advanced population initialization techniques perform poorly inhigh dimension?” In: SEAL. 2014, pp. 479–490.
[4] Eduardo Segredo et al. “On the comparison of initialisation strategies in diﬀerential evolution for large scale optimisation”.
In: Optimization Letters (2017), pp. 1–14.
Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

11 / 84

Sampling and Variation Operators
Opposition-based sampling [1]Center-based sampling [2].
Quantum-behaved particle swarm [3].
Competitive Swarm Optimizer [4].
Social learning PSO [5].
Mutation operators [6], [7].
[1] Hui Wang, Zhijian Wu, and Shahryar Rahnamayan. “Enhanced opposition-based diﬀerential evolution for solving
high-dimensional continuous optimization problems”. In: Soft Computing 15.11 (2011), pp. 2127–2140.
[2] Sedigheh Mahdavi, Shahryar Rahnamayan, and Kalyanmoy Deb. “Center-based initialization of cooperative co-evolutionary
algorithm for large-scale optimization”. In: IEEE Congress on Evolutionary Computation. IEEE. 2016, pp. 3557–3565.
[3] Deyu Tang et al. “A quantum-behaved particle swarm optimization with memetic algorithm and memory for continuous
non-linear large scale problems”. In: Information Sciences 289 (2014), pp. 162–189.
[4] Ran Cheng and Yaochu Jin. “A competitive swarm optimizer for large scale optimization”. In: IEEE Transactions on
Cybernetics 45.2 (2015), pp. 191–204.
[5] Ran Cheng and Yaochu Jin. “A social learning particle swarm optimization algorithm for scalable optimization”. In:
Information Sciences 291 (2015), pp. 43–60.
[6] Hongwei Ge et al. “Cooperative diﬀerential evolution with fast variable interdependence learning and cross-cluster
mutation”. In: Applied Soft Computing 36 (2015), pp. 300–314.
[7] Ali Wagdy Mohamed and Abdulaziz S Almazyad. “Diﬀerential Evolution with Novel Mutation and Adaptive Crossover
Strategies for Solving Large Scale Global Optimization Problems”. In: Applied Computational Intelligence and Soft Computing
2017 (2017).
Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

12 / 84

Approximation Methods and Surrogate Modeling

High-Dimensional Model Representation (HDMR) [1].
Radial Basis Functions [2].
Kriging and Gradient-Enhanced Kriging Metamodels [3].
Piecewise Polynomial (Spline) [4].

[1] Enying Li, Hu Wang, and Fan Ye. “Two-level Multi-surrogate Assisted Optimization method for high dimensional nonlinear
problems”. In: Applied Soft Computing 46 (2016), pp. 26–36.
[2] Rommel G Regis. “Evolutionary programming for high-dimensional constrained expensive black-box optimization using
radial basis functions”. In: IEEE Transactions on Evolutionary Computation 18.3 (2014), pp. 326–347.
[3] Selvakumar Ulaganathan et al. “A hybrid sequential sampling based metamodelling approach for high dimensional
problems”. In: IEEE Congress on Evolutionary Computation. IEEE. 2016, pp. 1917–1923.
[4] Zhenyu Yang et al. “Target shape design optimization by evolving B-splines with cooperative coevolution”. In: Applied
Soft Computing 48 (Nov. 2016), pp. 672–682.
Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

13 / 84

Local Search and Memetic Algorithms
Multiple Trajectory Search (MTS) [1].
Memetic algorithm with local search chaining [2].
!
!

MA-SW-Chains [3].
MA-SSW-Chains [4].

Multiple oﬀspring sampling (MOS) [5], [6].

[1] Lin-Yu Tseng and Chun Chen. “Multiple trajectory search for large scale global optimization”. In: IEEE Congress on
Evolutionary Computation. IEEE. 2008, pp. 3052–3059.
[2] Daniel Molina, Manuel Lozano, and Francisco Herrera. “Memetic algorithm with local search chaining for large scalecontinuous optimization problems”. In: IEEE Congress on Evolutionary Computation. IEEE. 2009, pp. 830–837.
[3] Daniel Molina, Manuel Lozano, and Francisco Herrera. “MA-SW-Chains: Memetic algorithm based on local search chainsfor large scale continuous global optimization”. In: IEEE Congress on Evolutionary Computation. IEEE. 2010, pp. 1–8.
[4] Daniel Molina et al. “Memetic algorithms based on local search chains for large scale continuous optimisation problems:
MA-SSW-Chains”. In: Soft Computing 15.11 (2011), pp. 2201–2220.
[5] Antonio LaTorre, Santiago Muelas, and José-Marı́a Peña. “Multiple oﬀspring sampling in large scale global optimization”.
In: IEEE Congress on Evolutionary Computation. IEEE. 2012, pp. 1–8.
[6] Antonio LaTorre, Santiago Muelas, and José-Marı́a Peña. “A MOS-based dynamic memetic diﬀerential evolution algorithm
for continuous optimization: a scalability test”. In: Soft Computing 15.11 (2011), pp. 2187–2199.
Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

14 / 84

Parallelization

Algorithms capable of parallelization [1], [2].
GPU [3], [4].
CPU/OpenMP [5].

[1] Jing Tang, Meng Hiot Lim, and Yew Soon Ong. “Diversity-adaptive parallel memetic algorithm for solving large scale
combinatorial optimization problems”. In: Soft Computing 11.9 (2007), pp. 873–888.
[2] Hui Wang, Shahryar Rahnamayan, and Zhijian Wu. “Parallel diﬀerential evolution with self-adapting control parametersand generalized opposition-based learning for solving high-dimensional optimization problems”. In: Journal of Parallel andDistributed Computing 73.1 (2013), pp. 62–73.
[3] Kumara Sastry, David E Goldberg, and Xavier Llora. “Towards billion-bit optimization via a parallel estimation of
distribution algorithm”. In: Genetic and Evolutionary Computation Conference. ACM. 2007, pp. 577–584.
[4] Alberto Cano and Carlos Garcı́a-Martı́nez. “100 Million dimensions large-scale global optimization using distributed GPU
computing”. In: IEEE Congress on Evolutionary Computation. IEEE. 2016, pp. 3566–3573.
[5] AJ Umbarkar. “OpenMP Genetic Algorithm for Continuous Nonlinear Large-Scale Optimization Problems”. In:
International Conference on Soft Computing for Problem Solving. Springer. 2016, pp. 203–214.
Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

15 / 84

Hybridization (The best of both worlds)
Rationale: benefiting from unique features of diﬀerent optimizers.
EDA+DE: [1].
PSO+ABC: [2].
! Diﬀerent DE variants: JADE+SaNSDE [3].
! PSO+ACO [4].
! Minimum Population Search+CMA-ES [5].
!
!

[1] Yu Wang, Bin Li, and Thomas Weise. “Estimation of distribution and diﬀerential evolution cooperation for large scaleeconomic load dispatch optimization of power systems”. In: Information Sciences 180.12 (2010), pp. 2405–2420.
[2] LN Vitorino, SF Ribeiro, and Carmelo JA Bastos-Filho. “A hybrid swarm intelligence optimizer based on particles andartificial bees for high-dimensional search spaces”. In: IEEE Congress on Evolutionary Computation. IEEE. 2012, pp. 1–6.
[3] Sishi Ye et al. “A hybrid adaptive coevolutionary diﬀerential evolution algorithm for large-scale optimization”. In: IEEE
Congress on Evolutionary Computation. IEEE. 2014, pp. 1277–1284.
[4] Wu Deng et al. “A novel two-stage hybrid swarm intelligence optimization algorithm and application”. In: Soft
Computing 16.10 (2012), pp. 1707–1722.
[5] Antonio Bolufé-Röhler, Sonia Fiol-González, and Stephen Chen. “A minimum population search hybrid for large scale
global optimization”. In: IEEE Congress on Evolutionary Computation. IEEE. 2015, pp. 1958–1965.
Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

16 / 84

Decomposition Methods

Divide-and-conquer
Dimensionality reduction

Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

17 / 84

Variable Interaction, Linkage, Epistasis
What is variable interaction?
Genetics: two genes are said to interact with each other if they collectively
represent a feature at the phenotype level.
The extent to which the fitness of one gene can be suppressed by another gene.
The extent to which the value taken by one gene activates or deactivates the eﬀect
of another gene.

Why variable interaction?
The eﬀectiveness of optimization algorithms is aﬀected by how muchthey respect variable interaction.
Also applies to classic mathematical programming methods.

Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

18 / 84

Variable Interaction, Linkage, Epistasis
Illustrative Example
f (x, y ) = x 2 + λ1 y 2
g (x, y ) = x 2 + λ1 y 2 + λ2 xyx2

x2

Improvement Interval

Improvement Interval

A

A

x1
Improvement Interval

Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

Improvement Interval

x1

19 / 84

Definitions
Variable Interaction
A variable xi is separable or does not interact with any other variable iﬀ:!
"
arg minf (x) = arg minf (x), arg minf (x) ,xix∀xj ,j̸=iwhere x = (x1 , . . . , xn )⊤ is a decision vector of n dimensions.

Partial Separability
A function f (x) is partially separable with m independent subcomponents iﬀ:!
"
arg minf (x) = arg minf (x1 , . . . ), . . . , arg minf (. . . , xm ) ,
x

x1

xm

x1 , . . . , xm are disjoint sub-vectors of x, and 2 ≤ m ≤ n.
Note: a function is fully separable if sub-vectors x1 , . . . , xm are 1-dimensional (i.e.,m = n).
Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

20 / 84

Definitions

Full Nonseparability
A function f (x) is fully non-separable if every pair of its decision variables interact witheach other.

Additive Separability
A function is partially additively separable if it has the following general form:f (x) =m#fi (xi ) ,i =1

where xi are mutually exclusive decision vectors of fi , x = (x1 , . . . , xn )⊤ is a global
decision vector of n dimensions, and m is the number of independent subcomponents.

Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

21 / 84

Eﬀect of Variable Interaction
Sampling and Variation Operators:
GAs: inversion operator to promote tight linkage [1].
Increasing the likelihood of placing linked genes close to each other toavoid disruption by crossover.
! Rotation of the landscape has a detrimental eﬀect on GA [2].
!

The need for rotationally invariance:!

Model Building Methods:
Estimation of Distribution Algorithms and Evolutionary Strategies:
Covariance Matrix Adaptation.
⋆ Bayesian Optimization: Bayesian Networks.
⋆!
!

DE’s crossover is not rotationally invariant.
PSO is also aﬀected by rotation [3].

[1] David E Goldberg, Robert Lingle, et al. “Alleles, loci, and the traveling salesman problem”. In: International Conference
on Genetic Algorithms and Their Applications. Vol. 154. 1985, pp. 154–159.
[2] Ralf Salomon. “Re-evaluating genetic algorithm performance under coordinate rotation of benchmark functions. A surveyof some theoretical and practical aspects of genetic algorithms”. In: BioSystems 39.3 (1996), pp. 263–278.
[3] Daniel N Wilke, Schalk Kok, and Albert A Groenwold. “Comparison of linear and classical velocity update rules in particle
swarm optimization: Notes on scale and frame invariance”. In: International journal for numerical methods in engineering 70.8
(2007), pp. 985–1008.
Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

22 / 84

Eﬀect of Variable Interaction

1

Approximation and Surrogate Modelling:!
!

2

Should be able to capture variable interaction.
Second order terms of HDMR.

Local Search and Memetic Algorithms:
What subset of variables should be optimized in each iteration of local
search?
! Coordinate-wise search may not be eﬀective. Memetics perform well on
separable functions! A coincidence?!
!

3

Decomposition and Divide-and-Conquer:!

Interacting variables should be placed in the same component.

Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

23 / 84

Linkage Learning and Exploiting Modularity
Implicit Methods:!

In EC:
Estimation of Distribution Algorithms
Bayesian Optimization: BOA, hBOA, Linkage Trees⋆ Adaptive Encoding, CMA-ES⋆⋆!

Classic Optimization:⋆

Quasi-Newton Methods: Approximation of the Hessian.

Explicit Methods:!

In EC:
Random Grouping
Statistical Correlation-Based Methods⋆ Delta Grouping⋆ Meta Modelling⋆ Monotonicity Checking⋆ Diﬀerential Grouping⋆⋆!

Classic Optimization⋆⋆

Block Coordinate Descent
Adaptive Coordinate Descent

Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

24 / 84

Implicit Methods
Scaling Up EDAs:
Model Complexity Control [1].
Random Matrix Projection [2].
! Use of mutual information [3].
! Cauchy-EDA [4].
!
!

Scaling up CMA-ES:!
!

CC-CMA-ES [5].
LM-CMA [6].

[1] Weishan Dong et al. “Scaling up estimation of distribution algorithms for continuous optimization”. In: IEEE
Transactions on Evolutionary Computation 17.6 (2013), pp. 797–822.
[2] Ata Kabán, Jakramate Bootkrajang, and Robert John Durrant. “Toward large-scale continuous EDA: A random matrix
theory perspective”. In: Evolutionary Computation 24.2 (2016), pp. 255–291.
[3] Qi Xu, Momodou L Sanyang, and Ata Kabán. “Large scale continuous EDA using mutual information”. In: IEEE
Congress on Evolutionary Computation. IEEE. 2016, pp. 3718–3725.
[4] Momodou L Sanyang, Robert J Durrant, and Ata Kabán. “How eﬀective is Cauchy-EDA in high dimensions?” In: IEEE
Congress on Evolutionary Computation. IEEE. 2016, pp. 3409–3416.
[5] Jinpeng Liu and Ke Tang. “Scaling up covariance matrix adaptation evolution strategy using cooperative coevolution”. In:
International Conference on Intelligent Data Engineering and Automated Learning. Springer. 2013, pp. 350–357.
[6] Ilya Loshchilov. “LM-CMA: An Alternative to L-BFGS for Large-Scale Black Box Optimization”. In: Evolutionary
Computation (2015).
Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

25 / 84

Scalability issues of EDAs
Accurate estimation requires a large sample size which grows
exponentially with the dimensionality of the problem [1].
A small sample results in poor estimation of the eigenvalues [2].
The cost of sampling from a multi-dimensional Gaussian distribution
increases cubically with the problem size [3].

[1] Jerome Friedman, Trevor Hastie, and Robert Tibshirani. The elements of statistical learning. Vol. 1. Springer series instatistics Springer, Berlin, 2001.
[2] Roman Vershynin. “Introduction to the non-asymptotic analysis of random matrices”. In: arXiv preprint arXiv:1011.3027(2010).
[3] Weishan Dong and Xin Yao. “Unified eigen analysis on multivariate Gaussian based estimation of distribution algorithms”.
In: Information Sciences 178.15 (2008), pp. 3000–3023.
Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

26 / 84

Random Projection EDA

Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

27 / 84

Explicit Methods

A large problem can be subdivided into smaller and simpler problems.
Dates back to René Descartes (Discourse on Method).
Has been widely used in many areas:! Computer Science: Sorting algorithms (quick sort, merge sort)! Optimization: Large-scale linear programs (Dantzig)! Politics: Divide and rule (In Perpetual Peace by Immanuel Kant: Divide et impera
is the third political maxims.)

Acknowledgement: the above image is obtained from: http://draininbrain.blogspot.com.au/
Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

28 / 84

Decomposition in EAs: Cooperative Co-evolution [1][1] Mitchell A. Potter and Kenneth A. De Jong. “A cooperative coevolutionary approach to function optimization”. In: Proc.
Int. Conf. Parallel Problem Solving from Nature. Vol. 2. 1994, pp. 249–257.
Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

29 / 84

CC is a Framework

CC as a scalability agent:CC is not an optimizer.
Requires a component optimizer.
CC coordinates how the component optimizer is applied tocomponents.
A scalability agent.

Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

30 / 84

Challenges of CC

Main Questions
1

How to decompose the problem?

2

How to allocated resources?

3

How to coordinate?

Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

31 / 84

The Decomposition Challenge

How to decompose?
There are many possibilities.
Which decomposition is the best?

Optimal decomposition
It is governed by the interaction structure of decision variables.
An optimal decomposition is the one that minimizes the interaction
between components.

Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

32 / 84

Survey of Decomposition Methods
Uninformed Decomposition [1]!
!

n 1-dimensional components (the original CC)
k s-dimensional components.

Random Grouping [2]Statistical Correlation-Based Methods
Delta Grouping [3]Meta Modelling [4]Monotonicity Checking [5]Diﬀerential Grouping [6][1] F. van den Bergh and Andries P Engelbrecht. “A cooperative approach to particle swarm optimization”. In: IEEE
Transactions on Evolutionary Computation 2.3 (June 2004), pp. 225–239.
[2] Zhenyu Yang, Ke Tang, and Xin Yao. “Large scale evolutionary optimization using cooperative coevolution”. In:
Information Sciences 178.15 (2008), pp. 2985–2999.
[3] Mohammad Nabi Omidvar, Xiaodong Li, and Xin Yao. “Cooperative co-evolution with delta grouping for large scale
non-separable function optimization”. In: IEEE Congress on Evolutionary Computation. IEEE. 2010, pp. 1–8.
[4] Sedigheh Mahdavi, Mohammad Ebrahim Shiri, and Shahryar Rahnamayan. “Cooperative co-evolution with a new
decomposition method for large-scale optimization”. In: IEEE Congress on Evolutionary Computation. IEEE. 2014,
pp. 1285–1292.
[5] Wenxiang Chen et al. “Large-scale global optimization using cooperative coevolution with variable interaction learning”.
In: Parallel Problem Solving from Nature. Springer. 2010, pp. 300–309.
[6] Mohammad Nabi Omidvar et al. “Cooperative co-evolution with diﬀerential grouping for large scale optimization”. In:
IEEE Transactions on Evolutionary Computation 18.3 (2014), pp. 378–393.
Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

33 / 84

Illustrative Example (Canonical CC)
x1

x2

x6

x3

x4

x5

x7

Figure: Variable interaction of a hypothetical function.

n 1-dimensional components:
C1 : {x1 }, {x2 }, {x3 }, {x4 }, {x5 }, {x6 }, {x7 }C2 : {x1 }, {x2 }, {x3 }, {x4 }, {x5 }, {x6 }, {x7 }! ...
! Cc : {x1 }, {x2 }, {x3 }, {x4 }, {x5 }, {x6 }, {x7 }!
!

Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

34 / 84

Illustrative Example (fixed k s-dimensional)
x1

x2

x6

x3

x4

x5

x7

Figure: Variable interaction of a hypothetical function.

k s-dimensional (k = 2, s = 4):
C1 : {x1 , x2 , x3 , x4 }, {x5 , x6 , x7 }C2 : {x1 , x2 , x3 , x4 }, {x5 , x6 , x7 }! ...
! Cc : {x1 , x2 , x3 , x4 }, {x5 , x6 , x7 }!
!

Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

35 / 84

Illustrative Example (Random Grouping)
x1

x2

x6

x3

x4

x5

x7

Figure: Variable interaction of a hypothetical function.

Random Grouping (k = 2, s = 4):
C1 : {x2 , x3 , x6 , x5 }, {x7 , x1 , x4 }C2 : {x3 , x4 , x1 , x2 }, {x6 , x7 , x5 }! ...
! Cc : {x1 , x5 , x6 , x7 }, {x2 , x4 , x3 }!
!

Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

36 / 84

Random Grouping

Theorem
Given N cycles, the probability of assigning v interacting variables
x1 , x2 , ..., xv into one subcomponent for at least k cycles is:P(X ≥ k) =N " #"
!
N
r =k

r

1
mv −1

#r "

1−

1
mv −1

#N−r

(4)

where N is the number of cycles, v is the total number of interacting
variables, m is the number of subcomponents, and the random variable X
is the number of times that v interacting variables are grouped in one
subcomponent.

Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

37 / 84

Random Grouping

ExampleGiven n = 1000, m = 10, N = 50 and v = 4, we have:#"
1 50= 0.0488
P(X ≥ 1) = 1 − P(X = 0) = 1 − 1 − 310which means that over 50 cycles, the probability of assigning 4 interacting
variables into one subcomponent for at least 1 cycle is only 0.0488. As we
can see this probability is very small, and it will be even less if there are
more interacting variables.

Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

38 / 84

1

P(X >= 1), N=50
P(X >= 1), N=10000

0.9
0.8
0.7

Probability

0.6
0.5
0.4
0.3
0.2
0.1
0
2

3

4

5
6
7
Number of interacting variables(v)

8

9

10

Figure: Increasing v , the number of interacting variables will significantly decrease
the probability of grouping them in one subcomponent, given n = 1000 and
m = 10.
Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

39 / 84

1

P(X>=1),v=3
P(X>=1),v=4
P(X>=1),v=5
P(X>=1),v=6

0.9
0.8
0.7

Probability

0.6
0.5
0.4
0.3
0.2
0.1
0
0

1000

2000

3000

4000
5000
6000
Number of cycles

7000

8000

9000

10000

Figure: Increasing N, the number of cycle increases the probability of grouping v
number of interacting variables in one subcomponent.
Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

40 / 84

Illustrative Example (Informed with Fixed Groups)
x1

x2

x6

x3

x4

x5

x7

Figure: Variable interaction of a hypothetical function.

Delta Grouping (k = 2, s = 4):
C1 : {x1 , x5 , x2 , x4 }, {x3 , x6 , x7 }C2 : {x3 , x5 , x6 , x7 }, {x1 , x2 , x4 }! ...
! Cc : {x3 , x6 , x1 , x4 }, {x2 , x5 , x7 }!
!

Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

41 / 84

Delta Groupingx2

x2

Improvement Interval

Improvement Interval

A

A

x1
Improvement Interval

Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

Improvement Interval

x1

42 / 84

Infomred Decompositions with Fixed Groups
Adaptive Variable Partitioning [1].
Delta Grouping [2].
Min/Max-Variance Decomposition (MiVD/MaVD) [3].
!

Sorts the dimensions based on the diagonal elements of the covariancematrix in CMA-ES.

Fitness Diﬀerence Partitioning [4], [5], [6].

[1] Tapabrata Ray and Xin Yao. “A cooperative coevolutionary algorithm with correlation based adaptive variable
partitioning”. In: IEEE Congress on Evolutionary Computation. IEEE. 2009, pp. 983–989.
[2] Mohammad Nabi Omidvar, Xiaodong Li, and Xin Yao. “Cooperative co-evolution with delta grouping for large scale
non-separable function optimization”. In: IEEE Congress on Evolutionary Computation. IEEE. 2010, pp. 1–8.
[3] Jinpeng Liu and Ke Tang. “Scaling up covariance matrix adaptation evolution strategy using cooperative coevolution”. In:
International Conference on Intelligent Data Engineering and Automated Learning. Springer. 2013, pp. 350–357.
[4] Eman Sayed, Daryl Essam, and Ruhul Sarker. “Dependency identification technique for large scale optimization problems”.
In: IEEE Congress on Evolutionary Computation. IEEE. 2012, pp. 1–8.
[5] Eman Sayed et al. “Decomposition-based evolutionary algorithm for large scale constrained problems”. In: Information
Sciences 316 (2015), pp. 457–486.
[6] Adan E Aguilar-Justo and Efrén Mezura-Montes. “Towards an improvement of variable interaction identification forlarge-scale constrained problems”. In: IEEE Congress on Evolutionary Computation. IEEE. 2016, pp. 4167–4174.
Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

43 / 84

Infomred Decompositions with Variable Groups

Multilevel Grouping: MLCC [1], MLSoft [2].
Adaptive Variable Partitioning 2 [3].
4CDE [4].
Fuzzy Clustering [5].

[1] Zhenyu Yang, Ke Tang, and Xin Yao. “Multilevel cooperative coevolution for large scale optimization”. In: IEEE Congress
on Evolutionary Computation. IEEE. 2008, pp. 1663–1670.
[2] Mohammad Nabi Omidvar, Yi Mei, and Xiaodong Li. “Eﬀective decomposition of large-scale separable continuous functions
for cooperative co-evolutionary algorithms”. In: IEEE Congress on Evolutionary Computation. IEEE. 2014, pp. 1305–1312.
[3] Hemant Kumar Singh and Tapabrata Ray. “Divide and conquer in coevolution: A diﬃcult balancing act”. In:
Agent-Based Evolutionary Search. Springer, 2010, pp. 117–138.
[4] Yazmin Rojas and Ricardo Landa. “Towards the use of statistical information and diﬀerential evolution for large scale
global optimization”. In: International Conference on Electrical Engineering Computing Science and Automatic Control. IEEE.
2011, pp. 1–6.
[5] Jianchao Fan, Jun Wang, and Min Han. “Cooperative coevolution for large-scale optimization based on kernel fuzzyclustering and variable trust region methods”. In: IEEE Transactions on Fuzzy Systems 22.4 (2014), pp. 829–839.
Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

44 / 84

Illustrative Example (Exact Methods)
x1

x2

x6

x3

x4

x5

x7

Figure: Variable interaction of a hypothetical function.

Diﬀerential Grouping and Variable Interaction Learning:
C1 : {x1 , x2 , x4 }, {x3 , x5 , x6 , x7 }C2 : {x1 , x2 , x4 }, {x3 , x5 , x6 , x7 }! ...
! Cc : {x1 , x2 , x4 }, {x3 , x5 , x6 , x7 }!
!

Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

45 / 84

Monotonicity Check∃ x, xi′ , xj′ :f (x1 , ..., xi , ..., xj , ..., xn ) < f (x1 , ..., xi′ , ..., xj , ..., xn )∧f (x1 , ..., xi , ..., xj′ , ..., xn ) > f (x1 , ..., xi′ , ..., xj′ , ..., xn )Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

46 / 84

Monotonicity Check (Algorithms)
Linkage Identification by Non-Monotonicity Detection [1]Adaptive Coevolutionary Learning [2]Variable Interaction Learning [3]Variable Interdependence Learning [4]Fast Variable Interdependence [5][1] Masaharu Munetomo and David E Goldberg. “Linkage identification by non-monotonicity detection for overlapping
functions”. In: Evolutionary Computation 7.4 (1999), pp. 377–398.
[2] Karsten Weicker and Nicole Weicker. “On the improvement of coevolutionary optimizers by learning variableinterdependencies”. In: IEEE Congress on Evolutionary Computation. Vol. 3. IEEE. 1999, pp. 1627–1632.
[3] Wenxiang Chen et al. “Large-scale global optimization using cooperative coevolution with variable interaction learning”.
In: Parallel Problem Solving from Nature. Springer. 2010, pp. 300–309.
[4] Liang Sun et al. “A cooperative particle swarm optimizer with statistical variable interdependence learning”. In:
Information Sciences 186.1 (2012), pp. 20–39.
[5] Hongwei Ge et al. “Cooperative diﬀerential evolution with fast variable interdependence learning and cross-cluster
mutation”. In: Applied Soft Computing 36 (2015), pp. 300–314.
Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

47 / 84

Diﬀerential Grouping [1]Theorem
Let f (x) be an additively separable function. ∀a, b1 ̸= b2 , δ ∈ R, δ ̸= 0, if
the following condition holds∆δ,xp [f ](x)|xp =a,xq =b1 ̸= ∆δ,xp [f ](x)|xp =a,xq =b2 ,(5)then xp and xq are non-separable, where∆δ,xp [f ](x) = f (. . . , xp + δ, . . . ) − f (. . . , xp , . . . ),(6)

refers to the forward diﬀerence of f with respect to variable xp withinterval δ.

[1] Mohammad Nabi Omidvar et al. “Cooperative co-evolution with diﬀerential grouping for large scale optimization”. In:
IEEE Transactions on Evolutionary Computation 18.3 (2014), pp. 378–393.
Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

48 / 84

Separability ⇒ ∆1 = ∆2
Assuming:
f (x) =m!

fi (xi )i =1

We prove that:
Separability ⇒ ∆1 = ∆2

By contraposition (P ⇒ Q ≡ ¬Q ⇒ ¬P):
∆1 ̸= ∆2 ⇒ non-separabilityor|∆1 − ∆2 | > ϵ ⇒ non-separability

Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

49 / 84

Deductive Reasoning

Strong Syllogism

Weak Syllogism

A⇒B

A⇒B

A is true

A is false∴ B is true

∴ B is less plausible

A⇒B

A⇒B

B is false

B is true∴ A is false∴ A is more plausible

Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

50 / 84

Deductive Reasoning - Example

Strong Syllogism

Weak Syllogism

Rain ⇒ CloudRain ⇒ Cloud

It is rainy

It is not rainy∴ It is cloudy∴ Cloud becomes less likely

Rain ⇒ CloudRain ⇒ Cloud

It is not cloudy

It is cloudy∴ It is not rainy∴ Rain becomes more likely

Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

51 / 84

The Diﬀerential Grouping Algorithm

Detecting Non-separable Variables|∆1 − ∆2 | > ϵ ⇒ non-separability

Detecting Separable Variables|∆1 − ∆2 | ≤ ϵ ⇒ Separability (more plausible)

Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

52 / 84

Example
Consider the non-separable objective function f (x1 , x2 ) = x12 + λx1 x2 + x22 ,λ ̸= 0.
∂f (x1 , x2 )= 2x1 + λx2 .
∂x1This clearly shows that the change in the global objective function withrespect to x1 is a function of x1 and x2 . By applying the Theorem:$% $%∆δ,x1 [f ] = (x1 + δ)2 + λ(x1 + δ)x2 + x22 − x12 + λx1 x2 + x22= δ2 + 2δx1 + λx2 δ.

Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

53 / 84

Diﬀerential Grouping vs CCVIL
x1′ = x1 + δ

x1
2

<
x2
1.5

A
1

>

x2′

B

0.5

0

-0.5

C

-1

-1.5

-2
-2

-1.5

-1

-0.5

0

0.5

1

1.5

2

Figure: Detection of interacting variables using diﬀerential grouping and CCVIL
on diﬀerent regions of a 2D Schwefel Problem 1.2.

Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

54 / 84

Diﬀerential Grouping Family of Algorithms
Linkage Identification by Non-linearity Check (LINC, LINC-R) [1]Diﬀerential Grouping (DG) [2]Global Diﬀerential Grouping (GDG) [3]
Improved Diﬀerential Grouping (IDG) [4]eXtended Diﬀerential Grouping (XDG) [5]Graph-based Diﬀerential Grouping (gDG) [6]Fast Interaction Identification [7][1] Masaru Tezuka, Masaharu Munetomo, and Kiyoshi Akama. “Linkage identification by nonlinearity check for real-coded
genetic algorithms”. In: Genetic and Evolutionary Computation–GECCO 2004. Springer. 2004, pp. 222–233.
[2] Mohammad Nabi Omidvar et al. “Cooperative co-evolution with diﬀerential grouping for large scale optimization”. In:
IEEE Transactions on Evolutionary Computation 18.3 (2014), pp. 378–393.
[3] Yi Mei et al. “Competitive Divide-and-Conquer Algorithm for Unconstrained Large Scale Black-Box Optimization”. In:
ACM Transaction on Mathematical Software 42.2 (June 2015), p. 13.
[4] Mohammad Nabi Omidvar et al. IDG: A Faster and More Accurate Diﬀerential Grouping Algorithm. Technical Report
CSR-15-04. University of Birmingham, School of Computer Science, Sept. 2015.
[5] Yuan Sun, Michael Kirley, and Saman Kumara Halgamuge. “Extended diﬀerential grouping for large scale global
optimization with direct and indirect variable interactions”. In: Genetic and Evolutionary Computation Conference. ACM.
2015, pp. 313–320.
[6] Yingbiao Ling, Haijian Li, and Bin Cao. “Cooperative co-evolution with graph-based diﬀerential grouping for large scale
global optimization”. In: International Conference on Natural Computation, Fuzzy Systems and Knowledge Discovery. IEEE.
2016, pp. 95–102.
[7] Xiao-Min Hu et al. “Cooperation coevolution with fast interdependency identification for large scale optimization”. In:
Information Sciences 381 (2017), pp. 142–160.
Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

55 / 84

Shortcomings of Diﬀerential Grouping

Cannot detect the overlapping functions.
Slow if all interactions are to be checked.
Requires a threshold parameter (ϵ).
Can be sensitive to the choice of the threshold parameter (ϵ).

Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

56 / 84

Algorithm 1: DG2(Λ, F, f̌, fbase , Γ) = ISM(f , n, x, x);
Θ = DSM(Λ, F, f̌, fbase , n);(k, y1 , . . . , yk ) = ConnComp(Θ) ;xsep = {}, g = 0;
for i = 1 → k do
if |yi | = 1 thenxsep = xsep ∪ yi ;else
g = g + 1, xg = yi ;Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

57 / 84

Diﬀerential Grouping 2
x3(a, b, c ′ )(a, b ′ , c ′ )(a′ , b, c ′ )32(a, b, c)(a, b ′ , c)x2

1(a′ , b, c)(a′ , b ′ , c)x1

Figure: Geometric representation of point generation in DG2 for a 3D function.

x1↔ x2 :∆(1)=f (a′ , b, c)−f (a, b, c),∆(2)=f (a′ , b ′ , c)−f (a, b ′ , c)x1↔ x3 :∆(1)=f (a′ , b, c)−f (a, b, c),∆(2)=f (a′ , b, c ′ )−f (a, b, c ′ )x2↔ x3 :∆(1)=f (a, b ′ , c)−f (a, b, c),∆(2)=f (a, b ′ , c ′ )−f (a, b, c ′ ),Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

58 / 84

Algorithm 2: ISM
Λ = 0n×n ;Fn×n = NaNn×n ;f̌n×1 = NaNn×1 ;x(1) = x, fbase = f (x(1) ), Γ = 1;m = 12 (x + x);
for i = 1 → n − 1 doif ¬isnan(f̌i ) then(2)x(2) = x(1) , xi = mi ;(2)f̌i = f (x ), Γ = Γ + 1;// matrix of all NaNs// vector of all NaNs

for j = i + 1 → n doif ¬isnan(f̌i ) then(3)x(3) = x(1) , xj = mj ;(3)f̌j = f (x ), Γ = Γ + 1;
(4)

(4)

x(4) = x(1) , xi = mi , xj = mj ;Fij = f (x(4) ), Γ = Γ + 1;∆(1) = f̌i − f (x(1) );∆(2) = Fij − f̌j ;Λij = |∆(1) − ∆(2) |;Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

59 / 84

DG2: Accuracyn = ±s × β e−p ,

0

1

2

3

4

5

6

7

Figure: Non-uniform distribution of floating-point numbers for a hypotheticalsystem (β = 2, emin = −1, emax = 3, and p = 3). The vertical bars denote all the
representable numbers in this system.

TheoremIf x ∈ R lies in the range of F, thenfl (x) = x(1 + δ),|δ| < µM ,where µM is called the unit roundoﬀ, which is equal to 12 β 1−p .
Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

60 / 84

DG2: Accuracy

Theorem
Given a floating-point number system that satisfies IEEE 754such that
|δi | < µM . We have:k&(1 + δi )ei = 1 + θk ,
(7)
i =1

where
|θk | ≤µM:= γk , ei = ±1,
1 − nµM

provided that kµM < 1.

Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

61 / 84

DG2: Accuracy

ˆ 1 = f (x) ⊖ f (x′ ) = (f (x) − f (x′ ))(1 + δ1 ) = ∆(1) (1 + δ1 ),∆ˆ 2 = f (y) ⊖ f (y′ ) = (f (y) − f (y′ ))(1 + δ2 ) = ∆(2) (1 + δ2 ),∆ˆ1 ⊖ ∆
ˆ 2 | = |∆
ˆ1 − ∆
ˆ 2 |(1 + δ3 )λ̂ = |∆'= 'f (x)(1 + δ1 )(1 + δ3 ) − f (x′ )(1 + δ1 )(1 + δ3 )'− f (y)(1 + δ2 )(1 + δ3 ) + f (y′ )(1 + δ2 )(1 + δ3 )' .

Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

62 / 84

DG2: Accuracy

'(
) (
) ''
'
|λ − λ̂| ≤ γ2 ' f (x) − f (x′ ) − f (y) − f (y′ ) '
'(
) (
) ''
'
= γ2 ' f (x) + f (y′ ) − f (y) + f (x′ ) '
*(
) (
)+
≤ γ2 · max f (x) + f (y′ ) , f (y) + f (x′ ) := einf .

(8)

Equation (8) is based on the assumption that the codomain of f is
non-negative, i.e., f : R → R+
0 . A more general form for f : R → R is asfollows:()(9)
einf = γ2 |f (x)| + |f (y′ )| + |f (y)| + |f (x′ )| .

Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

63 / 84

DG2: Accuracy|f (·) − fˆ(·)| ≤ γ√φ f (·) := esup .

(10)

esup = γ√n max{f (x), f (x′ ), f (y), f (y′ )}

(11)

ϵ=

Mohammad Nabi Omidvar, Xiaodong Liη0η1einf +
esup ,
η0 + η1
η0 + η1

Decomposition and CC for LSGO

(12)64 / 84

Algorithm 3: Θ = DSM(Λ, F, f̌, fbase,n )Θ = NaNn×n ;η1 = η2 = 0;
for i = 1 → n − 1 dofor j = i + 1 → n do
fmax = max{fbase , Fij , f̌i , f̌j };einf = γ2 · max{fbase + Fij , f̌i + f̌j };esup = γ√n · fmax ;if Λij < einf then
Θi ,j = 0; η0 = η0 + 1;
else if Λij > esup then
Θi ,j = 1; η1 = η1 + 1;
for i = 1 → n − 1 dofor j = i + 1 → n do
fmax = max{fbase , Fij , f̌i , f̌j };einf = γ2 · max{fmathrmbase + Fij , f̌i + f̌j };esup = γ√n · fmax ;if Θi ,j ̸= NaN then10
· einf + η0η+η
· esup ;ϵ = η0η+η1
1
if Λij > ϵ then
Θi ,j = 1;else
Θi ,j = 0;

Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

65 / 84

Direct/Indirect Interactions
Indirect Interactions
In an objective function f (x), decision variables xi and xj interact directly(denoted by xi ↔ xj ) if
'
∂f ''
̸= 0,
∃a :
∂xi ∂xj 'x=a
decision variables xi and xj interact indirectly if∂f= 0,∂xi ∂xjand there exists a set of decision variables {xk1 , ..., xks } such thatxi ↔ xl1 , ..., xks ↔ xj .

Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

66 / 84

Eﬃciency vs Accuracy
Saving budget at the expense of missing overlaps:
eXtended Diﬀerential Grouping [1].
Fast Interdependecy Identification [2].

1

2

6

3
3

5

4

5
1

2

4
6

Figure: The interaction structures represented by the two graphs cannot be
distinguished by XDG.
[1] Yuan Sun, Michael Kirley, and Saman Kumara Halgamuge. “Extended diﬀerential grouping for large scale global
optimization with direct and indirect variable interactions”. In: Genetic and Evolutionary Computation Conference. ACM.
2015, pp. 313–320.
[2] Xiao-Min Hu et al. “Cooperation coevolution with fast interdependency identification for large scale optimization”. In:
Information Sciences 381 (2017), pp. 142–160.
Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

67 / 84

Benchmark Suites

CEC’2005 Benchmark Suite (non-modular)
CEC’2008 LSGO Benchmark Suite (non-modular)
CEC’2010 LSGO Benchmark Suite
CEC’2013 LSGO Benchmark Suite

Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

68 / 84

Challenges of CC

Main Questions
1

How to decompose the problem?

2

How to allocated resources?

3

How to coordinate?

Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

69 / 84

The Imbalance Problem

Non-uniform contribution of components.

Imbalanced Functions
f (x) =m!

wi fi (xi ),

(13)

i =1

wi = 10sN (0,1) ,Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

70 / 84

The Imbalance Problem (2)1e+16

DECC-I-Nonsep
DECC-I-Sep

1e+14
1e+12
1e+10
1e+08
1e+06
10000
0

5000

10000

15000

20000

25000

30000

Iterations

Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

71 / 84

Contribution-Based Cooperative Co-evolution (CBCC)
Types of CC
CC: round-robin optimization of components.
CBCC: favors components with a higher contribution.
!
!

Quantifies the contribution of components.
Optimizes the one with the highest contribution.

How to Quantify the Contribution
For quantification of contributions a relatively accurate decompositionis needed.
Changes in the objective value while other components are kept
constant.

Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

72 / 84

1e+08
1e+06
10000
100
1
0.01
0.0001
1e-06
1e-08
1e-10
1e-12

S1
S2
S3
S4
S5
S6
S7
S8

f(x)

S1
S2
S3
S4
S5
S6
S7
S8

f(x)

1e+14
1e+13
1e+12
1e+11
1e+10
1e+09
1e+08
1e+07
1e+06
100000
10000
1000

0

5000 10000 15000 20000 25000 30000

Evaluations(a) Round-Robin CC

Mohammad Nabi Omidvar, Xiaodong Li

05000 10000 15000 20000 25000 30000

Evaluations(b) Contribution-Based CC

Decomposition and CC for LSGO

73 / 84

Contribution-Aware Algorithms

Contribution-Based Cooperative Co-evolution (CBCC) [1], [2].
Incremental Cooperative Coevolution [3]Multilevel Framework for LSGO [4][1] Mohammad Nabi Omidvar, Xiaodong Li, and Xin Yao. “Smart use of computational resources based on contribution forcooperative co-evolutionary algorithms”. In: Proc. of Genetic and Evolutionary Computation Conference. ACM, 2011,
pp. 1115–1122.
[2] Mohammad Nabi Omidvar et al. “CBCC3 – A Contribution-Based Cooperative Co-evolutionary Algorithm with Improved
Exploration/Exploitation Balance”. In: Proc. IEEE Congr. Evolutionary Computation. 2016, pp. 3541–3548.
[3] Sedigheh Mahdavi, Shahryar Rahnamayan, and Mohammad Ebrahim Shiri. “Incremental cooperative coevolution forlarge-scale global optimization”. In: Soft Computing (2016), pp. 1–20.
[4] Sedigheh Mahdavi, Shahryar Rahnamayan, and Mohammad Ebrahim Shiri. “Multilevel framework for large-scale global
optimization”. In: Soft Computing (2016), pp. 1–30.
Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

74 / 84

Large-Scale Multiobjective Optimization

Large-scale multiobjective optimization is growing popularity:
Development of a benchmark [1].
Exploiting modularity using CC [2], [3], [4].
Analysis of the existing benchmarks [5].

[1] Ran Cheng et al. “Test problems for large-scale multiobjective and many-objective optimization”. In: IEEE Transactions
on Cybernetics (2016).
[2] Luis Miguel Antonio and Carlos A Coello Coello. “Use of cooperative coevolution for solving large scale multiobjective
optimization problems”. In: IEEE Congress on Evolutionary Computation. IEEE. 2013, pp. 2758–2765.
[3] Luis Miguel Antonio and Carlos A Coello Coello. “Decomposition-Based Approach for Solving Large Scale Multi-objective
Problems”. In: Parallel Problem Solving from Nature. Springer. 2016, pp. 525–534.
[4] Xiaoliang Ma et al. “A multiobjective evolutionary algorithm based on decision variable analyses for multiobjective
optimization problems with large-scale variables”. In: IEEE Transactions on Evolutionary Computation 20.2 (2016),
pp. 275–298.
[5] Ke Li et al. “Variable Interaction in Multi-objective Optimization Problems”. In: Parallel Problem Solving from Nature.
Springer International Publishing. 2016, pp. 399–409.
Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

75 / 84

Analysis of ZDT

⎛

x1
⎜
x2⎜
⎜
x3⎜
⎜
⎜
x4⎜
⎜
x5⎜
⎝
x6

0 1 1 1 1 1
1 0 1 1 1 1
1 1 0 1 1 1
1 1 1 0 1 1
1 1 1 1 0 1
1 1 1 1 1 0x1 x2 x3 x4 x5 x6

⎞
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠

1

2

6

3

5

4

Figure: Variable interaction structures of the f2 function of ZDT test suite.

Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

76 / 84

Analysis of DTLZ1-DTLZ4
1

2

6

1

3

5

4

2

6

1

3

5

4

2

6

3

5

4

Figure: Variable interaction graphs of DTLZ1 to DTLZ4 .

Proposition 1
For DTLZ1 to DTLZ4, ∀fi , i ∈ {1, · · · , m}, we divide the corresponding decisionvariables into two non-overlapping sets: xI = (x1 , · · · , xℓ )T , ℓ = m − 1 for i ∈ {1, 2}
while ℓ = m − i + 1 for i ∈ {3, · · · , m}; and xII = (xm , · · · , xn )T . All members of xI not
only interact with each other, but also interact with those of xII ; all members of xII are
independent from each other.

Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

77 / 84

Analysis of DTLZ5-DTLZ7
1

2

6

1

3

5

4

2

6

1

3

5

4

2

6

3

5

4

Figure: Variable interaction graphs of DTLZ5 and DTLZ6.

Proposition 2
For DTLZ5 and DTLZ6, ∀fi , i ∈ {1, · · · , m}, we divide the corresponding decisionvariables into two non-overlapping sets: xI = (x1 , · · · , xℓ )T , ℓ = m − 1 for i ∈ {1, 2}
while ℓ = m − i + 1 for i ∈ {3, · · · , m}; and xII = (xm , · · · , xn )T . For fi , wherei ∈ {1, · · · , m − 1}, all members of xI and xII interact with each other; for fm , we havethe same interaction structure as DTLZ1-DTLZ4.

Proposition 3
All objective functions of DTLZ7 are fully separable.
Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

78 / 84

Some Future Directions (I)What if the components have overlap?
Diﬀerential group is oﬀ-line and can be time-consuming. Is there amore eﬃcient method?
Do we need to get 100% accurate grouping? What is the relationshipbetween grouping accuracy and optimality achieved by a CC
algorithm?

Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

79 / 84

Some Future Directions (II)CC for combinatorial optimization, e.g.,!

Y. Mei, X. Li and X. Yao, “Cooperative Co-evolution with RouteDistance Grouping for Large-Scale Capacitated Arc Routing Problems,”
IEEE Transactions on Evolutionary Computation, 18(3):435-449, June
2014.

However, every combinatorial optimization problem has its own
characteristics. We need to investigate CC for other combinatorial
optimization problems.

Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

80 / 84

Some Future Directions (III)

Learning variable interdependencies is a strength of estimation of
distribution algorithms (EDAs), e.g.,
W. Dong, T. Chen, P. Tino and X. Yao, “Scaling Up Estimation ofDistribution Algorithms for Continuous Optimization,” IEEE
Transactions on Evolutionary Computation, 17(6):797-822, December
2013.
! A. Kaban, J. Bootkrajang and R.J. Durrant. “Towards Large Scale
Continuous EDA: A Random Matrix Theory Perspective.” Evolutionary
Computation!

Interestingly, few work exists on scaling up EDAs.

Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

81 / 84

LSGO Resources

There is an IEEE Computational Intelligence Society (CIS) Task Forceon LSGO:
Upcoming LSGO Tutorials!
!

July 2017 GECCO (Berlin, Germany).
November 2017 SEAL (Shenzhen, China).

LSGO Repository: http://www.cercia.ac.uk/projects/lsgo

Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

82 / 84

Acknowledgement

Thanks goes toProfessor Xin Yao and EPSRC (grant nos. EP/K001523/1 andEP/J017515/1) for supporting this tutorial.
Dr. Ata Kaban and Dr. Momodou L. Sanyang for allowing us to usesome figures from their publications.

Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

83 / 84

Questions

Thanks for your attention!

Mohammad Nabi Omidvar, Xiaodong Li

Decomposition and CC for LSGO

84 / 84