Optimization design based on hierarchic genetic algorithm and particles swarm algorithm

Abstract

For a lot of data, it is time-consuming and unpractical to get the best combination by manual tests. The genetic algorithm can make up for this shortcoming through the optimization of parameters. In this paper, the advantages of traditional similarity algorithm is studied, the time model and the trust model for further filtering are introduced, and the parameters with the combination of hierarchical genetic algorithm and particle swarm algorithm are optimized. In the collaborative filtering algorithm, genetic algorithm is improved with hierarchical algorithm, and the user model and the algorithm process are optimized using the fitness function of selection, crossover, and variation, along with the optimization of recommendation result set. In the algorithm, the global optimal parameters can be calculated with the optimization of the obtained initial data, and the accuracy of the similarity calculation can also be improved. This study does the recommendation and comparison experiment in the MovieLens Dataset, and the results show that, on the basis of obtaining the nearest neighbor user group, the mixing use of the hierarchical genetic algorithm and the particle swarm algorithm can make more improvement in the recommendation quality than that of the traditional similarity algorithm.

Introduction

The resource recommendation algorithm ² is optimized by combining the user interest recommendation algorithm to construct the user interest model and by taking advantage of the collaborative filtering algorithm to recommend the user’s potential interests. ³ The key point is to excavate the theme of user’s interest and make a multi-level re-construction on the user interest model, which can improve the user recommendation quality. ⁴ The recommendation algorithm is constructed and improved by introducing the concept of user similarity and defining the composition and calculation method of attribute similarity. ⁵

The resource recommendation algorithm ² is a process to build the user interest model and to recommend potential interests of users through taking advantage of the collaborative filtering algorithm. ³ Its main task is to explore the themes of users’ interests and make a multi-level re-construction of users’ interest model so as to improve recommendation quality. ⁴ The recommendation algorithm is designed using the concept of user similarity, and the improved recommendation algorithm is implemented by defining composition and calculation of attribute similarity. ⁵

For a lot of data, it is time-consuming and unpractical to get the best combination by manual tests. However, the genetic algorithm (GA) just makes up for this shortcoming and greatly optimizes the combination of parameters. In the collaborative filtering algorithm, by using the improved hierarchical algorithm and the fitness function selection, crossover, and mutation, etc., the GA improves the user model and the algorithm process and optimizes the recommendation result set. ⁶

GA has realized the function of global search and achieved the optimal solution in the light of Darwin’s natural survival law – “survival of the fittest” and genetic mechanism.^7,8 The selection, cross, mutation and global search of the genetic particle swarm optimization (PSO) algorithm can significantly improve the efficiency and the quality of automatic generation and sequencing of data.^9,10 Based on the fitness function and the hierarchical GA, the GA improves the data generation efficiency by making up for the shortage of slow and local convergence. ¹¹

In this paper, user similarity can be calculated using the similarity algorithm with the combination of time effect and trust degree, and the nearest neighbor is taken as the initial data of the GA. The hierarchical GA searches and optimizes the data in a way to improve recommendation accuracy of the similarity algorithm.^12,13 PSO transmits the global optimal solution to other particles. This one-way transmission process ensures the optimal move of all particles so as to solve the problems of slow convergence and moving direction deviating from the optimal solution of the hierarchical GA. ¹⁴

Similarity algorithm

The idea of algorithmic optimization

This paper is based on the similarity algorithm and combines the time effect and the trust degree. Its main ideas are as follows: the first is to get the user’s nearest neighbor of the present moment according to the user’s static data and dynamic data; then, in terms of the timeliness of the user’s interest, the corresponding weights will be given to the neighbor users of each time period, and next, the nearest neighbor will be obtained through the weighted summation on each period; finally, based on the user’s social relations, the trust degree between users will be taken as the additional similar user group and be attached to the basic nearest neighbor to obtain the target user’s nearest neighbor set of the present moment. ¹⁵ This paper will apply the timeliness-based user interest model, whose ground is the ideas of sequential updating, and the nearest neighbor search model, which is based on the social network trust and uses the ideas of mutual familiarity, obtaining the user’s score matrix and combining the two models to generate the user’s recommendation set.^16,17

