Page - 185 - in Intelligent Environments 2019 - Workshop Proceedings of the 15th International Conference on Intelligent Environments

6. Mutation:ApplyDecrementMutation to randomlychosenN/20solutions (Fig. 3), and apply IncrementMutation to otherN/20 solutions (Fig. 2). Then, go to step2after incrementing t.N/20waschosenbasedon thedefaultmutation rate 0.1used inNSGA-II. 4.3. Mutation In our algorithm, we designed twoMutation algorithms: one is to randomly insert one PoI and the other is to randomly remove onePoI in a solution so that diverse solutions are kept in terms of the number of PoIs.One of the algorithms is selected to use at the probabilityof0.5. IncrementMutation:As shown inFig. 2, first aPoI (PoI7 in the fuigure) is randomly chosen from the set of all PoIs except for the ones already in the solution and a trans- portation type leaving from the addedPoI (Car in thefigure) is randomly chosen.Next, the insert position in a solution is randomly chosen, andboth the chosenPoI and trans- portation typeare inserted. DecrementMutation: This algorithm is applied only to a solution with lengthmore than two. If the length ismore than two, as shown inFig. 3, the point to removePoI is randomly chosen (PoI 21was chosen in the figure) and the PoI and the transportation type leaving from thePoI (Car in thefigure) are removed. Figure2. IncrementMutation Figure3. DecrementMutation 4.4. Crossover We employ single-point crossover where a single cut point in each of two parents is randomly selected and the left (right) part of the parent 1 and the right (left) part of the parent 2 are swapped tomake newoffspring, as shown in Fig. 4.However, simply using the single-point crossover forour algorithm, it is likely togenerate lethal (invalid) solutionswhich include the same PoImultiple times. Hence, before concatenating the divided parts of the parent solutions, we try to reduce generation rate of such lethal solutionsbyrandomlyreplacingeitherof thePoIs includedintheleftpartofaparentand rightpartofanotherparent (middleofFig.4).Forconvenience,whenwedivideaparent solution into twoparts,we remove the incoming transportation type in the rightpart and add a randomly selected transportation typewhen concatenating the parts as shown in Fig.4. Y.Hiranoetal. /AMethod forGeneratingMultipleTourRoutes 185