RLEMMO: Evolutionary Multimodal Optimization Assisted
By Deep Reinforcement Learning

Several works have made significant contributions for solving MMOPs by enhancing evolutionary computation from various perspectives.

The first aspect of the improvement involves integrating Evolutionary Computation (EC) with niching methods to enhance the diversity of the population during optimization. Thomsen et al. (Thomsen, 2004) proposed Crowding DE, which combines differential evolution with the crowding method. Each offspring replaces the nearest individuals if it has a better fitness. Qu et al. (Qu et al., 2012) introduced a locally informed particle swarm optimizer to enhance niching PSO by combining several local best solutions in the vicinity of each particle to guide the velocity update. Li et al. (Li, 2009) proposed a ring topology PSO that eliminates the need for an extra parameter. The swarm is divided using a ring topology. Zhang et al. (Zhang et al., 2023) proposed a method for choosing parents based on proximity ranking, where the probabilities of selecting neighbors as parents are determined by their distance from the individual. To adaptively adjust niching radii to align with the dynamical optimization process, Zhang et al. (Zhang et al., 2019) proposed VNCDE, which first constructed a Voronoi neighborhood for each individual and thereby adaptively assigned desired searching strategies within the neighborhood. Luo et al. (Luo et al., 2020) proposed an adaptive nearest-better neighbor clustering method for characterizing basins of attraction, which not only significantly enhances the diversity during the optimization process, but also provides flexible convergence.

The second aspect of the improvement leans utilizing an archive to assist optimization with historical experience. In particular, The dADE method (Epitropakis et al., 2013) identifies redundant individuals for reinitialization using an archive that stores promising solutions. Huang et al. (Huang et al., 2020) proposed storing historical information in an enhanced binary space partitioning tree, dividing the space with the tree to aid optimization. Liao et al. (Liao et al., 2023) developed a history archive-assisted niching differential evolution with variable neighborhood, using the information from the archive to control the size of the neighborhood and change it during the evolution process. Wang et al. (Wang et al., 2020) proposed a parameter-free niching method based on adaptive estimation distribution, where each individual estimates the distribution of the environment based on nearby neighbors and decides the size of the niching.

As for the third aspect of the improvement, several recent works solve MMOPs through transforming them into multi-objective optimization problems (MOOs). These works commonly considered two objectives: the solution quality and the solution diversity of the population (Deb and Saha, 2012; Bandaru and Deb, 2013). Wang et al. (Wang et al., 2014) highlighted the significance of conflicts between the two objectives and proposed a novel method to efficiently construct conflict objectives for problem transformation. Cheng et al. (Cheng et al., 2017) transformed MMOPs into multi-objective problems using multi-objective EAs to obtain an approximate fitness landscape and then detected peaks based on stored historical samples. A local search method was applied to optimize the global optima.

Though promising results have been achieved by the above evolutionary multimodal optimization methods, they often require intricate manual tuning with deep expertise to secure the desirable performance for unseen tasks. The labour-intensive design process of these human-crafted methods hinders both the efficiency and effectiveness of solving MMOPs.

