# Multiobjective Personalized Recommendation Algorithm Using Extreme Point Guided Evolutionary Computation

Authors: Qiuzhen Lin; Xiaozhou Wang; Bishan Hu; Lijia Ma; Fei Chen; Jianqiang Li; Carlos A. Coello Coello
Journal: Complexity
 (2018)

---

## Abstract

Recommender systems suggest items to users based on their potential interests, and they are important to alleviate the search and selection pressures induced by the increasing item information. Classical recommender systems mainly focus on the accuracy of recommendation. However, with the increase of the diversified demands of users, multiple metrics which may conflict with each other have to be considered in modern recommender systems, especially for the personalized recommender system. In this paper, we design a personalized recommendation system considering the three conflicting objectives, i.e., the accuracy, diversity, and novelty. Then, to let the system provide more comprehensive recommended items, we present a multiobjective personalized recommendation algorithm using extreme point guided evolutionary computation (called MOEA-EPG). The proposed MOEA-EPG is guided by three extreme points and its crossover operator is designed for better satisfying the demands of users. The experimental results validate the effectiveness of MOEA-EPG when compared to some state-of-the-art recommendation algorithms in terms of accuracy, diversity, and novelty on recommendation.


---

## Body

## 1. Introduction

With the rapid development of Internet and Web 2.0, consumers are facing a large amount of advertising and shopping information. To alleviate the search and selection burden for consumers, recommender systems (RSs) [1, 2] aim to suggest the suitable items by deducing the interesting information revealed from commodity. Nowadays, RSs have been successfully used in many applications; e.g., e-commerce websites recommend commodities [3, 4], social websites push some potential friends [5, 6] and link inferences [7], and e-learning educational institutions assist students in choosing courses and learning activities [8].In recent years, many RSs have been proposed [9–12], including the content-based RSs, the collaborative filtering based RSs, the knowledge-based RSs, and the hybrid RSs. The content-based RSs suggest similar items by extracting the content’s features from the profiles of items and users; the collaborative filtering based RSs exploit the community data (e.g., feedback rating, tags, or clicks from other users) to make recommendation, while the knowledge-based RSs use knowledge bases and knowledge models (e.g., ontologies) for recommendation. The hybrid RSs are the combination of the above approaches. A comprehensive survey of the state-of-the-art RSs can be found in [13, 14].In general, most traditional RSs [15–19] mainly focus on the accuracy of recommendations. However, with the increase of diversified demands of users, multiple metrics are often considered in personalized RSs, such as diversity and novelty that may conflict with each other. As pointed out by the studies in [20, 21], it is easy to guarantee the accuracy for recommendation, but it is difficult to maintain the diversity and novelty for recommendation. Generally, the increase of diversity or novelty in RSs will decrease their accuracy. Therefore, personalized RSs are often required to consider accuracy, diversity, and novelty simultaneously when making recommendation.Some research studies have been proposed to balance the accuracy and diversity of recommendations [18, 22, 23]. In [22], the balancing problem between the accuracy and diversity was modeled as a quadratic programming problem using a control parameter, which determines the importance of diversity in the recommendation lists. Then, several optimization strategies were accordingly designed to optimize the target model [22]. Similarly, in [23], a hybrid recommendation algorithm was proposed by combining heat-spreading (HeatS) algorithm and probabilistic spreading (ProbS) algorithm to improve the diversity and accuracy of recommendations. Moreover, in [18], some item ranking techniques were presented for giving diverse recommendations with comparable levels of accuracy. However, these algorithms [18, 22, 23] are limited to giving recommendations with both high accuracy and good diversity, ignoring novelty.Multiobjective optimization problems (MOPs) try to simultaneously optimize a set of conflicting objectives, which can be found in various research fields, such as engineering design [25] and route planning [26]. When solving MOPs, a number of nondominated solutions are returned, each of which is a tradeoff among different objectives [27]. Based on the studies in [28, 29], there is a tradeoff among multiple conflicting objectives (i.e., accuracy, diversity, and novelty) when modeling the MOPs for RSs. Recently, multiobjective evolutionary algorithms (MOEAs) have been proposed to solve the modeled MOPs for RSs. For instance, in [30], the personalized recommendation was first modeled as an MOP with two objectives (accuracy and diversity), and then an MOEA with the ProbS technique was proposed. Following this work, two novel MOEAs [31, 32] were designed based on the frameworks of MOEA/D [32] and NSGA-II [24] for recommendations with long tail items. These works [30–32] have based their performances on balancing the accuracy and diversity of recommendations. However, these MOEAs are also limited to considering the two conflicting objectives (accuracy and diversity) and do not consider the algorithm-specific knowledge in their designs.In this paper, a multiobjective personalized recommendation algorithm, called MOEA-EPG, with extreme point guided evolutionary computation is proposed. In MOEA-EPG, the accuracy, diversity, and novelty of recommendations are chosen as the three conflicting objectives, and the aim of our algorithm is to optimize the modeled MOP for personalized recommendation. The prior knowledge in RSs is extracted from the MOP by finding the extreme value of each objective, which is then incorporated into MOEA-EPG. As revealed by our experiments, this knowledge can effectively guide the population’s evolution, so as to improve the search efficiency. Moreover, the crossover operator is further designed for better satisfying the demands of users. To conclude, the main contributions of this paper are summarized as follows.(1)
The recommendation problem is modeled as an MOP with three conflicting objectives: accuracy, diversity, and novelty. The first objective measures the accuracy of recommendations determining whether the predicted ratings are similar to the true ones of users, and the second one optimizes the diversity of recommendations by calculating the recommendation coverage, while the last one reflects the capability of RSs to recommend unknown items to users.(2)
An extreme point guided method is proposed based on the prior knowledge of RSs, which is used to enhance the performance of personalized recommendation. For each objective, we choose the solution with the maximal value from the available items as the extreme point. Then, the chosen extreme points are embedded into the initialization of population to guide the evolutionary search toward the Pareto-optimal front.(3)
At the crossover process, the similarity between users’ interests is first evaluated, and then the users with a higher similarity will be selected for crossover with a larger probability. This process will help to generate offspring solutions with a good quality.(4)
The experiments on two classical data sets (Movielens and Netflix) show the superiority of our MOEA-EPG over the current MOEAs [30, 33] in terms of accuracy, diversity, and novelty.The rest of this paper is organized as follows. Section2 introduces the related background, such as the definition of RSs, MOPs, and classical recommendation algorithms. Section 3 presents the proposed MOEA-EPG algorithm, including the modeled MOP for RSs, individual representation, and the extreme point guided MOEA. Section 4 provides the experimental comparisons of MOEA-EPG with other competitive recommendation algorithms. At last, conclusions and future work are given in Section 5.


## 2. Related Background

### 2.1. Definition of RSs

RSs aim to predict potential likes and interests of users, according to their historical data about the users’ evaluations of items. Items in RSs may represent any consumed content, like books, movies, news, and music. LetU be a numberM of users, and letI be a numberN of items. Based on the historical data, a rating matrixR is generated to measure the users’ evaluations of items [34]. The aim of RSs is to push lists of personalized recommended items to the users. To do recommendation, the ratings of all the items should be assigned for all users. However, in practical cases, some users may not give evaluations to all items, and these evaluations need to be predicted. Let RM×N indicate the true ratings ofM users toN items, and let PrM×N represent the predicted ratings. Then, a number ofL items with the highest predicted ratings for a given user will be added to its recommendation list. Figure 1 gives a simple RS with four users (u1, u2, u3, u4) and four items (i1, i2, i3, i4), which records the ratings of users to movies. Please note that each rating in this recommendation would be “like” and “dislike”, while the solid and dashed lines indicate their true and predicted ratings, respectively.Figure 1
Illustration of a simple RS.


### 2.2. Multiobjective Optimization Problems

Multiobjective optimization problems (MOPs) often consist of several conflicting objectives. In MOPs, the optimization of one objective would affect that of the others. Thus, the result of optimizing all the objectives is not a single optimal solution, but a set of solutions, each of which is the best tradeoff among all the objectives [35–37]. Generally, an MOP can be modeled by(1)MaximizeFx=f1x,f2x,…,fmxwhere x=(x1,x2,...,xn)∈Ω is a decision vector withn dimensions, Ω is the decision space, andm is the number of objectives. The MOP in (1) aims to maximize all the objectives simultaneously. In the following, some definitions about the Pareto optimum theory [38] are given.Definition 1 (Pareto-dominance).
A decision vectorx dominates a decision vector y (noted as x ≻ y) if and only if(2)∀i∈1,2,…,m:fix≥fiy∧∃j∈1,2,…,m:fjx>fjy.Definition 2 (Pareto-optimal).
A solutionx is Pareto-optimal if and only if(3)¬∃y∈Ω:y≻x.Definition 3 (Pareto-optimal set, PS).
This set PS includes all the Pareto-optimal solutions.(4)PS=x∣¬∃y∈Ω:y≻x.Definition 4 (Pareto-optimal front, PF).
This set PF contains all the values of the objective functions related to the Pareto-optimal solutions in PS.(5)PF=Fx=f1x,f2x,…,fmxT∣x∈PS.


### 2.3. Classical Recommendation Algorithms

User based collaborative filtering: It is one classical RS method [39, 40] which predicts the ratings of a user for items based on the preference of some users who show similar interests. For a given useru, itsK most similar users are denoted byS (u,K). Let Iu represent the items rated by the users inS (u,K), but not by the useru. The predicted rating Pr(u,i) of useru to an itemi in Iu is computed by(6)Pru,i=∑v∈Su,Ksuv×rvi∑v∈Su,Ksuv,wheresuv is the similarity between usersu andv, ||suv|| is the absolute value ofsuv, andrvi is the rating of userv to itemi. Then, a numberL of items inIu with high Pr values are recommended to useru, whereL is the length of recommendation list. There are many well-known methods for computing the users’ similarity suv, such as Cosine Similarity (CS) [34], Pearson Correlation Similarity (PCS) [41], and Adjusted Cosine Similarity (ACS) [15]. In this paper, the CS method [34] is chosen due to its simplicity, which computes the similarity suv as follows:(7)suv=ru·rvrurv,whereru is the ratings of useru to all items and |ru| is the length ofru.MOEA with ProbS (MOEA-ProbS) [30]: This algorithm proposed a multiobjective recommendation model to solve the conflicts between accuracy and diversity. In MOEA-ProbS, the accuracy is evaluated by the ProbS method [42], while the diversity is measured by the coverage of the recommendations. MOEA-ProbS can provide multiple recommendations for users in an independent run, such that users can choose what they want from the multiple recommendations according to their preferences. However, the predicted ratings in [30] are not so accurate when compared to the traditional collaborative filtering (CF) algorithm, due to the lack of prior knowledge of RSs.Probabilistic MOEA (PMOEA) [33]: This algorithm mainly introduced a new diversity indicator and a multiparent probability crossover to have a better recommendation. PMOEA was validated to obtain a good balance between the two objectives (accuracy and diversity) in recommendations.Following the MOEAs-based recommendation algorithms in [30, 33], we propose a multiobjective personalized recommendation algorithm using extreme point guided evolutionary computation to enhance the performance of RSs, which shows some advantages in terms of accuracy, diversity, and novelty.


## 2.1. Definition of RSs

