#  cMLSGA: A Co-Evolutionary Multi-Level Selection Genetic Algorithm for
Multi-Objective Optimization

P. A. Grudniewski<EMAIL_ADDRESS>A. J. Sobey<EMAIL_ADDRESS>Fluid
Structure Interactions Group, University of Southampton, Southampton, SO16
7QF, England, UK  Marine and Maritime Group, Data-centric Engineering, The
Alan Turing Institute, The British Library, London, NW1 2DB, England, UK

###### Abstract

In practical optimisation the dominant characteristics of the problem are
often not known prior. Therefore, there is a need to develop general solvers
as it is not always possible to tailor a specialised approach to each
application. The hybrid form of Multi-Level Selection Genetic Algorithm
(MLSGA) already shows good performance on range of problems due to its
diversity-first approach, which is rare among Evolutionary Algorithms. To
increase the generality of its performance this paper proposes a distinct set
of co-evolutionary mechanisms, which defines co-evolution as competition
between collectives rather than individuals. This distinctive approach to co-
evolutionary provides less regular communication between sub-populations and
different fitness definitions between individuals and collectives. This
encourages the collectives to act more independently creating a unique sub-
regional search, leading to the development of co-evolutionary MLSGA (cMLSGA).
To test this methodology nine genetic algorithms are selected to generate
several variants of cMLSGA, which incorporates these approaches at the
individual level. The new mechanisms are tested on over 100 different
functions and benchmarked against the 9 state-of-the-art competitors in order
to find the best general solver. The results show that the diversity of co-
evolutionary approaches is more important than their individual performances.
This allows the selection of two competing algorithms that improve the
generality of cMLSGA, without large loss of performance on any specific
problem type. When compared to the state-of-the-art, the proposed methodology
is the most universal and robust, leading to an algorithm more likely to solve
complex problems with limited knowledge about the search space.

###### keywords:

Genetic algorithms, co-evolutionary, multi-level selection, multi-objective
optimisation.

##  1 The requirement for general algorithms

There is a growing interest in computer-aided optimisation of practical
problems. This has driven the rapid development of a diverse range of
evolutionary algorithms (EAs). Most of the current state-of-the-art algorithm
development is driven by the benchmarking problems developed as part of the
evolutionary computation literature to test their performance. The result is
that most of algorithms are specialists to these problems with a bias towards
high convergence over diversity. They exhibit high performance on this range
of problems, as can be seen in multiple competitive benchmarks [52, 32, 24]
and is summarised in Table 1 for unconstrained cases and in Table 2 for
constrained and imbalanced problems; but when they are applied to practical
applications they can exhibit poor performance, [19, 44, 48, 35]. This is
supported by the lack of uptake of many of the algorithms with top performance
in the evolutionary computation benchmarking exercises in the practical
literature and the prevalence of NSGA-II in many fields; this is despite its
original development dating back to 2002 and many newer solvers having been
developed since then. It is the only current algorithm that has been shown to
have high performance across the range of current benchmarking problems, shown
in Tables 1 \- 2, where the red boxes indicate a lack of testing on a given
problem set.

Table 1: Summary of the literature on the unconstrained benchmarking sets used to test genetic algorithms. | Test set
---|---
Algorithm |  ZDT |  DTLZ |  WFG |  UF
NSGA-II |  [13, 29] |  [12, 42, 29] |  [21, 29] |  [52, 29]
NSGA-III |  [42, 28] |  [11, 42, 28, 34] |  [11, 28] |  [28, 34]
U-NSGA-III |  [42] |  [42, 34] |  |  [34]
GAME |  |  |  |
aGAME |  |  |  |
MOEA/D |  [51, 29, 28] |  [11, 51, 29, 28, 34] |  [29, 28] |  [52, 29, 28, 34]
MOEA/D-DE |  |  |  |  [6]
MOEA/D-M2M |  |  |  [25] |  [25]
MOEA/D-PSF |  |  |  [25] |  [25]
MOEA/D-MSF |  |  |  [25] |  [25]
LiuLi |  |  |  |  [52]
DMOEA-DD |  |  |  |  [52]
COEA |  [17] |  [17] |  |
HEIA |  [29] |  [29] |  [29] |  [29]
BCE |  [28] |  [28] |  [28] |  [28]
MTS |  [46] |  [46] |  [46] |  [52]
Table 2: Summary of the literature on the constrained and imbalanced benchmarking sets used to test genetic algorithms. | Test set
---|---
| Constrained | Imbalanced
Algorithm |  CF |  DTLZ |  IMB |  DAS-CMOP |  MOP |  IMB
NSGA-II |  [52] |  [12, 42] |  [32] |  [16] |  [31] |  [32]
NSGA-III |  |  [22, 42] |  |  [16] |  |
U-NSGA-III |  |  [42] |  |  |  |
GAME |  [1] |  |  |  |  |
aGAME |  [2] |  |  |  |  |
MOEA/D |  |  [22] |  [32] |  [16] |  |  [32]
MOEA/D-DE |  [6] |  |  |  |  [31] |
MOEA/D-M2M |  |  |  |  |  [31, 25] |
MOEA/D-PSF |  |  |  |  |  [25] |
MOEA/D-MSF |  |  |  |  |  [25] |
LiuLi |  [52, 1] |  |  |  |  |
DMOEA-DD |  [52, 1] |  |  |  |  |
COEA |  |  |  |  |  |
HEIA |  |  |  |  |  |
BCE |  |  |  |  |  |
MTS |  [52, 1] |  |  |  |  |

There are a number of factors for why these new algorithms may not have found
success in the applied literature. Firstly, in many practical applications the
characteristics of the search and objective spaces are often not well
understood prior to performing the optimisation. Therefore, it is not possible
to select the most appropriate solvers in advance. Secondly, the benchmarking
problems commonly utilised in the evolutionary literature are dominated by one
main characteristic, whereas real-world problems may contain multiple dominant
features. Lastly, the current state-of-the-art focuses on unconstrained
continuous problems, with few efficient algorithms specialised for problems
with other characteristic types, whilst most of real-world applications tend
to have discontinuous, multi-modal and imbalanced search spaces. This is
reflected in Table 1 and in Table 2 where it is possible to see a trend
towards limited benchmarking during the development of an algorithm, although
many of these test problems were not available during the development of many
of these algorithms, and only the top performing algorithms eventually being
tested over a large range of test problems. There is a prevalence towards
testing on unconstrained problems, with all but the GAME and aGAME tested on
these problems, with more limited testing on the constrained and imbalanced
problems.

It is known that convergence first algorithms struggle on a range of problems
as they do not explore the entire decision variable and objective spaces due
to their lack of diversity [32, 31]. This is supported by investigations on
practical problems where algorithms with better diversity preservation show
better performance as the complexity of the problem increases [19, 44]. This
partly explains the success of NSGA-II, which has excellent diversity
retention and can be classed as a general solver. Despite this, most of the
currently developed evolutionary algorithms utilise a ”convergence first,
diversity second” approach [32] where the mechanisms that promote convergence
are preferred, while diversity is obtained using secondary methods such as
crowding distance calculations [13], external archive refining [57], problem
decomposition [51, 33, 30] or indicator-based solution selection [55, 4, 39].

A recent methodology developed by Grudniewski and Sobey [43], [18], Multi-
Level Selection Genetic Algorithm (MLSGA), introduces a Multi-Level Selection
(MLS) mechanism, via sub-populations called collectives. The approach is based
on distinct mechanisms at the individual and collective level, where the
collective level utilises reproduction of sub-groups based on selection and
elimination of collectives. This reproduction is based on distinctive fitness
definitions, allowing information exchange between groups and ensuring that
collectives with different fitness evaluations focus their search on different
parts of the search space promoting a ”diversity first, convergence second”
approach. The diversity is generated by the unique region-based search, which
is enhanced by separating the fitness function so that each level focuses its
reproduction on different parts of the objective space. This approach has been
shown to improve the diversity of the search and does not require extensive a
priori knowledge about the problem.

In parallel to the development of MLSGA, a new range of co-evolutionary
algorithms, such as HEIA and BCE, have been shown to have strong general
performance. They improve the generality of the search by merging multiple
reproduction and/or improvement mechanisms which increases the chance that an
effective approach will be available or by allowing the algorithm to self-
adapt to the optimised problem during the process [37, 10]. However, in most
cases the self-adapting algorithms have either high computational complexity
or are sensitive to predefined hyperparameters [54], making them impractical
for real problems and therefore these approaches are not considered.
Implementing these approaches without these complex mechanisms should allow a
more general approach, with high diversity, without substantially reduced
convergence.

