Heman Aguirre

Arnaud Liefooghe
email: arnaud.liefooghe@lifljr

Sebastien Verel
email: verel@i3s.unice.fr

Kiyoshi Tanaka

A Study on Population Size and Selection Lapse in Many-objective Optimization

In this work we study the effects of population size on selection and performance scalability of two dominance-based algorithms applied to many-objective optimization. Our aim is to understand the relationship between the size of the Pareto optimal set, a characteristic of the many-objective problem at hand, the population size and the ability of the algorithm to retain Pareto optimal solutions in its population and find new ones. This work clarifies important issues of the dynamics of evolutionary algorithms on many-objective landscapes, particularly related to survival selection. It shows that optimal solutions are dropped from the population in favor of suboptimal solutions that appear non-dominated when survival selection is applied. It also shows that this selection lapse, the dropping of optimal solution, affects the discovery of new optimal solutions and is correlated to population size and the distribution of solutions that survival selection renders. Selection makes less mistakes with larger populations and when the distribution of solutions is better controlled. The results of this study will be helpful to properly set population size and have a clearer idea about the performance expectation of the algorithm.

I . INTRODUCTION

Conventional evolutionary multi-objective (EMO) algo rithms [ 1 ] are known to scale up poorly to high dimensional objective spaces [START_REF] Ishibuchi | Evolutionary Many Objective Optimization: A Short Review[END_REF] , particularly dominance-based algorithms. This lack of scalability has been attributed mainly to some characteristics of the landscapes and inappropriate operators for selection and variation. In many-objective landscapes the number of solutions in the Pareto optimal set increases expo nentially [START_REF] Aguirre | Insights on Properties of Multi•objective MNK-Landscapes[END_REF] with the number of objectives. Assuming that the size of the decision space remains unchanged, an increase in the number of objectives also implies that these large num ber of Pareto optimal solutions become spread over broader regions of decision space [START_REF] Sato | Genetic Diversity and Effective Crossover in Evolutionary Many-objective Optimization[END_REF] . Analysis of many-objective landscapes shows that this is the case for the Pareto optimal set and also for Pareto suboptimal sets [START_REF] Aguirre | Insights on Properties of Multi•objective MNK-Landscapes[END_REF] . These characteristics of many-objective landscapes are directly correlated to the effectiveness of the operators of selection and variation and affect the dynamics of the optimizer. For example, the large number of non-dominated solutions causes dominance-based selection to become random, and their spread on decision space causes mating to pair distant solutions making recombination too disruptive. In addition to the operators for selection and variation, the population size greatly influences the dynamics of the algorithm. However, its effects on large dimensional objectives spaces are not well understood.

In this work we study the effects of population size on performance scalability of two dominance-based algorithms applied to many-objective optimization, a conventional evo lutionary multi-objective (EMO) algorithm and an evolution ary many-objective (EM yO) algorithm, using relatively small population sizes and also using large population sizes set as a fraction of the true Pareto optimal set. We are particularly interested in understanding the relationship between the size of the Pareto optimal set, a characteristic of the many-objective problem at hand, the population size the algorithm uses and the ability of the algorithm to retain true Pareto optimal solutions in its population and find new ones. We analyze the dynamics of the algorithms by observing at each generation the number of true Pareto optimal solutions that the algorithms find. We use MNK-landscapes with 3 -6 objectives and 20 bits, for which it is possible to know by enumeration all true Pareto optimal solutions of the landscapes. This work clarifies important issues of the dynamics of evolutionary algorithms on many-objective landscapes, particularly related to survival selection. The results of this study will also be helpful to properly set population size and have a clearer idea about the performance expectation of the algorithm.

II. METHODOLOGY

In our study we use four MNK-landscapes [START_REF] Aguirre | Insights on Properties of Multi•objective MNK-Landscapes[END_REF] randomly generated with m = 3, 4, 5, 6 objectives, n = 20 bits, and k = 1 epistatic bit. For each landscape we enumerate all its solutions and classify them to non-dominated fronts. The exact number of true Pareto optimal solutions POST found by enumeration are IPOSTI = 152, 1554, 6265, and 16845 for m = 3, 4, 5, and 6 objectives, respectively. Similarly, the exact number of non-dominated fronts of the landscapes are 258, 76, 29, and 22, respectively.

