Page - 188 - in Intelligent Environments 2019 - Workshop Proceedings of the 15th International Conference on Intelligent Environments
Image of the Page - 188 -
Text of the Page - 188 -
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 isdeïŹnedasEq. (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 deïŹned 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
Intelligent Environments 2019
Workshop Proceedings of the 15th International Conference on Intelligent Environments
- Title
- Intelligent Environments 2019
- Subtitle
- Workshop Proceedings of the 15th International Conference on Intelligent Environments
- Authors
- Andrés Muñoz
- Sofia Ouhbi
- Wolfgang Minker
- Loubna Echabbi
- Miguel Navarro-CĂa
- Publisher
- IOS Press BV
- Date
- 2019
- Language
- German
- License
- CC BY-NC 4.0
- ISBN
- 978-1-61499-983-6
- Size
- 16.0 x 24.0 cm
- Pages
- 416
- Category
- TagungsbÀnde