  Evolutionary algorithms (EAs) have been widely used to solve multi-objective
optimization problems, and have become the most popular tool. However, the
theoretical foundation of multi-objective EAs (MOEAs), especially the essential
theoretical aspect, i.e., running time analysis, has been still largely
underdeveloped. The few existing theoretical works mainly considered simple
MOEAs, while the non-dominated sorting genetic algorithm II (NSGA-II), probably
the most influential MOEA, has not been analyzed except for a very recent work
considering a simplified variant without crossover. In this paper, we present a
running time analysis of the standard NSGA-II for solving LOTZ, OneMinMax and
COCZ, the three commonly used bi-objective optimization problems. Specifically,
we prove that the expected running time (i.e., number of fitness evaluations)
is $O(n^3)$ for LOTZ, and $O(n^2\log n)$ for OneMinMax and COCZ, which is
surprisingly as same as that of the previously analyzed simple MOEAs, GSEMO and
SEMO. Next, we introduce a new parent selection strategy, stochastic tournament
selection (i.e., $k$ tournament selection where $k$ is uniformly sampled at
random), to replace the binary tournament selection strategy of NSGA-II,
decreasing the required expected running time to $O(n^2)$ for all the three
problems. Experiments are also conducted, suggesting that the derived running
time upper bounds are tight for LOTZ, and almost tight for OneMinMax and COCZ.
