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

4.1. Codingof solutioncandidates Figure1. Representationsofpathdata (right) and thecorrespondingTransportation type/PoIdata (left) Thesolutioncandidatesorsimplysolutions(i.e.,chromosomes)usedinouralgorithmare pathdata shown in the rightofFig. 1 that contains a seriesofmoves (i.e., transportation types) between twoconsecutivePoIs. These path data canbe converted toPoI data and transportation typedatashownin the leftofFig.1.Geneticoperations likeMutationand Crossover are applied to the PoI data and the transportation type data after converting from thepathdata. 4.2. DetailedAlgorithm The proposed algorithm consists of the following 6 steps and iterates Steps 2 to 6 for specified times (generations). 1. Initialization: First set thenumberofgenerations (iterations) toT, set thenum- ber of individuals (solutions) in initial population toN, and initialize the current generation number t=0 and searching populationQ0= /0. Next, create initial populationP0with randomlygeneratedpathdata. 2. Non-DominatedSort:GeneratenewpopulationRt=Pt∪Qt, andexecuteNon- Dominated sort forRt and classify all elements ofRt by their rank i (i.e., the numberofelementswhichdominate theelementunderconsideration).Todecide the rankof anelement, all elements in the set are compared in termsof stamina, time,money and satisfactionwhich are calculated for each element (path)with equations (1) and (2). Then, the classified elements of Rt are added to Fi(i= 0,..,n)according to their rank i. 3. Crowding Sort: Generate the next generation population Pt+1 by adding F0,F1,F2,... in thisorderwhilesatisfying thecondition |Pt+1|≤N. Inaddition, if |Pt+1|+|Fi|>N, applyCrowding sort toFi to addN−|Pt+1|better (i.e., higher diversity) solutions in Fi to Pt+1 . When the generation number t satisfies the condition t+1=T, thealgorithm is terminated. 4. CrowdingTournament: ApplyCrowding tournament based on stamina, time, moneyandsatisfactiontosolutionsinPt+1. It isappliedtorandomlyselectedN/2 pairs of 1-to-1 tournament to addN/2 better solutions to searching population Qt+1. 5. Crossover: Randomly choose N/4 pairs of solutions from Qt+1 and apply Crossover to them (Fig.4). Y.Hiranoetal. /AMethod forGeneratingMultipleTourRoutes184