UKSim 2009: 11th International Conference on Computer Modelling and Simulation

Empirical Analysis of Using Weighted Sum Fitness Functions in

NSGA-II for Many-Objective 0/1 Knapsack Problems

Hisao Ishibuchi, Noritaka Tsukamoto, Yusuke Nojima

Graduate School of Engineering, Osaka Prefecture University
hisaoi@cs.osakafu-u.ac.jp, nori@ci.cs.osakafu-u.ac.jp, nojima@cs.osakafu-u.ac.jp

Abstract toward the Pareto front. As a result, Pareto dominance-

based EMO algorithms can not efficiently drive the
Handling of many-objective problems is a hot issue population toward the Pareto front of a many-objective
in the evolutionary multiobjective optimization (EMO) problem. Pareto dominance-based EMO algorithms
community. It is well-known that frequently-used EMO often improve only the diversity of solutions without
algorithms such as NSGA-II and SPEA do not work improving their convergence toward the Pareto front.
well on many-objective problems whereas they have Various approaches have been proposed for improving
been successfully applied to a large number of test the scalability of EMO algorithms to many-objective
problems and real-world application tasks with two or problems (e.g., see [13]-[15] for a review). Whereas
three objectives. The main difficulty in the handling of those approaches clearly improve the convergence of
many-objective problems is that almost all solutions in solutions toward the Pareto front, the convergence
the current population of an EMO algorithm are non- improvement often involves an undesired side-effect:
dominated with each other. This means that Pareto Deterioration in the diversity of solutions [13]-[15].
dominance relation can not generate enough selection A simple approach to the scalability improvement
pressure toward the Pareto front. As a result, Pareto of Pareto dominance-based EMO algorithms is the use
dominance-based EMO algorithms such as NSGA-II of scalarizing fitness functions. This idea is simple but
and SPEA can not drive the current population toward effective. Actually it was clearly demonstrated in the
the Pareto front efficiently in a high-dimensional literature [11] that better results were obtained for
objective space of a many-objective problem. A simple many-objective problems by multiple runs of single-
idea for introducing additional selection pressure objective optimizers with scalarizing fitness functions
toward the Pareto front is the use of scalarizing fitness than Pareto dominance-based EMO algorithms.
functions. In this paper, we examine the effect of using Similar observations were also reported in [12]. In this
weighted sum fitness functions for parent selection and paper, we examine the effect of probabilistic use of
generation update on the performance of NSGA-II for weighted sum fitness functions on the performance of
many-objective 0/1 knapsack problems. NSGA-II for many-objective 0/1 knapsack problems
with up to ten objectives. As in our former study [16],
1. Introduction weighted sum fitness functions with uniformly
distributed weight vectors are probabilistically used for
Evolutionary multiobjective optimization (EMO) is parent selection and generation update in NSGA-II.
a very active research area in the field of evolutionary Through computational experiments, we demonstrate
computation [1]-[5]. Pareto dominance-based EMO that the performance of NSGA-II on many-objective
algorithms such as NSGA-II [6] and SPEA [7] have problems is clearly improved by the probabilistic use
been dominantly used in recent studies in this area. It is of weighted sum fitness functions.
well-known, however, that Pareto dominance-based This paper is organized as follows. In Section 2, we
EMO algorithms usually do not work well on many- demonstrate the difficulty in the handling of many-
objective problems with four or more objectives [8]- objective problems by Pareto dominance-based EMO
[12]. This is because almost all solutions in the current algorithms. In Section 3, we explain our hybrid
population of an EMO algorithm are non-dominated algorithm [16]. Experimental results by the hybrid
with each other when they are compared with respect algorithm on many-objective 0/1 knapsack problems
to many objectives. This means that Pareto dominance are reported in Section 4. Finally we conclude this
relation can not generate enough selection pressure paper in Section 5.

978-0-7695-3593-7/09 $25.00 © 2009 IEEE 71

