论文研究-Multi-objective Optimization Algorithms for Point-of-Interest Route Planning in LBSN.pdf

所需积分/C币:10 2019-08-16 15:40:58 404KB .PDF

LBSN中兴趣点路径规划的多目标优化算法,许莹,郭昱杉,基于位置的社交网络(LSBN)为用户提供平台,以在便兴趣点(POI)上共享位置,照片或评论。如何挖掘这些共享信息以向用户推荐兴趣点或旅�
山国科技论文在线 http:/www.paper.edu.cn Then gcnctic algorithm is uscd to solve the problcm In this paper, we firstly model the POl route recommendation problem as a multi-objective oplimization problem with three objectives, including the user preference, the location popularity, and the travel distance. then the user check-in dataset from lbsn is used to mine user 95 personalized information and obtain thc uscrs prcfcrrcd POls at ccrtain pcriod of timc. By using collaborative filtering, the Top-k POls can be obtained as the candidate recommendation POls from each POI set. Next, four multi-objective route recommendation algorithms based on evolutionaryalgorithms, including MOEA/D-PR MOEA/d based POl Route), NSGA-II-PR (NSGA-II based POIRoute ), SPEA-II-PR(SPEA-Il based POiRoute), PESA-lI-PR(PESA-II 100 based POIRoute) have been designed to obtain a set of non-dominated Pareto solution which containing multiple poi travel routes. The performance of these four multi-objective route planning algorithms has been investigated and compared. Finally, experimental results demonstrate that our proposed algorithms have better performance compared with some existing algorithms with rcspcct to thc accuracy and diversity 105 The lbsn data from JiePang are used in this work. The dataset d=data,, data2, data3, data4, datas) represents user check-in records. datai =< u, t,l> is the ith check-in dala. where u is the user ID, l is the check-in Lime, l is the location, i.e a POI. For each 1, a vector <l(x, y), 1-namc, 1 - type, 1-c>is defined, where l(x, y) is 110 coordinates of I in which x represents the longitude and y represents the latitude, I-name is the location name, I-type is the location type Here location type =(V,F, e).I-cE typei is the sub-category of type For example, Venue can be schools, office buildings, scenic buildings, etc. Spor is thc sct of POIS, SPoI=(1,2,,i.,I rcprcscnts thc ith POI in Spor Route=(1,I2,.,i,. is the planned sequence of POls, i. e. a POi route, where each Iiis 115 selected from a POi set for a given time slot. In order to define the multi-objective POi route planning problem, some key notations are applied and described in Table 1 In this work we define the multi-Obicctivc POI Route Planning( mopoirp)problcm which concerns three objectives, including maximizing the popularity of POl, maximizing the location popularity, and minimizing the total travel distance as follows 120 1) Maximize user preference By calculating the visiting frequency of each location category at different time slots, the highest one at different time slots is regarded as the user preferred category at different time slots According to the previous results, all the Pols in St belong to the preferred category at time slot tk. In addition, St, is obtained by deleting locations with the distance d greater than dmar. Top-k 125 POIs from Sti are selected as the recommended POI set St, we calculate the user preference F(u, typei, C;, tk) for the sub-category c in typei at a given time slot tk as follows ∑!-cec;cont(u!;tk,) F(u, typei, Ci, tr) ount(u, Lk, l) where j=1, 2 ,.typeil, Itypeil is the number of categories for typei. The preference Ftk., of u to typei at time slot tk can be defined in Formula(2) 130 K F(u, typei, Cl,tk),, F(u, typei, Cn,tr)>(2) Where n=typel, F(u, type;, Cn,tk) for c; E type is calculated based on Formula(1) The preference of u for location I at time slot tk, denoted by like(u, tk, l can be calculated as 山国酬技论文在线 http:/www.paper.edu.cn follows lke(x,t,)=、a(D.-(3) 135 Because of the sparsity of user's check-in data, the user based collaborative filtering is used to estimate the user preference. Sim(u, 1, cj, tk) is defined as the similarity between user u and user v for location category Ci at time slot tk using the cosine similarily as follows Sim(u, V,Ci, tx) (4) (u, tk, L) is delined as user's preference of location I at time slot tk, where U(u, cj) is the set of similar users of u for location category c; R(u, tk,l) EucU(uc) Sim(u, v, c i. tk)like(v. tk D) We can obtain all preferred locations in St, using the above formulas. S'ti is formed by selecting Top-k POls from S Tab. 1 Key notations Symbol Dcscription D check-in Data sets S the set pol location represented b <longitude, latitude L- type location typc C the maximum distance that user can visit ar the time limit d(l1,l2) the distance between, and l2 stay(l) stay time at location l T(l1,l2) he travel time froml, and C the set of location categories check-in time the k-th time sl Route the Pol route, i.e. a sequence of ordered POls type =(V, F,E location types, V for Venue, F for Food, E for Entertainment The poi set for by deleting locations with th distance d grcatcr than dmax S Top-k POls from St, are selected as the recommended pol 145 2) Maximizelocationpopular Location popularily is lime-dependent. So, we calculate the popularity of all POis in St,. lor a certain month. Therefore, a time factor m is introduced to calculate the popularity H: H(,m)= VT(L,m) VT(L,m) VT (L, m) represents the visited times for location I in the mth month 150 Based on the above definition, mOPOiRP problem considers three objectives, including maximizing the total preferences (i.e. the sum of all Poi preferences in the recommended route) maximizing the total popularity (i.e. the sum of all Poi popularity)and minimizing the total travel distance (i.e. the sum of all distances in the route), can be defined as follow 4 山国科技论文在线 http:/www.paper.edu.cn f(0 Maximize the total user preference fi(D=Max >like(Li) 155 f2(1)Maximize the total popularity f2(=Me L f3(1)Minimize the total travel distance f3(0)=Min>d(1,4+1)+d(lo, L1) S. t d=ddo, li< dmax tatt tma 160 Here t1=2i1 stay(l1), t2=2i=o T(, i+i) n= Routel Based on the well-known MOEA/D, we propose MOEA/D-PR(MOEA/D based POI Route) to solve the mopoirP problem concerned in this paper. MOEA/d is a multi-objective 1 65 evolutionary algorithm combining mathematical programming with evolutionary algorithm. It decomposes the MOP problem into a number of scalar optimization sub-problems and then optimizes them simultaneously. To solve the MOPOirP problem, the populalion initialization and update process is designed as shown in Fig. 1. A route of POIs is a chromosome. Each gene in the chromosome corresponds to a location in the route. Fig. 1(a) represents a chromosome with five 170 genes that correspond to different locations. Fig. I(b)shows locations are randomly selected from different st. to construct a chromosome. Fig. I(c) shows four random initial routes have been generated. The basic operation of MOEA/D-PR is similar to MOEA/D. MOEA/D-PR is then designed to generate a set of non-domination solutions, i. e. POI routes, for the mOPoirP problem e( location1)(s+(S2→(Sn→ →tXSs)1) Routel fcnc(locati l2 4→M1XS→)l) Route iene( location Gene( locations) →+(S2…-S→+)-(s-S=) Routed S 〔b) 0n1 cations 175 山国科技论文在线 http:/www.paper.edu.cn Fig 1: The procedure of generating the POi route NSGA-II adopts the fast-non-dominance sorting algorithm, the congestion comparison operator and the elite strategy to improve the computation speed and robustness. Similar to the 80 MOEA/D-PR algorithm, NSGA-Il-PR (NSGA-II bascd POI Route) is proposcd to salve thc MOPOIRP problem. After the population initialization (see Fig. 1), the population is sorted according to the domination relation. For each generation, the offspring population is obtained through the roulette selection, crossover(Fig. 2(a)) and mutation (Fig. 2(b)). Based on the non-domination sorting, optimal solutions are added into the non-dominant solution set. This 1 85 procedure repeats until the termination condition is met. The set of POI routes are the non-dominated solution set obtained at the end of the algorithm SPEA-II is the improved strength Pareto evolutionary algorithm. which incorporates a fine-grained fitness assignment strategy, a density estimation technique and an enhanced archive 190 truncation method. SPEA-II has good performance in terms of the convergence and diversity Samc as the previous mcthod, SPEA-lI-PR(SPEA-lI bascd POI Route)is proposcd to solvc the MOPOiRP problem. The genetic operation of the population is shown in Fig. 2 S→2)S)Sn→b8S=)(S+)(5:-(Sx)(S-×)(Sn 5,…→1)(8-→ 间a) The crossover 195 )(SxA14)(S4小)(S Mutation (Si> 3 iS)isIs yip (b) The mutation Fig 2: The Evolutionary Operators A PESA-lI based algorithm PESA-ll-PR(PESA-lI based POI Route) is proposed to solve the MOPOIRP problem, where PESA-II is the improved Pareto-Envelope based Selection Algorithm Instead ofassigning the fitness lo an individual, the fitness in PESA-lI is assigned to hyper-boxes in the objective space. The objective space is divided into many boxes. Based on the population 205 initialization shown in F PESA-II-PR also uscs Ga to update the population. In ordcr to reduce the computational cost, PESA-lI uses the region-based selection to select points(solutions) in hyper-box within the objective space We used the lbsn dataset of user check-in records obtained from JiePang, where each entry 210 contains user ID, check-in time, check-in geographic coordinates, location name, location category and location type. We randomly select a set of 4248 anonymous users with at least 100 check-in 山国酬技论文在线 http:/www.paper.edu.cn records. Thc datasct includes a total of 1263 32 records Wc sct 80%o chcck-in records as thc training data. and the rest is used as the test data 215 Hitrate and Diversily are used to measure experimental resulls, which can be describedasfollow: I The hitrat Hitrate-EuculR(u)nT(u(7) Here, R(u is the number of different POIs in the recommended travel packages of user u 220 R(un T(uI is the number of recommended POIs, which appear in the verification set t(u) of Iser u 2) The Diversity A recommendation should provide diverse recommendation results to users. The diversity of recommendation result for user u is defined as 225 ∑1cR( uj, ii Similarity(ll Diversity= 1 R(tD)(R(u)-1) (8) Here, Similarity (li, li)means the similarity between location li and lj. If location li and lj belong to the same category, Similarity (i, li) is set as 1; otherwise, Similarity (li, lj) is set as 0 3)F-measure 230 F-measure combines precision and recall together with a harmonic mean. Here we use commonly used FB with B=1, i.e. F1. If the value of F1 is high, it means that the test method is eftective FB=(1+B2) PrecisionxRecall B2Precision+Recall Here, Precision =R(u)nT(uI/R(ul, Recall=R(u)nT(u/R(u), where T(u)are the 235 different POIs a user visited in the verification set and rlu) are the different POis in the recommended routes In order to determine the appropriate iterations for these four multi-objective algorithms, the Hitrate of these four algorithms is compared by setting different iterations from 50, 100 to 200 in Fig 3. According to the test result, these four algorithms can obtain better or similar results when 240 the number of iteration is set as 50. We calculate diversity defined in Formula(7)of these four multi- objcctivc algorithms, which show that all valucs arc distributcd in the rangc of (0.8, 1)as shown in Fig 4. It indicates that using the proposed algorithms can generate the diverse pol routes i.e. these pois belong to different categories. Thus, we set the number of iterations as 50 in all proposed algorithms In this group of experiments, the hitrate of four multi-objective POI route planning algorithms is comparcd in Fig 3. Hcrc, the horizontal axis indicates thc test group numbcr and thevertical axis represents the corresponding hit rate values. We can see that, for the MOPOiRP problem, our proposed NSGA-lI-PR obtained the highest Hitrate compared with other algorithms 250 From Fig. 4, we can see that the four multi-objective optimization algorithms have similar diversity besides, the F1-measure value of nsga-Il-Pr is also better than other three algorithms as shown in Fig. 5 7 山国酬技论文在线 http:/www.paper.edu.cn 0.9 0.8 7 0.0000 6543 0.2 0.1 BNSGA-II-PR OSPEA-II-PR EPESA-II-II-PR GMOEA/D-PR Fig 3: The comparison of Hitrate △ 0000 9876 △ 6 7 NSGA-IL-PR eCO-. SPEA-IL-PR 255 一x一 PESA-I-I-PR 尘=MOEA/D-PR Fig 4: Comparison of Diversity 000 876 0.5 0.4 3210 NSGA-l-PR國SPEA-- PR PESA-l-l-PR口 MOEA/D-PR Fig 5: The comparison ofFi-measure Experimental results in 9I showed that the performance of tRP is better than the random 260 method and the hottest method. Since NSGA-II-PR and SPEA-lI-PR have better performance among our proposed four multi-objective POi route planning algorithms, so we compare them with the statc-of-art algorithm trP in the litcraturc. fig. 6 shows nsga-lI-PR improves hitrate by 10% compared with TRP. SPEA-ll-PR also obtained better Hitrate on two out of the three test data sets. Fig. 7 shows the comparison of Fr-measure. NSGA-ll-PR obtained better FI-measure 265 results than other algorithms. Experimental results demonstrate that our proposed algorithms are competitive approaches for solving the moPoirP problem in LBSN 山国酬技论文在线 http:/www.paper.edu.cn 0 86420 6 7 SNSGA-I-PR O SPEA-II-PR TRP Fig 6: Comparison of Hitrate with TRP 000 0000 87654321 LONSGALILPR 3 ESPEAJIL-PR TRP 7 270 Fig. 7: Comparison of Fl-measure with TRP In this papcr, thc POi route planning problcm is modeled as a multi-objcctivc optimization problem by considering three objectives, including maximizing the user preference, maximizing the location popularity and minimizing the travel distance. Four new multi-objective optimization 275 algorithms including NSGA-II-PR, SPEA-II-PR, PESA-Il-PR, and MoEa/D-PR have been proposed for thc first timc to solvc the Multi-Objcctivc Optimization Poi route planning problcm Experiments on some real lbsn data set demonstrate SPEA-ll-PR obtained the overall best non-dominated solution set among the proposed four multi-objective Pol route planning algorithms. When considering the hit rate of recommendation, NSGA-1I-PR performed the best compared with other three multi-objective Poi route planning algorithms proposed in this paper and the trp algorithm in the litcraturc. In the future, we plan to further improve the multi-objective optimization algorithms by applying some machine learning approaches to solve the poi route planning problem 285 [1]Bao J. Zheng Y, and Mokbel M F Location-based and preference-aware recommendation using sparse geo-social networking data [A]. In Proceedings of International Conference on Advances in Geographic Information Systems[C]. 2012. 199-208 [2] Kojima N, Takagi T. Location Recom-mendation Incorporating Temporal and Spatial Effects[A]. In International Conference on Web Intelligence and Intelligent Agent Technology[C]. 2016. 280-283 290 [31 Yu Z, Feng Y, Xu H, and Zhou X. Recommending travel packages based on mobile crowdsourced data[ J1 IEEE Communications Magazine, 2014, 52(8): 56-62 [4 Liu B, Xiong H, Papadimitriou S, et al. A General Geographical Probabilistic Factor Model for Point of Interest Recommendation[J]. IEEE Transactions on Knowledge Data Engineer ering,2015,27(5):1167-1179 [5] Cheng C. Yang H, King I. et al. Fused matrix factorization with geographical and social influence in 295 location-based social networks[A]. AAAI Conference on Artificial Intelligence[C]. 2012 [6 Zhang Q, and liH MOEA/ D: A Multiobjec-tive Evolutionary Algorithm Based on Decomposition[J]. IEEE Transactions on Evolutionary Computation, 2007, 11(6): 712-731 .7 Deb K, and Jain IL. An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point-Based Nondominated Sorting Approach, Part 1: Solving Problems With Box Constraints[J]. IEEE E Transactions on 300 Evolutionary Computation, 2014, 18(4): 577-601 山国酬技论文在线 http:/www.paper.edu.cn [8]Xu Y, Ding O, Qu R, and Li K Hybrid multi-objective evolutionary algorithms based on decomposition for wireless sensor network coverage optimization[]. Applied Soft Computing, 2018, S1568494618301868 Pareto approach []. IEEE Transactions on Evolutionary Computation, 1999, 3(4): 257-2Y an [9]Zitzler E and Thiele L. Multiobjective evolutionary algorithms: a comparative case study and the strength 305 [10] Wang H G, and Liang M A Multi-objcctivc particlc swarm optimization[J]. Computcr Enginccring Applications, 2008, 45(4): 82-85 [11Varadharajan T K, and Rajendran C A. Multi-objective simulated-annealing algorithm for scheduling in flowshops to minimize the makespan and total flowtime of jobs [ J. European Journal of operational Research, 2005,167(3):772-795 310 2] Corne D w, JerramNR, Knowles J D, et al. PESA-II: Region-based Selection in Evolutionary Multiobjective A Conference on Genetic Evolutionary Computation(c]. 2001, 283-290 [13]Zheng Y. Tutorial on Location-Bascd Social Nctworks [A]. In proceeding of the 2lst International confcrcncc on World wide Web[]. 2012 14] Peng D, and Zhang C. Research on Intelligent Route Programming for DIY Travel[A]. In Proceeding of 315 Intermational Conference on Computer Sciences and Applications[c]. 2014. 350-35 5] Bao J, Zheng Y, Wilkie D, Mokbel M. Recommendations in location-based social networks: a survey[] Geolnformatica, 2015, 19(3): 525-565 16 Cheng C, Yang H, King l, et al. A Unified Point-of-Interest Recommendation Framework in Location-Based Social Networks[. ACM Transactions on Intelligent Systems Technology, 2016,8(1):10 320 [17] Xu G, Fu B, and Gu Y. Point-of-Interest Recommendations via a Supervised Random Walk Algorithm[J] EEE Intelligent Systems, 2016, 31(1): 15-23 8]Liu Y, Liu C, Liu B, et al. Unified Point-of-Interest Recommendation with Temporal Interval As-sessmen[A] In Proceeding of ACM SIGKDD Intemational Conference on Knowledge Discovery and Data Mining[C]. 2016 1015-1024. 325 [19] Lin S. Computer solutions of the traveling salesman problem[J]. Bell Labs Technical Journal, 2014, 44(10) 2245-2269 [20]Yu Z, Xu h, Yang Z and Guo B Personalized travel package with multi- point-of-interest recommendation based on crowdsourced user footprints[J]. IEEE Transactions on Human-Machine Systems, 2015, 1-8 [21]Kenteris M, Gavalas D, Pantziou G, Konstantopoulos C Near-optimal personalized daily itineraries for a 330 mobile tourist guide[A]. Computers and Communications[C]. 2015. 862-864 [22]Wu P, Zhu J, and Zhu L. Rcscarch on the travel route dcsign based on multi-objectivc planning and intelligent optimization algorithm J Mathematics in Practice and Theory, 2016. (15): 105-114 [23]Chen C; Zhang D, (iuo B, et al. Trip Planner: Personalized Trip Planning Leveraging Ileterogeneous Crowdsourced Digital Footprints[J]. IEEE Transactions on Intelligent Transportation Systems, 2015, 16(3) 33512591273 [24]Han Y, Guan H, Duan J Tour Route Multi-objective Optimization Design Based on the Tourist Satisfaction(J. Discrete Dynamics in Nature and Society, 2014(1): 1-8 [25 Hasuikc T, Katagiri H, Tsubaki H, ct al. Routc planning problcm with groups of sightsccing sitcs classified by tourist's sensitivity under Time-Expanded Network[A]. IEEE International Conference on Systems, Man and 340 Cybernetics[C]. 2014. 188-193 [26]Zhang Y J and Xu K L Multi-Objective Team Personalized Travel Design Based on Fuzzy APACA[I Computer Engineering and Applications, 2012, 48(35): 207-212. 345 中兴趣点路径规划的多目标优化 算法 410006 摘要 (LSBN) (POn 350 355关键词 LSBN POI 中图分类号:TP39 10

...展开详情
img

关注 私信 TA的资源

上传资源赚积分,得勋章
最新资源