# An Improved MOEA/D Based on Reference Distance for Software Project Portfolio Optimization

Authors: Jing Xiao; Jing-Jing Li; Xi-Xi Hong; Min-Mei Huang; Xiao-Min Hu; Yong Tang; Chang-Qin Huang
Journal: Complexity
 (2018)

---

## Abstract

As it is becoming extremely competitive in software industry, large software companies have to select their project portfolio to gain maximum return with limited resources under many constraints. Project portfolio optimization using multiobjective evolutionary algorithms is promising because they can provide solutions on the Pareto-optimal front that are difficult to be obtained by manual approaches. In this paper, we propose an improved MOEA/D (multiobjective evolutionary algorithm based on decomposition) based on reference distance (MOEA/D_RD) to solve the software project portfolio optimization problems with optimizing 2, 3, and 4 objectives. MOEA/D_RD replaces solutions based on reference distance during evolution process. Experimental comparison and analysis are performed among MOEA/D_RD and several state-of-the-art multiobjective evolutionary algorithms, that is, MOEA/D, nondominated sorting genetic algorithm II (NSGA2), and nondominated sorting genetic algorithm III (NSGA3). The results show that MOEA/D_RD and NSGA2 can solve the software project portfolio optimization problem more effectively. For 4-objective optimization problem, MOEA/D_RD is the most efficient algorithm compared with MOEA/D, NSGA2, and NSGA3 in terms of coverage, distribution, and stability of solutions.


---

## Body

## 1. Introduction

Project portfolio management (PPM) is a management process to help project managers to analyze and acquire all information of current proposed projects. PPM helps decision makers to sort and prioritize each project according to certain criteria, such as business goals, strategic value, cost, and resource constraints. A key step of PPM is to decide which projects to invest in an optimal manner. Project portfolio optimization (PPO) is the effort to make the best decisions to select the best mix of projects from all candidate projects. Manual approaches include PPO include Q-Sort, analytic hierarchy process, and portfolio matrices [1–3]. These approaches are time-consuming and limited to the number of projects they can deal with. The project portfolio problem may be dealt as a multiobjective optimization problem, and it is difficult to tackle [4, 5]. Software managers and researchers used branch-and-bound approach, simulated annealing and Tabu search, and so on to obtain the uniformly distributed Pareto-optimal solutions [6–8]. It is hard to find an algorithm to deal with this problem efficiently when the complexity of the problem grows exponentially with the number of projects.Within this context, multiobjective evolutionary algorithms (MOEA) [9] which can obtain Pareto-optimal solutions are promising to solve the project portfolio optimization problem [10–12]. Pareto front-based MOEAs are superior to manual approaches in a way that they are able to create a set of efficient portfolios, for which it can be assured that there exist no solutions in the search space that promise better values in at least one of the objectives and offer at least the same values in all the other objectives [5]. MOEAs can obtain approximate optimal solutions. Furthermore, MOEAs can deal with the computational complexity with an increasing number of projects. That is why there are lots of publications devoted to solving portfolio optimization problems using MOEAs and also there are many applications of MOEAs in finance and economics areas [13].Compared with general project portfolio optimization using MOEAs, the number of publications dedicated to the MOEAs’ applications to software project portfolio problems is scarce. Kremmel et al. [5] introduced a multiobjective evolutionary approach, mPOEMS, to find the Pareto-optimal front for software project portfolio optimization problem. However, the paper only studied 2-objective optimization. In this paper, we first propose an improved MOEA/D [14] algorithm based on reference distance (MOEA/D_RD) to alleviate the inefficiency of MOEA/D’s weighted sum approach. Then, we use MOEA/D_RD to solve the 2-, 3-, and 4-objective software portfolio optimization problem. Comparison and analysis experiments are conducted among MOEA/D_RD, MOEA/D, NSGA2 [15], and NSGA3 [16].The rest of this paper is organized as follows. Section2 discusses the related work of portfolio optimization using evolutionary algorithms. Section 3 describes the software portfolio selection model we have used. The proposed MOEA/D_RD is explained in detail in Section 4, and the empirical experiments are described and discussed in Section 5. The last section gives the conclusion and lists the future work.


## 2. Related Work

The first formalization of methodology for solving portfolio optimization problems was proposed by Markowitz [17] in the 1950s. Markowitz defined a portfolio as a vector of real numbers that contains the weight corresponding to each available asset and stated that the investor searches the portfolio that minimizes the risk while maximizing the return ideally. However, with the increasing number of projects and many constraints in real world, the simple assumptions in Markowitz model are infeasible and it is hard to find an exact algorithm to deal with the problem. As such, the first use of genetic algorithm (GA) for optimizing project portfolio was proposed by Arnone et al. in 1993 [18]. The authors divided the population of a GA into different subpopulations and produced different portions of the Pareto front.An obvious advantage of MOEAs is their ability to produce, in one single run, a complete approximation of the Pareto front. MOEAs are suitable to solve the portfolio optimization problem since the aim of the problem is to provide a set of Pareto front solutions, that is, the best possible tradeoffs among the objectives, among which the managers can choose the most appropriate solution. In [19], the Markowitz model was solved with an MOEA in which the selection is carried out through a Pareto-ranking procedure. The authors used Sharpe’s ratio instead of the classical density estimators such as crowding distance to break ties between solutions from the same Pareto front. Lin et al. [20] implemented integer encoding, simulated binary crossover, and parameter-based mutation within the NSGA2 to solve the investment portfolio optimization problem with fixed transaction costs and minimum lots. Subbu et al. [21] combined a Pareto-sorting evolutionary algorithm with linear programming for investment portfolio optimization. The Pareto-sorting evolutionary algorithm is used to retain the nondominated solutions found along the search by a small population size and an archive. Branke et al. [22] combined NSGA2 with the critical line algorithm to obtain a continuous Pareto front for portfolio optimization. NSGA2 was first employed to define convex subset of the original search space, then the critical line algorithm was applied on every subset to form the complete Pareto front. Bradshaw et al. [23] employed an evolutionary algorithm similar to SPEA2 [24] to solving the portfolio optimization problem. In [25], the authors compared six MOEAs on the classical Markowitz model. The results showed that SPEA2 and NSGA2 performed more effectively among the six studied algorithms. [26] compared three MOEAs, that is, NSGA2, SPEA2, and PESA [27], to solve the Markowitz model with three objectives: return value, risk, and number of assets in the portfolio and found that SPEA2 can obtain the best performance for the test cases.Aforementioned work is based on Markowitz mean-variance model, and there are also a few publications devoted to other portfolio optimization models using MOEAs. Khalili-Damghani et al. [28] presented a hybrid fuzzy rule-based multiobjective framework for sustainable project portfolio selection. NSGA2 was applied to obtain the nondominated solutions. The proposed framework simultaneously considered the accuracy maximization and the complexity minimization objectives. Fernandez et al. [29] proposed a nonoutranked ant colony optimization II method for optimizing portfolio problem. The method incorporates integer linear programming to avoid clearly suboptimal regions in the search space and a priori preference system to focus the algorithmic effort on the most preferred region in the search space. Doerner et al. [4] introduced a Pareto ant colony optimization algorithm for solving the portfolio selection problem. Tofighian and Naderi [30] employed an ant colony optimization algorithm for solving the project selection and scheduling to optimize both total expected benefit and resource usage variation. Mavrotas et al. [31] studied the robustness analysis methodology for multiobjective project selection optimization.Relatively speaking, the publication with respect to software project management using MOEAs is scarce. Rodríguez et al. [32] employed NSGA2 and a system dynamics simulation model to generate the Pareto front needed by software project managers to find the best values for initial team size and schedule estimates for a given project with the optimal cost, time, and productivity. Gueorguiev et al. [33] formulated software project planning problem as biobjective optimization. Robustness and complete time are treated as two competing objectives, and SPEA2 was employed to obtain the Pareto solutions. The most closely related to this paper is the work by Kremmel et al. [5] in which the authors used Constructive Cost Model II (COCOMO II) [34] and a multiobjective evolutionary algorithm to find the Pareto front for software project portfolio optimization. Only 2-objective Pareto front solutions were studied in Kremmel’s work. In this paper, we extend Kremmel’s work and propose an improved MOEA/D algorithm called MOEA/D_RD for software project portfolio optimization. Optimization problems with 2, 3, and 4 objectives are studied using 50 projects that follow the validated COCOMO II model criteria, and the proposed approach is compared with several state-of-the-art evolutionary algorithms.The next section presents the list of goals borrowed from Kremmel’s software portfolio selection model [5]. We only use the first 4 objectives and use the synergy goal as a constraint in our framework.


