Knowledge-guided multiobjective particle swarm optimization with fusion learning strategies

In general, an MOP can be defined aswhere x = (\(x_1\), \(x_2\), \(\ldots \) , \(x_D\)) \(\in \) \(\Omega \), \(\Omega \) represents the decision space, D is the dimension of decision vector x, M represents the number of optimization objectives, \(N_\mathrm{{I}}\) and \(N_\mathrm{{E}}\) are the number of inequality constraints and equality constraints, respectively. For MOPs, because there are conflicts among the optimization objectives, the goal is to obtain a set of compromise solutions determined by the Pareto dominance relationship [34].

A solution vector x strictly dominates the solution vector y, expressed as x \(\prec \) y , if and only if \(\forall \) i \(\in \) 1, 2, \(\ldots \), M, \(f_{i}(x)\) \(\le \) \(f_{i}(y)\) and at least the following holds: \(\exists \) j \(\in \) 1, 2, \(\ldots \), M, \(f_{i}(x)\) < \(f_{i}(y)\). If there is no solution x dominated by any other solution y, then this solution x is considered to be the Pareto-optimal solution. The set of Pareto-optimal solution is called Pareto-optimal set (PS), and its value in each objective space is called Pareto-optimal front (PF), which is denoted as:

The PSO algorithm was first proposed by Kennedy and Eberhart in 1995 for solving continuous optimization problems [35, 36]. It originates from the simulation of the foraging behaviors of flocks of birds. In PSO, a feasible solution of the problem is abstractly represented as a particle, and the optimal solution of the problem is found through evolutionary strategies that are different from that of evolutionary algorithms. Without loss of generality, particle i with D problem dimensions consists of three components, including the historically best position found by each particle, named \(\mathbf{Pbest} ^{d}_{i}=[pbest^{1}_{i}, pbest^{2}_{i}, \ldots , pbest^{D}_{i}]\), the current velocity \(\mathbf{v} ^{d}_{i}=[v^{1}_{i}, v^{2}_{i}, \ldots , v^{D}_{i}]\) and the current position \(\mathbf{x} ^{d}_{i}=[x^{1}_{i}, x^{2}_{i}, \ldots , x^{D}_{i}]\). In addition, during the evolutionary process, a global best position \(\mathbf{Gbest} =[gbest^{1}, gbest^{2}, \ldots , gbest^{D}]\), found by the entire population, is shared with each particle. The evolutionary strategy of the PSO algorithm is expressed as follows:where \(d=1, 2,\ldots , D\) represents the dth dimension of the optimization problem, \(\omega \) is the inertia weight that is used to balance the global and local searches during PSO, \(r_{1}\) and \(r_{2}\) are two uniformly random numbers in the interval [0, 1], and \(c_{1}\) and \(c_{2}\) are acceleration factors, representing the extent of influence of one’s own experience and that of the swarm on the evolution of the population, generally, they are set to 2.0 [37].

When addressing MOPs, the selection of individual and global leaders needs to be carefully considered. This is because there is no unique optimal solution for MOPs. Some common methods include stochastic methods, dynamic neighborhood strategies, niche techniques, and ranking-based methods [38‐40]. In general, The fewer global leaders choices, the greater the pressure is increased to the population, which results in a fast convergence but a poor diversity [41]. Therefore, the balance between population diversity and convergence speed is also the main factor affecting the algorithm’s performance. Some research shows that the population diversity of MOPSO algorithm is obviously insufficient, which leads to the failure of the MOPSO to obtain a set of outstanding nondominated solutions [42, 43]. Although the MOPSO algorithm has the advantage of fast convergence, it is easy to prematurely perform convergence activities when solving complex and high-dimensional MOPs. Therefore, based on the above analysis, the global leaders of all particles are appropriately selected from the external archive based on neighborhood knowledge in our proposed KGMOPSO algorithm. In addition, the population diversity is dynamically managed, which helps balance the exploration and development capabilities of the algorithm. The details are introduced in the next section.

