# An Improved Hybrid Algorithm Based on Biogeography/Complex and Metropolis for Many-Objective Optimization

Authors: Chen Wang; Yi Wang; Kesheng Wang; Yao Dong; Yang Yang
Journal: Mathematical Problems in Engineering
 (2017)

---

## Abstract

It is extremely important to maintain balance between convergence and diversity for many-objective evolutionary algorithms. Usually, original BBO algorithm can guarantee convergence to the optimal solution given enough generations, and the Biogeography/Complex (BBO/Complex) algorithm uses within-subsystem migration and cross-subsystem migration to preserve the convergence and diversity of the population. However, as the number of objectives increases, the performance of the algorithm decreases significantly. In this paper, a novel method to solve the many-objective optimization is called Hmp/BBO (Hybrid Metropolis Biogeography/Complex Based Optimization). The new decomposition method is adopted and the PBI function is put in place to improve the performance of the solution. On the within-subsystem migration the inferior migrated islands will not be chosen unless they pass the Metropolis criterion. With this restriction, a uniform distribution Pareto set can be obtained. In addition, through the above-mentioned method, algorithm running time is kept effectively. Experimental results on benchmark functions demonstrate the superiority of the proposed algorithm in comparison with five state-of-the-art designs in terms of both solutions to convergence and diversity.


---

## Body

## 1. Introduction

In the scientific research and engineering practice, multiple objectives are usually needed to be optimized simultaneously. Because of the conflict between multiple targets in multiobjective optimization, the performance improvement of one subobjective may cause the performance of another subobjective to decrease. Only through the compromise method can all objectives go as far as possible to attain optimal. The set of all the optimal Pareto optimal solutions is known as the Pareto set (PS) and their corresponding objectives vector in the objective space is the Pareto Front (PF) [1]. The purpose of many multiobjective optimization evolutionary algorithms (MOEAs) is to determine a better approximation of the PF and PS. Although Many MOEAs have effectively solved multiobjective optimization problems (MOPs) with only two or three objectives [2], the MOPs with more than three objectives are too difficult to be solved by most already existing MOEAs [3]. In the recent literature report, the MOPs that have more than three objectives are often described as many-objective optimizations (MaOPs) [4, 5].Due to the fact that minimization and maximization problem can be mutual transformation, without loss of generality, this article mainly describes minimizing many-objective problem and its related concepts MaOPs which can be defined as follows:(1)MinimizeFx=f1x,f2x⋯fnxTSubjecttox∈Ω,where x=x1,x2,…,xnT is the n-dimensional decision variable vector, Ω is the feasible search region, and F  : Ω→Rn consists of n objective functions fixi=1,2,…,n,n>3.It is generally agreed that, evolutionary algorithms (EAs) are well suited for MOPs, due to their population based strategy for achieving an approximation to the PF. EAs achieve a Pareto approximation set in MOPs via pursing the entire PF and maximizing the diversity of solutions. The fundamentally balanced convergence and diversity between the EAs depend on the selection operator [6]. As far as we know, the popular MOEAs, including Hypervolume Estimation Algorithm for multiobjective optimization (HYPE) [7], nondominated sorting genetic algorithm II (NSGAII) [8], and grid-based evolutionary algorithm (GREA) [9], could effectively deal with two or three objectives’ optimization problems. However, there MOEAs are all confronted with great difficulties in many-objective optimization. With the increase of the objective space in size, the first problem is almost all solutions to the original population becoming nondominated with one another, which is mainly caused by the phenomenon calleddominance resistance [10]. This will result in the selection pressure toward PF severely deteriorating and considerably slowing down the evolutionary process. This is primarily because most of EMO algorithms used Pareto dominance as selection criteria. The other problem is that the conflict between diversity and convergence becomes deteriorated. This is mainly because most of the current diversity operators (like crowding distance) prefer selecting the dominance resistant solutions. The third problem is the computational complexity and efficiency. With the increase of the number of objectives, the complexity of the EMO algorithm is significantly increased, and the efficiency of the algorithm is substantially reduced. To tackle the above problems, a lot of methods have been proposed [11, 12], which can be roughly divided into mainly four categories:(1)
The dimensional reduction–based methods: by analyzing the relationship between objectives or using feature selection techniques, this method reduces the amount of objectives. In order to decrease the difficulty of the original problem, this method attempts to reduce those unimportant objectives. However, the method assumes that the MaOPs have redundant objectives. This assumption may restrict the application of the dimensional reduction–based methods [13].(2)
The relaxed Pareto-dominance-based methods: the relaxed Pareto-dominance-based methods enhance the selection pressure on the Pareto Front, such as the methods ofα-dominate [14] and ε-dominate [15]. But the main drawback of this method is that it involves one or more parameters and these parameters are difficult to choose.(3)
The indicator-based approaches: the indicator-based method is not subject to the selection pressure problem, since it is not depending on the Pareto-dominance to push the population toward the PF. However, it has also suffered from thecurse of dimensionality [16]. The current metrics available to Hypervolume is probably the most popular one that is employed for multiobjective search. However, computation cost of the Hypervolume grows exponentially with the number of objectives [17].(4)
The decomposition-based method: this method has developed the decomposition strategy and the neighborhood concept. As one of the popular algorithms, many-objective evolutionary algorithm based on decomposition (MOEA/D) was proposed by Zhang and Li (2007) [18]. The aggregation function is used to compare the solutions and the uniform distribution weight vectors preserving solution convergence and diversity.MOEA/D has a good convergence and diversity, with low computational complexity, so as to get an effective method. With the BBO/complex algorithm decomposition option, each subsystem has multiobjectives and multiple constraints [19]. It has more flexible decomposition options compared to traditional methods founded on decomposition. BBO/complex detailed explanations are introduced in Section 2. Despite the advance in adapting MOEAs for leading with MaOPs, very few have been recorded in the sense of improving BBO/complex for solving MaOPs so as to balance both convergence and diversity simultaneously. We present a new algorithm, the hybrid Metropolis BBO/Complex (Hmp/BBO) for many-objective optimization; Hmp/BBO, under the basic framework of BBO/Complex algorithm, improves the convergence and diversity in many-objective optimization by introducing the decomposition strategy and PBI aggregation function in MOEA/D.Furthermore, selection in BBO/complex plays a major role in the information exchange among subsystems. We hope the useful information can be forwarded to the appropriate subsystems to improve them and will not mislead other unsuitable subsystems. In the original version of BBO/complex, the roulette wheel selection is based on the emigration rates to select the emigration islands. On the stage of within-subsystem migration, each SIV in an immigrating island will have a chance to be replaced by SIV from an emigrating island. However, it is not clear whether the new emigration islands are suitable for these subsystems. During the within-subsystem migration phase, some solutions with high quality are easily found at initial search stages, and they will be replaced easily by most current solutions. Consequently various subsystems will be trapped at their local convergence. The simulated annealing (SA) algorithm was proposed by Kirkpatrick et al. [20] and Černý [21]. SA is an intelligent algorithm based on probabilistic stochastic search optimization. It has the capability of potential jumping, and it can accept noninferior solution and inferior solution. Therefore, it effectively avoids falling into the local minimum solution and keeps solutions diversity. We are inspired here by the Metropolis criterion of SA algorithm to solve the problem posed above. Details about SA will be introduced in next section.On the other hand, when sharing information in the subsystem, because there are numerous objectives and constraints, we need a new method to reduce the computation time of the central processor.From discussion above, this paper mainly focuses on the Hmp/BBO algorithm that promotes the performance of convergence and diversity in many-objective optimization. Our contributions to this topic are summarized as follows:(1)
We have designed a new framework of Hmp/BBO algorithm for many-objective optimization.(2)
We have introduced PBI aggregation function to improve the convergence and diversity for Hmp/BBO.(3)
We have to adopt the Metropolis criterion to improve the performance of exploration and exploitation.(4)
We have introduced a checking unit; this unit ensured that the new islands are only generated within the Hmp/BBO, so it has saved an additional amount of CPU time.The remainder of this paper is organized as follows: the principles of BBO/Complex and SA are, respectively, covered in Section2. The hybrid Metropolis BBO/Complex algorithm (Hmp/BBO) is presented in Section 3. In Section 4, the experimental studies are given to demonstrate the efficiency of the proposed method as well as some discussions on this paper. Finally, Section 5 concludes the paper and future research directions are proposed.


## 2. BBO/Complex and Simulated Annealing

### 2.1. BBO/Complex

The biogeography-based optimization algorithm is an inventive algorithm, introduced for the first time in 2013, and according to [19] it provides competitive optimization performance with NSGAII [8], differential evolution (DE) [22], ant colony optimization (ACO) [23], and a lot of other algorithms. BBO/Complex extends BBO algorithm system of multiple subsystems; each subsystem contains multiobjectives and multiconstraints. The BBO/complex framework comprises N archipelagos, where N equals the number of subsystems. Each archipelago appears to have a lot of islands. These islands represent candidate solutions to the problem. BBO/complex framework is distinct from other MOEA algorithms. It includes framework and optimization algorithm, as showed in Figure 1. It provides an efficient model for communication between subsystems and provides a new way of migrating to share information between within-subsystems and cross-subsystems.Figure 1
BBO/Complex formulation.The classical BBO/Complex algorithm proposed can be described with the following algorithm:(1)
Initialize the control parameters: population size, stop condition, and mutation probability. Initialization of the population is initialized by randomly generated individuals.(2)
Get the objective and constraints value similarity levels between all pairs of subsystems.(3)
Obtain the rank of islands in each subsystem.(4)
Perform within-subsystem migration.(5)
Perform cross-subsystem migration.(6)
Mutation on each island.(7)
Replace the worst island in the population with the generation’s good islands.(8)
If the termination condition is not met, go to step(3); otherwise, terminate.


### 2.2. Simulated Annealing Algorithm

The algorithm is built on the metaheuristic technique of thermodynamics of material annealing [24–26]. At the beginning of the process the temperature rises and it is gradually cooled down to a minimum. The objective is to minimize the cost function and is expected to reach the lowest cost function for the freezing temperature. When the process is there, the temperature decreases and a new state is created. A simulated annealing algorithm based on statistical mechanics is established. In 1953, [27] adopted the concept of Boltzmann’s probability distribution. This means that if a system maintains its thermal equilibrium at temperature T, the probability distribution P of its energy E can be calculated by the following [27]:(2)PE=-ΔEeKBT,where KB is Boltzmann’s constant. The difference in energy ΔE means the difference in cost function between the past and current iterations, which can be determined as follows:(3)ΔE=fxn-fxo.For minimization problems, ΔE⩽0 means f(xn)⩽f(xo), so the new point is directly accepted. Otherwise, the Metropolis criterion will be enabled to decide whether to accept or reject xo. For this case where ΔE>0, the acceptance is treated probabilistically according to the relation P=1/1+e(ΔE/max(T)). It can be seen that it is affected by the temperature of the receiving process. For the maximum amplitude of T, the acceptance probability is also selected to be a much worse state too. This process will avoid falling into local optima. As the temperature decreases, the algorithm accepts only states which minimize the F0 cost. Thus, in the iterative process, the temperature reduction way is one of the key parameters, which is named as the cooling schedule. On the other hand, once the iteration n is complete, the next cycle will begin with a smaller value. Therefore, the number of cycles in L and the number of iterations N per each cycle are crucial settings. Large N and L lead to better performance but with a longer process time, and vice versa, for small N and L, based on the need to choose a compromise between the quality of the solution and the processing speed. The Metropolis criterion can help the algorithm balance the performance of exploration and exploitation.


