# Mobile Robot Path Planning with a Non-Dominated Sorting Genetic Algorithm
## 4 NSGA-II for the Multi-Objective Path Planning Problem
### Flowchart  
The process of NSGA-II is as follows:  
1. The population (_POP_) is initialized. 2. In the population (_POP_), the objectives of each individual are evaluated. 3. An empty set (_NDPOP_) is generated to save the found feasible non-dominated individuals. 4. While the termination condition has not been reached, DO: 1. Two empty populations (_NEWPOP_, _POPc_) are generated. 2. The individuals are chosen from the population (_POP_) by the selection operator and put into the population (_POPc_). 3. Individuals within the population (_POPc_) are paired. Then, the crossover operator is performed on the two individuals. Next, new individuals are generated and stored in the population (_NEWPOP_). 4. For any individual in the population (_POPc_), the practical operators are sequentially executed. Then, the generated individuals are put into the population (_NEWPOP_). 5. Each individual within the population (_NEWPOP_) is evaluated, and the feasible solutions are put into the set (_NDPOP_). Then, the non-dominated individuals of the set (_NDPOP_) are retained. 6. Parental and children populations (_POP_) and (_NEWPOP_) are merged. Individuals in the combined population are classified according to the individual feasibility: feasible solutions' set and infeasible solutions' set. Then, the non-dominated sorting and crowding distance metric are performed on the two sets respectively. Next, individuals are picked from the two sets, and a new population (_POP_) is formed. The size of the population (_POP_) remains the same. 7. The loop counter is incremented by one. In the entire algorithm, a viable individual is a collision-free path. Steps 1-3 are the initialization process. The initial population (_POP_) is generated and evaluated. An empty set (_NDPOP_) is then made to store the found non-dominated solutions. This set is only used for storage and does not participate in the evolution of the population. Step 4 is the core of the algorithm, and the total iterative process is completed in this step until the termination condition is reached. In each iteration, two empty populations (_POPc_ and _NEWPOP_) are created. The population (_POPc_) is used to store the selected individuals of the parental population (_POP_). The population (_NEWPOP_) stores the children individuals. First, the selection operator is applied to choose individuals from the population (_POP_), and the selected individuals are stored in the population (_POPc_). Individuals of the population (_POP_c_) are then paired. New individuals are generated by using the crossover operator and then placed in the child population (_NEWPOP_). Next, a series of operators is executed for each within the population (_POPc_). When each operator is applied, a new individual is generated and stored in the child population (_NEWPOP_). After the individuals in the population (_POPc_) are treated with the evolutionary operators, the individuals in the children population (_NEWPOP_) are evaluated, and the feasible individuals are put into the set (_NDPOP_). Then, individuals of the population (_NDPOP_) are updated; in other words, the non-dominated solutions of the population (_NDPOP_) are retained; other individuals are excluded. Then, the elite strategy is executed. The parental population (_POP_) and the offspring population (_NEWPOP_) are merged, and the individuals in the merged set are classified according to individual feasibility: feasible solutions' set and infeasible solutions' set. Then, the non-dominated sorting and crowding distance metric are performed on the two sets, respectively. Then, individuals are picked from the two sets to form a new population (_POP_). In this step, the infeasible individuals are notentirely discarded, but some better individuals are preserved. Besides, the size of the population (_POP_) is unchanged. Then, the loop counter is incremented by one. Step 4 is iterated until the end condition is satisfied. At this point, the entire algorithm ends, and the set (_NDPOP_) is output. Furthermore, the operators are introduced.