Recent Meta-Black-Box Optimization (MetaBBO) approaches (Ma et al., 2023; Chen et al., 2024; Guo et al., 2024), facilitate a bi-level optimization scheme to meta-learn a parameterized control policy in a data-driven way, which configures the low-level black-box optimizer during the optimization process to mitigate the design efforts required for unseen tasks.The parameterized control policy at the meta level can be optimized in various ways (e.g., supervised learning (Chen et al., 2017; TV et al., 2019; Gomes et al., 2021), reinforcement learning (Sharma et al., 2019; Tan and Li, 2021; Sun et al., 2021), and self-referential searching (Gomes et al., 2021; Lange et al., 2023a, b)). Take MetaBBO with reinforcement learning (MetaBBO-RL) as an example, it models the fine-tuning of the optimizer as a Markov Decision Process (MDP) and trains an agent to make decisions regarding algorithmic configurations at the meta-level. At each step $t$, the agent queries the optimization status $s_{t}$, and the policy $\Pi_{\theta}$ uses $s_{t}$ as input to suggest an action $a_{t}$ for configuring the optimizer at the lower level. The environment then executes $a_{t}$ to obtain a new status $s_{t+1}$. A reward $r_{t}$ is generated to measure the meta-performance improvement of the optimizer at the lower level. Subsequently, the agent at the meta-level can be trained based on the rules of reinforcement learning. The action space of MetaBBO-RL can involve dynamically selecting evolutionary algorithms/operators (Guo et al., 2024; Sharma et al., 2019; Tan and Li, 2021), controlling hyper-parameters (Sun et al., 2021; Wu and Wang, 2022), or generating interpretable update rules (Chen et al., 2024). This paper shares the similar ambition with the MetaBBO-RL for selecting algorithms/operators. Along this research branch, Sharma et al. (Sharma et al., 2019) trained a Deep Q-Network (DQN) (Mnih et al., 2015) to dynamically select the mutation strategy for the backbone DE optimizer, for each individual based on the timely optimization status. Guo et al. (Guo et al., 2024), on the other hand, propose leveraging Proximal Policy Optimization (PPO) (Schulman et al., 2017) to train an RL agent which selects suitable optimizer to optimize the problem for different optimization phases, enhancing the final optimization performance. To the best of our knowledge, in the domain of using MetaBBO-RL to solve MMOPs, Xia et al. (Xia et al., 2021) proposed to use Q-Learning to select solutions within the approximated basin of attraction, which balances the quality and diversity of the solutions during the optimization. However, this method needs re-training for unseen problems, lacking of the ability of generalization.

KNN (Cover and Hart, 1967) identifies the class of point $X_{i}$ based on its $k$ neighbors. Firstly, the Euclidean distance between $X_{i}$ and other points is calculated as a measure of similarity. The $k$ points with the shortest distances are considered the k-nearest neighbors of $X_{i}$, and the class of $X_{i}$ is determined based on its neighbors. In this paper, the KNN method is used to construct the k-nearest neighborhood for each individual. Then, the features about the neighborhoods are calculated to provide local information to each individual, as described in Section 4.2.

Density-Based Spatial Clustering of Applications with Noise (DBSCAN) (Ester et al., 1996) is an unsupervised clustering algorithm. It is a non-parametric method based on density. For a set of points, the points that are closely packed together are grouped as clusters, while the points that lie alone in low-density regions are regarded as noise points. In this paper, RLEMMO utilizes DBSCAN to cluster the population in each generation, estimating the number of clusters and the members within each cluster. A novel reward mechanism based on the number of clusters and the best fitness within each cluster is designed to encourage the diversity and quality of the population during the optimization, as described in detail in Section 4.4.

Policy gradients is a method used to refine the Markov Decision Process (MDP) (Sutton and Barto, 1999). Given an MDP with the form $<S,A,\mathcal{T},R>$, the agent observes a state $s\in S$ and selects an action $a\in A$. The state $s$ transitions to $s^{\prime}$ according to the dynamics of the environment $\mathcal{T}(s^{\prime}|s,a)$, and the agent receives a reward $R(s,a)$ from the environment. The objective of RL is to find a policy $\pi_{\Theta}(a|s)$, parameterized by the model weights $\Theta$, that maximizes the cumulative discounted reward $E_{\pi_{\Theta}}(\sum_{t=1}^{T}\gamma^{t-1}R(s^{(t)},a^{(t)}))$, denoted as $J(\Theta)$. Policy gradients aim to maximize the expected value through gradient ascent. The gradient of $J(\Theta)$ with respect to $\Theta$, denoted as $\nabla J(\Theta)$, can be calculated as follows:

where $R^{(t)}$ represents the cumulative reward at time $t$. Due to the effectiveness of policy gradients, various extensions have been developed, such as REINFORCE (Williams, 1992), TRPO (Schulman et al., 2015), and PPO (Schulman et al., 2017). In this paper, we utilize PPO to refine the MDP of MMOPs.

The attention mechanism (Vaswani et al., 2017) is calculated as follows:

where $Q$, $K$, and $V$ are vectors representing the query, key, and value, respectively. These vectors are computed by weighting the input sequence with $W_{q}$, $W_{k}$, and $W_{v}$. The value of $d_{k}$ represents the dimension of the key vector and is used for result normalization. In the case of the self-attention mechanism, $Q$, $K$, and $V$ are derived from the same source sequence.

