1 Introduction

With the quick improvement of science and innovation, the blast of information has become progressively escalated [1]. However, in this information explosion era, users often encountered difficulties in finding the desired content due to the great volume of data [2]. Recommender systems (RSs) have proved to be an efficient tool to cope with the problem [3]. The main idea of RSs is to establish a model to automatically recommend the proper items to users based on the historical behavior and preference information [4]. RSs can assist users in decision making including movies, books, web search, tourism, and so on [5]. The existing RSs can be arranged into a few classes: hybrid recommendation, knowledge-based recommendation, collaborative filtering recommendation, and content-based recommendation [6].

Normally, the major aim of RSs is to satisfy the user by the best choice of recommendations, which can be interpreted as the maximum of accuracy [7]. Nonetheless, being accurate is not enough to guarantee the desired recommendation for users [8]. The other metric of performance, diversity, ought to likewise be taken into consideration to satisfy the multiple demands of users [9]. In practical application, a diversity-accuracy dilemma has been found, where the recommendation of manifold items contributes to a reduction of exactness for users and vice versa [10]. To accomplish an appropriate harmony among accuracy and diversity, we adopt a multi-objective recommendation model to optimize the conflicting objectives of diversity and accuracy. Thus, naturally, the problem of personalized recommendation is modeled as a multi-objective problem (MOP) [11].

There have been a lot of researches on recommendation based on multi-objective optimization. Ribeiro et al. exploited the Pareto-efficiency concept and select Pareto-efficient items to optimize the recommender systems by the means of weighted combination [12]. A model of personalized recommendation was proposed by Zuo et al., which optimizes the accuracy and coverage of the recommendation lists [13]. Agarwal et al. used a constrained optimization framework to naturally incorporate various application-driven requirements [14]. Rodriguez et al. framed an approach on optimizing non-smooth rank metrics for information retrieval.

To strike a better balance between accuracy and diversity, we furthered the research on the above recommendation techniques. In this paper, a novel multi-objective recommendation algorithm is proposed to generate diverse recommendations while reserving the competent accuracy of recommendation accuracy. The algorithm adopts bipartite network projection (Probs) as a recommendation technique to estimate accuracy, which is basic yet effective. Accordingly, the algorithm utilizes Coverage to measure the ability of diversity. Moreover, by encoding recommendations to different users in one individual, it is easy to obtain multiple recommendations for multiple users in one run. Via the technique of clustering, the numerous users can be separated into distinctive clusters to decrease the cost of computation. The main contributions can be given as follows: (1)A novel variation of Probs is implemented to make ratings. (2)A heuristic algorithm is adopted to initialize the population. (3)A new strategy of crossover based on the similar genes of parents is used to generate a child.

2 Technological Background

In this section, the definition of recommendation problem and multi-objective optimization is given, respectively, and then the ProbS method is reviewed in detail.

2.1 Recommendation problem

In general, we can formulate the problem of recommendation as follows. Assuming that Users includes the whole users of a system, and Items includes all the items to be recommended. Thus, a rating matrix R can be utilized to estimate the preference of users to items. If user i ∈ Users has priority to the item j ∈ items, the value of R(i, j) can be equal to 1, and R(i, j) is regularly a real number or non-negative integer inside a specific reach [15]. It is obvious that only a handful of items are evaluated by a handful of users. Therefore, the rating matrix R turns into a sparse matrix. The process of recommendation can be presented briefly. Firstly, on the basis of matrix R, the suggested algorithm predicts the unknown ratings in R. Consequently, one or a set of items will be provided for the user, this can be expressed as:

\( ∀ i∈ Users, j = arg max R(i, j), j ∈Items \) (1)

2.2 Multi-objective optimization

The multi-objective optimization can be mathematically defined as:

\( min F(x)={({f_{1}}(x),{f_{2}}(x),…,{f_{m}}(x))^{T}} \) (2)

where \( x=[{x_{1}},{x_{2}},…,{x_{d}}]∈Ω \) is a decision vector, and \( F(x) \) is an objective function of \( m \) dimensions. In view of a pair decision vectors \( {x_{A}}∈Ω \) and \( {x_{B}}∈Ω \) , if the equation is satisfied, it is said that \( {x_{B}} \) is dominated by \( {x_{A}} \) , which can be given in the form of \( {x_{A}}≻{x_{B}} \) . Consisting of decision variables, the pareto set refers to the solutions which are not dominated by any other solutions [16].

2.3 ProbS

By the means of ProbS, the basic element in rating matrix R(i, j) is equal to 1 or 0, representing that user i \( ∈ \) Users selected or not selected the item j \( ∈ \) items. Although it may sacrifice some information, the adoption of explicit ratings can obtain this form with ease [17]. The overall procedure of Probs algorithm can be separated into three steps. The first one is the contribution of user-item bipartite network, which is determined by the relationship of users and items [18]. The second one is distribution of the initial resource which are allocated to each item and then is distributed to adjacent users. The last step is that apportion users’ resources back to the neighboring items. Ultimately, a matrix of nominalized transition can be formulated. The specific computation of allocation can be expressed as follows:

\( {w_{mn}}=\frac{1}{{k_{n}}}\sum _{i=1}^{M} \frac{{r_{im}}{γ_{in}}}{{k_{i}}} \) (3)

where \( {w_{mn}} \) represents the fraction of the transition of initial resource from n to m, M is the summation of the users, and \( {k_{n}} \) represents the degree of node n. The ratings of items can be evaluated as follows:

\( f_{m}^{ \prime }=\sum _{n=1}^{N} {w_{mn}}{f_{n}} \) (4)

where the number of items is amount to N.

3 Methodology

In order to keep a balance between accuracy and diversity of the recommendation problem, a state-of-the-art algorithm is proposed, which is named MOEA-NProbS. In this part, the MOEA-NProbS algorithm will be interpreted in detail, including a new strategy to initialize the population, a novel algorithm for recommendation and method to make crossover.

3.1 A novel ProbS (NProbS)

Although Probs algorithm is confirmed to be effective by Zou, there are two aspects to be improved. Firstly, the neglection of items below score 3 sacrifice some information. Secondly, the average allocation of resources narrows the gap between likes and dislikes. As a consequence, NProbS is proposed to handle the above problems. The specific steps of NProbS are as follows: (1) Construct the user-item bipartite network. If the user A evaluated the item, then set the resource of item as 1, other items as 0. (2) Distribute the initial resources of items to entire users depending on the similarity of priority. In the event of high similarity of preference between users, allocate more weight. Generally, the absolute value of the score difference for the specific items can be divided into 5 conditions, that is \( \lbrace 0,1,2,3,4\rbrace \) . The lower score represents the higher similarity of preference. Therefore, the weights to be distributed are \( \lbrace 5x,4x,3x,2x,x\rbrace \) respectively ( \( x \) is an unknown number). (3) Distribute users’ resources to items. Allocate different weights to items depending on the ratings that users made. The ratings have five possibilities \( \lbrace 1,2,3,4,5\rbrace \) . As a result, the weights belong to them are \( \lbrace x,2x,3x,4x,5x\rbrace \) .

The Fig. 1 elucidates the process of resource distribution in a simple bipartite network. The circles represent users and squares represent items. The target user is marked by red color.

Fig. 1. Elucidation of NProbS

3.2 A heuristic method to initialize population based on selection

As a variation of optimization algorithms, heuristic method can be combined with genetic algorithm to reduce time for searching. Moreover, when it comes to select items according to ratings, users are more likely to choose the item with high score. As a result, we proposed a heuristic method to of initialization. It can be illustrated as follows: (1) Assuming that the individual size is \( |U|×L \) ( \( |U| \) represent the total number of users and \( L \) represent the length of recommendation list). Use NProbs algorithm to obtain the rating matrix \( {R_{1}} \) for prediction, which is as large as \( |U|×L \) . (2) For each user, select the top- \( L \) items as the recommendation list according to the row predictive vector in \( {R_{1}} \) . Then combine the top- \( L \) items to generate an individual of the initial population to guide the evolution of the population. (3) The rest initial individuals can be obtained by the following mean: Firstly, normalize \( {R_{1}} \) to get \( {R_{2}} \) . Then for the user \( i \) , select the item \( j \) at random and generate a random number between 0 and 1. If number < \( {R_{2}} \) ( \( i \) , \( j \) ), then add the item into the recommendation list of user \( i \) , vice versa. (4) Repeat the above process L times and get the recommendation list of user \( i \) . Subsequently, repeat \( |U| \) times to get the initial individuals. Finally, repeat the times of population size to get the initial population.

3.3 A crossover strategy based on the conservation of parent similar gens

To further the diversity of recommendation results, a novel crossover strategy is proposed. For the beginning, utilize the binary tournament to select an individual based on dominated sorting and crowing degree and repeat this procedure 3 times to get Patent1, Parent2 and Parent3. For the user \( i \) , recommendation lists rem_list1, rem_list2, rem_list3 can be obtained to compose rem_list. Record the appearance of different items. If the appearance time is greater than 1, mark the item lists as list1. If the appearance time is equal to 1, mark the item lists as list2. If the items quantity M in list1 is larger than L, preserve L items to the child by random selection. If M \( ≤ \) L, retain all the items in list1 to the child and randomly select the rest L-M items from list2. Repeat the process to gain the Child and new child population.

3.4 Framework of the proposed MOEA-NProbS

As shown in the following Fig. 2, the proposed recommendation algorithm has a similar framework to NSGA-II. Firstly, classify users U into k clusters. Then for each cluster, execute the following steps: utilize NProbS to obtain predictive rating matrix; initialize the population and calculate the target function; execute fast non-dominated sorting and calculate crowding distance. Afterward, iterate the population by following steps until it meets the maximum. Select F2, F2, F3 from parent P by the binary tournament. Generate offspring based on the proposed crossover strategy. Execute fast non-dominated sorting, calculate crowding distance and obtain new parent generation by elitist strategy. At last, select the first frontier individuals.

Fig. 2. Framework of the Proposed MOEA-NProbs

4 Conclusion

In this paper, a novel multi-objective model is proposed to optimize accuracy and diversity at the same time. NProbS is implemented to make ratings, which is a variation of the Probs algorithm. Moreover, a heuristic algorithm is adopted to accelerate the initialization of the population. The proposed MOEA-NProbS utilize a new strategy of crossover based on the similar genes of parents. From theoretical analysis, MOEA-NProbS is effective to improve the diversity and accuracy of the recommendation. In addition, for multiple users, the algorithm can generate multiple recommendations in only one run.

However, the MOEA-NProbS need to be verified by experiments and compared with prevalent MOEA algorithms. Our future work will confirm the validity of MOEA-NProbs based on the data set MovieLens. Moreover, to validate the advantage of MOEA-NProbs, it will be compared with well-known techniques, including CF and MF.