## 3. Software Portfolio Selection Model

Generally, a multiobjective optimization problem can be presented as the following:Find a vectorx∈Ω, Ω is decision (variable) space.
(1)maximizeQx=q1x,q2x,…,qnx,Q:Ω→Rn,under some constraints, where Ω is the decision (variable) space, Q consists of n real-valued objective functions, and Rn is called the objective space.Suppose there are two solutionsu,v∈Rn; u is said to dominate v if and only if ui≥vi for every i∈1,2,…,n and uj>vj for at least one index j∈1,2,…,n. A point x∗∈Ω is Pareto optimal to (1) if there is no point x∈Ω such that Qx dominates Qx∗. Qx∗ is then called a Pareto-optimal objective vector. In other words, any improvement in a Pareto-optimal point in one objective must lead to deterioration in at least one other objective. The set of all the Pareto-optimal points is called Pareto set, and the set of all the Pareto-optimal objective vectors is the Pareto front (PF).Specifically, a solution for software project portfolio optimization is represented by a vector with the length of the maximum available projects. The task can be formalized as follows:Find a vectorx=x1,x2,…,xp∈M1×⋯×Mp, where Mi⊆M, M=0,1,2,…,T×12, such that the objective vector y=q1x,q2x,…,qnx is maximum, where xi is greater than 0 if project i is selected, and 0 if not; p is the number of candidate projects; M is a set of the number of months in the planning horizon; Mi is the months in which project i can start; T is the number of timeframes in the planning horizon. qix is the ith optimization objective. In this work, we have considered the first 4 objectives defined in Kremmel’s model, and thus the value of n is 4. These 4 objectives are defined as follows:
(1)
Potential revenue (q1x). Software project investors invest human resources, knowledge, and money into a project, with the goal of obtaining benefits from this investment. The potential projects for the project portfolio have to be evaluated with regard to their potential financial revenue. Thus, the first objective deals with the need to maximize potential overall portfolio return. It is calculated as the following:
(2)q1x=∑i=1pri⋅wi,where ri is the potential revenue of project i, and wi is 1 if xi > 0 and 0 if xi = 0. Obviously, the greater the overall potential revenue, the better the solution is.
(2)
Strategic alignment (q2x). Project selection optimization has to consider the problems with little commitment from business leaders, poor alignment of projects to strategy, little coordination between projects, and conflicting project objectives. The strategic alignment on the portfolio level should be maximized. It is calculated as follows:
(3)q2x=∑i=1pai⋅wi,where ai is the strategic alignment value of project i, and wi is 1 if xi > 0 and 0 if xi = 0. The greater the overall strategic value, the better the solution is.
(3)
Resource usage distribution metric (q3x). Resources in each timeframe are limited. This objective is to maximize the resource usage per timeframe and at the same time have the best distribution among the timeframe. Its value is between 0 and 1, where 1 means full resource consumption in each timeframe and 0 means that, at least in one timeframe, there is no resource consumed. Thus, the objective function to maximize is expressed as follows:
(4)q3x=∏t=1T∑o=1l∑i=1pro,t,i⋅wi∑o=1tRo,t,where o is the type of a resource (there are l different resource types); t is the timeframe; T is the number of timeframes in the planning horizon; ro,t,i is the type o resource consumption of project i in timeframe t, and Ro,t is the type o resource limit in timeframe t. The closer the q3x is to one, the better the solution is.
(4)
Risk (q4x). The risk objective is calculated as follows:
(5)q4x=1−1p∑i=1priskix⋅wi,where riskix is the risk value of project i. The closer the q4x is to one, the better the solution is.The constraints we have used are listed as follows:(a)
Project starting timeframes. Most projects cannot start in an arbitrary timeframe, but very often in a few distinct timeframes. It is also possible that a project can only start in one timeframe in order to meet a special market opportunity. A feasible solution must adhere to the constraint of project starting time.
(b)
The “must-select” restriction. Due to the legal and economic circumstances, a project may have to be included in a valid portfolio. Therefore, it should be possible to define a “must-select” restriction for portfolio optimization.
(c)
Logical relationships. There are several logical relationships between projects such as linear, dependent, and mutually exclusive relationships. Linear relationship means if a certain project is selected for a portfolio, one or more predecessor projects must be selected obligatorily. If two projects are dependent, it means that the two projects must be selected to a portfolio together. On the contrary, two projects may not be selected for the same portfolio and thus are mutually exclusive.
(d)
Synergy effects. The synergy effect constraint is one of the objectives in the original Kremmel’s model. We consider it as a constraint when we optimize the first objective, that is, the potential revenue. If two projects are selected for the same portfolio, the total revenue could be more than the sum of the two project’s revenues or less than the sum. The synergy effects are also considered in the Pareto ant colony optimization approach presented in [4].In this paper, we consider the aforementioned four objectives and the four constraints for the software project portfolio problem. In the next section, we introduce the algorithm called MOEA/D_RD to solve the multiobjective optimization problem for software project selection.


## 4. An Improved MOEA/D Based on Reference Distance (MOEA/D_RD)

### 4.1. MOEA/D Based on Weighted Sum Approach

In this paper, we improve the weighted sum approach in MOEA/D algorithm [14] for solving the software project selection optimization problem. The approach considers a convex combination of the different objectives. Let λ=λ1,…,λmT be a weight vector; m is the number of objectives; fix is the ith objective to be optimized; and λi≥0 for all i=1,…,m and ∑i=1mλi=1. Then the optimal solution to the following scalar optimization problem
(6)maximizegwsx∣λ=∑i=1mλifixsubjecttox∈Ωis a Pareto-optimal point to (1) as we can see that qix corresponds to one of the objectives fix in (6), where we use gwsx∣λ to emphasize that λ is a coefficient vector in this objective function, where x is the variables to be optimized. To generate a set of different Pareto-optimal vectors, one can use different weight vectors λ1,λ2,…,λN in the above scalar optimization problem and the optimized problem is divided into N subproblems. The greater N is, the wider the search space is. However, the weighted sum-based MOEA/D has several drawbacks and we illustrate them as follows.Given an example, as shown in Figure1, f1 and f2 are two objectives; Fxi is the objective function of solution xi; PF is the assumed optimal Pareto front; x1, x2, and x3 are three solutions corresponding to weight vectors λ1,λ2, and λ3. The ideal case is that the algorithm moves x1, x2, and x3 to meet the PF. MOEA/D randomly picks up two solutions from the neighborhood of x2 and generates a new solution using genetic operators. If the fitness value of the new solution is better than x2, then x2 is replaced by the new solution. If the new solution is fallen in the overlapping area of the search spaces of neighboring solutions x1 and x2, then both x1 and x2 are replaced by the new solution. The strategy is efficient at the earlier search stage of the algorithm, and it can make the search direction move fast to the PF. But at the late stage of the algorithm, as shown in Figure 2, there is no overlapping area among most of the search spaces of solutions. The neighboring solutions of x2 cannot generate a new effective solution. The search process would stagnate at the late stage of the algorithm.Figure 1
Solution generation process of MOEA/D.Figure 2
The late stage of MOEA/D.If the PF is a line, as shown in Figure3, for the weight vector λ2, all solutions on the PF line are the same optimal solutions with the same fitness values. Among the solutions between the weight vectors λ1 and λ2, the optimal solution is the intersection point of PF and f2. Similarly, among the solutions between the weight vectors λ2 and λ3, the optimal solution is the interaction point of PF and f1. Assume that a solution with respect to λ2 during iteration is x2, x2 would not be replaced by x∗ even if x∗ is closer to λ2 and is a better solution. It is because x2 and x∗ are equally optimal with the same fitness values on the PF line. The search process is in a standstill.Figure 3
Pareto front as a line.If the PF is a convex curve, as shown in Figure4, assume that x2 is the solution with respect to λ2 during iteration; when the algorithm finds another solution x∗, x2 will be replaced by x∗ since the fitness value of x∗ is better than x2. Similarly, the solutions with respect to λ1 and λ3 will be replaced by the solutions that are located close to the ends of PF. At the late search process of the algorithm, most of solutions are aggregated at the ends of PF and the algorithm suffers in stagnation.Figure 4
Pareto front as convex.From the above analysis, we can see that the traditional weighted sum approach of MOEA/D suffers poor search ability. In the next subsection, we propose an improved MOEA/D based on reference distance to enhance the search ability of the algorithm.