We run the algorithms for a fixed number of generations, collecting all generated solutions. Once evolution is over, we compare the set of POST with the sets of unique non dominated solutions obtained at each generation after survival selection to determine which are true Pareto optimal solutions, count the number of true Pareto optimal solutions found at each generation, and their accumulated number found during evolution. That is, in our analysis we assume that the aim of the algorithms is to find all true Pareto optimal solutions. In this work, we relate performance scalability to the capacity of the algorithm to achieve its aim either when we increase the number of objectives for a given population size or when we increase the population size for a given number of objectives.

The motivation to use landscapes with n = 20 bits and k = 1 epistatic bit is that in small landscapes with minimum non-linearity it should be relatively simple for the algorithm to hit the optimal set. Experiments in these small and simple problems allow us to focus our study on the ability of the algorithm to retain optimal solutions in its population, which is directly correlated to the effectiveness of survival selection and the maintenance of selection pressure to find new optimal solutions. Also, it is feasible to enumerate these small landscapes to know exactly all true Pareto optimal solutions, which are important in our analysis.

In this work we use NSGA-II as the evolutionary multi objective optimizer and the Adaptive E-Sampling and E-Hood algorithm [START_REF] Aguirre | Adaptive E-Sampling and E-Hood for Evolutionary Many-Objective Optimization[END_REF] as the evolutionary many-objective optimizer. NSGA-II is a well known algorithm and due to space limita tions it is not described here. The interested reader is referred to [START_REF] Deb | A Fast Elitist Non Dominated Sorting Genetic Algorithm for Multi-Objective Optimiza tion: NSGA-Il[END_REF] for details about NSGA-II. In the following we describe the recently proposed many-objective optimizer used in our study.

III. THE AESEH ALGORITHM

A. Concept

Adaptive E-Sampling and E-Hood (AESEH) [START_REF] Aguirre | Adaptive E-Sampling and E-Hood for Evolutionary Many-Objective Optimization[END_REF] is an elitist evolutionary many-objective algorithm that applies E dominance principles both for survival selection and for clus tering and mating solutions located close by in objective space.

In multi-objective optimization, dominance is used for survival selection and to rank solutions in the elite surviving population, so that mating selection can give more reproductive opportunities to dominant individuals. However, this is imprac tical in many-objective optimization because of the large num ber of non-dominated solutions. In AESEH, dominance is used during the survival selection step of the algorithm to eliminate inferior dominated solutions, but it has no role in ranking the surviving population. For the majority of generations, survival selection is achieved by E-sampling, a E-dominance based procedure, which samples randomly from the large set of non dominated solutions and eliminates solutions E-dominated by the samples. The aim is to get a set of surviving solutions spaced according to the distribution implicit in the mapping function f ( x ) f-t€ / ( x ) used for E-dominance. Only during the few initial generations, where the number of non dominated solutions is smaller than the size of the surviving population, E-sampling plays no role during survival.

After survival selection, in AESEH there is not an explicit ranking that could be used to bias mating. Rather, the algorithm uses a procedure called E-hood creation to cluster solutions in objective space. This method is also based on E-dominance. Here, a randomly sampled solution from the surviving popula tion and its E-dominated solutions determine the neighborhood, so that recombination can take place between individuals located close by in objective space. The motivation to restrict mating is to enhance the effectiveness of recombination in many-objective problems, where the difference in variable space between individuals in the population is expected to be larger than in multi-objective problems and therefore more disruptive for recombination.

The main steps of the AESEH are as follows.

Step 1 Set Es f-0, used in E-sampling truncation, and its initial step of adaptation �s . Set Eh f-0, used in E hood creation, its initial step of adaptation �h and the reference number of neighborhoods NJ} e J to adapt Eh .

