Set-Based Particle Swarm Optimisation: A Review

In the original PSO, particles “move” through an $n_x$-dimensional real-valued space. The movement of particles is dictated by the attraction to different areas in the landscape, which determines the momentum and direction of the particles. However, the idea of direction and momentum is undefined in a set-based environment and the absence necessitates the development of set-based analogies of, and alternatives to, momentum and direction.

For SBPSO, the symbol i indicates the particle index, t denotes the current iteration, and f represents the objective function. The search space is defined by the universal set (the universe of discourse), U. The universal set is of size $n_U$ and contains elements $e_n$; the universal set is expressed as $U={\left\{e_n\right\}}_{n\in N_U}$. Position sets are subsets of the universal set, alternatively stated; position sets are elements of the power set of the universal set. The position of particle i at iteration t is expressed as $X_i\left(t\right)\subseteq U$. The velocity of particle i at iteration t is the set $V_i\left(t\right)$. The personal best and neighbourhood best positions of particle i are $Y_i\left(t\right)$ and ${\hat{Y}}_i\left(t\right)$, respectively.

Continuous-valued PSOs modify position vectors by modifying the real values in each dimension of the position with the real values in the corresponding dimension of the velocity vector. The change of the real-valued components brings the position vector closer to the positions defined by the attractors. However, “moving” a set-based position closer to the attractor positions with real-valued velocity components is not definable. Instead, the velocity set adds and removes position set elements to make the position more similar to the attractors. The concept of “alikeness”/similarity is well-defined for sets and has been studied in the context of set-based meta-heuristics [68].

In order to change a position set, the elements of a velocity set are applied to the position set. Each element of a velocity set is an operation pair: a tuple consisting of an element from the universal set and the instruction indicating whether the universal set element should be added to, or removed from, a position set. Velocity set elements take the form $(\pm ,e)$, where $(+,e)$ adds the element e to a position set while $(-,e)$ removes e from a position set. Consider the following example as a demonstration of the application of a velocity set to a position set. If $X=\{a,c\}$ is a position set and $V=\left\{\right(+,b),(-,c\left)\right\}$ is a velocity set, the resulting position after applying V to X is $X^{\prime }=\{a,b\}$.

In order to define the necessary SBPSO operators, let $\mathcal{P}\left(U\right)$ denote the power set of the universal set (meaning the set of all possible subsets) and let $A\times B$ denote the Cartesian product of two sets, A and B. The following definitions are set-based operators used in the SBPSO algorithm.

This section provides the mathematical definition of the MKP. Given an MKP, the combined value of the items placed into the knapsack is calculated as subject to the zero-one constraints where $x_i$ indicates if item i is in the knapsack. MKP is also subject to weight constraints The number of available items to add to the knapsack is $n_i$. The total number of weight constraints in the problem is $n_c$. The weight of each constraint, j, on each item, i, is given by $w_{i,j}$. The total weight of the items placed in the knapsack for constraint j must also not exceed the capacity of the constraint, $C_j$. MKP is also subject to value constraints The total weights of the MKP have the constraints where $C_j$ is defined as and $r_j$ is the “tightness ratio”, which determines how restrictive the weight constraints are.

Because the MKP requires an unknown number of items to be placed into a knapsack, a set-based representation of the candidate solutions is well suited. The suitability of a set-based representation is in contrast to other meta-heuristics, such as the PSO, which requires a fixed-length representation of candidate solutions, i.e., prior knowledge regarding the maximum dimension of the solution.

The universal set is generated to contain all possible items which can be added to the knapsack. The elements of U are represented as tuples which contain the details of an item. Each item has an index, i, a value, $v_i$, and $n_c$ weights. Each weight, $w_{i,j}$, corresponds to the cost of item i on constraint j. An element in U therefore takes the form $(i,v_i,(w_{i,1},\dots ,w_{i,n_c}))$. An example of a hypothetical universal set for an MKP with five items and three constraints is

The objective function of the SBPSO used on the MKP optimises MKP as a maximisation problem. It is important to note that not all particle positions necessarily represent feasible solutions, hence the objective function is piecewise defined. The objective function value for positions which satisfy all $n_c$ constraints is equal to the sum of all the values of the items in the position, while positions which violate at least one constraint are assigned a value of negative infinity. The objective function, f, is

The SBPSO performs well on the MKP, but Langeveld and Engelbrecht note that state-of-the-art MKP algorithms perform better. However, the MKP was merely used as a proof-of-concept for SBPSO. Considering that the work of Langeveld and Engelbrecht was used to introduce SBPSO, the approach from the paper is quite successful given that SBPSO does not require any domain-specific knowledge to solve the MKP.