### 4.2. An Improved Algorithm MOEA/D_RD Based on Reference Distance

To alleviate the aforementioned problems of MOEA/D, we propose an improved version based on reference distance, called MOEA/D_RD. Reference distance is the distance from each solution to the weight vector, as shown in Figure5. For each weight vector, we can calculate the distance of all solutions to it. For example, the distance of five solutions to weight vector λ1 is depicted in Figure 6. We can see that x1 is the solution with the shortest distance to λ1 among the solutions. The calculation of reference distance is described in the following.Given: the weight vectorλ, the line from original point to λ L, the solution Fx, the projection point from Fx to L is y; then, the distance d1 from original point to y is
(7)d1=FxTλλ,(8)Referencedistanced2=Fx−d1λ.Figure 5
Reference distance.Figure 6
Reference distance toλ1.MOEA/D_RD is described as follows.At each generationt, MOEA/D_RD maintains
(i)
N is the number of the subproblems considered in MOEA/D_RD,
(ii)
a population ofN points x1,x2,…,xN∈Ω; where xi is a vector and is the current solution to the ith subproblem; xi corresponds to the weight vector λi,
(iii)
FV1,…,FVN, where FVi is the fitness value of xi, that is, FVi=Fxi for each i=1,…,N,
(iv)
an external population (EP), which is used to store nondominated solutions found during the search,
(v)
a variableR, 0<R<N; N/R stands for the replace rate; the value of R is empirically set. The variable Count is used to record the number of solutions being replaced at each generation.The algorithm works as follows.Algorithm 1
Input
(i)Multiobjective optimization fitness function, that is, (6)
(ii)R and N
(iii)A uniform spread ofN weight vectors: λ1,λ2,…,λN
Output: EP.
Step 1. Initialization:
Step 1.1. SetEP=∅, Count = 0;
Step 1.2. Calculate the Euclidean distances between any two weight vectors and then work out theT closest weight vectors to each weight vectors. For each i=1,…,N, set Bi=i1,…,iT, where λi1,…,λiT are the T closest weight vectors to λi.
Step 1.3. Randomly generate an initial populationx1,x2,…,xN∈Ω. Compute FVi=Fxi.
Step 2. Update:
Fori=1,…,N, do the following.
Step 2.1. Randomly select two indexes,k and l from Bi, and then generate a new solution y from xk and xl by using general genetic operators.
Step 2.2. Check ify satisfies the constraints; if no, adjust y to meet the constraints and mark y to y∗.
Step 2.3. Update the neighboring solutions. For each indexj∈Bi, if gy∗∣λ≥gxj∣λ, then set xj=y∗ and FVj=Fy∗; Count=Count+1.
Step 2.4. Update the EP. Remove all the vectors dominated byFy∗ from EP. Add Fy∗ to EP if there is no vector in EP that dominates Fy∗.
Step 2.5. IfCount≤N/R, go to Step 2.6; else, go to Step 3.
Step 2.6. Find all the subproblems where solutions are not replaced and find the corresponding weight vectors to each subproblem.
Step 2.7. Adjust the values of fitness functions for the solutions in EP and normalize them to [0,1].
Step 2.8. For each weight vector found in Step 2.6, calculate the reference distances from the solutions in EP to the vector; find the solution with the shortest distance and use it to replace the current solution with respect to the corresponding subproblem.
Step 3. Stopping Criteria: If stopping criteria is satisfied, then stop and output EP. Otherwise, go to Step 2.Take Figure5 as an example. Assume N=5 and R=2; if the solutions corresponding to λ1 and λ4 are replaced, that is, Count = 2, since Count<N/R, the corresponding solutions of λ2,λ3,λ5 need to be replaced. Because x5 is dominated by x4, x5 is not in EP. x1, x2, x3, and x4 are in EP. x2 is used to replace the solution in terms of λ2 since x2 has the shortest distance to λ2. And x3 is used to replace the solution in terms of λ3 since x3 has the shortest distance to λ3. Although x5 has the shortest distance to λ5, but x5 is not in EP, thus x4 is used to replace the solution in terms of λ5.From the above example and algorithm description, we can see that MOEA/D_RD has the following features:(1)
The replacing strategy of MOEA/D_RD makes some unselected nondominate solutions in MOEA/D to generate the new population.
(2)
Although MOEA/D uses uniform weight vector, the subproblems of multiple weight vectors may fall in the same area and it may bring about the low diversity of population. MOEA/D_RD brings the idea of reference distance, and it can help the individuals that stuck in local area to search more widely.
(3)
MOEA/D_RD can bring new individuals when the algorithm is in stagnation; at the same time, the reference distance can guarantee that the new individuals are generated from the parents in neighborhood.In brief, compared to the original MOEA/D, the replacing strategy based on reference distance in MOEA/D_RD increases the diversity of population and can obtain well-distributed solutions. The improved algorithm performs well in high-dimensional multiobjective optimization.


## 4.1. MOEA/D Based on Weighted Sum Approach

In this paper, we improve the weighted sum approach in MOEA/D algorithm [14] for solving the software project selection optimization problem. The approach considers a convex combination of the different objectives. Let λ=λ1,…,λmT be a weight vector; m is the number of objectives; fix is the ith objective to be optimized; and λi≥0 for all i=1,…,m and ∑i=1mλi=1. Then the optimal solution to the following scalar optimization problem
(6)maximizegwsx∣λ=∑i=1mλifixsubjecttox∈Ωis a Pareto-optimal point to (1) as we can see that qix corresponds to one of the objectives fix in (6), where we use gwsx∣λ to emphasize that λ is a coefficient vector in this objective function, where x is the variables to be optimized. To generate a set of different Pareto-optimal vectors, one can use different weight vectors λ1,λ2,…,λN in the above scalar optimization problem and the optimized problem is divided into N subproblems. The greater N is, the wider the search space is. However, the weighted sum-based MOEA/D has several drawbacks and we illustrate them as follows.Given an example, as shown in Figure1, f1 and f2 are two objectives; Fxi is the objective function of solution xi; PF is the assumed optimal Pareto front; x1, x2, and x3 are three solutions corresponding to weight vectors λ1,λ2, and λ3. The ideal case is that the algorithm moves x1, x2, and x3 to meet the PF. MOEA/D randomly picks up two solutions from the neighborhood of x2 and generates a new solution using genetic operators. If the fitness value of the new solution is better than x2, then x2 is replaced by the new solution. If the new solution is fallen in the overlapping area of the search spaces of neighboring solutions x1 and x2, then both x1 and x2 are replaced by the new solution. The strategy is efficient at the earlier search stage of the algorithm, and it can make the search direction move fast to the PF. But at the late stage of the algorithm, as shown in Figure 2, there is no overlapping area among most of the search spaces of solutions. The neighboring solutions of x2 cannot generate a new effective solution. The search process would stagnate at the late stage of the algorithm.Figure 1
Solution generation process of MOEA/D.Figure 2
The late stage of MOEA/D.If the PF is a line, as shown in Figure3, for the weight vector λ2, all solutions on the PF line are the same optimal solutions with the same fitness values. Among the solutions between the weight vectors λ1 and λ2, the optimal solution is the intersection point of PF and f2. Similarly, among the solutions between the weight vectors λ2 and λ3, the optimal solution is the interaction point of PF and f1. Assume that a solution with respect to λ2 during iteration is x2, x2 would not be replaced by x∗ even if x∗ is closer to λ2 and is a better solution. It is because x2 and x∗ are equally optimal with the same fitness values on the PF line. The search process is in a standstill.Figure 3
Pareto front as a line.If the PF is a convex curve, as shown in Figure4, assume that x2 is the solution with respect to λ2 during iteration; when the algorithm finds another solution x∗, x2 will be replaced by x∗ since the fitness value of x∗ is better than x2. Similarly, the solutions with respect to λ1 and λ3 will be replaced by the solutions that are located close to the ends of PF. At the late search process of the algorithm, most of solutions are aggregated at the ends of PF and the algorithm suffers in stagnation.Figure 4
Pareto front as convex.From the above analysis, we can see that the traditional weighted sum approach of MOEA/D suffers poor search ability. In the next subsection, we propose an improved MOEA/D based on reference distance to enhance the search ability of the algorithm.


