English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Evolutionary algorithms (EAs) have been widely used to solve multi-objectiveoptimization problems, and have become the most popular tool. However, thetheoretical foundation of multi-objective EAs (MOEAs), especially the essentialtheoretical aspect, i.e., running time analysis, has been still largelyunderdeveloped. The few existing theoretical works mainly considered simpleMOEAs, while the non-dominated sorting genetic algorithm II (NSGA-II), probablythe most influential MOEA, has not been analyzed except for a very recent workconsidering a simplified variant without crossover. In this paper, we present arunning time analysis of the standard NSGA-II for solving LOTZ, OneMinMax andCOCZ, 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 issurprisingly as same as that of the previously analyzed simple MOEAs, GSEMO andSEMO. Next, we introduce a new parent selection strategy, stochastic tournamentselection (i.e., $k$ tournament selection where $k$ is uniformly sampled atrandom), to replace the binary tournament selection strategy of NSGA-II,decreasing the required expected running time to $O(n^2)$ for all the threeproblems. Experiments are also conducted, suggesting that the derived runningtime upper bounds are tight for LOTZ, and almost tight for OneMinMax and COCZ.

Running Time Analysis of the Non-dominated Sorting Genetic Algorithm II (NSGA-II) using Binary or Stochastic Tournament Selection