MaOEA/I: Many-objective Evolutionary Algorithm Based on Indicator Iε+

Sifeng Zhu, Chengrui Yang and Jiaming Hu

(School of Computer and Information Engineering, Tianjin Chengjian University, Tianjin, 300384, China)

Abstract：Balancing the diversity and convergence of the population is challenging in multi-objective optimization. The work proposed a many-objective evolutionary algorithm based on indicator Iε+ (MaOEA/I) to solve the above problems. Indicator Iε+(x,y) is used for environmental selection to ensure diversity and convergence of the population. Iε+(x,y) can evaluate the quality of individual x compared with individual y instead of the whole population. If Iε+(x,y) is less than 0, individual x dominates y. If Iε+(x,y) is 0, individuals x and y are the same. If Iε+(x,y) is greater than 0, no dominant relationship exists between individuals x and y. The smaller Iε+(x,y), the closer the two individuals. The dominated individuals should be deleted in environmental selection because they do not contribute to convergence. If there is no dominant individual, the same individuals and similar individuals should be deleted because they do not contribute to diversity. Therefore, the environmental selection of MaOEA/I should consider the two individuals with the smallest Iε+(x,y). If Iε+(x,y) is not greater than 0, delete individual y; if Iε+(x,y) is greater than 0, check the distance between individuals x, y, and the target point and delete the individual with a longer distance. MaOEA/I is compared with 6 algorithms until the population does not exceed the population size. Experimental results demonstrate that MaOEA/I can gain highly competitive performance when solving many-objective optimization problems.

Keywords：many-objective; evolutionary algorithm; indicator; diversity; convergence

0 Introduction

Optimization with multiple objective functions is called multi-objective optimization problems (MOPs)[1]. Since multiple objective functions often conflict with each other, MOPs are more complex than single objective optimization problems (SOPs). When MOPs have more than three objective functions, they are mentioned as many-objective optimization problems (MaOPs)[2-3]. MaOPs have more objective functions than MOPs, which makes solving more challenging.

multi-objective evolutionary algorithms (MOEAs) can solve MOPs that simulate natural biological evolution processes[4]. Traditional MOEAs can get better performance when dealing with MOPs; however, there will be a series of problems when dealing with MaOPs[5]. One of the important problems is that more objective functions will produce a large number of non-dominated solutions, and sometimes the whole population will be non-dominated solutions. Too many non-dominated solutions will make the environmental-selection strategy based on non-dominated relations fail.

Researchers have proposed a series of improved algorithms to meet the challenge brought about by the increased objectives. These algorithms are divided into the decomposition-based algorithm, laxity-based algorithm, and Indicator-based algorithm. The decomposition-based algorithm decomposes a MaOP into simple SOPs or MOPs, and it solves and merges these subproblems separately to obtain the solution to the MaOP. The representatives of such algorithms are the multi-objective evolutionary algorithm based on decomposition (MOEA/D)[6], reference-vector-guided evolutionary algorithm (RVEA)[7], and non-dominated sorting genetic algorithm III (NSGA-III)[8].

The laxity-based algorithm modifies the dominating relationship to expand the dominating region of the solution and alleviate the dominating failure to a certain extent. Such algorithms proposed recently include the many-objective evolutionary algorithm adopting dynamic angle vector-based dominance relation (DAV-MOEA)[9], many-objective particle swarm optimization based on adaptive fuzzy dominance (MAPSOAF)[10], etc.

Indicator-based algorithm proposes an indicator to map the objective values to a certain number, and the indicator is also used for environmental selection or mating selection.Immune-inspired resource allocation strategy for many-objective optimization (MaOEA/IRAS)[11]is a new indicator-based algorithm. The sparse region theory in Ref. [11] proposes a new indicator, which defined by the Euclidean distances of their projected points on the unit hyperplane. Solutions far from hyperplane are considered to be in the sparse region.The algorithm has less exploration in the sparse region, and exploring the region can increase the diversity of the algorithm. The indicator-based evolutionary algorithm (IBEA)[12]is the firstIε+-indicator-based algorithm and provides a common framework for indicator-based methods.