## 4.2. An Improved Algorithm MOEA/D_RD Based on Reference Distance

To alleviate the aforementioned problems of MOEA/D, we propose an improved version based on reference distance, called MOEA/D_RD. Reference distance is the distance from each solution to the weight vector, as shown in Figure5. For each weight vector, we can calculate the distance of all solutions to it. For example, the distance of five solutions to weight vector λ1 is depicted in Figure 6. We can see that x1 is the solution with the shortest distance to λ1 among the solutions. The calculation of reference distance is described in the following.Given: the weight vectorλ, the line from original point to λ L, the solution Fx, the projection point from Fx to L is y; then, the distance d1 from original point to y is
(7)d1=FxTλλ,(8)Referencedistanced2=Fx−d1λ.Figure 5
Reference distance.Figure 6
Reference distance toλ1.MOEA/D_RD is described as follows.At each generationt, MOEA/D_RD maintains
(i)
N is the number of the subproblems considered in MOEA/D_RD,
(ii)
a population ofN points x1,x2,…,xN∈Ω; where xi is a vector and is the current solution to the ith subproblem; xi corresponds to the weight vector λi,
(iii)
FV1,…,FVN, where FVi is the fitness value of xi, that is, FVi=Fxi for each i=1,…,N,
(iv)
an external population (EP), which is used to store nondominated solutions found during the search,
(v)
a variableR, 0<R<N; N/R stands for the replace rate; the value of R is empirically set. The variable Count is used to record the number of solutions being replaced at each generation.The algorithm works as follows.Algorithm 1
Input
(i)Multiobjective optimization fitness function, that is, (6)
(ii)R and N
(iii)A uniform spread ofN weight vectors: λ1,λ2,…,λN
Output: EP.
Step 1. Initialization:
Step 1.1. SetEP=∅, Count = 0;
Step 1.2. Calculate the Euclidean distances between any two weight vectors and then work out theT closest weight vectors to each weight vectors. For each i=1,…,N, set Bi=i1,…,iT, where λi1,…,λiT are the T closest weight vectors to λi.
Step 1.3. Randomly generate an initial populationx1,x2,…,xN∈Ω. Compute FVi=Fxi.
Step 2. Update:
Fori=1,…,N, do the following.
Step 2.1. Randomly select two indexes,k and l from Bi, and then generate a new solution y from xk and xl by using general genetic operators.
Step 2.2. Check ify satisfies the constraints; if no, adjust y to meet the constraints and mark y to y∗.
Step 2.3. Update the neighboring solutions. For each indexj∈Bi, if gy∗∣λ≥gxj∣λ, then set xj=y∗ and FVj=Fy∗; Count=Count+1.
Step 2.4. Update the EP. Remove all the vectors dominated byFy∗ from EP. Add Fy∗ to EP if there is no vector in EP that dominates Fy∗.
Step 2.5. IfCount≤N/R, go to Step 2.6; else, go to Step 3.
Step 2.6. Find all the subproblems where solutions are not replaced and find the corresponding weight vectors to each subproblem.
Step 2.7. Adjust the values of fitness functions for the solutions in EP and normalize them to [0,1].
Step 2.8. For each weight vector found in Step 2.6, calculate the reference distances from the solutions in EP to the vector; find the solution with the shortest distance and use it to replace the current solution with respect to the corresponding subproblem.
Step 3. Stopping Criteria: If stopping criteria is satisfied, then stop and output EP. Otherwise, go to Step 2.Take Figure5 as an example. Assume N=5 and R=2; if the solutions corresponding to λ1 and λ4 are replaced, that is, Count = 2, since Count<N/R, the corresponding solutions of λ2,λ3,λ5 need to be replaced. Because x5 is dominated by x4, x5 is not in EP. x1, x2, x3, and x4 are in EP. x2 is used to replace the solution in terms of λ2 since x2 has the shortest distance to λ2. And x3 is used to replace the solution in terms of λ3 since x3 has the shortest distance to λ3. Although x5 has the shortest distance to λ5, but x5 is not in EP, thus x4 is used to replace the solution in terms of λ5.From the above example and algorithm description, we can see that MOEA/D_RD has the following features:(1)
The replacing strategy of MOEA/D_RD makes some unselected nondominate solutions in MOEA/D to generate the new population.
(2)
Although MOEA/D uses uniform weight vector, the subproblems of multiple weight vectors may fall in the same area and it may bring about the low diversity of population. MOEA/D_RD brings the idea of reference distance, and it can help the individuals that stuck in local area to search more widely.
(3)
MOEA/D_RD can bring new individuals when the algorithm is in stagnation; at the same time, the reference distance can guarantee that the new individuals are generated from the parents in neighborhood.In brief, compared to the original MOEA/D, the replacing strategy based on reference distance in MOEA/D_RD increases the diversity of population and can obtain well-distributed solutions. The improved algorithm performs well in high-dimensional multiobjective optimization.


## 5. Experimental Evaluation

This section presents the experiments carried out to evaluate the performance of the proposed approach. First, the test data set based on the Constructive Cost Model (COCOMO II) is described. Three evaluating metrics are then introduced. Lastly, we compare MOEA/D_RD with MOEA/D, NSGA2, and NSGA3. All experiments were run on an Intel Core i5-2450M CPU@2.50 GHz, 4 GB memory PC with Win7 64-bit operating system.


### 5.1. COCOMO II Test Set

COCOMO II is a model to estimate the cost, effort, and schedule when planning a new software development activity. The test set is based on this model and consists of 50 software projects [5]. The number of lines of source code of these projects is between 1000 and 37000. The maximum duration of a project is 18 months, and the planning horizon is set to 3 years. The planning horizon is divided into 3 timeframes, one year (12 months) per timeframe. There are 1500 person-months in total for the planning horizon and 500 person-months per timeframe. Each project has an assigned risk value between 0.2 and 0.8. Potential revenue is set to the maximum of 150% and to the minimum of 85% of the initial costs. The total strategic alignment value is calculated by a weight sum of each strategy’s alignment value which is set randomly. A maximum number of 30% of all projects are selected to have synergy effects with exactly one project where there is 15% of the positive synergy and 15% of the negative synergy. A number of 10% of all projects are selected randomly to be mandatory, and 4 projects are manually selected to be mutually exclusive.


### 5.2. Evaluation Metrics

In order to verify the proposed algorithm and compare to other state-of-the-art algorithms, we use three performance indexes as the following:(i)
Set coverage (C-metric) [14]: Let A and B be the two approximations to the PF of a multiobjective optimization problem, CA,B is defined as the percentage of the solutions in B that are dominated by at least one solution in A, that is,
(9)CA,B=u∈B∣∃v∈A:vdominatesuB.CA,B=1 means that all solutions in B are dominated by some solutions in A, while CA,B=0 implies that no solution in B is dominated by a solution in A.
(ii)
IGD-metric [7]: Let A be a set of nondominated solutions obtained by the algorithm. Let P∗ be the true PF. Since we do not know the actual PF for the software portfolio optimization problem in this paper, we use the optimal solutions obtained by all the compared algorithms as the approximation of P∗. The average distance from P∗ to A is defined as
(10)IGDA,P∗=∑v∈P∗dv,AP∗,where dv,A is the minimum Euclidean distance between v and the points in A. If P∗ is large enough to represent the PF very well, IGDA,P∗ could measure both the diversity and convergence of A in a sense. To have a low value of IGDA,P∗, set A must be very close to the PF.
(iii)
GD-metric [7]:
(11)GDA,P∗=∑v∈Adv,P∗A,where P∗ and A have the same definitions as in IGD-metric. dv,P∗ is the minimum Euclidean distance between v and the points in P∗. The smaller value GD-metric is, the more stable the algorithm.To decide the value ofR in MOEA/D_RD suitably, we first analyze the impact of R to the performance. Figure 7 shows the different IGD-metric values with different R values in the objectives of q2 and q3 optimization task. For every R value, the algorithm is run 20 times and the reference PF consists of all the nondominated solutions of the 20 runs. Calculate the IGD-metric for every single R value. When R equals to 0, it means reference distance is not used in the algorithm. We can see that the IGD-metric is the best when R is 3. The algorithm performs similarly when R is between 3 and 8. Considering that the convergence is slow if R is too small and the stagnation in search process is serious if R is too large, we set R to 5 in the following experiments.Figure 7
The effect of differentR values.