DOI 10.1109/UKSIM.2009.54
2. Many-objective optimization population P U P’’ in Step 5. Each solution in the
merged (i.e., enlarged) population is evaluated by
In general, a k-objective maximization problem is Pareto sorting and the crowding distance in the same
written as follows: manner as Step 3. A prespecified number of the best
Maximize f ( x ) = ( f1 ( x ), f 2 ( x ), ..., f k ( x )) , (1) solutions are chosen from the merged population as the
next population P in Step 5.
subject to x ∈ X , (2) We applied NSGA-II [6] to 500-item 0/1 knapsack
where f (x) is the k-dimensional objective vector, fi (x) problems with 2, 4, 6, 8, 10 objectives. Those test
is the i-th objective to be maximized, x is the decision problems are denoted as k-500 problems where k is the
vector, and X is the feasible region. In this paper, number of objectives. Our two-objective and four-
multiobjective problems with four or more objectives objective problems (i.e., 2-500 and 4-500) are the same
are referred to as many-objective problems (i.e., k > 3). as those in Zitzler and Thiele [7]. We generated the
Let y and z be two feasible solutions of the k- other problems in the same manner as [7]. We also
objective maximization problem in (1)-(2). If the used the same greedy repair scheme as [7]. Parameter
following conditions hold between y and z, z can be values in NSGA-II were specified in this section as
viewed as being better than y: Population size: 200 individuals,
Crossover probability: 0.6 (Uniform crossover),
∀i , f i ( y ) ≤ f i ( z ) and ∃ j , f j ( y) < f j ( z) . (3) Mutation probability: 2/500 (Bit-flip mutation),
In this case, we say that z dominates y (equivalently y Stopping conditions: 100,000 generations.
is dominated by z: z is better than y). NSGA-II with the above-mentioned specifications
When y is not dominated by any other feasible was applied to each of the five test problems ten times.
solutions, y is referred to as a Pareto-optimal solution The average behavior of NSGA-II was examined for
of the k-objective maximization problem in (1)-(2). each test problem using the following five measures:
The set of all the Pareto-optimal solutions forms the
tradeoff surface in the objective space. This tradeoff (1) Number of non-dominated solutions
surface is called the Pareto front. EMO algorithms are We counted the number of non-dominated solutions
usually designed to search for a set of well-distributed in the merged population with 400 solutions in Step 5
non-dominated solutions that approximates the entire of NSGA-II in each generation. Experimental results
Pareto front very well. are summarized in Fig. 1. We can see that the number
NSGA-II [6] is currently the most well-known and of non-dominated solutions exceeded 200 in very early
frequently-used EMO algorithm in the literature. It has generations (i.e., after a few generations in the case of
the ( µ + λ )-ES style generation update mechanism as the 10-500 problem with ten objectives). This means
follows (usually µ = λ in NSGA-II): that all the 200 solutions in the next population after
the generation update procedure of NSGA-II became
Outline of NSGA-II non-dominated with each other within a small number
Step 1: P := Initialize (P) of generations. As a result, there was no selection
Step 2: while a termination condition is not satisfied, pressure toward the Pareto front in the parent selection
do phase in almost all generations of NSGA-II.
Step 3: P’ := Selection (P)
Step 4: P’’ := Genetic Operations (P’)
Number of Non-Dominated Solutions

2-500 4-500 6-500 8-500 10-500

Step 5: P := Generation Update (P U P’’) 400

Step 6: end while

Step 7: return (Non-dominated solutions (P)) 300

In Step 3, each solution in the current population is

evaluated using Pareto sorting (as a primary criterion) 200
and a crowding distance (as a secondary criterion). A
prespecified number of pairs of parents are selected
from the current population P by binary tournament 100

selection with replacement to form a parent population

P’ in Step 3. An offspring solution is generated from 0
1 10 100 1000 10000 100000
each pair of parents by crossover and mutation to form
Number of Generations
an offspring population P’’ in Step 4. The current and
offspring populations are merged to form an enlarged Figure 1. Number of non-dominated solutions.

