IDEAS home Printed from https://ideas.repec.org/a/eee/phsmap/v539y2020ics0378437119316917.html
   My bibliography  Save this article

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

Author

Listed:
  • Huang, Zhengxin
  • Zhou, Yuren
  • Xia, Xiaoyun
  • Lai, Xinsheng

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.

Suggested Citation

  • Huang, Zhengxin & Zhou, Yuren & Xia, Xiaoyun & Lai, Xinsheng, 2020. "An improved (1+1) evolutionary algorithm for k-median clustering problem with performance guarantee," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 539(C).
    • Handle: RePEc:eee:phsmap:v:539:y:2020:i:c:s0378437119316917
    DOI: 10.1016/j.physa.2019.122992
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0378437119316917
    Download Restriction: 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
    File URL: https://libkey.io/10.1016/j.physa.2019.122992?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Orlin, James & Punnen, Abraham & Schulz, Andreas, 2004. "Approximate Local Search in Combinatorial Optimization," Working papers 4325-03, Massachusetts Institute of Technology (MIT), Sloan School of Management.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Pisut Pongchairerks, 2019. "A Two-Level Metaheuristic Algorithm for the Job-Shop Scheduling Problem," Complexity, Hindawi, vol. 2019, pages 1-11, March.
    2. Daya Ram Gaur & Ramesh Krishnamurti & Rajeev Kohli, 2009. "Conflict Resolution in the Scheduling of Television Commercials," Operations Research, INFORMS, vol. 57(5), pages 1098-1105, October.
    3. Gallego, Camilo A., 2022. "Intertemporal effects of imperfect competition through forward contracts in wholesale electricity markets," Energy Economics, Elsevier, vol. 107(C).
    4. Alekseeva, Ekaterina & Kochetov, Yuri & Plyasunov, Alexander, 2008. "Complexity of local search for the p-median problem," European Journal of Operational Research, Elsevier, vol. 191(3), pages 736-752, December.
    5. Ben Hermans & Roel Leus & Jannik Matuschke, 2022. "Exact and Approximation Algorithms for the Expanding Search Problem," INFORMS Journal on Computing, INFORMS, vol. 34(1), pages 281-296, January.
    6. Cemalettin Öztürk & F. Zeynep Sargut & M. Arslan Örnek & Deniz Türsel Eliiyi, 2017. "Optimisation and heuristic approaches for assigning inbound containers to outbound carriers," Maritime Policy & Management, Taylor & Francis Journals, vol. 44(7), pages 825-836, October.
    7. T Öncan & S N Kabadi & K P K Nair & A P Punnen, 2008. "VLSN search algorithms for partitioning problems using matching neighbourhoods," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(3), pages 388-398, March.
    8. Martin Gairing & Rahul Savani, 2019. "Computing Stable Outcomes in Symmetric Additively Separable Hedonic Games," Mathematics of Operations Research, INFORMS, vol. 44(3), pages 1101-1121, August.
    9. Chien, Steve & Sinclair, Alistair, 2011. "Convergence to approximate Nash equilibria in congestion games," Games and Economic Behavior, Elsevier, vol. 71(2), pages 315-327, March.
    10. Asaf Levin & Uri Yovel, 2014. "Local search algorithms for multiple-depot vehicle routing and for multiple traveling salesman problems with proved performance guarantees," Journal of Combinatorial Optimization, Springer, vol. 28(4), pages 726-747, November.
    11. Shuyang Sheng, 2020. "A Structural Econometric Analysis of Network Formation Games Through Subnetworks," Econometrica, Econometric Society, vol. 88(5), pages 1829-1858, September.
    12. Brad D. Woods & Abraham P. Punnen, 0. "A class of exponential neighbourhoods for the quadratic travelling salesman problem," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-30.
    13. Brad D. Woods & Abraham P. Punnen, 2020. "A class of exponential neighbourhoods for the quadratic travelling salesman problem," Journal of Combinatorial Optimization, Springer, vol. 40(2), pages 303-332, August.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:phsmap:v:539:y:2020:i:c:s0378437119316917. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.journals.elsevier.com/physica-a-statistical-mechpplications/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.