## 2.1. BBO/Complex

The biogeography-based optimization algorithm is an inventive algorithm, introduced for the first time in 2013, and according to [19] it provides competitive optimization performance with NSGAII [8], differential evolution (DE) [22], ant colony optimization (ACO) [23], and a lot of other algorithms. BBO/Complex extends BBO algorithm system of multiple subsystems; each subsystem contains multiobjectives and multiconstraints. The BBO/complex framework comprises N archipelagos, where N equals the number of subsystems. Each archipelago appears to have a lot of islands. These islands represent candidate solutions to the problem. BBO/complex framework is distinct from other MOEA algorithms. It includes framework and optimization algorithm, as showed in Figure 1. It provides an efficient model for communication between subsystems and provides a new way of migrating to share information between within-subsystems and cross-subsystems.Figure 1
BBO/Complex formulation.The classical BBO/Complex algorithm proposed can be described with the following algorithm:(1)
Initialize the control parameters: population size, stop condition, and mutation probability. Initialization of the population is initialized by randomly generated individuals.(2)
Get the objective and constraints value similarity levels between all pairs of subsystems.(3)
Obtain the rank of islands in each subsystem.(4)
Perform within-subsystem migration.(5)
Perform cross-subsystem migration.(6)
Mutation on each island.(7)
Replace the worst island in the population with the generation’s good islands.(8)
If the termination condition is not met, go to step(3); otherwise, terminate.


## 2.2. Simulated Annealing Algorithm

The algorithm is built on the metaheuristic technique of thermodynamics of material annealing [24–26]. At the beginning of the process the temperature rises and it is gradually cooled down to a minimum. The objective is to minimize the cost function and is expected to reach the lowest cost function for the freezing temperature. When the process is there, the temperature decreases and a new state is created. A simulated annealing algorithm based on statistical mechanics is established. In 1953, [27] adopted the concept of Boltzmann’s probability distribution. This means that if a system maintains its thermal equilibrium at temperature T, the probability distribution P of its energy E can be calculated by the following [27]:(2)PE=-ΔEeKBT,where KB is Boltzmann’s constant. The difference in energy ΔE means the difference in cost function between the past and current iterations, which can be determined as follows:(3)ΔE=fxn-fxo.For minimization problems, ΔE⩽0 means f(xn)⩽f(xo), so the new point is directly accepted. Otherwise, the Metropolis criterion will be enabled to decide whether to accept or reject xo. For this case where ΔE>0, the acceptance is treated probabilistically according to the relation P=1/1+e(ΔE/max(T)). It can be seen that it is affected by the temperature of the receiving process. For the maximum amplitude of T, the acceptance probability is also selected to be a much worse state too. This process will avoid falling into local optima. As the temperature decreases, the algorithm accepts only states which minimize the F0 cost. Thus, in the iterative process, the temperature reduction way is one of the key parameters, which is named as the cooling schedule. On the other hand, once the iteration n is complete, the next cycle will begin with a smaller value. Therefore, the number of cycles in L and the number of iterations N per each cycle are crucial settings. Large N and L lead to better performance but with a longer process time, and vice versa, for small N and L, based on the need to choose a compromise between the quality of the solution and the processing speed. The Metropolis criterion can help the algorithm balance the performance of exploration and exploitation.


## 3. The Hybrid Metropolis BBO/Complex Algorithm

### 3.1. Framework of Proposed Algorithm

Hmp/BBO uses the original BBO/complex framework but extends it to multiple subsystems environments to accommodate many-objective optimization problems. First, many-objective problems are decomposed into multiple subsystems. Generally speaking, there are two decomposition methods: one is built on the system requirements and the other is based on the physical system; also the number of subsystems is set by the user according to the decomposition strategy. The original BBO/complex decomposes the problem based on system requirements. Because the objective space dimension is higher, we need to use the new decomposition method. Afterwards, like Figure2, a PBI aggregate function decomposition method can enhance the convergence and diversity of the algorithm when solving many-objective problems. With the above step, Hmp/BBO migration is divided into two categories: within-subsystem and cross-subsystem. During the within-subsystem migration phase, we enhance the probability of the solution and employ the Metropolis criterion to make the algorithm jump out of local optimal. During the cross-subsystem migration stage, we adopt the roulette wheel method to get best solution. Then we perform mutation and clear the duplicate algorithm.Figure 2
Illustration of decomposition strategy and PBI distance.Our algorithm does not take into account constraints problem. Constraints processing research questions will be in the rest of the work. Algorithm1 presents the general framework of Hmp/BBO.Algorithm 1:Hmp/BBO pseudocode.
Output:population p
(1) Initialization all the parameters
(2) generating parent population, weighting vectors and neighborhood index set
(3) decomposition strategy
(4) while the termination condition is not metdo
(5)  calculate the nondominated ranking system in subsystem
(6)  perform within-subsystem migration
(7)  perform cross-subsystem migration
(8)  perform mutation
(9)  clear the duplicate solution
(10)  replace the worst solutions with good islands
(11)  end while
(12) return p


### 3.2. Generating Weighting Vectors

We set weight vectors such that the optimal solutions of their subsystems are uniformly distributed along the PF. Most of the approaches for generating weight vectors for different decomposition strategies in MODE/D have been suggested [28]; we use Das’s method in [29], with a predefined integer H which controls the divisions along each axis. The total number of such vectors is N=CH+m-1m-1. Distributed reference points are λk=xk/H,k=1,2,…,m. Taking the three-dimension problem as an example, there are C52=10 reference points.


### 3.3. Decomposition Strategy

The Hmp/BBO initialization generatesNw weight vectors; PBI aggregate function [30] is employed to divide the weight vectors into a set of Ls (CO1,CO2,…,COL). Because the weight vectors uniformly distribute in the objective space, the number of weight vectors in one subsystem is approximate to Nw/L. Therefore, the whole objective space is divided into Ls subsystems.


### 3.4. The Nondominated Ranking System (NDRS)

NDRS was introduced in [31] as the ranking system in the multiobjective genetic algorithms (MOGA). It uses inconsecutive integers as ranks to reflect the relative performance of each individual in a population. Assume that we have a subsystem: Ri is the rank of the ith island, where a lower rank is better. If objective o1 of island i1 is better than o1 of i2, Ri2=Ri2+1; if objective o1 of island i2 is better than o1 of i1, Ri1=Ri1+1.


### 3.5. PBI Aggregate Function

In MOEA/D, several methods have been proposed for decomposing MOPs into a single-objective optimization subproblem, such as weighted sum method, Tchebycheff method, and Penalty-based Boundary Intersection (PBI) method, but it was shown that the MOEA/D-PBI is only best for many-objective optimization problem in [32]. This paper uses the PBI approach. A scalar optimization function is defined as(4)Mingpbixλ,Z∗=d1+θd2d1=z∗-FxTλλd2=Fx-z∗-d1λ.In Figure 2, Z∗ is the ideal point, d1 is the Euclidean distance between origin point and the foot point drawn from the solution to the reference direction, and d2 is the perpendicular distance of the solution from the reference direction. The θ value on the performance of Hmp/BBO is present in Section 4.3.


### 3.6. Within-Subsystem Migration

Within-subsystem migration is mainly for information sharing; we need a new rapid method for selection of immigration islands and emigration islands. First, immigrating islands are selected based on the NDRS. Afterward, emigrating islands are selected by emigration rates, in order to further improve the algorithm’s convergence speed, while avoiding falling into local optima. Features (n SIVs) of the islands will not be directly substituted with the new values that come from the probabilistically selected original islands mentioned above. Instead, n SIVs of the islands are maintained in two temporary matrices with size t1×t2. Each row of the matrices represents one individual. The old independent variables are used again if and only if the modified individual exhibits lower solution quality and does not comply with the Metropolis criterion. The inferior migrated island will be selected only if they pass the Metropolis criterion of SA. With this restriction on the with-subsystem migration, the Hmp/BBO algorithm can avoid falling into the local optimum. The algorithm is described in Algorithm 2.Algorithm 2:Within-migration pseudocode.
(1) Probabilistically choose the immigrating islands based on the NDRS.
(2)  Use the Metropolis criterion based on emigration rates to select the emigrating island.
(3) each SIV in an immigration island will have a chance to be replaced by an SIV from an emigrating island.


### 3.7. Cross-Subsystem Migration

During cross-system migration of the stage, it is desirable that the migration should be chosen from a neighborhood subsystem as much as possible. In Hmp/BBO, each island is uniquely specified by a weight vector; each weight vector has been assigned based on the Euclidean distance from a neighborhood. So we can select islands from its neighboring subsystems by neighboring index. First, we select islands between subsystems based neighboring index setE(i). Second, emigrating islands are selected based on the PBI distance. Furthermore, we need to eliminate those poor candidate islands to improve the algorithm diversity between subsystems. The inferior migrated island will not be selected unless it passes the roulette wheel method. With this restriction on the cross-subsystem migration, the Hmp/BBO algorithm’s diversity performance can be enhanced. The algorithm is described in Algorithm 3.Algorithm 3:Cross-migration pseudocode.
(1) Randomly select k indices from E(i) (choose similar subsystem) and select k immigrating islands based on
immigration rages from populationp.
(2) Calculate Euclidean distance between the islands of neighboring subsystem
(3) Use the roulette wheel selection based on emigration rates to select the emigrating islands.
(4) each SIV in an immigration island will have a chance to be replaced by an SIV from an emigrating island.


### 3.8. Mutation Algorithm

In the Hmp/BBO, these events are modeled as SIV mutation. The mutation ratemi can be determined by the following number of species involved in the probability pi to the following equation: (5)mi=mmax1-pipmax,where the mmax and pmax=max(pi) are a user-predefined maximum mutation rate that mi can reach. The ISI is the variable and function of SIV. The mutation processes are described in Algorithm 4.Algorithm 4:Mutation pseudocode.
(1) for  i←1 to k do
{whereL=numberofislands}
(2)  Calculate probability Pi based on λi and μi
{byiterativemethod}
(3)  Calculate mutation rate mi
(4) ifrand < mi and i≥Rm  then  {Rmisapredefinedmutationrange}
(5) Replace n SIVs vector of ISIi with a randomly generated n SIVs vector
(6) end if
(7) end for