Set population P f-0 and create randomly the initial population Q. Set population size Psize f-I QI .

Step 2 Evaluate the offspring population Q.

Step 3 Calculate non-dominated sorting on the population that results from joining the current population P and its offspring Q to obtain the non-dominated fronts F = {Fd, i = 1, 2, • • • , NF.

Step 4 Truncate the sorted non-dominated fronts F to obtain the surviving population P of size Psize using the E sampling truncation procedure set with parameter Es .

Step 5 Adapt Es and its step of adaptation �s using as reference the population size Psize and the number of sampled solutions Ns returned by E-sampling called from E-sampling truncation.

Step 6 Create neighborhoods from the surviving population P with the procedure E-hood creation, set with parameter Eh • Step 7 Adapt Eh and its step of adaptation �h using as reference the number of created neighborhoods N H and the number NJ} e J specified by the user.

Step 8 Create a pool of mates p ' with procedure E-hood mating that pairs solutions within the neighborhoods.

Step 9 Recombine and mutate the mated individuals in P ' to create the offspring population Q.

Step 10 Repeat from Step 2 if the termination criterion has not been met.

The next sections include additional details about the main procedures of the algorithm.

B. E-Sampling Truncation (Step 4)

Survival selection is implemented by the E-sampling trun cation procedure. This procedure receives the sets of solutions F created by non-dominated sorting and selects exactly Psize surviving solutions from them.

In case the number of non-dominated solutions IFl l > Psize, it calls E-sampling with parameter Es to get from Fl its extreme solutions £, a subset of randomly sampled solu tions S and their cs-dominated solutions DEs . The surviving population P always includes extreme solutions £ and it is complemented with solutions from S and possibly from DEs .

If S overfills P, solutions in S are randomly eliminated as survivors. Otherwise, if after adding S to P there is still room for some solutions, the required number are randomly chosen from DEs .

Otherwise (I FI I < Psize), the sets of solutions Fi are copied iteratively until P is filled. If set Fi, i > 1, overfills P, the required number of solutions are chosen randomly from it. Neighborhoods are created from the surviving population by the c-hood creation procedure, which is also based on c-dominance. This procedure randomly selects an individual from the surviving population and applies c-dominance with parameter Ch . A neighborhood is formed by the selected so lution and its ch-dominated solutions. Neighborhood creation is repeated until all solutions in the surviving population have been assigned to a neighborhood.

Mating for recombination is implemented by the procedure c-hood mating. Neighborhoods are considered to be elements of a list. Neighborhoods are assigned to the list in the same order they were created. To select two mates, first a neighbor hood from the list is specified deterministically in a round robin schedule. Then, two individuals are select randomly within the specified neighborhood, so that an individual will recombine with other individual that is located close by in objective space. Due to the round-robin schedule, the next two mates will be selected from the next neighborhood in the list. When the end of the neighborhoods list is reached, mating continues with the first neighborhood in the list. Thus, all individuals have the same probability of being selected within a specified neighborhood, but due to the round-robin scheduling individuals belonging to neighborhoods with fewer members have more recombination opportunities that those belonging to neighborhoods with more members. Once the pool of all mates P' has been established, they are recombined and mutated according to the order they were selected during mating.

D. Adaptation (Step 5 and Step 7)

The number of sampled solutions N s by c-sampling de pends on the value set to Cs (2: 0). Larger values of Es imply that sampled solutions cs-dominate larger areas, increasing the likelihood of having more cs-dominated solutions excluded from the sample. The algorithm adapts Cs at each generation so that N s is close to the population size Psize. The closer N s is to Psize, the larger the number of surviving solutions that will be spaced according to the distribution implicit in the mapped function used for c-dominance.

Similarly, the number of created neighborhoods N H de pends on the value set to Ch (2: 0). Larger values of Ch imply that sampled solutions ch-dominate larger areas, increasing the likelihood of having more ch-dominated solutions that form its neighborhood, and therefore fewer neighborhoods are created.

The algorithm adapts Ch at each generation so that N H is close to a user specified number NJj e J .