To provide an algorithm that can be used practically without a priori
knowledge, this paper creates a novel co-evolutionary approach that works at
the collective level rather than between individuals. In this case the
different collectives utilise separate reproduction mechanisms, and the
information exchange is performed via the collective-level reproduction
mechanisms. Due to the lack of characterisation of complimentary mechanisms in
co-evolutionary algorithms, different state-of-the-art Evolutionary Algorithms
are implemented as the individual-level reproduction mechanisms of cMLSGA:
Unified Non-dominated Sorting Genetic Algorithm (U-NSGA-III) [42], Indicator
Based Evolutionary Algorithm (IBEA) [55], Multi-Objective Evolutionary
Algorithm based on Decomposition (MOEA/D) [51], Bi-Criterion Evolutionary
Algorithm (BCE) [28], Hybrid Evolutionary Immune Algorithm (HEIA) [29],
Multiple-Trajectory Search (MTS) [47] and the updated MOEA/D variants with
different Scalarization Functions MOEA/D-PSF and MOEA/D-MSF [25]. The
resulting algorithms are tested on a number of multi-objective test functions
[53, 56, 21, 31, 32], and the top performing variants are selected and
compared to the current state-of-the-art.

The remainder of this paper is organised as follows. In section II, the
mechanisms are compared to the related co-evolutionary algorithm literature.
In section III the proposed methodology and the benchmarking exercise are
described in detail. Section IV presents the performance of cMLSGA, with a
comparison to the current state-of-the-art and is concluded in Section V.

##  2 Co-evolutionary Genetic Algorithms

Co-evolution is used to explain complex evolutionary dependencies between
various groups of organisms [36] such as: symbiosis [8], coadaptation [38],
host-parasite [3] and hunter-prey [14] relations. The term co-evolution is
first introduced by Ehrlich and Raven in 1964 [15] to describe the coexistence
of plants and butterflies where one group cannot survive without the other.
However, the origins of this theory are older and they are clearly described
by Darwin [9] when documenting the interactions between plants and insects.
Co-evolution can occur in two forms: cooperation [37], where organisms coexist
and “support” each other in various tasks or are mutually dependent for
further benefits; or competition [20], where an “arms race” occurs between
species as only the “strongest” may survive in the given environment.

The idea of introducing co-evolution into Evolutionary Algorithms is first
presented by Potter and De Jong in 1994 [37]. In the co-evolutionary approach
multiple populations of species of individuals coexist and evolve in parallel,
potentially utilising distinct reproduction mechanisms, with data exchange
introduced between them. The sub-populations can operate on the same search
space [10] or can be divided into several regions by problem decomposition and
additional separation mechanisms [23]. The form of data exchange between
groups depends on the type of co-evolution utilised: competitive or
cooperative. In cooperative co-evolution the genetic information, usually the
decision variables, is shared by different species to form a valid solution
when the problem is decomposed [37]; or different sub-populations may
cooperate to form the Pareto objective front with different subpopulations
focusing on different regions [7]. In competitive algorithms different groups
compete in the creation of new populations [29] or sub-populations [17], where
fitter sub-populations gain a wider proportion of children in the next
generation, or via an “arms race” where losing subpopulations try to counter
the winning ones by using a faster evolution approach [41].

In the evolutionary computation literature, multiple algorithms can be found
which are inspired by co-evolution. These can be separated into two groups:
approaches where all of the sub-populations are subject to the same individual
reproduction strategies or those where distinct mechanisms are used to provide
different performances. The algorithms where the individuals are subjected to
the same reproduction strategies use other means to increase the diversity
while maintaining convergence, such as the “species” approach, where
individuals have different “traits” assigned that determine their selection
process such as sex [40] or have a focus on different variables [27].
Otherwise problem decomposition[17] is used to split the complex problem into
sub-problems of a lower order. However, no increase in generality has been
demonstrated for these methods. In the second approach, each group of
individuals utilises distinct reproduction strategies, where each additional
mechanism decreases the risk that all of the strategies will be ineffective on
that particular problem at the same time, leading to a more general approach.
Here only the algorithms of the second group are considered, due to the
interest in improving the general performance of MLSGA, and the top performing
algorithms are reviewed.

There are two recent examples of algorithms using distinct reproduction
strategies, BCE and HEIA. In the BCE [28], sub-populations operate on the same
search spaces and individuals for each group are selected at each generation
based on two distinct fitness indicators: a Pareto-based criterion (PC) and a
Non-Pareto-based criterion (NPC). In the Pareto-based criterion, standard
Pareto dominance is utilised based on the objective functions, which rewards
convergence, whereas the Non-Pareto based selection uses an additional
indicator that rewards diversity of solutions, based on Hyper-Volumes.
Therefore, different sub-population evaluation schemes are utilised, rather
than distinct evolutionary strategies. This leads to an overall improvement in
diversity for the entire population, especially on many-objective cases and
problems with irregular search spaces and variable linkages. Additionally, it
has been shown that different methodologies can be utilised for both the
Pareto and Non-Pareto criteria searches, without extensive parameter tuning.
However, the search is still convergence dominated and shows decreasing
performance on practical problems of increasing complexity [44]. This shows
the potential for algorithms that combine a range of mechanisms in the co-
evolutionary search. A similar approach has been utilised in HEIA [29], but in
this case two distinct evolutionary computation methods are used, Immune
Algorithm and a Genetic Algorithm, instead of separate quality indicators. In
this method the best individuals are moved to a shared pool at each generation
and the sub-populations are recreated from the pool of individuals in a
cloning process. However, despite the potential of combining multiple distinct
mechanisms, shown by BCE and HEIA, there is a lack of comprehensive
documentation that would explain which combinations of mechanisms should be
chosen for a particular problem in order to achieve a high performance.
Therefore, the mechanisms appear to have been chosen arbitrarily, with the
potential for improvements with a clearer documentation of how different
mechanisms pair.

A similar approach to the co-evolutionary algorithms can be found in the
island-based methods [26, 50] and certain decomposition-based GAs, such as M2M
[31] and DMOEA-DD [33], which use sub-populations in a similar way to the co-
evolutionary approaches. For island-based methods, the sub-population based
approach is introduced with information exchange in the form of migration of
individuals. However, due to a lack of proper diversity preservation
mechanisms, island-based methods are predominantly utilised for single-
objective optimisation and specific problems, such as scheduling [26]. In both
M2M and DMOEA-DD, multiple sub-populations are also maintained and evolve in
parallel. In both DMOEA-DD and M2M the mechanisms are based on a forced
problem decomposition of the search spaces, which means that the individuals
are assigned to a specific sub-population dependant on their current
positions. However, the combination of assigning sub-populations and the
problem decomposition requires an extensive a priori knowledge about both the
search and objective spaces [45]. Many problem decomposition methods are shown
to be ineffective on problems with highly discontinuous areas, as the weight
vectors cannot operate freely around the infeasible regions [45], and
therefore application of these methods to real-life problems is limited.

The co-evolutionary approaches are therefore preferred as they provide an
additional diversity and generality of search, with minimal loss in
convergence and their performance is robust to the hyperparameter selection.
However, none of these current approaches provide a fitness definition
specific to the sub-population or reproduction mechanisms for these sub-
populations to allow them to evolve in combination with the individuals within
them.

##  3 cMLSGA

###  3.1 Multi-Level Selection Genetic Algorithm