RSs aim to predict potential likes and interests of users, according to their historical data about the users’ evaluations of items. Items in RSs may represent any consumed content, like books, movies, news, and music. LetU be a numberM of users, and letI be a numberN of items. Based on the historical data, a rating matrixR is generated to measure the users’ evaluations of items [34]. The aim of RSs is to push lists of personalized recommended items to the users. To do recommendation, the ratings of all the items should be assigned for all users. However, in practical cases, some users may not give evaluations to all items, and these evaluations need to be predicted. Let RM×N indicate the true ratings ofM users toN items, and let PrM×N represent the predicted ratings. Then, a number ofL items with the highest predicted ratings for a given user will be added to its recommendation list. Figure 1 gives a simple RS with four users (u1, u2, u3, u4) and four items (i1, i2, i3, i4), which records the ratings of users to movies. Please note that each rating in this recommendation would be “like” and “dislike”, while the solid and dashed lines indicate their true and predicted ratings, respectively.Figure 1
Illustration of a simple RS.


## 2.2. Multiobjective Optimization Problems

Multiobjective optimization problems (MOPs) often consist of several conflicting objectives. In MOPs, the optimization of one objective would affect that of the others. Thus, the result of optimizing all the objectives is not a single optimal solution, but a set of solutions, each of which is the best tradeoff among all the objectives [35–37]. Generally, an MOP can be modeled by(1)MaximizeFx=f1x,f2x,…,fmxwhere x=(x1,x2,...,xn)∈Ω is a decision vector withn dimensions, Ω is the decision space, andm is the number of objectives. The MOP in (1) aims to maximize all the objectives simultaneously. In the following, some definitions about the Pareto optimum theory [38] are given.Definition 1 (Pareto-dominance).
A decision vectorx dominates a decision vector y (noted as x ≻ y) if and only if(2)∀i∈1,2,…,m:fix≥fiy∧∃j∈1,2,…,m:fjx>fjy.Definition 2 (Pareto-optimal).
A solutionx is Pareto-optimal if and only if(3)¬∃y∈Ω:y≻x.Definition 3 (Pareto-optimal set, PS).
This set PS includes all the Pareto-optimal solutions.(4)PS=x∣¬∃y∈Ω:y≻x.Definition 4 (Pareto-optimal front, PF).
This set PF contains all the values of the objective functions related to the Pareto-optimal solutions in PS.(5)PF=Fx=f1x,f2x,…,fmxT∣x∈PS.


## 2.3. Classical Recommendation Algorithms

User based collaborative filtering: It is one classical RS method [39, 40] which predicts the ratings of a user for items based on the preference of some users who show similar interests. For a given useru, itsK most similar users are denoted byS (u,K). Let Iu represent the items rated by the users inS (u,K), but not by the useru. The predicted rating Pr(u,i) of useru to an itemi in Iu is computed by(6)Pru,i=∑v∈Su,Ksuv×rvi∑v∈Su,Ksuv,wheresuv is the similarity between usersu andv, ||suv|| is the absolute value ofsuv, andrvi is the rating of userv to itemi. Then, a numberL of items inIu with high Pr values are recommended to useru, whereL is the length of recommendation list. There are many well-known methods for computing the users’ similarity suv, such as Cosine Similarity (CS) [34], Pearson Correlation Similarity (PCS) [41], and Adjusted Cosine Similarity (ACS) [15]. In this paper, the CS method [34] is chosen due to its simplicity, which computes the similarity suv as follows:(7)suv=ru·rvrurv,whereru is the ratings of useru to all items and |ru| is the length ofru.MOEA with ProbS (MOEA-ProbS) [30]: This algorithm proposed a multiobjective recommendation model to solve the conflicts between accuracy and diversity. In MOEA-ProbS, the accuracy is evaluated by the ProbS method [42], while the diversity is measured by the coverage of the recommendations. MOEA-ProbS can provide multiple recommendations for users in an independent run, such that users can choose what they want from the multiple recommendations according to their preferences. However, the predicted ratings in [30] are not so accurate when compared to the traditional collaborative filtering (CF) algorithm, due to the lack of prior knowledge of RSs.Probabilistic MOEA (PMOEA) [33]: This algorithm mainly introduced a new diversity indicator and a multiparent probability crossover to have a better recommendation. PMOEA was validated to obtain a good balance between the two objectives (accuracy and diversity) in recommendations.Following the MOEAs-based recommendation algorithms in [30, 33], we propose a multiobjective personalized recommendation algorithm using extreme point guided evolutionary computation to enhance the performance of RSs, which shows some advantages in terms of accuracy, diversity, and novelty.


## 3. Our Algorithm: MOEA-EPG

In this section, we first model the MOP for RSs with three conflicting objectives: accuracy, diversity, and novelty, and then present the MOEA-EPG algorithm to solve this problem.


### 3.1. Optimization Objectives

Three optimization objectives, i.e., accuracy, diversity, and novelty, are used as the objectives for personalized recommendations.The accuracy of recommendations measures the similarity between the predicted ratings and the true user’s ratings. In fact, it is impossible to compute the true user’s ratings in the training stage. Therefore, the predicted ratings of items are used as the optimization objective. The predicted ratings of items for all the users in one clusterC are computed as follows:(8)Pr=∑u∈C∑i∈SupruiC·L,where |C| is the number of users in the clusterC,L is the length of the recommendation list, and Su represents the list of items recommended to useru. In MOEA-ProbS [30], the predicted ratings prui are obtained by ProbS algorithm [42]. Here, following the work in [39], prui is modified as follows:(9)prui=∑v∈Su,Ksuv·rviK,where S(u,K) denotes theK most similar users to useru.The diversity of recommendations reflects the difference between items in a recommendation list. Classical diversity metrics [43], such as interuser diversity, intrauser diversity, and coverage, can be used in our algorithm. Here, the coverage is chosen to evaluate the diversity of recommendations, which is computed as follows:(10)cov=NuN,whereN is the total number of items and Nu is the number of nonduplicated items in the recommendation lists for the users under the same cluster. Generally, RSs with a high coverage in (9) are valuable to users as many choices can be provided for the decisions.The novelty reflects the degree of recommendations, i.e., the number of the unknown items that are recommended to users. Here, we chose the most common index, self-information [30, 33], to evaluate the novelty of recommended items. Let di represent the popularity degree of an itemi. The self-information of itemi is defined as follows:(11)Ni=log2⁡Mdi,whereM is the total number of users. Generally, items with a low popularity degree are novel to users. For better recommendations, the average noveltyN(L) which represents the mean self-information of all the items in the recommendation list is used, which is computed as follows:(12)NL=1M∑u=1M∑i∈SuNiL,whereSu is the recommendation list of useru.


### 3.2. Our Method

#### 3.2.1. Extreme Point Guided Method

To accelerate the convergence of recommendations, an extreme point guided method is used, which incorporates the prior knowledge of RSs. In this method, three extreme points, each of which has the maximal value for one objective, are used to extend the Pareto-optimal front.The accuracy of recommendations in (8) will be affected by the coverage in (10) and the novelty in (12). In our approach, an optimal value for (8) is found at the initialization phase and it is treated as an extreme point to guide the evolutionary process, aiming to search the extreme region toward the accuracy. For each useru in one clusterC, let Su be the set of available items for userusorted by a descending order based on the predicted ratings. Then, the firstL items in Su are assigned to the recommendation list sumax_accuracy and recommended to useru. This extreme point eaccuracy has a maximal accuracy, as follows:(13)PReaccuracy=∑u∈C∑i∈sumax_accuracypruiC·L.Similarly, the second extreme point is found by only optimizing the coverage. The optimal value for coverage can include diverse categories of items. Therefore, assume that the users in a clusterC are represented by U={u1,u2,...,uM}, where M is the number of users in the clusterC. To enhance the coverage, the items that have been recommended to previous users are removed and no longer pushed to the other users. This method assures the diversity of items and reduces duplicates in the clusterC. Thus, this extreme point ecoverage shows the property of maximal coverage, as follows:(14)covecoverage=NumaxN,where Numax is the number of distinct items for all the users under the same cluster.The third extreme point is obtained by only optimizing the novelty of recommendations. Similarly, for each useru in a clusterC, theL items in Su with the largest self-information in (12) are first found, and then they are assigned to the recommendation list of useru. Based on (11), the items with low degree will have high self-information. Thus, theL items with the smallest degrees for each useru are actually recommended, and they are recorded by Sumax_novelity. This extreme point enovelity has a maximal novelty, as follows:(15)NLenovelity=1M∑u=1M∑i∈Sumax⁡_novelityNiL.Here Ni is the self-information of itemi as defined in (11).These three extreme points are used to accelerate the convergence of our algorithm toward the entire Pareto-optimal front and also to enhance the population’s diversity.


#### 3.2.2. Solution Encoding

The encoding formula in [30] is used to convert the recommendation list as the solutions for MOPs. In RSs, recommendation results should be provided to all the users in the same cluster. Here, a solution represents recommendation lists of all users in the same cluster. Given a numberM of users in a cluster and a lengthL of recommendation list, the solution is encoded by a matrix with sizeM×L. Therefore, the matrix consists of all items recommended to users in a cluster. The solution encoding is shown in Figure 2, in which each row represents theL items recommended for each user. In general, RSs are limited to recommend the same items to a user twice.Figure 2
Illustration of chromosome encoding.


#### 3.2.3. Evolutionary Operators

The uniform crossover [30] is used in our approach due to its simplicity. As shown in Figure 3, in each crossover process, two similar users are chosen to execute the crossover. To avoid generating invalid solutions (i.e., one item is recommended to a user twice or more), an additional operation which propagates the same elements in the two parents to the offspring is executed. In the remaining positions, the offspring will inherit from the first parent if a randomly generated value in [0,1] is larger than 0.5; otherwise, it will inherit from the second parent [30]. The above crossover is executed on all pairs of parent solutions.Figure 3
Illustration of crossover operator for two similar users on two parent solutions (Parent 1 and Parent 2).A mutation operator is performed on each individual generated by the crossover, which is detailed as follows: if a gene from the parent matrix is selected for mutation, an available item is randomly selected from the items. To avoid useless solutions, we choose one of the remaining items that does not exist in the parent.


#### 3.2.4. Complete Algorithm of MOEA-EPG