The adaptation rule, similar for both processes, is as

follows. If N > Ref it increases the step of adaptation � +--min (� x 2, �max) and E +--E + �. Otherwise, if N < Ref it decreases � +--max (� x 0.5, �mi n ) and E +--max (E -�, O.O).
In this work we set initial values EO = 0.0 and �o = 0.005. Also, �max = 0.05 and �mi n = 0.0001. that after few generations all solutions in the population are non-dominated, IFI I = IPI • However, not all solutions in FI are true Pareto optimal solutions, i.e. 1FT! < IFI I = IPI. Also, it is important to note that 1FT! fluctuates up and down after an initial increase. On the other hand, when we set the population size to a value larger than the number of true Pareto optimal solutions, IPI = 200 > IPOST I = 152, it can be seen in Fig. 1 (a.3) that the instantaneous non-dominated set is a subset of the population, FI = FI C P. Also, note that from generation 35 onwards, all non-dominated solutions in the population are also true Pareto optimal, FI = F'[. In this case, the algorithm finds and keeps in P almost all true Pareto optimal solutions, 147 out of 152, during the latest stage of the search.

It is known that the number of true Pareto optimal solutions IPOSTI increases considerably with the number of objectives. However, this is often ignored and the algorithm is set with a very small population size compared to IPOSTI. what we observe. When population sizes much smaller than the number of true Pareto optimal solutions are used, it is clear from our results that the capacity of the algorithm to keep true Pareto optimal solutions reduces considerably with the number of objectives, although the size of search space remains fixed and there are many more true Pareto optimal solutions in landscapes with a larger number of objectives.

To explain this behavior, Fig. 2 shows the instantaneous number of true Pareto optimal solutions in the population IFFI and its accumulated number IAFFI over the generations for population sizes IPI = 50, 100, and 200. Note that a large number of true Pareto optimal solutions are found by the algorithm. However, not all these solutions remain in the population (except in the case m = 3 IPI = 200).

Some of these solutions are lost from one generation to the next one during the survival selection step of the algorithm. At this step, the algorithm joins the population P with the offspring population Q and ranks individuals with respect to dominance-depth. The best rank is given to true Pareto optimal solutions and also to some others that are not true optimal but appear non-dominated in the combined population. As indicated above, we call the set of best ranked non-dominated solutions obtained from P U Q as Fl . If this set Fl is larger than the population P, a sample of them P = F l � Fl is chosen based on crowding distance during the survival step. At this point, some true Pareto optimal solutions are dropped in favor of less crowded non-optimal solutions. Summarizing, P = F l C Fl and therefore Fl' c Fl is more likely to occur for population sizes smaller than the number of true Pareto optimal solutions IPOST I.

For a given population size less true Pareto optimal solu tions are observed in the instantaneous population P when we increase the number of objectives. However, the accumulated number of true Pareto optimal solutions is bigger in problems with a larger number of objectives. For example, see Fig. 1 (a.2), (b.2), (c.2) and Fig. 2 (a)-(c) for P = 100. This suggests that the algorithm finds a larger number of different true Pareto optimal solutions from generation to generation in prob lems with more objectives, although its ability to retain non dominated solutions in the instantaneous population reduces. These results show that the effectiveness of the algorithm in many-objective landscapes depends strongly on the size of the population. However, it should be noted that larger populations demand more computational time and memory. Also, a relatively larger number of solutions need to be evaluated for the same number of generations. For example, after 100 generations, using a population size 4/3 of POST, the conventional EMO algorithm used in this study evaluates approximately a number of solutions equivalent to 2%, 19%, 76% and 215% of the size of the search space for m = 3, 4, 5, and 6 objectives, respectively. Thus, although a sufficiently large population allows us to find almost all true Pareto optimal solutions, the effectiveness of large populations should be evaluated against a reasonable budget of fitness evaluations.