A detailed explanation of the mechanisms and principles of working of MLSGA
can be found in Sobey and Grudniewski [43] and its extension to use other
algorithms at the individual level to improve convergence can be found in
Grudniewski and Sobey [18]. However, a short review of the mechanisms is
provided here for clarity. The high performance of MLSGA is based on two novel
mechanisms: collective reproduction, which creates an additional selection
pressure and enhances the convergence rate; and the separation of the fitness
between levels, which encourages each collective to explore different areas
and greatly increases the diversity of the obtained solutions. In MLSGA the
whole population is separated into a number of sub-groups, called collectives,
each operating on the same search and objective spaces. These collectives
evolve in parallel using the same reproduction mechanism, but after a
predefined, usually small, number of generations the worst collective is
eliminated, based on its collective fitness value, and repopulated by
individuals from the other collectives. Importantly, the collective has a
specific fitness definition which can be different to the individuals inside
of it. This is inspired by the evolutionary literature which demonstrates a
split in how the fitness should be defined for each collective with two
distinct options: MLS1 and MLS2. The MLS1 fitness is defined as the aggregate
of the objective functions for the individuals in the collective and in MLSGA
this focuses the search towards the centre of the Pareto Front; MLS2 is
defined as there being a different fitness between the individuals and the
collective. Therefore, in MLSGA, using a bi-objective problem as an example,
the collectives have one objective assigned to them and the individuals the
other, with the result that the focus is on one extreme region of the Pareto
front. By creating a reverse of this, MLS2R, the remaining collectives focus
their search on the other extreme values. Therefore, each collective is
”primed” to explore different regions of the objective space, leading to a
sub-regional search strategy. As each collective’s survival and convergence is
dependent on their ability to find diverse regions of the objective space,
MLSGA follows a “diversity first, convergence second” principle.

###  3.2 Novel co-evolutionary approach

In the previously developed hybrid approach each collective utilises the same
mechanisms for the individual-level reproduction, taken from the current
state-of-the-art. In this paper a novel method is suggested which utilises the
multi-level nature of MLSGA to develop a distinct co-evolutionary approach
that is competitive through its collective level reproduction mechanisms.
Different collectives utilise different mechanisms for individual offspring
creation and the information exchange is less regular than in other
approaches, encouraging collectives to act independently. All of the original
mechanisms, such as classification and collective reproduction, are copied
from the previous hybrid algorithms [18], and the same principle applies to
the reproduced state-of-the-art algorithms. The methodology for cMLSGA is
presented in Fig. 1, where darker circles indicate fitter individuals and
darker yellow rectangles indicate higher collective fitness. The new
algorithm, competitor algorithms and benchmarking are coded in C++111The code
is available online with detailed instructions at:
https://www.bitbucket.org/Pag1c18.

Figure 1: cMLSGA methodology. Only two collectives are shown to illustrate how
two distinct evolutionary strategies work in combination; in the results eight
collectives are used.

Similarly to MLSGA, the randomly generated initial population is first
classified into a predefined number of collectives using a Support Vector
Machine, based on the decision variable space. Importantly, the classification
step occurs only once and is not repeated over the course of the optimisation.
In this case, the multi-class classification SVM with C parameter and linear
function, called C-SVC, is used. The utilised code has been taken from the
LIBSVM open library [5] and the training parameters remains the same as in the
publication. Each collective has a separate fitness definition assigned, as
explained in [18].

In cMLSGA there is an additional step where half of the collectives utilise
the selected ”Evolutionary Strategy 1” (ES1) subroutine, and the other half
the ”Evolutionary Strategy 2” (ES2). The type of evolution is assigned
randomly to the collectives during the classification step and does not change
over the run, at any time half of the collectives are using ES1 and the other
half use ES2. Next, the individuals in each sub-population evolve separately
using the assigned strategy. After a predefined number of generations, the
collective with the worst fitness value is eliminated, with all of the
individuals inside of it, and is repopulated by copying the best individuals
from among the rest of the collectives.

After the collective reproduction step the offspring collective inherits the
individual reproduction methodology from the eliminated collective,
demonstrated further in Fig. 1 where the left collective retains MTS and the
right MOEA/D. Therefore, cMLSGA utilises the multi-level approach to generate
a distinct competitive co-evolutionary approach but this occurs via
elimination and repopulation of one group by other sub-populations, rather
than migration of individuals [28], competition in each group [17] or
recreation of all groups [29]. In addition, unlike in other co-evolutionary
GAs, the sub-populations are not allowed to exchange information every
generation, but only during the collective reproduction steps. This leads to a
high diversity search and a lack of bias towards specific problem types.

###  3.3 Computational complexity and constraint handling

In cMLSGA, no computationally expensive mechanisms are added to the original
MLSGA. Therefore, the computational complexity of one generation of cMLSGA is
the same as MLSGA, and is bounded by $O(mN^{2})$, where $m$ is the number of
objectives and $N$ is the population size; or $C$, which is the complexity of
the most complex embedded algorithm. More details can be found in [18]. The
constraint-domination principle is adopted from NSGA-II [13]. This applies
whenever two individuals are compared, similarly to the original MLSGA no
constraint handling is introduced for the collective comparison and selection.

##  4 Benchmarking cMLSGA performance

###  4.1 Test problems

In order to investigate the performance over cases with different dominate
characteristics the proposed methodology is verified over 60 state-of-the-art
bi-objective and 40 three-objective test functions [53, 56, 21, 31, 32, 16].
These problems are divided into twelve categories for the 2-objective problems
and nine for the 3-objective problems, with the justification for the
selection given in Tables LABEL:Tab:Test_set_uncons and
LABEL:Tab:Many_TestSet. Due to the variety of the problems in the test set two
and three objective problems are preferred as they allow a simpler
interpretation of the results, without issues of scaling, while providing
enough complexity to resemble a number of real-world problems. However, like
most benchmarking problems in evolutionary computation, they are dominated by
a single characteristic, which is less common in real-world problems.