Compared with other evolutionary algorithms, the evolution of the PSO algorithm is performed using the best experience of an individual and the entire population. This ensures that the PSO algorithm achieves a fast convergence speed and more efficient optimization performance [44]. However, it should be noted that when solving MOPs, the goal is to obtain a set of uniformly distributed Pareto-optimal solutions. The PSO algorithm tends to converge prematurely, and it is difficult to converge to the real PF. Therefore, in this paper, an effective knowledge-guided multiobjective particle swarm optimization algorithm is proposed to balance convergence and diversity.

Knowledge-guided search is a promising method for solving complex problems and it has been studied by many scholars in different fields [45, 46]. Zhao et al. proposed an OD-RVEA algorithm where the optimal solution of each subproblem is updated by a direction-guided variation strategy to achieve rapid convergence [47]. Their comparative experiment indicates that OD-RVEA offers preferable performance to those of preceding algorithms. Ghosh et al. proposed an efficient strategy in which the most promising evolutionary information from past generations is retained and used to generate offspring [48]. This strategy is integrated with the winners of the CEC, and the experimental results demonstrate that this leads to a significant improvement in the performance of the algorithm. The best search information is incorporated into the evolutionary process of the population, and the performance of the algorithm is effectively improved. Therefore, in this paper, a two-stage evolutionary strategy based on neighborhood knowledge search is proposed, as shown in Fig. 1. In stage I, two different leaders are selected from the external archive through the leader selection strategy based on the reference point angle, which is explained in detail in the following section. The evolution direction is constructed by the two extreme points that are selected from the external archive to guide the evolutionary process of the whole population. The nondominated solutions obtained by the KGMOPSO algorithm are expected to quickly identify the area where the real PF is located. The role of stage I is to enhance the global exploration capability of the algorithm. In stage II, the population approximates the PF based on the search results in stage I. Therefore, the local search capability of the algorithm needs to be strengthened gradually in order to obtain a set of outstanding nondominated solutions. The individual particle’s best experience is used as a guide particle to the evolution of the population. By using the best experience of each particle to guide the evolution of the population, the convergence ability of the algorithm may be limited to some extent, but the diversity of the population is enhanced gradually. Algorithm 1 gives the pseudocode for this strategy, and the details are shown in the following section.

Although the PSO algorithm achieves a fast convergence rate, it can easily and quickly lose population diversity when solving MOPs, which causes the algorithm to fail to converge to the real PF. Therefore, ensuring that the algorithm possesses sufficient population diversity during runtime is crucial to the optimization performance of the algorithm. An individual similarity detection technology is introduced to measure the diversity of the population for each generation, which is described as:where \(me^d\) is the average value of the population in the dth dimension, and \(x^d_\mathrm{{max}}\) and \(x^d_\mathrm{{min}}\) represent the maximum and minimum values of individuals in the dth dimension, respectively. By calculating the individual similarity of each generation, the diversity of the population can be dynamically measured. It is favorable to prevent the algorithm from falling into a local optimum.

There is no doubt that maintaining sufficient diversity is essential for promoting the search capabilities of the algorithm. Therefore, this paper proposes a new strategy to enhance population diversity. In this strategy, the Euclidean distance between individuals is calculated. The entire population is divided into two groups, and each group implements different mutation strategies to maintain the diversity of the population. The detailed steps are described below.

Step 1: Calculate the Euclidean distance between individuals in the decision space;

Step 2: Sort all the individuals, and select half of the individuals with the larger distance as one group (named group 1), and the rest as another group (named group 2).

Step 3: For group 1, when a random number is less than 0.5, the negation strategy is executed by Eq. (12); otherwise, a nondominated solution is randomly selected from an external archive for replacement.where \(\mathrm{{Upper}}(x_i^d)\) and \(\mathrm{{Lower}}(x_i^d)\) represent the upper and lower limits of the ith particle in the dth dimension, respectively.