User similarity based on time weight

Although user’s hobbies have the trait of timeliness, their deviation law is similar with the forgetting law. Thus, the “Ebbinghaus Forgetting Curve” can be applied to reflect the user’s interest change. The time forgetting function is

$$\text{f}({\text{x}}_i)=\frac{1}{1+e^{i-j}}=\frac{1}{1+e^{\frac{{\mathrm{X}}_i-{\mathrm{X}}_j}{K}}}$$

(1)

In this formula, $0\le i\le j,{\text{X}}_i={\text{X}}_0+i\text{K}$ ； X _i represents the recommendation set that is got in ith time, and X _j represents the current moment.

Based on the time forgetting function, the time function weight is

$$\text{g}({\mathrm{X}}_i)=1-f({\mathrm{X}}_i)$$

(2)

ΔPSN _i is the stage similarity of the target user p and other users in the time period [X_i−1, X _i ], according to the Pearson correlation coefficient.

$$PSN(p,q)=\frac{{\displaystyle {\sum }_{i\in Ypq}(Zpi-\overline{Zp})(Zqi-\overline{Zq})}}{\sqrt{{\displaystyle {\sum }_{i\in Ypq}{(Zpi-\overline{Zp})}^2\sqrt{{\displaystyle {\sum }_{i\in Ypq}(Zqi-\overline{Zq})}}2}}}$$

(3)

In this formula, $Ypq$ represents the item collection that is jointly scored by the user p and the user q. $\overline{Zp}$ represents the average score of the user p to all the items in $Ypq$ . $\overline{Z\text{q}}$ represents the average score of the user q to all the items in $Ypq$ . Then, the similarity PSN _j of the user p and the user in ${\text{Z}}_p^j$ at the moment X _j can be represented as

$$\text{PSN}j=\frac{1}{Cj}g({\mathrm{X}}_i)\times \Delta {\text{PSN}}_i$$

(4)

Based on the comparison of the size of $\text{PSN}j$ , the method of limiting threshold can be applied to get the nearest neighbor set of the user u at the moment X _j .

User similarity based on trust degree

The user trust has a significant influence on the effect of the personalized recommendation. According to the user’s trust relationship diagram, if U and V have a direct relationship, then U and V will have a direct trust relationship; if V has a direct relationship toward W, then U and W will have an indirect trust relationship. The trust degree between users is measured by the direct and indirect relationship between them.

The direct trust relationship normalized is represented by Trust whose value is [0,1]. E represents user direct trust set, and the direct trust relationship formula obtained by $\text{U}=\left\{{\text{u}}_1,{\text{u}}_2,\dots {\text{u}}_{\text{n}}\right\}$ is given in Formula (5).

$$\text{T}\mathrm{r}\text{ust}(\mathrm{u},\mathrm{v})=\frac{\mathrm{T}(\mathrm{u},\mathrm{v})}{{\sum }_{{\mathrm{u}}^{\prime }\in \mathrm{F}(\mathrm{u})}\mathrm{T}(\mathrm{u},{\mathrm{u}}^{\prime })}$$

(5)

In this formula, F(u)= {u′|<u,u′> ∈ E ∧ u,u′ ∈ U}, Trust(u,v) satisfies ${\sum }_{\text{u}\in \mathrm{f}(\mathrm{u})}\mathrm{Trust}(\mathrm{u},\mathrm{v})=1$ . The indirect trust relationship is represented by the path from u to v, then the indirect trust degree of u toward v is T(u,v) = (Trust(u,u1) + Trust(u1,u2) + … + Trust(un,v))/(n + 1).

GA-PSO algorithm