72
(2) Maximum sum of the objective values: MaxSum If one carefully compares Fig. 3 with Fig. 1, one
The maximum value of the sum of the k objective may notice that the diversity started to increase in Fig.
values was calculated in each generation as follows: 3 just after the number of non-dominated solutions
k
exceeded 200 in Fig. 1 (i.e., just after all the solutions
MaxSum( Ψ ) = max ∑ f i ( x ) , (4) in the current population became non-dominated).
x∈Ψ i =1

where Ψ denotes the current population, and k is the 2-500 4-500 6-500 8-500 10-500
300
number of the given objectives. This MaxSum measure
evaluates the convergence of solutions toward the 250

Normalized Range
Pareto front around its center region.
200
Experimental results are summarized in Fig. 2. We
normalized all the experimental results for each test 150
problem so that the average result over ten initial
populations becomes 100. From Fig. 2, we can see that 100

the convergence toward the center region of the Pareto

50
front was slowed down by the increase in the number
of objectives. We can also observe the deterioration of 0
1 10 100 1000 10000 100000
the convergence in the later generations of NSGA-II
Number of Generations
for the 4-500, 6-500 and 10-500 problems.
Figure 3. Diversity of solutions.
2-500 4-500 6-500 8-500 10-500
130
(4) Sum of the maximum objective values: SumMax
The sum of the maximum value of each objective
Normalized MaxSum

was calculated in each generation as follows:

120
k
SumMax( Ψ ) = ∑ max f i ( x ) . (6)
x∈Ψ i =1
110
This measure evaluates the convergence of solutions
toward the Pareto front around its k edges. It can also
100 evaluate the diversity of solutions implicitly.
1 10 100 1000 10000 100000 (5) Hypervolume measure
Number of Generations Hypervolume [17] is one of the most frequently-
used performance measures for evaluating the quality
Figure 2. Convergence around the center region. of solution sets in the EMO community. It has been
also frequently used in a class of EMO algorithms
(3) Sum of the ranges of the objective values: Range called IBEAs (indicator-based evolutionary algorithms
The sum of the range of objective values of each [18]-[20]). The hypervolume of a solution set is the
objective was calculated in each generation as follows: volume of the dominated region by the solution set. A
k reference point in the objective space is needed to limit
Range( Ψ ) = ∑ [ max { f i ( x )} − min { f i ( x )} ] . (5) the dominated area. We used the origin of the objective
i =1 x∈Ψ x ∈Ψ
space of each test problem as the reference point for
This measure evaluates the diversity of solutions in the the hypervolume calculation.
objective space in each generation.
Experimental results are shown in Fig. 3 where the 3. Our hybrid algorithm
diversity was first degraded then improved by NSGA-
II. From the comparison between Fig. 2 and Fig. 3, we Our hybrid algorithm [16] probabilistically uses the
can see that the diversity in Fig. 3 was degraded in the following weighted sum fitness function:
early generations where the convergence in Fig. 2 was
improved. On the contrary, the convergence in Fig. 2 g W ( x, w ) = w1 ⋅ f1 ( x ) + ⋅ ⋅ ⋅ + wk ⋅ f k ( x ) , (7)
was not improved in the later generations where the
diversity in Fig. 3 was improved. These observations where w = ( w1 , w2 , ..., wk ) is a weight vector.
suggest that the convergence and the diversity were We generated a set of uniformly distributed weight
improved in different phases of evolution. vectors from the following conditions as in [24]:

73
 w1 + w2 + L + wk = d , (8) for parent selection (PPS) and generation update (PGU):
wi ∈ {0, 1, 2, ..., d }, i = 1, 2, ..., k , (9) PPS = 0.0, 0.2, 0.4, 0.6, 0.8, 1.0,
PGU = 0.0, 0.2, 0.4, 0.6, 0.8, 1.0.
where d is a user-definable positive integer. Almost the
same idea was also used in [23]. In our computational We also examined several specifications of d in (8).
experiments, we examined various values of d. Experimental results are shown in Fig. 5 for d = 4 (126
NSGA-II is the framework of our hybrid algorithm. weight vectors) and Fig. 6 for d = 8 (1287).
When a pair of solutions are to be selected as parents
from the current population, the weighted sum scheme
is used with a probability PPS in our hybrid algorithm. (×10 25 )
3.20
In the weighted sum scheme for parent selection, a
weight vector is randomly selected from the set of

