Adaptive evolutionary algorithms for portfolio selection problems

Abstract

In this contribution we propose to solve complex portfolio selection problems via Evolutionary Algorithms (EAs) that resort to adaptive parameter control to manage the Exploration versus Exploitation balance and to find (near)-optimal solutions. This strategy modifies the algorithm’s parameters during execution, and relies on continuous feedbacks provided to the EA with respect to some user-defined criteria. In particular, our study aims to understand whether a standard EA can benefit from a robust method that iteratively selects the crossover operator out of a predefined set, in the context of optimised portfolio choices. We apply this approach to large-scale optimization problems, by tackling a number of NP-hard mixed-integer programming problems. Our results show that generic EAs equipped with single crossover operator do not perform homogeneously across problem instances, whereas the adaptive policy leads to robust (and improved) solutions, by alternating exploration and exploitation on the basis of the features of the current search space.

1 Introduction

Evolutionary Algorithms (EAs) are high-level strategies that aim to solve optimization problems by mimicking the Darwin theory of natural evolution and selection. From a conceptual point of view, EAs manage (i.e., maintain and manipulate) a population of individuals, and modify them via the application of variation operators: this is done to identify a (near)-optimal solution that optimizes a given fitness function, used to assess the individuals’ quality.

Since their introduction (Holland 1992; Goldberg 1989), Evolutionary Algorithms have been applied to many fields including logistics (Prins 2004; Archetti et al. 2012), meta-optimization (Birattari et al. 2002; Smit and Eiben 2009), economics (Tapia et al. 2007; Arifovic 1994) and finance (Dempster and Jones 2001; Hoogs et al. 2007): with respect to the last field, we mention in particular credit risk management (Wang et al. 2022; Brabazon and Keenan 2004), algorithmic trading (Brabazon and O’Neill 2004; Jeong et al. 2021) and the Portfolio Selection Problem (PSP) (Markowitz 1952, 1959), which represents one of the most studied subjects in finance.

The basic idea of portfolio selection developed by Markowitz (1952) involves the selection of promising assets in terms of their return and risk, and the allocation of capital to each of them: PSP was formulated as a bi-criteria optimization problem in a mean-variance framework, under the hypothesis that the distributions of asset returns are fully described by their means, variances and covariances: a growing body of literature outlines that the approximation of the exact maximum expected utility achieved by optimal mean-variance outperforms the one obtained by asymmetric risk measures for a variety of utility functions (see e.g. Carleo et al. 2017 for a comprehensive empirical study). However, normal returns or quadratic utility are sufficient but not necessary conditions for the optimality of mean-variance portfolios (Markowitz 2014), and since neither of the two assumptions hold in practice and given that mean-variance solutions are severely unstable (Corazza et al. 2013; Procacci and Aste 2022), new approaches have been investigated, and will be discussed in what follows.

First, evidence shows that asset returns are asymmetric and display excess kurtosis, so that the mean-variance approach cannot fully describe the investor preferences: new risk measures (Chen and Wang 2008; Maillard et al. 2010) have been proposed to satisfy some formal properties (Artzner et al. 1999), to take into account non-normal empirical distributions (Gilli et al. 2006) and/or to deal with unstable and poorly diversified solutions arising from noisy estimates of expected returns (Kizys et al. 2022). Second, it has to be taken into account that realistic formulations of the optimization problem have to consider extra-features as integer constraints, leading to mixed-integer constrained problems that have been proven to be NP-hard (Moral-Escudero et al. 2006), and that cannot be solved by traditional methods: in this case, EA-based approaches are particularly attractive, on the basis of different features that will be detailed in what follows.

The first application of EAs to PSP dates back to the nineties’ (Arnone et al. 1993; Loraschi et al. 1995; Loraschi and Tettamanzi 1995; Liu and Stefek 1995), and take into account different problem formulations and constraints (di Tollo and Roli 2008). More recent contributions improve the search component by embedding a hybrid mechanism that either add a local search component to refine found solutions, or introduce advanced constructive procedures to identify good individuals: the resulting strategies are referred to as memetic algorithms (Neri et al. 2012), and have been applied to Portfolio Selection by Maringer and Winker (2003) and Maringer (2005), that enhance Evolutionary Algorithms by adding Simulated Annealing (Crama and Schyns 2003) and Tabu Search (Schaerf 2002) modules in the framework of different risk measures. Moreover, several studies propose to hybridize evolutionary algorithms with machine learning techniques (Chen et al. 2020; Yaman and Dalkılıç 2021), whereas Salehpoor and Molla-Alizadeh-Zavardehi (2019) discuss a strategy which combines genetic algorithms with electromagnetism-like algorithms, Particle Swarm optimization, genetic network programming and Simulated Annealing. Finally, Kalayci et al. (2020) employ a hybrid approach based on continuous ant colony optimization, genetic algorithms and artificial bee colony for solving a cardinality constrained PSP. One of the main advantages of Evolutionary Computation lies in its strength to tackle multi-objective formulations, as shown by the applications of Multi Objective Evolutionary Algorithms (MOEAs), see, e.g. Streichert et al. (2004a), Streichert et al. (2004b), Streichert et al. (2004c) and Lin et al. (2001), Diosan (2005) in the context of multi-objective portfolio selection problems; also single-objective formulations have been devised (Chang et al. 2000; Xia et al. 2000; di Tollo and Roli 2008; Wang et al. 2006), even though it has been reported that single-objective formulations are less apt to embed users’ preferences (Subbu et al. 2005).

All the above mentioned contributions take into account a single variation operator to perform the recombination of individuals. Although it has been the current practice for years, this could lead to underperformance in terms of the optimization results: this is due to the Exploration vs Exploitation (EvE) balance. In a nutshell, one may describe the behaviour of an Evolutionary Algorithm by using the concepts of exploration and exploitation: the former, also referred to as diversification, ensures that the algorithm is able to explore regions of the search space that are far from each other; the latter, which is more broadly referred to as intensification, identifies the ability of the algorithm to find good solutions for the problem at hand. The balance between exploration and exploitation represents an open research topic (Maturana et al. 2009, 2010; Črepinšek et al. 2013; Huang et al. 2020) and a key issue of the overall EAs’ performances: this balance may be monitored and efficiently managed during the algorithm execution via the control of specified parameters, and in our case these are represented by the application rates of the different crossover operators available for the problem at hand.

Based on these considerations, in our contribution we want:

• 1. To give an overview of all crossover operators reported into the literature about Evolutionary approaches for Portfolio Selection;

• 2. To introduce a control procedure that uses all the mentioned operators during the algorithm run;

• 3. To perform an experimental analysis over different Portfolio Selection formulations.

As for the control procedure, we are exploiting the adaptive controller proposed by (di Tollo et al. 2015), that identifies the operator to be applied at each iteration on the basis of the past performances w.r.t. the criteria used to assess the population’s quality (average fitness) and diversity (entropy). In this way it is possible to devise adaptive strategies that select the operator needed in order to maintain the desired EvE balance, on the basis of an external parameter. Our goal is to show that the application of this control procedure leads to better (and/or more robust) solutions than the ones found by single-operator Evolutionary Algorithms.

The remainder of the paper is organized as follows. In Sect. 2 we present a literature review of evolutionary methods for portfolio management. In Sect. 3 we review the literature on crossover operators, with special focus on portfolio selection applications. In Sect. 4 we introduce a parameter control procedure and in Sect. 5 we perform a computational analysis over different formulations of the portfolio selection problem. Section 6 concludes.

2 Evolutionary algorithms for portfolio selection problems

Evolutionary algorithms are bio-inspired and population-based metaheuristics, which manage an evolving population of candidate solutions¹: a population is generated according to a user-defined random distribution, and modified by performing iteratively the following three steps:

• 1. Evaluate each individual according to a fitness function;

• 2. Identify the fittest individuals in order to converge to a (near)-optimal solution;

• 3. Modify the population through replacement of some individuals (selected w.r.t. a user-defined criterion) with new ones generated by applying crossover operators.

In the context of Portfolio Selection Problems, EAs have been applied to several extensions of the basic Markowitz model (Kolm et al. 2014; Gunjan and Bhattacharyya 2022) to obtain realistic results and/or to take into account real-world constraints. In what follows, we review the main literature about the applications of evolutionary algorithms to portfolio selection, before outlining some of the main components of the algorithm in the next sections.

The papers of Arnone et al. (1993) and Loraschi et al. (1995) are pioneering contributions in the field of evolutionary algorithms for Portfolio Selection Problems: they introduce basic approaches in order to determine the (approximated) constrained frontier of efficient portfolios, from a mean-semivariance point of view: they propose to exploit a genetic approach with a problem-specific crossover operator to tackle down-side risk measures, showing promising results.