### 3.9. Clear the Duplicate Algorithm

Clear duplication will increase the diversity of solutions and avoid duplication of features on other islands. The algorithm can be described in Algorithm5.Algorithm 5:Clear duplication pseudocode.
Require:Check all n SIVs on all ISIi
(1) whilethere is a duplicated SIVdo
(2) fori←1 to l do {wherel=numberofislands}
(3) if any duplicated SIVs is detected then
(4)  Replace the duplicated SIVs in ISIi with a randomly generated SIVs
(5) end ifIn conclusion, The Hmp/BBO would prove the performance of convenience and diversity by introducing a new framework for many-objective optimization. In addition, the SA algorithm comes with only one individual, while the Hmp/BBO is a population based algorithm. Instead of running SA with only one island, it can be executed with all islands in subsystems. Thus, internal searching loopsL of SA with each cycle of n can be invalid in Hmp/BBO without affecting the solution quality. This method will save one significant amount of CPU time. By these methods, the exploration and exploitation of the Hmp/BBO algorithm are much improved. The Hmp/BBO framework is described in Algorithm 6.Algorithm 6:Hybrid Metropolis Biogeography/Complex Based Optimization.
(1) Initialization with all the parameters. Initialization Nw weight vectors, CL are the center of the weight vectors cluster. Ls are the
number of subsystems and neighborhood set of weight vectorsE(i).
(2) Decomposition strategy
(3)forg←1 to G do {G=numberofgenerations}
(4) Calculate the rank of islands in each subsystem (NDRS)
(5) Probabilistically select the immigrating islands based on the islands rank, probabilistically select the emigrating islands based
on the emigration rates.
(6)  if  g=1  then
(7)     find the initial temperature T1
(8)   else
(9)    Update the temperature for the gth generation
(10)  end if
(11) Save the vectors of all the populations (before migration) in matrix mm1 with size t1∗t2 and their cost functions vector vv1
with lengthk.
(12) Do within-subsystem migration.
(13) Save the vectors of all the populations (after migration) in matrix mm2 with size t1∗t2 and their cost functions in vector vv2
with lengthk.
(14)for  i←1 to kdo (k is number of islands)
(15) CalculateΔE=V2(i)-V1(i)
(16)ifΔE>0  then
(17)P(E)=-ΔEeTgKB
(18)ifP(E)> rand  then
(19)   Acceptmm2(I,1→n) vector of matrix mm2 as an updated population for ISI
(20)else
(21)   Re-select the past mm1(I,1→n) vector of matrix mm1 as an updated population for ISIi
(22)end if
(23)end if
(24) Randomly selectk indices from E(i) and select k immigrating islands based immigration rates.
(25)ifgpbi(xnew∣w,z∗)⩽gpbi(x∣w,z∗)
(26) save the best islandsxnew for emigrating
(27)else
(28) Save the vectors of all the populations (before mutation) in matrix mm3 with size t3∗t4 and their cost functions in vector vv3
with lengthk
(29) Do cross-subsystem migration
(30) use the roulette wheel method to select population
with lengthk.
(31) Do mutation
(32)  Do clear duplicated SIV
(33)  ifg>1 then
(34)    Repalce the worst ISI with the good ISI saved in the elitism stage
(35)     end if
(36)     end for
(37)     display the best islands
(38)end if
(39)end if
(40)end if
(41) Do mutation
(42) Do clear duplicated SIV
(43)if  g>1  then
(44) Replace the worst ISI with the good ISI saved in the elitism stage
(45)end if
(46)end for
(47) Display the best islands.


### 3.10. Computational Complexity of One Generation of Hmp/BBO

In this section, we discuss the computational complexity of the Hmp/BBO. For a population sizeN and a problem of M objectives, the major computational costs are in steps (5), (6), and (7) of Algorithm 1. Step (5) is the computational complexity of NDRS; it requires O(NM) computations. Computing of within-subsystem (step (6)) needs O(LN12) computations, where L is cycles of Metropolis and N1 is generated by parents’ populations. Cross-subsystem migration (step (7)) needs O(LN12R) computations and R is equal to the number of subsystems. So for M objectives, reviewing all the above computations, the overall complexity of one generation of Hmp/BBO is O(NM+LN12+LN12R).


## 3.1. Framework of Proposed Algorithm

Hmp/BBO uses the original BBO/complex framework but extends it to multiple subsystems environments to accommodate many-objective optimization problems. First, many-objective problems are decomposed into multiple subsystems. Generally speaking, there are two decomposition methods: one is built on the system requirements and the other is based on the physical system; also the number of subsystems is set by the user according to the decomposition strategy. The original BBO/complex decomposes the problem based on system requirements. Because the objective space dimension is higher, we need to use the new decomposition method. Afterwards, like Figure2, a PBI aggregate function decomposition method can enhance the convergence and diversity of the algorithm when solving many-objective problems. With the above step, Hmp/BBO migration is divided into two categories: within-subsystem and cross-subsystem. During the within-subsystem migration phase, we enhance the probability of the solution and employ the Metropolis criterion to make the algorithm jump out of local optimal. During the cross-subsystem migration stage, we adopt the roulette wheel method to get best solution. Then we perform mutation and clear the duplicate algorithm.Figure 2
Illustration of decomposition strategy and PBI distance.Our algorithm does not take into account constraints problem. Constraints processing research questions will be in the rest of the work. Algorithm1 presents the general framework of Hmp/BBO.Algorithm 1:Hmp/BBO pseudocode.
Output:population p
(1) Initialization all the parameters
(2) generating parent population, weighting vectors and neighborhood index set
(3) decomposition strategy
(4) while the termination condition is not metdo
(5)  calculate the nondominated ranking system in subsystem
(6)  perform within-subsystem migration
(7)  perform cross-subsystem migration
(8)  perform mutation
(9)  clear the duplicate solution
(10)  replace the worst solutions with good islands
(11)  end while
(12) return p


## 3.2. Generating Weighting Vectors

We set weight vectors such that the optimal solutions of their subsystems are uniformly distributed along the PF. Most of the approaches for generating weight vectors for different decomposition strategies in MODE/D have been suggested [28]; we use Das’s method in [29], with a predefined integer H which controls the divisions along each axis. The total number of such vectors is N=CH+m-1m-1. Distributed reference points are λk=xk/H,k=1,2,…,m. Taking the three-dimension problem as an example, there are C52=10 reference points.


## 3.3. Decomposition Strategy

The Hmp/BBO initialization generatesNw weight vectors; PBI aggregate function [30] is employed to divide the weight vectors into a set of Ls (CO1,CO2,…,COL). Because the weight vectors uniformly distribute in the objective space, the number of weight vectors in one subsystem is approximate to Nw/L. Therefore, the whole objective space is divided into Ls subsystems.


## 3.4. The Nondominated Ranking System (NDRS)

NDRS was introduced in [31] as the ranking system in the multiobjective genetic algorithms (MOGA). It uses inconsecutive integers as ranks to reflect the relative performance of each individual in a population. Assume that we have a subsystem: Ri is the rank of the ith island, where a lower rank is better. If objective o1 of island i1 is better than o1 of i2, Ri2=Ri2+1; if objective o1 of island i2 is better than o1 of i1, Ri1=Ri1+1.


## 3.5. PBI Aggregate Function

In MOEA/D, several methods have been proposed for decomposing MOPs into a single-objective optimization subproblem, such as weighted sum method, Tchebycheff method, and Penalty-based Boundary Intersection (PBI) method, but it was shown that the MOEA/D-PBI is only best for many-objective optimization problem in [32]. This paper uses the PBI approach. A scalar optimization function is defined as(4)Mingpbixλ,Z∗=d1+θd2d1=z∗-FxTλλd2=Fx-z∗-d1λ.In Figure 2, Z∗ is the ideal point, d1 is the Euclidean distance between origin point and the foot point drawn from the solution to the reference direction, and d2 is the perpendicular distance of the solution from the reference direction. The θ value on the performance of Hmp/BBO is present in Section 4.3.


## 3.6. Within-Subsystem Migration

Within-subsystem migration is mainly for information sharing; we need a new rapid method for selection of immigration islands and emigration islands. First, immigrating islands are selected based on the NDRS. Afterward, emigrating islands are selected by emigration rates, in order to further improve the algorithm’s convergence speed, while avoiding falling into local optima. Features (n SIVs) of the islands will not be directly substituted with the new values that come from the probabilistically selected original islands mentioned above. Instead, n SIVs of the islands are maintained in two temporary matrices with size t1×t2. Each row of the matrices represents one individual. The old independent variables are used again if and only if the modified individual exhibits lower solution quality and does not comply with the Metropolis criterion. The inferior migrated island will be selected only if they pass the Metropolis criterion of SA. With this restriction on the with-subsystem migration, the Hmp/BBO algorithm can avoid falling into the local optimum. The algorithm is described in Algorithm 2.Algorithm 2:Within-migration pseudocode.
(1) Probabilistically choose the immigrating islands based on the NDRS.
(2)  Use the Metropolis criterion based on emigration rates to select the emigrating island.
(3) each SIV in an immigration island will have a chance to be replaced by an SIV from an emigrating island.


## 3.7. Cross-Subsystem Migration

During cross-system migration of the stage, it is desirable that the migration should be chosen from a neighborhood subsystem as much as possible. In Hmp/BBO, each island is uniquely specified by a weight vector; each weight vector has been assigned based on the Euclidean distance from a neighborhood. So we can select islands from its neighboring subsystems by neighboring index. First, we select islands between subsystems based neighboring index setE(i). Second, emigrating islands are selected based on the PBI distance. Furthermore, we need to eliminate those poor candidate islands to improve the algorithm diversity between subsystems. The inferior migrated island will not be selected unless it passes the roulette wheel method. With this restriction on the cross-subsystem migration, the Hmp/BBO algorithm’s diversity performance can be enhanced. The algorithm is described in Algorithm 3.Algorithm 3:Cross-migration pseudocode.
(1) Randomly select k indices from E(i) (choose similar subsystem) and select k immigrating islands based on
immigration rages from populationp.
(2) Calculate Euclidean distance between the islands of neighboring subsystem
(3) Use the roulette wheel selection based on emigration rates to select the emigrating islands.
(4) each SIV in an immigration island will have a chance to be replaced by an SIV from an emigrating island.


## 3.8. Mutation Algorithm

In the Hmp/BBO, these events are modeled as SIV mutation. The mutation ratemi can be determined by the following number of species involved in the probability pi to the following equation: (5)mi=mmax1-pipmax,where the mmax and pmax=max(pi) are a user-predefined maximum mutation rate that mi can reach. The ISI is the variable and function of SIV. The mutation processes are described in Algorithm 4.Algorithm 4:Mutation pseudocode.
(1) for  i←1 to k do
{whereL=numberofislands}
(2)  Calculate probability Pi based on λi and μi
{byiterativemethod}
(3)  Calculate mutation rate mi
(4) ifrand < mi and i≥Rm  then  {Rmisapredefinedmutationrange}
(5) Replace n SIVs vector of ISIi with a randomly generated n SIVs vector
(6) end if
(7) end for