### 5.3. Comparison between MOEA/D_RD and MOEA/D

As for the 4 objectives we mentioned in Section3, q1 and q3 are positively correlated; that is, high revenue can be expected only when resources are effectively used throughout the whole planning horizon and vice versa. For q2 and q4, usually the project with either the lowest risk or the highest strategic alignment value is selected to the portfolio. Thus, q1-q3 and q2-q4 are not studied in our 2-objective optimization experiments. The experiments are conducted on 2-objective optimization problems: q1-q2, q1-q4, q2-q3, and q3-q4; 3-objective optimization problems: q1-q2-q4, q1-q2-q3, q1-q3-q4, and q2-q3-q4; and 4-objective optimization problem: q1-q2-q3-q4. There are 150 weight vectors in 2-objective optimization experiments, 351 weight vectors in 3-objective optimization experiments, and 455 weight vectors in 4-objective optimization experiment. The number of neighborhood is 10. The mutation rate is 0.01. The number of generation is 500 for 2-objective optimization and 1000 for 3- and 4-objective optimization problems. We run 20 independent runs with each of the compared algorithms where each run produced a set of nondominated solutions. The final population of nondominated solutions is plotted in Figures 8 and 9. We can see that MOEA/D-RD obtains more nondominated solutions.Figure 8
Comparison of PF between MOEA/D_RD (red circle) and MOEA/D (green∗) for 2-objective optimization.Figure 9
Comparison of PF between MOEA/D_RD (red circle) and MOEA/D (green∗) for 3-objective optimization.Tables1–3 give the comparisons between MOEA/D-RD and MOEA/D in terms of C-metric, IGD-metric, and GD-metric. The better performance is marked in bold. From Tables 1 and 2, we can see that MOEA/D outperforms MOEA/D-RD in only one item of q1-q2-q4. MOEA/D_RD performs better in the other 8 optimization problems with smaller C-metric and IGD-metric.Table 1
Comparison ofC-metric of MOEA/D_RD and MOEA/D.
C-metric (MOEA/D_RD, MOEA/D)
C-metric (MOEA/D, MOEA/D_RD)
q1-q2
0.559
0.071
q1-q4
0.527
0.0628
q2-q3
0.768
0.021
q3-q4
0.75
0.018
q1-q2-q3
0.825
0.005
q1-q2-q4
0.265
0.321
q1-q4-q3
0.81
0.01
q2-q4-q3
0.632
0.063
q1-q2-q3-q4
0.43
0.176Table 2
Comparison of IGD-metric of MOEA/D_RD and MOEA/D.
IGD-metric (MOEA/D)
IGD-metric (MOEA/D_RD)
q1-q2
3669.74
313.09
q1-q4
4273.46
818.957
q2-q3
0.037
0.001
q3-q4
0.007
0.001
q1-q2-q3
1701.49
46.68
q1-q2-q4
212.82
544.87
q1-q4-q3
1732.64
31.49
q2-q4-q3
0.021
0.002
q1-q2-q3-q4
100.86
57.68Table 3
Comparison of GD-metric of MOEA/D_RD and MOEA/D.
GD-metric (MOEA/D)
GD-metric (MOEA/D_RD)
Mean
Deviation
Mean
Deviation
q1-q2
4361.43
5017.01
2751.47
3548.01
q1-q4
4364.78
5496.39
2435.11
3272.23
q2-q3
0.062
0.063
0.043
0.058
q3-q4
0.013
0.011
0.011
0.011
q1-q2-q3
1741.47
2734.43
662.37
1422.7
q1-q2-q4
338.23
503.61
310.92
459.31
q1-q4-q3
1591.24
3665.13
559.19
1084.4
q2-q4-q3
0.022
0.02
0.018
0.016
q1-q2-q3-q4
116.19
215.604
142.091
213.107Figures10 and 11 illustrate the improvement of the diversity of population and the distribution uniformity of solutions in MOEA/D_RD. Figure 10 presents the final population in one random run for q1-q4 problem. The number of population is 150, and there are only 9 different solutions at the last generation. We can see that the solutions in the neighborhood are almost the same and there is no new solution generated through genetic operators. The algorithm suffers in stagnation. Figure 11 gives the final population after 20 runs for q1-q4 problem. We can see that the nondominated solutions obtained by MOEA/D_RD are distributed more uniformly than the solutions by MOEA/D.Figure 10
The final population of MOEA/D.Figure 11
The final population of MOEA/D_RD and MOEA/D.


### 5.4. Comparison between MOEA/D_RD and NSGA2

NSGA2 has performed effectively in various optimization problems since it is invented. We also employ NSGA2 to solve our software project portfolio optimization model. The number of population of NSGA2 is 160, 360, and 500, respectively, for 2-objective, 3-objective, and 4-objective optimization problems. The mutation rate is 0.01. The number of generation is 500 for 2-objective optimization problem and 1000 for 3- and 4-objective optimization problems. The final population of nondominated solutions is plotted in Figures12 and 13 after 20 independent runs. We can see that NSGA2 performs better and obtains more nondominated solutions in 2- and 3-objective optimization problems. Tables 4–6 give the comparisons between MOEA/D-RD and NSGA2 in terms of C-metric, IGD-metric, and GD-metric. The better performance is marked in bold. MOEA/D_RD outperforms NSGA2 for 4-objective optimization problem.Figure 12
Comparison of PF between MOEA/D_RD (red circle) and NSGA2 (green∗) for 2-objective optimization.Figure 13
Comparison of PF between MOEA/D_RD (red circle) and NSGA2 (green∗) for 3-objective optimization.Table 4
Comparison ofC-metric of MOEA/D_RD and NSGA2.
C-metric (MOEA/D_D, NSGA2)
C-metric (NSGA2, MOEA/D_RD)
q1-q2
0.048
0.44
q1-q4
0.036
0.188
q2-q3
0
0.78
q3-q4
0
0.702
q1-q2-q3
0.027
0.531
q1-q2-q4
0.183
0.15
q1-q4-q3
0.024
0.385
q2-q4-q3
0.052
0.524
q1-q2-q3-q4
0.24
0.14Table 5
Comparison of IGD-metric of MOEA/D_RD and NSGA2.
IGD-metric (NSGA2)
IGD-metric (MOEA/D_RD)
q1-q2
313.793
2024.71
q1-q4
427.488
619.194
q2-q3
0
0.0127
q3-q4
0
0.006
q1-q2-q3
189.272
324.263
q1-q2-q4
40949.7
207.512
q1-q4-q3
138.696
326.496
q2-q4-q3
0.008
0.026
q1-q2-q3-q4
6633.18
67.3109Table 6
Comparison of GD-metric of MOEA/D_RD and NSGA2.
GD-metric (NSGA2)
GD-metric (MOEA/D_RD)
Mean
Deviation
Mean
Deviation
q1-q2
957.144
2152.5
2751.47
3548.01
q1-q4
1223.3
2475.81
2435.11
3272.23
q2-q3
0.003
0.011
0.043
0.058
q3-q4
0.002
0.003
0.011
0.011
q1-q2-q3
591.726
2347.86
662.374
1422.7
q1-q2-q4
228.112
437.182
310.917
459.31
q1-q4-q3
459.115
1074.91
559.196
1084.4
q2-q4-q3
0.01
0.011
0.018
0.016
q1-q2-q3-q4
184.506
324.817
142.091
213.107


### 5.5. Comparison between MOEA/D_RD and NSGA3