The flowchart of MOEA-EPG is shown in Figure4. MOEA-EPG includes two main parts: data processing and evolutionary algorithm. Moreover, the framework of MOEA-EPG is also provided in Algorithm 1, whereN is the population size,T means the maximum number of generations,K shows the ratio of similar users,P records the recommendation lists for all users, andL is the length of recommendation list.Algorithm 1:Framework of MOEA-EPG.
( 1 ) Input the training data, the test data, and a binary matrix R ( 2 ) Set g=0,L=10, N=100, T=3000, K=0.5 ( 3 ) Cluster all the users U in the training data into four clusters with size Mj, j={1,2,3,4} ( 4 ) U={U1,U2,U3,U4} and Uj={u1,u2,...,uMj} ( 5 ) Set P={p1,p2,p3,p4} with pj=[],j=1,2,3,4 ( 6 ) forj=1 to 4 ( 7 )   Compute the similarities of different users in Uj based on Eq. (7) ( 8 )   Set prj={0}Mj×Mj ( 9 )   fork=1 to Mj ( 10 )      Compute the available items of user uk, as recorded by the set Iuk={i1,i2,...,iNs} ( 11 )      for  n=1 to Ns ( 12 )       Compute the predict rating prui for user uk to item in by Eq. (8) ( 13 )    EPOP = Initialization(L, N,R,pr) ( 14 )    whileg<T ( 15 )        Epa = Objective_Func(EPOP) ( 16 )        Epa = Fast_Non_Dominated_Sort(EPa) ( 17 )        EPOP = Selection(EPOP,Epa) ( 18 )        EPOP = Uniform_Crossover(EPOP) ( 19 )        NPOP = Mutation(EPOP) ( 20 )        POP = [NPOP;EPOP] ( 21 )        EPOP = Update(POP,Epa, N) ( 22 )        g= g+1 ( 23 )   pi = EPOP ( 24 ) ReturnPFigure 4
Flowchart for MOEA-EPG.In the phase of data processing, the usersU are classified into several clusters based on theK-means clustering [44] in the training data. In this paper, we divide users into four clusters, i.e., U1,U2,U3,U4, and four recommendation lists p1,p2,p3,p4 are initialized as four empty sets, as shown in lines (3)-(5). After that, the available itemsIu of each user and the predicted ratings prui of these items are calculated according to the similarities of different users in lines (6)-(12). The framework of MOEA-EPG is given as follows.In line(13), the three extreme points (eaccuracy, ecoverage, and enovelity) are calculated using (13)-(15) and then the algorithm executes initialization. In line (15), the function Objective_Func(.) calculates the objective values of the individuals in the populationEPOP based on (8), (10), and (12), and it records the final results atEpa. After that, the function Fast_Non_Dominated_Sort(.) in Algorithm 2 is executed on the evolutionary population to generate nondominated fronts based onEpawhich are the solutions on the first level in line (16). Then, the function selection(.) in line (17) selects parent solutions from the populationEPOPby using the binary tournament [45]. The functions Uniform_Crossover(.) and Mutation(.) in lines (18)-(19) execute the crossover and mutation operations in Section 3.2.3 on the parent populationEPOP, respectively, which produce the offspring populationNPOP. Finally, the function Update(.) choosesN individuals asPOP fromEPOP andNPOP for the next evolution based on the elitist selection strategy [24] (lines (20)-(21)). This strategy is composed of a fast nondominated sorting and a crowding distance comparison. Then, the loop of evolutionary algorithm is repeated until the current generation numberg reaches the predefined maximal generationT. If this termination condition is satisfied, our algorithm will return the recommendation resultsP and all users are recommended (line (24)).Algorithm 2:Fast_Non_Dominated_Sort(Epa).
( 1 ) Input the population Epa ( 2 ) for each  p∈Epa ( 3 )     Sp =⌀, MP= 0 ( 4 )     for each  q∈Epa ( 5 )     if(p≻q) then    // If p dominates q ( 6 )     Sp = Sp∪q    // Add q to the set of solutions dominated by p ( 7 )     else if (q≻p) then ( 8 )     MP = MP +1  // Increment the domination counter of p ( 9 )       if  MP = 0 then    //p belongs to the first front ( 10 )     Eparank = 1 ( 11 )     F1 =F1∪p ( 12 ) i=1      // Initialize the front counter ( 13 ) while  Fi≠⌀ ( 14 )   S=⌀   // Used to store the members of the next front ( 15 )   for eachp∈Fi ( 16 )   for eachq∈Sp ( 17 )     Mq =Mq -1 ( 18 )     ifMq = 0 then  //q belongs to the next front ( 19 )     qrank = i+1 ( 20 )     H= H∪q ( 21 ) i = i+1 ( 22 ) Fi= H ( 23 ) ReturnFiThe function Fast_Non_Dominated_Sort(.) in Algorithm2 works as follows. Firstly, the solutions on the first level are found based on the nondominated sorting strategy (lines (4)-(11) in Algorithm 2). Secondly, the solutions on the first level are deleted, and the nondominated sorting strategy works on the rest of solutions to find the solutions on the top level (lines (13)-(20) in Algorithm 2). The steps above are executed until all solutions are sorted in a ranking level (lines (21)-(23) in Algorithm 2). In this case, all individuals are divided into multiple levels. The detailed descriptions for the Fast_Non_Dominated_Sort(.) in Algorithm 2 can be found in [24]. Here, a simple example is given in Figure 5 when optimizing the three conflicting objectives (accuracy, coverage, and novelty). The tradeoff on these three objectives can be well observed and the solutions plotted by the red circles on the first level are preferred, as they are more effective and efficient to approach the PF.Figure 5
A fast nondominated sorting procedure in NSGA-II regarding the three objective optimizations [24].


## 3.1. Optimization Objectives

Three optimization objectives, i.e., accuracy, diversity, and novelty, are used as the objectives for personalized recommendations.The accuracy of recommendations measures the similarity between the predicted ratings and the true user’s ratings. In fact, it is impossible to compute the true user’s ratings in the training stage. Therefore, the predicted ratings of items are used as the optimization objective. The predicted ratings of items for all the users in one clusterC are computed as follows:(8)Pr=∑u∈C∑i∈SupruiC·L,where |C| is the number of users in the clusterC,L is the length of the recommendation list, and Su represents the list of items recommended to useru. In MOEA-ProbS [30], the predicted ratings prui are obtained by ProbS algorithm [42]. Here, following the work in [39], prui is modified as follows:(9)prui=∑v∈Su,Ksuv·rviK,where S(u,K) denotes theK most similar users to useru.The diversity of recommendations reflects the difference between items in a recommendation list. Classical diversity metrics [43], such as interuser diversity, intrauser diversity, and coverage, can be used in our algorithm. Here, the coverage is chosen to evaluate the diversity of recommendations, which is computed as follows:(10)cov=NuN,whereN is the total number of items and Nu is the number of nonduplicated items in the recommendation lists for the users under the same cluster. Generally, RSs with a high coverage in (9) are valuable to users as many choices can be provided for the decisions.The novelty reflects the degree of recommendations, i.e., the number of the unknown items that are recommended to users. Here, we chose the most common index, self-information [30, 33], to evaluate the novelty of recommended items. Let di represent the popularity degree of an itemi. The self-information of itemi is defined as follows:(11)Ni=log2⁡Mdi,whereM is the total number of users. Generally, items with a low popularity degree are novel to users. For better recommendations, the average noveltyN(L) which represents the mean self-information of all the items in the recommendation list is used, which is computed as follows:(12)NL=1M∑u=1M∑i∈SuNiL,whereSu is the recommendation list of useru.


## 3.2. Our Method

### 3.2.1. Extreme Point Guided Method

To accelerate the convergence of recommendations, an extreme point guided method is used, which incorporates the prior knowledge of RSs. In this method, three extreme points, each of which has the maximal value for one objective, are used to extend the Pareto-optimal front.The accuracy of recommendations in (8) will be affected by the coverage in (10) and the novelty in (12). In our approach, an optimal value for (8) is found at the initialization phase and it is treated as an extreme point to guide the evolutionary process, aiming to search the extreme region toward the accuracy. For each useru in one clusterC, let Su be the set of available items for userusorted by a descending order based on the predicted ratings. Then, the firstL items in Su are assigned to the recommendation list sumax_accuracy and recommended to useru. This extreme point eaccuracy has a maximal accuracy, as follows:(13)PReaccuracy=∑u∈C∑i∈sumax_accuracypruiC·L.Similarly, the second extreme point is found by only optimizing the coverage. The optimal value for coverage can include diverse categories of items. Therefore, assume that the users in a clusterC are represented by U={u1,u2,...,uM}, where M is the number of users in the clusterC. To enhance the coverage, the items that have been recommended to previous users are removed and no longer pushed to the other users. This method assures the diversity of items and reduces duplicates in the clusterC. Thus, this extreme point ecoverage shows the property of maximal coverage, as follows:(14)covecoverage=NumaxN,where Numax is the number of distinct items for all the users under the same cluster.The third extreme point is obtained by only optimizing the novelty of recommendations. Similarly, for each useru in a clusterC, theL items in Su with the largest self-information in (12) are first found, and then they are assigned to the recommendation list of useru. Based on (11), the items with low degree will have high self-information. Thus, theL items with the smallest degrees for each useru are actually recommended, and they are recorded by Sumax_novelity. This extreme point enovelity has a maximal novelty, as follows:(15)NLenovelity=1M∑u=1M∑i∈Sumax⁡_novelityNiL.Here Ni is the self-information of itemi as defined in (11).These three extreme points are used to accelerate the convergence of our algorithm toward the entire Pareto-optimal front and also to enhance the population’s diversity.


### 3.2.2. Solution Encoding

The encoding formula in [30] is used to convert the recommendation list as the solutions for MOPs. In RSs, recommendation results should be provided to all the users in the same cluster. Here, a solution represents recommendation lists of all users in the same cluster. Given a numberM of users in a cluster and a lengthL of recommendation list, the solution is encoded by a matrix with sizeM×L. Therefore, the matrix consists of all items recommended to users in a cluster. The solution encoding is shown in Figure 2, in which each row represents theL items recommended for each user. In general, RSs are limited to recommend the same items to a user twice.Figure 2
Illustration of chromosome encoding.


### 3.2.3. Evolutionary Operators

The uniform crossover [30] is used in our approach due to its simplicity. As shown in Figure 3, in each crossover process, two similar users are chosen to execute the crossover. To avoid generating invalid solutions (i.e., one item is recommended to a user twice or more), an additional operation which propagates the same elements in the two parents to the offspring is executed. In the remaining positions, the offspring will inherit from the first parent if a randomly generated value in [0,1] is larger than 0.5; otherwise, it will inherit from the second parent [30]. The above crossover is executed on all pairs of parent solutions.Figure 3
Illustration of crossover operator for two similar users on two parent solutions (Parent 1 and Parent 2).A mutation operator is performed on each individual generated by the crossover, which is detailed as follows: if a gene from the parent matrix is selected for mutation, an available item is randomly selected from the items. To avoid useless solutions, we choose one of the remaining items that does not exist in the parent.


### 3.2.4. Complete Algorithm of MOEA-EPG

