An improved (1+1) evolutionary algorithm for k-median clustering problem with performance guarantee

Zhengxin Huang, Yuren Zhou, Xiaoyun Xia and Xinsheng Lai

Physica A: Statistical Mechanics and its Applications, 2020, vol. 539, issue C

Abstract: Evolutionary algorithms (EAs) have been widely studied in numerical experiments and successfully applied in practice. However, most existing EAs are designed without a theoretical analysis for their performance guarantee. In this paper, we define a fitness function to guide the well-known (1+1) evolutionary algorithm, called (1+1) EA, to optimize the NP-hard k-median problem. We prove that the (1+1) EA can obtain a performance guarantee of 5 for k-median problem in polynomial expected runtime O(mn2⋅dmax) if all distances between data points and cluster centers are integers, where m and n are respectively the cardinalities of the data set and cluster center set, and dmax denotes the largest distance between data points and cluster centers. To tackle the general case that the distances between data points and cluster centers are real number, we propose an improved (1+1) EA, which employs a distance scaling scheme during the evolutionary process. Our rigorous theoretical analysis shows that the improved (1+1) EA obtains a performance guarantee of 5+ε in expected runtime O(ε−1mn2log(m⋅dmax)), where ε>0 is a constant. This study reveals that an appropriate scaling scheme can help EAs to obtain a constant performance guarantee in polynomial expected runtime and provides insights into design EAs for some NP-hard problems. In addition, we conduct experiment to compare the efficiency of the improved (1+1) EA with three clustering algorithms on optimizing three UCI datasets.

Keywords: Evolutionary algorithms; Clustering; K-median problem; Performance analysis; Runtime analysis (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378437119316917
Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:phsmap:v:539:y:2020:i:c:s0378437119316917

DOI: 10.1016/j.physa.2019.122992

Access Statistics for this article

Physica A: Statistical Mechanics and its Applications is currently edited by K. A. Dawson, J. O. Indekeu, H.E. Stanley and C. Tsallis

More articles in Physica A: Statistical Mechanics and its Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().