NSGA3 is the newest version of NSGA2 designed for many objective optimization problems. We use NSGA3 to solve the software project portfolio optimization problem especially the 3- and 4-objective optimization problems. The number of population for NSGA3 is set to 152, division parameterρ 150, reference points 151 for 2-objective optimization experiments. The number of population is set to 352, division parameter ρ 25, reference points 351 for 3-objective optimization experiments. The number of population is 456, division parameter ρ 12, reference points 455 for 4-objective optimization experiments. The mutation rate is 0.01. The number of generation is 500 for biobjective optimization and 1000 for 3- and 4-objective optimization problems. The final population of nondominated solutions is plotted in Figures 14 and 15 after 20 independent runs. For 2-objective optimization problem, MOEA/D_RD can obtain more nondominated solutions and the distribution of solutions is more uniformly than NSGA3. For 3-objective optimization problem, the solutions obtained by NSGA3 are distributed in smaller area than MOEA/D_RD.Figure 14
Comparison of PF between MOEA/D_RD (red circle) and NSGA3 (green∗) for 2-objective optimization.Figure 15
Comparison of PF between MOEA/D_RD (red circle) and NSGA3 (green∗) for 3-objective optimization.Tables7–9 give the comparisons between MOEA/D_RD and NSGA3 in terms of C-metric, IGD-metric, and GD-metric. The better performance is marked in bold. From Tables 7 and 8, we can see that NSGA3 outperforms MOEA/D_RD in terms of C-metric while MOEA/D_RD outperforms NSGA3 in terms of IGD-metric. It means that NSGA3 can get better PF, but the distribution of solutions is worse than MOEA/D_RD. Table 9 indicates that NSGA3 can have better mean values but worse deviation values than MOEA/D_RD and we can have the same conclusion from Tables 7 and 8.Table 7
Comparison ofC-metric of MOEA/D_RD and NSGA3.
C-metric (MOEA/D_RD, NSGA3)
C-metric (NSGA3, MOEA/D_RD)
q1-q2
0.02
0.422
q1-q4
0.005
0.285
q2-q3
0.024
0.773
q3-q4
0.007
0.667
q1-q2-q3
0.144
0.065
q1-q2-q4
0.194
0.142
q1-q4-q3
0.156
0.055
q2-q4-q3
0.009
0.498
q1-q2-q3-q4
0.083
0.107Table 8
Comparison of IGD-metric of MOEA/D_RD and NSGA3.
IGD-metric (NSGA3)
IGD-metric (MOEA/D_RD)
q1-q2
8664.81
2028.22
q1-q4
2556.45
1077.42
q2-q3
0.027
0.013
q3-q4
0.001
0.006
q1-q2-q3
156706
43.468
q1-q2-q4
4337.33
179.436
q1-q4-q3
203970
54.698
q2-q4-q3
0.013
0.019
q1-q2-q3-q4
125345
81.746Table 9
Comparison of GD-metric of MOEA/D_RD and NSGA3.
GD-metric (NSGA3)
GD-metric (MOEA/D_RD)
Mean
Deviation
Mean
Deviation
q1-q2
517.813
2271.78
2751.47
3548.01
q1-q4
746.94
1970.08
2435.11
3272.23
q2-q3
0.002
0.014
0.043
0.058
q3-q4
0.001
0.002
0.011
0.011
q1-q2-q3
258.735
1916.26
662.374
1422.7
q1-q2-q4
249.137
594.39
310.917
459.31
q1-q4-q3
463.686
4324.19
559.196
1084.4
q2-q4-q3
0.006
0.016
0.018
0.016
q1-q2-q3-q4
67.996
393.873
142.091
213.107


### 5.6. More Experiments

We also conducted some experiments to compare the four studied algorithms. The results using the PF obtained by the four algorithms and the correspondingly computed IGD-metric are shown in Table10. NSGA2 performs the best in 6 2- and 3-objective optimization problems with the smallest IGD-metric values. But for the 4-objective optimization problem, MOEA/D_RD outperforms the other algorithms.Table 10
IGD-metric of the compared four algorithms.
MOEA/D_RD
MOEA/D
NSGA2
NSGA3
q1-q2
2327.95
4616.15
844.444
9693.75
q1-q4
1771.3
4314.13
1924.44
3258.74
q2-q3
0.013
0.056
0
0.027
q3-q4
0.007
0.011
0.001
0.001
q1-q2-q3
334.079
1908.11
222.284
120820
q1-q2-q4
615.151
341.423
39321.5
5671.34
q1-q4-q3
344
1893.54
138.744
148423
q2-q4-q3
0.026
0.04
0.012
0.019
q1-q2-q3-q4
136.089
146.714
5616.01
113234Table11 presents the average running time of the four algorithms in 20 runs for the 9 optimization problems. We can see that MOEA/D consumes the least time and MOEA/D_RD costs the similar time compared with MOEA/D. NSGA2 needs several or more than ten times than MOEA/D_RD, and NSGA3 consumes the most time. To sum up, MOEA/D needs the least time but it is easy to suffer in stagnation and cannot obtain good nondominated solutions. NSGA3 is not likely suitable to solve the software project portfolio optimization problem. It needs the most time, and the distribution of solutions is not good. NSGA2 performs well in 2- and 3-objective optimization problems, but it needs much more running time than MOEA/D_RD. Generally speaking, MOEA/D_RD has the excellent overall performance. It can get the uniformly distributed nondominated solutions and performs the best for the 4-objective optimization problem. Although MOEA/D_RD is a little worse than NSGA2 in 2- and 3-objective optimization problems, but it consumes much less running time. In conclusion, we can say that MOEA/D_RD is an effective approach to the software project portfolio optimization problem.Table 11
Average running time of the four compared algorithms.
MOEA/D_RD
MOEA/D
NSGA2
NSGA3
q1-q2
1.7
1.56
19.26
52.74
q1-q4
1.75
1.68
23.05
50.14
q2-q3
0.97
1.11
18.21
49.05
q3-q4
1.54
2.11
21.68
50.21
q1-q2-q3
14.62
14.75
102.95
516.95
q1-q2-q4
10.54
10.45
47.16
445.15
q1-q4-q3
19.61
19.01
136.11
493.5
q2-q4-q3
10.94
10.76
80.32
460.74
q1-q2-q3-q4
34.28
33.25
106.57
934.84


### 5.7. Conclusion and Future Work

Based on Kremmel’s model, a compact model with 4-objective optimization model for software project portfolio problem is proposed in this paper. The model is adaptive for software companies who can revise the objectives and constraints according to their own requirements. To solve the proposed model, an improved MOEA/D algorithm called MOEA/D_RD based on reference distance is proposed accordingly. The algorithm uses reference distance to select some solutions to generate new solutions. Compared with MOEA/D, NSGA2, and NSGA3, MOEA/D_RD performs well in terms of the quality of solutions and running time, especially for 4-objective optimization problem. Future work could cover several topics. A great number of projects for the test set could be conducted. It also would be important to test the approach on a test set with real-world data which may include some incomplete and uncertain data.


## 5.1. COCOMO II Test Set

COCOMO II is a model to estimate the cost, effort, and schedule when planning a new software development activity. The test set is based on this model and consists of 50 software projects [5]. The number of lines of source code of these projects is between 1000 and 37000. The maximum duration of a project is 18 months, and the planning horizon is set to 3 years. The planning horizon is divided into 3 timeframes, one year (12 months) per timeframe. There are 1500 person-months in total for the planning horizon and 500 person-months per timeframe. Each project has an assigned risk value between 0.2 and 0.8. Potential revenue is set to the maximum of 150% and to the minimum of 85% of the initial costs. The total strategic alignment value is calculated by a weight sum of each strategy’s alignment value which is set randomly. A maximum number of 30% of all projects are selected to have synergy effects with exactly one project where there is 15% of the positive synergy and 15% of the negative synergy. A number of 10% of all projects are selected randomly to be mandatory, and 4 projects are manually selected to be mutually exclusive.


## 5.2. Evaluation Metrics