Chang et al. (2000) propose to extend the standard mean-variance portfolio optimization model to take into account cardinality constraints and to impose a constraint on the proportion of each asset held in the portfolio. They address a NP-hard multi-objective mixed-integer quadratic programming (MIQP) problem (Moral-Escudero et al. 2006), by using a single-objective formulation in which the minimum return constraint and the risk aversion coefficient $\lambda$ are incorporated into the objective function. A similar approach is devised by Xia et al. (2000), in which the authors propose to model the PSP with an order of the expected returns of securities and with transaction costs. Also Chang et al. (2009) examine a genetic algorithm for single-objective problems with standard evolutionary features: they compare all the Pareto frontiers generated from portfolios with different number of assets, showing that low cardinality portfolios tend to outperform more complex portfolios with a larger number of assets.

The contribution of Lin and Liu (2008) is arguably the first one that proposes to solve the classic mean-variance quadratic program with minimum transaction lots constraint through evolutionary algorithms. The key point of this contribution is to consider a mixed-integer linear program in which the amount invested in each asset must be a multiple of the minimum amount that can be purchased of that security (roundlot).

Huang (2007, 2008) propose to overcome the limitations of mean-variance models by taking both the asymmetry and the uncertainty of stock returns into account, by using fuzzy logic (Zadeh 1965) to model the portfolio’s returns, allowing the user to refine the Markowitz model, by relaxing the usual hypothesis of normally distributed returns through the assumption that returns are only partially known, i.e. the mean $\mu$ and the standard deviation $\sigma$ of the distribution are fuzzy. These contributions introduce hybrid algorithms combining genetic algorithms and random fuzzy simulation to provide a general solution method. More recently, several studies (Kar et al. 2019; Yu et al. 2020) contribute to the literature by introducing new fuzzy hybrid methodologies, which combine genetic algorithms with machine learning techniques, in order to deal with multi-objective and multi-period portfolio problems, which take also into account higher-order moments.

Soleimani et al. (2009) extend the mean-variance model with the integer constraints proposed by Chang et al. (2000), and include a market capitalization constraint: the possible market sectors² are sorted in decreasing order with respect to their market capitalization, and the total weight of assets in the portfolio belonging to a given sector must be consistent with its market cap ranking. This constraint is formulated as follows:

$$\begin{aligned} \sum _{i\in \vert j\vert }x_i+(1-\delta _j)\ge \sum _{i\in \vert j+1\vert }x_i \qquad j=1,2,\dots ,s-1 \end{aligned}$$

(1)

where $x_i$ is the weight of security i in the portfolio and $\delta _i$ is a binary variable, which is equal to 1 if the asset is included in sector j and 0 otherwise.

Krink and Paterlini (2011) introduce a methodology based on Differential Evolution (Storn and Price 1997), which they call Differential Evolution for Multiobjective Portfolio Optimization (DEMPO): they propose some restrictions on turnover, by imposing a set of constraints involving the changes to the asset allocation (say, at time t) deriving from portfolio re-balance. For instance, they impose that the variation of the proportion of each asset must be greater than a threshold $\Delta _i$, and they constrain the total turnover ratio by imposing a maximum turnover ratio TR, as follows:

$$\begin{aligned}{} & {} \vert x_i^{t+1}-x_i^{t}\vert \ge \Delta _i \quad \text {or}\quad \vert x_i^{t+1}-x_i^{t}\vert =0 \end{aligned}$$

(2a)

$$\begin{aligned}{} & {} \sum _{i=1}^N\vert x_i^{t+1}-x_i^{t}\vert \le TR \end{aligned}$$

(2b)

Anagnostopoulos and Mamanis (2011) tackle quantile-based risk measures, namely Value-at-Risk (VaR) and Expected Shortfall (ES): they include floor and ceiling constraints, cardinality and class constraints, which are used to limit the the proportion of invested capital in assets with similar features. The constraints are handled with a problem-specific solution representation based on real-encoding, and infeasible solutions are managed with a novel repair mechanism, which presents some similarities with the approach outlined in Chang et al. (2000).

Hochreiter (2015) suggests to exploit Evolutionary Algorithms in order to tackle portfolio selection problems based on risk parity (Roncalli 2013): the main idea behind this approach is to determine a portfolio whose assets are included in such a way that the risk contributions of all the securities are made equal; denoting the portfolio standard deviation with $\sigma ({\textbf{x}})$, the marginal risk contribution of each asset $x_i$ is given by:

$$\begin{aligned} \frac{\partial \sigma ({\textbf{x}})}{\partial x_i}=\frac{x_i\sigma _i^2+\sum _{i\ne j}x_j\sigma _{ij}}{\sigma ({\textbf{x}})} \end{aligned}$$

(3)

The general formulation of the risk parity problem (Maillard et al. 2010) can be managed via sequential quadratic programming (SQP), in which the authors propose to remove the long-only constraint and to include the floor and ceiling constraint; another approach, presented by Kaucic (2019), imposes a risk parity constraint into cardinality constrained portfolios.

Lwin et al. (2017) propose a hybrid multiobjective evolutionary algorithm for solving mean-VaR problems with real-world constraints, including cardinality, floor, ceiling, pre-assignment, roundlots and class constraints: a learning-guided solution generation strategy is incorporated into the optimization process in order to guide the search process towards promising regions. A slightly different perspective is discussed by Ranković et al. (2016): the authors propose to model a novel mean-VaR portfolio optimization problem, where VaR is estimated with a univariate Generalized Auto-Regressive Conditional Heteroscedasticity (GARCH) volatility model. They opt for a parametric VaR, under the hypothesis that returns follow a standardized Student’s t distribution, with d degrees of freedom, whereas the conditional portfolio volatility is estimated via univariate GARCH(1, 1). The resulting multiobjective mean-VaR portfolio optimization problem with fixed asset holdings is solved by employing a Nondominated Sorting Genetic Algorithm (NSGA II).

In a nutshell: a strand of the literature on portfolio optimization proposes to use evolutionary algorithms to solve problems with complex constraints and/or objective functions. All the considered contributions rely on a broad range of crossover operators, whose role in finding a good solution is discussed in Sect. 3, together with a literature review.

3 Crossover operators for portfolio selection problems

As we have discussed in the previous sections, Evolutionary Algorithms operate via the evolution of a population of individuals, which is implemented by the application of variation (crossover and mutation) operators. As pointed out by Herrera et al. (2005), the crossover operator is the main search operator which leads the search process towards different areas of the solution space, and a key point of success for EAs lies in generating offspring solutions in a neighborhood of the parents, given that the degree of proximity is typically relevant to guide the search process properly.³

Since the introduction of Genetic Algorithms, a broad range of such operators has been introduced, both general purpose operators such as one-point crossover (Holland 1992), uniform crossover (Syswerda 1993), arithmetic crossover (Michalewicz 1992), heuristic crossover (Wright 1991) and tailored to specific domains, such as fuzzy crossover (Voigt et al. 1995), unimodal crossover (Ono and Kobayashi 1999), parent centric crossover (Ballester and Carter 2004) and simulated binary crossover (Deb et al. 1995). In this section we want to review these operators, in order to detail those that will be used in our operators pool, that will be outlined in Sect. 4. Though the elements of the search space have been often represented by means of binary encoding (Goldberg 1989), we stick to the tradition of GA-based portfolio selection literature, by focusing on a real-valued representation. In what follows, we will describe the different crossover operators proposed in the literature, highlighting their behaviour and their relations with the portfolio selection literature.

• Single point crossover [OPX]

  The single point crossover is the simplest crossover operator, which has been first proposed in the seminal works of Holland (1992) and Goldberg (1989). It generates an offspring by mating two parents by means of a cutting point, i.e. a randomly chosen position in the portfolio, by which the genetic material of each parent is split into two parts. It has been widely used in portfolio selection literature, in particular by Chang et al. (2000) and Suksonghong and Boonlong (2021), who propose to solve mean-variance optimization with integer constraints through GAs, and by Lin and Liu (2008), that discuss a similar approach with minimum lots constraints. This operator works as follows. Given a population of N individuals $\{x_1,x_2,\dots ,x_N\}$, each individual is characterized by n genes; let $x_i$ denote a parent and let $y_i$ be an offspring, then we have:

  $$\begin{aligned} x_i= & \, [x_i(1),x_i(2),\dots ,x_i(N)] \end{aligned}$$

  (4)
  $$\begin{aligned} y_i= & \, [y_i(1),y_i(2),\dots ,y_i(N)] \end{aligned}$$

  (5)

  Consider now two parents $x_a$ and $x_b$ and a cutting point $k\in {\mathbb {N}}$ randomly chosen in the interval $[1,n-1]$. Then, the two parents are mated to generate two offsprings, which in turn inherit the genes from their parents in a random fashion, as follows:

  $$\begin{aligned}{} & {} y_1(n)=[x_a(1),x_a(2),\dots ,x_a(k),x_b(k+1),\dots ,x_b(N)] \end{aligned}$$

  (6)
  $$\begin{aligned}{} & {} y_2(n)=[x_b(1),x_b(2),\dots ,x_b(k),x_a(k+1),\dots ,x_a(N)] \end{aligned}$$

  (7)