## 3.9. Clear the Duplicate Algorithm

Clear duplication will increase the diversity of solutions and avoid duplication of features on other islands. The algorithm can be described in Algorithm5.Algorithm 5:Clear duplication pseudocode.
Require:Check all n SIVs on all ISIi
(1) whilethere is a duplicated SIVdo
(2) fori←1 to l do {wherel=numberofislands}
(3) if any duplicated SIVs is detected then
(4)  Replace the duplicated SIVs in ISIi with a randomly generated SIVs
(5) end ifIn conclusion, The Hmp/BBO would prove the performance of convenience and diversity by introducing a new framework for many-objective optimization. In addition, the SA algorithm comes with only one individual, while the Hmp/BBO is a population based algorithm. Instead of running SA with only one island, it can be executed with all islands in subsystems. Thus, internal searching loopsL of SA with each cycle of n can be invalid in Hmp/BBO without affecting the solution quality. This method will save one significant amount of CPU time. By these methods, the exploration and exploitation of the Hmp/BBO algorithm are much improved. The Hmp/BBO framework is described in Algorithm 6.Algorithm 6:Hybrid Metropolis Biogeography/Complex Based Optimization.
(1) Initialization with all the parameters. Initialization Nw weight vectors, CL are the center of the weight vectors cluster. Ls are the
number of subsystems and neighborhood set of weight vectorsE(i).
(2) Decomposition strategy
(3)forg←1 to G do {G=numberofgenerations}
(4) Calculate the rank of islands in each subsystem (NDRS)
(5) Probabilistically select the immigrating islands based on the islands rank, probabilistically select the emigrating islands based
on the emigration rates.
(6)  if  g=1  then
(7)     find the initial temperature T1
(8)   else
(9)    Update the temperature for the gth generation
(10)  end if
(11) Save the vectors of all the populations (before migration) in matrix mm1 with size t1∗t2 and their cost functions vector vv1
with lengthk.
(12) Do within-subsystem migration.
(13) Save the vectors of all the populations (after migration) in matrix mm2 with size t1∗t2 and their cost functions in vector vv2
with lengthk.
(14)for  i←1 to kdo (k is number of islands)
(15) CalculateΔE=V2(i)-V1(i)
(16)ifΔE>0  then
(17)P(E)=-ΔEeTgKB
(18)ifP(E)> rand  then
(19)   Acceptmm2(I,1→n) vector of matrix mm2 as an updated population for ISI
(20)else
(21)   Re-select the past mm1(I,1→n) vector of matrix mm1 as an updated population for ISIi
(22)end if
(23)end if
(24) Randomly selectk indices from E(i) and select k immigrating islands based immigration rates.
(25)ifgpbi(xnew∣w,z∗)⩽gpbi(x∣w,z∗)
(26) save the best islandsxnew for emigrating
(27)else
(28) Save the vectors of all the populations (before mutation) in matrix mm3 with size t3∗t4 and their cost functions in vector vv3
with lengthk
(29) Do cross-subsystem migration
(30) use the roulette wheel method to select population
with lengthk.
(31) Do mutation
(32)  Do clear duplicated SIV
(33)  ifg>1 then
(34)    Repalce the worst ISI with the good ISI saved in the elitism stage
(35)     end if
(36)     end for
(37)     display the best islands
(38)end if
(39)end if
(40)end if
(41) Do mutation
(42) Do clear duplicated SIV
(43)if  g>1  then
(44) Replace the worst ISI with the good ISI saved in the elitism stage
(45)end if
(46)end for
(47) Display the best islands.


## 3.10. Computational Complexity of One Generation of Hmp/BBO

In this section, we discuss the computational complexity of the Hmp/BBO. For a population sizeN and a problem of M objectives, the major computational costs are in steps (5), (6), and (7) of Algorithm 1. Step (5) is the computational complexity of NDRS; it requires O(NM) computations. Computing of within-subsystem (step (6)) needs O(LN12) computations, where L is cycles of Metropolis and N1 is generated by parents’ populations. Cross-subsystem migration (step (7)) needs O(LN12R) computations and R is equal to the number of subsystems. So for M objectives, reviewing all the above computations, the overall complexity of one generation of Hmp/BBO is O(NM+LN12+LN12R).


## 4. Simulation Results

In this section, to prove the validity of Hmp/BBO, we compare it with five state-of-the-art algorithms for comparisons, including BBO/Complex, NSGAIII, MOEA/D-PBI, HYPE, and GREA. NSGAIII is based on the Pareto dominance relationship, but the maintenance of population diversity is supported by the use of a group of uniformly distributed reference points. MOEA/D-PBI is a representative of the decomposition-based approach and keeps the diversity of solutions using a series of predefined weight vectors. HYPE is a Hypervolume-based evolutionary algorithm for many-objective optimizations. GREA uses the NSGA-II framework and introduces two concepts (grid dominance and grid difference) and three grid-based standards, and a finesse adjustment strategy. We describe the test questions used in Section4.1 and the quality indicators in Section 4.2. Then we introduce five state-of-the-art algorithms that used comparison and the corresponding parameter settings in Section 4.3. Finally, the discussion results are in Section 4.4.


### 4.1. Test Problems

In checking to verify the proposed algorithm, the well-known test functions definitions of DTZ1–DTZ4 [33] functions and all of WFG test suite [34] are listed in Table 1. We only consider DTLZ 1–4 problems for DTLZ test suite, because the nature of DTLZ5 and DTLZ6’s PFs is unclear beyond three objectives [35]. DTLZ1 is a liner and multimodal function; DTLZ2 is a concave function; DTLZ3 is concave and multimodal function; DTLZ4 is concave and biased function, as summarized in Table 1.Table 1
Test functions utilized in this experiment.
Name of function
Characteristics
DTLZ1
Liner, multimodal
DTLZ2
Concave
DTLZ3
Concave, multimodal
DTLZ4
Concave, biased
WFG1
Mixed, Biased, scaled
WFG2
Convex, disconnected
WFG3
Linear, degenerate
WFG4
Concave, multimodal
WFG5
Concave, deceptive
WFG6
Concave, scaled
WFG7
Biased, scaled
WFG8
Biased, nonseparable
WFG9
Concave, scaled


### 4.2. Quality Indicators

In our empirical study, the following three extensively used quality indicators are examined. The first one can reflect the convergence of an algorithm. In the second one and last one, the convergence and diversity of the solutions can be recorded simultaneously.(1) Generational Distance (GD). Let P be the last series of nondominated points in the objective space and P∗ be a set of points evenly distributed over the actual PF. GD can only reflect the performance of convergence for an algorithm; a smaller value means better quality. Then GD is described as follows:(6)GDP,P∗=∑u∈Pdu,P∗P.(2) Inverted Generational Distance (IGD). Let P∗ be a set of points uniformly sampled over the actual efficient front (EF), and let P be the set of solutions obtained by an algorithm. IGD may be used to measure convergence and diversity in a sense, and a smaller value means better quality. Then IGD is described as follows:(7)IGDP,P∗=∑v∈P∗dv,PP∗.(3) Hypervolume (HV) Indicator. HV indicator can measure both convergence and diversity of a solution set. The HV is used for WFG test suite, and the larger the HV value is, the better the solution’s quality for the PF is. Then HV is described as follows:(8)HVA,r=Volume⋃f∈Af1,r1×⋯×fm,rm.M is the number of objectives.A is the set of nondominated points obtained in the objective space by an algorithm. r=(r1,r2,…,rm)T is a reference point in the objective space which is dominated by all Pareto points.


### 4.3. Parameters Setting

The parameters for the six MOEAs considered in this study are listed below.(1)
Population size: the population sizeN used in this study for Hmp/BBO is 91, 206, and 210 for three-, four-, and five-objective problems, respectively. Furthermore, the size of the NSGA-III population was mildly adjusted as in the original NSGAIII study, that is, 92, 212, and 276 for three-, four-, and five-objective problems.(2)
Stop condition: each algorithm runs 20 times independently on each test question. All algorithms are implemented on a 2.6 GHz CPU desktop computer, 8 GB RAM, and Windows 10. The stop condition of the algorithm is the maximum number of fitness evaluations, as outlined in Table2.(3)
Parameter setting in Hmp/BBO: set immigration rate isλmax=1, emigration rate is μmax=1, max=0.01, t0=1000, K=0.9, and Tend=0.001, and penalty parameter in PBI: θHmp=5, is also suggested in [18]. Neighborhood sizes MHmp=20.(4)
Parameter setting in BBO/Complex: set immigration rate isλmax=1, emigration rate is μmax=1, mutation probability p=0.05, and the generation count g=30.(5)
Reproduction operator setting: crossover probabilitypc=1, ηc=30 in NSGAIII. The mutation probability is pm=1/V and its distribution index ηm=30.(6)
Parameter setting in MOEA/D-PBI: neighborhood sizeMMOEA/D=20; probability used for selection in neighborhood δ=0.9. Penalty parameter θMOEA/D=5.(7)
The grid division (div) in GREA: Div is set according to [9] as shown in Table 3.(8)
Number of points in Monte Carlo sampling: it is placed at 1,000,000 to ensure accuracy.Table 2
Maximum number of fitness evaluation for different function.
Function
M
=
3
M
=
4
M
=
5
DTLZ1
36500
26400
12600
DTLZ2
22840
42500
73600
DTLZ3
92000
14600
220000
DTLZ4
54700
13200
220000
WFG1–9
36500
74300
157500Table 3
Settings of grid division div in GREA.
Function
M
=
3
M
=
4
M
=
5
DTLZ1
10
10
10
DTLZ2
10
10
9
DTLZ3
11
10
11
DTLZ4
10
10
7
WFG1
7
9
14
WFG2
18
17
16
WFG3
14
14
14
WFG4–9
10
10
11


### 4.4. Result and Discussion