The flowchart of MOEA-EPG is shown in Figure4. MOEA-EPG includes two main parts: data processing and evolutionary algorithm. Moreover, the framework of MOEA-EPG is also provided in Algorithm 1, whereN is the population size,T means the maximum number of generations,K shows the ratio of similar users,P records the recommendation lists for all users, andL is the length of recommendation list.Algorithm 1:Framework of MOEA-EPG.
( 1 ) Input the training data, the test data, and a binary matrix R ( 2 ) Set g=0,L=10, N=100, T=3000, K=0.5 ( 3 ) Cluster all the users U in the training data into four clusters with size Mj, j={1,2,3,4} ( 4 ) U={U1,U2,U3,U4} and Uj={u1,u2,...,uMj} ( 5 ) Set P={p1,p2,p3,p4} with pj=[],j=1,2,3,4 ( 6 ) forj=1 to 4 ( 7 )   Compute the similarities of different users in Uj based on Eq. (7) ( 8 )   Set prj={0}Mj×Mj ( 9 )   fork=1 to Mj ( 10 )      Compute the available items of user uk, as recorded by the set Iuk={i1,i2,...,iNs} ( 11 )      for  n=1 to Ns ( 12 )       Compute the predict rating prui for user uk to item in by Eq. (8) ( 13 )    EPOP = Initialization(L, N,R,pr) ( 14 )    whileg<T ( 15 )        Epa = Objective_Func(EPOP) ( 16 )        Epa = Fast_Non_Dominated_Sort(EPa) ( 17 )        EPOP = Selection(EPOP,Epa) ( 18 )        EPOP = Uniform_Crossover(EPOP) ( 19 )        NPOP = Mutation(EPOP) ( 20 )        POP = [NPOP;EPOP] ( 21 )        EPOP = Update(POP,Epa, N) ( 22 )        g= g+1 ( 23 )   pi = EPOP ( 24 ) ReturnPFigure 4
Flowchart for MOEA-EPG.In the phase of data processing, the usersU are classified into several clusters based on theK-means clustering [44] in the training data. In this paper, we divide users into four clusters, i.e., U1,U2,U3,U4, and four recommendation lists p1,p2,p3,p4 are initialized as four empty sets, as shown in lines (3)-(5). After that, the available itemsIu of each user and the predicted ratings prui of these items are calculated according to the similarities of different users in lines (6)-(12). The framework of MOEA-EPG is given as follows.In line(13), the three extreme points (eaccuracy, ecoverage, and enovelity) are calculated using (13)-(15) and then the algorithm executes initialization. In line (15), the function Objective_Func(.) calculates the objective values of the individuals in the populationEPOP based on (8), (10), and (12), and it records the final results atEpa. After that, the function Fast_Non_Dominated_Sort(.) in Algorithm 2 is executed on the evolutionary population to generate nondominated fronts based onEpawhich are the solutions on the first level in line (16). Then, the function selection(.) in line (17) selects parent solutions from the populationEPOPby using the binary tournament [45]. The functions Uniform_Crossover(.) and Mutation(.) in lines (18)-(19) execute the crossover and mutation operations in Section 3.2.3 on the parent populationEPOP, respectively, which produce the offspring populationNPOP. Finally, the function Update(.) choosesN individuals asPOP fromEPOP andNPOP for the next evolution based on the elitist selection strategy [24] (lines (20)-(21)). This strategy is composed of a fast nondominated sorting and a crowding distance comparison. Then, the loop of evolutionary algorithm is repeated until the current generation numberg reaches the predefined maximal generationT. If this termination condition is satisfied, our algorithm will return the recommendation resultsP and all users are recommended (line (24)).Algorithm 2:Fast_Non_Dominated_Sort(Epa).
( 1 ) Input the population Epa ( 2 ) for each  p∈Epa ( 3 )     Sp =⌀, MP= 0 ( 4 )     for each  q∈Epa ( 5 )     if(p≻q) then    // If p dominates q ( 6 )     Sp = Sp∪q    // Add q to the set of solutions dominated by p ( 7 )     else if (q≻p) then ( 8 )     MP = MP +1  // Increment the domination counter of p ( 9 )       if  MP = 0 then    //p belongs to the first front ( 10 )     Eparank = 1 ( 11 )     F1 =F1∪p ( 12 ) i=1      // Initialize the front counter ( 13 ) while  Fi≠⌀ ( 14 )   S=⌀   // Used to store the members of the next front ( 15 )   for eachp∈Fi ( 16 )   for eachq∈Sp ( 17 )     Mq =Mq -1 ( 18 )     ifMq = 0 then  //q belongs to the next front ( 19 )     qrank = i+1 ( 20 )     H= H∪q ( 21 ) i = i+1 ( 22 ) Fi= H ( 23 ) ReturnFiThe function Fast_Non_Dominated_Sort(.) in Algorithm2 works as follows. Firstly, the solutions on the first level are found based on the nondominated sorting strategy (lines (4)-(11) in Algorithm 2). Secondly, the solutions on the first level are deleted, and the nondominated sorting strategy works on the rest of solutions to find the solutions on the top level (lines (13)-(20) in Algorithm 2). The steps above are executed until all solutions are sorted in a ranking level (lines (21)-(23) in Algorithm 2). In this case, all individuals are divided into multiple levels. The detailed descriptions for the Fast_Non_Dominated_Sort(.) in Algorithm 2 can be found in [24]. Here, a simple example is given in Figure 5 when optimizing the three conflicting objectives (accuracy, coverage, and novelty). The tradeoff on these three objectives can be well observed and the solutions plotted by the red circles on the first level are preferred, as they are more effective and efficient to approach the PF.Figure 5
A fast nondominated sorting procedure in NSGA-II regarding the three objective optimizations [24].


## 3.2.1. Extreme Point Guided Method

To accelerate the convergence of recommendations, an extreme point guided method is used, which incorporates the prior knowledge of RSs. In this method, three extreme points, each of which has the maximal value for one objective, are used to extend the Pareto-optimal front.The accuracy of recommendations in (8) will be affected by the coverage in (10) and the novelty in (12). In our approach, an optimal value for (8) is found at the initialization phase and it is treated as an extreme point to guide the evolutionary process, aiming to search the extreme region toward the accuracy. For each useru in one clusterC, let Su be the set of available items for userusorted by a descending order based on the predicted ratings. Then, the firstL items in Su are assigned to the recommendation list sumax_accuracy and recommended to useru. This extreme point eaccuracy has a maximal accuracy, as follows:(13)PReaccuracy=∑u∈C∑i∈sumax_accuracypruiC·L.Similarly, the second extreme point is found by only optimizing the coverage. The optimal value for coverage can include diverse categories of items. Therefore, assume that the users in a clusterC are represented by U={u1,u2,...,uM}, where M is the number of users in the clusterC. To enhance the coverage, the items that have been recommended to previous users are removed and no longer pushed to the other users. This method assures the diversity of items and reduces duplicates in the clusterC. Thus, this extreme point ecoverage shows the property of maximal coverage, as follows:(14)covecoverage=NumaxN,where Numax is the number of distinct items for all the users under the same cluster.The third extreme point is obtained by only optimizing the novelty of recommendations. Similarly, for each useru in a clusterC, theL items in Su with the largest self-information in (12) are first found, and then they are assigned to the recommendation list of useru. Based on (11), the items with low degree will have high self-information. Thus, theL items with the smallest degrees for each useru are actually recommended, and they are recorded by Sumax_novelity. This extreme point enovelity has a maximal novelty, as follows:(15)NLenovelity=1M∑u=1M∑i∈Sumax⁡_novelityNiL.Here Ni is the self-information of itemi as defined in (11).These three extreme points are used to accelerate the convergence of our algorithm toward the entire Pareto-optimal front and also to enhance the population’s diversity.


## 3.2.2. Solution Encoding

The encoding formula in [30] is used to convert the recommendation list as the solutions for MOPs. In RSs, recommendation results should be provided to all the users in the same cluster. Here, a solution represents recommendation lists of all users in the same cluster. Given a numberM of users in a cluster and a lengthL of recommendation list, the solution is encoded by a matrix with sizeM×L. Therefore, the matrix consists of all items recommended to users in a cluster. The solution encoding is shown in Figure 2, in which each row represents theL items recommended for each user. In general, RSs are limited to recommend the same items to a user twice.Figure 2
Illustration of chromosome encoding.


## 3.2.3. Evolutionary Operators

The uniform crossover [30] is used in our approach due to its simplicity. As shown in Figure 3, in each crossover process, two similar users are chosen to execute the crossover. To avoid generating invalid solutions (i.e., one item is recommended to a user twice or more), an additional operation which propagates the same elements in the two parents to the offspring is executed. In the remaining positions, the offspring will inherit from the first parent if a randomly generated value in [0,1] is larger than 0.5; otherwise, it will inherit from the second parent [30]. The above crossover is executed on all pairs of parent solutions.Figure 3
Illustration of crossover operator for two similar users on two parent solutions (Parent 1 and Parent 2).A mutation operator is performed on each individual generated by the crossover, which is detailed as follows: if a gene from the parent matrix is selected for mutation, an available item is randomly selected from the items. To avoid useless solutions, we choose one of the remaining items that does not exist in the parent.


## 3.2.4. Complete Algorithm of MOEA-EPG

The flowchart of MOEA-EPG is shown in Figure4. MOEA-EPG includes two main parts: data processing and evolutionary algorithm. Moreover, the framework of MOEA-EPG is also provided in Algorithm 1, whereN is the population size,T means the maximum number of generations,K shows the ratio of similar users,P records the recommendation lists for all users, andL is the length of recommendation list.Algorithm 1:Framework of MOEA-EPG.
( 1 ) Input the training data, the test data, and a binary matrix R ( 2 ) Set g=0,L=10, N=100, T=3000, K=0.5 ( 3 ) Cluster all the users U in the training data into four clusters with size Mj, j={1,2,3,4} ( 4 ) U={U1,U2,U3,U4} and Uj={u1,u2,...,uMj} ( 5 ) Set P={p1,p2,p3,p4} with pj=[],j=1,2,3,4 ( 6 ) forj=1 to 4 ( 7 )   Compute the similarities of different users in Uj based on Eq. (7) ( 8 )   Set prj={0}Mj×Mj ( 9 )   fork=1 to Mj ( 10 )      Compute the available items of user uk, as recorded by the set Iuk={i1,i2,...,iNs} ( 11 )      for  n=1 to Ns ( 12 )       Compute the predict rating prui for user uk to item in by Eq. (8) ( 13 )    EPOP = Initialization(L, N,R,pr) ( 14 )    whileg<T ( 15 )        Epa = Objective_Func(EPOP) ( 16 )        Epa = Fast_Non_Dominated_Sort(EPa) ( 17 )        EPOP = Selection(EPOP,Epa) ( 18 )        EPOP = Uniform_Crossover(EPOP) ( 19 )        NPOP = Mutation(EPOP) ( 20 )        POP = [NPOP;EPOP] ( 21 )        EPOP = Update(POP,Epa, N) ( 22 )        g= g+1 ( 23 )   pi = EPOP ( 24 ) ReturnPFigure 4
Flowchart for MOEA-EPG.In the phase of data processing, the usersU are classified into several clusters based on theK-means clustering [44] in the training data. In this paper, we divide users into four clusters, i.e., U1,U2,U3,U4, and four recommendation lists p1,p2,p3,p4 are initialized as four empty sets, as shown in lines (3)-(5). After that, the available itemsIu of each user and the predicted ratings prui of these items are calculated according to the similarities of different users in lines (6)-(12). The framework of MOEA-EPG is given as follows.In line(13), the three extreme points (eaccuracy, ecoverage, and enovelity) are calculated using (13)-(15) and then the algorithm executes initialization. In line (15), the function Objective_Func(.) calculates the objective values of the individuals in the populationEPOP based on (8), (10), and (12), and it records the final results atEpa. After that, the function Fast_Non_Dominated_Sort(.) in Algorithm 2 is executed on the evolutionary population to generate nondominated fronts based onEpawhich are the solutions on the first level in line (16). Then, the function selection(.) in line (17) selects parent solutions from the populationEPOPby using the binary tournament [45]. The functions Uniform_Crossover(.) and Mutation(.) in lines (18)-(19) execute the crossover and mutation operations in Section 3.2.3 on the parent populationEPOP, respectively, which produce the offspring populationNPOP. Finally, the function Update(.) choosesN individuals asPOP fromEPOP andNPOP for the next evolution based on the elitist selection strategy [24] (lines (20)-(21)). This strategy is composed of a fast nondominated sorting and a crowding distance comparison. Then, the loop of evolutionary algorithm is repeated until the current generation numberg reaches the predefined maximal generationT. If this termination condition is satisfied, our algorithm will return the recommendation resultsP and all users are recommended (line (24)).Algorithm 2:Fast_Non_Dominated_Sort(Epa).
( 1 ) Input the population Epa ( 2 ) for each  p∈Epa ( 3 )     Sp =⌀, MP= 0 ( 4 )     for each  q∈Epa ( 5 )     if(p≻q) then    // If p dominates q ( 6 )     Sp = Sp∪q    // Add q to the set of solutions dominated by p ( 7 )     else if (q≻p) then ( 8 )     MP = MP +1  // Increment the domination counter of p ( 9 )       if  MP = 0 then    //p belongs to the first front ( 10 )     Eparank = 1 ( 11 )     F1 =F1∪p ( 12 ) i=1      // Initialize the front counter ( 13 ) while  Fi≠⌀ ( 14 )   S=⌀   // Used to store the members of the next front ( 15 )   for eachp∈Fi ( 16 )   for eachq∈Sp ( 17 )     Mq =Mq -1 ( 18 )     ifMq = 0 then  //q belongs to the next front ( 19 )     qrank = i+1 ( 20 )     H= H∪q ( 21 ) i = i+1 ( 22 ) Fi= H ( 23 ) ReturnFiThe function Fast_Non_Dominated_Sort(.) in Algorithm2 works as follows. Firstly, the solutions on the first level are found based on the nondominated sorting strategy (lines (4)-(11) in Algorithm 2). Secondly, the solutions on the first level are deleted, and the nondominated sorting strategy works on the rest of solutions to find the solutions on the top level (lines (13)-(20) in Algorithm 2). The steps above are executed until all solutions are sorted in a ranking level (lines (21)-(23) in Algorithm 2). In this case, all individuals are divided into multiple levels. The detailed descriptions for the Fast_Non_Dominated_Sort(.) in Algorithm 2 can be found in [24]. Here, a simple example is given in Figure 5 when optimizing the three conflicting objectives (accuracy, coverage, and novelty). The tradeoff on these three objectives can be well observed and the solutions plotted by the red circles on the first level are preferred, as they are more effective and efficient to approach the PF.Figure 5
A fast nondominated sorting procedure in NSGA-II regarding the three objective optimizations [24].