The multi-head attention mechanism maps vectors to different subspaces to enhance representation. Each attention head independently calculates $Q_{i}$, $K_{i}$, and $V_{i}$. The outputs of all heads are then concatenated together to produce the final result of the multi-head attention module:

In our work, we utilize an attention module to enhance information sharing among the individuals in RLEMMO.

Our RLEMMO is a Meta-Black-Box Optimization framework with Reinforcement Learning (MetaBBO-RL), which follows a bi-level optimization approach. For a given MMOP, the bi-level optimization is carried out as follows: At the lower level MDP, starting with an initial solutions population $X^{(0)}$, an RL agent (a policy network) dynamically switches diverse searching strategies for each individual in the population at each time step $t$ along the lower level optimization process. The solutions population is advanced from $X^{(t)}$ to $X^{(t+1)}$ using the strategy sampled from the RL agent, and emits a reward back to the RL agent. At the meta level, the RL agent is trained to maximize the expectation of the accumulated reward (meta objective) over a MMOP distribution. The blueprint of RLEMMO is illustrated in Figure 1. The components of the low-level MDP, including the optimization state representation, the solution-level optimization strategies (action), and the reward design, are detailed in Section 4.2, 4.3, and 4.4 respectively. A step-by-step derivation of the RLEMMO’s workflow is provided in Section 4.5.

In RLEMMO, we incorporate Fitness Landscape Analysis (FLA) (Pitzer and Affenzeller, 2012) and Exploratory Landscape Analysis (ELA) (Mersmann et al., 2011) to profile the optimization status of the solution population during the optimization process, which are commonly adopted in recent MetaBBO approaches (Sharma et al., 2019; TV et al., 2019). In specific, we utilize an individual-level feature $f_{\text{ind}}$ to analyze the status of each individual, as well as an additional neighbor-aware population feature $f_{\rm{pop}}=\{f_{g},f_{n}\}$, consisting of two parts: $f_{g}$ profiles the distributional features considering the entire population, and $f_{n}$ describes the local information around each individual. Feature $f_{\text{pop}}$ complements $f_{\text{ind}}$ and helps inform the meta-level RL to coordinate exploration and exploitation in the lower-level optimization. Note that we also inject the evolution-path information into the optimization status, such as stagnation and historical best solutions, to reflect the experience of the evolutionary history. The detailed formulas and descriptions of the state representation are presented in Table 1. We leave the per-feature exegesis at Appendix A.

We provide five optional searching strategies that vary in the extent of exploration and exploitation to enrich the behavioral diversity of the low-level optimization process. Given the optimization state $f_{\text{pop}}$ and $f_{\text{ind}}$ of the individuals in the current solution population, we allow the RL agent to choose the appropriate strategies for each individual to match the up-to-date optimization status. We use $A$ to denote the action (selected strategies) for all individuals, and $A_{1}\sim A_{5}$ to denote the five strategies respectively. These strategies are briefly introduced as follows:

1. A₁:

   Inspired by VNCDE (Zhang et al., 2019), the first strategy is the Gaussian-based local search strategy, which perturbs the individual to search for a local optimum in a narrow range. Its formulation for the $i$-th individual $X_{i}$ is shown below:

   (4)

   $$U_{i}=X_{i}+G(0,\sigma)$$

   where $G(0,\sigma)$ represents a random vector with values sampled from a Gaussian distribution with a mean of 0 and a standard deviation of $\sigma$. The setting for $\sigma$ follows the original VNCDE paper. $A_{1}$ can aid the convergence of the solution population when the solutions are approaching the global optima.
   

2. A₂:

   We propose a KNN-based neighborhood mutation strategy to enhance the exploitation of local optimization information. It is formulated as follows:

   (5)

   $$U_{i}=X_{i}+F\cdot(\Phi_{i}^{*}-X_{i})+F\cdot(\Phi_{i,r_{1}}-\Phi_{i,r_{2}})$$

   where $\Phi_{i}^{*}$ represents the best individual in the KNN-based neighborhood of $X_{i}$(denoted as $\Phi_{i}$), while $\Phi_{i,r_{1}}$ and $\Phi_{i,r_{2}}$ are two distinct random individuals selected from $\Phi_{i}$. $F$ denotes the scaling factor.
   