Table 3: Summary of the utilised two-objective test set  |  |  |
---|---|---|---
Category |  Problem |  d |  Additional properties
Unconstrained
I. Simple |  ZDT1 |  30 |  Convex
|  ZDT2 |  30 |  Concave
|  ZDT3 |  30 |  Discontinuous
|  ZDT4 |  10 |  Multimodal, Convex
|  ZDT6 |  10 |  Multimodal, Biased, Concave
II. Convex |  UF1 |  30 |  Complex PS
|  UF2 |  30 |  Complex PS
|  UF3 |  30 |  Complex PS
III. Concave |  UF4 |  30 |  Complex PS
|  WFG4 |  22 |  Multimodal
|  WFG5 |  22 |  Deceptive
|  WFG6 |  22 |  Non-separable
|  WFG7 |  22 |  Biased
|  WFG8 |  22 |  Biased, Non-separable
|  WFG9 |  22 |  Biased, Non-separable, Deceptive
IV. Linear/Mixed |  UF7 |  30 |  Complex PS, Linear
|  WFG1 |  22 |  Biased, Mixed
|  WFG3 |  22 |  Non-separable, Degenerated, Linear
V. Discontinuous |  UF5 |  30 |  Linear, Distinct points, Complex PS
|  UF6 |  30 |  Complex PS
|  WFG2 |  22 |  Convex, Non-Separable
|  MOP4 |  10 |  Discontinuous
VI. Imbalanced |  MOP1 |  10 |  Convex
|  MOP2 |  10 |  Convex
|  MOP3 |  10 |  Concave
|  MOP5 |  10 |  Convex
|  IMB1 |  10 |  Convex
|  IMB2 |  10 |  Linear
|  IMB3 |  10 |  Concave
|  IMB7 |  10 |  Convex, Non-separable
|  IMB8 |  10 |  Linear, Non-separable
|  IMB9 |  10 |  Concave, Non-separable
Constrained
VII. Discontinuous |  CF1 |  10 |  Linear, Complex PS, Distinct points
|  CF2 |  10 |  Convex, Complex PS
|  CF3 |  10 |  Concave, Complex PS
VIII. Continuous |  CF4 |  10 |  Linear, Complex PS
|  CF5 |  10 |  Linear, Complex PS
|  CF6 |  10 |  Mixed, Complex PS
|  CF7 |  10 |  Mixed, Complex PS
IX. Imbalanced |  IMB11 |  10 |  Convex
|  IMB12 |  10 |  Linear
|  IMB13 |  10 |  Concave
X. Diversity-hard |  DAS-CMOP1(5) |  30 |  Concave, Discontinuous
|  DAS-CMOP2(5) |  30 |  Mixed, Continuous
|  DAS-CMOP3(5) |  30 |  Linear, Discontinuous, Multimodal
|  DAS-CMOP4(5) |  30 |  Concave, Discontinuous
|  DAS-CMOP5(5) |  30 |  Mixed, Discontinuous
|  DAS-CMOP6(5) |  30 |  Distinct points, Degenerated
XI. Feasibility-hard |  DAS-CMOP1(6) |  30 |  Concave, Discontinuous
|  DAS-CMOP2(6) |  30 |  Mixed, Continuous
|  DAS-CMOP3(6) |  30 |  Linear, Discontinuous, Multimodal
|  DAS-CMOP4(6) |  30 |  Concave, Discontinuous
|  DAS-CMOP5(6)) |  30 |  Mixed, Discontinuous
|  DAS-CMOP6(6) |  30 |  Distinct points, Degenerated
XII.Convergence-hard |  DAS-CMOP1(7) |  30 |  Concave, Discontinuous
|  DAS-CMOP2(7) |  30 |  Mixed, Continuous
|  DAS-CMOP3(7)) |  30 |  Linear, Discontinuous, Multimodal
|  DAS-CMOP4(7) |  30 |  Concave, Discontinuous
|  DAS-CMOP5(7) |  30 |  Mixed, Discontinuous
|  DAS-CMOP6(7) |  30 |  Distinct points, Degenerated
d denotes the number of decision variables.
Table 4: Summary of the utilised three-objective test set  |  |  |
---|---|---|---
Category |  Problem |  d |  Additional properties
Unconstrained
I. Concave |  DTLZ2 |  12 |
|  DTLZ3 |  12 |  Multimodal
|  DTLZ4 |  12 |  Biased
|  DTLZ5 |  12 |  Degenerated
|  DTLZ6 |  12 |  Degenerated, Biased
|  UF8 |  30 |  Complex PS
|  UF10 |  30 |  Complex PS
|  WFG4 |  24 |  Multimodal
|  WFG5 |  24 |  Deceptive
|  WFG6 |  24 |  Non-separable
|  WFG7 |  24 |  Biased
|  WFG8 |  24 |  Biased, Non-separable
|  WFG9 |  24 |  Biased, Non-separable, Deceptive
IV. Linear/Mixed |  DTLZ1 |  7 |  Linear, Multimodal
|  WFG1 |  24 |  Biased, Mixed
|  WFG3 |  24 |  Non-separable, Degenerated, Linear
V. Discontinuous |  DTLZ7 |  22 |  Mixed, Multimodal
|  UF9 |  30 |  Complex PS
|  WFG2 |  24 |  Convex, Non-Separable
VI. Imbalanced |  MOP6 |  10 |  Linear
|  MOP7 |  10 |  Concave
|  IMB4 |  10 |  Linear
|  IMB5 |  10 |  Concave
|  IMB6 |  10 |  Linear
|  IMB10 |  10 |  Linear
Constrained
VII. Discontinuous |  DTLZ8 |  30 |  Mixed, Degenerated, Biased
|  DTLZ9 |  30 |  Concave, Degenerated
|  CF8 |  10 |  Concave, Degenerated, Complex PS
|  CF9 |  10 |  Concave, Complex PS
|  CF10 |  10 |  Concave, Complex PS
IX. Imbalanced |  IMB14 |  10 |  Linear
X. Diversity-hard |  DAS-CMOP7(5) |  30 |  Linear, Degenerated, Discontinuous
|  DAS-CMOP8(5) |  30 |  Concave, Discontinuous
|  DAS-CMOP9(5) |  30 |  Concave, Discontinuous, Biased
XI. Feasibility-hard |  DAS-CMOP7(6) |  30 |  Linear, Degenerated, Discontinuous
|  DAS-CMOP8(6) |  30 |  Concave, Discontinuous
|  DAS-CMOP9(6) |  30 |  Concave, Discontinuous, Biased
XII.Convergence-hard |  DAS-CMOP7(7) |  30 |  Linear, Degenerated, Discontinuous
|  DAS-CMOP8(7) |  30 |  Concave, Discontinuous
|  DAS-CMOP9(7) |  30 |  Concave, Discontinuous, Biased
d denotes the number of decision variables. The same categories are utilised
as for the two-objective cases.

###  4.2 Competitor algorithms and individual reproduction mechanisms

In this study, a variety of reproduction mechanisms are replicated from the
original papers and combined through the cMLSGA methodology: IBEA [55] as the
most commonly utilised indicator based GA; BCE [28] and HEIA [29] as the most
highly performing co-evolutionary approaches, demonstrating the difference in
performance with the proposed methodology; MOEA/D-TCH [51] and
MOEA/D-(PSF/MSF) [25] as different variants of the top performing solver for
unconstrained and imbalanced problems respectively; MTS [47] as a proficient
constrained and unconstrained solver that utilises local search strategies
instead of typical evolutionary mechanisms and U-NSGA-III [42] as the
universal two/many-objective variant of the most commonly utilised general-
solver NSGA-II [13].

Each utilised mechanism is combined with every other mechanism in the co-
evolutionary approach. However, the combinations between U-NSGA-III,
MOEA/D-TCH, MOEA/D-PSF and MOEA/D-MSF are discarded. This is because all of
the MOEA/D variants are based on the same framework while U-NSGA-III and
MOEA/D are both based on developing a constant Pareto front at each
generation. The pre-benchmarks demonstrate that similar mechanisms result in
no performance gains for co-evolutionary approaches, and the results for these
variants are not reported. Therefore, 22 variants in total are evaluated with
the results attached as a supplement to this paper.

The tests are performed over 30 separate runs, with 300,000 function
evaluations for each run. The results are compared using two performance
indicators: Inverted Generational Distance (IGD) and Hyper-Volume (HV), as
they provide information on the convergence and diversity of the obtained
solutions. IGD measures the average Euclidean distance between any point in a
uniformly distributed Pareto front and the closest solution in the obtained
set. Low scores for this metric emphasise convergence and uniformity of the
points [58]. HV is the measure of volume of the objective space between a
predefined reference point and the obtained solutions, and therefore has a
stronger focus on the diversity and edge points. 1,000,000 reference points
are generated in this paper for the IGD calculation, and the HV is calculated
according to While et al. [49], which provides the fastest and most widely
used method for this calculation.

###  4.3 Hyperparameters

Different operational parameters: population size, number of collectives and
collective reproduction delay, were tested and the best performing values are
summarised in Table 5. However, it has been concluded that these parameters do
not have significant impact on the performance. Between different groups of
mechanisms, the only parameter that is different is the collective
reproduction delay. The variance is caused by BCE, HEIA and IBEA developing
fronts at different paces and therefore low values of collective elimination
lead to premature removal of these underdeveloped fronts. MTS requires
significantly more iterations per generation, as it utilises multiple local
search methods, and therefore the elimination has to occur more frequently to
have an impact on the search. The number of collectives is 8 in all cases,
with 4 collectives using the first evolutionary algorithm and the other 4
using the second. All other GA specific parameters e.g. MOEA/D Neighbourhood
size; are taken directly from the original publications to create a more
realistic scenario where a priori knowledge cannot be utilised.

Table 5: The GA parameters utilised for benchmarking Parameter |  MTS |  BCE |  HEIA |  IBEA
---|---|---|---|---
Pop. Size | 1000
Crossover rate | 1
Mutation rate | 0.08
No. of collectives | 8
Collective reproduction delay |  1 |  4 | 10

###  4.4 Determining the characteristics of complementary co-evolutionary
mechanisms

The performances of the selected cMLSGA variants are compared to the original
algorithms with the data attached as a supplement. Due to the large quantity
of data, only the most interesting 4 representative cases of the 22 methods
trialled are described further in this section. IBEA_BCE, which shows the
highest improvement over the original algorithms; MOEA/D-MSF_HEIA as the
combination of a convergence-solver and a more general solver; MOEA/D-MSF_U-
NSGA-III, as the combination of a convergence-solver and the top algorithm for
problems with many objectives and MTS_MOEA/D, which combines two convergence
first methodologies: MTS which is a highly proficient constrained solver and
MOEA/D, the top unconstrained solver. This is summarised in Table 6. It can be
observed that the cMLSGA approach does not improve the performance of the
original algorithms in all cases and for the majority of them its performance
is in between the effectiveness of both implemented methodologies. This shows
that cMLSGA is often limited by the performance of the worst of the utilised
strategies but leads to a more robust, ”general solver”, with a lower chance
of poor performance.

Table 6: Comparison of selected cMLSGA variants to the implemented algorithms according to IGD/HV indicator. cMLSGA variant |  IBEA_BCE |  MOEA/D-MSF_HEIA |  MOEA/D-MSF _U-NSGA-III |  MTS_MOEA/D
---|---|---|---|---
Better than both |  67/62 |  38/40 |  33/31 |  29/23
Better than one |  28/32 |  46/44 |  57/52 |  52/56
Worse than both |  5/6 |  16/16 |  10/17 |  19/21