For group 2, when a random number is less than 0.5, a Gaussian mutation strategy based on individuals and randomly selected leaders is performed by Eq. (13). On the contrary, the individual does not undergo any changes.where r is a random number in the interval [0, 1], \(g^d\) represents a nondominated solution randomly selected from the external archive, and \(N(\cdot )\) is a Gaussian distribution function.

In addition, the computational cost of the algorithm may increase when the diversity operation is excessively performed. An effective method is proposed to solve this problem. When the population similarity is lower than a preset threshold, it indicates that there are too many identical or similar individuals in the population, and the diversity enhancement strategy needs to be implemented. Otherwise, the diversity enhancement strategy is not implemented. To reasonably evaluate the similarity of individuals for each generation, this paper adopts a dynamic method for setting the threshold, as shown in Eq. (14).where C is a fixed constant, which is set to 0.45 in this paper.

In general, to obtain a uniformly distributed PF, the redundant individuals in the external archive should be deleted. In [1], the crowding distance is first used as a method to judge the distance between nondominated solutions. A large crowding distance means that the more dispersed the individuals are, the better the diversity of the population. Inspired by [49], this paper proposes a pair of improved crowding distances, which are called the maximum and minimum crowding distances. Through this strategy, the nondominated solutions with good distributions are retained as much as possible, in contrast, the nondominated solutions with poor distributions are removed. The calculation process of the maximum and minimum crowding distances mainly involves two steps. The first step is to calculate the crowding distances, which are used in [1], of the individual on each objective space, including the maximum distance \(\mathrm{{CD}}_\mathrm{{max}}\), minimum distance \(\mathrm{{CD}}_\mathrm{{min}}\), and average distance \(\mathrm{{CD}}_\mathrm{{average}}\). The second step is to calculate the proposed crowding distance of each individual using the criteria shown in Eq. (15).where m = 1, 2, \(\ldots \), M is the index of the objective function.

To clearly explain the maximum and minimum crowding distance strategies, a simple example is given, as shown in Fig. 3. Assume that there are four nondominated solutions distributed on the PF, in which nondominated solution 1 and nondominated solution 4 are extreme points need to be retained in the PF. The goal is to find a poor solution from nondominated solution 2 and nondominated solution 3. As shown in Fig. 3a, we first calculate the crowding distance of nondominated solution 2 and nondominated solution 3 in each objective space. From Fig. 3a, the crowding distance of nondominated solution 2 is equal to \(\mathrm{{CD}}_{21}\) + \(\mathrm{{CD}}_{22}\) and \(\mathrm{{CD}}_{31}\) + \(\mathrm{{CD}}_{32}\) for the nondominated solution 3. Secondly, the \(\mathrm{{CD}}_\mathrm{{max}}\), \(\mathrm{{CD}}_\mathrm{{min}}\), and \(\mathrm{{CD}}_\mathrm{{average}}\) are calculated according to the crowding distance between nondominated solution 2 and nondominated solution 3 in each objective space. Next, Eq. (14) is used to calculate the proposed maximum and minimum crowding distance of each nondominated solution. Finally, they are sorted in ascending order to delete the nondominated solution with the minimum crowding distance, as shown in Fig. 3b. The remaining solution is the nondominated solution that needs to be retained, as shown in Fig. 3c. The good nondominated solutions can be retained by setting the maximum and minimum crowding distances, and they realize the balance of convergence and diversity of the algorithm by incorporating the leader selection strategy.

Based on the above description, the KGMOPSO algorithm is composed of a knowledge-guided two-stage evolutionary strategy, an individual similarity measurement and diversity enhancement strategy, and a maximum and minimum crowded distance strategy. Through different evolution strategies, KGMOPSO can balance the global and local search capabilities well. The individual similarity detection technique is adopted to dynamically measure the diversity of the population, and the diversity is enhanced by the proposed diversity enhancement strategy. The improved crowding distance strategy is employed, and the nondominated solutions are screened to obtain the approximate real PF of the problem. In addition, a simulated binary crossover (SBX) and polynomial mutation (PM) are also incorporated into the KGMOPSO algorithm [50, 51]. In KGMOPSO, the update scheme of individual leader is that when the new individual dominates the current individual leader, the new individual is regarded as new individual leader. Half of the probability is used to select one of the individuals as the current individual leader if the two individuals do not dominate each other. Algorithm 3 gives the overall framework of the proposed KGMOPSO algorithm.