The FSP is defined in this section as a precursor to the application of SBPSO to FSP. Given a dataset with the set of input features I of size $n_x$, define $\mathcal{P}\left(I\right)$ be the power set of I, i.e., the set containing all possible subsets of I. For a generic subset of I, denoted as $X\in \mathcal{P}\left(I\right)$, let the fitness of X be defined as $f\left(X\right)$. The fitness function, f, is a predefined minimisation or maximisation function which quantifies how well a subset of features solves an optimisation problem. Given an assumed a minimisation fitness function, the optimal solution set, X, is defined as

In order to determine how effectively the subset of features, S, captures the relationships of the underlying classification problem, the performance of a classifier (with relevance to a classification problem) is used. The performance of the classifier is measured using an evaluation metric, such as accuracy. To illustrate how the suitability of a selected subset of features can be evaluated, consider that a decision tree classifier is used to determine the fitness of a subset of features. Given two different subsets of features, $S_1$ and $S_2$, the decision tree classifier achieves a performance on the two subsets. Let the accuracies be $A\left(S_1\right)=83.1\%$ and $A\left(S_2\right)=68.4\%$. These scores show that $S_1$ is a better subset of features.

The feature selection problem can be solved with SBPSO, as shown by Engelbrecht et al. [87]. SBPSO is an apt approach to FSP because the feature subsets, $S\in \mathcal{P}\left(I\right)$, are easily represented as set-based particles.

The universal set contains all possible combinations of input attributes, i.e., all possibilities of $S\in \mathcal{P}\left(I\right)$. For a hypothetical dataset with four input attributes ($a_1$, $a_2$, $a_3$ and $a_4$), the generated universal set is Further, the power set of the generated universal set is

The fitness function is where $\Lambda (t_p,f_p,f_n,t_n)$ is a performance evaluation metric which, for classification problems, quantifies the confusion matrix into a single real value. The input parameters of $\Lambda$ are the measures from the confusion matrix: $t_p$ is the number of true positives, $f_p$ is the number of false positives, $f_n$ is the number of false negatives, and $t_n$ is the number of true negatives.

The approach used to apply SBPSO to the FSP involves creating an SBPSO wrapper method to evaluate the suitability of features. The method for SBPSO for FSP is very similar to the method outlined in Algorithm 3. The main difference is that the fitness function is the evaluation function of a classifier, $f_{C^{\prime }}$, instead of the standard objective function, f.

Engelbrecht et al. compare the SBPSO for feature selection against three state-of-the-art discrete PSO algorithms (binary PSO, catfish binary PSO, and probability binary PSO). SBPSO in conjunction with a k-nearest neighbours classifier outperforms all three state-of-the-art algorithms with statistical significance and is considered the most effective tool for the FSP.

Portfolio optimisation requires a mathematical description of the behaviour of the assets in the compiled portfolio in order to define the problem. A popularly used portfolio model, the mean-variance model [88], is defined as where $\lambda \in [0,1]$ is used to balance the risk, $\overline{\sigma }$, and return, R, of the portfolio. The risk of a portfolio is calculated as the weighted covariance between all $n_a$ assets, the formula used is where $w_i$ and $w_j$ are the weights assigned to assets i and j, respectively, and ${\sigma }_{ij}$ is the covariance between assets i and j. Further, the return of a portfolio is calculated as where $R_i$ is the return associated with asset i. All weights assigned to assets must be non-negative and must sum to one, i.e., and

The definition of the portfolio optimisation model optimised by SBPSO can be varied. These variations include the addition of constraints, the extension of portfolio optimisation as a MOOP, and the use of alternative definitions for risk and return. Constraints are added to the portfolio optimisation formulation such as, for example, the limitation of the total number of assets, the addition of a floor and ceiling to the asset weights, the incorporation of transaction costs, or the inclusion of capitalisation into the model. A multi-objective formulation of portfolio optimisation is obtained through the incorporation of more than one sub-objective in the objective function or by the use of constraints as stand-alone objectives. A multi-objective formulation can, for example, consist of the maximisation of return, the maximisation of the diversity of included assets, or the maximisation of liquidity. Alternative models of portfolio optimisation can include objectives such as semi-variance, value-at-risk, prospect theory, Sharpe ratio, or mean absolute deviation [89,90,91,92,93,94].

