Seite - 188 - in Intelligent Environments 2019 - Workshop Proceedings of the 15th International Conference on Intelligent Environments

Figure 9. Crowding Distance (RandomSolution) Figure 10. Crowding Distance (High initial resource) Figure 11. PoIs of Higashiya- ma-area 5.3. DiversityofSolutions Weusedcrowdingdistanceasan indicator toevaluatediversityof solutions.Thecrowd- ingdistancedistancei isdefinedasEq. (4). distancei= M ∑ m=1 (Em(i+1)−Em(i−1))/(Em(0)−Em(n)) i∈{2,...,n−1} (4) InEq.(4),n is thetotalnumberofsolutions,andEm,m=[money,time,stamina,satisfaction] is sorted evaluation values in ascending order. The boundary solutions are defined as distance1=distancen=∞. Thecrowdingdistance is calculated asManhattanDistance between theneighboring solutions, and crowdingdistances are equal in all neighboring pairs of solutions (except distance1 and distancen), if the distribution of solutions are completely uniform. When we compare the distribution of the crowding distances of randomly calculated solutions shown inFig. 9 and those at 500-thgenerationwithhigh initial resourcesshowninFig.10,wesee thatcrowdingdistancesofrandomlycalculated solutions have smaller crowding distances than that of high initial resource case. This result supports that solutionscalculatedwithhigh initial resourceshavehighdiversity. 5.4. ComputationTime Table3showsthecomputation time inonegenerationfor threedifferent initial resources cases.Whenwe use 500 generations, the total computation timewill be 1700 to 2900 seconds.This timemay lookvery long,butwestill believe that it is feasiblewhenplan- ningasatisfactorytour,byreducingthenumberofgenerationsandsoon.From the table, we see that our algorithm takesmore computation time inonegeneration in the caseof more initial resources assigned.This is because theprobability of lethal solutiongener- ation is higherwith low initial resources, because the lethal solutions are ignored at the crossoverandmutationsteps, thencomputation timedecreases. 6. Conclusion In this paper, we proposed the NSGA-II based Multi-Objective Genetic Algorithm to search the semi-pareto optimal solutions of the tour route search problem considering Table3. ComputationTime forOneGeneration (sec) N-DSort CrowdingSort Tournament Crossover Mutation Sum low 0.158±0.023 0.199±0.027 0.023±0.004 2.683±0.282 0.346±0.056 3.409±0.350 middle 0.210±0.041 0.261±0.049 0.023±0.004 3.596±0.625 0.454±0.101 4.544±0.773 high 0.266±0.082 0.325±0.089 0.023±0.005 4.610±1.281 0.579±0.179 5.803±1.576 Y.Hiranoetal. /AMethod forGeneratingMultipleTourRoutes188