The IBEA can be combined with arbitrary indicators. Although binary performance measureIε+(x,y) can be combined with arbitrary indicators, directly usingIε+(x,y) into the selection process also has good performance. The IBEA proposes a fitness function based onIε+(x,y) (fitness assignment), which considers the individual information of the entire population to evaluate individuals.Iε+(x,y) can be directly used for environmental selection (worst contribution) to balance the diversity and convergence, and only the information between two solutions is used for selection. The many-objective evolutionary algorithm based on indicatorIε+(x,y) is proposed.

1 Propaedeutics

1.1 Indicator-based Algorithm

Classification method[13]classifies IB mechanisms into two main categories: IB Selection (IB-environmental selection, IB-density estimation, and IB-archiving) and IB-mating selection. Many-objective metaheuristics based on theR2indicator (MOMBI)[14]and Indicator-based evolutionary algorithm (IBEA) use the IB-environmental selection mechanism. The hypervolume estimation algorithm (HypE)[15]and IGD-based many-objective evolutionary algorithm (MaOEA/IGD)[16]use the IB-density estimator. The adaptive archiving algorithm for storing nondominated vectors (LAHC)[17]uses IB-archiving methods.IB-mating selection involves the identification of good parent solutions based on quality indicator values. IB-mating selection mechanisms are used by theR2Indicator-based evolutionary algorithm for multi-objective optimization (R2-IBEA)[18], MaOEA/IGD, and adaptive reference points-based multi-objective evolutionary algorithm (ARMOEA)[19].

1.2 Indicator Iε+(x,y)

A general optimization problem is defined byd-dimensional decision spaceX,m-dimensional objective spaceY, andmobjective functionsf1,f2,f3,…,andfm.

y=(f1(x),f2(x),f3(x),…,fm(x))∈Yfor each decision variablex=(x1,x2,…,xd)∈X. All objective functions are assumed to be minimized, andY?m.Iε+(x,y) is defined as