Comparing the 22 variants of cMLSGA against the original algorithms the
highest improvement is exhibited by the cMLSGA_IBEA_BCE variant. In this case
the performance is improved on 67 out of 100 problems for the IGD indicator
and 62 cases for the HV indicator; it only exhibits worse performance in 5 and
6 cases for IGD and HV respectively. cMLSGA_MOEA/D-MSF_HEIA is the best
performer on the two-objective test set, where it is better than both
methodologies in 38 cases for IGD and 40 cases for HV but worse in 16 cases
for each indicator. Whereas cMLSGA_MOEA/D-MSF_U-NSGA-III is the top performer
for the three-objective problems. It performs better on 33 problems but is
worse for 10 problems for IGD and is better for 31 problems and worse for 17
problems when evaluating using the HV metric. For the high convergence solver,
cMLSGA_MTS_MOEA/D better results are obtained in 29 and 23 cases for IGD and
HV indicators but worse on 19 and 21 of them respectively. This indicates that
if two methodologies with strong diversity mechanisms, such as IBEA and BCE,
are used then cMLSGA is able to successfully combine the methodologies and
preserve the diversity mechanisms, while providing stronger convergence. It
supports the previous findings that the MLSGA mechanisms promote diversity
[43], but also indicates that if sufficient diversity is obtained the MLS-U
variants focus the search, improving convergence. The reduced performance of
the other two presented variants, which combine strong convergence based
mechanisms, may be caused by the inability of MLSGA to properly maintain a
search pattern during the collective elimination and reproduction steps, as
indicated previously in [18]. In the case of the MTS and MOEA/D variants the
performance of the cMLSGA approach resembles the results of MTS, especially
for the IGD indicator. This is due to the local searches that require a
significant number of iterations per generation, the MTS mechanisms ”dominate”
the search, and the secondary mechanisms, MLSGA and MOEA/D, do not have a
sufficient influence. Therefore, if a method is combined with a significantly
stronger convergence-first methodology than the other method, such as MTS, the
weaker method will have negligible impact on the search. The result is that
there is an improvement in the uniformity of the points, but no new areas of
the Pareto optimal front are found and so diversity is not increased. A
similar principle applies to the MOEA/D-MSF_HEIA and MOEA/D-MSF_U-NSGA-III
variants, where the specialist convergence-based methodology is combined with
a general diversity-based one. This indicates, that cMLSGA maintains distinct
searches for both algorithms if two methodologies with contrasting mechanisms
are combined, rather than one method outperforming the other. It can be
concluded that the success in combining methodologies is subject to how
similar the methods are and the poor performance of MOEA/D, MOEA/D-MSF and
MOEA/D-PSF, compared to the original algorithms, shows that implementing
methodologies that are too similar is not at all beneficial, due to the non-
complementary nature of the searches, and that the diversity of the approaches
is more important than their individual performances.

###  4.5 Behaviour of cMLSGA: increased generality

cMLSGA predominantly exhibits high performance on problems that require high
diversity in comparison to the original algorithms. It operates significantly
better on cases with discontinuous search spaces, categories V, VII and VIII,
rather than continuous problems, and on diversity- and feasibility-hard
functions, categories X and XI. The lower impact on the performance of the
continuous functions is caused by the additional region searches provided by
cMLSGA, which are not necessary as convergence is more important for these
problems. Therefore, the presented methodology does not lead to performance
improvements on the cases where the results from at least one of the original
algorithms are close to the ideal Pareto optimal front. This is caused by
there being little room for improvement, indicating that these mechanisms are
well tuned to these problems and any changes reduce their effectiveness or
that even more specialist mechanisms are required to improve the performance.
Therefore, adding additional mechanisms that are created to enhance the
overall diversity makes the search less focused and leads to worse overall
performance if the algorithm is already able to obtain excellent results.
Unsurprisingly this indicates that cMLSGA will underperform convergence
specialised GA methodologies on their preferred cases. This is demonstrated on
the category XII problems, which are difficult convergence problems, with all
of the cMLSGA variants performing relatively poorly. In contrast to the
results on the convergence based problems, high performance is achieved on
categories X-XI, which belong to the same test set [16], but focuses on
providing hard diversity and feasibility problems.

Figure 2: Occurrence of ranks for HEIA and cMLSGA algorithms on two-objective problems. Figure 3: Occurrence of ranks for U-NSGA-III and cMLSGA algorithms on three objective problems. Table 7: The rankings for the 9 genetic algorithms according to the average performance on different two-objective problem categories for IGD/HV indicator Cat. |  UNSGA-III |  MOEA/D |  MOEA/D PSF |  MOEA/D MSF |  IBEA |  MTS |  BCE |  HEIA |  cMLSGA
---|---|---|---|---|---|---|---|---|---
I |  4.60/ 2.60 |  3.00/ 3.80 |  4.60/ 5.00 |  6.60/ 7.20 |  8.40/ 6.80 |  7.00/ 8.60 |  7.40/ 7.40 |  2.40/ 2.60 |  1.00/ 1.00
II |  7.00/ 7.33 |  3.00/ 3.33 |  4.67/ 4.00 |  3.33/ 3.67 |  8.00/ 9.00 |  9.00/ 7.33 |  2.67/ 3.67 |  1.33/ 1.00 |  6.00/ 5.67
III |  3.14/ 3.29 |  4.86/ 5.00 |  7.57/ 7.29 |  5.43/ 5.29 |  6.43/ 6.71 |  6.86/ 6.14 |  5.57/ 7.00 |  2.57/ 2.14 |  2.57/ 2.14
IV |  3.33/ 3.33 |  3.33/ 3.33 |  5.67/ 5.67 |  5.33/ 5.00 |  8.00/ 6.33 |  6.33/ 7.67 |  7.67/ 8.67 |  1.00/ 1.00 |  4.33/ 4.00
V |  4.25/ 5.25 |  5.50/ 4.50 |  5.25/ 5.25 |  5.00/ 4.25 |  7.75/ 6.75 |  7.00/ 7.75 |  3.25/ 3.75 |  3.75/ 4.50 |  3.25/ 3.00
VI |  5.30/ 4.50 |  5.00/ 5.00 |  2.90/ 2.90 |  2.30/ 2.50 |  8.00/ 7.50 |  7.60/ 8.10 |  4.70/ 4.80 |  5.00/ 5.30 |  4.20/ 4.40
VII |  6.00/ 3.33 |  5.67/ 6.33 |  6.33/ 5.67 |  5.00/ 6.00 |  6.33/ 8.00 |  8.00/ 6.33 |  4.00/ 2.67 |  2.33/ 4.67 |  1.33/ 2.00
VIII |  4.25/ 3.75 |  6.75/ 6.00 |  7.25/ 7.00 |  6.00/ 6.75 |  6.25/ 8.75 |  8.50/ 6.50 |  1.00/ 1.00 |  2.50/ 3.25 |  2.50/ 2.00
IX |  7.33/ 7.00 |  1.00/ 1.33 |  3.67/ 3.00 |  2.67/ 2.67 |  6.00/ 9.00 |  9.00/ 6.00 |  7.67/ 8.00 |  4.00/ 4.67 |  3.67/ 3.33
X |  3.83/ 4.17 |  5.00/ 4.83 |  5.00/ 5.42 |  3.83/ 3.83 |  8.83/ 8.75 |  6.17/ 5.67 |  3.33/ 3.50 |  5.67/ 5.33 |  3.33/ 3.50
XI |  4.50/ 4.17 |  5.75/ 3.75 |  5.75/ 5.75 |  5.08/ 5.25 |  7.58/ 8.08 |  6.67/ 6.50 |  2.50/ 4.00 |  5.00/ 3.83 |  2.17/ 3.67
XII |  4.00/ 4.00 |  4.50/ 3.33 |  4.83/ 5.58 |  4.17/ 3.67 |  8.67/ 8.42 |  4.17/ 4.00 |  4.50/ 4.67 |  6.17/ 6.83 |  4.00/ 4.50
Overall |  4.617/ 4.233 |  4.642/ 4.342 |  5.158/ 5.158 |  4.425/ 4.508 |  7.642/ 7.625 |  7.000/ 6.867 |  4.467/ 4.917 |  3.867/ 4.033 |  3.183/ 3.317
Std |  2.244/ 2.348 |  2.564/ 2.353 |  2.294/ 2.369 |  2.278/ 2.469 |  1.435/ 1.488 |  2.106/ 2.164 |  2.735/ 2.691 |  2.284/ 2.295 |  1.455/ 1.466
The best algorithm in each category is highlighted in green, the second and
the third best are highlighted in orange and red respectively.
Table 8: The rankings for the 9 genetic algorithms according to the average performance on different three-objective problem categories for IGD/HV indicator Cat. |  UNSGA-III |  MOEA/D |  MOEA/D PSF |  MOEA/D MSF |  IBEA |  MTS |  BCE |  HEIA |  cMLSGA
---|---|---|---|---|---|---|---|---|---
I |  3.31/ 3.85 |  3.77/ 3.15 |  4.92/ 5.77 |  6.23/ 6.23 |  6.92/ 7.38 |  5.77/ 4.31 |  7.15/ 7.69 |  4.00/ 3.46 |  2.92/ 3.15
IV |  2.67/ 2.33 |  3.67/ 4.67 |  4.67/ 4.33 |  5.67/ 6.67 |  9.00/ 8.67 |  4.00/ 4.67 |  7.33/ 8.33 |  3.33/ 1.33 |  4.67/ 4.00
V |  2.67/ 2.00 |  7.00/ 4.67 |  5.00/ 4.67 |  6.33/ 5.33 |  4.00/ 6.67 |  7.00/ 7.33 |  5.00/ 8.00 |  4.33/ 4.00 |  3.67/ 2.33
VI |  5.83/ 6.50 |  4.00/ 4.50 |  1.17/ 1.33 |  2.17/ 2.17 |  6.67/ 6.00 |  8.83/ 8.83 |  6.33/ 6.67 |  5.00/ 4.67 |  5.00/ 4.33
VII |  4.40/ 4.00 |  5.20/ 5.10 |  5.20/ 5.50 |  4.40/ 5.20 |  5.60/ 6.30 |  6.40/ 6.40 |  3.40/ 3.30 |  6.80/ 5.80 |  3.60/ 3.40
IX |  5.00/ 5.00 |  1.00/ 3.00 |  2.00/ 1.00 |  4.00/ 2.00 |  6.00/ 7.00 |  8.00/ 8.00 |  9.00/ 9.00 |  3.00/ 4.00 |  7.00/ 6.00
X |  4.67/ 5.67 |  8.00/ 6.00 |  5.33/ 6.83 |  5.00/ 5.67 |  9.00/ 8.50 |  3.67/ 3.67 |  3.00/ 4.00 |  4.67/ 3.00 |  1.67/ 1.67
XI |  1.00/ 3.33 |  5.67/ 5.33 |  7.33/ 7.17 |  7.33/ 7.17 |  7.33/ 7.17 |  4.83/ 4.67 |  6.50/ 6.50 |  3.00/ 2.33 |  2.00/ 1.33
XII |  3.00/ 3.33 |  8.33/ 7.17 |  5.00/ 6.33 |  4.67/ 6.17 |  8.33/ 7.67 |  4.67/ 4.67 |  5.00/ 5.33 |  3.33/ 2.67 |  2.67/ 1.67
Overall |  3.675/ 4.100 |  4.950/ 4.500 |  4.525/ 4.988 |  5.175/ 5.375 |  6.925/ 7.163 |  6.013/ 5.600 |  5.938/ 6.550 |  4.375/ 3.650 |  3.425/ 3.075
std |  2.030/ 2.083 |  2.629/ 2.188 |  2.786/ 2.628 |  2.293/ 2.296 |  2.020/ 1.690 |  2.481/ 2.615 |  2.760/ 2.405 |  2.070/ 2.264 |  1.641/ 1.649
The best algorithm in each category is highlighted in green, the second and
the third best are highlighted in orange and red respectively.