3. $\text{A}_{3}$:

   Additionally, we propose a KNN-based neighborhood mutation strategy to enhance the exploration of local optimization information. It is formulated as follows:

   (6)

   $$U_{i}=\Phi_{i,r_{1}}+F\cdot(\Phi_{i,r_{2}}-\Phi_{i,r_{3}})$$

   where $\Phi_{i,\cdot}$ represents distinct random individuals selected from $\Phi_{i}$. $A_{3}$ serves as a complement to $A_{2}$ to ensure comprehensive exploration within the local neighborhood area.
   

4. $\text{A}_{4}$:

   We propose a global exploratory mutation strategy that reinforces information sharing across different KNN-based neighborhoods.

   (7)

   $$U_{i}=X_{i}+F\cdot(\Phi_{j}^{*}-X_{i})+F\cdot(X_{r_{1}}-X_{r_{2}})$$

   Using the best individual in a randomly chosen neighborhood $\Phi_{j}$ as $\Phi_{j}^{*}$, the strategy allows $X_{i}$ to jump out of the current area and chase another optimum. The inclusion of two randomly selected individuals, $X_{r_{1}}$ and $X_{r_{2}}$, makes the process highly exploratory.
   

5. $\text{A}_{5}$:

   We adopt the well-known ”DE/rand/1” mutation strategy to thoroughly explore the entire search space.

   (8)

   $$U_{i}=X_{r_{1}}+F\cdot(X_{r_{2}}-X_{r_{3}})$$

   where $X_{r\cdot}$ represents randomly selected individuals from the population. We note that $A_{4}$ and $A_{5}$ facilitate an individual’s ability to escape from both local optima and locally best neighbors.

The aforementioned searching strategies exhibit diverse behaviors when applied to the individuals in the solution population. Considering that in RLEMMO, the search behaviour of the population is controlled by the RL agent in a fine-grained way, e.g., at the individual level. This presents an opportunity for RLEMMO to enhance low-level optimization performance through meta-learning a flexible policy.

In the case of MMOP, providing feedback to the meta-level RL agent during the low-level optimization process poses a challenge. In RLEMMO, the reward feedback should not only inform the RL agent about the potential optimization performance gain achieved by adopting a specific searching strategy for the next optimization step (e.g., DE-DDQN (Sharma et al., 2019), LDE (Sun et al., 2021)), but it should also make the RL agent aware of the diversity within the current solution population, thereby facilitating the discovery of more global optima later on. To address this, we propose a novel reward scheme, denoted as $R_{\text{clb}}$, which synthetically reflects the potential performance gain in both solution quality and diversity based on clustering estimation. Specifically, when the solution population $X$ advances from time $t$ to $t+1$, we first cluster the solutions in $X^{(t+1)}$ using the DBSCAN (Ester et al., 1996) method. Let ${C_{1},C_{2},...,C_{k}}$ represent the resulting $k$ clusters. We then evaluate the solutions in each cluster and denote the objective value of the best-performing solution in the $j$-th cluster as $f^{*}_{j}$. The clustering-based reward at time step $t$ is calculated as $R_{\text{clb}}^{(t)}(X^{(t)},A^{(t)})=\sum_{j=1}^{k}f^{*}_{j}$. The $R_{\text{clb}}$ strikes a balance between the quality and diversity of solutions in a way that if the meta-level RL agent in RLEMMO seeks higher rewards throughout the MDP episode, it should learn a flexible policy that efficiently locates all global optima as quickly and comprehensively as possible. We note that the proposed clustering-based reward scheme aids the efficient convergence of the meta-level RL agent while enhancing the population diversity within the low-level optimization process.

