非表示:
キーワード:
-
要旨:
We study the convergence behavior of (+)-archiving algorithms. A (+)-
archiving algorithm defines how to choose in each generation children from
parents and offspring together. Archiving algorithms have to choose
individuals online without knowing future offspring. Previous studies assumed
the offspring generation to be best-case. We assume the initial population and
the offspring generation to be worst-case and use the competitive ratio to
measure how much smaller hypervolumes an archiving algorithm finds due to not
knowing the future in advance. We prove that all archiving algorithms which
increase the hypervolume in each step (if they can) are only -competitive. We
also present a new archiving algorithm which is (4 + 2/)-competitive. This
algorithm not only achieves a constant competitive ratio, but is also
efficiently computable. Both properties provably do not hold for the commonly
used greedy archiving algorithms, for example those used in SIBEA, SMS-EMOA, or
the generational MO-CMA-ES.