The performance of the best developed cMLSGA variant is compared to 8 selected
current state-of-the-art algorithms in order to evaluate the potential of the
cMLSGA approach as a general solver. In the case of two-objectives, the
cMLSGA_HEIA_MOEA/D-MSF variant is utilised, whereas for more objectives the
cMLSGA_MOEA/D-MSF_U-NSGA-III is compared, due to the outstanding performance
of U-NSGA-III on three-objective problems, and the lower effectiveness of HEIA
on them. This is presented in the form of an average ranking on each category
of problem in Table 7 for two-objective problems and 8 for three-objective
problems. From the two-objective ranking it can be observed that the best
solver on average is cMLSGA, 3.183/3.317 for the IGD/HV metrics, while HEIA
comes second with 3.867/4.033 for the IGD/HV indicators. Higher differences in
the HV scores indicates that cMLSGA is more likely to promote high diversity
than HEIA. In addition cMLSGA is shown to be more general than HEIA, which has
a higher deviation in performance with larger standard deviations of its
position in the rankings presented in Table 7, 2.284 for IGD and 2.295 for HV,
compared to cMLSGA, 1.455 for IGD and 1.466 for HV. This is illustrated in
Fig. 2 for the two objective problems, where the occurrence of each rank is
presented for the HEIA and cMLSGA algorithms. HEIA and cMLSGA are often the
top performers, rank 1, but HEIA is also regularly the second-best algorithm
on IGD, 13 times compared to 7 times for cMLSGA. However, when HEIA shows low
performance on a problem it performs very poorly with rank 7 eight times for
both indicators; rank 8 one time for IGD and two times for HV and rank 9 two
times for IGD and one time for HV. Whereas the lowest rank for cMLSGA is 6 and
it has a high occurrence in the 3rd, 4th and 5th positions; demonstrating that
cMLSGA is the best general solver.

Similar behaviour can be observed for the three-objective problems. From the
corresponding ranking, Table 8, it can be observed that the best solver on
average is cMLSGA and U-NSGA-III comes second. The IGD rankings are 3.425 for
cMLSGA and 3.675 for U-NSGA-III, and 3.075 and 4.100 according to HV.
Similarly, to the bi-objective cases, cMLSGA also shows lower standard
deviations than the second best-on-average algorithm, U-NSGA-III, further
proving its high generality. Comparing the occurrence of each rank for U-NSGA-
III and cMLSGA, illustrated on Fig. 3, it can be seen that cMLSGA is again
more likely to avoid poor performance. In this case, both algorithms are the
top performers an approximately equal number of times for IGD, but cMLSGA is
significantly more likely to exhibit the highest performance according to the
HV metric. Furthermore, U-NSGA-III is more likely to be second, 9 and 10 times
with IGD and HV respectively compared to 8 times for cMLSGA with both
indicators. In contrast, cMLSGA is significantly less likely to perform
poorly, as in the worst case scenario it is 7th for both indicators, whereas
for U-NSGA-III the lowest position is 9th for IGD and 8th for HV. Furthermore,
U-NSGA-III is more likely than cMLSGA to achieve ranks 6 and 7. Interestingly,
both algorithms are unlikely to be 1st or last, which occurs less than two
times for cMLSGA and U-NSGA-III, and are showing a distribution reflecting a
general performance. This indicates a high generality and universality of both
solutions which are often outperformed by specialist-solvers on their
preferred cases.

cMLSGA is bounded by the performance of the implemented algorithms and
therefore their selection remains important. A self-adaptive variant may be
considered in the future but currently the HEIA_MEOA/D-MSF combination is
suggested for two-objective problems and MOEA/D-MSF_U-NSGA-III for more
objectives, as these methodologies are the most distinct and show the most
“general” behaviour on corresponding cases. By combining the advantages of the
two methodologies selected at the individual level and utilising diversity-
first approaches, derived from the multi-level selection mechanisms, the
chance of success of cMLSGA is still significantly higher than other
algorithms, especially in cases where there is no knowledge about the
optimisation space. The profile is more similar to that of U-NSGA-III than the
rest of the state-of-the-art, as this algorithm also shows a strong general
performance and especially high performance on the HV diversity metric. This
combination provides confidence that cMLSGA will provide good results on cases
where there is no a priori knowledge of the problem characteristic or where
there are multiple dominating characteristics; the case for many real-world
problems. In cases where there is a priori knowledge of the problem the
provided supporting data, showing the results for all of the variants of
cMLSGA, will allow determination of the strongest variant for a given problem
type.

##  5 Conclusions