Iε+(x1,x2)=minε(?i∈{1,2,…,m},

(1)

Iε+(x,y) can be regarded as the enhancement of Pareto dominance, andIε+(x,y) can be directly used as a fitness value; therefore,Iε+(x,y) is used in the work. The two-objective problem is taken as an example (see Fig. 1).

Two solutionsX1andX2do not dominate each other on the left.S1andS2represent the distance betweenX2andX1on object 1 and that betweenX1andX2on object 2, respectively.Iε+(X1,X2)=S2.S2is interpreted as that ifX1wants to dominateX2,S2needs to be optimized at least. Similar toIε+(X2,X1)=S1, ifX2wants to dominateX1,S1needs to be optimized at least. Two solutionsX1andX2are on the right, andX2dominatesX1.Iε+(X2,X1)<0, that is, whenIε+(x,y)<0,xdominatesy.

Fig.1 Two cases of Iε+(x,y)

2 Proposed MaOEA/I

2.1 Framework of MaOEA/I

The overall framework of the proposed MaOEA/I is presented in Algorithm 1.

Algorithm1 General Framework of MaOEA/I Input :N (population size) ,maxFE (maximum function evaluation times)Output :P (final population)1: P=Initialization(N) 2: while FE

The MaOEA/I starts from randomly initialized populationPcontainingNindividuals. Afterward,Pundergoes an evolution procedure. Offspring populationOis first generated in each generation by performing mating selection, simulated binary crossover[20], and polynomial mutation[21]onP.Second,PandOare merged to form new populationPtof 2Nindividuals. Finally, environmental selection is performed to selectNelite individuals. The evolution procedure is repeated until the termination criterion is satisfied. The mating selection and environmental selection of the MaOEA/I are introduced in the following sections.

2.2 Mating Selection

The binary tournament selection method is used for a mating selection. FunctionFbased onIε+(x,y) is used as the fitness value of the mating selection (see Eq. (2)).

Fx=-minIε+(x,xi),xi∈P/{x}

(2)

whereFxis the fitness value of individualx;xiis the other individual except forxin populationP.

2.3 Environmental Selection

Environmental selection mainly depends on fitness assignments in the IBEA.

F(x1)=∑x2∈P/{x1}-e-I(x2,x1)/κ

(3)

wherePis the population;κthe fitness scaling factor. FitnessF(x) is related toIε+(x,y) betweenxand the whole population without itself.

The MaOEA/I has no fitness for the individual.IndicatorIε+(x,y) can measure individuals by its value.Iε+(x,y) is directly used to evaluate the quality of individuals.

A population of 100 individuals is taken as an example, and each iteration produces 100 new individuals.Both the IBEA and MaOEA/I need to calculateIε+(x,y) between each individual. TheIBEA usesIε+(x,y) to calculate the fitness of the 200 individuals, while the MaOEA/I usesIε+as the indicator of environmental selection. Although the environmental selection of the MaOEA/I needs to consider more values and the situation is more complex (with 200 fitness of IBEA and 200×199Iε+),it can more accurately select the individual with the lowest contribution.

The environmental selection procedure of the proposed MaOEA/I is presented in Algorithm 2.

Algorithm 2 Environmentals election Input: Pt (temporary population), count (number of individuals in Pt), and N (population size)Output: P (final population)1: I=CalculationI(Pt,2N) 2: Sort I from small to large3: i=1 4: while count>N do5: Get the elements in I (defined as Ii ) and corresponding individu-als xi,yi in order6: if xi∈Pt∧yi∈Pt, then7: Delete yi from Pt 8: count=count-1 9: end if10: i=i+111: end while12: P=Pt 13: Return P

CalculateIε+(x,y) of temporary populationPt, and sortIfrom small to large. WhenIε+(x,y)≤0,xdominatesy.SmallerIε+(x,y) means greater dominance. WhenIε+(x,y)>0, the closerxis toy, the smallerIε+(x,y) is. Therefore, the work gives priority to deleting the most dominant individual. When all the dominant individuals are deleted and the number of individuals in temporary populationPtis still larger thanN, one of the closest two individuals is deleted. The inferior individuals are deleted fromPtone by one until the number of individuals inPtisN.The individuals with poor convergence and diversity in the population are gradually eliminated by repeating the above operations, and the population converges and is evenly distributed on the Pareto front (see Fig. 2).

Iε+(x,y) calculation procedure is presented in Algorithm 3. In particular, wheni=j,I(i,j)=+∞ is set becauseIε+(x,y) cannot be calculated for the same individual.

2.4 Calculation of Iε+(x,y)

Algorithm 3 Calculation IInput: P (population) and N (population size)Output: I( Iε+ matrix)1: Normalize the objective values of all individuals in P2: Generate matrix Iof N×N, the value of the element in the matrix is +3: for i=1∶N do4: for j=1∶N do5: if i≠j do6: Calculate Iε+(xi,xj) by Eq. (1) and fill in storage matrixI(i,j)7: end if8: end for9: end for10:Return I

2.5 Computational Complexity Analysis

The computational complexity of the proposed MaOEA/I mainly depends on the mating selection and environmental selection. The computational complexity of the mating selection isO(N2) in the worst case. Environmental selection includes the calculation ofIε+(x,y), sort, and deletion. The calculation ofIε+(x,y) includesO(2mN) required for normalization.mis the objective number of the problem, and the calculated value ofIε+(x,y) requiresO(4mN2).Sort requiresO(4N2log2(2N)), and deletion requiresO(2N).Overall, the computational complexity of MaOEA/I isO(N2)+O(2mN)+O(4mN2)+O(4N2log2(2N))+O(2N)=O((4m+log2(2N))N2).

3 Experiment and Discussion

The proposed MaOEA/I was compared with other 6 algorithms, including IBEA[11], MOMBI-II[22], MaOEA/IGD[15], NSGA-III[8], RPEA[23], and RVEA, to test its performance in MaOPs. This section describes the test problems, performance indicator, experimental environment, parameter settings used in the experimental study, results, and discussion.

3.1 Test Problems

MaF[24]test problems are used to verify the performance of the MaOEA/I. MaF test problems have many properties of the Pareto Front, which can test the performance of solving MaOPs from many aspects.

The number of objectiveMis 5, 10, 15, and 25, respectively. The default values of the number of decision variableDis used for MaF test problems. CalculateDwithD=M+K-1 in MaFs 1-12, andK=10.CalculateDwithD=M+K-1 in MaF 7, andK=20.Dis fixed to 2 in MaFs 8 and 9. CalculateDwithD=M×20 in MaFs 14 and 15.

3.2 Performance Indicator

Inverse generation distance (IGD)[25]and Hypervolume (HV)[26]were used to evaluate the convergence and diversity of results. Each algorithm was independently executed 30 times on each test problem to reduce the impact of random factors on performance evaluations. The Wilcoxon rank sum test with a significance level of 0.05 was used to discuss the difference in algorithm performance.

3.3 Experimental Environment

The computer was configured with 16G memory, Intel (R) Core (TM) i7-10875H CPU@2.30GHz processor, and Windows10 X64 system. All algorithms were compared on PlatEMO[27]based on MATLAB, and the version of the PlatEMO was v3.5.

3.4 Parameter Settings

The population size with 5, 10, 15, and 25 objectives were 150, 200, 250, and 300, respectively. The termination condition was that the algorithm had exhausted the number of evaluations. The maximum number of evaluations was 100000. All evolutionary algorithms in the work used binary crossover and polynomial mutation to generate offspring. The crossover probability and mutation probability were set to 1.0 and 1/D, andDwas the number of decision variables. The fitness scaling factor of IBEA was set to 0.5. The number of evaluations for nadir point estimation of the MaOEA/IGD was set to 100×N.The parameter controlling the rate of change of penalty in RVEA was set to 2, and the frequency of employing reference vector adaptation was set to 0.1. The variance threshold,tolerance threshold, and record size of nadir vectors of MOMBI-II were set to 0.5, 0.001, and 5. The ratios of individuals used to generate reference points and parameters determining the difference between the reference point and the individuals of RPEA were set to 0.4 and 0.1, respectively. There was no need to set parameters for the MaOEA/I.

3.5 Results and Discussion

Tables 1 and 2 show the results of each algorithm on MaF(5-objective). The IBEA, MOMBI-II, MaOEA/IGD, NSGA-III, RPEA, RVEA, and MaOEA/I are in columns 1-7, respectively.

The MaOEA/I obtains significantly better performance on MaF testing problems with different dimensions and different difficulties (see Table 1). Although the performance of the MaOEA/I is not as good as that in Table 1, the MaOEA/I is still better than other algorithms (see Table 2). Fig. 3 shows the IGD changing curves of MaFs 1, 3, 5, 6, 7, and 13. IGD values obtained by the MaOEA/I in the 6 test problems can rapidly converge to a relatively good position and continue to optimize,which shows its performance in balancing convergence and diversity. The IGD of the IBEA, MaOEA/IGD, NSGA-III, RVEA, and MOMBIII fluctuates during the search process (see Fig. 3 (f)).

Table 3 shows the average running time of the algorithm for calculating MaFs. Environmental selection is more complex and the computation will increase with the expansion of the population; therefore, the MaOEA/I has no advantage over other algorithms in running time.

Fig. 4 shows IGD on 5-objective MaFs.

The MaOEA/I can obtain stable results on most problems in 30 repeated experiments, and it is only inferior to other algorithms on MaFs 6 and 15.

4 Conclusions

Aiming at the environmental selection strategy based on non-dominated relation failure and the difficulty in the balance of convergence and diversity in MaOPs, the work proposed the MaOEA/I. The MaOEA/I usedIε+(x,y) for environmental selection.Iε+(x,y) could select the dominated solution and the solution close in space with the strengthening non-dominated relationship, which considers convergence and diversity.

Table 3 Running time

The IBEA focused on global information and usedfitness assignment usingIε+(x,y); however, MaOEA/I used the local meaning and worst contribution. If two solutions were too close, no matter where they were in the population, one of them must be deleted. It solved the environmental selection strategy based on non-dominated relation failure and contributed to dealing with the irregular Pareto front. The experimental results showed that the MaOEA/I has a good performance on MaF problems, with effectiveness in balancing convergence and diversity.

Fig. 4 IGD on 5-objective MaFs