KLP Not Always Efficient

by

Zeng, S., Ding, L., Yao, S. and Kang, L.

Literature search on Evolutionary ComputationBBase ©1999-2013, Rasmus K. Ursem
     Home · Search · Adv. search · Authors · Login · Add entries   Webmaster
Note to authors: Please submit your bibliography and contact information - online papers are more frequently cited.

Info: Late Breaking Papers at the 2004 Genetic and Evolutionary Computation Conference (Conference proceedings), 2004
Keywords:genetic algorithms
Abstract:
The size of the nondominated set of a vector set is greatly dependent on the size of the original vector set $N$ and the dimension of the vector $M$. Theoretical analysis [TA] shows that when $M=O(\log N)$ the original set has big nondominated set which may be the original set itself, and in the case $M=O(\log N)$, a classical algorithm (KLP) for finding nondominated set has complexity of KLP higher than $N^2$. Experiment verifies the analysis result as well. Therefore, we should avoid employing KLP when $M=O(\log N)$.
Notes:
Part of keijzer:2004:GECCO:lbp
URL(s):PDF

Review item:

Mark as doublet (will be reviewed)

Print entry




BibTex:
@InProceedings{zeng:2004:lbp,
author =       "Sanyou Zeng and Lixin Ding and Shuzhen Yao and Lishan Kang",
title =        "{KLP} Not Always Efficient",
booktitle =    "Late Breaking Papers at the 2004 Genetic and Evolutionary Computation Conference",
year =         "2004",
editor =       "Maarten Keijzer",
address =      "Seattle, Washington, USA",
month =        "26 " # jul,
keywords = "genetic algorithms",
url = {http://www.cs.bham.ac.uk/~wbl/biblio/gecco2004/LBP012.pdf},
abstract = "The size of the nondominated set of a vector set is
greatly dependent on the size of the original vector set $N$ and the
dimension of the vector $M$. Theoretical analysis shows that when $M=O(\log N)$ the original set has big nondominated set which may be
the original set itself, and in the case $M=O(\log N)$, a classical
algorithm (KLP) for finding nondominated set has complexity of KLP
higher than $N^2$. Experiment verifies the analysis result as
well. Therefore, we should avoid employing KLP when $M=O(\log N)$.",
notes =        {Part of keijzer:2004:GECCO:lbp},
}