Current real-world problems have been shown to be more complex than the
available evolutionary computation benchmarking problems, requiring algorithms
tested on constrained and imbalanced problems that require high diversity. In
addition, when solving practical optimisation problems, there is often no a
priori knowledge about the problem set, meaning that specialist algorithms
can’t be selected in advance. To develop an algorithm with both high diversity
and general properties, this paper presents a novel co-evolutionary approach.
The novel approach is the first to develop an approach dependant on
competition between collectives and the additional mechanisms are added to the
Multi-Level Selection Genetic Algorithm, designated cMLSGA. A lower
communication rate between sub-populations than in other co-evolutionary
approaches and a split in the fitness definition between individual and
collective levels allows an independence of search between the different
collectives. The new methodology promotes a diversity first, convergence
second behaviour seen in previous iterations of this algorithm, improving
performance on highly discontinuous, constrained and irregular problems. An
investigation into the optimum pairing of algorithms in the co-evolutionary
approach provides general guidance for developers of algorithms utilising
these approaches, showing that the diversity of the co-evolutionary mechanisms
is more important than their individual performance. Based on this pairing the
resulting cMLSGA is shown to be the best currently existing general-solver
Evolutionary Algorithm. This greatly increases cMLSGA’s applicability to real-
world problems, especially on cases where the problem characteristics are not
known or where they are dominated by more than one characteristic.

## Acknowledgements

This work was sponsored by Lloyd’s Register Foundation.