Erwin and Engelbrecht [95] used SBPSO as part of a portfolio optimisation approach to maximise return and minimise risk. The resultant algorithm solved portfolio optimisation by interleaving SBPSO, to select assets, and PSO, to optimise the weights of selected assets. To select an optimal combination of financial products, the PSO algorithm is interleaved with SBPSO into a bi-level optimisation process to find optimal ratios of assets [95]. The two stages of the bi-level optimisation process are solved by SBPSO and PSO. SBPSO selects the assets to be included in the portfolio, after which PSO assigns the optimal weighting to each chosen asset.

The universal set contains all possible assets that can be included in a portfolio. If, for example, a portfolio is to be constructed from the top 10 companies in a hypothetical market (companies A to J), the universal set will be Combinations of these assets are selected and then used as input to the PSO.

The fitness of the SBPSO particle is the global optimum found by the PSO swarm which optimises the weights of the assets selected by the SBPSO particle. The fitness function is defined as the mean-variance model as in Equation (39), i.e., $f\left(X\right)=\lambda \overline{\sigma }-(1-\lambda )R$. The meanings from Equations (40)–(43) are retained.

Erwin and Engelbrecht improved on the original SBPSO-based portfolio optimisation approach by using the MGSBPSO to solve portfolio optimisation as a MOOP [73]. The improved approach uses MGSBPSO to select assets for investment, after which MGPSO is used to find the optimal weight allocations for each selected asset. Both the upper and lower levels of the approach define portfolio optimisation as a MOOP with respect to the maximisation of return and the minimisation of risk.

The new approach uses the same mean-variance model as in Equation (39), but instead of balancing the objectives with $\lambda$, the objective function is redefined as

Because there are two objectives, i.e., maximise return and minimise risk, the populations of both MGSBPSO and MGPSO implement two sub-swarms, one that optimises each objective. For positions in the first sub-swarm of MGSBPSO (which minimises risk) two separate MGPSO sub-swarms are created, one which minimises risk and another which maximises return. Similarly, for the second sub-swarm of MGSBPSO (which maximises return), two separate MGPSO sub-swarms are created, one which minimises risk and another which maximises return. Visually, the structure of the multi-sub-swarm approach is shown in Figure 1.

Erwin and Engelbrecht compared the performance of both SBPSO and MGSBPSO for portfolio optimisation against the non-dominated sorting genetic algorithm II [81] and strength Pareto evolutionary algorithm 2 [96]. In contrast to the comparison algorithms, the SBPSO-based approaches are able to approximate the whole true POF instead of only parts of the true POF. Further, MGSBPSO is able to obtain a diverse set of optimal solutions, which is beneficial to investors who have different risk preferences.

Polynomial approximation is the process by which the structure of a functional mapping from $n_x$ dimensional input data to a real-valued output is found, i.e., $f:{\mathbb{R}}^{n_x}\to \mathbb{R}$. One of the biggest advantages of learning the structure of the polynomial which maps input to output is that the model is transparent. A transparent model has an advantage over an opaque approach in that the results are more interpretable and explainable.

A polynomial is learned from an input dataset, D. The dataset D is $n_x$-dimensional, $D=\left\{({\mathit{x}}_p,y_p)\right|p=1,\dots ,n_N\}$ with $n_N$ instances, where p is a specific instance, ${\mathit{x}}_p=(x_{1p},x_{2p},\dots ,x_{n_{x}p})$ is a vector of input variables, and $y_p$ is the corresponding true output value. A polynomial is constructed from multiple monomials, the building blocks of a polynomial. Monomials take the form where $n_j$ is the power of variable $x_j$. Univariate polynomials have only a single input dimension, and are defined as where $n_l$ is the order of the polynomial. Multivariate polynomials have $n_x>1$ and take the form of where $n_t$ is the number of monomials and $a_t$ is the coefficient of the $t^{\mathrm{th}}$ monomial. Further, $n_q\le n_x$ is the number of input variables in the $t^{\mathrm{th}}$ monomial and ${\lambda }_q$ is the order of the corresponding variable.

Van Zyl and Engelbrecht applied SBPSO as part of a hybrid algorithm which approximates functional mappings [99]. According to [99], polynomial approximation is defined as a MOOP with two objectives. The two objectives are to find (1) the smallest number of terms and lowest polynomial order, and (2) optimal coefficient values for the terms in order to minimise the approximation error. Although polynomial approximation is defined as a MOOP, Van Zyl and Engelbrecht implement a weighted aggregation approach in order to apply the single-objective SBPSO algorithm to polynomial approximation.

