非表示:
キーワード:
-
要旨:
The core of hypervolume-based multi-objective evolutionary algorithms is an
archiving algorithm which performs the environmental selection. A (μ+λ)-
archiving algorithm defines how to choose μ children from μ parents and λ
offspring together. We study theoretically (μ+λ)-archiving algorithms which
never decrease the hypervolume from one generation to the next.
Zitzler, Thiele, and Bader (IEEE Trans. Evolutionary Computation, 14:58-79,
2010) proved that all (μ+1)-archiving algorithms are ineffective, which means
there is an initial population such that independent of the used reproduction
rule, a set with maximum hypervolume cannot be reached. We extend this and
prove that for λ<μ all archiving algorithms are ineffective. On the other hand,
locally optimal algorithms, which maximize the hypervolume in each step, are
effective for λ=μ and can always find a population with hypervolume at least
half the optimum for λ<μ.
We also prove that there is no hypervolume-based archiving algorithm which can
always find a population with hypervolume greater than 1/(1+0.1338(1/λ-1/μ))
times the optimum.