In this section, the GD metrics are used to compare the convergence capacity between the proposed Hmp/BBO and other five algorithms. Table4 shows the best, median, and worst GD values obtained by six algorithms on DTLZ1 to DTLZ4 with different number of objectives, and the one that is significantly better than the other is marked in bold face. Table 4 shows that all the test functions of Hmp/BBO performed well, especially in the DTLZ1 and DTLZ4 problems. Results of DTLZ test suite in comparison to results of Hmp/BBO with other five MOEAs in terms of IGD values on DTLZ test suite are presented in Table 5. It shows both the mean and IGD values of over 20 independent runs for the six compared MOEAs, where the best mean and standard deviation values are marked in bold. Furthermore, Table 6 presents the average and standard deviation of the Hypervolume over 20 independent runs on WFG problems, where the best performance is highlighted in bold. The quality of the solution sets obtained by the six algorithms on all WFG test problems in terms of Hypervolume was compared. From the experimental results of DTLZ and WFG test problem, we find that Hmp/BBO shows better performance than the other five algorithms.Table 4
Best, median, and worst GD values obtained by DTLZ1 to DTLZ4 with six algorithms by different number of objectives.
Functions
m
Values
Hmp/BBO
BBO/Complex
NSGAIII
MOEA/D-PBI
HYPE
GREA
DTLZ1
3
Best
6.078
e
-
05
1.380
e
-
04
3.324
e
-
04
1.478
e
-
04
2.073
e
-
04
2.544
e
-
04
Median
1.032
e
-
04
1.650
e
-
04
6.749
e
-
04
1.652
e
-
04
5.546
e
-
04
3.132
e
-
04
Worst
2.218
e
-
04
5.833
e
-
03
6.129
e
-
03
7.634
e
-
03
7.333
e
-
03
8.326
e
-
03
4
Best
1.733
e
-
05
2.478
e
-
05
2.189
e
-
05
3.452
e
-
05
3.321
e
-
05
2.235
e
-
05
Median
2.348
e
-
05
2.742
e
-
05
2.689
e
-
05
3.874
e
-
05
3.981
e
-
05
4.035
e
-
05
Worst
2.426
e
-
05
2.859
e
-
05
3.056
e
-
05
7.723
e
-
05
5.885
e
-
05
5.126
e
-
05
5
Best
1.740
e
-
04
1.857
e
-
04
1.032
e
-
04
2.023
e
-
04
2.253
e
-
04
3.224
e
-
04
Median
2.304
e
-
04
2.006
e
-
04
1.112
e
-
04
2.635
e
-
04
3.867
e
-
04
4.325
e
-
04
Worst
2.941
e
-
04
2.506
e
-
04
1.688
e
-
04
3.227
e
-
04
4.954
e
-
04
5.532
e
-
04
DTLZ2
3
Best
7.130
e
-
05
1.231
e
-
04
1.326
e
-
04
1.154
e
-
04
1.632
e
-
04
3.184
e
-
04
Median
7.458
e
-
05
1.335
e
-
04
1.631
e
-
04
1.536
e
-
04
2.547
e
-
04
4.368
e
-
04
Worst
1.102
e
-
04
1.421
e
-
04
1.967
e
-
04
1.859
e
-
04
5.456
e
-
04
1.559
e
-
03
4
Best
2.682
e
-
05
4.819
e
-
05
7.765
e
-
05
8.132
e
-
05
8.569
e
-
05
9.142
e
-
05
Median
5.791
e
-
05
5.321
e
-
04
7.969
e
-
04
8.486
e
-
04
5.723
e
-
04
8.836
e
-
04
Worst
1.008
e
-
04
7.021
e
-
04
9.366
e
-
04
1.455
e
-
03
8.454
e
-
04
1.357
e
-
03
5
Best
8.613
e
-
05
8.621
e
-
05
8.752
e
-
05
9.123
e
-
05
9.439
e
-
05
9.783
e
-
05
Median
1.193
e
-
04
1.323
e
-
04
1.456
e
-
04
1.523
e
-
04
1.717
e
-
04
1.986
e
-
04
Worst
2.101
e
-
04
2.458
e
-
04
2.569
e
-
04
2.834
e
-
04
5.956
e
-
04
3.549
e
-
04
DTLZ3
3
Best
1.128
e
-
04
1.227
e
-
04
1.360
e
-
04
1.257
e
-
04
1.453
e
-
04
1.257
e
-
04
Median
1.402
e
-
04
1.411
e
-
04
1.587
e
-
04
1.605
e
-
04
1.742
e
-
04
1.926
e
-
04
Worst
2.597
e
-
04
2.625
e
-
04
2.767
e
-
04
2.858
e
-
04
2.903
e
-
04
2.759
e
-
04
4
Best
1.325
e
-
04
1.423
e
-
04
1.560
e
-
04
1.568
e
-
04
1.954
e
-
04
2.856
e
-
04
Median
1.589
e
-
04
1.621
e
-
04
1.897
e
-
04
2.225
e
-
04
2.273
e
-
04
3.863
e
-
04
Worst
1.759
e
-
04
1.791
e
-
04
1.969
e
-
04
3.851
e
-
04
5.956
e
-
04
6.989
e
-
04
5
Best
7.138
e
-
05
7.026
e
-
05
1.161
e
-
04
1.229
e
-
04
1.156
e
-
04
1.559
e
-
04
Median
1.090
e
-
04
1.014
e
-
04
1.363
e
-
04
1.454
e
-
04
1.557
e
-
04
1.852
e
-
04
Worst
2.599
e
-
04
2.423
e
-
04
2.567
e
-
04
2.859
e
-
04
2.456
e
-
04
2.558
e
-
04
DTLZ4
3
Best
1.434
e
-
05
1.450
e
-
05
1.354
e
-
04
1.625
e
-
04
1.457
e
-
04
1.590
e
-
04
Median
1.658
e
-
05
1.752
e
-
05
1.811
e
-
04
1.757
e
-
04
1.956
e
-
04
1.869
e
-
04
Worst
1.766
e
-
05
1.781
e
-
05
1.867
e
-
04
1.853
e
-
04
2.156
e
-
04
1.954
e
-
04
4
Best
1.524
e
-
05
1.556
e
-
05
1.667
e
-
05
1.659
e
-
05
1.853
e
-
05
1.771
e
-
05
Median
1.626
e
-
05
1.629
e
-
05
1.711
e
-
05
1.731
e
-
05
1.950
e
-
05
1.859
e
-
05
Worst
1.735
e
-
05
1.778
e
-
05
1.797
e
-
05
2.741
e
-
05
2.757
e
-
05
1.959
e
-
05
5
Best
1.786
e
-
05
1.801
e
-
05
1.862
e
-
05
1.859
e
-
05
1.856
e
-
05
1.853
e
-
05
Median
1.938
e
-
05
2.024
e
-
05
3.767
e
-
05
2.850
e
-
05
5.456
e
-
05
3.559
e
-
05
Worst
7.809
e
-
05
8.421
e
-
05
8.760
e
-
05
8.857
e
-
05
8.454
e
-
05
8.554
e
-
05Table 5
Best, median, and worst IGD values obtained by DTLZ1 to DTLZ4 with six algorithms by different number of objectives.
Functions
m
Hmp/BBO
BBO/Complex
NSGAIII
MOEA/D-PBI
HYPE
GREA
DTLZ1
3
Best
3.114
e
-
04
3.380
e
-
04
3.424
e
-
04
4.274
e
-
04
4.071
e
-
04
4.644
e
-
04
Median
4.276
e
-
04
3.650
e
-
03
3.742
e
-
03
4.332
e
-
04
4.542
e
-
04
5.422
e
-
04
Worst
2.032
e
-
03
3.833
e
-
03
3.929
e
-
03
5.731
e
-
03
6.241
e
-
03
7.321
e
-
03
4
Best
1.873
e
-
04
1.978
e
-
05
1.789
e
-
04
1.884
e
-
04
1.981
e
-
04
2.014
e
-
04
Median
1.956
e
-
04
1.916
e
-
04
2.033
e
-
04
2.075
e
-
04
2.837
e
-
04
4.9233
e
-
04
Worst
2.126
e
-
04
2.054
e
-
04
3.126
e
-
04
3.071
e
-
04
3.985
e
-
04
5.126
e
-
04
5
Best
2.047
e
-
04
2.234
e
-
04
2.532
e
-
04
2.643
e
-
04
2.753
e
-
04
3.224
e
-
04
Median
2.273
e
-
04
2.301
e
-
03
2.611
e
-
03
2.831
e
-
04
3.817
e
-
04
4.125
e
-
04
Worst
3.162
e
-
04
2.706
e
-
03
2.754
e
-
03
2.927
e
-
03
3.914
e
-
04
4.512
e
-
04
DTLZ2
3
Best
3.209
e
-
04
5.201
e
-
04
3.371
e
-
04
3.694
e
-
04
3.732
e
-
04
3.984
e
-
04
Median
4.561
e
-
04
5.335
e
-
04
6.631
e
-
04
7.536
e
-
04
8.547
e
-
04
9.368
e
-
04
Worst
6.255
e
-
04
6.421
e
-
04
7.767
e
-
04
7.859
e
-
04
7.956
e
-
04
9.559
e
-
04
4
Best
4.682
e
-
05
5.717
e
-
05
6.765
e
-
05
7.732
e
-
05
8.579
e
-
05
9.742
e
-
05
Median
5.392
e
-
05
2.821
e
-
04
2.922
e
-
04
8.486
e
-
04
8.783
e
-
04
8.886
e
-
04
Worst
1.104
e
-
04
1.211
e
-
03
1.366
e
-
03
1.455
e
-
03
1.454
e
-
03
1.857
e
-
03
5
Best
8.613
e
-
05
1.621
e
-
04
1.752
e
-
04
2.123
e
-
04
2.432
e
-
04
5.783
e
-
04
Median
7.687
e
-
04
1.922
e
-
03
1.956
e
-
03
2.513
e
-
03
2.727
e
-
03
2.926
e
-
03
Worst
1.038
e
-
03
2.458
e
-
03
2.569
e
-
03
2.834
e
-
03
2.956
e
-
03
3.549
e
-
03
DTLZ3
3
Best
6.123
e
-
04
6.222
e
-
04
6.360
e
-
04
7.251
e
-
04
7.423
e
-
04
7.757
e
-
04
Median
1.587
e
-
03
1.616
e
-
03
1.784
e
-
03
1.905
e
-
03
1.942
e
-
03
1.926
e
-
02
Worst
3.929
e
-
03
4.695
e
-
03
7.555
e
-
03
2.858
e
-
02
2.903
e
-
02
3.359
e
-
02
4
Best
1.516
e
-
04
1.826
e
-
04
1.961
e
-
04
1.968
e
-
04
2.114
e
-
04
2.552
e
-
04
Median
1.782
e
-
04
1.922
e
-
04
2.117
e
-
04
2.221
e
-
04
2.371
e
-
04
2.661
e
-
04
Worst
1.951
e
-
04
1.993
e
-
04
2.762
e
-
04
2.852
e
-
04
2.952
e
-
04
2.989
e
-
04
5
Best
5.342
e
-
04
7.932
e
-
04
4.011
e
-
04
5.829
e
-
04
5.956
e
-
04
6.559
e
-
04
Median
1.137
e
-
03
1.514
e
-
03
1.113
e
-
03
1.154
e
-
03
1.157
e
-
03
1.252
e
-
03
Worst
1.574
e
-
03
2.423
e
-
03
1.537
e
-
03
1.859
e
-
03
1.956
e
-
03
2.151
e
-
03
DTLZ4
3
Best
9.243
e
-
05
1.420
e
-
04
1.554
e
-
04
1.835
e
-
04
1.957
e
-
04
1.992
e
-
04
Median
1.092
e
-
04
1.752
e
-
04
2.211
e
-
04
2.777
e
-
04
2.856
e
-
04
2.969
e
-
04
Worst
1.892
e
-
04
1.971
e
-
04
2.867
e
-
04
2.893
e
-
04
2.916
e
-
04
2.984
e
-
04
4
Best
1.231
e
-
05
1.526
e
-
05
1.667
e
-
05
1.669
e
-
05
1.543
e
-
05
1.541
e
-
05
Median
1.526
e
-
05
1.727
e
-
05
1.731
e
-
05
1.732
e
-
05
1.650
e
-
05
1.759
e
-
05
Worst
1.635
e
-
05
1.793
e
-
05
1.797
e
-
05
1.841
e
-
05
3.857
e
-
05
2.879
e
-
05
5
Best
1.336
e
-
04
1.701
e
-
04
1.852
e
-
04
1.179
e
-
05
2.346
e
-
05
2.353
e
-
05
Median
1.392
e
-
04
2.024
e
-
04
2.267
e
-
04
1.451
e
-
05
2.556
e
-
05
2.759
e
-
05
Worst
2.052
e
-
04
8.421
e
-
04
9.760
e
-
04
1.817
e
-
05
9.854
e
-
04
9.954
e
-
04Table 6
Average and standard deviation of the HV values on WFG1 to WFG9 with six algorithms by different number of objectives.
Functions
m
Hmp/BBO
BBO/Complex
NSGAIII
MOEA/D-PBI
HYPE
GREA
WFG1
3
4.232
e
-
01
4.806
e
-
01
5.138
e
-
01
4.821
e
-
01
5.385
e
-
01
7.235
e
-
01
4
4.611
e
-
01
3.252
e
-
01
4.054
e
-
01
4.458
e
-
01
6.141
e
-
01
5.326
e
-
01
5
5.340
e
-
01
4.587
e
-
01
5.032
e
-
01
5.023
e
-
01
5.953
e
-
01
5.224
e
-
01
WFG2
3
8.658
e
-
01
8.538
e
-
01
8.616
e
-
01
7.184
e
-
01
8.485
e
-
01
8.901
e
-
01
4
9.181
e
-
01
8.705
e
-
01
8.061
e
-
01
7.934
e
-
01
8.801
e
-
01
9.342
e
-
01
5
9.523
e
-
01
9.401
e
-
01
9.232
e
-
01
9.101
e
-
01
9.239
e
-
01
9.324
e
-
01
WFG3
3
8.032
e
-
01
8.127
e
-
01
8.311
e
-
01
9.102
e
-
01
9.333
e
-
01
9.202
e
-
01
4
8.926
e
-
01
8.422
e
-
01
7.552
e
-
01
7.456
e
-
01
8.014
e
-
01
8.716
e
-
01
5
9.337
e
-
01
8.323
e
-
01
8.001
e
-
01
7.123
e
-
01
8.326
e
-
01
7.007
e
-
01
WFG4
3
7.212
e
-
01
7.362
e
-
01
7.852
e
-
01
6.952
e
-
01
8.654
e
-
01
8.852
e
-
01
4
9.012
e
-
01
9.002
e
-
01
8.567
e
-
01
8.688
e
-
01
8.893
e
-
01
8.324
e
-
01
5
9.386
e
-
01
9.201
e
-
01
8.862
e
-
01
8.559
e
-
01
8.756
e
-
01
8.453
e
-
01
WFG5
3
6.331
e
-
01
6.433
e
-
01
6.321
e
-
01
6.512
e
-
01
6.213
e
-
01
6.790
e
-
01
4
6.823
e
-
01
6.522
e
-
01
6.247
e
-
01
5.955
e
-
01
5.896
e
-
01
6.001
e
-
01
5
6.743
e
-
01
6.801
e
-
01
6.363
e
-
01
6.442
e
-
01
6.782
e
-
01
6.553
e
-
01
WFG6
3
6.832
e
-
01
6.655
e
-
01
6.324
e
-
01
6.725
e
-
01
6.859
e
-
01
6.531
e
-
01
4
6.521
e
-
01
6.454
e
-
01
6.447
e
-
01
6.353
e
-
01
6.553
e
-
01
6.321
e
-
01
5
6.772
e
-
01
6.521
e
-
01
6.232
e
-
01
6.325
e
-
01
6.526
e
-
01
6.326
e
-
01
WFG7
3
7.137
e
-
01
7.150
e
-
01
7.254
e
-
01
7.025
e
-
01
6.957
e
-
01
7.012
e
-
01
4
7.024
e
-
01
7.536
e
-
01
7.237
e
-
01
7.558
e
-
01
7.001
e
-
01
7.121
e
-
01
5
7.874
e
-
01
7.321
e
-
01
6.969
e
-
01
7.051
e
-
01
7.326
e
-
01
7.353
e
-
01
WFG8
3
6.231
e
-
01
6.020
e
-
01
6.151
e
-
01
5.925
e
-
01
6.050
e
-
01
6.012
e
-
01
4
6.020
e
-
01
6.552
e
-
01
6.327
e
-
01
6.239
e
-
01
6.153
e
-
01
6.271
e
-
01
5
6.286
e
-
01
6.001
e
-
01
6.112
e
-
01
6.139
e
-
01
6.210
e
-
01
6.213
e
-
01
WFG9
3
6.144
e
-
01
6.235
e
-
01
6.312
e
-
01
6.121
e
-
01
6.352
e
-
01
6.124
e
-
01
4
6.441
e
-
01
6.348
e
-
01
6.320
e
-
01
6.259
e
-
01
6.404
e
-
01
6.472
e
-
01
5
6.281
e
-
01
6.101
e
-
01
6.161
e
-
01
6.254
e
-
01
6.056
e
-
01
6.113
e
-
01Figure3 shows the parallel coordinates of PF obtained by Hmp/BBO and the other five MOEAs with the five-objective of DTLZ1. This run is involved in the result closest to the mean IGD value. A parallel coordinates system is a visual representation of the overall performance of the algorithm for high-dimensional space, where each row represents a point in a high-dimensional space. If the lines on each object on the graph are distributed in [0,1], it is shown that the convergence of the better algorithm, if the lines can be evenly distributed in [0,1], indicates that the distribution of the algorithm is better. From this figure, it is found that the Hmp/BBO is slightly better in convergence and diversity than BBO/Complex, NSGAIII, and MOEA/D-PBI. HYPE and GREA are far away from the PF because the maximum value of some objectives is much larger than 0.5. Obviously, the solutions achieved by HYPE and GREA are worse than the above four algorithms.Figure 3
Parallel coordinates figure by six algorithms on the five-objective DTLZ1. (a) Hmp/BBO; (b) BBO/Complex; (c) NSGAIII; (d) MOEA/D-PBI; (e) HYPE; (f) GREA.
(a)
(b)
(c)
(d)
(e)
(f)Performance scores are introduced to the global performance of compared algorithms. For a problem test question, suppose that there areS algorithms al1,al2,…,alS; let γij be 1, if ali outperforms alj in terms of IGD metric, and 0 otherwise. This value indicates how many other algorithms are better than ali on the problem test question. Therefore, the smaller the value is, the better the algorithm is. Then, performance score S(ali) is determined as(9)Sali=∑j=1j≠isγij.In Figure 4, the average performance scores for different number of objectives and different test problems are briefly summarized. Score of Hmp/BBO is smaller than other algorithms in the corresponding number of objectives.Figure 4
Average performance score over all test problems for different number of objectives. The smaller the score, the better the performance in the corresponding number of objectives.