The universal set of the SBPSO used to approximate polynomials contains the monomials which can be added to the polynomial. The monomials in the universal set contain combinations of input variables. The combinations of input variables are repeated with different exponents, up to a user-specified polynomial order. The tuples in the universal set contain two components: (1) the input attribute(s) of the monomial and (2) the power of the monomial. A hypothetical dataset, with three input attributes and a specified order of two, will generate the universal set: Equation (48) allows for monomials with different powers for each input variable; however, Van Zyl and Engelbrecht limit the monomials to have the same power for all input variables in order to reduce the universal set size.

The objective function is used to quantify how well a candidate polynomial describes the mapping from input data to output values, as well as how optimal the polynomial structure is. Polynomial approximation is defined as a MOOP, and the objective function is formulated with a weighted aggregation approach. The objective function is where the approximation qualifier is the mean squared error, defined as and the penalty term is defined as the ridge regression function, i.e.,

The SBPSO solves the upper part of the bi-level optimisation process needed to approximate polynomials. Bi-level optimisation processes are separated into an upper-level and lower-level optimisation process [100]. The upper part, where the structure of the polynomial is determined, is solved by SBPSO. The lower part, where the coefficients of the monomials are estimated, is solved by adaptive coordinate descent (ACD) [101]. The interleaved algorithm is presented in Algorithm 6.

Algorithm 6 Set-Based Particle Swarm Optimisation for Polynomial Approximation.

Generate the universal set Create a swarm containing $n_s$ particles Initialise particle positions as random subsets of U Initialise personal best and neighbourhood best values while Stopping condition(s) not true do     for each particle $i=1,\dots ,n_s$ do         Use ACD to find monomial coefficients         Let $f\left(X_i\right)$ be ACD fitness value         if $f\left(X_i\right)<f\left(Y_i\right)$ then            Update personal best: $Y_i=X_i$         end if         if $f\left(Y_i\right)<f\left({\hat{Y}}_i\right)$ then            Update neighbourhood best: ${\hat{Y}}_i=Y_i$         end if     end for     for each particle $i=1,\dots ,n_s$ do         Update particle i’s velocity and position.     end for end while

SBPSO for polynomial approximation is a promising approach to induce accurate and low complexity functions. Van Zyl and Engelbrecht conclude that SBPSO scales better than BPSO for more complex polynomials and maintains the advantage of interpretability over universal approximators such as NN.

In order to train an SVM, instances from a training dataset are used as support vectors to construct the optimal hyperplane. SVMs have been extended to separate non-linear data through the use of techniques such as soft margins [104] and mapping to a higher-dimensional feature space with a kernel “trick” [102,105,106]. Consider a dataset with $n_N$ instances; let each instance consist of an input, ${\mathit{x}}_i\in {\mathbb{R}}^{n_N}$, and a class label, $y_i\in \{-1,1\}$. Provided that the training data is linearly separable, all instances of each class lie on either side of a separating hyperplane. The separating hyperplane has the form $\mathit{w}·\mathit{x}+b=0$, where $\mathit{w}$ is the normal vector to the hyperplane. The decision function used to classify an instance is where f classifies instance ${\mathit{x}}_i$ as either positive ($y_i=+1$) or as negative ($y_i=-1$). Under the assumption of linear separability where ∧ represents the logical and operator and equality holds for at least one ${\mathit{x}}_i$. The input instances for which the equality condition holds are referred to as support vectors and are used to construct the separating hyperplane. The margin of an SVM, which is the combined distance from the hyperplane to the support vectors on either side, is calculated by The maximisation of the margin of a SVM results in an optimal separating hyperplane for that SVM. The maximisation of the margin is equivalent to the optimisation of subject to the constraints outlined in Equation (54).

The introduction of a vector of Lagrange multipliers ($\alpha \in {\mathbb{R}}^{n_N}$) results in the primal Lagrangian, defined as The partial derivative of Equation (57) with respect to $\mathit{w}$ is when the partial derivative is set to zero, the result is Further, the partial derivative of Equation (57) with respect to b is when the partial derivative is set to zero, the result is The partial derivative results in Equations (59) and (61) are substituted into Equation (57) and results in the dual optimisation problem subject to where ∧ represents the logical and operator. Through Equations (53) and (59), $\mathit{w}$ is shown to be a linear combination of all training patterns as Furthermore, it has been shown that only support vectors have non-zero Lagrangian multipliers, i.e., ${\alpha }_i$, which further simplifies the linear combination of $\mathit{w}$.