We will now outline the step-by-step workflow of our RLEMMO approach. Firstly, we introduce the network architecture used in RLEMMO, as illustrated in Figure 2. The network parameters $\Theta$ consist of four parts, namely $\Theta:=\{\Theta_{PE},\Theta_{IE},\Theta_{Actor},\Theta_{Critic}\}$, where: 1) $\Theta_{PE}\in\mathbb{R}^{10\times 32}$ and $\Theta_{IE}\in\mathbb{R}^{12\times 32}$ represent the MLP embedders for population features $f_{\text{pop}}$ and individual features $f_{\text{ind}}$, respectively. 2) $\Theta_{Actor}$ denotes the strategy decoder (actor in RL) responsible for strategy sampling. It includes a $4$-heads self-attention block with a hidden embedding dimension of $64$ and an MLP layer with parameters in $\mathbb{R}^{64\times 5}$. Note that we introduce the self-attention mechanism to enhance communication among individuals. 3) $\Theta_{Critic}\in\mathbb{R}^{64\times 1}$ represents the MLP critic network used for estimating return values in RL. For the sake of clarity, we will omit the time stamp $t$ in the following derivation.

At each time step of the low-level optimization process, we start by aggregating the population features $f_{\text{pop}}(X)$ and individual features $f_{\text{ind}}(X)$ of all individuals in the current solution population $X$. Subsequently, we pass these two groups of features through separate embedders to obtain the corresponding feature embeddings:

We then obtain the decision embeddings for all individuals by concatenating their respective population feature embeddings ($PE$) and individual feature embeddings ($IE$):

We feed the decision embeddings ($DE$) into the actor network and simultaneously sample the strategies ($A$) for all individuals from the soft distributions on its outputs, as defined in Section 4.3:

The expectation of the return values ($G(X)$) is obtained by feeding the decision embeddings ($DE$) into the critic network:

We present the pseudo code of the training workflow in our RLEMMO in Algorithm 1. In this work, we utilize the Proximal Policy Optimization (PPO) method (Schulman et al., 2017) to meta-train the networks. Once the training process is complete, the trained RLEMMO model can be employed to solve unseen problems. Note that during training, the strategy $A$ is sampled from the output distribution, while during inference, the strategy is selected greedily based on the maximum likelihood.

We report the optimization performance (averaged over $50$ independent runs) and the runtime complexity of our RLEMMO and the considered baselines in Table 2 and Table 3. The results demonstrate that:

1. Our RLEMMO demonstrates its effectiveness in solving MMOP. For the problems in the training set, RLEMMO achieves superior optimization performance compared to the baselines. On average, it locates more global optima (PR) and has more successful runs (SR). The optimization performance of RLEMMO on high-dimensional problems such as $F10$, $F12$, and $F19$ (which are challenging due to the large number of optima) demonstrates that the learned policy, which conditions on the up-to-date optimization status to flexibly switch the searching strategy, may be more effective in solving high-dimensional MMOP than the human-crafted rules used in the baselines.

2.The results on the test set highlight the potential generalization ability of RLEMMO. Once trained, RLEMMO is used to solve the problems in the test set without further fine-tuning. Although our algorithm does not rank the first in the comparison, we note that it demonstrates an acceptable level of generalization performance. The problems in the test set have different problem structures and landscape features. Despite this challenging setting, RLEMMO maintains competitive performance by achieving a similar PR performance to the best-performing NBNC-PSO-ES algorithm ($0.693$ versus $0.701$), while demonstrating a more robust searching performance considering the SR ($0.290$ versus $0.273$). Furthermore, we would like to clarify that the generalization ability of RLEMMO could be further improved by training on a problem distribution that includes various MMOPs, which is one of our future works.

3. RLEMMO demonstrates a more robust optimization performance across different landscape properties. We observe that some of the baselines encounter a significant performance drop across different problems, e.g., VNCDE from $F10$ to $F19$, and PNF-PSO from $F14$ to $F18$. Note that $F10$ and $F19$ have different problem structures, while $F14$ and $F18$ share the same structure but differ in dimensions. In contrast, RLEMMO exhibits a relatively small performance drop in these situations. This may reveal that the human-crafted rules in some baselines would fail to generalize across certain problem classes. RLEMMO, however, meta-learns to adaptively alter its searching pattern for fitting unseen problems.

4. From the results in Table 3, it is evident that RLEMMO exhibits an acceptable running complexity compared to other algorithms.

To validate the effectiveness of the core designs in our work, we conducted several ablation studies from different aspects, including the state representation, the action set, and the design of the reward. Figure 3 shows the average PR (blue bar) and SR (orange bar) on the test set at an accuracy level of $10^{-4}$.