Hypervolume
3.00
uniformly distributed weight vectors in (8)-(9). The
weighted sum scheme is also used in the same manner
2.80
with a probability PGU for generation update in our
hybrid algorithm. Our hybrid algorithm is the same as 2.60
NSGA-II except for the use of the weighted sum 0.016
0.008
scheme for parent selection and generation update. It 2.40 0.004
should be noted that our hybrid algorithm is exactly 0.2 0.4 0.002 PM
0.6 0.8 0.001
the same as NSGA-II when PPS = PGU = 0.0 (i.e., when PC 1.0
the weighted sum scheme is never invoked).
Figure 4. NSGA-II on 6-500 (Hypervolume).
4. Results of our hybrid algorithm
We performed computational experiments under the (×10 25 )
following conditions: 3.20

Population size: 200 individuals,

Hypervolume

3.00
Stopping conditions: 2,000 generations.
Before examining the effect of using the weighted 2.80
sum fitness function, we first examined the sensitivity
of the performance of NSGA-II to the specification of 2.60
1.0
the crossover and mutation probabilities. We examined 0.8
all the 5x5 combinations of the following probabilities: 2.40 0.6
0.0 0.2 0.4 PGU
Crossover probability: 0.2, 0.4, 0.6, 0.8, 1.0, 0.4 0.6 0.2
PPS 0.8 1.0 0.0
Mutation probability: 0.001, 0.002, 0.004, 0.008, 0.016.
For each combination, we calculated the average Figure 5. Hybrid on 6-500 (d = 4: 126 vectors).
value of the hypervolume measure over ten runs for
each of the 2-500, 4-500 and 6-500 test problems.
Since the hypervolume calculation takes a long time
for many-objective problems, we did not use it for the (×10 25 )
3.20
other test problems: 8-500 and 10-500. Due to the page
limitation, we only show experimental results on the 6-
Hypervolume

3.00
500 problem in Fig. 4. We can see that the choice of a
mutation probability has a large effect on the average 2.80
value of the hypervolume measure. We chose the
combination of the crossover probability 0.6 and the 2.60
1.0
mutation probability 0.004 based on the results for the 0.8
three test problems (e.g., Fig. 4). Hereafter, we use this 2.40 0.6
0.0 0.2 0.4 PGU
combination in our computational experiments. 0.4 0.6 0.2
Then we applied our hybrid algorithm to the 6-500 PPS 0.8 1.0 0.0
problem. We examined all the 6x6 combinations of the
following probabilities of the weighted sum scheme Figure 6. Hybrid on 6-500 (d = 8: 1287 vectors).

74
 fitness function. Whereas the Range measure in Fig. 10
100000 was somewhat decreased, Fig. 11 does not suggest any
severe negative effect on the diversity of solutions.
99000
MaxSum

98000
158000
97000
155800
96000 1.0

MaxSum
0.8 153600
95000 0.6
0.0 0.2 0.4 PGU
0.4 0.6 0.2 151400
PPS 0.8 1.0 0.0
149200 1.0
Figure 7. MaxSum by Hybrid (6-500 with d = 4). 0.8
147000 0.6
0.0 0.2 0.4 PGU
0.4 0.6 0.2
PPS 0.8 1.0 0.0
25000
Figure 9. Hybrid on 10-500 (MaxSum).
22500
Range

20000 53000

17500 43000
1.0
0.8
Range