In the following we study the effects of population size on the AESEH algorithm. FigA shows the number of solutions in Fl and FT over the generations for m = 3, 4, and 5 objectives, running AESEH for 100 generations with three different population sizes IPI = 50, 100 and 200. Comparing with Fig. I , it can be seen that AcScH finds and keeps more true Pareto optimal solutions in the population than NSGA II. This difference becomes more remarkable for 4 or more objectives in all population sizes. For example, in m = 4 and 5 objectives AcScH keeps in the population approximately twice as many true Pareto solutions than NSGA-II. This shows the advantages of using c-sampling during the truncation of the population in the many-objective optimizer. However, similar to NSGA-II, note that for the same population size less true Pareto solutions are present in the instantaneous population P for landscapes with a larger number of objectives. Note that a larger number of true Pareto optimal solutions are accumulated by AcScH than by NSGA-II. That is, in addition to instantaneously keeping in the population a larger number of true Pareto optimal solutions, the many-objective optimizer is able to find more new solutions from generation to generation, which translates into a larger number of accumulated true Pareto optimal solutions. Note that the difference in the number of accumulated solutions becomes larger with the number of objectives. Also, it is worth noting that for 4 or more objectives the number of accumulated true Pareto optimal solutions found by AcScH with a population of 50 is larger than the number of accumulated solutions by NSGA-II with a population of 100. Likewise, AcScH with a population of 100 performs similar or better than NSGA-II with a population of 200. From these figures note that when a population larger than IPOST I is used both algorithms perform similarly in terms of the number of true Pareto optimal solutions found. However, for smaller populations, AcScH is more effective and efficient, especially for 4 or more objectives. For example, using a population size equivalent to 1/3 of IPOSTI, NSGA-II finds more than 70% of the true Pareto optimal solutions after 1 00 generations. AcScH with the same population size can find a similar number of solutions expending only half the number of generations and fitness evaluations. As mentioned above and shown in Fig.S, AcScH's efficiency becomes more evident when very small population sizes are used.

V. CONCLUSIONS

In this work we analyzed the effects of population size on selection and performance scalability of a conventional evolu tionary multi-objective algorithm and an evolutionary many objective algorithm for many-objective optimization, correlat ing population size to the size of the optimal set. We showed that optimal solutions are dropped from the population when survival selection is applied, especially in small populations. Since both algorithms used in our study are dominance based, this suggests that rather than the inability to distinguish among non-dominated solutions, an important issue for scalability of the algorithm is the distribution of solutions that survival selection renders. The many-objective optimizer uses the c sampling procedure, which induces a uniform distribution, and keeps more optimal solutions in the population than the multi-objective optimizer that uses crowding distance with no clear indication of what distribution it produces. Larger populations can cover a broader region in objective space, reduce the effect of dropping optimal solutions, and increase the effectiveness of the optimizers in many-objective problems. In fact, the performance of a conventional evolutionary multi objective optimizer can scale up fairly well to high dimensional objective spaces if the size of the population is sufficiently large compared to the size of the true Pareto optimal set. If the aim of the optimizer is to find all optimal solutions, our study suggests that population sizes similar or larger than the size of the optimal set might be required. However, this population sizes become impractical for many-objective problems due to the exponentially large number of solutions in the optimal set. If the aim of the algorithm is to find a significant number of optimal solutions under a reasonable budget of fitness evaluations, then more efficient algorithms like the many-objective optimizer used in this study become important. We also showed that the rate of discovering new optimal solutions is higher in problems with more objectives, although the ability to keep optimal solutions in the population reduces with the number of objectives.

As future work, we would like to analyze population size and its relationship to scalability using larger landscapes and other problems. Also, we would like to analyze in a similar manner other multi and many-objective optimizers that use different strategies for survival selection. Particularly, it will be interesting to study the behavior of indicator based algorithms [START_REF] Zitzler | Indicator-based Selection in Multiobjective Search[END_REF] .