## References

  * Abdou et al. [2012a] Abdou W, Bloch C, Charlet D, Spies F (2012a) Multi-pareto-ranking evolutionary algorithm. EvoCOP 7245:194–205
  * Abdou et al. [2012b] Abdou W, Charlet D, Bloch C, Spies F (2012b) Adaptive multi-objective genetic algorithm using multi-pareto-ranking categories and subject descriptors. In: GECCO’12, Philadelphia, USA, pp 449–456
  * Anderson and May [1982] Anderson RM, May RM (1982) Coevolution of hosts and parasites. Parasitology 85(02):411, DOI 10.1017/S0031182000055360, arXiv:1011.1669v3
  * Beume et al. [2007] Beume N, Naujoks B, Emmerich M (2007) SMS-EMOA: Multiobjective selection based on dominated hypervolume. European Journal of Operational Research 181(3):1653–1669, DOI 10.1016/j.ejor.2006.08.008
  * Chang and Lin [2011] Chang CC, Lin CJ (2011) Libsvm: A Library for Support Vector Machines. ACM Transactions on Intelligent Systems and Technology 2(3):1–27, DOI 10.1145/1961189.1961199, URL http://dl.acm.org/citation.cfm?doid=1961189.1961199, 0-387-31073-8
  * Chen et al. [2009] Chen CM, Chen YP, Zhang Q (2009) Enhancing MOEA/D with guided mutation and priority update for multi-objective optimization. 2009 IEEE Congress on Evolutionary Computation (CEC 2009) pp 209–216, DOI 10.1109/CEC.2009.4982950
  * Coello Coello and Sierra [2003] Coello Coello CA, Sierra MR (2003) A coevolutionary multi-objective evolutionary algorithm. 2003 Congress on Evolutionary Computation, CEC 2003 \- Proceedings 1(2508):482–489, DOI 10.1109/CEC.2003.1299614
  * Currie et al. [2003] Currie CR, Wong B, Stuart AE, Schultz TR, Rehner SA, Mueller UG, Sung GH, Spatafora JW, Straus NA (2003) Ancient Tripartite Coevolution in the Attine Ant-Microbe Symbiosis. Science 299(January):386–388
  * Darwin [1859] Darwin C (1859) On the Origin of Species by Means of Natural Selection, or the Preservation of Favoured Races in the Struggle for Life. London: John Murray
  * De Jong [2006] De Jong KA (2006) Evolutionary computation : a unified approach. MIT, Cambridge, Mass., London
  * Deb and Jain [2014] Deb K, Jain H (2014) An Evolutionary Many-Objective Optimization Algorithm Using Reference-point Based Non-dominated Sorting Approach, Part I: Solving Problems with Box Constraints. IEEE Transactions on Evolutionary Computation 18(4):577–601, DOI 10.1109/TEVC.2013.2281534, URL http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=6600851{%}5Cnhttp://ieeexplore.ieee.org/xpls/abs{_}all.jsp?arnumber=6600851
  * Deb et al. [2001] Deb K, Thiele L, Laumanns M, Zitzler E (2001) Scalable test problems for evolutionary multi-objective optimization. Tech. Rep. 1990, Computer Engineering and Networks Laboratory (TIK), Swiss Federal Institute of Technology (ETH), DOI 10.1007/1-84628-137-7˙6, URL http://www.springerlink.com/content/q404757t4q25m64l/{%}5Cnhttp://www.springerlink.com/index/q404757t4q25m64l.pdf
  * Deb et al. [2002] Deb K, Pratap A, Agarwal S, Meyarivan T (2002) A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation 6(2):182–197, DOI 10.1109/4235.996017
  * Downes and Shine [1998] Downes S, Shine R (1998) Sedentary snakes and gullible geckos: Predator-prey coevolution in nocturnal rock-dwelling reptiles. Animal Behaviour 55(5):1373–1385, DOI 10.1006/anbe.1997.0704
  * Ehrlich and Raven [1964] Ehrlich PR, Raven PH (1964) Butterflies and Plants: A Study in Coevolution. Evolution 18(4):586–608
  * Fan et al. [2019] Fan Z, Li W, Cai X, Li H, Wei C, Zhang Q, Deb K, Goodman E (2019) Difficulty Adjustable and Scalable Constrained Multiobjective Test Problem Toolkit. Evolutionary Computation (x):1–40, DOI 10.1162/evco˙a˙00259, 1612.07603
  * Goh and Tan [2009] Goh CK, Tan KC (2009) A competitive-cooperative coevolutionary paradigm for dynamic multiobjective optimization. IEEE Transactions on Evolutionary Computation 13(1):103–127, DOI 10.1109/TEVC.2008.920671
  * Grudniewski and Sobey [2018] Grudniewski PA, Sobey AJ (2018) Behaviour of Multi-Level Selection Genetic Algorithm (MLSGA) using different individual-level selection mechanisms. Swarm and Evolutionary Computation 44(September 2018):852–862, DOI 10.1016/j.swevo.2018.09.005
  * Grudniewski and Sobey [2019] Grudniewski PA, Sobey AJ (2019) Do general Genetic Algorithms provide benefits when solving real problems? In: 2019 IEEE Congress on Evolutionary Computation (CEC), Wellington
  * Hill [1990] Hill J (1990) The three C’s - competition, coexistence and coevolution - and their impact on the breeding of forage crop mixtures. Theoretical and Applied Genetics 79(2):168–176, DOI 10.1007/BF00225947
  * Huband et al. [2005] Huband S, Barone L, While L, Hingston P (2005) A Scalable Multi-objective Test Problem Toolkit. In: Evolutionary Multi-Criterion Optimization, June, pp 280–295, DOI 10.1007/978-3-540-31880-4˙20
  * Jain and Deb [2014] Jain H, Deb K (2014) An evolutionary many-objective optimization algorithm using reference-point based non-dominated sorting approach, part II: Handling constraints and extending to an adaptive approach. IEEE Transactions on Evolutionary Computation 18(4):602–622, DOI 10.1109/TEVC.2013.2281534
  * Jia et al. [2018] Jia YH, Chen WN, Gu T, Zhang H, Yuan H, Kwong S, Zhang J (2018) Distributed Cooperative Co-evolution with Adaptive Computing Resource Allocation for Large Scale Optimization. IEEE Transactions on Evolutionary Computation In press:1–15, DOI 10.1109/TEVC.2018.2817889
  * Jiang and Yang [2017] Jiang S, Yang S (2017) Evolutionary Dynamic Multiobjective Optimization: Benchmarks and Algorithm Comparisons. IEEE Transactions on Cybernetics 47(1):198–211, DOI 10.1109/TCYB.2015.2510698
  * Jiang et al. [2018] Jiang S, Yang S, Wang Y, Liu X (2018) Scalarizing Functions in Decomposition-Based Multiobjective Evolutionary Algorithms. IEEE Transactions on Evolutionary Computation 22(2):296–313, DOI 10.1109/TEVC.2017.2707980
  * Kurdi [2016] Kurdi M (2016) An effective new island model genetic algorithm for job shop scheduling problem. Computers and Operations Research 67:132–142, DOI 10.1016/j.cor.2015.10.005
  * Li et al. [2003] Li JP, Balazs ME, Parks GT, Clarkson PJ (2003) A species conserving genetic algorithm for multimodal function optimization (Evolutionary Computation). Evolutionary Computation 11(1):107–109, DOI 10.1162/106365603321829023
  * Li et al. [2016] Li M, Yang S, Liu X (2016) Pareto or Non-Pareto: Bi-criterion evolution in multiobjective optimization. IEEE Transactions on Evolutionary Computation 20(5):645–665, DOI 10.1109/TEVC.2015.2504730
  * Lin et al. [2016] Lin Q, Chen J, Zhan ZH, Chen WN, Coello Coello CA, Yin Y, Lin CM, Zhang J (2016) A Hybrid Evolutionary Immune Algorithm for Multiobjective Optimization Problems. Ieee Transactions on Evolutionary Computation 20(5):711–729, DOI 10.1109/TEVC.2015.2512930
  * Liu and Li [2009] Liu Hl, Li X (2009) The multiobjective evolutionary algorithm based on determined weight and sub-regional search. 2009 IEEE Congress on Evolutionary Computation (CEC 2009) pp 1928–1934, DOI 10.1109/CEC.2009.4983176
  * Liu et al. [2014] Liu Hl, Gu F, Zhang Q (2014) Decomposition of a multiobjective opti- mization problem into a number of simple multiobjective subproblems. IEEE Transactions on Evolutionary Computation 18(3):450–455
  * Liu et al. [2017] Liu HL, Chen L, Deb K, Goodman ED (2017) Investigating the effect of imbalance between convergence and diversity in evolutionary multiobjective algorithms. IEEE Transactions on Evolutionary Computation 21(3):408–425, DOI 10.1109/TEVC.2016.2606577
  * Liu et al. [2009] Liu M, Zou X, Yu C, Wu Z (2009) Performance assessment of DMOEA-DD with CEC 2009 MOEA competition test instances. 2009 IEEE Congress on Evolutionary Computation (CEC 2009) (1):2913–2918, DOI 10.1109/CEC.2009.4983309
  * Liu et al. [2019] Liu Q, Liu X, Wu J, Li Y (2019) An improved NSGA-III algorithm using genetic k-means clustering algorithm. IEEE Access 7:185239–185249, DOI 10.1109/ACCESS.2019.2960531
  * Mutlu et al. [2017] Mutlu U, Grudniewski PA, Sobey AJ, Blake JIR (2017) Selecting an optimisation methodology in the context of structural design for leisure boats. Design & Construction of Super & Mega Yachts (May):10–11
  * Nusimer [2017] Nusimer S (2017) Introduction to Coevolutionary Theory. Macmillan Learning
  * Potter and De Jong [1994] Potter MA, De Jong KA (1994) A cooperative coevolutionary approach to function optimization. The Third Parallel Problem Solving From Nature pp 249–257, DOI 10.1007/3-540-58484-6˙269, 9780201398298
  * Potter and De Jong [2000] Potter MA, De Jong KA (2000) Cooperative coevolution: an architecture for evolving coadapted subcomponents. Evolutionary computation 8(1):1–29, DOI 10.1162/106365600568086
  * Priester et al. [2013] Priester C, Narukawa K, Rodemann T (2013) A Comparison of Different Algorithms for the Calculation of Dominated Hypervolumes. Gecco’13: Proceedings of the 2013 Genetic and Evolutionary Computation Conference pp 655–662, DOI 10.1145/2463372.2463451
  * Raghuwanshi and Kakde [2006] Raghuwanshi MM, Kakde OG (2006) Genetic algorithm with species and sexual selection. 2006 IEEE Conference on Cybernetics and Intelligent Systems 00:590–595, DOI 10.1109/ICCIS.2006.252229
  * Rosin and Belew [1997] Rosin CD, Belew RK (1997) Methods for Competitive Co-evolution. Evolutionary Computation 5(1):1–29
  * Seada and Deb [2015] Seada H, Deb K (2015) U-NSGA-III: A Unified Evolutionary Algorithm for Single, Multiple, and Many-Objective Optimisation. In: Gaspar-Cunha A, Henggeler Antunes C, Coello CC (eds) Evolutionary Multi-Criterion Optimization: EMO 2015., Springer International Publishing, Cham, pp 1–30, DOI 10.1007/978-3-319-15892-1˙3, URL http://dx.doi.org/10.1007/978-3-319-15892-1{_}3
  * Sobey and Grudniewski [2018] Sobey AJ, Grudniewski PA (2018) Re-inspiring the genetic algorithm with multi-level selection theory: Multi-level selection genetic algorithm. Bioinspiration and Biomimetics 13(5):1–13, DOI 10.1088/1748-3190/aad2e8
  * Sobey and Grudniewski [2019] Sobey AJ, Grudniewski PA (2019) There’s no Free Lunch: A Study of Genetic Algorithm Use in Maritime Applications. In: 18th Conference on Computer Applications and Information Technology in the Maritime Industries (COMPIT)
  * Trivedi et al. [2017] Trivedi A, Srinivasan D, Sanyal K, Ghosh A (2017) A survey of multiobjective evolutionary algorithms based on decomposition. IEEE Transactions on Evolutionary Computation 21(3):440–462, DOI 10.1109/TEVC.2016.2608507
  * Tseng and Chen [2007] Tseng LY, Chen C (2007) Multiple trajectory search for multiobjective optimization. In: 2007 IEEE Congress on Evolutionary Computation (CEC 2007), pp 3609–3616, DOI 10.1109/CEC.2007.4424940
  * Tseng and Chen [2009] Tseng LY, Chen C (2009) Multiple trajectory search for unconstrained/constrained multi-objective optimization. In: 2009 IEEE Congress on Evolutionary Computation (CEC 2009), pp 1951–1958, DOI 10.1109/CEC.2009.4983179
  * Wang et al. [2018] Wang Z, Bai J, Sobey A, Xiong J, Shenoi A (2018) Optimal design of triaxial weave fabric composites under tension. Composite Structures 201(June):616–624, DOI 10.1016/j.compstruct.2018.06.090
  * While et al. [2012] While L, Bradstreet L, Barone L (2012) A fast way of calculating exact hypervolumes. IEEE Transactions on Evolutionary Computation 16(1):86–95, DOI 10.1109/TEVC.2010.2077298
  * Whitley et al. [1999] Whitley D, Rana S, Heckendorn RB (1999) The island model genetic algorithm: On separability, population size and convergence. Journal of Computing and Information Technology 7:33–47, DOI 10.1.1.36.7225
  * Zhang and Li [2007] Zhang Q, Li H (2007) MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition. IEEE Transactions on Evolutionary Computation 11(6):712–731, DOI 10.1109/TEVC.2007.892759
  * Zhang and Suganthan [2009] Zhang Q, Suganthan PN (2009) Final Report on CEC ’ 09 MOEA Competition. Tech. rep.
  * Zhang et al. [2009] Zhang Q, Zhou A, Zhao S, Suganthan PN, Liu W (2009) Multiobjective optimization Test Instances for the CEC 2009 Special Session and Competition. Tech. rep.
  * Zhou et al. [2011] Zhou A, Qu BY, Li H, Zhao SZ, Suganthan PN, Zhang Q (2011) Multiobjective evolutionary algorithms: A survey of the state of the art. Swarm and Evolutionary Computation 1:32–49, DOI 10.1016/j.swevo.2011.03.001
  * Zitzler and Simon [2004] Zitzler E, Simon K (2004) Indicator-Based Selection in Multiobjective Search. In: Parallel Problem Solving from Nature - PPSN VIII, pp 832–842, DOI 10.1007/978-3-540-30217-9˙84
  * Zitzler et al. [2000] Zitzler E, Deb K, Thiele L (2000) Comparison of Multiobjective Evolutionary Algorithms: Empirical Results. Evolutionary Computation 8(2):173–195, DOI 10.1162/106365600568202
  * Zitzler et al. [2001] Zitzler E, Laumanns M, Thiele L (2001) SPEA2: Improving the Strength Pareto Evolutionary Algorithm. Tech. rep., DOI 10.1.1.28.7571
  * Zitzler et al. [2002] Zitzler E, Thiele L, Laumanns M (2002) Performance Assessment of Multiobjective Optimizers: An Analysis and Review. IEEE Transactions on Evolutionary Computation. IEEE Transactions on Evolutionary Computation 7(2):117–132, URL http://www.tik.ee.ethz.ch/education/lectures/DSE/ZLTF03.pdf