• Multiple point crossover [MPX]

  The multiple point crossover (Goldberg 1989) is an extension of the single point crossover, in which the procedure includes more than one cutting point. In the context of portfolio selection problems, Skolpadungket et al. (2007) apply a three-point crossover to multiobjective portfolio optimization problems, while Hochreiter (2008) introduces an evolutionary approach based on stochastic programming, with the aim of solving multi-period portfolio selection problems by using a wide range of GAs, including a version with N-point crossover.

  This method works as follows. Consider, for instance, a three point crossover; three numbers are randomly drawn, therefore three different cutting point are chosen (say $k_1$, $k_2$, $k_3$). The cutting points are drawn one after another, so that that the inequality $k_1<k_2<k_3$ is verified and the cutting points are defined over the $[1,n-1]$ interval. Hence, an offspring inherits the first portion of genes (assets for PSP) $[1, k_1]$ from parent $x_a$, the second portion $[k_1, k_2]$ from parent $x_b$, the third one $[k_2, k_3]$ from parent $x_a$ and finally the last portion $[k_3, N-1]$ from parent $x_b$, as follows:

  $$\begin{aligned} \begin{aligned} \qquad \quad y_i=&\,[x_a(1),\dots ,x_a(k_1),x_b(k_1+1),\dots ,x_b(k_2),x_a(k_2+1),\\&\dots ,x_a(k_3),x_b(k_3+1),\dots ,x_b(N)] \end{aligned} \end{aligned}$$

  (8)

  The remaining values in the solution vectors, i.e. the first and the third portion of genes of parent $x_a$, the second and the last portion of genes of parent $x_b$ may be allocated to a second offspring.