In this paper, two popular test instances, including the ZDT [52] and DTLZ test instances [53], are employed to show the high effectiveness of KGMOPSO. These test problems possess different landscape characteristics, such as multimodality, convexity and discontinuity. Therefore, it is very challenging to optimize these problems by using the proposed KGMOPSO and other multiobjective algorithms. The two test instances used in this paper contain a total of twelve MOPs, of which the first five test problems (i.e., ZDT1 to ZDT4 and ZDT6) are biobjective problems from the ZDT test instance. The last seven problems (i.e., DTLZ1 to DTLZ7) are three-objective problems from the DTLZ test instance. The number of decision variables is set as 30 for ZDT1-ZDT3 and 10 for ZDT4 and ZDT6. For the DTLZ1 test problems, M + 4 decision variables are used, DTLZ2-DTLZ6 use M+9 decision variables, and the last problem is set uses M + 19 decision variables, in which M is the number of objective functions. Table 1 gives the main features of these two benchmark instances.

In our study, to comprehensively analyze KGMOPSO, three quantitative performance metrics are adopted for all the chosen algorithms for performance evaluation, including the inverted generational distance (IGD) [54], the hypervolume (HV) [55] and the distribution indicator of a nondominated solution (spread) [1]. These three performance indicators quantificationally evaluate the multiobjective optimization algorithm in terms of the convergence, diversity and uniformity of the nondominated solutions. A small IGD or spread value and a large HV value obtained by any algorithm indicates that the optimization performance of the algorithm is remarkable and outstanding.

Let S represent a set of nondominated solutions that are uniformly sampled from the real PF and let \(S'\) be the set of nondominated solutions achieved by a multiobjective optimization algorithm. Therefore, the IGD metric can be described as:where \(i=1, 2, \ldots , |S|\), |S| is the number of nondominated solutions in S, and \(d(S, S')\) represents the minimum Euclidean distance between the ith member of S and any member of \(S'\). If the IGD value is smaller, it indicates that the distribution of the nondominated solution is closer to the real PF.

The HV metric can be explained as follows:where \(\delta \) represents the Lebesgue measure and \(c_m^r\) is the reference point in the mth objective space. In general, a larger HV value indicates that the quality of the nondominated solution obtained by the algorithm is reliable.

The spread indicator (\(\varDelta \)) is defined as follows:where N is the number of nondominated solutions, \(d_i\) represents the Euclidean distance from the ith nondominated solution to its neighboring solution, \(\bar{d}\) is the average value of \(d_i\), and \(d_f\) and \(d_l\) are the Euclidean distances between the extreme solution obtained by the algorithm and the boundary solution. If the spread value is smaller, it means that the distribution and quality of the nondominated solution obtained by the algorithm is satisfactory.

In our experiments, the performance of KGMOPSO is validated through comparisons with two existing state-of-the-art multiobjective evolutionary algorithms and four advanced multi-objective PSO algorithms, including NSGA-II [1], SPEA/R [4], dMOPSO [27], MPSO/D [28], MMOPSO [34] and NMPSO [5].

For a fair comparison, the population size for each algorithm is set to 100. If the algorithm requires an external archive, its size is set to 100. For each ZDT test problem, the maximum number of function evaluations and DTLZ test instances on each test problem for each algorithm is 100,000 and 200,000, respectively. Three performance indicators are calculated by using 500 points uniformly sampled from the true PF for the ZDT test instances and 5000–10,000 points for the DTLZ test instances. To reduce the influence of experimental error, each algorithm runs independently 25 times on each problem. The average value and standard deviation of the experimental results are given to compare the optimization performance of these algorithms. The source codes of all the above algorithms come from the PlatEMO platform [56]. Table 2 summarizes the main parameter settings for all the algorithms.