## 4.1. Test Problems

In checking to verify the proposed algorithm, the well-known test functions definitions of DTZ1–DTZ4 [33] functions and all of WFG test suite [34] are listed in Table 1. We only consider DTLZ 1–4 problems for DTLZ test suite, because the nature of DTLZ5 and DTLZ6’s PFs is unclear beyond three objectives [35]. DTLZ1 is a liner and multimodal function; DTLZ2 is a concave function; DTLZ3 is concave and multimodal function; DTLZ4 is concave and biased function, as summarized in Table 1.Table 1
Test functions utilized in this experiment.
Name of function
Characteristics
DTLZ1
Liner, multimodal
DTLZ2
Concave
DTLZ3
Concave, multimodal
DTLZ4
Concave, biased
WFG1
Mixed, Biased, scaled
WFG2
Convex, disconnected
WFG3
Linear, degenerate
WFG4
Concave, multimodal
WFG5
Concave, deceptive
WFG6
Concave, scaled
WFG7
Biased, scaled
WFG8
Biased, nonseparable
WFG9
Concave, scaled


## 4.2. Quality Indicators

In our empirical study, the following three extensively used quality indicators are examined. The first one can reflect the convergence of an algorithm. In the second one and last one, the convergence and diversity of the solutions can be recorded simultaneously.(1) Generational Distance (GD). Let P be the last series of nondominated points in the objective space and P∗ be a set of points evenly distributed over the actual PF. GD can only reflect the performance of convergence for an algorithm; a smaller value means better quality. Then GD is described as follows:(6)GDP,P∗=∑u∈Pdu,P∗P.(2) Inverted Generational Distance (IGD). Let P∗ be a set of points uniformly sampled over the actual efficient front (EF), and let P be the set of solutions obtained by an algorithm. IGD may be used to measure convergence and diversity in a sense, and a smaller value means better quality. Then IGD is described as follows:(7)IGDP,P∗=∑v∈P∗dv,PP∗.(3) Hypervolume (HV) Indicator. HV indicator can measure both convergence and diversity of a solution set. The HV is used for WFG test suite, and the larger the HV value is, the better the solution’s quality for the PF is. Then HV is described as follows:(8)HVA,r=Volume⋃f∈Af1,r1×⋯×fm,rm.M is the number of objectives.A is the set of nondominated points obtained in the objective space by an algorithm. r=(r1,r2,…,rm)T is a reference point in the objective space which is dominated by all Pareto points.


## 4.3. Parameters Setting