15000 0.6
0.4 33000
0.0 0.2
0.2
PGU
0.4 0.6
PPS 0.8 1.0 0.0
23000
1.0
Figure 8. Range by Hybrid (6-500 with d = 4). 0.8
13000 0.6
0.0 0.2 0.4 PGU
0.4 0.6 0.2
From the comparison of Fig. 4 by NSGA-II with PPS 0.8 1.0 0.0
Fig. 5 and Fig. 6, we can see that the probabilistic use
of the weighted sum fitness function clearly improved Figure 10. Hybrid on 10-500 (Range).
the performance of NSGA-II. It should be noted that
the right bottom corner with PPS = PGU = 0.0 of Fig. 5
and Fig. 6 is the same as NSGA-II. The performance 176000
of NSGA-II at the right bottom corner of each figure
was improved by probabilistically using the weighted 174000
sum fitness function especially for generation update
SumMax

(i.e., by increasing PGU). We can also see our hybrid 172000

algorithm worked well in a wide range of d (d = 4 in
Fig. 5 and d = 8 in Fig. 6). 170000
1.0
To examine the behavior of our hybrid algorithm, 0.8
0.6
the MaxSum and Range measures are shown for the 168000 0.4
case of d = 4 in Fig. 7 and Fig. 8, respectively. The
0.0 0.2
0.2
PGU
0.4 0.6
convergence was improved from NSGA-II (i.e., from PPS 0.8 1.0 0.0
the case of PPS = PGU = 0.0) in Fig. 7 without severely
Figure 11. Hybrid on 10-500 (SumMax).
degrading the diversity (see Fig. 5 and Fig. 8).
Experimental results on the 10-500 problem by our
hybrid algorithm with d = 4 (715 weight vectors) are 5. Conclusions and future research
summarized in Figs. 9-11. The convergence property
of NSGA-II toward both the center region of the In this paper, we showed the probabilistic use of the
Pareto front (Fig. 9) and its ten edges (Fig. 11) was weighted sum fitness function improved the scalability
improved by the probabilistic use of the weighted sum of NSGA-II to many-objective 0/1 knapsack problems.