C

  . c-Hood Creation and c-Hood Mating (Step 6 and Step 8)

  I n the case o f adapting the parameter C s used for truncation, the above rule is called with c = Cs , � = �s , N = Ns, and Re f = Psize • On the other hand, in the case of the parameter Ch used for neighborhood creation, the above rule is called with c = Ch, � = �h, N = NH, and Ref = NJj e J . IV. EXPERIMENTAL RESULTS AND DISCUSSION A. Operators of Variation and Parameters In both algorithms, NSGA-II and AcScH, we use two point crossover with rate pc = 1.0, and bit flip mutation with rate pm = lin. Also, for AcScH we set the reference neighborhood size H:;:� to 20 individuals. The mapping function f ( x ) ME / ( x ) used for c-dominance in c sampling truncation and c-hood creation is additive, as follows i = 1, 2, • • • , m ( I ) B. NSGA-/l In this section we study the effects of population size on NSGA-II. Let us denote by FI the set of non-dominated solutions in the combined population P U Q of parents and offspring before survival selection, by FI <;;; FI the set of non dominated solutions in population P after survival selection, and by F'[ the set of solutions in FI that are true Pareto optimal solutions.

Fig. 1

 1 Fig. 1 shows the number of solutions in FI and F'[ over the generations for m = 3, 4, and 5 objectives, running the algorithm for 100 generations with three different population sizes IPI = 50, 100 and 200. First we analyze results for m = 3 objectives. When we set population size to IPI = 50 or 100, a value smaller than the number of true Pareto optimal solutions IPOST I = 152, it can be seen in Fig. 1 (a. l ) and (a.2)

Fig. 1 .Fig. 2 .

 12 Fig. 1. Results by NSGA-II. Number of non-dominated FI and actual number of true Pareto optimal solutions F{ in the population over the generations. I POS T I = 152, 1554 and 6265 for m = 3, 4 and 5 objectives, respectively.

Fig. 3 .

 3 Fig. 3. Results by NSGA-II increasing the number of objectives setting the population size as a fraction of the number of true Pareto Optimal Solutions of the landscape POS T Number of true Pareto optimal solutions found at each generation FT and their accumulated number over the generations AFT -Population sizes 1/3, 2/3 and 4/3 of POS T for m = 4, 5, and 6 objectives.

Fig. 2 (

 2 Fig.2 (a) and Fig.3 (a)-(c) show results for m = 3, 4, 5 and 6 objectives using population sizes that correspond approximately to 1/3, 2/3 and 4/3 of the set POST, re-

Fig. 4 .

 4 Fig. 4. Results by Ac:Sc:H. Number of non•dominated Fl and actual number of true Pareto optimal solutions F{ in the population over the generations. I POS T I = 152, 1554 and 6265 for m = 3, 4 and 5 objectives, respectively.

  Fig. S . Results by Ac:Sc:H increasing the number of objectives keeping the population size smaU compared to the number of true Pareto Optimal Solutions of the landscape POS T Number of true Pareto optimal solutions found at each generation F{ and their accumulated number over the generations AFT Population sizes IPI = 50, 100, and 200 for m = 3, 4, and 5 objectives. Results by NSGA-II are also included for comparison. 7000 1600 1400 6000 § 5000 "5 �4000 0

Fig. 6 .

 6 Fig. 6. Results by Ac:Sc:H increasing the number of objectives setting the population size as a fraction of the number of true Pareto Optimal Solutions of the landscape POS T Number of true Pareto optimal solutions found at each generation F{ and their accumulated number over the generations AFT -Population sizes 1/3, 2/3 and 4/3 of POS T for m = 4, 5, and 6 objectives. Results by NSGA-II are also included for comparison.

Fig.S shows

  Fig.S shows the accumulated number of true Pareto optimal solutions found by AcScH together with those found by NSGA-II for comparison. Results are shown for m = 3, 4, 5, and 6 objectives using population size I PI = 50, 100 and 200.

Fig

  Fig.S (a) and Fig.6 (a)-(c) show results by AcScH andNSGA-II for m = 3, 4, 5 and 6 objectives using population sizes that correspond approximately to 1/3, 2 j 3 and 4/3 of the set of true Pareto optimal solutions POS , respectively.