Soft Actor-Critic Approach to Self-Adaptive Particle Swarm Optimisation

Abstract

Particle swarm optimisation (PSO) is a swarm intelligence algorithm that finds candidate solutions by iteratively updating the positions of particles in a swarm. The decentralised optimisation methodology of PSO is ideally suited to problems with multiple local minima and deceptive fitness landscapes, where traditional gradient-based algorithms fail. PSO performance depends on the use of a suitable control parameter (CP) configuration, which governs the trade-off between exploration and exploitation in the swarm. CPs that ensure good performance are problem-dependent. Unfortunately, CPs tuning is computationally expensive and inefficient. Self-adaptive particle swarm optimisation (SAPSO) algorithms aim to adaptively adjust CPs during the optimisation process to improve performance, ideally while reducing the number of performance-sensitive parameters. This paper proposes a reinforcement learning (RL) approach to SAPSO by utilising a velocity-clamped soft actor-critic (SAC) that autonomously adapts the PSO CPs. The proposed SAC-SAPSO obtains a 50% to 80% improvement in solution quality compared to various baselines, has either one or zero runtime parameters, is time-invariant, and does not result in divergent particles.

1. Introduction

Particle swarm optimisation (PSO), introduced by Kennedy and Eberhart [1], is a swarm intelligence algorithm modelled after the swarming behaviour of birds in a flock. PSO finds candidate solutions by iteratively updating the positions and velocities of particles in a swarm. Position and velocity updates for each particle are calculated using the particle’s momentum, the best position the particle has visited so far, and the best position visited by any particle in that particle’s neighbourhood. PSO is ideally suited to problems with multiple local minima and deceptive fitness landscapes, where traditional gradient-based algorithms fail. PSO performance depends on the use of a suitable control parameter (CP) configuration, which governs the trade-off between exploration and exploitation in the swarm [2,3,4,5]. The CP configuration also determines whether the swarm reaches an equilibrium state or diverges. CPs are problem-dependent, and CP configurations that perform well over a large set of problems may not be suitable for the specific problem at hand [3,6], because the exploration-exploitation trade-off is fitness-landscape dependent. However, tuning CPs for a specific problem is computationally expensive.

Self-adaptive particle swarm optimisation (SAPSO) algorithms aim to adaptively adjust CPs during the optimisation process to improve performance, ideally while reducing the number of performance-sensitive CPs [7]. Recent studies have, however, shown that most SAPSO approaches introduce more parameters to which PSO performance is sensitive than they manage to adapt [7,8]. Most SAPSO approaches also result in divergent behaviour, infeasible solutions, low particle step sizes, and are generally ineffective at attaining better solutions [7,8,9]. Given complex, deceptive optimisation problems, often with rapidly changing landscape characteristics, there is in many cases no basis to assume that what worked up to a certain point will work in the future [10]. If self-adaptation is, therefore, based on behaviour observed up to a certain point during the search, it cannot automatically be inferred that this is indicative of what will work beyond that point. Many attempts also adapt the CP configuration in accordance with the current time-step, making for a time-variant SAPSO algorithm [11]. Time-variant SAPSO is more limited, as it only makes use of the computational budget to inform CP adaptation [12]. Ideally, a time-invariant self-adaptive algorithm should automatically adapt CPs by being fitness-landscape-aware to some extent, and not just depend on the number of time-steps used. Furthermore, particles should neither diverge and leave the feasible search space, nor should they converge prematurely to a local minimum.

Reinforcement learning (RL) is the process through which an agent learns an optimal behavioural policy by trying out actions in an environment, guided by a reward signal [13]. The agent may also receive information in order to know which state the environment is in. An RL agent can, therefore, learn to adjust the CPs of a PSO (action), based on the particle velocities or positions (observation state), guided by the best solution found at the current time-step (reward). The soft actor-critic (SAC) [14] is a specific RL formulation which employs continuous action and state spaces, compatible with the continuous domain of PSO variables, such as particle positions and velocities, and is, therefore, suitable towards dynamic adaptation of PSO CPs during the search process.

The contribution of this study is, therefore, the design and extensive empirical analysis of a truly self-adaptive, RL-based PSO algorithm. The proposed SAC-SAPSO obtains a 50% to 80% improvement in solution quality over relevant performance baselines. The SAC-SAPSO also reduces the number of runtime parameters to either one or zero, is time-invariant, and does not exhibit divergent search behaviour. Finally, whereas RL has been implemented to pre-tune hyperparameters for other heuristics [15,16,17,18], no existing research makes use of RL to dynamically adapt CPs during runtime.

The rest of this paper is structured as follows: Section 2 explains the fundamentals of PSO, RL, SAC, and some existing SAPSO algorithms. Section 3 elaborates on design decisions pertaining to the SAC-SAPSO, and Section 4 relates the experimental procedure followed as well as relevant evaluation metrics. Section 5 demonstrates characteristic search behaviour of SAC-SAPSO and discusses the results obtained, Section 6 summarizes the conclusions drawn, and Section 7 outlines future work.

2. Background

This section explains the PSO algorithm, the importance of CPs, methods such as velocity clamping, SAPSO algorithms proposed in the literature, RL principles, and the SAC algorithm.

2.1. Particle Swarm Optimisation

PSO performs swarm-based search to solve optimisation problems by updating particle velocities and then positions on each time-step, based on the best position a specific particle has found (cognitive component), the best position found by the swarm as a whole (social component), and the previous velocity, or inertia, of the particle [1,19]. The velocity update equation per dimension is given as

$$v_{ij}(t+1)=\omega v_{ij}\left(t\right)+c_1{r_1}_{ij}\left(t\right)\left[y_{ij}\left(t\right)-x_{ij}\left(t\right)\right]+c_2{r_2}_{ij}\left(t\right)\left[{\widehat{y}}_{ij}\left(t\right)-x_{ij}\left(t\right)\right]$$

(1)

where at time t, particle i in dimension j has a velocity of $v_{ij}\left(t\right)$, a position of $x_{ij}\left(t\right)$, a personal best of $y_{ij}\left(t\right)$, and a neighbourhood best of ${\widehat{y}}_j\left(t\right)$. The CPs are $\omega$, $c_1$, and $c_2$ for the inertia weight, cognitive, and social acceleration components, respectively. Sampled uniformly from (0,1), ${r_1}_j$ and ${r_2}_j$ introduce stochasticity into the search. Position updates are subsequently calculated per particle i using

$${\mathbf{x}}_i(t+1)={\mathbf{x}}_i\left(t\right)+{\mathbf{v}}_i(t+1)$$

(2)

where ${\mathbf{v}}_i$ is the velocity vector and ${\mathbf{x}}_i$ is the position vector.

2.2. Control Parameter Configurations

Constant CP values are often selected as $\omega =0.729844$, $c_1=1.496180$ and $c_2=1.496180$ [7,20]. However, successful adjustment of the CPs in order to manage the trade-off between exploration and exploitation improves the success of PSO, due to unexplored regions being explored sufficiently, while not wasting computational effort on evidently non-promising areas of the fitness landscape. Usually, more exploration (high $\omega$, high $c_1$, low $c_2$) is initially desirable, shifting to exploitative behaviour (low $\omega$, low $c_1$, high $c_2$) towards the end of the search. CPs can, therefore, be adjusted in a time-variant fashion using

$$\begin{array}{cc}\hfill \omega \left(t\right)& =0.4{\left({\displaystyle \frac{t-n_t}{n_t}}\right)}^2+0.4\hfill \\ \hfill c_1\left(t\right)& =-3{\displaystyle \frac{t}{n_t}}+3.5\hfill \\ \hfill c_2\left(t\right)& =+3{\displaystyle \frac{t}{n_t}}+0.5\hfill \end{array}$$

(3)

where t is the current time-step and $n_t$ is the maximum number of time-steps (adapted from [21] to satisfy $c_1+c_2>4$ [19]). Similarly to Equation (3), the time-variant acceleration coefficients PSO (PSO-TVAC) [11] also adjusts $c_1$ and $c_2$, but keeps $\omega$ at a fixed value. Time-variant SAPSO algorithms thus adjust CPs as a function of the current time-step and the total computational budget. Time-invariant SAPSO algorithms, however, adjust CPs as a function of the particle swarm’s properties, for example, the average particle velocity, or the rate of improvement in solution quality.