In order to verify the proposed algorithm and compare to other state-of-the-art algorithms, we use three performance indexes as the following:(i)
Set coverage (C-metric) [14]: Let A and B be the two approximations to the PF of a multiobjective optimization problem, CA,B is defined as the percentage of the solutions in B that are dominated by at least one solution in A, that is,
(9)CA,B=u∈B∣∃v∈A:vdominatesuB.CA,B=1 means that all solutions in B are dominated by some solutions in A, while CA,B=0 implies that no solution in B is dominated by a solution in A.
(ii)
IGD-metric [7]: Let A be a set of nondominated solutions obtained by the algorithm. Let P∗ be the true PF. Since we do not know the actual PF for the software portfolio optimization problem in this paper, we use the optimal solutions obtained by all the compared algorithms as the approximation of P∗. The average distance from P∗ to A is defined as
(10)IGDA,P∗=∑v∈P∗dv,AP∗,where dv,A is the minimum Euclidean distance between v and the points in A. If P∗ is large enough to represent the PF very well, IGDA,P∗ could measure both the diversity and convergence of A in a sense. To have a low value of IGDA,P∗, set A must be very close to the PF.
(iii)
GD-metric [7]:
(11)GDA,P∗=∑v∈Adv,P∗A,where P∗ and A have the same definitions as in IGD-metric. dv,P∗ is the minimum Euclidean distance between v and the points in P∗. The smaller value GD-metric is, the more stable the algorithm.To decide the value ofR in MOEA/D_RD suitably, we first analyze the impact of R to the performance. Figure 7 shows the different IGD-metric values with different R values in the objectives of q2 and q3 optimization task. For every R value, the algorithm is run 20 times and the reference PF consists of all the nondominated solutions of the 20 runs. Calculate the IGD-metric for every single R value. When R equals to 0, it means reference distance is not used in the algorithm. We can see that the IGD-metric is the best when R is 3. The algorithm performs similarly when R is between 3 and 8. Considering that the convergence is slow if R is too small and the stagnation in search process is serious if R is too large, we set R to 5 in the following experiments.Figure 7
The effect of differentR values.


## 5.3. Comparison between MOEA/D_RD and MOEA/D

As for the 4 objectives we mentioned in Section3, q1 and q3 are positively correlated; that is, high revenue can be expected only when resources are effectively used throughout the whole planning horizon and vice versa. For q2 and q4, usually the project with either the lowest risk or the highest strategic alignment value is selected to the portfolio. Thus, q1-q3 and q2-q4 are not studied in our 2-objective optimization experiments. The experiments are conducted on 2-objective optimization problems: q1-q2, q1-q4, q2-q3, and q3-q4; 3-objective optimization problems: q1-q2-q4, q1-q2-q3, q1-q3-q4, and q2-q3-q4; and 4-objective optimization problem: q1-q2-q3-q4. There are 150 weight vectors in 2-objective optimization experiments, 351 weight vectors in 3-objective optimization experiments, and 455 weight vectors in 4-objective optimization experiment. The number of neighborhood is 10. The mutation rate is 0.01. The number of generation is 500 for 2-objective optimization and 1000 for 3- and 4-objective optimization problems. We run 20 independent runs with each of the compared algorithms where each run produced a set of nondominated solutions. The final population of nondominated solutions is plotted in Figures 8 and 9. We can see that MOEA/D-RD obtains more nondominated solutions.Figure 8
Comparison of PF between MOEA/D_RD (red circle) and MOEA/D (green∗) for 2-objective optimization.Figure 9
Comparison of PF between MOEA/D_RD (red circle) and MOEA/D (green∗) for 3-objective optimization.Tables1–3 give the comparisons between MOEA/D-RD and MOEA/D in terms of C-metric, IGD-metric, and GD-metric. The better performance is marked in bold. From Tables 1 and 2, we can see that MOEA/D outperforms MOEA/D-RD in only one item of q1-q2-q4. MOEA/D_RD performs better in the other 8 optimization problems with smaller C-metric and IGD-metric.Table 1
Comparison ofC-metric of MOEA/D_RD and MOEA/D.
C-metric (MOEA/D_RD, MOEA/D)
C-metric (MOEA/D, MOEA/D_RD)
q1-q2
0.559
0.071
q1-q4
0.527
0.0628
q2-q3
0.768
0.021
q3-q4
0.75
0.018
q1-q2-q3
0.825
0.005
q1-q2-q4
0.265
0.321
q1-q4-q3
0.81
0.01
q2-q4-q3
0.632
0.063
q1-q2-q3-q4
0.43
0.176Table 2
Comparison of IGD-metric of MOEA/D_RD and MOEA/D.
IGD-metric (MOEA/D)
IGD-metric (MOEA/D_RD)
q1-q2
3669.74
313.09
q1-q4
4273.46
818.957
q2-q3
0.037
0.001
q3-q4
0.007
0.001
q1-q2-q3
1701.49
46.68
q1-q2-q4
212.82
544.87
q1-q4-q3
1732.64
31.49
q2-q4-q3
0.021
0.002
q1-q2-q3-q4
100.86
57.68Table 3
Comparison of GD-metric of MOEA/D_RD and MOEA/D.
GD-metric (MOEA/D)
GD-metric (MOEA/D_RD)
Mean
Deviation
Mean
Deviation
q1-q2
4361.43
5017.01
2751.47
3548.01
q1-q4
4364.78
5496.39
2435.11
3272.23
q2-q3
0.062
0.063
0.043
0.058
q3-q4
0.013
0.011
0.011
0.011
q1-q2-q3
1741.47
2734.43
662.37
1422.7
q1-q2-q4
338.23
503.61
310.92
459.31
q1-q4-q3
1591.24
3665.13
559.19
1084.4
q2-q4-q3
0.022
0.02
0.018
0.016
q1-q2-q3-q4
116.19
215.604
142.091
213.107Figures10 and 11 illustrate the improvement of the diversity of population and the distribution uniformity of solutions in MOEA/D_RD. Figure 10 presents the final population in one random run for q1-q4 problem. The number of population is 150, and there are only 9 different solutions at the last generation. We can see that the solutions in the neighborhood are almost the same and there is no new solution generated through genetic operators. The algorithm suffers in stagnation. Figure 11 gives the final population after 20 runs for q1-q4 problem. We can see that the nondominated solutions obtained by MOEA/D_RD are distributed more uniformly than the solutions by MOEA/D.Figure 10
The final population of MOEA/D.Figure 11
The final population of MOEA/D_RD and MOEA/D.


## 5.4. Comparison between MOEA/D_RD and NSGA2

NSGA2 has performed effectively in various optimization problems since it is invented. We also employ NSGA2 to solve our software project portfolio optimization model. The number of population of NSGA2 is 160, 360, and 500, respectively, for 2-objective, 3-objective, and 4-objective optimization problems. The mutation rate is 0.01. The number of generation is 500 for 2-objective optimization problem and 1000 for 3- and 4-objective optimization problems. The final population of nondominated solutions is plotted in Figures12 and 13 after 20 independent runs. We can see that NSGA2 performs better and obtains more nondominated solutions in 2- and 3-objective optimization problems. Tables 4–6 give the comparisons between MOEA/D-RD and NSGA2 in terms of C-metric, IGD-metric, and GD-metric. The better performance is marked in bold. MOEA/D_RD outperforms NSGA2 for 4-objective optimization problem.Figure 12
Comparison of PF between MOEA/D_RD (red circle) and NSGA2 (green∗) for 2-objective optimization.Figure 13
Comparison of PF between MOEA/D_RD (red circle) and NSGA2 (green∗) for 3-objective optimization.Table 4
Comparison ofC-metric of MOEA/D_RD and NSGA2.
C-metric (MOEA/D_D, NSGA2)
C-metric (NSGA2, MOEA/D_RD)
q1-q2
0.048
0.44
q1-q4
0.036
0.188
q2-q3
0
0.78
q3-q4
0
0.702
q1-q2-q3
0.027
0.531
q1-q2-q4
0.183
0.15
q1-q4-q3
0.024
0.385
q2-q4-q3
0.052
0.524
q1-q2-q3-q4
0.24
0.14Table 5
Comparison of IGD-metric of MOEA/D_RD and NSGA2.
IGD-metric (NSGA2)
IGD-metric (MOEA/D_RD)
q1-q2
313.793
2024.71
q1-q4
427.488
619.194
q2-q3
0
0.0127
q3-q4
0
0.006
q1-q2-q3
189.272
324.263
q1-q2-q4
40949.7
207.512
q1-q4-q3
138.696
326.496
q2-q4-q3
0.008
0.026
q1-q2-q3-q4
6633.18
67.3109Table 6
Comparison of GD-metric of MOEA/D_RD and NSGA2.
GD-metric (NSGA2)
GD-metric (MOEA/D_RD)
Mean
Deviation
Mean
Deviation
q1-q2
957.144
2152.5
2751.47
3548.01
q1-q4
1223.3
2475.81
2435.11
3272.23
q2-q3
0.003
0.011
0.043
0.058
q3-q4
0.002
0.003
0.011
0.011
q1-q2-q3
591.726
2347.86
662.374
1422.7
q1-q2-q4
228.112
437.182
310.917
459.31
q1-q4-q3
459.115
1074.91
559.196
1084.4
q2-q4-q3
0.01
0.011
0.018
0.016
q1-q2-q3-q4
184.506
324.817
142.091
213.107