The parameters for the six MOEAs considered in this study are listed below.(1)
Population size: the population sizeN used in this study for Hmp/BBO is 91, 206, and 210 for three-, four-, and five-objective problems, respectively. Furthermore, the size of the NSGA-III population was mildly adjusted as in the original NSGAIII study, that is, 92, 212, and 276 for three-, four-, and five-objective problems.(2)
Stop condition: each algorithm runs 20 times independently on each test question. All algorithms are implemented on a 2.6 GHz CPU desktop computer, 8 GB RAM, and Windows 10. The stop condition of the algorithm is the maximum number of fitness evaluations, as outlined in Table2.(3)
Parameter setting in Hmp/BBO: set immigration rate isλmax=1, emigration rate is μmax=1, max=0.01, t0=1000, K=0.9, and Tend=0.001, and penalty parameter in PBI: θHmp=5, is also suggested in [18]. Neighborhood sizes MHmp=20.(4)
Parameter setting in BBO/Complex: set immigration rate isλmax=1, emigration rate is μmax=1, mutation probability p=0.05, and the generation count g=30.(5)
Reproduction operator setting: crossover probabilitypc=1, ηc=30 in NSGAIII. The mutation probability is pm=1/V and its distribution index ηm=30.(6)
Parameter setting in MOEA/D-PBI: neighborhood sizeMMOEA/D=20; probability used for selection in neighborhood δ=0.9. Penalty parameter θMOEA/D=5.(7)
The grid division (div) in GREA: Div is set according to [9] as shown in Table 3.(8)
Number of points in Monte Carlo sampling: it is placed at 1,000,000 to ensure accuracy.Table 2
Maximum number of fitness evaluation for different function.
Function
M
=
3
M
=
4
M
=
5
DTLZ1
36500
26400
12600
DTLZ2
22840
42500
73600
DTLZ3
92000
14600
220000
DTLZ4
54700
13200
220000
WFG1–9
36500
74300
157500Table 3
Settings of grid division div in GREA.
Function
M
=
3
M
=
4
M
=
5
DTLZ1
10
10
10
DTLZ2
10
10
9
DTLZ3
11
10
11
DTLZ4
10
10
7
WFG1
7
9
14
WFG2
18
17
16
WFG3
14
14
14
WFG4–9
10
10
11


## 4.4. Result and Discussion