2.3. Convergence Condition

Particles with CPs which adhere to the stability condition [22,23] given by

$$c_1+c_2<{\displaystyle \frac{24\left(1-w^2\right)}{7-5w}}\mathrm{and}w\in [-1,1]$$

(4)

are considered stable, since Equation (4) ensures that the particle swarm will in the limit obtain an equilibrium state of zero velocity. This equilibrium state may, however, take very long to achieve, because the stability condition does not make a claim with regards to the number of iterations required to reach this state [24]. Similarly, velocities may also assume very large values during the search process before the equilibrium state is reached.

2.4. Velocity Clamping

Velocity explosion was first observed by Kennedy and Eberhart [19], and is the phenomenon whereby particle velocities grow unboundedly and sometimes leave the search space without ever returning [9]. Velocity explosion is especially common in high-dimensional search spaces, and can be countered using velocity clamping, which imposes limits on the maximum allowable velocity values by introducing the bound $v_{max}$ [25]. Given a search space with boundaries $\left[\ell ,\mathbf{u}\right]$, velocities can be clamped per dimension by constraining the velocity component in each search dimension j to a fixed value, according to

$$v_{i,j}^{t+1}=\left\{\begin{array}{cc}{v}_{i,j}^{t+1}\hfill & \mathrm{if}-v_{max,j}\le v_{i,j}^{t+1}\le v_{max,j}\hfill \\ v_{max,j}\hfill & \mathrm{if}{v}_{max,j}<v_{i,j}^{t+1}\hfill \\ -v_{max,j}\hfill & \mathrm{if}{v}_{i,j}^{t+1}<-v_{max,j}\hfill \end{array}\right.$$

(5)

for

$$v_{max,j}=\delta \left(u_j-{\ell }_j\right),\delta \in (0,1)$$

(6)

Alternatively, velocity magnitudes can be clamped by setting an upper bound on the magnitude of the velocity vector, i.e.,

$${\mathbf{v}}_i^{t+1}=\left\{\begin{array}{cc}{\mathbf{v}}_i^{t+1}\hfill & \mathrm{if}∥{\mathbf{v}}_i^{t+1}∥<=v_{max}\hfill \\ {\displaystyle \frac{v_{max}}{∥{\mathbf{v}}_i^{t+1}∥}}{\mathbf{v}}_i^{t+1}\hfill & \mathrm{if}∥{\mathbf{v}}_i^{t+1}∥>v_{max}\hfill \end{array}\right.$$

(7)

for

$$\begin{array}{cc}\hfill v_{max}& =\delta \sqrt{\sum _{j=1}^{n_x}{\left(u_j-{\ell }_j\right)}^2}\hfill \\ \hfill & =\delta |\mathbf{u}-\ell |\hfill \end{array}$$

(8)

where $\mathbf{u}={\left[u_1,\dots ,u_{n_x}\right]}^T$ and $\ell ={\left[{\ell }_1,\dots ,{\ell }_{n_x}\right]}^T$ are $n_x$-dimensional vectors.

Whereas clamping by magnitude purports to having the advantage of maintaining directionality, since all velocity components are scaled by the same factor, it has the disadvantage that large velocity components dominate, and small components might become infinitesimal. Conversely, velocity clamping by dimension modifies the particle’s trajectory, but smaller velocity components maintain significance. However, since the random components ${\mathbf{r}}_1$ and ${\mathbf{r}}_2$ modify the particle’s trajectory in all dimensions anyway, velocity clamping per dimension is preferred here.

2.5. Self-Adaptive Particle Swarm Optimisation

Numerous SAPSO algorithms exist in the literature, but many of them lead to particles that diverge into infeasible search space, or premature convergence due to step sizes which quickly approach zero [8]. Additionally, most of these algorithms add more CPs than are originally present. This observation is supported by another study [7], which found that many of the 18 examined SAPSO algorithms either displayed divergence or premature convergence. Efforts to suitably adjust the CPs $\omega$, $c_1$, and $c_2$, therefore generally fail to do so in a way that reduces the number of parameters which impact performance. Exceptions are SAPSO by [26], improved PSO by [27], and PSO with random acceleration coefficients by [7].

This section discusses SAPSO algorithms relevant for the purposes of this study.

2.5.1. Adaptive Particle Swarm Optimisation Based on Velocity Information

Adaptive particle swarm optimisation based on velocity information (APSO-VI) [28] seeks to adjust particle velocities towards an optimal, decreasing velocity by manipulating the inertia weight $\omega$ to reflect the shift from exploration to exploitation. The APSO-VI algorithm functions as follows: the average velocity of all particles in the swarm is calculated using

$$v_{avg}\left(t\right)={\displaystyle \frac{1}{n_x{n}_s}}\sum _{i=1}^{n_s}\sum _{j=1}^{n_x}\left|v_{ij}\left(t\right)\right|$$

(9)

where $n_x$ is the number of dimensions and $n_s$ is the size of the swarm. Thereafter, the optimal velocity is defined as

$$v_{ideal}\left(t\right)=v_s\left({\displaystyle \frac{1+cos\left(\pi \frac{t}{T_{0.95}}\right)}{2}}\right)$$

(10)

with the initial optimal velocity $v_s$ as

$$v_s={\displaystyle \frac{x_{max}-x_{min}}{2}}$$

(11)

and $T_{0.95}$ is the point where 95% of the search is finalized; $x_{max}$ and $x_{min}$ are the respective boundaries of the feasible search space. The CP $\omega$ is then updated using

$$\omega (t+1)=\left\{\begin{array}{cc}max\left\{\omega \left(t\right)-\Delta \omega ,{\omega }_{min}\right\}\hfill & \mathrm{if}{v}_{avg}\left(t\right)\ge v_{\mathrm{ideal}}(t+1)\hfill \\ min\left\{\omega \left(t\right)+\Delta \omega ,{\omega }_{max}\right\}\hfill & \mathrm{if}{v}_{avg}\left(t\right)<v_{\mathrm{ideal}}(t+1)\hfill \end{array}\right.$$

(12)

where ${\omega }_{min}=0.3$ and ${\omega }_{max}=0.9$ are the minimum and maximum inertia weights, and $\Delta \omega =0.1$ is the inertia weight step size. As the search progresses, the decrease in $\omega$ causes the CP configuration to become convergent according to Poli’s convergence criterion in Equation (4). Consequently, while initially almost the whole swarm resides in infeasible search space, upon completion of the search, only 6% of particle positions are infeasible.

APSO-VI is of interest, because it reflects the intuitive expectation that a successful SAPSO algorithm should exhibit a transition from exploration towards exploitation as the search progresses. Whether this characteristic is automatically learned by an RL-based SAPSO algorithm might be informative.

2.5.2. Adventurous Unified Adaptive Particle Swarm Optimisation

Adventurous unified adaptive particle swarm optimisation (UAPSO-A) [29] makes use of learning automata, which are defined as adaptive decision-making devices. As the learning automata interact with their stochastic environment, they begin to make better decisions, in this case choosing new CP values for the next time-step.

The UAPSO-A algorithm functions as follows: for each CP, a separate learning automaton selects new CP values from a discrete, predefined range of values on each time-step. The inertia weight range consists of $n_{\omega }$ equidistant values in $\left[{\omega }_{min},{\omega }_{max}\right]=[0,1]$. The cognitive and social components’ range consist of $n_c$ equidistant values in $\left[c_{min},c_{max}\right]=[0,4]$. A feedback signal instructs the automaton. If selection of the CP value at index i improved solution quality, selection probabilities are updated using

$$p_j(t+1)=\left\{\begin{array}{cc}{p}_j\left(t\right)+a\left(1-p_j\left(t\right)\right)\hfill & \mathrm{if}i=j\hfill \\ p_j\left(t\right)(1-a)\hfill & \mathrm{otherwise}\hfill \end{array}\right.$$

(13)

where $p_j$ is the selection probability of the CP value at index j. Furthermore, a is the reward step size, which increases the likelihood of reselection for the successful CP value and decreases the likelihood for all other CP values. If selection of the CP value at index i did not improve the solution quality, selection probabilities are updated using

$$p_j(t+1)=\left\{\begin{array}{cc}{p}_j\left(t\right)(1-b)\hfill & \mathrm{if}i=j\hfill \\ {\displaystyle \frac{b}{\left|A\right|-1}}+p_j\left(t\right)(1-b)\hfill & \mathrm{otherwise}\hfill \end{array}\right.$$

(14)

where b is the penalty step size, and $\left|A\right|$ is the number of possible CP values to choose from. The likelihood of reselection of the unsuccessful CP value is, therefore, decreased.

UAPSO-A demonstrates convergent behaviour despite not enforcing Poli’s convergence criterion in Equation (4). Between 60% and 80% of particles have convergent CP values at any given time-step. As a result, many particles initially violate boundaries of the feasible search space, but the bound violations decrease smoothly to less than 40% towards the end of the search process as the parameters are adapted [7]. Finally, UAPSO-A adapts $\omega$, $c_1$, and $c_2$, but introduces nine constants, namely, $n_{\omega }$, ${\omega }_{min}$, ${\omega }_{max}$, $n_c$, $c_{min}$, $c_{max}$, a, b, and $\tau$. UAPSO-A is of interest because the learning automata can be considered as a rudimentary form of RL. RL similarity lies in that the automata take actions by making decisions, informed by a reward signal which is based on the objective function value of the particle.

2.6. Reinforcement Learning

RL is the process by which an agent learns an optimal action to take in a given situation, guided by a reward signal [13]. In many cases, the agent observes the environment, meaning that it receives information that conveys the current state of the environment. The agent learns by interacting with its environment and trying out different actions, and receives rewards correspondingly. It should also sufficiently explore the possible action space, while still eventually converging to an optimal path of action. Furthermore, actions taken at a certain point in time usually affect the environment and future reward. The paradigms of trial-and-error, exploration-exploitation, and delayed gratification are, therefore, central to RL. Learning from experience in this fashion allows RL to engage with interactive and unfamiliar problems where examples of optimal behaviour might not be available, and which are, therefore, not readily addressable by supervised learning techniques.

This section elucidates the concepts of RL and the SAC algorithm. It introduces the principles of RL, outlines the SAC algorithm, and discusses the mathematical underpinnings of SAC, including policy iteration, entropy maximisation, and the modified Bellman backup operator. The section culminates by emphasising the scalability and stability of SAC, its ability to address high sample complexity and convergence brittleness, and its effectiveness in balancing exploration and exploitation.

Soft Actor-Critic

Introduced by Haarnoja et al. [14], the SAC is an RL algorithm that addresses the challenges typically faced by model-free RL, such as high sample complexity and convergence brittleness. High sample complexity implies a large computational cost, and convergence brittleness necessitates tedious hyperparameter tuning to ensure stable learning and convergence. In contrast to most RL algorithms, SAC aims to maximise not only the expected reward, R, but also the action-selection entropy. This is achieved by taking maximally random actions off-policy, while still optimising the policy for the given task. These random, albeit high-entropy actions, encourage diverse behaviour [30,31] and promote exploration of the action space. High-entropy actions provide resilience against estimation errors [32], as the policy assigns similar probabilities to actions with similar values to prevent the policy from continually reselecting the same action. Moreover, SAC can handle continuous, high-dimensional state and action spaces, which often pose problems for convergence stability [33].

The key constituents of SAC include an actor for the policy function, and a critic for the value function. Furthermore, off-policy learning increases efficiency by incorporating previously collected data, and entropy maximisation enhances exploration and reduces brittleness. In adherence to the actor-critic formulation, SAC performs policy iteration by cycling between policy evaluation, which calculates the value function $v_{\pi }$ of a policy $\pi$, and policy improvement, where the value function is used to improve the policy [13]. Policy iteration for SAC has a convergence proof [14]. Entropy maximisation ensures that random actions are chosen using

$$J\left(\pi \right)=\sum _{t=0}^T{\mathbb{E}}_{\left({\mathbf{s}}_t,{\mathbf{a}}_t\right)\sim {\rho }_{\pi }}\left[r\left({\mathbf{s}}_t,{\mathbf{a}}_t\right)+\alpha \mathcal{H}\left(\pi \left(·\mid {\mathbf{s}}_t\right)\right)\right]$$

(15)

where ${\mathbf{s}}_t$ represents the current state in state space $\mathcal{S}$, and ${\mathbf{a}}_t$ is the current action in action space $\mathcal{A}$. The expectation is taken over the state transition probability, ${\rho }_{\pi }\left({\mathbf{s}}_t\right)$. The reward function is denoted by r. This formulation yields a Markov decision process (MDP) defined as $(\mathcal{S},\mathcal{A},p,r)$ [13]. The temperature parameter $\alpha$ balances the weighting between entropy and reward, where a lower $\alpha$ results in less randomness in the optimal policy $v^{\ast }$ and, consequently, less exploration.

The Q-value represents the expected reward for a certain state-action pair, and is obtained by iteratively calculating the modified Bellman backup operator using

$${\mathcal{T}}^{\pi }Q\left({\mathbf{s}}_t,{\mathbf{a}}_t\right)\triangleq r\left({\mathbf{s}}_t,{\mathbf{a}}_t\right)+\gamma {\mathbb{E}}_{{\mathbf{s}}_{t+1}\sim p}\left[V\left({\mathbf{s}}_{t+1}\right)\right]$$

(16)

from any starting function $Q:\mathcal{S}\times \mathcal{A}\to \mathbb{R}$. The discount factor, $\gamma$, determines how myopic the agent is. For a small $\gamma$, the agent optimizes for immediate reward at the expense of potentially more reward later. Conversely, a higher $\gamma$ incentivises ‘delayed gratification’, where the agent might sacrifice reward at the current time-step if such action ensures increased reward at a later stage. After calculation of Equation (16), the value of the policy is calculated as

$$V\left({\mathbf{s}}_t\right)={\mathbb{E}}_{{\mathbf{a}}_t\sim \pi }\left[Q\left({\mathbf{s}}_t,{\mathbf{a}}_t\right)-log\pi \left({\mathbf{a}}_t\mid {\mathbf{s}}_t\right)\right]$$

(17)

During policy improvement, $\pi$ is updated using the Kullback–Leibler divergence [34] projection to constrain the policy to the set of tractable policies, $\mathsf{\Pi }$, according to

$$\begin{array}{c}\hfill {\pi }_{\mathrm{new}}=arg\underset{{\pi }^{\prime }\in \mathsf{\Pi }}{min}{\mathrm{D}}_{\mathrm{KL}}\left({\pi }^{\prime }\left(·\mid {\mathbf{s}}_t\right)\left|\right|{\displaystyle \frac{exp\left(Q^{{\pi }_{\mathrm{old}}}\left({\mathbf{s}}_t,·\right)\right)}{Z^{{\pi }_{\mathrm{old}}}\left({\mathbf{s}}_t\right)}}\right)\end{array}$$

(18)

where $Z^{{\pi }_{\mathrm{old}}}\left({\mathbf{s}}_t\right)$ is the partition function which normalises the distribution.

In order to extend Equations (16)–(18) to large, continuous domains, the policy $\pi$ must be approximated to the tractable policy ${\pi }_{\varphi }$, the Q-function Q to the “soft” Q-function $Q_{\theta }$, and the value function V to an approximate state value function $V_{\psi }$. Parameters $\varphi$, $\theta$, and $\psi$, respectively, govern these approximations. Also, since the complete, iterative evaluation of Equation (16) quickly becomes intractable, both approximations are updated alternatingly, rather than executing both evaluation and improvement to completion. The soft Q-function is, therefore, minimised with respect to the squared residual error,

$$J_V\left(\psi \right)={\mathbb{E}}_{{\mathbf{s}}_t\sim \mathcal{D}}\left[{\displaystyle \frac{1}{2}}{\left(V_{\psi }\left({\mathbf{s}}_t\right)-{\mathbb{E}}_{{\mathbf{a}}_t\sim \pi \varphi }\left[Q_{\theta }\left({\mathbf{s}}_t,{\mathbf{a}}_t\right)-log{\pi }_{\varphi }\left({\mathbf{a}}_t\mid {\mathbf{s}}_t\right)\right]\right)}^2\right]$$

(19)

where the error is the difference between the approximated value $V_{\psi }$, and the expectation of $Q_{\theta }$ in conjunction with the entropy of ${\pi }_{\varphi }$. The expectation is taken over all of $\mathcal{D}$, the distribution of all previous states and actions.

The SAC algorithm is a powerful tool for solving RL problems, demonstrating high efficiency and robustness. The actor-critic architecture allows for more efficient and effective learning by combining both value-based and policy-based methods. Entropy maximisation encourages diverse behaviour and exploration, reducing the brittleness commonly associated with model-free RL methods. The use of off-policy learning enhances sample efficiency, making better use of previously collected data. Overall, SAC offers a scalable and stable approach to RL, particularly in high-dimensional and continuous state and action spaces, and strikes a balance between exploration and exploitation.

2.7. Reinforcement Learning as a Hyper-Heuristic

Selection hyper-heuristics are control mechanisms that identify the most suitable optimisation technique over time, without complete knowledge of the problem domain [35]. Selection hyper-heuristics can function as operators which choose from a collection of population-based optimisation methods like PSO, which run concurrently. This approach is known as the heterogeneous meta-hyper-heuristic (HMHH) framework [36,37,38]. Although the focus of this paper is not the design of selection hyper-heuristics, HMHH warrants mention as it has seen the application of RL to population-based optimisation methods. Note, however, that in this context, RL does not refer to an agent being trained, but rather to the fact that a feedback signal is used to change the selection of the optimisation method.

This section examines the application of RL in selection hyper-heuristics within the HMHH framework. Two RL-inspired approaches, frequency improvement reinforcement learning Selection (HH_ReinfFr) and objective function proportional reinforcement learning selection (HH_ReinfPr), are discussed.

2.7.1. Frequency Improvement Reinforcement Learning Selection

HH_ReinfFr [35] is a hyper-heuristic approach inspired by the works of [39,40]. In this method, each heuristic $h_m$ has a rank score $r_m$, initially set to zero. The heuristics are rewarded or punished based on the frequency with which they improve the quality of assigned candidate solutions. The change in rank for a heuristic $h_m$ is calculated as $\Delta r_m\left(t\right)={\chi }_m\left(t\right)$, where ${\chi }_m\left(t\right)$ represents the frequency score according to

$${\chi }_m\left(t\right)=\sum _{m=1}^{n_t}\sum _{i=1}^{n_m}\left\{\begin{array}{cc}+1\hfill & \mathrm{if}{f}_i\mathrm{improved}\hfill \\ -1\hfill & \mathrm{if}{f}_i\mathrm{remained}\mathrm{the}\mathrm{same}\hfill \\ -1\hfill & \mathrm{if}{f}_i\mathrm{worsened}\hfill \end{array}\right.$$

(20)

where $f_i$ is the quality of candidate solution i, $n_m$ is the number of candidate solutions assigned to heuristic $h_m$, and $n_t$ is the number of iterations over which the calculation is performed. The range of ${\chi }_m\left(t\right)$ is $\left[-\left(n_s\times n_t\right),\left(n_s\times n_t\right)\right]$. Rank update happens according to $r_m\left(t\right)=r_m(t-n_t)+\Delta r_m\left(t\right)$. Candidate solutions are assigned to the highest-ranked heuristic, following the approach by [40], in effect, blacklisting all other heuristics. The values in $\mathsf{\Theta }\left(t\right)$ are assigned as $P_m=1$ for $m=r$ for the highest-ranked heuristic $h_r\in H$, while $P_m=0$ for $m\ne r$. Rank ties are resolved randomly, and the same $\mathsf{\Theta }\left(t\right)$ is employed for assigning all candidate solutions.

2.7.2. Objective Function Proportional Reinforcement Learning Selection

HH_ReinfPr [35] is another hyper-heuristic approach. While similar to HH_ReinfFr, the difference lies in the adjustment of ranks, which is based on the mean change in quality of candidate solutions. The mean change in solution quality is calculated using

$${\varphi }_m\left(t\right)={\displaystyle \frac{{\sum }_{i=1}^{n_m}\left(f_i\left(t\right)-f_i(t-n_t)\right)}{n_m}}$$

(21)

The change in rank $\Delta r_m\left(t\right)$ for each heuristic $h_m$ is calculated as

$$\Delta r_m\left(t\right)=\left\{\begin{array}{cc}+1\hfill & \mathrm{if}{\varphi }_m\left(t\right)>0\hfill \\ -1\hfill & \mathrm{if}{\varphi }_m\left(t\right)=0\hfill \\ -1\hfill & \mathrm{if}{\varphi }_m\left(t\right)<0\hfill \end{array}\right.$$

Ranks are updated using the formula $r_m\left(t\right)=r_m(t-n_t)+\Delta r_m\left(t\right)$. Initial ranks for all heuristics are $r_m=r_{min}=0$. As for HH_ReinfFr, candidate solutions are assigned to the highest-ranked heuristic in accordance with the approach by [40]. $\mathsf{\Theta }\left(t\right)$ probabilities are set as $P_m=1$ for $m=r$ in the case of the highest-ranked heuristic $h_r\in H$, while $P_m=0$ for $m\ne r$. Rank ties are broken at random, and the same $\mathsf{\Theta }\left(t\right)$ is used for assigning all candidate solutions. The difference between HH_ReinfFr and HH_ReinfPr is that the former rewards heuristics based on the frequency with which they improve solution quality, while the latter rewards heuristics based on the mean change in quality of candidate solutions assigned to them.

3. Design of Soft Actor-Critic Self-Adaptive Mechanism

This section details the design of the SAC-SAPSO algorithm, which uses the SAC to dynamically adjust the PSO CPs. Initially, the section motivates why RL is ideally suited, and a suitable RL algorithm is chosen. Thereafter, the SAC-SAPSO architecture is described, including design choices pertaining to the RL environment, agent, and reward function.

3.1. Motivation for Reinforcement Learning for Self-Adaptation

Development of a self-adaptive PSO algorithm essentially amounts to the adjustment of CP values, based on the behaviour of the particles, so as to improve the solution quality. This can be framed as an RL problem, where an agent finds a policy to govern its actions (choosing new CP values), based on observations (behaviour of the particles), in order to maximise a reward signal (solution quality). Using RL for SAPSO is somewhat related to UAPSO-A [29], because the UAPSO-A learning automata can be considered as simple RL agents which receive reward if the selected CP values improved solution quality. However, UAPSO-A is subject to several limitations:

• UAPSO-A does not consider particle characteristics such as velocity or position to inform CP updates.
• Orthogonal automata are used for each CP, which precludes the decision-making mechanism from considering the other CP values when updating the current CP.
• The UAPSO-A mechanism makes use of simplistic probability-based decision-making, which assumes previously successful CP values to be successful in the future. This assumption is not necessarily true, given deceptive optimisation problems with changing function landscape characteristics.
• UAPSO-A can only select CP values from a discrete set, disallowing fine-grained adjustment.

Moreover, RL has been used to statically pre-select hyperparameters or to tune hyperparameters [15,16,17,18]. However, no examples were found where RL is used to dynamically adjust hyperparameters during execution of the algorithm. Algorithms such as HH_ReinfFr and HH_ReinfPr (discussed in Section 2.7.1 and Section 2.7.2) also use RL, but they select amongst different heuristics, which also differs greatly from dynamic adjustment of PSO CPs during the search process.

A significant advantage of using RL for self-adaptation is that an RL agent can automatically discover the best policy. Most SAPSO approaches are based on inductive priors, i.e., the authors believe that adapting the CPs in a certain way is more likely to lead to a good outcome. For example, PSO-TVAC (see Section 2.2) is based on the assumption that decreasing particle inertia will lead to improved performance. While this may well be the case, it is difficult to reason a priori about the behaviour of the PSO swarm. For example, there is complex interplay between the fitness landscape, the CP configuration, and the particle positions and solutions. Correlations between these factors cannot easily be captured by a simple heuristic, but can be learned by an RL agent, which can then adjust the CP configuration accordingly. Also, if performed manually, only a few approaches toward SAPSO can be tried, whereas an RL agent explores millions of policies.

Using supervised neural networks (NNs) to adapt PSO CPs has also been considered. For example, the input to the NN could be information about the particles, such as fitness landscape characteristics at current positions, and the output could be the CP configuration predicted for the next time-step. This approach is inferior to RL for the following reasons:

• Labelling vs. Interacting: In order to train the NN, a labelled dataset is required. Since the NN has to predict the CPs, supervised learning requires knowledge of the “correct” CPs in order for the NN to train, which is, of course, not known in advance. RL bypasses this issue, as the agent interacts with the environment autonomously, and learns from experience. In this case, the agent is the SAC, and the environment is the PSO search process, which provides information such as particle velocities and solutions to the agent.
• Exploration vs. Exploitation: Just as the particle swarm should ideally maintain a suitable balance between exploration and exploitation, this balance should also be present in the CP space. NNs are not capable of exploring the CP space, but merely learn from labels. Conversely, the exploration-exploitation paradigm lies at the heart of the SAC formulation, as discussed in Section 2.6. The SAC agent explores the CP space by taking random actions, and exploits the CP space by taking actions which have been shown to be successful in the past.

To conclude, RL offers a promising avenue for self-adaptation in PSO algorithms by dynamically adjusting CP values during the execution of the algorithm. RL overcomes several limitations of existing methods such as UAPSO-A and supervised neural networks by enabling a more fine-grained, informed, and adaptive decision-making process. By interacting with the environment and learning from experience, an RL agent can discover optimal policies and maintain a balance between exploration and exploitation in the CP space, leading to improved performance and solution quality in complex optimisation problems.

3.2. Reinforcement Learning Algorithm Selection

A plethora of RL algorithms exist, some more suitable than others towards SAPSO. The following criteria are considered:

• Model-free, not model-based: Since there is no preexisting model of how the CP configuration should be adapted (if there was, the problem would be solved already), the agent has to learn in a model-free way.
• Off-policy, not on-policy: Exploration of the CP space is aided if the agent is permitted to take actions off-policy. If the agent only takes actions on-policy, the only possible actions are those which have been successful in the past, increasing the likelihood of becoming stuck in a local optimum.
• Continuous action space, not discrete: The possible CP values which can be selected form a continuous range and the policy should, therefore, have a continuous action space. Contrast this with the UAPSO-A algorithm in Section 2.5.2, which outputs a range of discrete values. Discretisation adds complexity because the agent chooses between n different values on every CP update. Nonetheless, it has less flexibility than a continuous action space because it is still limited to those n specific values.
• Continuous state space, not discrete: All variables in the PSO formulation (i.e., particle positions, velocities, etc.) are continuous floating-point values. Since these are the variables which the agent observes, the agent should have a continuous state (observation) space.

A comparison of RL algorithms is given in

Table 1. Comparison of RL algorithms. (Discr. = discrete action space, Cont. = continuous action space).

Algorithm	Definition	Action	State	Model	Policy
MC [41]	Every-Visit Monte Carlo	Discr.	Discr.	Model free	Either
SARSA [42]	State-action-reward-state-action	Discr.	Discr.	Model free	On-policy
Q-learning [43]	State-action-reward-state	Discr.	Discr.	Model free	Off-policy
DQN [44]	Deep Q-Network	Discr.	Cont.	Model free	Off-policy
A3C [45]	Asynchronous Advantage Actor-Critic	Cont.	Cont.	Model free	On-policy
TRPO [46]	Trust Region Policy Optimisation	Cont.	Cont.	Model free	On-policy
PPO [47]	Proximal Policy Optimisation	Cont.	Cont.	Model free	On-policy
DDPG [48]	Deep Deterministic Policy Gradient	Cont.	Cont.	Model free	Off-policy
TD3 [49]	Twin Delayed Deep Deterministic Policy Gradient	Cont.	Cont.	Model free	Off-policy
SAC [14]	Soft Actor-Critic	Cont.	Cont.	Model free	Off-policy

, from which deep deterministic policy gradient (DDPG), twin delayed DDPG (TD3), and SAC are eligible according to the aforementioned criteria. Since TD3 and DDPG are more prone to hyperparameter instability [14], they are eliminated for the purposes of this study.

Furthermore, in cases where the RL environment is not computationally expensive to simulate or execute, it is often preferable to use an algorithm with lower sample efficiency and to run it for more iterations. However, since evaluation of the environment (i.e., the PSO search) amounts to computing velocities and positions for $n_s$ particles in $n_d$ dimensions, this makes for a rather complex environment. For this reason, an algorithm with higher sample efficiency allows for the environment to be evaluated less often. SAC fits the aforementioned criteria, because it has higher-than-normal sample efficiency. It is also robust to convergence brittleness, as discussed in Section 2.6, and is, therefore, the algorithm of choice for the development of the RL-based SAPSO.

3.3. SAC-SAPSO Architecture

The architecture of SAC-SAPSO consists of the PSO and the SAC agent, which are implemented as described in Section 2.1 and Section 2.6, respectively. Interaction between PSO and SAC lies in that the SAC agent observes the PSO search process, which is the environment. The SAC agent then takes actions which influence the PSO environment.

This section presents the SAC-SAPSO architecture, consisting of the PSO and a SAC agent. The interaction between these components is explained, as well as the PSO environment details, the SAC agent’s actions, and the formulation of the SAC-SAPSO reward signal. Detailed discussion covers topics like PSO metrics, normalisation of velocities, SAC agent’s policy, and benefits and drawbacks of absolute and relative reward signals.

The SAC-SAPSO is summarised in Algorithm 1.  

Algorithm 1: SAC-SAPSO Algorithm

3.3.1. PSO as the Environment

The PSO search process serves as the environment for the SAC agent, which observes particle velocities, percentage stable particles, percentage infeasible particles, and the percentage completion of the search at any given time-step. See Section 4.1 for a discussion of these metrics, except for percentage completion, which is defined as the number of the current time-steps divided by the maximum number of time-steps. The observation space thus has a dimensionality of $n_s+3$, where $n_s$ is the number of particles in the swarm. This is because particle velocities are observed for each particle, while the other metrics are calculated for the entire swarm. To ensure a unitary observation space for the SAC agent, particle velocities are normalised and scaled according to the transformation,

$${\mathbf{v}}_{\mathrm{norm}}=tanh\left({\displaystyle \frac{2}{\mathbf{u}-\ell }}·\left(\mathbf{v}-{\displaystyle \frac{\ell +\mathbf{u}}{2}}\right)\right)$$

(22)

where $\mathbf{v}$ is the velocity vector of the particle, ℓ is the lower bound of the feasible search space, and $\mathbf{u}$ is the upper bound of the feasible search space. Equation (22) first normalises particle velocities by the boundaries of the feasible search space. This ensures that a velocity of 1 corresponds to traversal of the entire search space in one time-step. However, since velocity explosion [9,25] is a common problem in PSO, particle velocities can assume extremely large values. To still retain a unitary observation space, the normalised velocity vector is then squashed using the hyperbolic tangent function to the range of $[-1,1]$. Intuitively, a particle with a velocity which exploded to ${10}^5$ has just as little chance of finding a good solution in feasible space as does a particle with a velocity of ${10}^{10}$. The hyperbolic tangent function accounts for this, with all such large velocities being squashed to approximately 1.

3.3.2. SAC as the Agent

The SAC agent takes actions according to a policy, which governs the adjustment of the PSO CPs during the search process. Observation of the PSO environment is performed every $n_t$ time-steps. Upon observing the environment, the agent outputs as actions the continuous CP values of $\omega$, $c_1$, and $c_2$ at that time-step. Since all particles are given the same CP values, the action space has a dimensionality of 3. These values are then used to update the PSO CPs according to the velocity update rule in Equation (1).

Updating the CPs on every time-step (setting $n_t=1$) is inefficient, because the search characteristics do not change sufficiently during one time-step to necessitate a new CP configuration. A larger value for $n_t$ can be used, but introduces an additional hyperparameter. Alternatively, $n_t$ can form part of the action space, thus allowing the agent to autonomously learn an optimal value for $n_t$. The latter option has as an advantage that the agent can learn to adjust the observation-action frequency according to the current state of the search process, potentially improving the search performance. The three options are, therefore, $n_y=1$ to adapt on every time-step, $n_t=t^{\prime }$ to adapt every $t^{\prime }$ time-steps, and $n_t\in \mathcal{A}$ (the action space).

3.3.3. SAC-SAPSO Reward Signal

The reward signal informs an RL agent whether its actions achieve the desired outcome. The reward acts as a feedback mechanism and guides the agent towards learning the optimal policy, which maximizes the expected cumulative reward over time [13]. Proper reward shaping is crucial to align the goal of the SAC agent with that of the PSO, namely, to ensure that CP adaptation improves search performance. Since the minima and maxima of the training function set are known, it is straightforward to relate the global best solution to an absolute normalised reward signal according to

$$r_{\mathrm{abs}}\left(t\right)={\displaystyle \frac{y_f(t-1)-y_f\left(t\right)}{y_{max}-y_{min}}}$$

(23)

where $y_f$ is the global best solution at time-step t. The term ‘absolute’ indicates that the normalisation is performed using the absolute minimum and maximum of each function in the training function set. Note that the generic formula for absolute change is usually defined as

$${\delta }_{\mathrm{abs}}={\displaystyle \frac{y_{new}-y_{old}}{y_{max}-y_{min}}}$$

(24)

However, in Equation (23), the numerator is reverted, because a decreasing global best solution implies an increasing reward. Normalisation is necessary, because the functions lie on vastly different magnitude ranges, and ensures a direct relationship between reward maximisation and improvement of the global best solution found. Equation (23) has the reward landscape shown in Figure 1a.

The reason for computing the numerator of $r_{\mathrm{abs}}\left(t\right)$ with respect to $y_f(t-1)$ instead of $y_{\max }$ is to ensure that the maximum possible reward for a given function, which aggregates during the PSO search of that function, equals 1. The agent thus receives a cumulative reward of 1 only if the PSO manages to find $y_{\min }$ during the search process. Similarly, a cumulative reward of 0.5 indicates that the PSO only found a global best solution halfway between $y_{\max }$ and $y_{\min }$. If the reward was calculated with respect to $y_{\max }$, this would provide less incentive towards finding an optimal solution. For example, if a global best solution at a given time-step produced a reward of 0.5, the agent would continue to receive a reward of at least 0.5 for all subsequent time-steps, even if the global best solution stagnated there.

The reward formulation of Equation (23) is also preferable to that of UAPSO-A (Section 2.5.2), where a constant amount of reward is generated if the objective function value improved, irrespective of the degree of improvement. This UAPSO-A reward formulation could incentivise the agent into optimising for small, incremental steps, instead of just solving the function optimally.

Equation (23) evidently has the problem that it can only be used if the minimum and maximum of the objective function are known. If the minimum is known, the objective function has, of course, already been solved. To circumvent this, Equation (23) is modified to obtain a relative reward signal, defined as

$$r_{\mathrm{rel}}\left(t\right)=\left\{\begin{array}{cc}0\hfill & \mathrm{if}{y}_f\left(t\right)=y_f(t-1)\hfill \\ 2·{\displaystyle \frac{y_f(t-1)+\beta -y_f\left(t\right)+\beta }{y_f(t-1)+\beta }}\hfill & \mathrm{if}{y}_f\left(t\right)>0,y_f(t-1)>0\hfill \\ 2·{\displaystyle \frac{y_f(t-1)+2\beta -y_f\left(t\right)+2\beta }{y_f(t-1)+2\beta }}\hfill & \mathrm{if}{y}_f\left(t\right)<0,y_f(t-1)<0\hfill \\ 1\hfill & \mathrm{otherwise}\hfill \end{array}\right.$$

(25)

where $\beta =|y_f(t-1)|+|y_f\left(t\right)|$. The reward, $r_{\mathrm{rel}}\left(t\right)$, is, therefore, always only calculated as the improvement in solution quality with respect to the previous time-step, and never makes use of the absolute maximum and minimum of a function. However, functions can take on any range; that is, $y_{\min }$ and $y_{\max }$ can both be positive, both be negative, or negative and positive, respectively, and can be arbitrarily large or small. This precludes simply using the general formula for relative change (with an inverted numerator),

$${\delta }_{\mathrm{rel}}={\displaystyle \frac{y_{\mathrm{old}}-y_{\mathrm{new}}}{y_{\mathrm{old}}}}$$

(26)

which only works if all values have the same sign, and does not provide unitary normalisation. If not, Equation (26) results in a jump discontinuity as soon as $y_{\mathrm{new}}$ changes from positive to negative during the PSO search. Also, when both $y_{\mathrm{old}}$ and $y_{\mathrm{new}}$ are negative, the reward is distorted and inverted. The aforementioned problems are clear in Figure 1c.

Equation (25) addresses these problems by shifting $y_{\mathrm{old}}$ and $y_{\mathrm{new}}$ by $2\beta$ if both are negative, $\beta$ if both are positive, and scales by 2 for both. The shift is calculated in this way to ensure that after shifting, both $y_{\mathrm{old}}$ and $y_{\mathrm{new}}$ are positive and non-zero. Equation (25) also places a fixed limit of ${r_{\mathrm{rel}}}_{\max }=1$ for the rare time-steps where the global best solution transitions from positive to negative. The scaling factor of 2 ensures continuity between the four possible cases, with the resulting reward landscape shown in Figure 1b. Note that the objective function value y in Figure 1b,c has not been normalised, with $\left[-3,3\right]$ selected arbitrarily, because the range of y can take any value. Conversely, y is always normalised before calculating Equation (23) to obtain the landscape in Figure 1a, which is why the range is $\left[0,1\right]$. Furthermore, while the area in Figure 1b, where $r_{\mathrm{rel}}=1$, appears to be very large, the reality is that it only occurs at time-steps where $y(t-1)>0$ and $y\left(t\right)<0$. These time-steps are rare, because they only occur one or zero times during the PSO search.

4. Experimental Procedure

This section elaborates on the experimental procedure, focusing on evaluation metrics and specifics regarding the PSO implementation. Following this, the details of the algorithm’s implementation are presented. This includes the nature of RL, the role of training and testing sets, and the specifics of conducting an experiment. Lastly, the section delves into the hyperparameters used during the training phase of the SAC algorithm, underscoring their importance in the overall effectiveness and functionality of the SAC-SAPSO algorithm. As various aspects of the algorithm are assessed, a ‘run’ is defined as a single SAC-SAPSO execution on a single function, while an ‘experiment’ denotes $r=30$ independent runs for each function in the entire function set.

4.1. Evaluation Metrics

Multiple metrics are utilised to examine the performance and characteristics of the SAC-SAPSO:

• Normalised global best solution quality. The objective function value, or solution quality at the global best positions, signifies how well an algorithm solves a given optimisation problem. Because functions differ in their ranges, normalised global best solution quality is employed. Once all experiments have concluded, the highest and lowest global best solutions discovered throughout all experiments and runs are used to normalise global best solutions to [0, 1] for each experiment. The scale used for normalisation is chosen at will, but unitary scaling leads to easily comprehensible results, where lower values represent better solutions.
• Average swarm diversity offers insights into the balance of exploration and exploitation. Diversity is computed using [50]

  $$\mathcal{D}={\displaystyle \frac{1}{n_s}}\sum _{i=1}^{n_s}\sqrt{\sum _{j=1}^{n_x}{\left(x_{ij}-{\overline{x}}_j\right)}^2}$$

  (27)

  with the swarm center located at

  $$x_j={\displaystyle \frac{{\sum }_{i=1}^{n_s}{x}_{ij}}{n_s}}$$

  (28)

  where $n_s$ represents the number of particles in the swarm, and $n_x$ refers to the number of dimensions.
• Percentage of particles in infeasible space. A particle is considered to be in infeasible space if it breaches the boundaries of the feasible search space in at least one dimension. Infeasible particles should not be taken into account when updating the best positions found, so as not to steer the search away from feasible space [9].
• Percentage of particles that are stable. Poli’s stability condition (given in Section 2.3 in Equation (4)) determines whether a particle has convergent CP configurations, and is considered stable [51].
• Average particle velocity denotes the average step sizes. In order for the search process to converge, step sizes have to decrease. However, in order to not become trapped in a local minimum, step sizes should not become too small too quickly. The average particle velocity is calculated using [7]

  $$\Delta (t+1)={\displaystyle \frac{1}{n_s}}\sum _{i=1}^{n_s}∥{\mathbf{x}}_i(t+1)-{\mathbf{x}}_i\left(t\right)∥$$

  (29)

4.2. Implementation

Unlike supervised learning methods, which require separate training and testing sets to learn and evaluate the performance of a model, RL algorithms are trained on the environment for which they are used. The reason behind this difference lies in the nature of the RL learning process. In supervised learning, the model learns from a fixed set of labelled examples, and the testing set is used to evaluate the generalisation ability of the model to unseen data [52]. Conversely, RL agents take actions based on observations to solve environments [13]. Therefore, for each experiment (i.e., algorithmic aspect under investigation), an agent is trained and $r=30$ independent evaluation runs. This is performed using the set which contains 45 30-dimensional minimisation functions provided in Appendix A.

However, since the SAC-SAPSO algorithm must definitely generalise, the training function set cannot also represent algorithmic performance without bias. Thus, a test set of seven additional functions is used, also detailed in Appendix A. This ensures an 85% training, 15% testing split for honest assessment of performance. The test functions have specifically been chosen to be more complex than the training set in order to demonstrate performance differences between algorithms more clearly.

The inertia weight PSO [19] is employed (described by Equations (1) and (2)), and the neighbourhood for each particle encompasses the entire swarm. The objective function value is only computed for particles situated within feasible space. Particles that fall outside the viable space are assigned infinite objective values, which, under the assumption of minimisation, disqualifies those particles from global best position updates. The swarm size is $n_s=30$, with each function having a dimensional space of $n_x=30$, with a maximum of $t_{max}=5000$ iterations for each run.

The average and standard deviation for all plots and scores are calculated across all functions and runs within a specific experiment, resulting in $(30\times 45)+(30\times 7)=1560$ runs for each experiment. Given the various algorithmic components examined, a total of 15 experiments are conducted, which translates to 23,400 runs.

4.3. SAC Hyperparameters

The SAC training hyperparameters are shown in

Table 2. SAC hyperparameters.

Discount factor $\mathit{\gamma }$	1	Target smoothing coefficient $\mathit{\tau }$	0.005
Reward scale factor $f_r$	1	Learning rate $\alpha$	0.0001
Actor layer size	256	Replay buffer size	${10}^6$
Critic layer size	256	Training steps	$2\times {10}^5$

. Note that the SAC training hyperparameters differ from PSO CPs because they are only used during the training of the SAC policy, whereas the CPs are dynamically adjusted during the PSO search to improve performance. Moreover, since the impact of these hyperparameters on the SAC agent is well understood and documented [31], it is possible to reason a priori about the values that should be used. Default values are also provided in the SAC documentation (https://spinningup.openai.com/en/latest/, accessed on 1 November 2023). Finally, these are all training hyperparameters. Once a policy is learned which successfully adapts the PSO CPs on the training set, these hyperparameters are discarded, and have no bearing on the functioning of the SAPSO algorithm anymore. The SAC hyperparameters are, therefore, not counter to the aim of SAPSO.

The discount factor $\gamma$ governs the trade-off between immediate and future rewards, where a low $\gamma$ will result in the agent being myopic, and a high $\gamma$ will result in the agent being far-sighted. For infinite-horizon RL problems, $\gamma$ usually needs to be adjusted carefully. However, for episodic RL problems such as the PSO search, $\gamma =1$ is recommended [13].

The reward scale factor $f_r$ can be used to normalise the reward signal. However, the reward formulation defined in Equation (25) is already normalised to the range $[0,1]$. Therefore, the reward is not scaled here, i.e., $f_r$ is not used. For completeness, this is equivalent to setting $f_r=1$.

Actor and critic layer sizes are set to 256 each, the default values recommended by the SAC documentation. Barring the case of too small layer sizes, which could render the policy too simple to learn complex PSO dynamics, these hyperparameters are not expected to have a significant impact on the performance of the learned policy.

Two value (critic) networks and one policy (actor) network are used by the SAC [14]. The target smoothing coefficient $\tau$ controls the rate at which these networks are updated using

$${\mathbf{w}}_{\mathrm{target}}\leftarrow \tau ·{\mathbf{w}}_{\mathrm{critic}}+(1-\tau )·{\mathbf{w}}_{\mathrm{target}}$$

(30)

where ${\mathbf{w}}_{\mathrm{target}}$ represents the weights of the target network, and ${\mathbf{w}}_{\mathrm{critic}}$ denotes the weights of the critic network; $\tau$ lies between 0 and 1, where a smaller $\tau$ corresponds to slower updates, resulting in more stable value estimates but potentially slower learning. A larger $\tau$ leads to faster updates, which may cause higher variance in value estimates and less stable learning. The default, small value of $\tau =0.005$ is used here, as recommended by the SAC documentation, because slower learning during training does not have a bearing on the actual usage of the SAC-SAPSO.

The learning rate $\alpha$ is set to a small, default value of $\alpha =0.0003$. Similar reasoning as for $\tau$ applies here.

Replay buffers are used to store past experiences, which are sampled from during training. The main concern regarding the replay buffer size is potential memory constraints during training. A large, default value of ${10}^6$ is chosen.

The number of training steps are set to $2\times {10}^5$. Because the training is actually stopped upon stagnation in performance of the learned policy, this value has no bearing on performance and is chosen as an arbitrary, large value.

All the hyperparameters in Table 2 are training parameters. This disjoint between training and execution ensures no runtime CPs, except potentially $n_t$. However, $n_t$ can be set to form part of the SAC action space $\mathcal{A}$, which completely automates this parameter also, as discussed in Section 3.3.2. Such a training-execution disjoint may well be the only way to adapt all PSO CPs, corroborated by the fact that all approaches to SAPSO end up introducing more runtime CPs in an attempt to adapt $\omega$, $c_1$ and $c_2$, as shown by [7,8].

5. Results

This section details the algorithmic aspects of different experiments, together with their respective results. Four performance baselines are presented together with their comparative outcomes. The final part explores the functionality of the SAC-SAPSO algorithm and its performance implications, highlighting how it outperforms the established baselines. Some plots contain gaps, such as Figure 11e, which occur when particles drift far enough out of the search space to cause numerical overflow in the swarm diversity calculation from Equation (27). Plot lines represent performance averages, and shaded areas the standard deviation, calculated over all functions and runs for the experiment at hand, as discussed in Section 4.2.

5.1. Performance Baselines

Four baselines are defined in this section, and their performance is presented in

Table 3. Baseline normalised global best solution quality.

	Training		Testing
	$\mathit{\mu }$	$\mathit{\sigma }$	$\mathit{\mu }$	$\mathit{\sigma }$
baseline_tvac	0.0883	0.1894	0.2926	0.2037
baseline_timevariant	0.0888	0.1991	0.3287	0.3052
baseline_constant	0.0893	0.1856	0.3802	0.2822
baseline_random	0.1044	0.2032	0.3812	0.3125

and illustrated in Figure 2, Figure 3, Figure 4, Figure 5 and Figure 6. The first baseline (baseline_constant) employs the constant CP setup outlined in Section 2.2, and the second one (baseline_timevariant) applies the time-variant configuration described by Equation (3). PSO-TVAC (see Section 2.2) is used as the third baseline (baseline_tvac), and the final baseline (baseline_random) randomly samples CPs which adhere to Poli’s convergence criterion in Equation (4) at each time step, for every particle in the swarm [53,54].

5.2. Soft Actor-Critic Control Parameter Adaptation

The SAC-SAPSO algorithm is evaluated for various values of $n_t$ (sac_$n_t=k$), in addition to an experiment where $n_t$ is set by the SAC algorithm itself (sac_$n_t=$ auto), with results given in

Table 4. SAC-SAPSO normalised global best solution quality.

	Training		Testing
	$\mathit{\mu }$	$\mathit{\sigma }$	$\mathit{\mu }$	$\mathit{\sigma }$
sac_$n_t=$ 10	0.0589	0.1338	0.2585	0.2602
sac_$n_t=$ 125	0.0628	0.1299	0.1811	0.192
sac_$n_t=$ 25	0.0687	0.1475	0.2415	0.1712
sac_$n_t=$ 100	0.0693	0.1599	0.2363	0.1905
sac_$n_t=$ auto	0.0693	0.1529	0.2373	0.1675
sac_$n_t=$ 50	0.0737	0.1609	0.2342	0.1998

. Figure 7 shows how the CP values are adapted by the SAC-SAPSO algorithm throughout the search process, and Figure 8 shows the number of stable particles in the swarm. On average, about half of the particles in the swarm have stable (convergent) CP configurations, with generally less than 40% of particles residing in infeasible space, as seen in Figure 9. Nonetheless, Figure 10 clearly shows that some particles in the swarm have exploding velocities, which results in the exploded swarm diversity in Figure 11. In some cases, the swarm diversity becomes big enough to cause numerical overflow, indicated by gaps, such as in Figure 11e.

For sac_$n_t=$ auto, when considering Figure 7f and Figure 8f jointly, it is interesting to note how the agent which adapts $n_t$ autonomously ultimately decides to keep exploration ($c_1,\omega$) high (with an entirely stable CP swarm!) for approximately the first 1000 time-steps. Thereafter, exploration and exploitation are promptly switched around by lowering $c_1$ and $\omega$, and increasing $c_2$. This is especially interesting as the agent has learned to initially maintain stable CP values by itself, without the need to introduce such an inductive prior artificially. Such behaviour suggests more exploration during the first fifth of the search, while keeping the particles mostly within the feasible search space (Figure 9f). The effect is also reflected by the particle velocities in Figure 10f and swarm diversity (Figure 11f), both of which stay low initially.

According to Table 4, the best performing sac_$n_t=10$ improves upon the best performing baseline (baseline_tvac) by 33% for the training set. The test-set performance improvement is less significant at 13%. Self-adaptation using a SAC agent is, therefore, promising, because it improves on the baseline despite the velocity explosion.

Figure 11. Swarm diversity (log) for SAC.

Figure 11. Swarm diversity (log) for SAC.

5.3. Soft Actor-Critic Control Parameter Adaptation with Velocity Clamping

To counter the velocity explosion in Section 5.2, velocity clamping limits the maximum velocity of each particle, as discussed in Section 2.4. The velocity-clamped SAC-SAPSO results in the CP configurations are shown in Figure 12. Once again, multiple experiments are conducted for various values of $n_t$ (vc_sac_$n_t=k$), as well as for the auto-tuned value of $n_t$ (vc_sac_$n_t=$ auto), with results given in

Table 5. SAC-SAPSO normalised global best solution quality (velocity clamped).

	Training		Testing
	$\mathit{\mu }$	$\mathit{\sigma }$	$\mathit{\mu }$	$\mathit{\sigma }$
vc_sac_$n_t=$ 125	0.0428	0.1115	0.0919	0.0892
vc_sac_$n_t=$ 50	0.0431	0.103	0.0689	0.0575
vc_sac_$n_t=$ 100	0.0473	0.1143	0.1089	0.0828
vc_sac_$n_t=$ auto	0.049	0.109	0.228	0.1628
vc_sac_$n_t=$ 10	0.0554	0.1219	0.1931	0.1902
vc_sac_$n_t=$ 25	0.0559	0.1239	0.1443	0.1373

(refer to Figure 13, Figure 14, Figure 15 and Figure 16). Figure 15 and Figure 16 confirm that velocity clamping successfully constrains particle velocities and, therefore, also swarm diversity, as no explosion is present. Table 5 shows that velocity clamping has a massive effect on performance, which is to be expected because CP adjustments can have a more fine-grained effect on particles which reside within the boundaries of the search space than over those which overshoot the search space by many orders of magnitude. The best-performing vc_sac_$n_t=125$ improves on the best-performing baseline (baseline_tvac) by 52% for the training set; on the test set, the improvement is 69%.

5.4. Overview of Results

Table 6. Comparison of normalised global best solution quality.

	Training		Testing
	$\mu$	$\sigma$	$\mu$	$\sigma$
vc_sac_$n_t=$ 125	0.0428	0.1115	0.0919	0.0892
vc_sac_$n_t=$ 50	0.0431	0.103	0.0689	0.0575
vc_sac_$n_t=$ 100	0.0473	0.1143	0.1089	0.0828
vc_sac_$n_t=$ auto	0.049	0.109	0.228	0.1628
vc_sac_$n_t=$ 10	0.0554	0.1219	0.1931	0.1902
vc_sac_$n_t=$ 25	0.0559	0.1239	0.1443	0.1373
sac_$n_t=$ 10	0.0589	0.1338	0.2585	0.2602
sac_$n_t=$ 125	0.0628	0.1299	0.1811	0.192
sac_$n_t=$ 25	0.0687	0.1475	0.2415	0.1712
sac_$n_t=$ 100	0.0693	0.1599	0.2363	0.1905
sac_$n_t=$ auto	0.0693	0.1529	0.2373	0.1675
sac_$n_t=$ 50	0.0737	0.1609	0.2342	0.1998
baseline_tvac	0.0883	0.1894	0.2926	0.2037
baseline_timevariant	0.0888	0.1991	0.3287	0.3052
baseline_constant	0.0893	0.1856	0.3802	0.2822
baseline_random	0.1044	0.2032	0.3812	0.3125

provides an overview of performance, with the normalised global best solution quality ranked from best to worst. The improvement made by the SAC-SAPSO above the baseline PSO is clear, as is the improvement which results from velocity clamping.

Preceding velocity clamping, the best performing sac_$n_t=$ 10 demonstrates a 34% improvement above the constant baseline, and a 33% improvement above the time-variant baseline. On the test set, sac_$n_t=$ 10 outperforms the constant baseline by 32% and the time-variant baseline by 21%. The best performing vc_sac_$n_t=$ 125 improves on both the constant and time-variant baselines by 52% for the training set; on the test set, the improvement is 76% and 72%, respectively. Interestingly, vc_sac_$n_t=$ 50 actually performs better than vc_sac_$n_t=$ 125 on the test set, outperforming the constant baseline by 82% and the time-variant baseline by 79%.

6. Conclusions

This paper presented a novel approach to the automatic adaptation of control parameters (CPs) in particle swarm optimisation (PSO). The approach is based on the soft-actor critic (SAC) algorithm, which learns a policy for the dynamic adaptation of CPs during the search process. Furthermore, velocity clamping prevents particle velocities from growing unboundedly. In conclusion, the velocity-clamped soft-actor critic self-adaptive particle swarm optimisation (SAC-SAPSO) algorithm successfully adjusted the CPs. The SAC-SAPSO achieved an improvement in performance of 52% relative to the constant CP baseline (76% on the training set), and 52% relative to the time-variant baseline (72% on the training set). The value of $n_t$ can, of course, still be considered as a CP, implying a reduction in the total number of parameters from three to one, in addition to the improvement in performance. If a search process without CPs is desired, the velocity-clamped SAC-SAPSO which automatically adapts $n_t$ (vc_sac_$n_t=$ auto) can be used. Velocity clamping proved useful, firstly to improve performance, but also to prevent the search process from becoming unstable with particle velocities growing unboundedly. All methods displayed a degree of invariance with respect to the choice of $n_t$, because all SAC methods outperformed all baselines, and all velocity-clamped SAC methods outperform all SAC methods.

Finally, the environment and agent were configured in an agnostic fashion; many swarm intelligence or evolutionary algorithms with tunable parameters can, therefore, be “plugged into” the framework in order to find an adaptive policy for its parameters.

7. Future Work

The environment currently only generates particle velocities, percentage stable particles, percentage feasible particles, and percentage completion of the search for the agent to observe. The agent could theoretically reconstruct a much more nuanced representation of the fitness landscape if it received positions or objective function values also, thereby leading to a more landscape-aware PSO. However, to counteract an explosion in computational complexity, dimensionality reduction techniques such as principal component analysis (PCA) or linear discriminant analysis (LDA) might have to be used to obtain a lower-dimensional representation of particle positions.

Furthermore, the action space $\mathcal{A}$ can be extended so that the agent may adjust the CP configuration per particle.

The algorithm was evaluated for only 5000 time-steps. An alternative option is to not set a hard limit on the maximum time-steps, thereby allowing the agent to use as few or as many time-steps as it deems necessary for the problem at hand. This may require the introduction of negative reward if the agent begins to exceed the computational budget. Similarly, the search could be terminated if the swarm converges or if improvement has stalled. The aforementioned could thus introduce adaptive behaviour to the search length also.

Similarly, negative reward can be used to punish the agent proportionally to the number of particles which leave the feasible search space. While this will definitely lead to more stable CP configurations and less infeasible particles, care must be taken when introducing such an inductive bias, as it might also degrade performance since the agent would then no longer optimise purely with respect to performance. However, artificially encouraging convergent search behaviour might very well lead the agent to find better solutions, as it helps to prevent the SAC from choosing a CP configuration which lies outside of the convergent CP region.

The performance of the SAC-SAPSO on dynamic optimisation problems will also be studied.