• Linear crossover [LNX]

  The linear crossover has been devised by Wright (1991) to overcome some drawbacks of the n-point crossover: to our knowledge, there are no studies applying the linear crossover to GAs for portfolio optimization problems. The authors propose to generate three offsprings: each kth gene in the offspring is computed as a linear combination of the kth gene in parent 1 and in parent 2.

  $$\begin{aligned} {\left\{ \begin{array}{ll} y_i(k)&{}=0.5\cdot x_1(k)+0.5\cdot x_2(k)\\ y_{i+1}(k)&{}=1.5\cdot x_2(k)-0.5\cdot x_2(k)\\ y_{i+2}(k)&{}=-0.5\cdot x_1(k)+1.5\cdot x_2(k)\\ \end{array}\right. } \end{aligned}$$

• Uniform crossover [UX]

  The uniform crossover, devised by Syswerda (1993), generates an offspring by mating two parents: each kth gene is passed either from parent $x_a$ with probability $p=0.5$ or from parent $x_b$ with probability $1-p=0.5$, for each $k\in [1,n]$ position, that is:

  $$\begin{aligned} y_i(k)= {\left\{ \begin{array}{ll} x_a(k) \quad \hbox { with probability}\ p=0.5 \\ x_b(k) \quad \hbox { with probability}\ (1-p)=0.5 \end{array}\right. } \end{aligned}$$

  In order to solve the optimal portfolio choice problem, the uniform crossover has been often applied in the literature: for instance, Chang et al. (2009) and Drenovak et al. (2022) apply this crossover operator to a set of non-convex PSPs. Moreover, Arnone et al. (1993), Loraschi et al. (1995) and Loraschi and Tettamanzi (1995) examine a GA with a modified version of uniform crossover. Denoting with with $TOT_{x_a}$ and $TOT_{x_b}$ the total sums of the genes making up, respectively, parents $x_a$ and $x_b$, and supposing that a gene kth from parent $x_a$ has been chosen, the value of the kth gene in the ith offspring is:

  $$\begin{aligned} y_i(k)=\min \left\{ \max \{x_a(1),\dots ,x_a(k),\dots ,x_a(n)\},x_a(k)\frac{TOT_{x_a}+TOT_{x_b}}{2TOT_{x_a}}\right\} \end{aligned}$$

  (9)

• Global uniform crossover [GUX]

  The global uniform, proposed by Simon (2013), is a generalization of the two-parent uniform crossover, and, up to the authors’ knowledge, it has not yet found application for the portfolio selection problem. Hence, in what follows we propose to introduce this operator in the context of portfolio selection problems. The rationale of this operator is to extend the parent pool to the whole population, so that the kth gene is selected with probability $p=1/N$ from the ith parent. This algorithm, though, chooses genes in a completely random fashion; as a consequence, one may redefine the probability of selecting the kth gene in accordance with a fitness-based criterion.

• Queen-bee crossover [QBX]

  This method, discussed in Sung (2007), mimics the reproduction process of bees in nature; the author tests this recombination tool with a combinatorial problem and two continuous function optimization problems. We propose to introduce this crossover strategy for portfolio selection problems, as we have not found any application of this approach to GA-based portfolio optimization.

  We point out that a major limitation of this operator is its fast convergence to (potentially) local solutions. The idea is the following. The queen-bee represents the fittest parent, which is mated, at each step, with a randomly chosen parent, which in turn is dropped at the following step and she is replaced with another parent and so on. In order to have the parents mated, a wide array of choices is available (e.g. simple crossover techniques, like uniform or multiple point crossover strategies).

• Arithmetic and average crossover [AX]

  The arithmetic crossover, devised by Michalewicz (1992), produces two offspring by mating two parents at each iteration. In the context of portfolio selection problems, this crossover strategy has been applied by Xia et al. (2000) and Mazraeh et al. (2022) to solve the classic mean-variance problem. The offsprings are generated, gene by gene, as a weighted mean of their parents genes, displaced in the same position of the resulting offspring gene, as follows:

  $$\begin{aligned} y_i(k)=\beta x_a(k)+(1-\beta )x_b(k) \end{aligned}$$

  (10)

  The average crossover, mentioned in Michalewicz (1992) and also discussed in Simon (2013), simply derives the kth gene in the offspring as an average of his parents genes, drawn exactly from the same position in the vector representing an individual, as follows:

  $$\begin{aligned} y_i(k)=(x_a(k)+x_b(k))/2 \end{aligned}$$

  (11)

  Note that the average crossover is a special case of the arithmetic operator, i.e. we simply impose $\beta =0.5$.

• Simplex crossover [SPX]

  The design of the simplex crossover has been proposed by Renders and Bersini (1994) and it can be viewed as a generalization of the arithmetic crossover (Michalewicz and Schoenauer 1996). Up to the authors’ knowledge, no application of simplex crossover to portfolio optimization models exists in literature, hence we propose to test its behaviour for PSPs. The operator identifies a groups G of possible parents, and selects $k>2$ parents; then it determines the best and the worst individual (in terms of fitness) within G, and computes its centroid c, by removing the worst individual $x_i^w$ from it, as follows:

  $$\begin{aligned} c=\sum _{x_i\in G-x_i^w}x_i/(k-1) \end{aligned}$$

  (12)

  Then the ‘reflected point’ is computed:

  $$\begin{aligned} x_r=c+(c-x_i^w) \end{aligned}$$

  (13)

  If $x_r$ is better (in terms of fitness) than the best selected individual $x_{best}$, an expanded point $x_e$ is determined:

  $$\begin{aligned} x_e=x_r+(x_r-c) \end{aligned}$$

  (14)

  If $x_e$ is better than $x_r$, the offspring is $x_e$, else the offspring is $x_r$; otherwise if $x_r$ is not better than $x_{best}$ but it is better than $x_w$, then the offspring is $x_r$.

• Geometrical crossover [GX]

  With this operator, an offspring can be generated in this way:

  $$\begin{aligned} y_i(k)=\sqrt{x_a(k)\cdot x_b(k)} \qquad \text {for each} \quad k\text {-th gene} \end{aligned}$$

  (15)

  The geometrical crossover has been first proposed by Michalewicz et al. (1996), in which an offspring can be generated in this way:

  $$\begin{aligned} y_i(k)=\sqrt{x_a(k)\cdot x_b(k)} \qquad \text {for each} \quad k\text {-th gene} \end{aligned}$$

  (16)

  where $y_i$ denotes an offspring, $x_a$ and $x_b$ denote a given pair of parents. The mating process is repeated until a new population of N individuals is generated. Some simple tests are carried out to compare its performance to standard crossover operators, and though the authors have shown its effectiveness in the context of constrained problems, we have not found any application of this crossover strategy in the context of portfolio optimization, hence we propose to test its performance on a variety of portfolio selection problems.

• Direction-based crossover [DBX]

  The direction-based crossover, devised by Arumugam et al. (2005), is a variant of the linear crossover in the sense that the population is biased towards fitter individuals, i.e. problem-specific information is introduced in the search process.

  The direction-based crossover uses the fitness function information to determine the direction of the search in the following way. First, we denote with $f(\cdot )$ a generic fitness function and with r a random number such that $r\in U[0,1]$. For two given parents $x_a$ and $x_b$, assuming that $f(x_b)<f(x_a)$, the operator generates an offspring $y_i$ according to the following rule:

  $$\begin{aligned} {\left\{ \begin{array}{ll} y_1=r(x_b-x_a)+x_b \quad \text {if }f(x_b)<f(x_a)\\ y_1=r(x_a-x_b)+x_a \quad \text {otherwise}\\ \end{array}\right. } \end{aligned}$$

• Heuristic crossover [HX]

  The heuristic crossover, devised by Wright (1991), is a more sophisticated variant of the direction-based crossover: to our knowledge, Yusuf et al. (2019) is the only application of this version of the heuristic crossover in the context of Portfolio Selection Problems. It works as follows: the parents are chosen in the mating pool and their fitness, before running the usual procedure of gene transmission, is compared. Afterwards, a random number r is generated from a uniform distribution U[0, 1] and the genes are chosen according to the rule given in Eq. 17. Note that the resulting population is expected to display less diversity and a better mean vector after the crossover stage. For maximization problems we have:

  $$\begin{aligned} y_i(k)=x_b(k)+r(x_a(k)-x_b(k)) \quad \hbox { if}\ f(x_b)>f(x_a) \end{aligned}$$

  (17)

• Flat crossover [FX]

  The flat crossover, proposed by Radcliffe (1991), generates the offsprings from a uniform distribution, tweaking the classical crossover techniques in order to improve the search process in terms of exploration, since it extends the search process to every possible value contained in a uniform distribution bounded as follows, for a given kth gene of a generic offspring $y_i$:

  $$\begin{aligned} y_i(k)\sim U[\min (x_a(k),x_b(k)),\max (x_a(k),x_b(k))] \end{aligned}$$

  (18)

  Still, note that the offspring is generated from a uniform distribution bounded by the parents genes, which actually is not that beneficial for exploration purposes, according to the framework sketched in Herrera et al. (2005). Some applications of a variant of flat crossover to portfolio selection problems are discussed in the following item.

• Blend crossover [BLX]

  The blend crossover, proposed by Eshelman and Schaffer (1993), deals with the limited search capabilities of the flat crossover by adding a parameter $\alpha$ whose aim is to widen or to shrink the search domain. Hochreiter (2008) uses a GA with blend crossover to solve multi-period portfolio selection problems, with a wide range of structurally different risk measures applied for empirical simulations. Furthermore, Streichert et al. (2004b) investigate the impact of different crossover operators for a real-valued GA on a mean-variance cardinality constrained portfolio optimization problem, showing that blend crossover tends to display better performance compared to standard 1-point and N-point crossover approaches. More recently, Mazraeh et al. (2022) devise a combined model based on Grey Wolf optimizer and machine learning preselection methods, in which the blend crossover is used.

  Given two parents $x_a$ and $x_b$, then the kth gene of an offspring is drawn from a random uniform distribution, as follows:

  $$\begin{aligned} x_{min}(k)=\min (x_a(k),x_b(k)), \quad x_{max}(k)=\max (x_a(k),x_b(k)) \end{aligned}$$

  (19)

  Then we have:

  $$\begin{aligned} y_i(k)\sim U[x_{min}(k)-\alpha \Delta _x,x_{max}(k)+\alpha \Delta _x] \end{aligned}$$

  (20)

  with $\Delta _x=x_{max}-x_{min}$. As highlighted by Herrera et al. (2005), a negative alpha encourages exploitation, whereas a positive alpha steers the crossover operator towards exploration; note that the blend crossover is a simple generalization of the flat one: indeed, for $\alpha =0$, they are equivalent.

• Simulated binary crossover and fuzzy recombination [SBX] and [FR]

  The simulated binary crossover, proposed by Deb et al. (1995), generates two vectors of offsprings from a probability distribution, which is dependent on the location of their parents: in other terms, this crossover is self-adaptive in the sense that the spread of the possible offspring solutions depends on the distance between the parents, which decreases as the population converge. Fuzzy recombination is based on a similar hypothesis and it can be derived from the simulated binary crossover, so we discuss their properties jointly: the difference between the two operators stays in that [FR] is based on a triangular probability density, whilst the [SBX] design is based on a specific shape of the distribution, as we discuss below. Mehlawat et al. (2021) propose to use the simulated binary crossover to solve a mean-absolute semideviation problem, where the resultant multiobjective credibility model is solved with a real-coded genetic algorithm.

  The simulated binary crossover is defined as:

  $$\begin{aligned}{} & {} y_1=0.5[(1-\beta )x_a+(1+\beta )x_b] \end{aligned}$$

  (21)
  $$\begin{aligned}{} & {} y_2=0.5[(1+\beta )x_a+(1-\beta )x_b] \end{aligned}$$

  (22)

  $x_a$ and $x_b$ are independent samples from the population of parents and $\beta$ is a sample from a random number generator with density:

  $$\begin{aligned} p(\beta )= {\left\{ \begin{array}{ll} 0.5(n+1)\beta ^n \qquad &{}{\beta \le 1} \\ 0.5(n+1)\frac{1}{\beta ^{n+2}} \qquad &{}{\beta >1} \end{array}\right. } \end{aligned}$$

  This distribution can be obtained by sampling from a random uniform U[0, 1] and then by the following transformation:

  $$\begin{aligned} \beta = {\left\{ \begin{array}{ll} {(2u)^{\frac{1}{n+1}}} \qquad &{} \text {if }U(0,1)\le 0.5 \\ {[2(1-u)]^{\frac{-1}{(n+1)}}} \qquad &{}\text {otherwise} \end{array}\right. } \end{aligned}$$

  The fuzzy recombination, proposed by Voigt et al. (1995), is very similar to the simulated binary crossover. The density of $\beta$ has its maximum at $\beta =1$. while the only difference between them is the shape of the probability density $p(\beta )$, which is triangular for the fuzzy crossover:

  $$\begin{aligned} p_{\Delta }(\zeta )= {\left\{ \begin{array}{ll} \zeta +1 &{}\hbox { if}\ -1\le \zeta <1\\ 1-\zeta &{}\hbox { if}\ -0\le \zeta \le 1\\ \end{array}\right. } \end{aligned}$$

  The $\beta$ value in Eqs. 21 and 22 is then obtained as follows:

  $$\begin{aligned} \beta =1+2\zeta d \end{aligned}$$

  (23)

  As Beyer and Deb (2001) suggest, d is a ‘strategy parameter’, which determines how far the offspring should be located from parents. The random number $\zeta$ with triangular distribution can be obtained as the sum of two independent numbers U[0, 1]:

  $$\begin{aligned} \zeta =u_1+u_2-1 \end{aligned}$$

  (24)

• Laplace crossover [LX]

  The Laplace crossover, proposed by Deep and Thakur (2007), belongs to the family of parent-centric crossover operators, sharing many characteristics with the simulated binary crossover. Mittal and Srivastava (2021) introduce a refined version of the Laplace operator, which they call bounded exponential crossover [BEX], since it is based on a double exponential distribution. The authors show its superior performance in a set of numerical experiments, within the context of mean-variance-skewness portfolio optimization under uncertain environment (Liu 2010).

  Let us now comment briefly this approach. The density function of the Laplace distribution is given by:

  $$\begin{aligned} f(x)=\frac{1}{2b}exp\left( -\frac{\vert x-a \vert }{b}\right) \qquad \hbox { }\ -\infty<x<\infty \end{aligned}$$

  (25)

  where $a\in {\mathbb {R}}$ is the location parameter and $b>0$ is the scale parameter. For $b=0.5$ the probability of creating offsprings near the parents is higher and for b=1 distant points are likely to be selected as offsprings. Moreover, the authors proceed by drawing a random number $u\in {\mathbb {R}}$ from U[0, 1]; then a random number $\beta$ is generated from the Laplace distribution. This can be obtained by inverting it:

  $$\begin{aligned} \beta = {\left\{ \begin{array}{ll} a-b\log (u) \qquad \hbox { }\ u\le \frac{1}{2} \\ a+b\log (u) \qquad \hbox { }\ u>\frac{1}{2} \end{array}\right. } \end{aligned}$$

  Then, the offsprings are generated as follows:

  $$\begin{aligned}{} & {} y_1=x_a+\beta \vert x_a-x_b\vert \end{aligned}$$

  (26)
  $$\begin{aligned}{} & {} y_2=x_b+\beta \vert x_a-x_b\vert \end{aligned}$$

  (27)

• Parent-centric normal crossover [PNX]

  The parent-centric crossover, devised by Ballester and Carter (2004), seeks to improve the simulated binary crossover by generating offsprings in regions of the search space neglected by SBX; in particular, it is a parent-centric and self-adaptive operator, i.e. the spread of offspring solutions depends on the distance between parents, which decreases as the population tends to converge to a solution. To our knowledge, this approach has never been discussed in the context of portfolio selection problems, hence we propose to introduce it and to evaluate its performance.

  $$\begin{aligned}{} & {} y_1(j)\sim N(x_a(j),\vert x_b(j)-x_a(j)\vert /\eta ) \end{aligned}$$

  (28)
  $$\begin{aligned}{} & {} y_2(j)\sim N(x_b(j),\vert x_b(j)-x_a(j)\vert /\eta ) \end{aligned}$$

  (29)

  where $N(\mu ,\sigma ^2)$ is a normal random number, $\eta$ is a tunable parameter. With j we denote as usual the jth component of parent a or b.

• Unimodal normal distribution crossover [UNDX]

  The unimodal normal distribution crossover, devised by Ono and Kobayashi (1999), belongs to the family of mean-centric operators and it uses an ellipsoidal probability distribution to generate offsprings. We propose to introduce this crossover strategy for portfolio selection problems, as we have not found any application of this approach to GA-based portfolio optimization.

  Fundamentally, $(\mu -1)$ parents are randomly chosen (say, $\mu =3$) and their midpoint $x_p$ is computed; thereafter, the difference vector (primary search direction) as $d=x^{2}-x^{1}$. Furthermore a third parent $x^3$ is picked up randomly, and let D denote the distance between $x^3$ and the line connecting $x^1$ and $x^2$:

  $$\begin{aligned} D=\vert x^3-x^1\vert \times \Biggr (1-\Bigr (\dfrac{(x^3-x^1)^T(x^2-x^1)}{\vert x^2-x^1\vert \vert x^2-x^1\vert }\Bigr )^2\Biggr )^{1/2} \end{aligned}$$

  (30)

  An offspring is generated by the equation:

  $$\begin{aligned} y_1=x_p+\xi d+\sum _{i=1}^{n-1}\eta _ie_iD \end{aligned}$$

  (31)

  where $\xi$ is a random number following a random distribution $N(0,\sigma _{\xi }^2)$, $\eta _i$ are $n-1$ random numbers sampled from a normal distribution $N(0,\sigma _{\eta }^2)$ and $e_i$ an orthogonal basis vector. Ono and Kobayashi (1999) suggest to use $\sigma _{\xi }^2=0.25$ and $\sigma _{\eta }^2=(0.35)^2/n$ and $\mu =3$ to 7.

4 A controller for evolutionary algorithms

In this section we will outline the structure of the adaptive controller that is to be connected to a basic Evolutionary Algorithm in order to perform Adaptive Operator Selection (AOS), i.e., to choose at each iteration what operator to be used, out of the ones detailed in Sect. 3, depending on the criteria to be defined by the user (or by the adaptive strategy).

As we have seen into the Introduction, the EvE (exploration versus exploitation) balance is a key point in the Evolutionary Algorithm design, and in our contribution we aim to address this trade-off in a dynamic way: given the set of operators detailed in Sect. 3, the adaptive controller chooses what operator to be applied on the basis of the past operators’ performances with regard to some user-defined criteria: it is well known that some operators are designed to foster exploitation, and other to foster exploitation (Eiben and Smith 2015), but for most operators, their effect on these two criteria depends on the current state of the search. Our controller assigns a reward to each operator after each iteration, and may adopt a deterministic (pre-defined) or an adaptive strategy in order to manage the EvE trade-off over the time.

Our controller is based on Reinforcement Learning, and its main components are iterated in a state-action-reward sequence; it defines an input/output interface with the EA (solver) in which the EA itself sends the last applied operator identifier and its performance metrics w.r.t. the desired criteria, and selects the operator to be applied next on the basis of the following modules: Aggregated Criteria Computation, Reward Computation, Credit Assignment, Operator Selection (Maturana et al. 2010; di Tollo et al. 2015). These modules are executed sequentially and are detailed in what follows:

• Aggregated Criteria Computation this module stores the impact of successive applications of a crossover operator on the desired criteria: in our contribution, these criteria are the variation of population quality and diversity, and are computed as the variation of the value of population’s entropy ($\Delta D$) and mean fitness ($\Delta Q$). These values are stored in a sliding window $W_{ij}$ of size T, where i is the operator and j the criterion taken into account. A function $F(\cdot )$ computes the final impact, which could be instantiated to max (to detect outliers) or avg if one wants to register a smooth behaviour (di Tollo et al. 2015). The inputs of this module are the identifier of the last applied operator and the observed variation of each criteria. The output, which is sent to to the Reward Computation module, is a vector containing a scalar value for each criterion; for our experiments, $F(\cdot )$ will be instantiated with $avg(\cdot )$; preliminary experiments showed that the behaviour of the AOS is rather robust with regards to the instantiation of $F(\cdot )$. This module is described in Algorithm 1.

  

• Reward Computation the reward strategy computes a reward for the operator identified by the previous module, and can be implemented by using several functions (Fialho 2010). In our case we have chosen the Compass, method, proposed by Maturana and Saubion (2008), that employs the input from the previous module (a vector) and computes the reward on the basis of an hyper-parameter $\theta \in [0,\pi /2]$, that identifies a search angle in the $\Delta D/\Delta Q$ plane. The value of $\theta$ can be set a priori or computed through a dynamic strategy. Via this module, each operator’s performances are represented in the $\Delta D/\Delta Q$ plane, according to the aggregated impact vector previously computed and associated to an additional vector, that will be used to store the rewards. The main idea is to attribute a reward to each operator by computing the distance between the performance point and the plane defined by $\theta$, as shown in Fig. 1: in this way, $\theta =0$ indicates a scenario that fosters diversity and neglects quality, whilst $\theta =\pi /2$ indicates a scenario in which quality is fostered. Intermediate values indicate a weighted compromise between these two criteria. Algorithm 2 outlines this behaviour.

  

• Credit Assignment the credit amount summarizes the reward obtained by an operator during recent applications: it takes as input the reward of each operator $op_i$ at time t, which is then is stored into a sliding window of size $T'$. Then, the module computes an aggregate reward by specifying an aggregation function $F(\cdot )$ (which could be instantiated to $max(\cdot )$ or $avg(\cdot )$ over the period $T'$). These aggregated values represent the credit, i.e., the output of the module sent to Operator Selection.

  

• Operator Selection this module receives as input the credits of all operators and determines the next crossover operator to be applied by the solver, according to a predefined selection scheme. The input of the operator selection module is the credit estimate ${\mathcal {U}}_i$, while the output is the identifier $op_{next}$, which is sent to the EA. In our experiments we have performed operator selection by using Probability Matching (PM), as outlined by Algorithm 4; for a summary of other selection methods, we forward the reader to Maturana et al. (2009), Lardeux et al. (2006), and Maturana et al. (2010).

  

Fig. 1

Reward computation based on a compass method, adapted from Maturana et al. (2010) and di Tollo et al. (2015)

In order to determine the value of $\theta$, we have implemented the framework devised by di Tollo et al. (2015), that uses four high-level dynamic strategies:

• 1. Increasing this strategy splits the number of iterations into n epochs and increases $\theta$ value in equally spaced steps in $[0,\pi /2]$;

• 2. Decreasing this strategy splits the number of iterations into n epochs and decreases $\theta$ value in equally spaced steps in $[0,\pi /2]$;

• 3. Always moving this strategy splits the number of iterations into n epochs and alternates $\theta \in \{0,\pi /2\}$ in equally spaced steps;

• 4. Reactive moving this strategy sets $\theta =0$ if $\frac{\Delta D(P,t)}{D(P,t-1)}<1e-01$, else if $\frac{\Delta Q(P,t)}{Q(P,t-1)}<1e-01$, set $\theta =\pi /2$, where Q(P, t) and D(P, t) denote respectively the mean fitness and the entropy of population P at time t. Otherwise, if neither conditions are satisfied, $\theta =0$.

Note that strategies 1), 2), and 3) define a deterministic schedule, whereas reactive moving is adaptive: the schedule induces an increase in population entropy when the search procedure is stagnating in a local minimum, by selecting exploration operators for the next operations. These strategies will be used in our computational experiments in Sect. 5.

5 Computational experiments

In this section we describe the computational experiments aimed to optimize the portfolios with regards to specific risk measures, and to evaluate the performance of the crossover operators detailed in Sect. 2. After detailing our experimental setting in Sect. 5.1, we will evaluate the behaviour of each crossover operator in Sect. 5.2, in order to understand the specific features of each crossover operator (if any) and to assess whether each operator is more inclined towards exploration or exploitation; then we perform experiments by pooling all crossover operators together in Sect. 5.3, in order to assess the benefits of Adaptive Operator Selection (AOS), which is supposed to direct the search towards the desired direction, by selecting the optimal operator for the next iteration. Finally, in Sect. 5.4 we perform an out-of-sample test, in order to evaluate future performances of portfolios obtained in Sect. 5.3, and to assess eventual benefits over plain GAs equipped with a single crossover operator.

5.1 Our data and experimental settings

We have defined our formulations imposing budget, short-selling, cardinality, floor and ceiling constraints. We have tackled five sets of data, relative to daily closing prices of assets from different stock exchanges indices, over a period of 5 years from 01/01/2009 to 01/01/2014. The summary of our sets of data is reported on Table 1.

Table 1 The sets of data used in our experimental phase

We recall that the solution of the portfolio selection problem (PSP) is given by a vector of n variables $x_1,\dots ,x_n$, where each $x_i$ represents a fraction of the amount invested in asset i. In what follows, we deal with the above mentioned constraints with the following general formulation of a mixed-integer portfolio selection problem, which has been proven to be NP-Hard (Moral-Escudero et al. 2006), for which evolutionary approaches seem particularly suitable:

$$\begin{aligned} \begin{aligned} \min _{{\textbf{x}}}&\quad \phi \mathbf {(x})\\ \text {s.t.}&\quad \sum _{i=1}^{n}x_i=1\\&x_i\ge 0 \qquad \qquad \quad i=1,\dots ,n\\&\sum _{i=1}^{n}\delta _i=K \\&\delta _il_i\le x_i\le \delta _iu_i \quad i=1,\dots ,n\\&\delta _i\in \{0,1\} \qquad \quad i=1,\dots ,n\\ \end{aligned} \end{aligned}$$

(32)

where $\phi ({\textbf{x}})$ is a generic objective function, $\delta _i\in \{0,1\}$ represent n integrality constraints, namely $\delta _i$ is a binary variable to include or exclude asset i in the portfolio; moreover, with $\delta _il_i\le x_i\le \delta _iu_i$ we impose n floor and ceiling constraints (respectively, $l_i$ and $u_i$) and with $\sum _{i=1}^{n}\delta _i=K$ we denote the cardinality constraint, i.e. we impose that exactly k active position are chosen from the market index. Finally with $x_i\ge 0$ we denote the no-short selling constraint and with $\sum _{i=1}^{n}x_i=1$ we ensure that the whole capital is invested in the portfolio.

In what follows, we adopt the penalty approach of Fletcher (2013) and Corazza et al. (2013, 2021), by defining a $\ell _1$ penalty function $C({\textbf{x}},\delta ,\varepsilon )$:

$$\begin{aligned} \begin{aligned} C({\textbf{x}},\mathbf {\delta },\varepsilon )=&\,\phi ({\textbf{x}})+\dfrac{1}{\varepsilon }\Bigg [\Big \vert \sum _{i=1}^{N}x_i-1\Big \vert +\max \Big \{0,\sum _{i=1}^N \delta _i-K\Big \}+\sum _{i=1}^N\max \{0,\delta _il_i-x_i\}\\&+\sum _{i=1}^N\max \{0,x_i-\delta _iu_i\}+\sum _{i=1}^{N}\Big \vert \delta _i(1-\delta _i)\Big \vert \Bigg ] \end{aligned} \end{aligned}$$

(33)

With $\varepsilon$ denoting a penalty parameter. Finally, our $\ell _1$ penalty problem is:

$$\begin{aligned} \min _{{\textbf{x}}\in {\mathbb {R}}^N,\mathbf {\delta }\in {\mathbb {R}}^N} C({\textbf{x}},\mathbf {\delta },\varepsilon ) \end{aligned}$$

(34)

We have defined six different sets of experiments based on optimizing six different risk measures, that are outlined in Table 2, along with the corresponding cost functions⁴.

Table 2 Cost functions used in our experimental phase

We have set $\lambda =0.5$ for the Mean-Variance risk measure. Moreover, for the Two-sided risk measure of Chen and Wang (2008) we use $a=0.5$ and $p=2$, while for VaR we consider a monthly probability of losses exceeding the $VaR_{(1-\beta )}$ threshold $\beta =0.05$.

Two performance criteria have been defined to evaluate the GAs’ performances: the first is the average fitness of the population, defined as $fitness(P)=\dfrac{\sum _{ind\in P}eval(ind)}{\vert P\vert }$, where eval(ind) denotes the individual fitness; the second is the population entropy, defined as $entropy(P)=\dfrac{-\sum _{i=1}^{n}\sum _{j=0}^{k}\frac{n_{ij}}{\vert P\vert }log\frac{n_{ij}}{\vert P\vert }}{nlog2}$, where n is the number of individuals in the population and k is the number of genes for each individual. For these experiments, we set $P=50$, while the number of generations g is set to 1000. Finally, we consider the set of twenty crossover operators defined in Sect. 3.

All algorithms have been implemented in Python and run on a Intel Core i7 2.4 GHz processor, with 8 GB RAM. In what follows we evaluate the crossover performances, first by using each crossover as a stand-alone operator in Sect. 5.2; then, we evaluate our Adaptive Operator Selection in Sect. 5.3.

5.2 Single operators’ results

In the following experiments, the main idea is to isolate the influence of the optimization process in the assessment of the performance of each recombination operator. In the first group of tests, the crossover operator has the goal of retaining a significant amount of diversity, reaching simultaneously a near-optimal level of fitness. In the second group of tests, instead, the behaviour of each operator is assessed when neither selection nor mutation is allowed: the population generated with recombination is sent to the following generation as it is, so that the behaviour of each crossover strategy is singled out.

As a general rule, the crossover operator should strike a balance between quality and entropy, i.e. it is supposed to offset the impact of the selection operator by retaining a reasonable amount of variance while the optimization process is ongoing. Furthermore, as noted by di Tollo et al. (2015) and Maturana et al. (2010), the correlation of the absolute value of fitness and entropy should be generally low; ideally, an operator should be able to increase entropy when the search is stuck in local optima, displaying a self-adaptive behaviour. It is well known that these two factors are strongly related (Arabas et al. 1994): a too strong selective pressure may lead to early convergence towards a suboptimal solution, while a weak selective pressure makes the search ineffective. As noted by Maturana et al. (2010), it is difficult to reach such a balance over all phases of the search, and this is precisely the reason that led us to implement an AOS controller, in order to select the right operator w.r.t. the wished compromise between quality and diversification at each search step. This will be discussed in Sect. 5.3.

In what follows, we analyse the behaviour of different operators during the optimization phase. Further comments on the in-sample performance and a comparison between standard GAs and the adaptive GA are available in Sect. 5.3.

Fig. 2

Single operator performances with respect to quality and diversity. In each panel the average fitness and the entropy over the iterations is reported. The red line indicates the entropy level and the blue line indicates the fitness level. In this set of plots we report results w.r.t. a VaR-optimal portfolio, fitted on a Nikkei 225 dataset (colour figure online)

Figure 2 shows the convergence of the average fitness of the population and its entropy for different configurations of the genetic algorithm. Let us mention a few intriguing facts with respect to the results of the simulation. Note that operators belonging to the family of self-adaptive crossovers display some very promising features. For example, note that the [SBX] crossover (and to a certain extent, also the [LX] crossover) manage to reduce quickly the entropy, with a considerable and fast improvement observed in the average fitness. Furthermore, when improvements become harder, the operator turns to exploration. Both [SBX] and [LX] crossover are able to increase the diversity of the population and to improve its fitness at the same time, especially in the latter stages of the search.

All the operators that by construction are designed to use fitness information ([QBX], [LNX], [DBX], [SPX]) tend to give up some diversification in order to generate fitter individuals, converging steadily to an approximated solution, due to the fact that, by design, the search region is restricted to a very limited area. An efficient crossover should instead ensure a good trade-off between quality and entropy (Lardeux et al. 2006), preventing the population from getting stuck in local optima.

Fig. 3

Single operator performances with respect to quality and diversity. In each panel the average fitness and the entropy over the iterations is reported. The red line indicates the entropy level and the blue line indicates the fitness level. The optimization process is carried out by a GA without the selection operator. In this set of plots we report results w.r.t. a CVaR-optimal portfolio, fitted on a Nikkei 225 dataset (colour figure online)

In Fig. 3 we report the behaviour of a subset of operators with respect to quality and diversity. Some standard recombination operators do not yield any substantial variation ([OPX], [QBX], [AX], [GX], [HX], [AVX], [BLX], [FX], [GUX]) both in fitness and entropy, others induce just slight variation ([UX], [TPX]), whereas some self-adaptive operators ([LX], [SBX], [PNX]), as shown in Fig. 3 lean towards an explorative behaviour. Finally, the [SPX] operator tends to generate fitter individuals, as by construction it exploits fitness information in the mating process.

To recap, in this section we have proposed to test a broad range of crossover strategies for portfolio selection problems: among them, we have chosen both crossovers already in use for evolutionary-based portfolio selection and crossovers for which we have not found any financial application in the literature. Among the latter operators, let us remark again that the performance of crossovers with self-adaptive features ([LX], [SBX], [PNX], [UNDX]) stands out in our investigation: by introducing effective and flexible crossovers, which cope better with different fitness landscapes in the context of portfolio selection, we address the problem of finding high-quality solutions rapidly and in a robust way. We have not found also any financial application for other non-self-adaptive operators, i.e. [HX], [GX], [QBX] and [DBX], which behave similarly to crossovers already in use in the literature, whereas the simplex crossover [SPX] is particularly efficient at finding good solutions.

5.3 Adaptive operator selection results

In this section we report the performance of the GA that resorts to AOS for operator selection, and we compare it with GAs with standard crossover operator. We also propose to evaluate the operator selection frequency for different search policies, in order to test whether the controller is able to affect indirectly fitness and entropy levels, by picking appropriate operators, which in turn should impact the exploitation or exploitation capabilities of the solver. Furthermore, we assess whether the search direction is consistent with the predefined high-level search policies described in Sect. 4. Eventually, we check the quality of the final solutions and the ability of the controller of managing efficiently an optimal quality/diversity tradeoff.

Figures 4, 5, 6 and 7 present four panels, including:

• The operators’ frequency of application (top panel), needed to check whether the controller is able to discriminate operators according to different EvE tradeoffs;

• The level of population entropy over time;

• The value of the hyperparameter $\theta \in [0,\frac{\pi }{2}]$, that defines the dynamic policy guiding the search, according to the predefined (or adaptive schedule) described in Sect. 4.

• The levels of individual fitness over time (bottom panel).

As a first remark, we note that mild improvements of diversity during the search are generally triggered by a variation of the search angle in the range $[0,\pi /2]$; this also generates an immediate variation of cost for some individuals for a few generations. We also note that operators based on exploration are usually selected when small or no improvements are possible; a changing value of the angle generally leads to a non negligible impact on selection probabilities and consequently on performance. In particular, note that [LX], [SBX] and [PNX] operators provide a good trade-off of exploration and exploitation; therefore, especially at advanced stages of search, they seem to be more effective when small or no improvements are possible. Some preliminary experiments show that the probability of selection of these exploration operators turns out to be very high whenever the solver is stagnating, so that the controller turns to exploration, by rewarding them. The selection probability of all mildly relevant operators instead tends to fall to smaller values towards later stages of the process, close to the lower bound $p_{min}=0.01$ established before running the process, with most of the selection frequency concentrated at initial or intermediate stages of search.

Fig. 4

Experiments with the AOS: portfolios are fitted to the Nikkei dataset. From top to bottom: histogram of the operator frequency of application (1), the entropy convergence curve (2), the always moving driving the search process (3), the individual cost scatter plot (4)

Fig. 5

Experiments with the AOS: portfolios are fitted to the CAC 40 dataset. From top to bottom: histogram of the operator frequency of application (1), the entropy convergence curve (2), the reactive policy driving the search process (3), the individual cost scatter plot (4)

Fig. 6

Experiments with the AOS: portfolios are fitted to the Hang Seng dataset. From top to bottom: histogram of the operator frequency of application (1), the entropy convergence curve (2), the always moving policy driving the search process (3), the individual cost scatter plot (4)

Fig. 7

Experiments with the AOS: portfolios are fitted to the Hang Seng dataset. From top to bottom: histogram of the operator frequency of application (1), the entropy convergence curve (2), the reactive moving policy driving the search process (3), the individual cost scatter plot (4)

As a general remark, we can say that none of the introduced search policies outperforms the others: Always Moving and Reactive policy, that led to the best results in di Tollo et al. (2015), perform similarly on our problem instances. Anyhow, we also stress the robustness of the Reactive policy (Fig. 7), whose behaviour is less predictable than standard search strategies, but whose action typically succeeds in increasing the population diversity when entropy is stagnating.

In Table 3 we report the best in-sample value of the objective function obtained with a GA solver equipped with a standard operator crossover or with the controller (in bold). The solutions are reported for just one problem instance, across different objective functions.

The solver is allowed to visit infeasible solution during the search process, which comes at the price of higher penalties attributed to the cost function due to constraint violation. We remark that the Adaptive Operator Selection strategy has proven to be an effective approach when dealing with a variety of optimization problems. The GA equipped with AOS shows results that outperform the majority of the single-crossover based runs. Some operators still perform better than our AOS, but this is due to the computational time required to learn, which has to be taken into account when devising an adaptive procedure: our goal is to devise a tool that shows good performances without a-priori knowledge of the used crossovers and of the instance at hand, and to this extent, our approach is satisfactory.

Indeed, as we show in Table 3, the adaptive strategy is regularly among the top performers, whereas the results from single crossover-based genetic algorithms are less homogeneous across different risk measures, with some performing very poorly in a few cases (see in particular the ‘ERC’ column); note also that the genetic algorithm equipped with the controller is the best performing strategy for CVaR portfolio construction. Let us also mention some exceptions: the [SPX]-based genetic algorithm provide solutions that are far from optimal, whereas the quality of solutions generated by genetic algorithms equipped with [BLX], [HX] and [GUX] crossovers are generally above average. Altogether, we find that no operator can systematically outperform the others: when taking into account single-crossover genetic algorithms, the distinction between exploration and exploitation crossovers in terms of performance is less apparent.

Table 3 Best in-sample solutions

5.4 Out-of-sample performance of rebalanced portfolios

In this section we evaluate the out-of-sample performance of the adaptive policy by computing four performance criteria, namely the annualized portfolio returns, the annualized standard deviation, the out-of-sample Sharpe Ratio and the turnover (see the set of Eq. 35). These four metrics are accessible to a wide audience, which makes them popular among practitioners, despite some well-known shortcomings (Biglova et al. 2004). These four criteria are also extensively used in the literature (DeMiguel et al. 2009), with the purpose of getting a first impression of the out-of-sample portfolio performance.

The performances of the adaptive strategy are compared with a set of genetic algorithms, each equipped with one of the twenty crossover operators presented in Sect. 3.

The main objective of this set of experiments is to extend our investigation on the benefits of the adaptive approach to practical portfolio management issues, by evaluating its performance across different out-of-sample performance metrics, objective functions and over different sets of data: an assessment of the out-of-sample performance is therefore crucial to validate the model from an asset management point of view, but also to deal with potential concerns about overfitting, which might be caused by the model being too strictly tailored to the features of the training data and generalizing poorly to new data.

In order to do this, we implement a rolling-window backtest for each strategy, which is applied to the adaptive model and to the set of twenty genetic algorithms as well. We describe below the structure of our backtests, which largely follows the moving-window backtest proposed in Gilli et al. (2011) for portfolio selection. The model is fitted on training data at time $t_1$ from $t_1-\tau$; for this set of tests, we set the window $\tau$ equal to 2 years (about 500 data points). The portfolio is held for $F=125$ days, i.e. until $t_2=t_1+F$. Therefore, the portfolio is trained on new data starting from $t_2-\tau$ until $t_2-1$ and held for 125 more days, i.e. $t_3=t_2+F$. With T we denote the total number of returns in the dataset, while with ${\mathcal {I}}$ we denote the number of holding periods of each rebalanced portfolio.

$$\begin{aligned} \begin{aligned} {\widehat{\mu }}^i&=\dfrac{1}{{\mathcal {I}}F}\sum _{j=1}^{{\mathcal {I}}}\sum _{k=1}^{F}x^{i^T}_{t_j}r_{t_j+k}^i{} & {} \text {average daily out-of-sample returns}\\ {\widehat{\sigma }}^i&=\sqrt{\dfrac{1}{{\mathcal {I}}F-1}\sum _{j=1}^{{\mathcal {I}}}\sum _{k=1}^{F}\Bigg (x^{i^T}_{t_j}r_{t_j+k}^i-{\widehat{\mu }}^i\Bigg )^2}{} & {} \text {daily out-of-sample standard deviation}\\ \widehat{SR^i}&=\dfrac{{\widehat{\mu }}^i}{{\widehat{\sigma }}^i}{} & {} \text {out-of-sample Sharpe Ratio}\\ \widehat{{\mathcal {T}}}^i&=\dfrac{1}{{\mathcal {I}}-1}\sum _{j=1}^{{\mathcal {I}}-1}\sum _{k=1}^{N}\Bigg (\Big \vert x_{k,t_{j+1}}^i-x_{k,t_{j}}^i\Big \vert \Bigg ){} & {} \text {turnover} \end{aligned} \end{aligned}$$

(35)

The out-of sample tests are performed for various combinations of objective functions and problem instances. The out-of-sample performance statistics for portfolios constructed with assets from Nikkei 225 are reported in Table 4; the results are shown for Omega Ratio-optimal portfolios for two different cardinality constraints. In order to test the hypothesis that the Sharpe Ratios and the variances of the competing strategies are equal (DeMiguel et al. 2009) (that is $H_0:\frac{\mu _{i}}{\sigma _{i}}-\frac{\mu _i}{\mu _n}=0$ and $H_0:\sigma _{i}-\sigma _{n}=0$ respectively, where i is one of the twenty portfolios construct a standard methodology and n always denotes the adaptive strategy) we use bootstrapping methods, which are suitable when portfolio returns are not independently and identically distributed. In particular, since we deal with time series data, we follow the approach of Ledoit and Wolf (2008, 2011) to generate bootstrap data and we use the circular block bootstrap (Politis and Romano 1991) and the stationary bootstrap (Politis and Romano 1994) to carry out pairwise tests of equality of the portfolio Sharpe ratios and variances, respectively. Please notice that standard tools such as the Jobson and Korkie (1981) test for the equality of Sharpe Ratios or the F-test for the equality of variances assume that the data come from a bivariate normal distribution and are dependent over time. However, these tests are not valid if the returns are correlated, have heavy tails or are dependent over time: since financial data generally violate at least one of these conditions, a different approach should be pursued, hence we compute a two-sided p value using the time series bootstrap confidence interval for the difference of the Sharpe ratios and variances, to declare the two are different if zero is not contained in the obtained interval, following the procedure described in Ledoit and Wolf (2008) and Ledoit and Wolf (2011), with $B=5000$ bootstrap resamples and a block size equal to $b = 5$.

Table 4 suggests that the best annualized Sharpe Ratio is obtained for $K=10$; on average we observe larger values of the Sharpe Ratio for portfolios with a smaller number of assets, suggesting that some ‘rough’ regularization approaches, involving the number of holdings or the inclusion of weight constraints (Jagannathan and Ma 2003) are particularly useful for managing overfitting issues, because they reduce the degree of freedom of the optimization process. Note that risk and return are inevitably measured with estimation error: as pointed out by Roncalli (2013), in a dynamic framework (e.g. for semiannually-rebalanced portfolios) estimation errors have a dramatic impact on turnover, with a significant impact on the stability of solutions. Furthermore, we empirically observe that the portfolios constructed with stricter cardinality constraints are slightly more volatile. Finally, we check whether the variance and the Sharpe Ratio for a specific strategy are statistically different from that for the adaptive portfolio, and for this purpose we have implemented the tests introduced by Ledoit and Wolf (2008, 2011). The p values are reported in parentheses in Table 4 (recall that we want to test the null of equality of the Sharpe ratios and variances of the two portfolios being compared, hence the null hypothesis is rejected when the p values are at least lower than the $10\%$ level): it is possible to see that the variances and the Sharpe Ratios of the adaptive model with the constraint $K=10$ record a high number of rejections. In particular, the differences are statistically significant at the $5\%$ level for, respectively, nine and eight portfolios out of twenty, whereas a smaller, yet non-negligible number of significant differences is observed when considering a less strict cardinality constraint.

As far as the crossover performance is involved, the genetic algorithm resorting to the adaptive approach behaves well on average, with some single crossover-based genetic algorithms performing occasionally better, though. Our adaptive strategy is however more robust across different risk measures and problem instances, as we also show in Fig. 8. Among standard genetic algorithms, let us highlight the fact that neither those equipped with exploration crossovers nor those employing exploitation crossovers outperform the others: note indeed that for $K=10$ the best Sharpe Ratio is achieved by [GUX] and [BLX] (respectively, ${\widehat{SR}}^{GUX}=1.1401$ and ${\widehat{SR}}^{BLX}=1.0938$); however, these two operators do not share any specific features (the former is more oriented towards exploitation, the latter towards exploration, see Sect. 3). Moreover, for $K=20$ [QBX] and [AX] outperform the rest of the operators, though not by a wide margin.

Table 4 The table reports the average returns ($\widehat{\mu ^i}$), the standard deviation ($\widehat{\sigma _i}$), the Sharpe ratio ($\widehat{SR^i}$), and the turnover $\widehat{{\mathcal {T}}}$ computed on the out-of-sample returns

Fig. 8

Rolling-window backtest of the adaptive strategy on Nikkei 225 index, with $K=10$, $l_i=0.05$ and $u_i=0.15$

Altogether, an inspection of the results point to the fact that operators are generally unable to stand out consistently from the rest, which might suggest that combining operators at different stages of the search process could be actually beneficial for the solver. Furthermore, the AOS-based genetic algorithm is stably among top five performers across different risk measures and problem instances, signalling that this approach is rather effective at producing consistent and robust results across various formulations of the optimization problem. Further unreported results show that the best annualized Sharpe Ratio is achieved with a two-sided risk measure across different problem instances. Mean-variance portfolios perform poorly, with some portfolios constructed from a subset of the FTSE MIB displaying even a negative Sharpe Ratio.

For what concerns transaction costs, as shown in Table 4, there are no outperforming strategies in terms of turnover: the impact of regular portfolio rebalancing is overall homogeneous across different genetic algorithms, as we do not find any strategy regularly generating less costs. For instance, note that the turnover of [AVX] and [PNX] is definitely low compared to other single crossover-based GAs; however, when turning to portfolio with $K=20$ assets, both are among the worst strategies in terms of trading costs.

Now consider a final example w.r.t. Nikkei 225 index. In Fig. 8 we present six different panels, in which both standard and adaptive strategies are backtested across different risk measures; rather than resorting to capitalization-weighted indices, we use as benchmarks the cumulative out-of-sample returns series optimized with standard genetic algorithms, which we construct with the crossover operators discussed in Sect. 3. In this set of backtests, the adaptive policy definitely performs better compared to alternative optimizers; also in terms of risk/reward tradeoff (Table 4), a small but consistent outperformance of the adaptive strategy stands out.

6 Conclusions

In this contribution we have applied an Adaptive Operator Selection (AOS) to Evolutionary Algorithms (EA) to solve Portfolio Selection Problems. First, we have identified all the crossover operators devised by the related literature regarding optimal portfolio choices; then, we have used AOS to decide which operator to use at each step of the search process, depending on several strategies.

We have seen that the introduction of AOS makes the genetic algorithm outperform the majority of the single crossover-based ones. This is due to the fact that the AOS decides, for each step of the search process, the right operator to be used with respect to the desired Exploration vs Exploitation balance: in our approach this balance can be either set by a deterministic strategy, or by an adaptive procedure that reacts to changes of the population’s quality and diversity.

The genetic algorithm resorting to AOS show good performances over all instances taken into account. We have remarked that the genetic algorithm that relies on some specific single operators perform better than our AOS in some specific instances. This is due to the fact that AOS requires computational time to learn the features of the crossover operator, hence subtracting computational time to the optimization phase itself. Single crossover-based GAs instead, do not suffer from this shortcoming. Of course, we would obtain better results by our AOS if we would run the algorithm for longer search epochs, but this is out of the scope of the current contribution: our goal is to devise a tool that show good performances without a-priori knowledge of the used crossovers and of the instance at hand, and to this extent, our approach shows good performances.

We can conclude by saying that the use of AOS improves the performances with regards to EAs that use single operators, which are the most used approaches in portfolio selection, no matter the objective function used, and over different sets of data coming from different countries and from different financial scenarios. Up to the authors’ knowledge, this is the first contribution attempting to devise an approach based on all previous GA approaches for Portfolio Selection.

Moreover, we also contribute to the literature by investigating the benefits of introducing a broad range of operators for which we have not found any application to EA-based portfolio optimization: indeed, we shed light on the performance of crossovers as stand-alone operators and we find that the self-adaptive ones are able to achieve the best exploration–exploitation tradeoff, as pointed out by experiments showing both a promising behaviour and also a significantly high selection frequency.

Further work will be devoted to devise strategies that take into account external constraints and data-features. To this regard, we want to create specific variation operators that define, over the search, the investor preferences, in order to identify search spaces that corresponds to portfolios meeting the investor’s preferences. Furthermore, we want to devise operators that test some of the features of the benchmark, in order to verify the investor’s preferences, and to produce customized investment signals, i.e., to stay away from the market, or to enter into the market. Finally, a natural extension of our model should include further real-world constraints, e.g. by incorporating a restriction on tracking-error volatility or by defining a minimum lot size, so as to further challenge its capabilities in tackling an even more complex and realistic search space.