## 4. Experimental Results

In this section, experiments on two data sets are executed to examine the performance of MOEA-EPG. First, some settings about the experiments are introduced, including the experimental data, the performance metrics, and the parameters settings. Second, comparisons of MOEA-EPG with two state-of-the-art recommendation algorithms (i.e., User-based-CF [39] and MF [46]) and two competitive MOEAs for RSs (i.e., MOEA-ProbS [30] and PMOEA [33]) are made to demonstrate the effectiveness of MOEA-EPG in the accuracy, diversity, and novelty of the recommendations. Finally, the effectiveness of the extreme point guided method and the impacts of some parameters are analyzed.


### 4.1. Experimental Data

In our experiments, two classical benchmark data sets, i.e., Movielens and Netflix, are used. The Movielens data set includes 943 users and 1682 movies, which can be downloaded from the website of GroupLens Research (http://www.grouplens.org/). The original ratings in this data are assigned values from 1 to 5. Here, a binary rating system is used by using “like” or “dislike”. An item is assigned to the binary rating “like” by a user when his original rating is larger than 3 [30]. Then, 80% of the data are randomly selected as the training data set with known information for recommendations, while the remaining data are used as the test data set. To make a fair comparison, similar to [30], the users in this data are divided into four clusters by using theK-means algorithm [47], each of which is used as the test data. The properties of these data sets are presented in Table 1 [23].Table 1
Properties of the Movielens data sets.
Data sets Users Items Sparsity Movielens 1 200 1682 1.39 × 1 0 - 2 Movielens 2 258 1682 5.17 × 1 0 - 2 Movielens 3 227 1682 2.38 × 1 0 - 2 Movielens 4 258 1682 6.89 × 1 0 - 2The Netflix data set was used for the Netflix prize, which can be downloaded from the contest website (http://www.netflixprize.com/). Here, a random subset of Netflix set is used, containing 155177 ratings of 1000 users on 3952 movies. The properties of these data sets are shown in Table 2.Table 2
Properties of the Netflix data sets.
Data sets Users Items Sparsity Netflix 1 191 3952 2.11 × 1 0 - 2 Netflix 2 250 3952 1.92 × 1 0 - 2 Netflix 3 375 3952 2.73 × 1 0 - 2 Netflix 4 184 3952 2.21 × 1 0 - 2


### 4.2. Performance Metrics

Here, the hypervolume (HV) metric [27] is adopted to evaluate the convergence and diversity of solutions, which is widely used for the evaluations of MOEAs [36, 37]. Let zr=(z1r,⋯,zmr)T be a reference point in the objective space that is dominated by all vectors in true PF. TheHV metric calculates the size of the objective space dominated by the solutions inS and bounded byzr, which is computed as follows:(16)HVS=VOL⋃x∈Sf1x,z1r×⋯×fmx,zmr,where VOL(·) denotes the Lebesgue measure. In this paper, the reference pointzr is set to (0, 0) and (0, 0, 0) for biobjective and three-objective problems, respectively. A largeHV indicates the solution set has a good quality. In this experiment, all the algorithms with the highestHV from 30 runs are selected for comparisons.Moreover, three performance metrics are used, i.e., precision, coverage, and novelty. Precision is the most important metric for evaluating RSs. For a given useru, its precision is defined as the ratio of relevant items, which are correctly recommended, as defined by(17)Pu=NRuL,where NRu is the number of common items in the recommendation list of useru and the test data set preferred by useru, andL is the length of recommendation list. The recommendation accuracy in this paper is measured by the mean precision of all the users.The coverage metric of RSs illustrates the ratio of distinct items in the recommendation list over all the available items. Generally, RSs with a low coverage may be ineffective to users, as they are not enough to make decisions. In this paper, the objective in (10) is used as a performance metric to measure the diversity of RSs.The novelty of RSs reflects how well RSs can recommend unknown items to users. Generally, RSs with a large novelty will extend user’s interests. In this paper, the objective in (12) is used as a performance metric for this indicator.


### 4.3. Experimental Settings of Comparison Algorithms

The related parameters in comparison algorithms are listed in Table3, and the length of recommendation listL is set to 10. To allow a fair comparison, the related parameters for each algorithm were set as suggested in the corresponding references [30, 33, 39, 46].Table 3
The related parameters in comparison algorithms.
Algorithms Parameters Settings User-based-CF L=10  MF L=10  MOEA-ProbS p c=0.8, pm=1/L, L=10, N=100, T=3000, Tr=30  PMOEA p n =5, pm=1/L, L=10, N=100,T =3000, Tr=30, n=20  MOEA-EPG p c =0.8, pm=1/L, L=10, N=100, T=3000, Tr=30, K=0.5In Table3,N is the population size, pc and pm are, respectively, the crossover probability and the mutation probability, pn is the number of parents used for crossover in PMOEA (PMOEA-ProbS and PMOEA-CF),n is the number of neighbors, andTr is the number of independent trials. Moreover, in MOEA-EPG, K means the ratio of the most similar users to the target users within a cluster. The comparisons of MOEA-EPG with these algorithms are comprehensive and effective in validating its performance.


### 4.4. Effectiveness of MOEA-EPG

To study the effectiveness of our MOEA-EPG, a three-objective model is used to show the experimental results of MOEA-EPG on all the eight data sets. The nondominated solutions with the highestHV value [27] are plotted as the final results for each data set. In Figure 6, the final solutions of MOEA-EPG are plotted for all the eight data sets on the objective space. As observed from Figure 6, there exists a tradeoff among the used three objectives, which forms a nondominated front. Each solution in the nondominated front is marked by the blue square. From these plots, we can observe that the quality and distribution of solutions are quite good.Figure 6
Final solutions of MOEA-EPG under the accuracy-coverage-novelty space for (a) Movielens 1, (b) Movielens 2, (c) Movielens 3, (d) Movielens 4, (e) Netflix 1, (f) Netflix 2, (g) Netflix 3, and (h) Netflix 4.
(a) (b) (c) (d) (e) (f) (g) (h)To further show the distributions ofHV results, Figure 7 gives the boxplots of differentHV values for eight data sets obtained by MOEA-EPG in the accuracy-coverage space under 30 runs. On each box diagram, the central mark is the median, while the upper and lower edges of the box mean the 25th and 75th percentiles, respectively. Obviously, the distribution ofHV values of MOEA-EPG is robust, which further confirms the effectiveness of our algorithm.Figure 7
The boxplots ofHV values for MOEA-EPG under the accuracy-coverage space for different data sets. 1: Movielens 1, 2: Movielens 2, 3: Movielens 3, 4: Movielens 4, 5: Netflix 1, 6: Netflix 2, 7: Netflix 3 and 8: Netflix 4.


### 4.5. Comparisons with Other Competitors

In this subsection, our algorithm is compared with five competitors on the classical Movielens and Netflix data sets. As User-based-CF and MF only obtain one optimal value in one run, they cannot be used as comparison algorithms usingHV. In our experiments, the performance comparisons are conducted under different objectives, i.e., the accuracy-coverage, the accuracy-novelty, and the accuracy-coverage-novelty spaces.Since the computation difficulties under different objectives are varied, the parameterT is set to 3000 for the accuracy-coverage and accuracy-novelty spaces and set to 6000 for the accuracy-coverage-novelty space, while the remaining parameters are set the same as listed in Table 3. All the meanHV values and the standard deviations are collected for performance comparisons in Table 4, where the best result is highlighted in boldface. From Table 4, it can be observed that MOEA-EPG shows the best performance among all the MOEAs-based recommendation algorithms, especially in the accuracy-novelty space and accuracy-coverage-novelty spaces.Table 4
HV comparison results of MOEA-EPG and other algorithms on all the objectives for eight data sets.
Data sets Test Instance MOEA-ProbS PMOEA-ProbS PMOEA-CF MOEA-EPG Movielens 1 Accuracy-coverage 1.4431.38e-02 1.5331.13e-02 1.3681.36e-02 3.202 7.74e-02 Accuracy-novelty 11.401.45e-01 9.6671.16e-01 9.2881.07e-01 36.89 6.05e-02 Accuracy-coverage-novelty 5.5041.06e-01 5.3191.13e-01 4.8189.50e-02 12.23 5.34e-01  Movielens 2 Accuracy-coverage 1.5311.03e-02 1.1921.83e-02 1.0851.68e-02 4.677 3.46e-02 Accuracy-novelty 10.961.12e-01 9.2881.23e-01 8.8191.34e-01 35.43 7.83e-02 Accuracy-coverage-novelty 6.0271.23e-01 5.4941.43e-01 4.4945.33e-02 21.28 2.74e-01  Movielens 3 Accuracy-coverage 1.5431.36e-02 1.2901.49e-02 1.0301.34e-02 3.343 1.07e-02 Accuracy-novelty 11.211.07e-01 9.2182.15e-01 9.1432.57e-01 36.10 7.62e-02 Accuracy-coverage-novelty 5.7709.50e-02 5.0863.23e-01 4.8335.46e-02 14.05 3.52e-01  Movielens 4 Accuracy-coverage 1.7631.15e-02 1.1801.13e-02 1.1233.87e-02 6.385 5.62e-02 Accuracy-novelty 13.901.66e-01 9.2711.11e-01 9.3321.76e-01 38.24 1.22e-02 Accuracy-coverage-novelty 6.0081.02e-01 5.3321.13e-01 4.2106.27e-02 18.68 3.25e-01  Netflix 1 Accuracy-coverage 1.8486.54e-02 1.5484.91e-02 1.1745.34e-02 2.877 7.49e-02 Accuracy-novelty 12.695.56e-03 10.344.72e-02 9.3751.99e-02 30.44 2.40e-02 Accuracy-coverage-novelty 6.9723.08e-02 5.5541.15e-02 4.3074.22e-02 10.41 2.97e-02  Netflix 2 Accuracy-coverage 1.6529.08e-02 1.3591.02e-02 1.1832.20e-02 6.914 5.29e-02 Accuracy-novelty 12.826.54e-02 10.481.49e-02 8.5766.76e-03 31.96 1.22e-02 Accuracy-coverage-novelty 7.9174.27e-02 6.5475.40e-02 4.2516.27e-02 12.10 6.57e-03  Netflix 3 Accuracy-coverage 1.7633.27e-02 1.4754.99e-02 1.1464.48e-02 5.082 3.62e-02 Accuracy-novelty 13.713.94e-03 9.6922.13e-02 8.4462.48e-02 29.65 8.97e-03 Accuracy-coverage-novelty 7.3304.14e-02 6.3682.16e-03 4.3022.49e-02 13.27 3.25e-01  Netflix 4 Accuracy-coverage 1.4404.36e-02 1.2521.13e-02 1.0183.87e-02 1.975 1.05e-02 Accuracy-novelty 12.633.34e-04 9.2711.87e-02 7.6591.92e-02 28.25 6.08e-02 Accuracy-coverage-novelty 6.3585.99e-02 5.6304.97e-02 4.4236.92e-02 11.92 3.25e-02To visually show the advantages of MOEA-EPG, Figures8–10 give the final recommendation results with the bestHV values regarding the accuracy-coverage, accuracy-novelty, and accuracy-coverage-novelty spaces, respectively. In Figure 8, it is observed that, when compared to User-based-CF and MF, MOEA-EPG is advantageous, as it can find better results in the accuracy and coverage. Moreover, for the data sets of Movielens 2, Movielens 4, and Netflix 2, MOEA-EPG has the advantages over MOEA-ProbS, PMOEA-ProbS, and PMOEA-CF. For the rest of data sets, MOEA-EPG performs competitively, as it can produce the best results among all the competitors. Only a few results of MOEA-ProbS, PMOEA-ProbS, and PMOEA-CF are better than those of MOEA-EPG in the coverage. However, this performance enhancement for coverage decreases a large proportion of accuracy. For Movielens 1, Movielens 3, and Netflix 1, the loss on their accuracy is significant. In Figure 9, it is also confirmed that the advantages of MOEA-EPG are particularly pronounced, as MOEA-EPG can always outperform the other algorithms to find good recommendation solutions for all the data sets, regarding both accuracy and novelty. In Figure 10, MOEA-EPG also performs much better than MOEA-ProbS, PMOEA-ProbS, and PMOEA-CF. This indicates that MOEA-EPG is able to produce superior solutions in terms of the accuracy, coverage, and novelty.Figure 8
Final recommendation results of comparison algorithms under the accuracy-coverage space for (a) Movielens 1, (b) Movielens 2, (c) Movielens 3, (d) Movielens 4, (e) Netflix 1, (f) Netflix 2, (g) Netflix 3, and (h) Netflix 4.
(a) (b) (c) (d) (e) (f) (g) (h)Figure 9
Final recommendation results of comparison algorithms under the accuracy-novelty space for (a) Movielens 1, (b) Movielens 2, (c) Movielens 3, (d) Movielens 4, (e) Netflix 1, (f) Netflix 2, (g) Netflix 3, and (h) Netflix 4.
(a) (b) (c) (d) (e) (f) (g) (h)Figure 10
Final recommendation results of comparison algorithms under the accuracy-coverage-novelty space for (a) Movielens 1, (b) Movielens 2, (c) Movielens 3, (d) Movielens 4, (e) Netflix 1, (f) Netflix 2, (g) Netflix 3, and (h) Netflix 4.
(a) (b) (c) (d) (e) (f) (g) (h)


### 4.6. Effectiveness of the Extreme Point Guided Method

In this section, the effectiveness of the extreme point guided method is studied. As introduced in Section3.2.1, three extreme points with respect to accuracy, coverage, and novelty will be used in the evolutionary process to guide the search processes. To further study the underlying rationality of our proposed method, MOEA-EPG is compared to its three variants, i.e., MOEA-EPG-I, MOEA-EPG-II, and MOEA-EPG-III. MOEA-EPG-I, MOEA-EPG-II, and MOEA-EPG-III are implemented, to remove the accuracy extreme point, the coverage extreme point, and the novelty extreme point from the original MOEA-EPG, respectively. In this experiment, we use Movielens data sets due to the limitation of paper.All the meanHV values and the standard deviation from 30 runs are recorded for performance comparisons in Tables 5 and 6 for four data test sets (Movielens 1, Movielens 2, Movielens 3, and Movielens 4), where the best result is highlighted in boldface. Based on the experimental results, MOEA-EPG can find better solutions than MOEA-EPG-I and MOEA-EPG-II in the accuracy-coverage space, and it outperforms MOEA-EPG-III in the accuracy-novelty space. In particular, the accuracy extreme point and the novelty extreme point have a significant impact on the performance of the algorithm. They facilitate the efficiency in evolutionary search with better directions, and therefore the application of extreme point guided strategy is effective.Table 5
HV comparison results of MOEA-EPG, MOEA-EPG-I, and MOEA-EPG-II in the accuracy-coverage space.
Data sets MOEA-EPG MOEA-EPG-I MOEA-EPG-II Movielens 1 3.203 7.74e-02 2.1606.98e-02 3.1681.44e-01 Movielens 2 4.677 3.46e-02 3.4094.96e-02 4.5361.01e-01 Movielens 3 3.343 1.07e-02 2.3417.24e-02 3.3309.94e-02 Movielens 4 6.385 5.62e-02 4.5037.43e-02 6.1581.05e-01Table 6
HV comparison results of MOEA-EPG and MOEA-EPG-III in the accuracy-novelty space.
Data sets MOEA-EPG MOEA-EPG-III Movielens 1 36.89 6.05e-02 28.253.71e-01 Movielens 2 35.43 7.83e-02 23.794.03e-01 Movielens 3 36.10 7.62e-02 27.204.77e-01 Movielens 4 38.24 1.22e-02 24.114.39e-01Figure11 shows the final recommendation results with the bestHV values regarding MOEA-EPG with three variants (MOEA-EPG-I, MOEA-EPG-II, and MOEA-EPG-III) on the accuracy-coverage and the accuracy-novelty spaces for all the data sets, respectively. Figure 11(a) illustrates that MOEA-EPG performance is superior to that of MOEA-EPG-I in terms of accuracy. It can be seen that the accuracy of the algorithm can be improved due to the introduction of the extreme accuracy point. Figure 11(b) shows that MOEA-EPG is better than MOEA-EPG-II on the coverage. Figure 11(c) confirms that MOEA-EPG gets a performance superior to that of MOEA-EPG-III regarding novelty. Similar to the accuracy extreme point, the novelty extreme point also has a great impact on the performance of the algorithm. These results further validate the effectiveness of the extreme point guided method on accelerating the convergence of our algorithm.Figure 11
Final solutions of MOEA-EPG and comparison algorithms under the accuracy-coverage space for (a) MOEA-EPG-I and (b) MOEA-EPG-II, and those under the accuracy-novelty space for (c) MOEA-EPG-III.
(a) (b) (c)


### 4.7. Impact of Parameters

In MOEA-EPG, the setting of parameterK(i.e., the similar ratio of users in (9)) may affect the performance of our algorithm. In this section, in order to study the impact of parameterK in MOEA-EPG, MOEA-EPG was run with differentK values (i.e., 0.3, 0.5, 0.7, 0.9), while the other parameters in MOEA-EPG are kept the same as listed in Table 3. In Table 7, all the meanHV results and the standard deviations over 30 runs are recorded for performance comparisons. The best result for each data set is highlighted in boldface.Table 7
HV comparison results under different settings of K to MOEA-EPG on the accuracy-coverage space.
Data sets K=0.3 K=0.5 K=0.7 K=0.9 Movielens 1 2.8616.05e-02 3.203 7.74e-02 3.0131.01e-01 2.9147.30e-02 Movielens 2 3.9443.06e-02 4.4384.51e-01 3.3344.03e-02 4.592 2.86e-02 Movielens 3 2.5971.35e-02 3.343 1.07e-01 2.8168.29e-02 2.3876.77e-02 Movielens 4 5.6593.46e-02 5.985 5.62e-02 5.4614.52e-02 5.7003.12e-02 Netflix 1 2.7628.49e-02 2.877 7.49e-02 2.4253.27e-02 1.9611.28e-02 Netflix 2 7.102 5.00e-02 6.9145.29e-02 6.4343.58e-02 6.3704.15e-02 Netflix 3 4.6192.66e-02 5.082 3.62e-02 4.4377.19e-02 3.6963.55e-02 Netflix 4 1.7914.82e-02 1.975 1.05e-02 1.5941.45e-02 1.2395.07e-02Figure12 further gives the final results with the bestHV values in data sets. From the comparison results, we observe that the setting of parameterK would affect the performance of MOEA-EPG. Moreover, theHV values of MOEA-EPG underK=0.5 are large in most data sets, whereas the performance of our algorithm becomes poor whenK takes other values. Therefore, in this paper, we select 0.5 as the similar ratio of users.Figure 12
Influence of similar ratio parameterK to MOEA-EPG under the accuracy-coverage space for (a) Movielens 1, (b) Movielens 2, (c) Movielens 3, (d) Movielens 4, (e) Netflix 1, (f) Netflix 2, (g) Netflix 3, and (h) Netflix 4.
(a) (b) (c) (d) (e) (f) (g) (h)


### 4.8. Computational Complexity Analysis of MOEA-EPG

The computational complexity of MOEA-EPG can be easily deduced from its pseudocode introduced in Algorithm1. Its computational complexity is mainly determined by the evolutionary search in lines (13)-(24). In this evolutionary loop, the functions Objective_Func(.) in line (15) and selection(.) in line (17) take a computational complexity withO(N·m2·n), whereN is the population size,m denotes the number users, andn represents the number of items. According to [24], the functions Fast_Non_Dominated_Sort(.) in line (16) and Update(.) in line (21) own a computational complexity with O(M·N2). Moreover, the functions Uniform_Crossover(.) and Mutation(.) in lines (18)-(19) have a computational complexity withO(N·m2·n). Therefore, the overall computational complexity of MOEA-EPG is approximatelyO(T·N·m2·n) asN·m2·n≫N2 generally, whereTis the predefined maximal generation number.Table8 further gives the computational complexities of all comparison recommendation algorithms. User-based-CF [39] and MF [46] have a computation complexity withO(m2·n) while our computational complexity analysis is given above withO(T·N·m2·n). Since MOEA-ProbS and PMOEA adopt the same NSGA-II framework except for the crossover operators, they share the same computational complexity (i.e.,O(T·N·m2·n)) with MOEA-EPG.Table 8
Computational complexities of all comparison recommendation algorithms.
Comparison algorithms Computational complexity User-based-CF O(m2⋅n) MF O(m2⋅n) PMOEA-ProbS O(T⋅N⋅m2⋅n) PMOEA-CF O(T⋅N⋅m2⋅n) MOEA-ProbS O(T⋅N⋅m2⋅n) MOEA-EPG O(T⋅N⋅m2⋅n)To show the actual running efficiency of all the MOEAs-based recommendation algorithms, Table9 records their average execution times over 30 independent trials. From the results in Table 9, it can be found that although they share the same computational complexity, the actual running times are different due to the running of different crossover operators and some extra strategies. For example, MOEA-ProbS shows the fast execution efficiency, as it adopts the original NSGA-II [24] on the recommendation system. Since MOEA-EPG has some extra processes, such as the calculation for the three extreme points and the selection of similar parents for crossover, its execution times are a little longer than that of MOEA-ProbS on all the data sets. It is noted that PMOEA-ProbS and PMOEA-CF consume the longest execution times, as they need to run the crossover operators multiple times.Table 9
Average execution times in seconds of all the MOEAs based recommendation algorithms over 30 independent trials.
Data sets MOEA-ProbS PMOEA-ProbS PMOEA-CF MOEA-EPG Movielens 1 2.584e+03 6.386e+03 5.080e+03 3.937e+03 Movielens 2 2.793e+03 7.859e+03 6.627e+03 4.532e+03 Movielens 3 2.630e+03 7.096e+03 6.163e+03 4.227e+03 Movielens 4 2.887e+03 7.663e+03 1.338e+04 4.963e+03 Netflix 1 2.718e+03 7.149e+03 6.018e+03 5.539e+03 Netflix 2 2.960e+03 7.542e+03 6.548e+03 5.707e+03 Netflix 3 2.964e+03 8.128e+03 7.633e+03 6.532e+03 Netflix 4 2.237e+03 5.843e+03 5.639e+03 5.431e+03


## 4.1. Experimental Data

In our experiments, two classical benchmark data sets, i.e., Movielens and Netflix, are used. The Movielens data set includes 943 users and 1682 movies, which can be downloaded from the website of GroupLens Research (http://www.grouplens.org/). The original ratings in this data are assigned values from 1 to 5. Here, a binary rating system is used by using “like” or “dislike”. An item is assigned to the binary rating “like” by a user when his original rating is larger than 3 [30]. Then, 80% of the data are randomly selected as the training data set with known information for recommendations, while the remaining data are used as the test data set. To make a fair comparison, similar to [30], the users in this data are divided into four clusters by using theK-means algorithm [47], each of which is used as the test data. The properties of these data sets are presented in Table 1 [23].Table 1
Properties of the Movielens data sets.
Data sets Users Items Sparsity Movielens 1 200 1682 1.39 × 1 0 - 2 Movielens 2 258 1682 5.17 × 1 0 - 2 Movielens 3 227 1682 2.38 × 1 0 - 2 Movielens 4 258 1682 6.89 × 1 0 - 2The Netflix data set was used for the Netflix prize, which can be downloaded from the contest website (http://www.netflixprize.com/). Here, a random subset of Netflix set is used, containing 155177 ratings of 1000 users on 3952 movies. The properties of these data sets are shown in Table 2.Table 2
Properties of the Netflix data sets.
Data sets Users Items Sparsity Netflix 1 191 3952 2.11 × 1 0 - 2 Netflix 2 250 3952 1.92 × 1 0 - 2 Netflix 3 375 3952 2.73 × 1 0 - 2 Netflix 4 184 3952 2.21 × 1 0 - 2


## 4.2. Performance Metrics

Here, the hypervolume (HV) metric [27] is adopted to evaluate the convergence and diversity of solutions, which is widely used for the evaluations of MOEAs [36, 37]. Let zr=(z1r,⋯,zmr)T be a reference point in the objective space that is dominated by all vectors in true PF. TheHV metric calculates the size of the objective space dominated by the solutions inS and bounded byzr, which is computed as follows:(16)HVS=VOL⋃x∈Sf1x,z1r×⋯×fmx,zmr,where VOL(·) denotes the Lebesgue measure. In this paper, the reference pointzr is set to (0, 0) and (0, 0, 0) for biobjective and three-objective problems, respectively. A largeHV indicates the solution set has a good quality. In this experiment, all the algorithms with the highestHV from 30 runs are selected for comparisons.Moreover, three performance metrics are used, i.e., precision, coverage, and novelty. Precision is the most important metric for evaluating RSs. For a given useru, its precision is defined as the ratio of relevant items, which are correctly recommended, as defined by(17)Pu=NRuL,where NRu is the number of common items in the recommendation list of useru and the test data set preferred by useru, andL is the length of recommendation list. The recommendation accuracy in this paper is measured by the mean precision of all the users.The coverage metric of RSs illustrates the ratio of distinct items in the recommendation list over all the available items. Generally, RSs with a low coverage may be ineffective to users, as they are not enough to make decisions. In this paper, the objective in (10) is used as a performance metric to measure the diversity of RSs.The novelty of RSs reflects how well RSs can recommend unknown items to users. Generally, RSs with a large novelty will extend user’s interests. In this paper, the objective in (12) is used as a performance metric for this indicator.


## 4.3. Experimental Settings of Comparison Algorithms

The related parameters in comparison algorithms are listed in Table3, and the length of recommendation listL is set to 10. To allow a fair comparison, the related parameters for each algorithm were set as suggested in the corresponding references [30, 33, 39, 46].Table 3
The related parameters in comparison algorithms.
Algorithms Parameters Settings User-based-CF L=10  MF L=10  MOEA-ProbS p c=0.8, pm=1/L, L=10, N=100, T=3000, Tr=30  PMOEA p n =5, pm=1/L, L=10, N=100,T =3000, Tr=30, n=20  MOEA-EPG p c =0.8, pm=1/L, L=10, N=100, T=3000, Tr=30, K=0.5In Table3,N is the population size, pc and pm are, respectively, the crossover probability and the mutation probability, pn is the number of parents used for crossover in PMOEA (PMOEA-ProbS and PMOEA-CF),n is the number of neighbors, andTr is the number of independent trials. Moreover, in MOEA-EPG, K means the ratio of the most similar users to the target users within a cluster. The comparisons of MOEA-EPG with these algorithms are comprehensive and effective in validating its performance.


## 4.4. Effectiveness of MOEA-EPG

To study the effectiveness of our MOEA-EPG, a three-objective model is used to show the experimental results of MOEA-EPG on all the eight data sets. The nondominated solutions with the highestHV value [27] are plotted as the final results for each data set. In Figure 6, the final solutions of MOEA-EPG are plotted for all the eight data sets on the objective space. As observed from Figure 6, there exists a tradeoff among the used three objectives, which forms a nondominated front. Each solution in the nondominated front is marked by the blue square. From these plots, we can observe that the quality and distribution of solutions are quite good.Figure 6
Final solutions of MOEA-EPG under the accuracy-coverage-novelty space for (a) Movielens 1, (b) Movielens 2, (c) Movielens 3, (d) Movielens 4, (e) Netflix 1, (f) Netflix 2, (g) Netflix 3, and (h) Netflix 4.
(a) (b) (c) (d) (e) (f) (g) (h)To further show the distributions ofHV results, Figure 7 gives the boxplots of differentHV values for eight data sets obtained by MOEA-EPG in the accuracy-coverage space under 30 runs. On each box diagram, the central mark is the median, while the upper and lower edges of the box mean the 25th and 75th percentiles, respectively. Obviously, the distribution ofHV values of MOEA-EPG is robust, which further confirms the effectiveness of our algorithm.Figure 7
The boxplots ofHV values for MOEA-EPG under the accuracy-coverage space for different data sets. 1: Movielens 1, 2: Movielens 2, 3: Movielens 3, 4: Movielens 4, 5: Netflix 1, 6: Netflix 2, 7: Netflix 3 and 8: Netflix 4.


## 4.5. Comparisons with Other Competitors

In this subsection, our algorithm is compared with five competitors on the classical Movielens and Netflix data sets. As User-based-CF and MF only obtain one optimal value in one run, they cannot be used as comparison algorithms usingHV. In our experiments, the performance comparisons are conducted under different objectives, i.e., the accuracy-coverage, the accuracy-novelty, and the accuracy-coverage-novelty spaces.Since the computation difficulties under different objectives are varied, the parameterT is set to 3000 for the accuracy-coverage and accuracy-novelty spaces and set to 6000 for the accuracy-coverage-novelty space, while the remaining parameters are set the same as listed in Table 3. All the meanHV values and the standard deviations are collected for performance comparisons in Table 4, where the best result is highlighted in boldface. From Table 4, it can be observed that MOEA-EPG shows the best performance among all the MOEAs-based recommendation algorithms, especially in the accuracy-novelty space and accuracy-coverage-novelty spaces.Table 4
HV comparison results of MOEA-EPG and other algorithms on all the objectives for eight data sets.
Data sets Test Instance MOEA-ProbS PMOEA-ProbS PMOEA-CF MOEA-EPG Movielens 1 Accuracy-coverage 1.4431.38e-02 1.5331.13e-02 1.3681.36e-02 3.202 7.74e-02 Accuracy-novelty 11.401.45e-01 9.6671.16e-01 9.2881.07e-01 36.89 6.05e-02 Accuracy-coverage-novelty 5.5041.06e-01 5.3191.13e-01 4.8189.50e-02 12.23 5.34e-01  Movielens 2 Accuracy-coverage 1.5311.03e-02 1.1921.83e-02 1.0851.68e-02 4.677 3.46e-02 Accuracy-novelty 10.961.12e-01 9.2881.23e-01 8.8191.34e-01 35.43 7.83e-02 Accuracy-coverage-novelty 6.0271.23e-01 5.4941.43e-01 4.4945.33e-02 21.28 2.74e-01  Movielens 3 Accuracy-coverage 1.5431.36e-02 1.2901.49e-02 1.0301.34e-02 3.343 1.07e-02 Accuracy-novelty 11.211.07e-01 9.2182.15e-01 9.1432.57e-01 36.10 7.62e-02 Accuracy-coverage-novelty 5.7709.50e-02 5.0863.23e-01 4.8335.46e-02 14.05 3.52e-01  Movielens 4 Accuracy-coverage 1.7631.15e-02 1.1801.13e-02 1.1233.87e-02 6.385 5.62e-02 Accuracy-novelty 13.901.66e-01 9.2711.11e-01 9.3321.76e-01 38.24 1.22e-02 Accuracy-coverage-novelty 6.0081.02e-01 5.3321.13e-01 4.2106.27e-02 18.68 3.25e-01  Netflix 1 Accuracy-coverage 1.8486.54e-02 1.5484.91e-02 1.1745.34e-02 2.877 7.49e-02 Accuracy-novelty 12.695.56e-03 10.344.72e-02 9.3751.99e-02 30.44 2.40e-02 Accuracy-coverage-novelty 6.9723.08e-02 5.5541.15e-02 4.3074.22e-02 10.41 2.97e-02  Netflix 2 Accuracy-coverage 1.6529.08e-02 1.3591.02e-02 1.1832.20e-02 6.914 5.29e-02 Accuracy-novelty 12.826.54e-02 10.481.49e-02 8.5766.76e-03 31.96 1.22e-02 Accuracy-coverage-novelty 7.9174.27e-02 6.5475.40e-02 4.2516.27e-02 12.10 6.57e-03  Netflix 3 Accuracy-coverage 1.7633.27e-02 1.4754.99e-02 1.1464.48e-02 5.082 3.62e-02 Accuracy-novelty 13.713.94e-03 9.6922.13e-02 8.4462.48e-02 29.65 8.97e-03 Accuracy-coverage-novelty 7.3304.14e-02 6.3682.16e-03 4.3022.49e-02 13.27 3.25e-01  Netflix 4 Accuracy-coverage 1.4404.36e-02 1.2521.13e-02 1.0183.87e-02 1.975 1.05e-02 Accuracy-novelty 12.633.34e-04 9.2711.87e-02 7.6591.92e-02 28.25 6.08e-02 Accuracy-coverage-novelty 6.3585.99e-02 5.6304.97e-02 4.4236.92e-02 11.92 3.25e-02To visually show the advantages of MOEA-EPG, Figures8–10 give the final recommendation results with the bestHV values regarding the accuracy-coverage, accuracy-novelty, and accuracy-coverage-novelty spaces, respectively. In Figure 8, it is observed that, when compared to User-based-CF and MF, MOEA-EPG is advantageous, as it can find better results in the accuracy and coverage. Moreover, for the data sets of Movielens 2, Movielens 4, and Netflix 2, MOEA-EPG has the advantages over MOEA-ProbS, PMOEA-ProbS, and PMOEA-CF. For the rest of data sets, MOEA-EPG performs competitively, as it can produce the best results among all the competitors. Only a few results of MOEA-ProbS, PMOEA-ProbS, and PMOEA-CF are better than those of MOEA-EPG in the coverage. However, this performance enhancement for coverage decreases a large proportion of accuracy. For Movielens 1, Movielens 3, and Netflix 1, the loss on their accuracy is significant. In Figure 9, it is also confirmed that the advantages of MOEA-EPG are particularly pronounced, as MOEA-EPG can always outperform the other algorithms to find good recommendation solutions for all the data sets, regarding both accuracy and novelty. In Figure 10, MOEA-EPG also performs much better than MOEA-ProbS, PMOEA-ProbS, and PMOEA-CF. This indicates that MOEA-EPG is able to produce superior solutions in terms of the accuracy, coverage, and novelty.Figure 8
Final recommendation results of comparison algorithms under the accuracy-coverage space for (a) Movielens 1, (b) Movielens 2, (c) Movielens 3, (d) Movielens 4, (e) Netflix 1, (f) Netflix 2, (g) Netflix 3, and (h) Netflix 4.
(a) (b) (c) (d) (e) (f) (g) (h)Figure 9
Final recommendation results of comparison algorithms under the accuracy-novelty space for (a) Movielens 1, (b) Movielens 2, (c) Movielens 3, (d) Movielens 4, (e) Netflix 1, (f) Netflix 2, (g) Netflix 3, and (h) Netflix 4.
(a) (b) (c) (d) (e) (f) (g) (h)Figure 10
Final recommendation results of comparison algorithms under the accuracy-coverage-novelty space for (a) Movielens 1, (b) Movielens 2, (c) Movielens 3, (d) Movielens 4, (e) Netflix 1, (f) Netflix 2, (g) Netflix 3, and (h) Netflix 4.
(a) (b) (c) (d) (e) (f) (g) (h)


## 4.6. Effectiveness of the Extreme Point Guided Method

In this section, the effectiveness of the extreme point guided method is studied. As introduced in Section3.2.1, three extreme points with respect to accuracy, coverage, and novelty will be used in the evolutionary process to guide the search processes. To further study the underlying rationality of our proposed method, MOEA-EPG is compared to its three variants, i.e., MOEA-EPG-I, MOEA-EPG-II, and MOEA-EPG-III. MOEA-EPG-I, MOEA-EPG-II, and MOEA-EPG-III are implemented, to remove the accuracy extreme point, the coverage extreme point, and the novelty extreme point from the original MOEA-EPG, respectively. In this experiment, we use Movielens data sets due to the limitation of paper.All the meanHV values and the standard deviation from 30 runs are recorded for performance comparisons in Tables 5 and 6 for four data test sets (Movielens 1, Movielens 2, Movielens 3, and Movielens 4), where the best result is highlighted in boldface. Based on the experimental results, MOEA-EPG can find better solutions than MOEA-EPG-I and MOEA-EPG-II in the accuracy-coverage space, and it outperforms MOEA-EPG-III in the accuracy-novelty space. In particular, the accuracy extreme point and the novelty extreme point have a significant impact on the performance of the algorithm. They facilitate the efficiency in evolutionary search with better directions, and therefore the application of extreme point guided strategy is effective.Table 5
HV comparison results of MOEA-EPG, MOEA-EPG-I, and MOEA-EPG-II in the accuracy-coverage space.
Data sets MOEA-EPG MOEA-EPG-I MOEA-EPG-II Movielens 1 3.203 7.74e-02 2.1606.98e-02 3.1681.44e-01 Movielens 2 4.677 3.46e-02 3.4094.96e-02 4.5361.01e-01 Movielens 3 3.343 1.07e-02 2.3417.24e-02 3.3309.94e-02 Movielens 4 6.385 5.62e-02 4.5037.43e-02 6.1581.05e-01Table 6
HV comparison results of MOEA-EPG and MOEA-EPG-III in the accuracy-novelty space.
Data sets MOEA-EPG MOEA-EPG-III Movielens 1 36.89 6.05e-02 28.253.71e-01 Movielens 2 35.43 7.83e-02 23.794.03e-01 Movielens 3 36.10 7.62e-02 27.204.77e-01 Movielens 4 38.24 1.22e-02 24.114.39e-01Figure11 shows the final recommendation results with the bestHV values regarding MOEA-EPG with three variants (MOEA-EPG-I, MOEA-EPG-II, and MOEA-EPG-III) on the accuracy-coverage and the accuracy-novelty spaces for all the data sets, respectively. Figure 11(a) illustrates that MOEA-EPG performance is superior to that of MOEA-EPG-I in terms of accuracy. It can be seen that the accuracy of the algorithm can be improved due to the introduction of the extreme accuracy point. Figure 11(b) shows that MOEA-EPG is better than MOEA-EPG-II on the coverage. Figure 11(c) confirms that MOEA-EPG gets a performance superior to that of MOEA-EPG-III regarding novelty. Similar to the accuracy extreme point, the novelty extreme point also has a great impact on the performance of the algorithm. These results further validate the effectiveness of the extreme point guided method on accelerating the convergence of our algorithm.Figure 11
Final solutions of MOEA-EPG and comparison algorithms under the accuracy-coverage space for (a) MOEA-EPG-I and (b) MOEA-EPG-II, and those under the accuracy-novelty space for (c) MOEA-EPG-III.
(a) (b) (c)


## 4.7. Impact of Parameters

In MOEA-EPG, the setting of parameterK(i.e., the similar ratio of users in (9)) may affect the performance of our algorithm. In this section, in order to study the impact of parameterK in MOEA-EPG, MOEA-EPG was run with differentK values (i.e., 0.3, 0.5, 0.7, 0.9), while the other parameters in MOEA-EPG are kept the same as listed in Table 3. In Table 7, all the meanHV results and the standard deviations over 30 runs are recorded for performance comparisons. The best result for each data set is highlighted in boldface.Table 7
HV comparison results under different settings of K to MOEA-EPG on the accuracy-coverage space.
Data sets K=0.3 K=0.5 K=0.7 K=0.9 Movielens 1 2.8616.05e-02 3.203 7.74e-02 3.0131.01e-01 2.9147.30e-02 Movielens 2 3.9443.06e-02 4.4384.51e-01 3.3344.03e-02 4.592 2.86e-02 Movielens 3 2.5971.35e-02 3.343 1.07e-01 2.8168.29e-02 2.3876.77e-02 Movielens 4 5.6593.46e-02 5.985 5.62e-02 5.4614.52e-02 5.7003.12e-02 Netflix 1 2.7628.49e-02 2.877 7.49e-02 2.4253.27e-02 1.9611.28e-02 Netflix 2 7.102 5.00e-02 6.9145.29e-02 6.4343.58e-02 6.3704.15e-02 Netflix 3 4.6192.66e-02 5.082 3.62e-02 4.4377.19e-02 3.6963.55e-02 Netflix 4 1.7914.82e-02 1.975 1.05e-02 1.5941.45e-02 1.2395.07e-02Figure12 further gives the final results with the bestHV values in data sets. From the comparison results, we observe that the setting of parameterK would affect the performance of MOEA-EPG. Moreover, theHV values of MOEA-EPG underK=0.5 are large in most data sets, whereas the performance of our algorithm becomes poor whenK takes other values. Therefore, in this paper, we select 0.5 as the similar ratio of users.Figure 12
Influence of similar ratio parameterK to MOEA-EPG under the accuracy-coverage space for (a) Movielens 1, (b) Movielens 2, (c) Movielens 3, (d) Movielens 4, (e) Netflix 1, (f) Netflix 2, (g) Netflix 3, and (h) Netflix 4.
(a) (b) (c) (d) (e) (f) (g) (h)


## 4.8. Computational Complexity Analysis of MOEA-EPG

The computational complexity of MOEA-EPG can be easily deduced from its pseudocode introduced in Algorithm1. Its computational complexity is mainly determined by the evolutionary search in lines (13)-(24). In this evolutionary loop, the functions Objective_Func(.) in line (15) and selection(.) in line (17) take a computational complexity withO(N·m2·n), whereN is the population size,m denotes the number users, andn represents the number of items. According to [24], the functions Fast_Non_Dominated_Sort(.) in line (16) and Update(.) in line (21) own a computational complexity with O(M·N2). Moreover, the functions Uniform_Crossover(.) and Mutation(.) in lines (18)-(19) have a computational complexity withO(N·m2·n). Therefore, the overall computational complexity of MOEA-EPG is approximatelyO(T·N·m2·n) asN·m2·n≫N2 generally, whereTis the predefined maximal generation number.Table8 further gives the computational complexities of all comparison recommendation algorithms. User-based-CF [39] and MF [46] have a computation complexity withO(m2·n) while our computational complexity analysis is given above withO(T·N·m2·n). Since MOEA-ProbS and PMOEA adopt the same NSGA-II framework except for the crossover operators, they share the same computational complexity (i.e.,O(T·N·m2·n)) with MOEA-EPG.Table 8
Computational complexities of all comparison recommendation algorithms.
Comparison algorithms Computational complexity User-based-CF O(m2⋅n) MF O(m2⋅n) PMOEA-ProbS O(T⋅N⋅m2⋅n) PMOEA-CF O(T⋅N⋅m2⋅n) MOEA-ProbS O(T⋅N⋅m2⋅n) MOEA-EPG O(T⋅N⋅m2⋅n)To show the actual running efficiency of all the MOEAs-based recommendation algorithms, Table9 records their average execution times over 30 independent trials. From the results in Table 9, it can be found that although they share the same computational complexity, the actual running times are different due to the running of different crossover operators and some extra strategies. For example, MOEA-ProbS shows the fast execution efficiency, as it adopts the original NSGA-II [24] on the recommendation system. Since MOEA-EPG has some extra processes, such as the calculation for the three extreme points and the selection of similar parents for crossover, its execution times are a little longer than that of MOEA-ProbS on all the data sets. It is noted that PMOEA-ProbS and PMOEA-CF consume the longest execution times, as they need to run the crossover operators multiple times.Table 9
Average execution times in seconds of all the MOEAs based recommendation algorithms over 30 independent trials.
Data sets MOEA-ProbS PMOEA-ProbS PMOEA-CF MOEA-EPG Movielens 1 2.584e+03 6.386e+03 5.080e+03 3.937e+03 Movielens 2 2.793e+03 7.859e+03 6.627e+03 4.532e+03 Movielens 3 2.630e+03 7.096e+03 6.163e+03 4.227e+03 Movielens 4 2.887e+03 7.663e+03 1.338e+04 4.963e+03 Netflix 1 2.718e+03 7.149e+03 6.018e+03 5.539e+03 Netflix 2 2.960e+03 7.542e+03 6.548e+03 5.707e+03 Netflix 3 2.964e+03 8.128e+03 7.633e+03 6.532e+03 Netflix 4 2.237e+03 5.843e+03 5.639e+03 5.431e+03


## 5. Conclusions

In this paper, we presented a multiobjective personalized recommendation algorithm, MOEA-EPG, based on extreme point guided evolutionary computation. In this algorithm, we modeled the personalized recommendation as an MOP with the three conflicting objectives, i.e., accuracy, diversity, and novelty. The accuracy of recommendations considers whether the predicted ratings are similar to the true ones of users, and the diversity reflects the coverage on recommendation, while the novelty evaluates the capability of RSs to recommend unknown items to users. In MOEA-EPG, three extreme points on accuracy, diversity, and novelty were incorporated to guide its evolutionary search toward the PF, and a novel crossover operator was designed to better satisfy the demands of users. The experimental results demonstrated the superior performance of the proposed MOEA-EPG over two state-of-the-art recommendations (i.e., User-based-CF [39] and MF [46]) and two competitive MOEAs for RSs (i.e., MOEA-ProbS [30] and PMOEA [33]), in terms of the accuracy, diversity, and novelty. Moreover, the effectiveness of the extreme point guided method was also validated to accelerate the convergence speed toward the PF, and the sensitivity analysis on parameters was conducted to have a robust performance for MOEA-EPG.Our future work will focus on the performance metrics for the recommendation algorithms and further study other nature-inspired optimization algorithms (e.g., particle swarm optimization and ant optimization algorithms) for RSs.



---

*Source: 1716352-2018-11-12.xml*