On the basis of the situation and context information, the recommendation effect can be fully improved by the integration of the user time effect and trust degree into the construction of the interest model and the usage of the naive Bayesian method and clustering characteristics to improve the calculation process of GA. ¹¹ This paper applies the improved GA-PSO algorithm, using the PSO to optimize the basic data and unify the population evolution direction, combining the improved hierarchical GA for independent evolution, crossover, mutation, etc., and finally obtaining the improved recommended data.

Hierarchic genetic algorithm model

The hierarchical GA ensures that different sub-populations can conduct the parallel genetic independently and generates a multifarious population by reciprocal chiasma among the excellent individuals from the multiple sub-populations. Assuming that the number of the sub-populations in the first layer is K₁, and each sub-population of the second layer has K₂ sub-populations, then the number of the sub-populations in the second layer will be K₁ × K₂. By that analogy, the number of the sub-populations in the nth layer will be ${\prod }_{i=1}^{\text{n}}{K}_i$ . According to the concepts of the hierarchical GA, let ${\text{P0}}_{ij},{\text{PS}}_{ij},{\text{IS}}_{ij},{\text{Fπ}}_{ij},{\text{S0}}_{ij},{\text{C0}}_{ij}\text{\hspace{0.17em}\hspace{0.17em}and\hspace{0.17em}\hspace{0.17em}}{\text{M0}}_{ij}$ , respectively, represent the initial population, population size, coding length, and fitness value of the jth module in the ith layer, and selection, crossover, and mutation. Then, the hierarchical GA can be described as

$${\text{GA}}_{ij}=({\text{P0}}_{ij},{\text{PS}}_{ij},{\text{IS}}_{ij},{\text{Fπ}}_{ij},{\text{S0}}_{ij},{\text{C0}}_{ij},{\text{M0}}_{ij})$$

(6)

The consideration of the influence between the upper and lower layers helps to get the schematic diagram of the hierarchical GA, as shown in Figure 1.

Figure 1.

Schematic diagram of hierarchical genetic algorithm.

In Figure 1, the dotted line represents the control relationship, while full line represents the information feedback. The first layer controls the heritage algorithm of the sub-populations of other layers, and other layers respectively include a series of modules. From this diagram, it can be seen that the solving of the independent heritage algorithm is not only influenced by its upper layer but also by other layers.

PSO algorithm principle

The basic ideas of PSO is that during the particle swarm’s independent flight in the s-dimensional space, the particle swarm will continuously search for the information of its own optimal point and the maximum fight fitness value of other particles in the space and then adjust its own change according to this historical information. The position of the nth particle is represented as $\alpha \text{n}=(\alpha n1,\alpha n2,\cdots ,\alpha ns)$ ; the velocity of the nth particle as $\nu \text{n}=(\nu n1,\nu n2,\cdots ,\nu ns)$ , n = 1, 2, …, m; the movement maximum value of the nth particle as $s\text{n}=(sn1,sn2,\cdots ,sns)$ ; and the movement maximum value of all the particles in the particle warm as $s\text{g}=(sg1,sg2,\cdots ,sgs)$ . Then, the updated formula of particle position and velocity is

$${\nu }_{\text{nd}}^{t+1}=\omega {\nu }_{\mathrm{n}\mathrm{d}}^t+c1\epsilon (s_{\mathrm{n}\mathrm{d}}^t-{\alpha }_{\mathrm{n}\mathrm{d}}^t)+c1\eta (s_{\mathrm{g}\mathrm{d}}^t-{\alpha }_{\mathrm{n}\mathrm{d}}^t)$$

(7)

$${\alpha }_{\text{nd}}^{t+1}={\alpha }_{\text{nd}}^t+{\nu }_{\text{nd}}^{t+1}$$

(8)

In this formula, ω represents inertia weight; c1 and c2 represent learning factor; ε and η represent random numbers in [0, 1].^18,19

Implementation of similarity calculation model

The similarity algorithm combines the time effect and the trust degree to get the user’s nearest neighbor. As the initial particle swarm population, the PSO algorithm encodes the feasible decomposition and velocity of the initial population, updates, and iterates at any time. The GA is nested in the outer layer of the PSO algorithm and manipulates the population through the steps of selection, crossover, and mutation, etc., which can generate the optimal values and data diversification. The algorithm flow diagram of the resource recommendation model is shown in Figure 2.