75
We also showed that its use in the generation update Evolutionary Computation, pp. 3959-3966, Vancouver,
phase has a dominant effect. Future research issues July 16-21, 2006.
include the use of other scalarizing fitness functions [13] H. Ishibuchi, N. Tsukamoto, and Y. Nojima,
(e.g., scalarizing achievement function), computational “Evolutionary many-objective optimization: A short
experiments on other test problems, and performance review,” Proc. of 2008 IEEE Congress on Evolutionary
comparison with other EMO algorithms such as IBEAs Computation, pp. 2424-2431, Hong Kong, June 1-6, 2008.
[18]-[21], MSOPS-II [22] and MOEA/D [23]. [14] H. Ishibuchi, N. Tsukamoto, and Y. Nojima, “Behavior
This work was supported in part by Grant-in-Aid of evolutionary many-objective optimization,” Proc. of
10th International Conference on Computer Modeling
for Scientific Research (B) (20300084).
and Simulation, pp. 266-271, Cambridge, April 1-3, 2008.
[15] H. Ishibuchi, N. Tsukamoto, Y. Hitotsuyanagi, and Y.
References Nojima, “Effectiveness of scalability improvement
attempts on the performance of NSGA-II for many-
[1] K. Deb, Multi-Objective Optimization Using Evolution- objective problems,” Proc. of 2008 Genetic and
ary Algorithms, John Wiley & Sons, Chichester, 2001. Evolutionary Computation Conference, pp. 649-656,
[2] C. A. C. Coello, D. A. van Veldhuizen, and G. B. Atlanta, July 12-16, 2008.
Lamont, Evolutionary Algorithms for Solving Multi- [16] H. Ishibuchi, T. Doi, and Y. Nojima, “Incorporation of
Objective Problems, Kluwer Academic Publishers, scalarizing fitness functions into evolutionary
Boston, 2002. multiobjective optimization algorithms,” Lecture Notes
[3] C. A. C. Coello and G. B. Lamont, Applications of Multi- in Computer Science 4193: Parallel Problem Solving
Objective Evolutionary Algorithms, World Scientific, from Nature - PPSN IX, pp. 493-502, Springer, Berlin,
Singapore, 2004. September 2006.
[4] A. Abraham, L. C. Jain, and R. Goldberg (eds.), [17] E. Zitzler and L. Thiele, “Multiobjective optimization
Evolutionary Multiobjective Optimization: Theoretical using evolutionary algorithms – A comparative case
Advances and Applications, Springer, Berlin, 2005. study,” Lecture Notes in Computer Science, vol. 1498, pp.
[5] K. C. Tan, E. F. Khor, and T. H. Lee, Multiobjective 292-301, Springer, Berlin, September 1998.
Evolutionary Algorithms and Applications, Springer, [18] E. Zitzler and S. Künzli, “Indicator-based selection in
Berlin, 2005. multiobjective search,” Lecture Notes in Computer
[6] K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, “A Science 3242: Parallel Problem Solving from Nature -
fast and elitist multiobjective genetic algorithm: NSGA- PPSN VIII, pp. 832-842, Springer, Berlin, 2004.
II,” IEEE Trans. on Evolutionary Computation 6 (2), pp. [19] M. Emmerich, N. Beume, and B. Naujoks, “An EMO
182-197, April 2002. algorithm using the hypervolume measure as selection
[7] E. Zitzler and L. Thiele, “Multiobjective evolutionary criterion,” Lecture Notes in Computer Science 3410:
algorithms: A comparative case study and the strength Evolutionary Multi-Criterion Optimization - EMO 2005,
Pareto approach,” IEEE Trans. on Evolutionary pp. 62-76, Springer, Berlin, 2005.
Computation 3 (4), pp. 257-271, November 1999. [20] N. Beume, B. Naujoks, and M. Emmerich, “SMS-
[8] V. Khara, X. Yao, and K. Deb, “Performance scaling of EMOA: multiobjective selection based on dominated
multi-objective evolutionary algorithms,” Lecture Notes hypervolume,” European Journal of Operational
in Computer Science 2632: Evolutionary Multi-Criterion Research 180 (3), pp. 1653-1669, September 2007.
Optimization - EMO 2003, pp. 367-390, Springer, Berlin, [21] T. Wagner, N. Beume, and B. Naujoks, “Pareto-,
April 2003. aggregation-, and indicator-based methods in many-
[9] R. C. Purshouse and P. J. Fleming, “Evolutionary many- objective optimization,” Lecture Notes in Computer
objective optimization: An exploratory analysis,” Proc. Science 4403: Evolutionary Multi-Criterion Optimization
of 2003 IEEE Congress on Evolutionary Computation, - EMO 2007, pp. 742-756, Springer, Berlin, March 2007.
pp. 2066-2073, Canberra, December 8-12, 2003. [22] E. J. Hughes, “MSOPS-II: A general-purpose many-
[10] A. Jaszkiewicz, “On the computational efficiency of objective optimiser,” Proc. of 2007 IEEE Congress on
multiple objective metaheuristics: The knapsack problem Evolutionary Computation, pp. 3944-3951, Singapore,
case study,” European Journal of Operational Research September 25-28, 2007.
158 (2), pp. 418-433, October 2004. [23] Q. Zhang and H. Li, “MOEA/D: A multiobjective
[11] E. J. Hughes, “Evolutionary many-objective evolutionary algorithm based on decomposition,” IEEE
optimization: Many once or one many?,” Proc. of 2005 Trans. on Evolutionary Computation 11 (6), pp. 712-731,
IEEE Congress on Evolutionary Computation, pp. 222- December 2007.
227, Edinburgh, September 2-5, 2005. [24] T. Murata, H. Ishibuchi, and M. Gen, “Specification of
[12] H. Ishibuchi, Y. Nojima, and T. Doi, “Comparison genetic search directions in cellular multi-objective
between single-objective and multi-objective genetic genetic algorithm,” Lecture Notes in Computer Science
algorithms: Performance comparison and performance 1993: Evolutionary Multi-Criterion Optimization - EMO
measures,” Proc. of 2006 IEEE Congress on 2001, pp. 82-95, Springer, Berlin, March 2001.

76