In this section, the GD metrics are used to compare the convergence capacity between the proposed Hmp/BBO and other five algorithms. Table4 shows the best, median, and worst GD values obtained by six algorithms on DTLZ1 to DTLZ4 with different number of objectives, and the one that is significantly better than the other is marked in bold face. Table 4 shows that all the test functions of Hmp/BBO performed well, especially in the DTLZ1 and DTLZ4 problems. Results of DTLZ test suite in comparison to results of Hmp/BBO with other five MOEAs in terms of IGD values on DTLZ test suite are presented in Table 5. It shows both the mean and IGD values of over 20 independent runs for the six compared MOEAs, where the best mean and standard deviation values are marked in bold. Furthermore, Table 6 presents the average and standard deviation of the Hypervolume over 20 independent runs on WFG problems, where the best performance is highlighted in bold. The quality of the solution sets obtained by the six algorithms on all WFG test problems in terms of Hypervolume was compared. From the experimental results of DTLZ and WFG test problem, we find that Hmp/BBO shows better performance than the other five algorithms.Table 4
Best, median, and worst GD values obtained by DTLZ1 to DTLZ4 with six algorithms by different number of objectives.
Functions
m
Values
Hmp/BBO
BBO/Complex
NSGAIII
MOEA/D-PBI
HYPE
GREA
DTLZ1
3
Best
6.078
e
-
05
1.380
e
-
04
3.324
e
-
04
1.478
e
-
04
2.073
e
-
04
2.544
e
-
04
Median
1.032
e
-
04
1.650
e
-
04
6.749
e
-
04
1.652
e
-
04
5.546
e
-
04
3.132
e
-
04
Worst
2.218
e
-
04
5.833
e
-
03
6.129
e
-
03
7.634
e
-
03
7.333
e
-
03
8.326
e
-
03
4
Best
1.733
e
-
05
2.478
e
-
05
2.189
e
-
05
3.452
e
-
05
3.321
e
-
05
2.235
e
-
05
Median
2.348
e
-
05
2.742
e
-
05
2.689
e
-
05
3.874
e
-
05
3.981
e
-
05
4.035
e
-
05
Worst
2.426
e
-
05
2.859
e
-
05
3.056
e
-
05
7.723
e
-
05
5.885
e
-
05
5.126
e
-
05
5
Best
1.740
e
-
04
1.857
e
-
04
1.032
e
-
04
2.023
e
-
04
2.253
e
-
04
3.224
e
-
04
Median
2.304
e
-
04
2.006
e
-
04
1.112
e
-
04
2.635
e
-
04
3.867
e
-
04
4.325
e
-
04
Worst
2.941
e
-
04
2.506
e
-
04
1.688
e
-
04
3.227
e
-
04
4.954
e
-
04
5.532
e
-
04
DTLZ2
3
Best
7.130
e
-
05
1.231
e
-
04
1.326
e
-
04
1.154
e
-
04
1.632
e
-
04
3.184
e
-
04
Median
7.458
e
-
05
1.335
e
-
04
1.631
e
-
04
1.536
e
-
04
2.547
e
-
04
4.368
e
-
04
Worst
1.102
e
-
04
1.421
e
-
04
1.967
e
-
04
1.859
e
-
04
5.456
e
-
04
1.559
e
-
03
4
Best
2.682
e
-
05
4.819
e
-
05
7.765
e
-
05
8.132
e
-
05
8.569
e
-
05
9.142
e
-
05
Median
5.791
e
-
05
5.321
e
-
04
7.969
e
-
04
8.486
e
-
04
5.723
e
-
04
8.836
e
-
04
Worst
1.008
e
-
04
7.021
e
-
04
9.366
e
-
04
1.455
e
-
03
8.454
e
-
04
1.357
e
-
03
5
Best
8.613
e
-
05
8.621
e
-
05
8.752
e
-
05
9.123
e
-
05
9.439
e
-
05
9.783
e
-
05
Median
1.193
e
-
04
1.323
e
-
04
1.456
e
-
04
1.523
e
-
04
1.717
e
-
04
1.986
e
-
04
Worst
2.101
e
-
04
2.458
e
-
04
2.569
e
-
04
2.834
e
-
04
5.956
e
-
04
3.549
e
-
04
DTLZ3
3
Best
1.128
e
-
04
1.227
e
-
04
1.360
e
-
04
1.257
e
-
04
1.453
e
-
04
1.257
e
-
04
Median
1.402
e
-
04
1.411
e
-
04
1.587
e
-
04
1.605
e
-
04
1.742
e
-
04
1.926
e
-
04
Worst
2.597
e
-
04
2.625
e
-
04
2.767
e
-
04
2.858
e
-
04
2.903
e
-
04
2.759
e
-
04
4
Best
1.325
e
-
04
1.423
e
-
04
1.560
e
-
04
1.568
e
-
04
1.954
e
-
04
2.856
e
-
04
Median
1.589
e
-
04
1.621
e
-
04
1.897
e
-
04
2.225
e
-
04
2.273
e
-
04
3.863
e
-
04
Worst
1.759
e
-
04
1.791
e
-
04
1.969
e
-
04
3.851
e
-
04
5.956
e
-
04
6.989
e
-
04
5
Best
7.138
e
-
05
7.026
e
-
05
1.161
e
-
04
1.229
e
-
04
1.156
e
-
04
1.559
e
-
04
Median
1.090
e
-
04
1.014
e
-
04
1.363
e
-
04
1.454
e
-
04
1.557
e
-
04
1.852
e
-
04
Worst
2.599
e
-
04
2.423
e
-
04
2.567
e
-
04
2.859
e
-
04
2.456
e
-
04
2.558
e
-
04
DTLZ4
3
Best
1.434
e
-
05
1.450
e
-
05
1.354
e
-
04
1.625
e
-
04
1.457
e
-
04
1.590
e
-
04
Median
1.658
e
-
05
1.752
e
-
05
1.811
e
-
04
1.757
e
-
04
1.956
e
-
04
1.869
e
-
04
Worst
1.766
e
-
05
1.781
e
-
05
1.867
e
-
04
1.853
e
-
04
2.156
e
-
04
1.954
e
-
04
4
Best
1.524
e
-
05
1.556
e
-
05
1.667
e
-
05
1.659
e
-
05
1.853
e
-
05
1.771
e
-
05
Median
1.626
e
-
05
1.629
e
-
05
1.711
e
-
05
1.731
e
-
05
1.950
e
-
05
1.859
e
-
05
Worst
1.735
e
-
05
1.778
e
-
05
1.797
e
-
05
2.741
e
-
05
2.757
e
-
05
1.959
e
-
05
5
Best
1.786
e
-
05
1.801
e
-
05
1.862
e
-
05
1.859
e
-
05
1.856
e
-
05
1.853
e
-
05
Median
1.938
e
-
05
2.024
e
-
05
3.767
e
-
05
2.850
e
-
05
5.456
e
-
05
3.559
e
-
05
Worst
7.809
e
-
05
8.421
e
-
05
8.760
e
-
05
8.857
e
-
05
8.454
e
-
05
8.554
e
-
05Table 5
Best, median, and worst IGD values obtained by DTLZ1 to DTLZ4 with six algorithms by different number of objectives.
Functions
m
Hmp/BBO
BBO/Complex
NSGAIII
MOEA/D-PBI
HYPE
GREA
DTLZ1
3
Best
3.114
e
-
04
3.380
e
-
04
3.424
e
-
04
4.274
e
-
04
4.071
e
-
04
4.644
e
-
04
Median
4.276
e
-
04
3.650
e
-
03
3.742
e
-
03
4.332
e
-
04
4.542
e
-
04
5.422
e
-
04
Worst
2.032
e
-
03
3.833
e
-
03
3.929
e
-
03
5.731
e
-
03
6.241
e
-
03
7.321
e
-
03
4
Best
1.873
e
-
04
1.978
e
-
05
1.789
e
-
04
1.884
e
-
04
1.981
e
-
04
2.014
e
-
04
Median
1.956
e
-
04
1.916
e
-
04
2.033
e
-
04
2.075
e
-
04
2.837
e
-
04
4.9233
e
-
04
Worst
2.126
e
-
04
2.054
e
-
04
3.126
e
-
04
3.071
e
-
04
3.985
e
-
04
5.126
e
-
04
5
Best
2.047
e
-
04
2.234
e
-
04
2.532
e
-
04
2.643
e
-
04
2.753
e
-
04
3.224
e
-
04
Median
2.273
e
-
04
2.301
e
-
03
2.611
e
-
03
2.831
e
-
04
3.817
e
-
04
4.125
e
-
04
Worst
3.162
e
-
04
2.706
e
-
03
2.754
e
-
03
2.927
e
-
03
3.914
e
-
04
4.512
e
-
04
DTLZ2
3
Best
3.209
e
-
04
5.201
e
-
04
3.371
e
-
04
3.694
e
-
04
3.732
e
-
04
3.984
e
-
04
Median
4.561
e
-
04
5.335
e
-
04
6.631
e
-
04
7.536
e
-
04
8.547
e
-
04
9.368
e
-
04
Worst
6.255
e
-
04
6.421
e
-
04
7.767
e
-
04
7.859
e
-
04
7.956
e
-
04
9.559
e
-
04
4
Best
4.682
e
-
05
5.717
e
-
05
6.765
e
-
05
7.732
e
-
05
8.579
e
-
05
9.742
e
-
05
Median
5.392
e
-
05
2.821
e
-
04
2.922
e
-
04
8.486
e
-
04
8.783
e
-
04
8.886
e
-
04
Worst
1.104
e
-
04
1.211
e
-
03
1.366
e
-
03
1.455
e
-
03
1.454
e
-
03
1.857
e
-
03
5
Best
8.613
e
-
05
1.621
e
-
04
1.752
e
-
04
2.123
e
-
04
2.432
e
-
04
5.783
e
-
04
Median
7.687
e
-
04
1.922
e
-
03
1.956
e
-
03
2.513
e
-
03
2.727
e
-
03
2.926
e
-
03
Worst
1.038
e
-
03
2.458
e
-
03
2.569
e
-
03
2.834
e
-
03
2.956
e
-
03
3.549
e
-
03
DTLZ3
3
Best
6.123
e
-
04
6.222
e
-
04
6.360
e
-
04
7.251
e
-
04
7.423
e
-
04
7.757
e
-
04
Median
1.587
e
-
03
1.616
e
-
03
1.784
e
-
03
1.905
e
-
03
1.942
e
-
03
1.926
e
-
02
Worst
3.929
e
-
03
4.695
e
-
03
7.555
e
-
03
2.858
e
-
02
2.903
e
-
02
3.359
e
-
02
4
Best
1.516
e
-
04
1.826
e
-
04
1.961
e
-
04
1.968
e
-
04
2.114
e
-
04
2.552
e
-
04
Median
1.782
e
-
04
1.922
e
-
04
2.117
e
-
04
2.221
e
-
04
2.371
e
-
04
2.661
e
-
04
Worst
1.951
e
-
04
1.993
e
-
04
2.762
e
-
04
2.852
e
-
04
2.952
e
-
04
2.989
e
-
04
5
Best
5.342
e
-
04
7.932
e
-
04
4.011
e
-
04
5.829
e
-
04
5.956
e
-
04
6.559
e
-
04
Median
1.137
e
-
03
1.514
e
-
03
1.113
e
-
03
1.154
e
-
03
1.157
e
-
03
1.252
e
-
03
Worst
1.574
e
-
03
2.423
e
-
03
1.537
e
-
03
1.859
e
-
03
1.956
e
-
03
2.151
e
-
03
DTLZ4
3
Best
9.243
e
-
05
1.420
e
-
04
1.554
e
-
04
1.835
e
-
04
1.957
e
-
04
1.992
e
-
04
Median
1.092
e
-
04
1.752
e
-
04
2.211
e
-
04
2.777
e
-
04
2.856
e
-
04
2.969
e
-
04
Worst
1.892
e
-
04
1.971
e
-
04
2.867
e
-
04
2.893
e
-
04
2.916
e
-
04
2.984
e
-
04
4
Best
1.231
e
-
05
1.526
e
-
05
1.667
e
-
05
1.669
e
-
05
1.543
e
-
05
1.541
e
-
05
Median
1.526
e
-
05
1.727
e
-
05
1.731
e
-
05
1.732
e
-
05
1.650
e
-
05
1.759
e
-
05
Worst
1.635
e
-
05
1.793
e
-
05
1.797
e
-
05
1.841
e
-
05
3.857
e
-
05
2.879
e
-
05
5
Best
1.336
e
-
04
1.701
e
-
04
1.852
e
-
04
1.179
e
-
05
2.346
e
-
05
2.353
e
-
05
Median
1.392
e
-
04
2.024
e
-
04
2.267
e
-
04
1.451
e
-
05
2.556
e
-
05
2.759
e
-
05
Worst
2.052
e
-
04
8.421
e
-
04
9.760
e
-
04
1.817
e
-
05
9.854
e
-
04
9.954
e
-
04Table 6
Average and standard deviation of the HV values on WFG1 to WFG9 with six algorithms by different number of objectives.
Functions
m
Hmp/BBO
BBO/Complex
NSGAIII
MOEA/D-PBI
HYPE
GREA
WFG1
3
4.232
e
-
01
4.806
e
-
01
5.138
e
-
01
4.821
e
-
01
5.385
e
-
01
7.235
e
-
01
4
4.611
e
-
01
3.252
e
-
01
4.054
e
-
01
4.458
e
-
01
6.141
e
-
01
5.326
e
-
01
5
5.340
e
-
01
4.587
e
-
01
5.032
e
-
01
5.023
e
-
01
5.953
e
-
01
5.224
e
-
01
WFG2
3
8.658
e
-
01
8.538
e
-
01
8.616
e
-
01
7.184
e
-
01
8.485
e
-
01
8.901
e
-
01
4
9.181
e
-
01
8.705
e
-
01
8.061
e
-
01
7.934
e
-
01
8.801
e
-
01
9.342
e
-
01
5
9.523
e
-
01
9.401
e
-
01
9.232
e
-
01
9.101
e
-
01
9.239
e
-
01
9.324
e
-
01
WFG3
3
8.032
e
-
01
8.127
e
-
01
8.311
e
-
01
9.102
e
-
01
9.333
e
-
01
9.202
e
-
01
4
8.926
e
-
01
8.422
e
-
01
7.552
e
-
01
7.456
e
-
01
8.014
e
-
01
8.716
e
-
01
5
9.337
e
-
01
8.323
e
-
01
8.001
e
-
01
7.123
e
-
01
8.326
e
-
01
7.007
e
-
01
WFG4
3
7.212
e
-
01
7.362
e
-
01
7.852
e
-
01
6.952
e
-
01
8.654
e
-
01
8.852
e
-
01
4
9.012
e
-
01
9.002
e
-
01
8.567
e
-
01
8.688
e
-
01
8.893
e
-
01
8.324
e
-
01
5
9.386
e
-
01
9.201
e
-
01
8.862
e
-
01
8.559
e
-
01
8.756
e
-
01
8.453
e
-
01
WFG5
3
6.331
e
-
01
6.433
e
-
01
6.321
e
-
01
6.512
e
-
01
6.213
e
-
01
6.790
e
-
01
4
6.823
e
-
01
6.522
e
-
01
6.247
e
-
01
5.955
e
-
01
5.896
e
-
01
6.001
e
-
01
5
6.743
e
-
01
6.801
e
-
01
6.363
e
-
01
6.442
e
-
01
6.782
e
-
01
6.553
e
-
01
WFG6
3
6.832
e
-
01
6.655
e
-
01
6.324
e
-
01
6.725
e
-
01
6.859
e
-
01
6.531
e
-
01
4
6.521
e
-
01
6.454
e
-
01
6.447
e
-
01
6.353
e
-
01
6.553
e
-
01
6.321
e
-
01
5
6.772
e
-
01
6.521
e
-
01
6.232
e
-
01
6.325
e
-
01
6.526
e
-
01
6.326
e
-
01
WFG7
3
7.137
e
-
01
7.150
e
-
01
7.254
e
-
01
7.025
e
-
01
6.957
e
-
01
7.012
e
-
01
4
7.024
e
-
01
7.536
e
-
01
7.237
e
-
01
7.558
e
-
01
7.001
e
-
01
7.121
e
-
01
5
7.874
e
-
01
7.321
e
-
01
6.969
e
-
01
7.051
e
-
01
7.326
e
-
01
7.353
e
-
01
WFG8
3
6.231
e
-
01
6.020
e
-
01
6.151
e
-
01
5.925
e
-
01
6.050
e
-
01
6.012
e
-
01
4
6.020
e
-
01
6.552
e
-
01
6.327
e
-
01
6.239
e
-
01
6.153
e
-
01
6.271
e
-
01
5
6.286
e
-
01
6.001
e
-
01
6.112
e
-
01
6.139
e
-
01
6.210
e
-
01
6.213
e
-
01
WFG9
3
6.144
e
-
01
6.235
e
-
01
6.312
e
-
01
6.121
e
-
01
6.352
e
-
01
6.124
e
-
01
4
6.441
e
-
01
6.348
e
-
01
6.320
e
-
01
6.259
e
-
01
6.404
e
-
01
6.472
e
-
01
5
6.281
e
-
01
6.101
e
-
01
6.161
e
-
01
6.254
e
-
01
6.056
e
-
01
6.113
e
-
01Figure3 shows the parallel coordinates of PF obtained by Hmp/BBO and the other five MOEAs with the five-objective of DTLZ1. This run is involved in the result closest to the mean IGD value. A parallel coordinates system is a visual representation of the overall performance of the algorithm for high-dimensional space, where each row represents a point in a high-dimensional space. If the lines on each object on the graph are distributed in [0,1], it is shown that the convergence of the better algorithm, if the lines can be evenly distributed in [0,1], indicates that the distribution of the algorithm is better. From this figure, it is found that the Hmp/BBO is slightly better in convergence and diversity than BBO/Complex, NSGAIII, and MOEA/D-PBI. HYPE and GREA are far away from the PF because the maximum value of some objectives is much larger than 0.5. Obviously, the solutions achieved by HYPE and GREA are worse than the above four algorithms.Figure 3
Parallel coordinates figure by six algorithms on the five-objective DTLZ1. (a) Hmp/BBO; (b) BBO/Complex; (c) NSGAIII; (d) MOEA/D-PBI; (e) HYPE; (f) GREA.
(a)
(b)
(c)
(d)
(e)
(f)Performance scores are introduced to the global performance of compared algorithms. For a problem test question, suppose that there areS algorithms al1,al2,…,alS; let γij be 1, if ali outperforms alj in terms of IGD metric, and 0 otherwise. This value indicates how many other algorithms are better than ali on the problem test question. Therefore, the smaller the value is, the better the algorithm is. Then, performance score S(ali) is determined as(9)Sali=∑j=1j≠isγij.In Figure 4, the average performance scores for different number of objectives and different test problems are briefly summarized. Score of Hmp/BBO is smaller than other algorithms in the corresponding number of objectives.Figure 4
Average performance score over all test problems for different number of objectives. The smaller the score, the better the performance in the corresponding number of objectives.


## 5. Conclusions

In this paper, we propose a novel many-objective optimization algorithm called Hmp/BBO. It addresses the problem of a many-objective optimization which uses the mechanism of adaptive hierarchical. The problem is decomposed into many subsystems through PBI aggregate function. Through combining the advantages of MOEA/D, Hmp/BBO is expected to enhance the convergence ability and the valuable diversity performance. As it can be seen in the results obtained in Section4, Hmp/BBO performance can be enhanced by PBI aggregation function and the control the migration flow of n SIV between rich and poor islands. Within this process, the old features will not always be overwritten by the newly emigrated features from other islands. It has more flexible decomposition optimization options compared to other five state-of-the-art algorithms.The future work will discuss the Hmp/BBO in terms of objective number greater than five and in terms of solving constrained many-objective problems. The constrained many-objective problems seem to be a new challenge for MaOPs, and we try to extend our algorithm to solve them by combining constraint handling techniques. And also we would want to apply Hmp/BBO to solve more real-world problems.



---

*Source: 2462891-2017-03-30.xml*