Figure 2.

Algorithm flow diagram of resource recommendation model.

As represented in Figure 2, the data obtained based on the similarity algorithm are taken as the initial population. First, the initial population is stratified, the genetic algebraic variable t being 0 and the initial value of the circulation number m being 3. Then, the fitness function of the individuals in mth layer is calculated, and the results are regarded as the basis for individual judgment and choice in the whole population. If the given fitness value is satisfied, the resource recommendation data will be output; if not, selection, mutation, and crossover will be performed in this layer to get new category. The fitness function will be used to make new judgments until the conditions are satisfied.

Experiment and result analysis

Experiment objective and experiment environment

The purpose of this experiment is to validate the resource recommendation effect. Compared with the basic similarity algorithm, using the similarity algorithm of blending, the GA and the PSO can get a better recommendation effect. The experiment compares the recommendation effects obtained respectively by the algorithm of this paper and by the basic similarity algorithm, adopting the Windows Server environment and writing the program in the Java programming language. The experimental data adopt the MovieLens Dataset (including 10,000 scores by nearly 943 independent users on 1682 movies), among which 80% of the user’s rating data is used for the calculation data, and 20% is used as the verification data.

Experiment result and its analysis

The “precision rate” of the recommendation system can adequately assess the algorithm quality. However, Shardanand et al. point out that the “error rate” has a more accurate measurement effect.¹⁹ Through the random selection of 20 users from the Dataset, this experiment uses the hybrid similarity algorithm and the basic similarity algorithm to make recommendations, calculates the precision and recall rates of the final results, and compares the rates. The comparison results are shown in Figures 3 and 4. According to the precision formula

$$\mathrm{precision}=\mathrm{t}\mathrm{p}/(\mathrm{t}\mathrm{p}+\mathrm{f}\mathrm{p})$$

(9)

Figure 3.

Precision rate of recommendation result.

Figure 4.

Recall rate of recommendation result.

The recall formula is represented as

$$\mathrm{recall}=\mathrm{t}\mathrm{p}/(\mathrm{t}\mathrm{p}+\mathrm{fn})$$

(10)where tp and fp represent the number of items that are properly recommended and the number of items that are falsely recommended, respectively. Fn represents the number of items that should be recommended but are not included in the recommendation list. The higher the precision and recall rates are, the more accurate the results of the similarity calculation are.

The comparison between the precision rate and the recall rate can show that the hybrid similarity algorithm used for recommendation is more accurate than the result of using the basic similarity algorithm, and the recall rate of the former is lower than the latter.

Time complexity analysis

According to the text results, the data optimization made by different similarity algorithm is calculated, and the time of outputting result sets is regarded as the evaluation index of time complexity without considering the precision and recall rates of the recommendation result. U₁ and U₂ represent the combination collaborative filtering and the basic collaborative filtering, respectively, and their comparison result is shown in Table 1.

Table 1.

Comparison of time complexity.

Similarity algorithm	Population size (user rating)	Maximum number of iteration	Running time
U1	100	500	2.1232
U2	100	400	3.7623

The result indicates that in terms of running time, the combination collaborative filtering algorithm is less time-consuming than the basic collaborative filtering algorithm, which shows that the former can improve the resource recommendation precision with the characteristics of conciseness and quickness.

Conclusion

The main objective of this paper is to improve the basic similarity algorithm. First, on the basis of adopting the basic similarity algorithm, this paper combines the time effect and social trust relationship to make a preliminary improvement; then, this paper applies the hybrid optimization algorithm that combines the GA with the PSO which remedies each other’s shortcomings in the solving process; finally, this paper makes optimal computation on the initial data to generate the global optimal solution, which improves the similarity calculation precision. Depending on the complexity of the particular item, the next step will simplify the algorithm calculation to improve the efficiency in the large-scale and high-complexity project design and its implementation.