## 5.5. Comparison between MOEA/D_RD and NSGA3

NSGA3 is the newest version of NSGA2 designed for many objective optimization problems. We use NSGA3 to solve the software project portfolio optimization problem especially the 3- and 4-objective optimization problems. The number of population for NSGA3 is set to 152, division parameterρ 150, reference points 151 for 2-objective optimization experiments. The number of population is set to 352, division parameter ρ 25, reference points 351 for 3-objective optimization experiments. The number of population is 456, division parameter ρ 12, reference points 455 for 4-objective optimization experiments. The mutation rate is 0.01. The number of generation is 500 for biobjective optimization and 1000 for 3- and 4-objective optimization problems. The final population of nondominated solutions is plotted in Figures 14 and 15 after 20 independent runs. For 2-objective optimization problem, MOEA/D_RD can obtain more nondominated solutions and the distribution of solutions is more uniformly than NSGA3. For 3-objective optimization problem, the solutions obtained by NSGA3 are distributed in smaller area than MOEA/D_RD.Figure 14
Comparison of PF between MOEA/D_RD (red circle) and NSGA3 (green∗) for 2-objective optimization.Figure 15
Comparison of PF between MOEA/D_RD (red circle) and NSGA3 (green∗) for 3-objective optimization.Tables7–9 give the comparisons between MOEA/D_RD and NSGA3 in terms of C-metric, IGD-metric, and GD-metric. The better performance is marked in bold. From Tables 7 and 8, we can see that NSGA3 outperforms MOEA/D_RD in terms of C-metric while MOEA/D_RD outperforms NSGA3 in terms of IGD-metric. It means that NSGA3 can get better PF, but the distribution of solutions is worse than MOEA/D_RD. Table 9 indicates that NSGA3 can have better mean values but worse deviation values than MOEA/D_RD and we can have the same conclusion from Tables 7 and 8.Table 7
Comparison ofC-metric of MOEA/D_RD and NSGA3.
C-metric (MOEA/D_RD, NSGA3)
C-metric (NSGA3, MOEA/D_RD)
q1-q2
0.02
0.422
q1-q4
0.005
0.285
q2-q3
0.024
0.773
q3-q4
0.007
0.667
q1-q2-q3
0.144
0.065
q1-q2-q4
0.194
0.142
q1-q4-q3
0.156
0.055
q2-q4-q3
0.009
0.498
q1-q2-q3-q4
0.083
0.107Table 8
Comparison of IGD-metric of MOEA/D_RD and NSGA3.
IGD-metric (NSGA3)
IGD-metric (MOEA/D_RD)
q1-q2
8664.81
2028.22
q1-q4
2556.45
1077.42
q2-q3
0.027
0.013
q3-q4
0.001
0.006
q1-q2-q3
156706
43.468
q1-q2-q4
4337.33
179.436
q1-q4-q3
203970
54.698
q2-q4-q3
0.013
0.019
q1-q2-q3-q4
125345
81.746Table 9
Comparison of GD-metric of MOEA/D_RD and NSGA3.
GD-metric (NSGA3)
GD-metric (MOEA/D_RD)
Mean
Deviation
Mean
Deviation
q1-q2
517.813
2271.78
2751.47
3548.01
q1-q4
746.94
1970.08
2435.11
3272.23
q2-q3
0.002
0.014
0.043
0.058
q3-q4
0.001
0.002
0.011
0.011
q1-q2-q3
258.735
1916.26
662.374
1422.7
q1-q2-q4
249.137
594.39
310.917
459.31
q1-q4-q3
463.686
4324.19
559.196
1084.4
q2-q4-q3
0.006
0.016
0.018
0.016
q1-q2-q3-q4
67.996
393.873
142.091
213.107


## 5.6. More Experiments

We also conducted some experiments to compare the four studied algorithms. The results using the PF obtained by the four algorithms and the correspondingly computed IGD-metric are shown in Table10. NSGA2 performs the best in 6 2- and 3-objective optimization problems with the smallest IGD-metric values. But for the 4-objective optimization problem, MOEA/D_RD outperforms the other algorithms.Table 10
IGD-metric of the compared four algorithms.
MOEA/D_RD
MOEA/D
NSGA2
NSGA3
q1-q2
2327.95
4616.15
844.444
9693.75
q1-q4
1771.3
4314.13
1924.44
3258.74
q2-q3
0.013
0.056
0
0.027
q3-q4
0.007
0.011
0.001
0.001
q1-q2-q3
334.079
1908.11
222.284
120820
q1-q2-q4
615.151
341.423
39321.5
5671.34
q1-q4-q3
344
1893.54
138.744
148423
q2-q4-q3
0.026
0.04
0.012
0.019
q1-q2-q3-q4
136.089
146.714
5616.01
113234Table11 presents the average running time of the four algorithms in 20 runs for the 9 optimization problems. We can see that MOEA/D consumes the least time and MOEA/D_RD costs the similar time compared with MOEA/D. NSGA2 needs several or more than ten times than MOEA/D_RD, and NSGA3 consumes the most time. To sum up, MOEA/D needs the least time but it is easy to suffer in stagnation and cannot obtain good nondominated solutions. NSGA3 is not likely suitable to solve the software project portfolio optimization problem. It needs the most time, and the distribution of solutions is not good. NSGA2 performs well in 2- and 3-objective optimization problems, but it needs much more running time than MOEA/D_RD. Generally speaking, MOEA/D_RD has the excellent overall performance. It can get the uniformly distributed nondominated solutions and performs the best for the 4-objective optimization problem. Although MOEA/D_RD is a little worse than NSGA2 in 2- and 3-objective optimization problems, but it consumes much less running time. In conclusion, we can say that MOEA/D_RD is an effective approach to the software project portfolio optimization problem.Table 11
Average running time of the four compared algorithms.
MOEA/D_RD
MOEA/D
NSGA2
NSGA3
q1-q2
1.7
1.56
19.26
52.74
q1-q4
1.75
1.68
23.05
50.14
q2-q3
0.97
1.11
18.21
49.05
q3-q4
1.54
2.11
21.68
50.21
q1-q2-q3
14.62
14.75
102.95
516.95
q1-q2-q4
10.54
10.45
47.16
445.15
q1-q4-q3
19.61
19.01
136.11
493.5
q2-q4-q3
10.94
10.76
80.32
460.74
q1-q2-q3-q4
34.28
33.25
106.57
934.84


## 5.7. Conclusion and Future Work

Based on Kremmel’s model, a compact model with 4-objective optimization model for software project portfolio problem is proposed in this paper. The model is adaptive for software companies who can revise the objectives and constraints according to their own requirements. To solve the proposed model, an improved MOEA/D algorithm called MOEA/D_RD based on reference distance is proposed accordingly. The algorithm uses reference distance to select some solutions to generate new solutions. Compared with MOEA/D, NSGA2, and NSGA3, MOEA/D_RD performs well in terms of the quality of solutions and running time, especially for 4-objective optimization problem. Future work could cover several topics. A great number of projects for the test set could be conducted. It also would be important to test the approach on a test set with real-world data which may include some incomplete and uncertain data.



---

*Source: 3051854-2018-05-30.xml*